Wireless Broadcast with Network Coding: A Connected Dominating Sets Approach

Cédric Adjih 1 Song Yean Cho 1, 2
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : We study network coding for multi-hop wireless networks. We focus the case of broadcasting, where one source transmits information to all the nodes in the network. Our goal is energy-efficient broadcasting, in other words, to minimize the number of transmissions for broadcasting to the entire network. To achieve this goal, we propose a family of methods that combine the use of network coding and connected dominating sets. They consists in rate selections using connected dominated sets (RAUDS: Rate Adjustment Using Dominating Sets, and an generalized version, MARAUDS). The main insight behind these methods is that their use of connected dominating sets, allows near-optimality in the core of the network, while they efficiently handle borders and non-uniformity. The main contribution is a formal proof of the performance of these families of algorithms. One main result is the comparison of performance between routing and these methods (and in general, network coding).
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00284317
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, June 4, 2008 - 10:09:15 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Long-term archiving on : Tuesday, September 21, 2010 - 4:29:47 PM

Files

RR-6547.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00284317, version 2

Collections

Citation

Cédric Adjih, Song Yean Cho. Wireless Broadcast with Network Coding: A Connected Dominating Sets Approach. [Research Report] RR-6547, INRIA. 2008. ⟨inria-00284317v2⟩

Share

Metrics

Record views

308

Files downloads

176