Review of Research on Computing-Intensive Task Scheduling in Edge Environments

doi:10.3778/j.issn.1002-8331.2202-0243

Abstract

Abstract: With the dramatic increase in the number of mobile devices and the widespread use of computing-intensive applications such as face recognition, internet of vehicles and virtual reality. In order to achieve the optimal matching of tasks and collaborative resources to meet user QoS requests, using a task scheduling scheme for reasonably computing-intensive applications can solve the problems of extended time, high cost, unbalanced load and low resource utilization in the edge cloud center. Firstly, the scheduling framework, execution process, application scenarios and performance indicators of computing-intensive application tasks in the edge computing environment are described. Secondly, this paper analyzes and compares three task scheduling schemes from the optimization goals of time and cost, energy consumption and resource utilization, load balancing and throughput, and summarizes the advantages, disadvantages and applicable scenarios of these schemes. Then, by analyzing the SDN-based edge computing architecture in the 5G environment, the task scheduling strategy for edge computing-intensive data packet based on SDN, task scheduling strategy for computing-intensive application based on deep reinforcement learning, multi-objective cross-layer task scheduling strategy in 5G IoV network are proposed. At last, the challenges of task scheduling in edge computing environment are summarized from the aspects of fault-tolerant scheduling, dynamic microservice scheduling, crowd aware scheduling, security and privacy.

Key words: edge computing, computing-intensive, task scheduling, software defined network（SDN）, scheduling strategy

摘要： 随着移动设备数量的急剧增长及计算密集型应用如人脸识别、车联网以及虚拟现实等的广泛使用，为了实现满足用户QoS请求的任务和协同资源的最优匹配，使用合理的计算密集型应用的任务调度方案，从而解决边缘云中心时延长、成本高、负载不均衡和资源利用率低等问题。阐述了边缘计算环境下计算密集型应用的任务调度框架、执行过程、应用场景及性能指标。从时间和成本、能耗和资源利用率以及负载均衡和吞吐量为优化目标的边缘计算环境下计算密集型应用的任务调度策略进行了对比和分析，并归纳出目前这些策略的优缺点及适用场景。通过分析5G环境下基于SDN的边缘计算架构，提出了基于SDN环境下的边缘计算密集型数据包任务调度策略、基于深度强化学习的计算密集型应用的任务调度策略和5G IoV网络中多目标跨层任务调度策略。从容错调度、动态微服务调度、人群感知调度以及安全和隐私等几个方面总结和归纳了目前边缘计算环境中任务调度所面临的挑战。

关键词: 边缘计算, 计算密集型, 任务调度, 软件定义网络（SDN）, 调度策略

LIU Yanpei, ZHU Yunjing, BIN Yanru, CHEN Ningning, WANG Liping. Review of Research on Computing-Intensive Task Scheduling in Edge Environments[J]. Computer Engineering and Applications, 2022, 58(20): 28-42.

刘炎培, 朱运静, 宾艳茹, 陈宁宁, 王丽萍. 边缘环境下计算密集型任务调度研究综述[J]. 计算机工程与应用, 2022, 58(20): 28-42.

References

