Scheduling in Green Vehicular Infrastructure with Multiple Roadside Units

Smart scheduling can be used to reduce infrastructure energy costs in vehicular roadside networks [1]. In this paper we consider the scheduling problem when there are multiple roadside units (RSUs) in tandem. In this case it is often desirable to load balance the energy consumption across the roadside units so that energy provisioning costs can be reduced as much as possible. We first derive an integer linear programming bound on the min-max energy usage of the roadside units for a given input sample function. This bound is used for comparisons with two proposed on-line scheduling algorithms. The first is a low complexity First-Come-First-Assigned (FCFA) scheduler that makes greedy RSU selections followed by a minimum energy time slot assignment. The second algorithm, the Greedy Flow Graph Algorithm (GFGA), makes the same RSU selection but reassigns time slots 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. Results from a variety of experiments show that the proposed scheduling algorithms perform well when compared to the energy lower bounds. Our results also show that near-optimal results are possible but come with increased computation times compared to our heuristic algorithms.