一种移动边缘云计算任务卸载算法

查易艺 袁 烨 李金湖 柳 欢 陈振兴 李 进

1(国网江苏省电力有限公司信息通信分公司 江苏 南京 210024)

2(江苏电力信息技术有限公司 江苏 南京 210024)

3(国网信通亿力科技有限责任公司 福建 福州 350003)

4(江苏大学计算机学院 江苏 镇江 212013)

0 引 言

移动智能手机的普及使得诸如面部识别、移动健康监测、增强现实和移动游戏等复杂的交互式应用越来越多地运行于移动设备端[1]。此类应用的执行需要高速的处理资源，从而得到较快的响应时间，提高用户体验[2-3]。面对此类需求，移动边缘云计算及其任务卸载(Task Offloading)技术应运而生[4-5]。应用移动边缘计算技术，可以将移动用户设备方复杂的计算任务从移动设备上卸载至资源能力更加强大的边缘云服务器上执行，借助于边缘云的资源优势，得到更快的响应时间，并节省移动设备能耗[6-8]。然而，移动设备与边缘云间的无线通信环境对于任务卸载性能会产生重要影响[9-10]，且会直接影响到移动用户设备进行任务卸载的决策。

目前，任务卸载问题已有一些研究。考虑到5G时代移动设备计算需求的巨大增长，文献[11]为了改善能效，设计了一种基于博弈理论的分布式任务卸载算法。文献[12]在多信道环境下研究了面向多用户的计算卸载决策问题，但以上文献均忽略了信道通信时的干扰问题。为了节省移动设备能耗，满足应用执行的延时约束，文献[13]提出了一种基于Lyapunov优化技术的动态卸载算法，能以较低的计算复杂度获得近似最优解。在大规模移动应用环境下，文献[14]以最小化平均任务执行延时为目标，研究了多用户的应用分割与卸载问题，并设计了离线式卸载决策算法。为了解决任务卸载面临的传输延时和能耗问题，文献[15]设计了一种基于马尔可夫决策过程的朵云任务卸载算法。然而，由于受限的无线网络覆盖问题，朵云环境无法确保服务提供的连续性，无法应用于移动边缘云中的卸载决策问题。类似地，文献[16]同样利用马尔可夫决策过程对服务迁移的序列卸载决策问题进行了形式化描述，并设计了求解算法。考虑到受限的无线信道数量和通信干扰问题，文献[17]基于博弈论设计了一种分布式卸载决策算法，文献[18]联合考虑通信资源和计算资源分配，设计了迭代式任务卸载算法。

然而，以上方法在其性能和灵活性上有一定限制，算法的复杂性导致其不一定适应于大规模无线网络环境。移动边缘云环境下，无线访问点(基站)通常在多信道环境下，若过多的移动设备同步选择相同信道进行任务卸载，通信干扰将严重影响数据传输性能，进而导致任务执行延时增加和移动设备能耗增加。此时，任务卸载将得不偿失，即：任务卸载决策必须同步考虑通信资源和计算资源的分配。为了解决此问题，本文将设计基于能效的任务卸载决策算法，并重点解决：1) 考虑能效和延时的情况下，哪些移动用户任务适合于进行卸载；2) 从全局最优的角度，对于需要进行卸载的任务，如何选择合适的无线信道进行任务卸载。

1 系统模型与优化目标

移动边缘云计算(Mobile Edge Computing, MEC)包括三个组成部分：移动边缘云服务器，无线访问点AP和移动用户设备。结构如图1所示。移动用户可将本地任务通过Wi-Fi、4G或5G通信方法通过无线访问点提交至边缘云服务器执行，即任务卸载。假设N={1,2,…,N}表示移动用户集合，M={1,2,…,M}表示无线访问点AP可提供的无线信道集合，且每个移动用户拥有一个任务执行需求。用户任务具有两个属性，表示为Ti=(Oi,Di)，i=1,2,…,N，其中，Oi表示完成用户i的任务需要的总CPU周期数，Di表示用户i任务的数据量。用户任务Ti可在移动设备上本地执行，也可以通过卸载方式传输至边缘云端执行。

图1 移动边缘云计算结构

(1)

根据移动设备的CPU能量模型[19]，任务本地执行的能耗可表示为：

(2)

式中：αi、βi、χi均表示CPU能量模型的参数，不同类型和处理能力的CPU拥有不同的取值。

若移动用户将任务通过无线信道卸载至边缘云执行，则整个任务执行过程由三个部分组成。

(3)

令ψ=(ψ1,j,ψ2,j,…,ψN,j)表示所有移动用户的卸载决策解，移动用户i选择无线信道j上传数据的速率计算为：

(4)

(5)

(6)

2) 无线访问点AP通过高速有线网络将任务负载数据传输至边缘云服务器，该部分的传输延时可忽略不计。

(7)

若任务在边缘云执行，移动用户设备需要等待返回结果，此时移动设备的空闲能耗计算为：

(8)

因此，任务卸载至边缘云执行的总体能耗为：

(9)

任务卸载至边缘云执行的总时间为：

(10)

