A Hierarchical Hybrid Subtask Scheduling Algorithm in UAV-Assisted MEC Emergency Network

As a technique to buffer the conflict between computation-intensive tasks and capability-limited devices, unmanned aerial vehicle-enabled mobile-edge computing (UAV-MEC) has been witnessed as a promising approach, especially in the post-disaster scenario where the infrastructure is limited or unavailable. In this article, we consider a joint optimization of topology reconstruction and subtask scheduling to minimize the average completion time of the subtask. To address this problem, we propose a hierarchical hybrid subtask scheduling algorithm (H-HSS). First, a topology reconstruction game algorithm for energy-efficient control (TRGE) is investigated to get optimal power and node-to-node connection decision, in which the interaction between the node with its neighbors is modeled as a single-leader–multifollowers Stackelberg game. Second, by analyzing the dependency between subtasks, a hierarchical-dependent subgraph extraction scheme (HDSE) is proposed, which transforms the subtask call graph into a hierarchical tree diagram to obtain a hierarchical scheduling list. Finally, a hybrid subtask scheduling scheme is presented to make optimal task scheduling decisions. Numerical results show that H-HSS can significantly outperform the other representative benchmarks with low complexity, in subtask completion time, energy consumption, or weighted sum. In addition, the tolerance capability of our proposed TRGE algorithm is increased by 66%.

I. Introduction

In post-disaster emergency communications, the destruction of ground infrastructure leads to the communication link being interrupted, normal communications services cannot be guaranteed. Stable and continuous communication is essential for emergency rescue. Due to flexible mobilities, fast deployment, low cost, and strong line-of-sight (LOS) link, unmanned aerial vehicles (UAVs) are regarded as a key solution to restore communication, have received extensive attention from academia and industry [1]. In a UAV-assisted emergency network, UAVs can quickly provide ubiquitous connections, can serve as relay nodes, and can also disseminate information [2]. Mobile-edge computing (MEC) can provide computing and communication capabilities at the edge of the network. UAVs have recently emerged as MEC nodes with computing and communication capabilities. Through cooperation with the ground command center, UAVs assist the cellular network to provide wireless services to ground users [3]. The UAV-assisted MEC emergency network can realize rapid recovery of communication and efficient rescue.