Abstract: 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.

Key words: mobile edge computing, delay optimization, fault-tolerant strategy, immune algorithm, particle swarm optimization algorithm, service workflow

摘要： 针对移动边缘计算环境下服务工作流延时优化问题以及工作流任务执行失败的情况,提出一种适用于服务工作流的容错免疫粒子群优化调度算法(FT-IPSO)。该算法首先采用异构最早完成时间算法计算已分层任务的权重并生成就绪队列;其次,结合服务工作流调度流程加入了混合容错策略,确保工作流在任务失败后能够继续执行;然后,采用粒子群算法快速寻找最优调度方案,编码时利用整数映射调度过程中主副版本任务调度位置,并融入免疫算法,保证粒子寻优的全局性;最后,根据算法得出的最优调度方案对任务进行调度。仿真实验结果表明,FT-IPSO算法有效降低了服务任务失败率,并且对服务工作流的延时优化效果较反应式容错算法、基于聚类启发式算法的检查点和复制算法,以及基于群集的异构最早完成时间算法分别提高了约4.1%、6.3%和9.1%。

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