基于服务质量的能耗感知工作流卸载策略

袁友伟,吴浩天+,张雪峰,李万清,李忠金,邱仁志

(1.杭州电子科技大学 计算机学院,浙江 杭州 310018;2.浙江省脑机协同智能重点实验室,浙江 杭州 310018)

0 引言

随着物联网技术和移动通信技术的快速发展,包括音频识别、增强现实和协同驾驶等应用[1]在内的延时敏感型和计算密集型计算任务已逐步在移动设备(Mobile Device,MD)上广泛应用,为用户提供更加便捷的移动服务。然而,移动设备在存储资源、网络带宽、计算能力和电池续航方面存在巨大的限制[2-3]。为应对上述问题带来的挑战,移动边缘计算(Mobile Edge Computing,MEC)被提出,使得复杂计算任务能够在移动边缘设备上被高能效地完成。工作流延时优化作为边缘计算环境下工作流调度的关键挑战,随着应用的进一步发展,传统的调度方案无法继续满足用户对低延时的需要,故需采用新的调度方案。其次,移动设备由于其体积较小,极大地限制了电池寿命。若直接将计算任务卸载至边缘服务器执行,尤其在较差的网络环境中,不仅任务执行延时较高,还会造成大量的电池能量消耗,极大地降低设备待机时间。要解决MEC领域性能的瓶颈问题,为用户提供更高质量的服务体验,关键在于进一步降低移动设备的延时和能耗[4]。而诸如图像识别、推荐算法等计算密集型且对计算精度要求不高的应用,可以通过降低卸载节点的服务质量(Quality of Service,QoS)即引入近似计算技术[5-6],降低卸载到边缘节点的任务计算精度,以最大限度降低移动设备的能耗与工作流的延时。

基于上述原因,本文研究了边缘计算工作流调度的任务卸载问题,提出一种基于服务质量的能耗感知工作流卸载策略(Energy Aware workflow offloading strategy based on Quality of Service,EA-QoS)。该策略通过对工作流进行分层,利用HEFT(heterogeneous earliest finish time)算法生成就绪队列,确保卸载任务间依赖关系的有效性;搜集边缘节点信息,为节点分组设置QoS等级,降低任务调度过程的复杂度;利用非支配排序算法(Non-dominated Sorting Genetic Algorithm Ⅲ,NSGA-Ⅲ)生成调度方案,确保能耗与时延的全局最优性。

1 相关工作

近年来,移动智能设备及MEC得到了快速发展,众多专家学者对MEC环境下工作流卸载问题的延时优化和能耗优化算法进行了研究,本章主要从MEC环境下工作流卸载的延时优化和能耗优化两个方面对研究现状进行介绍。

MEC作为一种新兴的并行式计算技术,通过将工作流从资源受限的智能移动设备卸载到边缘演进型节点(evolved Node B,eNB)中执行,以降低应用任务的处理延时。最常见的工作流卸载的延时优化调度算法是整数线性规划(Integer Linear Program,ILP)[7-9],也有许多专家学者研究了贪心算法[10]、马尔可夫决策过程[11]和Petri网[12]等卸载方法。KIM等[13]提出一种基于预测工作流任务的卸载方法,通过使用线性回归预测任务的预期处理时间,以降低每个MEC服务器上应用程序的平均处理时间。TONG等[14]考虑了移动用户设备在基站件的移动性,提出一种基于深度强化学习(Deep Reinforcement Learning,DRL)的任务卸载方法,有效降低了任务平均响应时间。ALGHAMDI等[15]针对工作流卸载中数据质量感知的卸载顺序决策问题,通过最大化卸载任务到处理时间最短边缘节点的概率,从而显著减少分析任务执行的预期处理时间。XU等[16]研究了云边缘环境下的物联网大数据卸载问题,提出一种结合NSGA-Ⅲ的计算卸载方法,显著降低了工作流的执行延时。

智能移动设备的电池容量有限,故能耗优化成为了移动边缘计算卸载性能评估的重要标准。ZHANG等[17]提出一种能耗感知卸载方案,该方案通过利用小型边缘节点调整计算任务的卸载服务器,以降低工作流卸载的能耗。MAZOUZI等[18]研究了多用户工作流能耗受限的边缘与远程联合卸载问题,提出一种利用拉格朗日分解法的分布式线性启发式算法,从而最小化移动设备能耗。ALAM等[19]综合考虑资源需求、资源可用性和网络状态的代码卸载单元,最大限度地减少了工作流迁移计算的能耗。XU等[20]分析了原始接入节点到目的接入节点之间的所有接入路由,提出一种搜索寻找最短路径卸载任务的算法,以大幅降低设备能耗。徐佳等[3]对云边缘计算环境中的计算资源进行了综合的考虑,提出一种多重资源计算卸载粒子群任务调度算法,在考虑了响应时间的约束下,充分降低移动终端的能耗。