为了优化任务卸载执行的能效，需要合理地进行通信资源和计算资源的分配。故任务卸载决策的能效最优化可形式化为：

(11)

约束条件为：

(12)

(13)

(14)

(15)

ψi,j={0,1} ∀i∈N,j∈M

(16)

其中：式(12)确保任务卸载执行的能耗应小于或等于任务本地执行能耗；式(13)确保任务卸载执行的时间应小于或等于任务本地执行时间；式(14)确保无线信道的通信质量，为信道设置门限值π可以避免过多的移动用户方同时访问同一信道，增加数据冲突；式(15)表明移动用户仅能选择访问一条无线信道；式(16)表明任务仅能在本地执行或边缘云上执行。

2 能效任务卸载算法

为了求解式(11)的最优化问题，本文设计了一种能效任务卸载算法。算法由两个部分组成：(1) 决定移动用户分类和优先级；(2) 根据优先级，移动用户依次获得通信资源分配。

2.1 移动用户分类和优先级确定

根据任务数据量、负载密度、计算能力以及能耗，移动用户可划分为两类。第一种类型的移动用户为本地执行任务的移动用户，令Ul表示该类型用户。当移动用户单独占用一个信道时，该移动用户设备的数据传输速率可表示为：

(17)

(18)

换言之，若任务卸载执行的能耗大于本地执行能耗，则移动用户划分为第一类用户Ul。

令Uo表示为第二种类型用户，为除了第一种类型用户外的其他用户。属于Uo的移动用户可选择在本地执行任务或卸载至边缘云执行，其最终决策取决于信道的通信质量。对于该类型移动用户，在卸载决策过程中需设置不同的优先级，按其优先级依次作出卸载决策，将优先级定义为：

(19)

算法1为移动用户分类与优先级确定过程。

算法1移动用户分类与优先级计算

2. 输出：移动用户分类集合Ul和Uo，移动用户优先级η={ηi},i∈Uo

3. For 移动用户i=1 toNdo

4. For 信道j=1 toMdo

5. 根据式(17)和式(18)分别计算移动用户独占用一条信道时的数据传输速率和能耗

7. 移动用户i归属于类型Ul

8. else

9. 移动用户i归属于类型Uo

11. end if

12. end for

2.2 基于拍卖的卸载机制

图2 拍卖示意图

传统的拍卖过程中，资源分配是通过多轮的竞标过程确定最终的赢家。然而，这种多轮拍卖并不适用于本文的场景，因为这会导致移动用户任务执行中过多的等待延时。本文采用单轮拍卖以改进能效，降低任务卸载延时。

资源分配中，结合资源和竞标者给出的价格信息，移动用户可以决定哪条信道成为拍卖赢家，并确定最终的资源交易价格bj。因此，此时的最优化问题即可转换为拍卖问题，ψi,j表示拍卖结果，ψi,j=0表示无拍卖赢家，ψi,j=1表示信道j赢得拍卖。而算法目标也相应地可转化为是最大化移动用户的效用，形式化为：

(20)

为了确定拍卖赢家和资源分配关系，首先需要计算拍卖参与者的竞标密度并对其排序。对于给定的无线信道，无线信道可根据其竞标密度进行降序排列。对于移动用户，最低的竞标密度即表示最优的通信质量。定义作为卖方的信道的竞标密度为：

(21)

移动用户向卖方支付的最终交易价格为bj，即为赢家无线信道发送的竞标价格。此时，移动用户的效用函数为：

(22)

若移动用户没有参与拍卖，其效用值为0。换言之，若ψi,j=0，则U=0。而作为卖方的无线信道的效用函数可表示为：

(23)

若无线信道没有赢得拍卖，则ψi,j=0，显然其效用也为0。

拍卖过程如算法2所示。

算法2基于拍卖的任务卸载决策算法

1. 输入：分类移动用户Ul和Uo，及优先级η

2. 输出：移动用户的卸载决策解ψ=(ψ1,j,ψ2,j,…,ψN,j)

3. 设置临时集合U’o=Uo

4. whileU’o≠

5. 选择移动用户i,i=argmax{ηi}i,i∈Uo}

6. for 信道j=1 toM

8. ifπj>0 then

9. 根据二元组(bj,sj)计算信道j的竞标密度bdj(式(21))

10. 设置竞标密度bd={bdj}

11. whilebd≠

12. 选择信道j,j=argmin{bdj}j

14.ψi,j=1

//更新信道门限值

16. else

17.ψi,j=0

18. end if

19.bd=bdj

//计算竞标密度时将信道j移出集合bd

20. end while

21. else

22.ψi,j=0

23. end if

24. end for

25.U’o=U’oi

//移出信道j，更新第二种类型移动用户

26. end while

3 实验分析

通过仿真实验评估算法性能，选择基于竞争的博弈卸载算法GOCA[20]、基于用户满意度的卸载算法USOA[21]以及本地执行算法LA作为对比算法。GOCA将任务卸载问题建立了任务执行期限和信道速率约束的竞争博弈模型，在竞争有限的通信资源的同时，最小化能耗，通过一种基于纳什均衡的方式得到了移动用户的卸载决策解。USOA引入一种效用函数，根据系统吞吐量、能耗以及执行延时描述的用户满意度进行最优的通信资源选择，并最终得到其卸载决策解。LA选择将所有任务均在本地设备上执行，以此衡量任务卸载执行的优势。选取平均能耗、延时和移动用户设备上的系统吞吐量作为性能评估指标。

