Energy-Efficient Bridge Detection Algorithms for Wireless Sensor Networks

A bridge is a critical edge whose fault disables the data delivery of a WSN component. Because of this, it is important to detect bridges and take preventions before they are corrupted. Since WSNs are battery powered, protocols running on WSN should be energy efficient. In this paper, we propose two distributed energy-efficient bridge detection algorithms for WSNs. The first algorithm is the improved version of Pritchard's algorithm where two phases are merged into a single phase and radio broadcast communication is used instead of unicast in order to remove a downcast operation and remove extra message headers. The second algorithm runs proposed rules on 2-hop neighborhoods of each node and tries to detect all bridges in a breadth-first search (BFS) execution session using O( N ) messages with O ( Δ ( log 2 ( N ) ) ) bits where N is the node count and Δ is the maximum node degree. Since BFS is a natural routing algorithm for WSNs, the second algorithm achieves both routing and bridge detections. If the second proposed algorithm is not able to to classify all edges within the BFS phase, improved version of Turau's algorithm is executed as the second phase. We show the operation of the algorithms, analyze them, and provide extensive simulation results on TOSSIM environment. We compare our proposed algorithms with the other bridge detection algorithms and show that our proposed algorithms provide less resource consumption. The energy saving of our algorithms is up to 4.3 times, while it takes less time in most of the situations.