Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods
Authors:
Open Access
- 18 May 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 135-144
Abstract
Location-free boundary recognition is crucial and critical for many fundamental network functionalities in wireless ad hoc and sensor networks. Previous designs, often coarse-grained, fail to accurately locate boundaries, especially when small holes exist. To address this issue, we propose a fine-grained boundary recognition approach using connectivity information only. This algorithm accurately discovers inner and outer boundary cycles without using location information. To the best of our knowledge, this is the first design being able to determinately locate all hole boundaries no matter how small the holes are. Also, this distributed algorithm does not rely on high node density. We formally prove the correctness of our design, and evaluate its effectiveness through extensive simulations. Copyright 2009 ACMKeywords
This publication has 17 references indexed in Scilit:
- Classes of cycle basesDiscrete Applied Mathematics, 2007
- Coordinate-free Coverage in Sensor Networks with Controlled Boundaries via HomologyThe International Journal of Robotics Research, 2006
- Hole detection or2006
- Topological hole detection in wireless sensor networks and its applications2005
- Neighborhood-Based Topology Recognition in Sensor Networks2004
- Localized Delaunay triangulation with application in ad hoc wireless networksIEEE Transactions on Parallel and Distributed Systems, 2003
- Geographic routing without location information2003
- Power-aware localized routing in wireless networksIEEE Transactions on Parallel and Distributed Systems, 2001
- A linear algorithm for embedding planar graphs using PQ-treesJournal of Computer and System Sciences, 1985
- Congruent Graphs and the Connectivity of GraphsAmerican Journal of Mathematics, 1932