The coverage problem in a wireless sensor network

Chi Fu Huang, Yu-Chee Tseng*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

474 Scopus citations


One of the fundamental issues in sensor networks is the coverage problem, which reflects how well a sensor network is monitored or tracked by sensors. In this paper, we formulate this problem as a decision problem, whose goal is to determine whether every point in the service area of the sensor network is covered by at least k sensors, where k is a given parameter. The sensing ranges of sensors can be unit disks or non-unit disks. We present polynomial-time algorithms, in terms of the number of sensors, that can be easily translated to distributed protocols. The result is a generalization of some earlier results where only k = 1 is assumed. Applications of the result include determining insufficiently covered areas in a sensor network, enhancing fault-tolerant capability in hostile regions, and conserving energies of redundant sensors in a randomly deployed network. Our solutions can be easily translated to distributed protocols to solve the coverage problem.

Original languageEnglish
Pages (from-to)519-528
Number of pages10
JournalMobile Networks and Applications
Issue number4
StatePublished - 4 Jul 2005


  • Ad hoc network
  • Computer geometry
  • Coverage problem
  • Sensor network
  • Ubiquitous computing
  • Wireless network

Fingerprint Dive into the research topics of 'The coverage problem in a wireless sensor network'. Together they form a unique fingerprint.

Cite this