云-边-端协作网络中的细粒度任务调度策略

doi:10.3778/j.issn.1002-8331.2405-0011

摘要/Abstract

摘要： 针对已有的任务卸载及调度方案大多计算过程复杂、易忽略任务多属性及子任务间可并行性等问题，设计了一种云-边-端协作网络中的细粒度任务调度策略。构建了一个涵盖云-边-端三层的网络架构并引入SDN（software defined network）来实现高效的网络信息管理和边缘负载均衡。提出了包含两种任务服务模式（整体服务模式、分割服务模式）及三种执行机制（云执行、边执行、端执行）的任务调度策略：对于整体服务模式下的任务，设计了一个时延与能耗联合优化的优化问题来获取对应任务的最佳执行机制；对于分割服务模式下的任务，利用改进的动态列表调度方法设计了一种子任务调度并行度最大化（subtask scheduling parallelism maximization, SSPM）算法来最大化分割后被调度子任务的并行度。在NS-3平台上进行仿真实验，仿真结果表明该策略的性能表现优于其他对比方案。

关键词: 云-边-端协作, 任务调度, 任务服务模式, 任务执行机制

Abstract: For the existing task offloading and scheduling scheme, focus on the problem of computing process is complex, easily overlook the multiple task properties and the parallelism of subtasks, et al. this paper proposes a fine-grained task scheduling strategy under the cooperation of cloud, edge and terminal. Firstly, a hierarchical network architecture with cloud, edge and terminal layers and introduce SDN (software defined network) is built to achieve efficient network information management and balance the edge load. Then the task scheduling strategy is proposed with two task serving patterns and three execution mechanisms: for tasks with pattern of “served as a whole”, an optimization problem is built to minimize delay and energy consumption jointly, thus achieving the optimal execution mechanisms; for tasks with pattern of “served with segmentations”, a SSPM (subtask scheduling parallelism maximization) algorithm based on dynamic list scheduling is designed to maximize the parallelism degree of subtasks scheduling as much as possible. Finally, the simulation is carried out on NS-3 platform, and results show that the scheme outperforms others.

Key words: cloud-edge-terminal cooperation, task scheduling, task serving pattern, task execution mechanism

郭辉, 史瑞昌, 高黎明, 王志乾, 魏全瑞. 云-边-端协作网络中的细粒度任务调度策略[J]. 计算机工程与应用, 2024, 60(21): 274-285.

GUO Hui, SHI Ruichang, GAO Liming, WANG Zhiqian, WEI Quanrui. Fined-Grained Task Scheduling Strategy for Cloud-Edge-Terminal Cooperative Networks[J]. Computer Engineering and Applications, 2024, 60(21): 274-285.

参考文献

