面向多应用的绿色卸载与处理方案研究

张竣铭，王俊义，彭 捷，李 然

(桂林电子科技大学 信息与通信学院，广西 桂林 541004)

0 引言

随着物联网技术的快速发展,大量新型物联网应用也随之迅速发展,激发包括人脸识别、VR、AR在内的时延敏感、计算密集型应用广泛应用于智慧城市等场景,极大地促进了信息化社会进程[1]。但由于终端设备的有限计算资源和有限的功率供应,无法全面满足所有的物联网时延需求。为解决上述问题,移动边缘计算(Mobile Edge Computing, MEC)应运而生。MEC在接入网端部署有限的计算资源并允许终端设备将应用请求通过接入节点上传到边缘云端进行处理,旨在实现低时延的应用响应[2]。

然而部分终端设备由于有限的功率供应无法将应用请求实时通过接入节点上传到边缘云端,因此为充分利用终端设备上的计算资源进而提高网络容量,终端设备可以将应用请求上传到其他空闲的终端设备进行处理(D2D卸载模式)[3]。同时考虑到实际情况中,多应用请求面对有限的计算资源存在激烈竞争,导致大量应用请求仅获得少量的计算资源,进而导致应用请求失效。因此为扩展系统服务能力并降低系统功耗,合理协调多个应用请求的处理顺序是有效的方式之一。

已有的文献中,单终端设备场景下的边缘计算卸载研究中涉及移动视频流服务性能以及基于无线电力传输的节能研究[4-5]。文献[6]考虑了D2D卸载模型对降低单个应用请求时延的影响,证明了终端设备间的协作卸载机制对实现快速的应用响应具有重要作用。文献[7-10]考虑了多终端设备场景,文献[7-8]分别对多终端设备场景的MEC系统中的安全性和节能问题进行研究。文献[9-10]进一步考虑到了终端设备之间的协作机制(D2D卸载),文献[9]考虑了2个终端设备,通过终端设备间的毫米波通信技术显著降低了网络延迟并提高了网络容量;文献[10]进一步研究了利用ETSI多址的多终端设备间D2D辅助卸载机制,以实现实时的网络服务。此外,维持系统的长效性能也十分重要。因此文献[11]考虑了多用户MEC系统的动态缓存、计算卸载和计算资源分配问题,并考虑基于流行度的边缘缓存策略,最小化成本函数的长期平均值。然而考虑到现实情况中,应用请求的产生时刻具有差异性,因此文献[12]考虑了应用请求的不同到达时间,提出一个基于激励机制的任务卸载框架,然后提出的定价算法通过考虑在边缘计算节点上的延迟成本来给出最优的计算定价和卸载方案。进一步,文献[13]考虑在边缘计算节点上应用请求的处理顺序,在有限计算资源下提高有效卸载量,应用处理过程被建模为M/M/1/B队列,证明了合理协调应用请求的处理顺序有利于提高系统的卸载性能。然而目前已有的工作还未充分探究基于D2D辅助卸载的MEC系统中应用处理顺序对系统带来的影响,有待进一步探究。

为解决上述问题,本文首先提出了一个基于D2D辅助卸载的移动边缘计算模型,其中包括本地卸载、D2D辅助卸载和卸载到边缘云端3种卸载模式,然后构建在终端设备和边缘云端上面向多应用的应用处理顺序模型,最小化终端设备总功耗,以实现绿色卸载目标。对于这个终端设备总功耗最小化问题,基于贪婪配置思想和冒泡排序思想,并通过分析不同应用请求对等待时延的容许能力及其对总功耗的影响,提出了绿色卸载与应用处理排序算法(Green Offloading and Application Processing Sorting Algorithm, GOAPSA),实现了最小化所有终端设备的总功耗,充分发挥了终端设备间辅助卸载和灵活调整应用处理顺序的优势。

1 模型构建与问题建模

1.1 系统模型

图1 D2D辅助的MEC模型Fig.1 D2D-assised MEC model

1.1.1 应用卸载模型

(1)

(2)

1.1.2 应用响应时延模型

(3)

(4)

终端设备m的应用请求通过无线通信链路上传到终端设备m′后,应用处理时延可表示为:

(5)

(6)

(7)

(8)

1.1.3 功耗模型

(9)

(10)

(11)

1.1.4 应用处理顺序模型

图2 终端设备m的应用请求处理时间轴Fig.2 The timeline of application requests for terminal equipment m

(12)

(13)

(14)

(15)

(16)

1.2 问题建模

综上所述,本文考虑终端设备有限的计算资源、有限的功率供应和应用请求处理的时延约束,最小化系统终端设备的总功率消耗。总体优化问题可规划为如下P1问题:

P1中共包含3类决策变量,分别为卸载决策变量α,卸载功率分配变量Poff和应用处理顺序变量Q={Q1,Q2,…,QM,QC}。上述问题P1中,C1和C2为卸载决策变量约束,约束C3表示终端设备的计算资源有限,约束C4表示有限的终端功率供应,C5表示所有应用请求的时延约束。

2 问题求解与算法设计

问题P1表明,总功耗最小化问题涉及卸载决策变量α、卸载功率变量Poff和应用处理顺序变量Q,其中卸载决策变量α为0～1变量,卸载功率分配变量为实数决策向量,应用处理顺序变量为离散决策空间变量,且变量之间存在耦合关系。显然P1问题为NP-hard问题,求解具有挑战性。因此本文基于贪婪配置思想和冒泡排序算法思想,给出了如下的GOAPSA。

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

