Design and Analysis of a Breadth First Search based Connectivity Robustness Estimation Approach in Wireless Sensor Networks

Maintaining the connectivity in wireless sensor networks (WSNs) is one of the fundamental tasks that directly affects the functionality of these networks. WSNs use multi hop ad hoc connections to deliver the packets between remote nodes, hence failures in some nodes can destroy the network connectivity. Tolerating the node failures without loosing the connectivity is one of the important properties of reliable WSNs. A kappa-connected network keeps its connectivity after failures in any kappa-1 nodes. So, a WSN has robust connectivity, if the kappa value is reasonably high. Detecting the k value of an existing WSN may provide important information about the reliability of that network. This paper proposes a distributed algorithm for finding the k value of a WSN. The proposed algorithm uses a distributed breadth first search (BFS) algorithm to find the bottleneck of a network. The bottleneck in the BFS tree is defined as the level of tree that has minimum number of nodes. The proposed algorithm finds the number of nodes in the bottleneck and minimum degree of nodes and sets the k value to the minimum of these values. The comprehensive simulation results shows that the energy consumption of proposed algorithm is up to 85% lower and its estimations are up to 17.5% more accurate with up to 16% lower mean square error than the existing distributed algorithms.