# A Network Coding Based Hybrid ARQ Protocol for Underwater Acoustic Sensor Networks
## 4 Protocol Design
### Window Size Estimation
#### 4.2.2 Retransmission Window Size Estimation  
In fact, we cannot always guarantee a 100% success ratio for data recovery at one block sending round. Although we could increase the overhead to raise the data transfer reliability, it is not practical for battery-powered underwater facilities. Thus, automatic repeat request (ARQ) is a promising technique to achieve high data transfer reliability in underwater scenes. In traditional fountain code  
\begin{table}
\begin{tabular}{p{340.0 pt}} \hline \hline
**Sender** \\ (1) Updates the sending window size \(K_{i}^{\prime}\) for node \(i\), encodes the recovered data packets in a block into \(N\) encoded packets, and sends out \(K_{i}^{\prime}\) encoded packets at one time; \\ (2) Sets a timer and waits for the ACK/NACK feedback. If an ACK is received, then it goes to (1), else goes to (3); \\ (3) Estimates the retransmission window size \(m\) with the information from NACK and sends \(m\) selected encoded packets. Then, it goes back to (2). \\ \hline
**Receiver** \\ (1) Decodes the received packets from all upstream nodes until no more packets are received from its adjacent upstream node; \\ (2) Sends an ACK packet back and goes to (3) if the original data in the block can be reconstructed successfully or sends a NACK packet and goes back to (1) if else. The information (lost packets number and index) in an ACK or NACK packet is detailed in Section 4.2; \\ (3) Encodes the recovered data packets again and transmits them to the next hop. \\ \hline \hline \end{tabular}
\end{table}
Table 1: The operations in the sender and receiver.  
based hybrid ARQ protocols, such as SDRT [13] and FOCAR [15], retransmitted packets are randomly selected from the encoded packets in a block. This scheme is very inefficient because the retransmitted packets may have already been recovered with the previous transmitted packets and the sender has to wait for the NACK packet again and transmit more packets until some useful encoded packets are received successfully. It is particularly obvious when the output degree is low in the design of fountain code. Thus, we need an efficient scheme to ensure precise retransmission. In this paper, we propose a practical algorithm to estimate the retransmission window size. We divide the retransmission process into two situations. When \(N_{r,i+1}\left(k\right)<K\), it means the receiver does not obtain a big enough number of encoded packets and the corresponding sender needs to send more encoded packets. The number of retransmitted packets \(N_{s,i}(k)\) is obtained by Equation (12):  
\[N_{s,i}(k)=\lceil\frac{1}{1-p_{i}(k)}\left(K-N_{r,i+1}\left(k\right)\right)\rceil \tag{12}\]  
where \(p_{i}(k)\) is the packet error rate in the \(i\)th hop when sending the \(k\)th block and an estimation of \(p_{i}(k)\) can be calculated as follows:  
\[p_{i}(k)=1-\frac{\alpha K}{K_{i}^{\prime}\left(k\right)} \tag{13}\]  
However, when \(N_{r,i+1}\left(k\right)\geq n\), it means the receiver has obtained enough number of encoded packets, but some of the packets may be reduplicative to some extent. Thus, we need to send a packet which is not recovered by the receiver yet, and this can be done by sending back the index number of the lost data packet with a NACK packet. We should note that the data packets are also part of the encoded packets in the design of fountain code. Thus, the retransmission process is summarized as follows: the sender reads the information of the NACK packet and sends \(m=\max\left(N_{s,i}(k),1\right)\) packets to its corresponding downstream node. The retransmitted packets contain a lost data packet informed by the receiver.