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

Abstract

<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> -connectivity is a strong notion of robust connectivity. Indeed, in a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> -connected network, each node has k disjoint paths to all the other nodes in the network. Therefore, even in the case of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{k}-1$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> 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.