Topology Property Based on Network Tomography for Wireless Mobile Multihop Communication Network

Abstract

The random movement of nodes makes the dynamic topology structure be one of the most important characteristics in wireless multihop communication network, which makes the description and quantization of the dynamic property the very foundation of the design, simulation, and measurement for this kind of network. The distributions of the link duration and the topology duration will be derived and verified by simulations. Then, the topology flapping sensing method has been put forward based on TTL. Finally, the probability model of the topology stability in the measurement time has been established and calculated based on network tomography for wireless mobile multihop communication network in this paper. Simulating results verify the correctness and efficiency of the approach, which will provide the technique basis of research on the dynamic property and end-to-end measurement for wireless mobile multihop communication network.

1. Introduction

A wireless mobile multihop communication network is a self-configuring infrastructureless network of mobile devices connected by wireless links, with a typical example as mobile ad hoc network (MANET), vehicle ad hoc network (VANET), wireless sensor network (WSN), and so on. Each device in such a kind of network is free to move independently in any direction and will therefore change its links to other devices frequently. Each must forward traffic unrelated to its own use and therefore be a router. The primary challenge in building a wireless mobile multihop communication network is equipping each device to continuously maintain the information required to properly route traffic, which is quite difficult since the topology caused by nodes movement keeps changing [1, 2]. Relevant studies indicate that the overall performance of wireless mobile multihop communication network is closely related to the adaptability of the network protocol to the dynamic property. The description and quantization of the dynamic property are the foundation of design, simulation, and measurement for wireless mobile multihop communication network [3]. The topology duration is always adopted to measure the dynamic property in relevant researches [4]. Luo et al. have made analysis of four common moving model link distributed functions and pointed out by both theoretical and simulating way that the distribution would never be described by a simple probability distributed function [5]. With a longer route, the link duration distribution would approach an exponential distribution, which has been verified by [6]. The work in [7] established a relational model of route and link duration. The inconsistency of probability distributed function, however, appeared when the length of route is 1.

The network tomography is the science of inferring performance characteristics of the network interior by correlating sets of the end-to-end measurements [8]. The strength of protocol and the forwarding nodes being independent are quite appropriate for wireless mobile multihop communication network. Generally, the network tomography problems can be approximately described by a linear model as $\mathit{Y}=\mathit{A}\theta +\epsilon$ , where $\mathit{Y}$ is the measurement vector by observation, $\mathit{A}$ is the route matrix, θ is the parameter vector to be estimated, and ε is the error vector, which has often been ignored for simplification, and the vector function $\mathit{X}$ with respect to θ has been taken to substitute θ, so there is $\mathit{Y}=\mathit{A}\mathit{X}$ . The work in [9, 10] discussed the measuring techniques for wireless ad hoc networks based on the network tomography. However, the researches in existence seldom take the dynamic property into account which has an impact on the adaptation of the network tomography. A TTL (TTL, time-to-live) based topology flapping sensing method will be put forward in this paper, and the topology duration distribution will be derived as well. Finally, the probability model of the topology stability in the measurement time will be established and calculated for wireless mobile multihop communication network. The paper is organized as follows. Section 2 gives the mathematical model based on network tomography for wireless mobile multihop communication network. The topology flapping sensing model and scheme is described in Section 3. Section 4 presents the dynamic property of the network. Section 5 will discuss the measurement time constraints. The conclusions are summarized in Section 6.

2. Mathematical Model

The network tomography is usually adopted on the premise of the fixed or already-known network topology [11, 12]. However, the nodes random movement raises new limitations for the network tomography in wireless mobile multihop communication network [13], since the false route information $\mathit{A}$ will produce errors for $\mathit{X}$ . There are two ways to resolve the contradiction between the dynamic topology for wireless mobile multihop communication network and the fixed or already-known topology premise for network tomography [14, 15]:

• (1)

to sense the topology flapping by data measurement and to make further deduction by the obtained information before or after the topology changing,

(2)

to shorten the measuring time to make the probability of topology flapping acceptable when the topology changing is imperceptible.

Let $\stackrel{-}{\alpha }$ be the average probability of the topology flapping not being sensed in the measurement duration ${\tau }_M$ , and let $\alpha =\mathrm{1}-\stackrel{-}{\alpha }$ be the correct rate. That is to say, given the correct rate α, the average maximum measurement duration will be ${\tau }_M$ , which is called the time constraint. Assume the topology flapping sensing rate is η; then the topology flapping occurring probability in ${\tau }_M$ will be $\gamma ({\tau }_M)$ , and there is

$$\begin{array}{cc}& \alpha =\mathrm{1}-\gamma \left({\tau }_M\right)\left(\mathrm{1}-\eta \right).\end{array}$$

(1)

The topology flapping caused by nodes movement will be considered in this paper. Researches show that the factors which impact the measurement time constraint usually fall into one of three categories: $(1)$ the parameters of the network dynamic property, including the nodes velocity, transmitting radius, scene area, and number of nodes; $(2)$ the parameters of the network scale, including the number of source and destination nodes; $(3)$ the inferring accuracy of the user requirement; the higher the requirement, the less the measurement time, so as to reduce the probability of the topology changing without being sensed during the measurement period. In a single measurement, the topology of wireless multihop communication network is known [16] so a more precise computational procedure could be adopted, such as taking the length information of each path as in (2), where $l_s$ is the length of the path s:

$$\begin{array}{cc}& \alpha =\mathrm{1}-\gamma \left({\tau }_M\mid l_s\right)\left(\mathrm{1}-\eta \left(l_s\right)\right).\end{array}$$

