移动边缘计算中利用BPSO的任务卸载策略

汪小威，林 宁+，胡玉平

(1.南宁学院 信息工程学院，广西 南宁 530200；2.广东财经大学 信息学院，广东 广州 510320)

0 引 言

随着智能设备的剧增以及通信技术的突飞猛进，促使边缘计算突破技术瓶颈，并极大地提高了物联网(Internet of thing，IoT)的计算效率[1]。面对着越来越多的数据，各类终端设备不断研发出来并且功能愈发丰富，甚至逐渐承担了云服务的作用，实现了更高的计算效率。移动边缘计算(moving edge computing，MEC)技术作为云计算相关领域最为关键的方向之一，已在物联网和嵌入式系统等众多新技术中广泛应用并投入实际运行[2]。然而，各种终端设备在不断竞争与脚逐的过程中计算成为了关键环节，大量的计算开销对计算能力和网络承载能力也提出了新的要求[3]。

一般情况下云计算速度的快慢以及其性能的高低依赖于物理服务器，终端设备利用云计算时首先要将相应的数据传送给物理服务器，这样可以有效解决中断设备自身能力不足的弊病[4]。但是不可否认的是随着终端设备越来越多，大量数据不断汇集到服务器将会对其造成巨大压力。与云服务器相反，边缘节点有限的计算和存储资源要求其将部分计算或存储任务卸载到其它边缘节点，以提高系统资源利用率，便于灵活高效地进行任务卸载，以实现对所需处理任务的合理规划[5]。

对于任务卸载策略最优化问题，从最优化动机的角度来看，移动边缘设备必须克服数据量大、带宽低、设备电池容量受限等不利因素[6]。因此，在保证数据处理速率的前提下，降低能量消耗是保证设备连续运行的关键[7]。传统的任务卸载优化方法除了需要对数据隐私性进行强化以外，还需要在保证低数据延迟的同时，降低任务处理能耗，提高系统计算效率。所提出的任务卸载策略基于由移动设备、边缘节点和云服务器组成的三层网络架构提出了任务卸载方案，用以实现移动设备在所有任务持续时间内的能耗的最小化。

1 相关工作

目前已经有许多关于计算卸载优化问题的研究成果，其中包括由移动设备和边缘节点组成的移动边缘计算网络场景研究，以及由移动设备和云服务器组成的移动云计算(mobile cloud computing，MCC)网络场景研究等[9]。

在移动边缘计算网络的基础上，为尽可能延长中断设备使用时间，提升能源使用效率，要寻找出最优的资源分配方案。文献[10]考虑了MEC网络中分布式能量收集设备通过射频实现功率传输的能量感知架构，充分利用乘子交替方向法有效提升计算能力降低其延迟时间，但该方法不能在各种网络设置下有效地实现最佳性能，具有一定的局限性[11]。文献[12]为了最大限度地降低移动设备的能耗，将约束条件设成所有任务的持续时间，针对边缘计算中能量消耗的最优化问题展开研究，分别从协同任务卸载和计算资源配置两方面进行了问题优化，在最短的时间内实现能耗最低的需求，虽然兼顾了能耗和延迟最小化，但在实际应用中还不具有一定的可行性。文献[13]为了解决MEC任务卸载中兼顾效率与数据隐私性的问题，提出了一种包含实用感知卸载程序和用于隐私权衡的两阶段联合卸载优化策略，用于MEC系统任务卸载策略优化和隐私保护，实验结果表明了该方法的高效性和可靠性。由于任务卸载过程中对隐私保护的权衡，导致算法在处理延迟和综合能耗方面表现较差。

