## 3 Network and Partial Networking Coding Models
### The Partial Network Coding Model  
With partial network coding [14], each source node simply broadcasts the original data without encoding it. Each intermediate forwarding node can adopt an encoding method that uses an appropriate length to reduce the delay caused by waiting for the data packets from other nodes to arrive. Each destination node executes Gaussian digestion after receiving packets and decides whether decoding can be completed successfully. If decoding is done, each decoded packet is transmitted to the upper protocol layer; otherwise, the packet is inserted into the waiting queue. Partial network coding better adapts to dynamic networks than full network coding does, especially in terms of network delay, which can be illustrated by the following example, where the source node \(S\) transmits data packets _p\({}_{1}\)_, _p\({}_{2}\)_, _p\({}_{3}\)_, and _p\({}_{4}\)_ to node \(D\) via four intermediate nodes. The example in Figure 3 depicts a scenario of full network coding. The source node \(S\) encodes the data packets of _p\({}_{1}-p_{4}\)_ to be \(p_{1}^{\prime}-p_{4}^{\prime}\) respectively and sends the encoded packets to the intermediatenodes, which in turn encode them again to be \(p_{1}^{\prime}-p_{4}^{\prime}\) respectively and then forward the re-encoded packets to node \(D\). Suppose packets \(p_{1}^{\prime}\), \(p_{2}^{\prime}\), \(p_{3}^{\prime}\) and \(p_{4}^{\prime}\) from node \(S\) arrive at node \(D\) at the time interval of \(t\), that is their arrival times are \(t\), \(2t\), \(3t\), and \(4t\) respectively. Node \(D\) can only decode the received packets back into the original data of \(p_{1}\), \(p_{2}\), \(p_{3}\), and \(p_{4}\) after all the four packets have been received and as a result the average delay of transmitting these data packets is \((4t\times 4)/4=4t\). In contrast, Figure 4 shows an example of the partial network coding algorithm. The source node \(S\) broadcasts directly the original data packets to the intermediate nodes, which each encodes them using partial network coding of some length and then forwards the encoded packets to the node \(D\). When node \(D\) receives the encoded data packet \(r_{1}p_{3}\) forwarded by the intermediate node \(1\) at time \(t\), it decodes it back to the original packet \(p_{3}\). When node \(D\) receives the encoded data packet \(r_{2}p_{2}+r_{3}p_{3}\) forwarded by the intermediate node \(3\) at time \(2t\), it decodes \(p_{2}\) because \(p_{3}\) has already been decoded. In a similar token, when node \(D\) receives the encoded packets \(r_{4}p_{1}+r_{5}p_{2}+r_{6}p_{3}\) and \(r_{7}p_{1}+r_{8}p_{2}+r_{9}p_{3}+r_{10}p_{4}\) from the nodes \(2\) and \(4\) at time \(3t\) and \(4t\) respectively, it can decode \(p_{1}\) and \(p_{4}\). So the average delay of transmitting the four packets is \((t+2t+3t+4t)/4=2.5t\), which is much better than that of the full network coding algorithm. Figure 4: Partial network coding algorithm. Figure 3: Full network coding algorithm. The original data is divided into different blocks in partial network coding, each of which includes N packets. If the random selection strategy is adopted, an intermediate node then randomly selects several packets to encode from the cache of the same block. As shown in Figure 5, an intermediate node first generates a random integer M and then randomly selects M packets from the cache queue to encode before forwarding the encoded data packets. Assume M = 2 and node A stores three packets from the same block: \(p_{3}^{\prime}\), \(p_{1}^{\prime}=r_{1}p_{1}+r_{2}p_{2}\), and \(p_{2}^{\prime}=r_{1}^{\prime}p_{1}+r_{2}^{\prime}p_{2}+r_{3}^{\prime}p_{3}\). Then packets \(p_{1}^{\prime}\) and \(p_{2}^{\prime}\) are encoded by node B to be \(p^{\prime}=a_{1}p_{1}^{\prime}+a_{2}p_{2}^{\prime}=a_{1}(r_{1}p_{1}+r_{2}p_{2 })+a_{2}(r_{1}^{\prime}p_{1}+r_{2}^{\prime}p_{2}+r_{3}^{\prime}p_{3})=(a_{i}r_{ 1}+a_{2}r_{1}^{\prime})p_{1}+(a_{1}r_{2}+a_{2}r_{2}^{\prime})p_{2}+a_{2}r_{3}^{ \prime}p_{3}\).