The optimal throughput order of wireless ad hoc networks and how to achieve it


Event IEEE MILCOM 2008


Garcia-Luna-Aceves, J J.
Technical Publications
November 17th 2008
In this paper, we study the contribution of network coding (NC) in improving the multicast capacity of random wireless ad hoc networks when nodes are endowed with multi-packet transmission (MPT) and multi-packet reception (MPR) capabilities. We show that a per session throughput capacity of $Thetaleft(nT^{3}(n)right)$,where $n$ is the total number of nodes and $T(n)$ is the transmission range, can be achieved as a tight bound when each session contains a constant number of sinks. Surprisingly, an identical order capacity can be achieved when nodes have only MPR and MPT capabilities. This result proves that NC does not contribute to the order capacity of multicast traffic in wireless ad hoc networks. The result is in sharp contrast to the general belief (conjecture) that NC improves the order capacity of multicast. Furthermore, if the communication range is selected to guarantee the connectivity in the network, i.e., $T(n)ge Thetaleft(sqrt{log n/n}right)$, then the combination of MPR and MPT achieves a throughput capacity of $Thetaleft(frac{log^{frac{3}{2}} n}{sqrt{n}}right)$ which provides an order capacity gain of $Thetaleft(log^2 nright)$ compared to the point-to-point communication capacity that was reported by Gupta and Kumar.


Karande, S.; Wang, Z.; Sadjadpour, H.; Garcia-Luna-Aceves, J. J. The optimal throughput order of wireless ad hoc networks and how to achieve it. IEEE Military Communications Conference (MILCOM 2008); 2008 November 16-19, San Diego, CA.

Additional information

Focus Areas

Our work is centered around a series of Focus Areas that we believe are the future of science and technology.

Licensing & Commercialization Opportunities

We’re continually developing new technologies, many of which are available for¬†Commercialization.


PARC scientists and staffers are active members and contributors to the science and technology communities.