边缘计算平台中面向分簇的半在线调度方法  

Cluster-oriented semi-online task scheduling method in the edge computing platform

作　　者：韩家曦 赵辉[1,2,3] 冯南之 王静 万波[1,2,3] 王泉 HAN Jiaxi;ZHAO Hui;FENG Nanzhi;WANG Jing;WAN Bo;WANG Quan(School of Computer Science and Technology,Xidian University,Xi’an 710071,China;Shaanxi Province Key Laboratory of Smart Human-Computer Interaction and Wearable Technology,Xi’an 710071,China;Hangzhou Institute of Technology,Xidian University,Hangzhou 311231,China)

机构地区：[1]西安电子科技大学计算机科学与技术学院,陕西西安710071 [2]陕西省智能人机交互与可穿戴技术重点实验室,陕西西安710071 [3]西安电子科技大学杭州研究院,浙江杭州311231

出　　处：《西安电子科技大学学报》2024年第6期104-116,共13页Journal of Xidian University

基　　金：陕西省重点研发计划(2024GX-YBXM-010,2024GX-YBXM-140,2024GX-YBXM-039);陕西省创新能力支撑计划(2023-CX-TD-08);陕西省秦创原“科学家+工程师”团队(2023KXJ-040);中央高校基本科研业务费专项资金(ZYTS24089)。

摘　　要：目前面向边缘计算的任务调度方法未考虑因网络延迟造成边缘节点性能不确定的问题,无法适应存在节点性能不确定的延迟敏感型边缘计算平台。针对此问题,提出了一种延迟敏感型边缘计算平台中面向分簇的半在线调度方法。首先,针对边缘计算平台中存在性能不确定的节点,设计了性能模糊度指标表示边缘节点的性能确定程度,为半在线调度算法提供额外信息;其次,以QoS保障和最小化任务完成时间为目标,提出了双段QoS保障模型和任务完成时间优化模型,建立任务调度双目标优化模型;再次,针对任务调度NP难问题,提出了一种基于映射的半在线任务调度算法MSSA,按照性能模糊度结合用户位置划分服务区域,建立面向分簇的边缘计算平台模型,并根据负载变化动态调整簇容量,实现高效的半在线任务调度。最后,基于真实边缘计算平台日志数据,通过仿真实验与其它方法进行对比,结果表明提出的算法能够减少26%的任务完成时间,并在QoS保障方面提升19%。The existing task scheduling methods for edge computing do not consider the problem of uncertain performance of edge nodes caused by network delay,and cannot adapt to the delay sensitive edge computing platform with uncertain node performance.To solve this problem,this paper proposes a cluster-oriented semi-online scheduling method for delay-sensitive edge computing platform.First,considering the nodes with uncertain performance caused by network delay,a performance uncertainty metric is designed to represent the degree of performance certainty of edge nodes.This metric provides extra pieces of information for the semi-online scheduling algorithm.Second,a dual-objective QoS guarantee model and a task completion time optimization model are proposed to establish a dual-objective optimization model for task scheduling,which focuses on guaranteeing QoS and minimizing makespan.Third,to address the NP-hard problem of task scheduling,a mapping-based semi-online task scheduling algorithm(MSSA)is proposed which divides the service area range based on the performance uncertainty metric and user location,establishes a cluster-oriented edge computing platform model,and dynamically adjusts cluster capacity based on load changes,thus enabling efficient semi-online task scheduling.Finally,by using trace data from a real edge computing platform,simulation experiments are conducted to compare the proposed algorithm with other methods.Experimental results demonstrate that the proposed algorithm can reduce the task completion time by 26%and improves the QoS guarantee by 19%.

关 键 词：边缘计算 调度算法 服务质量 任务完成时间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]