RoadGate: Mobility-Centric Roadside Units Deployment for Vehicular Networks

With the increase of the storage capacity, computing, and wireless networking of the vehicular embedded devices, the vehicular networks bring a potential to enable new applications for drivers and passengers in the vehicles. Due to the prohibitive cost of deployment and management of a roadside unit (RSU), it is difficult to cover roads with a large number of RSUs so that every vehicle can always keep a connection with the nearby RSU. In this paper, we study the problem of deploying the RSUs to provide the desired connectivity performance while minimizing the number of the deployed RSUs. The key idea of our solution is to exploit the time-stable mobility pattern to find the optimal deployment places. We analyze a realistic vehicle trace, observe the mobility pattern, and propose a graph model to characterize it. Based on the graph model, we transform the gateway deployment problem into a vertex selection problem in a graph. By reducing it into the minimum vertex coverage problem, we show that the RSU deployment problem is NP-complete. Then, a heuristic algorithm RoadGate is proposed to search greedily the optimal positions. Extensive simulations based on the synthetic and realistic scenarios are carried out to evaluate the performance. The results show that RoadGate outperforms other approaches in terms of the number of required RSUs and the actual achieved coverage performance.