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

ISBN-10 0-470-09453-2

**Download**(direct link)

**:**

**35**> 36 37 38 39 40 41 .. 122 >> Next

a.a.s.

Note that the CTR in presence of RWP mobility is always larger than the CTR in case of uniform node distribution since 1/.Ppause is larger than 1 for any value of tp. For instance, with tp = 75 and v = 0.01, we have 1/-Ppause = 1.69485. Clearly, a longer pause time results in a more uniform node distribution and, consequently, in a smaller value of the CTR. For instance, with tp = 150, we have 1/Epause = 1.34743.

Note also the asymptotic gap of the CTR in the most extreme case of RWP mobility, that is, when tp = 0: in this case, for any constant c > 0, setting the transmitting range to

is not sufficient for achieving a.a.s. connectivity. The exact value of the CTR with RWP mobility when tp = 0 is not known to date. In (Santi 2005), it is conjectured that

0 1 log n

''RWP ^4 lOg «V—-

n

This formula is supported by experimental evidence.

THE CTR FOR CONNECTIVITY: MOBILE NETWORKS

59

Figure 5.3 CTR for connectivity in case of RWP mobility with tp = 75 and v = 0.01, for increasing values of n. The lower plot (ThCTR) refers to the asymptotic value, calculated in accordance with Theorem 5.1.4. The upper plot (ExpCTR) is obtained from the experimental CTR distribution generated by the simulations.

Figure 5.3 shows the rate of convergence of the actual CTR for connectivity to the asymptotic value stated in Theorem 5.1.4 in case of RWP mobility with tp = 75. The actual CTR value is computed as follows. Initially, n nodes are distributed uniformly at random in R = [0, 1]2. Then, they start moving according to the RWP mobility model. After a large number of mobility steps (1000 in our experiments), nodes’ positions are recorded, and utilized to generate the experimental distribution of the longest MST edge length in case of mobility. As in the case of stationary networks, the experimental CTR value is defined as the 0.99 quantile of this distribution.

From the Figure, it is seen that the formula of Theorem 5.1.4 is quite accurate only for large values of n (n = 1000 and above). The experimental value of the CTR for RWP mobile networks with different values of the pause time is reported in Table 5.1.

Before concluding this section, we prove that the RWP mobility model satisfies the conditions for ergodicity.

Theorem 5.1.5 A network with RWP mobility is ergodic with respect to the CTR for connectivity.

Proof. In order to prove the theorem, we have to show that the RWP mobility model is stable and c-independent, for some constant c > 0. The first property is an immediate consequence of Theorem 5.1.1. As for the second, consider an arbitrary time instant i. We have to determine a certain value c > 0 such that the positions of all the nodes at time i + c are independent of node positions at time i. Let us define a movement epoch as the time needed for a node just arrived at a waypoint to reach the next waypoint. In other words, a movement epoch is composed of the pause time plus the travel time between two consecutive waypoints. Since the length of the trajectory and node velocity are in general

60

THE CTR FOR CONNECTIVITY: MOBILE NETWORKS

Table 5.1 Values of the transmitting range yielding 99% of connected communication graphs in RWP mobile networks, for different values of the pause time tp

n tp= 0 tP =75 tp = 150

10 0.56423 0.61625 0.64226

25 0.41203 0.44705 0.46285

50 0.33644 0.33892 0.34404

75 0.29454 0.28179 0.28054

100 0.26526 0.25736 0.2395

250 0.19761 0.17163 0.17117

500 0.15955 0.12728 0.1134

750 0.13963 0.10507 0.10086

1000 0.12708 0.08931 0.08416

2500 0.09482 0.05963 0.05473

random variables, the duration of a movement epoch is also a random variable. Indeed, we have a sequence of random variables representing the duration of the various epochs that constitute the movement trace of a node. We denote these variables with Euj, where u is the node to which the variable is referred and j denotes the j th epoch of node u. By definition of RWP mobility, node u’s position at time i + c is independent of its position at time i if and only if c is larger than Euj + Euj+i, where j is the index of the epoch occurring at time i. In words, the node must conclude the current and the next epoch before its position is independent of the position at time i. Note that it is not enough for the node to terminate the current epoch, since a node which is traveling at time i is on its trajectory to a certain waypoint Wuj, which is also the starting point of the next trajectory. However, after the node has reached the next waypoint, the conditions for independence are satisfied. So, proving the theorem reduces to proving that there exists constant c > 0 such that Euj + Euj+i < c, for any j > 0 and for any node u. This is accomplished by setting c = 2-^-. In fact, the maximum length of a linear trajectory in R = [0, l]2 is V2, and node

%lin ^

velocity in the RWP model is at least umin > 0. Note that, by setting c = 2-^-, we ensure

^min

that the positions of all the nodes at time i + c are independent of their positions at time i. This follows from the fact that inequality Euj + Euj+1 < c is satisfied for any epoch and for any node.

**35**> 36 37 38 39 40 41 .. 122 >> Next