端边云协同环境下能耗感知的工作流实时调度策略

秦志威,栗 娟+,刘 晓，朱梦圆

(1.武汉工程大学 计算机科学与工程学院，湖北 武汉 430205；2.武汉工程大学 智能机器人湖北省重点实验室,湖北 武汉 430205；3.迪肯大学 信息技术学院，澳大利亚 墨尔本 VIC 3125)

0 引言

近年来，随着物联网、移动互联网等技术的深入发展，涌现出了智慧物流、数字电网、智能家居、车联网等由大量终端设备、传感设备、通讯系统、数据中心组成的具体应用[1]。以基于无人机自主巡检的输电线路巡检为例，利用无人机拍摄输电线路通道图像，并进行图像特征提取和挖掘，识别出设备故障，其执行过程是一个典型的业务流程，也称为工作流应用[2]。对于这样一个内部逻辑结构复杂、传输数据量大、实时性要求高的工作流，若利用传统的云计算技术将工作流中的所有子任务均上传到云数据中心处理，则不仅将增加网络带宽负载、加大任务数据传输时间，还给自身续航能力有限的智能终端带来巨大挑战。

为解决智能终端计算、存储、续航等能力不足的问题，作为一种新型的计算模式，边缘计算(Edge Computing, EC)通过充分利用靠近设备终端的网络、计算、存储等资源来提供就近服务，将各类计算任务就近卸载到边缘服务器去执行，有效解决了将任务直接上传到云数据中心带来的高延时问题，提升了任务处理实时性，缓解了网络带宽的压力[3-4]。

目前，边缘计算研究在国内外受到了越来越多的关注，其中计算卸载技术和资源调度技术被广泛应用于各类场景，如车载网、移动边缘计算、物联网、无人机巡检等。LIU等[5]结合边缘计算与车载网，将车辆作为边缘服务器，用户设备的任务可以卸载至车辆执行；GAO等[6]提出一种结合移动边缘计算与深度神经网络的计算任务卸载模型，基于该模型提出的基于多重资源任务卸载的粒子群优化调度(Multi-Resource task offloading based Particle Swarm Optimization scheduling, MRPSO)算法能够有效降低终端能耗；DENG等[7]针对物联网设备延时问题，提出一种结合边缘计算的框架，物联网设备可以将任务卸载至边缘服务器执行，从而满足低时延需求。综合来看，有关计算卸载的研究大多只针对终端任务是否卸载到边缘层，忽略了云资源，然而对海量数据进行挖掘和分析是很多工作流任务中重要的内容，不但离不开功能强大的云资源，而且需要处理一些对实时性要求高的任务。因此在工作流执行过程中，对数据处理效率、网络服务质量等的要求更高，需要将端边云三层异构资源有效协同才能弥补智能终端在自身续航、计算能力和存储能力等方面的不足。

基于此，在基于端边云协同的工作流应用场景中：①可通过计算卸载技术将部分低延时任务卸载到边缘侧资源中处理，将对实时性要求不是很高的任务传输到云端处理，有机协同设备终端资源、边缘计算资源和云资源，最大化各自优势，从而加快巡检工作流任务的总执行时间，减少无人机自身耗能，提高系统效用[8]；②智能终端的移动性和边缘服务器的有效服务范围是其不可忽视的特征，在工作流执行过程中，需要根据终端实时位置和移动轨迹及时发现周边可用的资源进行任务迁移，以保证工作流完成时间，减少终端能耗。

针对上述问题，本文以端边云协同环境中的工作流任务为研究对象，结合终端设备移动路径，构建基于终端移动性的工作流任务执行时间模型、能耗模型和迁移模型，并构建一种能耗感知的工作流任务调度模型，在此基础上提出一种基于最低延时和最小能耗的工作流任务实时协同调度算法。

1 相关工作

近年来，从优化目标来看，边缘计算环境中的计算卸载技术大致分为以降低时延为优化目标、以降低能耗为优化目标和以两者结合优化为目标3类。

WANG等[9]将Web服务与移动边缘计算结合，提出一种基于强化学习的在线Web服务调度算法，降低了服务时延；REN等[10]通过将任务卸载到云服务器和边缘服务器来降低任务时延；WU等[11]针边缘计算场景下的服务请求延时问题，提出一种将遗传算法和模拟退火算法相结合的启发式算法，有效降低了服务请求时延；CHEN等[12]针对采用无人机处理大型任务，提出一种适用于无人机的智能任务卸载算法(Intelligent Task Offloading Algorithm, ITOA)，从而降低任务的平均执行时延。上述研究只针对任务完成时间进行优化，而且任务之间缺乏联系，无法适用于工作流任务场景。

