计算机科学 ›› 2021, Vol. 48 ›› Issue (1): 40-48.doi: 10.11896/jsjkx.200900195
所属专题: 智能化边缘计算
马堉银1, 郑万波2, 马勇3, 刘航1, 夏云霓1, 郭坤银1, 陈鹏4, 刘诚武5
MA Yu-yin1, ZHENG Wan-bo2, MA Yong3, LIU Hang1, XIA Yun-ni1, GUO Kun-yin1, CHEN Peng4, LIU Cheng-wu5
摘要: 移动边缘计算是一种新兴的分布式和泛在计算模式,其将计算密集型和时延敏感型任务转移到附近的边缘服务器,有效缓解了移动终端资源不足的问题,显著减小了用户与计算处理节点之间的通信传输开销。然而,如果多个用户同时提出计算密集型任务请求,特别是流程化的工作流任务请求,边缘计算环境往往难以有效地进行响应,并会造成任务拥塞。另外,受任务负载、电力供给、通信能力的实时变化等不利因素的影响,边缘服务器本身的性能总是处于波动和变化中,从而为保证任务执行效能和用户感知服务效率带来了挑战。针对上述问题,文中提出了一种基于深度Q网络(DQN)与概率性能感知机制的边缘计算环境多工作流调度方法。首先对边缘云服务器的历史性能数据进行概率分析,然后利用获得的性能概率分布数据驱动DQN模型,不断迭代优化,生成多工作流的卸载策略。在实验验证环节,基于边缘服务器位置数据集、性能测试数据和多个科学工作流模板,在反映不同系统负载水平的多个场景下进行了模拟实验。实验结果表明,所提方法在多工作流执行效率方面明显优于传统方法。
中图分类号:
[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. |
[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 |
|