云边协同环境下基于局部关键路径的工作流应用调度策略

林潮伟,林 兵,陈 星

1(福州大学 计算机与大数据学院,福州 350108)

2(福建省网络计算与智能信息处理重点实验室,福州 350108)

3(福建师范大学 物理与能源学院,福州 350117)

0 引 言

工作流应用结构复杂,通常包含数十个计算任务,这些任务之间具有数据或控制流依赖关系.典型的工作流应用[1]包括基于深度神经网络(Deep Neural Network,DNN)的应用、物联网(Internet of Things,IoT)应用等.这些应用计算复杂度高,对数据传输时延敏感,一般需要高性能的计算平台来执行完成.云计算提供强大的计算性能,但由于IoT设备和云端间的数据传输时延严重,导致IoT设备的时延敏感工作流应用无法直接调度至云端执行.移动边缘计算[2,3](Mobile Edge Computing,MEC)作为一种不断发展的计算范式,能够提供一种更有效的方法,即在更接近数据创建点的位置处理数据,使得延迟敏感的工作流应用可以得到及时处理.考虑到云端虚拟机的强大存储、计算能力和边缘服务器的更靠近用户端的优势,云边协同计算模式作为一种融合云计算与边缘计算差异化优势的新型计算范式[4,5],将数据密集型任务调度至边缘,计算密集型任务调度至云端,云计算与边缘计算有机结合,为移动用户设备的各种请求提供不同的按需服务.然而,由于云边协同环境的资源异构性高,各个计算节点的计算能力、带宽、存储等均存在差异,同时每个工作流应用中任务之间存在复杂的数据依赖关系,如何在云边协同环境下合理高效地调度多工作流应用仍然存在重大挑战.

近年来,许多研究工作针对云计算或边缘计算环境下的工作流应用调度展开[6-8].工作流应用调度是一个NP难问题[9],通常考虑在单一平台(云计算或边缘计算)环境下,将工作流应用的依赖任务分别调度到不同的计算节点,满足工作流应用的服务质量(Quality of Service,QoS)要求.云边协同环境下的工作流应用调度,不仅需要满足工作流应用的高计算复杂度需求,而且能够有效降低数据传输时延[5].现有研究工作大多仅考虑单一工作流应用的调度问题,而忽略了多个工作流应用的调度,且在满足工作流应用截止时间约束前提下的调度代价优化方面仍有较大的可挖掘空间.如何在满足多个不同工作流应用时延约束前提下,考虑不同工作流应用的差异化生成时间,有效调度工作流应用的依赖任务至合适的云边计算节点上,降低多工作流应用的总体执行代价,仍是一项极具挑战的研究.

目前关于工作流应用调度的研究主要集中在确定性环境下,即计算节点的计算性能、传输带宽等计算环境因素相对稳定,不存在波动.然而,在云边协同环境中,由于不同服务器之间的负载不同、带宽波动、网络拥塞等原因和计算机自身特性,工作流任务的执行时间往往不能准确地预测[10],并且即使是相同的数据在固定的服务器之间传输时,其传输时间也会时常变化.因此,在实际的调度过程中,服务器的性能和服务器之间的带宽通常是波动的.调度环境的波动会对工作流应用调度产生不确定的影响,这是不可忽视的,在建立工作流调度模型时,需要考虑到这种不确定性.目前的不确定性环境下的调度研究主要针对模糊作业车间调度[11]和实时嵌入式系统的任务调度[12]等,较少关注模糊云边协同环境下工作流应用调度的研究.

在前期工作中,云边协同环境中基于DNN的应用程序的代价驱动卸载[13],以及基于DNN的智能物联网系统的节能卸载[14]得到解决,在工作流应用调度方面已积累相关经验,并在云边协同卸载方面也有一定工作基础.与本文工作相比,它们都处理某些云边协同环境中的工作流调度,而不是模糊云边协同环境.在本文研究中,进一步解决了降低任务计算和数据传输导致的多个工作流应用的执行代价,且满足相应的截止时间约束,同时考虑调度策略对于实际调度中不同规模工作流应用的决策实时性.三角模糊数[15]被用于来表示模糊环境下服务器的计算性能和传输带宽.特别地,提出一种基于局部关键路径的多工作流应用调度策略(Workflow applications Scheduling strategy based on Partial Critical Path,WSPCP),该策略基于工作流应用的数据依赖结构,采用预处理方法合并有向割边;同时在调度过程中,将局部关键路径的所有任务作为调度单元进行统一调度,很大程度上避免了任务之间的数据传输,从而减少数据传输代价,从而实现在满足每个工作流应用截止时间约束的前提下,尽可能地降低模糊执行代价.本文的主要贡献包括以下3个部分:

