基于改进蚁群算法的边缘计算迁移策略

刘雨忻，马占飞，林继祥，巩传胜，李克见

（1.内蒙古科技大学信息工程学院，包头 014010；2.内蒙古科技大学包头师范学院计算机系，包头 014030）

0 引言

随着物联网技术的创新和发展，物联网的应用场景越来越多样化，如智慧交通、智慧农场、智慧医疗等。这些物联网的应用领域会产生大量的计算密集型和时延敏感型任务，如果将这些任务上传到云端执行不仅会增加传输链路和云端的负担，还会造成一定的时延。为了解决上述问题，2014年，欧洲电信标准化协会ETSI提出了一个新的概念，即移动边缘计算（Mobile Edge Computing，MEC），并指出移动边缘计算区别于云计算，是一种在移动网络边缘的位置提供IT服务环境和计算能力的新型架构。后来随着研究的不断深入，边缘计算也用于Wi-Fi、固网接入等多种接入网络架构，因此其概念也被扩展成为多接入边缘计算（Multiaccess Edge Computing，MEC）。边缘计算迁移卸载最早由文献［3］提出，是指将资源受限的移动设备或终端上的任务交由计算和存储能力强的其它设备处或者边缘服务器处执行，从而减小终端的压力，提高终端的使用寿命，增强用户体验。

1 相关工作

文献［4］提到边缘计算已经成为解决物联网（Internet of Things，IoT）和本地计算的一种新范式，将各种计算任务或存储任务迁移到终端用户附近的网络“边缘”位置，在贴近网络边缘处完成数据的处理和存储等操作，从而减少数据传输到云端执行的成本和时间。因为边缘设备的计算能力和存储资源相对于大型服务器是有限的，所以无法支持复杂任务的执行，因此需要将这些任务迁移到其他资源比较丰富的终端去执行。文献［5］将计算迁移分为4个阶段，分别为分布式计算阶段、普适计算阶段、云计算阶段和边缘计算阶段，并说明计算迁移的目标是根据某一种决策方式，把当前节点存在的某些任务迁移到其他节点的一种优化方案。文献［6］认为计算迁移属于边缘计算原生性技术之一，并将计算迁移技术分为计算迁移决策机制设计和计算迁移资源优化调度机制，其中计算迁移决策要解决的关键问题为是否要进行迁移、要进行哪些任务迁移以及要将任务迁移到哪里的问题。文献［7］提出一种新型的动态分布式异构任务卸载算法，利用分布式博弈机制并结合李雅普诺夫优化理论，设计了一种动态报价机制，这种机制可以实现对不同资源的按需分配。文献［8］通过考虑影响任务执行时间的因素，应用遗传算法以简单有效的方式分配边缘设备上的任务，使得任务执行的时间最小。文献［9］提到边缘设备的物理资源是有限的，其物理资源一般要远小于云计算中心的资源，因此如果有大量的、较复杂的并发任务被分配到某一边缘设备上时，会有一部分任务不能及时执行，此时这些任务只能在边缘设备处排队等候执行。文献［10］首先利用非支配排序遗传算法将任务迁移的时间和负载情况进行联合优化，找到比较有效的迁移策略，再利用多目标决策准则和逼近理想解排序法选择最优迁移策略。文献［11］建立了节点服务质量可信模型，并且从3个维度对任务迁移节点进行了综合评价，筛选出一些可以迁移的节点，最后利用灰色关联分析法选择出最终可以迁移的节点。文献［12］提出了一种节能的计算迁移方法，该方法既优化了任务卸载问题，同时也解决了无线资源分配问题，以便在时延约束下使得能量消耗最小。文献［13］综合考虑了计算资源、带宽，构建了一个最小化时延和能耗的问题，并利用异步云边协同的深度强化学习方法进行求解。

