云辅助移动边缘计算中的计算卸载策略

王 妍,葛海波,冯安琪

(西安邮电大学 电子工程学院,西安 710121)

0 概述

随着移动设备的普及,计算密集型、时延敏感型等新兴移动应用不断涌现并迅速受到用户的青睐,如增强现实、图像识别、网络游戏、车联网等[1]。这类新兴的应用通常需要消耗大量的计算资源,以满足低时延需求。然而,资源有限的移动设备很难满足上述移动应用的需求[2]。计算卸载是一种有效的解决方案,通过卸载计算任务到云服务器或者边缘服务器,从而达到缓解计算和存储的限制、降低时延的目的。移动云计算(Mobile Cloud Computing,MCC)被认为是一种很有效的卸载计算任务的方法,其强大的计算能力可以显著降低移动服务的处理时延。然而,将计算任务卸载到空间上远离移动设备的云服务器上会造成较高的传输时延,增加能量消耗。为了解决云计算卸载过程中面临的高传输时延等问题,移动边缘计算(Mobile Edge Computing,MEC)应运而生[3],MEC的核心思想是将服务器的计算和存储资源迁移到移动设备附近,降低移动服务处理过程中的传输时延、处理时延,减少能量消耗。移动边缘计算是移动云计算的一种特殊情况。

在计算卸载问题中,MCC和MEC各有利弊,适用于不同的移动服务[4]。当面临延迟敏感任务时,MEC以其靠近移动设备、传输延迟短的优点,可以提供比MCC更好的服务,当处理非延迟敏感任务时,则会突出MCC中计算资源丰富的优势。因此,MCC和MEC两者应相互协调、相互补充,确保计算卸载策略能满足不同的应用场景。

本文综合考虑MCC计算资源丰富以及MEC靠近移动设备的优势,提出一种云辅助移动边缘计算的计算卸载策略(CAME),在此基础上,设计基于改进遗传算法的计算卸载算法(CAMEGA),优化移动服务的运行时间和设备能耗,从而得到系统总代价较优的计算卸载策略。

1 相关研究

计算卸载是研究MEC的关键问题之一。近年来,研究人员对MEC中的计算卸载问题进行了大量研究,并且取得了突破性的进展。这些研究旨在探索制定最佳卸载决策,达到降低时延和节省移动设备能耗的目的。文献[5]利用马尔科夫链理论分析给定计算任务的时延,运用一维搜索算法寻找时延最小的计算卸载策略。文献[6]研究在移动边缘计算环境下,卸载延时和可靠性之间的权衡问题,利用基于启发式搜索、重构造线性化技术和半定松弛3种算法,实现系统延时和卸载失败率最小。文献[7]运用排队网络的方法分析系统时延,提出一种具有线性复杂度的算法,该算法能显著降低系统时延。文献[8]提出一种基于李亚普诺夫的动态卸载算法,在满足指定应用程序对时延要求的前提下,实现系统节能。文献[9]研究一个带有能量收集器件的MEC系统,提出基于李亚普诺夫优化的动态计算卸载算法,实现应用程序的执行延迟最小。文献[10]提出一种细粒度卸载策略,将任务卸载问题表示为一个有约束的0-1规划问题,采用BPSO算法,旨在满足严格的延时约束的同时,最大限度地减少能量消耗。文献[11]研究了由多个用户组成的移动边缘计算卸载系统中的资源分配问题,将最优资源分配问题表示为一个凸优化问题,实现在满足时延要求的条件下,移动设备能耗最小。文献[12]提出一种面向优先级业务的边缘计算资源分配方法,根据业务价值赋予相应的优先级,对不同优先级的任务进行加权资源分配,旨在降低业务的执行时间和能耗。文献[13]提出基于拉格朗日的计算卸载策略,将移动边缘计算框架下的计算卸载问题建模为一个凸优化问题,采用拉格朗日乘子法优化移动终端总的计算时间和能耗。文献[14]采用云辅助移动边缘计算框架,旨在以最小的系统成本保证用户服务质量。文献[15]提出一种新的异构网络两层计算卸载框架。基于此框架,设计有效的计算卸载方案,以使总体能耗最小化。文献[16]提出一个云、MEC和LoT集成的融合框架,解决MEC面临的可扩展问题,设计了一个选择卸载方案,在满足时延要求的条件下实现移动设备能耗最小。文献[17]提出一种资源优化方法来最小化多天线接入点的能耗。文献研究总结如表1所示,其中,√为是,×为否。

