A Dynamic Programming Framework for Vehicular Task Offloading with Successive Action Improvement

In this paper, task offloading from vehicles with random velocities is optimized via a novel dynamic programming framework. Particularly, in a vehicular network with multiple vehicles and base stations (BSs), computing tasks of vehicles are offloaded via BSs to an edge server. Due to the random velocities, the exact locations of vehicles versus time, namely trajectories, cannot be determined in advance. Hence, instead of deterministic optimization, the cell association, uplink time, and throughput allocation of multiple vehicles during a period of task offloading are formulated as a finite-horizon Markov decision process. In order to derive a low-complexity solution algorithm, a two-time-scale framework is proposed. The scheduling period is divided into super slots, each super slot is further divided into a number of time slots. At the beginning of each super slot, we first obtain a reference scheduling scheme of cell association, uplink time and throughput allocation via deterministic optimization, yielding an approximation of the optimal value function. Within the super slot, the actual scheduling action of each time slot is determined by making improvement to the approximate value function according to the system state. Due to the successive improvement framework, a non-trivial average cost upper bound could be derived. In the simulation, the random trajectories of vehicles are generated from a high-fidelity traffic simulator. It is shown that the performance gain of the proposed scheduling framework over the baselines is significant.