HE等[13]设计了一种新型车辆网边缘计算模型，提出一种结合优先化经验回放和随机权值平均机制的深度强化学习算法，有效降低了车辆执行任务的能耗；FAN等[14]针对边缘计算环境中工作流任务的特点，提出一种基于最短路径算法的计算卸载方案，有效降低了系统能耗；LI等[15]提出一种基于移动边缘计算(Mobile Edge Computing, MEC)的物联网能耗感知任务卸载模型，根据每个任务的完成时间(Time-to-Live, TTL)选择最佳卸载位置，以降低任务传输及在边缘服务器执行任务的能耗；WANG等[16]提出一种单用户无线供电的MEC系统，针对任务卸载至边缘服务器产生的传输能耗和执行能耗，结合凸优化技术提出一种启发式算法，得到最佳卸载策略。上述研究只针对能耗进行优化，而且卸载资源仅结合边缘服务器，并未考虑云端资源。

ZHOU等[17]针对一种单移动终端设备和多边缘服务器的应用场景，利用Markov近似技术提出一种轻量级算法，使任务卸载的时间与终端能耗最小化；YAN等[18]首先提出一种多无线设备单边缘服务器的MEC模型，每个无线设备都有许多需要执行的任务，而且两个设备之间有些任务存在依赖关系，在此场景下提出一种Gibbs抽样算法获取最优卸载策略，使无线设备上的所有任务完成时间与设备能耗加权和最小；TRAN等[19]提出一种多用户多边缘服务器的MEC模型，将减少任务完成时间与终端能耗的加权和定义为任务卸载效益，采用凸优化和拟凸优化技术解决资源分配问题，并提出一种启发式算法获取最优卸载决策，使得用户任务卸载效益最大；由于带有能量收集的多设备多边缘器MEC系统是高度动态的，ZHANG等[20]提出一种基于深度强化学习的动态迁移算法，使任务完成时间与能耗的平加权和最小。上述研究虽然以权衡时延与能耗为目标，但是只使用了边缘端资源，并未考虑与云端资源结合。

综上所述，在基于端边云协同的工作流应用场景中，单一优化并不能满足工作流低时延、低能耗的要求，加上任务之间有一定联系，而上述研究很少考虑任务之间的联系，且大部分研究在任务卸载资源的选择上均未考虑使用云端丰富的资源。鉴于此，在基于端边云协同的工作流应用场景中，亟需采用针对工作流任务特性和终端移动性的端边云协同资源调度算法来降低任务完成时间与能耗。

2 端边云协同环境下的工作流任务调度模型

以无人机自主巡检系统为例，其构成主要包括无人机飞行控制系统和图像处理系统，如图1所示。

图像处理系统包括图像采集模块、通讯模块和本地处理模块。图像采集模块主要采集无人机巡检过程中拍摄的照片；通讯模块主要将图像处任务传输到边缘服务器或云服务器；本地处理模块主要处理在本地执行的任务。本文无人机巡检路线为固定路线，飞行所需的时间和能耗已知，因此只考虑图像处理系统产生的工作流任务所需的时间和能耗。

端边云协同环境下的工作流应用场景，以无人机巡检时输电线路中的设备故障诊断为例，其巡检过程如图2所示。整个任务执行过程看作为一个工作流，可用加权的有向无环图进行建模。

2.1 工作流任务模型

工作流任务用有向无环图(Direct Acyclic Graph, DAG)表示[21]为G=V,E，其中：V为n个任务的集合，V={v1,v2,v3,…,vn}；E为任务之间的依赖关系，E={(vi,vj)|vi,vj∈vn}。工作流中存在出口任务vout和入口任务vin，本文工作流任务只有一个入口任务和一个出口任务。每个任务由一个三元组vi={Ii,Di,Oi}构成，其中：Ii为任务输入的数据量，Di为处理任务所需的资源数，Oi为任务结束输出的数据量。以图2为例，一个工作流可用图3所示的DAG表示。

2.2 端边云资源模型

工作流任务可以在本地端处理，可以卸载至边缘端执行，也可以卸载至云端处理，通过本地通讯模块将任务发送至其他位置，其通讯模型如图4所示。

终端资源可用L={fl,Pwork,Pin,Pout,Pwait}表示，其中：fl为终端的计算能力，Pwork为终端执行功率，Pin为传输功率，Pout为下载功率，Pwait为空闲功率。

边缘端资源由多个服务器构成，假设有s个边缘服务器，M为边缘服务器的集合，M={m1,m2,…,ms}。为了简便计算数据的传输，假设基站的信道充足，数据的传输带宽由基站决定，每个基站由一个三元组mj={Rj,fej,Dej}构成，其中：Rj为上传带宽，fej为边缘服务器的计算能力，Dej为下载带宽。

