## 5 Routing in 3D Sensor Network with Internal Holes
### 3D Sensor Networks with Multiple Internal Holes
#### 5.2.1 Network Segmentation and Mapping  
The first step is to segment a 3D sensor network with multiple inner holes into a set of clusters, each containing one hole only. We first give the definition of network segmentation and then introduce an algorithm to realize it.  
**Definition 13**.: _Cluster cell (CCELL): Consider a 3D sensor network with \(m\) interior holes. Let \(\{B_{i}|1\leq i\leq m\}\) denote the boundaries of the holes. The sensor network is decomposed into a set of sub-networks, or CCELLs, \(\{C_{i}|1\leq i\leq m\}\), as follows: \(C_{i}=\{q|\ |B_{i}q|\leq|B_{j}q|,\forall j\
eq i\}\), where \(|B_{i}q|\) is the shortest hop distance from a node, \(q\), to \(B_{i}\). Since the entire network is bounded, each CCELL is bounded, too. Therefore, the outer boundary of a CCELL forms a closed surface, denoted as \(\Lambda_{i}\)._  
To construct CCELLs, the exterior and interior boundaries of a sensor network can be extracted by identifying the boundary UTCs in a UTC mesh (see Section 2. An example of boundaries are illustrated in the first row of Figures 6 and 8,e, where the boundary nodes are highlighted in colors.  
Based on Definition 13, CCELLs of a 3D sensor network can be established by an algorithm outlined below. Let \(B_{0}\) denote the outer boundary and \(\{B_{i}|1\leq i\leq m\}\) the inner boundaries. Each inner boundary node initiates a flooding message that includes its boundary ID and a hop counter that records the number of hops the message has traveled. A non-inner-boundary node learns its hop distance to nearby holes according to the received flooding messages. It always keeps the shortest distance and the corresponding boundary ID.  
Figure 7: Failure of end-to-end greedy routing after global alignment of two spheres of mapped CCELLs. The packet from \(S\) to \(D\) will be stuck at \(L_{min}\), which is closest to \(D\) in CCELL 1.  
When flooding stops, a node checks the shortest distance(s) and the corresponding boundary ID(s) it has learned. If a non-inner-boundary node has equal shortest hop distance to at least two inner boundaries, \(B_{i}\) and \(B_{j}\), the node is marked by selecting the one with the smaller ID, indicating that it belongs to corresponding CCELLs, _i.e._, \(\Lambda_{i}\) if \(i<j\), which is also called the intersection node. In the discrete case, the hop distances of a node to two inner boundaries are considered equal if they have the same hop counts or differ by one.  
It is worth mentioning that under an extreme (artificial) condition, a CCELL established by the method introduced above may have more than one separate boundary (see [38] for a similar discussion on generalized Voronoi cells), where each boundary is still a closed surface. In such a case, an arbitrary boundary is chosen as CCELL.  
Now, the 3D sensor network has been segmented into a set of CCELLs, and each CCELL is bounded by corresponding closed surface \(\Lambda_{i}\) (see Figure 8b,f for example). For each CCELL, the same mapping algorithm discussed in Section 5.1 can be applied to build a local virtual coordinate system (see Figure 8c,g). Note here that the virtual coordinates of each CCELL are independent and not aligned with each other. Moreover, the intersection nodes will have at least one neighbor located in different CCELLs. Routing inside each CCELL is naturally supported, as we discussed in the network with one hole scenario. In the next part, we will propose a routing scheme, dubbed tunnel routing, to coordinate these local coordinates to support global routing across CCELLs.