基于蚁群算法的移动边缘服务器收益优化策略

黄冬艳 付中卫 李 浪

(桂林电子科技大学广西无线宽带通信与信号处理重点实验室 广西 桂林 541004)

0 引 言

随着5G网络的普及，依靠其衍生出来的新型应用，如车联网、远程医疗、虚拟现实、增强现实等得到快速发展。但由于移动设备和物联网设备计算能力和电池容量受限，这些新型应用和服务难以部署。为了解决这个问题，近年来研究人员提出了移动边缘计算[1]。

在移动边缘计算的架构中，边缘计算服务提供商在无线接入网边缘为移动设备提供云计算能力[2]，从而创造出一个具备高性能、低延迟与高带宽的电信级服务环境。用户通过将应用程序的计算任务卸载到边缘服务器端进行计算，可实现超低计算延迟。

在移动终端进行计算任务卸载时，为实现如能耗、延迟等性能的优化，需要判断是否将计算任务全部或部分卸载至边缘服务器执行，这被称为计算分区问题[3]。很多文献以移动设备的能耗[4]、应用延迟[5-7]和网络上的数据传输量等因素中的一个或多个的组合作为优化目标，提出了不同的计算分区问题模型。

在文献[4]中，为使设备能耗或任务延迟达到最小，作者分别提出了能耗最小、延迟最小的卸载算法，对移动设备的计算资源、传输功率和任务卸载比例进行联合优化。文献[5]在双时间尺度的情况下，采用马尔可夫决策过程方法，提出一个一维搜索算法，搜索出最优调度策略，实现了在设备能耗约束下的计算延迟最小化。文献[8]以用户的QoE作为优化目标，提出一个近似动态规划算法，找出任务最佳卸载策略。

然而，文献[4-5，8]主要研究用户独立模型下的计算分区问题，只针对单个用户进行计算分区，而不考虑其他用户的分区结果。在实际过程中，通常会出现多个用户共同占用边缘服务器计算资源的现象。由于移动边缘服务器计算资源受限，不能同时接受多个用户的卸载请求，因此多用户分区问题也是移动边缘计算的研究热点。

文献[3]考虑了如SIFT算法这类子任务执行关联性的情况下，多用户计算任务的划分以及云计算资源的调度，根据云服务器的资源占用情况，提出了SearchAdjust算法来解决多用户分区问题，使得用户的平均完成时间最小化。文献[6]考虑了如何对延迟敏感型应用计算分区和对移动边缘服务器资源分配，使得用户整体延迟达到最小。为解决该问题，设计了一种多维搜索和调整算法(MDSA)。文献[7]研究了多用户的网络感知环境下，通过对用户任务的计算分区和边缘服务器的带宽资源分配，使用户的平均吞吐量(应用程序每秒处理的数据单元数)最大化。

以上文献主要考虑通过计算分区技术使得用户获得最大的收益(如最小化计算延迟或能耗)。事实上，为了收回设备的部署和维护成本并盈利，MEC服务提供商如何利用有限的计算资源来最大化其利润，也是一个亟待解决的问题，但是以MEC服务器收益为优化目标的研究较为少见。

本文研究多个用户对边缘服务器端计算资源存在竞争且每个用户会在本地做出最小化自身成本(计算延迟和花费加权和)的卸载决策的情况下，MEC服务器提供商通过采用合适的资源分配策略实现其收益(利润)的最大化。本文的主要贡献如下：1) 在用户子任务具有顺序执行的关联性及用户之间对金钱和延迟的偏好程度不同的场景下，建立以服务器端任务执行次序为变量的服务器收益最大化模型；2) 提出基于蚁群算法求解任务最佳分区及服务器端任务最佳执行次序的算法。

1 系统模型及问题建模

1.1 系统模型

为了获得更好的用户体验，当执行某些延迟敏感型应用时，如无人驾驶、增强现实、人脸识别等，用户会将程序中的某些进程卸载至云端执行以获得更小的计算延迟。

如图1所示，考虑多个计算密集型任务占用单个MEC服务器的重业务场景，然后建立多用户MEC系统模型。该MEC系统由两部分组成：移动边缘服务器和移动客户端。任务卸载具体流程如图2所示。在移动客户端处，客户端中间件的监视代理程序收集设备的计算能力、任务大小等信息，当用户向边缘服务器发送卸载请求时，这些信息随请求一起发送到边缘服务器端，服务器端在接收到用户的请求后，将空闲计算资源分配给请求用户并为请求卸载任务进行执行排序，然后将资源分配信息反馈至终端设备，终端设备在本地做出最小化自身成本的卸载决策。本文中的符号和含义如表1所示。

图1 多用户MEC系统

图2 MEC系统任务卸载流程

表1 符号及其含义

(1)

本地计算花费为：

(2)

令xi,j=1表示任务(i,j)在服务器端计算，其计算时间为：

(3)

(4)

任务(i,j)在服务器端计算花费为：

(5)

为保证任务之间的执行顺序，令z(i,j),(i′,j′)=1表示任务(i,j)在任务(i′,j′)前执行，z(i,j),(i′,j′)=0表示任务(i′,j′)在(i,j)前执行。

1.2 问题建模

(6)

IN×(2-xs(o)-xs(k)),k≠o,1≤o≤K；

式中：约束条件C1保证单个用户各个子任务间执行顺序；约束条件C2保证两个不同用户子任务的服务器端执行次序；IN表示正无穷大的数；约束条件C3保证卸载任务在服务器端执行时开销小于在本地执行开销；约束条件C4限制卸载变量xs(k)取值0或1，保证子任务的本地计算时间、服务器端等待时间、服务器端计算时间大于0；约束条件C5保证在边缘服务器端闲置的时候，卸载至边缘服务器端的计算花费要小于本地计算花费。

