# 3D Void Handling Geographic P2P-RPL for Indoor Multi-Hop IR-UWB Networks
## 2 Related Works
### Greedy Forwarding and Void Handling Point-to-Point RPL in 3D Indoor Environments  
In this subsection, we propose a reactive geographic routing protocol called GVA-P2P-RPL for 3D environments, which improves the P2P-RPL [1] standard by forwarding P2P-DIO messages in a greedy manner when it is possible to reduce the routing overheads. To greedily choose the next hop, the location information acquired from the previous multi-hop positioning system is utilized. When expanding the network simulation environments from 2D to 3D, greedy forwarding techniques generally encounter local minimum or void (routing hole) situations more often in which a packet cannot be forwarded to the next closer hop to the destination. The internode connectivity is weakened as the network topology is transformed from 2D to 3D [7]. Figure 4 illustrates that the void problem occurs more often when the network dimensionality is expanded from 2D to 3D. Coverage and connectivity adversities in 3D networks are further addressed and explained in [4]. To overcome the local minimum problem, GVA-P2P-RPL simply switches back to the standard P2P-RPL's flooding strategy until a neighbor node closer to the destination is discovered. When recovered from the local minimum, GVA-P2P-RPL again greedily forwards P2P-DIO messages. Adaptive trickle timer (ATT) in 3D GVA-P2P-RPL is also newly presented to reduce the route discovery time and avoid collisions of P2P-DIO messages. Since GVA-P2P-RPL has only a few nodes participating in the route discovery process, contention among nodes is alleviated and redundant message suppression is less necessary. Therefore, it is reasonable to use a smaller minimum trickle timer interval \(I_{min}\) parameter value than the standard trickle algorithm. As closer nodes to the destination are more probable of constructing the shortest path by intuition, ATT gives higher transmission priority to those nodes by shortening their listen-only periods. The shortened listen-only periods also provide better collision avoidance because the range of randomly selected transmission time becomes wider [20]. The general forwarding scheme of GVA-P2P-RPL is depicted in Figure 5. At first, a node that has a P2P-DIO message to forward creates a neighbor node list that does not contain any neighbor existing in the previously discovered routes to avoid the loop. Then, it sets the next hop address as the closest neighbor node's unicast address to the destination when such a neighbor node exists as the solid arrows in Figure 5b,d,f. If not, the forwarding node sets the next hop address as the broadcast address to recover from the local minimum as the solid dashed arrows in Figure 5c,e. By repeating this process from the source node to the destination node, reliable route discovery is completed and several different routes may be found. The destination node records all the discovered routes and chooses the best route among them according to the RPL objective function set in the initial DODAG configuration as the solid arrow route in Figure 5g. The best route is piggybacked in the P2P-DRO (P2P discovery reply object) [1] message and sent backwards to the source. Upon receiving the P2P-DRO message, the source sends data packets along the discovered route. Detailed next-hop selection and packet forwarding algorithms of GVA-P2P-RPL are shown in Algorithm 1. In implementation, we modified the route discovery option (RDO) [1] field, a RPL control message option defined for P2P-DIO messages, by piggybacking the target's location information to enable the greedy forwarding operation. Figure 4: Void problem in 3D. As the dimension expands from 2D to 3D, internode connectivity weakens and the void problem appears more often. ```
//\(s\) = source node, \(d\) = destination node, \(c\) = current node. // Algorithm starts when \(s\) needs to discover route to \(d\). begin \(c\longleftarrow s\) while\(c\
eq d\)do  Define \(N(c)\) as the set of one-hop neighbors of \(c\). Define \(R(c)\) as the set of all nodes participating in discovered routes from \(s\) to \(c\).