Delay-bounded minimal cost placement of roadside units in vehicular ad hoc networks

This paper addresses the delay-bounded minimal cost roadside units (RSUs) placement problem in vehicular ad hoc networks. There are two types of RSUs: cable connected RSU (c-RSU) and wireless RSU (w-RSU). c-RSUs are interconnected through wired lines, and they form the backbone of VANETs. They also usually have a larger communication range due to the availability of power source and more powerful devices. Despite the benefit of fast information dissemination, c-RSUs are often associated with high cost. On the other hand, w-RSUs connect to other RSUs through wireless communication and typically have a smaller transmission range. Given a set of candidate sites in a region and a delay bound, the problem is how to find the optimal placement of c-RSUs and w-RSUs, such that the total cost is minimized, while all of the vehicles in the region can receive the message sent out from c-RSUs within the delay bound. We first prove that the problem is NP-hard. Then, we propose a greedy algorithm and a two-phase algorithm to solve the problem. Simulation results show our proposed algorithms can significantly reduce the total cost, compared with other methods.