Topological Geometric Algorithm And Applications In Wireless Sensor Networks

WSN (Wireless Sensor Network) has been made viable by the convergence ofmicro-electro-mechanical systems technology, wireless communications and digitalelectronics. The sensing tasks and potential applications are explored. WSNs are densewireless networks of small, low-cost sensors, which collect and disseminateenvironmental information.Topological geometrical algorithms of WSN are capable of improving performancesof some applications by applying computational geometrics. They have significantinfluences on fundamental applications of WSN like routing, localization, boundarydetection, skeleton extraction, convex partition and so on. The thesis providescomprehensive research on topological geometrical algorithms and applications whichare connectivity-based localization and boundary detection. We propose novel algorithmson these applications to solve existing difficult problems and improve performances ofWSN.Connectivity-based and Anchor-free Three-dimensional Localization (CATL) schemefor large scale sensor networks with concave regions distinguishes itself from previouswork with a combination of three features:(1) it works for networks in both2D and3Dspaces, possibly containing holes or concave regions;(2) it is anchor-free, and uses onlyconnectivity information to faithfully recover the original network topology, up to scalingand rotation;(3) it does not depend on the knowledge of network boundaries, which suitsit well to situations where boundaries are difficult to identify. The key idea of CATL is todiscover the notch nodes, where shortest paths bend and hop-count-based distance startsto significantly deviate from the true Euclidean distance. An iterative protocol isdeveloped that uses a notch-avoiding multilateration mechanism to localize the network.Simulations show that CATL achieves accurate localization results with a moderateper-node message cost.To the best of our knowledge, CABET, a novel Connectivity-bAsed BoundaryExtraction scheme for large-scale Three-dimensional sensor networks, is the first3D capable and pure connectivity-based solution for detecting sensor network boundaries. Itis fully distributed. A highlight of CABET is its non-uniform critical node sampling,called r’-sampling, that selects landmarks to form boundary surfaces with bias towardnodes embodying salient topological features. Simulations show that CABET is able toextract a well-connected boundary in the presence of holes and shape variation, withperformance superior to that of some state-of-the-art alternatives. In addition, we showhow CABET benefits a range of sensor network applications including3D skeletonextraction and3D segmentation.