(2)

Mobility is one of the most important characters for wireless mobile multihop communication network, and the movement conditions of the nodes are various. We focus the research on the velocity of 0.5 m/s~2 m/s which is according with the walking speed. During the performance analysis in the following parts, NS2.34 will be adopted to simulate the wireless mobile multihop network with walking speed, and the related parameters settings will be as follows: the number of nodes N is 20~60; the minimum and maximum speed of the nodes are 0.5 m/s and 2 m/s, respectively; the network scene is square with 1250 m, 2500 m, and 5000 m on the side; the pause time is 0 s; the coverage radius is 250 m.

3. Topology Flapping Sensing

The impact of the dynamic property on network tomography inferring result will be alleviated effectively by sensing the topology flapping according to the hop changes of the detecting packets. The probability η of the topology flapping sensed by detecting packets is equivalent to the probability of the path length changing when the route changes. TTL is usually adopted in Internet [17], and recent researches have indicated that 80% of changes in end-to-end path are caused by the changes of the route length. Few studies, however, are carried out in wireless mobile multihop communication network. η has a close relationship with the length of paths, the probability of connections, and the number of nodes. The global estimation of η will be obtained by random waypoint model [18]. Simulating results in walking speed scenes indicate that η is inversely proportional to the connection probability as shown in Figure 1. That is mainly because the average path length is large with a small connection probability and the probability of an equal route length in two successive selections will be small. Comparing with the connection probability, η is weakly correlated with the number of nodes though appearing as an inverse proportion as well. Therefore, to sense the topology flapping by the TTL changes of the detecting packets is an effective way for wireless mobile multihop communication network with a sensing rate over 50%.

Figure 1

Topology flapping sensing rate by TTL in a typical wireless mobile multihop communication.

4. Dynamic Property Analysis

The definitions of the link and the route duration have been given out in [19, 20], where the one lying on the connectivity graph level has been adopted in this paper. The meaning of some main parameters will be defined as follows.

• (1)

The topology duration is the time interval between all links from each source to each destination being established and one of them is being interrupted.

(2)

The route duration is the special case of the topology duration with the number of the source node and the destination node is 1 for both.

(3)

The frequency distributed function of the topology duration denoted as $F_n(t)$ is the ratio of the frequency of the topology duration being smaller than t and the big enough simulating times n.

(4)

The time distributed function of the topology duration denoted as $F_t(t)$ is the ratio of total time with the topology duration being smaller than t and the total duration in n times simulation.

It can be noticed that the frequency distributed function and the time distributed function are describing the probability of duration in different viewpoints and they satisfy the relationship as shown in (3), where

$$\begin{array}{cc}& F_t\left(t\right)=\frac{\mathrm{1}}{C}{{\displaystyle \int }}_{\mathrm{0}}^{t}x{F}_n^{\prime }\left(x\right)\text{d}x.\end{array}$$

(3)

Existing researches in link duration usually take the first definition, while the time distributed function should be adopted as the distributed function of topology duration with regard to wireless mobile multihop communication network with high dynamic property.

4.1. Link Duration

The link duration is an important parameter to measure the dynamic property of wireless mobile multihop communication network. Since the link duration equals the time taken by two nodes passing through the coverage of each other, the value only depends on the relative velocity of these two nodes and their communication radius. Accordingly, it is necessary to derive the probability distributed function of the link duration for the random waypoint model. The mobility model of wireless mobile multihop communication network should satisfy the following assumptions: $(1)$ the network area is much larger than the node coverage; $(2)$ the node moving direction obeys the uniform distribution on $[\mathrm{0,2}\pi )$ ; that is to say, the mobility model has no direction specificity with the pause time as 0.

The probability distribution of the link duration equals the product of the probability distribution of the link duration ${\lambda }_{\mathrm{12}}$ and the velocity probability of the mobility model in the condition of any two nodes ( $n_1$ , $n_2$ ) with the velocity known and the angle φ between the relative velocity directions obeying the uniform distribution on $[\mathrm{0,2}\pi )$ , as shown in the following equation:

$$\begin{array}{l}{F}_t\left(t\right)=\iint F_t\left({\lambda }_{\mathrm{12}}\mid v_{\mathrm{1}},v_{\mathrm{2}},f\left(\phi \right)=U\left(\mathrm{0,2}\pi \right)\right)\\ \hspace{1em}\hspace{1em}\times f_v\left(v_{\mathrm{1}}\right)f_v\left(v_{\mathrm{2}}\right)\text{d}{v}_{\mathrm{1}}\text{d}{v}_{\mathrm{2}}.\end{array}$$

(4)

Since the link duration between any two nodes in a wireless mobile multihop communication network is independent identical distribution, the distribution of the network link duration is the same as the distribution of any link duration. The velocity of $n_1$ and $n_2$ is $v_1$ and $v_2$ , respectively, which are the independent identical distribution. $F_t({\lambda }_{\mathrm{12}}\mid v_{\mathrm{1}},v_{\mathrm{2}})$ will be taken as the abbreviated form of $F_t({\lambda }_{\mathrm{12}}\mid v_{\mathrm{1}},v_{\mathrm{2}},f(\phi )=U(\mathrm{0,2}\pi ))$ in this paper. Assume the link has been established by $n_1$ and $n_2$ at $(r_{\mathrm{0}},\theta )$ as shown in Figure 2. There is ${\theta }_v\in (\pi /\mathrm{2}+\theta ,\mathrm{3}\pi /\mathrm{2}+\theta )$ .