3.1 实验环境搭建

在MATLAB环境中搭建以下实验环境：无线访问点AP的覆盖半径设置为2 km，并拥有4条无线信道，信道带宽设置为1 MHz，信道噪声功率σ2=-100 dBm，路径衰减因子设置为2。若干移动用户设备随机分布无线访问点的覆盖区域中，边缘云服务器位于无线访问点附近。实验利用四种类型的移动设备进行仿真分析，包括Galaxy Note、Galaxy Note2、Nexus S和Galaxy Nexus，不同的移动设备其CPU处理能力均不相同，相关参数配置如表1所示。实验将随机选择若干台移动设备部署于无线访问点附近，且每台移动设备均有一个任务执行需求。任务类型包括面部识别、病毒扫描、在线游戏和虚拟现实等。每台移动设备上随机分配一种任务类型，不同类型的移动设备处理不同类型任务时具有不同的处理能力和速度，对应参数配置如表2所示，包括负载密度、数据大小及分配的处理能力。

表1 移动设备类型及参数

表2 任务类型及参数

3.2 实验结果

图3为四种算法的移动设备的平均能耗结果，移动设备数量选择200、400、600、800、1 000进行结果观察。可以看到，本地执行算法LA的平均能耗约为22.1 J，其他三种基于任务卸载的算法得到的能耗均小于LA，说明任务卸载可以带来能效的优化。在200个移动设备情况下，三种卸载算法的能耗分别为6.42、6.5和6.95。随着移动设备数量的逐步增加，平均能耗分别增加至11、12.6和14.5 J，这是由于此时过多的移动设备同步选择访问相同的无线信道进行任务卸载，进而导致了过多的信道冲突。由信道速率的计算公式可知，过多的信道冲突会降低信道通信质量和计算卸载的数据传输速率。因此，在1 000个移动设备情况下，会有越来越多的用户选择本地执行方法，进而导致平均能耗逐渐增加。总体来说，本文算法可节省约56%的能耗。而在三种基于卸载的算法中，本文算法也具有一定的优势，原因在于基于拍卖机制的任务卸载决策方法是以更长周期的方式得到任务卸载决策，以更加合理的方式在满足用户质量需求的情况下为移动用户分配通信资源。同时，在移动设备相对较少时，能耗节省效果也更加明显。随着移动设备数量的显著增加，由于负载拥塞，本文算法性能有所下降，但仍优于GOCA和USOA。

图3 平均能耗

图4为移动用户执行任务的平均延时情况。本地执行算法的平均延时约为27.5 s，在移动设备数为200时，另外三种算法的平均延时分别约为14.6、14.7和15.5 s。比较本地执行算法，卸载算法至少可节省约45.6%的延时。在1 000个移动设备情况下，四种算法得到的延时分别为19.6、20.06、20.84和27.5 s。本文算法依然是所有算法所用延时最少的。

图4 平均延时

图5为三种任务卸载算法的移动设备上吞吐量的变化情况，由于LA算法仅在本地进行任务执行，无需进行数据传输，其吞吐量始终为0。从结果可以看出，尽管本文算法在初始情况下吞吐量更低，但随着移动设备的增加，其吞吐量下降的趋势要慢于对比算法，最终超过对比算法。随着移动设备数的增加，相应的信道通信干扰也将增加。相应地，数据传输速率有所下降，导致卸载能耗高于本地执行能耗。因此，更多的移动设备将倾向于采用本地执行策略取代任务卸载。总体来说，本文算法在大规模移动设备的测试中得到的吞吐量高于两种对比算法。

图5 平均吞吐量

综合仿真实验来看，在无线访问点及其无线信道数量固定的情况下，可以支持仿真实验环境设置的不同规模移动设备量的任务执行与卸载需求。但在有限的无线信道条件下，势必会导致任务执行延时和平均能耗的增加，以及平均吞吐量的降低。原因在于：移动设备量越多，负载将出现拥塞，信道争用将越剧烈，数据传输时间势必变长，相应传输能耗也将增加，单位时间内系统完成的任务量则相应减少。在实际应用环境中，单个无线访问点在其覆盖范围内所能支持的移动设备数量则与访问点自身的处理能力和支持的无线信道数量相关。

4 结 语

为了优化移动设备的能耗，本文基于移动边缘云计算环境提出了一种基于能效的任务卸载决策算法。算法综合考虑信道干扰、任务本地执行延时以及执行能耗，将任务卸载决策问题形式化为0-1非线性整数规划问题。为求解该问题，设计了移动用户分类和优先级确定机制，利用拍卖理论求解了任务卸载决策，并确定了所选任务卸载信道。仿真实验表明，在能耗、延时以及吞吐量三个指标上，本文算法均优于对比算法。