Subject: Re: The throughput that can be provided by wireless networks

From: "P. R. Kumar" <[email-masked]>
Date: Thu, 3 Dec 1998 15:19:55 -0600 (CST)

First, I would like to thank Dr. Carlberg for his comments.

At the outset I should mention that the results apply only to the case
of omni-directional type transmissions.
If precise directed transmissions are used, then wireless networks behave like 
wired ones, and the throughput bound does not apply.
(Actually for the results below to hold we do not need fully omni-directional 
transmissions. We just need that the transmissions are not precisely aimed at
just the receiver).

With that in mind, please consider any framework which meets the following 
assumptions:

(i) There are $n$ nodes arbitrarily located in a disk of unit area on the plane.

(ii) The network transports $\lambda n T$ bits over $T$ seconds.
(Different bits may have different source-destination pairs).

(iii) The average distance between the source and destination of a bit is $L$.

(iv) Each node can transmit over any subset of $M$ sub-channels with capacities
$W_m$ bits/sec, $1 \leq m \leq M$, where $\sum_{m=1}^M W_m = W$.
(This is explained below).

(v) Transmissions are slotted into synchronized slots of length $\tau$ secs.
(This assumption can be eliminated, but makes the exposition easier).

(vi) If a node $X_i$ transmits to another node $X_j$ located at a distance
of $r$ units on a certain sub-channel in a certain slot, then there can be no 
other receiver
within a radius of $\Delta r $ around $X_j$ on the same sub-channel in the same 
slot.
(This will not hold if transmissions are precisely directed from a transmitter 
to a receiver, as for example in a microwave link).

Now for some explanation as to what we allow in (iv).
Let us suppose that there is an overall frequency band available which can 
transmit $W$  bits/sec.
Let us suppose that using CDMA, or TDMA, or FDMA, it has been subdivided into
M separate "sub-channels."
For concreteness, let us say that FDMA is being used.
Then there are M bands into which the original large band has been split.
Each band is what we mean by a "sub-channel."
(If CDMA is being used, a "sub-channel" would correspond to a "code.")
Let us suppose that the $m$-th band can transmit at $W_m$ bits/sec.
Note that $\sum_{m=1}^M W_m = W$.

Now for (vi).
This assumption basically stipulates when "collisions" will not occur between
two transmissions over the same band in the same slot.
Suppose node $X_i$ is transmitting to node $X_j$ over a certain band
in a certain slot.
Suppose that the distance between $X_i$ and $X_j$ is $r$.
Then we are making the assumption that this transmission will be very disruptive 
to nodes within a range $\Delta r$ of $X_j$ (for some $\Delta > 0$),
so that those nodes so close to $X_j$ cannot receive
any other transmission successfully over the same band in the same slot.
Please note that this rules out very precise directed transmissions since then
it is as though the two nodes are connected by a "wire."

Under assumptions (i)-(vi) it can be shown that the $\lambda$ is less than 
$O( 1/sqrt(n) )$.
More precisely, the upper bound on $\lambda$ is
$sqrt(8/pi) (W/(Delta L)) (1/sqrt(n))$.

In fact we can look at the product of the bits carried and the
distance travelled by a bit, the "bit-distance" product, which
is a valuable indicator of the network performance.
The result above shows that even if the demands on the network
are arbitrarily distributed, the network cannot transport more than
$sqrt(8/pi) (W/Delta) (1/sqrt(n))$ BIT-METERS/SEC.

The proof of all this is in Section 15 of the paper available at:
http://black.csl.uiuc.edu/~prkumar/capacity.ps

Actually even more results are in the paper.
If the nodes are randomly located, and all have the same range, then
the throughput is less than $O( 1 / ( sqrt (n log n) ) )$.
In fact we show that this order is sharp.
There is a constructive scheme for achieving this capacity.
This scheme also does not need to split the overall
channel into many sub-channels.

The results show that the throughput that can be provided to nodes
can be increased only in one of two ways:
(i) Reducing $\Delta$, that is targeting transmissions carefully
to include only the intended receiver, since two-dimensional space
is also a valuable resource. 
(ii) Reducing $L$. This corresponds to sources only needing to
communicate with nearby receivers.

Any further comments will be appreciated, since there may still be 
some room for confusion, and the language I am using may not be typical.

Best Regards,  Kumar
----------------------------------------------------

> X-Unix-From: [email-masked]  Thu Dec  3 08:09:22 1998
> X-BadHeader: Thu Dec  3 08:09:22 1998
> To: "P. R. Kumar" <[email-masked]>
> cc: [email-masked], [email-masked]
> Subject: Re: The throughput that can be provided by wireless networks 
> Mime-Version: 1.0
> 
> Hello,
> 
> at the risk of speaking for kimberly, i have a couple of comments. 
> first, thanks. you've given some of us some interesting to chew on
> and a tangible notation to play with.
> 
> as for the following...
> 
> 
> > whether the results on the throughput that can be provided by 
> > wireless networks even apply when multiple technologies are used for 
routing.
> > 
> > The results do apply. It does not matter if the channel is split into
> > several subchannels.
> 
> i'm not sure i understand the context you speak of when you refer to
> 'multiple technologies' and splitting _a_ channel to several subchannels.
> 
> MANET's charter focuses on IP, implying that the solution space for ad-hoc 
> networks is targeted at IP and not a specific subnet technology.  and
> granted, the limitations of the physical subnet(s), as in plural, can be 
> expected to affect the throughput and effectiveness of a MANET protocol.
> 
> but when i think of MANET and different technologies, i think of cases 
> where a wireless IP network can be comprised of omni-directional and
> directional links (eg, routers that have UHF and L-band interfaces).
> certainly, in the military, these type of cases exist today, and i think
> a commercial case can be made for this scenario as well.
> 
> hence, i think your paper tells us a worst case scenario for a single
> technology (i.e., single frequency range) system and all the entities
> that reside within it.
> 
> cheers,
> 
> -ken
> 
> 
--------------
P. R. Kumar
Professor, Dept. of Electrical and Computer Engineering, and
Research Professor, Coordinated Science Lab

Univ. of Illinois			Off: 217-333-7476
CSL      				Sec: 217-333-0282
1308 West Main St			Fax: 217-244-1653
Urbana, IL 61801			WWW: http://black.csl.uiuc.edu/~prkumar