移动边缘计算环境下服务工作流容错调度算法

袁友伟，黄锡恺+，俞东进，李忠金

(1.杭州电子科技大学 计算机学院，浙江 杭州 310018；2.复杂系统建模与仿真教育部重点实验室，浙江 杭州 310018)

0 引言

随着移动互联网技术的不断发展，涌现出越来越多的新型移动应用程序，其中部分应用如人脸识别、自然语言处理和增强现实[1]对于计算资源有较高的需求。由于移动设备在存储器、电池和处理器等方面[2-3]的限制，部分新型移动应用程序无法在其上运行，而移动边缘计算(Mobile Edge Computing, MEC)的出现，为解决上述问题提供了新的平台和思路。在MEC的工作流调度过程中，将移动设备中需要大量计算资源的任务卸载至边缘侧的演进节点(evolved Node B，eNB)中执行[4]，可以减少任务执行时间。服务工作流延时优化[5]是MEC环境下工作流调度的核心问题，然而随着应用的不断发展，服务工作流所需要的计算资源需求量日益增加，传统的调度方案已经不能够满足日渐增长的计算需求，故需对调度方案[6]进行优化。在任务执行过程中，服务器通常会因资源节点的软件或者硬件故障问题出现资源失效情况[7]，导致在其上运行的任务执行失败，故需引入容错技术减少任务失败率，提高工作流执行的稳定性。目前调度算法大都只针对工作流延时问题或容错策略中的某一方面进行考虑，而在实际工作流调度过程中，任务出错无法避免，故需要综合考虑工作流延时问题和容错策略。

基于上述分析，本文研究了移动边缘环境下服务工作流容错调度，针对移动端的服务工作流调度问题，提出一种适用于多服务工作流的容错免疫粒子群优化调度算法(Fault Tolerant Immune Particle Swarm Optimization algorithm, FT-IPSO)。该算法利用异构最早完成时间(Heterogeneous Earliest Finish Time, HEFT)算法对抵达的工作流进行分层，并计算其中的任务权重生成就绪队列，保证了调度的公平性；通过免疫算法保持粒子群寻优的全局性，避免粒子陷入局部最优解；制定了一种混合容错策略，根据任务子期限以及任务期望执行时间确定任务容错方法，保证服务工作流在执行过程中的鲁棒性；在粒子的编码设计中以整数映射任务和资源节点的调度关系，并考虑了主副版本任务的调度位置，加快了粒子群的寻优速度。

1 相关工作

近年来，随着MEC的发展，大量学者对移动边缘环境下的工作流卸载问题以及工作流容错调度算法进行了研究，本章主要从MEC下工作流卸载和容错算法两方面对研究现状进行介绍。

MEC是一种新颖的并行计算技术，该技术可将移动设备中具有严格延迟要求的计算密集型任务卸载至边缘服务器中执行，有效降低任务的传输延时。ZHAO等[8]针对移动边缘环境下具有延迟限制工作流任务卸载的问题，提出一种最小化延时优化算法，将具有严格延迟边界的任务卸载到边缘云，并将松散延迟边界的任务卸载到远程云。CHAMOLA等[9]通过将计算密集型任务卸载到云服务器，解决了cloudlet网络中的任务分配问题，降低了任务延时。LE等[10]针对移动边缘环境中多用户共享资源的任务卸载问题，制定了相应的联合优化问题优化算法，使得用户任务的完成时间最小化。CHEN等[4]利用软件定义网络的思想，将工作流任务卸载问题表示为NP-hard的混合整数非线性程序，并提出一种工作流任务卸载方案，有效减少了任务的执行时间。

