Offloading Algorithm for Multi-Agent and Double-Layer Offloading in Internet of Vehicle

doi:10.19678/j.issn.1000-3428.0068262

Abstract

Abstract:

In the edge computing environment of the Internet of Vehicles (IoV), with the aim of efficiently offloading tasks and allocating resources to alleviate the limited storage and computing power of vehicles, this study proposes a offloading algorithm based on multi-agent and double-layer offloading in IoV. A three-layer network model consisting of a Mobile Edge Computing (MEC) server, Vehicles, and Non-Task Vehicle Cloud(MEC-V-NTVC) interconnection is first proposed. Additionally, task, judgment, and calculation models are established. Second, the computational offloading and resource allocation of task vehicles are abstracted into a Partially Observable Markov Decision Process (POMDP), and a double-layer offloading mechanism is proposed to minimize the system cost. Applying a double-layer offloading mechanism and monotonic value function factorization for deep multi-agent reinforcement learning QMIX, a deep reinforcement learning offloading algorithm DLSQMIX based on the double-layer offloading mechanism is proposed, which coordinates task vehicles, non-task vehicles, and state information, considering the time constraint and cooperates with the computation power of the MEC and the non-task vehicle cloud, to learn optimal offloading decisions. The system overhead and latency are compared and explained in terms of the computing power of edge servers and non-task vehicles, number of task vehicles and non-task vehicles, and average task volume. The simulation experiment results demonstrate that the DLSQMIX algorithm can effectively solve the task-offloading problem. Compared with the Genetic Algorithm (GA), Particle Swarm Optimization (PSO) algorithm, and QMIX algorithm, the proposed algorithm reduces the system overhead by 2.52%-3.91% and latency by 3.50%-6.59%.

Key words: Internet of Vehicle(IoV), edge computing, non-task vehicle cloud, double-layer offloading mechanism, monotonic value function factorization

摘要：

在车联网(IoV)边缘计算环境中, 针对如何高效地进行任务卸载和资源分配来缓解移动车辆存储和计算能力有限的问题, 提出多智能体与双层卸载的IoV卸载算法。首先, 提出移动边缘计算(MEC)服务器与车辆以及空闲车辆(MEC-V-NTVC)互联的3层网络模型, 建立了任务模型、判断模型和计算模型; 其次, 将任务车辆的计算卸载以及资源分配抽象成部分可观测马尔可夫决策过程(POMDP), 并提出双层卸载机制以达到最小化系统总成本的目的。基于空闲车辆云以及单调值函数分解QMIX, 提出一种基于双层卸载机制的深度强化学习卸载算法DLSQMIX。该算法协调任务车辆、空闲车辆以及环境信息, 在考虑车辆任务时间约束的情况下, 充分利用MEC服务器以及空闲车辆的计算能力, 求得系统最优卸载决策。从边缘服务器、空闲车辆的计算能力、任务车辆、空闲车辆的数量以及平均任务量等方面对系统开销和时延进行对比。仿真实验结果表明, DLSQMIX算法能够有效求解任务卸载问题, 与遗传算法(GA)、粒子群优化(PSO)算法以及QMIX算法相比, 所提算法的系统开销减小2.52%~3.91%, 时延降低3.50%~6.59%。

关键词: 车联网, 边缘计算, 空闲车辆云, 双层卸载机制, 单调值函数分解

Ji ZHANG, Wenwen GONG, Chunhong DUO, Guoliang QI. Offloading Algorithm for Multi-Agent and Double-Layer Offloading in Internet of Vehicle[J]. Computer Engineering, 2024, 50(8): 182-197.

张冀, 龚雯雯, 朵春红, 齐国梁. 面向多智能体与双层卸载的车联网卸载算法[J]. 计算机工程, 2024, 50(8): 182-197.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0068262

https://www.ecice06.com/EN/Y2024/V50/I8/182

Figures/Tables 16

Fig.1 MEC-V-NTVC system model

Fig.2 Schematic diagram of judgement model

Fig.3 Schematic diagram of QMIX algorithm structure

Fig.4 Flowchart of DLSQMIX algorithm

