一种基于深度强化学习与概率性能感知的边缘计算环境多工作流卸载方法

doi:10.11896/jsjkx.200900195

计算机科学 ›› 2021, Vol. 48 ›› Issue (1): 40-48.doi: 10.11896/jsjkx.200900195

所属专题：智能化边缘计算

一种基于深度强化学习与概率性能感知的边缘计算环境多工作流卸载方法

马堉银¹, 郑万波², 马勇³, 刘航¹, 夏云霓¹, 郭坤银¹, 陈鹏⁴, 刘诚武⁵

1 重庆大学计算机学院重庆 400044
2 昆明理工大学理学院昆明 650500
3 江西师范大学计算机信息工程学院南昌 330022
4 西华大学计算机与软件工程学院成都 610039
5 上海交通大学重庆研究院重庆 401135

收稿日期:2020-09-27 修回日期:2020-12-09 出版日期:2021-01-15 发布日期:2021-01-15
通讯作者: 郑万波(zwanbo2001@163.com)
作者简介:mayuyin@cqu.edu.cn
基金资助:
重庆市研究生科研创新项目(CYS20066,CYB20062);重庆市科技局技术创新项目(cstc2019jscx-msxm0652,cstc2019jscx-fxyd0385);四川省科技计划项目(2020JDRC0067,2020YFG0326);西华大学人才引进项目(Z202047);重庆市科技局重点研发计划项目(cstc2018jszx-cyzdX0081);江西省重点研发计划(20181ACE50029)

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

MA Yu-yin¹, ZHENG Wan-bo², MA Yong³, LIU Hang¹, XIA Yun-ni¹, GUO Kun-yin¹, CHEN Peng⁴, LIU Cheng-wu⁵

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

摘要： 移动边缘计算是一种新兴的分布式和泛在计算模式,其将计算密集型和时延敏感型任务转移到附近的边缘服务器,有效缓解了移动终端资源不足的问题,显著减小了用户与计算处理节点之间的通信传输开销。然而,如果多个用户同时提出计算密集型任务请求,特别是流程化的工作流任务请求,边缘计算环境往往难以有效地进行响应,并会造成任务拥塞。另外,受任务负载、电力供给、通信能力的实时变化等不利因素的影响,边缘服务器本身的性能总是处于波动和变化中,从而为保证任务执行效能和用户感知服务效率带来了挑战。针对上述问题,文中提出了一种基于深度Q网络(DQN)与概率性能感知机制的边缘计算环境多工作流调度方法。首先对边缘云服务器的历史性能数据进行概率分析,然后利用获得的性能概率分布数据驱动DQN模型,不断迭代优化,生成多工作流的卸载策略。在实验验证环节,基于边缘服务器位置数据集、性能测试数据和多个科学工作流模板,在反映不同系统负载水平的多个场景下进行了模拟实验。实验结果表明,所提方法在多工作流执行效率方面明显优于传统方法。

关键词: 边缘计算, 概率分布模型, 工作流调度, 强化学习, 深度Q网络

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

中图分类号:

TP301

马堉银, 郑万波, 马勇, 刘航, 夏云霓, 郭坤银, 陈鹏, 刘诚武. 一种基于深度强化学习与概率性能感知的边缘计算环境多工作流卸载方法[J]. 计算机科学, 2021, 48(1): 40-48. https://doi.org/10.11896/jsjkx.200900195

MA Yu-yin, ZHENG Wan-bo, MA Yong, LIU Hang, XIA Yun-ni, GUO Kun-yin, CHEN Peng, LIU Cheng-wu. Multi-workflow Offloading Method Based on Deep Reinforcement Learning and ProbabilisticPerformance-awarein Edge Computing Environment[J]. Computer Science, 2021, 48(1): 40-48. https://doi.org/10.11896/jsjkx.200900195

参考文献

