Prioritized Assignment With Task Dependency in Collaborative Mobile Edge Computing

Collaborative mobile edge computing enables resource-constrained edge facilities to work cooperatively for computation-intensive tasks. However, as the number of tasks demanded by various applications increases, resource competition is inevitable in edge facilities. Existing works tackle the resource competition problem with a first come first served (FCFS) scheme, which is blind to different delay requirements among tasks. This may result in tasks with higher delay requirements waiting a long time for service, thereby reducing overall service quality. This paper proposes a prioritized queuing scheme with task dependency (PQTD), which allows high-prioritized sub-tasks with higher delay requirements to jump into the queue ahead of low-prioritized sub-tasks with lower delay requirements. To describe the complicated delay change caused by queue-jumping, a joint DAG-queue delay (JDQD) model is proposed, which analyzes the chain reaction of delay changes caused by the processing queue on the server and the task dependency. With JDQD, a multi-task assignment optimization problem is formulated to maximize the average satisfaction degree (AvgSatD), which is defined according to the priorities of the tasks and their delay requirements. Then, a tree-based algorithm is proposed to solve the NP-hard optimization problem, i.e., Monte Carlo Tree Search (MCTS). Simulation results demonstrate the effectiveness of the PQTD queuing scheme and tree search mechanism of MCTS. Overall, PQTD + MCTS can increase AvgSatD by at least 45.8% with an acceptable complexity.