Network coding can be done both in wired networks [Ref.1] and also in wireless networks [Ref.2]. In the overview of network coding discussion below we are considering only the case of wireless networks.
Basic Idea of Network Coding:
Network coding is a kind of coding technique which is used for multicast-broadcast wireless communication systems [Ref.3]. In multicast-broadcast communication system there is only one transmitter but multiple receivers to receive the same transmitted signal. Network coding increases the data throughput and also a small number of re-transmission is required to recover the lost packets during the transmission [Ref.4].
Example of Network Coding:
To simplify the idea of network coding in a very basic and simple way let us consider one example:
Suppose one transmitter want to transmit 2 packets together which are x1 and x2 to 2 receiver. Now on the path of transmission there is channel. In channel there is noise. Because of the noise suppose X1 gets lost in the path of 1st receiver R1 and X2 gets lost in the path of 2nd receiver R2.
Now, if the receivers want to get the packets again then the transmitter again need to transmit X1 and X2. For this, the transmitter needs two re-transmission. But if network coding is used here then the transmitter will need only one re-transmission. How? Yes, now i am going to answer this question.
Network coding X-OR’s the two packets X1+X2 (here + means the exclusive or operation) and transmits it. As receiver R1 has X2 packet it will do X-OR operation with X1+X2. So, X1 will get recovered or demodulated. On the other hand, the receiver R2 will do X-OR operation with X1+X2 and as an output receiver 2 will get X2.
How Network Coding Increases Data Rate and Coverage?:
So, from the above example this is quite clear that network coding can lessen the number of re-transmission significantly which increases the data rate and also the coverage.
Now you may have one question in your mind that this is clear that it increases the data rate by decreasing the number of re-transmission but how it can increase the coverage? Yes is the answer and i am explaining how?
As the number of re-transmission increases, the decoder can decode more packets and the number of re-transmission increases according to the error probability. As the receiver distance becomes more from the transmitter, the error probability is also high as the channel gets bad. So, for high error probability the number of re-transmission is more and in this way receiver also get the ability to recover all the lost packets.
Decoders Used for Network Coding:
There are mainly two types of receivers which are used for network coding : one is optimal receiver [Ref. 2] and another one is iterative receiver [Ref. 4]. The optimal receiver works on the basis of Gaussian Elimination ; On the other hand the Iterative receiver uses Tanner Graph to decode the received packets. The performance of optimal receiver is better than iterative receiver. So far researchers only worked on this two types of receivers as per the history of publications.
Types of Network Coding Discovered So Far :
Linear Network Coding [Ref. 5]:
Figure Courtesy [Ref. 5]
The first network coding which was introduced is the linear network coding but in that case the performance was not that much good.
Random Network Coding [Ref. 2]:
After that Random network coding is used and researchers got good result. In random network coding. The secret behind getting good result using random network coding was the packets in the retransmittion were distributed randomly. So, there was a high probability to recover the missing packets. The packets were equally distributed in the retransmission part. So, if any packet in the transmission was lost, it has high chance to get recovered by using random network coding.
But random network coding has one disadvantage and that is the redundancy in the packet header. For random network coding the packet coefficients need to be added in the packet header which will cost high redundancy and which is not good for the data throughput. Also this is very difficult to use random network coding where there is no feedback information from the receiver side about the received and lost packets.
So, scientists tried to improve this and they found some other design of network coding codebook.
Motorola Codebook For Network Coding [Ref. 6]:
Motorola research lab found one network coding codebook for no feedback information and a very little feedback information case but the performance is not good. For details readers can refer to the document for Motorola codebook. The algorightm to design the codebook is described below:
Figure Courtesy [Ref. 6]
Dia-PRNC (Diagonal-Pseudo Random Network Coding ) and Tri-PRNC (Triangular – Pseudo Random Network Coding) [Ref. 3]:
In 2010 another network coding scheme with no Feedback is proposed in VTC 2013, Taipei, Taiwan conference. In this two codebook the performance was better than Motorola scheme and No coding scheme but not better than random network coding scheme. But there is no packet overhead for this scheme.
For the diagonal codebook, the researchers used on diagonal codebook in the transmission part of the matrix and for triangular codebook in the transmission part triangle shaped codebook is used. For both the case the lower retransmission matrix was same.
While proposing these codebooks, researchers also mentioned one important parameter which is All Perfect Ratio (APR), which means the ratio of number of successful trial to the total number of trial. Suppose, the transmitter transmits 50 packets to the receiver for 10 times, then we need to calculate the ratio of number of successful trial (when all the 50 packets were received by the receiver) divided by 10 (which is total number of trial). If the APR =1 , this means that the preformance of the codebook is very good.
In some cases of communication this is very important to have APR=1, otherwise all the transmitted packets need to be re-transmitted.
Figure Courtesy from [Ref. 3]
From the above figure we can observe that the performance of dia-prnc in terms of decoded packet is higher than Motorola Arulselvan’s scheme and no coding.But not better than random network coding.Also the performance of tri-prnc is not good from the starting.
Harmonized Scheme For Network Coding [Ref. 7 ]:
NEC Lab America. proposed another network coding scheme which is named as harmonezied shceme. In this network coding scheme they used some small blocks in the retransmission part to design the codebook. Readers can see the performance below:
Figure Courtesy from [Ref. 7]
From the above picture this is clear that the performance of Harmonized scheme is better than NTU (National Taiwan University, Taiwan) dia-prnc.
References :
[1] W. Hu D. Katabi M. Medard S. Katti, H. Rahul and J. Crowcroft.” Xors in the air: practical wireless network coding”. IEEE/ACM Transactions on Networking (TON), 16(3):497–510, 2008.
[2] J. Jin, B. Li, and T. Kong.“Is random network coding helpful in wimax?” In INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, pages 2162–2170, 2008.
[3] C. Chao, C. Chou, and H. Wei, “Pseudo random network coding design for IEEE 802.16m enhanced multicast and broadcast service,” in Proc. IEEE Veh. Technol. Conf. (VTC), Taipei, Taiwan, Apr. 2010.
[4] G. Yue and X. Wang, “Anti-jamming coding techniques with application to cognitive radio,” IEEE Trans. Wireless Commun., vol. 8, no. 12, pp. 5996–6007, Dec. 2009.
[5] R. Y. S. Li, R. Yeung, and N. Cai. Linear network coding. IEEE Transactions on Information Theory, 49(2):371–381, 2003.
[6] N. Arulselvan S. Kalyanasundaram H. Xu, S. Xu. Network coding-based
retransmission for e-mbs with and without ms feedback. IEEE 802.16 standard meeting Session 59, 2009.
[7] Guosen Yue, Mohammad Khojastepour, Sampath Rangarajan,“Design of Binary Network Coding for Wireless Broadcast” IEEE Globecom 2011
