云边协同系统中基于博弈论的资源分配与任务卸载方案

doi:10.16182/j.issn1004731x.joss.21-0077

摘要/Abstract

摘要：

综合考虑时延、能耗和计算资源成本，构建云边协同系统中的效用最大化问题，并将其分解为计算资源分配、上行功率分配和任务卸载策略三个子问题。提出一种基于博弈论的资源分配和任务卸载方案（game-based resource allocation and task offloading， GRATO） 以分别解决上述子问题。利用凸优化条件求得计算资源分配最优解；设计一种低复杂度的上行功率分配方法用于降低无线干扰；针对任务卸载策略优化问题，提出一种基于博弈论的分布式任务卸载算法（game-based distributed task offloading algorithm， GDTOA）。仿真结果表明，GRATO方案在时延和能耗方面的性能优于其他方案，还可以感知用户的优先级，使紧急用户具有更高的效用和更低的时延。

关键词: 边缘计算, 资源分配, 计算任务卸载, 博弈, 效用最大化

Abstract:

Considering the delay, energy consumption and computing resource cost, the utility maximization problem in collaborative cloud-edge system is constructed, and divided into three subproblems: computing resource allocation, uplink power allocation and task offloading strategy. A game-based resource allocation and task offloading(GRATO) scheme is proposed to solve those subproblems. The optimal solution of computing resource allocation is obtained by using convex optimization conditions; a low complexity uplink power allocation method is designed to reduce wireless interfere; a game-based distributed task offloading algorithm (GDTOA) is proposed to optimize the task offloading strategy. Simulation results show that the performance of GRATO is better than other schemes on delay and energy consumption, and it can sense the priority of users, resulting in higher utility and lower latency for emergency users..

Key words: edge computing, resource allocation, computation task offloading, game, utility maximization

中图分类号:

TP301.6

吴学文, 廖婧贤. 云边协同系统中基于博弈论的资源分配与任务卸载方案[J]. 系统仿真学报, 2022, 34(7): 1468-1481.

Xuewen Wu, Jingxian Liao. Game-Based Resource Allocation and Task Offloading Scheme in Collaborative Cloud-Edge Computing System[J]. Journal of System Simulation, 2022, 34(7): 1468-1481.

图/表 10

图1

表1

实验参数

参数	数值
系统带宽 $B$ /MHz	20
用户最大上行发射功率 $p m a x$ /dBm	23
背景噪声功率 $σ 2$ /dBm	-100
从BS到云的单位数据传输时延 $v$ / $μ s / b i t - 1$	$1$
能量系数 $κ$	$5 × 10 - 27$
MEC服务器的CPU频率F/GHz	20
用户设备的CPU频率 $f i l$ /GHz	1
MEC服务器的计算资源成本/ $$ / G H z - 1$	$0.015$
云服务器的计算资源成本/ $$ / G H z - 1$	$0.03$

表1

图2

表2

各方案的运行时间 (ms)

方案	$N = 5$	$N = 10$
MCORA	0.096±0.02	0.22±0.07
COSO	0.63±0.2	0.77±0.18
DCORA	0.71±0.18	0.95±0.32
JTORA	0.93±0.2	2.51±0.4
GRATO	3.26±0.37	11.8±2.5
Exhaustive	32.2±3.9	2 543±36

表2

图3

图4

图5

图6

图7

图8

参考文献 23

