UNFOLD
Authors:
Open Access
- 17 May 2011
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-11
Abstract
A wireless sensor network becomes dynamic if it is monitoring a time-variant event (e.g., expansion of oil spill in ocean). In such applications, on-line 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., oil spill again), the algorithm has to work for 3D cases. To this end, we propose UNiform Fast On-Line boundary Detection (UNFOLD) to tackle the challenge. The essence of UNFOLD is to inverse node coordinates such that a "notched" surface is "unfolded" into a convex one, which in turn reduces boundary detection to simple convexity test. UNFOLD is uniform as every node behaves the same (performing coordinate inversion and convexity test), and it is super fast as both computation and communication involve only one-hop neighbors. We prove the correctness and efficiency of UNFOLD; we also use simulations and implementations to evaluate its performance, which demonstrates that UNFOLD is 100 times more time and energy efficient than the most up-to-date proposal.Keywords
This publication has 16 references indexed in Scilit:
- 3DQS: Distributed Data Access in 3D Wireless Sensor Networks2011
- Localised alpha-shape computations for boundary recognition in sensor networksAd Hoc Networks, 2009
- Optimal Geographic Routing for Wireless Networks with Near-Arbitrary Holes and Traffic2008
- Localized algorithms for coverage boundary detection in wireless sensor networksWireless Networks, 2007
- Boundary recognition in sensor networks by topological methods2006
- Localization in sparse networks using sweeps2006
- Improved MDS-based localization2005
- Geographic routing without location information2003
- Three-Dimensional Triangulations from Local TransformationsSIAM Journal on Scientific and Statistical Computing, 1989
- On the shape of a set of points in the planeIEEE Transactions on Information Theory, 1983