# Self-Organized Fast Routing Protocol for Radial Underwater Networks
## 4 Routing Path Formation
### Phase 2: String Formation  
In this phase, the routing paths will be formed. The gateway allocates a string identification (ST_ID) to each neighbor node. The gateway neighbor nodes are called the first nodes in the strings, the next nodes below them are called second nodes, and so on (see Figure 2). The process will be completed layer by layer. That is, first of all, the first nodes in the strings will identify the second nodes in the strings, then the second nodes will identify the third nodes, and this process will continue until the end of each string. In each layer, the identification of the nodes will start from the side nodes and will continue inwards through the intermediate nodes. Step-by-step detail of the procedure is given below:  
1. First, Route Request (RR) packets are sent from the gateway to each of its neighbors (see 1 in Figure 5a) using mode4. The RR packet contains the IDs of all the neighbors and their respective string IDs. When a neighbor receives the RR packet for the first time it checks the list of node IDs to know its assigned string ID. 2. The neighbor nodes will send the RR acknowledgement (RR_ACK) using mode4 as well. 3. After that, first the side nodes in the string will forward the RR packet (see 3 in Figure 5a), now using mode3. The RR packet will be received by all adjacent nodes within range. These RR packets contain the node IDs with their corresponding string IDs and packet sequence number. Figure 4: (**a**) Transmission sequence of SGN, SHN, SHN_ACK, SGN_RSP and SGNRSP_ACK between the gateway and the neighbors, (**b**) The same transmission sequence is also shown in message sequence diagram. When a node receives the RR packet, it records the ID of the sender and its respective ST_ID. The gateway discards any RR packets it receives from its neighbors. The nodes that already have received the RR packet also discard the RR packet. 5. Only the node below in the string will reply with the RR_ACK packet, which will contain the sender ID and the ST_ID. They use mode3. 6. The node that receives the RR_ACK packet as a reply to a previous RR packet transmission records the node and the string IDs in its routing table. This way each node has complete information about the nodes above and below it in the string. 7. Now, the side nodes of the first layer send a Clear to Forward RR (CF_RR) packet (see 5 in Figure 5a) to their adjacent horizontal nodes (first nodes of the intermediate strings) using mode3. 8. The intermediate nodes send a CF_RR acknowledgement (CFRR_ACK) packet using mode3. 9. The process of sending RR and CF_RR will continue repetitively as described above until all the first layer nodes in all the strings have sent an RR packet to the second layer nodes. 10. When the last intermediate node in the first layer sends the CF_RR packet, it will not receive the CFRR_ACK reply because it is the last intermediate node. It will retransmit the CF_RR packet two more times and then it will decide to send a CFRR_BACK packet. 11. The CFRR_BACK packet will travel from this last intermediate node in the first layer to the side nodes in the second layer (see 9 in Figure 5a). CFRR_BACK and CFRRBACK_ACK packets will also be transmitted using mode3. 12. When the node of the second layer in the side string receives the CFRR_BACK packet, it starts the process of forwarding the RR packet to the third layer node. 13. Assuming that the number of nodes in all the strings is the same, the last nodes of the side strings will transmit the RR packet three times, but will not get any acknowledgement. Hence, they will conclude that they are the last nodes and will send the CF_RR packet to the intermediate nodes, with information that they are the last nodes. The intermediate nodes also transmit an RR packet, using mode3, and then send a CFRR_BACK packet to the side nodes informing that it is the last node of the string as well. At this stage, all the last nodes randomly select a time slot and send the RR_RSP response (see Figure 6). 14.