Constrained Relay Node Placement in Energy Harvesting Wireless Sensor Networks

The constrained relay node placement problem In a wireless sensor network is concerned with deploying a minimum number of relay nodes (RNs) in a set of candidate locations in the network to satisfy a specific requirement(s), such as connectivity or survivability. In this paper, we study the constrained relay node placement problem in an energy harvesting network. In such a network, it is imperative that the placement be energy harvesting aware, because the more energy the placed nodes can harvest the more effective the network can be. In our study, the RNs are constrained to be placed at only the candidate locations, where the energy harvesting potential of the locations are known a priori. Our aim is to place a minimum number of relay nodes, to achieve connectivity or survivability, while ensuring that the relay nodes harvest large amounts of ambient energy. For both the connectivity and survivability, we study the problems, prove that they are NP-hard, and propose polynomial time O(1) approximation algorithms with low approximation ratios. We also validate the effectiveness and efficiency of our algorithms through simulations and show that the RNs placed by our algorithms harvest 50% more energy on average, in comparison to those placed by the algorithms unaware of energy harvesting.