基于博弈论和启发式算法的超密集网络边缘计算卸载

doi:10.19678/j.issn.1000-3428.0063734

摘要/Abstract

摘要： 超密集网络与边缘计算相结合时，高密度的基站分布可能会对同一用户重复覆盖，该用户选择不同基站进行卸载将会对系统性能产生不同影响，由此引出卸载对象选取问题。同时边缘计算可以将部分任务卸载到边缘服务器进行处理，选择合适的卸载比例能够显著降低所需的时延和能耗，由此引出卸载比例选取问题。提出一种超密集网络环境中基于博弈论和启发式算法的边缘计算卸载策略。针对卸载对象选取问题，根据边缘服务器到用户之间的距离和工作负载定义偏好度指标，各用户根据偏好度进行博弈后选择卸载对象，并对用户进行分组，将原问题分解为若干个并行的子问题。针对卸载比例选取问题，基于萤火虫群优化算法对各用户的卸载比例进行优化，得到适当的卸载比例。与全本地处理（ALP）策略、全卸载策略（AOS）和基于粒子群优化（PSO）算法的卸载策略进行对比，实验结果表明，ALP和AOS策略在总能耗和平均时延上具有一定的局限性，相比基于PSO的卸载策略，所提策略的时延降低22%，能耗降低20%，可以有效减少系统损失。

关键词: 边缘计算, 计算卸载, 超密集网络, 博弈论, 萤火虫群优化算法

Abstract: When an Ultra-Dense Network(UDN) is combined with edge computing, the distribution of high-density base stations may repeatedly cover the same user.The base station chosen by the user for offloading affects the system's performance, which leads to the problem of offloading object selection.Simultaneously, edge computing can offload tasks to the edge server for processing.Choosing an appropriate offloading proportion significantly reduces the required delay and energy consumption;thus, selecting the offloading proportion is a challenge.An edge computing offloading strategy based on game theory and a heuristic algorithm in a UDN environment is proposed.For the offloading object selection problem, the preference function is first defined according to the distance between the edge server, user, and workload.Each user then selects the offloading object after playing a game according to their preference and groups the users.The original problem is decomposed into several parallel subproblems.To address the problem of offloading proportion selection, the offloading proportion of each user is optimized based on the Glowworm Swarm Optimization(GSO) algorithm, and the appropriate offloading proportion is obtained.Through a simulation experiment, compared with the All-Local Processing(ALP) strategy, All-Offloading Strategy(AOS), and offloading strategy based on Particle Swarm Optimization(PSO) algorithm, the delay and energy consumption of the ALP and AOS strategies have certain limitations in terms of the total energy consumption and average delay, respectively.Compared with the offloading strategy based on PSO, the delay of the proposed strategy is reduced by 22% and the energy consumption is reduced by 20%.Experimental results show that this strategy can effectively reduce system loss.

Key words: edge computing, computing offloading, Ultra-Dense Network(UDN), game theory, Glowworm Swarm Optimization (GSO) algorithm

中图分类号:

TP393

刘振鹏, 郭超, 王仕磊, 陈杰, 李小菲. 基于博弈论和启发式算法的超密集网络边缘计算卸载[J]. 计算机工程, 2022, 48(12): 54-61,71.

LIU Zhenpeng, GUO Chao, WANG Shilei, CHEN Jie, LI Xiaofei. Edge Computing Offloading of Ultra-Dense Network Based on Game Theory and Heuristic Algorithm[J]. Computer Engineering, 2022, 48(12): 54-61,71.

http://www.ecice06.com/CN/Y2022/V48/I12/54

图/表 10

20230112182531

20230112182535

20230112182539

20230112182543

20230112182547

20230112182551

20230112182556

20230112182600

20230112182604

20230112182608

参考文献

