基于粒子群算法的移动边缘计算任务分配方法

陈 刚，王志坚，徐胜超

(广州华商学院数据科学学院,广东 广州 511300)

0 引 言

在移动互联网[1]高速发展的同时，移动终端等设备逐渐替代了台式设备[2-3]，成为人们日常生活中不可缺少的主要工作设备，但因为物理大小的限制，目前的移动终端产品对问题的处理能力以及续航能力都不够理想，难以保证用户需求，极大降低了用户的体验感。移动终端的数据信息量常常以指数形式增长，这会加大数据传输时延，从而加快电池的能量消耗。通常情况下移动终端会将需要计算的任务分配到云服务器，降低移动终端计算时延，但同时会加长传输时延，这就需要进行移动边缘计算，该思想是利用与用户移动端较近的边缘网络资源，降低网络负荷以及传输时延，但需要合理分配任务。

文献[4]充分分析数据传输约束以及数据信息保密中断概率约束，在能耗权重因子的帮助下平衡系统能量消耗，满足上述条件后利用基于二分搜索的迭代优化算法，将其中的任务进行分配并得到最优解，实现移动边缘计算任务分配。文献[5]在单位时间总代价指标不断改进的帮助下得出边缘计算服务器，并选取出最适合自身的最小代价算法对任务进行分配，生成在特定约束条件下的任务分配方案，实现移动边缘计算任务分配。文献[6]为克服任务分配不准确或分配效率低下等问题，提出了一种新的MCS任务分配方案。先基于用户附近的多个边缘计算节点，将用户和附近的用户聚合为组来协同参与MCS任务分配，然后基于Johnson-Lindenstrauss(JL)变换进一步增强位置隐私保护效果，最终实现了精确的任务分配，提升了分配效率和分配准确度。文献[7]方法为保证用户服务质量，最大化系统的能量效率，提出了一种基于分组异构网络节能资源分配方法。该方法先将非凸优化问题转化为凸优化问题，将分数形式问题转化为等价的减法形式问题，提出了一种迭代功率分配算法，以使分配后的系统能量效率最大化。然后利用拉格朗日方法推导了最优闭式功率分配表达式，最后利用该公式完成资源分配。

以上几种方法分配结果中部分分配不理想，存在任务分配计算时间长、能量消耗大和数据传输的时延长的问题。造成问题的原因主要在于其并未对模型分配的最优解进行计算，其优化的效果并不好。群体智能算法可以对资源分配的最优解进行很好的优化，粒子群算法是通过模拟鸟群觅食这一行为而发展起来的一种基于群体智能的随机搜索算法，利用该算法可以较快地求取最优解。基于此，为解决上述方法中存在的问题，本文引入粒子群算法，提出基于粒子群算法的移动边缘计算任务分配方法。

1 移动边缘计算任务分配

1.1 任务分配调度原理

图1 基站协同合作示意图

移动边缘计算是将网络控制、数据处理和相关存储迁移到网络边缘，为覆盖范围内的移动用户提供较好的密集型计算服务。本文主要研究的任务分配方法是要实现基站与用户之间的互动，在用户密集且流动性大的情况下实现任务合理分配，其多基站协同合作的示意图如图1所示。

移动边缘计算任务分配调度质量取决于边缘基站计算资源的分配。要想实现边缘云中资源的公平合理分配，就要对智能边缘基站进行研究。边缘云为基站分配任务时，需要考虑2个因素，分别为数据传输速率和任务执行能耗。通过任务分类合理化的方式提高数据传输速率，将优先级高的任务卸载到边缘基站中，优化资源调度程序。除此之外，基站的能耗是一定的，应在提供能量一定的前提下，让基站能源的总消耗小于所有任务执行任务结束时的总和。本文基于以上2个要素完成任务分配范围的划定，然后基于粒子群算法求得任务分配的最优解，使其既可节约能源，又可提高任务分配质量和分配效率。

1.2 任务分配范围