1)考虑到实际调度过程中服务器的负载压力、网络拥塞等计算环境因素造成计算性能和传输带宽的不稳定性,采用三角模糊数来表示模糊云边协同环境中服务器的计算性能和传输带宽.

2)针对泊松到达的多工作流应用,提出一种基于局部关键路径的多工作流应用调度策略(WSPCP),基于工作流应用自身结构,提出合并有向割边的预处理方法;同时,将局部关键路径作为调度单元进行统一调度,充分避免任务之间的数据传输,从而满足多工作流应用的时延约束,并降低其模糊执行代价.

3)通过仿真实验验证,与其他基准调度策略相比,在常用的工作流基准数据集上,WSPCP可以在满足多个工作流应用的截止时间的前提下获得更优的可行调度方案,有效降低了模糊执行代价.同时,对于不同规模的多工作流应用,WSPCP能够在平均秒级时间内得到可行的调度方案,具有较好的决策实时性,能够一定程度上应对实际调度中多个应用同时到达的极端情况.针对交通系统中的车辆识别应用,考虑工作流应用的任务规模、任务的计算复杂度、任务之间的数据传输量,进一步分析WSPCP对于实际应用的可行性.

本文的其余章节安排如下:第1节回顾相关工作,第2节给出多工作流应用调度模型的定义,并对模糊云边协同环境下的多工作流应用调度进行形式化表示;第3节详细描述本文所提出的WSPCP策略;第4节设计仿真实验环境,通过对比实验,分析WSPCP的性能效果,以及对于实际应用的可行性;最后,第5节概述本文的工作,并展望未来的研究方向.

1 相关工作

随着移动边缘计算的快速发展和云边协同模式的广泛应用,IoT设备对于在边缘节点运行复杂应用程序的需求越来越大[16].这些复杂的应用程序可以表示为任务之间存在数据依赖关系的工作流应用.在本节中,将简要回顾并分析云计算和边缘计算中的工作流应用调度以及模糊不确定性环境中任务调度的研究.

近年来,云计算环境中的工作流应用调度已经展开了许多研究工作[17-19].Meng等人[8]提出一种基于粒子群优化算法的安全感知调度方法,用于跨异构云的实时资源分配.实验结果表明,该策略能够在调度和安全性能之间取得良好的平衡.Paknejad等人[19]提出一种增强的多目标协同进化算法,用于云环境中的工作流调度.实验结果表明,该算法在代价、完工时间和能耗等性能指标上均优于同类算法.Qin等人[20]研究云工作流调度问题,在其执行时间保持在截止时间内的同时降低执行代价.基于云工作流调度问题的特定知识,提出一种新型的基于知识的自适应离散水波优化算法(Knowledge-based Adaptive Discrete Water Wave Optimization,KADWWO).实验结果表明,KADWWO算法的性能优于最先进的算法.然而,上述研究工作往往忽略了IoT设备向云端提交工作流应用的数据传输,虽然云计算为调度工作流应用提供了强大的计算性能,但由于IoT设备与云端之间的大量数据传输,可能会增加核心网络的流量负载并导致高延迟.

边缘计算技术能够有效降低工作流调度和计算卸载的系统时延,带来更好的用户体验[5,21,22].近年来,云边协同环境中任务调度和卸载问题已引起广泛研究.Xie等人[22]提出一种新的定向非局部收敛粒子群优化算法(Directional and Non-local-Convergent PSO,DNCPSO),利用非线性惯性权重,通过定向搜索过程进行变异和选择操作,同时降低云边环境下工作流的执行成本和完成时间.仿真实验表明,DNCPSO算法的性能优于其他经典算法和改进算法.Hazra等人[23]提出一种节能任务卸载策略(Energy-Efficient Task Offloading,EETO),通过联合卸载和调度光纤陀螺网络中的实时IoT应用,解决能源性能权衡问题.在不同QoS参数下的实验结果表明,EETO策略比现有策略具有更好的性能.Zhao等人[24]提出一种边缘环境下基于Q-learning算法的低负载分布式入侵检测系统任务调度策略,该策略根据网络变化动态调整调度策略,使得总体负载保持在较低水平,同时保持低负载和丢包率之间的平衡.实验结果表明,与其他经典方法相比,该策略具有更好的低负载性能,恶意特征检测率等指标没有显著降低.然而,现有的云边协同环境下工作流应用调度的研究很少考虑在满足截止时间约束的同时优化工作流应用任务计算和数据传输造成的执行代价.

