Locating and bypassing holes in sensor networks

Qing Fang, Jie Gao, Leonidas J. Guibas

Research output: Contribution to journalArticlepeer-review

192 Scopus citations


In real sensor network deployments, spatial distributions of sensors are usually far from being uniform. Such networks often contain regions without enough sensor nodes, which we call holes. In this paper, we show that holes are important topological features that need to be studied. In routing, holes are communication voids that cause greedy forwarding to fail. Holes can also be defined to denote regions of interest, such as the "hot spots" created by traffic congestion or sensor power shortage. In this paper, we define holes to be the regions enclosed by a polygonal cycle which contains all the nodes where local minima can appear. We also propose simple and distributed algorithms, the TENT rule and BOUNDHOLE, to identify and build routes around holes. We show that the boundaries of holes marked using BOUNDHOLE can be used in many applications such as geographic routing, path migration, information storage mechanisms and identification of regions of interest.

Original languageEnglish (US)
Pages (from-to)187-200
Number of pages14
JournalMobile Networks and Applications
Issue number2
StatePublished - Apr 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


  • Distributed algorithms
  • Routing
  • Sensor networks


Dive into the research topics of 'Locating and bypassing holes in sensor networks'. Together they form a unique fingerprint.

Cite this