Global optimum encoding packet selection mechanism based on opportunistic network coding for wireless network retransmission

doi:10.1016/S1005-8885(17)60187-0

中国邮电高校学报(英文) ›› 2017, Vol. 24 ›› Issue (1): 47-59.doi: 10.1016/S1005-8885(17)60187-0

Global optimum encoding packet selection mechanism based on opportunistic network coding for wireless network retransmission

Wang Lian, Peng Daiyuan, Liang Hongbin

1. School of Information Science and Technology, Southwest Jiaotong University
2. School of Computing Science and Technology, Chongqing University of Posts and Telecommunications
3. School of Transportation and Logistics, Southwest Jiaotong University
4. School of Computing Informatics and Decision Systems Engineering, Arizona State University

收稿日期:2016-07-26 修回日期:2016-12-27 出版日期:2017-02-28 发布日期:2017-02-28
通讯作者: 王练 E-mail:910294040@qq.com
基金资助:
This work was supported by the National Natural Science Foundation of China (61571375), and the Hi-Tech Research and Development Program of China (2015AA01A705).

Global optimum encoding packet selection mechanism based on opportunistic network coding for wireless network retransmission

Wang Lian, Peng Daiyuan, Liang Hongbin

1. School of Information Science and Technology, Southwest Jiaotong University
2. School of Computing Science and Technology, Chongqing University of Posts and Telecommunications
3. School of Transportation and Logistics, Southwest Jiaotong University
4. School of Computing Informatics and Decision Systems Engineering, Arizona State University

Received:2016-07-26 Revised:2016-12-27 Online:2017-02-28 Published:2017-02-28
Contact: WANG Lian E-mail:910294040@qq.com
Supported by:
This work was supported by the National Natural Science Foundation of China (61571375), and the Hi-Tech Research and Development Program of China (2015AA01A705).

摘要/Abstract

摘要： Packet loss cannot be avoided in wireless network due to wireless transmission medium particularity, therefore improving retransmission efficiency is meaningful to wireless transmission. The current retransmission packet selection mechanisms based on opportunistic network coding (ONC) face low retransmission efficiency and high computational complexity problems. To these problems, an optimized encoding packet selection mechanism based on ONC in wireless network retransmission (OONCR) is proposed. This mechanism is based on mutual exclusion packets and decoding gain concepts, and makes full use of ONC advantages. The main contributions of this scheme are to control the algorithm complexity of the maximum encoding packets selection effectively, avoid the redundancy encoding packets due to the overlapping among encoding packets, and take the encoding packet local and global optimization problem into consideration. Retransmission efficiency is evaluated according to the computational complexity, the throughput, the retransmission redundancy ratio, and the number of average retransmission. Under the various conditions, the number of average retransmission of OONCR is mainly lower than that of other typical retransmission packet selection schemes. The average retransmission redundancy ratios of OONCR are lower about 5%~40% compared with other typical schemes. Simultaneously the computational complexity of OONCR is comparatively lower than that of other typical schemes.

关键词: wireless network, retransmission, network coding, throughput

Abstract: Packet loss cannot be avoided in wireless network due to wireless transmission medium particularity, therefore improving retransmission efficiency is meaningful to wireless transmission. The current retransmission packet selection mechanisms based on opportunistic network coding (ONC) face low retransmission efficiency and high computational complexity problems. To these problems, an optimized encoding packet selection mechanism based on ONC in wireless network retransmission (OONCR) is proposed. This mechanism is based on mutual exclusion packets and decoding gain concepts, and makes full use of ONC advantages. The main contributions of this scheme are to control the algorithm complexity of the maximum encoding packets selection effectively, avoid the redundancy encoding packets due to the overlapping among encoding packets, and take the encoding packet local and global optimization problem into consideration. Retransmission efficiency is evaluated according to the computational complexity, the throughput, the retransmission redundancy ratio, and the number of average retransmission. Under the various conditions, the number of average retransmission of OONCR is mainly lower than that of other typical retransmission packet selection schemes. The average retransmission redundancy ratios of OONCR are lower about 5%~40% compared with other typical schemes. Simultaneously the computational complexity of OONCR is comparatively lower than that of other typical schemes.

Key words: wireless network, retransmission, network coding, throughput

中图分类号:

TN919.3