表1 不同方案的计算卸载策略

上述对于移动边缘计算环境下的计算卸载问题的研究工作,大部分只是将能耗或时延其中一项作为优化目标,或者没有考虑任务之间的数据依赖关系和顺序依赖关系。此外,大部分研究集中于应用MEC或MCC来卸载计算任务,并未考虑两者之间的协作。很少有文献在综合考虑以上3种情况的基础上研究计算卸载问题,这就导致设计的卸载策略局限性较大。因此,设计一个适用于不同移动服务的计算卸载策略成为计算卸载问题中的难点。为了解决上述问题,本文提出CAMEGA计算卸载算法。主要工作如下:

1)综合考虑MEC传输时延低、计算能力有限而MCC传输时延高、计算资源丰富的特点,提出云辅助移动边缘计算的计算卸载框架(CAME)。

2)考虑到任务之间的依赖关系,将复杂的移动服务简化为具有优先约束关系的工作流模型处理。

3)设计基于改进遗传算法的计算卸载算法(CAEMGA),利用改进遗传算法循环得到最优卸载策略,最小化移动服务总的执行时间和能耗。

2 系统模型

本节主要阐述系统模型,系统模型主要包括移动服务模型和计算卸载模型。

2.1 移动服务模型

本文主要研究云辅助移动边缘计算环境下单用户单个移动服务的计算卸载问题。将复杂的移动服务简化为具有优先约束关系的工作流模型处理。用S={s1,s2,…,si,…,sn}表示工作流中任务的集合,n为任务的数量,用户可以通过调整任务的数量以及任务间的依赖关系来模拟各种各样的移动服务。每个任务被建模为一个二元组{αi,βi},其中,αi为第i个任务的工作量,βi为输出数据量。

在移动服务的运行过程中,本地设备输入数据,第一个任务从本地设备获取数据,因此第一个任务必须在本地设备中执行。类似地,当移动服务运行完后,应该把输出数据传回本地设备,最后一个任务也必须在本地执行。

2.2 计算卸载模型

计算卸载模型如图1所示,移动设备通过移动网络连接到基站。当移动设备运行移动服务时,可以将工作流中的任务卸载到边缘服务器或云服务器中执行。边缘服务器和云服务器接收来自移动用户的请求并处理,最后将处理结果返回给移动用户。移动用户可以根据移动服务的需求选择任务部分卸载或者完全卸载。由图1可知,用户U3将工作流中第2个任务卸载至边缘服务器中执行,将第3个任务卸载至云服务器中执行,第1个和第4个任务在本地设备执行。

图1 计算卸载模型Fig.1 Computation offloading model

边缘服务器可通过一个二元组E={Ce,Fe},其中,Ce为边缘服务器处理1 bit数据所需的CPU周期数,Fe为边缘服务器计算能力。

云服务器可通过一个二元组E={Cc,Fc},其中用Cc表示云服务器处理1bit数据所需的CPU周期数,Fc为云服务器计算能力。

3 问题分析

图2展示了一个由9个任务组成的移动服务工作流,这9个任务的执行顺序具有优先约束关系,箭头表示任务执行的先后顺序,这些任务可以在本地设备、边缘服务器或云服务器中执行。由图2可以看出,任务S1、S2、S5、S9在本地执行,S3、S4、S7在边缘服务器中执行,S6、S8在云服务器中执行。

图2 任务卸载模型Fig.2 Task offloading model

