移动边缘计算中的协同计算卸载策略

李 顺，葛海波，刘林欢，陈旭涛

西安邮电大学 电子工程学院，西安 710121

随着网络时代的来临，网络设备的使用量呈爆发式增长。人们在移动设备上执行任务时对数据速率和服务质量的要求越来越高，卸载任务的类型也越来越复杂，如增强现实（augmented reality，AR）、手势识别、人脸识别等[1]，这些应用不仅是计算任务密集型，而且对时延要求敏感。随着技术的发展，尽管现在移动设备的中央处理器（CPU）速率已经得到很大的提升，但在需要大量计算资源的应用面前在短时间内也是无能为力。移动云计算（mobile cloud computing，MCC）中将计算资源需求量大的任务卸载至远端具有强大计算能力的云服务器中，能够在保证时延和能耗的前提下高效的解决这一问题。由于云服务器与用户之间距离较远，在传输过程中由于各种因素的影响导致高时延问题，为了解决这一问题，业内学者将目光聚焦到移动边缘计算（mobile edge computing，MEC）上来[2]，MEC 将远端服务器的计算和存储资源迁下沉到用户端，降低计算任务传输时延和能量消耗，并且对计算资源需求量很大的任务，直接将其传输到远端计算能力更强的云服务器中执行。MEC 靠近用户端设备但计算能力有限，MCC 远离用户端设备但其计算能力巨大，两者相互协作能够满足不同的应用场景。

计算卸载作为MEC 的主要优势之一，成为广大研究人员的关注热点[3]。在现有的移动边缘计算任务卸载的研究中，用户将任务卸载至边缘服务器或者云服务器，忽略了附近拥有计算资源的边缘服务器，导致这部分计算资源的浪费。将任务卸载至边缘服务器时，边缘服务器之间作为一个协同的整体对卸载的任务进行计算，能够有效减少向远程云传输的时间成本。

本文中结合MCC和MEC的优势，将边缘服务器及其附近边缘服务器看作一个协同整体，任务选择卸载至本地、本地边缘服务器、附近边缘服务器中以及云服务器中计算。将任务卸载中传输时延与能耗建立模型，并分别赋予权重值，通过改进的混合粒子群算法找到最优解，并得到最优的卸载策略。

随着5G的迅速发展以及普及，MEC的发展和研究迎来了新的高度。在MEC 的研究中，计算卸载技术一直备受关注，大量的学者也对其进行了研究并有了突破性的进展[4]。文献[5]提出一种无线感知联合调度和计算卸载的策略（joint scheduling and compute offloading，JSCO），通过在移动端和云端并行处理的方式，减少了执行时间，并将优先关系和总执行时间作为约束条件，以此来权衡能耗。文献[6]研究了具有小型网络的MEC系统节能计算卸载策略，通过联合优化功率、无线和计算资源分配等因素最小化终端能耗，将卸载问题表述为NP-hard的MINLP问题，提出了一种基于遗传和粒子群（hierarchical genetic algorithm and particle swarm optimization based computation algorithm，HGPCA）的计算卸载策略。但在文中重点考虑了能耗问题，时延问题有所忽略。文献[7]提出一种基于粒子群优化的卸载策略，将任务卸载表示为能耗约束下的时延最小化问题，并通过惩罚函数平衡时延和能耗。文章中只考虑了时延敏感型的应用，对于能耗方面的关注不足。文献[8]研究了协同计算卸载、计算和通信资源分配方案，开发了一个协同计算框架，考虑了卸载策略、计算资源等因素提出一种基于管道的策略，并采用经典的逐次凸逼近（successive convex approximation，SCA）方法将非凸优化问题转化为凸优化问题。文献[9]针对网络节点的计算能力与现实通信资源之间的差异，根据距离的远近以及网络节点密度的疏密，提出基于遗传算法的近岸多节点协同卸载策略和远岸基于分组交叉粒子群可容错卸载策略。文献[10]考虑了延迟、内存、可用能量以及智能设备的传输能量等约束，通过非线性约束优化问题，提出一种元启发式算法的部分计算卸载策略。文献[11]实现复杂依赖应用的低能量迁移问题，在子任务关系的基础上构建能量最小化的划分模型，并从任务迁移、执行位置和电量剩余三个方面出发提出一种基于遗传算法（fine-grainedtask migration energy-saving strategy based on genetic algorithm，FGMBGA）的卸载策略，通过调整任务能耗和手机电量来动态调整最优解。文献[12]为了使用户独立选择卸载决策，提出一种基于博弈论的分散计算卸载算法，并且在卸载过程中将问题转化为部分观测型的马尔可夫决策过程（partially observed markov decision processes，POMDP），并通过基于策略梯度深度强化学习（deep reinforcement learning，DRL）来解决此问题。文献[13]研究了在云边协作系统中，将通信和计算资源共同分配问题转化为凸优化问题，最终得到资源分配策略。能够看出文献所提策略有效减少设备的时延，但对能耗问题关注度相对较少。综合上述文献研究总结对比如表1所示。

