WirelessNetworksCapacity

Foreword

To make it very clear at the beginning: The capacity problem as presented in this article is not mainly related to wireless networks but rather to all kind of peer-to-peer networks. That is, the presented capacity problem does not only occur in wireless networks but in all kind of multihop networks, which are organised in a peer-to-peer manner. So this has nothing to do with the interference problems (e.g. hidden node, exposed node).

Intuitively, one could think that the more nodes join a wireless peer-to-peer net, the more capacity is available to each node. This maybe naive idea is somewhat lead by assuming that more nodes mean more redundant routes, which in return means more transportable traffic. In the end, this article tries to explain why this is not true.

I would also like to mention that this article is very much based on two papers, which can be found in the references section.

MANET with optimally and radomly placed nodes

In the following we will look at to the following two distinct setups of wireless ad-hoc networks. First we will consider a MANET with optimally placed nodes. Then we will look at how the capacity available to each node evolves when the nodes are randomly placed.

MANET with optimally placed nodes

Let's consider a MANET with optimally placed nodes.

Assumptions

In order to draw our conclusion the following assumptions are made:

1. each node's transmission range is optimally chosen
2. each node wishes to communicate with each other node equally often

Conclusions

Regarding these assumptions we can draw the following conclusions:

1. The total one-hop capacity of an optimal net grows linearly with the area of the net. That is, if nodes are added to the net, the total capacity of the net increases linearly. This is because each added node is placed to the edge of the network, increasing the area of the net, due to the optimal characteristics of this kind of net. Therefore, an added node also adds his capacity part to the total capacity of the network.
   Here we assume a constant node density (and as said in the foreword we neglect interference issues).
   To put it more mathematically we can say that the total number of bits that can be transported by the net obeys to $O(n)$, where n stands for the number of nodes.
2. Since each node wishes to communicate with each other node equally often (see the made assumptions), the average path length grows linearly with the diameter of the area of the net. As you might still know from your math classes at school the diameter and the area obey to the following equations:
   $A=r^{2}\cdot \Pi =\left({\frac {d}{2}}\right)^{2}\cdot \Pi$
   $d=2\cdot {\sqrt {\frac {A}{\Pi }}}$
   Here π and the number 2 are constant -- only A is variable. Hence, the diameter d is dependent on the sq root of the area A. Therefore, we can conclude that (taken the assumptions) the average path length grows with the square root of the area. The area itself is linearly dependent on the total number of nodes in the net. Hence the average path length (or number of hops, respectively) grows with
   $O\left({\sqrt {n}}\right)$
3. Considering the above two conclusions one can see that the total end-to-end capacity is the total one-hop capacity divided by the average path length (or number of hops, respectivly):
   $O\left({\frac {n}{\sqrt {n}}}\right)$
4. Hence, the total end-to-end capacity available to each node is the total end-to-end capacity divided by the number of nodes n:
   $O\left({\frac {n}{\sqrt {n}}}\cdot {\frac {1}{n}}\right)=\left({\frac {1}{\sqrt {n}}}\right)$
   So assuming the given assumptions the optimal end-to-end throughput available to each node in a manet is:
   $\Theta =\left({\frac {W}{\sqrt {n}}}\right)$
   where W stands for the maximum capacity of transport medium (e.g. 11Mbit/s for 802.11b Wifi).