Locating and bypassing routing holes in sensor networks

Qing Fang, Jie Gao, Leonidas J. Guibas

Research output: Contribution to journalConference articlepeer-review

344 Scopus citations


Many algorithms for routing in sensor networks exploit greedy forwarding strategies to get packets to their destinations. In this paper we study a fundamental difficulty such strategies face: the "local minimum phenomena" that can cause packets to get stuck. We give a definition of stuck nodes where packets may get stuck in greedy multi-hop forwarding, and develop a local rule, the TENT rule, for each, node in the network to test whether a packet can get stuck at that node. To help the packets get out of stuck nodes, we describe a distributed algorithm, BOUNDHOLE, to build routes around holes, which are connected regions of the network with boundaries consisting of all the stuck nodes. We show that these hole-surrounding routes 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)2458-2468
Number of pages11
JournalProceedings - IEEE INFOCOM
StatePublished - 2004
Externally publishedYes
EventIEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies - Hongkong, China
Duration: Mar 7 2004Mar 11 2004

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering


  • Combinatories
  • Graph theory
  • System design


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

Cite this