Optimal 3-coverage with minimum separation requirements for ubiquitous computing environments

Jung Eun Kim, Junghee Han, Chang Gun Lee

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


Sensors have been increasingly used for many ubiquitous computing applications such as asset location monitoring, visual surveillance, and human motion tracking. In such applications, it is important to place sensors such that every point of the target area can be sensed by more than one sensor. Especially, many practical applications require 3-coverage for triangulation, 3D hull building, and etc. Also, in order to extract meaningful information from the data sensed by multiple sensors, those sensors need to be placed not too close to each other-minimum separation requirement. To address the 3-coverage problem with the minimum separation requirement, our recent work (Kim et al. 2008) proposes two heuristic methods, so called, overlaying method and TRE-based method, which complement each other depending on the minimum separation requirement. For these two methods, we also provide mathematical analysis that can clearly guide us when to use the TRE-based method and when to use the overlaying method and also how many sensors are required. To make it self-contained, in this paper, we first revisit the two heuristic methods. Then, as an extension, we present an ILP-based optimal solution targeting for grid coverage. With this ILP-based optimal solution, we investigate how much close the two heuristic methods are to the optimal solution. Finally, this paper discusses the impacts of the proposed methods on real-deployed systems using two example sensor systems. To the best of our knowledge, this is the first work that systematically addresses the 3-coverage problem with the minimum separation requirement.

Original languageEnglish (US)
Pages (from-to)556-570
Number of pages15
JournalMobile Networks and Applications
Issue number5
StatePublished - Oct 2009
Externally publishedYes


  • 3-coverage
  • Minimum separation requirement
  • Sensor placement
  • Ubiquitous computing

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Optimal 3-coverage with minimum separation requirements for ubiquitous computing environments'. Together they form a unique fingerprint.

Cite this