基于博弈论和粒子群优化的移动边缘计算任务卸载方法

doi:10.3969/j.issn.0255-8297.2023.03.004

应用科学学报 ›› 2023, Vol. 41 ›› Issue (3): 405-418.doi: 10.3969/j.issn.0255-8297.2023.03.004

基于博弈论和粒子群优化的移动边缘计算任务卸载方法

李晗, 孟顺梅, 蔡志成

南京理工大学计算机科学与工程学院, 江苏南京 210094

收稿日期:2022-11-22 出版日期:2023-05-30 发布日期:2023-06-16
通信作者: 孟顺梅,副教授,研究方向为推荐系统、云计算、服务计算。E-mail:mengshunmei@njust.edu.cn E-mail:mengshunmei@njust.edu.cn
基金资助:
国家自然科学基金(No.61972202)；计算机软件新技术国家重点实验室开放课题(No.KFKT2022B28)；中国博士后科学基金面上基金(No.2019M651835)资助

Game Theory and Particle Swarm Optimization Based Task Offloading Method in Mobile-Edge Computing

LI Han, MENG Shunmei, CAI Zhicheng

School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, Jiangsu, China

Received:2022-11-22 Online:2023-05-30 Published:2023-06-16

摘要/Abstract

摘要： 移动边缘计算（mobile-edge computing, MEC）是一种新兴的计算范式，移动设备可以通过将计算密集型任务卸载到边缘服务器上来降低本地计算能耗和计算时延。首先，该文研究了在微蜂窝基站密集区域场景下的多移动设备独立任务集计算卸载问题，其中每个微蜂窝基站配备了一个计算性能有限的MEC服务器。为了尽可能地降低移动设备的任务集计算能耗和计算时延，使用博弈论的方法将该问题建模为一个非合作多移动设备计算卸载策略博弈。通过对该博弈的分析，证明了其纳什均衡的存在性和有限改进性。然后，设计了一个基于博弈论的分布式计算卸载算法（game theory based distributed computation offloadingalgorithm, GDCOA），并在GDCOA中引入了一个基于粒子群优化（particle swarm optimization, PSO）的移动设备任务集卸载策略改进算法（PSO based improving computationoffloading policy algorithm, PSOIPA）。GDCOA 在有限次迭代后可以达到一个均衡状态。最后，通过仿真对比实验证明了本文所提出的算法GDCOA可以获得较好的计算卸载性能。

关键词: 移动边缘计算, 计算卸载, 博弈论, 粒子群优化

Abstract: Mobile-edge computing (MEC) is an innovative computing paradigm. Mobile devices can reduce local computation energy consumption and delay by offloading computation intensive tasks to the edge servers. In this paper, we first study the computation offloading problem for multiple mobile devices with independent task sets in the dense area of microcell base stations, where each microcell base station is equipped with a computationally limited MEC server. To reduce the task sets computation energy consumption and delay of the mobile devices as much as possible, adopting a game theoretic approach, the problem is formulated as a non-cooperative multi-mobile-device computation offloading strategy game. Through analysis, the Nash equilibrium existence and the finite improvement property of the game are proved. Then, we design a game theory based distributed computation offloading algorithm, namely GDCOA, and introduce a particle swarm optimization (PSO) based improving computation offloading policy algorithm named PSOIPA in it. GDCOA can reach an equilibrium state after a finite number of iterations. Finally, the simulation and comparison experiments corroborate that the proposed algorithm GDCOA in this paper can achieve better computation offloading performance.

Key words: mobile-edge computing (MEC), computation offloading, game theory, particle swarm optimization (PSO)

中图分类号:

TP39

李晗, 孟顺梅, 蔡志成. 基于博弈论和粒子群优化的移动边缘计算任务卸载方法[J]. 应用科学学报, 2023, 41(3): 405-418.

LI Han, MENG Shunmei, CAI Zhicheng. Game Theory and Particle Swarm Optimization Based Task Offloading Method in Mobile-Edge Computing[J]. Journal of Applied Sciences, 2023, 41(3): 405-418.

参考文献

