Stochastic and information theoretic models for design and performance evaluation of mobile ad hoc and sensor networks

Autonomous multihop wireless networks, such as wireless ad hoc, mesh, and sensor networks, have a lot of applications in a variety fields like providing short and long term connectivity to communities, surveillance, monitoring, and defense. However, scalability of such networks is marred by scarce bandwidth, broadcast nature of the wireless medium, and dynamic nature of network topology due to node mobility. In this thesis we investigate the fundamental performance limits of multihop wireless networks and study the impact of mobility on capacity deficit and coverage quality. We also present mechanisms to exploit trade-offs in order to improve the scalability of such autonomous networks.; We use a queuing theoretic approach in order to evaluate average end-to-end delay and maximum achievable per-node throughput in random access MAC based wireless ad hoc, mesh, and energy efficient sensor networks. We present an analytical model that takes into account the number of nodes, the random packet arrival process, the extent of locality of traffic, and the back off and collision avoidance mechanisms of random access MAC. We model the random access multihop wireless networks as open G/G/1 queuing networks and use the diffusion approximation method for evaluating the closed form expressions for average end-to-end delay. The average service time of a node is calculated and used to evaluate the expressions for maximum achievable per-node throughput. For similar network parameters, the maximum achievable throughput result obtained through our analysis is asymptotically similar to the established information theoretic results. This implies that the capacity of multihop wireless networks diminishes to 0 as network size grows.; The overhead incurred by routing protocols in order to cope with dynamic topology causes deficit in the capacity of mobile ad hoc networks. Knowledge of minimum routing overheads required for reliable routing of data packets is important for understanding the deviation of a routing protocol from the optimal and for inspiring the development of optimal routing protocols. We use an information-theoretic framework for analyzing the minimum routing overhead incurred by geographic routing in mobile networks. We formulate the minimum routing overhead problem as a rate-distortion problem and evaluate a lower bound on the minimum routing overhead incurred for routing packets with a desired level of reliability. The lower bound depends not only on the node mobility but also on the packet arrival process in the network. We also characterize the deficit in transport capacity caused by the routing overheads. It is observed that for high node mobility and packet arrival rate, the complete transport capacity may be exhausted by the routing overheads only. Based on the insights developed from the analysis we present mechanisms to reduce routing overhead in geographic and reactive routing protocols at the cost of increased packet delay.; To improve the scalability of multihop wireless networks, it is important to develop mechanisms that explore various trade-offs such as overhead-delay and overhead-success rate tradeoffs. The use of random walk for discovering routing information and other resources is an efficient means of reducing overheads at the cost of increased delay and failure probability. We present an analytical framework for performance analysis of random walk in a well connected network graph. Based on the analytical results we develop a mechanism, called EBAS, which uses feedback from previous searches in order to adapt the aggressiveness of random walk. EBAS may also be used to fine-tune the overhead-delay-failure ratio trade-offs according to the needs of an application. The simulation results indicate that EBAS performs better than flooding and non-adaptive random walk.; It has been recently shown that mobility improves capacity (at the cost of possibly infinite delays) and coverage of wireless ad hoc and sensor network...