Subject: Re: [manet] Question regarding Mobility

From: Richard Ogier <[email-masked]>
Date: Tue, 25 Nov 2003 12:22:08 -0800

John,

The proof that Philippe gave is essentially what I was thinking of when I
mentioned the equivalence of going straight through the boundary to
an equivalent region.  I understood him to mean that, since the number
of nodes is constant, the resulting Poisson distribution in the original
square (after moving each node from its position in a cloned square to
the corresponding position in the original square) becomes a uniform
distribution because of the well-known result that you mentioned.

Richard

John Mullen wrote:

>Hi Philippe,
>
>The (two-dimensional) Poisson assumes that, for a very small area within
>a region, the probability of a node being in an area is proportional to
>the area plus something that becomes insignificant as the area become
>extremely small.  If you use the Poisson on a bounded region, the number
>of nodes within that region will be a random variable.  If you apply a
>Poisson distribution to a region when the number of nodes within the
>region is known in advance, the result is a uniform distribution.
>
>If the number of nodes is fixed, then eventually, the node density will
>drop to zero on the infinite plane.  The Poisson keeps the local density
>constant, so any piece of the plain will appear to be distributed
>uniformly, but the expected number of nodes on the plane will be
>infinite, since the expected value of the Poisson is the expected node
>density times the node area.
>
>So, I'm not quite sure what you are saying.  Are you saying the number
>of nodes in the finite region is a random variable (Poisson) or that the
>number of nodes is fixed, but the positions are random (Uniform)?  
>
>
>
>John Mullen  
>
>
>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
>Philippe Jacquet
>Sent: Tuesday, November 25, 2003 12:13 PM
>To: Richard Ogier
>Cc: MANET
>Subject: Re: [manet] Question regarding Mobility
>
>
>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,
>>>
>>>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
>>>
>>>----- Original Message -----
>>>From: Richard Ogier <[email-masked]>
>>>To: Philippe Jacquet <[email-masked]>
>>>Cc: MANET <[email-masked]>
>>>Sent: Friday, November 21, 2003 5:37 PM
>>>Subject: Re: [manet] Question regarding Mobility
>>>
>>>
>>>>Philippe Jacquet wrote:
>>>>
>>>>>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
>>>>>
>>>>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
>>>>
>>>>>----- Original Message -----
>>>>>From: Peter Pham <[email-masked]>
>>>>>To: MANET <[email-masked]>
>>>>>Sent: Thursday, November 20, 2003 2:03 AM
>>>>>Subject: [manet] Question regarding Mobility
>>>>>
>>>>>
>>>>>>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
>>>>>>
>>>>>_______________________________________________
>>>>>manet mailing list
>>>>>[email-masked]
>>>>>https://www1.ietf.org/mailman/listinfo/manet
>>>>>
>>>
>>>_______________________________________________
>>>manet mailing list
>>>[email-masked]
>>>https://www1.ietf.org/mailman/listinfo/manet
>>>
>>
>
>
>_______________________________________________
>manet mailing list
>[email-masked]
>https://www1.ietf.org/mailman/listinfo/manet
>
>
>_______________________________________________
>manet mailing list
>[email-masked]
>https://www1.ietf.org/mailman/listinfo/manet
>

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

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 26 Nov 2003 11:55:05 +0100

Hi, John,

The Poisson distribution is more than this. It tells that that the number of
nodes in area A is independent of the number of nodes in area B, provided
that A and B have intersection null (more precisely of measure 0). It is not
the case when the number N of nodes in the square is fixed (if you have N
nodes in A then there is zero node in B). Therefore there is the question:
does the property hold for uniform distribution? The answer is yes and this
should be a simple corollary of the result over Poisson, because:

1. The position of a random node is uniform in the square (Poisson result)
2. The positions of nodes are independent (basic hypothesis)

Philippe

---

From: [email-masked]
Date: Wed, 26 Nov 2003 08:16:08 -0700

Hi Philippe,

Yes.  I was just lost over the point of reference.  I wasn't sure if you were 
talking about the entire MANET region, for which the number of nodes is fixed, 
or a sub-region, for which the number of nodes is a random variable.

Strictly speaking, the numbers are not independent, if the number in the 
region of concern is fixed.  If you have a MANET consisting of 100 nodes and 
you know that 40 are in sub-region A, then no more than 60 can be in a non-
overlapping sub-region B.  We usually dont worry about this because the sub-
regions are small, compared to the whole.  But, to be precise, if your MANET 
will exist in a region of fixed size and you say that nodes have a Poisson 
distribution, then the number of nodes in the MANET will be a random variable.

In the mobility models we are speaking of (billards and Random Waypoint) the 
MANET is assumed to exist within a fixed region and the number of member nodes 
is assumed to be constant.  Thus, the distribution of the nodes within the 
whole region cannot be Poisson, while that within a small subregion of that 
MANET could be approximated by a Poisson.  On the other hand, if we want the 
nodes within a fixed MANET region to have a Poisson distribution, we need to 
use a mobility model in which nodes are free to either leave or join the MANET 
region, and thereby, the MANET itself.

John Mullen

---

From: "Richard Ogier" <[email-masked]>
Date: Wed, 26 Nov 2003 08:18:15 -0800

Actually, we only need to consider a single node, and show that it is
uniformly distributed in the square.  Thus, even though Philippe's
explanation is accurate, I don't think it is necessary to talk about
a Poisson distribution.   Allowing the single node to travel straight
through boundaries, we only need to show that it is uniformly
distributed in whatever "clone" of the square it happens to be in
at any time.   I think this follows simply because the node is
initially placed uniformly, and its movements are independent of
its location.

Richard