期刊名称：International Journal of Distributed Sensor Networks
印刷版ISSN：1550-1329
电子版ISSN：1550-1477
出版年度：2013
卷号：2013
DOI：10.1155/2013/690974
出版社：Hindawi Publishing Corporation
摘要：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.
