Subject: RE: Ad Hoc Network Scalability

From: Phillip Neumiller <[email-masked]>
Date: Thu, 5 Jul 2001 19:13:54 -0400

I would like to challenge the list to an even simpler 
problem.  Assume a static model, i.e. no mobility, but
nodes appear randomly positioned up to some maximum
number in a fixed size area (once nodes appear they 
remain transmitting at the peak they can acheive).  
Assume CSMA/CA MAC.

I am quite sure that there is some number n, the
maximum density, where the throughput per node starts 
dropping off.  After you find n, start moving the mobiles
around with various patterns and see if per node throughput
goes up or goes down on average.  My bet is on down for 
all known MANET routing algorithms!  

To talk about mobility without talking about mobile density
seem erroneous to me.

Thanks,

Phil Neumiller
Mesh Networks, Inc.

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]
> Sent: Thursday, July 05, 2001 3:49 PM
> To: [email-masked]
> Subject: RE: Ad Hoc Network Scalability
> 
> 
> 
> Is it possible to conduct a mathmatical proof to see whether
> mobility will increase capacity with some assumptions?
> 
> Yang
> 
> 
> 
> On Thu, 5 Jul 2001, Nitin H Vaidya wrote:
> 
> > Date: Thu, 5 Jul 2001 13:01:08 -0500 (CDT)
> > From: Nitin H Vaidya <[email-masked]>
> > To: [email-masked], [email-masked]
> > Subject: RE: Ad Hoc Network Scalability
> >
> >
> >   >> From [email-masked] Thu Jul  5 12:29:52 2001
> >   >>
> >   >> With the risk of digressing a little, I would like to 
> point out that even
> >   >> with a more conventional model, mobility increases 
> capacity. By conventional
> >   >> model I mean a model where we want to relay packets 
> between end points as
> >   >> soon as possible, instead of waiting and buffering for 
> the most opportune
> >   >> moments. This is the model the MANET community is most 
> familiar with.
> >   >>
> >   >> The intuition here is that mobility randomizes the 
> node positions enough
> >   >> that radio congestion points are now less on average 
> or are more avoidable
> >   >> with an idealized routing protocol (assuming 
> CSMA-based MAC). We have
> >   >> analyzed this effect using simulations (results 
> forthcoming). Also, some
> >   >> published ns-2 based simulation results in the last 
> few years also did show
> >   >> occassional routing performance improvements with mobility!
> >
> > I have not seen your results, but I won't let that stop me -:)
> >
> > The results for mobility (including those from the
> > Infocom papers cited previously) essentially imply that mobile nodes
> > are likely to see more "favorable environment" every once
> > in a while -- to put it differently, results for the mobile case
> > are averaged over a series of "static" topologies, and hence would
> > look better than some unfavorable static topologies, and worse than
> > others.
> >
> > For instance, consider the scenario below:
> >
> >   A -- C -- E -- B -- D   (topology 1)
> >
> > Assume that A is sending packets to B, and C is sending 
> packets to D.
> >
> > Also assume that nodes B and C move such that they periodically
> > swap positions. So the alternative topology here is
> >
> >   A -- B -- E -- C -- D  (topology 2)
> >
> > If we measure performance in presence of mobility, the
> > average is over all topologies, including topology 1 and 2.
> > Clearly, these could look better in the mobile case than
> > in static topology 1, but worse than in static topology 2.
> >
> > Thus, whether mobility improves "capacity" or not
> > depends on the mobility and communication patterns.
> > Mobility does *not* always improve capacity (i.e.,
> > per-session throughput), and might even make it worse,
> > depending on mobility/communication patterns.
> >
> > So the definition of "capacity" itself is debatable,
> > more so for the mobile case.
> >
> > - nitin
> >
>

---

From: "Philippe Jacquet" <[email-masked]>
Date: Sat, 7 Jul 2001 04:30:04 +0200

Well, putting aside the problem of CSMA/CA which is specific to 802.11, one
would probably
come again in the model of Gupta. And we will get the O(1/sqrt(n)), i.e. an
overall traffic of
O(sqrt(n)). The funny part of this result is that it lead to an unbounded
overall total traffic when
n increases contrary to a fully wired network.

Philippe