Connectivity-aware Relay Node Deployment in Grid-based Wireless Sensor Networks

Relay node placement can be an effective mean for boosting the performance of a Wireless Sensor Network (WSN) in terms of several metrics such as network connectivity, network lifetime and fault tolerance. In this paper, we consider the problem of deploying relay nodes (RNs) in a WSN to ensure network connectivity. We propose a novel heuristic to find a minimum number of RNs together with their locations needed in order to repair a disconnected network with a grid topology. We first determine the optimal solution for connecting a set of four disconnected nodes and then, by applying our heuristic, we ensure connectivity between these sets via steinerized edges. The runtime complexity of the proposed heuristic is quasilinear in the number of nodes, which is lower than competitive approaches. In addition to that, our heuristic can achieve network connectivity using 32% less of RNs. The performances of the proposed heuristic are validated through simulations.