边缘计算资源分配与任务调度优化综述

doi:10.16182/j.issn1004731x.joss.20-0584

摘要/Abstract

摘要： 随着物联网和移动终端的迅速发展,边缘计算技术应运而生,通过将计算和存储配置在互联网边缘,处理物联网终端产生的大量数据,应对时延敏感型应用请求。为提高计算资源使用效率,优化性能指标,边缘计算资源分配与任务调度优化问题受到了广泛关注。边缘计算资源的地理分散性、异构性以及对性能、能耗、费用、稳定性等的需求,增加了优化调度的复杂性。通过介绍边缘计算和物联网、云计算协同的系统模型,给出优化的指标、调度模型及其求解算法,包括精确算法、启发式方法及智能优化方法等,归纳典型应用案例,指出有待进一步研究的内容和方向,有助于促进边缘计算的发展。

关键词: 边缘计算, 资源分配, 调度, 优化, 建模与仿真

Abstract: With the rapid development of Internet of Things (IoT) and mobile terminals, the concept of edge computing arises. By moving the computation and storage capacity to the edge of network, edge computing is able to deal with a large amount of data produced by IoT devices and the responsive request from IoT application. To improve the utility of edge resource, the quality of service and quality of user experience, resource allocation and task scheduling optimization problems under edge computing attract wide attention. It becomes more difficult due to the geographic separated and heterogeneous features of edge computing resource as well as the requirements of performance, energy consumption, cost and stability and introduces the system models of edge computing, IoT and cloud computing, presents the optimization metrics, scheduling models and solution optimization, including exact algorithms, heuristic methods and intelligent optimization algorithms. In addition, typical application cases, and points out the further research contents and directions are provided to promote the development of edge computing.

Key words: edge computing, resource allocation, scheduling, optimization, modeling and simulation

中图分类号:

TP391

王凌,吴楚格,范文慧 . 边缘计算资源分配与任务调度优化综述[J]. 系统仿真学报, 2021, 33(3): 509-520.

Wang Ling,Wu Chuge,Fan Wenhui . A Survey of Edge Computing Resource Allocation and Task Scheduling Optimization[J]. Journal of System Simulation, 2021, 33(3): 509-520.

参考文献

