PACK: Path coloring based k-connectivity detection algorithm for wireless sensor networks

A k-connected wireless sensor network (WSN) can tolerate failures on k-1 arbitrary nodes without loosing the connectivity between the remaining active nodes. Hence, the k value is one of the useful benchmarks that can help to measure the network reliability. Given that the nodes in a k-connected network has at least k disjoint paths to each other, we propose the path coloring based k-connectivity detection algorithm (PACK) that finds the k by counting the disjoint paths between the sink and all other nodes. The proposed algorithm has two Detection and Notification phases. In the Detection phase, all nodes find their disjoint paths to the sink and in the Notification phase the minimum detected path count, which determines the global k, is sent to the sink node. We theoretically prove that the detection range of our proposed algorithm is better than the existing distributed algorithms and uses fixed length messages with O(nΔlog2n) bit complexity and O(n) time complexity where n is the number of nodes and Δ is the maximum node degree. According to the comprehensive simulation results, the average correct detection ratio of proposed algorithm is more than 91% which is at least 2.3 times higher than the existing algorithms.