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) of which one usually immediately starts to think of when one hears about capacity problem and Wifi.

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.

This article tries to explain the problem in simple words without proving it mathematically. If you are looking for an in-depth explanation of the topic I highly recommend reading the two papers which can be found in the References section.

MANET with optimally and randomly 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 added node expands the area of the net, i.e. each new node is added to the edge of the existing net
3. 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 its 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 the underlying transport medium (e.g. 11Mbit/s for 802.11b Wifi).

Illustrating example

Imagine a net whose transport medium is capable of 11 Mbit/s (e.g. 802.11b). If this net consists of 100 nodes the total end-to-end throughput available to each node is theoretically at best 1.1 Mbit/s (in practice it would be much less):
$\Theta =\left({\frac {11Mbit/s}{\sqrt {100}}}\right)=1.1Mbit/s$
If the net increased to 1000 nodes the throughput available to each node would decrease to about 0.34 Mbit/s:
$\Theta =\left({\frac {11Mbit/s}{\sqrt {1000}}}\right)\approx 0.34Mbit/s$
Please bear in mind that this capacity needs to include all kinds of protocol overhead (e.g. MAC, IP, TCP or UDP etc.) and would also be subjected to other problems (e.g. the interference problem, that two neighboured nodes cannot transmit at the same time).

MANET with randomly placed nodes

In a randomly chosen network with

• n identical randomly located nodes
• fixed transmission range
• randomly chosen destination (likely far away destinations)
• interference issues are again neglected

we get at best the following total end-to-end throughput available to each node:
$\Theta =\left({\frac {W}{\sqrt {n\cdot log(n)}}}\right)$
Explaining this result would be beyond the scope of this article. If you are interested in how this is derived, you should read this paper.

Ways out of the capacity limitations

Questioning the results

As one can see this is quite bad news and very much against the intuitive ideas I pointed out at the beginning of this article. This is especially bad, since capacity is (as far as we know today) the limiting factor in manets. Take this as an example: Due to mobility of the nodes, there is link breakage, which in turn causes routing queries (bursty traffic) depending on the routing protocol. This again causes congestion. Finally, the result will not just be some dropped data packets but loss of routing information and further misrouting.

However, as with most good theories there might be some hope in questioning the taken assumptions. Do these assumptions really apply to the real world scenarios? Let's concentrate on the following assumption:

• each node wishes to communicate with each other node equally often

This means that the load on each node increases with the distance each node wishes to communicate (due to the multi hop nature of manets). However, is it really justified to assume that each node wishes to communicate with each other node equally often? Wouldn't it be much more likely, that a node's end-point of communication is a nearby node, say a neighbour?

Dependence on traffic patterns

As I pointed out the above results are probably dependant on the Traffic pattern. Remember the following assumptions, which were necessary for the depressing capacity result:

• the node density δ within the net is constant which means that:
  $A={\frac {n}{\delta }}$
• the total capacity of net grows linear with area:
  $C=k\cdot A=k\cdot {\frac {n}{\delta }}$ (where k is a constant)
• the radio transmission range is fixed, therefore:
  $MinimumNumberOfHops={\frac {L}{r}}$
  (where r is fixed radio transmission range, and L is the average path length)
• assume that each node originates packets at rate λ , then the total capacity required to send and forward packets must be at least:
  $C>n\cdot \lambda \cdot MinimumNumberOfHops$      or
  $C>n\cdot \lambda \cdot L/r$

Combining these assumptions one ends up with:
$k\cdot {\frac {n}{\delta }}>n\cdot \lambda \cdot L/r$
Of course, we are most interested in how much the capacity available to each node depends on the average path length. Therefore, we shuffle the equation as long as we get this:
$\lambda <{\frac {k\cdot r}{\delta }}\cdot {\frac {1}{L}}$         or
$\lambda <{\frac {C/n}{L/r}}$

Here $k\cdot r,\ \delta \ and\ C/n$ are constant. Only L (the average path length) is variable.

As one can see the obtainable throughput available to each node decreases with an increase of the average path length. So the capacity available to each node is very much dependent on the traffic patterns. If nodes primarily wish to communicate to far away nodes, the throughput will diminish rapidly. However, if the traffic remains primarily local, then the capacity will also remain almost constant.

References

This article is very much based on the following two papers:

• The capacity of wireless networks
• Capacity of Ad Hoc Wireless Networks

You also might want to have a look at my lecture on the same topic.