## 3 Routing at Internal UTCs: Face-Based Greedy Routing  
As discussed in Section 1 and demonstrated in Figure 1b, the node-based greedy routing scheme ensures success at neither boundary nor internal nodes in a 3D wireless sensor network. We focus on the latter in this section. We first show that node-based greedy routing is not always successful even under the UTC structure, for example, in a case as simple as across two neighboring UTCs. More specifically, let us consider two UTCs, \(UTC(A,B,C,D)\) and \(UTC(B,C,D,E)\), which share \(Face(B,C,D)\). If they are DUTCs, as illustrated in Figure 4a, Nodes \(A\) and \(E\) are greedily reachable to each other. However, building DUTCs is expensive and often impractical in sensor networks. The UTCs constructed by the algorithm introduced in Section 2 are not necessarily DUTCs. For a UTC shown in Figure 4b, for example, \(l_{EA}\) can be shorter than \(l_{BA}\), \(l_{CA}\) and \(l_{DA}\) (where \(l_{ij}\) denotes the distance between Nodes \(i\) and \(j\)), thus resulting in a failure in node-based greedy routing from \(E\) to \(A\). Obviously, the UTC mesh is a special structure of a 3D sensor network. Since the node-based greedy routing is not always successful under UTCs, it offers no guarantee of data delivery in a general 3D sensor network either. To this end, we propose a face-based greedy routing algorithm. Let us consider a data packet that is to be delivered from Source \(S\) to Destination \(D\). Similar to conventional node-based greedy routing algorithms, we assume the data packet contains the IDs and coordinates of \(S\) and \(D\). Note that the coordinates are not necessarily based on GPS. Instead, they can be virtual coordinates, e.g., produced by our proposed volumetric harmonic mapping algorithm, to be discussed later in Section 4. Node \(S\) first computes a line segment between \(S\) and \(D\), which is denoted by \(\Gamma\). Clearly, \(\Gamma\) passes through a set of UTCs between \(S\) and \(D\) and intersects with a sequence of faces, denoted by \(\Phi=\{Face(A_{i},B_{i},C_{i})|1\leq i\leq k\}\), where \(k\) is the total number of such faces (see Figure 5). The distance from \(Face(A_{i},B_{i},C_{i})\) to destination \(D\) is defined as the distance between \(D\) and the intersection point of \(\Gamma\) and \(Face(A_{i},B_{i},C_{i})\). To be proven in Lemma 1, \(Face(A_{i},B_{i},C_{i})\) and \(Face(A_{i+1},B_{i+1},C_{i+1})\) must be neighboring faces and, thus, share an edge. Let us denote the shared edge as \(\tau_{i}\). Under the proposed face-based greedy routing algorithm, data packets are forwarded from \(Face(A_{1},B_{1},C_{1})\) to \(Face\)\((A_{k},B_{k},C_{k})\). Each intermediate node only needs to calculate the next face in \(\Phi\). For example, Node \(S\) can easily determine \(Face(A_{1},B_{1},C_{1})\), because the latter must be one of the faces in the UTCs that contain the former. Therefore, Node \(S\) can check which of them intersects with \(\Gamma\)  
Figure 5: A packet is routed through a sequence of faces under face-based greedy routing. with a computation time bounded by a small constant. \(Face(A_{2},B_{2},C_{2})\) is determined similarly. Thus, the packet is routed from \(S\) to one of the end nodes of edge \(\tau_{1}\), _i.e._, the edge shared by \(Face(A_{1},B_{1},C_{1})\) and \(Face(A_{2},B_{2},C_{2})\). The above process repeats at each intermediate node, until the packet arrives at \(Face(A_{k},B_{k},C_{k})\) that contains destination \(D\), or it fails to find the next face in \(\Phi\) based on locally available information. Next, we prove that the proposed face-based greedy routing algorithm is always successful at internal nodes. **Lemma 1**. : _The face-based greedy routing does not fail at a non-boundary UTC._  
Proof. : \(\Gamma\) intersects with a sequence of faces, _i.e._, \(\Phi\).