云边协同计算中基于强化学习的依赖型任务调度方法

doi:10.11896/jsjkx.220900076

Abstract

Abstract: In cloud-edge collaborative computing,computing resources are scattered among mobile devices,edge servers and cloud servers,Offloading the computation-intensive tasks from mobile devices to remote servers for execution and thus expand local computing capability by utilizing powerful remote resources,which is an effective way to solve the resource-constrained problem of mobile devices.Aiming at the scheduling decision problem of tasks with dependencies in cloud-edge collaborative computing,this paper proposes a model-free approach based on reinforcement learning.First,this paper models the mobile application as a directed acyclic graph,and builds a task scheduling problem model in cloud-edge collaborative computing.Second,it models the task scheduling process as a Markov decision process,using Q-learning to learn reasonable scheduling decisions by interacting with the network environment.Experimental results show that,the dependency-aware task scheduling based on Q-learning method proposed in this paper outperforms the compared benchmark algorithms in different scenarios,and effectively reduces the execution time of the application.

Key words: Cloud-edge collaborative computing, Task scheduling, Dependency-aware task, Reinforcement learning

CLC Number:

TP338

HU Shengxi, SONG Rirong, CHEN Xing, CHEN Zheyi. Dependency-aware Task Scheduling in Cloud-Edge Collaborative Computing Based on Reinforcement Learning[J].Computer Science, 2023, 50(11A): 220900076-8.

References

