DECK: A distributed, asynchronous and exact k-connectivity detection algorithm for Wireless Sensor Networks

Wireless Sensor Networks (WSNs) are one of the widespread platforms for communications and remote sensing. A robust WSN should tolerate the failures of nodes without losing the connection to active nodes. A network is k-connected if all active nodes remain connected after failures in k-1 arbitrary nodes. Finding (detecting) the k value in a WSN is a significant operation to estimate the connectivity robustness, reliability and load balancing level of the network. Also, the detection of k values provides useful information for connectivity restoration, lower bound of node degree, critical nodes and possible cycles. In this paper, we propose an asynchronous distributed algorithm (DECK) for k-connectivity detection in WSNs. In the proposed algorithm, each node estimates a local k using its 2-hop neighborhood information and then a distributed linked list of minimum estimations is created between the nodes. Finally, the sink node validates the correctness of detected values by finding the number of node-disjoint paths to the node having the minimum estimation. We analyze our algorithm in detail, provide theoretical analysis, testbed experiments on the IRIS nodes and simulation results in the TOSSIM simulator by comparing with the other algorithms. The comprehensive testbed and simulation results show that the proposed algorithm always finds exact k values with reasonable energy consumption while the correct detection ratios of existing distributed algorithms on similar networks are usually less than 40%.