Fig.5 Network training under different learning rates

Fig.6 Network training under different batch sizes

Fig.7 The impact of delay weight factor on delay and energy consumption

Fig.8 The impact of average task volume on system overhead, task offloading quantity and system latency

Fig.9 The impact of MEC server computing power on system overhead and task offloading quantity

Fig.10 The impact of the number of task vehicles on system overhead and task offloading quantity

Fig.11 The impact of the number of non-task vehicles on system overhead and task offloading quantity

Fig.12 The impact of the number of non-task vehicles on system latency and offloading ratio

Fig.13 The impact of non-task vehicle computing power on system overhead and task offloading quantity

Fig.14 The impact of vehicle speed on system overhead and non-task vehicle load

References 40

1	ZHANG K, MAO Y M, LENG S P, et al. Mobile-edge computing for vehicular networks: a promising network paradigm with predictive off-loading. IEEE Vehicular Technology Magazine, 2017, 12(2): 36- 44. doi: 10.1109/MVT.2017.2668838
2	蔡星娟, 郭彦亨, 赵天浩, 等. 基于进化多任务的边缘计算服务部署和任务卸载. 计算机工程, 2023, 49(7): 1- 9. doi: 10.19678/j.issn.1000-3428.0066105
	CAI X J, GUO Y H, ZHAO T H, et al. Edge computing service deployment and task offloading based on evolutionary multitasking. Computer Engineering, 2023, 49(7): 1- 9. doi: 10.19678/j.issn.1000-3428.0066105
3	LIU Q L, LUO R, LIU Q. Mobility-aware computation offloading for cloud-assisted mobile edge computing in vehicular networks[C]//Proceedings of the IEEE 96th Vehicular Technology Conference (VTC2022-Fall). Washington D. C., USA: IEEE Press, 2022: 1-7.
4	张丙鑫. 基于无人机的移动边缘计算资源调度机制研究[D]. 徐州: 中国矿业大学, 2020.
	ZHANG B X. Research on resource scheduling mechanism of mobile edge computing based on UAV[D]. Xuzhou: China University of Mining and Technology, 2020. (in Chinese)
5	SORKHOH I, EBRAHIMI D, ATALLAH R, et al. Workload scheduling in vehicular networks with edge cloud capabilities. IEEE Transactions on Vehicular Technology, 2019, 68(9): 8472- 8486. doi: 10.1109/TVT.2019.2927634
6	XU X L, LIU Q X, LUO Y, et al. A computation offloading method over big data for IoT-enabled cloud-edge computing. Future Generation Computer Systems, 2019, 95(C): 522- 533.
7	WANG J, WU W B, LIAO Z F, et al. A probability preferred priori offloading mechanism in mobile edge computing. IEEE Access, 2020, 8, 39758- 39767. doi: 10.1109/ACCESS.2020.2975733
8	陈刚, 王志坚, 徐胜超. 基于可行点追踪-连续凸逼近的移动边缘计算任务卸载. 计算机与现代化, 2023,(8): 93- 97. URL
	CHEN G, WANG Z J, XU S C. Mobile edge computing task offloading based on feasible point tracking continuous convex approximation. Computer and Modernization, 2023,(8): 93- 97. URL
9	薛建彬, 丁雪乾, 刘星星. 缓存辅助边缘计算的卸载决策与资源优化. 北京邮电大学学报, 2020, 43(3): 32- 37. URL
	XUE J B, DING X Q, LIU X X. Offloading decision and resource optimization for cache-assisted edge computing. Journal of Beijing University of Posts and Telecommunications, 2020, 43(3): 32- 37. URL