云端资源由一个拥有海量资源的云服务器C={Rc,fc,Dc}构成，其中：Rc为上传带宽，fc为计算能力，Dc为下载带宽。

2.3 时间模型和能耗模型

任务可以在本地、边缘服务器和云服务器上执行。将工作流任务的出入口任务均设为不可卸载任务，只能在本地执行，剩余任务可以在不同位置执行。为了简化模型，假设每个服务器同时只能处理一个任务。

(1)本地执行

任务vi在本地执行时，只考虑任务执行时间。本地任务完成时间为

(1)

式中Di为任务所需资源数。

本地执行能耗为

El(vi)=Tl(vi)·Pwork。

(2)

(2)边缘服务器执行

考虑到终端设备的移动性，当任务vi卸载至边缘服务器j执行时，会出现任务可以成功执行、任务上传成功但无法返回结果和任务上传过程中失败3种情况。当任务发生迁移时，可忽略相关数据在边缘服务器之间的传输时间。

当任务成功执行时，任务完成时间为

(3)

式中：Ii为任务的输入数据量；Oi为任务输出的数据量。

任务在边缘服务器执行的能耗为

(4)

当任务上传成功但结果无法返回本地时，任务需要迁移到可用边缘服务器k中，然后将结果传输到本地。此时任务执行时间为

(5)

(6)

当任务无法成功上传时，需要重新选择卸载位置，以保证任务成功执行。因为任务仍在本地，所以不考虑等待时间。

(3)云端执行

与边缘服务器类似，云服务器的执行时间为

(7)

式中：Rc为任务的上传带宽；fc为云服务器的计算能力；Dc为任务的下载带宽。

任务在云端执行的能耗为

Ec(vi)=

(8)

由于工作流任务之间有联系，需要确定任务执行顺序。通过定义工作流任务的优先级，再对优先级的值进行区域划分，相同等级的任务可以并行执行，从而得到任务的执行顺序。用rank(vi)表示任务vi的优先级，令出口任务的优先级为1，同一区域的任务可以在本地、边缘端和云端并行执行，每个区域的执行时间为所有任务在不同位置执行的总时间。假设区域i中有a个任务在本地执行，b个任务在边缘服务器执行，c个任务在云服务器执行，则区域i的完成时间为

(9)

假设rank(vin)=k，则工作流任务的完成时间为

(10)

任务执行的总能耗为

(11)

式中ai+bi+ci=1，ai，bi，ci∈{0,1}，表示任务只能在本地、边缘端和云端中的一处执行。

2.4 工作流调度模型

在端边云协同环境下，执行工作流需要有效结合端边云3层计算资源，将任务卸载至不同的服务器并行执行，以降低任务完成时间和终端能耗。由式(10)可得工作流任务的完成时间T，由式(11)可得执行任务所耗费的总能耗E，将问题优化目标设置为任务完成时间与智能终端能耗的加权和最小，得到如下优化问题：

(12)

s.t.

C1：T≤Tmax；

C2：E≤Emax；

C3：0≤ω≤1。

其中：C1表示工作流任务完成的时间不能超过最大限制时间；C2表示任务执行能耗不能超过最大限制能耗；C3表示权重的取值范围不能小于0，也不能大于1。

3 能耗感知的工作流任务调度算法

本文针对端边云协同环境下工作流调度问题提出一种能耗感知的工作流任务调度算法(Energy-Aware Workflow Scheduling Algorithm, EAWSA)。算法主要思路为：①针对工作流任务的特性划分每个任务的优先级；②根据每个任务的优先级，采用改进的粒子群优化(Impoved Particle Swarm Optimization, IPSO)算法获取每个任务的最优执行位置；③在任务执行过程中考虑边缘服务器的有效范围，通过判断任务执行状态选择适当的迁移策略，实时更新任务执行的位置，最终使整个系统效用最优。

(1)划分任务优先级

首先划分工作流任务的优先级，将出口任务优先级定位为1，假设任务vm和vp是vn的直接前置任务，则vm和vp的优先级为

rank(vm)=rank(vp)=rank(vn)+1。

(13)

如果vm也是vp的直接前置任务，则vm的优先级为

rank(vm)=

max{rank(vp)，rank(vn)}+1。

(14)

然后从倒数第2个任务开始，根据DAG获取当前任务的直接后置节点，计算其后置节点任务的最大优先级数，依次类推，得到所有任务的优先级。将相同优先级的任务划分到同一集合，得到任务的执行顺序。最后，依次从最高优先级的任务区域开始执行任务。

