## 1 Introduction
It is proposed in [3] to construct hulls to partition a network into subspaces, limiting the recovery to search a subspace only. Separately, the random-walk algorithm is proposed in [6], where random walk is employed on a local spherical structure to escape from voids when a local minimum is reached. However, such attempts for randomized recovery of local minimums are non-deterministic and often lead to high overhead or long delay. Among all routing algorithms discussed in the literature for 3D sensor networks, random-walk [6] is the sole truly greedy routing scheme with constant-bounded storage and computation complexity. Figure 1: Illustration of the proposed greedy routing protocol. (**a**) A 3D sensor network that has irregular outer and inner boundaries and consists of about \(2,000\) nodes. This is one of the network models used in our simulation (see Figures 6 and 8 for other network models). The nodes on the inner boundary are highlighted in red. (**b**) The nodes that are local minimums under node-based greedy routing are highlighted as blue squares and red triangles, for boundary nodes and internal nodes, respectively. (**c**) The established unit tetrahedron cells (UTCs). (**d**) The result after volumetric harmonic mapping, with both outer and inner boundaries mapped to spheres. (**e**) A greedy routing path shown in virtual coordinates created by volumetric harmonic mapping. (**f**) The greedy routing path shown in the original network. **Figure 2.** Comparison of face routing in 2D and 3D networks. Node \(S\) has a shorter distance to destination, \(D\), than all of its neighbors and, thus, is a local minimum. (**a**) Face routing is successful in a 2D planar network, because a concave void is a face with a simple line boundary and, thus, a local deterministic algorithm can be employed to search the boundary in either the clockwise or counter-clockwise direction, as shown by the blue and red lines. (**b**) In a 3D network, a void is no longer a face. Its boundary becomes a surface, yielding an arbitrarily large number of possible paths to be explored (as indicated by the arrows). Thus, face routing fails. Our proposed solution 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 a 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 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  
Figure 3: The storage load distribution in GDSTR-3D, where the storage load of a node is measured by the number of entries in its local convex hull table. Figure 2: Comparison of face routing in 2D and 3D networks. Node \(S\) has a shorter distance to destination, \(D\), than all of its neighbors and, thus, is a local minimum. (**a**) Face routing is successful in a 2D planar network, because a concave void is a face with a simple line boundary and, thus, a local deterministic algorithm can be employed to search the boundary in either the clockwise or counter-clockwise direction, as shown by the blue and red lines. (**b**) In a 3D network, a void is no longer a face. Its boundary becomes a surface, yielding an arbitrarily large number of possible paths to be explored (as indicated by the arrows). Thus, face routing fails. _VHM_ to support global end-to-end routing. As far as we know, this is the first work that realizes truly deterministic routing with constant-bounded storage and computation in general 3D sensor networks.