容错策略能够增强工作流运行的稳定性，减少因任务失败带来的损失，从而提高工作流执行效率，经典的工作流容错策略主要包括任务复制[11-12]、重提交[13]和检查点[14]等。ZHAO等[11]提出了根据任务特性制定不同数量的副本任务个数的容错算法，在利用任务复制策略保证系统可靠性的同时降低了系统冗余程度。VINAY等[12]提出了一种启发式的基于异构最早完成时间(Cluster based Heterogeneous Earliest Finish Time, C-HEFT)算法，其通过使用配置资源的空闲时间重新提交失败的任务，减少了任务的失败率从而保证了工作流的成功执行。WANG等[13]提出一种基于复制策略的最大化系统可靠性调度(Replication-based scheduling for Maximizing System Reliability, RMSR)算法，该算法通过任务的动态副本机制，大幅减少了复制机制引起的额外通信量。NIRMALA等[14]使用轻量级同步检查点重新提交失败的任务，确保任务在不稳定的环境中能够成功执行。ABDELFATTAH等[15]提出一种任务复制策略和重提交策略相结合的混合容错模型，一旦故障发生到最高可靠性处理节点，将重新计划任务，确保任务的正确执行。LEE等[16]提出了考虑检查点和复制机制相结合的容错调度算法，提高了准确性，减少了资源消耗并降低了任务的平均执行时间。

2 系统模型

本章主要介绍MEC环境下服务工作流容错调度模型、工作流模型、可靠性模型以及调度目标，其中工作流容错调度模型为整体的结构模型，工作流模型、可靠性模型为工作流容错调度模型的组成部分，描述了所研究的工作流的结构和调度过程中任务执行出错的可能性，具体模型描述如下。

2.1 MEC环境下服务工作流容错调度模型

MEC环境下服务工作流容错调度模型如图1所示。系统首先对用户提交的服务工作流进行建模并分层生成就绪任务队列，然后将其提交至用户设备(User Equipment，UE)端的任务调度器进行编码，并利用容错免疫粒子群优化调度算法确定各个任务所采用的容错方案调度寻优，输出调度结果，将其交给UE端任务管理器，根据所得调度方案对任务进行分配，根据任务执行情况进行动态资源调整，最后得到最优调度方案下的服务工作流执行结果。

2.2 工作流模型

在MEC中，服务工作流以有向无环图集DAGs表示：W={w1,w2,…,wN}。其中：N为工作流数。wi={(V,E),RD}(i=1,2，…,n)表示其中一条工作流，V={ti,0,ti,1,…,ti,n}为任务集合;ti,j代表第i个服务工作流中的第j个任务;RD为服务工作流可靠性需求;E={(ti,m,ti,n,tdi,m,n)|ti,m,ti,n∈V}为任务之间的边集，描述任务之间的依赖关系，ti,m为ti,n的前驱任务，tdi,m,n为ti,m向ti,n传输的数据集。任务的前驱和后继任务集定义如下：

定义1前驱和后继任务集。ti,j所有的前驱任务集为其所有前驱任务组成的集合：pred(ti,j)={ti,k|(ti,k,ti,j,tdi,k,j)∈E}，后继任务集为：succ(ti,j)={ti,m|(ti,j,ti,m,tdi,j,m)∈E}。

每个任务都有自身的属性：ti,j={di,j，ci,j,oi,j},di,j、ci,j和oi,j分别表示输入数据大小、完成该任务需求计算资源和输出数据大小。如图2所示为一个移动边缘环境下健康应用程序的工作流实例图，选取了工作流中有依赖关系的两个任务节点，并列出了详细的配置信息。节点ti,j从文件中读取数据，在获取体重数据之后将结果写至相应文件，节点ti,k从多个输入文件中读取数据并计算健康状况，将结果写至结果文件。

本文主要考虑单出入口节点的服务工作流，并将服务工作流任务按层进行划分，任务的深度计算公式如下：

(1)

其中DP(ti,j)为任务深度，若ti,j为入口任务，则其深度为0。

2.3 可靠性模型

在MEC环境中，任务在n号资源节点上执行的失败概率

(2)

其中：λ为故障系数，RDi为第i条工作流wi的可靠性需求，TLn为编号为n的资源节点的可信度。

2.4 调度目标

本文以最小化延时为目标调度服务工作流，若系统中有n个服务工作流，则服务工作流平均延时

(3)

式中makespan(wi)表示服务工作流wi的完工时间，

makespan(wi)=max{lft(wi,M)}-lft(wi,0)。

(4)

式中：max{lft(wi,M)}为最大层任务结束时间，lft(wi,0)为服务工作流首个任务的到达时间。式(3)给出了未考虑容错的调度目标，但是在实际中会有任务执行失败的情况发生，第3章将结合可靠性模型详细介绍任务容错方法。

3 容错免疫粒子群优化调度算法

