Energy-sustainable relay node deployment in wireless sensor networks

Emergence of diverse renewable energy harvesting technologies and their incorporation into tiny sensor devices have given birth to Energy Harvesting Wireless Sensor Networks (EH-WSNs), where the problem domain has shifted from energy conservation to energy sustainability of the network. Renewable energy harvesting and depletion of sensor devices are stochastic and thus, energy availability in the devices is sporadic rather than continuous. Therefore, the optimal deployment of data routing devices (i.e., relay nodes) and their activity scheduling to ensure that, the data from all source sensors could be routed to the sink while keeping the network functional perpetually, is a challenging research problem. In this paper, we develop a multi-constraint mixed integer linear program (MILP) to minimize the number of relay nodes to be deployed in the network, while considering connectivity, sustainability and unpredictable energy harvesting and depletion rates. We refer to this problem as SMRMC (sustainable minimum-relay maximum-connectivity deployment) which is proved to be NP-hard. A light weight k-connected greedy solution to the SMRMC problem has been developed first for k=1,k=1, and thereafter, a generalized solution has been presented for any k (k ≥ 2) by constructing convex-polytopes among the existing relay nodes. Extensive simulation experiments have been conducted to validate the performance of the proposed deployment strategies. Performance studies carried out in MATLAB, show that the proposed SMRMC algorithms can achieve up to twice the network lifetime compared to state-of-the-art approaches whilst deploying minimum number of relay nodes.