在工作流应用的实际调度过程中,服务器的性能和它们之间的带宽通常会发生波动,这可能会对调度结果产生相当大的影响.现有工作解决了模糊环境中的调度问题,但此类工作主要面向其他领域.Sun等人[11]考虑模糊柔性作业车间调度问题,将不确定的加工时间表示为三角模糊数,提出一种有效的混合协同进化算法来最小化模糊最大完工时间.通过五个基准测试和三个处理时间模糊的大规模问题的测试,结果表明该算法的性能优于现有方法,表现出较好的收敛能力.Muhuri等人[12]提出一种新的解决模糊不确定环境下实时嵌入式系统节能任务调度问题的方法,称为“约束耦合节能遗传算法”.实验结果表明,该算法的性能优于现有的同类算法.Wu等人[25]针对具有不确定参数的物联网应用提出一种模糊逻辑卸载策略,以优化鲁棒性和一致性指数,其中三角模糊数与半梯形模糊数分别用于建模任务处理时间和数据传输时间.同时,设计一种多目标分布估计算法,用于各种应用中优化模糊卸载策略.实验结果表明,该算法在鲁棒性和一致性指标上均优于经典启发式算法.尽管相关研究领域已经取得了显著进展,但是在不确定性云边协同环境中多工作流应用的模糊调度仍然是一个极具价值的研究方向.

受到上述工作的启发,本文将提出一种启发式调度策略,用于解决在模糊云边协同环境中截止时间约束的多工作流应用的代价驱动调度.

2 系统模型

云边协同环境下的多工作流应用调度框架如图1所示,主要包括3个组成部分:带截止时间约束的多工作流应用、云边协同环境以及启发式调度器.

图1 云边协同环境下的多工作流应用调度框架Fig.1 Framework model of workflow scheduling in edge-cloud environment

2.1 多工作流应用模型

用户在不同时间通过IoT设备向云边协同环境提交工作流应用,本文假设工作流应用的到达满足一个强度为λ的泊松过程[26],因此工作流应用到达的时间间隔服从参数为λ的指数分布,其中,λ表示工作流的到达率.多工作流应用W由多个工作流应用{w1,w2,…,wn}组成,每个工作流应用wi可以表示为一个三元组wi=(αi,di,Gi),αi表示第i个工作流应用Wi到达的时间;di表示第i个工作流应用的截止时间,在某个调度方案中,若所有工作流应用都能在相应的截止时间前被执行完成,则称该调度方案是可行的;Gi表示第i个工作流应用的数据依赖结构.

此外,工作流应用可能包含两个及以上入任务或出任务,可以通过为其添加虚拟入任务vin或虚拟出任务vout,将其转化为仅含有一个入任务和出任务的工作流,具体操作为:设置虚拟入任务vin或虚拟出任务vout的计算量为0,并将原有的入任务和出任务分别与vin和vout通过虚拟数据边连接,同时将上述虚拟数据边的权值设置为0,即其传输数据量为0.值得注意的是,增加虚拟任务和虚拟数据边不会对多工作流应用调度的结果产生任何影响.

2.2 云边协同环境

在多工作流应用调度过程中,云边协同环境主要向用户提供计算服务和带宽服务,同时允许动态租赁.云边协同环境S={Scloud,Sedge}由云和边缘组成,具有不同的计算节点,即云的虚拟机和边缘的服务器.为了简化表述,统一使用“服务器”表示云和边缘中的计算节点.云Scloud={s1,s2,…,su}包含的u个服务器,边缘Sedge={su+1,su+2,…,su+v}包含v个服务器.服务器sk可以表示为:

(1)

根据服务器所属平台的类型,云边协同环境中的服务器sr和st之间的带宽βr,t可表示为:

(2)

2.3 多工作流应用调度方案

在云边协同环境中,启发式调度器的目标是给定一个调度方案,在每个工作流应用都满足截止时间约束的条件下,使得多工作流应用的执行代价最低.其根据调度方案中工作流应用任务和服务器之间的映射关系,为工作流应用任务分配相应的服务器.

因此,多工作流应用的调度方案可以被定义如下:

Γ=(W,S,M,ce,Tf)

(3)

(4)

(5)

2.3.1 确定性云边协同环境下的调度

在本次研究中,主要关注服务器的任务计算能力和服务器之间的数据传输能力,并假定在执行过程中有足够的容量存储传输数据.因此,本文侧重于考虑任务计算时间ttc和数据传输时间tdt,其计算方式具体如式(6)和式(7)所示:

(6)

(7)

(8)

(9)

(10)

(11)

