On Maximizing Capacity And Mobile Coverage In Urban Vehicular Networks

The success of a real-time sensing application with a vehicular network highlydepends on the spatiotemporal coverage of sensing data that can be collected from thevehicular network. Deploying broadband wireless base stations is an effective way tocollect vehicular sensing data and the deployment of base stations has a great impacton delay-constrained coverage. This paper considers the critical problem of basestations for maximizing delay-constrained coverage of an urban area achieved by thevehicular network. This is particularly challenging. We theoretically prove that theoptimal deployment of base stations is NP-hard even when the future vehicular tracesare assumed as a priori. In a realistic setting, however, the future vehicular tracescannot be known in advance. Therefore, the challenge is to incorporate high vehiclemobility and compute the base station deployment for maximizing the expecteddelay-constrained coverage. By mining a large dataset of real vehicular GPS traces,we show that there is strong regularity with vehicle mobility. With this importantobservation, we formulate a new objective of maximizing the expected sensingcoverage. This takes random vehicle mobility into account and exploits the regularityin vehicle mobility. We develop greedy algorithms for base station deployment. Theachieved 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 onthe real vehicular GPS trace dataset and conclusive results show that our algorithmsachieve near optimal coverage of the urban area and significantly outperformalternative algorithms.Nextly，after solving the problem of maximzing the delay-constrained coveragewith one hop data relaying, we challenge a more difficult problem of maximizingcapacity in vehicular networks. Capacity of wireless vehicular networks is of greatimportance to a wide spectrum of mobile sensing applications. A vehicular network issubject to frequent disconnection and fast topology change and thus its capacitybecomes a critical issue. In this paper, we study the fundamental problem ofmaximizing message delivery capacity of a delay-constrained vehicular network. The message delivery capacity is affected by a number of factors, such as AP deployment,message relaying, delay constraint, road topology and vehicle movement. Maximizingmessage delivery capacity with delay constraint in a vehicular network remains achallenging issue. This paper formulates the problem of maximizing the messagedelivery capacity into an optimization problem with delay constraint. We solve theproblem in two steps. First, we build a generalized abstract communication graphbased on an arbitrary underlying road network and derive the delivery probability of adelay-constrained message. We then design a Simulated Annealing (SA) basedalgorithm for obtaining a new optimal deployment for the APs. Second, we build theupper bound of the message delivery capacity of a delay-constrained vehicularnetwork by devising a dynamic programming (DP) based algorithm. A centralizedalgorithm and a distributed algorithm are designed for approximating the tight upperbound. To the best of our knowledge, this is the first attempt to approaching themaximum message delivery capacity in a realistic delay-constrained vehicularnetwork. Comprehensive simulations based on real vehicle traces have beenconducted. Performance results validate our analysis and demonstrate theeffectiveness of the designed algorithms.