当前在MEC环境下工作流卸载问题的研究主要是通过任务调度来减少延时与能耗,这种通过调度任务卸载位置的优化方式存在一定的局限,然而结合近似计算技术对被调度的工作流任务本身进行优化处理的研究很少。本文在上述研究的基础上提出的基于服务质量的能耗感知工作流卸载策略,采用近似计算优化处理工作流任务,从而降低工作流任务的计算工作量。实现了在满足服务质量限制的情况下,在原有调度算法研究的基础上,进一步降低移动设备的能耗和延时。

2 系统模型

本章主要介绍边缘环境下的基于服务质量的能耗感知工作流卸载模型、QoS模型、时间模型、能耗模型和优化目标,其中QoS模型、时间模型和能耗模型为基于服务质量的能耗感知工作流卸载模型的组成部分。

2.1 边缘环境下基于服务质量的能耗感知工作流卸载模型

边缘环境下基于服务质量的能耗感知工作流卸载架构如图1所示,系统首先对每个移动设备应用程序提交的工作流进行建模分层,确定就绪任务队列。然后搜集边缘节点信息,使用能耗感知优化方法进行排序并分组分配服务质量(QoS)级别。再对就绪工作流队列、边缘节点等进行编码,最后任务调度器利用非支配排序算法(NSGA-Ⅲ)确定最优卸载方案,卸载任务到相应节点上执行,得到工作流执行结果。

图1 边缘环境下基于服务质量的能耗感知工作流卸载架构示意图

2.2 工作流模型

2.3 QoS模型

(1)

当q=0时,表示实际输出的近似结果与所能达到的最高精度结果完全不同;当q=1时,表示服务质量达到当前边缘节点的最高级别,近似结果与精确计算的结果完全相同。

定义1QoS约束。令Q为移动设备(用户)赋予某特定应用程序所能接受的最低QoS等级。每一个边缘节点都会被分配一个服务质量等级qi(qi∈[0,1])。无论工作负载如何分布,系统中负责处理任务的节点的聚合QoS等级不能小于Q,即：

(2)

2.4 时间模型

MEC场景中的响应时间主要由工作流执行计算的任务处理时间Tex和数据传输时间Ttx组成。在执行计算任务时,任务处理时间取决于计算任务的工作量、计算平台的计算能力和分配给卸载节点的QoS等级。工作负载为wi的任务vi计算时间为：

Tex=wi/Ci=wiTi(qi)。

(3)

其中：Ci为节点i的处理能力,Ti(qi)表示节点i以qi的QoS等级处理单位工作负载所消耗的时间。

设Bi为移动设备与边缘节点i之间的数据传输速度,则任务vi数据传输所需的时间为：

(4)

总体工作负载的处理时间被定义为：

(5)

2.5 能耗模型

(6)

(7)

故此,移动设备的总能耗E为：

(8)

2.6 目标函数

本文主要考虑在最小化移动设备总能耗的情况下,同时降低工作流执行时间并满足应用程序对服务质量的要求,目标函数表示为：

minE+αT。

s.t.

(9)

其中α为时间与能耗的权重因子,用于反映对于延时和能耗的偏好。用户对能耗的要求越高,α的取值越低;反之,用户对时延的要求越高,α的取值越高。系统可以通过调整α的取值针对不同应用场景改善实际优化效果。

3 基于服务质量的能耗感知工作流卸载策略

本章提出一种基于服务质量的能耗感知工作流卸载策略。该策略以非支配排序遗传算法(NSGA-Ⅲ)[21]为基础,结合基于服务质量的能耗感知(Energy Aware,EA)优化方法降低生成卸载方案过程的复杂度,同时保证对移动设备能耗和延时的优化。最后通过NSGA-Ⅲ算法生成调度方案,保证方案的全局优化。下面分别从基于服务质量的能耗感知优化方法和EA-QoS卸载策略的流程进行介绍。

3.1 基于服务质量的能耗感知优化方法