其中,由于工作流调度过程中数据存储、资源监控等代价与上述代价相比可以忽略不计,从而只考虑任务计算代价和数据传输代价.

对于多工作流应用的一个调度方案,其目标是在所有工作流应用的完成时间均满足截止时间约束的同时,最小化其执行代价.因此,多工作流应用调度问题可形式化定义为:

(12)

2.3.2 不确定性云边协同环境下的调度

(13)

图2 三角模糊数的隶属函数Fig.2 Membership function of triangular fuzzy number

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

基于上述形式化定义(12),模糊云边协同环境下的多工作流应用调度方案的优化问题可形式化定义如式(22)所示:

(22)

(23)

(24)

(25)

(26)

综上所述,基于上述形式化定义(22),模糊云边协同环境下的多工作流应用调度问题可转化为式(27)所示:

(27)

3 基于局部关键路径的多工作流应用调度策略

本节首先介绍一些局部关键路径相关的基本变量定义,然后给出基于局部关键路径的多工作流应用调度策略(Workflow applications Scheduling strategy based on Partial Critical Path,WSPCP)的具体描述,用于在满足每个工作流应用的截止时间约束的情况下,尽可能减少多工作流应用的执行代价.

3.1 基本定义

在本文中,将工作流应用中已经分配到某个服务器的任务称为已调度任务,反之,则是未调度任务.在完成工作流应用wi的调度前,任务vi,j的最早完成时间(Earliest Finish Time,EFT)可定义如下:

(28)

根据任务vi,j的最早完成时间,定义vi,j的最早开始时间(Earliest Start Time,EST)如下:

(29)

另外,由于虚拟入任务的计算量为0,其在任何服务器上的执行时间均为0,因此虚拟入任务的最早完成时间和最早开始时间为工作流应用的到达时间,即:

EST(vin)=EFT(vin)=αi

(30)

在WSPCP中,为了确保工作流应用wi能够在截止时间di之前完成,定义任务vi,j的最迟开始时间(Latest Start Time,LST)如式(31)所示,任务vi,j必须在LST(vi,j)前完成调度并开始执行.

(31)

根据任务vi,j的最迟开始时间,定义vi,j的最迟完成时间(Latest Finish Time,LFT)如下:

(32)

同样地,由于虚拟出任务的计算量为0,其在任何服务器上的执行时间均为0,因此虚拟出任务的最早完成时间和最早开始时间为工作流应用的到达时间,即:

LST(vout)=LFT(vout)=di

(33)

在WSPCP中,局部关键路径(Partial Critical Path,PCP)是其最核心的思想之一.在传统的调度策略中,往往以工作流应用的单个任务作为调度单元进行调度;与之不同的是,WSPCP将同一局部关键路径上的所有任务作为调度单元进行统一调度,从而有效压缩依赖任务之间的数据传输量,减少数据传输代价.对于任务vi,j,其局部关键路径定义如下:

(34)

其中,path(PCP(v),v)表示一条局部关键路径,在任务v之前连接任务v的局部关键路径PCP(v);CP(vi,j)表示vi,j的关键父任务(Critical Parent,CP),在任务vi,j的所有直接未调度父任务中,关键父任务到任务vi,j的数据最迟传输到达,具体定义如下:

(35)

根据上述定义可知,在PCP(vi,j)上的任何一个任务,数据传输到达其后继任务的时间总是最迟的.

3.2 WSPCP

对于泊松到达的多工作流应用,WSPCP实时监测每个工作流应用wi的到达,进行工作流应用的任务调度,在满足所有工作流应用的截止时间约束的前提下,尽可能减少执行代价.在调度过程中,WSPCP通过为局部关键路径分配局部截止时间,即最迟完成时间,并对整个局部关键路径进行统一调度,而不会对单一任务进行调度,这样大大压缩局部关键路径上任务之间的数据传输量,减少数据执行代价,具体过程如算法1所示.

算法1.WSPCP

procedureWorkflow_Applications_Scheduling(W,S)

Input:W,S

1.Initialization:M←null;

2.whileany ofWhas not arriveddo

3. ifwiarrivesthen

4. //每次生成1个新的线程,用于处理新到达的wi

5. #pragmaompparallelnum_threads(1){

6. //调用算法2,对wi进行预处理

7. Workflow_Application_Preprocessing(wi);

9.forj=1toj=|Vi|do

10. 初始化任务vi,j为未调度任务;

11. 计算EFT(vi,j),EST(vi,j),LST(vi,j),LFT(vi,j)

12.endfor

13.tstart(vin)=tend(vin)=αi,tstart(vout)=tend(vout)=di;

