# A Novel Cross-Layer Routing Protocol Based on Network Coding for Underwater Sensor Networks
## 3 Background
### Overview of NCHARQ  
NCHARQ is a transport protocol which combines network coding and hybrid ARQ techniques [16]. Traditional transfer control protocol (TCP) cannot adapt to underwater environment as TCP requires short round-trip time (RTT) and long RTT is one of the adverse characteristics in underwater environment. The key idea of NCHARQ is to group original data packets into several encoded blocks and data are sent block by block. This improvement can significantly reduce redundant feedback messages. Meanwhile, the transmission power is optimized by controlling the window size of sending block. The flow chart of NCHARQ is given in Figure 2. At the beginning of the sending procedure, the sending node \(S_{n}\) sends a block of encoded data packets continuously by multi-casting. The number of packets in one sending block is \(W_{i}\) for the \(i\)th sending procedure. Each encoded packet \(m\) contains the following information: the unique ID of current sending block \(B_{m}\), the coding vector \(C_{m}\), the unique ID of next hop node \(Node_{m}\) and the remaining number of unsent packets \(N_{rm}\). \(S_{n}\) will wait for feedbacks if all the packets in current block are sent. The neighborhood nodes of node \(S_{n}\) receive the encoded packets and try to decode with packets in the same block. When a receiver detects \(N_{rm}=0\), it will send back the number of unrecovered packets \(N_{fail}\) (Negative acknowledgement, NACK) or the number of redundant packets \(N_{rd}\) (Acknowledgement, ACK) according to the decoding result. The sending node \(S_{n}\) begins to update the sending block window \(W_{i}\) by Equation (9) if it receives the ACK/NACK information. \[ \begin{split}& W_{i+1}=W_{i}+k_{1}A_{i}+k_{2}\delta_{i}\\ &\text{and}\ \ A_{i}=\sum\limits_{j=0}^{i}\delta_{i}\\ &\delta_{i}=\left\{\begin{array}{ll}-N_{rd},&\quad if\ decode\ successfully\\ N_{fail},&\quad else\end{array}\right.\end{split}  \tag{9}\]  
Figure 2: (**a**) The sending procedure for NCHARQ: (**b**) The receiving procedure for NCHARQ. Here, \(W_{i+1}\) is the updated window size. \(A_{i}\) is the accumulated error which reflects the slow change trend of underwater channel and \(\delta_{i}\) reflects the instant channel changes. \(k_{1},k_{2}\) are impact factors of long time and instant channel changes, respectively. The value of \(k_{1},k_{2}\) is determined by the channel change speed and the requirement for loop filter convergence speed. We will give the parameter analysis and numerical simulations in Section 5. Considering that the packet loss is a random event and the packet loss rate of one data send-and-receive procedure cannot reflect the channel quality accurately, we use Equation (9) which is based on loop filter to update the window size \(W_{i}\) and thus the effect of packet loss rate estimation fluctuation is reduced. Meanwhile, the window size can converge into a stable state quickly and thus the sending efficiency is improved. Here we will use \(W_{i}\) as an important parameter for routing maintenance and this will be further discussed in Section 4. After updating window size, nodes determine to resend data packets or start a new send-and-receive round according to the received feedbacks. If NACKs are received, the unique IDs of unrecovered data packets are extracted from NACK packets and the corresponding data packets are retransmitted. If ACKs are received, nodes can start to send a new block. NCHARQ can adjust the number of sending packets according to the channel quality and thus optimize the transmission power and reduce the energy consumption. As feedbacks and network coding techniques are included in transmission procedure, NCHARQ can control the packet delivery ratio more efficiently compared with pure forward error correction (FEC) technique. Moreover, the feedback procedure is operated after all the packets in one block are transmitted and this scheme can greatly reduce transmission delay which is brought by long RTT.