A random scheme to implement m-connected k-covering wireless sensor networks

Deploying m-connected k-covering (MK) wireless sensor networks (WSNs) is crucial for reliable packet delivery and target coverage. This paper proposes implementing random MK WSNs based on expected m-connected k-covering (EMK) WSNs. We define EMK WSNs as random WSNs mathematically expected to be both m-connected and k-covering. Deploying random EMK WSNs is conducted by deriving a relationship between m-connectivity and k-coverage, together with a lower bound for the required number of nodes. It is shown that EMK WSNs tend to be MK asymptotically. A polynomial worst-case and linear average-case complexity algorithm is presented to turn an EMK WSN into MK in non-asymptotic conditions. The m-connectivity is founded on the concept of support sets to strictly guarantee the existence of m disjoint paths between every node and the sink. The theoretical results are assessed via experiments, and several metaheuristic solutions have been benchmarked to reveal the appropriate size of the generated MK WSNs.