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. This thesis proves that deploying sensors on grid points to construct a wireless sensor network that fully covers critical equilateral (or, square) grids using minimum sensors, termed CRITICAL-GRID COVERAGE (or, CRITICAL-SQUARE-GRID COVERAGE), is NP-Complete. In addition, approximation algorithms are proposed for CRITICAL-SQUARE-GRID COVERAGE. Simulations show that the proposed algorithms provide good solutions for CRITICAL-SQUARE-GRID COVERAGE.