Download (direct link):
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—-
This formula is supported by experimental evidence.
THE CTR FOR CONNECTIVITY: MOBILE NETWORKS
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
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
velocity in the RWP model is at least umin > 0. Note that, by setting c = 2-^-, we ensure
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.