10	KHAYYAT M, ELGENDY I A, MUTHANNA A, et al. Advanced deep learning-based computational offloading for multilevel vehicular edge-cloud computing networks. IEEE Access, 2020, 8, 137052- 137062. doi: 10.1109/ACCESS.2020.3011705
11	XIONG K, LENG S P, HUANG C W, et al. Intelligent task offloading for heterogeneous V2X communications. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(4): 2226- 2238. doi: 10.1109/TITS.2020.3015210
12	KE H C, WANG J, DENG L Y, et al. Deep reinforcement learning-based adaptive computation offloading for MEC in heterogeneous vehicular networks. IEEE Transaction on Vehicular Technology, 2020, 69(7): 7916- 7929. doi: 10.1109/TVT.2020.2993849
13	GUO Y X, NING Z L, KWOK R. Deep reinforcement learning based traffic offloading scheme for vehicular networks[C]//Proceedings of the 5th International Conference on Computer and Communications (ICCC). Washington D. C., USA: IEEE Press, 2019: 81-85.
14	于晶, 鲁凌云, 李翔. 车联网中基于DDQN的边云协作任务卸载机制. 计算机工程, 2022, 48(12): 156- 164. doi: 10.19678/j.issn.1000-3428.0063739
	YU J, LU L Y, LI X. Edge-cloud collaborative task offloading mechanism based on DDQN in vehicular networks. Computer Engineering, 2022, 48(12): 156- 164. doi: 10.19678/j.issn.1000-3428.0063739
15	WANG D, QIN H, SONG B, et al. Resource allocation in information-centric wireless networking with D2D-enabled MEC: a deep reinforcement learning approach. IEEE Access, 1829, 7, 114935- 114944.
16	LIAO H J, ZHOU Z Y, ZHAO X W, et al. Task offloading for vehicular fog computing under information uncertainty: a matching-learning approach[C]//Proceedings of the 15th International Wireless Communications & Mobile Computing Conference (IWCMC). Washington D. C., USA: IEEE Press, 2019: 2001-2006.
17	XU X L, ZHANG X, LIU X H, et al. Adaptive computation offloading with edge for 5G-envisioned Internet of connected vehicles. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(8): 5213- 5222. doi: 10.1109/TITS.2020.2982186
18	WU Y L, WU J G, CHEN L, et al. Fog computing model and efficient algorithms for directional vehicle mobility in vehicular network. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(5): 2599- 2614. doi: 10.1109/TITS.2020.2971343
19	ZHANG J, GUO H Z, LIU J J, et al. Task offloading in vehicular edge computing networks: a load-balancing solution. IEEE Transactions on Vehicular Technology, 2020, 69(2): 2092- 2104. doi: 10.1109/TVT.2019.2959410
20	WANG X J, NING Z L, WANG L. Offloading in Internet of vehicles: a fog-enabled real-time traffic management system. IEEE Transactions on Industrial Informatics, 2018, 14(10): 4568- 4578. doi: 10.1109/TII.2018.2816590
21	LI S L, ZHAI D S, DU P F, et al. Energy-efficient task offloading, load balancing, and resource allocation in mobile edge computing enabled IoT networks. Science China Information Sciences, 2018, 62(2): 29307.
22	YU Z Y, TANG Y L, ZHANG L T, et al. Deep reinforcement learning based computing offloading decision and task scheduling in Internet of vehicles[C]//Proceedings of the IEEE/CIC International Conference on Communications in China (ICCC). Washington D. C., USA: IEEE Press, 2021: 1166-1171.
23	SUN J N, GU Q, ZHENG T, et al. Joint optimization of computation offloading and task scheduling in vehicular edge computing networks. IEEE Access, 2020, 8, 10466- 10477. doi: 10.1109/ACCESS.2020.2965620
24	LIU Y J, WANG S G, HUANG J, et al. A computation offloading algorithm based on game theory for vehicular edge networks[C]//Proceedings of the IEEE International Conference on Communications (ICC). Washington D. C., USA: IEEE Press, 2018: 1-6.
25	HE W, YAN G J, XU L D. Developing vehicular data cloud services in the IoT environment. IEEE Transactions on Industrial Informatics, 2014, 10(2): 1587- 1595. doi: 10.1109/TII.2014.2299233
26	AL-RASHED E, AL-ROUSAN M, AL-IBRAHIM N. Performance evaluation of wide-spread assignment schemes in a vehicular cloud. Vehicular Communications, 2017, 9, 144- 153. doi: 10.1016/j.vehcom.2017.05.005
27	HU X Y, TANG X K, YU Y T, et al. Joint load balancing and offloading optimization in multiple parked vehicle-assisted edge computing. Wireless Communications and Mobile Computing, 2021, 2021, 8943862. doi: 10.1155/2021/8943862
28	NGUYEN D C, PATHIRANA P N, DING M, et al. Deep reinforcement learning for collaborative offloading in heterogeneous edge networks[C]//Proceedings of the 21st International Symposium on Cluster, Cloud and Internet Computing (CCGrid). Washington D. C., USA: IEEE Press, 2021: 297-303.
29	HUANG X Y, LENG S P, MAHARJAN S, et al. Multi-agent deep reinforcement learning for computation offloading and interference coordination in small cell networks. IEEE Transactions on Vehicular Technology, 2021, 70(9): 9282- 9293. doi: 10.1109/TVT.2021.3096928
30	LI S L, LI B G, ZHAO W. Joint optimization of caching and computation in multi-server NOMA-MEC system via reinforcement learning. IEEE Access, 2020, 8, 112762- 112771. doi: 10.1109/ACCESS.2020.3002895
31	GAN Z Y, LIN R H, ZOU H. A multi-agent deep reinforcement learning approach for computation offloading in 5G mobile edge computing[C]//Proceedings of the 22nd IEEE International Symposium on Cluster, Cloud and Internet Computing (CCGrid). Washington D. C., USA: IEEE Press, 2022: 645-648.
32	叶佩文, 贾向东, 杨小蓉, 等. 面向车联网的多智能体强化学习边云协同卸载. 计算机工程, 2021, 47(4): 13- 20. doi: 10.19678/j.issn.1000-3428.0058323
	YE P W, JIA X D, YANG X R, et al. Collaborative edge and cloud offloading for Internet of vehicles using multi-agent reinforcement learning. Computer Engineering, 2021, 47(4): 13- 20. doi: 10.19678/j.issn.1000-3428.0058323