在移动边缘计算中，任务卸载迁移的方式有两种，一是将任务迁移到MEC服务器上；二是将任务迁移到周围闲置的边缘设备中，本文考虑将任务卸载迁移到MEC服务器中。文中首先根据各个边缘设备的负载情况筛选出需要迁移的任务，然后构建时延模型、任务匹配度模型和负载模型，对蚁群算法进行改进，应用改进的蚁群算法求解出最优的迁移策略，以保证在进行迁移后任务的执行时间和边缘设备的负载都处于一个较低的水平。

2 边缘计算任务迁移模型

2.1 问题模型

本文首先给出了边缘计算任务迁移系统模型图，如图1所示。在一定区域内有许多边缘设备，由边缘服务器对这些边缘设备进行统一管理，边缘服务器与上层云端直接相连，其中边缘服务器分为边缘管理服务器和边缘计算服务器。边缘管理服务器负责实时收集边缘设备的信息并做出迁移决策，将决策结果返回给边缘设备，各个设备按照决策结果将任务直接发送到相应的边缘计算服务器中，由边缘计算服务器执行计算任务，文中将边缘计算服务器和边缘管理服务器统称为MEC服务器。进行任务迁移的目的是减少任务执行的时间，并平衡此区域内MEC服务器的负载。

图1 边缘计算任务迁移系统模型图

2.2 问题定义

假设在一定区域内的边缘设备中产生了个任务，这些任务可以表示为T ={,,…,t }，每一个任务都包含如下几个属性，t ={,,,,}，表示任务编号，、、、依次表示任务需要的cpu资源、内存资源、带宽资源和任务大小。假定在此区域内有个MEC服务器可以提供计算和通信服务，边缘计算服务器的集合表示为{,,…,d }，每一个MEC服务器自身能提供的可用资源如下，d ={,,,}，表示边缘计算服务器的编号，表示MEC服务器中可用cpu资源、表示MEC服务器中可用内存资源、表示MEC服务器中可用带宽资源。用表示任务是否要迁移到MEC服务器执行，的取值是∈{0,…,}，=0表示任务在本地执行；=表示任务迁移到第个MEC服务器处执行。

2.2.1 任务时延模型

首先定义任务在MEC服务器执行的时间矩阵：

其中，time 表示第个任务迁移到第个MEC服务器的总期望执行时间，总执行时间分为任务传输时间tr 、任务在MEC服务器处的执行时间ex ，因为任务执行完成后将结果回传到本地设备的时间很短，可以忽略不计，所以任务迁移到MEC服务器的期望执行总时间为：

=0表示任务在本地执行，=表示任务迁移到第个MEC服务器执行。

当任务在本地设备执行而不需要进行迁移时，只存在任务执行时间而不存在任务在链路中的传输时间。其中将任务传输时间定义为：

2.2.2 任务匹配度模型

在选择MEC服务器时，不同任务对资源的需求程度不同，且每一个MEC服务器能够提供的资源类型不同，比如一个任务是计算消耗型任务，则需要选择计算能力较强的MEC服务器。因此如果想让任务高效执行，那么就需要将任务需求的类型与边缘设备能够提供的资源类型进行匹配，用匹配度来表示任务和边缘设备的匹配结果，将匹配度定义为当前任务的资源请求量与边缘设备提供的资源量的差值。

、、分别为各个差值的权重，m 的值越小，说明任务需求的资源与MEC服务器所能提供的资源越匹配，匹配度越高，任务更偏向于在匹配度高的MEC服务器中执行。

2.2.3 任务负载模型

进行任务迁移时，要考虑当前设备和MEC服务器的负载情况，如果当前设备负载较高，则应对当前设备上的任务进行迁移操作，以降低设备负载，同时需要选择负载较低的MEC服务器作为任务迁移的目的地。边缘设备负载函数定义为：

其中，T 表示第个边缘设备已经执行任务的时间，T 表示所有边缘设备平均执行任务的时间。T 的值越小，说明边缘设备执行任务的时间较短，负载较小，Load 的值也较小。反之，边缘设备执行任务时间较长，负载较大，Load 的值也较大。

