Subject: Re: Path length Distribution in MANET

From: [email-masked]
Date: Fri, 02 Jun 2000 17:15:47 +0200

What do you mean by path length? The length of the shortest path or the
length of the route obtained by a MANET protocol? In both cases you need a
model of the network geometry.

Philippe

A 09:41 02/06/00 -0400, Fabrice Tchakountio a écrit :
>Hi all -
>Can anyone point me to any papers related to a probabilistic distribution
>model of the path length between two nodes in Mobile Ad-Hoc Networks ?
>I've been unable to find any links related to that topic, so far.
>A positive reply will be greatly appreciated !
>Thanks
>Fabrice..
>
>
>
>
>
>
>

---

From: Ram Ramanathan <[email-masked]>
Date: Fri, 02 Jun 2000 14:14:37 -0400

Yes, it is model dependent. Let me rephrase Fabrice's question (Fabrice and 
I are working together on the problem).

Given a "randomly generated" (elaborated later) network, what is the
expected value of the shortest path between two nodes in the network.
Somewhat equivalently, what is the prob that the length of the shortest path
between two nodes is equal to K, for K = 1..D, where D = diameter of network.

We are looking for answers for any of these "random genartion" models:

1) random graphs (a la Bollobas and his random graph theory, e.g., there 
   exists a link between two nodes with fixed probability p)
2) unit disk graphs (modelling ad hoc networks)
3) manhattan street network with boundaries

We would also be interesting in hearing simulation results for specific
protocols, e.g., what was the average route hops in a simulation of DSR for
a given number of nodes, density etc.

thanks in advance,

-Ram.

> From: [email-masked]
> Received: from bur-smtp1.bbn.com (bur-smtp1.bbn.com [199.92.105.175])
> 	by bur-mailer1.bbn.com (8.8.8+Sun/8.8.8) with ESMTP id LAA05503;
> 	Fri, 2 Jun 2000 11:11:17 -0400 (EDT)
> Received: by bur-smtp1.bbn.com (8.9.1/8.9.1) id LAA06243;
> 	Fri, 2 Jun 2000 11:11:20 -0400 (EDT)
> Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78])
> 	by bur-smtp1.bbn.com (8.9.1/8.9.1) with ESMTP id LAA06232;
> 	Fri, 2 Jun 2000 11:11:16 -0400 (EDT)
> Received: from prisse (prisse.inria.fr [128.93.9.64])
> 	by nez-perce.inria.fr (8.10.0/8.10.0) with SMTP id e52FB8f16907;
> 	Fri, 2 Jun 2000 17:11:08 +0200 (MET DST)
> Message-Id: <[email-masked]>
> X-Sender: [email-masked]
> X-Mailer: Windows Eudora Pro Version 3.0.1 (32) [F]
> Date: Fri, 02 Jun 2000 17:15:47 +0200
> To: [email-masked], [email-masked]
> Subject: Re: Path length Distribution in MANET
> Cc: [email-masked]
> In-Reply-To: <[email-masked]
>  .com>
> Mime-Version: 1.0
> Content-Type: text/plain; charset="iso-8859-1"
> Content-Transfer-Encoding: 8bit
> X-MIME-Autoconverted: from quoted-printable to 8bit by cam-mbx1.bbn.com id LAA08031
>

---

From: Ken Carlberg <[email-masked]>
Date: Fri, 02 Jun 2000 14:19:23 -0400

Ram,

> 3) manhattan street network with boundaries

Have you had a chance to look at Ellen Zegura's work (GA. Tech) on modeling
networks?  The one paper that comes to mind is: "A Quantitative Comparison
of Graph-Based Models".   An attractive aspect of the work was the
notion of locality with respect to connectivity.  The work had sessile
(non-moving networks) in mind, but perhaps it be helpful.

-ken

---

From: Fabrice Tchakountio <[email-masked]>
Date: Fri, 2 Jun 2000 14:50:21 -0400 (EDT)

On Fri, 2 Jun 2000 [email-masked] wrote:

> What do you mean by path length? 
The length of the shortest path , assuming for instance , that a version
of link-state routing protocol is implemented.

Thanks..

---

From: [email-masked]
Date: Mon, 05 Jun 2000 10:43:49 +0200

>I are working together on the problem).

Just few very simple results before you attack the "details" of the problems. 

>   exists a link between two nodes with fixed probability p)

when the number n of node get large (with p fixed) pair of nodes are at
distance 1 with probability p, and distance 2 with probability 1-p. Other
distance probabilities tend to zero (exponentially fast in n). Interesting
things occurs when p=O(1/n) or p=O(1/sqrt(n)).

>2) unit disk graphs (modelling ad hoc networks)

If the node density is increasing, the shortest path length between two
nodes quickly tends to be ceil of the cartesian distance. Interesting
things occurs when the unit is not the disk.

>3) manhattan street network with boundaries
Nothing specific wireless. the shortest path length equal to the sum of the
absolute discrepancies between node coordinates.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 05 Jun 2000 07:17:36 -0700

Hello,

> things occurs when p=O(1/n) or p=O(1/sqrt(n)).

This seems like an impossible result, unless there is more to the
problem statement.  For instance, if p==0, then surely P(distance==2) == 0.
If p==0.00000001, then P(distance=2) is not much larger than 0.

Besides, this problem statement places no geometric constraint.
The two nodes that are farthest apart are equally probable to
have a link as the two nodes closest together.  Is there some
intuition that I can gain to make this problem statement relevant
to ad hoc networks that use actual physical media?

> things occurs when the unit is not the disk.

Can you be more specific?  I would have expected that the results
would be roughly similar.

Regards,
Charlie P.

---

From: [email-masked]
Date: Mon, 05 Jun 2000 17:54:14 +0200

Hello, Charlie,

