Relay Node Placement with Assured Coverage and Connectivity: A Jarvis March Approach

Relay node placement preserving coverage and connectivity is an important problem for the deployment of a fault tolerant two tier wireless sensor network (WSN). In this paper, we propose an algorithm for relay node placement that ensures k-coverage of the sensor nodes and s-connectivity of the relay nodes within the network. The basic goal of the algorithm is to optimize the network cost by using least number of relay nodes. This is carried out by reducing the overlapped coverage area of the relay nodes. The algorithm is based on the spiral traversal of sensor nodes, which is generated by using Jarvis March approach. The proposed algorithm runs in \(O(n^{2})\) time for n sensor nodes and is shown to be a 1.5-approximation algorithm. It is equally efficient for different and unequal degree of coverage and connectivity in the target area. The algorithm is experimented through the simulation run for different scenarios of WSN. The experimental results are then compared with some existing algorithms to demonstrate its effectiveness.