WiTMeMo '05 Paper    [WiTMeMo '05 Technical Program]

Mobility Assessment for MANETs Requiring Persistent Links

Sanlin Xu	Kim Blackmore	Haley Jones
Department of Engineering, Australian National University

Abstract

Mobile ad hoc networks (MANETs) have inherently dynamic topologies. It is important to be able to determine the reliability of the communication paths created under these difficult circumstances. For this purpose, mobility metrics have been proposed in the literature, but most existing research is based on simulation results and empirical analysis. We consider two metrics, link persistence and path persistence, and develop an analytical framework to derive their exact expressions as well as the corresponding link residual time and path residual time, under a random mobility environment. Such exact expressions constitute precise mathematical relationships between the network connectivity and the mobility of mobile nodes. This framework could be used to develop efficient algorithms for medium access control, or to optimize existing network routing protocols.

1 Introduction

Mobile ad hoc networks are comprised of mobile nodes communicating via wireless links. Due to the mobility, communication paths are dynamic, affecting path reliability. Meaningful analysis of the reliability of these constituent links is crucial to understanding the reliability of the paths themselves. Node mobility leads to changes in network topology resulting in link additions and breakages, and alteration of traffic patterns and/or traffic distributions. Routing protocols [12,11,9] based on mobility metric prediction have been shown to increase the packet delivery ratio and reduce routing overhead.

In this paper, we consider the notions of link persistence and path persistence to describe the continuous link and path availabilities, respectively, for an active communication route. The link (path) persistence is the probability that a link (path) lasts constantly until a future time, $k$ , given that it existed at time 0 . From theoretical analyses of the link (path) persistence, we derive the expected residual time for an active link (path). The residual time is evaluated deterministically in [12,11], by simulation in [4,2,10], and by calculation in [13]. Note that the various mobility measures have been given different names by different authors.

A similar measure to link persistence, link availability, is considered by Jiang et al [6]. The link availability is approximated as the ratio of the mean time a link will be continuously available to a link prediction time. The calculation method in [6] relies on a parameter, $\varepsilon$ , that must be experimentally determined. In [8], link availability is also considered but, in this case, a link is considered to be available at $k$ even if it has undergone failure during the time between 0 and $k$ . Further, in [13] an expression for link availability, using a simple straight line mobility model, is derived.

Our notion of link or path persistence requires a random mobility model [3] governing the behaviour of the nodes in the network. We assume nodes move according to a generalisation of the Random Walk Mobility Model. Such an assumption is clearly not realistic, but may be useful as an aid to predicting link reliability for routing purposes [8]. Moreover, random mobility models are regularly used for protocol evaluation [2], so our work is important to facilitate comparison of the evaluation environment with practical implementation environments.

This paper is organised as follows. In Section 2 we present definitions for the mobility metrics investigated in this paper. In Section 3 we develop an expression for the PDF of the separation distance between an arbitrary pair of mobile nodes after one epoch, and generalize the results to a network of nodes with i.i.d. mobility. In Section 4 we develop a Markov chain model for the evolution of the separation distance between two nodes. This Markov model is applied, in Section 5, to the determination of expressions for a range of mobility metrics. In Section 6 we compare our theoretical and simulation results. Finally, we present conclusions in Section 7.

2 Mobility Metric Definitions

While fading links are the norm in wireless communication networks [7], the existing literature on mobility in MANETs concentrates on ``binary'' links. That is, links are understood to be ``on'' or ``off'' at any point in time. Schemes which use network topology information are sensitive to the length of time for which a link is consistently ``on''. Therefore, we consider the following metrics, which assume that the link is ``on'', and ask how long it will continue to be ``on''.

• Link Persistence, $\mathcal{P}_{L}(k)$ : Given an active link between two nodes at time 0, the persistence of this link, $\mathcal{P}_{L}(k)$ , until (at least) epoch $k$ is defined as the probability that the link continuously lasts until epoch $k$ .

  $$\mathcal{P}_{L}(k) \triangleq \Pr\{ k\vert \textsl{0}\}$$ (1)

  
  

