Subject: [manet] Question regarding Mobility

From: Peter Pham <[email-masked]>
Date: Thu, 20 Nov 2003 11:33:47 +1030

Hi all
I am interested in modelling ad hoc networks. In the stationary scenario 
(nodes do not move), I can assume that the mobile nodes are distributed 
randomly according to Poisson distribution (many assumed so). However, 
is this assumption still valid under the mobility ?
Can anyone give me some advice ?

Peter Pham

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "John Mullen" <[email-masked]>
Date: Wed, 19 Nov 2003 19:47:36 -0700

Hi Peter,

In general, the distribution of nodes while in motion differs from that
when they are stationary, but in the particular case you describe, I am
not sure.  

The Poisson distribution essentially describes a uniform distribution
over an unbounded region.  If the region is bounded, and if nodes pick a
location, then move to it, the distribution of nodes in motion will have
a more central distribution because when near a boundary, it is more
likely to pick a new location that is towards the interior than further
out.  However, without a boundary, this reasoning does not apply and it
might be that the distribution does not change.

So if the region is bounded, and if destinations are chosen according to
the original placement distribution, the answer is "yes," but if the
region is unbounded or if some other destination rule is used, I am not
sure.

John Mullen

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Peter Pham
Sent: Wednesday, November 19, 2003 6:04 PM
To: MANET
Subject: [manet] Question regarding Mobility

Hi all

Peter Pham

---

From: "Zhenqiang(Frank) Ye" <[email-masked]>
Date: Wed, 19 Nov 2003 17:24:55 -0800 (PST)

> randomly according to Poisson distribution (many assumed so). However,
What do you mean Poission distribution?

Thanks,

Frank

-- 

****************************************
Zhenqiang(Frank) Ye
Ph.D Student
Department of Electrical Engineering
University of California, Riverside
Phone: (909)-787-2434
email: [email-masked]
****************************************

---

From: "Philippe Jacquet" <[email-masked]>
Date: Thu, 20 Nov 2003 14:15:49 +0100

Yes, Peter, the distribution changes if you introduce mobility and it
depends on the mobility model. Take the random way point model where each
node has a distinct a random destination point selected uniformly in a
square, and each node moves to this destination at constant speed. In this
case, the stationary density at point (x,y) (assuming a 1x1 square) is
*( x* log x+(1-x)*log(1-x))*(y*log y +(1-y)*log(1-y)) which differs from
uniform density (which is equal to 1 at any point in the 1x1 square).

Philippe

---

From: Peter Pham <[email-masked]>
Date: Fri, 21 Nov 2003 10:41:51 +1030

Dear Philippe

I am really intersted in the result. Is there any papers on this that 
you can refer to ?...Can you let me know ?

Cheers
Peter Pham

---

From: Richard Ogier <[email-masked]>
Date: Fri, 21 Nov 2003 08:37:40 -0800

>uniform density (which is equal to 1 at any point in the 1x1 square).
Philippe,

Your result implies that you can consider the x and y directions
independently. I don't think this is the case, because the speed
in the x direction depends on the (x,y) direction of movement. 
I did some calculations, and I think your result assumes that
the time to go from one random point to the next random point
is constant (thus, if the distance between the 2 points is
greater, the speed must be greater). 

Just for fun I tried to derive the steady state distribution in one
dimension for a unit interval [0,1] and got the following result
(assuming constant speed and zero pause time):

   C * x*(1-x)   (C is a normalization constant)

The x*(1-x) term is simply the probability that the point x
lies between two random numbers uniformly distributed in [0,1].
I ran a simulation on the unit interval [0,1] which confirms this result.
In particular, the probability that the node is near x = 0.25
is 0.75 times the probability that the node is near x = 0.50.

Unfortunately, this result cannot be extended to 2 dimensions by
taking the product of this term for the x and y directions, because
the x and y components of the node speed are not independent.

Richard

---

From: "John Mullen" <[email-masked]>
Date: Fri, 21 Nov 2003 09:55:39 -0700

Hi Richard,

You are correct in the matter of non-independent speed, however, I am
unaware of any result that takes this into consideration.  In "The
spatial node distribution of the random waypoint mobility model." (1st
German Workshop on Mobile Ad-Hoc Networks (WMAN'02), Ulm, Germany,
2002.), Christian Bettstetter discusses this problem at length and
develops a couple of approximate distributions.  He also performed some
simulations which seem to indicate the approximations are pretty close.
Bettstetter has published more on this topic, so you may want to check
out his web page:

http://www.lkn.ei.tum.de/~chris/#Publications

John Mullen

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Richard Ogier
Sent: Friday, November 21, 2003 9:38 AM
To: Philippe Jacquet
Cc: MANET
Subject: Re: [manet] Question regarding Mobility

Philippe Jacquet wrote:

>depends on the mobility model. Take the random way point model where 
>each node has a distinct a random destination point selected uniformly 
>in a square, and each node moves to this destination at constant speed.

>In this case, the stationary density at point (x,y) (assuming a 1x1 
>square) is *( x* log x+(1-x)*log(1-x))*(y*log y +(1-y)*log(1-y)) which 
>differs from uniform density (which is equal to 1 at any point in the 
>1x1 square).
>
>Philippe
>
Philippe,

Your result implies that you can consider the x and y directions
independently. I don't think this is the case, because the speed in the
x direction depends on the (x,y) direction of movement. 
I did some calculations, and I think your result assumes that the time
to go from one random point to the next random point is constant (thus,
if the distance between the 2 points is greater, the speed must be
greater). 

The x*(1-x) term is simply the probability that the point x lies between
two random numbers uniformly distributed in [0,1]. I ran a simulation on
the unit interval [0,1] which confirms this result. In particular, the
probability that the node is near x = 0.25 is 0.75 times the probability
that the node is near x = 0.50.