>If p==0.00000001, then P(distance=2) is not much larger than 0.

The formula is of the kind P(distance>2)<n*(1-p)^(p*n). Therefore for
*reasonable* values of p and large n (take p=0.5 and n=100), the diameter
of the graph is 2 with probability 1-2^(-44).

>would be roughly similar.

The ceil of the cartesian distance is the best you can get (since the
number of hops is integer). cartesian distance and shortes path tends to be
equivalent when the distances increase. However the distance obtained by
flooding significantly differs from shortest path in this model. 
Regards,
Philippe

---

From: Ram Ramanathan <[email-masked]>
Date: Mon, 05 Jun 2000 13:54:12 -0400

> Date: Mon, 05 Jun 2000 07:17:36 -0700
> From: "Charles E. Perkins" <[email-masked]>
> Organization: Nokia Research Center
> X-Mailer: Mozilla 4.7 [en] (X11; I; FreeBSD 2.2.6-RELEASE i386)
> X-Accept-Language: en
> MIME-Version: 1.0
> To: [email-masked]
> CC: Ram Ramanathan <[email-masked]>, [email-masked],
>         [email-masked]
> References: <Your message of "Fri, 02 Jun 2000 17:15:47 +0200."             <[email-masked]> <[email-masked]>
> Content-Type: text/plain; charset=us-ascii
> Content-Transfer-Encoding: 7bit
> Sender: [email-masked]
> Precedence: bulk
> Status:  O
> 
> 
> Hello,
> 

I didn't say or mean to imply that it was a good model for ad hoc nets.
I was picking the pure random graph and the unit disk graphs as the
two "extremes" of a continuum in which a typical ad hoc network might lie --
I believe most ad hoc networks will have some distance dependency, but
not depend *only* on distance as unit disk graphs do.

Another way to look at it is using the well-known (e.g. see Rappaport's book
Wireless Communication) large scale propagation model which says that the
actual path loss is log-normally distributed with variance V around a
mean path loss computed using some formula (e.g. k1/d^4 + k2). The
log-normal distribution is to model "environmental clutter" (e.g. metal 
objects or other RF barriers). The more the clutter, the higher the V, and
more "arbitrary" the graph starts looking. In the extreme, there is so much 
clutter that whether or not two nodes can communicate has nothing to do with 
distance, only on the presence or absence of barriers -- which may be purely 
random. (For practical relevance think gigabit ad hoc nets in the 24 GHz ISM 
band:)

At the other  extreme, when there is no clutter at all, the 
connectivity is purely distance dependent (corresponds to V=0 of 
log-normal distribution mentioned above). 

If there are expected path length results for the general model (say as a 
function of V), that would be great! But I think that is unlikely and
so posed the question for the two extremes - which will at least be some
insight. 

-Ram.

---

From: Ravi Prakash <[email-masked]>
Date: Mon, 5 Jun 2000 14:52:22 -0500 (CDT)

Hi,

We did some preliminary simulation experiments to determine the upper
bounds on path lengths and path stability in mobile ad hoc networks. The
idea was to have nodes move on a grid of streets, as in a fleet of
taxi-cabs. 

The goal of these experiments was to determine the feasibility of route
caching in protocols like AODV and DSR. Our experiments seem to indicate
that caching may have very limited utility as paths do not stay unchanged
for long. 

The paper containing these results is available as University of Texas at
Dallas Technical Report # UTDCS-05-00 and can be downloaded from the
following URL:

  www.utdallas.edu/~ravip/papers/persist.ps

Here is a brief description of the work and a synopsis of results. I would
really appreciate your comments. 

With best regards,

----Ravi.

========================= DESCRIPTION ================================

Two cabs (also referred to as nodes) in line of sight have a range R, and
two cabs on mutually perpendicular streets have range R' (where R' <
R). Then, two nodes that are within range are supposed to have a link. So,
it is a minor modification of the unit-disk graph model. We ran the
Bellman-Ford algorithm to determine the reachability of nodes.
Also, we decided to simulate movement in a region where the bounds along
the x-axis and y-axis were both significantly more than R. This ensures
that the network does not appear to be a linear alignment of nodes.

We noticed that when  the number of nodes was small the graph was highly
partitioned and there were very few paths, with a majority being one-hop.
As the number of nodes increased, as expected the number of partitions
decreased and the average path length increased. The paper presents the
mean and the 90% confidence intervals of path length and path persistence. 

Path persistence was measured as the duration for which the shortest path
between a pair of nodes remains unchanged, i.e., all the intermediate
nodes stay in the same alignment. As expected, with increasing path
length, path persistence declined rather steeply. This, in our opinion, is
because in a longer path there is a higher probability that at least
one node will move such that it is now out of range of at least one of its
neighbors (predecessor/successor) in the path. 

What was most disturbing was that path persistence was very low even when
nodes alternated between moving at an average speed of 35 kph for a while,
and staying put for a while on reaching the destination of their
trip. Please note that we considered an ideal (i.e., highly
unrealistic) communication model where two nodes within range always had a
link. So, in reality both path persistence and path length may be far
lower than what our experiments indicate. This seems to imply that the
reduction in route discovery traffic that protocols like AODV and DSR
strive to achieve by caching routes may be limited. 

Also, we found that deploying traffic lights at street-intersections
increased path persistence while significantly reducing path lengths. This
is because traffic lights tend to aggregate nodes at the intersections and
they tend to move almost in unison until the next light. 

The presence of one-way streets has very little additional impact on path
persistence and path lengths. 

========================================================================
Ravi Prakash ([email-masked])		www.utdallas.edu/~ravip
Department of Computer Science
The University of Texas at Dallas
Richardson, TX 75083-0688.  Phone: (972) 883-2289,   Fax: (972) 883-2349