一种基于综合匹配度的边缘计算系统任务调度方法

An Integrative Matching Degree Based Task Scheduling Method for Edge Computing System

边缘计算模式满足数据的实时和低功耗处理需求,是缓解当前网络数据洪流实时处理问题的有效方法之一.但边缘设备资源的异构与多样性给任务的调度与迁移带来极大的困难与挑战.目前,边缘计算任务调度研究主要集中在调度算法的设计与仿真,这些算法和模型通常忽略了边缘设备的异构性和边缘任务的多样性,不能使多样化的边缘任务与异构的资源能力深度匹配.本文针对边缘计算系统资源异构且受限的特性,研究边缘任务与目标设备资源深度匹配的有效方法,提出基于任务资源匹配、负载均衡和任务公平性的综合匹配度评估方法(integrative matching evaluation degree method,IMDE),并设计基于网络流的在线多任务调度算法(IMDE and network flow based online multi-task scheduling algorithm,IMD-FLOW)来验证该方法的有效性.同时,研究边缘计算的仿真系统,将实际环境中用户、任务和设备等若干实体抽象成多个角色和组件,构建符合边缘环境异构特征的EdgeSimPy离散事件仿真平台.在该平台上的实验结果表明,提出的IMD-FLOW调度算法相较于轮询、主资源公平(dominant resource fairness,DRF)、Quincy等其他算法,至少降低6.26%的任务响应延迟与7.53%的网络通信开销,在集群超负荷的情况下,系统失效时间平均延缓1.24倍.

With the rapid growth of intelligent devices,massive amounts of perception data are generated at the network edge.The cloud computing model for Internet of Things(IoT)systems has brought a lot of problems,including high response latency,high transmission energy consumption,privacy leak,etc.Meanwhile,the growth of computing power in data centers cannot meet the exponentially increasing data volume gradually.The edge computing paradigm can satisfy the demands of real-time and low-power data processing,and it is an effective solution for dealing the data deluge in real time.However,there are significant differences in resource types and performance in edge computing environments.The diversity and heterogeneity of computing resources in edge computing systems brings difficulty and challenges to the task scheduling and migration among edge devices.At present,the research on task scheduling in edge computing mainly focuses on the design and simulation of scheduling algorithms.They usually simply consider only one or two computing resources,leading to the mismatch of diverse edge tasks and the heterogeneous resource capabilities.To address this problem,we propose effective mechanisms for matching edge tasks and the resources of target devices deeply based on an integrative matching evaluation degree method(IMDE)which includes task and resource matching degree,device load balance degree and task fairness.This method analyzes the correlation between edge tasks and computing devices from multiple perspectives,and finally uses the integrative matching degree to represent the relevance of each task and the target device at the current moment of edge system.Then,in order to verify the effectiveness of this method,we design and develops an online multi-task scheduling algorithm based on IMDE and network flow(IMD-FLOW),which aims to maximize the matching degree of the decision set.This algorithm maps the integrative matching degree between tasks and devices to the network flow graph,assigns appropriate weights and capacities to the edges in the graph,uses the minimum cost flow algorithm which can solve the global optimal problem to obtain the initial scheduling decision,detects conflicts and extracts the final scheduling decisions.In addition,according to task’s data requirements and device’s network communication capabilities,we construct a fine-grain network communication graph to describe the network environment and data distribution in a simulated edge computing system,and proposes a bandwidth allocation algorithm,with the goal of minimizing data transfer time,to allocate the device bandwidth for one migrated task optimally.We also design a simulation system,named EdgeSimPy,for edge computing includes entities of users,devices,and tasks.It does not limit the kinds of computing resources,and supports distributed data storage to simulates actual edge computing systems.Experimental results on this platform show that IMD-FLOW reduces the task response delay by at least 6.26%and the network communication overhead by at least 7.53%compared with round-robin,random,dominant resource fairness(DRF),Quincy algorithms,and the online algorithm for the multi-component application placement problem(MCAPP-IM).The system failure time is delayed by 1.24 times in average when the edge cluster is overload.