HMUR: A Two-Stage Heuristic for UAV Scheduling in Mobile Edge Computing with Time Window Constraints
Guangrui Liu, Xia Zhu, Long Chen, Xin Li · 2024
In Mobile Edge Computing (MEC), efficiently scheduling limited resources to fulfill the service requirements of massive Internet of Things (IoT) ground devices (GDs) presents a significant challenge. Unmanned Aerial Vehicles (UAVs), as airborne mobile devices, can be deployed to GD Task Areas (TAs) to provide communication relay or computational support. In this paper, a new multiple UAVs scheduling problem with UAV heterogeneity and time windows constraints is considered and modeled as a Multi-Traveling Salesman Problem (MTSP) with soft time constraints. A two-stage heuristic Heterogeneous Multiple UAVs Routing (HMUR) was proposed for the problem. The approach first identifies TAs and the optimal hovering positions for UAVs, and defines an effective fitness measurement to match between UAVs and different routing path under certain energy constraints. A score function is also defined to determine the final path under the real-time constraints of tasks, thereby enhancing the Quality of Service (QoS). Simulation results demonstrate that our proposed HMUR method surpasses existing baseline algorithms across multiple metrics, validating its effectiveness in optimizing resource scheduling in MEC environments.