# A Network Coding Based Hybrid ARQ Protocol for Underwater Acoustic Sensor Networks
## 3 Network Coding Design
### A Practical Network Coding Based on Fountain Code  
Fountain code is a class of erasure code and used for recovering lost packets in the erasure channel. The representative fountain codes are Luby transform (LT) codes [28] and Raptor codes by [PERSON] et al. [29]. The basic idea of fountain codes can be described as follows : the sender divides the source file into \(K\) packets and encodes these packets into \(N\) packets (\(N\gg K\)), anyone who wishes to receive the source data file collects the encoded packets until the number of received packets is a little larger than \(K\), then the receiver can recover the original file with these packets. The advantage of fountain code scheme in a multicast system is that any node in the network can recover the original data packets with enough coded packets and the decoding process could be done in a linear time with high successful probability [28]. In addition, if each node encodes the data packets independently and randomly, the receiver can recover the original data packets with encoded packets from different sending nodes. In this way, the fountain code shares the same properties with network coding and can be treated as a particular class of network coding. A typical encoding process of LT codes is illustrated in Figure 2. There are 5 original data packets and 10 encoded packets in the Tanner graph. Each output encoded packet is the XOR of randomly selecting data packets. The number of original packets participating in an encoded packet relies on the design of output degree distribution \(\rho\left(d\right)\). The decoding process of such codes can be performed in a simple way by belief propagation (BP) algorithm [30] as follows:1. Find a coded packet \(c_{k}\) that is connected only to one data packet \(d_{j}\) and then \(d_{j}\) can be decoded by \(d_{j}=c_{k}\). Remove all the edges connected to packet \(d_{j}\).
2. Repeat (1) until all the data packets are decoded or there is no existing packet that is connected to only one data packet.  
The design of degree distribution \(\rho\left(d\right)\) is crucial for the coding efficiency. However, most \(\rho\left(d\right)\) designs like robust soliton distribution [28] require a large number of redundant packets and are optimized for large file transmission over high bandwidth links. We prefer a simple degree distribution of SVT (simple variant of tornado) codes by [PERSON] et al. [13] in our protocol design. The SVT codes can only produce a limited number of encoded packets, but they can achieve higher coding efficiency. It is sufficient in our design because of the limited channel bandwidth in the sparse underwater acoustic sensor networks. Each node generates the encoded packets independently with the same output degree distribution \(\rho\left(d\right)\). The encoding vector could be sent as part of the packet header overhead. In this way, each node in the network can recover the original data packets successfully if the node can receive a sufficient number of packets from any nodes in the network. Thus, the information in the network can be used sufficiently and an optimized performance could be achieved by designing an efficient data transfer protocol.