Optimizing wireless sensor networks deployment with coverage and connectivity requirements

The wireless sensor networks are widely studied in the scientific literature due to their practical importance. They are used for monitoring and surveillance of strategic areas, and tracking targets in several fields, such as military, battlefields, health care, agriculture, and industry. Challenges in wireless sensor networks are related to localization, routing, limited storage, and deployment of sensors. In this paper, we focus on deployment issues. While the main aim is to use the smallest number of sensors, a wireless sensor network has to ensure full coverage of the area of interest, collect the proper data, and guarantee that such data are available at a sink node, that plays the role of the central base station. We consider the problem of deploying the minimum number of sensors that are able to fully cover the area of interest, ensuring the connectivity of each sensor with the sink node. We propose a new formulation, based on both the set covering problem and the shortest paths problem from a single source to all destinations. The proposed model has been compared with the state-of-the-art considering instances inspired by the scientific literature. The numerical results highlight the superiority of the proposed formulation in terms of both efficiency and effectiveness.