Multi-objective task offloading algorithm based on deep Q-network

doi:10.11772/j.issn.1001-9081.2021061367

Abstract

Abstract:

For the Mobile Device （MD） with limited computing resources and battery capacity in Mobile Edge Computing （MEC）， its computing capacity can be enhanced and its energy consumption can be reduced through offloading its own computing-intensive applications to the edge server. However， unreasonable task offloading strategy will bring a bad experience for users since it will increase the application completion time and energy consumption. To overcome above challenge， firstly， a multi-objective task offloading problem model with minimizing the application completion time and energy consumption as optimization targets was built in the dynamic MEC network via analyzing the mobility of the mobile device and the sequential dependencies between tasks. Then， a Markov Decision Process （MDP） model， including state space， action space， and reward function， was designed to solve this problem， and a Multi-Objective Task Offloading Algorithm based on Deep Q-Network （MTOA-DQN） was proposed， which uses a trajectory as the smallest unit of the experience buffer to improve the original DQN. The proposed MTOA-DQN outperforms three comparison algorithms including MultiObjective Evolutionary Algorithm based on Decomposition （MOEA/D）， Adaptive DAG （Directed Acyclic Graph） Tasks Scheduling （ADTS） and original DQN in terms of cumulative reward and cost in a number of test scenarios， verifying the effectiveness and reliability of the algorithm.

Key words: Mobile Edge Computing (MEC), task offloading, completion time, energy consumption, Reinforcement Learning (RL)

摘要：

在移动边缘计算（MEC）中，计算资源和电池容量有限的移动设备（MD）可卸载自身计算密集型应用到边缘服务器上执行，这样不仅可以提高MD计算能力，也能降低能耗。然而，不合理的任务卸载决策不但会延长应用完成时间，而且会大量增加能耗，进而降低用户体验。鉴于此，首先分析MD的移动性和任务间的顺序依赖关系，建立动态MEC网络下的以应用完成时间和能源消耗最小为优化目标的多目标任务卸载问题模型；然后，设计求解该问题的马尔可夫决策过程（MDP）模型，包括状态空间、动作空间和奖励函数，并提出基于深度Q网络（DQN）的多目标任务卸载算法（MTOA-DQN），该算法采用一条轨迹作为经验池的最小单元来改进原始的DQN算法。在多种测试场景下，MTOA-DQN的性能在累积奖励和Cost方面均优于三种对比算法（基于分解的多目标进化算法（MOEA/D）、自适应的DAG任务调度算法（ADTS）和原始的DQN算法），验证了该算法的有效性和可靠性。

关键词: 移动边缘计算, 任务卸载, 完成时间, 能源消耗, 强化学习

CLC Number:

TP391.9

Shiquan DENG, Xuguo YE. Multi-objective task offloading algorithm based on deep Q-network[J]. Journal of Computer Applications, 2022, 42(6): 1668-1674.

