Tuesday, 22 July 2014

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 interboundaries from external ones and distributed coordinations on a boundary. We implement LBS in TOSSIM and use simulations to show its effectiveness.
Existing boundary detection approaches are designed just for a “one-time shot,” the detection actually has to be constantly conducted, given the time-varying nature of the events under surveillance. Such events, for example, can be bio-geo-chemical processes, streams/currents, or pollution in atmosphere or waterbodies (e.g., ocean).Depending on different deployments, a WSN can be either static (e.g., in smart buildings) to observe the event passing through or stuck to an event to keep monitoring it (e.g., for water monitoring). In both cases, boundary detection has to be performed online to keep tracking either the event or the network boundary. Unfortunately, the existing approaches have too high message or time complexity to be performed in an online manner. Another feature of the events under consideration is that they often span a 3-D volume rather than a 2-D surface. Given the fact that very few existing proposals deal with 3-D boundary detection and that extending the approaches designed for 2-D surfaces to 3-D volumes is highly nontrivial in geometry,1 a clean-slate boundary detection algorithm needs to be designed for 3-D WSNs. Note that, should a 2-D boundary detection be ever needed, it would be really trivial to reduce a 3-D detection approach to 2-D.
·       It difficult to tell internal boundaries from the external one from a local point of view.
·       Routing protocols may fail when facing or on such boundaries.
·       These approaches have too high message or time complexity to be performed in an online manner.
We tackle the aforementioned challenges by proposing Localized Boundary Detection and Parametrization (LBDP). LBDP comes with two components: Uniform Fast On-Line boundary Detection (UNFOLD) for boundary detection and Localized Boundary Sphericalization (LBS) for boundary regularization. The underlying principle of UNFOLD is to apply a spherical inversion to the local coordinates of every node, such that a (locally) concave surface can be “unfolded” into a convex one. As a result, the painful procedure of identifying a boundary node on a “notched” surface is reduced to convexity test (which can be tackled with simple geometric tools). Though the idea of inversion is borrowed from, UNFOLD has substantially improved on it by implementing it in a distributed networking scenario. As UNFOLD entails only simple and uniform computation for every node, it can be performed super fast and hence enable online boundary detection. Building upon UNFOLD, LBS employs a diffusion process to regularize an arbitrary boundary into a unit sphere. The algorithm is purely localized and involves only arithmetic operations, and the resulting virtual coordinates on the sphere may be exploited by many networking functionalities, such as distinguishing internal boundaries from the external one.
·       It efficiently regularizes an arbitrary genus-0 boundary into a unit sphere.
·       It distinguishes internal boundaries from the external one (from a local point of view) based on the virtual coordinates delivered by LBS.



ü Processor                  -        Pentium –IV

ü Speed                        -        1.1 Ghz
ü RAM                         -        512 MB(min)
ü Hard Disk                 -        40 GB
ü Key Board                -        Standard Windows Keyboard
ü Mouse                       -        Two or Three Button Mouse
ü Monitor                     -        LCD/LED

         Operating system :         Windows XP
         Coding Language :         Java
         Data Base             :         MySQL
         Tool                     :         Net Beans IDE

 Feng Li, Chi Zhang, Jun Luo, Shi-Qing Xin, and Ying He, LBDP: Localized Boundary Detection and Parametrization for 3-D Sensor Networks IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 22, NO. 2, APRIL 2014.

No comments:

Post a Comment