14. 标记虚拟入任务vin和虚拟出任务vout为已调度任务;

15. //调用算法3,基于局部关键路径思想,调度所有任务

16. Scheduling_All_Parents(M,vout);

17. }

18.else

19. //Waiting for a workflow application arriving;

20.continue;

21.endif

22.endwhile

endprocedure

该算法描述了WSPCP的整体过程,对于泊松到达的工作流应用wi,主要包括3个部分:1)调用算法2,对wi进行预处理,基于wi的结构特征,合并存在有向割边的相邻任务,从而减少算法的时间复杂度;2)计算WSPCP过程中需要用到的相关变量,并标记虚拟入任务vin和虚拟出任务vout为已调度任务;3)调用算法3,以虚拟出任务vout作为输入,基于关键父任务迭代机制,寻找带局部截止日期的局部关键路径,并为局部关键路径分配相应的最适合服务器,并执行所有任务.

3.2.1 工作流应用的预处理过程

由于多工作流应用调度的任务规模较大,通过合并有向割边可以有效减少任务规模,从而降低算法执行时间.有向割边的定义为:对于一条有向边,其出节点的出度为1,且入节点的入度为1,则称作有向割边.如图3所示的工作流应用中,一共存在7条有向割边,其中相同图案的任务和有向边(虚线箭头)组成的结构即为有向割边.

图3 工作流应用中的有向割边Fig.3 Directed cut-edge in workflow application

在工作流应用的预处理过程中,算法2根据当前工作流应用wi的数据依赖结构特征,将存在有向割边的相邻任务进行合并,得到新任务的计算量为相邻任务之和.对于存在大量有向割边的工作流应用,如Epigenomics和LIGO[28]等,预处理过程能够大幅度减少其任务规模,降低WSPCP的执行时间.

算法2.工作流应用预处理

procedureWorkflow_Application_Preprocessing(wi)

Input:wi

1.记录wi每个任务的入度和出度

2.do{

4.if出节点vi,p的出度为1and入节点vi,q的入度为1then

6. 合并出任务vi,p和入任务vi,q,并更新任务计算量;

7.endif

8.endfor

9.}whilewi存在有向割边;

endprocedure

3.2.2 调度未调度任务

在算法1中,WSPCP调用算法3,以虚拟出任务vout作为输入,调度工作流应用wi的所有未调度任务.

算法3.调度任务vi,j的所有未调度父任务

procedureScheduling_All_Parents(M,vi,j)

Input:M,vi,j

1.whilevi,j存在直接未调度父任务do

2.Initialization:v←vi,j,stack←null,PCP(vi,j)←null;

3.whilev存在直接未调度父任务then

4.stack.push(CP(v));

5.v=CP(v);

6.endwhile

7.whilestackis not emptydo

8.PCP(vi,j).append(stack.pop());

9.endwhile

10. //调用算法4,调度任务vi,j的局部关键路径

11. Scheduling_Path(M,PCP(vi,j));

12.foreachvi,p∈PCP(vi,j)do

13. 更新vi,p所有未调度后继任务的EFT和EST;

14. 更新vi,p所有未调度前驱任务的LST和LFT;

15. Scheduling_All_Parents(M,vi,p)

16.endfor

17.endwhile

endprocedure

3.2.3 调度局部关键路径

在算法3中,Scheduling_All_Parents过程调用算法4,将任务vi,j的局部关键路径统一调度到云边协同环境中的最适合服务器上.

算法4.调度局部关键路径

procedureScheduling_Path(M,PCP)

Input:M,PCP

1.foreachsk∈Sdo

2. 寻找执行PCP的最适合服务器sk;

3.endfor

4.ifsk不存在then

5. 在满足PCP的局部截止时间约束完成所有任务的条件下,租赁并初始化一个单位计算代价最小的服务器sk,即最适合服务器;

6.endif

7.将PCP调度到最适合服务器sk上;

8.foreachvi,p∈PCPdo

9.M=M∪(vi,p,sk);

11. 设置任务vi,p为已调度任务;

12.endfor

endprocedure

该算法描述了局部关键路径PCP的调度过程,利用贪心策略寻找执行PCP的最适合服务器.对于局部关键路径PCP,对应的最合适服务器定义如下:云边协同环境中的某个服务器sk,能够在PCP对应的局部截止时间内完成PCP上的所有任务,且同时满足以下3个条件:

(36)

其中,t1和t2分别表示在执行PCP前后服务器sk的实际执行时间,「t1⎤表示根据要价单元时间uk的向上整合时间.特别地,若服务器sk刚启动,则t1=0.

