一种多边缘协作的任务卸载策略*

徐永杰,李 晖,2,兰 松,徐文校,于心远,杨山山

(1.南京信息工程大学 电子与信息工程学院,南京 210044;2.无锡学院 电子信息工程学院,江苏 无锡 214105)

0 引 言

随着物联网的快速发展,网络边缘设备已经产生了海量的数据,给通信带宽资源带来了巨大的挑战。与此同时,应用对数据速率和服务质量的要求也越来越高,传统的云计算模型已经无法有效应对,因此移动边缘计算(Mobile Edge Computing,MEC)应运而生[1]。MEC并不是取代云计算,而是云计算的补充和拓展。MEC更加靠近用户层,不仅可以向用户提供任务计算和内容缓存等服务,还可以减少终端的能耗和降低用户与云服务器之间频繁地交互,减轻了云层的压力[2]。其中,计算卸载技术是MEC中最为关键的技术,主要包括卸载策略和资源分配两个方面[3]。一般来说,计算卸载的优化目标有三种,分别是以时延为优化目标、以能耗为优化目标和综合时延和能耗的方式作为优化目标。Li等人[4]在单终端单边缘服务器的排队任务场景下,使用了梯度策略算法,与贪心算法和穷举法相比较,可以通过更短的决策时间获得高质量的卸载方案,仿真结果表明梯度策略算法减少了50%的时间开销。Liu等人[5]将给定顺序的有向无环的任务序列切割成基本单元,再根据不同的场景将基本单元分解成子问题来解决,结果表明该方法与比较算法相比,实现了最少的消耗时间。Ketykó等人[6]将多用户卸载问题建模为NP-hard 问题,并采用背包模型去优化整个资源分配和负载均衡的问题。Wang等人[7]提出了干扰管理的方案,在最小化干扰的条件下进行通信资源分配、计算资源分配的方案。Ndikumana等人[8]为使得资源利用率最大化,将MEC服务器组合起来使用,提出了一种协作式缓存的卸载策略。Xu等人[9]提出了一种非静态的卸载策略,使用了深度学习的方法来对有限的资源进行分配。Mehrabi等人提出了一个三节点的MEC架构,在满足任务完成期限和任务依赖性的要求下最小化系统能耗,结果表明该架构优于比较的卸载方式[10]。Guo等人[11-12]建立了两个计算效率髙的模型,分别具有可忽略和不可忽略的边缘服务器执行时间以封闭形式获得了最优解,利用Johnson算法来获得低复杂度的次优解决方案。Zhang等人[13]基于人工鱼群算法,将前传网络和回传网络的链路状态考虑在内,与对比算法相比节约了30%的能耗。鲜永菊等人[14]提出了一种主从MEC的系统架构,采用了贪婪选择算法完成计算资源的合理分配,实验结果表明该卸载策略减少了系统总代价。Huang等人[15]提出了一种基于深度强化学习的在线卸载框架,可以有效地减少计算复杂度,使得CPU计算时延小于0.1 s。

以上篇幅针对时延和能耗进行了一定程度的优化,但大多只考虑了单边缘或者边云协同的方式。本文采用了多边缘的网络架构,通过免疫粒子群算法对任务的卸载方式进行求解,得到最佳的卸载策略,使得能耗和时延的加权求和最小化。

1 系统模型

1.1 网络架构

经典的边缘计算系统架构是由用户层、边缘层、云层组成的。用户层是由各种终端物联网设备构成;边缘层是三层架构的核心,一般由蜂窝塔、路侧单元[16]等构成,具有比用户层更加强大的计算和存储能力;云层可以处理和存储大量的数据。用户终端产生的任务可以选择在本地计算、卸载到边缘服务器计算或者卸载到云端处理。传统的三层架构共同协作来对终端的任务进行卸载处理,再将处理后的结果数据返回,通过合理的卸载策略可以有效地减少系统的能耗和任务处理的延时。

尽管上述的系统架构已经取得了显著的效果,但是现有的卸载方案往往忽略了异地闲置边缘服务器的作用,造成了资源的不充分利用。因此,本文提出了一种多边缘协作的“物-边-云”卸载系统,根据产生任务的终端与边缘服务器物理距离的远近,在原有系统的基础上,将边缘服务器分为本地边缘服务器和异地边缘服务器。在此系统上,任务除了可以选择卸载到本地边缘服务器和云端上,还可以卸载到异地边缘服务器上。因为异地边缘服务器相对于云端来说距离用户终端更近,这样就大大地减少了传输延迟,也对闲置的计算资源进行了充分地利用。具体的通信场景如图1所示。

