Download (direct link):
The collection of the results presented in this section indicates that the characterization of the CTR based on the quite idealized point graph model can be considered as the worst-case scenario among all situations where the radio coverage area is the same. In other words, if the conditions for connectivity are met in the point graph model, then the same conditions are satisfied also in more realistic models that account for irregular coverage area, provided the wireless transmission footprint (and, hence, the expected number of neighbors) is the same. We can then conclude that the characterizations of the CTR for connectivity presented in Sections 4.1 and 4.2 do have practical significance.
The CTR for Connectivity: Mobile Networks
In the previous chapter, we have presented several characterizations of the CTR for connectivity in case of stationary networks. In this chapter, we analyze the effect of mobility on this important network parameter.
First, we have to agree on the definition of CTR in presence of mobility. Differing from the stationary case, the network topology changes with time because of node mobility. This implies that the CTR for connectivity also changes with time. Denoting with t1,t2,... ,ti,... a sequence of time instants, we then have a sequence of values of the CTR for connectivity r1,r2,... ,ri,..., where ri equals the length of the longest edge of the MST built on the n nodes at time ti. Note that, in general, the values in the ri sequence are neither increasing nor decreasing, that is, there could exist time instants ii, i2 with i1 < i2 such that ril < ri2, and time instants i3, i4 with i3 < i4 such that ri3 > ri4.
Several definitions of CTR for connectivity in mobile networks are possible. For instance, we could define the CTR as the maximum value of the ri s in the sequence of time instants corresponding to the network operational time. This is a very conservative definition of CTR, since it ensures that by setting the transmitting range to the critical value the resulting communication graph is connected during the entire network operational lifetime. However, this definition of mobile CTR in many situations might be too strong, because an occasional, extremely high value of one of the ri s would render the CTR very high as well. For this reason, in the literature, a definition of CTR for connectivity in presence of mobility that is based on a stochastic property of the mobile system has been introduced.
Definition 5.0.1 (Asymptotic node spatial distribution) Assume n nodes are initially deployed in a certain region R according to some probability density function F. After initial deployment, nodes start moving according to a certain mobility model M. The asymptotic node spatial distribution generated by M-like mobility with initial deployment F is the probability density function Fm defined as
Fm = lim Fi, (5.1)
Topology Control in Wireless Ad Hoc and Sensor Networks P. Santi
© 2005 John Wiley & Sons, Ltd
THE CTR FOR CONNECTIVITY: MOBILE NETWORKS
where Fi is the probability density function modeling node spatial distribution at time ti. If the limit on the right-hand side of (5.1) does not exist, we say that mobility model M with initial deployment F does not stabilize.
Note the stochastic nature of this definition: it is assumed that initial node positions, as well as node positions at any time instant ti, can be modeled by a certain probability density function that evolves with time. As discussed in Section 2.4, because of the lack of real movement patterns, a common approach in the evaluation of mobile ad hoc network properties is to use synthetic, stochastic mobility models. Thus, our definition of asymptotic node spatial distribution is coherent with the stochastic nature of mobility models for ad hoc networks.
We are now ready to define the CTR in presence of mobility.
Definition 5.0.2 (Mobile CTR) Assume n nodes are initially deployed in a certain region R according to some probability density function F. After initial deployment, nodes start moving according to a certain mobility model M. The CTR for connectivity in M-mobile networks with initial deployment F is defined as the minimum value of the transmitting range that ensures a.a.s connectivity under the assumption that n nodes are distributed in R with density Fm, where Fm is the asymptotic node spatial distribution generated by M-like mobility with initial deployment F.
Implicit in the definition above is the fact that the mobility model stabilizes. This is actually the case of most of the models considered in the literature (for instance, all the models described in Section 2.4). In case of unstable mobility patterns, a different definition of CTR (such as the maximum of the ri s sequence) should be used.
By defining the CTR in presence of mobility as above, we can prove an ergodic property of certain mobile networks. We recall that a stochastic process composed of a sequence of random variables r1,r2,... ,ri,... (in our case, the sequence of the longest MST edge lengths) is ergodic if sampling from the sequence of random variables is statistically equivalent to repeatedly sampling from a certain, fixed random variable (in our case, the length of the longest MST edge computed when nodes are distributed according to FM).