Optimal roadside gateway deployment for VANETs

VANETs allowing the mobile vehicles exchange data with the roadside gateways are being used in various applications such as local electronic advertisement, intelligent transportation system and urban data collection. In this paper, we study the problem of deploying the gateways to provide the desired communication performance while minimizing the deployment cost. The key idea of our solution is to exploit the time-stable vehicular mobility pattern to find the optimal deployment places. We propose a graph model to characterize the observed mobility pattern. Then the gateway deployment problem is transformed into a vertex selection problem in a graph. By reducing it the minimum vertex coverage problem, we show the gateway deployment problem is NP-complete, so a heuristic algorithm MobGDeploy is proposed to search greedily the optimal deployment points. Extensive simulations are carried out to evaluate the performance, and the results show that the proposed algorithm outperforms others.