Q. Fang and J. Gao and L. Guibas, Locating and Bypassing Routing Holes in Sensor Networks, 23rd Conference of the IEEE Communications Society (InfoCom), 2004.

Abstract:

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.

Bibtex:

@inproceedings{fgg-lbrhsn-04,
author="Q. Fang and J. Gao and L. Guibas",
title="Locating and Bypassing Routing Holes in Sensor Networks",
booktitile="The 23rd Conference of the IEEE Communications Society (Infocom)
year="2004",
page=""
}