为能有效研究移动边缘计算的任务分配问题[6]，首先建立一个异构网络[7]，设该异构网络中存在N个移动设备及一个移动应用[8]，设置的移动应用内部存有M个具有相关性的任务。

(1)

其中，xik表示任务分配矩阵。

当不同的任务i分配到设备上时，所产生的上传、下载、计算延迟均由下述方程定义，标记如下：

(2)

通过方程(2)计算出任务在上传、下载、计算过程中的总耗时，用方程表达式定义如下：

(3)

(4)

(5)

而任务i的总时延定义为：

(6)

其中，Dik表示上传、下载、计算过程中的总任务数量。

以式(3)～式(6)为基础，计算任务目标在设备中的总能量消耗，定义为：

(7)

(8)

其中，Ecomp表示总计算能量消耗，PR0表示移动设备的计算能力，ETP表示总无线传输能量消耗，PUL表示设备任务上传的能力，PDL表示设备任务下载的能力。

基于上述可知，移动边缘计算任务的总能耗[11-12]及任务执行时延定义为：

(9)

其中，E(X,R0)表示总能耗，T(X,R0)表示总执行延时。

为了能够合理分配任务[13]，任务在分配过程中的能耗、时延均衡[14]，设置任务最小化目标的设备能耗及时延为总体代价[15]，从而取得任务目标函数即min(γ(X))：

γ(X)=αT+(1-α)E

(10)

其中，min(γ(X))表示优化目标函数，αT+(1-α)E表示求解目标函数的方程表达式。E表示任务分配时消耗的总能耗，T表示总延时，α表示时延权重，(1-α)表示能耗权重。

令α满足0≤α≤1的条件，使各个设备的任务量均在移动终端设备指定范围内[3]，CPU频率调节范围具有有限性，并在分配每个任务时保证各个任务可分配到指定的移动设备中[16-18]。

1.3 移动边缘计算任务分配实现

通过上述对移动边缘计算任务分配的优化[19-20]，采用粒子群算法获取最优分配解[21]。首先利用上文的任务分配范围可将粒子的分配半径进行设置，将最大分配半径和最小分配半径设置为粒子的搜索空间范围，即基站与任务之间的最短距离为分配半径下限，反之基站与任务之间的最长距离为分配半径上限，则设置其粒子空间搜索范围为[min(γ(x)), max(γ(x))]，将基站数量R设为粒子维数,由此生成以各个基站为中心，R个分配半径为γ1,γ2,…,γR的圆。然后设置任务定义方向系数，即：

(11)

其中，Nd表示最大迭代次数，t表示当前迭代次数，h表示方向系数。h在初始阶段的搜索范围较大，最终搜索范围会缩短，可有效预防粒子在计算过程中出现的发散问题。

将粒子群体中的最优粒子的加速常数及随机常数相结合，其加速常数分别为sp、sg，随机常数为rp(t)、rg(t)，此时粒子个体的远离因子b1为：

b1=h·sp·rp(t)

(12)

而粒子全局远离因子b2为：

(13)

基于粒子群算法更新粒子速度及所处位置[22]，其更新方法定义如下：

(14)

Xi(t+1)=Xi(t)+Vi(t+1)

(15)

其中，ω表示惯性权重，通常取值为0.7～1.5，可达到提升收敛速度的目的，同时能够有效均衡收敛速度。Pbesti表示个体最优解，Gbesti表示全局最优解，Pworsti表示粒子以最优状态为主向前前进，Gworsti表示粒子与最劣解的距离。

基于粒子群算法对粒子速度及位置的更新，完成移动边缘计算任务的分配。在进行任务分配的过程中，还需要考虑基站之间相互协调的问题：1)在粒子位置的更新的过程中，由于相交处存在任务会造成任务重叠问题，此种情况下可将任务分配给任意一个或者分配给任意几个；2)利用粒子群算法进行优化的过程中如基站的任务数量超过其荷载，需要对超出的任务进行舍弃，以确保其可完成该任务。基于粒子群算法的任务分配协调流程如图2所示。