在移动边缘环境下的多服务工作流调度中，本文提出的FT-IPSO算法以粒子群算法[17-18]为基础算法，在粒子群算法中加入工作流调度问题，利用免疫算法的免疫操作保证工作流调度方案的全局性，并加入容错策略保证工作流执行的鲁棒性。本章主要从容错策略、粒子编码设计、粒子适应度函数、算法流程方面对FT-IPSO算法进行介绍，并分析算法的复杂度。移动边缘环境下服务工作流调度算法定义如下：

定义2映射关系。在移动边缘环境中，任务和资源节点之间的分配关系映射为整数，如Xi,j=5表示将Xi,j分配至5号资源节点。其中Xi,j∈[0,n+0.5]，i∈[1,m],j∈[1,2n]，n为资源节点数目，i表示种群编号，j表示相应的任务的分配节点，Xi,j取值为小数时，则取整数部分作为任务调度节点位置。

3.1 容错策略

本文结合任务复制和重提交策略，设计了一种混合容错策略，主要包含两个版本任务，分别为主本任务和副本任务，副本任务的容错方式根据下式确定：

(5)

dl(ti,j)=TDP(m)+lft(wi,m),DP(ti,j)=m。

(6)

式中：DP(ti,j)为任务ti,j所在层的深度;TDP(m)和lft(wi,m)分别为每层可分配期限和工作流中第m层的运行结束时间，每层可分配期限

TDP(m)=(dl(wi)-lft(wi,0))×

(7)

层结束时间由该层中最迟结束的任务确定，若服务工作流的最大深度为M，则层结束时间计算方法如式(8)所示：

lft(wi,m)=

(8)

其中：at(wi)为工作流wi到达时间，st(ti,j)为任务ti,j的开始时间，Te(ti,j)为任务ti,j的执行时间。

3.2 粒子编码设计

粒子编码方案如图3所示，在使用容错免疫粒子群优化调度算法实现多服务工作流调度时，需考虑任务的执行顺序并分配卸载位置。任务的执行顺序由就绪队列给定，编码中相邻两个位置为某个任务不同卸载位置，以整数表示。若编码值为小数，则取整，当任务卸载位置为0时，其将在本地执行，否则任务将被卸载至相应编号的边缘服务器中执行。

3.3 粒子适应度函数

根据容错调度策略，若任务在某个资源节点执行成功，则副本任务或重提交任务将不会执行；若主本任务执行失败，则副本任务在不同资源节点中继续执行。因此，任务的期望时间E(ts)为：

Pkeep(ftj)×(ftj+1-ftj);

(9)

(10)

其中：Pkeep(sts)和Pkeep(fts)分别为任务在时间点sts和fts之后继续执行的概率，sts和fti分别表示在第s次执行的开始时间和第i次执行的结束时间，粒子适应度

fit(Xi)=E(Xi)+α·Pfail(Xi)。

(11)

式中：E(Xi)为粒子Xi的期望调度时间，α为对于任务失败率的惩罚系数，Pfail(Xi)为粒子Xi调度的整体失败率。

3.4 FT-IPSO算法流程

如图4所示为FT-IPSO算法的流程，主要包括以下步骤：首先，利用随机数和得到的就绪队列根据编码策略初始化粒子群;然后,计算服务工作流子期限，确定任务使用的容错策略，并采用免疫操作避免粒子在迭代过程中陷入局部最优解，保证寻优的全局性；最后，利用更新公式更新粒子群，通过种群迭代寻找最优调度方案。若粒子调度序列的适应度值不再更新，则认为当前调度方案最优，并输出最优调度方案。

3.4.1 工作流分层排序

本文使用HEFT算法对初始工作流进行加工并生成就绪队列，该算法首先计算每个任务深度并分层，然后对任务权重进行计算，最后对每一层的任务按照权重值大小进行升序排序合并，任务权重计算方法如下：

(12)

rank(ti,j)=ci,j/Pref。

(13)

3.4.2 工作流中粒子群容错方法选取

本文提出一种任务复制和重提交相结合的容错策略，首先对主本任务和副本任务的执行时间和相应的数据传输时间进行计算，再利用所得结果根据

