LBDP: Localized Boundary Detection and Parametrization for 3-D Sensor Networks
- 8 April 2013
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 22 (2) , 567-579
Abstract
Many applications of wireless sensor networks involve monitoring a time-variant event (e.g., radiation pollution in the air). In such applications, fast boundary detection is a crucial function, as it allows us to track the event variation in a timely fashion. However, the problem becomes very challenging as it demands a highly efficient algorithm to cope with the dynamics introduced by the evolving event. Moreover, as many physical events occupy volumes rather than surfaces (e.g., pollution again), the algorithm has to work for 3-D cases. Finally, as boundaries of a 3-D network can be complicated 2-manifolds, many network functionalities (e.g., routing) may fail in the face of such boundaries. To this end, we propose Localized Boundary Detection and Parametrization (LBDP) to tackle these challenges. The first component of LBDP is UNiform Fast On-Line boundary Detection (UNFOLD). It applies an inversion to node coordinates such that a “notched” surface is “unfolded” into a convex one, which in turn reduces boundary detection to a localized convexity test. We prove the correctness and efficiency of UNFOLD; we also use simulations and implementations to evaluate its performance, which demonstrates that UNFOLD is two orders of magnitude more time- and energy-efficient than the most up-to-date proposal. Another component of LBDP is Localized Boundary Sphericalization (LBS). Through purely localized operations, LBS maps an arbitrary genus-0 boundary to a unit sphere, which in turn supports functionalities such as distinguishing inter boundaries from external ones and distributed coordinations on a boundary. We implement LBS in TOSSIM and use simulations to show its effectiveness.Keywords
This publication has 25 references indexed in Scilit:
- Harmonic quorum systems: Data management in 2D/3D wireless sensor networks with holes2012
- Connectivity-based and anchor-free localization in large-scale 2d/3d sensor networks2010
- Localized Algorithm for Precise Boundary Detection in 3D Wireless Networks2010
- Localised alpha-shape computations for boundary recognition in sensor networksAd Hoc Networks, 2009
- Light-Weight Contour Tracking in Wireless Sensor Networks2008
- Localized algorithms for coverage boundary detection in wireless sensor networksWireless Networks, 2007
- Hole detection or2006
- Topological hole detection in wireless sensor networks and its applications2005
- Coverage and hole-detection in sensor networks via homology2005
- Improved MDS-based localization2005