[0044] 以下将结合附图对本发明提供的技术方案作进一步说明。
[0045] 参见图1，所示为本发明一种边缘计算环境下针对可靠性的工作流容错调度方法的流程图，具体步骤如下：
[0046] 步骤S1：定义移动边缘环境下的工作流和基站。本发明研究的是移动边缘环境下工作流的调度，需对工作流和基站进行定义。本发明采用有向无环图DAG表示用户提交到移动边缘环境的服务工作流，DAG由W＝(T,E)表示，W代表工作流，其中由R个任务T＝{t1,t2...tR}组成，任务之间存在以下依赖关系：
[0047] E＝{(ti,tj,Dij)|(ti,tj)∈T×T,i≠j}
[0048] 其中Dij表示任务ti和任务tj的数据传输成本，任务ti的前驱任务集合和后继任务集合分别用pred(ti)及succ(ti)来表示，所有的任务需等到其前驱任务集合全部执行完毕并完成成本数据传输才可以执行。假设移动边缘计算系统M由一组给定的基站组成，M＝{eNB1,eNB2...eNBn}，eNB代表基站，每个基站对外提供一定程度的工作流执行可靠性，可用γ＝{γ1,γ2…γn}表示。基站之间通过网络互相连接，连接基站eNBi和eNBj之间的带宽为BWij。
[0049] 步骤S2：建立可靠性模型。用户在提交工作流W时，通常采用可靠性需求(Reliability Demand,RD)描述不同计算密集型的任务，具体地由RD＝{RD1,RD2...RDR}组成，RDi表示任务ti的可靠性需求系数。任务模型的失败概率通常采用指数分布表示，负指数失败对于流程任务ti的可靠性可理解为执行时间内任务失效的概率，即移动设备无法完成所调度工作流任务的概率。移动设备的失败计算服从暂态故障变量，故障变量服从泊松分布，因此基站站点l下执行任务的可靠性如下：
[0050]
[0051] 其中γl表示任务调度基站的对外可靠性服务系数，λ表示移动边缘环境的故障系数。
[0052] 步骤S3：建立延迟执行模型。当边缘计算资源的某个计算资源节点出现失效时，分配在此资源节点上的所有任务都无法执行。本发明的解决方法是中止任务调度并重新分配资源。工作流中在基站站点l任务的延迟执行时间概率模型如下所示：
[0053]
[0054] 其中参数μ表示由临时资源故障导致的延迟时间系数；
[0055] 步骤S4：建立执行时间模型。假设所有的工作流调度采用批处理的调度方式，同时任务间的调度相互独立，且满足失败-停止策略，即流程任务一旦出现执行失败的情况，相应的任务将会被重新调度到其他的基站上执行。工作流的主要调度目标在于减少其执行时间，较快地得到工作流的执行结果，其执行时间模型定义如下，TFT(ti)代表任务ti的结束时间：
[0056]
[0057] 步骤S5：建立容错机制。图2为移动边缘环境下基于复制策略的工作流调度系统，该调度系统包含了工作流分析器、资源管理器、主版本任务控制器及复制版本控制器四大模块，用户提交的工作流进入工作流调度队列，顺序进入工作流系统执行，工作流系统高效监控流程任务的执行状态并根据实际的运行情况做出相应的资源调整。针对计算资源的故障问题，采用任务复制策略，通过将某个即将执行的流程任务进行多个版本的复制，在任务分配至计算资源的执行过程中，实时的监控任务的执行状态及计算资源的运行状态，一旦发生计算资源失效，复制版本控制器将执行失败任务的复制版本二次调度至有效的基站节点上执行，进而实现资源的容错，更好地改善系统的性能和调度能力，保证了复杂工作流的可靠运行。
[0058] 步骤S6：初始化各参数。种群中的个体都使用染色体进行编码，用以表示调度问题的一组可行解。染色体用一个向量组Ψ＝(Λ，Γ，Δ)来表示，向量Λ表示满足顺序约束的工作流任务的编码序列，Γ为移动边缘环境下的基站资源节点编码，显然向量Λ和Γ的长度均为待执行工作流的总体任务数|W|。Δ表示预先设定的染色体模版，根据遗传算法的迭代次数不断上升，染色体通过一系列操作产生最新的调度方案。初始化时随机产生N个染色体，从而生成初始的生物种群POPULATION，并从POPULATION中确定当前最优调度方案Δ，以及设定算法中的最大迭代次数GENERATION_MAXIMUM。
[0059] 步骤S7：计算调度方案的适应度值。图3显示了任务调度过程的某一个运行快照，基于任务复制策略，某一任务ti调度至某个基站等待执行，其中令Pfail(eNBi)表示为站点i的执行失败率，则站点1,2,3的执行失败率分别可表示为Pfail(eNB1)＝0.4，Pfail(eNB2)＝0.1，Pfail(eNB3)＝0.3，任务ti在三个基站节点的开始执行时间分别为st1,st2,st3，若任务成功执行，则其执行结束时间分别为ft1,ft2,ft3。若任务成功执行，则其他基站的复制任务停止执行。即任务ti1在基站eNB1上成功执行，复制任务ti2将不会执行，复制任务ti3将在ft1处停止执行，因此在时间ft1后任务继续执行的概率为Pcont(ti2)＝Pfail(eNB1)。故在移动边缘环境下，假设有n个基站站点，针对某一指定的站点l，在站点l的执行结束时间ftl之后任务继续执行的概率如下：
[0060]
[0061] 位于基站站点l的执行时间El(ti)如下所示：
[0062]
[0063]
[0064] 将计算得到的工作流执行时间作为适应度函数的值，评价工作流调度方案的优劣程度。
[0065] 步骤S8：更新调度方案。本发明是基于遗传算法的进化算法，需要进行迭代，不断更新现有的调度方案。其包括调度方案双亲选择、染色体切除操作、染色体拼接操作和染色体变异操作，具体步骤如下：
[0066] 步骤S81：调度方案双亲选择。通过步骤S7中获得的各个调度方案的适应度值，根据适应度值计算每个调度方案被选中的概率，调度方案i被选择的概率等于调度方案i的适应度除以所有调度方案的适应度之和，适应度值越大则被选中的概率越大，具体的选择操作使用轮盘赌选择算法实现，确保每种调度方案都有概率被选中。
[0067] 步骤S82：双亲染色体切除。通过步骤S81中获得的双亲染色体，随机选取染色体编码向量的切除点，例如可将编码向量(3，2，6，5，7，1，4)和编码向量(5，6，2，7，3，2，2)的切除点设置为第三位，即对应的两个向量值为6和2。
[0068] 步骤S83：双亲染色体拼接。通过步骤S82中获得的双亲染色体的切除点，将双亲染色体的编码向量进行拼接，如编码向量(3，2，6，5，7，1，4)和编码向量(5，6，2，7，3，2，2)的切除点为第三位，则拼接成的染色体编码向量为(3，2，6，7，3，2，2)，从而生成新的染色体。
[0069] 步骤S84：染色体变异。通过步骤S83中获得的染色体，将该染色体上的编码向量对个体编码串随机指定的某一位或某几位基因作变异运算，最终生成新的调度方案。例如编码向量(3，2，6，7，3，2，2)变异为(3，2，5，7，3，1，2)。
[0070] 步骤S9：判断是否达到结束条件。若方案迭代次数达到原先设定的最大迭代次数，则推出循环，输出最优调度方案最优调度方案best_Scheduling_Scheme及其适应度值，否则ITERATOR＝ITERATOR+1，返回步骤S7进入下一个循环，继续进行迭代更新。
[0071] 以下对本发明的性能进行仿真评估，并分别与基于重调度IRW和基于复制的工作流容错调度算法CCRH进行任务失败率、任务执行成功率及任务平均延迟时间方面的对比。
[0072] 本发明的实验是在WorkflowSim仿真平台实现的，具体的实验环境为：操作系统是Windows 10专业版64位，处理器是Intel酷睿i5-4590，内存大小是8GB，JDK版本是1.8.0_131，集成开发环境是Eclipse Neon.3Release(4.6.3)。
[0073] 其中工作流任务失败率(Task failure rate,TFR)：当提交工作流的可靠性RD小于资源节点的可靠系数γi，则可能导致任务执行失败,Nfail表示由于任务执行失败进行再次调度的任务数目。N表示工作流的任务数。因此失败率定义如下：
[0074]
[0075] 工作流任务成功率(Task success rate,TSR)定义如下：
[0076]
[0077] 工作流的执行时间降速比(Slowdown ratio,SLR)：假设任务开始时间为sti，到达时间为ari,完成时间为fti，则平均等待时间为 因此降速比SLR定义如下：
[0078]
[0079] 实验采用DAG生成器产生的工作流作为实验样例，关于具体实验的工作流样例参数设置如表1所示。实验中假设移动设备资源节点的可靠性系数服从[0.3,1.0]均匀分布，工作流的任务可靠性服从[0.6,0.9]的均匀分布。
[0080] 表1随机工作流生成器得到的工作流样例
[0081]
[0082] 图4展示了不同的工作流样例上任务失败率TFR的比较。任务失败率是衡量工作流容错调度算法是否能够根据资源失效引发的任务失效，任务失败率的比较是衡量算法是否能够根据资源失效导致的任务失败做出有效调整的重要指标。通过图4中对比发现，与传统算法CCRH、IRW相比，本发明的工作流调度方案具有更低的任务失败率，平均降低了15.6％、21.8％。随着工作流的任务数量不断增加，相应的调度算法的执行失败率也在不断的上升。
从实验结果得出，本发明与CCRH、IRW算法相比，产生的调度方案更加的稳定，任务数量较大的情况下，仍能保持较好的容错调度性能。
[0083] 图5是不同测试的工作流样例上任务的执行时间降速比SLR比较。实际工作流调度过程中，前驱任务的失败必然会引起任务的二次调度，二次调度的发生会产生一定的后继任务的执行时间延迟。SLR的比较是检测容错调度算法是否能够有效容错的另一个重要指标。通过图5的对比可以得到在所有的测试工作流样例上本发明拥有较低的任务延迟时间。随着工作流样例的任务数量不断增加，与CCRH、IRW算法相比，本发明的任务延迟时间优化效果更加明显。这是由于本发明在进行实际工作流的容错调度考虑了时间期限对调度性能的影响，可以有效的根据资源失效引发的任务失败，对任务的复制版本进行重新调度，保证了工作流任务的执行时间。
[0084] 为了进一步的探究任务平均延迟时间与任务成功率TSR的关系，我们针对某一特定的工作流样例，通过改变任务的失败率，观测其平均延迟时间的变化。如图6所示，随着任务成功率的不断降低，任务的平均延迟时间不断的上升。当任务的平均延迟时间增大到一定程度，任务的成功率也趋于0，这说明相对于CCRH、IRW算法，在相同的任务平均延迟时间下，本发明具有更好的容错调度性能，随着任务平均时间的增加，本发明算法具有更高的任务执行成功率，并且其随平均延迟时间的变化也更加稳定。
[0085] 为了探究工作流平均延迟时间与任务数量的关系，首先通过工作流生成器产生了四组工作流样例，其相应的任务数量分别为5，10，15，20。然后针对特定工作流任务失败率下，探究了四组工作流样例调度执行的任务延迟时间。图7展示了任务失败率为0.1至0.7下，不同的工作流DAG数量与平均延迟时间的关系。分析图7不难发现，任务的失败率越低，其工作流执行的延迟时间越低。当工作流的任务数量不断增加，相同的任务失败率下，其任务延迟时间也逐渐增加，且任务失败率越高，任务延迟时间增加更明显。
[0086] 实验结果表明本发明所提出的一种边缘计算环境下针对可靠性的工作流容错调度方法生成的调度方案相对于CCRH、IRW算法生成的调度方案具有更低的任务失败率，且本发明的容错策略具有较少的任务延迟时间。本发明结合任务的复制策略，可在资源失效情况下，做出准确的任务二次调度调整，在任务数量较大的情况下仍能保持较好的容错调度性能。
[0087] 以上实施例的说明只是用于帮助理解本发明的方法及其核心思想。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以对本发明进行若干改进和修饰，这些改进和修饰也落入本发明权利要求的保护范围内。
[0088] 对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。
