系统仿真学报 ›› 2021, Vol. 33 ›› Issue (3): 509-520.doi: 10.16182/j.issn1004731x.joss.20-0584
所属专题: 特约稿件
• 专家约稿 • 下一篇
王凌, 吴楚格, 范文慧
收稿日期:
2020-08-10
修回日期:
2020-09-03
出版日期:
2021-03-18
发布日期:
2021-03-18
作者简介:
王凌(1972-),男,博士,教授,研究方向为智能优化调度理论与方法等。E-mail:wangling@mail.tsinghua.edu.cn
基金资助:
Wang Ling, Wu Chuge, Fan Wenhui
Received:
2020-08-10
Revised:
2020-09-03
Online:
2021-03-18
Published:
2021-03-18
摘要: 随着物联网和移动终端的迅速发展,边缘计算技术应运而生,通过将计算和存储配置在互联网边缘,处理物联网终端产生的大量数据,应对时延敏感型应用请求。为提高计算资源使用效率,优化性能指标,边缘计算资源分配与任务调度优化问题受到了广泛关注。边缘计算资源的地理分散性、异构性以及对性能、能耗、费用、稳定性等的需求,增加了优化调度的复杂性。通过介绍边缘计算和物联网、云计算协同的系统模型,给出优化的指标、调度模型及其求解算法,包括精确算法、启发式方法及智能优化方法等,归纳典型应用案例,指出有待进一步研究的内容和方向,有助于促进边缘计算的发展。
中图分类号:
王凌, 吴楚格, 范文慧. 边缘计算资源分配与任务调度优化综述[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. |
[1] | 李智杰, 石昊琦, 李昌华, 张颉. 基于改进遗传算法的影像中心布局优化方法[J]. 系统仿真学报, 2022, 34(6): 1173-1184. |
[2] | 段绍米, 罗会龙, 刘海鹏. 人群搜索和樽海鞘群的混合算法优化PID参数[J]. 系统仿真学报, 2022, 34(6): 1230-1246. |
[3] | 赵也践, 王艳红, 张俊, 于洪霞, 田中大. 改进Q学习算法在作业车间调度问题中的应用[J]. 系统仿真学报, 2022, 34(6): 1247-1258. |
[4] | 程鹏, 张文柱, 谢书翰, 杨子轩. 基于移动边缘计算的车联网任务卸载研究与仿真[J]. 系统仿真学报, 2022, 34(6): 1304-1311. |
[5] | 张其文, 张斌. 基于教学优化算法求解置换流水车间调度问题[J]. 系统仿真学报, 2022, 34(5): 1054-1063. |
[6] | 古鹏飞, 张霖, 陈真, 叶俊杰. 基于X语言的起飞场景民机协同设计与仿真一体化方法[J]. 系统仿真学报, 2022, 34(5): 929-943. |
[7] | 刘永奎, 曾鸣, 张霖, 郭金维, 原思阳, 平垚垚. 基于微服务架构的云制造调度仿真系统设计与开发[J]. 系统仿真学报, 2022, 34(4): 700-711. |
[8] | 叶澍, 吉晓东, 李文华. 全双工无人机中继系统物理层安全性能研究[J]. 系统仿真学报, 2022, 34(4): 788-796. |
[9] | 高鑫宇, 倪静. 救援效率视角下灾后动态应急配送网络优化[J]. 系统仿真学报, 2022, 34(4): 806-816. |
[10] | 薛乃阳, 丁丹, 王红敏, 樊怡乐, 刘仲谦. 引入微元法思想的混合测控资源联合调度方法[J]. 系统仿真学报, 2022, 34(4): 826-835. |
[11] | 王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919. |
[12] | 叶飞, 李梓晴, 赖李媛君. 分布式车间生产维修联合调度仿真优化方法[J]. 系统仿真学报, 2022, 34(4): 688-699. |
[13] | 冯开团, 袁杰. 基于改进注水算法的离散车间任务分配问题研究[J]. 系统仿真学报, 2022, 34(4): 768-776. |
[14] | 陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469. |
[15] | 李建锋, 卢迪, 李贺香. 一种改进的原子搜索算法[J]. 系统仿真学报, 2022, 34(3): 490-502. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||