A unifying perspective on the capacity of wireless ad hoc networks


Event IEEE Infocom 2008


Garcia-Luna-Aceves, J J.
Technical Publications
April 13th 2008
We present the first unified modeling framework for the computation of the throughput capacity of random wireless ad hoc networks in which information is disseminated by means of unicast routing, multicast routing, broadcasting, or different forms of anycasting. We introduce $(n,m,k)$-casting as a generalization of all forms of one-to-one, one-to-many and many-to-many information dissemination in wireless networks. In this context, $n$, $m,$ and $k$ denote the total number of nodes in the network, the number of destinations for each communication group, and the actual number of communication-group members that receive information (i.e., $k leq m$), respectively. We compute upper and lower bounds for the $(n,m,k)$-cast throughput capacity in random wireless networks. When $m= k = Theta(1)$, the resulting capacity equals the well-known capacity result for multi-pair unicasting by Gupta and Kumar. We demonstrate that $Theta ( 1/ sqrt{mnlog n} )$ bits per second constitutes a tight bound for the capacity of multicasting (i.e., $m = k < n$) when $mle Theta left( n/(log n) right)$. We show that the multicast capacity of a wireless network equals its capacity for multi-pair unicasting when the number of destinations per multicast source is not a function of $n$. We also show that the multicast capacity of a random wireless ad hoc network is $Theta left(1/n right)$, which is the broadcast capacity of the network, when $m ge Theta ( n/ log n )$. Furthermore, we show that $ Theta (sqrt{m}/(ksqrt{nlog n}) )$, $Theta ( 1/(k log n) )$ and $Theta ( 1/n )$ bits per second constitutes a tight bound for the throughput capacity of multicasting (i.e., $k< m < n$) when $Theta(1)le mle Thetaleft(n/log nright)$, $kleThetaleft(n/log nright)le mle n$ and $Thetaleft(n/log nright)le kle mle n$, respectively.


Wang, Z.; Sadjadpour, H.; Garcia-Luna-Aceves, J. J. A unifying perspective on the capacity of wireless ad hoc networks. Proceedings of the 27th IEEE Conference on Computer Communications (Infocom 2008); 2008 April 13-18; Phoenix, AZ. Piscataway, NJ: IEEE; 2008; 211-215.

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.