# Void Avoidance Opportunistic Routing Protocol for Underwater Wireless Sensor Networks
## 3 EEDOR Void Avoidance with Hop Count Discovery Mechanism
### Description of the Proposed EEDOR-VA Protocol
#### 3.3.1 Hop Count Discovery Phase  
Hop count discovery is used to help any sensor node in the network to discover its hop count to sinks in the network, whether directly reachable within the transmission range or reachable via one or more hops through relay nodes. The general objective behind the hop count discovery phase is to obtain the hop count of all connected nodes in the network. The hop count discovery phase consists of two procedures and assigns a hop count to the sensor nodes. Appendix A presents Algorithm A1, which illustrates both procedures of the hop count discovery. First, in the hop-count request procedure (lines 1-15), a source node generates the HCREQ consisting of a sequence number and the source's ID and broadcasts it to its neighbors. Each neighbor node receives the HCREQ, updates its neighboring table with source ID (line 6) and maintains the request sequence number. If the request with this sequence number is received for the first time (line 7), then the neighbor node replaces the source's ID with its ID in the HCREQ and rebroadcasts it to its neighbors (lines 8-9). Otherwise, the node just ignores the HCREQ (line 11). This procedure (lines 3-15) is repeated until the HCREQ reaches the destination (one of the sinks). Once a sink receives an HCREQ message, it will start a hop-count reply procedure that finds each receiving node's hop count to the nearest sink. The sink hop count is initialized as 0 (line 16). The sink generates an HCREP consisting of sink's ID, sink's depth, sink's hop count and the sequence number and broadcasts the reply (lines 17-19). When a node receives the HCREP and has previously received an HCREQ with this sequence number, the node then obtains the HCREP sender hop count from the reply message and compares it with its hop count (lines 21-23). If the node's hop count is greater than hop count in the HCREP + 1, then this node will update its hop count by increasing the hop count in the received HCREP by 1 and assign it as its own hop count (line 24). After updating the HCREP receiver information, if this node is not the source node then the node updates the HCREP with its own ID, depth and hop count, and then rebroadcasts it to its neighbors (lines 25-27). If it is the source, the node then prepares for the next phase and will not rebroadcast the HCREP (lines 28-30). A sensor node will also ignore the HCREP if its hop count is less than or equal to the hop count attached to the HCREP (lines 31-33). The hop-count reply procedure (lines 20-35) is repeated until all nodes that have previously received the HCREQ receive the HCREP and rebroadcast it. The HCREP will eventually reach the source node. The following example in Figure 4 illustrates the hop count discovery phase of EEDOR-VA. In each round of our protocol, the nodes start collecting data from the surrounding environment. Whenever a node (n1) has a packet to transmit, the node will start hop count discovery to reach at least one of the sinks on the surface (s1). The current source (n1) broadcasts an HCREQ consisting of its ID (i.e., n1) and a sequence number to its one-hop neighbors (n2, n3, n4 and n10). Each neighbor node (n2, n3, n4) receives the HCREQ message, replaces its ID in the request and rebroadcasts it to its neighbors to continue the hop count discovery algorithm until sink (s1) receives the HCREQ message. The solid arrows in Figure 4a represent the HCREQ path. Upon receiving the HCREQ, sink (s1) generates an HCREP (i.e., HCREP contains HCREP sender's (ID, depth, hop count) and a sequence number) and broadcasts it to its neighbors (n8, n9). Node n8 ignores the reply message since it did not receive any HCREQ, while n9 updates its hop count and stores its information into the HCREP (i.e., nodes store their ID, depth and hop count) in addition to the sequence number. This is shown in Figure 4b as a combination next to each node. In this step, for example, node n9 has its ID n9 and it is at depth d9 with hop count 1; it will store (n9, d9, 1) and rebroadcast the reply to its neighbors.