Unfortunately, this result cannot be extended to 2 dimensions by taking
the product of this term for the x and y directions, because the x and y
components of the node speed are not independent.

Richard

>>I am interested in modelling ad hoc networks. In the stationary 
>>scenario (nodes do not move), I can assume that the mobile nodes are 
>>distributed randomly according to Poisson distribution (many assumed 
>>so). However, is this assumption still valid under the mobility ? Can 
>>anyone give me some advice ?
>>
>>Peter Pham
>>
>>
>>

---

From: Richard Ogier <[email-masked]>
Date: Fri, 21 Nov 2003 18:32:09 -0800

John,

Thanks for the pointer.   Frankly,  instead of studying bad mobility 
models (like
random waypoint), I prefer to use a good mobility model that ensures 
node positions
are uniformly distributed.  One model that achieves a uniform 
distribution (assuming
zero pause time) is a random walk model, where each node moves in a 
random direction
for T seconds, then chooses a new random direction.  If the node hits a 
boundary,
it bounces off as in billiards (angle of reflection equals angle of 
incidence).

There is another model called the "random direction" model, in which the 
node chooses
a new random direction only when it hits the boundary.  However, I don't 
think
this model achieves a uniform distribution (assuming zero pause time).

The following paper discusses these model and several others (but does 
not talk about
probability distributions):

T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad 
hoc network research. Wireless Communications & Mobile Computing (WCMC): 
Special issue on Mobile Ad Hoc Networking: Research, Trends and 
Applications, 2(5):483--502, 2002.

Richard

John Mullen wrote:

Hi Richard,

John Mullen

-----Original Message-----
From: [email-masked] [mailto:[email-masked] ] On Behalf Of
Richard Ogier
Sent: Friday, November 21, 2003 9:38 AM
To: Philippe Jacquet
Cc: MANET
Subject: Re: [manet] Question regarding Mobility

Philippe,

Your result implies that you can consider the x and y directions
independently. I don't think this is the case, because the speed in the
x direction depends on the (x,y) direction of movement. I did some 
calculations, and I think your result assumes that the time
to go from one random point to the next random point is constant (thus,
if the distance between the 2 points is greater, the speed must be
greater).
Just for fun I tried to derive the steady state distribution in one
dimension for a unit interval [0,1] and got the following result
(assuming constant speed and zero pause time):

Richard

---

From: "Philippe Jacquet" <[email-masked]>
Date: Tue, 25 Nov 2003 15:13:13 +0100

Richard,

My mistake, you are right. I was considering the case where the node reaches
its way point in a constant time. With a constant speed, zero pause time,
the density is your result: C (1-x)*x in dimension one. To be forgiven I
tried to compute the formula for the density in two dimensions. Not really
fun. For x>y and (1-x)>y it should be proportional to j(x,y)+j(1-x,y) with a
normalizing factor, with
j(x,y)=(1-x)*y*(2+log(x/y)-log((1-x)/(1-y))).

For the other cases for (x,y) one makes use of symmetries and finally:
density(x,y)=C*(j(max(x,y),min(x,y))+j(max(1-x,y),min(1-x,y)))

I made the integration over all angle of the product of the two distances of
the point (x,y) to the border of the square within a given angle. I used
Maple. It needs to be cross checked.
.

The plot looks like a very eroded pyramid: null density on the border and
top on the square center. The result should be the same when the speed is
randomly selected on finite distribution.

Best regards,
Philipe

---

From: "Philippe Jacquet" <[email-masked]>
Date: Tue, 25 Nov 2003 20:12:43 +0100

There is likely a proof for the invariance of the Poisson distribution under
the billard model.

There is a general result that tells that on an infinite plane, an initial
Poisson distribution of nodes remains Poisson at any time given simple
conditions on node motions, i.e. move are indendent of nodes and position.

I think it is easily extendable to the billard model, one just have to clone
the square and cover the whole the plane by mirror effect, so that bouncing
is just equivalent to going straight through the border between two mirror
images. And then we distribute nodes indifferently in the original square
and in its mirror images as if it was a Poisson distribution on the whole
plane. After letting the node moving, we apply the general result.

Notice that the result remains valid even when the motions are complicated
(pause times, distance travelled, changes of direction, curves, etc), given
they are independent of nodes and locations. Random change of direction at
the border may not satisfy this rule.

Philippe
----- Original Message -----
From: Richard Ogier <[email-masked]>
To: Philippe Jacquet <[email-masked]>
Cc: MANET <[email-masked]>
Sent: Tuesday, November 25, 2003 6:02 PM
Subject: Re: [manet] Question regarding Mobility

> Philippe,
>
> Thanks for computing the formula for the probability density of node
> position
> for random waypoint. I also started to compute the formula for 2
> dimensions,
> but quit when I saw how complicated it is. In actual simulations, to
> start out
> with the steady state density, it might be easiest to just generate two
> random
> points in the square and then choose a random point uniformly
> distributed on the
> line connecting the two points.
>
> Someone asked me about a proof that the random-walk billiards model
results
> in uniformly distributed node positions.  (This is the model in which a
node
> moves in a random direction for T seconds, bouncing off boundaries
> like a billiards ball, and choosing a new random direction after T
seconds.)
> I think this is fairly intuitive, by considering what happens if the
> node instead
> goes straight through the boundary into an equivalent region adjacent to
> the original region.  But is this result well known?   Can anyone point
> to a reference for this?
>
> Richard
>
>
>
> Philippe Jacquet wrote:
>
> >Richard,
> >
each
> >>>square, and each node moves to this destination at constant speed. In
> >>>
> >this
> >
scenario