# Topologi control in wireles ad hoc and sensor network - Santi P.

ISBN-10 0-470-09453-2

**Download**(direct link)

**:**

**33**> 34 35 36 37 38 39 .. 122 >> Next

Theorem 5.0.3 Let M be a stable and c-independent mobility model, that is, a model such that node positions at time ti+c are independent of node positions at time ti, for some constant c > 0. Then, a network with M-like mobility is ergodic with respect to the CTR for connectivity.

Proof. Consider an M-mobile network. Let r1,r2,... ,ri,... denote the sequence of random variables corresponding to the critical range for connectivity computed at time

ti,t2,...,ti,_______ By hypothesis, M is stable, that is, there exists a probability density

function FM such that, for i sufficiently large, ri has the same distribution as that of random variable r, where r denotes the length of the longest MST edge when nodes are distributed according to FM.

Let us consider two consecutive random variables ri and ri+1 in the sequence. In general, ri+1 is not independent of ri, since node positions at time ti+1 might depend on node positions at the previous step (for instance, because nodes are moving along a certain trajectory). However, by hypothesis, there exists a constant c > 0 such that, for any i sufficiently

THE CTR FOR CONNECTIVITY: MOBILE NETWORKS

55

large, the node positions at time ti+c are independent of node positions at time ti. Thus, variables ri and ri+c are independent, and sampling from ri and subsequently from ri+c is statistically equivalent to sampling twice from r (this is true because also random variable ri+c has the same distribution as r). Given this observation, we can subdivide the original sequence of random variables S = {ri, ri+1,..., ri+c, ri+1+c,...} into c subsequences So = {ri, ri+c, ri+2c,...}, Si = {ri+i, ri+i+c, ri+i+2c,...}, .... For any such subsequence Sj, successively sampling from Sj is statistically equivalent to repeatedly sampling from r (this is because the random variables in Sj are independent). Since any random variable in the original sequence S belongs to one and only one of the Sj s, it follows that successively sampling from S is statistically equivalent to repeatedly sampling from r, and the theorem is proven.

Intuitively, ergodicity adds a temporal dimension to our definition of CTR in presence of mobility. To better understand this point, assume that the transmitting range is set to a value r such that the probability of generating a connected graph when nodes are distributed according to Fm is 0.99, and assume M satisfies the hypotheses of Theorem 5.0.3. By ergodicity, we can state that, on the average, 99% of the values observed in the sequence S of the longest MST edge lengths is below r. This means that if we observe the mobile network for a sufficiently long period of time then the fraction of time in which the network is connected approaches 0.99. So, by observing the network behavior when nodes are distributed according to the asymptotic node spatial distribution generated by M-like mobility, we can obtain information on the dynamic behavior of the network when nodes move.

The discussion above has outlined that, assuming M is a stable mobility model, the problem of characterizing the CTR in presence of M-like mobility can be reduced to studying the CTR under the assumption that nodes are distributed according to a certain distribution Fm-

The first observation is that if a certain mobility model M generates a uniform asymptotic node spatial distribution (i.e. FM is the uniform distribution) then the results on the CTR presented in the previous chapter can be directly applied to M-mobile networks. An example of such mobility model is Brownian-like mobility (see Section 2.4 for the definition of Brownian-like motion): in (Blough et al. 2003b), it is shown through simulation that this mobility model generates a uniform long-term node spatial distribution.

In the next section, we consider the case of RWP mobility, which is the only mobility model for which the asymptotic node spatial distribution has been derived.

5.1 The CTR in RWP Mobile Networks

In this section, we characterize the CTR for connectivity in case of RWP mobility, which is by far the most popular mobility model used in the simulation of ad hoc networks.

It is known that the asymptotic node spatial distribution generated by RWP mobility is not uniform but is somewhat concentrated in the center of the deployment region (Bettstetter and Krause 2001; Blough et al. 2004). This phenomenon, which is called the border effect, is due to the fact that the waypoints (i.e. the destinations of a movement) in the RWP model are selected uniformly at random in a bounded deployment region R. To better understand this point, consider a RWP mobile node u, and assume that node u is currently

56

THE CTR FOR CONNECTIVITY: MOBILE NETWORKS

u

*

\ ^1

\ ^2

Figure 5.1 The border effect in RWP mobile networks: when a node is resting close to the border, it is likely that the trajectory to the next waypoint crosses the center of the deployment region (dark shaded area). In the figure, the probability that the trajectory of node u to the next waypoint intersects A1 equals the sum of the areas of A1 and A2 (we are assuming R = [0, 1]2).

**33**> 34 35 36 37 38 39 .. 122 >> Next