1.2 卸载计算模型

以往的有些研究不考虑任务间的依赖关系,但是实际应用中某些任务在执行时需要有前置任务,因此本文研究的任务卸载时要考虑任务之间的优先关系。图2描述了终端产生的任务之间的关系。图中的单位圆代表了一个任务,任务之间的约束关系用箭头来表示,箭头末端的任务是前置任务,如任务1指向任务2,则表示任务1是任务2的前置任务。必须把前置任务1执行了才能继续执行新任务2。

图2 任务关系

1.2.1 本地计算

当任务被选择在本地进行计算时,则造成的时延主要为计算延时,不存在传输延时;能量消耗则为计算任务时处理器的能量消耗。

(1)

(2)

1.2.2 卸载到本地服务器计算

当任务卸载到本地服务器计算时,造成的时延主要是由传输延时、卸载到本地服务器的计算延时和将数据返回的延时造成的。能耗主要是上传和下载数据产生的和服务器处理任务时产生的。

由香农公式可得,本地设备和服务器无线传输速率为

(3)

式中:B1是本地设备与本地服务器的通信带宽;ρ1和ρ2为路径的衰落因子和损耗因子;ρ0是噪声密度;d1是本地设备与本地边缘服务器的最近距离。

(4)

(5)

式中:pe为本地服务器的计算功率。

1.2.3 卸载到异地服务器计算

当把任务从本地服务器卸载到异地服务器时,延迟主要包括传输延时、计算延迟和返回延时,能耗包括计算能耗、上传能耗和下载能耗。

由香农公式可得,本地设备和服务器无线传输速率为

(6)

式中:d2为两个服务器之间的直线距离。任务卸载到异地服务器的时延为

(7)

任务卸载到异地服务器的能耗为

(8)

1.2.4 卸载到云层计算

当把任务卸载到云层时,延迟主要包括传输延时、计算延迟和返回延时,能耗包括计算能耗、上传能耗和下载能耗。

由香农公式可得,本地设备和云服务器无线传输速率为

(9)

式中:B3为本地设备与云端的通信带宽;d3为本地设备与云端的距离。任务卸载到云端的时延为

(10)

任务卸载到云端的能耗为

(11)

1.2.5 合作计算成本

当计算任务所需要的计算资源较大时,若将任务选择在本地执行,则会使得终端能耗增大;若将任务选择卸载到云层执行,由于云层距离用户层较远,则会导致任务完成的时延较大,因此本文将协作计算引入到卸载计算的模型中。为了鼓励更多的边缘服务器可以将计算资源共享,则终端用户应该付出一定的成本来吸引服务器帮助用户完成任务。对于数据量越大的任务需要更多的传输时间,所以合作计算成本coi与任务数据量成正比。因此合作计算成本coi的计算范式为

coi=ktdi。

(12)

式中:k为比例系数,表示用户请求服务器协作完成任务的单价。

1.2.6 目标函数定义

综上所述,任务卸载的总时延和总能耗可以表示成

(13)

(14)

定义系统总代价为目标函数,其表示为时延和能耗的加权和。考虑了合作成本,因此目标函数便遵循一定的约束,所以完整的目标函数如下:

g=wtTsum+(1-wt)Esum,

(15)

(16)

式(15)是本文的优化目标,式(16)表示任务卸载到边缘计算服务器上用户付出的成本约束。若计算任务对时延比较敏感,则可适当地将时间权重wt调大;若希望能耗减少,则可将wt调小。

2 算法设计

粒子群(Particle Swarm Optimization,PSO)算法在解决目标优化问题时一直以来都颇受学者们的青睐,但传统的粒子群算法在实际工程优化中容易出现早熟收敛和陷入局部最优。为克服这些缺点,本文将生物学中免疫机制引入到粒子群算法中,基于免疫粒子群算法来完成对目标函数的优化。

2.1 传统的粒子群算法

粒子是优化问题的候选解,粒子有两个参数,分别是速度和位置。每个粒子都有其适应度函数,一般是目标优化函数,其用于评价粒子的质量。在一次次的迭代中,粒子通过个体极值pbest和全局极值gbest来更新自己,直到达到满足条件。以下两式描述了粒子速度和位置更新:

(17)

(18)

式中:w代表惯性因子,表示粒子对自身运动状态的信任;c1和c2代表学习因子;r1和r2是两个相互独立的取值都在[0,1]的随机数[17]。

2.2 编码方式

