A Caltech Library Service

Locating and Bypassing Holes in Sensor Networks

Fang, Qing and Gao, Jie and Guibas, Leonidas J. (2006) Locating and Bypassing Holes in Sensor Networks. Mobile Networks And Applications, 11 (2). pp. 187-200. ISSN 1383-469X. doi:10.1007/s11036-006-4471-y.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access
Additional Information:© Springer Science + Business Media, LLC 2006. Published online: 31 March 2006. The authors wish to thank Alon Efrat and the anonymous reviewers for their suggestions in improving the presentation of this paper.
Subject Keywords:distributed algorithms; routing; sensor networks
Issue or Number:2
Record Number:CaltechAUTHORS:20170408-143451175
Persistent URL:
Official Citation:Fang, Q., Gao, J. & Guibas, L.J. Mobile Netw Appl (2006) 11: 187. doi:10.1007/s11036-006-4471-y
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:75970
Deposited By: 1Science Import
Deposited On:25 Apr 2017 22:26
Last Modified:15 Nov 2021 16:56

Repository Staff Only: item control page