Latency-optimized Broadcast in Mobile Ad Hoc Networks
without Node Coordination
Bin Tang
State Ke y Lab for Novel
Software Technology
Nanjing University, China
tb@nju.edu.cn
Baoliu Ye
∗
State Ke y Lab for Nov el
Software Technology
Nanjing University, China
yebl@nju.edu.cn
Sanglu Lu
State Ke y Lab for Novel
Software Technology
Nanjing University, China
sanglu@nju.edu.cn
Song Guo
School of Computer Science
and Engineering
The University of Aizu, Japan
sguo@u-aizu.ac.jp
Ivan Stojmenovic
School of Information
Technology and Engineering
University of Ottawa, Canada
ivan@site.uottawa.ca
ABSTRACT
We consider the problem of broadcasting a message in a mo-
bile ad hoc network (MANET) with the objective of mini-
mizing the broadcast latency. Due to the mobility of network
nodes, the coordination among nodes is hard and expensive.
Thus it is much desired to design efficient, one-sided broad-
cast protocols where each node acts according to its own
state solely. Although random scheduling is a popular and
effective one-sided approach for leveraging the broadcast na-
ture of wireless medium while coping with transmission colli-
sions, both critical for reducing the broadcast latency, in this
paper, we show that when nodes move very fast, the perfor-
mance of pure random scheduling must be sub-optimal, no
matter how the forwarding probabilities are specified. Fur-
thermore, we propose a novel one-sided broadcast protocol
named R
2
, which first splits the message into a certain num-
ber of mini-messages and then couples a fine-grained random
scheduling with random linear network coding for broadcast-
ing the mini-messages. Theoretical analyses demonstrate
that R
2
performs optimally in order sense, no matter how
fast network nodes move around, although different mobility
has distinct effect on the speed of message broadcast.
Categories and Subject Descriptors
C.2.2 [Computer-Communication Networks]: Network
Protocols
Keywords
Mobile Ad Hoc Networks, Broadcast, Random Linear Net-
work Coding, Random Scheduling
∗
Corresponding author
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full cita-
tion on the first page. Copyrights for components of this work owned by others than
ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or re-
publish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
MobiHoc’14, August 11–14, 2014, Philadelphia, PA, USA.
Copyright @ 2014 ACM 978-1-4503-2620-9/14/08
˙
..$15.00.
http://dx.doi.org/10.1145/2632951.2632982 .
1. INTRODUCTION
With the fast development of wireless and social network-
ing technologies, there has been increasing interest on the
use of mobile ad hoc networks (MANETs) for data commu-
nication. A typical MANET is self-configured and formed
by a collection of wireless nodes which act not only as hosts
but also as relays, storing and forwarding data for other
nodes in the network. The nodes in a MANET can move
around at their will, which on one hand, brings the poten-
tial to improve the network performance, e.g., capacity [18]
and throughput-delay tradeoff [39], but on the other hand,
raises great challenges for protocol design and performance
optimization, as the network topology may change rapidly
and unpredictably.
Network-wide broadcast, i.e., delivering a message from
a source node to all other network nodes, is a fundamental
operation in MANETs. For many important applications
of MANETs, like military communication, it is essential to
design an efficient broadcast scheme with low br oadcast la-
tency (i.e., the time it takes for all the network nodes to
receive a copy of the message), so that the end-to-end delay
for higher-level applications could be stringently guaranteed.
Towards minimizing the broadcast latency in MANETs,
two key features of wireless communications should be care-
fully addressed. One is the broadcast nature of wireless
medium, i.e., a transmission of a message could be heard
simultaneously by multiple neighboring nodes, which can
speed up the broadcast process. The other is wireless in-
terference/collision, i.e., a node cannot receive a message if
more than one neighboring nodes are transmitting at the
same time, which can thus limit the diffusion of the mes-
sage. In static wireless ad hoc networks, the two features
are usually incorporated by constructing a broadcast tree
together with a collision-free broadcast schedule [15, 25, 33,
14]. However, in a MANET, the network topology is dy-
namic over time, making the construction and maintenance
of a broadcast tree prohibitive and also the coordination
among nodes expensive, especially when the network nodes
move very fast. Therefore, it is much desired if we could
design an efficient one-sided broadcast protocol where each
node acts according to its own state solely, avoiding the co-
ordination among nodes.