Network coding based schemes for imperfect wireless packet retransmission problems: A divide and conquer approach

Zhenguo Gao, Mei Yang, Jianping Wang, Klara Nahrstedt, Shaobin Cai, Xiang Li, Huiqiang Wang

Research output: Contribution to journalArticlepeer-review

Abstract

NC (Network Coding) provides a new approach to packet retransmission problems in wireless networks, which are named as WPRTPs (Wireless Packet Retransmission Problems) in this paper. Some research has been conducted on P-WPRTPs (Perfect WPRTPs) where, for one receiver, a packet is either being requested by or already known to it. However, very few efforts are focused on IP-WPRTPs (Imperfect WPRTPs) where, for one receiver, a packet can be neither requested by nor already known to it. In this paper, we focus on IP-WPRTPs. Firstly, a WPRTP reduction theorem for simplifying WPRTPs is proposed and proved. Then, the upper and lower bounds of the number of necessary packet transmissions in optimal NC-based solutions to IP-WPRTPs are analyzed. Next, a scheme named as IP-WPRTP-DC (Divide and Conquer based scheme for IP-WPRTPs) is proposed based on the WPRTP reduction theorem using a divide and conquer approach. Extensive simulations show that the IP-WPRTP-DC scheme is effective in saving the number of packet transmissions for solving IP-WPRTPs.

Original languageEnglish (US)
Pages (from-to)937-958
Number of pages22
JournalWireless Personal Communications
Volume62
Issue number4
DOIs
StatePublished - Feb 2012

Keywords

  • Divide and conquer approach
  • Imperfect wireless packet retransmission problems
  • Problem reduction
  • Random network coding

ASJC Scopus subject areas

  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Network coding based schemes for imperfect wireless packet retransmission problems: A divide and conquer approach'. Together they form a unique fingerprint.

Cite this