This research focuses on distributed and localized algorithms for precise boundary detection in 3-D wireless networks. Our objectives are twofold. First, we aim to identify the nodes on the boundaries of a 3-D network, which serve as a key attribute that characterizes the network, especially in such geographic exploration tasks as terrain and underwater reconnaissance. Second, we construct locally planarized 2-manifold surfaces for inner and outer boundaries in order to enable available graph theory tools to be applied on 3-D surfaces, such as embedding, localization, partition, and greedy routing among many others. To achieve the first objective, we propose a Unit Ball Fitting (UBF) algorithm that discovers a majority of boundary nodes, followed by a refinement algorithm, named Isolated Fragment Filtering (IFF), to remove isolated nodes that are misinterpreted as boundary nodes. Based on the identified boundary nodes, we develop an algorithm that constructs a locally planarized triangular mesh surface for each 3-D boundary. Our proposed scheme is localized, requiring information within 1-hop neighborhood only. We further extend the schemes for online boundary detection in mobile sensor networks aiming to achieve low overhead. Our simulation and experimental results demonstrate that the proposed algorithms can effectively identify boundary nodes and surfaces, even under high measurement errors.

We propose a distributed and deterministic routing algorithm with constant storage, communication and computation overhead, dubbed trace-routing, for strong-connected 3D wireless sensor networks. Its basic idea is to construct a virtual cutting plane that intersects boundary surface to yield a trace, along which a routing path with guaranteed delivery can be established. We prove the correctness of trace-routing under both continuous and discrete settings. We implement the trace-routing algorithm on Crossbow sensors and carry out extensive simulations to evaluate its routing efficiency.

This paper focuses on greedy routing in wireless networks deployed on 2-D and 3-D surfaces. It introduces a distributed embedding scheme based on the conformal map theory. The proposed scheme identifies the convex hull of each boundary and employs Yamabe flow to compute flat metric under convex hull boundary condition to establish virtual coordinates. Such virtual coordinates are then used for greedy routing. Since the proposed embedding algorithm maps the outer boundary to a convex shape and an interior concave void to a circle-like convex polygon, it effectively eliminates local minimum and attains guaranteed delivery. At the same time, it introduces a small distortion only and consequently achieves a low stretch factor. Our simulations show that its stretch factor is lower than any existing greedy embedding algorithms. Moreover, the proposed scheme is merely based on local connectivity and consumes a small constant storage, thus scaling to arbitrarily large networks.

The medial axis of a shape provides a compact abstraction of its global topology and a proximity of its geometry. The construction of medial axis in two-dimensional (2D) sensor networks has been discussed in the literature, in support of several applications including routing and navigation. In this work, we first reveal the challenges of constructing medial axis in a three-dimensional (3D) sensor network. With more complicated geometric features and complex topology shapes, previous methods proposed for 2D settings cannot be extended easily to 3D networks. Then we propose a distributed algorithm with linear time complexity and communication cost to build a well-structured medial axis of a 3D sensor network without knowing its global shape or global position information. Furthermore we apply the computed medial axis for safe navigation and distributed information storage and retrieval in 3D sensor networks. Simulations are carried out to demonstrate the efficiency of the proposed medial axis-based applications in various 3D sensor networks.

Location awareness is imperative for a variety of sensing applications and network operations. Although a diversity of GPS-less and GPS-free solutions have been developed recently for autonomous localization in wireless sensor networks, they primarily target at 2D planar or 3D volumetric settings. There exists unique and fundamental hardness to extend them to 3D surface. The contributions of this work are twofold. First, it proposes a theoretically-proven algorithm for the 3D surface localization problem. Seeing the challenges to localize general 3D surface networks and the solvability of the localization problem on single-value (SV) surface, this work proposes the {\em cut-and-sew} algorithm that takes a divide-and-conquer approach by partitioning a general 3D surface network into SV patches, which are localized individually and then merged into a unified coordinates system. The algorithm is optimized by discovering the minimum SV partition, an optimal partition that creates a minimum set of SV patches. Second, it develops practically-viable solutions for real-world sensor network settings where the inputs are often noisy. The proposed algorithm is implemented and evaluated via simulations and experiments in an indoor testbed. The results demonstrate that the proposed cut-and-sew algorithm achieves perfect 100% localization rate and the desired robustness against measurement errors.

This work aims to address the problem of localization in 3D surface wireless sensor networks. First, it reveals the unique hardness in localization on 3D surface in comparison with the well-studied localization problems in 2D and 3D space, and offers useful insight into the necessary conditions to achieve desired localizability. Second, it formulates the localization problem under a practical setting with estimated link distances (between nearby nodes) and nodal height measurements, and introduces a layered approach to promote the localizability of such 3D surface sensor networks. Crossbow sensor-based experiments and large-scale simulations are carried out to evaluate the performance of the proposed localization algorithm. The numeric results show that it can effectively improve localizable rate and achieve low location errors and computational overhead, with the desired tolerability to measurement errors and high scalability to large-size wireless sensor networks.

Compared with its 2D counterpart, the scalability problem is greatly exacerbated in a 3D wireless sensor network. In this paper, we propose a scalable routing algorithm, dubbed Bubble Routing. It preprocesses global knowledge via a distributed algorithm, such that a node only needs to store a small constant information to make correct and efficient local routing decisions and achieve guaranteed delivery at the same time. More specifically, the proposed bubble routing algorithm first decompose a 3D network into a set of hollow spherical cells (HSCs). A continuous and one-to-one mapping is applied and a virtual tree structure is established inside each HSC to enable greedy routing. On the other hand, routing across HSCs is guided by a small routing table whose size is bounded by the number of interior holes. Our simulation results show that bubble routing can achieve guaranteed data delivery, low stretch factor, and well balanced traffic load.

