Fundamental problems in vehicular ad hoc networks: Connectivity, reachability, interference, broadcast capacity, and online routing algorithms

Vehicular Ad Hoc Networks (VANET), which are composed of vehicles equipped with advanced wireless communication devices, is a paradigm of the decentralized Advanced Traveler Information Systems (ATIS). With inter-vehicle communication being enabled, VANET present high potential to overcome the disadvantages of current centralized ATIS. Therefore, they attracted significant interest of researchers from several academic disciplines such as transportation science, computer science, and electrical engineering. However, very few previous efforts have integrated traffic flow features into vehicular ad hoc networks research. As an effort to make up this deficiency, this research investigates several properties of VANET taking account of the traffic flow characteristics. In particular, we address the geometric connectivity, reachability, interference, broadcast capacity, and online routing problems respectively.;The first part of this research explores the geometric connectivity which represents the probability that the network is connected at any time instant over a given time period. This study considers a VANET as a nominal system with uncertain disturbance. The nominal system is represented by a free flow, in which space headway is assumed to obey an exponential distribution. The unexpected driver behavior such as acceleration, deceleration, and lane changing are modeled as uncertain disturbance which is further characterized by a robustness factor in our analytical model. Our regression results show that the robustness factor is a function of the traffic flow parameters including average traffic speed, average space headway and its variance. Analytical expressions are developed to characterize the connectivity of VANET on freeway segments incorporating traffic flow features and driver behavior. The simulation validation demonstrates that our analytical expression can evaluate the geometric connectivity of VANET more accurately than previous efforts in literature.;We study the influence of vehicular mobility on information propagation in VANET in the second part of the dissertation. In our study, we first define an "information flow network" and then introduce "reachability" to characterize information propagation performance. An information flow network is a time expanded graph composed of asynchronous communication link (based on geometric distance) and nodes (vehicles). The reachability is the probability that every two vehicles in the information flow network are connected in a given time interval. To capture various driver behavior, we separate the drivers into three clusters which are aggressive, defensive, and slow drivers respectively. Correspondingly, we approximate the relative movement between individual vehicles by the relative movement between different driver clusters. Based on this approximation, we develop analytical expressions to evaluate the reachability during a short time period. Our results show that the relative movement between vehicles enables individual vehicles to communicate with more neighbors and therefore improves the opportunity that the traffic information is transmitted in a forward direction. Simulation results validate our assumptions and analytical expressions.;Based on the analytical results in the previous topics, the third part of this research further explores the interference in VANET under various traffic flow conditions. Both our analytical expressions and the simulation results show that the vehicular mobility impacts the interference that individual vehicles experiences significantly.;The capacity of VANET, which is another important aspect to evaluate the performance of VANET, is explored in the fourth part of this research. In our study, the capacity of VANET is defined as the number of vehicles that can successfully transmit information simultaneously. This number is constrained by the interference in the physical layer. Under the constraints of the interference, the capacity of VANET is first explored using an integer programming formulation. And then, based on the integer programming model, we further develop statistical model to characterize the capacity of VANET by the parameters of the traffic flow network as well as the communication network. To improve the prediction accuracy of the statistical model, central composite experiment design method is applied.;The last issue of this dissertation focuses on developing an online routing algorithm for vehicles accessing to real-time traffic information through VANET. The presented routing policy attempts to take into account the dynamic traffic features so that we model the system as a network with stochastic time-varying link cost information, and at each intersection instead of specifying an optimal path, our routing policy only identifies the optimal immediate arc to take. In addition, we consider uncertain VANET performance. The proposed routing policy involves time-dependent information reliability and time delay in the optimal arc decision procedure. Our routing policy is formulated as a set of recurrent equations which is solved by the proposed modified label-correcting algorithm.;In summary, this research contributes to understanding the performance of VANET by integrating transportation science and wireless networking concepts. (Abstract shortened by UMI.)...