Figure 2

$n_2$ passing through the coverage of $n_1$ .

Since the velocity of $n_1$ is higher than that of $n_2$ , the link establishment can only lie in the fore semicircle covered by $n_1$ . Considering the symmetry, the condition of $\theta \in [\mathrm{0},\pi /\mathrm{2})$ will only be taken into account in derivation. Since ${\lambda }_{\mathrm{12}}=\mathrm{1}/v$ , according to Figure 2, there will be $l=\mathrm{2}{r}_{.\mathrm{0}}\cos (\theta +\beta )$ or $l=\mathrm{2}{r}_{.\mathrm{0}}\cos (\theta -{\beta }^{\prime })$ . The relationship between $v_1$ , $v_2$ , and v with $k>1$ can be seen in Figure 3.

Figure 3

Relationship between $v_1$ , $v_2$ , and v with $k>1$ .

So there will be

$$\begin{array}{cc}& {\theta }_v=\pi -\beta =\pi -\arcsin \frac{\sin {\theta }_{v_{\mathrm{2}}}}{\sqrt{\mathrm{1}-\mathrm{2}k\cos {\theta }_{v_{\mathrm{2}}}+k^{\mathrm{2}}}},\\ v=v_{\mathrm{2}}\sqrt{\mathrm{1}-\mathrm{2}k\cos {\theta }_{v_{\mathrm{2}}}+k^{\mathrm{2}}}.\end{array}$$

(5)

In a condition with the given value of θ, the range of the links being established is $\mathrm{\Theta }$ , and there will be