粒子群优化算法作为一种经典的智能算法，目前已有一些文献将其广泛应用于优化决策过程中[14]。文献[15]针对预测任务之间的全局时空相关性，时空异质性与模型的全局预测能力之间的平衡以及预测模型的参数优化等挑战，结合基于粒子群优化的时空多任务和多视图特征学习模型提高模型的训练速度，对MEC中任务卸载进行优化。但传统的粒子群优化算法容易陷入局部最优，难以获得全局最优解，因此文献[16]提出了计算分流模型，将任务卸载表述为一个混合整数非线性规划问题。在该文献中引入了两种算法，一种是数学中经典的遗传算法，另外一种是粒子群优化算法，通过这两种算法的结合有效提升了计算速度。仿真研究表明该算法的收敛性和可靠性，但由于算法迭代耗时，导致任务卸载整体延迟较其它算法较高，还有可提升的空间。文献[17]在考虑完成时间和能效的基础上，把计算分流进行了转化，利用能效成本进行代替。同时在该文献中还对时钟频率以及其发射功率等再次进行了优化从而建立了一种有效的分布式算法，这种方法对本地任务执行的时钟频率和边缘云执行的传输功率进行了联合优化，在保证卸载效率的同时降低了能耗。文献[18]提出了一个包含对卸载策略制定、负载平衡、计算资源分配的多维优化问题，以最小化多MEC服务器多智能移动终端(smart mobile devices，SMD)网络中所有SMD的总延迟和能耗的加权总和，并进行功率控制。通过一种低复杂度的启发式算法来获得卸载策略，同时保证多个MEC服务器之间的负载平衡；并使用拉格朗日对偶分解法解决计算资源分配子问题。

虽然该方法在任务卸载策略的能耗优化方面取得了一定的成绩，但是无法兼顾能耗与传输延迟，系统整体负载均衡方面仍存在一定的提升空间。为此，提出了一种移动边缘计算中利用BPSO的任务卸载策略。其主要的创新点总结如下：

(1)由于核心计算网络负担较大，所提策略构建了三层移动边缘计算(moving edge computing，MEC)网络架构，移动设备中的计算任务可以在本地进行，也可卸载至边缘计算节点与云服务器中执行，有利于任务卸载策略的高效实施。

(2)为了提高任务卸载方案的性能，所提策略根据MEC网络中的计算模型、通信模型设计了计算卸载目标，并利用二进制粒子群(binary particle swarm optimization，BPSO)算法对其进行求解，以得到最优卸载策略，实现能量消耗最小且时延最短，系统整体负载最为均衡。

2 系统模型

2.1 网络模型

为了任务卸载策略的高效实施，提出了一个分布式的三层边缘计算网络模型，其架构如图1所示。其中包括了M个移动设备(mobile devices，MD)、N个基站(base stations，BS)和一个远程云服务器。每个基站都配备了一个边缘计算节点。此外，移动设备的电池容量是有限的，将移动设备的集合表示为m={1,2,…,M}，边缘节点的集合为n={1,2,…,N}。当每个基站通过有线链路连接到云端时，可以通过无线链路与多个移动设备进行通信，并且移动设备与基站之间的距离远小于基站与云之间的距离[19]。

图1 移动边缘计算网络模型的架构

(1)

上式表示一个计算任务要么由移动设备在本地执行，要么由设备卸载到基站或云再进行处理，且总数据量大小为Dm。

其次，介绍了服务缓存的概念。缓存将数据副本存储在靠近请求的位置，并预期会收到相同的请求，这样的方式可以减少计算延迟和网络负担。在所提策略中，将服务的集合表示为s={1,2,…,S}，用cs来表示服务S所需的存储空间大小，用Cn来表示基站n的存储空间。更具体地说，所提策略中假设计算任务以vs,n的速率到达，并服从泊松过程。需要注意的是，服务缓存将在每次基于短期预测而做出决策之前进行更改。

2.2 通信模型

提出的网络模型中，每个移动设备都需要为其任务选择最佳的策略。将Bn(Hz)表示为边缘节点n的无线信道带宽；以ηm,n表示移动设备m和边缘节点n之间的上行传输效率。根据香浓公式，可以近似得到

(2)

式中：pm,n代表的是使用的终端设备m的传输功率，δm,n代表的是使用的终端设备m和相应基站n之间的信道增益，τ2代表的是背景噪声的功率值，即加性高斯白噪声。pm,nδm,n/τ2可以表示移动设备m与基站n之间的上行链路信噪比。根据ηm,n的定义，进一步地定义移动设备m与基站n之间传输数据的上行速率为

(3)

