Computer Science ›› 2021, Vol. 48 ›› Issue (1): 40-48.doi: 10.11896/jsjkx.200900195

Special Issue: Intelligent Edge Computing

• Intelligent Edge Computing • Previous Articles     Next Articles

Multi-workflow Offloading Method Based on Deep Reinforcement Learning and ProbabilisticPerformance-awarein Edge Computing Environment

MA Yu-yin1, ZHENG Wan-bo2, MA Yong3, LIU Hang1, XIA Yun-ni1, GUO Kun-yin1, CHEN Peng4, LIU Cheng-wu5   

  1. 1 College of Computer Science,Chongqing University,Chongqing 400044,China
    2 Faculty of Science,Kunming University of Science and Technology,Kunming 650500,China
    3 School of Computer Information Engineering,Jiangxi Normal University,Nanchang 330022,China
    4 School of Computer Science and Software Engineering,Xihua University,Chengdu 610039,China
    5 Shanghai Jiaotong University Chongqing Research Institute,Chongqing 401135,China
  • Received:2020-09-27 Revised:2020-12-09 Online:2021-01-15 Published:2021-01-15
  • About author:MA Yu-yin,born in 1995,postgraduate,is a member of China Computer Federation.Her main research interests include edge computing,service computing and workflows scheduling.
    ZHENG Wan-bo,born in 1981,Ph.D,associate researcher.His main research interests include big data intersects with cloud computing,data analysis and mining,mine tunnel emergency management,research on mine tunnel emergency rescue,disposal information technology and equipment,engineering geophysical exploration,as well as measurement & control technology and instruments.
  • Supported by:
    Graduate Scientific Research and Innovation Foundations of Chongqing(CYS20066,CYB20062),Chongqing Technological Innovation Foundations (cstc2019jscx-msxm0652,cstc2019jscx-fxyd0385),Sichuan Scientific Foundations(2020JDRC0067,2020YFG0326),Research Talent Foundation of Xihua University(Z202047),Chongqing Key R&D Project(cstc2018jszx-cyzdX0081) and Jiangxi Key R&D Project(20181ACE50029).

Abstract: Mobile edge computing is a new distributed and ubiquitous computing model.By transferring computation-intensive and time-delay sensitive tasks to closer to the edge servers,it effectively alleviates the resource shortage of mobile terminals andthe communication transmission overhead between users and computing processing nodes.However,if multiple users request computation-intensive tasks simultaneously,especially process-based workflow task requests,edge computing are often difficult to respond effectively and cause task congestion.Inaddition,the performance of edge servers is affected by detrimental factors such as task overload,power supply and real-time change of communication capability,and its performance fluctuates and changes,which brings challenges to ensure task execution and user-perceived service efficiency.To solve the above problems,a Deep-Q-Network (DQN) and probabilistic performance aware based multi-workflow scheduling approach in edge computing environment is proposed.Firstly,the historical performance data of edge cloudservers is analyzed probabilistically,then the DQN model is driven by performance probability distribution data,and iterative optimization is carried out continuously to generate multi-workflow offloading strategy.In the process of experimental verification,simulation experiments areconducted in multiple scenarios reflecting difterent levels of system load based on edge server Location data set,performance test data and multiple scientific workflow templates.The results show that the proposed method is superior to the traditional method in the execution efficiency of multi-workflow.

Key words: Deep Q network, Edge computing, Probability distribution model, Reinforcement learning, Workflow scheduling

CLC Number: 

  • TP301
