Abstract
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. In this thesis, the problem of deploying the minimum sensors on grid points to construct a wireless sensor network fully covering critical grids, termed CRITICAL-GRID COVERAGE, is studied. Since CRITICAL-GRID COVERAGE is NP-Complete [16], four heuristics for CRITICAL-GRID COVERAGE are proposed. Simulations show that STBCGCA the proposed algorithm provides a good solution for CRITICAL-GRID COVERAGE.