The Throughput Order of Ad Hoc Networks Employing Network Coding and Broadcasting
Goeckel,Dennis
University of Massachusetts
Towsley,Donald
University of Massachusetts
Liu,Junning
University of Massachusetts
Gupta and Kumar established that the per
node throughput of ad hoc networks with
multi-pair unicast traffic scales as
O(1 /sqrt(n log n)), thus indicating that
network performance does not scale well
with an increasing number of nodes.
However, the model of Gupta and Kumar did
not allow for the possibility of
network coding and broadcasting,
and recent work has suggested that such
techniques have the potential to greatly
improve network throughput. Here, for
multiple unicast flows in a random
topology under the protocol communication
model of Gupta and Kumar, we show that
for arbitrary network coding and broadcasting
in a two-dimensional random topology that
the throughput scales as O(1/(nr(n))),
where n is the total number of nodes and
r(n) is the transmission radius.
When r(n) is set to ensure connectivity,
the throughput is O(1 /sqrt(n log n)),
which is of the same order as the lower bound
for the throughput without network coding and
broadcasting; in order words, network coding
and broadcasting can at most provide a constant
factor improvement of the throughput. This
conclusion is also extended to one-dimensional
and three-dimensional random deployment
topologies.
Dennis Goeckel split time between Purdue
University and Sundstrand Corporation from
1987-1992, receiving his BSEE from Purdue in
1992. From 1992-1996, he was a National
Science Foundation Graduate Fellow and
then Rackham Pre-Doctoral Fellow at the
University of Michigan, where he received
his MSEE in 1993 and his Ph.D. in 1996, both
in Electrical Engineering with a specialty
in Communication Systems. In September 1996,
he joined the Electrical and Computer
Engineering department at the University
of Massachusetts, where he is currently
an Associate Professor. His current
research interests are in the areas of
signal processing and communication theory.
Dr. Goeckel was the recipient of a
1999 CAREER Award from the National Science
Foundation for "Coded Modulation for
High-Speed Wireless Communications". He
was a Lilly Teaching Fellow at UMass-Amherst
for the 2000-2001 academic year. He served
as an Editor for the IEEE Journal on Selected
Areas in Communications: Wireless Communication
Series during its transition to the IEEE
Transactions on Wireless Communications
from 1999-2002, and as a Technical Program
Committee Co-Chair for the Communication
Theory Symposium at Globecom 2004. He is
currently an Editor for the IEEE Transactions
on Communications.