Graph-Represented Computation-Intensive Task Scheduling Over Air-Ground Integrated Vehicular Networks

This article investigates vehicular cloud (VC)-assisted task scheduling in an air-ground integrated vehicular network (AGVN), where tasks carried by unmanned aerial vehicles (UAVs) and resources of VCs are both modeled as graph structures. We consider a scenario in which resource-limited UAVs carry a set of computation-intensive graph tasks, which are offloaded to resource-abundant vehicles for processing. We formulate an optimization problem to jointly optimize the mapping between task components and vehicles, and transmission powers of UAVs, while addressing the trade-off between i) completion time of tasks, ii) energy consumption of UAVs, and iii) data exchange cost among vehicles. We show that this problem is a mixed-integer non-linear programming, and thus NP-hard. We subsequently reveal that satisfying constraints related to graph task structure requires addressing the non-trivial subgraph isomorphism problem over a dynamic vehicular topology. Accordingly, we propose a decoupling approach by segregating template searching from transmission power allocation, where a template denotes a mapping between task components and vehicles. For template search, we introduce a low-complexity algorithm for isomorphic subgraphs extraction. For power allocation, we develop an algorithm using p-norm and convex optimization techniques. Extensive simulations demonstrate that our approach outperforms baseline methods in various network settings.

Automated summary

This article investigates the application of vehicular cloud-assisted task scheduling in an air-ground integrated vehicular network. By modeling tasks carried by unmanned aerial vehicles and resources of vehicular clouds as graph structures, the authors consider the scenario where resource-limited UAVs offload computation-intensive tasks to resource-abundant vehicles for processing. They formulate an optimization problem to jointly optimize the mapping between task components and vehicles, transmission powers of UAVs, and address the trade-off between completion time of tasks, energy consumption of UAVs, and data exchange cost among vehicles. The authors propose a decoupling approach for task scheduling by segregating template searching from transmission power allocation, which is shown to outperform baseline methods in extensive simulations.