Type
Text
Type
Thesis
Date
2011-05-31
Keywords
wireless sensor networks | network topology | sensor network geometry
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/70786
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
Wireless sensor networks are tightly associated with the underlying environment in which the sensors are deployed. The global geometry and topology of the network is of great importance to both sensor network applications and the implementation of networking functionalities. In this thesis, we contribute a comprehensive framework for the discovery of sensor network geometry based only on connectivity information, and apply it to several challenging problems: Boundary Recognition, Homology Computation, Layout Recovery and Localization We develop a distributed algorithm to detect the nodes on the boundaries in a sensor network by using only connectivity information. Our algorithm is motivated by an observation that holes in a sensor field create irregularities in hop count distance. Inner holes of the sensor field disrupt the natural flow of the shortest path tree. We then exploit special structure of the shortest path tree to detect the existence of holes. We also connect those boundary nodes into meaningful boundary cycles and obtain the medial axis of the sensor field as a byproduct. We show by extensive simulation that our boundary detection algorithm gives good results even for networks with low density. The correctness of the algorithm for a continuous geometric domain bounded by polygonal obstacles is proved rigorously as well. iii We introduce a new quantity, called homotopy feature size (hfs), for bounded domains. It measures half the length of the shortest loop through point x in domain X. The resort to an intrinsic metric makes this feature size rather insensitive to the local geometry of the domain. Therefore, hfs can lead to a reduced number of samples which still capture the topology of X. We propose algorithms for estimating the hfs, selecting a landmark set of sufficient density, and computing the homology of domain X using the geodesic witness complex W X (L) and a relaxed version W X,ν(L). We also present some practical simulations in the context of sensor networks that corroborate our theoretical results. We propose a distributed algorithm to discover and recover the layout of a large sensor network. We select landmarks on network boundaries with sufficient density, construct the landmark Voronoi diagram and its dual combinatorial Delaunay complex on these landmarks. The key insight is that when the landmarks are dense enough to capture the local geometric complexity, the combinatorial Delaunay complex is globally rigid and has a unique realization in the plane. Moreover, an embedding by simply gluing the Delaunay triangles properly derives a faithful network layout, which consequently leads to a practical and sufficiently accurate localization algorithm. We also prove the global rigidity of the combinatorial Delaunay complex in the case of a continuous geometric region. A limitation of our original layout discovery algorithm is its reliability of boundary detection result. As a follow up to the previous algorithm, we develop a new landmark selection algorithm with incremental Delaunay refinement. The new algorithm does not assume any knowledge of the network boundary and runs in a distributed manner to select landmarks incrementally until both the global rigidity property (the Delaunay complex is globally rigid and thus can be embedded uniquely) and the coverage property (every node is not far from the embedded Delaunay complex) are met. The new algorithm improves the robustness and applicability of the original localization algorithm substantiall
Recommended Citation
Wang, Yue, "Geometry Discovery with Connectivity Information and Applications in Sensor Networks" (2011). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 6.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/6