(2)资源冲突解决算法

相同区域中的任务有可能同时分配到同一个资源，对于有冲突的任务，通过Min-Min算法解决资源冲突问题。首先获取每个资源的冲突任务集合，依次计算每个任务的完成时间，将完成任务时间按升序排列，即得到任务的执行顺序。

(3)IPSO算法

IPSO算法主要根据初始位置获取当前最佳的卸载策略，该算法包括初始化任务卸载策略、算法迭代和返回全局最佳卸载策略3部分。初始化任务卸载策略是随机生成任务的卸载策略和搜索速度，根据任务卸载策略计算每个粒子的适应度值，其中适应度函数为

(15)

式中：α为时延的权重，α∈[0,1]；Tmax为所有任务都在本地端执行时的任务响应时间；Emax为所有任务都在本地端执行时的系统总能耗。然后比较所有粒子的适应度值，得到初始的全局最优卸载策略(第2～10行)。算法迭代是根据定义的迭代次数进行循环，根据公式更新每个粒子的速度和位置(第13～14行)，从而更新全局最佳卸载策略(第15～20行)。迭代结束后返回的是全局最佳卸载策略(第23行)。伪代码如下：

算法1IPSO()。

输入：最大迭代次数(Max_Iteration)、终端属性(localList)、边缘服务器属性(edgeList)、云服务器属性(cloudList)。

输出：最优卸载策略(Gbest)。

1 GetlocalList, edgeList, cloudList；//获取开始位置所有的服务器信息

2 Initial population generation；//初始化种群速度与位置

3 For i=1 to population size

4 Calculate fitness[i]；

5 End for；

6 For k=1 to population size

7 P[k].best=current position;//记录最小适应度的粒子位置；

8 P[k].bestfitness=current fitness;//记录最小适应度值；

9 End for；

10 Gbest=the lowest fitness position；// 将初始最小适应度值的粒子位置赋给Gbest；

11 For i=1 to Max_Iteration

12 For k=1 to population size

15 Calculate new fitness；//计算更新后的适应度值

16 If new fitness< P[k].bestfitness

17 P[k].bestfitness=new fitness；

18 P[k].best=current position；

19 End if；

20 End for；

21 Gbest=the lowest fitness position；

22 End for；

23 Return Gbest

(4)最优迁移

迁移算法主要根据终端实时位置进行最优迁移，算法分为计算优先级区域的开始时间和完成时间、选择任务迁移方式和返回全局最佳卸载策略3部分。计算优先级区域的开始时间与完成时间是根据IPSO算法得到最佳卸载策略，计算每个区域的开始时间和完成时间(第1～6行)。选择任务迁移方式是根据终端到边缘服务器之间的距离和任务执行状态，选择当前任务完成适应度值最小的迁移方案(第7～24行)。根据任务的迁移方案更新最佳卸载策略(第25行)，最终返回最佳迁移卸载策略(第26行)。伪代码如下：

算法2Task-migration()。

输入：最优卸载策略(Gbest)、区域个数(ranklist)、终端属性(localList)、边缘服务器属性(edgeList)、云服务器属性(cloudList)。

输出：最优卸载策略(Gbest)。

1 GetlocalList, edgeList, cloudList；//获取所有服务器信息

2 Calculate tasks of EST and EFT；//计算最佳卸载策略的每个任务开始和结束时间

3 For i=1 to ranklist //计算每个优先级区域的EST和EFT

4 Rank[i][0]=EST;

5 Rank[i][1]=EFT;

6 End for；

7 For i=1 to ranklist

8 Calculate tmax//计算离开目标服务器时间

9 If Rank[i][1]>tmax//判断当前区域任务完成时是否离开目标服务器

10 Obtain all tasks which need migration;//获取需要迁移的任务

11 Sort by EST;//将需要迁移的任务按照开始时间进行升序排序

12 For k=1 to MigrationList size