式(5)确定工作流任务所采用的容错方式。若满足公式，则将任务的容错方法设置为重提交，副本任务将在主本任务失败后重提交至不同服务器中执行；否则使用主动任务复制策略，主副版本任务将会一同提交至不同服务器执行，工作流任务容错方法选取如算法1所示。

算法1工作流任务容错方法选取算法。

输入：任务子期限矩阵dead_t，开始时间矩阵strat_t，eNB性能集合P_eNB，

任务位置矩阵X；

输出：任务容错方案矩阵FT。

1. for i=0 to m+s do /*种群遍历*/

2. for j=0 to 2n-1 do/*个体循环*/

3. Comp_time_p=c[i][j]/P_eNB(x[i][j])/*主本任务在所调度基站中的执行时间*/

4. Comp_time_b=c[i][j]/P_eNB(x[i][j+1])/*副本任务在所调度基站中的执行时间*/

5. Calculate tr_prime and tr_back /*计算在主副版本任务所调度基站的数据传输时间*/

6. if dead_t-strat_t>Comp_time_p+Comp_time_b+max(tr_prime,tr_back)

7. ft[i][j]=0/*用0表示重提交策略*/

8. else

9. ft[i][j]=1/*用1表示任务复制策略*/

10. end if

11. end for

12.end for

3.4.3 粒子群算法免疫操作

(14)

(15)

(16)

3.4.4 工作流任务调度序列信息更新方法

任务的调度位置和粒子速度更新公式如下：

(17)

3.5 算法复杂度分析

在FT-IPSO算法中，给定粒子群种群规模为s，每次随机生成的抗体数量为m，同时给定n个服务工作流任务，则算法所占用的空间为：存储任务调度位置和粒子适应度值所占用的空间(s+m)×(2n+1)，粒子速度矩阵所占用的空间s×2n，以及其他变量和常量所需空间C，故空间复杂度为：S(n)=O(s×4n+m×2n+C)。在迭代过程共有s个粒子执行寻优工作且需要进行maxG次迭代找到最优工作流调度方案，故算法的时间复杂度为：T(n)=O(s×4n×maxG+C)。

4 仿真实验

为分析和评估FT-IPSO算法性能，本文进行了大量实验：首先，对不同条件下的FT-IPSO算法表现进行了实验，然后，为探究FT-IPSO算法与其他算法之间的性能差异，分别选取了C-HEFT算法[12]、基于聚类启发式算法的检查点和复制(Checkpointing and Replication based on Clustering Heuristics, CRCH)算法[14]和加入混合容错策略的反应式容错(Reactive Fault Tolerance Approach, RFTA)算法[15]作为比较对象。

4.1 实验环境与实验参数

本文使用EdgeCloudSim[20]模拟MEC环境，随机生成服务工作流任务，其中服务工作流[21]任务的计算量服从[1,10]的均匀分布(单位：GHz)，任务输出数据的大小服从[1,10]的均匀分布(单位：Mb)，每个服务工作流包含的任务节点数为10～100个。另外，eNB个数为10个，工作可靠性需求(RD):0.6～0.9，服务器可信性等级(TL)：0.4～1.0，式(2)故障系数λ=2.7。移动端的计算能力为1.2 GHz，上传和下载速率分别为5 Mb/s和10 Mb/s；边缘服务器的计算能力为4 GHz，传输速率为100 Mb/s。参考文献[22]中的参数设置，本文实验中边缘环境中粒子群参数设置为：粒子速度Vmax=0.6；最大迭代次数maxG=500；粒子群种群数s=50；每次循环新增抗体数量m=20；惯性权重w0=0.73；学习参数c1=c2=1.496 18；适应度函数中γ=10。本文实验平台如下：Inter(R)Core(TM)i7-8700K处理器；32 GB内存；Windows 10专业版64位操作系统。

4.2 不同条件下FT-IPSO算法表现

为探究FT-IPSO算法在不同条件下的表现，改变eNB个数和工作流任务到达率，对不同的工作流进行实验并取平均值。在粒子群种群数为50、最大迭代次数为500和重复实验次数为10的条件下对算法进行实验，得到的结果如图5和图6所示。