在实际场景中,非线性处理时间Ti(qi)往往是QoS等级qi的凸函数,因为Ti(qi)具有单调递增的梯度,所以,当Ti(qi)=aif(qi)时,对于一些αi>0和凸函数f,在满足EA-QoS优化约束下的最优解中,工作流卸载的单位负载传输能耗较小的边缘节点总是能获得较高的QoS等级。

(10)

(11)

(12)

因此,根据以下等价链

(13)

可以得出 ：

(14)

(15)

3.2 EA-QoS算法步骤

EA-QoS卸载基于非支配排序遗传算法实现[21]。非支配排序遗传算法是一种随机搜索算法,从初始种群出发,经过交叉、变异和最优化选择产生下一代种群,然后通过迭代找到期望目标。EA-QoS算法首先对所有边缘节点划分QoS组,然后利用遗传算法得到最优任务调度方案,主要包括编码、种群初始化、交叉和变异、初始选择、优化选择5个步骤,EA-QoS卸载策略具体流程如图2所示。

图2 EA-QoS算法流程示意图

(2)编码策略 使用遗传算法解决工作流任务卸载问题,需要将卸载策略转化为算法中对应的染色体编码。假设某工作流可被分解为N个任务,当可卸载节点数量为h时,染色体编码包括工作流的任务执行顺序V={v0,v1,…,vN},其中任务的执行先后顺序必须满足任务的依赖关系;边缘网络中h+1个用于提供计算服务的节点Vm={vm0,vm1,vm2,…,vmh},其中vm0表示提交工作流的移动设备;分配给卸载节点的QoS级别QoS={q0,q1,…,qN},聚合的QoS等级必须满足QoS约束。

(3)种群初始化 首先确定NSGA-Ⅲ的参数,包括种群大小M,迭代的最大次数Max,交叉概率Cr和突变概率Cf。然后采用随机法初始化任务调度位置和执行顺序。任务调度顺序进行初始化时,应考虑任务间的依赖关系,即初始化任务vi时,其前驱任务必须为已排序任务。

(4)交叉与变异 本文采用单点交叉法生成新个体,以交叉概率Cr随机选取染色体交叉点。为避免“早熟”现象,通过变异概率Cf确定个体是否发生变异。然后随机确定变异位置,并随机生成一个除原位置之外的vmi(0≤vmi≤h)作为新的基因值。通过交叉和变异操作生成包含有效工作流迁移策略的子代Qt。

(5)初始选择 选择操作的目的是为下一次迭代筛选更优秀的个体,保持种群大小在迭代前后一致以确保算法性能。EA-QoS卸载策略采用NSGA-Ⅲ中的非支配排序算法选择性能表现优秀的迁移策略个体。首先合并父种群与交叉变异产生的新种群得到Rt(|Rt|=2M)。然后通过计算个体适应度确定支配与非支配关系。EA-QoS算法为联合优化能耗与延时,选取式(16)作为适应度函数。

Fitness=E+αT。

(16)

对Rt进行非支配排序,首先计算Rt中个体对应的移动设备能耗E和延时T,根据适应度Fitness=E+αT,划分Rt为若干非支配解层(F1,F2,…)。然后计算个体被其他解支配数ni和支配解集合SPi。将所有ni=0的个体纳入当前非支配解层Fj,并将其支配解集SPi中个体的被支配数nk减1,令j=j+1。重复上述过程,直到所有个体都被纳入一个非支配解层。最后重复将最低非支配解层Fi纳入临时种群St中,直到|St|≥M。若|St|=M,则令新一代种群Pt+1=St,否则进行优化选择。

(17)

(18)

然后在截距为1的坐标轴上进行划分,使用结构化参考点生成方法生成参考点。计算St中的染色体坐标点到连线的垂直距离,从而将所有个体与参考点相关联。根据参考点关联的个体数,随机从Fl中选择个体进入下一代种群Pt+1中,直到|Pt+1|=M。

EA-QoS卸载策略的流程如算法1所示。

算法1EA-QoS卸载策略。

输入：QoS分组数K,可用节点Vm,种群大小M,最大迭代次数Max,变异概率Cf,交叉概率Cr;

输出：Pt+1//迁移工作流策略。

1.任务分层

2.HEFT算法得到工作流就绪队列

3.搜集节点信息并划分为K组

4.设置卸载节点分组的QoS等级

5.生成初始种群

6.for t=1 to I do

7.QtRt=Pt∪Coross_Mutation(Pt)//交叉变异至个体数为2M

8.(F1,F2,…)=Non-dominate-sort(Rt)//非支配排序