表1 不同卸载策略总结对比Table 1 Comparison of different uninstall strategies

综上所述，以上计算卸载策略问题的研究，大多只对时延或能耗进行优化，亦或对任务之间的依赖关系没有考虑。另外，大部分工作只针对移动边缘计算或者移动云计算的卸载策略进行研究，并没有考虑MEC 与MCC 之间的协同。综合考虑上述研究的局限性，本文设计了一种云边协同的计算卸载策略，并提出了CRPSO计算卸载算法。主要工作如下：

（1）为防止任务无序执行时导致服务器负载过高，无法很好地执行卸载策略，很大程度上影响卸载进度，考虑了任务之间的依赖关系，并使用任务的优先级矩阵表示任务执行的先后顺序，优化卸载效率。

（2）在任务卸载时，利用MCC 和MEC 各自的传输时延和计算能力特点，将任务采用就近原则卸载，总体考虑移动设备、边缘服务器和云服务器的计算资源，将计算任务卸载至附近有计算资源的边缘服务器中，形成边缘服务器间的协同卸载，合理利用本地端、边缘端和云端服务器的计算资源。

（3）设计了基于改进混合粒子群算法的计算卸载算法，利用改进后的算法对粒子进行分组交叉迭代后得到最优卸载策略，从而得到最小系统总代价。

2.1 通信模型

本文提出的移动云计算融合MEC的网络通信框架模型如图1 所示，分为三层：用户层、边缘计算层、云计算层。其中，云计算层有高性能的服务器群组成，具有强大的计算能力并且能够协同管理边缘层服务器之间的资源；
边缘计算层由小型基站以及具有一般计算能和存储能力的边缘服务器组成；
用户层可根据自身设备计算和存储能力计算一定范围内的任务。

2.2 计算卸载模型

假设用户在进行任务卸载时的卸载决策：

本地执行：计算任务在本地用户设备执行。

边缘服务器执行：通过无线网络将计算任务卸载至边缘服务器或者周边具有计算能力的边缘服务器执行。

云服务器执行：云服务器具有强大的计算能力。

假设由n个任务T={ }T1,T2,…,Tn。其中每个任务被建模为一个三元组{ }αi,βi,γi，其中，αi表示任务Ti的输入数据量，βi表示任务计算的数据量，γi表示为反馈计算任务结果的数据量。移动设备、边缘端和云端服务器的计算力（单位：GHz）分别为fl、fe、fc；
移动设备、边缘服务器和云服务器计算1 bit 数据所需CPU 周期分别为Clb、Ceb、Ccb。其中本地与异地边缘服务器计算能力相同。

在任务执行的过程中，移动服务中往往不只存在一个任务，任务与任务之间存在依赖关系，所以在任务卸载时要考虑任务卸载的优先关系。引入n×n的任务卸载优先级矩阵D来表示任务i与任务j的优先关系：

由于用户产生的任务数量的不固定性，任务之间的关系也是不确定的，由此可以根据具体数量和关系自定义矩阵，如图2 所示为3.2 节中7 个任务的优先级矩阵。例如，D23=1，则说明任务2优于任务3先执行；
D26=0，说明任务2 与任务6 之间无约束关系；
D56=-1，说明任务6优于任务5先执行。