邓世权, 叶绪国. 基于深度Q网络的多目标任务卸载算法[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1668-1674.

Figures/Tables 7

Fig. 1 Schematic diagram of MEC system

Fig. 2 DAG of an application

Tab. 1 Summary of main symbols

符号	定义
$C o s t (G)$	MD完成应用G的总代价
$c i$	执行任务v_i 需要的CPU循环次数
$d i$	任务v_i 的输入数据规模
E	应用G中任务间的顺序依赖关系集
$E C (G)$	MD执行应用G所消耗的能量
$e (v i, v j)$	表示任务v_i 和v_j 间的顺序依赖关系
$e x i t (G)$	应用G的结束任务集
$f l$	MD计算能力
$f m s$	第m个边缘服务器的计算能力
$F T (G)$	应用G的完成时间
$G$	MD待执行的应用
$M$	边缘服务器数量
$M$	边缘服务器集
$m$	第m个边缘服务器
$o i$	任务v_i 的输出数据规模
$p r e (v i)$	任务v_i 的直接前驱任务集
$p w t$	MD的传输功率
$p w r$	MD的接收功率
$R m$	MD与边缘服务器 $E m$ 间的可达上行传输速率
$s u c (v i)$	任务v_i 的直接后继任务集
$V$	应用G的任务集合
$v i$	应用G的第i个任务
$x$	应用G中所有任务的卸载决策
$x i$	任务v_i 的卸载决策
$α$	应用完成时间的权重
$β$	MD能耗的权重

Tab. 1 Summary of main symbols

符号	定义
$C o s t (G)$	MD完成应用G的总代价
$c i$	执行任务v_i 需要的CPU循环次数
$d i$	任务v_i 的输入数据规模
E	应用G中任务间的顺序依赖关系集
$E C (G)$	MD执行应用G所消耗的能量
$e (v i, v j)$	表示任务v_i 和v_j 间的顺序依赖关系
$e x i t (G)$	应用G的结束任务集
$f l$	MD计算能力
$f m s$	第m个边缘服务器的计算能力
$F T (G)$	应用G的完成时间
$G$	MD待执行的应用
$M$	边缘服务器数量
$M$	边缘服务器集
$m$	第m个边缘服务器
$o i$	任务v_i 的输出数据规模
$p r e (v i)$	任务v_i 的直接前驱任务集
$p w t$	MD的传输功率
$p w r$	MD的接收功率
$R m$	MD与边缘服务器 $E m$ 间的可达上行传输速率
$s u c (v i)$	任务v_i 的直接后继任务集
$V$	应用G的任务集合
$v i$	应用G的第i个任务
$x$	应用G中所有任务的卸载决策
$x i$	任务v_i 的卸载决策
$α$	应用完成时间的权重
$β$	MD能耗的权重

Fig. 3 Cumulative rewards under different parameters

Fig. 4 Cumulative rewards of two DQNs under different task sizes N

Fig. 5 Box plots of four algorithms under different task sizes N

Tab. 2 Comparison of average Cost for different task sizes N

算法	$N = 10$	$N = 20$	$N = 30$
MOEA/D	4.666 5	9.487 1	14.253 7
ADTS	4.632 3	9.419 7	14.217 5
DQN	4.493 1	9.164 7	13.673 4
MOTA-DQN	4.487 8	9.106 6	13.606 1

Tab. 2 Comparison of average Cost for different task sizes N

算法	$N = 10$	$N = 20$	$N = 30$
MOEA/D	4.666 5	9.487 1	14.253 7
ADTS	4.632 3	9.419 7	14.217 5
DQN	4.493 1	9.164 7	13.673 4
MOTA-DQN	4.487 8	9.106 6	13.606 1

References 21

1	LI L L， LIU Z F， TSENG M L， et al. Enhancing the Lithium-ion battery life predictability using a hybrid method［J］. Applied Soft Computing， 2019， 74： 110-121. 10.1016/j.asoc.2018.10.014
2	ATAT R， LIU L J， CHEN H， et al. Enabling cyber-physical communication in 5G cellular networks： challenges， spatial spectrum sensing， and cyber-security［J］. IET Cyber-Physical Systems： Theory and Applications， 2017， 2（1）： 49-54. 10.1049/iet-cps.2017.0010
3	LI C L， ZHU L Y， TANG H L， et al. Mobile user behavior based topology formation and optimization in ad hoc mobile cloud［J］. Journal of Systems and Software， 2019， 148： 132-147. 10.1016/j.jss.2018.11.005
4	NOVAK E， TANG Z F， LI Q. Ultrasound proximity networking on smart mobile devices for IoT applications［J］. IEEE Internet of Things Journal， 2019， 6（1）： 399-409. 10.1109/jiot.2018.2848099
5	MAO Y Y， YOU C S， ZHANG J， et al. A survey on mobile edge computing： the communication perspective［J］. IEEE Communications Surveys and Tutorials， 2017， 19（4）： 2322-2358. 10.1109/comst.2017.2745201
6	WANG S， ZHANG X， ZHANG Y， et al. A survey on mobile edge networks： convergence of computing， caching and communications［J］. IEEE Access， 2017， 5： 6757-6779. 10.1109/access.2017.2685434
7	ABBAS N， ZHANG Y， TAHERKORDI A， et al. Mobile edge computing： a survey［J］. IEEE Internet of Things Journal， 2018， 5（1）： 450-465. 10.1109/jiot.2017.2750180
8	KENESHLOO Y， SHI T， RAMAKRISHNAN N， et al. Deep reinforcement learning for sequence-to-sequence models［J］. IEEE Transactions on Neural Networks and Learning Systems， 2020， 31（7）： 2469-2489.
9	MNIH V， KAVUKCUOGLU K， SILVER D， et al. Human-level control through deep reinforcement learning［J］. Nature， 2015， 518（7540）： 529-533. 10.1038/nature14236
10	LUONG N C， HOANG D T， GONG S M， et al. Applications of deep reinforcement learning in communications and networking： a survey［J］. IEEE Communications Surveys and Tutorials， 2019， 21（4）： 3133-3174. 10.1109/comst.2019.2916583
11	KIRAN B R， SOBH I， TALPAERT V， et al. Deep reinforcement learning for autonomous driving： a survey［J/OL］. IEEE Transactions on Intelligent Transportation Systems. （2021-01-23）［2022-06-20］. . 10.1109/tits.2021.3054625
12	WAN Z Q， JIANG C， FAHAD M， et al. Robot-assisted pedestrian regulation based on deep reinforcement learning［J］. IEEE Transactions on Cybernetics， 2020， 50（4）： 1669-1682. 10.1109/tcyb.2018.2878977
13	LIN X， WANG Y Z， XIE Q， et al. Task scheduling with dynamic voltage and frequency scaling for energy minimization in the mobile cloud computing environment［J］. IEEE Transactions on Services Computing， 2015， 8（2）： 175-186. 10.1109/tsc.2014.2381227
14	MAHMOODI S E， UMA R N， SUBBALAKSHMI K P. Optimal joint scheduling and cloud offloading for mobile applications［J］. IEEE Transactions on Cloud Computing， 2019， 7（2）： 301-313. 10.1109/tcc.2016.2560808
15	周业茂，李忠金，葛季栋，等. 移动云计算中基于延时传输的多目标工作流调度［J］. 软件学报， 2018， 29（11）： 3306-3325. 10.13328/j.cnki.jos.005479
	ZHOU Y M， LI Z J， GE J D， et al. Multi-objective workflow scheduling based on delay transmission in mobile cloud computing［J］. Journal of Software， 2018， 29（11）： 3306-3325. 10.13328/j.cnki.jos.005479
16	SONG F H， XING H L， LUO S X， et al. A multiobjective computation offloading algorithm for mobile-edge computing［J］. IEEE Internet of Things Journal， 2020， 7（9）： 8780-8799. 10.1109/jiot.2020.2996762
17	杨天，杨军. 移动边缘计算中的卸载决策与资源分配策略［J］. 计算机工程， 2021， 47（2）： 19-25. 10.19678/j.issn.1000-3428.0058085
	YANG T， YANG J. Offloading decision and resource allocation strategy in mobile edge computing［J］. Computer Engineering， 2021， 47（2）： 19-25. 10.19678/j.issn.1000-3428.0058085
18	YANG L， ZHONG C Y， YANG Q H， et al. Task offloading for directed acyclic graph applications based on edge computing in Industrial Internet［J］. Information Sciences， 2020， 540： 51-68. 10.1016/j.ins.2020.06.001
19	WU Q， WU Z W， ZHUANG Y H， et al. Adaptive DAG tasks scheduling with deep reinforcement learning［C］// Proceedings of the 2018 International Conference on Algorithms and Architectures for Parallel Processing， LNTCS 11335. Cham： Springer， 2018： 477-490.
20	詹文翰，王瑾，朱清新，等. 移动边缘计算中基于深度强化学习的计算卸载调度方法［J］. 计算机应用研究， 2021， 38（1）： 241-245， 263. 10.19734/j.issn.1001-3695.2019.10.0594
	ZHAN W H， WANG J， ZHU Q X， et al. Deep reinforcement learning based offloading scheduling in mobile edge computing［J］. Application Research of Computers， 2021， 38（1）： 241-245， 263. 10.19734/j.issn.1001-3695.2019.10.0594
21	YAN J， BI S Z， ZHANG Y J A. Offloading and resource allocation with general task graph in mobile edge computing： a deep reinforcement learning approach［J］. IEEE Transactions on Wireless Communications， 2020， 19（8）： 5404-5419. 10.1109/twc.2020.2993071

[1]	Junna ZHANG, Xinxin WANG, Tianze LI, Xiaoyan ZHAO, Peiyan YUAN. Task offloading method based on dynamic service cache assistance [J]. Journal of Computer Applications, 2024, 44(5): 1493-1500.
[2]	Xiaoyan ZHAO, Wei HAN, Junna ZHANG, Peiyan YUAN. Collaborative offloading strategy in internet of vehicles based on asynchronous deep reinforcement learning [J]. Journal of Computer Applications, 2024, 44(5): 1501-1510.
[3]	Haixin HUANG, Guangwei YU, Shoushan CHENG, Chunming LI. Full coverage path planning of bridge inspection wall-climbing robot based on improved grey wolf optimization [J]. Journal of Computer Applications, 2024, 44(3): 966-971.
[4]	Ziyang SONG, Junhuai LI, Huaijun WANG, Xin SU, Lei YU. Path planning algorithm of manipulator based on path imitation and SAC reinforcement learning [J]. Journal of Computer Applications, 2024, 44(2): 439-444.
[5]	Jian SUN, Baoquan MA, Zhuiwei WU, Xiaohuan YANG, Tao WU, Pan CHEN. Joint optimization of UAV swarm path planning and task allocation balance in earthquake scenarios [J]. Journal of Computer Applications, 2024, 44(10): 3232-3239.
[6]	Xiaolin LI, Yusang JIANG. Task offloading algorithm for UAV-assisted mobile edge computing [J]. Journal of Computer Applications, 2023, 43(6): 1893-1899.
[7]	Xingbin LIAO, Xiaolin QIN, Siqi ZHANG, Yangge QIAN. Review of interactive machine translation [J]. Journal of Computer Applications, 2023, 43(2): 329-334.
[8]	Kuineng CHEN, Xiaofang YUAN. Multi-objective hybrid evolutionary algorithm for solving open-shop scheduling problem with controllable processing time [J]. Journal of Computer Applications, 2022, 42(8): 2617-2627.
[9]	Yanpei LIU, Ningning CHEN, Yunjing ZHU, Liping WANG. Review of mobile edge caching optimization technologies for 5G/Beyond 5G [J]. Journal of Computer Applications, 2022, 42(8): 2487-2500.
[10]	Jieqin WANG, Shihyang LIN, Shiming PENG, Shuo JIA, Miaohui YANG. Hierarchical resource allocation mechanism of cooperative mobile edge computing [J]. Journal of Computer Applications, 2022, 42(8): 2501-2510.
[11]	Jingling YUAN, Huihua MAO, Nana WANG, Yao XIANG. Dynamic service deployment strategy in resource constrained mobile edge computing [J]. Journal of Computer Applications, 2022, 42(6): 1662-1667.
[12]	Yu LI, Xiping HE, Lianggui TANG. Multi-user computation offloading and resource optimization policy based on device-to-device communication [J]. Journal of Computer Applications, 2022, 42(5): 1538-1546.
[13]	Xuling ZENG, Taoshen LI, Jian GONG, Lijun DU. Secure offloading optimization of wireless powered mobile edge computing system [J]. Journal of Computer Applications, 2022, 42(4): 1216-1224.
[14]	Xueming LI, Guohao WU, Shangbo ZHOU, Xiaoran LIN, Hongbin XIE. Image instance segmentation model based on fractional-order network and reinforcement learning [J]. Journal of Computer Applications, 2022, 42(2): 574-583.
[15]	Xiao GUO, Chunshan LI, Yuyue ZHANG, Dianhui CHU. Service integration method based on adaptive multi‑objective reinforcement learning [J]. Journal of Computer Applications, 2022, 42(11): 3500-3505.