Real-Time and Low-Overhead Graph Task Scheduling over Vehicular Computing-Assisted Edge Networks

Modern vehicular networks encounter a multitude of computation-intensive tasks that have unique processing topologies represented by graph structures. The integration of edge computing and vehicular networks has provided a unique platform for handling these tasks at the network edge. However, the complex structure of these tasks makes their scheduling and execution challenging. This paper proposes a Vehicular Computing-assisted Edge Network (VCEN) architecture, where graph tasks are scheduled over a Vehicle-Edge Collaborative Cloud (VECC) for parallel execution. Our goal is to obtain feasible mappings between task components and computing nodes in the VECC while minimizing task execution latency and energy consumption. We show that achieving this goal requires solving an NP-hard optimization problem with complex constraints related to task structure and VECC topology. We then propose a fast and lightweight approach for graph task scheduling over VECC that comprises two key phases. In the former phase, we introduce a preprocessing algorithm that reduces the graph task's dimensionality by merging important components and cutting redundant edges. In the latter phase, we deploy a cost-reduction-preferred mapping algorithm to obtain feasible mappings between task components and VECC. Through simulations, we demonstrate our superior performance in different network settings.