2.2.4 目标函数构建

针对多目标优化问题，利用线性加权方式将其转换成为单目标问题，进行归一化处理后，构建时间和匹配度的目标函数。

、分别表示时间和匹配度所占的权重，+=1且＞0，＞0。

3 基于改进蚁群算法的边缘计算任务迁移

蚁群算法是一种典型的群智能优化算法，常被用于解决路径选择、资源调度等一些常见问题，文献［14］为了提升蚁群算法的收敛速度，引入动态更新挥发系数，在信息素更新过程中引入负载权重系数来平衡负载。文献［15］提出一种测试任务并行任务调度优化方法，并对蚁群算法进行改进，包括对启发式函数和信息素更新规则的改进，提出了一种资源均衡度评价标准，最终求得了测试时间最短、资源最均衡的任务调度序列。

3.1 改进的蚁群算法

在蚂蚁搜索过程中，蚂蚁为每一个任务选择合适的MEC服务器，将状态转移函数、信息素更新过程进行了改进，具体改进方法如下。

3.1.1 初始化

首先对蚂蚁个数、迭代次数、信息素矩阵进行初始化操作，其中用每个MEC服务器的固有属性作为信息素矩阵的初始化值，如公式（11）所示：

3.1.2 选择下一个节点

根据公式（12）中的信息素浓度和启发因子来综合考虑，得出相应的概率值，并采用轮盘赌方式进行选择。

其中()代表每一条路径上的信息素浓度，()代表蚂蚁对某个路径倾向程度。本文针对公式（12）中启发式因子η()做出如下改进：

Load 代表MEC服务器的负载情况，L oad 越小，表明此设备的负载值越小，η()的值越大，启发函数值越大，蚂蚁越容易选择此边缘设备。

3.1.3 信息素更新

信息素的浓度是指导蚂蚁搜索的关键，蚂蚁在搜索时会偏向信息素浓度高的地方，因此为了让信息素更好地指引蚂蚁搜索，需要不断地对每一个路径进行信息素更新，这样可以防止信息素过多积累而过早收敛，同时也可以防止信息素挥发过快而错过最优解。信息素更新公式如下：

式中τ()为更新前信息素浓度矩阵，记录了进行信息素更新之前每条路径上的信息分布情况，为信息素挥发系数，因为信息素不断挥发的原因，导致在每一次迭代中，每条路径上的信息素也会随着迭代次数的增加而逐渐下降。Δτ是每一次更新过程中信息素增量的定义，也就是信息素改变了多少。Δτ分为局部信息素的更新和全局信息素的更新，即：

当一只蚂蚁完成了一次搜索后，对该蚂蚁的匹配路径进行局部信息素的更新，定义信息素更新公式中的Δ为：

其中，为信息素常量，为目标函数的值，越小，路径上增加的信息素就越多。

当所有蚂蚁都完成了一次搜索后，即所有蚂蚁都找到一组分配结果，此时记录本次迭代中最优的分配结果，然后进行全局信息素更新操作，即：

是一次迭代中的最佳分配结果。

3.2 算法总体流程

算法详细步骤如下：

Step 1：根据公式（9）判断边缘设备上的任务是否超过平均负载，将超过负载的边缘设备上的任务加入到待迁移队列中。

Step 2：初始化蚁群算法的相关参数，包括蚂蚁个数、最大迭代次数MaxCycle等，并根据公式（11）对信息素浓度进行初始化。

Step 3：将蚂蚁随机放置在边缘设备上。

Step 4：根据公式（12）和公式（13），计算蚂蚁为任务选择边缘设备的概率，并采用轮盘赌算法进行选择。

Step 5：当一只蚂蚁对所有任务都选择了相应的边缘设备，根据公式（14）和公式（15）进行局部信息素更新。

