Random network coding based schemes for perfect wireless packet retransmission problems in multiple channel networks

Zhenguo Gao, Klara Nahrstedt, Weidong Xiang, Huiqiang Wang, Yibing Li

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)1517-1534
Number of pages18
JournalWireless Personal Communications
Issue number4
StatePublished - Apr 2013


  • Integer linear programming
  • Linear programming
  • Multiple channel networks
  • Random network coding
  • Wireless packet retransmission problem

ASJC Scopus subject areas

  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Random network coding based schemes for perfect wireless packet retransmission problems in multiple channel networks'. Together they form a unique fingerprint.

Cite this