Combining Capital and Operating Expenditure Costs in Vehicular Roadside Unit Placement
Journal Articles
Overview
Research
Identity
Additional Document Info
View All
Overview
abstract
Vehicular ad-hoc networks will be the next step towards intelligent transportation systems. Roadside infrastructure is a key component of these systems that will eventually support various applications such as road safety, transportation services, infotainment, and in-vehicle Internet access.
This thesis considers the problem of roadside unit (RSU) placement and configuration in vehicular networks. The goal is to select the RSU locations and configurations such that the sum of capital and operational expenditure costs is minimized. Historical vehicular traffic traces and a set of RSU candidate locations are used as inputs. First, the problem is formulated as an integer linear program (ILP), which provides a lower bound on the total cost, and can be found for moderate size problems. A practical algorithm called Minimum Cost Route Clustering (MCRC) is then introduced that solves a relaxed version of the ILP and uses a novel rounding procedure to obtain real RSU placements. The algorithm takes into account the energy costs incurred by transmitting vehicular requests when the latter are scheduled using a minimum energy online scheduler. Performance results are presented that show that the proposed algorithm performs well compared to the case where placements are done without considering both capital and operational expenditure costs.
The problem of capacity augmentation is then addressed, as a way of adjusting the initial RSU network design, and serves to counterbalance its failure to take causality into account. The objective is to find an RSU radio capacity assignment that minimizes the long-term operating expenditure costs subject to meeting packet deadline constraints, subject to a given packet loss rate target. A procedure, referred to as the Capacity Augmentation (CA) Algorithm, is proposed that iterates over the RSUs, selecting candidates for capacity augmentation based on their packet loss rate sensitivities. A variety of results is presented that characterize and compare the performance of the CA Algorithm using a greedy online packet scheduler. It is shown that the CA Algorithm is an efficient way to assign RSU radio capacity that achieves the desired performance objectives.
The thesis then considers the problem of RSU job scheduling when vehicle routes are unknown. The objective is to minimize the long-term RSU energy costs, subject to satisfying hard deadline constraints and a packet loss criterion. A scheduler referred to as the Route Coverage Expectation Scheduler (RCES) is proposed that uses the historical traffic traces of an urban road network to estimate vehicular motion and the energy costs needed for RSU-to-vehicle communications. The algorithm schedules job requests across multiple RSUs whenever possible, by assigning part of a request to the current RSU and by deferring the remainder to future RSUs. A variety of results is presented that show that the RCES Algorithm achieves a packet drop ratio similar to that achieved when routes are known, with only a modest increase in energy cost.