本文旨在制定最佳的卸载策略,实现工作流的执行时间和移动设备的能耗最小。因此,将目标函数定义为工作流执行时间和能耗的加权和。

F=ωT+(1-ω)E

(1)

其中,E为执行工作流服务过程中移动设备的总能耗,T为工作流执行的总时间,ω为时延权重系数,1-ω为能耗权重系数。ω可根据移动服务的需求及移动设备的状态来设置,例如,当运行延时敏感型移动服务时,可以适当增加ω的值,当移动设备电量不足时,ω必须设置为较小的值。本文以时延敏感型移动服务为例,ω取0.8。

按照如下方式计算目标函数中的分量:

1)任务i在本地执行的计算时间为:

(2)

任务i在本地执行的能耗为:

El=Tl×Pl

(3)

2)任务i从本地卸载至边缘服务器的总时间为:

(4)

任务i从本地卸载至边缘服务器的总能耗为:

(5)

3)任务i从本地设备卸载至云服务器的总时间为:

(6)

任务i从本地设备卸载至云服务器的总能耗为:

(7)

综上所述,移动服务运行的总时间和移动设备的总能耗可以表述为:

(8)

(9)

4 卸载算法设计

目前,研究人员使用智能算法解决优化问题[18-19]。本文选择遗传算法作为基础算法,部分修改传统遗传算法,以满足计算卸载问题的特殊需求[20-21]。

在云辅助移动边缘计算的计算卸载系统中,移动服务工作流中的每个任务可在不同服务器上执行(本地、边缘、云),这些服务器具有不同的计算能力,所以不同的执行位置会造成不同的执行时间和设备能耗。此外,当工作流中包含大量任务数时,会出现多个任务同时竞争一个计算资源的情况。因此,本文采用排序任务的执行顺序来解决这个问题。考虑以上两点,本文主要关注任务的执行位置和执行顺序两组变量,这两组变量相互影响,共同决定卸载策略。如果分开优化每组变量,将不能得到最优卸载策略。本文采用改进遗传算法,即嵌套遗传算法,同时优化任务执行顺序和执行位置。

4.1 编码

本文采用改进浮点数编码的编码方式。与传统的浮点数编码不同的是,分别让浮点数整数和小数部分映射不同的个体特征,即一种基因型映射两种表现型,这样编码能够降低算法复杂度,提高运算效率。假设n为任务总数,用集合X.Y={x1.y1,x2.y2,…,xi.yi,…,xn.yn}表示任务执行顺序和执行位置,其中整数部分xi表示工作流中的某个任务,小数部分yi表示任务xi∈{s0,s1,s2,…,si,…,sn-1}的执行位置,yi=0表示任务在本地设备执行,yi=1表示任务在边缘服务器执行,yi=2表示任务在云服务器执行。图3描述的是编码方案示例。

图3 编码方案示例Fig.3 Example of encoding scheme

4.2 适应度函数

在遗传算法中,适应度是描述个体性能的主要指标,适应度越大,个体越优秀。根据适应度的大小,对个体进行优胜劣汰。本文关注的问题是搜寻最优卸载策略,实现移动服务工作流的执行时间与能耗的加权和最小化。因此,使用目标函数的倒数计算工作流的适应度值。

4.3 初始化

由于任务之间有一定的顺序关系,因此借助优先约束矩阵PCM来初始化任务的执行顺序。PCM是一个n×n矩阵,用D表示,Dij表示工作流中第i个任务与第j个任务的约束关系。当Dij=0时表示任务i和任务j没有优先约束关系,可以同时执行;Dij=1表示任务i必须先执行;Dij=-1表示任务j必须先执行。可以根据任务的数量及任务之间的具体依赖关系自定义PCM矩阵,图4为图2中9个任务的优先约束矩阵。

图4 优先约束矩阵

