Dependent Task Scheduling and Offloading for Minimizing Deadline Violation Ratio in Mobile Edge Computing Networks
Shumei Liu, Yao Yu, Xiao Lian, Yuze Feng, Changyang She, Phee Lep Yeoh, Lei Guo, Branka Vucetic, Yonghui Li
Abstract
This paper considers computation offloading for mobile applications with task-dependency requirements in mobile edge computing (MEC) systems. Based on the online arrival patterns and various delay constraints of practical applications, we focus on minimizing the system deadline violation ratio (DVR) to improve the overall reliability performance. Specifically, we propose a DVR minimization computation offloading scheme with task migration and merging, in which the task migration and merging model is designed to construct an overall directed acyclic graph (DAG) for all currently dependent tasks. We consider a multi-slot MEC system where applications arrive slot-by-slot without prior knowledge of future arrivals. Then given the number of application arrivals at each time slot, we equivalently transform the DVR minimization problem into a problem that maximizes the number of completed applications in a finite time horizon. The above problem is challenging to determine the optimal task execution order for different applications with various task dependencies and delay constraints. To address this, we develop a migration-enabled multi-priority task sequencing algorithm, which creatively introduces several task priority metrics and determines the optimal task execution order. Then, a deep deterministic policy gradient (DDPG)-based learning algorithm is developed to find the optimal offloading policy. Experimental results demonstrate that the proposed scheme can reduce the system DVR by 60.34%~70.3% compared with existing benchmark schemes under various network scenarios.