1	Tao Xiaoyi, Ota Kaoru, Dong mianxiong, et al. Performance Guaranteed Computation Offloading for Mobile-edge Cloud Computing[J]. IEEE Wireless Communications Letters (S2162-2337), 2017, 6(6): 774-777.
2	Zhang Guowei, Fei Shen, Zhang Yueyue, et al. Delay Minimized Task Scheduling in Fog-enabled IoT Networks[C]// International Conference on Wireless Communications and Signal Processing (WCSP). IEEE, 2018, 10:1-6.
3	Hu Yun Chao, Patel Milan, Sabella Dario, et al. Mobile Edge Computing—A key technology towards 5G[R]. ETSI white paper, 2015, 11(11): 1-16.
4	Tran Tuyen X, Hajisami Abolfazl, pandey parul, et al. Collaborative Mobile Edge Computing in 5G Networks: New Paradigms, Scenarios, and Challenges[J]. IEEE Communications Magazine (S0163-6804), 2017, 55(4): 54-61.
5	Lei Yang, Cao Jiannong, Cheng Hui, et al. Multi-user Computation Partitioning for Latency Sensitive Mobile Cloud Applications[J]. IEEE Transactions on Computers(S0018-9340), 2015, 64(8): 2253-2266.
6	Valeria Cardellini, Vittoria De Nitto Personé, Divacerio Valero,et al. A Game-theoretic Approach to Computation Offloading in Mobile Cloud Computing[J]. Math Program (S0025-5610), 2016, 157(2): 421-449.
7	You Changsheng, Huang Kaibin, Hyukjin Chae, et al. Energy-efficient Resource Allocation for Mobile-edge Computation Offloading[J]. IEEE Transactions on Wireless Communications (S1536-1276), 2016, 16(3): 1397-1411.
8	Reza Rahimi M, Venkatasubramanian Nalini, vasilakos Av, et al. Music: Mobility-aware Optimal Service Allocation in Mobile Cloud Computing[C]// IEEE Sixth International Conference on cloud computing. IEEE, 2013: 75-82.
9	Xiao Surong, Liu Chubo, Li Kenli, et al. System Delay Optimization for Mobile Edge Computing[J]. Future Generation Computer Systems (S0167-739X), 2020(109): 17-28.
10	Huynh Luan NT, Pham Quoc-Viet, Pham Xuan-Qui, et al. Efficient Computation Offloading in Multi-Tier Multi-Access Edge Computing Systems: A Particle Swarm Optimization Approach[J].Applied Sciences (S2076-3417), 2020(10): 203.
11	Lyu X., Tian H, Zhang P, et al. Multi-user Joint Task Offloading and Resources Optimization in Proximate Clouds[J]. IEEE Transactions on Vehicular Technology(S0018-9545), 2017, 66(4): 3435–3447.
12	Tran Tuyen X, Pompili Dario. Joint Task Offloading and Resource Allocation for Multi-server Mobile-edge Computing Networks[J]. IEEE Transactions on Vehicular Technology (S0018-9545), 2019, 68(1): 856-868.
13	Ren Jinke, Yu Guanding, Cai Yunlong, et al. Latency optimization for Resource Allocation in Mobile-edge Computation Offloading[J]. IEEE Transactions on Wireless Communications (S1536-1276), 2018, 17(8): 5506-5519.
14	Gu Yunan, Zheng Chang, Miao Pan, et al. Joint radio and computational resource allocation in IoT fog computing[J].IEEE Transactions on Vehicular Technology (S0018-9545), 2018, 67(8): 7475-7484.
15	Ma S, Guo S, Wang K, et al. A cyclic game for service-oriented resource allocation in edge computing[J]. IEEE Transactions on Services Computing (S1939-1374), 2020, 13(4): 723-734.
16	Chen Yifan, Zhi Y, Yang B, et al. A Stackelberg Game Approach to Multiple Resources Allocation and Pricing in Mobile Edge Computing[J]. Future Generation Computer Systems (S0167-739X), 2020, 108: 273-287.
17	Chen Xu. Decentralized Computation Offloading Game for Mobile Cloud Computing[J]. IEEE Transactions on Parallel and Distributed Systems (S1045-9219), 2014, 26(4): 974-983.
18	Hu Junyan, Li kenli, Liu chubo, et al. Game-Based Task Offloading of Multiple Mobile Devices with QoS in Mobile Edge Computing Systems of Limited Computation Capacity[J].ACM Transactions on Embedded Computing Systems (S1539-9087), 2020, 19(4): 1-21.
19	Long Long, Liu zichen, Zhou Yiqing, et al. Delay Optimized Computation Offloading and Resource Allocation for Mobile Edge Computing[C]// IEEE 90th Vehicular Technology Conference (VTC2019-Fall), IEEE, 2019:1-5.
20	Misra S, Sarkar S. Priorty-based Time-slot Allocation in Wireless Body Area Networks during Medical Emergency Situations: An Evolutionany Game-Thearetic Perspective[J]. IEEE Journal of Biamed and Health Informatios, 2015, 19(2): 541-548.
21	Tammer K.. The Application of Parametric Optimization and Imbedding to the Foundation and Realization of a Generalized Primal Decomposition Approach[J]. Mathematical research (S0138-3019), 1987, 35: 376-386.
22	Zhao Junhui, Li Qiuping, Gong Yi, et al. Computation Offloading and Resource Allocation for Cloud Assisted Mobile Edge Computing in Vehicular Networks[J]. IEEE Transactions on Vehicular Technology (S0018-9545), 2019, 68(8): 7944-7956.
23	Ren J, Yu G, He Y, et al. Collaborative Cloud and Edge Computing for Latency Minimization[J]. IEEE Transactions on Vehicular Technology (S0018-9545), 2019, 68(5): 5031-5044.

