Order-Optimal Information Dissemination in MANETs via Network Coding

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 objec...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2014-07, Vol.25 (7), p.1841-1851
Main Authors: Bin Tang, Baoliu Ye, Song Guo, Sanglu Lu, Wu, Dapeng Oliver
Format: Article
Language:English
Subjects:
Ad hoc networks
Algorithms
Coding
Encoding
Information dissemination
Manufacturing cells
Messages
mobile ad-hoc networks
Mobile communication systems
Mobile computing
Network coding
Network topology
Networks
Packets (communication)
Protocols
random linear network coding
Vectors
Wireless networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2013.275