Efficient Algorithm for Constructing Minimum Size Wireless Sensor Networks to Fully Cover Critical Square Grids

Wireless sensor networks are formed by connected sensors that each have the ability to collect, process, and store environmental information as well as communicate with others via inter-sensor wireless communication. These characteristics allow wireless sensor networks to be used in a wide range of applications. In many applications, such as environmental monitoring, battlefield surveillance, nuclear, biological, and chemical (NBC) attack detection, and so on, critical areas and common areas must be distinguished adequately, and it is more practical and efficient to monitor critical areas rather than common areas if the sensor field is large, or the available budget cannot provide enough sensors to fully cover the entire sensor field. This provides the motivation for the problem of deploying the minimum sensors on grid points to construct a connected wireless sensor network able to fully cover critical square grids, termed CRITICAL-SQUARE-GRID COVERAGE. In this paper, we propose an approximation algorithm for CRITICAL-SQUARE-GRID COVERAGE. Simulations show that the proposed algorithm provides a good solution for CRITICAL-SQUARE-GRID COVERAGE.