## 5 Routing in 3D Sensor Network with Internal Holes
### 3D Sensor Networks with Multiple Internal Holes
#### 5.2.2 Tunnel Routing  
The CCELLs constructed by network segmentation capture the approximated geometric shape of a 3D sensor network. A graph can make a compact representation of CCELLs available, where vertices represent CCELLs and an edge connects two vertices if the corresponding CCELLs are adjacent. Here, we say one CCELL is adjacent to the other, if at least one of its nodes has a neighbor belonging to the other CCELL. Let \(T_{ij}\) indicate a _tunnel_ from CCELL \(i\) to CCELL \(j\), which is described by a point, \(t_{ij}\), and a radius, \(r_{ij}\), on the mapped spherical outer surface of CCELL \(i\), where \(t_{ij}\) is the \"center\" of intersection nodes (between CCELLs \(i\) and \(j\)), and \(r_{ij}\) is the maximum radius of the circle centered at \(t_{ij}\) containing only intersection nodes on the spherical surface of CCELL \(i\) (see Figure 9, for example). The information of \(T_{ij}\) is broadcast to all the nodes within CCELL \(i\). The message includes the tunnel description, \(t_{ij}\), \(r_{ij}\), and its adjacent CCELLs ID, \(j\). Therefore, every node in the network can construct a global graph and, accordingly, establish a global routing table, which is very compact, with its size only proportional to the number of interior holes. Figure 8: Illustration of the proposed greedy routing protocol for a network with multiple internal holes, Models 7 and 8 used in our simulations. (**a**,**e**) 3D sensor networks that have irregular outer and inner boundaries and have multiple internal holes. The nodes on the inner boundary are highlighted in purple. (**b**,**f**) After the segmentation, the networks are decomposed into cluster cells (CCELLs), each containing one hole only. The intersection nodes are highlighted in green and red. Additionally, we separate the CCELLs further apart for a clearer view. (**c**,**g**) The result after volumetric harmonic mapping, with both outer and inner boundaries mapped to spheres for each CCELL. The intersection nodes are in green and red, and here, we partially “align” the CCELLs to get a better view, but actually, the virtual coordinates of these CCELLs are independent of each other. (**d**,**h**) An example of the greedy routing path according to our proposed scheme is shown in the original network domain. If the source and destination are inside the same CCELL, routing in a CCELL (see Section 5.1) is applied. Otherwise, the source checks its global routing table to find the next hop CCELL and the _tunnel_ to that CCELL. Then, the source randomly pick a target point, \(p_{i}\), on the spherical surface within the tunneland route toward \(p_{i}\). The algorithm of routing in a CCELL is employed to deliver the packet toward \(p_{i}\). Note that the packet is not necessary to actually reach \(p_{i}\). Since adjacent CCELLs share a good amount of intersection nodes, the packet can directly route to the next CCELL without passing through \(p_{i}\), as long as it meets an intersection node on the shared boundary. Thus, the traffic across CCELLs can be nicely distributed among the intersection node on the shared boundary between CCELLs. This has also been verified by our extensive simulations; see Section 6. The procedure repeats, until the packet enters the destination CCELL, where it can be delivered, as we have discussed in Section 5.1. Figure 8d visualizes the view of a global routing path where source \(S\) and destination \(D\) are located in different CCELLs. In addition, Figure 8d,h gives examples of end-to-end paths in a 3D network with two and three internal holes, respectively. In summary, the proposed tunnel routing algorithm is a combination of greedy routing, face routing and conventional table-based routing with guaranteed delivery, reasonable path stretch and desired scalability. It decomposes a 3D sensor network with multiple holes into a set of CCELLs and maintains a small global routing table with a bounded size to route packets across CCELLs. The data delivery inside one CCELL is realized by greedy routing and face routing.