• Link Residual Time, $\mathcal{R}_L$ : Given an active link between two nodes at time 0, the link residual time, $\mathcal{R}_L$ , is the length of time for which the link will continue to exist until it is broken.
• Path Persistence, $\mathcal{P}_{P}(k;h)$ : Given an active path with $h$ hops between two nodes at time 0, the path persistence, at epoch $k$ , is defined as the probability that the path will continuously last until at least epoch $k$ .

  $$\mathcal{P}_{P}(k;h) \triangleq \Pr\{ k\vert \textsl{0}\}$$ (2)

  
  

• Path Residual Time, $\mathcal{R}_P(h)$ : Given an active path with $h$ hops between two nodes at time 0, the path residual time, $\mathcal{R}_P(h)$ , is the length of time for which the path will continue to exist.

3 Node Separation After One Epoch

In this paper, we assume that each mobile node moves with a velocity uniformly distributed in both speed, $V$ , and direction, $\Phi$ . Both the speed and direction change in each epoch but are constant for the duration of an epoch, and independent of each other. The speed has mean, $\overline {v}$ , and variance $\delta^2/3$ , such that $V\in\{\overline{v}-\delta, \overline{v}+\delta\}$ . The direction, $\Phi$ , is uniformly distributed in $[0, 2\pi )$ . This random mobility model is widely used to analyze route stability in multi-hop mobile environments [11,13,1].

The status of a wireless link depends on numerous system and environmental factors that affect transmitter and receiver transmission range. A widely applied, albeit optimistic, model is used in this paper, whereby transmission range is approximated by a circle of radius $r$ corresponding to a signal strength threshold. If the separation distance between a given pair of nodes is less than $r$ , it is assumed the link between them is active. Let the random variable representing the separation distance between two nodes at epoch $m$ be $L_m$ , and let $l_m$ denote an instance of $L_m$ . The PDF, $f_{L_{m+1}\vert L_m}(l_{m+1}\vert l_m)$ , forms a basis for the derivations of expressions for the metrics given in Section 2. We derive this PDF below.

3.1 Relative Movement Between $2$ Nodes

To determine $f_{L_{m+1}\vert L_m}(l_{m+1}\vert l_m)$ , we begin with the PDF of the relative movement between a given pair of nodes, labelled $i$ and $j$ . The relationship between the relative movement vector, $\overrightarrow{X}$ , in any given epoch, and the node velocity vectors, $\overrightarrow{V_i}$ and $\overrightarrow{V_j}$ , is $\overrightarrow{X} = \overrightarrow{V}_j - \overrightarrow{V}_i$ , as depicted in Fig. 1. Let $X$ be the random variable representing the magnitude of $\overrightarrow{X}$ , similarly for $V_i$ and $V_j$ . Let $\Psi$ be the angle between $\overrightarrow{V_i}$ and $\overrightarrow{V_j}$ . As $X = \sqrt{V_i^2+V_j^2-2V_iV_j\cos\Psi}$ , we use the Jacobian transform to obtain the joint PDF:

$$f_{X, V_i, V_j}(x,v_i,v_j) =$$

$$\frac{2x f_{\Psi,V_i,V_j}(\psi,v_i,v_j)} {\sqrt{2v_i^2v_j^2+2v_i^2x^2+2v_j^2x^2-v_i^4-v_j^4-x^4}}.$$ (3)

Figure 1: Relationship between the node movement vectors $\overrightarrow{V}_i$ and $\overrightarrow{V}_j$ of nodes $i$ and $j$ , relative movement vector, $\overrightarrow{X}$ , initial separation distance, $l_m$ , and separation vector, $\overrightarrow{L}_{m+1}$ .

As $\Psi$ is uniformly distributed in $[0, \pi)$ and $V_i$ , $V_j$ and $\Psi$ are independent, we can simplify (3) to

$$f_{X, V_i, V_j}(x,v_i,v_j) =$$

