Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

7.6 DETECTION OF CRITICAL NODES AND LINKS

In sensor and actuator networks, the failure of some nodes or links, if generating several partitions of the network, may be fatal for collecting data from the field or performing certain actions on sensors. It is expected, however, that the network exhibits some critical connectivity before partitioning. Recognizing such properties in a timely manner could allow to perform some data or service replication, so that the network can continue to function after the partition occurred. This kind of detection may also be used at deployment time (e.g., while deciding a common communication radius) to ensure that no such critical node or link exists, that is, the network is biconnected. Both approaches may be considered to add fault tolerance to the network. We discuss below some ideas for detecting critical links and nodes.

Algorithms for detecting critical nodes and links based on global knowledge are well known. However, their use in sensor networks is limited since this requires the entire topology to be known by a single entity, which is not scalable and implies a delay between topological changes and the system reactions. It appears therefore preferable to try to detect critical links and/or nodes in a local and distributed manner, even if making possibly a few appreciation mistakes that imply a more “pessimistic view” of the connectivity (an element seen as critical while not being so).

In a global context, a node or link is said to be critical, ...