Wang Lian, Peng Daiyuan, Liang Hongbin. Global optimum encoding packet selection mechanism based on opportunistic network coding for wireless network retransmission[J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2017, 24(1): 47-59.

参考文献

1. Garg V. Wireless communications and networking. Burlington, FL, USA: Morgan Kaufmann, 2010

2. Rappaport T S. Wireless communications: principles and practice. Upper Saddle River, NJ, USA: Prentice Hall, 2002

3. Hong W. Reliable and security coding in wireless communication. Beijing, China: National Defense Industry Press, 2011 (in Chinese)

4. Wang W B, Zheng K. Broadband wireless communication OFDM technology. Beijing, China: Posts and Telecom Press, 2007 (in Chinese)

5. Telatar E. Capacity of multi-antenna Gaussian channels. European Transactions on Telecommunications, 1999, 10(6): 585-595

6. Foschini G J, Gans M J. On limits of wireless communications in a fading environment when using multiple antennas. Wireless Personal Communications, 1998, 6(3): 311-335

7. Paulraj A J, Gore D A, Nabar R U, et al. An overview of MIMO communications: a key to Gigabit wireless. Proceedings of the IEEE, 2004, 92(2): 198-218

8. Sendonaris A, Erkip E, Aazhang B. Increasing uplink capacity via user cooperation diversity. Proceedings of the 1998 IEEE International Symposium on Information Theory, Aug 16-21, 1998, Cambridge, MA, USA. Piscataway, NJ, USA: IEEE, 1998: 156

9. Laneman J. Cooperative diversity in wireless networks: algorithms and architectures. PhD Thesis. Cambridge, MA, USA: Massachusetts Institute of Technology, 2002

10. Scaglione A, Goeckel D L, Laneman J N. Cooperative communications in mobile Ad hoc networks. IEEE Signal Processing Magazine, 2006, 23(5): 18-29

11. Wicker S B. Error control systems for digital communication and storage. Upper Saddle River, NJ, USA: Prentice Hall, 1994

12. Rizzo L, Vicisano L. RMDP: an FEC-based reliable multicast protocol for wireless environments. ACM SIGMOBILE Mobile Computing and Communications Review, 1998, 2(2): 23-31

13. Munoz L, Garcia M, Choque J, et al. Optimizing Internet flows over IEEE 802.11b wireless local area networks: a performance-enhancing proxy based on forward error correction. IEEE Communications Magazine, 2001, 39(12): 60-67

14. Eklund C, Marks R B, Stanwood K, et al. IEEE standard 802.16: a technical overview of the wireless MAN/sup TM air interface for broadband wireless access. IEEE Communications Magazine, 2002, 40(6): 98-107

15. Balakrishnan H, Seshan S, Amir E, et al. Improving TCP/IP performance over wireless networks. Proceedings of the 1st ACM International Conference on Mobile Computing and Networking (MobiCom’95), Nov 13-15, 1995, Berkeley, CA, USA. New York, NY, USA: ACM, 1995: 2-11

16. Altman E, Jiménez T. Novel delayed ACK techniques for improving TCP performance in multi-hop wireless networks. Proceedings of the IFIP 8th Conference on Personal Wireless Communications (PWC’03), Sept 23-25, 2003, Venice, Italy. LNCS 2775. Berlin, Germany: Springer, 2003: 237-250

17. Dianati M, Ling X, Naik K, et al. A node-cooperative ARQ scheme for wireless Ad hoc networks. IEEE Transactions on Vehicular Technology, 2006, 55(3): 1032-1044

18. Naijoh M, Sampei S, Morinaga N, et al. ARQ schemes with adaptive modulation/TDMA/TDD systems for wireless multimedia communication services. Proceedings of the 8th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC’97): Vol 2, Sept 1-4, 1997, Helsinki, Finland. Piscataway, NJ, USA: IEEE, 1997: 709-713

19. Ayanoglu E, Paul S, Laporta T F, et al. AIRMAIL: a link-layer protocol for wireless networks. Wireless Networks, 1995, 1(1): 47-60

20. Chockalingam A, Zorzi M, Tralli V. Wireless TCP performance with link layer FEC/ARQ. Proceedings of the 1999 IEEE International Conference on Communications (ICC’99): Vol 2, Jun 6-10, 1999, Vancouver Canada. Piscataway, NJ, USA: IEEE, 1999: 1212-1216

21. Choi S, Arbor A, Shin K G. A class of adaptive hybrid ARQ schemes for wireless links. IEEE Transactions on Vehicular Technology, 2001, 50(3): 777-790

22. Rozner E, Iyer A P, Mehta Y, et al. ER: efficient retransmission scheme for wireless LANs. Proceedings of the 3rd International Conference on Emerging Networking Experiments and Technologies (CoNEXT’ 07), Dec 10-13, 2007, New York, NY, USA. New York, NY, USA: ACM, 2007: 8

23. Nguyen D, Tran T, Nguyen T, et al. Wireless broadcast using network coding. IEEE Transactions on Vehicular Technology, 2009, 58(2): 914-925

24. Tran T, Nguyen T, Bose B, et al. A hybrid network coding technique for single-hop wireless networks. IEEE Journal on Selected Areas in Communications, 2009, 27(5): 685-698

25. Cui T, Chen L J, Ho T. Energy efficient opportunistic network coding for wireless networks. Proceedings of the 27th Annual Joint Conference of the IEEE Computer and Communications (INFOCOM’08), Apr 13-18, 2008, Phoenix, AZ, USA. Piscataway, NJ, USA: IEEE, 2008: 361-365

26. Alimi R, Li L, Ramjee R, et al. iPack: in-network packet mixing for high throughput wireless mesh networks. Proceedings of the 27th Annual Joint Conference of the IEEE Computer and Communications (INFOCOM’08), Apr 13-18, 2008, Phoenix, AZ, USA. Piscataway, NJ, USA: IEEE, 2008: 66-70