具体的操作步骤为:每次选取没有先序任务或先序任务已经排序完毕的任务,即选取优先约束矩阵中所有Cij不等于-1的行数,然后把优先约束矩阵中与所选取任务相关的行和列都置为0,即选取任务Si后,将Cij、Cji都置为0。按照此方法继续选取下一任务,直到形成一组可行任务序列。循环N次形成初始种群,N为种群规模。

完成任务执行顺序初始化后,进行任务执行位置初始化。随机产生0.0、0.1、0.2中的一个数,如果产生为0.0,则表示任务在本地设备执行,同理,产生0.1、0.2分别表示在边缘服务器或云服务器中执行。

4.4 交叉

采用传统的单点交叉法,进行任务执行位置的交叉操作,经过交叉操作后,得到新的个体X1.Y12和X2.Y21。

算法1排序交叉算法

输入完成位置交叉操作的任务序列

输出完成整体交叉操作的任务序列

Begin

1.生成[1,n]之间的随机数r;

3.X12.Y12=X21.Y211≠φ

4.for i=1 to r

6.end for

8.for i=1 to r

10.end for

12.for i=1 to n+r

13.for m=1 to n

16.else

18.end if

19.end for

20.for i=1 to n+r

21.for m=1 to n

24.else

26.end if

27.end for

任务执行顺序变异过程如图5所示。

图5 任务执行顺序变异过程1Fig.5 Mutation process 1 of task execution sequence

4.5 变异

变异操作是将染色体中的某个基因值做出变动。随机选取任务序列中一个任务作为变异点,以突变概率决定是否进行变异,若变异,则任务执行位置变为除当前执行位置之外的任一位置,即基因小数部分0变为1或2、1变为0或2、2变为0或1。

在执行任务执行顺序的变异操作时,同样需要考虑任务之间的优先约束关系。从任务集合X.Y中随机选取一个任务xi.yi作为变异点,在任务集合X.Y中,以xi.yi为中心,分别往正反方向查找,直到找到xi.yi所有的先序任务集合{x1.y1,x2.y2,…,xa.ya}和后继任务集合{xb.yb,xb+1.yb+1,…,xn.yn}。最后,在不包含xi.yi的先序任务和后继任务的序列{xa+1.ya+1,xa+2.ya+2,…,xb+1.yb+1}中,随机选取一个任务,与xi.yi交换执行顺序。任务执行顺序的变异过程如图6所示。

图6 任务执行顺序变异过程2Fig.6 Mutation process 2 of task execution sequence

算法2排序变异算法

输入完成位置变异的任务序列

输出完成整体变异操作的任务序列

Begin

1.生成[1,n-1]之间随机数r;

2.for i=1 to r

3.搜索xr.yr的先序任务集{x1.y1,x2.y2,…,xa.ya};

4.end for

5.for i=r to n-1

6.搜索xr.yr的后继任务{xb.yb,xb+1.yb+1,…,xn.yn};

7.end for

8.得到集合X′.Y′={xa+1.ya+1,xa+2.ya+2,…,xb+1.yb+1};

9.排出xr.yr当前位置,在集合X′.Y′中随机选择位置插入

10.得到新个体

End

5 仿真实验与结果分析

本节对本文CAMEGA算法以及All-Local算法、Random算法、ECGA算法进行了仿真对比实验。根据已有相关文献,遗传算法相关参数由表2[23]给出,网络仿真参数由表3给出,其中,任务工作量为服从[1,200]之间均匀分布(单位为GHz),输出数据量为服从[1,50]之间均匀分布(单位为MB)。

表2 遗传算法相关参数

表3 网络仿真参数

All-Local算法:将所有的任务都放在移动设备执行。

Random算法:在云辅助移动边缘计算的计算卸载框架下,随机分配任务的执行位置(本地、边缘、云)和执行顺序。

ECGA算法:移动边缘计算的计算卸载框架下,基于遗传算法的计算卸载算法。

5.1 任务数变化对系统总代价的影响

