On Maximizing Delay-Constrained Coverage of Urban Vehicular Networks

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.