2)如果存在多个最低执行增长代价相等的服务器,则选择实际执行时间最长的服务器sk.

(37)

如果不存在可用的最适合服务器,则租赁并初始化一个单位计算代价最小的服务器sk,同时能够在满足PCP局部截止时间约束的条件下完成所有任务.最后,将PCP调度到最适合服务器sk上,同时将所有任务设置为已调度任务.

4 仿真实验与分析

4.1 实验设置

所有实验都在16 GB RAM和3.00GHz Intel i5-9500F CPU的Win 10系统下运行,WSPCP和所有对比调度策略均在Python 3.8环境下实现.

用户每次提交的工作流应用均来自于Bharathi等[28]所提出的5种小型工作流应用模型:地震科学CyberShake、生物基因学Epigenomics、重力物理学LIGO、天文学Montage和生物信息学SIPHT.每种工作流应用含有约30个任务,具有不同的依赖结构,其计算需求和数据集大小等相关信息均被存储在xml文件中.在本次实验中,设置多工作流应用的规模为20个.假定工作流应用的到达是一个强度为λ的泊松过程,工作流应用到达的时间间隔服从参数为λ的指数分布,用户平均每隔2.5s向云边协同环境提交工作流应用,则工作流的平均间隔时间为1/λ=2.5,即λ取0.4.因此,对于工作流应用wi,定义其到达时间αi如式(38)所示:

(38)

其中,randexp(λ)用于产生参数为λ的指数分布随机数.

另外,每个工作流应用都有对应的截止时间约束,并以此来测试调度策略的有效性.对于工作流应用wi,定义其截止时间di如式(39)所示:

di=αi+bl*|W|*HEFT(wi),bl={2.0,2.5,3.0,3.5}

(39)

其中,HEFT(wi)表示用HEFT算法[29]调度工作流应用wi所需的执行时间.参数bl表示截止时间因子.

在模糊云边协同环境中,假定初始时刻存在5个云服务器(s1,s2,…,s5)和5个边缘服务器(s6,s7,…,s10).每个服务器具有特定的任务计算能力和单位计算代价.假定云服务器s1,s2,…,s5的计算能力分别为2.5,3.5,5.0,7.5,10.0GHz,边缘服务器s6,s7,…,s10的计算能力约2.5GHz,分别为2.5,2.6,2.2,2.3,2.7GHz;假定计算能力最强的云服务器s5的单位计算代价为12.5 $/h或(5/24 $/min),以云服务器s5的单位时间计算代价为基准,其余服务器的单位计算代价近似与其计算能力成正比.在工作流应用调度中,可以根据需要动态租赁并初始化具有上述性能的服务器.

目前主流的商业云服务,如Amazon EC2,通常按1分钟或1小时为要价单元时间μi进行付费.在本次实验中,用户提交的工作流应用均为小型规模,选择以1分钟为单位进行付费.

两个服务器si和sj之间的带宽和单位数据传输代价,根据二者所属环境fi和fj的不同,如表1进行设置.

表1 不同服务器si和sj之间的带宽Table 1 Bandwidths between different servers

第2.3.2节详细阐述了如何将计算性能pk和带宽br,t模糊化为对应的三角模糊数,参数δ1和δ2分别取为0.75和1.2.为了比较实验结果的好坏,第2.3.2节同时给出了模糊云边协同环境下的多工作流应用模糊执行代价和模糊完成时间的去模糊化方法,参数ϖ取为1;另外,基于时效性的考虑,设置参数η的值为0.95.

4.2 基准策略

WSPCP是一种启发式调度策略,为了验证该策略对于降低多工作流应用模糊执行代价的有效性,在本次实验中,将以下3个调度策略作为基准策略,用于比较WSPCP和其他基准策略的调度性能.

1)WSGS(Workflow applications Scheduling based on Greedy Strategy):该策略采用与WSPCP相同的预处理方法,在调度过程中,对于泊松到达的每个工作流应用,采用最早完成时间优先[29]的策略为每个任务选择执行的服务器.当现有服务器无法满足截止时间约束时,允许在云边协同环境中租赁并初始化新的服务器.

2)WSPG(Workflow applications Scheduling strategy based on Particle swarm optimization employing Genetic operators):该策略采用服务器和优先级嵌套的编码策略,服务器编码采用离散值表示执行任务的服务器编号,优先级编码采用连续值表示同一时刻服务器中待执行任务的优先级大小;采用PSO-GA更新策略[14]对粒子编码进行更新以寻找较优的调度方案,参数w,c1,c2根据文献[14]进行设置,种群规模和迭代次数分别设置为100和1000.

