云边环境下基于博弈论的两阶段任务迁移策略

doi:10.11772/j.issn.1001-9081.2020071091

计算机应用 ›› 2021, Vol. 41 ›› Issue (5): 1392-1398.DOI: 10.11772/j.issn.1001-9081.2020071091

所属专题：先进计算

云边环境下基于博弈论的两阶段任务迁移策略

王艺洁¹, 凡佳飞², 王陈宇¹

1. 山东科技大学计算机科学与工程学院, 山东青岛 266000;
2. 空装驻上海地区军事代表局空装驻南京地区第三军事代表室, 南京 211100

收稿日期:2020-07-27 修回日期:2020-09-15 出版日期:2021-05-10 发布日期:2020-10-20
通讯作者: 王艺洁
作者简介:王艺洁(1995-),女,江苏徐州人,硕士研究生,主要研究方向:云计算、移动边缘计算;凡佳飞(1991-),男,江苏扬州人,硕士研究生,主要研究方向:云计算、虚拟化、嵌入式系统;王陈宇(1995-),男,山东枣庄人,硕士研究生,CCF会员,主要研究方向:云计算、任务调度、进化计算。
基金资助:
中国航空研究院、中国航空工业集团公司金城南京机电液压工程研究中心、航空机电系统综合航空科技重点实验室航空基金资助项目（201928052006）。

Two-stage task offloading strategy based on game theory in cloud-edge environment

WANG Yijie¹, FAN Jiafei², WANG Chenyu¹

1. College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao Shandong 266000, China;
2. The Third Military Representative Office of Air Force in Nanjing, Military Representative Office of Air Force in Shanghai, Nanjing Jiangsu 211100, China

Received:2020-07-27 Revised:2020-09-15 Online:2021-05-10 Published:2020-10-20
Supported by:
This work is partially supported by the Aeronautical Fund of Chinese Aeronautical Establishment, AVIC Nanjing Engineering Institute of Aircraft Systems and Aviation Key Laboratory of Science and Technology on Aero Electromechanical System Integration (201928052006).

摘要/Abstract

摘要： 移动边缘计算（MEC）为计算密集型应用和资源受限的移动设备之间的冲突提供了有效解决办法，但大多关于MEC迁移的研究仅考虑移动设备与MEC服务器之间的资源分配，忽略了云计算中心的巨大计算资源。为了充分利用云和MEC资源，提出一种云边协作的任务迁移策略。首先，将云边服务器的任务迁移问题转化为博弈问题；然后，证明该博弈中纳什均衡（NE）的存在以及唯一性，并获得博弈问题的解决方案；最后，提出了一种基于博弈论的两阶段任务迁移算法来求解任务迁移问题，并通过性能指标对该算法的性能进行了评估。仿真结果表明，采用所提算法所产生的总开销分别比本地执行、云中心服务器执行和MEC服务器执行的总开销降低了72.8%、47.9%和2.65%，数值结果证实了所提策略可以实现更高的能源效率和更低的任务迁移开销，并且随着移动设备数量的增加可以很好地扩展规模。

关键词: 移动边缘计算, 云边协作, 任务迁移, 博弈论, 纳什均衡

Abstract: Mobile Edge Computing (MEC) provides an effective solution to the conflict between computationally intensive applications and resource constrained mobile devices. However, most studies on the MEC offloading only consider the resource allocation between mobile devices and MEC servers, and ignore the huge computing resources in the cloud computing centers. In order to make full use of cloud and MEC resources, a task offloading strategy of cloud-edge collaboration was proposed. Firstly, the task offloading problem of the cloud-edge servers was transformed into a game problem. Then, the existence and uniqueness of Nash Equilibrium (NE) in this game were proved, and the solution to this game problem was obtained. Finally, a two-stage task offloading algorithm based on game theory was proposed to solve the task offloading scheme, and the performance of this algorithm was evaluated by performance indicators. The simulation results show that the total overhead of using the proposed algorithm is reduced by 72.8%, 47.9%, and 2.65% compared with those of local execution, cloud server execution and MEC server execution, respectively. The numerical results confirm that the proposed strategy can achieve higher energy efficiency and lower task offloading overhead, and extend scale well with the number of mobile devices increases.

