A Randomized Algorithm for Roadside Units Placement in Vehicular Ad Hoc Network

In this paper, we investigate the problem of optimal road side units (RSUs) placement in Vehicular Ad Hoc Network (VANET) on a highway, which enables the VANET maintain a good connectivity. Our goal is to find out minimal number of road side units, such that the vehicles could communicate with RSUs. These road side units are connected by wire. We develop a randomized algorithm to deploy road side units in the VANET. It gives an approximation to the optimal distance to guarantee the information can be passed to RSUs from the accident site via the VANET. Simulations are conducted to show the performance of our proposed method.