Adaptive Offloading Algorithm Based on Lyapunov Optimization Under Resource Constraints

doi:10.19678/j.issn.1000-3428.0067064

Abstract

Abstract:

In Mobile Edge Computing (MEC), computing, storage, network resources, and services are relegated to the edge of the network, allowing users to process tasks on edge servers. However, in practical applications, the amount of task offloading requested by users and the state of wireless channels constantly change over time, which poses challenges to task offloading and resource allocation, as computing and communication resources are limited. To address this issue, a system utility optimization model is constructed to handle dynamic environments under resource constraints. In this model, each terminal device is equipped with energy harvesting devices, fully utilizing external renewable energy to support system processing tasks.The dependence of optimization models on uncertain information is eliminated using Lyapunov optimization theory, whereby the original optimization objective that relies on unknown information is transformed into an optimization problem that only relies on the current time slice system information. This optimization is an NP-hard problem, which is proved using the reduction method.Subsequently, Deep Reinforcement Learning(DRL) method is used to design an adaptive unloading algorithm, LyUO, under resource constraints. When the system dynamic information is unknown, this algorithm is responsible for the near optimal task unloading decision and the MEC server communication/computing resource allocation strategy in real time.The simulation results show that the LyUO algorithm can keep the task queue stable for all devices in the system even when the task arrival rate and wireless channel state change, improving the system utility by about 15% compared to the benchmark algorithm while meeting the long-term constraints of the queue.

Key words: Mobile Edge Computing(MEC), adaptive offloading algorithm, Lyapunov optimization theory, Deep Reinforcement Learning(DRL), system stability, resource allocation

摘要：

移动边缘计算（MEC）将计算、存储、网络资源和服务向网络边缘下沉，并允许用户在边缘服务器上处理任务。然而，在实际应用中，用户请求的任务卸载量和无线信道状态随时间不断变化，同时计算和通信资源受限也对任务卸载和资源分配任务带来了挑战。针对该问题，构建一种资源约束下面向动态环境的系统效用优化模型。该模型中各个终端设备均配备能量收集装置，充分利用外界可再生能源来支持系统处理任务。运用Lyapunov优化理论消除优化模型对不确定信息的依赖，将原依赖未知信息的目标优化问题转化为只依赖当前时间片系统信息的优化问题，使用归约法证明该优化问题为一个NP-hard问题。结合深度强化学习方法设计一种资源约束下的自适应卸载算法LyUO，该算法在系统动态信息未知的情况下实时确定近优任务卸载决策及MEC服务器通信/计算资源分配策略。仿真结果表明，LyUO算法在任务到达率和无线信道状态变化时可使系统中所有设备的任务队列保持稳定，在满足队列长期约束的同时使系统效用较基准算法提升约15%。

关键词: 移动边缘计算, 自适应卸载算法, Lyapunov优化理论, 深度强化学习, 系统稳定, 资源分配

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.

梅晶, 戴龙宝, 童钊, 邓昕, 王嘉珂. 资源约束下基于Lyapunov优化的自适应卸载算法[J]. 计算机工程, 2023, 49(7): 34-46.

/ Recommend / Download Citations

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

https://www.ecice06.com/EN/Y2023/V49/I7/34

Figures/Tables 16

Fig.1 MEC scenario with multiple IoT devices

Fig.2 The procedure of LyUO algorithm

Table 1 Parameter settings for simulation experiments

参数	含义	设置
$ T $/s	系统时隙长度	1
$ B $/MHz	用户上行带宽	2
$ {\varphi }_{i} $	设备计算1 bit数据所需要的CPU周期数	100
$ f $/MHz	用户i的CPU主频	150
$ {p}_{i}^{t} $/mW	用户i的传输功率	U[300, 500]
$ \phi $	MEC计算1 bit数据所需要的CPU周期数	100
$ {F}_{M, \mathrm{m}\mathrm{a}\mathrm{x}}^{} $/GHz	MEC最大CPU主频	4
$ \alpha $	系统处理1 Mb数据的收益	0.1
$ \beta $	系统消耗1 J能量所需要的费用	0.6
$ \chi $/J	用户收集能量的期望	0.08

Fig.3 Training loss values

Fig.4 User average queue length 1

Fig.5 MEC average queue length 1

Fig.6 System average utility 1

Fig.7 User average queue length 2

Fig.8 MEC average queue length 2

Fig.9 System average utility 2

Fig.10 User average queue length 3

Fig.11 MEC average queue length 3

Fig.12 System average utility 3

Fig.13 User average queue length 4

Fig.14 MEC average queue length 4

Fig.15 System average utility 4

References 29