2 算法设计

为求解问题P1，需要在K个任务的K!个排列集合中，找出令边缘服务器端获得最大收益的一个排列，因此问题P1为组合优化问题[10]。解决该类问题可以使用启发式算法、近似算法和枚举法。当问题规模较大时，枚举法求解时间过长，近似算法难以找出精确解，因此本文采用启发式算法中具有较强的全局寻优能力和较强的鲁棒性的蚁群算法[11]寻找多个请求卸载任务的最佳执行次序。本文算法流程如图3所示。

图3 本文算法流程

本文算法具体步骤：

1) 计算在服务器端资源未被占用时，各个任务的子任务最佳分区决策。

2) 计算服务器资源占用列表Lcro。

3) 从Lcro中搜索服务器端的冲突的任务集合Lcon，其搜索步骤为：

(1) 搜索在Lcro中，最先在服务器端完成任务。

(2) 搜素出与此任务在服务器端执行时间相互冲突的任务。

(3) 将此任务与其冲突的任务放在集合Lcon中。

4) 应用蚁群算法搜索出Lcon中冲突任务执行的最佳次序，其执行步骤为：

(1) 对相关参数进行初始化，信息启发式因子α=1、期望启发因子β=5、信息素挥发系数ρ=0.1、信息素强度Q=100、最大迭代次数N=500、蚂蚁个数为Lcon中冲突任务个数m。

(4) 当所有蚂蚁经过一轮路径选择后，对路径上的信息素浓度进行更新。

(5) 判断是否达到最大迭代次数N，若否，返回步骤(3)继续循环；若是，结束蚁群算法程序循环，输出冲突任务Lcon最终执行次序Scon及其收益。

6) 服务器端任务执行次序S中所包含的任务为卸载计算任务，剩余任务为本地计算任务，得到各用户的分区策略。

算法步骤2)中所述的云端资源占用列表Lcro为包含每个用户子任务在云端的开始时刻和完成时刻。

算法步骤4)中蚂蚁k随机选择下一任务的概率：

(7)

式中：τi1j1,i2j2(t)为边(i1j1,i2j2)上的信息素；ηi1j1,i2j2(t)为启发式函数，alloweCk为蚂蚁k待访问的任务集合。

启发式函数ηi1j1,i2j2(t)的更新规则为：

ηi1j1,i2j2(t)=revenuei1j1,i2j2/max(revenue)

(8)

式中：revenue为各个子任务需交付费用集合；

步骤4)中，m只蚂蚁完成一次循环后，各个任务连接路径上的信息浓度更新为：

τi1j1,i2j2(t+1)=(1-ρ)×τi1j1,i2j2(t)+Δτi1j1,i2j2(t)

(9)

式中：Δτi1j1,i2j2(t)为所有蚂蚁在子任务(i1,j1)与子任务(i2,j2)连接路径上释放信息素而增加的信息素浓度。Δτi1j1,i2j2(t)的计算为：

(10)

(11)

3 仿真结果及分析

假设每个用户有5个待卸载子任务，子任务之间存在顺序执行的关联性；服务器端有两个收费标准可供用户选择，每个用户从两个收费标准中随机选择一个。参照文献[12-13]，具体参数设置如下：向服务器端发送请求的用户总数在[5，90]范围内；两收费标准分别为(CPU的单个时钟周期内)u0=1×10-9元,u1=0.5×10-9元，每个子任务所需要的CPU周期在0.1～1 GHz随机取值，每个设备的计算能力在1～2 GHz随机取值。然后，对SearchAdjust算法改进，使得其优化目标函数为边缘服务器收益，在相同参数下对改进的SearchAdjus[3]算法与本文算法进行仿真对比。

仿真时，设置蚁群的数量为冲突任务的个数大小、迭代的最大次数为500，信息启发式因子为1，期望启发因子为5，信息素挥发系数为0.1，信息素强度为100，使用MATLAB R2012a版进行仿真。

图4比较了在边缘服务器计算能力为fc=4 GHz和fc=12 GHz的条件下，本文算法与基准算法的边缘服务器收益。从仿真图可得，两种算法所获得的收益都随着用户的增多而增多，但本文算法的收益增速要大于基准算法。当用户数目为90、fc=4 GHz时，本文算法的收益相比基准算法提高了33.6%；当用户数目为90、fc=12 GHz时，本文算法的收益相比基准算法提高了49.9%。这是因为随着计算能力的提高，相比较SearchAdjust算法，本文算法在各任务可容忍执行期限内可以处理更多的任务。

图4 不同算法的MEC服务器收益对比

图5比较了在边缘服务器计算能力fc=4 GHz和fc=12 GHz的条件下，本文算法与基准算法在用户数目不同的情况下的每用户平均延迟。从仿真图中可得，两种算法中每用户平均延迟都随着用户增多而增多。当用户数目为90、fc=4 GHz时，本文算法的每用户平均延迟相比基准算法增加1.6%；当用户数目为90、fc=12 GHz时，本文算法的每用户平均延迟相比基准算法增加了6%。结合图4，可以得出本文算法是以牺牲较低的用户的平均延迟为代价，极大提高了MEC服务器的收益。

图5 两种算法每用户平均计算延迟

4 结 语

本文研究了5G网络中移动边缘计算的多用户分区问题，以最大化MEC服务器收益为优化目标，提出基于蚁群算法求解服务器端任务最佳执行次序的算法，以获得最优的任务分区策略和最佳任务执行次序。仿真结果表明，在用户子任务具有顺序执行的关联性及用户之间对金钱和延迟的偏好程度不同的场景下，本文算法能够明显提高MEC服务器的平均收益。下一步工作将在多个边缘服务器相互协作的场景下，研究用户QoE约束下的多个边缘服务器的收益最大化策略。