3)WSRS(Workflow applications Scheduling based on Random Searching):该策略采用与WSPG相同的优先级和服务器嵌套的编码策略,使用随机搜索策略生成新的种群,在相应的定义域内随机生成每个粒子的优先级和服务器编码,并将粒子映射到对应的调度方案,记录随机搜索过程中的最优解,每次迭代之间互不影响,最终输出种群的最优解,即最优调度方案,其中,种群规模和迭代次数分别设置为100和1000.

4.3 实验结果与分析

4.3.1 不同截止时间约束下的调度性能

为了比较WSPCP和其他基准策略在模糊云边协同环境中多工作流应用的调度性能,在不同的截止时间约束下,对多工作流应用调度进行4组仿真实验,包括严格(bl=2.0)、 中等(bl=2.5)、微小(bl=3.0)和宽松(bl=3.5)4种截止时间约束,并分析WSPCP在降低多工作流应用模糊执行代价方面的优越性.对于每种截止时间约束,记录10次独立重复实验中的最优和平均模糊执行代价及其适应度(单位:10-3$).表2展示了在不同调度策略下多工作流应用的最优模糊执行代价,其中,最优解用粗体表示,不可行解用符号“*”标记.

表2 不同调度策略下多工作流应用的最优模糊执行代价Table 2 Optimal fuzzy execution cost of workflow applications based on different scheduling strategies

从优化目标来看,本文所提出的调度策略WSPCP在4种截止时间约束下都得到了最优的调度方案,即多工作流应用的模糊执行代价最小,而WSPG的性能次之.WSPCP采用预处理方法合并有向割边,降低了问题的任务规模;同时将局部关键路径的所有任务作为调度单元进行调度,很大程度上避免了任务之间的数据传输,从而减少数据传输代价,最终得到最优的调度方案.而WSPG作为一个全局搜索策略,由于受到解空间规模的限制,难以在有限的迭代次数内得到更优的调度方案,但仍然优于传统的贪心策略,即WSGS.值得注意的是,WSRS在指数级的解空间中进行无差别的随机搜索,仅在宽松的截止时间约束下可以得到可行的调度方案,对于多工作流调度这一约束优化问题而言,WSRS是无法接受的.

从截止时间约束来看,WSPCP和WSGS在任何情况下都能得到满足约束的可行调度方案.在严格(bl=2.0)的截止时间约束下,WSPG和WSRS是无效的,无法得到可行的调度方案.随着截止时间约束的放宽(bl≥2.5),多工作流应用的模糊执行代价呈降低趋势,且WSPG能够得到可行的调度方案.然而,仅在宽松(bl=3.5)的截止时间约束下,WSRS能够得到可行解.这是因为多工作流应用调度是一个组合优化问题,具有大量的局部极值点,是不连续的、高度非线性的NP难问题.在严格的截止时间约束下,作为全局搜索策略,对于指数级规模的解空间,WSPG在有限的迭代次数内无法得到更优的调度方案,即使它能够对解空间进行有方向、有目标地探索;而WSRS所采用的随机搜索策略效率较低,在解空间内进行无差别地探索,难以搜索到高质量的、可行的调度方案.

此外,对于每种截止时间约束下的10次独立重复实验,图4展示了在不同调度策略下多工作流应用的平均模糊执行代价.从图4中可以看出,在4种截止时间约束下,WSPCP所产生的调度方案下的多工作流应用的平均模糊执行代价均优于其他基准策略.特别地,在严格(bl=2.0)的截止时间约束下,相较于其他基准策略,WSPCP对于多工作流应用平均模糊执行代价的降低约为7.5%～70.0%.由此可见,WCPCP在不同截至时间约束下的鲁棒性更强.

图4 不同调度策略下多工作流应用的平均模糊执行代价Fig.4 Average fuzzy execution cost of workflow applications based on different scheduling strategies

综上所述,相较于其他基准策略,WSPCP将局部关键路径上所有任务作为调度单元进行统一调度,很大程度上避免了任务之间的数据传输,减少数据传输的时间和代价,从而总是能够得到更优的可行调度方案.特别地,在严格的截止时间约束下,WSPCP仍然可以得到满足截止时间约束的可行调度方案,同时降低多工作流应用的模糊执行代价,表现出更优的性能.

4.3.2 实际应用中的决策实时性与调度分析