本文具体算法如算法1所示。

算法1:GOAPSA1. 输出:最优的任务卸载决策α∗,卸载功耗决策Poff,∗,应用处理顺序变量∗。2. 对所有终端设备m∈,如果cm≤Cm,ϕmcm≤Pm,令m(1)=m。3. Repeat4. 根据式(20)对∀m∈求出对应的can-offm。5. 对∀m∈令αmm′=1,其中m′=argmaxm″∈{can-offm,C}hHm,m″。6. 求出over={m∈∑m′∈offmαm′mcm′>Cm∪Pm>Pmaxm},即过度使用的终端设备集合。7. Whileover≠⌀8. For i=1 toover9. 对m∈offi求出其最小卸载功率向量Poff-minm={Poff-minm,1,Poff-minm,2,…,Poff-minm,M,Poff-minm,C}。10. 根据式(23)求出{msend,mreceive},令αmsendm=0,αmsendmreceive=1。11. End for12. End while13. Until∪m∈can-offm=⌀∪over=⌀14. 对∀m∈,C,所有的最大容许时延排序表示为tw-maxm1≤tw-maxm2≤…≤tw-maxmoffm,令Qm(i)=mi其中∀m∈offm,i∈[1,2,…,offm]。15. For i=1 to M16. For j=1 to offi17. For z=1 to offi-j18. If twaiti(i(z+1))+Tsumi(z)hHi,i(z+1)219. 交换i(z)以及i(z+1)。20. End if21. End for22. End for23. End for21. 对∀m∈,根据式(25)和式(26)求出Poffm(i),m。

3 算法复杂度分析

4 仿真结果与分析

本节主要展示了GOAPSA仿真结果及分析。证实了GOAPSA通过灵活调整终端设备的卸载决策、卸载功率决策和应用处理顺序决策,有效降低了所有终端设备的总功耗并提高了有效的应用请求数量。展示了GOAPSA在节能以及有效服务应用请求数量上的优势,对比了2种常见的计算卸载算法,包括只将应用请求卸载到边缘云端或本地处理的贪婪计算卸载算法(GCOA_E)和随机应用处理顺序的贪婪卸载算法(GCOA_Rand)。

4.1 仿真场景设置

在本文的仿真中,设置接入节点的覆盖半径为300 m[17],其中终端数量M=80均匀分布在覆盖范围内[17]。对于终端设备而言,其计算资源上限Cm=[0.5,2]×109cycle[18],最大的功率供应为5 W。

4.2 仿真结果

图3展示了本文提出GOAPSA迭代次数与终端设备数间的关系,显然随着终端设备的数量增加,GOAPSA的迭代次数也随之增加。当终端设备数较大时(例如终端设备数为70或80时),本文的迭代次数维持在80左右,具有较快的收敛速度。

图3 算法迭代次数 v.s. 终端设备数Fig.3 The iterations of GOAPSA vs the number ofterminal devices

图4 系统总功耗v.s.CmFig.4 Total system power consumption vs Cm

图5 有效服务终端个数v.s.CmFig.5 The number of effective applications vs Cm

图6、图7和图8展示了本文提出的GOAPSA在充分利用终端设备间的D2D协作卸载以及灵活调整应用处理顺序的优势。具体来说,在图6中,随着终端设备的增多,3种算法的系统总功耗都逐渐增加。这是因为终端设备的增加意味着应用请求和系统计算资源上限的增多,此时更多的计算资源被使用以满足更多应用请求的时延需求,进而造成了系统总功耗的增加。同时由图6可得出,在本文提出的GOAPSA控制下的系统总功耗小于GCOA_Rand这一结论。图7表明在GOAPSA控制下,有效服务应用请求的数量大于GCOA_Rand,证实了在GOAPSA的控制下,通过灵活调整应用请求的处理顺序可以有效降低系统总功耗并提高有效服务的应用请求个数。此外,图7和图8显示,相比于GCOA_E,在本文提出的GOAPSA控制下的系统可以充分利用终端设备上计算资源(即更高的终端设备计算资源利用率)来为更多应用提供有效的服务(即更高的有效服务应用请求数)。

图6 系统总功耗v.s.终端设备数Fig.6 Total system power consumption vs thenumber of terminal devices

图7 有效服务的终端设备数 v.s. 终端设备数Fig.7 The number of effective applications vs thenumber of terminal devices

图8 终端设备计算资源利用率v.s.终端设备数Fig.8 The computing resource utilization rate on terminaldevices vs the number of terminal devices

5 结束语

本文研究了MEC系统下面向多应用的计算卸载、传输功率分配和应用处理方案的联合设计,创新性地探究了终端间的计算共享机制以及多应用的处理顺序对计算资源利用率以及终端设备总能耗的影响,分析了多应用请求对时延的容许能力,因此在面向实际中多个不同种类的应用请求时,分析其对时延、计算资源等因素的需求状态,可以实现对多应用的有效服务。仿真实验证明本文通过充分探究终端设备间的计算共享机制并灵活调整应用请求的处理顺序可以有效降低系统的总功耗,并提高有效服务的应用请求数量,为实际中计算资源有限的MEC系统下的高效计算资源部署和配置方案提供了一种新的思路和解决方案。