Order-optimal information dissemination in MANETs via network coding

Bin Tang, Baoliu Ye, Song Guo, Sanglu Lu, Dapeng Oliver Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

Motivated by various applications in mobile ad-hoc networks (MANETs) that require nodes to share their individual information to each other, we study the multi-message dissemination problem in a MANET, which is to distribute multiple messages to all mobile nodes in the network in parallel. The objective is to minimize the stopping time, i.e., the time taking for all nodes to receive a copy of the whole messages. We consider an intrinsically one-sided protocol based on random linear network coding (RLNC), where all packets forwarded are in the form of random linear combinations of packets received so far. Its supreme performance is demonstrated theoretically for two cases, low mobility and high mobility, according to the node velocity. In particular, we show that, under general settings, our derived upper bounds of the stopping time match the established lower bound in both cases, although the effects of mobility in the two cases are significantly different. Thus, we conclude that RLNC achieves order optimality for fast information dissemination in MANETs.
Original languageEnglish
Article number6648317
Pages (from-to)1841-1851
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Volume25
Issue number7
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes

Keywords

  • Information dissemination
  • mobile ad-hoc networks
  • random linear network coding

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this