在服务缓存的情况下必须要强调的是，基站n的有限存储空间Cn迫使基站必须做出选择，即基站需要选择哪些服务进行缓存[21]。具体地说，基站n需要在服务S中选择若干个服务进行缓存。为此，引入一个二进制变量φs,n∈{1,0}，用来表示服务s是否被缓存在基站n中。因此，服务缓存的约束条件服从下式

(4)

进一步地，将φs,n⊆N表示缓存服务S的基站集合，所以这些基站可以向移动设备提供相应的服务。

2.3 计算模型

(1)本地计算

(5)

(2)边缘计算

(6)

(7)

由于被基站n处理后的数据量大小与原先相比将变得非常小，所以忽略将处理后的数据发送回移动设备m的下行链路传输延迟。综上所述，将从移动设备m中数据卸载到基站n的传输能量成本定义为

(8)

(3)云计算

(9)

与边缘计算类似，忽略基站与移动设备之间的下行传输延迟。值得注意的是，计算过程的总能耗是十分复杂的，它还包括基站和云的计算成本。然而，由于考虑的问题是关于移动设备的电池续航能力，这意味着需要进行最优化的问题仅需关注到移动设备的能源成本。

根据以上所述，可以总结得出每个移动设备的所有任务持续时间Tt和能量消耗Em分别如下

(10)

(11)

2.4 计算卸载目标

计算机卸载的主要作用就是将原有的计算工作转至云计算或者其它边缘计算中，然后再利用各种终端设备发送需求指令，待计算完成结束，最终的结果利用终端显示出来。计算卸载应用场景越来越多并且也逐渐引起了人们的重视。其具体的架构如图2所示。

图2 计算卸载框架

从具体过程来看，计算卸载正式开始前，终端设备必须对其要开展的计算工作做出合理、科学的分配，一部分归为本地进行，另外一部分可以归为节点进行。其中前者就是指在设备中即可进行操作。而后者则需要依赖于边缘计算节点。另外，计算节点一旦接受相应指令就要对资源进行详细的规划，具体的工作任务会根据规划进行分配，假如节点不能实现，那么就需要将其转至云服务中心。计算节点根据规划完成任务后还要将结果再次传送至终端设备。

对卸载目标进行准确的确定目的就是要快速的将计算任务进行科学、合理的分配，具体来讲卸载目标涵盖了如下3个部分。

(1)任务最优分配。最优分配通俗来讲就是确定一个最为合理同时效率又最高的一种方法，使得整个计算过程的延时能够达到最小，从而提升用户的体验感。

(2)节点负载均衡。边缘计算平台一般包括很多个计算节点，而这些节点必须利用足够数量的计算机，当其数量达到一定程度后，每个节点的负载如何保证最佳也是卸载目标要实现的，这样才能够将有效的资源充分调动起来。

(3)经济利益最大化。计算卸载任务同样要考虑到所需要的成本以及能够实现的经济效益，尤其是在数据爆炸的今天，对于设备数量需求只会越来越高，所以卸载目标必须考虑经济效益的问题，平衡使用者与运营公司二者之间的利益。

3 基于二进制粒子群的调度策略

这里假定本地执行的与卸载至边缘计算平台进行的任务都已经明确，通常情况下用Qm表示总任务，那么卸载后的任务就能够通过ϑi进行表示，这里需要注意的是ϑi属于二进制，其中ϑi∈{0,1}。当ϑi=0时，表示计算任务Qm在本地执行计算；当ϑi=1时，表示计算任务Qm需要卸载到边缘计算或云计算服务器去执行。如此，就能够知道任何一个Q都将会对应着一个ϑ,并且ϑ属于通过(0,1)形成的二进制向量，这个向量维数可以用N表示。

利用蛮力搜索就能够进一步求出ϑ的最优值所在的时间复杂度为O(2N)，基于此就能够再利用BPSO算法进一步求出最终的解。

为了判断粒子是否是最优的，需要通过目标函数进行计算，其中目标函数为系统整体负载φ

φ=γ1Tt+γ2Em

(12)

式中：γ1,γ2分别表示在卸载决策时计算任务延迟和能耗的权重。

(13)

(14)