Key words: Mobile Edge Computing (MEC), cloud-edge collaboration, task offloading, game theory, Nash Equilibrium (NE)

中图分类号:

TP393.0

王艺洁, 凡佳飞, 王陈宇. 云边环境下基于博弈论的两阶段任务迁移策略[J]. 计算机应用, 2021, 41(5): 1392-1398.

WANG Yijie, FAN Jiafei, WANG Chenyu. Two-stage task offloading strategy based on game theory in cloud-edge environment[J]. Journal of Computer Applications, 2021, 41(5): 1392-1398.

参考文献

[1] 刘志禹. 5G移动通信发展趋势与若干关键技术分析[J]. 中国新通信,2018,20(11):20. (LIU Z Y. Analysis of 5G mobile communication development trend and some key technologies[J].China New Telecommunications,2018,20(11):20.)
[2] JEONG B,YOON J,LEE J M. Social media mining for product planning:a product opportunity mining approach based on topic modeling and sentiment analysis[J]. International Journal of Information Management,2019,48:280-290.
[3] MAKRANSKY G,TERKILDSEN T S,MAYER R E. Adding immersive virtual reality to a science lab simulation causes more presence but less learning[J]. Learning and Instruction,2019, 60:225-236.
[4] ZHU L,YU F R,WANG Y,et al. Big data analytics in intelligent transportation systems:a survey[J]. IEEE Transactions on Intelligent Transportation Systems,2019,20(1):383-398.
[5] NING Z,HUANG J,WANG X,et al. Mobile edge computingenabled Internet of vehicles:toward energy-efficient scheduling[J]. IEEE Network,2019,33(5):198-205.
[6] 施巍松, 孙辉, 曹杰, 等. 边缘计算:万物互联时代新型计算模型[J]. 计算机研究与发展,2017,54(5):907-924.(SHI W S, SUN H,CAO J,et al. Edge computing-an emerging computing model for the Internet of everything era[J]. Journal of Computer Research and Development,2017,54(5):907-924.)
[7] AHMED E, REHMANI M H. Mobile edge computing:opportunities,solutions,and challenges[J]. Future Generation Computer Systems,2017,70:59-63.
[8] ZHANG K,MAO Y,LENG S,et al. Energy-efficient offloading for mobile edge computing in 5G heterogeneous networks[J]. IEEE Access,2016,4:5896-5907.
[9] REN J,YU G,CAI Y,et al. Latency optimization for resource allocation in mobile-edge computation offloading[J]. IEEE Transactions on Wireless Communications,2018,17(8):5506-5519.
[10] LIU B,XU H,ZHOU X. Resource allocation in wireless-powered mobile edge computing systems for Internet of Things applications[J]. Electronics,2019,8(2):No. 206.
[11] CHEN X,JIAO L,LI W,et al. Efficient multi-user computation offloading for mobile-edge cloud computing[J]. IEEE/ACM Transactions on Networking,2016,24(5):2795-2808.
[12] JOŠILO S,DÁN G. Decentralized algorithm for randomized task allocation in fog computing systems[J]. IEEE/ACM Transactions on Networking,2019,27(1):85-97.
[13] ZHENG J,CAI Y,WU Y,et al. Dynamic computation offloading for mobile cloud computing:a stochastic game-theoretic approach[J]. IEEE Transactions on Mobile Computing,2019,18(4):771-786.
[14] LIU Y,WANG S,HUANG J,et al. A computation offloading algorithm based on game theory for vehicular edge networks[C]//Proceedings of the 2018 IEEE International Conference on Communications. Piscataway:IEEE,2018:1-6.
[15] 董思岐, 李海龙, 屈毓锛, 等. 移动边缘计算中的计算卸载策略研究综述[J]. 计算机科学,2019,46(11):32-40.(DONG S Q, LI H L, QU Y B, et al. Survey of research on computing offloading strategies in mobile edge computing[J]. Computer Science,2019,46(11):32-40.)
[16] LIN T,ALPCAN T,HINTON K. A game-theoretic analysis of energy efficiency and performance for cloud computing in communication networks[J]. IEEE Systems Journal,2017,11(2):649-660.
[17] LIU J,MAO Y,ZHANG J,et al. Delay-optimal computation task scheduling for mobile-edge computing systems[C]//Proceedings of the 2016 IEEE International Symposium on Information Theory. Piscataway:IEEE,2016:1451-1455.
[18] CHEN X. Decentralized computation offloading game for mobile cloud computing[J]. IEEE Transactions on Parallel and Distributed Systems,2015,26(4):974-983.
[19] LI N,MARTÍNEZ-ORTEGA J F,DIAZ V H. Distributed power control for interference-aware multi-user mobile edge computing:a game theory approach[J]. IEEE Access,2018,6:36105-36114.
[20] LOH K H, GOLDEN B, WASIL E. Solving the maximum cardinality bin packing problem with a weight annealing-based algorithm[M]//CHINNECK J W, KRISTJANSSON B, SALTZMAN M J. Operations Research and Cyber-Infrastructure. Boston:Springer,2009:147-164.