[1] Cisco. Cisco annual Internet report (2018—2023) white paper[EB/OL].(2023). http://www.cisco.com/go/vni.
[2] KUMAR M, DUBEY K, PANDEY R. Evolution of emerging computing paradigm cloud to fog: applications, limitations and research challenges[C]//Proceedings of the 11th International Conference on Cloud Computing, Data Science & Engineering (Confluence), Noida, India, 2021: 257-261.
[3] 郑逢斌, 朱东伟, 臧文乾, 等. 边缘计算: 新型计算范式综述与应用研究[J]. 计算机科学与探索, 2020, 14(4): 541-553.
ZHENG F B, ZHU D W, ZANG W Q, et al. Edge computing: review and application research on new computing paradigm[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(4): 541-553.
[4] SHARBAF M S. IoT driving new business model, and IoT security, privacy, and awareness challenges[C]//Proceedings of the IEEE 8th World Forum on Internet of Things (WF-IoT), Yokohama, Japan, 2022: 1-4.
[5] 赵庶旭, 元琳, 张占平. 多智能体边缘计算任务卸载[J]. 计算机工程与应用, 2022, 58(6): 177-182.
ZHAO S X, YUAN L, ZHANG Z P. Multi-agent edge computing task offloading[J]. Computer Engineering and Applications, 2022, 58(6): 177-182.
[6] ZHANG G, SHEN F, LIU Z, et al. FEMTO: fair and energy-minimized task offloading for fog-enabled IoT networks[J]. IEEE Internet of Things Journal, 2079, 6(3): 4388-4400.
[7] HE X, DOU W. Offloading deadline-aware task in edge computing[C]//Proceedings of the 13th International Conference on Cloud Computing (CLOUD), 2020: 28-30.
[8] MISRA S, BERA S. Soft-VAN: mobility-aware task offloading in software-defined vehicular network[J]. IEEE Transactions on Vehicular Technology, 2020, 69(2): 2071-2078.
[9] TUONG V D, TRUONG T P, TRAN A T, et al. Delay-sensitive task offloading for Internet of things in nonorthogonal multiple access MEC networks[C]//Proceedings of the 2020 International Conference on Information and Communication Technology Convergence (ICTC), 2020: 597-599.
[10] PHAM X Q, NGUYEN T D, NGUYEN V D, et al. Joint node selection and resource allocation for task offloading in scalable vehicle-assisted multi-access edge computing[J]. Symmetry-Basel, 2019, 11(1): 58.
[11] ALELAIWI A. An efficient method of computation offloading in an edge cloud platform[J]. Journal of Parallel and Distributed Computing, 2019, 127: 8-64.
[12] PAN S, CHEN Y. Energy-optimal scheduling of mobile cloud computing based on a modified Lyapunov optimization method[J]. IEEE Transactions on Green Communications and Networking, 2019, 3(1): 227-235.
[13] SHU C, ZHAO Z, HAN Y, et al. Multi-user offloading for edge computing networks: a dependency-aware and latency-optimal approach[J]. IEEE Internet of Things Journal, 2020, 7(3): 1678-1689.
[14] YANG T, CHAI R, ZHANG L, et al. Worst case latency optimization-based joint computation offloading and scheduling for interdependent subtasks[C]//Proceedings of the 2020 International Conference on Wireless Communications and Signal Processing (WCSP), 2020: 1010-1015.
[15] SAHNI Y, CAO J, YANG L, et al. Multihop offloading of multiple dag tasks in collaborative edge computing[J]. IEEE Internet of Things Journal, 2021, 8(6): 4893-4905.
[16] XIE J, JIA Y, CHEN Z, et al. Efficient task completion for parallel offloading in vehicular fog computing[J]. China Communications, 2019, 16(11): 42-55.
[17] WEI F, CHEN S, ZOU W. A greedy algorithm for task offloading in mobile edge computing system[J]. China Communications, 2018, 5(11): 149-157.
[18] YUAN W, NAHRSTEDT K. Energy-efficient CPU scheduling for multimedia applications[J]. ACM Transactions on Computer Systems, 2006, 24(3): 292-331.
[19] ZHANG W, WEN Y, GUAN K, et al. Energy-optimal mobile cloud computing under stochastic wireless channel[J]. IEEE Transactions on Wireless Communications, 2013, 12(9): 4569-4581.
[20] WANG H, SINNEN O. List-scheduling versus cluster-scheduling[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 29(8): 1736-1749.
[21] WU M, GAJSKI D. Hypertool: a programming aid for message-passing systems[J]. IEEE Transactions on Parallel and Distributed Systems, 1990, 1(3): 330-343.
[22] HWANG J, CHOW Y, ANGER F, et al. Scheduling precedence graphs in systems with interprocessor communication times[J]. SIAM Journal on Computing, 1989, 18(2): 244-257.
[23] SAMADI Y, ZBAKH M, TADONKI C. E-HEFT: enhancement heterogeneous earliest finish time algorithm for task scheduling based on load balancing in cloud computing[C]//Proceedings of the 2018 International Conference on High Performance Computing & Simulation (HPCS), Orleans, 2018: 601-609.