多设备间任务依赖的最佳卸载决策和资源分配①

胡 恒, 金凤林, 谢 钧, 刘 莹

(陆军工程大学 指挥控制工程学院, 南京 210007)

随着物联网技术和5G技术的发展, 产生的各种新型应用, 对网络的时延和带宽提出了更高的要求. 但由于终端设备的计算和存储能力的限制, 无法处理和存储如此庞大的数据. 因此移动边缘计算[1]应运而生,MEC能有效解决时延长、能耗高和数据不安全等问题. 其中计算卸载技术[2]作为MEC的关键技术之一,通过合理的卸载决策和资源分配策略将终端设备上运行的任务卸载到边缘服务器, 能够减少任务完成时延和设备的能耗, 提高设备性能. 而通过将D2D技术与MEC结合, 可以更进一步降低数据传输时延和能耗.

对于计算卸载技术, 目前已经出现了很多研究成果对其进行研究. 文献[3]提出了一种低复杂度的启发式算法来最小化共享频谱中的任务执行延迟. 文献[4]考虑了具有辅助节点的MEC系统, 联合优化了用户和辅助节点的计算和通信资源分配, 使总能耗降至最低.文献[5]基于一种低复杂度的算法来降低设备能耗. 文献[6]使用线性规划的方法解决卸载决策、延迟和能耗联合优化问题. 文献[7]为了最大程度地减少任务等待时间和能耗, 提出了一种启发式算法, 该算法保证了子任务之间的依赖性并提高了任务效率. 文献[8]提出了一种基于Lyapunov优化的低复杂度的动态计算卸载在线算法, 获得了最优的卸载策略. 文献[9]考虑了包含多个忙碌智能设备和多个空闲智能设备的D2D与MEC协作系统, 基于块坐标下降法和凸优化技术的两阶段迭代算法解决卸载决策和资源分配的联合优化问题, 获得最佳卸载策略和资源分配策略, 最小化了系统的总能耗. 文献[10]建立了一个具有通信资源和计算资源约束的混合整数非线性问题, 开发了一种优化算法来解决此问题. 文献[11–13]同样考虑了在MEC环境下引入D2D技术进行协作, 来考虑任务的卸载情况 .

然而以上文献都仅考虑了单个设备上任务的卸载情况. 对于不同设备之间任务具有依赖性的研究非常少, 几乎没有. 实际上, 在不同设备上执行的任务通常也是具有相关依赖性的. 文献[14]虽然考虑了MEC系统环境下两个不同设备之间的任务相关性, 但没有考虑与D2D技术进行协作来优化系统性能. 虽然业内也在MEC环境中引入了D2D技术来优化系统性能,但是对于MEC与D2D技术协作网络环境中不同设备任务之间任务具有相关性的研究, 就作者目前所知, 还没有相关文献对此方面进行研究. 同时, 在优化卸载决策方面文献[14]提出的算法复杂度仍然很高, 本文提出的线性搜索算法更进一步的优化了卸载决策, 并且本文将场景扩展到多设备. 因此, 本文在文献[14]的基础上进行了进一步的优化研究, 联合优化了设备任务完成时延和能耗.

本文在第1节中对系统进行了分析, 建立了通信、计算和任务依赖模型. 在第2节中运用凸优化方法得到最佳资源分配. 在第3节中提出了一种降低复杂度的线性搜索算法来优化卸载决策. 最后通过仿真实验进行性能评估.

1 系统模型

1.1 MEC与D2D协作网络系统模型

本文考虑了多个设备的MEC与D2D协作网络.如图1所示, MEC与D2D协作网络系统模型. 其中ds和d2分别表示设备S、设备2与MEC服务器之间的距离, 其中,S=1,3,4,···,s, 表示设备1, 设备3, …,设备s,d(S,2)表 示设备1 ,3,4,···,s和设备2之间的距离.

图1 MEC与D2D协作网络系统模型

设备S和设备2分别具有ms和n个要执行的任务,其中ms表示设备S的第m个任务. 将任务之间的依赖关系建模为顺序图, 对每个设备引入两个虚拟任务, 0为设备的输入任务,ms+1和n+1为输出任务, 如图2所示. 其中设备2的第k个子任务的输入依赖于设备S第ms个任务的输出和设备2第k–1个任务的输出.

