移动边缘计算中以节点能耗约束的迁移策略研究

杨晓慧，熊小峰，宋逸杰，杨忠明，赵玲珠

（江西理工大学 理学院，江西 赣州 341000）

0 引言

过去10 年中，为满足爆炸式增长的流量对大量计算资源的需求，将计算、控制和数据存储转移到云成为趋势，这种重新定位引入了网络延迟，对时延敏感的应用程序延迟要求带来了重大挑战。移动应用程序日益复杂化、智能化及多样化，人脸识别、语言处理、在线游戏和远程医疗等应用均具有时效性强、数据量大、带宽高等特点，越来越超出设备的有限能力，使得智能移动终端在计算能力和电池寿命方面面临巨大挑战。由此，边缘计算（Edge Computing，EC）应运而生，并与传统云计算互补，在靠近移动用户附近的网络边缘提供云计算功能，满足快速交互响应需求，提供普遍且灵活的计算服务［1］。边缘计算思想是将全部或部分计算任务迁移至边缘服务器/其余终端设备，降低计算时延与能耗开销。因此，计算迁移是边缘计算的关键技术之一，可弥补设备的能力限制和不断增长的计算需求［2］。计算迁移有以下3 个优点：①降低了移动设备本地处理计算任务的能耗，延长了电池使用寿命；②利用远程云/边缘服务器等更强大的CPU 计算能力，减少任务的处理延迟；③通过本地和云处理资源协同服务处理更多的计算任务，提高服务质量（Quality of service，QoS），提高用户满意度。计算迁移有效解决了设备在资源存储、计算性能以及能效等方面的不足。

智能终端的电池能量局限性很大，电池更换或充电不便且成本较大；因终端自身资源不足，部分设备在计算迁移过程中出现拒绝协作现象，增加了网络负载和延迟，导致丢包率增加。特别是在MEC（Mobile edge computing）场景下，当计算任务较小且完成的延迟和能量较低时，迁移反而导致成本增加［3］。因此，通过制定有效的迁移策略快速响应，降低节点能耗，提高边缘网络QoS、吞吐量和生命周期，成为边缘计算领域需要解决的核心问题之一。

针对上述问题，本文提出一种基于节点剩余能量的计算迁移策略。以节点剩余能量为约束，构建计算迁移决策模型，降低因能源不足导致的网络抖动；利用模拟退火算法（Simulated Annealing，SA）和改进的粒子群算法（Particle Swarm Optimization，PSO）对该模型求解，提高网络吞吐量，降低丢包率和延迟，使网络边缘设备获得良好性能，以保障边缘网络的鲁棒性和稳定性。

1 相关工作

为实现就近服务、提高网络容量和保障数据安全，边缘计算通过计算迁移方式，根据策略将计算向边缘节点、边缘服务器或云迁移，通过计算迁移协同服务，提升边端计算能力和电池寿命，降低计算延迟和网络带宽消耗，均衡云中心负载，提高网络QoS。其中，边缘计算迁移的能耗与延迟是衡量迁移决策的重要指标，降低处理及传输任务的延迟和能耗的相关研究成果颇丰。

文献［4］考虑了移动边缘计算中优化资源策略的单一性，为保证延迟约束情况下充分降低边缘设备能耗，提出一种基于粒子群任务调度算法的多重资源计算迁移能耗模型。验证了该策略所对应的任务调度算法收敛稳定、适应度最优；文献［5］以移动设备的任务处理延迟和能量消耗约束为研究对象，通过迁移将边缘服务器分配给一对深度神经网络移动设备，使边缘服务器利润最大化；文献［6］提出一种高效安全的多用户多任务计算迁移模型，使用JPEG 和MPEG4 压缩算法来减少传输开销，对大规模物联网具有很好的扩展性。

