naa a22 4500 510794769 CHVBK 20180411083332.0 cr unu---uuuuu 180411e20130401xx s 000 0 eng 10.1007/s11277-012-0648-9 doi (NATIONALLICENCE)springer-10.1007/s11277-012-0648-9 Random Network Coding Based Schemes for Perfect Wireless Packet Retransmission Problems in Multiple Channel Networks [Elektronische Daten] [Zhenguo Gao, Klara Nahrstedt, Weidong Xiang, Huiqiang Wang, Yibing Li] Solving WPRTPs (wireless packet retransmission problems) using NC (network coding) is increasingly attracting research efforts. However, no work on NC based schemes for WPRTPs in MCNs (multiple channel networks) has been found. In this paper, RNC (random network coding) based schemes for P-WPRTPs (perfect WPRTPs) in MCNs, denoted as MC-P-WPRTPs (multiple channel perfect WPRTPs), are studied by transforming MC-P-WPRTPs into ILP (integer linear programming) problems. The ILP problems corresponding to MC-P-WPRTPs with four typical configurations are derived. Then the corresponding packet retransmission schedule schemes for MC-P-WPRTPs are proposed based on the solutions to the ILP problems and random network coding. To solve the ILP problems efficiently, an algorithm named as progressively fixing algorithm is proposed which recursively reduce the size of the ILP problem by fixing some of the variables according to some criteria. The criteria are related to the solution to the LP problem obtained by relaxing the integral constraints on the variables in the original ILP problem. Simulation results show that the NC based schemes for MC-P-WPRTPs are effective in saving packet retransmissions. In some situations, NC based schemes can save about 50% packet retransmissions. Springer Science+Business Media, LLC., 2012 Wireless packet retransmission problem nationallicence Multiple channel networks nationallicence Random network coding nationallicence Integer linear programming nationallicence Linear programming nationallicence ILP : Integer linear programming nationallicence IP-WPRTP : Imperfect WPRTP nationallicence IP-WPRTP-DC : Divide and conquer based scheme for IP-WPRTP nationallicence LP : Linear programming nationallicence MCNC : Multiple-channel with network coding nationallicence MCNoNC : Multiple-channel no network coding nationallicence MC-P-WPRTP : Perfect MC-WPRTP nationallicence MC-WPRTP : Multiple channel wireless packet retransmission problem nationallicence NC : Network coding nationallicence P-WPRTP : Perfect WPRTP nationallicence RNCOPT : Random network coding based optimal scheme for P-WPRTP nationallicence SCNC : Single-channel with network coding nationallicence SCNoNC : Single-channel no network coding nationallicence WPRTP : Wireless packet retransmission problem nationallicence Gao Zhenguo College of Automation, Harbin Engineering University, Harbin, China aut Nahrstedt Klara Department of Computer Science, University of Illinois at Urbana-Champaign, 61801, Urbana, IL, USA aut Xiang Weidong Department of Electrical and Computer Engineering, University of Michigan, 48141, Dearborn, MI, USA aut Wang Huiqiang College of Computer Science and Technology, Harbin Engineering University, Harbin, China aut Li Yibing College of Information and Communications Engineering, Harbin Engineering University, Harbin, China aut Wireless Personal Communications Springer US; http://www.springer-ny.com 69/4(2013-04-01), 1517-1534 0929-6212 69:4<1517 2013 69 11277 https://doi.org/10.1007/s11277-012-0648-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11277-012-0648-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Gao Zhenguo College of Automation, Harbin Engineering University, Harbin, China aut NATIONALLICENCE 700 1- Nahrstedt Klara Department of Computer Science, University of Illinois at Urbana-Champaign, 61801, Urbana, IL, USA aut NATIONALLICENCE 700 1- Xiang Weidong Department of Electrical and Computer Engineering, University of Michigan, 48141, Dearborn, MI, USA aut NATIONALLICENCE 700 1- Wang Huiqiang College of Computer Science and Technology, Harbin Engineering University, Harbin, China aut NATIONALLICENCE 700 1- Li Yibing College of Information and Communications Engineering, Harbin Engineering University, Harbin, China aut NATIONALLICENCE 773 0- Wireless Personal Communications Springer US; http://www.springer-ny.com 69/4(2013-04-01), 1517-1534 0929-6212 69:4<1517 2013 69 11277 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer