Bridge protection algorithms - A technique for fault-tolerance in sensor networks

Sensor networks operating in the field might be subject to catastrophic events which destroy a large number of nodes in the geographic area. Often, the aftermath of such an event is the creation of a network of bridged fragments where connectivity is maintained by one or several bridge nodes. These networks are vulnerable, because the bridge nodes will soon exhaust their energy resources leading to the fragmentation of the network. This paper describes a bridge protection algorithm (BPA), a combination of techniques which, in response to a catastrophic event, change the behavior of a set of topologically important nodes in the network. These techniques protect the bridge node by letting some nodes take over some of the responsibilities of the sink. At the same time, they relieve some other overwhelmed nodes and prevent the apparition of additional bridge nodes. To achieve this, the algorithm sacrifices the length of some routes in order to distribute routes away from critical areas. In a variation on the BPA algorithm, we show that if geographic information about the nodes is available, replacing shortest path routing with a routing model which follows the edges of the relational neighborhood graph will lead to further improvements in the expected connected lifetime of the network.