Nodes Deployment for Coverage in Rechargeable Wireless Sensor Networks

This paper considers a novel problem in rechargeable wireless sensor networks (WSNs), given a set of locations with one or more targets, determine the minimum number of sensor nodes to deploy in order to ensure a given coverage quality. This problem is significant as sensor nodes are often used to monitor one or more valuable assets or critical infrastructure. We formulate the problem as an integer linear program (ILP) and use it to compute the minimum number of sensor nodes required to monitor targets in small-scale WSNs. For large-scale WSNs, we relax the integer variables of the ILP and devise three approximation algorithms: greedy round node placement, target protection node placement, and energy efficient node placement (EENP). We prove the worst case performance bound of these algorithms. We also conducted simulation to compare these algorithms against the optimal solution produced by the ILP. Our results show that the solution computed by EENP is within one percentage point from the optimal solution.