Distributed Boundary Detection Algorithms for 3D Wireless Sensor Networks

In this dissertation, I have firstly proposed a distributed and localized algorithm for precise boundary detection in 3D wireless networks based on local coordinates. The objectives have been in two folds. First, I have aimed to identify the nodes on the boundaries of a 3D network, which serve as a key attribute that characterizes the network, especially in such geographic exploration tasks as terrain and underwater reconnaissance. Second, I have intended to construct locally planarized 2-manifold surfaces for inner and outer boundaries, in order to enable available graph theory tools to be applied on 3D surfaces, such as embedding, localization, partition, and greedy routing among many others. My proposed scheme is localized, requiring information within one-hop neighborhood only. The simulation results have shown that the proposed algorithms can effectively identify boundary nodes and surfaces, even under high measurement errors.;Secondly, I have proposed a distributed boundary detection algorithm, dubbed Coconut, based on connectivity only for 3D wireless sensor networks. Its basic idea is to construct a tetrahedral structure to delineate the approximate geometry of the 3D sensor network, which consequently yields a set of sealed triangular boundary surfaces for separating non-boundary nodes and boundary node candidates. While the former are hollowed out immediately, the latter are further refined to identify the final boundary nodes and fine-grained boundary surfaces. I have proven the correctness of the algorithm and quantitatively demonstrated its effectiveness via simulations under various network models. The proposed Coconut algorithm is a connectivity-based approach, with no need for localization or distance measurement. It has not constraint on communication models and only assumes a constant maximum transmission range, which is generally known in practical wireless sensor networks. Moreover, it can effectively identify boundaries in both uniformly and non-uniformly distributed sensor networks, exhibiting excellent robustness to sensor distribution.;Finally, I have proposed a distributed algorithm based on the boundary nodes identified by previous algorithms that triangulates an arbitrary sensor network, with no constraints on the communication model or the granularity of the triangulation. I have proven its correctness in 2D, and further extend it to 3D surface networks.