# A Two-Stage Routing Protocol for Partitioned Underwater Wireless Sensor Networks
## 3 Methodology
### Rerouting  
Whenever a node's residual energy level reaches the minimum residual energy threshold, it transmits a notification to inform all its neighbors about itself quitting the forwarder/relay role. The notification also contains a list of neighbors of the quitting node. Upon reception of the notification, the neighboring nodes reorient their neighborhood tables by removing the quitting node from their neighborhood tables. The topmost node in the reoriented table (that represents the least hop count node with acceptable level of expected received power) is selected as the relay node. If more than one node have the minimum hop count to the UW-Sink, the node with maximum residual energy is selected as relay. However, there is possibility that:  
1. All the one hop neighbors have reached their minimum residual energy threshold. 2. There is no other one-hop neighbor in the list. Figure 7: Relay Selection. In the first case, any node X, whose predetermined next hop node is a quitting node, searches for a suitable next hop node in the one-hop neighbors of its neighbors. If a suitable next hop node is found in the neighborhood of a neighboring node Y, node X increases its range equal to its distance from node Y plus node Y's distance from the neighbor which is being considered as next hop. In the second case, i.e., when there is no other neighbor except the current next hop node (i.e., the quitting node), node X searches for a suitable next hop node in the one hop neighborhood of its current next hop node. However, if no appropriate next hop node is found even in the neighborhood of the neighboring nodes, the packet for this cycle is dropped. Our partition handling mechanism ensures that the node finds an appropriate next hop node in the next Cycle. Rerouting can be explained using Figure 8.  
Consider the scenario in Figure 8. In this figure, we assume that node one has two available routes (one through node 2 and the other through node 4) to send its data to the UW-Sink. However, node 2 offers the least hop count to the UW-Sink. Therefore, node 2 is selected as relay for node 1. Node 2 has only two nodes in its neighborhood, i.e., node 1 and node 3. Node 3 is relay for node 2 as it offers smaller hop count as compared to node 1. In order to understand loop creation, we assume that node 3 reaches residual energy threshold and therefore it denies relay service to node 2. In response, node 2 selects node 1 as its next hop as there is no other node in node 2's neighborhood table (node 4, 5 and 6 are out of node 2's current communication range). This will create a loop where node 1 and node 2 keep forwarding data to each other, thus, are not able to deliver data to the UW-Sink. Forwarding Loop Resolution  
If at any time a node X receive a data packet from another node Y where Y is the next hop node of node X, node X changes its next hop. For changing the next hop, node X removes node Y from its neighborhood table and selects the least hop count neighbor from the remaining nodes. For instance, in Figure 9, upon reception of an RTS packet from node 2 (which is node 1's next hop), node 1 removes node 2 from its neighborhood table and evaluates the remaining nodes in its table to select the  
Figure 8: Relay selection and rerouting. best forwarder, i.e., node 4. This will result in breaking the loop and avoiding connectivity loss due to loops. Why Residual Energy Threshold  
Connectivity holes are created because the nodes nearer to the UW-Sink have a higher volume of traffic going through them. This results in early drainage of their batteries thus disabling the nodes, which are sending data through them to reach the UW-Sink. According to [8], when the nodes near the UW-Sink have consumed all their initial energy deposit, the nodes farther down the stream have 93% of their energy deposit intact. Thus, if the connectivity holes are not resolved, even though the farther nodes have enough energy, it is not useful as the packets from such node may not be delivered. Moreover, the relay nodes are also sensor nodes.