（2）卸载至边缘服务器执行

将任务卸载至边缘服务器时，边缘服务器可以看作一个感知节点，若边缘服务器过载，则可以将任务卸载至附近资源较多的边缘服务器进行计算，然后将结果回传给用户端。根据Shannon公式，移动用户与边缘服务器的通信传输速率为：其中，l2为本地边缘服务器与异地边缘服务器之间的距离。

任务i从本地边缘服务器卸载至异地边缘服务器执行时，时间延迟为：其中，l3为用户设备与云服务器之间的直线距离，Be为用户设备与云服务器之间的信道带宽。

任务i从本地设备卸载至云服务器执行时，总时延为：

本文的目标是任务执行总时间和设备的总能耗最小时的卸载策略。因此，目标函数定义如式（15）：

将粒子群优化算法（particle swarm optimization，PSO）应用到移动用户任务卸载的现实场景中，传统粒子群算法容易早熟，导致局部最优解[14]。为了解决这个问题，本文中引入遗传算法中的交叉操作，将粒子根据适应度进行分级，适应度低的粒子经过交叉重组后得到适应度好的粒子进入适应度高的等级中，这样得到的种群中的粒子适应度较优。因此，在粒子群算法快速收敛并保持较好的全局搜索能力的同时，结合遗传算法选择交叉的思想能够提高算法的精度，并跳出局部最优。

3.1 传统粒子群算法

粒子群算法是一种常见的传统智能算法，在PSO算法中设置粒子种群数量，粒子的位置与速度。第i个粒子的位置Xi和速度Vi分别表示目标优化问题的解和粒子i位置的更新方向以及距离，Pbest表示粒子i自身最优位置，Pgbest表示整个种群搜索到的最佳位置。在每次迭代中，粒子i速度和位置更新公式如式（16）、（17）：

其中，c1、c2为学习因子；
r1、r2为0～1 之间的随机数；
ω为惯性因子（ω较大则全局搜索能力强，ω值较小时局部搜索能力强）。

3.2 粒子编码

本文采用浮点数编码方式，每个粒子对应任务分配方案。文中用0、1、2、3表示4种不同的卸载方案，0表示任务在本地设备执行，1表示任务在边缘服务器执行，2表示任务在异地边缘服务器执行，3表示在云服务器执行。假设任务集合有7 个任务（n=7）T={T1,T2,T3,T4,T5,T6,T7}，对应的粒子编码为χ=[1.1，2.0，3.2，4.0，5.1，6.1，7.3]，其中整数部分表示任务Ti{i∈[1,n] }；
小数部分表示任务的执行位置（取整数）。例如编码χ=[1.1，2.0，3.2，4.0，5.1，6.1，7.3]，根据上述编码过程可知：T4和T2在本地执行（任务t4先于t2执行可根据关系矩阵判定）；
T1、T6、T5在边缘服务器执行；
T3在异地边缘服务器执行；
T7在云服务器执行。

3.3 适应度函数

本文中所要解决的问题的是得到最优的卸载策略，由建立的模型可知，目标函数值f越大，系统总成本越大，卸载方案越差；
反之亦然。因此，将目标函数的倒数作为适应度函数。其中，f的最小值不为0。

3.4 分组交叉重组

在常用的进化算法中[15]，选择操作是把相对较好的区域与较差区域区别开来并将较差的区域直接淘汰。但是进行选择操作将较差区域的粒子淘汰后，粒子种群的丰富性就会降低。为了提高粒子种群的优越性与多样性，在本文所提出的改进算法中，先通过各个粒子的适应度值的高低将粒子分为两个小组。第1 组为适应度高的粒子，第2组为适应度低的粒子，迭代时用第1组粒子的位置和速度矢量取代第2组粒子的对应矢量，并且不改变其个体极值。在执行遗传思想的交叉重组操作时，第2 组粒子进行两两配对重组，子代粒子与父代粒子进行适应度对比，选取整组中适应度高的一半粒子进入第一组。通过交叉重组使得第1 组中的粒子种群适应度优于分组前，能够增加粒子种群的优越性和多样性，防止陷入局部最优并使收敛速度增加。粒子分组交叉过程如图4所示。

