Wireless vehicular networks have received significant attention. As vehicles are increasingly equipped with onboard sensors, large-scale urban monitoring with vehicular networks becomes attractive. To facilitate better monitoring, it is highly desirable that sensory data of the vehicles can be gathered with high fidelity. Deploying wireless relays is a cost-effective approach for connection enhancement. In this paper we consider the crucial problem of optimal relay placement for maximum data collection from the vehicles. The placement is greatly impacted by vehicle distribution and mobility, which makes it difficult to determine the optimal locations. We theoretically prove that the relay placement problem (RPP) is NP-hard even when the vehicle traces are assumed as a priori knowledge. We first propose an approximate algorithm for the RPP with given vehicle traces (D-RPP). This algorithm is proved to achieve an approximation ratio of (1-1/ e), where e is the natural logarithm base. To solve the RPP without a priori knowledge about future vehicle traces (N-RPP), we first show that there is strong regularity with vehicle mobility by entropy analysis. Then, we propose an algorithm for solving the N-RPP, which exploits regularity extracted from historical traces. Extensive simulations based on real trace datasets show that the D-RPP algorithm produces performance close to the optimum.
['Youchen Bao', 'Yanmin Zhu']
On Optimal Relay Placement for Urban Vehicular Networks