图2 不同设备间调用图模型

采用 {Li,j,Ii,j,Oi,j}来描述每个设备的每个任务, 其中j=S或2,j=S表示设备S=1,3,4,···,s,j=2表示设备2,i表示设备上的任务,i=0,1,2,···,ms+1或i=0,1,2,···,n+1.Li,j表示任务的计算量, 完成任务总共需要的CPU周期,Ii,j表示计算任务的输入数据的大小,Oi,j表示任务的输出数据的大小. 对于设备S和设备2第0个和最后一个虚拟任务计算量为0. 同时对于设备而言, 第0个任务输入数据的大小为0, 最后一个任务输出数据的大小为0. 对于设备S和设备2第i个任务的输入等于上一个任务的输出:Ii,j=Oi-1,j. 特别的是,对于设备2的第k个任务的输入依赖于设备2的第k–1个任务和设备S第ms个 任务的输出:Ik,2=Ok-1,2+Oms,s. 本文规定第0个和最后一个虚拟任务只能在本地执行. 同时,ai,j={0, 1}表示卸载决策:ai, j=0表示在本地执行,ai,j=1表示在服务器执行.

1.2 通信模型

对于每个设备分配带宽相等的正交信道, 用W表示, 卸载和上传设备之间互不干扰:

其中,pi,j表 示设备j的发射功率,hi,j表示设备j到边缘服务器的信道增益, σ2表示设备的噪声功率程.

下载速率为:

其中,p0表示边缘服务器的固定发射功率.

设备S与设备2之间的传输速率为:

其中,和分别表示设备S第ms个任务的输出与设备2的第k个任务都在本地执行时, 设备的发射功率和此时设备间的信道增益.

信道增益为:

其中,g表示天线增益,Fc表示载波频率,dr表示距离,dr=dS或d2或d(S,2),pl表示路径损耗指数.

1.3 计算模型

下面给出了执行和传输任务的时间和能耗.

本地执行任务i的完成时间:

其中,fi,j表示执行任务i的CPU计算能力.

本地完成任务i所消耗的能耗:

其中,k是取决于芯片架构的有效开关电容参数, 是固定常数.

服务器执行任务i的完成时间:

其中,f0表示服务器的恒定CPU频率.

将任务i从设备传输到服务器的上传时间:

将任务i从设备传输到服务器的传输能耗:

由文献[15]可知式(9)是关于的凸函数.

从服务器返回到设备的下载时间:

将任务从设备S传输到设备2的传输时间:

将任务从设备S传输到设备2的传输能耗:

1.4 依赖模型

由于设备S的第ms个 任务的输出作为设备2第k个任务的输入, 所以要综合考虑设备S第ms个任务和设备2第k个任务的位置关系. 通过综合分析, 设备S的第ms个任务和设备2的第k个任务的位置关系都有4种:当设备S第ms个 任务和设备2第k个任务都在本地执行时, 第k个任务的输入依赖于第ms个任务的输出, 由于两设备都支持D2D技术, 所以设备之间可以直接通信,设备S不必将第ms个任务的输出先传递到边缘服务器,然后再又服务器传递到设备2, 节省了时间和能耗, 此时只有设备间的传输时间和能耗; 当设备S第ms个任务和设备2第k个任务都在服务器上执行时, 此时设备没有传输时间和能耗的损耗; 当第ms个任务在本地执行时, 当第k个任务在服务器上执行时, 由于第k个任务的输入依赖于第ms个任务的输出, 此时设备S需要将第ms个任务的输出传输到服务器, 有上传时延和能耗; 当第ms个 任务在边缘服务器执行, 第k个任务在本地执行时, 此时设备S需要将第ms个任务的输出从服务器传输到设备2, 此时需要下载时延.

1.5 问题公式化

由以上分析可知, 设备S的任务完成时间为:

由于设备间任务的依赖关系, 在式(14)的最后一行关系式中描述了设备间任务的依赖关系. 当设备S第ms个任务和设备2的第k个任务都在本地执行时, 则设备之间需要传输能耗当设备S第ms个任务在本地执行, 而设备2的第k个任务在服务器上执行时, 则需要上传能因此设备s的能耗为:

由于设备2的第k个任务输入依赖于设备S的第ms个 任务和设备2第k–1任务的输出, 当设备S第ms个任务和设备2的第k个任务都在本地执行时, 设备间需要传输时间当设备S第ms个任务在服务器执行, 而设备2的第k个任务在本地执行时, 则需要下载时间当设备S第ms个任务在本地执行, 而设备2的第k个任务在服务器上执行时, 则需要上传时间因此设备2的第k个任务等待设备S的第ms个任务的输出时间为:

等待设备2第k–1个任务的输出时间:

设备2的任务完成时间为:

设备2消耗的能耗为:

设备总性能指标为:

所以问题公式化为式(20):

其中,Ppeak表示设备发射功率的峰值,fpeak表示设备CPU计算能力的峰值. 由式(5), 式(8), 式(11)可知所以式(20)可以转化为:

由于含有二进制变量ai,j, 所以问题是非凸的, 但当固定ai,j时, 原来的非凸问题就会转化为关于的凸问题.

2 固定卸载决策的最佳资源分配

假设固定ai,j, 则非凸问题P(2) 转化为关于的凸问题P(3):

问题P(3)的拉格朗日表示为:

其中, λ1,λ2,···,λs都是不小于零的表示与相应约束相关联的对偶变量, λ1*,λ2*,···,λs*表示最佳对偶变量, 则能推导出每个设备的最佳CPU频率和发射功率的闭合表达式如下:

W(x) 表示函数LambertW, 应用梯度下降法迭代更新, 直到满足一定的停止标准. 该方法的伪代码如算法1所示. 由于是P(3) 一 个固定ai,j的凸问题, 梯度下降法保证收敛.

算法1. 固定卸载决策下求解最佳资源分配算法λsλ2 α pre 1. 输入: 给定大于0的 , , 步长 和精度值p*,f*2. 输出:3. While True:fi,j 4. 根据最佳CPU频率的闭合表达式(24)计算pi,j 5. 根据最佳发射功率的闭合表达式(25)计算fi,j pi,j Twait s Twait 2 6. 根据 和 分别计算 , 和目标值t=max{Twait s ,Twait2 }7.λs 8. 根据梯度下降算法, 分别更新 的值|Twait s -Twait2 |＜pre 9. 如果 :10. 退出循环11. End

3 优化卸载决策

在第2节中, 给定卸载决策, 可以得出最佳资源分配, 需要搜索 2m1×n×m3×···×ms次卸载决策, 然后从中选择最小目标的卸载决策. 但是随着任务任务的增多, 这种遍历搜索方法是行不通的, 复杂度会很高. 基于此提出了一种降低复杂度的线性搜索算法, 可以在线性时间内获得最佳卸载决策.

3.1 一次爬升策略

定理1. 假设f0＞fpeak, 则最优卸载决策具有连续性(如果有任务要卸载), 即对于最优决策, 如果设备有任务需要卸载到边缘服务器, 那么在整个任务的执行过程中, 任务卸载到边缘服务器只会发生一次, 它被称为一次爬升策略.

证明: 由于文章篇幅限制, 并且有许多文献都有证明了一爬策略, 这里就不再证明.

3.2 基于一爬策略的线性搜索算法

在本小节中, 借鉴了文献[16]的思想, 同时基于一次爬升策略提出了一种低复杂度的线性搜索算法, 来优化卸载决策. 首先根据式(27)证明所有卸载点共享最小加权和点, 然后在找到最小加权和点的基础上寻找入口任务, 只需将两点之间的任务包括两点, 都卸载到服务器, 如图3所示.

图3 一次爬升策略

公式如下, 设备有m个任务:

其中, ηi表 示任务i到最小加权和点o的 最佳性能,η(i,o)表示任务从入口任务i到出口任务o的加权和.eu: 传输能耗,el: 本地能耗,tu: 上传时间,tc: 在服务器上的执行时间,td: 下载时间,tl: 本地执行时间, βE和 βT分别代表权重.

定理2. 所有卸载点共享最小加权和点o.

证明: 假设当任务i=j时最小加权和点为o,1≤j≤o≤m, 那么j+1 的最小加权和点也是o.

当i=j, 卸载任务j时:

卸载任务j,j+1时:

卸载任务j,j+1,j+2 , …,o时:

卸载任务j,j+1, …,m时:

因为当i=j时 , 最小加权和点是o, 所以:

当i=j+1, 卸载任务j+1时:

卸载任务j+1,j+2 , …,o时:

卸载任务j+1,j+2 , …,m时 :

当i=j, 最小加权和点为o, 仔细观察可以得出当i=j+1时 , 最小加权和点也是o, 即:

从而得出所有卸载点共享最小加权和点o, 证毕.

从定理2可知, 只需遍历i=1就可以找到最小加权和点o, 同时得到此时的最佳性能为η1=η(1,o), 然后根据ηi与ηi-1的关系, 求出η1,···,ηo, 通过式(37)找到入口任务h.

基于定理1和定理2, 可以通过提出的线性搜索算法快速地找到最小加权和点o和入口任务h. 算法2给出了寻找最优的入口任务h和最佳性能点o的算法, 初始时, 任务全部在本地执行. 因此只需要枚举满足一次爬政策的卸载决策, 而不必遍历所有 2m1×n×m3×···×ms个卸载决策. 对于每个设备, 根据算法2首先遍历m个任务寻找到最佳性能点o, 然后再根据每个卸载点的关系,求出每个卸载点到最佳性能点o的值, 选出最小的作为卸载点, 算法的复杂度为O (m). 其他设备类似. 所以只需O(m1×n×m3×···×ms)的复杂度就可以找到最优的卸载策略. 随着任务数的增多, 基于单爬策略的线性搜索算法的性能远远优于暴力搜索算法, 复杂度更低, 算法2描述如下.

算法2. 低复杂度线性搜索算法η(1,1) ηmin=η(1,1)o 1. 输入: 根据式(33)计算令 , =1 ho 2. 输出: ,i m 3. For ←1 to :f* p*4. 根据算法1计算出最优 和5. 然后分别计算设备能耗和时间η(1,i)6. 根据能耗、时间和式(26)计算η(1,i) ηmin 7. If ＜ :ηmin=η(1,i)o=i 8.9. End i o 10. 找到=1时的最小加权和点η1=ηmin 11.j o 12. For ←2 to :ηj ηj-1 ηj 13. 根据 与 的关系公式计算出 的值14. End ηh=max{η1,···,ηo} h 15. 根据公式 选出入口任务

4 实验评估

在这一节, 将进行数值模拟来评估所提的卸载算法, 关注的性能指标是两设备的总性能(时延和能耗的加权和最小), 用ETC表示, 其中每个设备的性能用设备完成任务所消耗的能耗和时间的加权和表示, 实验数据值的大小参考了文献[14]进行了设置.

图4为每个设备的任务调用图, 每个节点代表一个任务, 节点权值为完成此任务的计算量, 边权值表示输入和输出数据的大小. 这里将设备1、设备2和设备3的实际任务数量分别设置为3、4和5, 每个设备引入了两个虚拟任务. 服务器的发射功率p0固定为1 W,每个设备的发射功率峰值Ppeak为0.1 W, 边缘服务器的CPU频率fc和每个设备的CPU频率峰值fpeak分别为1010和108(cycles/s), 噪声功率 σ2为10–7W,k是取决于芯片架构的有效开关电容参数, 是固定常数, 这里设置为10–26. 此外设置带宽W为2 MHz. 对于每个设备上任务的计算量大小设置为Li,1=[0, 65.5, 40, 3, 96.6, 0](Mcycles),Li,2=[0, 70.8, 95.3, 86.4, 18.6, 158.6, 0](Mcycles),Li,3=[0, 65.5, 86.4, 158.6, 96.6, 0](Mcycles).

图4 实验模型和参数

根据第3节列出的信道增益公式, 公式中的一些参数设置为:g=4.11表示天线增益,Fc=915 MHz表示载波频率,dr表示距离,r=1,2,3,(1,2),(3,2)对于设备1、设备2和设备3到服务器的距离d1、d2、d3的值别为100 m、100 m和100 m.设备1到设备2和设备3到设备2之间的距离d(1,2)、d(3,2)的值分别为10 m和10 m,pl=3表示路径损耗指数. 这里将每个设备的时间和能耗权重分别设置为0.05, 0.95, 0.1, 0.9, 0.02, 0.98.

