# Self-Organized Fast Routing Protocol for Radial Underwater Networks
## 4 Routing Path Formation
### Phase 1: Search for Gateway Neighbors  
As we mentioned earlier, in Section 3, the gateway is the controlling node of the network and it can only communicate with its neighbor nodes, which are at one hop distance. The gateway is responsible for starting the process of forming the strings. Since, initially, the gateway does not know about its neighbor nodes, it finds them first. This phase follows these steps:  
1. Initially, all the nodes transmit a beacon packet, using mode1, at random time slots to inform of their presence. Other than the gateway, all other nodes ignore the packet.
2. When the gateway receives a beacon packet from any of its neighbor nodes it will wait for a WP. This avoids a possible collision between the SGN packet (see next step) and a beacon packet from another node.
3. The gateway broadcasts the first Search Gateway Neighbor (SGN) packet to find its neighbors (see 1 in Figure 3(a)). Altogether, the gateway sends the SGN packet using mode2 (three consecutive transmissions) (Figure 3(b)). The SGN packets carry a sequence number.
4. The nodes that receive the first SGN packet wait to receive two more SGN packets before they start finding horizontal neighbor nodes. Suppose that a node fails to receive the first two SGN packets but receives the third SGN packet. This node does not wait for two more SGN packets because it knows from the sequence number that this is the third SGN packet.
5. After receiving the SGN packet(s), each neighbor broadcasts a Search Horizontal Neighbors (SHN) packet to find its horizontal neighbors (see 2 in Figure 3(a)) using mode3. Each node selects a random timeslot for transmission.
6. The nodes that received a SGN packet earlier, send an SHN acknowledgment (SHN_ACK) packet. (see 3 in Figure 3(a)). The SHN_ACK packets are transmitted using mode3 after all the neighbor nodes have finished sending their SHN packets. The nodes in the lower layer receive the SHN packets as well but they ignore them because they did not previously receive the SGN packet from the gateway.
7. When the waiting time for SHN_ACK packets finishes, each neighbor node sends an SGN response (SGN_RSP) packet to the gateway (see 4 in Figure 3(a)), using mode3. The SGN_RSP packet includes information on the neighbors of the sender. When all responses are received, the gateway will know its neighbors and can determine their relative positions by the horizontal neighbor information of each node.
* The gateway sends back an SGN_RSP acknowledgement (SGNRSP_ACK) packet at a random time, using mode3 as well.
* To form a string, the gateway assigns a unique string identification (ST_ID) number to each neighbor. The nodes below each gateway neighbor will be part of that straight hop-by-hop forwarding path.  
We can explain mode3 in more detail with the help of the SHN and SHN_ACK packets. If the SHN_ACK packet is not received by a node, it will retransmit the SHN request. If the SHN_ACK packet is still not received, then the sender will transmit the SHN packet a third and last time. The next step, transmission of the SGN_RSP packets from the neighbors, will start after six WPs, which is the time required for a sequence of three iterations of SHN and SHN_ACK packets. However, during this period the SHN packet will be retransmitted only if the SHN_ACK packet is not received.