13 Migration_way[MigrationList[k]=current way//根据每个任务的情况选择对应的卸载方式

14 Migration_loction[MigrationList[k]]=current location;//选择适应度值最小的位置进行迁移

15 Update the EST and EFT；

16 Best_EFT=current EFT;//记录最后一个任务的完成时间

17 End for;

18 If Best_EFT!=Rank[i][1]

19 Migration_time[i]=Best_EFT-Rank[i][1];

20 Update Rank[i][1], Rank[i+1][0]and Rank[i+1][1]//如果当前区域最后一个任务时间改变，则改变当前区域的EFT以及下一个区域的EST和EFT。

21 End if;

22 End if;

23 Update the EST and EFT of all tasks；

24 End for；

25 Update Gbest;//根据迁移情况更新任务位置

26 Return Gbest

4 实验分析

4.1 环境及参数设置

为了分析和验证所提模型和算法的有效性，采用JAVA语言编写并设计了仿真实验，实验运行环境为11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40 GHz(8 CPUs),2.4 GHz CPU,16 GB内存的PC机。工作流为混合型结构的DAG(如图5)，该工作流中包括N个子任务节点，这些子任务节点中既有汇聚节点(如节点5和节点N)，又有并发节点(如节点2和节点3)。新增两个哑节点In和Out分别表示工作流的起始节点。

除此之外，仿真实验中包括1台云服务器(计算能力为7 GHz)、1个智能终端(计算能力为1 GHz)和3个边缘服务器(计算能力分别为3 GHz，2 GHz，2 GHz)，如表1所示。

表1 任务卸载仿真参数

4.2 评价指标

问题的优化目标是工作流任务的完成时间和系统能耗，因此选取任务完成时间、系统能耗、总体的适应度值3个指标进行评价分析。

对比算法包括任务全在本地执行(local)、任务卸载到云端执行(cloud)、任务随机卸载至边缘服务器执行(random)和使用IPSO算法但不使用迁移算法(Nomigration)，通过比较不同任务数量下的时间、能耗和适应度评价算法性能，其中Random算法采用相同的任务迁移算法。

4.3 结果分析

本文主要的判断依据是在不同权值下工作流任务数不同时每种算法的性能。每种情况取10次实验结果的平均值，分别比较每种算法在不同任务数下的任务完成时间、终端消耗能量和适应度值。

当权值ω=0.5时，工作流任务完成时间的实验结果如图6所示。

由图6可见，随着任务数的增加，各算法的工作流任务完成时间均逐渐增加，EAWSA任务完成时间的增长速度最低，说明该算法在降低时间方面效果显著。当任务数量为20时，EAWSA与Nomigration算法的工作流任务完成时间相同，主要因为任务完成后并未离开目标边缘服务器，所以没有发生任务迁移。随着任务数的增加，工作流任务中的部分任务不能在离开目标服务器之前完成，需要任务迁移。因为Nomigration算法未使用迁移算法，所以任务完成时间逐渐大于EAWSA的完成时间。Random算法因为采用了迁移算法，所以任务完成时间增长得比较缓慢，但仍大于EAWSA。总之，EAWSA能够降低任务完成时间。

算法能耗如图7所示。可见随着任务的增加，本地能耗增长迅速，其余能耗增长缓慢。

随着任务数的不同，各算法的适应度值如图8所示。可见，EAWSA的适应度最低，其次是Nomigration算法。本文主要考虑任务完成时间与能耗的加权和，权值系数均取0.5表明时间和能耗的重要性相同，虽然Random算法的能耗较低，但是任务完成时间相对较长，因此适应度值较高。综合来看，本文所提算法能够明显降低时延和能耗。

工作流任务类型不同，用户定义的服务质量(Quality of Service, QoS)不同，时间与能耗的权值也不同。因此，本文第2组实验重在考察时间和能耗权值对算法性能的影响，设置任务数量为60时ω=0.3，0.5，0.7。实验取10次结果的平均值，任务完成时间、能耗和适应度值如图9～图11所示。

由图9～图11可见，当权值小于0.5时，EAWSA更注重任务完成的能耗，因为本地执行任务能耗较大，所以会将任务卸载至边缘端和云端，使相应的任务完成时间有所增加；当权值大于0.5时，算法更加侧重任务完成时间，因为任务传输至云端的时延较大，所以侧重于本地与边缘层，但会增加相应的任务完成能耗。总之，每种情况下EAWSA的适应度值最小，表明该算法对时间与能耗的平衡最好。

5 结束语

本文考虑智能终端移动性、边缘服务器覆盖范围和工作流任务，提出结合端边云3层资源协同的任务完成时间与能耗模型，并提出EAWSA。首先，针对工作流任务的特性，提出一种工作流优先级划分算法，以确定工作流任务执行顺序；然后通过使用IPSO算法获取最佳任务卸载策略，同时为解决资源冲突问题，将任务分配到相同资源后采用Min-Min算法获取冲突任务的执行顺序；最后考虑到终端移动性和边缘服务器的范围，对最佳卸载策略中的部分任务进行最优迁移，并通过仿真实验验证了EAWSA在降低任务完成时间与能耗方面具有优势。未来将进一步研究任务迁移过程中的安全问题，通过一种边缘服务器的信任评估模型来保证任务迁移的成功率。