其中，k代表的是具体的迭代次数，ω、g1以及g2代表的是不同的参数，通常情况下它们都为常数；rand()命令用来获得随机数，具体的范围是[0,1]。利用上面的这个计算公式能够对全部粒子的具体位置以及其相应的速度进行不断的迭代更新，然后对得到的数值取最优。

但是因为BPSO算法本身就决定了所有粒子得出的位置值都会在{0,1}范围内，所以还需要通过Sigmoid函数将其对应的速度重新进行映射至迭代更新之后的位置。具体如下

(15)

式中：wij∈[0,1]表示在[0,1]区间内均匀分布的随机数。

根据以上分析，利用BPSO的任务卸载具体过程如图3所示。

图3 基于BPSO的任务卸载流程

利用不同粒子的具体位置就能够进一步获取本地执行以及通过边缘计算执行两部分的具体的任务，这里用T1与T2分别表示。这样就可以得到相应的调度策略并从中择取最佳的一种方案。基于该方案可以计算出延迟时间以及相应的能耗，同时能够计算出粒子的具体位置。通过不断迭代就可以最终获得最优解。

4 仿真实验及分析

通过MATLAB仿真平台对所提任务卸载策略性能进行评估。在移动边缘计算网络模型中，移动设备数量为200个，基站数量为50个，云计算服务器为1个。相关的实验参数设置见表1。需要强调的是，在仿真实验中，边缘节点的设置相对更靠近于设备，而云服务器则远得多。

表1 仿真实验参数设置

4.1 参数讨论

为了分析BPSO算法中参数wij对任务卸载策略能量消耗的影响，通过改变参数值比较能量的消耗情况，具体结果如图4所示。这里做理想假设所有终端设备计算任务基本一致，且外部环境一致，仅仅改变wij的数值，实验中选取了3个不同的wij值对能量消耗曲线收敛的影响进行分析。

图4 参数wij对收敛性的影响

从图4中可以看出，当wij的值较小时，能量消耗曲线的收敛速度最快。因此，应当在合理的范围内选择相对较小的wij，以获得更好的收敛性能。

4.2 基站数量对所提策略能耗的影响分析

在所提任务卸载策略中，系统参数都会影响其性能和收敛性，例如基站总带宽、计算速率和传输速率的变化、移动设备和基站的数目等。为了对实验结果进行分析，筛选了若干个具有代表性的参数，其中基站数量对所提策略能耗的影响如图5所示。

图5 基站数量对所提策略能耗的影响

从图5中可以看出，在迭代开始之时的能量消耗远远高于在最终取得最优结果时的能耗。随着迭代的不断进行，在迭代次数为20左右之前，能量消耗一直急剧下降，而超过20次迭代之后，其能量消耗变化并不明显。经过大约40次迭代后，曲线实现近似的收敛，此时如果算法不要求更高的精度，那么收敛值就可作为卸载选择的最优解。需要注意的是，曲线上方的n=0直线表示计算任务只能在本地处理，在一定范围内，能量消耗随着基站数量的增加而减少。基站越多，完成计算任务卸载的能力越强，因此能量消耗随之减少。

此外，当结果接近收敛时，基站的数量对平均迭代次数的影响如图6所示。

图6 基站数量对平均迭代次数的影响

从图6中可以看出，当基站的数量越大时，卸载策略需要花费更多的时间和进行更多次迭代才能实现收敛。另外，将所提策略与文献[10]进行对比，由于文献[10]采用具有差分隐私的交替方向乘子算法，其收敛需要更多次迭代，且迭代过程受到高斯噪声的影响。而所提策略基于BPSO算法，寻优能力更强，因此能够以最少的迭代次数实现收敛。

信道带宽的变化对所提策略能量损耗的影响如图7所示。

图7 信道带宽变化对能量消耗的影响

从图7中可以看出，总带宽越大，能量消耗越低，并且随着带宽的增加，当带宽还处于一个较低水平时(如6 MHz)，能量消耗迅速降低；当带宽已经到达一个很高的水平时(如15 MHz)，能量消耗会缓慢降低。即较高的带宽会导致较低的传输延迟，而这就意味着处理每一位数据时的能量消耗较小。此外，边缘节点和移动设备之间的传输延迟远小于边缘节点和云服务器之间的传输延迟，因为基站建造时十分接近移动设备，而云服务器却离移动设备更远。因此，与卸载到云服务器相比，带宽的变化对卸载到基站这种方式的影响更小。

