Reduced-complexity network coding for multicasting over ad hoc networks

Yunnan Wu, Sun-Yuan Kung

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

14 Scopus citations

Abstract

Network coding generalizes the conventional routing paradigm by allowing nodes to mix information received on its incoming links to generate information to be transmitted to other nodes. As a result, network coding improves throughput, resource efficiency, robustness, manageability, etc, in wired and wireless ad hoc networks. In particular, it was established that network coding can achieve the maximum rate for multicasting information from a source node to multiple destination nodes. The objective of this work is to show how to achieve the aforementioned multicast capacity with lower processing/implementation complexity than what was proposed in the literature. We classify the links in a network into two categories: 1) links entering relay nodes, and 2) links entering destinations. We show the same multicast capacity can be achieved by applying (non-trivial) network coding only on the links entering relay nodes. In other words, links entering destinations will only require routing, which leads to a saving in the processing/implementation complexity. The novelty of this work lies in a new algorithm, its proof of correctness, and a complexity analysis.

Original languageEnglish (US)
Title of host publication2005 IEEE International Conference on Acoustics, Speech, and Signal Processing,ICASSP '05 - Proceedings - Audio and ElectroacousticsSignal Processing for Communication
PublisherInstitute of Electrical and Electronics Engineers Inc.
VolumeIII
ISBN (Print)0780388747, 9780780388741
DOIs
StatePublished - Jan 1 2005
Event2005 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP '05 - Philadelphia, PA, United States
Duration: Mar 18 2005Mar 23 2005

Other

Other2005 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP '05
CountryUnited States
CityPhiladelphia, PA
Period3/18/053/23/05

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering
  • Signal Processing
  • Acoustics and Ultrasonics

Fingerprint Dive into the research topics of 'Reduced-complexity network coding for multicasting over ad hoc networks'. Together they form a unique fingerprint.

  • Cite this

    Wu, Y., & Kung, S-Y. (2005). Reduced-complexity network coding for multicasting over ad hoc networks. In 2005 IEEE International Conference on Acoustics, Speech, and Signal Processing,ICASSP '05 - Proceedings - Audio and ElectroacousticsSignal Processing for Communication (Vol. III). [1415756] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2005.1415756