# A Novel Cross-Layer Routing Protocol Based on Network Coding for Underwater Sensor Networks
## 4 Design of Network Coding Routing Protocol
### Network Coding Design  
Network coding is a new coding scheme which is based on network and multi-node coding. The conventional approach of sending information from one node to multi-node is to send information to relay node equally, and these relay nodes just store and forward the information they receive. This scheme is simple but cannot use the channel resource efficiently. Some relay nodes might send repetitive packets so the receiving nodes have much data redundancy. Network coding is proposed to solve high energy consumption and low data delivery ratio in multi-cast network and it has been attracting attention since it is proposed. In network coding, each relay node recodes data packets before sending them to the next hop node. Based on the multi-cast feature in wireless network, network coding can significantly reduce repetitive data sending, decrease energy consumption and prolong the network lifetime. In UWSNs, data transmissions need more energy and the delay of data retransmission is longer compare with terrestrial wireless network. So network coding can play a greater role in UWSNs. Network coding can be illustrated in Figure 4. Node \(A\) and node \(C\) wish to send packets \(x_{a}\) and \(x_{c}\) to each other and node \(B\) is a relay node which can relay data to node \(A\) or \(C\). In Figure 4a, according to the conventional multi-hop transmission approach, there are four steps in data transmissions: (1) node \(A\) sends \(x_{a}\) to node \(B\). (2) node \(B\) forwards \(x_{a}\) to node \(C\). (3) node \(C\) sends \(x_{c}\) to node \(B\). (4) node \(B\) forwards \(x_{c}\) to node \(A\). If node \(B\) recodes packets using network coding before sending out, the transmission process can be decreased to three steps as shown in Figure 4b: (1) node \(A\) sends \(x_{a}\) to node \(B\). (2) node \(C\) sends \(x_{c}\) to node \(B\). (3) node \(B\) broadcast the exclusive-or (XOR) of \(x_{a}\) and \(x_{c}\) to node \(A\) and node \(C\). Node \(A\) and \(C\) can recover the original data packets by XOR with their own sent packets. This simple change can decrease the propagation delay significantly. For unidirectional transmissions, we can illustrate the transmission efficiency improvement by a simple three node transmission case in Figure 4c. We wish that node \(A\) sends data packets to node \(C\) and node \(B\) is the relay node. With the multi-cast effect in UWSNs, the packets sent by node \(A\) can be received by node \(B\) and \(C\) under a certain error probability. As the distance between node \(A\) and \(B\) is shorter than the distance between node \(A\) and node \(C\), the quality of underwater channel between node \(A\) and \(B\) is better. So node \(B\) can receive enough encoded packets for successful decoding while node \(C\) needs more packets. If node \(B\) recodes the received packets by network coding and sends a few encoded packets to node \(C\), node \(C\) can jointly decode messages successfully with packets from node \(A\) and \(B\). This scheme can reduce the repetitive packets transmission and improve the data transmission efficiency. This advantage is highlighted when there are many nodes (more than 3) participating in data transfer. From the above analysis we know that the key of designing network coding is to find a proper coding scheme which can avoid repetitive data transmissions. In 2003, [PERSON] et al. proposed random linear network coding [27] which is widely used currently. The key idea of linear network coding is to encode data packets by random linear combination at the sender side, and to decode messages by matrix inversion at the receiver side. The detailed procedure can be described as follows: At the sender side, data packets are grouped into several clusters. Suppose \(X_{1},\cdots,X_{K}\) are data packets in a cluster and \(Y_{1},\cdots,Y_{N}\) are packets after encoding. Then \(Y_{i}=\sum\limits_{j=1}^{K}g_{ij}X_{j}\), \(i=1,\cdots,N\).