计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (11A): 220900076-8.doi: 10.11896/jsjkx.220900076

• 网络&通信 • 上一篇    下一篇

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

胡晟熙, 宋日荣, 陈星, 陈哲毅   

  1. 福州大学计算机与大数据学院 福州 350108
    福建省网络计算与智能信息处理重点实验室 福州 350108
  • 发布日期:2023-11-09
  • 通讯作者: 陈哲毅(z.chen@fzu.edu.cn)
  • 作者简介:(sxhu0913@qq.com)
  • 基金资助:
    国家自然科学基金项目(62072108);福建省自然科学基金杰青项目(2020J06014)

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

HU Shengxi, SONG Rirong, CHEN Xing, CHEN Zheyi   

  1. College of Computer and Data Science,Fuzhou University,Fuzhou 350108,China
    Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information Processing,Fuzhou 350108,China
  • Published:2023-11-09
  • About author:HU Shengxi,born in 1998,postgraduate,is a member of China Computer Federation.His main research interests include edge computing and task sche-duling.
    CHEN Zheyi,born in 1991,Ph.D.His main research interests include cloud-edge computing,resource optimization,deep learning,and reinforcement lear-ning.

PDF (PC)

168

摘要： 云边协同计算中,计算资源分散在移动设备、边缘服务器和云服务器。将应用程序中的计算密集型任务从本地卸载到远程设备执行,利用远程资源来扩展本地资源,是解决移动设备资源受限问题的一个有效途径。针对云边协同计算中存在依赖关系的任务调度问题,提出一种基于强化学习的无模型方法。首先,将移动应用程序建模为有向无环图,建立云边协同计算中的任务调度问题模型。其次,将任务调度过程建模为马尔可夫决策过程,即使用Q学习通过与网络环境交互学习合理的调度策略。实验结果表明,所提出的基于Q学习的依赖型任务调度方法在不同场景下均优于所对比的基准算法,有效地减少了应用程序的执行时间。

关键词: 云边协同计算, 任务调度, 依赖型任务, 强化学习

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

中图分类号: 

  • TP338
[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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发