This work proposes a novel connectivity-based localization algorithm, well suitable for large-scale sensor networks with complex shapes and non-uniform nodal distribution. In contrast to current state-of-art connectivity-based localization methods, the proposed algorithm is fully distributed, where each node only needs the information of its neighbors, without cumbersome partitioning and merging process. The algorithm is highly scalable, with limited error propagation and linear computation and communication cost with respect to the size of the network. Moreover, the algorithm is theoretically guaranteed and numerically stable. Extensive simulations and comparison with other methods under various representative network settings are carried out, showing superior performance of the proposed algorithm.

Triangulation serves as the basis for many geometry-based algorithms in wireless sensor networks. In this paper we propose a distributed algorithm that produces a triangulation for an arbitrary sensor network, with no constraints on communication model or granularity of the triangulation. We prove its correctness in 2D, and further extend it to sensor networks deployed on 3D open and closed surfaces. Our simulation results show that the proposed algorithms can tolerate distance measurement errors, and thus work well under practical sensor network settings and effectively promote the performance a range of applications that depend on triangulations.

With both computational complexity and storage space bounded by a small constant, greedy routing is recognized as an appealing approach to support scalable routing in wireless sensor networks. However, significant challenges have been encountered in extending greedy routing from 2D to 3D space. In this research we develop decentralized solutions to achieve greedy routing in 3D sensor networks. Our proposed approach is based on a unit tetrahedron cell (UTC) mesh structure. We propose a distributed algorithm to realize volumetric harmonic mapping of the UTC mesh under spherical boundary condition. It is a one-to-one map that yields virtual coordinates for each node in the network. Since a boundary has been mapped to a sphere, node-based greedy routing is always successful thereon. At the same time, we exploit the UTC mesh to develop a face-based greedy routing algorithm, and prove its success at internal nodes. To deliver a data packet to its destination, face-based and node-based greedy routing algorithms are employed alternately at internal and boundary UTCs, respectively. As far as we know, this is the first work that realizes truly deterministic greedy routing with constant-bounded storage and computation in 3D wireless sensor networks.

Segmentation decomposes a network with complex and irregular shape into a set of subnetworks, each under a simple boundary condition without bottlenecks. It has a wide spectrum of applications in routing, coverage, localization, backbone construction and maintenance, and in-network data centric storage and retrieval. To our best knowledge, this is the first work that tackles the segmentation problem in 3D wireless sensor networks. We propose a fully distributed 3D segmentation scheme with mere network connectivity information. Each node on boundary computes its injectivity radius, which reflects the narrowness of the corresponding boundary area and thus is employed to locate the undesired bottlenecks. A cluster of connected boundary nodes with similar smallest injectivity radii form a bottleneck segment. A recursive process is applied to identify a set of such bottlenecks, which together divide the network boundary into segments. An internal non-boundary node simply joins the nearest segment, thus completing the segmentation of the entire 3D sensor network. Our simulations show that the proposed algorithm works efficiently under various sensor network models with different boundary conditions and noise levels, always yielding appropriate segmentation results. We further demonstrate that segmentation can effectively promote the performance of a range of applications in 3D wireless sensor networks.

This research focuses on distributed and localized algorithms for precise boundary detection in 3D wireless networks. Our objectives are in two folds. First, we aim 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, we 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. To achieve the first objective, we propose a Unit Ball Fitting (UBF) algorithm that discovers a set of potential boundary nodes, followed by a refinement algorithm, named Isolated Fragment Filtering (IFF), which removes isolated nodes that are misinterpreted as boundary nodes by UBF. Based on the identified boundary nodes, we develop an algorithm that constructs a locally planarized triangular mesh surface for each 3D boundary. Our proposed scheme is localized, requiring information within one-hop neighborhood only. Our simulation results demonstrate that the proposed algorithms can effectively identify boundary nodes and surfaces, even under high measurement errors. As far as we know, this is the first work for discovering boundary nodes and constructing boundary surfaces in 3D wireless networks.

The code division multiple access (CDMA) technology has been recently introduced into mesh wireless networks for improving channel efficiency. The existing approaches, however, do not maximize the capacity of a CDMA system, because the sender transmits to one receiver only. In this paper, we explore novel approaches to allow multiple data frames be transmitted from a sender to multiple receivers simultaneously by using multi-user detection techniques and efficient power control schemes, thus maximizing network capacity and decreasing data delivery delay. More specifically, we propose two CDMA-based medium access control schemes, the PNO (Pseudo Noise Only) scheme and the PPO (PN Plus Orthogonal) scheme, for highly efficient data transmission in mesh wireless networks, especially for those networks serving as communication backbone and thus experiencing high traffic load. The performance of our proposed schemes is evaluated via simulations, and compared with IEEE 802.11 and other CDMA-based schemes under the same channel bandwidth. Our results show that PPO achieves the highest channel efficiency, because of its use of orthogonal codes for channelization. Both PPO and PNO can significantly improve network throughput and reduce packet delivery delay, without increasing signaling overhead noticeably.