Latency-Constrained Multi-User Efficient Task Scheduling in Large-Scale Internet of Vehicles

Driven by the tremendous demand for real-time data processing in the Internet of Vehicles (IoV), edge computing is envisioned as a promising solution to alleviate the resource limitation on vehicles. Current works on edge task scheduling simply optimize the total system cost and ignore the various constraints of applications, which will result in the reduction of the task completion rate and even cause security accidents. Although few works studied the multi-task deadline-constrained scheduling problem, their complexity is too high, resulting in the explosive growth of the runtime. Spurred by the above issues, the multi-task scheduling problem is formulated to maximize the task completion rate. Further, a Multi-user Efficient Task Scheduling (METS) algorithm is proposed to solve the formulated problem, which consists of three key components: (1) the dominating set-based network clustering that aims to reduce the network scale, (2) the matching-based task assignment to assign tasks that are modeled by the Directed Acyclic Graph (DAG) to their proper clusters, and (3) the intra-cluster DAG scheduling to schedule DAGs to the proper network nodes. Simulation results show that the proposed METS algorithm can significantly improve the task completion rate and reduce the algorithm runtime in an IoV environment with thousand-level network scale and thousand-level task requests.