计算任务的增加使得电池使用寿命成为难题。文献［7］为解决移动终端电池能量和计算能力受限问题，基于MEC 架构，以终端能耗最小化与移动服务提供商收益最大化为目标，提出一种动态定价策略，使用Q-learning 与DE相结合的算法，提高资源的利用率和处理效率；文献［8］基于无线供电技术研究了MEC 场景中终端迁移决策问题，设计一种基于深度强化学习的在线迁移决策算法，降低计算时间开销和网络延迟，实现计算自适应迁移和资源合理分配；文献［9］基于能量收集技术，提出一种绿色可持续的移动边缘计算（GS-MEC）模型，提出在能量队列稳定性限制下最小化任务响应时间和包丢失，提高任务处理的及时性和可靠性，实现设备在物联网环境中利用绿色能源自供电。

源任务节点通常在覆盖范围内首先考虑优秀节点进行迁移，导致优秀节点任务队列任务堆积，致使负载不均，降低了网络吞吐量。为解决该问题，文献［10］基于无线传感网络应用场景，提出一种改进的簇头节点选择算法，循环选择剩余能量较高的节点作为簇头，并在其之间轮换簇头位置，提高了网络的吞吐量、生命周期及剩余能量，实现网络负载均衡；文献［11］研究了计算迁移环境下移动设备资源的能效问题，基于修改的李雅普诺夫优化技术优化计算迁移决策，保持移动设备上运行程序的吞吐量和公平性；文献［12］提出一种基于累积社会信任组织计算迁移的在线学习辅助协同迁移机制，在无法精准预测的情况下保证接近最优的系统性能，但是系统的鲁棒性是以降低稳定性为代价；文献［13］提出一种在多约束条件下边缘计算可信协同任务迁移策略，以K 维权值任务迁移作为优化目标，采用改进的贪心算法求解最优任务分配策略，保障计算迁移效率和QoS。

随着我国海事活动日趋频繁，海洋无线通信与边缘计算融合应用越来越多。文献［14］联合优化迁移策略、通信资源和计算资源，研究了MEC 系统在慢衰落信道和快衰落信道下的计算任务与迁移顺序之间的依赖性，分别设计了黄金算法和即时信道策略选择最优迁移决策，实现在延迟约束下最小化终端设备的能耗；文献［15］针对海上资源有限导致延迟和能耗过大问题，提出一种基于移动边缘计算的两段式联合优化迁移算法（JOOA）。通过构建低成本、大规模的海上通信网络框架，降低了任务迁移中的延迟以及计算能耗。但在海上大规模网络环境中，若节点掉线会导致网络抖动且在短期内难以重新自主组网，所以保证网络节点的稳定性是需要考虑的重点。

以上方法都未在因节点下线导致的网络抖动方面进行能耗优化。本文根据迁移决策和任务分配方式的不同，提出基于能耗约束的计算混合迁移策略（Hybrid Offloading Strategy Constrained by Node Energy，HOS-NE）。利用粒子群算法和模拟退火算法优化该迁移模型，综合考虑计算迁移时边缘迁移节点的负载情况和能量利用率等因素，自主选择迁移决策和任务分配，保证在任务期限内降低任务的丢包率，提高节点能量利用率和系统吞吐量。

2 HOS-NE 策略模型构建

2.1 边缘计算迁移模式

根据源迁移节点与迁移节点的相对位置关系，边缘计算迁移可分为上行、平行和下行3 种迁移模式［16］。其中，利用上行迁移与平行迁移技术，将任务及时迁移到移动边缘计算服务器或临近空闲的移动终端进行计算处理，能够有效扩展移动设备的即时计算能力，降低计算延迟，提高移动终端电池寿命。如图1 所示，当智能终端发起计算请求时，依据任务计算量、响应延迟进行迁移决策，将计算量较大的任务迁移至计算能力强的远程云中心或边缘服务器执行，降低终端能耗；将计算量小的任务或者需要地理位置信息、响应延迟低的任务留在本地处理或D2D 协作执行，降低计算响应延迟。因此，计算密集型任务计算量大，采用以能耗为约束的上行迁移；而对于延迟敏感任务采用以延迟为约束的本地迁移。

Fig.1 Computing migration scenario图1 计算迁移场景

