Algebraic approach to random convolutional network coding over wireless packet networks

Abstract

To characterize the algebraic structure of wireless network coding, a hypergragh is utilized to model wireless packet networks from network layer. The algebraic description of random convolutional network coding is deduced, and the coding condition is also presented. Analyses and simulations show that random convolutional coding is capacity-achieving with probability approaching 1.

Keywords

wireless network coding / random convolutional network coding / hypergraph / capacity-achieving

References

[1] Alshwede R, Cai N, Li S Y R, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216.

[2] Li S Y R, Yeung R W, Cai N. Linear network coding[J]. IEEE Transactions on Information Theory, 2003, 49(2): 371 381

[3] Koetter R, Medard M. An algebraic approach to network coding[J]. IEEE/ACM Transactions on Networking, 2003, 11(5): 782-795.

[4] Ho T, Medard M, Koetter R, et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory, 2006, 52(10): 4413 4430

[5] Lun D S, Medard M, Effros M. Further results on coding for reliable communication over packet networks[C]. 2005 IEEE International Symposium on Information Theory, 2005

[6] Li J, Ge W, Wang J, et al. Enhanced network coding for TCP in wireless networks[C]. 7th International Conference on Wireless Communications, Networking and Mobile Computing, 2011

[7] Kim M J, Medard M. Algebraic network coding approach to deterministic wireless relay networks[C]. 48th Annual Allerton Conference on Communication, Control and Computing, 2010

[8] Dana A F, Gowaikar R, Palanki R, et al. Capacity of wireless erasure network[J]. IEEE Transactions on Information Theory, 2006, 52(3): 789 804

[9] Katti S, Rahul H, Hu W, et al. XORs in the air: Practical wireless network coding[J]. IEEE/ACM Transactions on Networking, 2008, 16(3): 497-510.

[10] Shen L, Hou C, Yang Jiachen. Information exchange using network coding in wireless network[J]. Journal of Tianjin University, 2007, 40(Suppl): 58-65.

[11] Lu J, Xiao S, Wu Chengke. A broadcast retransmission method using opportunistic network coding in wireless networks[J]. Journal of Xi’an Jiaotong University, 2011, 45(2): 68-72.

[12] Hao J, Feng H, Wu Guangxue. Improving data transmission reliability with network coding in wireless sensor network[C]. Proceedings 2010 Second International Conference on Multimedia Information Networking and Security, 2010

[13] Hao K, Jin Zhigang. An optimization algorithm of network coding for minimizing coding nodes[J]. Journal of Electronics & Information Technology, 2011, 33(2): 260-265.

[14] Suk K T, Serdar V, Ioannis B, et al. A framework for joint network coding and transmission rate control in wireless networks[C]. IEEE Conference on Computer Communications 2010, 2010

[15] Motwani R, Raghavan P. Randomized Algorithms[M]. 1995, UK: Cambridge University Press.