[1]	罗俊仁, 张万鹏, 袁唯淋, 胡振震, 陈少飞, 陈璟. 面向多智能体博弈对抗的对手建模框架[J]. 系统仿真学报, 2022, 34(9): 1941-1955.
[2]	程鹏, 张文柱, 谢书翰, 杨子轩. 基于移动边缘计算的车联网任务卸载研究与仿真[J]. 系统仿真学报, 2022, 34(6): 1304-1311.
[3]	许斌, 闫文卿, 韩卓凡, 何广深, 邓涛, 赵云凯, 亓晋. 基于烟花算法的基站群协作计算卸载模型研究[J]. 系统仿真学报, 2022, 34(2): 354-365.
[4]	徐颖, 刘勤明, 周林森. 基于博弈论的闭环双渠道回收供应链决策研究[J]. 系统仿真学报, 2022, 34(2): 396-408.
[5]	吴曦, 孟祥林, 杨镜宇. 下一代战略博弈推演系统研究[J]. 系统仿真学报, 2021, 33(9): 2017-2024.
[6]	李小莉, 曹策俊, 张帆顺. 进口国规制下医药产品出口安全监管演化仿真[J]. 系统仿真学报, 2021, 33(9): 2252-2260.
[7]	黄海涛, 刘勤明, 叶春明, 陈翔. 基于区块链技术的政府采购合同融资博弈分析[J]. 系统仿真学报, 2021, 33(8): 1947-1958.
[8]	王凌, 吴楚格, 范文慧. 边缘计算资源分配与任务调度优化综述[J]. 系统仿真学报, 2021, 33(3): 509-520.
[9]	魏翔宇, 张琪. 基于非合作博弈的路网对抗行为建模研究[J]. 系统仿真学报, 2021, 33(2): 271-279.
[10]	王青云, 焦德忠, 史铄, 彭根燕, 孙俊华, 段雨昕. 改进的蚁群干扰资源分配方法[J]. 系统仿真学报, 2021, 33(12): 2967-2974.
[11]	张巍, 李权, 周宇球, 罗雨航, 奚培锋. 有源配电网两阶段动态应急抗灾运行策略[J]. 系统仿真学报, 2020, 32(5): 936-945.
[12]	马华红, 吴红海, 郑国强, 冀保峰. 基于合作博弈的性能均衡机会路由及仿真分析[J]. 系统仿真学报, 2020, 32(3): 404-413.
[13]	陈斐然, 陈彬, 朱正秋, 邱晓刚, 王一多, 赵勇. 基于博弈论的化工园区合作巡逻策略研究[J]. 系统仿真学报, 2020, 32(10): 1903-1909.
[14]	刘小虎, 张恒巍, 张玉臣, 马壮, 吕文雷. 基于博弈模型与NetLogo仿真的网络攻防态势研究[J]. 系统仿真学报, 2020, 32(10): 1918-1926.
[15]	林彬, 宋晨晨, 张雅静, 段建丽. 面向e-引航的近海边缘计算网络优化与仿真[J]. 系统仿真学报, 2020, 32(10): 1989-1996.