[1] GHOBAEI-ARANI M，SOURI A，RAHMANIAN A A.Resource management approaches in fog computing：a comprehensive review[J].Journal of Grid Computing，2020，18（1）：1-42.
[2] AMINI MOTLAGH A，MOVAGHAR A，RAHMANI A M.Task scheduling mechanisms in cloud computing：a systematic review[J].International Journal of Communication Systems，2020，33（6）：e4302.
[3] TALEB T，SAMDANIS K，MADA B，et al.On multi-access edge computing：a survey of the emerging 5G network edge cloud architecture and orchestration[J].IEEE Communications Surveys & Tutorials，2017，19（3）：1657-1681.
[4] YANG Y，WANG K，ZHANG G，et al.MEETS：maximal energy efficient task scheduling in homogeneous fog networks[J].IEEE Internet of Things Journal，2018，5（5）：4076-4087.
[5] JIANG K，NI H，SUN P，et al.An improved binary grey wolf optimizer for dependent task scheduling in edge computing[C]//Proceedings of the 2019 21st International Conference on Advanced Communication Technology（ICACT），2019：182-186.
[6] GUO X，LIU L，CHANG Z，et al.Data offloading and task allocation for cloudlet-assisted ad hoc mobile clouds[J].Wireless Networks，2018，24（1）：1-10.
[7] HU H Y，PATEL M，SABELLA D，et al.Mobile edge computing—a key technology towards 5G[J].ETSI White Paper，2015，11（11）：1-16.
[8] WU Y，GUO W，REN J，et al.NO2：speeding up parallel processing of massive compute-intensive tasks[J].IEEE Transactions on Computers，2013，63（10）：2487-2499.
[9] KOLICI V，HERRERO A，XHAFA F.On the performance of Oracle grid engine queuing system for computing intensive applications[J].Journal of Information Processing Systems，2014，10（4）：491-502.
[10] DIETZE R，HOFMANN M，RüNGER G.Water-level scheduling for parallel tasks in compute-intensive application components[J].The Journal of Supercomputing，2016，72（11）：4047-4068.
[11] THAI M T，LIN Y D，LAI Y C，et al.Workload and capacity optimization for cloud-edge computing systems with vertical and horizontal offloading[J].IEEE Transactions on Network and Service Management，2019，17（1）：227-238.
[12] HAZRA A，ADHIKARI M，AMGOTH T，et al.Stackelberg game for service deployment of IoT-enabled applications in 6G-aware fog networks[J].IEEE Internet of Things Journal，2020，8（7）：5185-5193.
[13] MANSOURI N，JAVIDI M M.Cost-based job scheduling strategy in cloud computingenvironments[J].Distri-
buted and Parallel Databases，2020，38（2）：365-400.
[14] BARIKA M，GARG S，ZOMAYA A，et al.Online scheduling technique to handle data velocity changes in stream workflows[J].IEEE Transactions on Parallel and Distributed Systems，2021，32（8）：2115-2130.
[15] RIZVI N，DHARAVATH R，EDLA D R.Cost and makespan aware workflow scheduling in IaaS clouds using hybrid spider monkey optimization[J].Simulation Modelling Practice and Theory，2021，110（3）：102328.
[16] NEDUNCHELIAN R，KOUSHIK K，NAGAPPAN M，et al.Dynamic task scheduling using parallel genetic algorithms for heterogeneous distributed computing[C]//Proceedings of GCA，2006：82-88.
[17] LI C，ZHANG Y H，LUO Y.Neighborhood search-based job scheduling for IoT big data real-time processing in distributed edge-cloud computing environment[J].The Journal of Supercomputing，2021，77：1853-1878.
[18] MOHAMMADZADEH A，MASDARI M，GHAREHCHOPOGH F S.Energy and cost-aware workflow scheduling in cloud computing data centers using a multi-objective optimization algorithm[J].Journal of Network and Systems Management，2021，29（3）：1-34.
[19] ZADE B，MANSOURI N，JAVIDI M M.SAEA：a security-aware and energy-aware task scheduling strategy by parallel squirrel search algorithm in cloud environment[J].Expert Systems with Applications，2021，176（1）：1-30.
[20] FAN Q，LI Z，CHEN X.Deep reinforcement learning based task scheduling in edge computing networks[C]//Proceedings of the 2020 IEEE/CIC International Conference on Communications in China（ICCC），2020：835-840.
[21] SINGH H，BHASIN A，KAVERI P R.QRAS：efficient resource allocation for task scheduling in cloud computing[J].SN Applied Sciences，2021，3（4）：1-7.
[22] LUO Y，LI F W，YANG W，et al.A real-time edge scheduling and adjustment framework for highly customizable factories[J].IEEE Transactions on Industrial Informatics，2020，17（8）：5625-5634.
[23] WEN Z，GARG S，AUJLA G，et al.Running industrial workflow applications in a software-defined multicloud environment using green energy aware scheduling algorithm[J].IEEE Transactions on Industrial Informatics，2021，17（8）：5645-5656.
[24] IJAZ S，MUNIR E U，AHMAD S G，et al.Energy-makespan optimization of workflow scheduling in fog-cloud computing[J].Computing，2021，103（9）：2033-2059.
[25] SV A，PK B，VMAX C，et al.Hybrid electro search with genetic algorithm for task scheduling in cloud computing-ScienceDirect[J].Ain Shams Engineering Journal，2021，12（1）：631-639.
[26] LIU Z，ZHAO A，LIANG M.A port-based forwarding load-balancing scheduling approach for cloud datacenter networks[J].Journal of Cloud Computing，2021，10（1）：1-14.
[27] ZHENG G，ZHANG H，LI Y，et al.5g network-oriented hierarchical distributed cloud computing system resource optimization scheduling and allocation[J].Computer Communications，2020，164：88-99.
[28] MISHRA K，PRADHAN R，MAJHI S K.Quantum-inspired binary chaotic salp swarm algorithm（QBCSSA）-based dynamic task scheduling for multiprocessor cloud computing systems[J].The Journal of Supercomputing，2021，77（9）：10377-10423.
[29] MALARVIZHI N，ASWINI J，SASIKALA S，et al.Multi-parameter optimization for load balancing with effective task scheduling and resource sharing[J].Journal of Ambient Intelligence and Humanized Computing，2021（9）：1-9.
[30] ALQAHTANI F，AMOON M，NASR A A.Reliable scheduling and load balancing for requests in cloud-fog computing[J].Peer-to-Peer Networking and Applications，2021（5）：1-12.
[31] TONG Z，DENG X，CHEN H，et al.DDMTS：a novel dynamic load balancing scheduling scheme under SLA constraints in cloud computing[J].Journal of Parallel and Distributed Computing，2020，149（4）：138-148.
[32] LI C，ZHANG Y，SUN Q，et al.Collaborative caching strategy based on optimization of latency and energy consumption in MEC[J].Knowledge-Based Systems，2021，233：1-18.
[33] DEWANGAN B K，AGARWAL A，CHOUDHURY T，et al.Workload aware autonomic resource management scheme using grey wolf optimization in cloud environment[J].IET Communications，2021，15（14）：1869-1882.
[34] LEI X，ASSEM H，YAHIA I，et al.CogNet：a network management architecture featuring cognitive capabilities[C]//Proceedings of the European Conference on Networks & Communications，2016：325-329.
[35] NEVES P，CALé R，COSTA M R，et al.The SELFNET approach for autonomic management in an NFV/SDN networking paradigm[J].International Journal of Distributed Sensor Networks，2016，12（2）：1-17.
[36] GU X，JIN L，ZHAO N，et al.Energy-efficient computation offloading and transmit power allocation scheme for mobile edge computing[J].Mobile Information Systems，2019：1-9.
[37] WANG J，ZHAO L，LIU J，et al.Smart resource allocation for mobile edge computing：a deep reinforcement learning approach[J].IEEE Transactions on Emerging Topics in Computing，2019，9（3）：1529-1541.
[38] LIU Q，ZHAI J W，ZHANG Z Z，et al.A survey on deep reinforcement learning[J].Chinese Journal of Computers，2018，41（1）：1-27.
[39] VOLODYMYR M，KORAY K，DAVID S，et al.Human-level control through deep reinforcement learning[J].Nature，2019，518（7540）：529-533.
[40] 姜同全，王子磊，奚宏生.基于动态阈值分配的流媒体边缘云会话迁移策略[J].计算机工程，2017，43（1）：55-60.
JIANG Tongquan，WANG Zilei，XI Hongsheng.Session migration strategy for streaming media edge cloud based on dynamic threshold allocation[J].Computer Engineering，2017，43（1）：55-60.
[41] ZHAO J，LI Q，GONG Y，et al.Computation offloading and resource allocation for cloud assisted mobile edge computing in vehicular networks[J].IEEE Transactions on Vehicular Technology，2019，68（8）：7944-7956.
[42] MENG S，LI Q，WU T，et al.A fault-tolerant dynamic scheduling method on hierarchical mobile edge cloud computing[J].Computational Intelligence，2019，35（3）：577-598.
[43] XIE G，CHEN Y，XIAO X，et al.Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[J].IEEE Transactions on Sustainable Computing，2018，3（3）：167-181.
[44] YAO G，DING Y，HAO K.Using imbalance characteristic for fault-tolerant workflow scheduling in cloud systems[J].IEEE Transactions on Parallel & Distributed Systems，2017，28（12）：3671-3683.
[45] MENG S，SONG W，WU T，et al.An uncertainty-aware evolutionary scheduling method for cloud service provisioning[C]//Proceedings of the IEEE International Conference on Web Services，2016：506-513.
[46] FAN G，CHEN L，YU H，et al.Modeling and analyzing dynamic fault-tolerant strategy for deadline constrained task scheduling in cloud computing[J].IEEE Transactions on Systems Man & Cybernetics Systems，2017，50（4）：1260-1274.
[47] RAHME J，XU H.A software reliability model for cloud-based software rejuvenation using dynamic fault trees[J].International Journal of Software Engineering & Knowledge Engineering，2015，25：1491-1513.
[48] SAMANTA A，TANG J.Dyme：dynamic microservice scheduling in edge computing enabled IoT[J].IEEE Internet of Things Journal，2020，7（7）：6164-6174.
[49] SAMANTA A，LEI J，MüHLH?USER M，et al.Incentivizing microservices for online resource sharing in edge clouds[C]//Proceedings of the IEEE International Conference on Distributed Computing Systems（ICDCS），2019：420-430.
[50] YU R，KILARI V T，XUE G，et al.Load balancing for interdependent IoT microservices[C]//Proceedings of the IEEE Conference on Computer Communications，2019：298-306.
[51] KAUR K，GARG S，KADDOUM G，et al.A big data-enabled consolidated framework for energy efficient software defined data centers in IoT setups[J].IEEE Transactions on Industrial Informatics，2020，16（4）：2687-2697.
[52] YU G，CHEN P，ZHENG Z.Microscaler：cost-effective scaling for microservice applications in the cloud with an online learning approach[J].IEEE Transactions on Cloud Computing，2022，10（2）：1100-1116.
[53] HU Y，LAAT C D，ZHAO Z.Optimizing service placement for microservice architecture in clouds[J].Applied Sciences，2019，9（21）：4663.
[54] FILIP I D，POP F，SERBANESCU C，et al.Microservices scheduling model over heterogeneous cloud-edge environments as support for IoT applications[J].IEEE Internet of Things Journal，2018，5（4）：2672-2681.
[55] BAO L，WU C，BU X，et al.Performance modeling and workflow scheduling of microservice-based applications in clouds[J].IEEE Transactions on Parallel and Distri-
buted Systems，2019，30（9）：2114-2129.
[56] YANG Z，NGUYEN P，JIN H，et al.MIRAS：model-based reinforcement learning for microservice resource allocation over scientific workflows[C]//Proceedings of the 2019 IEEE 39th International Conference on Distributed Computing Systems（ICDCS），2019：122-132.
[57] LIU C C，HUANG C C，TSENG C W，et al.Service resource management in edge computing based on microservices[C]//Proceedings of the 2019 IEEE International Conference on Smart Internet of Things（SmartIoT），2019：388-392.
[58] WANG S，GUO Y，ZHANG N，et al.Delay-aware microservice coordination in mobile edge computing：a reinforcement learning approach[J].IEEE Transactions on Mobile Computing，2021，20（3）：939-951.
[59] ZHANG X，ZHENG Y，WEI S，et al.Incentives for mobile crowd sensing：a survey[J].IEEE Communications Surveys & Tutorials，2015，18（1）：1-14.
[60] WANG J，WANG L，WANG Y，et al.Task allocation in mobile crowd sensing：state-of-the-art and future opportunities[J].IEEE Internet of Things Journal，2018，5（5）：3747-3757.
[61] WANG J，WANG Y，ZHAO G，et al.The active learning multi-task allocation method in mobile crowd sensing based on normal cloud model[J].Pervasive and Mobile Computing，2020，67：1-19.
[62] 景瑶，郭斌，陈荟慧，CrowdTracker：一种基于移动群智感知的目标跟踪方法[J].计算机研究与发展，2019，56（2）：328-337.
JING Yao，GUO Bin，CHEN Huihui.CrowdTracker：object tracking using mobile crowd sensing[J].Journal of Computer Research and Development，2019，56（2）：328-337.
[63] JIAN A N，PENG Z L，GUI X L，et al.Research on task distribution mechanism based on public transit system in crowd sensing[J].Chinese Journal of Computers，2019，42（2）：65-78.
[64] WANG L，YU Z，GUO B，et al.Mobile crowd sensing task optimal allocation：a mobility pattern matching perspective[J].Frontiers of Computer Science，2018，12（2）：231-244.
[65] YANG Y，LIU W，WANG E，et al.A prediction-based user selection framework for heterogeneous mobile crowd sensing[J].IEEE Transactions on Mobile Computing，2018，18（11）：2460-2473.
[66] ABOUOUF M，MIZOUNI R，SINGH S，et al.Multi-worker multi-task selection framework in mobile crowd sourcing[J].Journal of Network and Computer Applications，2019，130：52-62.
[67] ZHOU J，FAN J，WANG J.Task scheduling for mobile edge computing enabled crowd sensing applications[J].Int J Sensor Networks，2021，35（2）：88-98.
[68] LIN L，LIAO X，JIN H，et al.Computation offloading toward edge computing[J].Proceedings of the IEEE，2019，107（8）：1584-1607.
[69] IBIKUNLE F.Cloud computing security issues and challenges[J].International Journal of Computer Networks（IJCN），2011，3（5）：247-255.
[70] DAMODAR T，SHAILENDRA S，SANJEEV S.Theoretical analysis of bio-inspired load balancing approach in cloud computing environment[J].International Journal of Database Theory and Application，2017，10（11）：15-26.
[71] HOUSSEIN E H，GAD A G，WAZERY Y M，et al.Task scheduling in cloud computing based on meta-heuristics：review，taxonomy，open challenges，and future trends[J].Swarm and Evolutionary Computation，2021，62：1-41.
[72] PANG M，WANG L，FANG N.A collaborative scheduling strategy for IoV computing resources considering location privacy protection in mobile edge computing environment[J].Journal of Cloud Computing，2020，9（1）：1-17.
[73] WEN Y，LIU J，DOU W，et al.Scheduling workflows with privacy protection constraints for big data applications on cloud[J].Future Generation Computer Systems，2020，108：1084-1091.
[74] NAJAFIZADEH A，SALAJEGHEH A，RAHMANI A M，et al.Privacy preserving for the internet of things in multiobjective task scheduling in cloud fog computing using goal programming approach[J].Peer-to-Peer Networking and Applications，2021，14（6）：3865-3890.