The success of a real-time sensing application with a vehicular network highly depends on the spatiotemporal coverage of sensing data that can be collected from the vehicular network. Deploying broadband wireless base stations is an effective way to collect vehicular sensing data and the deployment of base stations has a great impact on delay-constrained coverage. This paper considers the critical problem of base stations for maximizing delay-constrained coverage of an urban area achieved by the vehicular network. This is particularly challenging. We theoretically prove that the optimal deployment of base stations is NP-hard even when the future vehicular traces are assumed as a priori. In a realistic setting, however, the future vehicular traces cannot be known in advance. Therefore, the challenge is to incorporate high vehicle mobility and compute the base station deployment for maximizing the expected delay-constrained coverage. By mining a large dataset of real vehicular GPS traces, we show that there is strong regularity with vehicle mobility. With this important observation, we formulate a new objective of maximizing the expected sensing coverage. This takes random vehicle mobility into account and exploits the regularity in vehicle mobility. We develop greedy algorithms for base station deployment. The achieved sensing coverage of the proposed algorithm is guaranteed to be larger than (1-1/e) of the theoretical optimum. We have performed extensive simulations based on the real vehicular GPS trace dataset and conclusive results show that our algorithms achieve near optimal coverage of the urban area and significantly outperform alternative algorithms.

This paper considers the problem of optimal relay placement for urban monitoring in wireless vehicular networks. The placement of relays 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. Keywords-wireless vehicular networks, wireless relays, optimal placement, approximation algorithms.