假设由1 个边缘服务器和u个智能终端（本文统称为节点）构成的集合U={1 ,2,…,U} ，移动边缘计算应用场景中每个终端可同时执行多个计算任务且每个计算任务不能再进行划分。其中，每个终端ui的任务表示为Aui={aui,1,aui,2,…,aui,m}，用ζui,j={cui,j,dui,j,tui,j} 表示每个任务aui,j的属性特征。cui,j表示任务aui,j需求的计算能力，dui,j为该任务的最后期限，即该任务所能容忍的最大时延，tui,j为该任务在标准算力下完成所需要的时间。

为克服设备资源、算力限制，以及响应高效、实时的需求，MEC 允许UEs 根据任务的属性特征选择执行方式：

（1）平行迁移。迁移至邻近设备执行延迟较低且满足实时响应需求。

（2）上行迁移。允许UEs 将任务转移到邻近的服务器以更快地进行任务计算。

本文主要采用平行迁移与上行迁移相结合的混合迁移模式，依据任务计算量、响应延迟进行迁移决策，以降低终端能耗和响应延迟。使用二元变量xij∈{ 0,1} 表示终端的决策，xij= 1 表示任务迁移到其余节点j执行，xij= 0 表示任务在终端本地执行。

根据文献［17］构建MEC 迁移系统模型。当任务在终端本地执行时，设节点ui的计算能力为fiL，TiL表示任务aui,j在本地执行的时间，则：

本地计算的能耗为：

其中，κm为一个受设备硬件影响的参数。

当任务迁移到MEC服务器执行时，设边缘服务器的计算能力为fiS，TiS表示任务aui,j迁移到网络边缘执行的时间，则：

其中，Tit为任务的传输时间，受传输任务量的大小与传输链路的影响。迁移到边缘服务器远程执行，则终端ui的能耗为：

其中，pi为ui的发射功率，ζi为设备的功率放大器效率。

综上所述，最小化移动智能终端公式可表示为：

其中，为ui的最大功率。

考虑到终端设备的多样异构性，且功率差异较大，实际上公式（5）的求解过程较复杂。为简化问题复杂度，本文使用终端节点的待机时长表示终端能耗，根据剩余电量的状态表示终端设备的状态。因此，本文提出一种基于节点剩余能量的移动边缘计算混合迁移策略——HOS-RE，根据源迁移节点任务的算力、能量等需求特征和迁移节点的剩余能量、计算能力等特征，将任务迁移至合适的节点执行。采用上行与平行的混合迁移模式，提高网络的稳定性、鲁棒性，实现负载均衡。制定合适的迁移决策是求解该问题的关键，具体策略框架如图2 所示。

2.2 平行迁移决策

对于每个终端ui，使用三元组{,u_ti,τi}表示节点的属性特征。其中，表示终端ui的实时计算能力，u_ti表 示终端初始待机时长，τi为节点实时待机时长。当任务i发送迁移请求给终端ui时，设备根据以下两个方面来判断是否接受任务：

Fig.2 Framework for computing migration strategy图2 计算迁移策略框架

（1）终端ui选择接受任务时首先需要考虑自身的算力能不能满足任务需求的算力，节点的实时计算能力可以表示为：

其中，c′ui,j表示正在处理计算任务所需的算力。

（2）终端ui选择接受任务时还需要考虑自身的能量能不能保持完成任务后仍在线。因此，节点接受计算请求服务待机时长下界u_ti′可表示为：

其中，ω表示节点电量预留的阈值，保证节点执行任务后仍有能量保持自身在线，进而维持网络稳定。

综上所述，使用二元变量yij表示终端ui的任务接收决策，当yij= 1 时表示uj成功接受任务ai的迁移请求，否则不接受。任务接收决策函数表示为：

当终端ui向周围节点发送任务计算迁移请求时，周围节点可拒绝接受该任务请求。当该任务被拒绝多次，则将该任务计算迁移到MEC 服务器进行处理。平行迁移终端设备的剩余能量可表示为：

2.3 上行迁移决策