[1]WANG J,LIU J,KATO N.Networking and communications in autonomous driving:A survey [J].IEEE Communications Surveys & Tutorials,2018,21(2):1243-1274.
[2]HASSABALLAH M,ALY S.Face recognition:challenges,achievements and future directions [J].IET Computer Vision,2015,9(4):614-626.
[3]KIM K,BILLINGHURST M,BRUDER G,et al.Revisiting trends in augmented reality research:A review of the 2nd deca-de of ISMAR(2008-2017) [J].IEEE Transactions on Visualization and Computer Graphics,2018,24(11):2947-29629.
[4]HUANG J,ZHOU Y,NING Z,et al.Wireless power transferand energy harvesting:Current status and future prospects [J].IEEE Wireless Communications,2019,26(4):163-169.
[5]CONG P,ZHOU J,LI L,et al.A survey of hierarchical energy optimization for mobile edge computing:A perspective from end devices to the cloud [J].ACM Computing Surveys(CSUR),2020,53(2):1-44.
[6]SHAKARAMI A,GHOBAEI-ARANI M,MASDARI M,et al.A survey on the computation offloading approaches in mobile edge/cloud computing environment:a stochastic-based perspective [J].Journal of Grid Computing,2020,18(4):639-671.
[7]CUI Y,SONG J,MIAO C C,et al.Mobile cloud computing research progress and trends [J].Chinese Journal of Computers,2017,40(2):273-295.
[8]DONG S Q,LI H L,QU Y B,et al.Survey of research oncomputation unloading strategy in mobile edge computing[J].Computer Science,2019,46(11):32-40.
[9]CHEN X,ZHANG J,LIN B,et al.Energy-efficient offloadingfor DNN-based smart IoT systems in cloud-edge environments [J].IEEE Transactions on Parallel and Distributed Systems,2021,33(3):683-697.
[10]TOPCUOGLU H,HARIRI S,WU M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing [J].IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.
[11]LIANG Y C,CHEN A H L,NIEN Y H.Artificial bee colony for workflow scheduling [C]//2014 IEEE Congress on Evolutionary Computation(CEC).IEEE,2014:558-564.
[12]CHENG Z,LI P,WANG J,et al.Just-in-time code offloading for wearable computing [J].IEEE Transactions on Emerging To-pics in Computing,2015,3(1):74-83.
[13]XIE Y,ZHU Y,WANG Y,et al.A novel directional and non-local-convergent particle swarm optimization based workflow scheduling in cloud-edge environment [J].Future Generation Computer Systems,2019,97:361-378.
[14]LIN B,GUO W Z,CHEN G L.Scheduling strategy for science workflow with deadline constraint on multi-cloud [J].Journal on Communications,2018,39(1):56-69.
[15]MIN M,XIAO L,CHEN Y,et al.Learning-based computation offloading for IoT devices with energy harvesting [J].IEEE Transactions on Vehicular Technology,2019,68(2):1930-1941.
[16]CHEN X,ZHANG H,WU C,et al.Optimized computation offloading performance in virtual edge computing systems via deep reinforcement learning [J].IEEE Internet of Things Journal,2018,6(3):4005-4018.
[17]HUANG L,BI S,ZHANG Y J A.Deep reinforcement learningfor online computation offloading in wireless powered mobile-edge computing networks [J].IEEE Transactions on Mobile Computing,2019,19(11):2581-2593.
[18]LIN KAI,LU YU,CHEN X,et al.Workflow Scheduling Strategy for Reasoning Task of Autonomous Driving [J].Journal of Chinese Computer Systems,2021,42(3):632-639.
[19]TONG Z,DENG X M,CHEN H J,et al.Multi-objective task scheduling algorithm based on reinforcement learning in cloud environment [J].Journal of Chinese Computer Systems,2020,41(2):285-290.
[20]MAO Y,YOU C,ZHANG J,et al.A survey on mobile edge computing:The communication perspective [J].IEEE Communications Surveys & Tutorials,2017,19(4):2322-2358.
[21]MIETTINEN A P,NURMINEN J K.Energy efficiency of mobile clients in cloud computing [C]//2nd USENIX Workshop on Hot Topics in Cloud Computing(HotCloud 10).2010.
[22]MAHMOODI S E,UMA R N,SUBBALAKSHMI K P.Optimal joint scheduling and cloud offloading for mobile applications [J].IEEE Transactions on Cloud Computing,2016,7(2):301-313.
[23]JIA M,CAO J,YANG L.Heuristic offloading of concurrenttasks for computation-intensive applications in mobile cloud computing [C]//2014 IEEE Conference on Computer Communications Workshops(INFOCOM WKSHPS).IEEE,2014:352-357.
[24]RA M R,SHETH A,MUMMERT L,et al.Odessa:enabling in-teractive perception applications on mobile devices [C]//Proceedings of the 9th International Conference on Mobile Systems,Applications,and Services.2011:43-56.
[25]LIN X,WANG Y,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,2014,8(2):175-186.
[26]LIU Y,WANG S,ZHAO Q,et al.Dependency-aware taskscheduling in vehicular edge computing [J].IEEE Internet of Things Journal,2020,7(6):4961-4971.
[27]SHU C,ZHAO Z,HAN Y,et al.Multi-user offloading for edge computing networks:A dependency-aware and latency-optimal approach [J].IEEE Internet of Things Journal,2019,7(3):1678-1689.
[28]ChEN X,HU J,CHEN Z,et al.AReinforcement Learning-Empowered Feedback Control System for Industrial Internet of Things [J].IEEE Transactions on Industrial Informatics,2021,18(4):2724-2733.
[29]WATKINS C J C H,DAYAN P.Q-learning [J].Machine learning,1992,8(3):279-292.
[30]ZHANG W,WEN Y.Energy-efficient task execution for application as a general topology in mobile cloud computing [J].IEEE Transactions on cloud Computing,2015,6(3):708-719.
[31]XIE G,CHEN Y,LIU Y,et al.Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems [J].IEEE Transactions on Industrial Informa-tics,2016,13(4):1629-1640.
[32]WU Q,ISHIKAWA F,ZHU Q,et al.Deadline-constrained cost optimization approaches for workflow scheduling in clouds [J].IEEE Transactions on Parallel and Distributed Systems,2017,28(12):3401-3412.
[33]KANG Y,HAUSWALD J,GAO C,et al.Neurosurgeon:Collaborative intelligence sbetween the cloud and mobile edge [J].ACM SIGARCH Computer Architecture News,2017,45(1):615-629.

Related Articles 15

