Capacity of Mobile Ad-hoc Networks

Wireless devices are bound to become smaller and more pervasive; they will not only be carried by humans, but integrated into physical objects (such as cars, electrical appliances, etc.) It is unlikely that the density of base-stations will keep pace, due to cost as well as regulatory and environmental hurdles in deploying them. This problem could be alleviated through ad-hoc networking, where nodes (wireless terminals) can act as relays for traffic on behalf of other nodes; it is then unnecessary for a basestation to directly communicate with every node in its cell.

However, concurrent wireless transmissions in an ad-hoc network limit its throughput capacity, because they create mutual interference. In fact, Gupta and Kumar have recently analyzed this capacity in an analytical model of fixed ad-hoc networks, where nodes are randomly located but are immobile. Their main result shows that as the number of nodes n per unit area increases, the throughput per node goes to zero. This pessimistic result suggests that large ad-hoc networks are impractical.

On the other hand, wireless data services are expected to grow quickly over the next few years. Some of these services, such as email, paging, or database synchronization, possess very loose delay constraints (on the order of minutes to hours). In our work, we show that such delay-tolerant applications can exploit node mobility to increase capacity through a new type of multiuser diversity. Specifically, our main result shows that if nodes are mobile, the average long-term throughput per node can be kept constant even as the number of nodes n increases. This is in sharp contrast to the fixed network scenario, and the dramatic performance improvement is obtained through the exploitation of the time-variation of the users' channels due to mobility. This is an important architectural insight, as it suggests that ad-hoc networks (or hybrid ad-hoc/cellular networks) may be a much more viable alternative for delay-tolerant data applications than for telephony.

M. Grossglauser and D. Tse, "Mobility Increases the Capacity of Adhoc Wireless Networks", IEEE/ACM Transactions on Networking, vol. 10, no. 4, August, 2002, pp. 477-486.

This result assumes that each node moves randomly in the 2-D plane. In subsequent work, we showed that the result continues to hold even when each node's mobility pattern is much more restricted.

R. S. Diggavi, M. Grossglauser and D. Tse, " Even One-Dimensional Mobility Increases Adhoc Wireless Capacity" , submitted to the IEEE Transactions on Information Theory, August 2003.

For a quick overview of the basic ideas, see the following presentation:

"Multiuser Diversity in Wireless Networks: Smart Scheduling, Dumb Antennas and Epidemic Communication", IMA Wireless Workshop, Minneapolis, August 10, 2001.

This work is supported by the National Science Foundation under grant #ANI-9814567.