计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 277-283.doi: 10.11896/jsjkx.190600048
简琤峰, 平靖, 张美玉
JIAN Cheng-feng, PING Jing, ZHANG Mei-yu
摘要: 边缘计算有高实时性和大数据交互处理的需求,边缘异构节点间的调度时耗长、通信时延高以及负载不均衡是影响边缘计算性能的核心问题,传统的云计算平台难以满足新的要求。文中研究了在边缘计算环境下Storm边缘节点的调度优化方法,建立了面向边缘计算的Storm任务卸载调度模型。针对拓扑任务在边缘异构节点间的实时动态分配问题,提出了一种启发式动态规划算法(Inspire Dynamic Programming,IDP),通过改变Storm的Task实例的排序分配方式以及Task实例和Slot任务槽的映射关系实现全局的优化调度;同时,针对拓扑任务的并发度受限于JVM栈深度的缺陷,提出了一种基于蝙蝠算法的调度策略。实验结果表明,与Storm调度算法相比,所提算法在边缘节点CPU利用率指标上平均提升了约60%,在集群的吞吐量指标上平均提升了约8.2%,因此能够满足边缘节点之间的高实时性处理要求。
中图分类号:
[1]GUO H,LIU J,ZHANG J,et al.Mobile-edge computation offloading for ultradense IoT networks[J].IEEE Internet of Things Journal,2018,5(6):4977-4988. [2]PHAM Q,LE L B,CHUNG S,et al.Mobile edge computingwith wireless backhaul:Joint task offloading and resource allocation[J].IEEE Access,2019,7:16444-16459. [3]ZHANG Y,CHEN X,CHEN Y,et al.Cost Efficient Scheduling for Delay-Sensitive Tasks in Edge Computing System[C]//Proceedings of 2018 IEEE International Conference on Services Computing.2018:73-80. [4]KIM Y,KWAK J,CHONG S.Dual-Side Optimization for Cost-Delay Tradeoff in Mobile Edge Computing[J].IEEE Transactions on Vehicular Technology,2017,PP(99):1-1. [5]ZENG D,GU L,GUO S,et al.Joint Optimization of TaskScheduling and Image Placement in Fog Computing Supported Software-Defined Embedded System[J].IEEE Transactions on Computers,2016,65(12):1-1. [6]GU L,ZENG D,GUO S,et al.Cost Efficient Resource Management in Fog Computing Supported Medical Cyber-Physical System[J].IEEE Transactions on Emerging Topics in Computing,2017,5(1):108-119. [7]JIAN C F,CHEN J W,PING J,et al.An Improved Chaotic Bat Swarm Scheduling Learning Model on Edge Computing[J].IEEE Access,2019,7(1):58602-58610. [8]CHENG B.Edge-Computing-Aware Deployment of Stream Processing Tasks Based on Topology-External Information:Model,Algorithms,and a Storm-Based Prototype[C]//IEEE International Congress on Big Data.IEEE,2016. [9]PENG B,HOSSEINI M,HONG Z,et al.R-Storm:Resource-Aware Scheduling in Storm[C]//Middleware Conference.ACM,2015. [10]ANIELLO L,BALDONI R,QUERZONI L.Adaptive OnlineScheduling in Storm[C]//Proceedings of the 7th ACM International Conference on Distributed Event-based Systems.ACM,2013:207-218. [11]CARDELLINI V,GRASSI V,PRESTI F,et al.DistributedQoS-aware Scheduling in Storm[C]//ACM International Conference on Distributed Event-Based Systems.ACM:2015:344-267. [12]JIAN C F,LU T,ZHANG M Y.Storm Scheduling Optimization Method Based on Graph Partitioning Strategy[J].Journal of Chinese Computer Systems,2018,39(11):2538-2544. [13]ESKANDARI L,HUANG Z,EYERS D.P-Scheduler:adaptivehierarchical scheduling in apache storm[C]//Proceedings of the Australasian Computer Science Week Multiconference.ACM,2016. [14]CHEN Z H,XU J L,TANG J,et al.G-Storm:GPU-enabledHigh-throughput Online Data Processing in Storm[C]//2015 IEEE International Conference on Big Data.IEEE,2015:307-312. [15]ZHANG W,HU Y,HE H,et al.Linear and dynamic programming algorithms for real-time task scheduling with task duplication[J].The Journal of Supercomputing,2017,75(2):494-509. [16]XIE Y,ZHU Y,WANG Y,et al.A novel directional and non-local-convergent particle swarm opti-mization based workflow scheduling in cloud–edge environment[J].Future Generation Computer Systems,2019,97:361-378. [17]MOON Y J,YU H C,GIL J M,et al.A slave ants based ant co-lony optimization algorithm for task scheduling in cloud computing environments[J].Human-centric Computing and Information Sciences,2017,7(1):28. [18]DENG X H,GUAN P Y,WAN Z W,et al.Integrated TrustBased Resource Cooperation in Edge Computing[J].Journal of Computer Research and Development,2018,55(3):449-477. [19]FU X.Task Scheduling Scheme Based on Sharing Mechanism and Swarm Intelligence Optimization Algorithm in Cloud Computing[J].Journal of Computer Science,2018,45(6):290-294. [20]KONGKAEW W.Bat algorithm in discrete optimization:A review of recent applications[J].Songklanakarin Journal of Scie-nce and Technology(SJST),2017,39(5):641-650. [21]JIAN C F,CHEN J W,PING J,et al.An Improved Chaotic Bat Swarm Scheduling Learning Model on Edge Computing[J].IEEE Access,2019,7(1):58602-58610. [22]JIAN C F,LI M,QIU K Y,et al.An improved NBA-basedSTEP design intention feature recognition[J].Future Generation Computer Systems,2018,88(6):357-362. |
[1] | 孙慧婷, 范艳芳, 马孟晓, 陈若愚, 蔡英. VEC中基于动态定价的车辆协同计算卸载方案 Dynamic Pricing-based Vehicle Collaborative Computation Offloading Scheme in VEC 计算机科学, 2022, 49(9): 242-248. https://doi.org/10.11896/jsjkx.210700166 |
[2] | 陈莹, 郝应光, 王洪玉, 王坤. 基于局部梯度强度图的动态规划检测前跟踪算法 Dynamic Programming Track-Before-Detect Algorithm Based on Local Gradient and Intensity Map 计算机科学, 2022, 49(8): 150-156. https://doi.org/10.11896/jsjkx.210700135 |
[3] | 于滨, 李学华, 潘春雨, 李娜. 基于深度强化学习的边云协同资源分配算法 Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning 计算机科学, 2022, 49(7): 248-253. https://doi.org/10.11896/jsjkx.210400219 |
[4] | 李梦菲, 毛莺池, 屠子健, 王瑄, 徐淑芳. 基于深度确定性策略梯度的服务器可靠性任务卸载策略 Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient 计算机科学, 2022, 49(7): 271-279. https://doi.org/10.11896/jsjkx.210600040 |
[5] | 袁昊男, 王瑞锦, 郑博文, 吴邦彦. 基于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 |
[6] | 方韬, 杨旸, 陈佳馨. D2D辅助移动边缘计算下的卸载策略优化 Optimization of Offloading Decisions in D2D-assisted MEC Networks 计算机科学, 2022, 49(6A): 601-605. https://doi.org/10.11896/jsjkx.210200114 |
[7] | 刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 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 |
[8] | 谢万城, 李斌, 代玥玥. 空中智能反射面辅助边缘计算中基于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 |
[9] | 周天清, 岳亚莉. 超密集物联网络中多任务多步计算卸载算法研究 Multi-Task and Multi-Step Computation Offloading in Ultra-dense IoT Networks 计算机科学, 2022, 49(6): 12-18. https://doi.org/10.11896/jsjkx.211200147 |
[10] | 柳鹏, 刘波, 周娜琴, 彭心怡, 林伟伟. 混合云工作流调度综述 Survey of Hybrid Cloud Workflow Scheduling 计算机科学, 2022, 49(5): 235-243. https://doi.org/10.11896/jsjkx.210300303 |
[11] | 彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰. 视频缓存策略中QoE和能量效率的公平联合优化 Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos 计算机科学, 2022, 49(4): 312-320. https://doi.org/10.11896/jsjkx.210800027 |
[12] | 张海波, 张益峰, 刘开健. 基于NOMA-MEC的车联网任务卸载、迁移与缓存策略 Task Offloading,Migration and Caching Strategy in Internet of Vehicles Based on NOMA-MEC 计算机科学, 2022, 49(2): 304-311. https://doi.org/10.11896/jsjkx.210100157 |
[13] | 林潮伟, 林兵, 陈星. 边缘环境下基于模糊理论的科学工作流调度研究 Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment 计算机科学, 2022, 49(2): 312-320. https://doi.org/10.11896/jsjkx.201000102 |
[14] | 梁俊斌, 张海涵, 蒋婵, 王天舒. 移动边缘计算中基于深度强化学习的任务卸载研究进展 Research Progress of Task Offloading Based on Deep Reinforcement Learning in Mobile Edge Computing 计算机科学, 2021, 48(7): 316-323. https://doi.org/10.11896/jsjkx.200800095 |
[15] | 薛艳芬, 高继梅, 范贵生, 虞慧群, 许亚杰. 边缘计算中基于能耗感知的容错协同任务执行算法 Energy-aware Fault-tolerant Collaborative Task Execution Algorithm in Edge Computing 计算机科学, 2021, 48(6A): 374-382. https://doi.org/10.11896/jsjkx.200900027 |
|