[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].http://www.qcloud.com/.
[48] Aliyun official website.Aliyun official website[DB/OL].2016-9-12.[2016-9-12].https://www.aliyun.com/minisite/goods?userCode=om2mzele
[49] Qi Chacha-Huawei Cloud.Qi Chacha[DB/OL].[2020-07-1].https://www.qcc.com/product/c893fb05-edc2-4f3b-9f2d-ed4e0c60-bbcd.html.
[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.

相关文章 15

[1]	刘兴光, 周力, 刘琰, 张晓瀛, 谭翔, 魏急波. 基于边缘智能的频谱地图构建与分发方法 Construction and Distribution Method of REM Based on Edge Intelligence 计算机科学, 2022, 49(9): 236-241. https://doi.org/10.11896/jsjkx.220400148
[2]	孙慧婷, 范艳芳, 马孟晓, 陈若愚, 蔡英. VEC中基于动态定价的车辆协同计算卸载方案 Dynamic Pricing-based Vehicle Collaborative Computation Offloading Scheme in VEC 计算机科学, 2022, 49(9): 242-248. https://doi.org/10.11896/jsjkx.210700166
[3]	熊丽琴, 曹雷, 赖俊, 陈希亮. 基于值分解的多智能体深度强化学习综述 Overview of Multi-agent Deep Reinforcement Learning Based on Value Factorization 计算机科学, 2022, 49(9): 172-182. https://doi.org/10.11896/jsjkx.210800112
[4]	史殿习, 赵琛然, 张耀文, 杨绍武, 张拥军. 基于多智能体强化学习的端到端合作的自适应奖励方法 Adaptive Reward Method for End-to-End Cooperation Based on Multi-agent Reinforcement Learning 计算机科学, 2022, 49(8): 247-256. https://doi.org/10.11896/jsjkx.210700100
[5]	袁唯淋, 罗俊仁, 陆丽娜, 陈佳星, 张万鹏, 陈璟. 智能博弈对抗方法:博弈论与强化学习综合视角对比分析 Methods in Adversarial Intelligent Game:A Holistic Comparative Analysis from Perspective of Game Theory and Reinforcement Learning 计算机科学, 2022, 49(8): 191-204. https://doi.org/10.11896/jsjkx.220200174
[6]	于滨, 李学华, 潘春雨, 李娜. 基于深度强化学习的边云协同资源分配算法 Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning 计算机科学, 2022, 49(7): 248-253. https://doi.org/10.11896/jsjkx.210400219
[7]	李梦菲, 毛莺池, 屠子健, 王瑄, 徐淑芳. 基于深度确定性策略梯度的服务器可靠性任务卸载策略 Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient 计算机科学, 2022, 49(7): 271-279. https://doi.org/10.11896/jsjkx.210600040
[8]	袁昊男, 王瑞锦, 郑博文, 吴邦彦. 基于Fabric的电子病历跨链可信共享系统设计与实现 Design and Implementation of Cross-chain Trusted EMR Sharing System Based on Fabric 计算机科学, 2022, 49(6A): 490-495. https://doi.org/10.11896/jsjkx.210500063
[9]	方韬, 杨旸, 陈佳馨. D2D辅助移动边缘计算下的卸载策略优化 Optimization of Offloading Decisions in D2D-assisted MEC Networks 计算机科学, 2022, 49(6A): 601-605. https://doi.org/10.11896/jsjkx.210200114
[10]	刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems 计算机科学, 2022, 49(6A): 619-627. https://doi.org/10.11896/jsjkx.210600165
[11]	郭雨欣, 陈秀宏. 融合BERT词嵌入表示和主题信息增强的自动摘要模型 Automatic Summarization Model Combining BERT Word Embedding Representation and Topic Information Enhancement 计算机科学, 2022, 49(6): 313-318. https://doi.org/10.11896/jsjkx.210400101
[12]	范静宇, 刘全. 基于随机加权三重Q学习的异策略最大熵强化学习算法 Off-policy Maximum Entropy Deep Reinforcement Learning Algorithm Based on RandomlyWeighted Triple Q -Learning 计算机科学, 2022, 49(6): 335-341. https://doi.org/10.11896/jsjkx.210300081
[13]	谢万城, 李斌, 代玥玥. 空中智能反射面辅助边缘计算中基于PPO的任务卸载方案 PPO Based Task Offloading Scheme in Aerial Reconfigurable Intelligent Surface-assisted Edge Computing 计算机科学, 2022, 49(6): 3-11. https://doi.org/10.11896/jsjkx.220100249
[14]	周天清, 岳亚莉. 超密集物联网络中多任务多步计算卸载算法研究 Multi-Task and Multi-Step Computation Offloading in Ultra-dense IoT Networks 计算机科学, 2022, 49(6): 12-18. https://doi.org/10.11896/jsjkx.211200147
[15]	洪志理, 赖俊, 曹雷, 陈希亮, 徐志雄. 基于遗憾探索的竞争网络强化学习智能推荐方法研究 Study on Intelligent Recommendation Method of Dueling Network Reinforcement Learning Based on Regret Exploration 计算机科学, 2022, 49(6): 149-157. https://doi.org/10.11896/jsjkx.210600226

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

一种基于深度强化学习与概率性能感知的边缘计算环境多工作流卸载方法

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0