LBDP: Localized Boundary Detection and Parametrization for 3-D Sensor Networks

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.