An Approximation Algorithm for Joint Data Uploading and Task Offloading in IoV

This chapter investigates cooperative data uploading and task offloading in heterogeneous IoV. First, considering the characteristics that different tasks may require common data and can be offloaded to heterogeneous nodes, we present an end–edge–cloud cooperative data uploading and task offloading architecture. Second, we formulate a Joint Data Uploading and Task Offloading (JDUTO) problem, aiming 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. Third, 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. Then, we adopt Lagrange multiplier method to derive the optimal solution of resource allocation. Finally, we design a filter mechanism-based Markov-approximation algorithm for task offloading. We prove that the gap of the approximation algorithm is \(\frac {1}{\beta } \log |\Phi |\) , where \(\beta \) is a positive constant and \(\Phi \) 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.