# A Novel Cross-Layer Routing Protocol Based on Network Coding for Underwater Sensor Networks
## 4 Design of Network Coding Routing Protocol
### Initial Routing Construction  
In this part, we will discuss issues about how to find a reliable route to forward data from the source node to the destination node. There are two steps in initial routing construction: The first is to find a primary path which has the minimal hops and shortest distance to the destination. We call nodes in this path the _primary nodes_. However, nodes in the primary path might have relative long distance between each other, thus the channel condition is poor and the links might have high PER. In order to solve the above problem, we add some _secondary nodes_ into the primary path at the second step. These secondary nodes are distributed between every two primary nodes and are responsible for sending supplemental packets so that the receiver can obtain enough packets for successful decoding. The initialization process is shown in Algorithm 1. ```
1:procedureInitialize(Node)
2:ifNode\(\in\)DestinationSetthen
3:\(Dm(Node)\gets 0\);
4:else
5:\(Dm(Node)\leftarrow\infty\);
6:endif
7:\(Dn(Node)\leftarrow\infty\);
8:\(nId(Node)\gets null\);
9:\(rId(Node)\gets null\);
10:\(Dth\leftarrow\infty\);
11:endprocedure
```  
**Algorithm 1** Routing Initialization  
The parameters that each node stores are: \(Dm\) (the path distance between current node and the destination node after multi-hop transmission), \(Dn\) (the distance between current node and its next-hop primary node), \(nId\) (the next-hop node Id in the primary path), \(nPos\) (the 3D geographical position of next-hop primary node), \(rId\) (the next-hop Id of secondary node), \(Dth\) (the sum of distance between next-hop secondary node and its two neighborhood primary nodes). At the beginning of routing protocol, \(Dm=0\) for the destination node and \(Dm=\infty\) for others. Other parameters are set as in line 7\(\sim\)10. Algorithm 2 is the process of sending and receiving beacon message. Each beacon transmitted message contains three parameters: \(Dm\) (the length of primary path), \(Pos\) (the geographic position of sending node) and \(Id\) (the unique Id of current node). When detecting changes in the primary path, a random time slot timer is set before broadcasting the changed beacon messages (line 1\(\sim\)8). Suppose node \(m\) receives beacon messages from node \(r\) and node \(n\) is the next hop primary node of node \(m\). After receiving beacon messages from node \(r\), node \(m\) calculate \(DistanceMR\) and \(DistanceRN\), which are the distance between node \(r\) and \(m\) and distance between node \(r\) and \(n\), respectively (line 11\(\sim\)12). Then node \(m\) checks the overall path length towards the destination node. If the path length becomes shorter, node \(r\) can be chosen as a new next hop primary node and node \(m\) updates its beacon messages and sets a timer to broadcast the changes. If not, we consider whether node \(r\) can be chosen as a secondary node between node \(m\) and node \(n\) or not. Here we choose the node with the minimal \(DistanceMR+DistanceRN\) value. This can ensure that the secondary node is close to the line between node \(n\) and \(m\). Moreover, we require that \(DistanceMR\) and \(DistanceRN\) are both smaller than the distance between node \(m\) and node \(n\) (line 21\(\sim\)23). This requirement can ensure that the secondary node can receive enough packets for decoding. When node \(n\) cannot decode successfully, the secondary node \(r\) will send extra encoded packets to node \(n\) under better channel condition. The beacon messages are sent by the destination node at the beginning. After multi-hop transmission, all the reachable node can find a path to the destination node and the nodes near this path are included into secondary node sets. It is worthy to be mentioned that the beacon messages in NCRP do not need to be sent frequently as most receiver-side routing protocols do, although the nodes in underwater environment move quickly and the channel might change accordingly.