Step 6：当所有蚂蚁都完成了任务与边缘设备的分配操作，则应保留下最优的分配策略，并根据公式（14）和公式（16）对全局最优分配策略的信息素进行更新操作。

Step 7：判断当前迭代次数是否超过最大迭代次数，若没有，则跳转至Step 3继续进行迭代；若超过了最大迭代次数，则输出最优的分配策略。

图2 算法流程图

4 实验分析

通过CloudSim平台对本文改进的蚁群算法进行仿真实验，并与轮循算法和标准的蚁群算法结果进行对比。

4.1 参数设置

将任务数量设为50、100、150、200，任务长度设为5000MI～10000 MI，所有任务随机生成。将MEC服务器的数量设置为6个，其具体参数设置见表1。

表1 MEC服务器的参数配置

本文改进的蚁群算法和标准蚁群算法设置了相同参数，具体参数设置见表2。

表2 蚁群算法的参数设置

4.2 结果分析

首先随机生成一定数量的任务，判断本文算法产生的迁移策略与任务执行时间的关系。在执行相同数量任务时，三种算法产生不同的迁移结果，执行完每种迁移策略后任务的完成时间与任务数量的关系如图3所示。

图3 三种算法的完成时间

从图3可以看出，随着任务数量的增多，轮循算法和标准蚁群算法的任务执行时间增长迅速，但是两种算法做出的迁移策略使得任务执行的时间相差不大。而随着任务数量的增加，本文算法的任务执行时间虽然也在增长，但是增长幅度不是很大，并且远小于轮循算法和标准的蚁群算法，显然本文做出的迁移策略相较于其他两种算法在执行任务花费的时间上是相对较优的。

对于负载均衡的判断，本文采用了文献［16］的负载均衡度判断方法，即用负载均衡标准差作为负载均衡度的判断依据。

L 表示所有MEC服务器的平均负载，表示单个MEC服务器的负载情况，即MEC服务器已经执行任务的时间，表示MEC服务器的总数，负载均衡标准差用表示，即MEC服务器的负载均衡度，的值越大，负载均衡度越大，说明MEC服务器的负载越不均衡。

保持MEC服务器的数量一定，不断增加任务数量，根据迁移之后负载均衡度对不同任务数下的边缘设备负载情况进行判断，结果如图4所示。任务数量一定而边缘设备数量不同时，每个边缘设备的负载也会有所不同，将任务数量固定为200，将边缘设备数量置为4、6、8、10时，边缘设备的负载均衡度如图5所示。

图5 不同MEC服务器数量的负载均衡度对比

由图4可知，随着任务数量增加，各个MEC服务器的负载均衡度也逐渐上升，但本文算法对应的每个MEC服务器的负载均衡度都要优于其他两个算法中的负载均衡度。当任务数量相同时，轮循算法和标准蚁群算法计算得出的负载均衡度高于本文算法，这是因为本文算法在选择目标设备时考虑到了负载的影响，因此负载均衡度相对其他两种算法较低。

图4 不同任务数下的负载均衡度对比

由图5可以看出，当任务数量固定时，MEC服务器的负载均衡度随着服务器的增多而下降，因为任务都被均匀分配到了每一个服务器上，因此服务器的负载均衡度呈现下降趋势。由于本文算法考虑了负载的影响，所以无论边缘设备的数量如何变化，负载均衡度相较于轮循算法和标准蚁群算法总是较低的。

5 结语

本文针对边缘设备的计算迁移工作展开了研究，构建了任务与边缘服务器间的时延模型、任务匹配度模型和负载模型，利用构建的模型对标准蚁群算法进行改进。利用设备的固有属性作为信息素初始化依据，利用设备负载信息改进状态转移函数，使得任务更容易找到负载较低的边缘服务器，其次将所构建的目标函数作为信息素更新规则，仿真结果表明改进的算法既减少了任务执行的时间、也降低了边缘服务器的负载均衡度。