From eyh5@ee.cornell.edu Wed Oct 24 20:36:29 2001
Return-Path: <eyh5@ee.cornell.edu>
Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8])
by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9P0aTo22544
for <egs@cs.cornell.edu>; Wed, 24 Oct 2001 20:36:29 -0400 (EDT)
Received: from james (james.ee.cornell.edu [128.84.236.65])
by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9P0aqN06629
for <egs@cs.cornell.edu>; Wed, 24 Oct 2001 20:36:52 -0400
Date: Wed, 24 Oct 2001 20:35:13 -0400 (EDT)
From: Edward Hua <eyh5@ee.cornell.edu>
To: egs@CS.Cornell.EDU
Subject: 615 Paper # 46
Message-ID: <Pine.GSO.4.21.0110242034390.18644-100000@james.ee.cornell.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Capacity of Ad Hoc Wireless Networks
Jinyang Li, Charles Blake, Douglas S.J. De Couto, Hu Imm Lee, Robert
Morris
This paper aims to address the capacity in the ad hoc wireless
networks. An a priori key assumption made is that the ad hoc network,
although dynamic in nature, can be viewed as static when evaluating its
capacity, since in most scenarios, nodes do not travel significant
distances during packet transmissions. Although this assumption can be
justified in this paper, not all scenarios of ad-hoc mobile networks may
fit this criterion. Throughout the evaluations of ad hoc network capacity,
the measurements are benchmarked against the single-hop throughput.
Several conclusions are drawn from the analysis of ad hoc network
capacity:
1)802.11 MAC is capable of sending at the optimal rate, but does
not discover the optimum schedule of transmissions on its own. This
inability is caused by the amount of competition the sender experiences,
which prevents it from injecting more packets into the network.
2)An ideal ad hoc forwarding chain (i.e., a chain of forwarding
nodes along the path) should be able to achieve one quarter of the
throughput that a single-hop transmission can achieve. But the 802.11 MAC
protocol is able to handle only one-seventh of the single-hop throughput.
3)When the network nodes are in an orderly fashion, carrying
orderly traffic patterns, the 802.11 MAC protocol is more efficient, and
the per-hope throughput remains relatively constant. On the other hand, in
an environment of random node placement and random traffic pattern, as the
path length increases, the bandwidth available for each node to originate
packets decreases.
One contribution given in the paper is that is provides a
mathematical formula to calculate the expected path length between any
source-destination pair in an ad hoc network. This length is influenced by
two parameters: the locality index and the total area of the network
coverage. This formula may be helpful in assisting the network designer to
assess the optimal nodal placement and density in an ad hoc network.
From wbell@CS.Cornell.EDU Wed Oct 24 22:06:50 2001
Return-Path: <wbell@CS.Cornell.EDU>
Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7])
by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9P26no01929
for <egs@cs.cornell.edu>; Wed, 24 Oct 2001 22:06:49 -0400 (EDT)
Received: from [192.168.1.100] (syr-66-24-16-64.twcny.rr.com [66.24.16.64])
by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id WAA10649
for <egs@cs.cornell.edu>; Wed, 24 Oct 2001 22:06:32 -0400 (EDT)
Subject: 615 PAPER #46
From: Walter Bell <wbell@CS.Cornell.EDU>
To: egs@CS.Cornell.EDU
Content-Type: text/plain
Content-Transfer-Encoding: 7bit
X-Mailer: Evolution/0.16.99+cvs.2001.10.18.15.19 (Preview Release)
Date: 24 Oct 2001 22:06:10 -0400
Message-Id: <1003975600.1044.72.camel@brute>
Mime-Version: 1.0
46) Capacity of Ad Hoc Wireless Networks
This work presents a highly theoretical and math oriented analysis of
the overall capacity of wireless networks. They analyze so called
'arbitrary' networks where nodes are randomly located in a disk of
unit area in the plane and have an arbitrary destination to which they
wish to send traffic at an arbitrary rate. They analyze situations in
terms of the protocol model and the physical model, which are models
for successful reception of a packet from a source to a
destination. The protocol model simply says that the packet is
received if the distance between source and destination is smaller
than any other source sending to this destination, the packet is
received. The physical model more closely models the physical layer
and is represented by a distance fall off equation for the signal
strength. Any signal received above a threshold is received.
They show that under the protocol model, if each node has a
transmission capacity of W, and all nodes are optimally places, the
traffic pattern is optimal, and the range of transmission is optimal,
a throughput of O(W\sqrt{n}) is achievable. They present the insight
that wireless networks throughput decreases with the number of nodes
if the communication distance increases with the number of nodes,
therefore it is crucial to scalability to limit the number of hops
communication must travel as the network grows. They also note that
adding pure relay nodes to the network doesn't make the problem any
better, as kn relays are added to the network, the throughput of the
network only increases \sqrt{k+1} fold.
This paper presents strong arguments that highly scalable ad-hoc
networks are likely only possible given short communication distances
and therefore compel routing algorithms to utilize this fact in
improving protocols, as information about distant hosts is unlikely to
be used in a successful large ad-hoc network.
From papadp@ece.cornell.edu Thu Oct 25 10:12:45 2001
Return-Path: <papadp@ece.cornell.edu>
Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8])
by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PECio21965
for <egs@CS.Cornell.EDU>; Thu, 25 Oct 2001 10:12:45 -0400 (EDT)
Received: from hegel (hegel.ee.cornell.edu [128.84.236.63])
by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9PED5N17422;
Thu, 25 Oct 2001 10:13:05 -0400
Date: Thu, 25 Oct 2001 10:12:24 -0400 (EDT)
From: "Panagiotis (Panos) Papadimitratos" <papadp@ece.cornell.edu>
X-Sender: papadp@hegel.ee.cornell.edu
To: Emin Gun Sirer <egs@CS.Cornell.EDU>
cc: Panagiotis Papadimitratos <papadp@ece.cornell.edu>
Subject: 615 PAPER 46
Message-ID: <Pine.GSO.4.21.0110250940200.19832-100000@hegel.ee.cornell.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Review of "Capacity of Ad Hoc Wireless Networks," by J. Li, R. Morris et
al.
papadp@ece.cornell.edu Panagiotis Papadimtratos
The authors examine the limitations imposed on ad hoc multihop topologies
due to the use of a shared channel. They investigate the forwarding
capability of a 802.11-based MANET without the presence of a routing
protocol, which would simply impose additional tranmsission overhead. If
the packet size of all traffic is assumed the same, then the presence of a
routing protocol does not have a qualitative impact.
First, a detailed study of the interactions between node transmissions is
provided, over different types of topologies. The coupling of concurrent
transmissions is shown through simulations for three different topologies:
chain, sets of vertical/horizontal chains and grid. The theoreticaly
(given the coupling) maximum throughput is not achieved by 802.11 under
uniform load conditions. Nonetheless, it is approached when the pattern is
randomized.
This is the main contribution of this work: they provide an upper bound
that incorporates the effect of the communication pattern on capacity,
i.e., the achieved transmission rate per node. Their formulation under
some assumptions matches the upper bound given by [Kumar] but with an
arbitrary pdf (i.e., non uniform) modeling the communiation pattern, they
indicate that the highest achievable throughput can exceed the
O(1/sqrt(n)) bound. This is due to the locality of communication, and the
reduced average path length leads to the increased achievable througput.
An interesting point (not very well-supported though) is that the
'shortest path routing' (e.g., min-hop, or geographcal routing) is in
accordance with the upper bound formulation, which seems to me that it
brings route optimality back into the game.
From daehyun@csl.cornell.edu Thu Oct 25 11:11:55 2001
Return-Path: <daehyun@csl.cornell.edu>
Received: from wilkes.csl.cornell.edu (wilkes.csl.cornell.edu [132.236.71.69])
by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PFBto00068
for <egs@cs.cornell.edu>; Thu, 25 Oct 2001 11:11:55 -0400 (EDT)
Received: (from daehyun@localhost)
by wilkes.csl.cornell.edu (8.9.3/8.9.2) id LAA11999
for egs@cs.cornell.edu; Thu, 25 Oct 2001 11:11:50 -0400 (EDT)
(envelope-from daehyun)
From: Daehyun Kim <daehyun@csl.cornell.edu>
Message-Id: <200110251511.LAA11999@wilkes.csl.cornell.edu>
Subject: 615 PAPER 46
To: egs@CS.Cornell.EDU
Date: Thu, 25 Oct 2001 11:11:49 -0400 (EDT)
X-Mailer: ELM [version 2.4ME+ PL54 (25)]
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
This paper is a simulation/analysis study on the capacity of ad hoc
wireless networks. They changed simulation parameters such as network size,
traffic patterns and local radio interactions, and analyzed the results.
They even validate some simulation results with experiments.
This paper showed that the capacity of networks highly depends on the
traffic pattern. If the distance between the source and the destination
does not remain small, the capacity can not be scaled up with the
network size. Therefore, the feasibility of large ad hoc networks is
determined by the locality of traffic.
In my opinion, the main contribution of this paper is that it analyzed
the relationship between traffic pattern and network capacity.
Other papers we have talked used very simple traffic patterns and did
not pay attention to the network capacity much. But this paper showed
this feature clearly, which can be used for the future protocol
development.
One think I'd like to point out is that this paper assumed static
ad hoc network. Their reason for this assumption is that nodes do
not move much during packet transit times. But, I think this might
be over-simplified. As far as I know, any intensive study on the
characteristics of ad hon network traffic has not be done yet. I
think such studies should be done first, Before this kind of
assumption is made.
From jcb35@cornell.edu Thu Oct 25 11:34:34 2001
Return-Path: <jcb35@cornell.edu>
Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7])
by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PFYYo02940
for <egs@cs.cornell.edu>; Thu, 25 Oct 2001 11:34:34 -0400 (EDT)
Received: from localhost.localdomain (syr-66-66-30-147.twcny.rr.com [66.66.30.147])
by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA12074
for <egs@cs.cornell.edu>; Thu, 25 Oct 2001 11:34:33 -0400 (EDT)
Received: from localhost (john@localhost)
by localhost.localdomain (8.11.0/8.11.0) with ESMTP id f9PFbUL03923
for <egs@cs.cornell.edu>; Thu, 25 Oct 2001 11:37:31 -0400
Date: Thu, 25 Oct 2001 11:37:29 -0400 (EDT)
From: "John C. Bicket" <jcb35@cornell.edu>
To: egs@CS.Cornell.EDU
Subject: 615 paper 46
Message-ID: <Pine.LNX.4.21.0110251111290.3914-100000@localhost.localdomain>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
This paper further elaborates on the capacity on ad hoc wireless
networks. Specifically, they look at how the traffic pattern determines
the capacity of ad hoc networks, and indicated that large ad hoc networks
are feasible if most of the communication is local.
The first investigation this paper undertakes is the capacity of
"chained" nodes, where each node is not mobile. They show that because a
node's ability to send in 802.11 is affected by the amount of competition
it experiences - a node can inject more packets into an network than the
subsequent nodes can forward, and they get dropped as a result.
The paper also considers how 802.11's back off performs poorly - They
mention that a node may exponentially back off one of its timers when a
RTS packet is corrupted by a hidden terminal.
Next their analysis turns to lattice networks (ie chains but with 2
dimensions), and find the same problems as in the chain networks. They
then evaluate how these results carry over into a graph with random
traffic and random layout, where they determine that the capacity
available to each node is explicitly dependent on the expected path
length. They then find that with either bounded paths lengths or
probabilistically short paths, ad hoc networks do not have unrealistically
low capacity.
comments:
I would like to see some analysis in mobile environments, but I think that
using a static network provides a good upper bound, and I thought it was
a key insight that capacity depends on the locality of communication.
From avneesh@csl.cornell.edu Thu Oct 25 11:57:03 2001
Return-Path: <avneesh@csl.cornell.edu>
Received: from capricorn.ds.csl.cornell.edu (capricorn.csl.cornell.edu [132.236.71.92])
by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PFv3o06269
for <egs@cs.cornell.edu>; Thu, 25 Oct 2001 11:57:03 -0400 (EDT)
content-class: urn:content-classes:message
Subject: 615 Paper 46
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Date: Thu, 25 Oct 2001 11:58:19 -0400
Message-ID: <97C142C1212ED545B0023A177F5349C4053B04@capricorn.ds.csl.cornell.edu>
X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Thread-Topic: 615 Paper 46
Thread-Index: AcFdbd3pf86mURwLQjaUmr8RpEJ+aw==
From: "Avneesh Bhatnagar" <avneesh@csl.cornell.edu>
To: <egs@CS.Cornell.EDU>
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f9PFv3o06269
Capacity of Wireless Networks.
This paper evaluates a theoretical limit on the capacity of adhoc
wireless networks. Two models are assumed: the arbitrary and random, but
both in a static setting. The efficacy of MAC forwarding and 802.11
routing is evaluated under a horizontal flow and both horizontal and
vertical grid flow model, thus establishing a upper and lower bound on
the throughput possible and what kind of scheduling would enable this.
Some results:
a. 802.11 can send at the optimum rate but cannot find the right
schedule.
b. Throughput for a single chain is 1/7 insteafd of the expected 1/4.
c. Increase in path length decreases available bandwidth.
I think that since the paper was entirely theoretical, the authors have
done a good job defining the upper and lower limits. However since my
knowledge as to the basis of the assumpotions in these evaluations is
limited, the only queries that I have are:
a. Static model: It would be interesting to know why the paper takes
this assumption and why could'nt a mobility model have been strapped
onto these evaluations.
b. There are horizontal and vertical chains that were considered for
this study. Why could'nt any other model be chosen?
From c.tavoularis@utoronto.ca Thu Oct 25 12:04:34 2001
Return-Path: <c.tavoularis@utoronto.ca>
Received: from bureau6.utcc.utoronto.ca (bureau6.utcc.utoronto.ca [128.100.132.16])
by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PG4Yo07456
for <egs@cs.cornell.edu>; Thu, 25 Oct 2001 12:04:34 -0400 (EDT)
Received: from webmail3.ns.utoronto.ca ([128.100.132.26] EHLO webmail3 ident: IDENT-NOT-QUERIED [port 64811]) by bureau6.utcc.utoronto.ca with ESMTP id <240592-28258>; Thu, 25 Oct 2001 12:04:18 -0400
Received: by webmail3.ns.utoronto.ca id <414676-224>; Thu, 25 Oct 2001 12:04:11 -0400
To: COM S 615 <egs@CS.Cornell.EDU>
Subject: 615 PAPER 46
Message-ID: <1004025848.3bd837f8e5083@webmail.utoronto.ca>
Date: Thu, 25 Oct 2001 12:04:08 -0400 (EDT)
From: c.tavoularis@utoronto.ca
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
User-Agent: IMP/PHP IMAP webmail program 2.2.3
Scalability is a factor of network size, traffic patterns, local interaction
and MAC layer interaction of the routing protocol. This paper addresses the
effects of the MAC and routing layer interaction on ad hoc network capacity. It
also determines the communication patterns that allow scalability. The authors
consider a single shared channel and a static wireless network.
The authors determine the network capacity limited only by the 802.11 MAC layer
contention through a chain of nodes. A chain of nodes has ultimate throughput
1/3 since successive nodes must wait for each other to transmit, causing
delays. Allowing interference further deteriorates performance due to
collisions. Simulation results show even worse throughputs, down to 1/7 of
1.7Mbps. This decrease in performance is due to unfair contention since the
source node has less contention than intermediate nodes (by symmetry) and
therefore can �overload� the forwarding nodes with traffic, while also delaying
them from transmitting. The exponential backoff scheme in 802.11 is also
disadvantageous since it results in periods of time when the channel is not
being used. The authors then consider a square lattice network with horizontal
and vertical traffic flows. Similar yet worse results are observed such that
source nodes experience less contention than forwarding nodes, and exponential
backoff periods are wasteful. In a random situation with predetermined routes
(no routing protocol present), the throughput degrades even more, mainly due to
areas of the network lacking in forwarding nodes.
To study the capacity of an entire large network, the authors scale a network
such that traffic increases with number of nodes and distance. Capacity is
found to decrease with the length of the path and is therefore dependent on the
traffic pattern. The most scalable traffic patterns occur when source
destination pairs are within a local vicinity of each other. This also
demonstrates the importance of choosing a shortest path when routing.
The intuition is that ad hoc networks scale well because of spectral reuse, but
increasing the number of nodes also increases forwarding load per node. In
fact, ad hoc networks scale well when they behave as a set of overlapping sub-
networks. Capacity of networks is an important issue, since it limits causes
congestion, deteriorating performance. This study shows the importance of the
MAC layer in routing, and demonstrates that 802.11 does not significantly
hinder capacity.
From viran@csl.cornell.edu Thu Oct 25 12:09:41 2001
Return-Path: <viran@csl.cornell.edu>
Received: from moore.csl.cornell.edu (moore.csl.cornell.edu [132.236.71.83])
by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PG9fo08033
for <egs@cs.cornell.edu>; Thu, 25 Oct 2001 12:09:41 -0400 (EDT)
Received: from localhost (viran@localhost)
by moore.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f9PG9ZD15774
for <egs@cs.cornell.edu>; Thu, 25 Oct 2001 12:09:35 -0400 (EDT)
(envelope-from viran@moore.csl.cornell.edu)
X-Authentication-Warning: moore.csl.cornell.edu: viran owned process doing -bs
Date: Thu, 25 Oct 2001 12:09:35 -0400 (EDT)
From: "Virantha N. Ekanayake" <viran@csl.cornell.edu>
To: <egs@CS.Cornell.EDU>
Subject: 615 Paper 46
Message-ID: <Pine.BSF.4.33.0110251209030.14081-100000@moore.csl.cornell.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
This paper tries to simplify the results obtained in the earlier Gupta
paper on capacity, in context of 802.11 and different traffic patterns.
They show how the expected bandwidth isn't as bad as predicted by Gupta et
al. as long as the traffic patterns are predominantly local.
The paper was very clear, and had an excellent example of how inteference
can affect the throughput of wireless networks. They also took into
account how the 802.11 backoff scheme, and rts/cts signalling affects
throughput.
From teifel@csl.cornell.edu Thu Oct 25 12:22:23 2001
Return-Path: <teifel@csl.cornell.edu>
Received: from disney.csl.cornell.edu (disney.csl.cornell.edu [132.236.71.87])
by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PGMNo09668
for <egs@cs.cornell.edu>; Thu, 25 Oct 2001 12:22:23 -0400 (EDT)
Received: from localhost (teifel@localhost)
by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f9PGMH770651
for <egs@cs.cornell.edu>; Thu, 25 Oct 2001 12:22:17 -0400 (EDT)
(envelope-from teifel@disney.csl.cornell.edu)
X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs
Date: Thu, 25 Oct 2001 12:22:17 -0400 (EDT)
From: "John R. Teifel" <teifel@csl.cornell.edu>
To: <egs@CS.Cornell.EDU>
Subject: 615 PAPER 46
Message-ID: <20011025122138.G62337-100000@disney.csl.cornell.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Gupta & Kumar:
This paper also discusses the capacity of wireless networks. It is a
theory paper and quite frankly way too verbose and the writing style
was almost unbearable.
They show that every node in an ad hoc network must share channels
with local neighbors in order for the total network capacity to be
utilized. The throughput available to users tends towards zero as the
number of users is increased, they suggest some type of clustering (i
think) might be useful for maintaining throughput for users.
They suggest that wireless networks may only be beneficial for
networks with a small number of nodes--not very encouraging i suppose
for ad hoc network visionaries. Adaptive or clustering may be able to
overcome this or help in scalability.
Essentially this paper said that ad hoc networks in their current
implementation are limited and more complex schemes are needed in
order for ad hoc networks to become practical.
From andre@CS.Cornell.EDU Thu Oct 25 12:43:12 2001
Return-Path: <andre@CS.Cornell.EDU>
Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7])
by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PGhBo12098;
Thu, 25 Oct 2001 12:43:11 -0400 (EDT)
Received: from khaffy (d7a046.dialup.cornell.edu [128.253.49.46])
by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA25655;
Thu, 25 Oct 2001 12:43:08 -0400 (EDT)
Received: from andre by khaffy with local (Exim 3.31 #1 (Debian))
id 15wi0T-0000ZU-00; Thu, 25 Oct 2001 12:45:01 +0200
Date: Thu, 25 Oct 2001 12:45:01 +0200
From: =?iso-8859-1?Q?Andr=E9?= Allavena <andre@CS.Cornell.EDU>
To: egs@CS.Cornell.EDU
Cc: andre@CS.Cornell.EDU
Subject: 615 PAPER 46
Message-ID: <20011025124501.A2144@khaffy>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
User-Agent: Mutt/1.3.20i
Sender: =?iso-8859-1?Q?Andr=E9_Allavena?= <andre@CS.Cornell.EDU>
Capacity of Ad Hoc Networks
A very good paper, describing and poving in which cases an ad hoc
network can work (scale) or not.
The idea is to look at the capacity of a node (the amount of data a node
an send) and compare it with the average length of a path.
End to End througput is in O(1/sqrt(n)).
They fisrt look at 802.11 which does not manage to achieve the
theoretical maximum throughput in chain situations (the first node sends
too much, the other ones wait for too much to gain access to the
communication chanel). But overall the result is not too bad (1/7
instead of 1/4), closer to optimal in other situations.
Scaling:
Let C be the one hop capacity (how much a node sends to its neightboor,
whether or not it was within a multihop path or not).
C=kA=kn/d with A the surface, n the number of nodes and d the density
C > n�L/r where L/r is the number of hops on the path
(physical distance / radius of transmission)
� the packet rate
then
� < (C/n) / (L/r) = (k/d)/ P
P begin the avergae length of a path.
_
P ~ sqrt(A) ~ sqrt(n) hence � = O(1/sqrt(n))
Instead if you choose a power law for the neighbours instead of a random
distribution, matching on the power exposant
| x < -2 -> per node capacity constant (great!)
| x = 2 -> per node capacity of O(1/log n)
| -2 < x < -1 -> per node capacity of O(log(n)/sqrt(n))
| -2 < x -> per node capacity of O(1/sqrt(n))
Conclusion, stay with x<-2 if you want to scale (collection of
superposed networks not using the links between them).
--
Andr� Allavena (local) 154 A Valentine Place
�cole Centrale Paris (France) Ithaca NY 14850 USA
Cornell University (NY) (permanent) 879 Route de Beausoleil
PhD in Computer Science 06320 La Turbie FRANCE
From samar@ece.cornell.edu Thu Oct 25 13:03:48 2001
Return-Path: <samar@ece.cornell.edu>
Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8])
by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PH3lo14826
for <egs@cs.cornell.edu>; Thu, 25 Oct 2001 13:03:47 -0400 (EDT)
Received: from descartes (descartes.ee.cornell.edu [128.84.236.60])
by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9PH47N22103
for <egs@cs.cornell.edu>; Thu, 25 Oct 2001 13:04:07 -0400
Date: Thu, 25 Oct 2001 13:03:16 -0400 (EDT)
From: Prince Samar <samar@ece.cornell.edu>
X-Sender: samar@descartes.ee.cornell.edu
To: egs@CS.Cornell.EDU
Subject: 615 PAPER 46
Message-ID: <Pine.GSO.4.21.0110251302492.12898-100000@descartes.ee.cornell.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
46) Capacity of Ad hoc Wireless Networks
This paper illustrates the capacity of wireless ad hoc networks over the
802.11 MAC layer using simulations and analysis. The article examines the
limitations imposed by the use of a single shared channel over data
forwarding and shows its effects on the network capacity and scalability.
Various factors affecting the capacity, like network size, traffic
patterns and local interactions, are studied alone and in combination.
The authors examine different topologies: chains, sets of horizontal
chains, grid and random topology. The authors conclude that the 802.11 is
successful in determining reasonably good schedules. At the same time,
they find that the simulated capacity is quite small in comparison to the
optimal value. For example, for a chain topology, the ideal capacity is
1/4 and the simulated one is about 1/7.
The paper shows that scalability of ad hoc networks is dependent on the
locality of the communication pattern. Large networks are feasible only
if the traffic is limited to the neighborhood of a node. The results in
this paper reinforce the results in the Gupta and Kumar paper.
It would be interesting to see how the results of the paper change when
mobility is introduced.