1	田秀霞, 杨明夷. 家庭物联网中基于智能合约的访问控制机制. 计算机工程, 2023, 49(3): 18- 28. URL
	TIAN X X, YANG M Y. Smart contract-based access control mechanism in home IoT. Computer Engineering, 2023, 49(3): 18- 28. URL
2	李雪松, 张锲石, 宋呈群, 等. 自动驾驶场景下的轨迹预测技术综述. 计算机工程, 2023, 49(5): 1- 11. URL
	LI X S, ZHANG Q S, SONG C Q, et al. Review of trajectory prediction technology in autonomous driving scenes. Computer Engineering, 2023, 49(5): 1- 11. URL
3	邓晓衡, 关培源, 万志文, 等. 基于综合信任的边缘计算资源协同研究. 计算机研究与发展, 2018, 55(3): 449- 477. URL
	DENG X H, GUAN P Y, WAN Z W, et al. Integrated trust based resource cooperation in edge computing. Journal of Computer Research and Development, 2018, 55(3): 449- 477. URL
4	MEI J, DAI L B, TONG Z, et al. Throughput-aware dynamic task offloading under resource constant for MEC with energy harvesting devices. IEEE Transactions on Network and Service Management, 2023, 12, 1- 14.
5	张依琳, 梁玉珠, 尹沐君, 等. 移动边缘计算中计算卸载方案研究综述. 计算机学报, 2021, 44(12): 2406- 2430. URL
	ZHANG Y L, LIANG Y Z, YIN M J, et al. Survey on the methods of computation of loading in mobile edge computing. Chinese Journal of Computers, 2021, 44(12): 2406- 2430. URL
6	谢娜, 谭文安, 曹彦, 等. 移动边缘计算中安全信息流建模与分析. 计算机工程, 2022, 48(5): 35-42, 52 URL
	XIE N, TAN W A, CAO Y, et al. Modeling and analysis of security information flow in mobile edge computing. Computer Engineering, 2022, 48(5): 35-42, 52 URL
7	DUAN H Y, ZHENG Y F, WANG C, et al. Treasure collection on foggy islands: building secure network archives for Internet of Things. IEEE Internet of Things Journal, 2019, 6(2): 2637- 2650. doi: 10.1109/JIOT.2018.2872461
8	LIU J, MAO Y Y, ZHANG J, et al. Delay-optimal computation task scheduling for mobile-edge computing systems[C]//Proceedings of IEEE International Symposium on Information Theory. Washington D. C., USA: IEEE Press, 2016: 1451-1455.
9	ZHOU W, XING L, XIA J J, et al. Dynamic computation offloading for MIMO mobile edge computing systems with energy harvesting. IEEE Transactions on Vehicular Technology, 2021, 70(5): 5172- 5177.
10	DINH T Q, TANG J H, LA Q D, et al. Offloading in mobile edge computing: task allocation and computational frequency scaling. IEEE Transactions on Communications, 2017, 65(8): 3571- 3584.
11	BI S Z, ZHANG Y J. Computation rate maximization for wireless powered mobile-edge computing with binary computation offloading. IEEE Transactions on Wireless Communications, 2018, 17(6): 4177- 4190. doi: 10.1109/TWC.2018.2821664
12	DU J, JIANG C X, WANG J, et al. Machine learning for 6G wireless networks: carrying forward enhanced bandwidth, massive access, and ultrareliable/low-latency service. IEEE Vehicular Technology Magazine, 2020, 15(4): 122- 134.
13	ZHANG J, SHEN Y, WANG Y, et al. Dual-timescale resource allocation for collaborative service caching and computation offloading in IoT systems. IEEE Transactions on Industrial Informatics, 2023, 19(2): 1735- 1746.
14	LÜ X C, TIAN H, SENGUL C, et al. Multiuser joint task offloading and resource optimization in proximate clouds. IEEE Transactions on Vehicular Technology, 2017, 66(4): 3435- 3447.
15	DAI S J, WANG M L, GAO Z B, et al. An adaptive computation offloading mechanism for mobile health applications. IEEE Transactions on Vehicular Technology, 2020, 69(1): 998- 1007.
16	QIU C R, HU Y, CHEN Y. Lyapunov optimized cooperative communications with stochastic energy harvesting relay. IEEE Internet of Things Journal, 2018, 5(2): 1323- 1333.
17	CHEN Y, ZHANG N, ZHANG Y C, et al. Energy efficient dynamic offloading in mobile edge computing for Internet of Things. IEEE Transactions on Cloud Computing, 2021, 9(3): 1050- 1060.
18	BI S Z, HUANG L, WANG H, et al. Lyapunov-guided deep reinforcement learning for stable online computation offloading in mobile-edge computing networks. IEEE Transactions on Wireless Communications, 2021, 20(11): 7519- 7537.
19	XIA S C, YAO Z X, LI Y, et al. Online distributed offloading and computing resource management with energy harvesting for heterogeneous MEC-enabled IoT. IEEE Transactions on Wireless Communications, 2021, 20(10): 6743- 6757.
20	ZHAO F J, CHEN Y, ZHANG Y C, et al. Dynamic offloading and resource scheduling for mobile-edge computing with energy harvesting devices. IEEE Transactions on Network and Service Management, 2021, 18(2): 2154- 2165.
21	刘振鹏, 郭超, 王仕磊, 等. 基于博弈论和启发式算法的超密集网络边缘计算卸载. 计算机工程, 2022, 48(12): 54-61, 71 URL
	LIU Z P, GUO C, WANG S L, et al. Edge computing offloading of ultra-dense network based on game theory and heuristic algorithm. Computer Engineering, 2022, 48(12): 54-61, 71 URL
