Polynomial time and provably efficient network coding scheme for lossy wireless networks

Abdallah Khreishah, Issa M. Khalil, Jie Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

The network coding problem across multiple unicasts is an open problem. Previously, the capacity region of 2-hop relay networks with multiple unicast sessions and limited feedback was characterized where the coding and decoding nodes are neighbors and packet erasure channels are used. A near-optimal coding scheme that exploits the broadcast nature and the diversity of the wireless links was proposed. However, the complexity of the scheme is hyper' exponential as it requires the knowledge of the packets that are received by any subset of the receivers. In this paper, we provide a polynomial time coding scheme and characterize its performance using linear equations. The coding scheme uses random network coding to carefully mix intra and intersession network coding and makes a linear, not exponential, number of decisions. We also provide a linear programming formulation that uses our 2-hop relay network results as a building block in large lossy multihop networks. Through simulations, we verify the superiority of our proposed schemes over state-of-the-art.

Original languageEnglish (US)
Title of host publicationProceedings - 8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011
Pages391-400
Number of pages10
DOIs
StatePublished - Dec 16 2011
Externally publishedYes
Event8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011 - Valencia, Spain
Duration: Oct 17 2011Oct 22 2011

Publication series

NameProceedings - 8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011

Other

Other8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011
CountrySpain
CityValencia
Period10/17/1110/22/11

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Networks and Communications

Keywords

  • 2-hop relay networks
  • Network coding
  • capacity
  • fairness
  • lossy wireless networks

Fingerprint Dive into the research topics of 'Polynomial time and provably efficient network coding scheme for lossy wireless networks'. Together they form a unique fingerprint.

Cite this