[1] Li L, Liao X F, Jin H, et al. Computation offloading toward edge computing [J]. Proceedings of the IEEE, 2019, 107(8): 1584-1607.
[2] Dinh H T, Lee C, Niyato D, et al. A survey of mobile cloud computing: architecture, applications, and approaches [J]. Wireless Communications & Mobile Computing, 2013, 13(18): 1587-1611.
[3] Mach P, Becvar Z. Mobile edge computing: a survey on architecture and computation offloading [J]. IEEE Communications Surveys & Tutorials, 2017, 19(3): 1628-1656.
[4] Zhang R, Cheng P, Chen Z, et al. Calibrated bandit learning for decentralized task offloading in ultra-dense networks [J]. IEEE Transactions on Communications, 2022, 70(4): 2547-2560.
[5] Guo F X, Zhang H L, Ji H, et al. An efficient computation offloading management scheme in the densely deployed small cell networks with mobile edge computing [J]. IEEE/ACM Transactions on Networking, 2018, 26(6): 2651-2664.
[6] Kwak J, Kim Y, Lee J, et al. DREAM: dynamic resource and task allocation for energy minimization in mobile cloud systems [J]. IEEE Journal on Selected Areas in Communications, 2015, 33(12): 2510-2523.
[7] 罗斌, 于波. 移动边缘计算中基于粒子群优化的计算卸载策略[J]. 计算机应用, 2020, 40(8): 2293- 2298. Luo B, Yu B. Computation offloading strategy based on particle swarm optimization in mobile edge computing [J]. Journal of Computer Applications, 2020, 40(8): 2293-2298. (in Chinese)
[8] Liu J, Mao Y Y, Zhang J, et al. Delay-optimal computation task scheduling for mobile-edge computing systems [C]//2016 IEEE International Symposium on Information Theory (ISIT), 2016: 1451-1455.
[9] Fan W H, Yao L, Han J T, et al. Game-based multi-type task offloading among mobile-edgecomputing-enabled base stations [J]. IEEE Internet of Things Journal, 2021, 8(24): 17691-17704.
[10] Alfakih T, Hassan M M, Gumaei A, et al. Task offloading and resource allocation for mobile edge computing by deep reinforcement learning based on SARSA [J]. IEEE Access, 2020, 8: 54074-54084.
[11] 邝祝芳, 陈清林, 李林峰, 等. 基于深度强化学习的多用户边缘计算任务卸载调度与资源分配算法[J]. 计算机学报, 2022, 45(4): 812-824. Kuang Z F, Chen Q L, Li L F, et al. Multi-user edge computing task offloading scheduling and resource allocation based on deep reinforcement learning [J]. Chinese Journal of Computers, 2022, 45(4): 812-824. (in Chinese)
[12] Chen X, Jiao L, Li W Z, et al. Efficient multi-user computation offloading for mobile-edge cloud computing [J]. IEEE/ACM Transactions on Networking, 2016, 24(5): 2795-2808.
[13] Cao H J, Cai J. Distributed multiuser computation offloading for cloudlet-based mobile cloud computing: a game-theoretic machine learning approach [J]. IEEE Transactions on Vehicular Technology, 2018, 67(1): 752-764.
[14] Shah-Mansouri H, Wong V W S. Hierarchical fog-cloud computing for IoT systems: a computation offloading game [J]. IEEE Internet of Things Journal, 2018, 5(4): 3246-3257.
[15] Kennedy J, Eberhart R. Particle swarm optimization [C]//Proceedings of ICNN’95- International Conference on Neural Networks (ICNN), 1995: 1942-1948.
[16] 余翔, 石雪琴, 刘一勋. 移动边缘计算中卸载策略与功率的联合优化[J]. 计算机工程, 2020, 46(6): 20-25. Yu X, Shi X Q, Liu Y X. Joint optimization of offloading strategy and power in mobile-edge computing [J]. Computer Engineering, 2020, 46(6): 20-25. (in Chinese)
[17] 周晓敏. 面向节能的移动边缘计算的卸载策略研究[D]. 北京: 北京邮电大学, 2019.

基于博弈论和粒子群优化的移动边缘计算任务卸载方法

Game Theory and Particle Swarm Optimization Based Task Offloading Method in Mobile-Edge Computing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	曾磊, 白金明, 刘琦. 多群落粒子群优化供应链数据中心任务调度[J]. 应用科学学报, 2023, 41(3): 419-430.
[2]	邹倩颖, 陈晖阳, 李永生, 胡力雯, 王小芳. 粒子群优化的深海图像暗边缘检测优化算法[J]. 应用科学学报, 2023, 41(1): 153-169.
[3]	彭艺, 张申, 朱豪, 李启骞. 一种基于博弈论的D2D通信中继选择算法[J]. 应用科学学报, 2020, 38(6): 871-881.
[4]	迟忠君, 万庆祝, 陈娅兰, 孙健, 谷君, 张淼, 王鑫. 基于纳什谈判的家用热水器的优化运行[J]. 应用科学学报, 2018, 36(6): 987-995.
[5]	王光艳, 耿艳香, 陈雷. 改进粒子群算法在水下盲语音分离中的应用研究[J]. 应用科学学报, 2018, 36(4): 589-600.
[6]	姜长泓, 张永恒, 王盛慧. 基于改进粒子群优化算法的PID控制器参数优化[J]. 应用科学学报, 2017, 35(5): 667-674.
[7]	董莉, 宋晓勤, 韩杰. 基于遗传粒子群优化的认知OFDM网络资源分配算法[J]. 应用科学学报, 2017, 35(3): 288-298.
[8]	杨柳, 郭道省, 叶展, 谢斯林, 王雅慧, 张邦宁. 卫星通信系统中编码调制模式分配算法[J]. 应用科学学报, 2016, 34(4): 371-379.
[9]	杨洪涛，耿金华，丁小瑞，喻曹丰，禹斌. 数控机床力-几何误差的PSO-SVM建模[J]. 应用科学学报, 2014, 32(3): 325-330.
[10]	刘立昕，卞红雨. 用于水下目标跟踪的多特征融合PSOPF 算法[J]. 应用科学学报, 2013, 31(6): 564-568.
[11]	张树银，郭英，齐子森，苏令华. 共形阵列LFM信号DOA和极化参数的联合估计[J]. 应用科学学报, 2013, 31(3): 252-258.
[12]	陈志敏，薄煜明，吴盘龙，宋公飞，段文勇. 一种新型自适应粒子群优化粒子滤波算法及应用[J]. 应用科学学报, 2013, 31(3): 285-293.
[13]	王建青，李帆，赵建辉. 基于混合粒子群优化的巡航导弹低空突防航迹规划[J]. 应用科学学报, 2012, 30(3): 317-323.
[14]	靳一，王继武，吴乐南. 基于IM-SAPSO和SVM的EBPSK检测器设计[J]. 应用科学学报, 2012, 30(2): 141-145.
[15]	张民，陈欣，陆宇平. PSO算法用于导弹鲁棒控制器性能权函数优化[J]. 应用科学学报, 2011, 29(6): 650-654.