9.while |St|

10.St=St∪Fiand i=i+1

11.end while

12.if|St|>M then//优化选择,维持迁移策略的多样性

14.搜索E、T最小值并计算各点截距

15.对Fl中个体进行归一化并关联参考点

16.根据参考点选取k(k=M-|Pt+1|)个迁移策略加入Pt+1

17.else

18.Pt+1=St

19.end for

20.return Pt+1

4 仿真实验评估

为了分析和评估EA-QoS的性能,本文首先在不同的QoS等级下进行任务调度,研究QoS等级对工作流的任务处理时间的影响。然后将EA-QoS与不采用近似计算的NSGA-Ⅲ算法[16]、粒子群优化(Particle Swarm Optimization,PSO)算法[3]进行对比,研究引入QoS的优化角度和遗传算法对工作流调度能耗与延时的影响。最后为研究EA-QoS与其他调度策略之间的性能差异,分别选取4种策略作为比较对象,各算法说明如下：策略Ⅰ(B-QoS)：采用最高QoS等级均匀卸载;策略Ⅱ(R-QoS)：采用最低QoS等级均匀卸载;策略Ⅲ(E-QoS)：最小化传输能耗,单位负载传输能耗较小的节点分配更多的任务;策略Ⅳ(T-QoS)：最大限度地减少响应时间,调整节点的任务数量与强度来平衡负载。

4.1 实验环境与实验参数

实验中MD与基站之间的距离是[1,200]的随机变量(单位：m),MD与不同边缘节点传输功率不同,MD的数据传输基准功率Ptx=110 mW,MD的CPU基础频率为1.8 GHz,加速频率为3.2 GHz,计算能力为900 mW。在仿真实验中,采用DAG随机生成的方式产生工作流,假定随机生成的工作流任务满足进行近似计算的需求,每个工作流任务数服从[10,110]的正态分布,工作流中的任务大小服从1～10之间的均匀分布(单位：kB),工作量W为0.1～1之间服从正态分布的随机值(单位：GHz/s),节点的QoS分组K=3,最大迭代次数Max=500。边缘节点的参数如表1所示。

表1 边缘节点参数设置

4.2 QoS等级对任务处理时间的影响研究实验

本节主要研究QoS等级对任务处理时间的影响,并量化QoS等级与单位任务处理时间的关系,实验中针对图像处理应用定义了10个不同的QoS等级,并在每个不同的QoS等级下分别进行10次实验,实验结果如图3所示。

图3 不同QoS等级与处理时间关系图

由实验可知,QoS等级和单位任务处理时间呈凸函数关系。当节点的QoS等级不断增大时,当前节点所需处理的工作量也不断增大,故单位任务负载的处理时间逐渐增大。经过后续的大量实验测试,使用凸曲线拟合QoS等级和处理速度的误差为9.1%左右。

4.3 QoS对能耗延时影响研究实验

为探究引入QoS的角度对工作流设备能耗和任务处理时间的影响,本节采用不使用近似计算技术的NSGA-Ⅲ、PSO与EA-QoS策略进行比较,在表1所示的边缘环境中,设置EA-QoS的α=200,QoS等级q=0.96,其他参数与NSGA-Ⅲ、PSO相同,初始种群也相同的情况下进行实验。针对4组工作量逐渐增大的工作流WF1、WF2、WF3、WF4,3种方案的调度实验结果如图4所示。

图4 相同环境下各算法能耗延时对比

在4组实验中,NSGA-Ⅲ算法的性能表现要优于通常的PSO算法,因为NSGA-Ⅲ算法能够更快速地寻找多目标优化的全局最优解,所以优化效果优于PSO。由图4a中可以看出,EA-QoS策略在工作流卸载的能耗方面的表现始终优于NSGA-Ⅲ和PSO,这是由于EA-QoS策略在任务卸载执行的过程中通过设置QoS等级牺牲任务的部分准确率,从而进一步降低移动设备的能耗。由图4b可知,EA-QoS与NSGA-Ⅲ算法的任务处理时间的差距随工作量增大而逐渐减小。原因在于为节点分配QoS等级消耗时间不变且占比逐渐减小,而QoS对任务处理时间的优化效果随任务计算量增大而增大。在大多数情况下,采用NSGA-Ⅲ算法相较于普通基因算法,都能带来明显的性能改善。而引入QoS的优化角度能够进一步使工作流的设备能耗降低8.98%～12.31%。

