Redundancy Analysis and a Distributed Self-Organization Protocol for Fault-Tolerant Wireless Sensor Networks∗

∗A preliminary and abridged version of this paper was published in Proc. IEEE DCOSS Conf. (Lecture Notes in Computer Science LCNS 3560), pp. 191–205, 2005. This research was supported by DARPA, and administered by the Army Research Office under Emergent Surveillance Plexus MURI Award No. DAAD19-01-1-0504. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the sponsoring agencies.

This work was carried out when Yi Zou was working as a post-doc research associate at the Department of Electrical and Computer Engineering, Duke University.

Abstract

Sensor nodes in a distributed sensor network can fail due to a variety of reasons, e.g., harsh environmental conditions, sabotage, battery failure, and component wear-out. Since many wireless sensor networks are intended to operate in an unattended manner after deployment, failing nodes cannot be replaced or repaired during field operation. Therefore, by designing the network to be fault-tolerant, we can ensure that a wireless sensor network can perform its surveillance and tracking tasks even when some nodes in the network fail. In this paper, we describe a fault-tolerant self-organization scheme that designates a set of backup nodes to replace failed nodes and maintain a backbone for coverage and communication. The proposed scheme does not require a centralized server for monitoring node failures and for designating backup nodes to replace failed nodes. It operates in a fully distributed manner and it requires only localized communication. This scheme has been implemented on top of an energy-efficient self-organization technique for sensor networks. The proposed fault-tolerance-node selection procedure can tolerate a large number of node failures using only localized communication, without losing either sensing coverage or communication connectivity.

Keywords:

• Connected Dominating Set
• Fault Tolerance
• Localized Communication
• Network Organization
• Sensor Networks
• Topology Control

Notes

∗A preliminary and abridged version of this paper was published in Proc. IEEE DCOSS Conf. (Lecture Notes in Computer Science LCNS 3560), pp. 191–205, 2005. This research was supported by DARPA, and administered by the Army Research Office under Emergent Surveillance Plexus MURI Award No. DAAD19-01-1-0504. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the sponsoring agencies.

This work was carried out when Yi Zou was working as a post-doc research associate at the Department of Electrical and Computer Engineering, Duke University.