当终端设备的计算能力与待机时长均无法满足任务ai需求，即被拒绝次数R达到上界k时，则该任务所在的终端选择将任务迁移至MEC 服务器执行。与终端节点相似，使用三元组{,s_ti,τis}表示边缘服务器属性特征。其中,表示边缘服务器计算能力，s_ti表示边缘服务器初始能量，表示边缘服务器实际能量。使用二元变量zij表示终端是否将任务迁移到边缘服务器。当zij= 1 时表示将任务迁移到边缘服务器执行，否则为0，丢弃该任务，将本次迁移视为失败，则：

上行迁移的剩余能量表示为：

综上，将式（5）中的终端设备能耗最小化问题转化为最大化终端剩余能量问题：

2.4 算法设计与实现

由于公式（13）求解复杂度较高，为优化求解能力，本文分别采用PSO 算法和SA 算法对该问题进行求解，具体算法描述如下：

3 实验仿真与分析

3.1 仿真场景与实验设计

构建计算迁移系统模型应用场景如下：一个MEC 网络环境中分布127 个节点以及1 个MEC 服务器，设定每个设备产生任务的个数在区间［0，20］中随机生成，每个任务所需算力在区间［1，5］中随机产生。设节点初始电量均为300min，且不可持续充电，即当电量耗尽后该节点下线，仿真参数及描述如表1 所示。

Table 1 Experimental simulation parameters表1 仿真参数

为验证所提出迁移模型的有效性，采用MATLAB 工具进行仿真实验。首先，第一组实验从迁移失败次数和节点平均剩余能量两方面与基于PSO 的智能算法［18］、随机游走（Random execution，RE）和基于能量的贪心算法（Greedy_energy，G_E）［19］进行比较；第二组仿真实验中，与基于SA 的智能算法［20］、RE、基于算力的贪心算法（Greedy_compute，G_C）和G_E 算法在吞吐量、剩余能量和任务处理成功率方面进行比较。

3.2 算法仿真与性能分析

3.2.1 同一周期内不同迁移策略性能分析

为了验证迁移策略的有效性，本文将基于PSO 的智能算法与RE、G_E 算法进行丢包数与设备剩余时间对比分析。RE 算法、G_E 算法介绍如下：

（1）随机迁移（RE）算法。在任务迁移请求发起时，每个设备的任务随机选择边缘服务器端或邻近的终端设备进行处理，但未进行选择优化。

（2）基于能量的贪心（G_E）算法。任务迁移时为每个任务在时间允许范围内贪心地选择能量较多的终端设备进行处理。

实验1算法稳定性评估

从图3 可以看出，算法迭代次数达到80 时趋于稳定，表1 给出了实验中共用参数的详细值。PSO 算法实验参数设置如下：算法迭代次数为L= 150，速度最大最小值Smax=5,Smin= -5，学习因子C1= 2,C2= 1.5，惯性因子W1=0.9,W2= 0.4。为了提高实验的准确性，针对设备资源是否重置进行两组实验：①随着任务量增加，每次迁移时重新寻找最优迁移矩阵；②随着任务数增加，依据剩余资源寻找最优迁移矩阵，即终端资源不进行重置。

Fig.3 Stability of the algorithm图3 算法稳定性

实验2设备资源重置

在设备资源重置场景下，随着任务量的增加，任务丢包数与平均剩余能量的对比如图4、图5 所示。

Fig.4 Change of lost packet number图4 丢包数的变化（彩图扫OSID 码可见，下同）

Fig.5 Average residual time change图5 平均剩余时间变化

从图4 可以看出，随着任务的增加，3 种算法的任务丢包数均增加，RE 与G_E 算法几乎呈线性增长趋势。与其余两种算法相比，PSO 算法能够显著降低丢包数。这是因为RE 算法虽然可以在很短的时间内选择一个节点进行迁移，但随机性较高导致被选择节点的属性差异也较大，且可能多个任务同时迁移到同一迁移节点，致使任务超时被丢包；G_E 算法会优先考虑能量和算力较大的节点，计算任务堆积在队列中从而导致任务完成时间超过任务期限，丢包数增大；基于PSO 算法进行迁移时，综合考虑节点的多种特征如能耗、时延、代价等，所以任务选到适合自己的节点概率较高，丢包数比较理想。随着任务数量上升，基于PSO 算法的迁移方式丢包数也呈现出平缓增加趋势。