在图5中, 首先进行了本文所提的算法和一爬策略枚举搜索算法的比较. 通过图5可以观察到, 随着任务数的增多获得最佳卸载策略所花费的时间, 本文所提算法的性能要优于一爬枚举搜索算法. 在相同的任务数下, 本文所提的算法获得最优卸载策略的时间明显小于一爬策略枚举搜索算法明.

图5 两种算法对比曲线图

接下来, 本文给出了当d1、d2和d(1,2)变化时, 不同算法下设备的性能, 其中设置=0.0 5、=0.1和0.02. 为了进行性能比较, 考虑了3个次优算法作为基准. 第1种算法被称为所有任务卸载, 其中将3个设备中的所有任务卸载到边缘边缘服务器上执行. 对于第2种算法被称为所有任务本地执行, 3个设备中的所有任务都在本地执行. 此外, 本文将没有D2D技术支持称为第3种算法, 也算是文献[14]算法的一种实现, 其中每个设备最小化自己的性能ETC.

从图6(a)可以观察到, 当固定其他距离时, 随着距离d1越来越大, 本文所提算法要优于另外3种卸载算法, 性能更好. 而任务全部在本地执行算法和本文所提算法性能都没有变化, 是因为对于任务全部在本地执行算法, 此时设备1的第m个任务与设备2的第k个任务都在本地执行, 而两个设备都支持D2D技术, 可以直接进行通信, 所以距离d1增大, 对于任务全部在本地执行的性能是没有影响, 而本文所提的算法获得的最优卸载决策设备1的任务也都是在本地执行, 所以也不受距离d1变化的影响. 另外两种算法, 所有任务卸载和无D2D技术支持算法都随着距离的增大, 性能越来越差, 因为当距离d1增大时, 卸载任务到服务器需要花费更高的传输时延和能耗. 同时也可以观察到, 当服务器和设备距离小于160 m时, 全部卸载算法要优于无D2D技术支持算法, 因为服务器的性能更好, 设备距离服务器更近时, 将任务全部卸载到服务器, 能获得更短的时延和更低的能耗. 但不管距离如何增大, 本文所提算法都要优于其他算法.

图6(b)显示了距离d2变化对设备性能的影响. 从图中可以观察到本文所提算法、全部在服务器执行算法和无D2D技术支持算法, 设备ETC性能都随着距离的增加而增加. 虽然随着距离的增加, 性能变差, 但是本文所提算法还是优于服务器执行算法和无D2D技术支持算法. 同时从图中可以观察到, 当距离小于130 m左右时, 全部卸载算法还要优于无D2D技术支持算法. 而全部在本地执行算法, 总的ETC不变

图6 与其他算法的对比

图6(c)显示了距离d(1,2)变化对设备性能的影响.对于任务全部在本地执行算法和本文所提算法有明显的影响, 因为此时设备1的第m个任务与设备2的第k个任务都在本地执行, 而两个设备都支持D2D技术,两设备可以直接进行通信. 所以随着距离d(1,2)的增大,任务全部在本地执行算法和本文所提算法性能越来越差, 但本文所提算法还是优于全部在本地执行算法. 另一个方面也可以得出, 当两设备间距离更近时, 设备间直接通信越节省时间和能耗. 而对于全部卸载算法和无D2D技术支持算法, 由于本次设备1的第m个任务与设备2的第k个任务都在服务器上执行, 所以距离d(1,2)的变化, 对于这两种算法都不受影响. 类似的当d3和d(3,2)变 化时, 能够得到与d1和d(1,2)变化时类似图6(a)和图6(c)的结果, 这里不再过多叙述.

通过以上对比分析, 本文所提的算法明显优于其他基准算法, 同时与D2D技术协作可以显着提高系统的性能.

5 结论与展望

本文研究了MEC与D2D技术协作系统环境下不同设备之间具有任务依赖性的最优的资源分配和优化任务卸载决策问题, 来最小化设备的能耗和任务完成时间的加权和, 为了解决该问题, 提出了一种低复杂度的在线任务卸载算法, 获得了最优计算卸载策略. 最后通过数值实验表明, 本文所提的算法明显优于其他基准算法. 下一步将对多设备多服务器场景进行研究.