[1]	LIU Xingguang, ZHOU Li, ZHANG Xiaoying, CHEN Haitao, ZHAO Haitao, WEI Jibo. Edge Intelligent Sensing Based UAV Space Trajectory Planning Method [J]. Computer Science, 2023, 50(9): 311-317.
[2]	LIN Xinyu, YAO Zewei, HU Shengxi, CHEN Zheyi, CHEN Xing. Task Offloading Algorithm Based on Federated Deep Reinforcement Learning for Internet of Vehicles [J]. Computer Science, 2023, 50(9): 347-356.
[3]	JIN Tiancheng, DOU Liang, ZHANG Wei, XIAO Chunyun, LIU Feng, ZHOU Aimin. OJ Exercise Recommendation Model Based on Deep Reinforcement Learning and Program Analysis [J]. Computer Science, 2023, 50(8): 58-67.
[4]	XIONG Liqin, CAO Lei, CHEN Xiliang, LAI Jun. Value Factorization Method Based on State Estimation [J]. Computer Science, 2023, 50(8): 202-208.
[5]	ZHANG Naixin, CHEN Xiaorui, LI An, YANG Leyao, WU Huaming. Edge Offloading Framework for D2D-MEC Networks Based on Deep Reinforcement Learningand Wireless Charging Technology [J]. Computer Science, 2023, 50(8): 233-242.
[6]	XING Linquan, XIAO Yingmin, YANG Zhibin, WEI Zhengmin, ZHOU Yong, GAO Saijun. Spacecraft Rendezvous Guidance Method Based on Safe Reinforcement Learning [J]. Computer Science, 2023, 50(8): 271-279.
[7]	LIU Chenwei, SUN Jian, LEI Bingbing, XU Tao, WU Zhuiwei. Task Scheduling Strategy for Energy Consumption Optimization of Cloud Data Center Based on Improved Particle Swarm Algorithm [J]. Computer Science, 2023, 50(7): 246-253.
[8]	ZENG Qingwei, ZHANG Guomin, XING Changyou, SONG Lihua. Intelligent Attack Path Discovery Based on Hierarchical Reinforcement Learning [J]. Computer Science, 2023, 50(7): 308-316.
[9]	LIN Xiangyang, XING Qinghua, XING Huaixi. Study on Intelligent Decision Making of Aerial Interception Combat of UAV Group Based onMADDPG [J]. Computer Science, 2023, 50(6A): 220700031-7.
[10]	SHI Liang, WEN Liangming, LEI Sheng, LI Jianhui. Virtual Machine Consolidation Algorithm Based on Decision Tree and Improved Q-learning by Uniform Distribution [J]. Computer Science, 2023, 50(6): 36-44.
[11]	WANG Hanmo, ZHENG Shijie, XU Ruonan, GUO Bin, WU Lei. Self Reconfiguration Algorithm of Modular Robot Based on Swarm Agent Deep Reinforcement Learning [J]. Computer Science, 2023, 50(6): 266-273.
[12]	MIAO Kuan, LI Chongshou. Optimization Algorithms for Job Shop Scheduling Problems Based on Correction Mechanisms and Reinforcement Learning [J]. Computer Science, 2023, 50(6): 274-282.
[13]	ZHANG Qiyang, CHEN Xiliang, CAO Lei, LAI Jun, SHENG Lei. Survey on Knowledge Transfer Method in Deep Reinforcement Learning [J]. Computer Science, 2023, 50(5): 201-216.
[14]	YU Ze, NING Nianwen, ZHENG Yanliu, LYU Yining, LIU Fuqiang, ZHOU Yi. Review of Intelligent Traffic Signal Control Strategies Driven by Deep Reinforcement Learning [J]. Computer Science, 2023, 50(4): 159-171.
[15]	XU Linling, ZHOU Yuan, HUANG Hongyun, LIU Yang. Real-time Trajectory Planning Algorithm Based on Collision Criticality and Deep Reinforcement Learning [J]. Computer Science, 2023, 50(3): 323-332.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Dependency-aware Task Scheduling in Cloud-Edge Collaborative Computing Based on Reinforcement Learning

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0