Subject: Re: Ad Hoc Network Scalability

From: [email-masked]
Date: Thu, 28 Jun 2001 19:21:11 +0200

It is clear that multihop impacts the performance. 

In a recent paper (in information theory, I must look in my records), it is
shown that the percentage of throughput in an ad hoc network of N users is
at best of order 1/sqrt(N) in a 2D network with power law signal
attenuation. The impact of routing makes that each packet has to be routed
in an average of sqrt(N) hop. 

If the traffic would have been local (i.e. directed to neighbor), then the
average percentage traffic per node would be O(1) due to spatial reuse.
This is not too bad, since if the network would have been connected on a
single Ethernet hub, then the percentage would have been O(1/N). Notice
that even with routing overhead, the ad hoc network does better than the
Ethernet hub. 

This result is attainable because when the traffic density increases, the
distance between hops decreases and spatial reuse is possible.
Unfortunately this is not completely possible with IEEE 802.11 because the
CSMA carrier sense level is fixed and prevent close spatial reuse. To
obtain theoretical bounds  one should need at least a tunable carrier sense
level. 

Philippe 

A 15:36 27/06/01 -0400, Phillip Neumiller a écrit :
>Hello,
>
>In the paper found at http://www.pdos.lcs.mit.edu/papers/grid:mobicom01/
>"Capacity of Ad Hoc Networks" from MIT labs for CS, the paper concludes
>that the "key factor" determining whether large ad hoc networks are feasible
>
>is the locality of traffic (which results in fewer hops on average between
>communicators).
>
>Have others found this to be the "key factor" in ad hoc network feasibility?
>
>It would seem to me, that "WHAT" the key factor is would depend somewhat
>on the network architecture being analyzed and specifically it would depend
>heavily on the MAC implementation.  It seems to me that this paper may
>have been more appropriately titled "Capacity of Ad Hoc 802.11 Wireless
>Networks".  Is it generally agreed that the 802.11 MAC can adequately
>represent what the "key scalability factors" are?  I think the 802.11 MAC
>is expedient but not necessarily that useful for generalized analysis.  Is
>there such a thing as a perfect MAC model?, i.e. a MAC that achieves X%
>efficiency (my guess is its just a circuit switch big enough to connect 
>everyone to everyone else n(n+1)/2!!!).  This would not be very practical
>in an RF MANET so there must be some happy medium (pun intended)!
>
>Thanks,
>
>Phil Neumiller
>

---

From: Joe Macker <[email-masked]>
Date: Fri, 29 Jun 2001 10:57:52 -0400

>in an average of sqrt(N) hop.

Gupta and Kumar, IEEE transactions on Information Theory, vol IT-46, no.2, 
pp 388-404, March 2000.