本节主要研究在不同的工作流任务数量下,CAMEGA算法、All-Local算法、Random算法、ECGA算法的性能比较,模拟的任务数分别为30、60、90、120和150的情况。如图7所示,随着工作流中任务数的增加,系统的总代价逐渐增加。与All-Local算法、Random算法、ECGA算法相比,CAMEGA算法的系统总代价最小,约为All-Local算法的8.4%、Random算法的43.7%、ECGA算法的30%。因此,在计算卸载问题中,CAMEGA算法有较大的优势。

图7 任务数变化对系统总代价的影响Fig.7 Impact of task number changes on total system cost

5.2 时延权重变化对系统总代价的影响

本节主要研究时延权重ω与能耗权重1-ω的比值大小在[0.01,100]时,CAMEGA算法、All-Local算法、ECGA算法与Random算法4种算法的性能比较。如图8所示,针对不同的时延和能耗比值,本文提出的CAMEGA算法得到的结果明显优于其他3种算法。因此,CAMEGA算法可以更好地适用于需求不同的移动服务。

图8 时延权重与能耗权重的比值对系统总代价的影响Fig.8 Effect of ratio of delay weight to energy consumption weight on total system cost

5.3 迭代次数对系统总代价的影响

本节主要研究迭代次数在[10,100]时,迭代次数的变化对系统总代价的影响。取移动服务工作流中的任务数N=60,如图9所示,随着迭代次数的增加,All-Local算法得到的实验结果几乎没有变化(略去),基于CAMEGA算法、Random算法、ECGA算法的系统总代价值呈下降趋势,当迭代次数在[10,100]时,系统总代价的下降趋势较大,迭代次数超过50以后,系统总代价的变化趋势很小、趋于稳定。由此可以得出,迭代次数取50时,可以得到较优的实验结果。

图9 迭代次数对系统总代价的影响Fig.9 Impact of workload changes on total system cost

5.4 工作量变化对系统总代价的影响

本节主要研究任务工作量在[0,200]之间时系统总代价的变化。从图10可以看出,随着任务工作量的增加,系统总代价也在逐渐增加。这是因为在本地设备、边缘服务器、云服务器的计算能力不变的情况下,增加任务的输入数据量必然会导致执行时间变长,从而系统总代价变大。同样,CAMEGA算法得到的系统总代价明显小于All-Local算法、Random算法和ECGA算法。

图10 工作量变化对系统总代价的影响Fig.10 Impact of workload changes on total system cost

5.5 任务输出数据量变化对系统总代价的影响

本节主要研究工作流任务的输出数据在[10,50]时,4种算法的系统总代价的变化。如图11所示,对于All-Local算法,随着任务输出数据量的增加,All-Local算法的系统总代价几乎没有变化,这是由于在All-Local算法中,移动服务中所有任务都在本地执行,不存在数据上传/下载过程,也就不存在传输时延和传输能耗。对于Random算法、ECGA算法和CAMEGA算法,任务的输出数据量越大,系统总代价越大。这是因为任务的输出数据量对于工作流执行过程中的上传/下载的时延和能耗都会产生较大的影响。在同样的卸载策略下,较大的数据传输量会花费较长的时间。同样,较大的数据传输量会给移动设备带来更多的传输能耗。

图11 输出数据量对系统总代价的影响Fig.11 Impact of amount of output data on total system cost

综合上述分析可以看出,与All-Local算法、Random算法和ECGA算法相比,本文提出的CAMEGA算法均能得到最小的系统总代价。

6 结束语

本文针对移动服务的执行时间和移动设备能耗的优化问题进行研究,设计云辅助移动边缘计算的计算卸载框架,并提出基于改进遗传算法的计算卸载算法。通过选择、交叉、变异等遗传操作,迭代得到最优的卸载策略,实现系统总代价最小。仿真结果表明,与All-Local算法、Random算法和ECGA算法相比,CAMEGA算法系统总代价最小。下一步工作将对包含多个移动设备、边缘服务器和云服务器等系统中的计算卸载问题进行研究。