K-Connectivity in Wireless Sensor Networks: Overview and Future Research Directions

Abstract

$k$-connectivity is a strong notion of robust connectivity. Indeed, in a $k$-connected network, each node has k disjoint paths to all the other nodes in the network. Therefore, even in the case of $\mathrm{k}-1$ node/link failure(s), a k-connected wireless sensor network (WSN) remains connected because each node still has, at least, one path to the rest of the surviving nodes. Networks with higher $k$ values are, typically, more reliable and fault tolerant than those with lower k values. In this study, we present a systematic and dedicated overview of WSN k-connectivity problem. We, first, outline the k-connectivity detection problem (i.e., determining the k value of a network). Second, we explore the k-connected network deployment problem. Third, we dissect the restoration problem that addresses the rehabilitation of a deteriorated network to restore its original k value. Built upon the provided foundations, we identify and discuss a rich set of important and promising open research problems along with pointers to possible solution approaches. © 1986-2012 IEEE.