本文有4种卸载方式,分别用1,2,3,4代表本地卸载、本地服务器卸载、异地服务器卸载和云层卸载。因为有N个任务且需要体现任务之间的优先级,所以本文采用两位浮点数编码方式。其中,整数部分表示任务编号,小数第一位表示卸载方式,小数第二位表示任务的优先级(数值越大,任务越优先被执行)。

2.3 适应度函数

由系统模型可知,优化目标是使得系统总代价最小,因此本文将目标函数取反,作为适应度函数。适应度函数越大,则系统总代价越小,卸载方案越有效。

fitness=-[wTsum+(1-w)Esum] 。

(19)

2.4 免疫粒子群算法(Immune Particle Optimization,IPSO)

本文在粒子群算法的基础上,引入了人工免疫算法,特别是结合了免疫系统中的免疫记忆机制和浓度调节机制。免疫记忆机制指的是在免疫系统中分泌能够与抗原结合的抗体的浆细胞作为记忆细胞储存下来,当机体再次遇到相同抗原入侵时,记忆细胞就会分化为浆细胞,产生大量抗体。本文将这种思想引入了粒子群算法中,将每次迭代产生的适应度较高的粒子作为记忆细胞保存下来。当遇到适应度较低的粒子时,可以将记忆细胞代替。浓度调节机制是指与浓度低的抗体会被促进,浓度高会被抑制。在算法中应用则保证了粒子的多样性,有利于避免陷入局部最优解。

与传统的粒子群算法不同,评价粒子(抗体)的质量是由亲和力决定的,其由式(20)计算:

p(xi)=αf(xi)+(1-α)d(xi) 。

(20)

式中:α是比例因子;p(xi)代表亲和度值;f(xi)代表适应度值;d(xi)代表浓度值。为了避免陷入局部最优解,研究中应该尽量地保证种群的多样性,防止高亲和度值的粒子大量存在,因此,引入了d(xi)浓度这一变量,计算方式如式(21)和式(22)所示:

(21)

(22)

式中:ρ(xi)代表相似度,若粒子的每个维度都相近时,则判断为相似粒子;N代表解空间里所有的粒子数量。

本文将粒子种群根据粒子最大浓度分为两个种群a和b。种群a是亲和度高的粒子,让这些粒子按照传统的粒子群方法迭代;种群b则是亲和度低的粒子,将种群b的粒子进行疫苗接种,让记忆细胞中亲和度高的粒子增值代替它们。这里种群a和b粒子数量由下面两式计算得出:

N(a)=dmaxN,

(23)

N(b)=N-N(a) 。

(24)

式中:N(a)和N(b)分别代表种群a和b的粒子数量;dmax式粒子的最大浓度。控制两个种群的粒子数量,有利于保持粒子的多样性,使得种群朝着好的方向进化。

2.5 算法流程

表1给出了免疫粒子群算法与卸载问题的对应关系。在使用免疫粒子群算法求解问题时,把目标优化问题抽象为抗原,把问题的候选解抽象为抗体(粒子),通过求解亲和度在解空间中进行启发式搜索来寻找最优抗体,解码最优抗体输出目标问题的最优解,使用抗体(粒子)X={x1,x2,…,xi,…,xN}表示任务调度的结果,xi=1时表示任务在本地执行,xi=2时任务在本地服务器执行,xi=3时任务在异地服务器执行,xi=4在云端执行。

表1 算法参数与卸载策略参数的对应关系

免疫粒子群算法流程如下:

输入:计算任务集的各个参数

输出:计算任务卸载策略

1 初始化种群数量为N的粒子群包括位置和速度。

2 根据式(20)计算每一个粒子的亲和度,并将个体极值的粒子视为记忆细胞作为疫苗。

3 根据粒子亲和度由大到小排序。

4 根据粒子最大浓度分为两个种群a和b,种群a按照式(17)和式(18)进行迭代,种群b进行疫苗接种。

5 种群a和种群b合并为种群c。

6 种群根据粒子群算法的速度和位置公式更新。

7 判断群体极值是否满足循环退出条件,若满足则输出结果,否则跳转到第2步。

2.6 算法复杂度分析

假设IPSO算法的种群数量为N,迭代次数为K,先对单次迭代的操作进行时间复杂度分析,然后扩展到整个过程。初始化种群并计算每个抗体的亲和度,其时间复杂度为O(N);将抗体亲和度值从大到小按选择排序的方式排序,其时间复杂度为O(N2);每个抗体的速度和位置按式(17)和式(18)更新,其时间复杂度也是O(N);其余操作均为常数时间复杂度。综上所述,IPSO算法的复杂度为O(KN2)。