分析图5 可知，随着任务数增加，节点平均剩余能量逐渐减少。与RE 算法相比，基于PSO 算法的平均剩余能量在任务量少时近似相同。但随着任务量的增加，PSO 算法下的节点处理任务较多，能耗增加；在G_E 算法下的节点由于呈现任务趋优现象，任务丢包率较大所以能耗较低。

实验3设备资源非重置

图6 和图7 均在节点资源非重置的环境下进行仿真，即每产生一个计算迁移任务，该任务就会在节点处理完之前的任务后在剩余节点资源中寻找适合自己的设备。

Fig.6 Change of lost packet number图6 丢包数变化

Fig.7 Average residual time change图7 平均剩余时间变化

由图6 分析可知，随着任务数的增加，任务丢包数都呈现上升趋势。基于PSO 算法的任务丢包数上升缓慢，丢包率在5%-10%之间，比RE和G_E算法分别降低了65% 、71.4%。

分析图7 可知，基于PSO 的算法随着任务量的增加耗能也增加，剩余能量逐渐减少。PSO 算法平均剩余时间比RE 和G_E 算法分别提高了16.7%、28.6%，在任务数增加至1 000 后下降，趋于平缓的趋势更加明显。

综合图6 和图7 可以得出，PSO 算法在能耗和丢包方面都优于RE 和G_E 算法，任务通过PSO 算法选择最适合自己的节点，既不浪费资源也不增大延迟，可消耗更少的能量处理更多的任务。

3.2.2 任务周期内不同迁移策略性能分析

为进一步验证迁移策略模型性能，在图1 场景下，本文从时间周期角度运用基于SA 的智能算法与G_C、RE 和G_E 算法进行比较，分析吞吐量、丢包数与平均剩余能量评价性能的优劣，仿真结果分别如图8-图10 所示。

Fig.8 The throughput change图8 吞吐量变化

Fig.9 Change of lost packet number图9 丢包数变化

从图8 分析可知，每个周期中基于SA 智能算法的吞吐量都优于其他3 种算法，且SA 算法在第14 周期达到稳定，吞吐量比其余3 种算法提高约40%，G_C 算法优化后的系统吞吐量在第9 个观察周期达到稳定，这是由于G_C 算法中算力高的节点能量耗光后网络无法处理后续的迁移任务，且由于网络总能量不足致使G_C 算法和SA 算法优化后的系统吞吐量增量逐渐减少。

从图9 分析可知，随着时间推迟，设备能量逐渐消耗，SA、G_C、RE 算法的丢包数逐渐增加。实验中仅考虑了平行迁移的丢包数，其中G_E 算法由于参数原因不会使任务堆积而导致卸载失败，所以不产生丢包；SA 算法因节点电量降低导致丢包现象，但与G_C、RE 算法相比，任务迁移的丢包率降低了很多。

Fig.10 Average residual energy change图10 平均剩余能量变化

从图10 分析可知，随着系统完成任务数的增加，节点剩余能量逐渐减少。SA 算法的剩余电量小于其余3 种算法，结合图8、图9，SA 算法提高了边缘计算的资源利用率和协作率，合理利用了不同算力设备，且节点剩余能量会收敛在一定范围，以便提供耗能较小的计算迁移服务和处理自身任务，提高了网络稳定性。

综上所述，基于SA 智能算法优化的迁移策略能实现网络负载均衡，提高系统吞吐量和网络稳定性。

4 结语

针对移动智能终端电力受限问题，本文根据迁移决策和任务分配方式不同，提出一种基于节点剩余能量的移动边缘计算混合迁移策略HOS-NE，并将迁移问题中的节点功率使用终端节点的剩余能量进行转化，采用PSO 与SA 的智能算法对化简后的问题进行求解。仿真结果表明，基于智能算法优化后的HOS-NE 能有效提高系统吞吐量和节点在线时长，实现负载均衡。但由于节点的自主性，并非网络中所有计算节点均能满足迁移节点条件。所以，如何评价节点，构建可信、可靠的计算迁移策略是下一步研究工作重点。