在实际应用中,往往还需要考虑多工作流应用的平均到达率和应用规模等.在极端情况下,多个工作流应用在同一时刻被提交至云边协同环境中执行,这种情形则考虑调度策略的决策实时性.为了比较WSPCP和其他基准策略在模糊云边协同环境中的决策时间,在中等(bl=2.5)的截止时间约束下,对4种不同规模的多工作流应用调度进行实验,包括20、30、50和100,并分析WSPCP的调度决策实时性.对于不同规模的多工作流应用调度,记录10次独立重复实验的总决策时间(单位:s).图5展示了在不同工作流应用规模下不同调度策略的总决策时间,为了方便对比,图5的纵坐标采用底数为4的对数刻度,将总决策时间控制在合理的区间范围内.值得注意的是,当工作流应用的规模为100时,WSPG和WSRS的总决策时间将超过64800s(即18 hour),这是无法接受的决策时间,因此在图5中不展示二者的实际决策时间,仅以填充图案为横线的柱状表示.

图5 不同工作流应用规模下不同调度策略的总决策时间Fig.5 Total decision time of different scheduling strategies under different workflow application scales

由图5可以看出,与全局调度策略WSPG和WSRS相比,两个启发式调度策略WSPCP和WSGS在决策时间上具有绝对的优势,二者的单次决策时间仅1s不到,能够做到接近实时调度.这是因为WSPCP和WSGS基于有向割边的预处理机制,降低工作流应用的任务规模,同时采用启发式方法,基于某种寻优策略,能够快速得到较优的可行调度方案;而WSPG和WSRS则需要在全局解空间中不断迭代搜索,由于多工作流应用调度的解空间随着工作流应用的规模指数级增长,因此需要花费更多的决策时间,此类调度策略更适合静态调度的情形.相对于WSGS,WSPCP所需的决策时间更久,这是因为对于每个到达的工作流应用,WSPCP需要寻找工作流应用的局部关键路径,从而将其统一调度到服务器上,以减少任务之间的数据传输.从4.3.1节的结论来看,同样是秒级的决策时间,较少的时间差能够得到更优的工作流应用调度方案,这是值得的.

另外,工作流应用的实际情况,包括其任务规模、任务的计算复杂度、任务之间的数据传输量等因素,也是实际调度过程中可能遇到的挑战.特别地,作为交通系统中的工作流应用之一,车辆识别应用的核心技术是DNN,而工作流应用调度决策是影响车辆识别应用中DNN性能的关键问题之一[1].处理能力有限的交通摄像头会定期记录道路车辆的图像,但是通常无法在其截止时间内完成应用,因此往往需要将此类应用提交到云边协同环境进行处理.在不确定性云边协同环境中,计算环境的不确定性因素对此类问题的系统延迟影响很大,容易导致对最优调度方案的误判,很难从众多方案中选择最佳的服务器解决方案.本文所提出的调度策略WSPCP能够为车辆识别应用做出高效的工作流应用调度决策,同时可以降低主要由层内计算和层间数据传输在截止时间内引起的执行代价.具体而言,WSPCP可以将车辆识别应用中的复杂DNN层(任务)可以调度到云端执行,而简单的DNN层(任务)则在边缘进行处理,云和边缘平台之间相互协作,以较低的执行代价和系统延迟执行DNN层;将局部关键路径作为整体统一调度到同一服务器上执行,从而一定程度上避免DNN层(任务)之间的数据传输,有效减低数据传输产生的代价和时延.

5 结束语

针对模糊云边协同环境下多工作流应用调度,本文将服务器的计算性能和服务器之间的带宽表示三角模糊数,以体现云边协同环境中的不确定性对多工作流应用调度的影响.同时,针对泊松到达的多工作流应用,提出一种基于局部关键路径的多工作流应用调度策略WSPCP,用于优化截止时间约束下多工作流应用的模糊执行代价.实验结果表明,与其他基准策略相比,所提出的策略在多工作流应用调度方面表现出良好的性能,在不同的截止时间约束下,WSPCP都能获得多工作流应用最优的可行调度方案,同时实现了模糊执行代价的有效优化.在实际应用中,对于不同规模的多工作流应用,WSPCP展现了良好的决策实时性.同时,针对工作流应用的实际情况,包括工作流应用的任务规模、任务的计算复杂度、任务之间的数据传输量等因素,WSPCP具有一定的可行性.

在未来的工作中,希望建立一个适用于现实世界中多工作流应用的实时调度系统,整合云边协同环境中的计算资源,考虑工作流应用任务规模庞大、多个应用同一时刻到达、工作流应用执行出错等实际应用的各类极端情况,对IoT设备提交的工作流应用进行高效地调度.同时,根据当前云边协同环境中服务器的实时负载情况和租赁成本,动态调整服务器的开启和关闭,进一步优化多工作流应用的执行代价.