22	ZHANG G L, ZHANG W Q, CAO Y, et al. Energy-delay tradeoff for dynamic offloading in mobile-edge computing system with energy harvesting devices. IEEE Transactions on Industrial Informatics, 2018, 14(10): 4642- 4655.
23	杨天, 田霖, 孙茜, 等. 移动边缘计算中基于用户体验的计算卸载方案. 计算机工程, 2020, 46(10): 33- 40. URL
	YANG T, TIAN L, SUN Q, et al. Computing offloading scheme based on user experience in mobile edge computing. Computer Engineering, 2020, 46(10): 33- 40. URL
24	TONG Z, CAI J H, MEI J, et al. Dynamic energy-saving offloading strategy guided by Lyapunov optimization for IoT devices. IEEE Internet of Things Journal, 2022, 9(20): 19903- 19915.
25	NEELY M J. Stochastic network optimization with application to communication and queueing systems. Synthesis Lectures on Communication Networks, 2010, 3(1): 1- 211.
26	KU M L, LI W, CHEN Y, et al. Advances in energy harvesting communications: past, present, and future challenges. IEEE Communications Surveys & Tutorials, 2016, 18(2): 1384- 1412.
27	MAO Y Y, ZHANG J, SONG S H, et al. Stochastic joint radio and computational resource management for multi-user mobile-edge computing systems. IEEE Transactions on Wireless Communications, 2017, 16(9): 5994- 6009.
28	KARP R M. Reducibility among combinatorial problems. Berlin, Germany: Springer, 2010.
29	MARSLAND S. Machine learning: an algorithmic perspective. [S. l. ]: CRC Press, 2015.

[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]	Qiong SHI, Hui DUAN, Zhibin SHI. Trusted Task Offloading Scheme Based on Deep Reinforcement Learning [J]. Computer Engineering, 2024, 50(8): 142-152.
[3]	Jiao CHEN, Yan SHEN. Research on Task Offloading of Mobile Edge Computing for Caching Mechanism [J]. Computer Engineering, 2024, 50(7): 194-203.
[4]	FU Mingjian, GUO Fuqiang. Research on Decision-Making at Intersection Without Traffic Lights Based on Deep Reinforcement Learning [J]. Computer Engineering, 2024, 50(5): 91-99.
[5]	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.
[6]	Haijun DU, Su YU. Dynamic Obstacle Avoidance for Service Robots Based on Spatio-Temporal Graph Attention Network [J]. Computer Engineering, 2024, 50(2): 105-112.
[7]	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.
[8]	Ziyue CAI, Beihai TAN, Rong YU, Xumin HUANG, Siming WANG. Dynamic Blockchain Sharding for 6G Internet of Things Devices Collaboration [J]. Computer Engineering, 2024, 50(1): 50-59.
[9]	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.
[10]	Linghui KONG, Zheheng RAO, Yanyan XU, Shaoming PAN. Intelligent Routing Algorithm for Wireless Networks Based on Deep Reinforcement Learning [J]. Computer Engineering, 2023, 49(9): 199-207, 216.
[11]	Guanying ZHANG, Peng YI, Dan LI, Di ZHU, Ming MAO. Service Function Chain Deployment Method for Large-Scale Network [J]. Computer Engineering, 2023, 49(8): 122-129.
[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]	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.
[14]	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.
[15]	ZHENG Liping, ZHAO Yujuan, FEI Xuan. Communication Resource Allocation Algorithm Based on Improved MOEA/D in Internet of Vehicles [J]. Computer Engineering, 2023, 49(5): 191-197.

Please choose a citation manager

Content to export