| Firstly, I have proposed a routing scheme for 3D wireless networks, which is based on Harmonic Volumetric Embedding (HVE). More specifically, my proposed solution is based on a unit tetrahedron cell (UTC) mesh structure. 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 route a data packet to its destination, face-based and node-based greedy routing algorithms are employed alternately at internal and boundary UTCs, respectively. For networks with multiple internal holes, a segmentation and tunnel-based routing strategy is proposed on top of VHM to support global end-to-end routing.;Secondly, I have proposed a Bubble Routing scheme, which does not require the global coordinates of sensors (such as GPS). The sensor distribution can be either uniform or non-uniform. The sensor deployment may be constrained by obstacles and terrain variations, thus resulting in complex network shapes with multiple interior holes and concave exterior boundary. The key contribution of our proposed scheme is to preprocess the global information via a distributed algorithm, such that a sensor only needs to store a minimum amount of information to make correct and efficient local routing decisions, thus achieving scalable routing with guaranteed delivery.;Finally, I consider a sensor network deployed in a 3D space with one or multiple internal holes, where sensors cannot be deployed. I show that there exists a DISCO algorithm to support routing between any pair of points in a strong-connected 3D network. I propose a distributed and deterministic algorithm with constant storage, communication and computation overhead, dubbed trace-routing, to escape from local minima. Trace-routing is triggered when a packet reaches a local minimum. The trace is a closed loop that can be computed locally with constant overhead. The packet is routed along such a trace, thus deterministically moving out of the local minimum. |
