Order-Optimal Information Dissemination in MANETs via Network Coding

• 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
• ISSN: 1045-9219; 1558-2183
• DOI: 10.1109/TPDS.2013.275

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.