[1] YE Q, ZHUANG W H, LI X, et al.End-to-end delay modeling for embedded VNF chains in 5G core networks[J].IEEE Internet of Things Journal, 2019, 6(1):692-704.
[2] HUANG H, XIA W C, XIONG J, et al.Unsupervised learning-based fast beamforming design for downlink MIMO[J].IEEE Access, 2018, 7:7599-7605.
[3] KUANG Z F, MA Z H, LI Z, et al.Cooperative computation offloading and resource allocation for delay minimization in mobile edge computing[J].Journal of Systems Architecture, 2021, 118:102167.
[4] ABBAS N, ZHANG Y, TAHERKORDI A, et al.Mobile edge computing:a survey[J].IEEE Internet of Things Journal, 2018, 5(1):450-465.
[5] CHATZOPOULOS D, BERMEJO C, KOSTA S, et al.Offloading computations to mobile devices and cloudlets via an upgraded NFC communication protocol[J].IEEE Transactions on Mobile Computing, 2020, 19(3):640-653.
[6] YOU C S, HUANG K B, CHAE H.Energy efficient mobile cloud computing powered by wireless energy transfer[J].IEEE Journal on Selected Areas in Communications, 2016, 34(5):1757-1771.
[7] 陈清林, 邝祝芳.基于DDPG的边缘计算任务卸载和服务缓存算法[J].计算机工程, 2021, 47(10):26-33. CHEN Q L, KUANG Z F.Task offloading and service caching algorithm based on DDPG in edge computing[J].Computer Engineering, 2021, 47(10):26-33.(in Chinese)
[8] WU Z Y, YAN D F.Deep reinforcement learning-based computation offloading for 5G vehicle-aware multi-access edge computing network[J].China Communications, 2021, 18(11):26-41.
[9] 张依琳, 梁玉珠, 尹沐君, 等.移动边缘计算中计算卸载方案研究综述[J].计算机学报, 2021, 44(12):2406-2430. ZHANG Y L, LIANG Y Z, YIN M J, et al.Survey on the methods of computation offloading in mobile edge computing[J].Chinese Journal of Computers, 2021, 44(12):2406-2430.(in Chinese)
[10] GE X H, TU S, MAO G Q, et al.5G ultra-dense cellular networks[J].IEEE Wireless Communications, 2016, 23(1):72-79.
[11] KAMEL M, HAMOUDA W, YOUSSEF A.Ultra-dense networks:a survey[J].IEEE Communications Surveys & Tutorials, 2016, 18(4):2522-2545.
[12] AN J P, YANG K, WU J S, et al.Achieving sustainable ultra-dense heterogeneous networks for 5G[J].IEEE Communications Magazine, 2017, 55(12):84-90.
[13] 张海波, 李虎, 陈善学, 等.超密集网络中基于移动边缘计算的任务卸载和资源优化[J].电子与信息学报, 2019, 41(5):1194-1201. ZHANG H B, LI H, CHEN S X, et al.Computing offloading and resource optimization in ultra-dense networks with mobile edge computation[J].Journal of Electronics & Information Technology, 2019, 41(5):1194-1201.(in Chinese)
[14] 王雪, 刘京, 孙佳妮, 等.基于谱聚类的异构蜂窝超密集网络高能效资源分配算法[J].通信学报, 2021, 42(7):162-175. WANG X, LIU J, SUN J N, et al.Spectral clustering-based energy-efficient resource allocation algorithm in heterogeneous cellular ultra-dense network[J].Journal on Communications, 2021, 42(7):162-175.(in Chinese)
[15] 王刚, 于银辉, 杨莹.超密集网络中基于集群分配的干扰管理与资源分配[J].吉林大学学报(理学版), 2021, 59(5):1228-1236. WANG G, YU Y H, YANG Y.Interference management and resource allocation based on cluster allocation in ultra-dense network[J].Journal of Jilin University (Science Edition), 2021, 59(5):1228-1236.(in Chinese)
[16] CHEN Y, ZHANG N, ZHANG Y C, et al.TOFFEE:task offloading and frequency scaling for energy efficiency of mobile devices in mobile edge computing[J].IEEE Transactions on Cloud Computing, 2021, 9(4):1634-1644.
[17] LIU C F, BENNIS M, POOR H V.Latency and reliability-aware task offloading and resource allocation for mobile edge computing[C]//Proceedings of IEEE Globecom Workshops.Washington D.C., USA:IEEE Press, 2017:1-7.
[18] LIU C F, BENNIS M, DEBBAH M, et al.Dynamic task offloading and resource allocation for ultra-reliable low-latency edge computing[J].IEEE Transactions on Communications, 2019, 67(6):4132-4150.
[19] GUO H Z, LIU J J, ZHANG J, et al.Mobile-edge computation offloading for ultradense IoT networks[J].IEEE Internet of Things Journal, 2018, 5(6):4977-4988.
[20] ZHOU S C, JADOON W.Jointly optimizing offloading decision and bandwidth allocation with energy constraint in mobile edge computing environment[J].Computing, 2021, 103(12):2839-2865.
[21] LYU X C, TIAN H, SENGUL C, et al.Multiuser joint task offloading and resource optimization in proximate clouds[J].IEEE Transactions on Vehicular Technology, 2017, 66(4):3435-3447.
[22] CHEN M, HAO Y X.Task offloading for mobile edge computing in software defined ultra-dense network[J].IEEE Journal on Selected Areas in Communications, 2018, 36(3):587-597.
[23] DENG Y Q, CHEN Z G, YAO X, et al.Task scheduling for smart city applications based on multi-server mobile edge computing[J].IEEE Access, 2019, 7:14410-14421.
[24] 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.
[25] FENG S L, CHEN Y J, ZHAI Q H, et al.Optimizing computation offloading strategy in mobile edge computing based on swarm intelligence algorithms[J].EURASIP Journal on Advances in Signal Processing, 2021(1):36.
[26] BOUET M, CONAN V.Mobile edge computing resources optimization:a geo-clustering approach[J].IEEE Transactions on Network and Service Management, 2018, 15(2):787-796.
[27] CARVALHO G H S, WOUNGANG I, ANPALAGAN A, et al.Analysis of joint parallelism in wireless and cloud domains on mobile edge computing over 5G systems[J].Journal of Communications and Networks, 2018, 20(6):565-577.
[28] TANG L, HE S B.Multi-user computation offloading in mobile edge computing:a behavioral perspective[J].IEEE Network, 2018, 32(1):48-53.
[29] JOŠILO S, DÁN G.A game theoretic analysis of selfish mobile computation offloading[C]//Proceedings of 2017 IEEE Conference on Computer Communications.Washington D.C., USA:IEEE Press, 2017:1-9.
[30] LIAO Z F, PENG J S, XIONG B, et al.Adaptive offloading in mobile-edge computing for ultra-dense cellular networks based on genetic algorithm[J].Journal of Cloud Computing, 2021, 10:15.

选择文件类型/文献管理软件名称

选择包含的内容