$$\frac{x}{2\pi\delta^2 \sqrt{2v_i^2v_j^2+2v_i^2x^2+2v_j^2x^2-v_i^4-v_j^4-x^4}}.$$ (4)

Then the marginal PDF of the magnitude of the relative movement is,

$$f_X(x) = \int_{\overline{v}-\delta}^{\overline{v}+\delta} \int... ...verline{v}-\delta}^{\overline{v}+\delta} f_{X, V_i, V_j}(x,v_i,v_j) dv_i dv_j.$$ (5)

Thus, (4) and (5) describe the behaviour of the relative distance, $X$ , between a given pair of nodes, $i$ and $j$ , in any one epoch.

3.2 Calculation of the Separation Distance

From Fig. 1, $\overrightarrow{L}_{m+1}$ = $\overrightarrow{l}_m$ + $\overrightarrow{X}$ . Let $\Theta$ from Fig. 1 be uniformly distributed in the interval $[0, 2\pi )$ . The conditional PDF is

$$f_{L_{m+1}\vert L_m,\Theta}(l_{m+1}\vert l_m,\theta) = f_{X,\Theta}(x,\theta)\left\vert\frac{\partial(x,\theta)} {\partial(l_{m+1},\theta)}\right\vert$$

$$= f_{X,\Theta}(x,\theta) \frac{l_{m+1}} {\sqrt{ l_{m+1}^2-l_m^2\sin^2\theta}},$$ (6)

where $x = l_m\cos\theta\pm\sqrt{l_{m+1}^2-l_m^2\sin^2\theta}$ . Since the magnitude and phase are independent, we obtain

$$f_{L_{m+1}\vert L_{m}}(l_{m+1}\vert l_m) = \frac{2}{\pi}\int_0^{\pi} f(x) \frac{l_{m+1}} {\sqrt{ l_{m+1}^2-l_m^2\sin^2\theta}} d\theta,$$ (7)

where $0 \leq x \leq\max(V_i+V_j)$ , due to the triangular relationship between $\overrightarrow{X}$ , $\overrightarrow{V_i}$ and $\overrightarrow{V_j}$ .

Next, we use $f_{L_{m+1}\vert L_m}(l_{m+1}\vert l_m)$ to derive the node separation distance PDF after $k$ epochs.

4 Markov Chain Model of Separation

In Section  we derived the PDF of the distance between a given pair of nodes in epoch $m+1$ , $m\in Z^+$ , given the separation distance in epoch $m$ . That is, the separation distance in epoch $m$ can be represented as a random variable, $L_m$ . The evolution of the separation distance can be represented by a sequence of random variables, $\{\cdots, L_{m-1}, L_m, L_{m+1}, \cdots\}$ . So, the relationship between the separation distances in a sequence of epochs readily lends itself to modelling via a Markov chain process.

4.1 Transition Model

Figure 2: State space for distance between a pair of nodes, where separations outside of the transmission range (absorbing state) result in a link being discarded.

We first define the state space governing the range of node separation distances, $0 \le l_m < \infty$ . We divide the interval $[0,r)$ into $n$ bins of width $\varepsilon$ . If a link is active, $l_m$ falls into one of these bins, as shown in Fig. 2. The $i$ th bin corresponds to the $i$ th state, denoted $e_i$ . The $(n+1)$ th state, corresponding to $l_m>r$ , is defined as the absorbing state. A separation distance in the absorbing state indicates a broken link. If the nodes move back within communication range, a new link is considered to have been formed. The distance, $L_m$ , is in $e_i$ if the following conditions hold,