$$\begin{array}{cc}& \mathrm{\Theta }=\{\begin{array}{cc}\left[\mathrm{0},\theta -\alpha \right)\cup \left(\theta +\alpha ,\mathrm{2}\pi \right),\hfill & k\cos \theta <\mathrm{1}\hfill \\ \left[\mathrm{0,2}\pi \right),\hfill & k\cos \theta \ge \mathrm{1},\hfill \end{array}\end{array}$$

(6)

where $\alpha =\text{arccos}(k\cos \theta )$ . The value range of ${\theta }_{v_{\mathrm{2}}}$ with ${\lambda }_{\mathrm{12}}<t$ is denoted as $\mathrm{\Psi }$ .

Assume the link between $n_1$ and $n_2$ has been established for $N_{12}$ times during $n_1$ moving for $T_{\text{mov}}$ , and the movement covering area is Q, as shown in Figure 4. $n_1$ will set up the connection with $n_2$ in the angle range of $(\theta ,\theta +\mathrm{\Delta }\theta )$ , and the velocity direction will lie in $({\theta }_{v_{\mathrm{2}}},{\theta }_{v_{\mathrm{2}}}+\mathrm{\Delta }{\theta }_{v_{\mathrm{2}}})$ with the times of connection as $\mathrm{\Delta }m$ . Here $\mathrm{\Delta }m$ equals the product of the area of relative movement of $\mathrm{\Delta }d$ in $T_{\text{mov}}$ and the probability density of $n_2$ as shown in the following equation:

$$\begin{array}{l}\mathrm{\Delta }m=\frac{\mathrm{\Delta }{\theta }_{v_{\mathrm{2}}}}{\mathrm{2}\pi }\frac{S}{Q_{\mathrm{\Delta }{\theta }_{v_{\mathrm{2}}}\to \mathrm{0}}^{\mathrm{\Delta }\theta \to \mathrm{0}}}\\ =\frac{\mathrm{1}}{\mathrm{2}\pi Q}{r}_{\mathrm{0}}v{T}_{\text{mov}}\mathrm{\Delta }{\theta }_{v_{\mathrm{2}}}\mathrm{\Delta }\theta \sin \left({\theta }_v-\theta -\frac{\pi }{\mathrm{2}}\right).\end{array}$$

(7)

Accordingly, the distributed function of link duration will be calculated by the following equation:

$$\begin{array}{l}{F}_t\left({\lambda }_{\mathrm{12}}\mid v_{\mathrm{1}}>v_{\mathrm{2}}\right)\\ \hspace{1em}\hspace{1em}=\underset{\begin{array}{l}\mathrm{\Delta }{\theta }_{v_{\mathrm{2}}}\to \mathrm{0}\\ \mathrm{\Delta }\theta \to \mathrm{0}\\ T_{\text{mov}}\to \infty \end{array}}{\lim }\frac{\mathrm{1}}{{{\displaystyle \sum }}_{\theta \in \left[\mathrm{0},\pi /\mathrm{2}\right)}^{}{{\displaystyle \sum }}_{{\theta }_{v_{\mathrm{2}}}\in \mathrm{\Theta }}^{}\mathrm{\Delta }m}{\displaystyle \sum }_{\theta \in \left[\mathrm{0},\pi /\mathrm{2}\right)}{\displaystyle \sum }_{{\hspace{0.17em}\theta }_{v_{\mathrm{2}}}\in \mathrm{\Psi }}\mathrm{\Delta }m.\end{array}$$

(8)

Then the distributed function of link duration with $v_1>v_2$ will be as shown in (9), where $\mathrm{\Theta }$ satisfies (10). Similar to the condition above, when $v_2>v_1$ , the link establishing point may be in the whole coverage circle of $n_1$ . In view of the symmetry, only the condition of $\theta \in [\mathrm{0},\pi )$ has to be considered in derivation. When there is $\theta \in [\mathrm{0},\pi /\mathrm{2})$ , the value range of ${\theta }_{v_{\mathrm{2}}}$ will be ${\mathrm{\Theta }}_{\mathrm{1}}=(\alpha +\theta ,\mathrm{2}\pi +\theta -\alpha )$ and $\alpha =\text{arccos}(k\cos \theta )$ . When there is $\theta \in [\pi /\mathrm{2},\pi )$ , the value range of ${\theta }_{v_{\mathrm{2}}}$ will be ${\mathrm{\Theta }}_{\mathrm{2}}=(\mathrm{0},\alpha +\theta -\pi )\cup (\pi +\theta -\alpha ,\mathrm{2}\pi )$ and there will be $\alpha =\text{arccos}(k\cos (\pi -\theta ))$ . Let ${\mathrm{\Theta }}_{\mathrm{11}}$ , ${\mathrm{\Theta }}_{\mathrm{12}}$ , ${\mathrm{\Theta }}_{\mathrm{21}}$ , and ${\mathrm{\Theta }}_{\mathrm{22}}$ substitute the value range as shown in (11); then there is ${\mathrm{\Theta }}_{\mathrm{1}}={\mathrm{\Theta }}_{\mathrm{11}}\cup {\mathrm{\Theta }}_{\mathrm{12}}$ and ${\mathrm{\Theta }}_{\mathrm{2}}={\mathrm{\Theta }}_{\mathrm{21}}\cup {\mathrm{\Theta }}_{\mathrm{22}}$ . Consider

$$\begin{array}{cc}& \begin{array}{c}\begin{array}{c}{F}_t\left({\lambda }_{\mathrm{12}}\mid v_{\mathrm{1}}>v_{\mathrm{2}}\right)=\frac{{{\displaystyle \int }}_{\mathrm{0}}^{\pi /\mathrm{2}}{{\displaystyle \int }}_{{\theta }_{v_{\mathrm{2}}}\in \mathrm{\Psi }}\sqrt{\mathrm{1}-\mathrm{2}k\cos {\theta }_{v_{\mathrm{2}}}+k^{\mathrm{2}}}\sin \left(\pi /\mathrm{2}-\theta -\arcsin \left(\sin {\theta }_{v_{\mathrm{2}}}/\sqrt{\mathrm{1}-\mathrm{2}k\cos {\theta }_{v_{\mathrm{2}}}+k^{\mathrm{2}}}\right)\right)\text{d}{\theta }_{v_{\mathrm{2}}}\text{d}\theta }{{{\displaystyle \int }}_{\mathrm{0}}^{\pi /\mathrm{2}}{{\displaystyle \int }}_{{\theta }_{v_{\mathrm{2}}}\in \mathrm{\Theta }}\sqrt{\mathrm{1}-\mathrm{2}k\cos {\theta }_{v_{\mathrm{2}}}+k^{\mathrm{2}}}\sin \left(\pi /\mathrm{2}-\theta -\arcsin \left(\sin {\theta }_{v_{\mathrm{2}}}/\sqrt{\mathrm{1}-\mathrm{2}k\cos {\theta }_{v_{\mathrm{2}}}+k^{\mathrm{2}}}\right)\right)\text{d}{\theta }_{v_{\mathrm{2}}}\text{d}\theta },\end{array}\end{array}\end{array}$$

(9)

$$\begin{array}{cc}& \mathrm{\Theta }=\{\begin{array}{cc}\left[\mathrm{0},\theta -\text{arccos}\left(k\cos \theta \right)\right)\cup \left(\theta +\text{arccos}\left(k\cos \theta \right),\mathrm{2}\pi \right),\hfill & k\cos \theta <\mathrm{1}\hfill \\ \left[\mathrm{0,2}\pi \right),\hfill & k\cos \theta \ge \mathrm{1},\hfill \end{array}\end{array}$$

(10)

$$\begin{array}{cc}& \hspace{0.17em}{\mathrm{\Theta }}_{\mathrm{11}}=\left(\text{arccos}\left(k\cos \theta \right)+\theta ,\mathrm{2}\pi -\text{arccos}\hspace{0.17em}k\right),\\ \hspace{0.17em}\hspace{1em}\hspace{1em}{\mathrm{\Theta }}_{\mathrm{12}}=\left(\mathrm{2}\pi -\text{arccos}\hspace{0.17em}k,\mathrm{2}\pi +\theta -\text{arccos}\left(k\cos \theta \right)\right),\\ \hspace{0.17em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}{\mathrm{\Theta }}_{\mathrm{21}}=\left(\mathrm{0},\text{arccos}\left(k\cos \left(\pi -\theta \right)\right)+\theta -\pi \right)\cup \left(\mathrm{2}\pi -\text{arccos}\hspace{0.17em}k,\mathrm{2}\pi \right),\\ \hspace{0.17em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{\mathrm{\Theta }}_{\mathrm{22}}=\left(\pi +\theta -\text{arccos}\left(k\cos \left(\pi -\theta \right)\right),\mathrm{2}\pi -\text{arccos}\hspace{0.17em}k\right).\end{array}$$

(11)

${\mathrm{\Psi }}_{\mathrm{11}}$ , ${\mathrm{\Psi }}_{\mathrm{12}}$ , ${\mathrm{\Psi }}_{\mathrm{21}}$ , and ${\mathrm{\Psi }}_{\mathrm{22}}$ represent the value range of ${\theta }_{v_2}$ in ${\mathrm{\Theta }}_{\mathrm{11}}$ , ${\mathrm{\Theta }}_{\mathrm{12}}$ , ${\mathrm{\Theta }}_{\mathrm{21}}$ , and ${\mathrm{\Theta }}_{\mathrm{22}}$ , respectively, with ${\lambda }_{\mathrm{12}}<t$ as follows:

$$\begin{array}{cc}& {\mathrm{\Psi }}_{\mathrm{11}}=\left\{{\theta }_{v_{\mathrm{2}}}\mid {\mathrm{\Gamma }}_{\mathrm{1}}<t,{\theta }_{v_{\mathrm{2}}}\in {\mathrm{\Theta }}_{\mathrm{11}},\theta \in \left[\mathrm{0},\pi /\mathrm{2}\right)\right\},\\ {\mathrm{\Psi }}_{\mathrm{12}}=\left\{{\theta }_{v_{\mathrm{2}}}\mid {\mathrm{\Gamma }}_{\mathrm{2}}<t,{\theta }_{v_{\mathrm{2}}}\in {\mathrm{\Theta }}_{\mathrm{12}},\theta \in \left[\mathrm{0},\pi /\mathrm{2}\right)\right\},\\ {\mathrm{\Psi }}_{\mathrm{21}}=\left\{{\theta }_{v_{\mathrm{2}}}\mid {\mathrm{\Gamma }}_{\mathrm{2}}<t,{\theta }_{v_{\mathrm{2}}}\in {\mathrm{\Theta }}_{\mathrm{21}},\theta \in \left[\pi /\mathrm{2},\pi \right)\right\},\\ {\mathrm{\Psi }}_{\mathrm{22}}=\left\{{\theta }_{v_{\mathrm{2}}}\mid {\mathrm{\Gamma }}_{\mathrm{1}}<t,{\theta }_{v_{\mathrm{2}}}\in {\mathrm{\Theta }}_{\mathrm{22}},\theta \in \left[\pi /\mathrm{2},\pi \right)\right\},\end{array}$$

(12)

where

$$\begin{array}{cc}& {\mathrm{\Gamma }}_{\mathrm{1}}=\frac{\mathrm{2}{r}_{\mathrm{0}}\cos \left(\theta +\arcsin \left(\sin {\theta }_{v_{\mathrm{2}}}/\mathrm{\Gamma }\right)\right)}{\left(v_{\mathrm{2}}\mathrm{\Gamma }\right)},\\ {\mathrm{\Gamma }}_{\mathrm{2}}=\frac{\mathrm{2}{r}_{\mathrm{0}}\cos \left(\pi -\theta +\arcsin \left(\sin {\theta }_{v_{\mathrm{2}}}/\mathrm{\Gamma }\right)\right)}{\left(v_{\mathrm{2}}\mathrm{\Gamma }\right)},\\ \mathrm{\Gamma }=\sqrt{\mathrm{1}-\mathrm{2}k\cos {\theta }_{v_{\mathrm{2}}}+k^{\mathrm{2}}}.\end{array}$$

(13)

Then there will be (14) and (15) according to the condition with $v_1>v_2$ . The distributed function of the link duration with $v_1<v_2$ can be obtained by the integral of $\mathrm{\Delta }m$ as shown in (16):

$$\begin{array}{ll}& l=\{\begin{array}{ll}\mathrm{2}{r}_{\mathrm{0}}\cos \left(\pi -\theta +\arcsin \left(\frac{\sin {\theta }_{v_{\mathrm{2}}}}{\mathrm{\Gamma }}\right)\right),\hfill & {\theta }_{v_{\mathrm{2}}}\in {\mathrm{\Theta }}_{\mathrm{12}}\cup {\mathrm{\Theta }}_{\mathrm{21}}\hfill \\ \mathrm{2}{r}_{\mathrm{0}}\cos \left(\theta +\arcsin \left(\frac{\sin {\theta }_{v_{\mathrm{2}}}}{\mathrm{\Gamma }}\right)\right),\hfill & {\theta }_{v_{\mathrm{2}}}\in {\mathrm{\Theta }}_{\mathrm{11}}\cup {\mathrm{\Theta }}_{\mathrm{22}},\hfill \end{array}\end{array}$$

(14)

$$\begin{array}{ll}& \underset{\begin{array}{l}\mathrm{\Delta }\theta \to \mathrm{0}\\ \mathrm{\Delta }{\theta }_{v_{\mathrm{2}}}\to \mathrm{0}\end{array}}{\mathrm{\Delta }m}=\{\begin{array}{ll}\frac{\mathrm{1}}{\mathrm{2}\pi Q}{r}_{\mathrm{0}}{v}_{\mathrm{2}}{T}_{\text{mov}}\mathrm{\Delta }{\theta }_{v_{\mathrm{2}}}\mathrm{\Delta }\theta \mathrm{\Gamma }\hfill & \hfill \\ \hspace{1em}\times \sin \left(\phantom{\left(\frac{\sin {\theta }_{v_{\mathrm{2}}}}{\mathrm{\Gamma }}\right)}\frac{\pi }{\mathrm{2}}-\theta -\arcsin \left(\frac{\sin {\theta }_{v_{\mathrm{2}}}}{\mathrm{\Gamma }}\right)\right),\hfill & \hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\theta \in \left[\mathrm{0},\pi \right),\hspace{0.17em}\hspace{0.17em}{\theta }_{v_{\mathrm{2}}}\in {\mathrm{\Theta }}_{\mathrm{11}}\cup {\mathrm{\Theta }}_{\mathrm{22}}\hfill & \hfill \\ \frac{\mathrm{1}}{\mathrm{2}\pi Q}{r}_{\mathrm{0}}{v}_{\mathrm{2}}{T}_{\text{mov}}\mathrm{\Delta }{\theta }_{v_{\mathrm{2}}}\mathrm{\Delta }\theta \mathrm{\Gamma }\hfill & \hfill \\ \hspace{1em}\times \sin \left(\frac{\mathrm{3}\pi }{\mathrm{2}}-\theta +\arcsin \left(\frac{\sin {\theta }_{v_2}}{\mathrm{\Gamma }}\right)\right),\hfill & \hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\theta \in \left[\mathrm{0},\pi \right),\hspace{0.17em}\hspace{0.17em}{\theta }_{v_{\mathrm{2}}}\in {\mathrm{\Theta }}_{\mathrm{12}}\cup {\mathrm{\Theta }}_{\mathrm{21}},\hfill & \hfill \end{array}\end{array}$$

(15)

$$\begin{array}{l}{F}_t\left({\lambda }_{\mathrm{12}}\mid v_{\mathrm{1}}<v_{\mathrm{2}}\right)\\ =({{\displaystyle \int }}_0^{\pi /\mathrm{2}}{{\displaystyle \int }}_{{\theta }_{v_2}\in {\mathrm{\Psi }}_{\mathrm{11}}}^{}\mathrm{\Gamma }{\mathrm{\Gamma }}_{\mathrm{3}}\text{d}{\theta }_{v_2}\hspace{0.17em}\text{d}\theta +{{\displaystyle \int }}_0^{\pi /\mathrm{2}}{{\displaystyle \int }}_{{\theta }_{v_2}\in {\mathrm{\Psi }}_{\mathrm{12}}}^{}\mathrm{\Gamma }{\mathrm{\Gamma }}_{\mathrm{4}}\text{d}{\theta }_{v_2}\hspace{0.17em}\text{d}\theta \\ \hspace{1em}\hspace{1em}+{{\displaystyle \int }}_{\pi /\mathrm{2}}^{\pi }{{\displaystyle \int }}_{{\theta }_{v_2}\in {\mathrm{\Psi }}_{\mathrm{21}}}^{}\mathrm{\Gamma }{\mathrm{\Gamma }}_{\mathrm{4}}\text{d}{\theta }_{v_{\mathrm{2}}}\hspace{0.17em}\text{d}\theta +{{\displaystyle \int }}_{\pi /\mathrm{2}}^{\pi }{{\displaystyle \int }}_{{\theta }_{v_2}\in {\mathrm{\Psi }}_{\mathrm{22}}}^{}\mathrm{\Gamma }{\mathrm{\Gamma }}_{\mathrm{3}}\text{d}{\theta }_{v_2}\hspace{0.17em}\text{d}\theta )\\ \hspace{1em}\times ({{\displaystyle \int }}_0^{\pi /\mathrm{2}}{{\displaystyle \int }}_{{\theta }_{v_2}\in {\mathrm{\Theta }}_{\mathrm{11}}}^{}\mathrm{\Gamma }{\mathrm{\Gamma }}_{\mathrm{3}}\text{d}{\theta }_{v_2}\text{d}\theta +{{\displaystyle \int }}_{\mathrm{0}}^{\pi /\mathrm{2}}{{\displaystyle \int }}_{{\theta }_{v_2}\in {\mathrm{\Theta }}_{\mathrm{12}}}^{}\mathrm{\Gamma }{\mathrm{\Gamma }}_{\mathrm{4}}\text{d}{\theta }_{v_2}\text{d}\theta \\ \hspace{1em}\hspace{1em}\hspace{0.5em}+{{\displaystyle \int }}_{\pi /\mathrm{2}}^{\pi }{{\displaystyle \int }}_{{\theta }_{v_2}\in {\mathrm{\Theta }}_{\mathrm{21}}}^{}\mathrm{\Gamma }{\mathrm{\Gamma }}_{\mathrm{4}}\text{d}{\theta }_{v_2}\text{d}\theta {+{{\displaystyle \int }}_{\pi /\mathrm{2}}^{\pi }{{\displaystyle \int }}_{{\theta }_{v_2}\in {\mathrm{\Theta }}_{\mathrm{22}}}^{}\mathrm{\Gamma }{\mathrm{\Gamma }}_{\mathrm{3}}\text{d}{\theta }_{v_2}\text{d}\theta )}^{-1}.\end{array}$$

(16)

Though the existing researches have obtained the distribution of the link duration for many nodes velocities, the functions are quite complicated. In order to simplify the latter calculation, the distribution of the link duration will be obtained by simulation and the distributed function could be set up by means of fitting. The result shows that the average deviation and the variance of Gompertz function are small with three parameters as in the following equation:

$$\begin{array}{l}{F}_d\left(t\right)=a\exp \left(-\exp \right)\frac{t_0-t}{d}\\ =\mathrm{0.99}\exp \left(-\exp \right)\frac{146-t}{120}.\end{array}$$

(17)

Figure 4

Calculation for connecting times for $n_1$ and $n_2$ .

4.2. Number of Topology Links

The topology duration has a close relationship with the number of links in wireless ad hoc network. The more links exist, the shorter the average topology duration will be. Assume that the set of source nodes is S with M elements and the set of destination nodes is D with N elements. The path from node i to node j is $P[i,j]$ . The shared path of $P[k,i]$ and $P[k,j]$ will be denoted as $P[k;i,j]$ and $P[i,j;k]$ for $P[i,k]$ and $P[j,k]$ . The number of topology links being measured can be represented as follows:

$$\begin{array}{l}h\left(G\right)={\displaystyle \sum }_{i\in \mathbf{S},\hspace{0.17em}j\in \mathbf{D}}h\left(P\left[i,j\right]\right)-{\displaystyle \sum }_{i\in \mathbf{S},\hspace{0.17em}j,k\in \mathbf{D}}h\left(P\left[i;j,k\right]\right)\\ \hspace{1em}-{\displaystyle \sum }_{i,j\in \mathbf{S},\hspace{0.17em}k\in \mathbf{D}}h\left(P\left[i,j;k\right]\right).\end{array}$$

(18)

When the source nodes and destination nodes are selected randomly, simulating results show that few shared paths exist for two routes in wireless mobile multihop network. Then (18) can be simplified as

$$\begin{array}{cc}& h\left(G\right)={\displaystyle \sum }_{i\in \mathbf{S},\hspace{0.17em}j\in \mathbf{D}}h\left(P\left[i,j\right]\right).\end{array}$$

(19)

The distributed function of topology links will be

$$\begin{array}{cc}& F_G\left(h,\rho ,N\right)={\displaystyle \sum }_{{{\displaystyle \sum }}_{i\in \mathbf{S},\hspace{0.17em}j\in \mathbf{D}}h\left(P\left[i,j\right]<h\right)}{\displaystyle \prod }\phi \left(h\left(P\left[i,j\right]\right),\rho ,N\right),\end{array}$$

(20)

where $\phi (h(P[i,j]),\rho ,N)$ is the probability distribution of the path length, which can be obtained by simulation as in Figure 5 with $L=2500$  m.

Figure 5

Probability distributed functions of the path length with $L=2500$  m.

4.3. Topology Duration

Simulations based on NS2.34 have been carried out to analyze the relationship between the topology duration and the wireless mobile multihop communication network parameters in this paper.

In walking speed scenes, the set of source nodes and destination nodes will be selected randomly with (1) $M=1$ and $N=4$ ; (2) $M=1$ and $N=8$ ; (3) $M=3$ and $N=4$ . Then the number of paths included in these topologies will be 4, 8, and 12, respectively. Simulation results of topology duration distribution can be seen in Figure 6, which shows that the more paths there are in wireless multihop network topology, the smaller the topology duration will be.

Figure 6

Continuous distributed function of topology duration.

Since the length of path depends on the number of nodes and the probability of connections, they have a direct impact on the network topology duration. Simulations will make the measurement time, the source node, and destination node be selected randomly in each walking speed scene, and the results can be seen in Figures 7 and 8.

Figure 7

Impacts of number of nodes on topology duration with $L=2500$  m.

Figure 8

Impacts of nodes connecting rate on topology duration with $N=40$ .

The topology duration equals the smallest remaining time of all links duration after the topology is being completely set up. This is because the links setting up time may be different. When the last one ξ is being established, other links may hold for some time. Assume that the rest ratio of other links ${\lambda }_i$ is $c_i$ , $c_i\in [\mathrm{0,1}]$ as shown in Figure 9.

Figure 9

Relationship between the topology duration and the link duration.

Therefore, the distribution of topology duration can be represented as follows:

$$\begin{array}{cc}& P\left\{T<t\right\}=P\left\{\underset{i\in \left(E-\xi \right)}{\min }\left\{c_i{\lambda }_i,\xi \right\}<t\right\}.\end{array}$$

(21)

The movement of the shared node in adjacent links may have an impact on the link duration of the adjacent links, so the durations of all links in wireless mobile multihop communication network are correlated with each other. Existing researches, however, show that this kind of correlation is weak. Assume that the link duration and $c_i$ are mutually independent. Then there is the following equation:

$$\begin{array}{l}P\left\{T<t\mid E\right\}=1-{\displaystyle \prod }_{i\in \left\{E-\xi \right\}}P\left\{c_i{\lambda }_i>t\right\}P\left\{\xi >t\right\}\\ =1-{\left(P\left\{c\lambda >t\right\}\right)}^{\left|E\right|-1}P\left\{\lambda >t\right\}\\ =1-{\left({{\displaystyle \int }}_0^1{{\displaystyle \int }}_{t/x}^{\infty }{f}_c\left(x\right)f_{\lambda }\left(y\right)\text{d}y\hspace{0.17em}\text{d}x\right)}^{\left|E\right|-1}\\ \hspace{1em}\times \left({{\displaystyle \int }}_t^{\infty }{f}_{\lambda }\left(y\right)\text{d}y\right).\end{array}$$

(22)

Since the starting time of each link is independent, $c_i$ can be assumed to obey a uniform distribution on $[\mathrm{0,1}]$ . Then (22) will be simplified as

$$\begin{array}{l}{F}_n\left(t,\left|E\right|\right)=1-{\left({{\displaystyle \int }}_0^1{{\displaystyle \int }}_{t/x}^{\infty }{f}_{\lambda }\left(y\right)\text{d}y\hspace{0.17em}\text{d}x\right)}^{\left|E\right|-1}\left({{\displaystyle \int }}_t^{\infty }{f}_{\lambda }\left(y\right)\text{d}y\right)\\ =1-{\left({{\displaystyle \int }}_0^1\left(1-F_{\lambda }\left(\frac{t}{x}\right)\right)\text{d}x\right)}^{\left|E\right|-1}\left(1-F_{\lambda }\left(t\right)\right)\\ =1-{\left(1-{{\displaystyle \int }}_0^1{F}_{\lambda }\left(\frac{t}{x}\right)\text{d}x\right)}^{\left|E\right|-1}\left(1-F_{\lambda }\left(t\right)\right),\\ \gamma \left(t,\left|E\right|\right)=F_t\left(t,\left|E\right|\right)\\ =\frac{1}{C}{{\displaystyle \int }}_0^{t}y({\left(1-{{\displaystyle \int }}_0^1{F}_{\lambda }\left(\frac{y}{x}\right)\text{d}x\right)}^{\left|E\right|-1}{f}_{\lambda }\left(y\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}+{\left(1-{{\displaystyle \int }}_0^1{F}_{\lambda }\left(\frac{y}{x}\right)\text{d}x\right)}^{\left|E\right|-2}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}\times \left(1-F_{\lambda }\left(y\right)\right){{\displaystyle \int }}_0^1\frac{1}{x}{f}_{\lambda }\left(\frac{y}{x}\right)\text{d}x\phantom{{\left(1-{{\displaystyle \int }}_0^1{F}_{\lambda }\left(\frac{y}{x}\right)\text{d}x\right)}^{\left|E\right|-1}})\text{d}y.\end{array}$$

(23)

The path duration function will be obtained by substituting the link duration distributed function to (23). Comparison result of the simulation and the calculation for time distributed function can be seen in Figure 10, which shows a big difference in the conditions with a large duration.

Figure 10

Continuous distributed function of the topology duration.

That is because

• (1)

there are errors existing in topology duration statistics caused by limited simulating duration;

(2)

there is an approximate calculation in the link duration fitting function.

In process of calculating the measurement time constraint, the value on small duration of the topology duration function has been mainly adopted so as hardly to produce any severe impacts.

5. Measurement Time Constraints

The simulations are performed in walking speed scenes with TTL method to sense the topology changing in order to obtain the correct rate α in the measurement duration constraint ${\tau }_M$ as shown in Table 1.

Table 1

Relationship between ${\tau }_M$ and α in walking scenes.

${\tau }_M$	10 s	20 s	40 s	80 s
$M=1$    $N=4$	0.99	0.97	0.92	0.80
$M=1$    $N=8$	0.98	0.92	0.84	0.67
$M=3$    $N=4$	0.97	0.80	0.77	0.51

Since the topology sensing rate with $L=1250$  m is smaller than that with $L=2500$  m and the path duration is bigger, the value of α will increase with ${\tau }_M$ when $L=1250$  m, while the situation is just the reverse with $L=2500$  m. From the results in Table 1, it can be seen that in measurement for wireless mobile multihop communication network with suitable number of nodes and the value of duration, it is available to infer the topology and analyze the link performance based on network tomography.

The calculation formula for the average α should be derived with the source nodes and the destination nodes being randomly selected. Assume that the paths from the source nodes to the destinations are independent based on the simulation results above, and, based on (1), there will be

$$\begin{array}{cc}& \alpha ={\left(\mathrm{1}-{\displaystyle \int }\gamma \left({\tau }_M,h\right)\left(1-\eta \left(h,\rho ,N\right)\right)\phi \left(h,\rho ,N\right)\text{d}h\right)}^{MN}.\end{array}$$

(24)

Then for each measurement, the value of α will be obtained based on (2) as shown in (25), and all parameters related have the same meaning as in Section 2:

$$\begin{array}{cc}& \alpha =\mathrm{1}-\gamma \left({\tau }_M,h\left(G\right)\right)\left(\mathrm{1}-{\displaystyle \prod }_{i\in \mathbf{S},\hspace{0.17em}j\in \mathbf{D}}\eta \left(h\left(P\left[i,j\right]\right),\rho ,N\right)\right).\end{array}$$

(25)

There are four ways to improve the value of α based on (24) and (25): firstly, to reduce the network size; secondly, to reduce the number of detecting packets so as to shorten the measurement duration; thirdly, to increase the detecting packets sending rate; finally, to adopt multisource measurement instead. The former three have deficiencies in themselves, so the optimization based on the network reality will be needed. The disadvantage of reducing the network size is that it will reduce the number of links inferred by measurement, which will be better to restrict the number of nodes from several to ten. To reduce the number of detecting packets to some certain value will bring a fast increasing error range for the inferring result. To increase the packets, sending rate will change the link performance, and the sending rate should lie in 5%~10% of the network data stream rate. The last method with multisource measurement will reduce the measurement duration because many source nodes carrying out the measurement at the same time will improve the efficiency.

6. Conclusions

Wireless mobile multihop communication network has been regarded as an important step to realize the ubiquitous communication world. The dynamic topology makes the network being organized flexibly adapt to more general environment but will have an impact on packets transmitting performance. We have focused on the topology flapping in wireless mobile multihop communication network to obtain the description and quantification for dynamic properties based on network tomography. Combining the theoretical derivation and simulation verification, the dynamic property has been investigated systematically, and a novel method to sense the topology flapping based on TTL has been proposed in this paper. Simulation results show a better sensing rate. The network tomography has been introduced in wireless mobile multihop communication network, through which the calculating model for the probability distributed function of the network topology stability has been established and simulated in wireless mobile multihop communication network in walking speed scenes. The experimental results with both simulation and calculation demonstrated the effectiveness of the proposed model. Future work will concentrate on the algorithm universality and environment adaption.