ERCIM News No.47, October 2001 [contents]
Fault Diagnosis in Wireless Sensor Networks
by Stefano Chessa and Paolo Santi
Scientists at CNR address the problem of identifying faulty mobiles in ad hoc wireless networks and propose an energy efficient silent fault diagnosis protocol.
Wireless sensor networks are receiving increasing attention due to their ability to monitor a wide variety of environments, ranging from remote geographical regions to industrial plants, from office buildings to toxic urban locations. A wireless sensor network is usually composed of hundreds or thousands of sensors equipped with computation, sensing and communication devices, which are coordinated in a distributed mode in order to collect information on their surroundings. During the lifetime of the network, the information collected by the sensors is periodically transmitted to sink nodes, which can be either mobile or base stations. Sink nodes are used by external operators to retrieve the information gathered by the network.
Due to the limited energy supply of sensors, protocols for sensor networks should be designed with the goal of minimizing energy consumption. For this reason, energy-efficient information dissemination protocols for sensor networks have been recently proposed in the literature. These protocols exploit network redundancy to achieve fault tolerance: when a sensor crashes (either because of battery depletion or due to a catastrophic event), neighboring sensors can cover, at least partially, its sensing task. However, none of these protocols provide explicit knowledge regarding the state (faulty or fault-free) of the sensors in the network. In our opinion, the extraction of explicit diagnostic information from the network could be important in those situations in which sensors repair/ reconfiguration is feasible.
In order to motivate this hypothesis, consider the following example. A sensor network is used to help rangers to monitor a vast natural park. The sensors, which have limited energy supplies and are mostly static, provide information about the presence of animals, tourists, fire, flooding and so on. Rangers, who are equipped with mobile stations, move around the park for control and maintenance. Mobile stations are connected to the sensor network through the nearest sensor. This way, the rangers can be alerted of abnormal events, and they can quickly intervene where needed. However, if there is no provision for sensor maintenance, eventually the batteries will be depleted and crash. As a consequence, the number of non-operating sensors in the system will increase until the system gets disconnected, and is no longer functional. In such a scenario, sensors should provide diagnostic information along with sensor data, thus enabling rangers to maintain network functionality by replacing faulty sensors or by recharging depleted batteries. For this purpose, sensors in the network should execute a distributed diagnosis protocol, either periodically or on-demand.
However, existing distributed diagnosis protocols have been designed either for multiprocessor computers or for wired computer networks. As a consequence, all the protocols proposed so far assume that units communicate according to the one-to-one paradigm typical of wired networks. This means that, if applied to sensor networks, these models are unable to take advantage of the shared nature of communication, and are thus not feasible or at best extremely energy consuming.
For this reason, we have developed a distributed silent fault diagnosis protocol explicitly designed for wireless sensor networks. The protocol takes advantage of the shared nature of communications and aims at minimizing the total number of bits exchanged for the purpose of diagnosis, thus reducing the energy consumption entailed by the protocol execution. The protocol first constructs a spanning tree of the graph representing the network topology, then exchanges diagnostic information only along the edges of the tree. This allows a significant reduction in the number of messages to be sent for the purpose of diagnosis. We have shown that the protocol exchanges the minimum number of bits required by any diagnosis algorithm for wireless sensor networks, thus proving its optimality.
We have also studied the problem of identifying soft-faulted mobiles in ad hoc networks. Contrary to the case of silent faults, soft-faulted nodes can continue to communicate with other units, although with altered behavior. We have proposed a new comparison-based diagnostic model based on the one-to-many communication paradigm. We show that using this strategy the ability to diagnose soft faults in the presence of mobility is significantly reduced with respect to the stationary case, meaning that a somewhat weaker notion of diagnosis should be considered under this scenario. We have also designed a distributed soft faults diagnosis protocol for stationary ad hoc networks based on the new model. The analysis of the time and communication complexity of the protocol shows that efficient soft faults diagnosis in this scenario is possible.