3 仿真与分析

本节通过Java语言仿真平台来对本文提出的卸载策略进行验证,并与本地卸载策略、基于免疫算法(Immune Algorithm,IA)和基于传统的粒子群算法策略进行了对比。

本地卸载(LOCAL):终端产生的任务都集中在本地执行。

免疫算法[17](Immune Algorithm,IA):基于免疫优化算法卸载策略。

PSO[18](Particle Swarm Optimization)算法:基于传统的粒子群算法卸载策略。

IPSO(Immune Particle Optimization)算法:基于免疫粒子群算法卸载策略。

与真实场景不同的是,没有考虑服务器计算资源和通信资源的有限性。在文献[17]的基础上设定任务传输的数据量在[1,600]KB随机生成,结果返回的数据量在区间[0.1,100]KB上随机生成。算法的基本参数设定基于文献[19-21]中提供的参数示例,并且本文根据仿真环境进行了一定的调整。算法和任务卸载相关参数在表2和表3中给出。

表2 算法相关参数

表3 任务卸载相关参数

3.1 用户设备数量对系统总代价的影响

图3描述了用户设备数量的增多对于系统总代价的影响。图3中,横坐标代表用户数量,单位为用户个数;纵坐标表示的是系统总代价其值代表时延和能耗的加权和,是一个无量纲的物理量,图4～6的纵坐标也是如此。本文在设置仿真环境时设备服务器待机状态下存在少量的能量消耗,所以曲线并不归于原点。用户产生的任务数量的增加会使得在任务卸载过程中系统消耗的能量和时延都会增加,但从图中可以看出,本文使用的IPSO算法相比本地卸载策略、IA算法和传统的PSO算法来说,系统的总代价是最小的,相比较其他三种策略分别提升了66.7%,54%和45.5%,证明了该策略的有效性。

图3 用户数量的影响

图4 任务计算量的影响

3.2 任务计算量对于系统总代价的影响

图4描述了任务计算量的增大对于系统总代价的影响。任务数量取值为50,随着任务计算量的增大,系统总代价也在增大,但本文提出的IPSO算法总代价始终是最小的。在任务计算量低于60 GHz时,PSO算法的系统总代价与IPSO算法和IA算法相差不大,但大于60 GHz后,IPSO算法就明显优于PSO算法和IA算法。这是因为PSO算法容易收敛于局部最优,并且在以后的搜索过程中卸载效果不理想。

3.3 异地服务器数量对于系统总代价的影响

为了探究异地边缘服务器的数量对于系统总代价,本次实验设置本地服务器的数量为1台。从图5可以看出,在边缘服务器为5台时,系统总代价最低。与此同时,当服务器大于5台时,随着异地服务器数量的增加,系统总代价却略微增加。这是因为较多的异地边缘节点会使得计算任务卸载较为分散,系统的能耗和传输延时成本会增加,所以曲线会出现少许的波动,而本地卸载几乎不受服务器数量增多的影响。

图5 服务器数量的影响

3.4 用户最大合作成本的影响

图6描述了用户最大合作成本对于系统总代价的影响,本次实验任务的比例系数K取值为0.1。由式(16)可知,用户请求边缘服务器协作完成任务时需要付出的成本与任务数据量相关,任务数据量在[1,600]KB随机生成,因此设置横坐标用户所能承受的最大成本在区间[10,60]递增。图中横坐标表示用户付出的最大成本,与任务的数据量有关,但它是一个无量纲的物理量,因为它的物理含义表示的是用户购买服务器资源所付出的代价。由图可知,随着用户能承受的最大成本的增加,系统总代价在不断地减少。这是因为用户可以把更多的任务卸载到边缘服务器执行,减少了计算时延和能耗。而本地卸载任务基本保持不变是因为任务都在本地处理,不需要请求边缘服务器合作计算,系统总代价在本地执行任务几乎不受到影响。

图6 用户最大成本的影响

4 结束语

本文基于用户设备、本地边缘设备、异地边缘设备和云服务器协作的任务计算卸载模式,将时延和能耗建模成为系统总代价,采用免疫粒子群优化算法。仿真结果表明,该任务卸载策略可以提高任务的执行效率,有效地减少系统地总代价。但是本文没有考虑通信链路的干扰,也没有考虑边缘服务器的通信和计算资源的有限性。在后续的工作中,将会考虑以上不足,采用深度强化学习的方式继续研究任务卸载策略。