云边环境下基于博弈论的两阶段任务迁移策略

Two-stage task offloading strategy based on game theory in cloud-edge environment

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	郭棉, 张锦友. 移动边缘计算环境中面向机器学习的计算迁移策略[J]. 计算机应用, 2021, 41(9): 2639-2645.
[2]	董文涛, 李卓, 陈昕. 基于联邦学习的在线短视频内容分发策略[J]. 计算机应用, 2021, 41(6): 1551-1556.
[3]	毛莺池, 徐雪松, 刘鹏飞. 基于稳定匹配的多用户任务卸载策略[J]. 计算机应用, 2021, 41(3): 786-793.
[4]	张舒瑶, 李勇华, 范家佳. 基于博弈论的散货港口堆场堆位分配算法[J]. 计算机应用, 2021, 41(3): 867-874.
[5]	王岱巍, 徐高潮, 李龙. 无人机辅助的移动边缘计算中的任务分配策略[J]. 计算机应用, 2021, 41(10): 2928-2936.
[6]	吴雨芯, 蔡婷, 张大斌. 移动边缘计算中基于Stackelberg博弈的算力交易与定价[J]. 计算机应用, 2020, 40(9): 2683-2690.
[7]	罗斌, 于波. 移动边缘计算中基于粒子群优化的计算卸载策略[J]. 计算机应用, 2020, 40(8): 2293-2298.
[8]	郑延斌, 樊文鑫, 韩梦云, 陶雪丽. 基于博弈论及Q学习的多Agent协作追捕算法[J]. 计算机应用, 2020, 40(6): 1613-1620.
[9]	柳兴, 杨震, 王新军, 朱恒. 移动边缘计算中的内容分发加速策略[J]. 计算机应用, 2020, 40(5): 1389-1391.
[10]	黄冬艳, 付中卫, 王波. 计算资源受限的移动边缘计算服务器收益优化策略[J]. 计算机应用, 2020, 40(3): 765-769.
[11]	范家佳, 刘洪星, 李勇华, 杨丽金. 基于博弈论的内河港口作业车辆协同选路方法[J]. 计算机应用, 2020, 40(1): 50-55.
[12]	袁培燕, 蔡云云. 移动边缘计算中一种贪心策略的内容卸载方案[J]. 计算机应用, 2019, 39(9): 2664-2668.
[13]	王甜甜, 于双元, 徐保民. 基于策略梯度算法的工作量证明中挖矿困境研究[J]. 计算机应用, 2019, 39(5): 1336-1342.
[14]	郑延斌, 王林林, 席鹏雪, 樊文鑫, 韩梦云. 基于蚁群算法及博弈论的多Agent路径规划算法[J]. 计算机应用, 2019, 39(3): 681-687.
[15]	余韵, 连晓灿, 朱宇航, 谭国平. 增强现实场景下移动边缘计算资源分配优化方法[J]. 计算机应用, 2019, 39(1): 22-25.