4.4 EA-QoS卸载策略性能研究实验

本节主要研究EA-QoS和4种基本策略在最小化设备能耗和任务处理时间方面的表现。为探究不同用户对能耗E和整体延时T的偏好对卸载策略性能的影响,实验设置了4种不同的α等级以模拟从能耗敏感(α=50)到延时敏感(α=1 000)的场景,QoS等级设置为q=0.96。每组实验分别运行30次,将结果取平均值并记录。实验结果如图5所示。

图5 不同α下各卸载策略性能对比

由实验可知,在不同偏好的调度环境中,EA-QoS策略始终拥有相对较好的性能表现。由图5中优化目标实验结果中可以看出,EA-QoS策略的优化目标始终优于其他算法,其原因在于,EA-QoS策略综合考虑了任务执行时间与能耗关系,优化了任务卸载策略,如将任务中计算量较大、QoS等级要求较高的任务卸载至高性能低传输能耗的节点执行,可以降低任务整体延时并减少能耗。在该场景中,EA-QoS策略的性能相对其他4种基础策略提高了43%～87%。

为进一步探究EA-QoS的实际性能表现,实验测量图5对应的4组模拟实验中,边缘节点的工作负载与QoS等级的分配情况。qi为分配给边缘节点i的QoS等级,wi为该节点所分配的工作量,实验详细设置如表2所示。

表2 各算法工作负载与QoS等级分配情况

由表2可知,EA-QoS算法通过优化工作量分配和为边缘节点分配不同的QoS等级,实现了如图5所示的降低能耗与延时的整体性能提升。通过对比策略Ⅰ、Ⅱ可知,当将QoS等级从1放宽到0.96时,近似计算能够降低应用的时延与能耗。此外,通过比较策略Ⅱ、Ⅳ与EA-QoS算法的实际表现可以看出,EA-QoS算法相对于其他两种策略对能耗和时延的联合优化拥有更好的性能表现。

4.5 网络规模对EA-QoS的影响研究

为探究不同网络规模对于EA-QoS策略的影响,实验首先使用表1中的参数设置4个边缘节点,然后对工作流进行调度,测量能耗与延时情况,重复10次取平均值。实验完成后,在实验环境中添加4个边缘节点,参数与表1一致,进行下一次实验。重复上述步骤,直至环境中边缘节点个数达到40。实验主要测试了α=50,α=200和α=800时设备的能耗与任务延时情况,实验结果如图6所示。

图6 不同节点数量对EA-QoS算法的影响图

从实验中可以看出,随着可用边缘节点数量的增加,实现的优化目标E+αT值不断减小,说明EA-QoS能够有效利用边缘环境中的可用资源来进行任务调度。在α值较高的调度方案中,时间的权重比例较大,增加节点能够提供更多的优质节点选择,使任务执行时间大幅降低,故在α=800时,增加节点带来的收益最大,而在α=50时,增加节点带来的收益最小。当α一定时,随着边缘节点数增大,增加边缘节点带来的收益增量在不断减小,其原因在于,当边缘节点数增加时,任务划分数量增多能够减少一部分的执行延时,但传输时间不可避免,且不能无限划分任务,当任务工作量到某个临界值时,任务执行延时达到最低,此时工作流结束时间主要由数据传输时间决定。此外,由于协议和通信开销,有效数据传输的时间比例变小,将工作负载分配给更多的边缘节点也可能导致更高的能耗。

5 结束语

为进一步降低工作流卸载的能耗与延时,本文结合近似计算优化处理工作流任务,通过引入服务质量(QoS)的优化角度,限制任务准确度损失,并在此基础上考虑了不同场景下平衡移动设备的能耗与任务时延的问题,提出一种基于服务质量的能耗感知工作流卸载策略。该策略利用HEFT算法对工作流任务分层进行拓扑排序,保证遗传编码对应迁移策略的有效性;基于QoS的能耗感知优化降低了分配QoS等级的复杂度;结合NSGA-Ⅲ算法,加快了寻找全局最优解的速度。仿真实验结果表明,EA-QoS策略由于引入了QoS的优化角度,能够有效降低移动设备能耗并减少工作流延时,并且其结合NSGA-Ⅲ算法生成的卸载策略较4种基础QoS卸载策略,能耗与延时的优化效果显著。未来的工作中,期望能够进一步改进EA-QoS卸载策略,在该策略中考虑多用户的工作流租用成本问题与卸载过程中的安全问题,并结合工作流调度历史进行研究。