An Approximation Algorithm for Joint Data Uploading and Task Offloading in IoV
Hualing Ren, Kai Liu, Chunhui Liu, Guozhi Yan, Yantao Li
Abstract
This paper investigates cooperative data uploading and task offloading in heterogeneous Internet of Vehicles (IoV). Specifically, considering the characteristics that different tasks may require common data and can be offloaded to heterogeneous nodes, we first present an end-edge-cloud architecture for cooperative data uploading and task offloading. Then, we formulate a Joint Data Uploading and Task Offloading (JDUTO) problem, which aims at minimizing the average service delay by considering common input data, heterogeneous resources, and vehicle mobility. JDUTO is proved as NP-hard by reducing the well-known NP-hard problem Capacitated Vehicle Routing problem (CVRP) in polynomial time. On this basis, we propose an approximation algorithm. Specifically, we first design an optimal algorithm to select a set of vehicles with common data requirements for data uploading. Second, we adopt Lagrange multiplier method to derive the optimal solution of resource allocation. Third, we design a filter mechanism-based Markov-approximation algorithm for task offloading, where specific Initialization and State Transition Strategy are designed to accelerate convergence. We prove that the gap of the approximation algorithm is 1/βlog|Φ|, where β is a positive constant and Φ is the size of solution space. Finally, we build a simulation model based on real trajectories and give comprehensive performance evaluations, which conclusively demonstrate the superiority of the proposed solution.