Research On DAG Application Scheduling Algorithm In Heterogeneous Edge Environment

With the continuous development of mobile Internet technology,a variety of computing-intensive and delay-sensitive applications have emerged on mobile devices,such as VR games,face recognition,etc.These applications usually consist of multiple tasks with dependencies,which can be represented as a Directed Acyclic Graph(DAG).Mobile devices cannot support such applications due to limited computing,communication and other resources,and the unstable network environment and the high delay caused by longdistance data transmission in the core network make cloud computing services unable to meet the needs of such applications.Quality requirements.In this context,edge computing emerges as the times require,which provides nearby low-latency,low-power services for mobile devices by sinking computing,storage,network and other resources from the cloud to the edge of the network.Therefore,how to efficiently schedule such computationintensive and delay-sensitive DAG applications in edge computing systems is a key issue that needs to be solved urgently.The traditional DAG application scheduling algorithm is mainly based on the critical path idea,which minimizes the application completion time by heuristically offloading the tasks on the critical path of the DAG to the earliest completed edge nodes.However,such scheduling algorithms mainly have the following limitations in the edge environment: First,due to the high heterogeneity of edge node computing and communication capabilities,the running time of tasks on different edge nodes varies greatly,which makes traditional scheduling algorithms based on the average capacity of nodes.It is difficult to determine the task priority effectively with the critical path selection method based on the algorithm;secondly,in the edge computing scenario,some tasks have privacy requirements,which need to be constrained to be executed locally,which also brings new challenges to the task scheduling algorithm;finally,Most of the existing DAG application scheduling algorithms aim to minimize the application running time.In edge computing scenarios,tasks running on different edge nodes have different costs.Therefore,how to coordinately consider application time constraints(Deadline)and budget constraints(Budget),It is also critical to improve the scheduling success rate of applications in edge computing systems.In order to meet the above challenges,this paper mainly carries out the following research work:Aiming at the problem that the traditional DAG scheduling algorithm cannot effectively determine the task priority in the highly heterogeneous edge environment,this paper proposes a Dynamic Priority Scheduling algorithm(DPS)with the goal of minimizing the application completion time.Different from the traditional algorithm that uses the average node capability to solve the critical path,the DPS algorithm builds multiple DAGE graphs(Directed Acyclic Graph on Edge)according to the actual computing time of the task on the heterogeneous edge nodes,and searches for the corresponding multiple dynamic graphs.Critical Path.In order to effectively determine the task priority,the DPS algorithm adjusts the DAGE graph according to the actual calculation and communication time of the scheduled tasks,and dynamically determines the priority of the unscheduled tasks.In addition,considering the impact of privacy tasks on determining the critical path,the DPS algorithm prioritizes the execution time of privacy tasks and constrains their execution locally.The experimental results show that,compared with the traditional algorithm,the DPS algorithm improves the application completion time by 4%-14%.Considering the cost budget constraints of DAG applications in heterogeneous edge environments,this paper proposes a Budget-Deadline Aware Scheduling algorithm(BDAS)based on budget-deadline awareness.Specifically: 1)In the task priority determination stage,unlike traditional algorithms that only consider the time budget constraint,the BDAS algorithm uses the task’s disposable execution time to account for the remaining application time budget and the disposable cost budget to the application’s remaining cost budget.The sum of the ratios is used as a metric to determine the task priority;2)In the task scheduling stage,the BDAS algorithm performs node matching according to the task priority.During the matching process,the normalized task execution time and cost at a specific node are used as the edge node selection indicators,which takes into account the task execution time and cost.Experiments show that when there are time and cost constraints,the BDAS algorithm has a 12%-22% improvement in the scheduling success rate compared with the traditional algorithm.