Exact and Efficient Heuristic Deployment in WSN under Coverage, Connectivity, and Lifetime Constraints

Wireless sensor networks lay down many challenging optimization problems, such as coverage, node deployment, tracking or energy conservation. In this paper, we are interested in deployment strategies that result in a minimum of sensors network while ensuring target coverage connectivity between the sensors and sink. To this end, we propose two alternative deployment approaches based on integer linear programming and we exploit the linear-programming sequential fixing technique to design three polynomial-time heuristic procedures. The performance and effectiveness of these approaches in terms of network cost and computational requirements are highlighted through several experiments. Furthermore, we investigate the network lifetime problem where a given operational duration must be reached.