On the Monitoring Period for Fault-Tolerant Sensor Networks

F. Araújo and L. Rodrigues

Selected sections of this report will be published in the Proceedings of the Second Latin-American Symposium on Dependable Computing, Salvador, Bahia, Brazil, October 2005.

Abstract

Connectivity of a sensor network depends critically on tolerance to node failures. Nodes may fail due to several reasons, including energy exhaustion, material fatigue, environmental hazards or deliberate attacks. Although most routing algorithms for sensor networks have the ability to circumvent zones where nodes have crashed, if too many nodes fail the network may become disconnected.

A sensible strategy for increasing the dependability of a sensor network consists in deploying more nodes than strictly necessary, to replace crashed nodes. Spare nodes that are not fundamental for routing or sensing may go to sleep. To ensure proper operation of the sensor network, sleeping nodes should monitor active nodes frequently. If crashed nodes are not replaced, messages follow sub-optimal routes (which are energy inefficient) and, furthermore, the network may eventually become partitioned due to the effect of accumulated crashes. On the other hand, to save the energy, nodes should remain sleeping as much as possible. In fact, if the energy consumed with the monitoring process is too high, spare nodes may exhaust their batteries (and the batteries of active nodes) before they are needed.

This paper studies the optimal monitoring period in fault-tolerant sensor networks to ensure that: i) the network remains connected (i.e., crashed nodes are detected and substituted fast enough to avoid the network partition) and, ii)} the lifetime of the network is maximized (i.e., inactive nodes save as much battery as possible).

Also available extended report, (pdf) .


Luís Rodrigues