k-Connected Relay Node Deployment in Heterogeneous Wireless Sensor Networks

Wireless sensor networks (WSNs) are mostly implemented in outdoor and harsh environments; consequently, the probability of node failure is high and applying the fault tolerance mechanisms becomes crucial. The relay nodes placement is a mechanism in order to increase the connectivity level of WSNs. In this paper, a new method (KCN) is proposed to create k-connected WSNs based on injection of relay nodes in heterogeneous WSNs, where sensor nodes have different transmission radii. KCN consists of three algorithms. Algorithm 1 creates a minimum k-vertex connected graph based on graph theory and Algorithm 2 determines the candidate relay nodes and their locations for implementing each edge in the obtained graph. Algorithm 3 minimizes the deployed relay node count based on two new proposed lemmas. The main issues of concern here are the time complexity and the deployed relay node count. KCN has a low time complexity of O(n²), where n is the sensor node count. The simulation results demonstrate that KCN applies less relay nodes than the most closely related approach.