A Depth-First Search based Connectivity Estimation Approach for Fault Tolerant Wireless Sensor Networks

Connectivity stability is one of the most important requirements in Wireless Sensor Networks (WSNs) that has a considerable effect on the functionality of these networks. WSNs use multi hop connections for packet delivery. Failures on nodes may change the network topology and connectivity status. A reliable WSN must tolerate the node failures without loosing its connectivity. One of an important approach for increasing the network connectivity is k-connectivity. A k-connected network remains connected after removing arbitrary k-1 nodes. So, in high k values, the connectivity of a WSN can be considered as stable. Finding the k value of a WSN provides useful information about the stability of its connections. In this paper, we propose a distributed algorithm for estimating the k value of a WSN. The proposed approach establishes distributed depth first search (DFS) trees to find the available disjoint paths between the nodes. The minimum number of disjoint paths between the nodes determines the k value. During the DFS tree construction, the nodes overhear the sent packets of their neighbors to reduce the total energy consumption. The comprehensive simulation results show that the mean square errors of the estimated values by the proposed algorithm reach up to 28.5% lower and its correct estimations are up to 32% higher than the existing distributed algorithms.