Distributed Protocols for Connectivity Restoration in Damaged Wireless Sensor Networks

Abstract

Decreasing costs and increasing functionality of hardware devices have made Wireless Sensor Networks (WSNs) attractive for applications that serve in inhospitable environments like battlefields, planetary exploration or environmental monitoring. WSNs employed in these environments are expected to work autonomously and extend network lifespan for as long as possible while carrying out their designated tasks. The harsh environment exposes individual nodes to a high risk of failure and potentially partition the network into disjoint segments. Therefore, a network must be able to self-heal and restore lost connectivity using available resources. The ad-hoc nature of deployment, harsh operating environment means that proactive strategies based on redundancy cannot be applied as the scope of the damage could be so large that redundant nodes could be lost as well. The lack of external resources like satellite coverage preclude the application of centralized recovery approaches since they require the entire network state to be available for recovery. Hence distributed approaches that employ reactive strategies are the most viable solutions for these networks. In this dissertations, we tackle the problem of distributed connectivity restoration in a WSN that has been partitioned into multiple disjoint segments due to multi-node failures. We consider multiple variants of the problem based on the available resources, and present a set of novel recovery schemes that suit the capabilities and requirements of the WSN being repaired. The correctness and time-complexity of all proposed approaches are analyzed and their performance is validated through extensive experiments.