On Lifetime Maximization and Fault Tolerance Measurement in Wireless Ad Hoc and Sensor Networks

Abstract

In this dissertation we study two important issues in wireless ad hoc and sensor networks: lifetime maximization and fault tolerance. The first part investigates how to maximally extend the lifetime of randomly deployed wireless sensor networks under limited resource constraint, and the second part focuses on how to measure the fault tolerance and attack resilience of wireless ad hoc networks. We take the approach of adaptive traffic distribution and power control to maximize the lifetime of randomly deployed wireless sensor networks. After abstracting the network into multiple layers, we model the lifetime maximization problem as a linear program. We study both scenarios where receiving/processing power consumption is ignored and receiving/processing is included. In both cases, we have a similar observation: for each packet to be sent, the sender should either transmit it using the transmission range with the highest energy efficiency per bit per meter, or transmit it directly to the sink. We then prove it is true in general. Finally, we propose a fully distributed algorithm to adaptively split traffic and adjust transmission power. Extensive simulation studies demonstrate that the network lifetime can be dramatically extended by applying the proposed approach in various scenarios. Besides studying the lifetime extension problem for fully deployed wireless sensor networks, we also investigate how to extend the network lifetime via joint relay node deployment and adaptive traffic distribution. We formulate this problem as a mixed-integer nonlinear-program problem, which is NP-hard in general. We then propose a greedy heuristic to attack it. Both numerical and simulation results show that significant network lifetime extension can be achieved. In the second part of this dissertation, we investigate how to measure the fault tolerance and attack resilience for randomly deployed wireless ad hoc networks. We first propose two new metrics to measure the average case of network service quality: average pairwise connectivity and pairwise connected ratio. We then propose the fault tolerance and attack resilience metric: alpha-p-resilience, where a network is alpha-p-resilient if at least alpha portion of nodes pairs remain connected as long as no more than p fraction of nodes is removed from the network.