其中，X和V分别为位置与速度矢量；
child1(X) 和child2(X)为子代粒子的位置；
child1(V)和child2(V)为子代粒子的速度；
p是均匀分布的随机数向量，为交叉概率，并且每个分量都在[0，1]取值；
子代粒子的位置由父代粒子位置的算数加权和计算[16]。

进行交叉操作过程如图5所示。

粒子交叉重组后得到的Pbest和Pgbest，根据粒子与速度更新公式进行全局学习，通过交叉重组操作后可以跳出局部最优，以更快的收敛速度找到优化问题的最优解。

3.5 算法流程设计

CRPSO算法参数与卸载策略参数的对应关系如表2所示。

表2 算法参数与卸载策略参数的对应关系Table 2 Uninstall policy parameter relationship

基于CRPSO算法的优化策略流程，具体如下。

输入：请求任务数量n、移动设备的计算能力fl、边缘服务器的计算能力fe、云服务器的计算能力fc、本地设备计算功率pl、边缘服务器的计算功率pe、云服务器的计算功率pc。

输出：最优卸载策略，最优适应度值。

步骤1 初始化。确定迭代次数和粒子的数量，并初始化粒子的速度和位置。

步骤2 计算每个粒子的适应度值，并比较各个粒子的适应度值，记录其当前个体极值Pbesti和群体最优粒子Pgbest。

步骤3 执行分级交叉重组操作。

步骤4 根据公式（15）和（16）更新交叉重组之后新粒子的位置和速度。

步骤5 计算交叉后粒子的适应度，更新个体极值Pbesti和全局极值Pgbest。

步骤6 终止条件判断。检查是否满足迭代次数，若满足则执行步骤7，若不满足，执行步骤3。

步骤7 输出全局最优适应度和最优任务卸载策略。

根据以上模型中假设的服务器的数量以及模型中涉及到的参数，在本节的仿真场景中，由于用户在通信小区内的移动性较小，因此忽略移动过程中通信链路软硬切换带来的影响，只关注任务卸载的过程，并假设所有边缘服务器的计算能力都是相同的，本地终端设备为3个，边缘服务器数量为8个，1个云服务器。

在文献[17]的基础上设定系统的基本参数，并结合本文所建立的任务卸载模型，将实验环境适当调整后，对本文所提出的CRPSO 算法以及Local-MEC 算法、ECPSO 算法、GCPSO 算法利用MATLAB R2020a 仿真平台进行了仿真对比实验。任务卸载的仿真参数由表3给出，CRPSO算法的相关参数由表4给出。

表3 算法相关参数Table 3 Algorithm related parameters

表4 实验仿真参数Table 4 Experimental simulation parameters

Local-MEC算法：任务卸载至本地设备的计算卸载策略。

ECPSO（Edge Computing PSO）算法：边缘计算中基于传统粒子群算法的计算卸载算法。

GCPSO（Genetic Cross PSO）算法：边缘计算中基于遗传的改进粒子群的计算卸载算法。

4.1 任务数量改变对系统总代价的影响

为了研究任务数量的变化对系统总代价的影响，设置模拟的任务数量分别为25、50、75、125、150（个），利用CRPSO 算法、Local-MEC 算法、ECPSO 算法、GCPSO 算法进行性能比较。仿真结果如图6所示，随着任务数量的增加，系统的总代价逐渐增加，这是由于任务数的增加将会导致任务在卸载过程中消耗的能量和处理任务的时间会增加。从图中能够看出，与Local-MEC 算法、ECPSO 算法、GCPSO 算法相比，本文提出的CRPSO 算法的系统总代价是最小的，约为Local-MEC 算法的11.91%、ECPSO算法的36.79%、GCPSO算法的56.24%。

4.2 迭代次数对系统总代价的影响