33	杨超, 王宗山, 聂仁灿, 等. 车联网中基于麻雀搜索算法的计算卸载策略. 计算机工程与设计, 2023, 44(1): 1- 7. URL
	YANG C, WANG Z S, NIE R C, et al. Computing offloading strategy based on sparrow search algorithm in vehicular networks. Computer Engineering and Design, 2023, 44(1): 1- 7. URL
34	丛玉良, 孙闻晞, 薛科, 等. 基于改进的混合遗传算法的车联网任务卸载策略研究. 通信学报, 2022, 43(10): 77- 85. URL
	CONG Y L, SUN W X, XUE K, et al. Research on task offloading strategy of Internet of vehicles based on improved hybrid genetic algorithm. Journal on Communications, 2022, 43(10): 77- 85. URL
35	景泽伟, 杨清海, 秦猛. 移动边缘计算中的时延和能耗均衡优化算法. 北京邮电大学学报, 2020, 43(2): 110- 115. URL
	JING Z W, YANG Q H, QIN M. A delay and energy tradeoff optimization algorithm for task offloading in mobile-edge computing networks. Journal of Beijing University of Posts and Telecommunications, 2020, 43(2): 110- 115. URL
36	LI J, GAO H, LV T J, et al. Deep reinforcement learning based computation offloading and resource allocation for MEC[C]//Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC). Washington D. C., USA: IEEE Press, 2018: 1-6.
37	RASHID T, SAMVELYAN M, SCHROEDER DE WITT C, et al. QMIX: monotonic value function factorisation for deep multi-agent reinforcement learning[EB/OL]. [2023-07-12]. https://arxiv.org/pdf/1803.11485.
38	王珺, 刘家豪, 宋巧凤. 一种基于遗传算法的车载边缘计算卸载方案. 南京邮电大学学报(自然科学版), 2022, 42(6): 1- 9. URL
	WANG J, LIU J H, SONG Q F. An offloading scheme of vehicle edge computing based on the genetic algorithm. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2022, 42(6): 1- 9. URL
