Building Sustainable Wireless Sensor Network Systems: Flooding Designs and Network Diagnosis

Intended for network-wide dissemination of commands, configurations and code binaries, flooding has been investigated extensively in wireless sensor networks. However, little work has yet been done on low-duty-cycle wireless sensor networks in which, nodes stay asleep most of time and wake up asynchronously. Due to the loss of connectivity while nodes are sleeping, a broadcasting packet is rarely received by multiple nodes simultaneously, a unique constraining feature that makes existing solutions unsuitable. Combined with unreliable links, flooding in low-duty-cycle networks is a new challenging issue.;This thesis presents two flooding solutions for low-duty-cycle wireless sensor networks with the consideration of unreliable wireless links, as well as a fault detection design for further prolonging the lifetime of sensor networks. First, we introduce Opportunistic Flooding, a novel design tailored for the low-duty-cycle operation and predetermined working schedules. This design starts with an energy-optimal tree structure as the basic flooding structure. Probabilistic forwarding decisions are made at each sender based on the delay distribution of next-hop receivers, and that only opportunistically early packets are forwarded via links outside the tree. The flooding delay is efficiently improved from sending these opportunistically early packets, and by avoiding sending those late ones, the redundant energy cost is significantly reduced. To improve the performance further, we further propose a forwarder selection method to alleviate the hidden terminal problem and a link-quality-based backoff method to resolve simultaneous forwarding operations. Opportunistic Flooding is evaluated in extensive simulations and a testbed experiment, with comparison to an improved traditional flooding method as well as the optimal performance achievable by oracle flooding designs. Evaluation shows that Opportunistic Flooding is close to the optimal performance achievable by oracle flooding designs. It also achieves significantly shorter flooding delay while consuming only 20%∼60% of the transmission energy in various low-duty-cycle network settings.;While Opportunistic Flooding is suitable for those sensor networks with predetermined schedules, we discover that the energy cost can be further reduced by allowing sensor nodes tune their schedules to make the flooding process efficient. The second flooding design, named Correlated Flooding, is then presented. This design adapts existing flooding-tree-based designs for low-duty-cycle networks by scheduling the sender nodes of common parents wake up simultaneously. In contrast to traditional solutions where the energy optimality in a designated flooding-tree is achieved by selecting parents with the highest link quality, we demonstrate that surprisingly more energy can be saved by considering link correlation. We not only experimentally verify the existence of link correlation but also mathematically prove that the energy consumption of broadcasting can be reduced by letting nodes with higher correlation receive packets simultaneously. Correlated Flooding exploits the link correlation so that nodes with high correlation are assigned to a common sender and their receptions of a broadcasting packet are only acknowledged by a single ACK. This unique feature effectively ameliorates the ACK implosion problem, saving energy on both data packets and ACKs. Correlated Flooding is extensively evaluated by simulations and a test-bed experiment with up to 40 MICAz nodes. The performance of Correlated Flooding is compared with a traditional energy-optimal tree approach. Evaluation results show that Correlated Flooding saves more than 66% energy on ACKs and 15%¡"50% energy on data packets for most network settings, while having similar performance on flooding delay and reliability.;With the designs of Opportunistic Flooding and Correlated Flooding, the lifetime of wireless sensor networks are prolonged by both low-duty-cycle operations and energy efficient communication protocols. After the deployment of a sensor network, however, individual sensor nodes may fail due to a number of reasons, such as bad weather and limited battery. The existence of faulty nodes greatly affects the performance of a sensor network, including the performance of the flooding service. As a result, they should be detected and removed from the network as fast as possible. We finally present a fault detection design, named FIND, for network maintenance. FIND works for systems where the measured signal attenuates with distance. After the nodes in a network detect a natural event, FIND ranks the nodes based on their sensing readings as well as their physical distances from the event. A node is considered faulty if there is a significant mismatch between the sensor data rank and the distance rank. FIND is extensively evaluated in simulations and two test bed experiments, with radio signal and acoustic signal respectively. Evaluation shows that FIND has a less than 5% miss detection rate and false alarm rate in most noisy environments.