27. Prasad R, Wu H Y, Perkins D, et al. Local topology assisted XOR coding in wireless mesh networks. Proceedings of the 28th International Conference on Distributed Computing Systems (ICDCS’08), Jun 17-20, 2008, Beijing, China. Piscataway, NJ, USA: IEEE, 2008: 156-161

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

29. Koetter R, Médard M. Beyond routing: an algebraic approach to network coding. Proceedings of the 21th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’02): Vol 1, Jun 23-27, 2002, New York, NY, USA. Piscataway, NJ, USA: IEEE, 2002: 122-130

30. Jaggi S, Sanders P, Chou P A, et al. Polynomial time algorithms for multicast network code construction. IEEE Transactions on Information Theory, 2005, 51(6): 1973-1982

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

32. Koetter R, Médard M. An algebraic approach to network coding. IEEE/ACM Transactions on Networking, 2003, 11(5): 782-795

33. Katti S, Rahul H, Hu W, et al. XORs in the air: practical wireless network coding. ACM SIGCOMM Computer Communication Review, 2006, 36(4): 243-254

34. Wu H, Zheng J. Efficient network coding-based multicast retransmission mechanism for mobile communication networks. IET Communications, 2012, 6(2): 187-193

35. Wu H, Zheng J. Network coding based multicast retransmission for mobile communication networks. Proceedings of the 12th International Conference on Communication Technology (ICCT’10), Nov 11-14, 2010, Nanjing, China. Piscataway, NJ, USA: IEEE, 2010: 235-238

36. Xiao X, Yang L M, Wang W P, et al. A wireless broadcasting retransmission approach based on network coding. Proceedings of the 4th IEEE International Conference on Circuits and Systems for Communications (ICCSC’08), May 26-28, 2008, Shanghai, China. Piscataway, NJ, USA: IEEE, 2008: 782-786

37. Wu H, Zheng J. CoRET: a network coding based multicast retransmission scheme for mobile communication networks. Proceedings of the 2011 IEEE International Conference on Communications (ICC’11), Jun 5-9, 2011, Kyoto, Japan. Piscataway, NJ, USA: IEEE, 2011: 5p

38. Hu Q, Zheng J. An efficient packet selection algorithm for network coding based multicast retransmission in mobile communication networks. Proceedings of the IEEE 13th International Conference on Communication Technology (ICCT’11), Sept 25-28, 2011, Jinan, China. Piscataway, NJ, USA: IEEE, 2011: 999-1003

39. Gou L, Zhang G X, Bian Z G, et al. Minimizing completion time for relay-assisted multicast with instantly decodable network coding. IEEE Communications Letters, 2016, 20(3): 434-437

40. Wang B, Wang W N. Wireless broadcast retransmission scheme based on parallel network coding. Journal of Nanjing University of Posts and Telecommunications (Natural Science), 2014, 34(6): 9-15 (in Chinese)

41. Yao Y K, Yi J Q, Ren Z, et al. Efficient rapid multi-packet decoding and network coding based broadcasting retransmission. Journal of Huazhong University of Science and Technology (Natural Science), 2013, 4(6): 30-41

42. Zhian H, Sabaei M, Javan N T, et al. Increasing coding opportunities using maximum-weight clique. Proceedings of the 5th IEEE Computer Science and Electronic Engineering Conference (CEEC’13), Sept 17-18, 2013, Colchester, UK. Piscataway, NJ, USA: IEEE, 2013: 168-173

43. Zhan C, Lee V C S, Wang J P, et al. Coding-based data broadcast scheduling in on-demand broadcast. IEEE Transactions on Wireless Communications, 2011, 10(11): 3774-3783

44. Hu X, Wang L Z, He W T, et al. Degree-based approach for the maximum clique problem. Journal of Frontiers of Computer Science and Technology, 2013, 7(3): 262-271 (in Chinese)

45. Li P, Wang Z B, Guo M. A maximum clique algorithm based on MapReduce. Proceedings of the 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE’10): Vol 6, Aug 20-22, 2010, Chengdu, China. Piscataway, NJ, USA: IEEE, 2010: 87-90

46. Dai B, Cao Z G, Yang J, et al. Coded retransmission algorithm based on matching theory for wireless broadcasting. Journal of Software, 2011, 22(11): 2833-2842 (in Chinese)

[1]	Wang Xiuli, Hao Yakun. Two constructions of LDPC codes based on pseudo-symplectic geometry over finite fields[J]. 中国邮电高校学报(英文版), 2018, 25(2): 49-59.
[2]	王亚峰魏国兴杨大成向维. Research on uplink coordinated transmission schemes in LTE-advanced systems[J]. Acta Metallurgica Sinica(English letters), 2011, 18(2): 72-77.
[3]	刘海涛;韩方景;万建伟. Performance analysis of anti-interference wireless packet networks for LEO micro-satellite with adaptive nulling antenna array[J]. Acta Metallurgica Sinica(English letters), 2006, 13(2): 10-14.

Global optimum encoding packet selection mechanism based on opportunistic network coding for wireless network retransmission

Global optimum encoding packet selection mechanism based on opportunistic network coding for wireless network retransmission

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价