39	林峰, 罗铖文, 丁鹏举, 等. 车联网中自适应联合计算卸载资源分配算法. 计算机工程与设计, 2021, 42(7): 1824- 1830. URL
	LIN F, LUO C W, DING P J, et al. Resource allocation algorithm for adaptive joint computing offloading in C-V2X. Computer Engineering and Design, 2021, 42(7): 1824- 1830. URL
40	HESSEL M, MODAYIL J, VAN HASSELT H, et al. Rainbow: combining improvements in deep reinforcement learning[EB/OL]. [2023-07-12]. https://arxiv.org/pdf/1710.02298.

[1]	ZHANG Junna, LI Tianze, ZHAO Xiaoyan, YUAN Peiyan. A Decentralized Priority Offloading Strategy Based on DQN [J]. Computer Engineering, 2024, 50(9): 235-245.
[2]	Junhui ZHOU, Peng XU, Shengli SUN. A Service Strategy Based on Age of Information Optimization in Collaborative Perception Systems [J]. Computer Engineering, 2024, 50(8): 165-181.
[3]	Qiong SHI, Hui DUAN, Zhibin SHI. Trusted Task Offloading Scheme Based on Deep Reinforcement Learning [J]. Computer Engineering, 2024, 50(8): 142-152.
[4]	Jiao CHEN, Yan SHEN. Research on Task Offloading of Mobile Edge Computing for Caching Mechanism [J]. Computer Engineering, 2024, 50(7): 194-203.
[5]	ZHAO Yuntao, XIAO Junjie, LI Weigang, XIONG Yating. Research on Information Code Correction Based on Improved PPYOLOE-R [J]. Computer Engineering, 2024, 50(6): 358-366.
[6]	Yaoping ZENG, Yuting XIA, Weiwei JIANG, Yueqiang LIU. Research on UAV-Assisted Mobile Edge Computing Strategy with Weighted Energy Minimization [J]. Computer Engineering, 2024, 50(2): 288-297.
[7]	WAN Haonan, WU Fei, YIN Ling. Time-Saving Deployment Optimization Algorithm Based on the Number of Adaptive Drones [J]. Computer Engineering, 2024, 50(10): 302-312.
[8]	YANG Jianjun, TANG Dongming, LI Juguang, XIAO Yufeng. Task Offloading Strategy of MEC Based on Improved Artificial Hummingbird Algorithm [J]. Computer Engineering, 2024, 50(10): 291-301.
[9]	ZHANG Junna, HAN Chaochen, CHEN Jiawei, ZHAO Xiaoyan, YUAN Peiyan. A Method for Joint Edge Server Deployment and Service Placement [J]. Computer Engineering, 2024, 50(10): 266-280.
[10]	Xiuyu SHEN, Weifeng JI, Yingqi LI, Xuan WU. TCA1C DDoS Detection Model for Edge Computing [J]. Computer Engineering, 2024, 50(1): 198-205.
[11]	Shiming PENG, Shiyang LIN, Shuo JIA, Miaohui YANG. Multi-Objective Optimization Task Offloading Strategy Based on Load Prediction [J]. Computer Engineering, 2024, 50(1): 206-215.
[12]	Yuqi BAN, Liguo DUAN, Haoyu WEN, Aiping LI, Jumin ZHAO. Research on Mobility-Aware Computation Offloading and Resource Allocation Strategy [J]. Computer Engineering, 2023, 49(8): 163-173.
[13]	Jing MEI, Longbao DAI, Zhao TONG, Xin DENG, Jiake WANG. Adaptive Offloading Algorithm Based on Lyapunov Optimization Under Resource Constraints [J]. Computer Engineering, 2023, 49(7): 34-46.
[14]	Xingjuan CAI, Yanheng GUO, Tianhao ZHAO, Wensheng ZHANG. Edge Computing Service Deployment and Task Offloading Based on Evolutionary Multitasking [J]. Computer Engineering, 2023, 49(7): 1-9.
[15]	LI Qiang, YI Jinhui, DU Tingting, WANG Shengchun. Dependent Task Offloading and Resource Allocation Based on A3C in Mobile Edge Computing [J]. Computer Engineering, 2023, 49(6): 42-52.

Please choose a citation manager

Content to export