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

Fault-tolerant scheduling algorithm for service workflow in MEC environment

作　　者：袁友伟[1,2] 黄锡恺 俞东进 李忠金[1] YUAN Youwei;HUANG Xikai;YU Dongjin;LI Zhongjin(School of Computer Science and Technology, Hangzhou Dianzi University,Hangzhou 310018, China;Key Laboratory of Complex Systems Modeling and Simulation,Ministry of Education,Hangzhou 310018,China)

机构地区：[1]杭州电子科技大学计算机学院,浙江杭州310018 [2]复杂系统建模与仿真教育部重点实验室,浙江杭州310018

出　　处：《计算机集成制造系统》2021年第6期1693-1702,共10页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(61702144,61802095);浙江省自然科学基金资助项目(LY17E050027)。

摘　　要：针对移动边缘计算环境下服务工作流延时优化问题以及工作流任务执行失败的情况,提出一种适用于服务工作流的容错免疫粒子群优化调度算法(FT-IPSO)。该算法首先采用异构最早完成时间算法计算已分层任务的权重并生成就绪队列;其次,结合服务工作流调度流程加入了混合容错策略,确保工作流在任务失败后能够继续执行;然后,采用粒子群算法快速寻找最优调度方案,编码时利用整数映射调度过程中主副版本任务调度位置,并融入免疫算法,保证粒子寻优的全局性;最后,根据算法得出的最优调度方案对任务进行调度。仿真实验结果表明,FT-IPSO算法有效降低了服务任务失败率,并且对服务工作流的延时优化效果较反应式容错算法、基于聚类启发式算法的检查点和复制算法,以及基于群集的异构最早完成时间算法分别提高了约4.1%、6.3%和9.1%。To address the problem of service workflow delay optimization and workflow task execution failure in Mobile Edge Computing(MEC)environment,a Fault Tolerant Immune Particle Swarm Optimization Scheduling Algorithm(FT-IPSO)for service workflow was proposed.The Heterogeneous Earliest Finish Time(HEFT)algorithm was used to calculate the weight of task and generate the ready queue.The mixed fault-tolerant strategy was added to the service workflow scheduling process to ensure the workflow continue to execute after the task fails.The particle swarm optimization algorithm was used to quickly find the optimal scheduling scheme and incorporates an immune algorithm to ensure the global optimization of the particle.To map out the scheduling position of the prime and backup version of task,the encoding scheme had been redesigned using integer.The task was scheduled according to the optimal scheduling scheme obtained by the algorithm.The simulation result showed that FT-IPSO algorithm reduced the service task failure rate and optimizes the service delay about 4.1%,6.3%and 9.1%compared with the RFTA,CRCH and C-HEFT algorithms respectively.

关 键 词：移动边缘计算 延时优化 容错策略 免疫算法 粒子群算法 服务工作流 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]