图2 移动边缘计算任务分配流程图

2 实验结果与分析

2.1 实验环境设置

本文实验在一台操作系统为Windows 10的笔记本电脑上进行，电脑的配置为IntelCore-i5-6500@3.2 GHz处理器、4 GB内存。以Matlab 2016a为实验平台，由于边缘云的任务分配受到多因素影响，故对基站部署方式、用户量及所处物理环境进行设置。为验证实验结果，在调整用户规模与基站数量时假设其余条件均相同，其实验参数设置如表1所示。

表1 实验数据参数

为验证基于粒子群算法的移动边缘计算任务分配方法的整体有效性，选取边缘计算任务安全分配方法和车联网下移动边缘计算任务分配方法为对比方法，与本文方法共同进行任务分配计算时间、能量消耗和数据传输时延的测试，同时分析测试结果。

2.2 任务分配计算时间

移动边缘计算任务分配的主要作用是减少数据传输延时，提高移动终端计算能力，降低终端计算产生的能量消耗。已知实验过程中移动端需要进行分配的任务数量在10个～100个之间，随机选取不同数量的任务，利用本文方法与其余2个方法对其进行分配，得出每组实验下不同方法所需的任务分配时间，以此论证本文方法的有效性，实验结果如图3所示。

根据实验结果可知，在分配任务数量为20个～100个之间时，本文方法任务分配的计算时间为1 s～3.3 s，而边缘计算任务安全分配方法的任务分配计算时间为1.6 s～3.9 s，车联网下移动边缘计算任务分配方法的任务分配计算时间为2.5 s～4.5 s，由此可证明，在不同任务数量下，移动边缘计算的任务分配所需时间最短的均是本文方法，本文方法效率较高。分析原因是本文采用了粒子群算法对任务分配的最优解进行了优化。

图3 3种方法的任务分配计算时间

2.3 能量消耗

移动终端在计算过程中不可避免地产生能量消耗，目前的移动终端设备由于各种限制，其电量过小，边缘计算时间过程或运算量过大都会导致能耗的迅速上升，能量的快速消耗无法满足用户需求。为此在上述环境下选取不同数量的任务，利用3种方法对其进行分配，令3种方法的分配效果一致，得出每种方法所需的能量消耗，消耗越低该方法的分配能力越强，实验结果如图4所示。

图4 3种方法的能量消耗

根据实验结果可知，在其余条件均相同的情况下，能耗最低的都是本文方法，当任务数量为100时，本文方法能耗仅为4107 J，而边缘计算任务安全分配方法消耗能量为12000 J，车联网下移动边缘计算任务分配方法消耗能量为16000 J，本文方法所消耗的能量远远少于其余2种方法，由此验证了本文方法节能性更优。

2.4 数据传输的时延

为进一步论证本文方法的可行性，从分配的另一个角度出发，分配的目的是减少时间延迟，因此在不同任务到达率下判断每种方法的时延，时延越短说明方法的能力越强，实验结果如图5所示。

图5 3种方法的时间延迟

依据图5数据可知，本文方法在任务达到率达到100%时，其时延仅为12.5 ms，而边缘计算任务安全分配方法的时延为20 ms，车联网下移动边缘计算任务分配方法的时延为24.7 ms，由此可证明本文方法数据传输的时间延迟最短，优于对比方法。

3 结束语

移动终端设备的普及十分广泛，但移动终端最大的缺点是不能承受过大的能耗，为此本文提出基于粒子群算法的移动边缘计算任务分配方法。该方法通过对任务分配的分析将其问题转化生成分配任务最优解，在粒子群算法的帮助下完成任务分配，实现移动边缘计算任务分配，解决了任务分配计算时间长、能量消耗大和数据传输的时延长的问题，接下来移动终端的方向是如何在不改变移动终端物理大小的方向下加强对运算能耗的承受能力的研究[24-27]。