基于偏好和虚拟适应度的两阶段依赖任务卸载算法  

Two-Stage Dependent Task Offloading AlgorithmBased on Preference and Virtual Fitness

作　　者：董立岩[1,2] 齐竞则 刘元宁[1,2] 冯嘉辉 DONG Liyan;QI Jingze;LIU Yuanning;FENG Jiahui(College of Computer Science and Technology,Jilin University,Changchun 130012,China;Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education,Jilin University,Changchun 130012,China)

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012

出　　处：《吉林大学学报（理学版）》2024年第4期923-932,共10页Journal of Jilin University:Science Edition

基　　金：国家自然科学基金(批准号:61471181);吉林省科技发展计划项目(批准号:20230101054JC)。

摘　　要：针对云边端协同环境中依赖任务卸载时效率低以及任务卸载失败的问题,提出一种基于偏好和虚拟适应度的两阶段依赖任务卸载算法.第一阶段,根据提出的二维卸载偏好因子对依赖任务的部分子任务进行直接卸载决策,从而有效缩小遗传算法初始种群的规模.第二阶段,提出基于虚拟适应度的启发式交叉方法,并对基于参考点的快速非支配排序遗传算法(non-dominated sorting genetic algorithmⅢ, NSGA-Ⅲ)的交叉算子进行改进,保留了种群多样性并提升了算法收敛速度,最后使用改进的算法对所有依赖任务的子任务进行最优卸载决策集的搜索.实验结果表明,与其他算法相比,该算法在任务完成时间、任务能耗和边缘云集群成本方面平均优化了10.2%~18.3%,并且将任务失败率平均降低了10.7%~25.6%.Aiming at the problem of low efficiency and failure of dependent task offloading in the cloud-edge-end architecture,we proposed a two-stage dependent task offloading algorithm based on preference and virtual fitness.In the first stage,based on the proposed two-dimensional offloading preference factor,direct offloading decisions were made for some sub-tasks of the dependent tasks,thus effectively reducing the size of the initial population of the genetic algorithm.In the second stage,we proposed a heuristic crossover method based on virtual fitness to improve the crossover operator of the fast non-dominated sorting genetic algorithmⅢ(NSGA-Ⅲ)based on reference points,which preserved the diversity of population and improved the convergence speed of the algorithm.Finally,we used the improved algorithm to search for the optimal offloading decision set for the subtasks of all dependent tasks.The experimental results show that compared with other algorithms,the proposed algorithm optimizes task completion time,task energy consumption and edge cloud cluster cost by 10.2%—18.3%on average and reduces the task failure rate by 10.7%-25.6%on average.

关 键 词：云边端协同环境 依赖任务卸载 多目标优化 虚拟适应度 遗传算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]