Scheduling in Green Vehicular Infrastructure with Multiple Roadside Units

Abstract

<p>In this thesis we consider low complexity downlink traffic scheduling for green vehicular roadside infrastructure. In multiple roadside unit (RSU) deployments, the energy provisioning of the RSUs may differ, and it is therefore desirable to balance RSU usage from a normalized energy viewpoint. We consider both splittable and unsplittable RSU assignment scheduling (SRA and URA). We first derive an offline integer linear programming bound for the normalized min-max RSU energy usage, which can be solved for a given input sample function. We then show that in the SRA case there is a polynomial complexity 2-approximation bound for the normalized min-max energy schedule. These bounds are used for comparisons with several proposed online scheduling algorithms. The first scheduler is a low complexity Greedy Online Algorithm (GOA) that makes greedy RSU selections followed by minimum energy time slot assignments. A normalized min-max online algorithm is then proposed (TOAA) which is an online version of the 2-approximation bound for SRA scheduling. Then, the Greedy Flow Graph Algorithm (GFGA), which makes greedy RSU selections followed by time slots reassignment whenever a new vehicle is assigned to the same RSU. This is done using a locally optimum integer linear program that can be efficiently solved using a minimum cost flow graph. Two low complexity algorithms are then introduced based on a potential function scheduling approach. The One-Objective algorithm, uses a primary objective based on normalized min-max energy. The second, the Bi-Objective algorithm, uses the same primary objective combined with a total energy secondary objective. These algorithms have provable performance guarantees, in that their worse-case competitive ratio performance is upper bounded. Results from a variety of experiments show that the proposed scheduling algorithms perform well. In particular, we find that in the SRA case, the TOAA and GFGA algorithms perform very close to the lower bound, but at the expense of having to reassign time slots whenever a new vehicle arrives. In the URA case, our low complexity One-Objective algorithm performs better than the others over a wide range of traffic conditions.</p>