[1]李奕杭,张洁.一种基于联盟博弈的依赖型任务卸载算法[J].计算机技术与发展,2025,(03):76-83.[doi:10.20165/j.cnki.ISSN1673-629X.2024.0344]
　LI Yi-hang,ZHANG Jie.A Dependency-aware Task Offloading Algorithm Based on Coalitional Game[J].,2025,(03):76-83.[doi:10.20165/j.cnki.ISSN1673-629X.2024.0344]
点击复制

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

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2025年03期
页码:
76-83
栏目:
移动与物联网络
出版日期:
2025-03-10

文章信息/Info

Title:
A Dependency-aware Task Offloading Algorithm Based on Coalitional Game
文章编号:
1673-629X(2025)03-0076-08
作者:
李奕杭; 张洁
南京邮电大学 计算机学院,江苏 南京 210023
Author(s):
LI Yi-hang; ZHANG Jie
School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China
关键词:
计算卸载; 边缘计算; 联盟博弈; 分层博弈; 依赖型任务
Keywords:
computation offloading; edge computing; coalitional game; layering game; dependency-aware task
分类号:
TP929.5
DOI:
10.20165/j.cnki.ISSN1673-629X.2024.0344
摘要:
大规模的数据采集处理任务对计算能力的要求很高,然而分布式部署在各地基层服务器上可用的计算资源有限,不足以单独处理整个任务数据。 边缘计算(Edge Computing,EC)通过将计算任务卸载到边缘服务器上改善服务,为此类应用提供了有效的解决方案。 但是,传统的顺序决策策略大多依赖于预调度,且忽略了任务群之间的合作,存在一定的优化空间。 对此,基于前序任务层优先策略(Predecessor Layer First,PLF)对具有依赖关系的计算卸载过程进行建模,提出了一种基于分层联盟博弈的计算卸载算法(Layering Coalitional Game Computation Offloading Algorithm,LCGCO)来优化卸载决策,从而降低计算卸载时延和能耗。 LCGCO 通过前序任务层优先策略确定子任务的卸载顺序,然后通过同优先级子任务间的联盟博弈确定卸载策略,以实现任务群整体最优调度。 通过仿真显示,与基于 MEFT 的遗传算法、拉格朗日求解凸规划方法相比,LCGCO 具有更低的时延、能耗和更少的时间复杂度,并且任务图越复杂,LCGCO 算法的优化性能越好。
Abstract:
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 co-alitional 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.

相似文献/References:

[1]沈大港,范鹏飞,周慧娟,等.面向车联网基于边缘计算的点对点信息传输[J].计算机技术与发展,2021,31(08):139.[doi:10. 3969 / j. issn. 1673-629X. 2021. 08. 024]
　SHEN Da-gang,FAN Peng-fei,ZHOU Hui-juan,et al.Point-to-point Information Communication Based on Edge Computing for Internet of Vehicle[J].,2021,31(03):139.[doi:10. 3969 / j. issn. 1673-629X. 2021. 08. 024]
[2]张云飞,高 岭,丁彩玲,等.边缘计算环境下改进蚁群算法的任务调度算法[J].计算机技术与发展,2021,31(09):86.[doi:10. 3969 / j. issn. 1673-629X. 2021. 09. 015]
　ZHANG Yun-fei,GAO Ling,DING Cai-ling,et al.Improved Task Scheduling Algorithm of Ant Colony Algorithm in Edge Computing[J].,2021,31(03):86.[doi:10. 3969 / j. issn. 1673-629X. 2021. 09. 015]
[3]王 闯,沈苏彬.一种基于多智能体的分布式深度神经网络算法[J].计算机技术与发展,2021,31(12):45.[doi:10. 3969 / j. issn. 1673-629X. 2021. 12. 008]
　WANG Chuang,SHEN Su-bin.A Distributed Deep Neural Network Algorithm Based on Multi-agent[J].,2021,31(03):45.[doi:10. 3969 / j. issn. 1673-629X. 2021. 12. 008]
[4]林广栋,黄光红,陆俊峰.一款人工智能芯片上 FCOS 模型的应用研究[J].计算机技术与发展,2023,33(05):9.[doi:10. 3969 / j. issn. 1673-629X. 2023. 05. 002]
　LIN Guang-dong,HUANG Guang-hong,LU Jun-feng.Application of FCOS Model on an AI Chip[J].,2023,33(03):9.[doi:10. 3969 / j. issn. 1673-629X. 2023. 05. 002]
[5]薛 锋,张雅文,陈思光.基于 D2D 协同的边缘计算迁移机制研究[J].计算机技术与发展,2023,33(06):117.[doi:10. 3969 / j. issn. 1673-629X. 2023. 06. 018]
　XUE Feng,ZHANG Ya-wen,CHEN Si-guang.Research on Edge Computing Offloading Mechanism Based on D2D Collaboration[J].,2023,33(03):117.[doi:10. 3969 / j. issn. 1673-629X. 2023. 06. 018]
[6]张海超,赖金山,刘 东,等.边缘计算下的轻量级联邦学习隐私保护方案[J].计算机技术与发展,2023,33(09):161.[doi:10. 3969 / j. issn. 1673-629X. 2023. 09. 024]
　ZHANG Hai-chao,LAI Jin-shan,LIU Dong,et al.Lightweight Federated Learning Privacy Protection Scheme under Edge Computing[J].,2023,33(03):161.[doi:10. 3969 / j. issn. 1673-629X. 2023. 09. 024]
[7]王 冠,张倩倩.基于 SGX 的车联网身份认证方案研究[J].计算机技术与发展,2023,33(11):99.[doi:10. 3969 / j. issn. 1673-629X. 2023. 11. 015]
　WANG Guan,ZHANG Qian-qian.Research on Identity Authentication Scheme Based on SGX in Internet of Vehicles[J].,2023,33(03):99.[doi:10. 3969 / j. issn. 1673-629X. 2023. 11. 015]
[8]王志良,何 刚*,俞文心,等.边缘场景下动态联邦学习优化方法[J].计算机技术与发展,2024,34(02):98.[doi:10. 3969 / j. issn. 1673-629X. 2024. 02. 015]
　WANG Zhi-liang,HE Gang*,YU Wen-xin,et al.Dynamic Federated Learning Optimization Method in Edge Scenarios[J].,2024,34(03):98.[doi:10. 3969 / j. issn. 1673-629X. 2024. 02. 015]
[9]刘善明,余新阳,欧阳魁.面向筛面复杂背景的矿山异物视觉检测方法[J].计算机技术与发展,2024,34(05):196.[doi:10.20165/j.cnki.ISSN1673-629X.2024.0060]
　LIU Shan-ming,YU Xin-yang,OUYANG Kui.A Visual Detection Method of Foreign Bodies in Mines Facing Complex Background of Screen Surface[J].,2024,34(03):196.[doi:10.20165/j.cnki.ISSN1673-629X.2024.0060]
[10]白金婷,罗飞*,孙超,等.基于KubeEdge的全国气象监视数据采集软件设计[J].计算机技术与发展,2024,34(08):67.[doi:10.20165/j.cnki.ISSN1673-629X.2024.0150]
　BAI Jin-ting,LUO Fei*,SUN Chao,et al.Design of Nationwide Meteorological Monitoring Data Collection Software Based on KubeEdge[J].,2024,34(03):67.[doi:10.20165/j.cnki.ISSN1673-629X.2024.0150]
[11]钟云峰,宋伟宁.基于云边协同多任务计算卸载策略[J].计算机技术与发展,2022,32(04):69.[doi:10. 3969 / j. issn. 1673-629X. 2022. 04. 012]
　ZHONG Yun-feng,SONG Wei-ning.Multi-task Computation Offloading Strategy Based on Cloud-side Collaboration[J].,2022,32(03):69.[doi:10. 3969 / j. issn. 1673-629X. 2022. 04. 012]
[12]赵尚维康,孙 君.工业物联网中基于 SMDP 的协同卸载方案[J].计算机技术与发展,2022,32(09):76.[doi:10. 3969 / j. issn. 1673-629X. 2022. 09. 012]
　ZHAO Shang-wei-kang,SUN Jun.Multi-MEC Collaborative Computing Unloading Scheme Based on SMDP in Industrial Internet of Things[J].,2022,32(03):76.[doi:10. 3969 / j. issn. 1673-629X. 2022. 09. 012]

更新日期/Last Update: 2025-03-10