[1] Pang H H, Tan K L.Authenticating Query Results in Edge Computing[C]//20th International Conference on Data Engineering. Boston, MA, USA: IEEE Comput Soc, 2004: 560-571.
[2] Bonomi F, Milito R, Zhu J, et al.Fog Computing and its Role in the Internet of Things[C]//1st Edition MCC Workshop Mobile Cloud Comput. NY, USA: ACM, 2012: 13-16.
[3] Vaquero L M, Rodero-Merino L.Finding Your Way in the Fog: Towards a Comprehensive Definition of Fog Computing[J]. ACM SIGCOMM Computer Communication Review (S0146-4833), 2014, 44(5): 27-32.
[4] Hu P, Dhelim S, Ning H, et al.Survey on Fog Computing: Architecture, Key Technologies, Applications and Open Issues[J]. Journal of Network and Computer Applications (S1084-8045), 2017, 98(11): 27-42.
[5] Yousefpour A, Fung C, Nguyen T, et al.All One Needs to Know About Fog Computing and Related Edge Computing Paradigms: A Complete Survey[J]. Journal of Systems Architecture (S1383-7621), 2019, 98(1): 289-330.
[6] O. C.Architecture Working Group, Open Fog Reference Architecture for Fog Computing[R]. 2017, 1(1): 162.
[7] Shi W, Cao J, Zhang Q, et al.Edge Computing: Vision and Challenges[J]. IEEE Internet of Things Journal (S2327-4662), 2016, 3(5): 637-646.
[8] Hussain H, Malik S U R, Hameed A, et al. A Survey on Resource Allocation in High Performance Distributed Computing Systems[J]. Parallel Computing (S0167-8191), 2013, 39(11): 709-736.
[9] Bellendorf J, Mann Z Á.Classification of Optimization Problems in Fog Computing[J]. Future Generation Computer Systems (S0167-739X), 2020, 107(1): 158-176.
[10] Brogi A, Forti S, Guerrero C, et al.How to Place Your Apps in the Fog: State of the Art and Open Challenges[J]. Software: Practice and Experience (S0167-739X), 2019, 1(1): 1-8.
[11] Wu C, Li W, Wang L, et al.Hybrid Evolutionary Scheduling for Energy-efficient Fog-enhanced Internet of Things[J]. IEEE Transactions on Cloud Computing (S2168-7161), 2018, 1(1): 1-1.
[12] Atzori L, Iera A, Morabito G.The Internet of Things: A Survey[J]. Computer Networks (S1389-1286), 2010, 54(15): 2787-2805.
[13] Bonomi F, Milito R, Natarajan P, et al.Fog Computing: A Platform for Internet of Things and Analytics. N. Bessis, C. Dobre. Big Data and Internet of Things: A roadmap for smart environments[M]. Cham: Springer, 2014, 546: 169-186.
[14] Mahmud R, Srirama S N, Ramamohanarao K, et al.Quality of Experience (QoE)-aware Placement of Applications in Fog Computing Environments[J]. Journal of Parallel and Distributed Computing (S0743-7315), 2019, 132(1): 190-203.
[15] Buyya R., Srirama S.N. 雾计算与边缘计算: 原理和范式[M]. NJ, USA: Wiley, 2019: 31-50.
[16] Wu H, Yue K, Hsu C, et al.Deviation-based Neighborhood Model for Context-aware QoS Prediction of Cloud and IoT Services[J]. Future Generation Computer Systems (S0167-739X), 2017, 76(1): 550-560.
[17] Brogi A, Forti S.QoS-Aware Deployment of IoT Applications Through the Fog[J]. IEEE Internet of Things Journal (S2327-4662), 2017, 4(5): 1185-1192.
[18] Yousefpour A, Ishigaki G, Gour R, et al.On Reducing IoT Service Delay Via Fog Offloading[J]. IEEE Internet of Things Journal (S2327-4662), 2018, 5(2): 998-1010.
[19] Merlino G, Arkoulis S, Distefano S, et al.Mobile Crowdsensing as a Service[J]. Future Generation Computer Systems (S0167-739X), 2016, 56(1): 623-639.
[20] Lomotey R K, Pry J, Sriramoju S.Wearable IoT Data Stream Traceability in a Distributed Health Information System[J]. Pervasive and Mobile Computing (S1574-1192), 2017, 40(1): 692-707.
[21] Desikan K E S, Srinivasan M, Murthy C S R. A Novel Distributed Latency-aware Data Processing in Fog Computing-enabled IoT Networks[C]//Proc. of the ACM Workshop on Distributed Information Processing in Wireless Networks. Chennai, India: ACM, 2017: 1-6.
[22] Gorlatova M, Inaltekin H, Chiang M.Characterizing Task Completion Latencies in Fog Computing[J].Computer Networks (S1389-1286), 2020, 181:107526.
[23] Abbott R K, Garcia-Molina H.Scheduling Real-time Transactions: A Performance Evaluation[J]. ACM Transactions on Database Systems (S0362-5915), 1992, 17(3): 513-560.
[24] Meng J, Tan H, Li X Y, et al.Online Deadline-aware Task Dispatching and Scheduling in Edge Computing[J]. IEEE Transactions on Parallel and Distributed Systems (S1045-9219), 2020, 31(6): 1270-1286.
[25] Ye D, Wu M, Tang S, et al.Scalable Fog Computing with Service Offloading in Bus Networks[C]//3rd International Conference on Cyber Security and Cloud Computing. Beijing, China: IEEE, 2016: 247-251.
[26] Verba N, Chao K M, Lewandowski J, et al.Modeling Industry 4.0 based Fog Computing Environments for Application Analysis and Deployment[J]. Future Generation Computer Systems (S0167-739X), 2019, 91(1): 48-60.
[27] Wu C, Wang L.A Deadline-aware Estimation of Distribution Algorithm for Resource Scheduling in Fog Computing Systems[C]//IEEE Congress on Evolutionary Computation. Wellington, New Zealand: IEEE, 2019: 660-666.
[28] 林闯, 胡杰, 孔祥震. 用户体验质量(QoE)的模型与评价方法综述[J]. 计算机学报, 2012, 35(1): 1-15.
Lin Chuang, Hu Jie, Kong Xiangzhen.Survey on Models and Evaluation of Quality of Experience[J]. Chinese Journal of Computers, 2012, 35(1): 1-15.
[29] Lin Y, Shen H.Cloud Fog: Towards high quality of experience in cloud gaming[C]//44th International Conference on Parallel Processing. Beijing, China: IEEE, 2015: 500-509.
[30] Aazam M, St-Hilaire M, Lung C, et al.MeFoRE: QoE based Resource Estimation at Fog to Enhance QoS in IoT[C]//23rd International Conference on Telecommunications. Thessaloniki, Greece: IEEE, 2016: 1-5.
[31] Jalali F, Hinton K, Ayre R, et al.Fog Computing May Help to Save Energy in Cloud Computing[J]. IEEE Journal on Selected Areas in Communications (S0733-8716), 2016, 34(5): 1728-1739.
[32] Halgamuge M N, Zukerman M, Ramamohanarao K, et al.An Estimation of Sensor Energy Consumption[J]. Progress in Electromagnetics Research B (S1559-8985), 2009, 12(12): 259-295.
[33] Li W, Delicato F C, Zomaya A Y.Adaptive Energy-efficient Scheduling for Hierarchical Wireless Sensor Networks[J]. ACM Transactions on Sensor Networks (S1550-4859), 2013, 9(3): 1-34.
[34] Dietrich I, Dressler F.On the Lifetime of Wireless Sensor Networks[J]. ACM Transactions on Sensor Networks (S1550-4859), 2009, 5(1): 1-39.
[35] Deng R, Lu R, Lai C, et al.Optimal Workload Allocation in Fog-cloud Computing Towards Balanced Delay and Power Consumption[J]. IEEE Internet of Things Journal (S2327-4662), 2016, 1(1): 1-1.
[36] Wan J, Chen B, Wang S, et al.Fog Computing for Energy-aware Load Balancing and Scheduling in Smart Factory[J]. IEEE Transactions on Industrial Informatics (S1551-3203), 2018, 14(10): 4548-4556.
[37] 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 (S2168-6750), 2017, 5(1): 108-119.
[38] Sturzinger E, Tornatore M, Mukherjee B.Application- aware Resource Provisioning in a Heterogeneous Internet of Things[C]//International Conference on Optical Network Design and Modeling. Budapest: IEEE, 2017: 1-6.
[39] Kumar K, Liu J, Lu Y H, et al.A Survey of Computation Offloading for Mobile Systems[J]. Mobile Networks and Applications (S1383-469X), 2013, 18(1): 129-140.
[40] Aazam M, Zeadally S, Harras K A.Offloading in Fog Computing for IoT: Review, Enabling Technologies, and Research Opportunities[J]. Future Generation Computer Systems (S0167-739X), 2018, 87(1): 278-289.
[41] Fricker C, Guillemin F, Robert P, et al.Analysis of an Offloading Scheme for Data Centers in the Framework of Fog Computing[J]. ACM Transactions on Modeling and Performance Evaluation of Computing Systems(S2376-3639), 2016, 1(4): 16-34.
[42] Wang X, Ning Z, Wang L.Offloading in Internet of Vehicles: A Fog-enabled Real-time Traffic Management System[J]. IEEE Transactions on Industrial Informatics (S1551-3203), 2018, 14(10): 4568-4578.
[43] Zhao X, Zhao L, Liang K.An Energy Consumption Oriented Offloading Algorithm for Fog Computing[C]//12th International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness. Cham: Springer, 2016: 293-301.
[44] Xiao Y, Krunz M.QoE and Power Efficiency Tradeoff for Fog Computing Networks with Fog Node Cooperation[C]// IEEE Conference on Computer Communications. Atlanta, USA: IEEE, 2017: 1-9.
[45] Kattepur A, Dohare H, Mushunuri V, et al.Resource Constrained Offloading in Fog Computing[C]//1st Workshop on Middleware for Edge Clouds & Cloudlets. Trento, Italy: ACM, 2016: 1-6.
[46] Pisinger D.Where Are the Hard Knapsack Problems[J]. Computers & Operations Research (S1873-765X), 2005, 32(9): 2271-2284.
[47] Skarlat O, Nardelli M, Schulte S, et al.Towards QoS-aware Fog Service Placement[C]//1st International Conference on Fog and Edge Computing. Madrid, Spain: IEEE, 2017: 89-96.
[48] Zeng D, Gu L, Guo S, et al.Joint Optimization of Task Scheduling and Image Placement in Fog Computing Supported Software-Defined Embedded System[J]. IEEE Transactions on Computers (S0018-9340), 2016, 65(12): 3702-3712.
[49] Mennes R, Spinnewyn B, Latre S, et al.GRECO: A Distributed Genetic Algorithm for Reliable Application Placement in Hybrid Clouds[C]//5thInternational Conference on Cloud Networking. Pisa, Italy: IEEE, 2016: 14-20.
[50] Rahbari D, Nickray M.Scheduling of Fog Networks with Optimized Knapsack by Symbiotic Organisms Search[C]// 21stConference of Open Innovations Association. Helsinki: IEEE, 2017: 278-283.
[51] Tang Z, Zhou X, Zhang F, et al.Migration Modeling and Learning Algorithms for Containers in Fog Computing[J]. IEEE Transactions on Services Computing (S1939-1374), 2019, 12(5): 712-725.
[52] Kwok Y, Ahmad I.Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors[J]. ACM Computing Surveys (S1557-7341), 1999, 31(4): 406-471.
[53] Kao Y, Krishnamachari B.Optimizing Mobile Computational Offloading with Delay Constraints[C]// IEEE Global Communications Conference. TX, Austin: IEEE, 2014: 2289-2294.
[54] Sundar S, Liang B.Offloading Dependent Tasks with Communication Delay and Deadline Constraint[C]//IEEE Conference on Computer Communications. Honolulu, HI: IEEE, 2018: 37-45.
[55] Mahmoodi S E, Uma R N, Subbalakshmi K P.Optimal Joint Scheduling and Cloud Offloading for Mobile Applications[J]. IEEE Transactions on Cloud Computing (S2168-7161), 2019, 7(2): 301-313.
[56] Selvi S, Manimegalai D.DAG Scheduling in Heterogeneous Computing and Grid Environments Using Variable Neighborhood Search Algorithm[J]. Applied Artificial Intelligence (S0883-9514), 2017, 31(2): 134-173.
[57] Topcuoglu H, Hariri S, Min-You Wu.Performance-effective and Low-complexity Task Scheduling for Heterogeneous Computing[J]. IEEE Transactions on Parallel & Distributed Systems (S1045-9219), 2002, 13(3): 260-274.
[58] Liou J, Palis M A.A Comparison of General Approaches to Multiprocessor Scheduling[C]//11th International Parallel Processing Symposium. Switzerland: IEEE, 1997: 152-156.
[59] Xu Y, Li K, He L, et al.A DAG Scheduling Scheme on Heterogeneous Computing Systems Using Double Molecular Structure-Based Chemical Reaction Optimization[J]. Journal of Parallel and Distributed Computing (S0743-7315), 2013, 73(9): 1306-1322.
[60] Pham X Q, Huh E N.Towards Task Scheduling in a Cloud-fog Computing System[C]//18th Asia-Pacific Network Operations and Management Symposium. Kanazawa, Japan: IEEE, 2016: 1-4.
[61] Stavrinides G L, Karatza H D.A Hybrid Approach to Scheduling Real-time IoT Workflows in Fog and Cloud Environments[J]. Multimedia Tools and Applications (S1380-7501), 2019, 78(17): 24639-24655.
[62] Skarlat O, Nardelli M, Schulte S, et al.Optimized IoT Service Placement in the Fog[J]. Service Oriented Computing and Applications (S1863-2386), 2017, 11(4): 427-443.
[63] 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 (S0167-739X), 2019, 97(1): 361-378.
[64] 赵梓铭, 刘芳, 蔡志平, 等. 边缘计算:平台、应用与挑战[J], 计算机研究与发展, 2018, 55(2): 327-337.
Zhao Ziming, Liu Fang, Cai Zhiping, et al.Edge Computing: Platforms, Applications and Challenges[J]. Journal of Computer Research and Development, 2018, 55(2): 327-337.
[65] Sonmez C, Ozgovde A, Ersoy C, et al.EdgeCloudSim: An Environment for Performance Evaluation of Edge Computing Systems[J]. Transactions on Emerging Telecommunications Technologies (S2161-3915), 2018, 29(11): 1-1.
[66] Gupta H, Dastjerdi A V, Ghosh S K, et al.iFogSim: A Toolkit for Modeling and Simulation of Resource Management Techniques in the Internet of Things, Edge and Fog computing environments[J]. Software - Practice and Experience (S0038-0644), 2017, 47(9): 1275-1296.
[67] Jonathan M, Nan W, Ashish T, et al.DeFog: fog Computing Benchmarks[C]//Proc 4th ACM/IEEE Symposium on Edge Computing. New York, USA: ACM Press, 2019: 47-58.
[68] Sharma S, Saini H.A Novel Four-tier Architecture for Delay Aware Scheduling and Load Balancing in Fog Environment[J]. Sustainable Computing: Informatics and Systems (S2210-5379), 2019, 1(1): 1-8.
[69] Xia C, Li W, Chang X, et al.Edge-based Energy Management for Smart Homes[C]//16th Dependable, Autonomic and Secure Computing. Athens, Greece: IEEE, 2018: 849-856.
[70] 翟岩龙, 孙文心, 包天虹, 等. 基于微服务的边缘侧仿真方法及框架研究[J]. 系统仿真学报, 2018, 30(12): 44-53.
Zhai Yanlong, Sun Wenxin, Bao Tianhong, et al.Edge-side Simulation Method and Framework Based on Micro-services[J]. Journal of System Simulation, 2018, 30(12): 44-53.