# A Novel Cross-Layer Routing Protocol Based on Network Coding for Underwater Sensor Networks
## 4 Design of Network Coding Routing Protocol
### Network Coding Design
#### 4.3.2 SLT Decoder  
We hope that each receiver can decode and reply immediately after receiving an encoded packet. Fortunately, [PERSON] et al. proposed a simple way to solve this problem is by message passing [28]. However, the decoding algorithm proposed by [PERSON] needs to use all the received packets at each decoding round. So we design an improved decoding algorithm for real-time decoding in Algorithm 4. In this decoder, each node stores the set of recovered packets \(\mathbb{F}\) and the set of unrecovered packets \(\mathbb{Z}\). When a new encoded packet \(Y_{i}\) is received, the node deletes all the recovered packets from \(Y_{i}\) by XOR. Then the node calculates the remaining degree of \(Y_{i}\). If the degree equals zero, all the messages in this received packet have already been recovered and this packet is useless for decoding process. If the degree is larger than one, this packet will be included into unrecovered packet set \(\mathbb{Z}\). If the degree equals one, the corresponding data packet can be recovered immediately and this packet is included into recovered packet set \(\mathbb{F}\). Once a new \(Y_{i}\) is added into \(\mathbb{F}\), all the packets in \(\mathbb{Z}\) delete \(Y_{i}\) and check if their degrees equal one. If so, new recovered packets are found and the decoding process continues until no one-degree packet is found. This decoding process can delete the useless packets and only needs a few XOR operations. So the speed of decoding process can be improved significantly. It should be pointed out that the start of the decoding process relies on the reception of one-degree packet (or the original data packets). Unless the decoder cannot have enough decoded messages for further decoding. Considering the packet loss in underwater channel, the proportion of one-degree packets in total encoded packets is advised to be over 30% in practical applications. This proportion will be further discussed in Section 5.1. Meanwhile, as SLT is a variant version of fountain codes, the decoding scheme cannot guarantee complete retrieval of the input packets even in perfect channel conditions if the received packets are not enough. However, with a proper degree distribution design, [PERSON] et.al. proved that the decoder can complete decoding successfully with \(N\) output packets (\(N\) is a little larger than the number of input packets) under high probability [28]. The analysis of successful decoding probability in our designed degree distribution is also given in Section 5.1.  
```
1:procedure\(SLT\_Decoder(Y_{i})\)
2:\(Y_{i}\): new received packet;
3:\(\mathbb{F}\): the set of recovered packets;
4:\(\mathbb{Z}\): the set of unrecovered packets;
5:\(Header\gets RemoveHeader(Y_{i})\);
6:\(C_{i}\leftarrow GetCodeVector(Y_{i})\);
7:\(Degree\gets GetDegree(C_{i})\);
8:for\(a_{k}\in C_{i}\)do
9:if\(TestRecovered(a_{k})=true\)then
10:\(Y_{i}\gets xor(Y_{i},P_{a_{k}})\);
11:\(Degree\gets Degree-1\);
12:endif
13:endfor
14:if\(degree=1\)then
15:\(\mathbb{F}\leftarrow\mathbb{F}\bigcup Y_{i}\);
16:for\(z_{k}\in\mathbb{Z}\&(z_{k}\) contains \(Y_{i})\)do
17:\(z_{k}\gets xor(z_{k},Y_{i})\);
18:\(Degree_{z_{k}}\gets Degree_{z_{k}}-1\);
19:if\(Degree_{z_{k}}=1\)then
20:\(SLT\_Decoder(Z_{k})\);
21:elseif\(Degree_{z_{k}}=0\)then
22: Remove \(z_{k}\) from \(\mathbb{Z}\);
23:endif
24:endfor
25:elseif\(Degree=0\)then
26: drop packet;
27:else
28:\(\mathbb{Z}\leftarrow\mathbb{Z}\bigcup Y_{i}\);
29:endif
30:endprocedure
```  
**Algorithm 4** SLT Decoder  
During the decoding process, we will calculate two parameters for transport layer feedback. One is \(N_{fail}\), which is the unrecovered packet number and the other is \(N_{rd}\), which is the number of redundant packets. These two parameters will be sent back to the sender for data retransmissions and power allocation as described in Section 3.3.