Variable-Bit-Rate Transmission Schedule Generation in Green Vehicular Roadside Units

Smart traffic scheduling can be used to reduce downlink roadside unit (RSU) energy use in green vehicular roadside infrastructure. In this paper, we consider the problem of downlink schedule generation when the RSU-to-vehicle radios use a variable bit rate (VBR) air interface. We first present offline scheduling formulations that provide lower bounds on the energy required to fulfill vehicle requests. An integer linear program is introduced that can be solved to find optimal offline VBR time slot schedules. We then prove that this problem is NP-complete by a reduction from the well-known Santa Claus problem. Two flow-graph-based models are then used to solve the minimum energy VBR scheduling problem. The first uses generalized flow (GF) graphs that represent time slots as individual graph nodes. The second uses time-expanded graphs (TEGs) that model the temporal evolution of the system. Both of these models can be used to compute lower bounds on energy performance and provide the basis for energy-efficient online schedulers. The first scheduler introduced, i.e., First-Come First-Serve (FCFS), is very simple and treats all vehicles equally and in the order of arrival. Since the time spent in energy-favorable locations decreases with higher vehicle speed, the second scheduler, i.e., Fastest First (FF), gives priority to faster moving vehicles. The greedy GF (G-GF) and greedy TEG (G-TEG) schedulers are then introduced, which are motivated by the two flow-graph-based models. The proposed algorithm performance is examined under different traffic scenarios, and they are found to perform well compared with the lower bound. Our results show that the less computationally intensive algorithms, i.e., FCFS and FF, can perform well under light load, but G-GF and G-TEG, while more complex, can provide near-optimal energy consumption and with reasonable demand dropping rates. The results also show that the G-GF and G-TEG algorithms are much more fair than the simpler algorithms in heavy-load situations.