由图5可以看出，当eNB数量增多时，任务延时逐渐降低，其原因在于边缘服务器和移动设备的性能差异较大，当FT-IPSO算法将计算需求较大的任务卸载至eNB中并行执行，能够缩短任务执行时间，工作流的平均延时大幅降低。但是由于工作流中最大可并行任务数量存在上限，当eNB数量超过一定值时，任务延时下降幅度减小。图6显示了在eNB数量为10的情况下，不同工作流到达率的任务平均延时的影响。FT-IPSO算法将部分计算量小但数据传输量大的任务保留至本地执行，将计算量大的任务调度至边缘服务器，减少任务执行时间，从而降低了任务的平均延时。此外，本文统计了FT-IPSO算法在工作流数量为50的情况下，不同eNB的可信度值下任务失败率变化情况，其中任务失败率为主本任务执行失败的任务个数占总任务数的百分比，实验结果如表1所示。

表1 不同eNB的可信度值下任务失败率变化情况

续表1

由表1可知，当资源节点可信度一定时，任务可靠性需求越高，任务失败率越高；当任务可靠性需求不变，资源节点可信度逐渐增加时，任务失败率下降。

4.3 相同条件下不同算法对比实验

4.3.1 与C-HEFT算法对比

为验证FT-IPSO算法在求解服务工作流调度问题上的有效性，将FT-IPSO算法与C-HEFT算法和FT-IPSO算法进行比较。在相同环境下，将FT-IPSO算法的种群数设置为50，最大迭代次数为500次，其他实验参数与C-HEFT算法保持一致，采用相同的初始解生成方式，对16个服务工作流实例进行对比实验，两种算法求解的调度方案适应度值结果如表2所示。

表2 FT-IPSO算法与C-HEFT算法解的适应度值对比

由表2可知，与C-HEFT算法相比，本文所设计的FT-IPSO算法在16个工作流实例实验中均得到了两种算法的中的最优解，且解的提升幅度较大。在算法的标准方差上，由于FT-IPSO算法中引入了免疫算法，保证了解的全局最优性，解的波动性较小，因此，从解的质量上可以看出，FT-IPSO算法具有较强的竞争力。

4.3.2 不同算法性能对比

为进一步验证FT-IPSO算法在求解多服务工作流调度问题中的有效性，分别选取不同算法作为对比实验，并设置任务首次执行失败率、任务平均延时作为性能指标，在相同的实验条件下，记录不同算法的各项实验数据，并对其进行分析，实验结果如图7和图8所示。

由图7和图8可知，FT-IPSO算法相对于CRCH算法、C-HEFT算法和RFTA算法拥有较小的工作流延时和较低的任务失败率，其原因在于本文提出的FT-IPSO算法对容错策略进行了优化，利用任务复制和重提交相结合的容错策略降低了系统的冗余程度以及任务失败率，一方面减少了系统因任务失败导致的额外任务调度和执行时间开销，并且有部分任务采用重提交策略时，其主本任务执行成功之后副本任务不需要再次执行，节约了系统资源，从而降低了工作流延时;另一方面通过改进的免疫粒子群算法寻找最优调度方案，提高了解的全局性，确保最终方案为使任务调度延时最低的调度方案。因此，FT-IPSO算法在求解多服务工作流调度问题时具有高效性，且解的质量更优，在延时上相对于使用混合容错策略的RFTA算法缩短了约4.1%，较CRCH算法和C-HEFT算法分别缩短了约6.3%和9.1%。

5 结束语

MEC中服务工作流调度是边缘计算研究中的一个重要内容。本文改进了粒子群算法，并将其与服务工作流调度问题相结合，提出了FT-IPSO算法，改进包括：利用HEFT算法对分层合并后的任务计算权重并生成就绪队列，保证了调度公平性；在粒子群算法中算法融入免疫算法，解决了粒子易陷入局部最优的缺陷，确保解的全局性；加入了一种任务复制和重提交策略相结合的容错算法，提高了工作流执行的稳定性。仿真实验结果表明，使用FT-IPSO算法能够有效减少服务工作流延时，且其相对于CRCH算法和C-HEFT算法所占用的系统资源更少；在确定任务容错策略时，考虑了任务子期限，较RFTA算法更好地制定了任务所应采用的容错方法，减少了任务错误率，延时的优化效果更优。在未来工作中，期望能够进一步改进算法，在算法中引入多服务工作流的费用模型和移动设备能耗模型，并对已知服务工作流历史到达情况的调度问题进行研究。