Cost Effective Mobile and Static Road Side Unit Deployment for Vehicular Adhoc Networks

Abstract—This paper investigates a new strategy to best deploy road side units so that their spatio-temporal coverage is maxi-mized under a limited budget. For the first time in the literature, we consider three different RSU deployment strategies in a single framework, on static locations, public mobile transportation, and fully controllable vehicles. We first introduce a new strategy to abstract a map of city area into a grid graph. Then, we formulate the problem as a new optimization problem and show its NP-hardness. To solve this problem, we transform this problem into another optimization problem and propose a new polynomial running time approximation algorithm and show its performance ratio is at least the half of the best possible ratio. Index Terms—Vehicular ad-hoc networks, road side unit de-ployment, approximation algorithm, graph theory, optimization. I