不同任务数据量大小对能量消耗的影响如图8所示。

图8 任务数据量大小与能耗的关系

从图8中可以看出，随着任务数据量的增加，能量消耗也随之增加，但是并不是线性变化。这是因为计算延迟或能量消耗远小于传播时的延迟与能量消耗，而且任务数据量的大小对传播时的能量消耗的影响也相对较小。在这种情况下，随着任务数据量的增加，总体的能量消耗会在一定范围内以逐渐减小的速度上升。

4.3 不同策略的对比分析

为了论证所提任务卸载策略的性能，将其与文献[10]、文献[13]、文献[17]中策略的能量开销进行对比分析，结果如图9所示。

图9 不同任务卸载策略的能量消耗情况

从图9中可以看出，随着移动用户数量的增加，文献[17]策略的能量开销略微高于所提任务卸载策略的能量开销，导致这一现象的原因在于该最优解的获取与迭代次数有着直接关系，如果迭代次数有限那么最终的结果仅仅就是一个局部最优的结果。利用BPSO则很好地解决了这一问题。因此相比于其它3种策略，其能耗最低。同时，文献[13]中通过深入分析发现本地计算所需要的能量远远超过了卸载方案，同时当终端设备数量不断上升时本地计算所需能量的增加也不是非线性的。在该文献中所选择的卸载方案对能量优化效果远远低于文中所提到的其它方案，导致这一问题的根源在于随机选择接入的条件下，如果同时接入基站的终端设备数量陡然增加，那么必然会造成同一个信道被多个设备使用，这样就使得前向以及后向链路都受到一定的作用从而降低了传输速度，这样能量损耗自然会有所上升。

此外，在不同移动设备数量的情况下，所提任务卸载策略与文献[10]、文献[13]、文献[17]中策略的系统整体负载对比情况如图10所示。

图10 不同任务卸载策略的系统平均整体负载情况

从图10中可以看出，文献[10]中采用本地执行方案，其具有最大的系统整体负载，在其余各个卸载策略中，其它方案都有效减少了系统的载荷，这也就意味着当任务卸载至边缘计算中后，用户可以得到更好的服务体验。所提策略的系统整体负载最低，比文献[10]策略相比，平均降低67.5%的系统负载，性能提升效果很明显。文献[13]采用随机卸载方案，其系统整体负载也较大，由于其随机地将任务卸载到边缘计算或者云计算服务器上，忽略了不同用户之间会有一定的干扰，所以有时卸载并未显著提高性能。与这两个文献不同的是文献[17]策略的系统整体负载明显降低，但仍高于所提策略，由于其忽略了在 MEC 服务器中的等待延迟。

5 结束语

随着移动互联网的快速崛起，各种终端设备被研发出来并且走入了人们的生活，但终端自身资源有限，无法满足部分应用对计算性能的需求，为此，充分挖掘边缘计算的潜力，尤其是对于技术上已经相对比较成熟的云计算如果能够将其运用至接入网络边缘，将会更大提升用户的体验感，本文提出了一种移动边缘计算中利用BPSO的任务卸载策略。基于构建的三层移动边缘计算(MEC)网络架构，并根据网络的计算模型、通信模型设计计算卸载优化目标，利用BPSO算法进行求解，以得到最优卸载策略，满足能量消耗小、时延低且整体负载均衡的需求。此外，基于MATLAB仿真平台对所提任务卸载策略的性能进行实验论证，结果表明，所提策略能够实现能量消耗曲线的快速收敛，基站数量越多、信道带宽越大，系统能量损耗越小，但移动设备越多，能耗越大。

本文提出的方案对于MEC节点计算具有显著效果，但是该方案首先要假定所有的CPU能耗均属于线性，也就意味着当占用率提高时该值并不会明显提升，这与现实情况有一定的差异。为了解决这一问题还要对CPU能耗开展深入研究并建立相应的数学模型，这将是下一步的研究重点。