[1] CHEN X,LIU Z,CHEN Y,et al.Mobile edge computing based task offloading and resource allocation in 5g ultra-dense networks[J].IEEE Access,2019,7:184172-184182.
[2] LYU X,NI W,TIAN H L,et al.Optimal schedule of mobile edge computing for internet of things using partial information[J].IEEE Journal on Selected Areas in Communications,2017,35(11):2606-2615.
[3] ZHANG Y,DU P.Delay-driven computation task scheduling in multi-cell cellular edge computing systems[J].IEEE Access,2019,7:149156-149167.
[4] CAO H,XU X,LIU Q,et al.Uncertainty-aware resource provisioning for workflow scheduling in edge computing environment[C]//18th IEEE International Conference on Trust,Security And Privacy In Computing And Communications/13th IEEE International Conference on Big Data Science And Engineering,TrustCom/BigDataSE.Rotorua,New Zealand,2019:734-739.
[5] DENG Y,CHEN,YAO X,et al.Task scheduling for smart city applications based on multi-server mobile edge computing[J].IEEE Access,2019,7:14410-14421.
[6] CHEN J F,CHEN J W,JING P,et al.An improved chaotic bat swarm scheduling learning model on edge computing[J].IEEE Access,2019:58602-58610.
[7] MA Y,ZHANG J,WANG S,et al.A Novel Approach to Cost-Efficient Scheduling of Multi-workflows in the Edge Computing Environment with the Proximity Constraint[C]//International Conference on Algorithms and Architectures for Parallel Processing.Springer,Cham,2019:655-668.
[8] PENG Q,JIANG H,CHEN M,et al.Reliability-aware andDeadline-constrained workflow scheduling in Mobile Edge Computing[C]//2019 IEEE 16th International Conference on Networking,Sensing and Control (ICNSC).IEEE,2019:236-241.
[9] BERNAL J,KUSHIBAR K,ASFAW D S,et al.Deep convolutional neural networks for brain image analysis on magnetic resonance imaging:a review[J].Artificial intelligence in medicine,2019,95:64-81.
[10] BOUWMANS T,JAVED S,SULTANA M,et al.Deep neural network concepts for background subtraction:A systematic review and comparative evaluation[J].Neural Networks,2019,117:8-66.
[11] GREKOUSIS G.Artificial neural networks and deep learning in urban geography:A systematic review and meta-analysis[J].Computers,Environment and Urban Systems,2019,74:244-256.
[12] LAI P,HE Q,ABDELRAZEK M,et al.Optimal edge user allocation in edge computing with variable sized vector bin packing[C]//International Conference on Service-Oriented Computing.Springer,Cham,2018:230-245.
[13] LI W,XIA Y,ZHOU M,et al.Fluctuation-aware and predictive workflow scheduling in cost-effective infrastructure-as-a-service clouds[J].IEEE Access,2018,6:61488-61502.
[14] KAUR M,KADAM S.A novel multi-objective bacteria foraging optimization algorithm (MOBFOA) for multi-objective scheduling[J].Applied Soft Computing,2018,66:183-195.
[15] ZHANG L,LI K,LI C,et al.Bi-objective workflow scheduling of the energy consumption and reliability in heterogeneous computing systems[J].Information Sciences,2017,379:241-256.
[16] CASAS I,TAHERI J,RANJAN R,et al.GA-ETI:An enhanced genetic algorithm for the scheduling of scientific workflows in cloud environments[J].Journal of computational science,2018,26:318-331.
[17] VERMA A,KAUSHAL S.A hybrid multi-objective particleswarm optimization for scientific workflow scheduling[J].Parallel Computing,2017,62:1-19.
[18] ZHOU X,ZHANG G,SUN J,et al.Minimizing cost and makespan for workflow scheduling in cloud using fuzzy dominance sort based HEFT[J].Future Generation Computer Systems,2019,93:278-289.
[19] HABAK K,AMMAR M,HARRAS K A,et al.Femto clouds:Leveraging mobile devices to provide cloud service at the edge[C]//2015 IEEE 8th international conference on cloud computing.IEEE,2015:9-16.
[20] MAO Y,ZHANG J,SONG S H,et al.Stochastic Joint Radioand Computational Resource Management for Multi-User Mobile-Edge Computing Systems[J].IEEE transactions on wireless communications,2017,16(9):5994-6009.
[21] TONG L,LI Y,GAO W.A hierarchical edge cloud architecture for mobile computing[C]//IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications.IEEE,2016:1-9.
[22] ZHANG Y,CHEN X,CHEN Y,et al.Cost efficient scheduling for delay-sensitive tasks in edge computing system[C]//2018 IEEE International Conference on Services Computing (SCC).IEEE,2018:73-80.
[23] ZHAO T,ZHOU S,GUO X,et al.Tasks scheduling and re-source allocation in heterogeneous cloud for delay-bounded mobile edge computing[C]//2017 IEEE international conference on communications (ICC).IEEE,2017:1-7.
[24] HWANG S Y,HSU C C,LEE C H.Service selection for web services with probabilistic QoS[J].IEEE transactions on services computing,2014,8(3):467-480.
[25] PAN Y,WANG S,WU L,et al.A Novel Approach to Scheduling Workflows Upon Cloud Resources with Fluctuating Performance[J].Mobile Networks and Applications,2020:1-11.
[26] LI W,XIA Y,ZHOU M,et al.Fluctuation-aware and predictive workflow scheduling in cost-effective infrastructure-as-a-service clouds[J].IEEE Access,2018,6:61488-61502.
[27] BERTSEKAS D P.Feature-based aggregation and deep rein-forcement learning:A survey and some new implementations[J].IEEE/CAA Journal of Automatica Sinica,2018,6(1):1-31.
[28] MAO H,ALIZADEH M,MENACHE I,et al.Resource management with deep reinforcement learning[C]//Proceedings of the 15th ACM Workshop on Hot Topics in Networks.2016:50-56.
[29] XUE L,SUN C,WUNSCH D,et al.An adaptive strategy via reinforcement learning for the prisoner's dilemma game[J].IEEE/CAA Journal of Automatica Sinica,2017,5(1):301-310.
[30] ZHAN Y,AMMAR H B.Theoretically-grounded policy advice from multiple teachers in reinforcement learning settings with applications to negative transfer[J].arXiv:1604.03986,2016.
[31] WANG H,HUANG T,LIAO X,et al.Reinforcement learning for constrained energy trading games with incomplete information[J].IEEE transactions on cybernetics,2016,47(10):3404-3416.
[32] ZHENG L,YANG J,CAI H,et al.Magent:A many-agent reinforcement learning platform for artificial collective intelligence[J].arXiv:1712.00600,2017.
[33] LOWE R,WU Y I,TAMAR A,et al.Multi-agent actor-critic for mixed cooperative-competitive environments[C]//Advances in Neural Information Processing Systems.2017:6379-6390.
[34] DUAN R,PRODAN R,LI X.Multi-objective game theoreticschedulingof bag-of-tasks workflows on hybrid clouds[J].IEEE Transactions on Cloud Computing,2014,2(1):29-42.
[35] CUI D,KE W,PENG Z,et al.Multiple DAGs workflow scheduling algorithm based on reinforcement learning in cloud computing[C]//International Symposium on Computational Intelligence and Intelligent Systems.Springer,Singapore,2015:305-311.
[36] IRANPOUR E,SHARIFIAN S.A distributed load balancingand admission control algorithm based on Fuzzy type-2 and Game theory for large-scale SaaS cloud architectures[J].Future Generation Computer Systems,2018,86:81-98.
[37] WU J H,PENG Z P,CUI D L,et al.A multi-object optimization cloud workflow scheduling algorithm based on reinforcement learning[C]//International Conference on Intelligent Computing.Springer,Cham,2018:550-559.
[38] DONG T,XUE F,XIAO C,et al.Task scheduling based on deep reinforcement learning in a cloud manufacturing environment[J].Concurrency and Computation:Practice and Experience,2020,32(11):e5654.
[39] PENG Z,CUI D,ZUO J,et al.Random task scheduling scheme based on reinforcement learning in cloud computing[J].Cluster computing,2015,18(4):1595-1607.
[40] CHENG M,LI J,NAZARIAN S.DRL-cloud:Deep reinforce-ment learning-based resource provisioning and task scheduling for cloud service providers[C]//2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC).IEEE,2018:129-134.
[41] WANG Y,LIU H,ZHENG W,et al.Multi-objective workflow scheduling with deep-Q-network-based multi-agent reinforcement learning[J].IEEE Access,2019,7:39974-39982.
[42] GUO S,LIU J,YANG Y,et al.Energy-efficient dynamic computation offloading and cooperative task scheduling in mobile cloud computing[J].IEEE Transactions on Mobile Computing,2018,18(2):319-333.
[43] MNIH V,KAVUKCUOGLU K,SILVER D,et al.Human-level control through deep reinforcement learning[J].nature,2015,518(7540):529-533.
[44] MNIH V,KAVUKCUOGLU K,SILVER D,et al.Playing atari with deep reinforcement learning[J].arXiv:1312.5602,2013.
[45] BHARATHI S,CHERVENAK A,DEELMAN E,et al.Characterization of scientific workflows[C]//2008 third workshop on workflows in support of large-scale science.IEEE,2008:1-10.
[46] ZHANG G M.Gauss-legendre Multi-Repetition Integral formula and its application[J].Journal of Lanzhou University,2000(5):30-34.
[47] Tencent Cloud.Tencent Cloud gradually opens up BAT comprehensively competitive cloud platform[DB/OL].[2013-09-10].
[48] Aliyun official website.Aliyun official website[DB/OL].2016-9-12.[2016-9-12].
[49] Qi Chacha-Huawei Cloud.Qi Chacha[DB/OL].[2020-07-1].
[50] AJEENA BEEGOM A S,RAJASREE M S.Non-dominated sorting based PSO algorithm for workflow task scheduling in cloud computing systems[J].Journal of Intelligent & Fuzzy Systems,2019,37(5):6801-6813.
[51] MOLLAJAFARI M,SHAHHOSEINI H S.Cost-OptimizedGA-Based Heuristic for Scheduling Time-Constrained Workflow Applications in Infrastructure Clouds Using an Innovative Feasibility-Assured Decoding Mechanism[J].Journal Information Science and Engineering,2016,32(6):1541-1560.
[1] LIU Xing-guang, ZHOU Li, LIU Yan, ZHANG Xiao-ying, TAN Xiang, WEI Ji-bo. Construction and Distribution Method of REM Based on Edge Intelligence [J]. Computer Science, 2022, 49(9): 236-241.
[2] SUN Hui-ting, FAN Yan-fang, MA Meng-xiao, CHEN Ruo-yu, CAI Ying. Dynamic Pricing-based Vehicle Collaborative Computation Offloading Scheme in VEC [J]. Computer Science, 2022, 49(9): 242-248.
[3] YUAN Wei-lin, LUO Jun-ren, LU Li-na, CHEN Jia-xing, ZHANG Wan-peng, CHEN Jing. Methods in Adversarial Intelligent Game:A Holistic Comparative Analysis from Perspective of Game Theory and Reinforcement Learning [J]. Computer Science, 2022, 49(8): 191-204.
[4] SHI Dian-xi, ZHAO Chen-ran, ZHANG Yao-wen, YANG Shao-wu, ZHANG Yong-jun. Adaptive Reward Method for End-to-End Cooperation Based on Multi-agent Reinforcement Learning [J]. Computer Science, 2022, 49(8): 247-256.
[5] YU Bin, LI Xue-hua, PAN Chun-yu, LI Na. Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning [J]. Computer Science, 2022, 49(7): 248-253.
[6] LI Meng-fei, MAO Ying-chi, TU Zi-jian, WANG Xuan, XU Shu-fang. Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient [J]. Computer Science, 2022, 49(7): 271-279.
[7] YUAN Hao-nan, WANG Rui-jin, ZHENG Bo-wen, WU Bang-yan. Design and Implementation of Cross-chain Trusted EMR Sharing System Based on Fabric [J]. Computer Science, 2022, 49(6A): 490-495.
[8] FANG Tao, YANG Yang, CHEN Jia-xin. Optimization of Offloading Decisions in D2D-assisted MEC Networks [J]. Computer Science, 2022, 49(6A): 601-605.
[9] LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[10] XIE Wan-cheng, LI Bin, DAI Yue-yue. PPO Based Task Offloading Scheme in Aerial Reconfigurable Intelligent Surface-assisted Edge Computing [J]. Computer Science, 2022, 49(6): 3-11.
[11] HONG Zhi-li, LAI Jun, CAO Lei, CHEN Xi-liang, XU Zhi-xiong. Study on Intelligent Recommendation Method of Dueling Network Reinforcement Learning Based on Regret Exploration [J]. Computer Science, 2022, 49(6): 149-157.
[12] GUO Yu-xin, CHEN Xiu-hong. Automatic Summarization Model Combining BERT Word Embedding Representation and Topic Information Enhancement [J]. Computer Science, 2022, 49(6): 313-318.
[13] FAN Jing-yu, LIU Quan. Off-policy Maximum Entropy Deep Reinforcement Learning Algorithm Based on RandomlyWeighted Triple Q -Learning [J]. Computer Science, 2022, 49(6): 335-341.
[14] ZHANG Jia-neng, LI Hui, WU Hao-lin, WANG Zhuang. Exploration and Exploitation Balanced Experience Replay [J]. Computer Science, 2022, 49(5): 179-185.
[15] LI Peng, YI Xiu-wen, QI De-kang, DUAN Zhe-wen, LI Tian-rui. Heating Strategy Optimization Method Based on Deep Learning [J]. Computer Science, 2022, 49(4): 263-268.
Full text



No Suggested Reading articles found!