一种基于联盟博弈的依赖型任务卸载算法  

A Dependency-aware Task Offloading Algorithm Based on Coalitional Game

作　　者：李奕杭 张洁[1] LI Yi-hang;ZHANG Jie(School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

机构地区：[1]南京邮电大学计算机学院,江苏南京210023

出　　处：《计算机技术与发展》2025年第3期76-83,共8页Computer Technology and Development

基　　金：国家自然科学基金青年基金(61902195);国家重点研发计划(2018YFB1500902)。

摘　　要：大规模的数据采集处理任务对计算能力的要求很高,然而分布式部署在各地基层服务器上可用的计算资源有限,不足以单独处理整个任务数据。边缘计算(Edge Computing,EC)通过将计算任务卸载到边缘服务器上改善服务,为此类应用提供了有效的解决方案。但是,传统的顺序决策策略大多依赖于预调度,且忽略了任务群之间的合作,存在一定的优化空间。对此,基于前序任务层优先策略(Predecessor Layer First,PLF)对具有依赖关系的计算卸载过程进行建模,提出了一种基于分层联盟博弈的计算卸载算法(Layering Coalitional Game Computation Offloading Algorithm,LCGCO)来优化卸载决策,从而降低计算卸载时延和能耗。LCGCO通过前序任务层优先策略确定子任务的卸载顺序,然后通过同优先级子任务间的联盟博弈确定卸载策略,以实现任务群整体最优调度。通过仿真显示,与基于MEFT的遗传算法、拉格朗日求解凸规划方法相比,LCGCO具有更低的时延、能耗和更少的时间复杂度,并且任务图越复杂,LCGCO算法的优化性能越好。Large-scale data processing tasks require a high-level computing power.However,the computing capacity of primary sever are not enough to process the entire task data alone,and can hardly meet the overall delay and energy consumption requirement.Edge computing(EC)provides an effective solution for such applications by offloading computing tasks to edge servers to improve services.However,most of the traditional strategies rely on pre-scheduling,and ignore the cooperation between subtasks,leading to the possibility of optimization.Therefore,the dependency-aware task offloading is modeled based on predecessor layer first(PLF),and a layering coalitional game offloading algorithm(LCGCO)is proposed to optimize the offloading scheme,thereby reducing the overall computation delay and energy consumption.LCGCO applies PLF to determine the offloading order,and then play a coalitional game between tasks in same priority.Simulations demonstrate that LCGCO has lower overall offloading latency,energy consumption and time complexity compared with genetic algorithm based on MEFT and the convex planning method based on Lagrange.And also,LCGCO plays better roles when the DAG of task becomes more complex.

关 键 词：计算卸载 边缘计算 联盟博弈 分层博弈 依赖型任务 

分 类 号：TP929.5[自动化与计算机技术]