本节中为了更好地显示迭代次数对系统总代价的影响，取最大迭代次数G=100，总任务数n=80，时延与能耗的权重系数ω=0.5。由于Local-MEC 算法中任务只在本地设备和边缘服务器执行卸载策略，迭代次数对实验结果的影响省略。仿真结果如图7所示，随着迭代次数的增加，CRPSO算法、ECPSO算法、GCPSO算法的系统总代价都逐渐减小。从图中可以看出，迭代70 次之后，系统总代价趋于平稳。因此，当迭代次数为70时，可以得到系统最优解。

4.3 工作量对系统总代价的影响

任务工作量的大小对系统总代价也是有影响的，在本节中取任务工作量在[0，100]之间，任务数n=100，ω=0.5，从图8 可以看出，任务工作量的增加，设备的能耗会随之增加，由于计算量较大，执行时间也会增加，故而系统的总体代价也逐渐变大。从图中可以看出，CRPSO算法得到的系统总代价最小，约为Local-MEC算法的13.1%、ECPSO算法的31.8%、GCPSO算法的76.5%。

4.4 异地边缘服务器对系统总代价的影响

本文提出的边缘协同的框架下，离用户最近的边缘服务器周边服务器的数量也会对系统总代价产生影响。考虑到若附近边缘服务器的数量为0时，边缘服务器之间的协同卸载则不能执行，因此本节中附近边缘服务器的数量设置为1～7个进行仿真实验，由于传统卸载策略不受周边服务器数量的影响，所以在图中略去。仿真结果如图9所示，当附近边缘服务器的数量为3个时，系统总代价最低，可以输出最优卸载策略；
随着附近边缘服务器的数量不断增加时，任务卸载时服务器之间的传输时延与能耗增加，导致系统总代价升高，当附近边缘服务器的数量为6个时，系统总代价有略微的升高就是这个原因。但是从图中可以得到，本文提出的CRPSO算法卸载策略系统总代价始终是最低的。

4.5 时延与能耗权重比对系统总代价的影响

在对系统总代价产生影响的因素中，时延与能耗权重比值也是需要考虑的重要因素之一。本节主要研究时延与能耗权重比ω/(1-ω)在[0.01，100]时，ECPSO 算法、GCPSO算法、CRPSO算法的性能比较。仿真结果如图10所示，随着时延与能耗权重比值的增大，CRPSO算法的系统总代价约为ECPSO 算法的33.1%，GCPSO 算法的58.9%，明显优于上述算法。因此，CRPSO 算法能够对不同场景下的移动服务起到优化作用。

本文针对移动任务卸载的时延与设备能耗的优化问题，及多个边缘服务器与云服务的协同问题进行研究，提出了多个边缘服务器的协同计算卸载方案，通过引进遗传交叉思想对粒子群中部分粒子进行分组交叉取优，使算法跳出局部最优，更快收敛于全局最优解，得到最优卸载策略。仿真结果表明，CRPSO 算法的系统总体代价最小，可以在时延与能耗均衡的情况下输出最优卸载策略。下一步工作将对卸载模型进一步完善，采用深度学习相关算法进行卸载策略研究。

猜你喜欢 适应度代价时延 改进的自适应复制、交叉和突变遗传算法计算机仿真(2022年8期)2022-09-28计算机网络总时延公式的探讨电脑知识与技术(2021年22期)2021-09-14《舍不得星星》特辑：摘颗星星给你呀花火B(2019年3期)2019-04-27基于GCC-nearest时延估计的室内声源定位电子制作(2019年23期)2019-02-23基于移动站的转发式地面站设备时延标校方法宇航计测技术(2018年3期)2018-09-08爱的代价海峡姐妹(2017年12期)2018-01-31幸灾乐祸的代价语文世界(初中版)(2017年5期)2017-06-22代价作文与考试·初中版(2017年12期)2017-04-19启发式搜索算法进行乐曲编辑的基本原理分析当代旅游(2016年10期)2017-04-17基于人群搜索算法的上市公司的Z—Score模型财务预警研究财经理论与实践(2015年2期)2015-04-16

推荐访问:计算 卸载 协同