$$\left \{ \begin{array}{l} L_m \in e_i \Leftrightarrow \varepsil... ...ightarrow l_m > r \ i = n+1. \end{array}\right.$$ (8)

4.2 Initial Condition Vector

The initial condition vector denotes the probability of the initial separation distance, $L_0$ , being in each state at time 0. It has entries

$$p_{e_i}(0) = \Pr(L_0 \in e_i).$$ (9)

We assume nodes are initially uniformly distributed. Since they move according to a random walk, they remain (approximately) uniformly distributed in the transmission region. Therefore, if a link exists the initial separation distance, $L_0$ , has a linear distribution [5]:

$$f_{L_0}(l_0) = \frac{2l_0}{r^2} 0 \leq l_0 \leq r,$$ (10)

$$p_{e_i}(0) = (2i-1)\frac{\epsilon^2}{r^2} 0 \leq i \leq n.$$ (11)

4.3 Transition Matrix

Figure 3: Shows $a_{ij}$ , the probability of transferring from $e_i$ to $e_j$ after one epoch, for various $j$ .

Let $L_m$ be in $e_i$ . Then, after one epoch, $L_{m+1}$ , must be in the range $[l_m-2(\overline{v}+\delta),l_m+2(\overline{v}+\delta)]$ . This corresponds to $L_{m+1}$ being in $e_j$ such that $j \in [\max(1,i-\gamma), \min(i+\gamma,n+1)]$ , where $\gamma = \lceil 2(\overline{v}+\delta)/\varepsilon \rceil$ , is the maximum number of bins that can be traversed in a single epoch. The transition matrix is denoted by

$$A = \left[ \begin{array}{cccc} a_{11} & \cdots & a_{1,n} & a_{1... ...& \cdots & a_{n,n} &a_{n,n+1} 0 & \cdots &0 & 1 \end{array} \right],$$ (12)

where $a_{ij}$ is the probability of transition from $e_i$ to $e_j$ in a given epoch. We note that $\forall i, j, a_{ij} \geq 0$ and $\sum _{j }a_{ij} = 1$ . The last row in (12) represents transition from absorbing state.

To calculate the transition probabilities between non-absorbing states, illustrated in Fig. 3, consider the state transition probabilities at epoch $m$ , and using (7)

$$a_{ij} = \Pr{ ( e_j \leftarrow e_i)}$$ (13)

$$= \int_{(j-1)\varepsilon}^{j \varepsilon} \int_{(i-1)\varepsilon}^{i \varepsilon} f_{L_{m+1}\vert L_m}(l_{m+1}\vert l_m)f_{L_m}(l_m) dl_mdl_{m+1}.$$

The PDF $f_{L_m}(l_m)$ changes with $m$ . However, if $\varepsilon$ is sufficiently small, and $e_i$ is known, we can assume that $l_m$ is approximately uniformly distributed within the $i$ th bin. In this case,

$$f_{L_m}(l_m) \approx 1/\varepsilon.$$ (14)

Moreover, we can approximate the PDF of the conditioned separation distance from any point in $e_i$ to any point in $e_j$ using the midpoints of the two states:

$$f_{L_{m+1}\vert L_m}(l_{m+1}\vert l_m) \approx f_{L_{m+1}\vert L_m}\left [(j-1/2)\varepsilon \vert (i-1/2)\varepsilon \right ].$$ (15)

Thus, from (13), (14) and (15) we can write

$$a_{ij} \approx \varepsilon f_{L_{m+1}\vert L_m}\left[(j-1/2)\varepsilon\vert(i-1/2)\varepsilon\right].$$ (16)

4.4 Distribution After $k$ Epochs

According to the properties of Markov Chains, we can use $A$ and $P(0)$ to determine the probability of the separation distance being in state $e_i$ after $k$ epochs:

$$P(k) = [p_{e_1}(k) p_{e_2}(k) \cdots p_{e_{n+1}}(k)] = P(0) A^k,$$ (17)

5 Mobility Metric Calculations

Having developed a Markov chain model for the evolution of the node separation, we now derive expressions for the mobility metrics defined in Section 2.

5.0.0.1 Link Persistence, $\mathcal{P}_{L}(k)$ :

The probability of the link being in existence after $k$ epochs is the probability that the separation distance is in a non-absorbing state:

$$\mathcal{P}_{L}(k) = \sum_{i=1}^{n} p_{e_i}(k) = 1-p_{e_{n+1}}(k),$$ (18)

where $p_{e_i}(k)$ can be calculated from (17).

5.0.0.2 Link Residual Time, $\mathcal{R}_L$ :

The CDF, $F_{\mathcal{R}_L}(k)$ , of the link residual time, is:

$$F_{\mathcal{R}_L}(k) = \Pr\{\mathcal{R}_L \leq k\} = 1 - \mathcal{P}_{L}(k).$$ (19)

Then, the PDF of the link residual time is

$$f_{\mathcal{R}_L}(k) = \Pr\{\mathcal{R}_L =k\}=\mathcal{P}_{L}(k-1)-\mathcal{P}_{L}(k).$$ (20)

The expected value of the link residual time is

$$E\{\mathcal{R}_L\} = \sum_{k=1}^{\infty} k  f_{\mathcal{R}_L}(k) = \sum_{k=1}^{\infty}k  [\mathcal{P}_{L}(k-1)-\mathcal{P}_{L}(k)].$$ (21)

5.0.0.3 Path Persistence, $\mathcal{P}_{P} \left(k;h\right)$ :

For a path to persist, each of the component links must persist:

$$\mathcal{P}_{P} \left(k;h\right) = \prod_{i=1}^{h} \mathcal{P}_{L} (k).$$ (22)

5.0.0.4 Path Residual Time, $\mathcal{R}_P(h)$ :

The CDF, $F_{\mathcal{R}_P(h)}(k;h)$ , of the path residual time is

$$F_{\mathcal{R}_P(h)}(k;h)= \Pr\{\mathcal{R}_P(h)\leq k\} = 1 - \mathcal{P}_{P}(k;h)$$ (23)

Therefore, the PDF of the path residual time is

$$f_{\mathcal{R}_P(h)}(k;h) = \mathcal{P}_{P}(k-1;h)-\mathcal{P}_{P}(k;h).$$ (24)

And, the expected value of the path residual time is

$$E\{\mathcal{R}_P(h)\} = \sum_{k=1}^{\infty}k  [\mathcal{P}_{P}(k-1;h)-\mathcal{P}_{P}(k;h)].$$ (25)

6 Simulation Results

We verify all analytically derived expressions for the mobility metrics by simulation. The simulations were conducted with MNs moving according to the description in Section 3.

The network consisted of $100$ nodes initially placed randomly in a square plane of side $1000$ distance units. We use the generic term ``units'' rather than, say, m or km because it is the relative and not the absolute distances that are important. Each MN had a maximum transmission range of $r=100$ units, with between $1000$ and $5000$ epochs per trial for $3000$ trials.

Figure 6 illustrates the comparisons of the simulation results to the theoretical calculations. The link persistence, shown in Fig. 4(a), decreases with increasing simulation time and, at a greater rate with increasing ratio of mean node speed to transmission range, $\overline{v}/r$ . Further, the path persistence drops off at a greater rate than the link persistence, for the same mean node speed, as would be expected. The path persistence also drops off more quickly with an increased number of hops, as there is more chance of an individual link breaking.

In the bounded simulation environment, MNs were ``reflected'' back into the simulation area, if their movement would otherwise take them outside. Consequently, nodes near the edge are more likely to remain in transmission range, and the link persistence is artificially increased, compared to that for the unbounded simulation area. The experimental results for the bounded area are still close to the calculated results, as expected, though not as well matched.

The expected link and path residual times have been plotted against the second order of $r/\overline{v}$ , each showing a linear relationship, particularly for larger ratios. As expected, $E\{\mathcal{R}_P\}$ is much lower than $E\{\mathcal{R}_L\}$ for the same communication range to speed ratio. Finally, the probability distributions of $\mathcal{R}_L$ and $\mathcal{R}_P$ show that the path residual time is more likely to have a shorter length, in epochs, than the link residual time.

Figure 4: Comparison of the mobility metric calculations and simulated results. Each MN moves at a randomly chosen velocity during each epoch, which has uniformly distributed speed with mean $\overline {v}$ , and uniformly distributed direction in the range $[0, 2\pi )$ . The ``shape'' plots in each figure indicate simulated results, while the solid lines indicate calculated values with the relevant equations within the paper. The vertical bar indicates the $95\%$ confidence interval for the unbounded scenario.

[a]

[b]

[c]

[d]

[e]

[f]

7 Conclusions

Frequent changes in network topology caused by mobility in MANETs imposes great challenges for developing efficient routing algorithms. The theoretical analysis framework presented in this paper provides a better understanding of network behavior under mobility and some fundamental work on the issue of path stability. We propose link persistence and path persistence for evaluating link and path stability. The Markov chain model used in this paper, has enabled us to accurately determine a series of mobility metrics. These calculations are useful for comparison of artificial mobility behaviours with actual network implementation scenarios. The analytical results can be readily applied to various adaptive routing protocols that use corresponding mobility metrics.

Bibliography

1

B. An and S. Papavassiliou.
An Entropy-Based Model for Supporting and Evaluating Route Stability in Mobile Ad Hoc Wireless Networks.
IEEE Commun. Lett., 6(8):328-330, 2002.

2

F. Bai, N. Sadagopan, and A. Helmy.
IMPORTANT a Framework to Systematically Analyze the Impact of Mobility on Performance of Routing Protocols for Ad Hoc Networks.
In IEEE INFOCOM, volume 2, pages 825-835, April 2003.

3

T. Camp, J. Boleng, and V. Davies.
A Survey of Mobility Models for Ad Hoc Network Research.
Wireless Commun. and Mobile Computing (WCMC), 5(2):483-502, 2002.

4

M. Gerharz, C. Waal, and P. Martini.
Strategies for Finding Stable Paths in Mobile Wireless Ad Hoc Networks.
In Proc. of IEEE Conf. on Local Computer Networks (LCN), pages 130-139, October 2003.

5

D. Hong and S. Rappaport.
Traffic Model and Performance Analysis for Cellular Mobile Radio Telephone Systmes with Prioritized and Nonprioritized Handoff Procedures.
IEEE Trans. Veh. Technol., 35:77-92, August 1986.

6

S. Jiang.
An Enhanced Prediction-based Link Availability Estimation for Manets.
IEEE Trans. Commun., 52(2):183-186, February 2004.

7

H. Jones, S. Xu, and K. Blackmore.
Link Ratio for Ad Hoc Networks in a Rayleigh Fading Channel.
WITSP, Australia, December 2004.

8

A. B. McDonald and T. Znati.
A Mobility Based Framework for Adaptive Clustering in Wireless Ad-Hoc Networks.
IEEE J. Select. Areas Commun., 17(8):1466-1487, August 1999.

9

L. Qin and T. Kunz.
Increasing Packet Delivery Ratio in DSR by Link Prediction.
In Proc. 36th Hawaii Int. Conf. on Syst. Sciences, January 2002.

10

N. Sadagopan, F. Bai, B. Krishnamachari, and A. Helmy.
PATHS: Analysis of PATH Duration Statistics and Their Impact on Reactive MANET Routing Protocols.
In MobiHoc 03, pages 246-256, June 2003.

11

P. Samar and S. B. Wicker.
On the Behavior of Communication Links of a Node in a Multi-Hop Mobile Envirionment.
In Proceedings of MobiHoc, pages 145-156, May 2004.

12

W. Su, S.J. Lee, and M. Gerla.
Mobility Prediction and Routing in Ad Hoc Wireless Networks.
Int. J. of Network Management, 2000.

13

D. Yu and H. Li.
Path Availability in Ad Hoc Networks.
IEEE ICT Conf., 1:383-387, 2003.

About this document ...

Mobility Assessment for MANETs Requiring Persistent Links

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -show_section_numbers -local_icons mobhtml.tex

The translation was initiated by Sanlin Xu on 2005-05-10

WiTMeMo '05 Home USENIX home