Hop count limitation analysis in wireless multi-hop networks

Abstract

Recent studies about wireless multi-hop networks mainly focus on two aspects, network performance and network strategy. A mass of models and algorithms about network connectivity, path reliability, and node mobility have been proposed to improve network performance. However, hop count, an important factor of wireless multi-hop networks, is rarely researched. In this article, we propose some feasible research methods to figure out the connections between hop count and network connectivity, and path reliability and node mobility, respectively. By modeling the network connectivity, path reliability, and node mobility, we get the maximum hop count of arbitrary wireless multi-hop network. This study shows that the hop count limitation has great effect on network stability. With an increase in hop count, the network stability gets worse. Thinking about this situation, we propose some feasible advices to avoid the hop count limitation problem, which may provide some useful theoretical foundation for further study on wireless multi-hop networks.

Introduction

Wireless multi-hop networks mainly refer to wireless sensor networks (WSNs), wireless mesh networks (WMNs), mobile ad hoc networks (MANETs), and so on. Due to their flexibility, there is a bright future in terms of their wide applications in fields of Internet of things (IOT), vehicle ad hoc networks (VANETs), aeronautical ad hoc networks (AANETs) as well as inter-stellar communications (ISC).

In wireless multi-hop networks, network stability is one of the most important network performances and also the prerequisite of their wide spread. Network stability mainly reflects in three aspects: network connectivity, path reliability, and node mobility.

Network connectivity describes the connections between any two nodes in the network. Generally, network connectivity is measured by the probability that any two nodes connect with each other within the network. The greater the probability value, the better the network connectivity. Thus, the network is more stable. Plentiful of research works focused on the network connectivity.^1–6 Authors in the literature ¹ studied the connectivity of wireless multi-hop network in a shadow fading environment and determined the greatest lower bound of network connectivity under the condition of a certain node density. Then, the minimum node density for a certain probability of network connectivity was deduced. Connectivity of AANETs ² and MANETs^3,4 was also studied and some important conclusions were obtained. In VANETs, the impact of multi-cooperation strategy ⁵ on network connectivity was studied. To further analyze the network connectivity, a probabilistic connectivity matrix was introduced as a tool to measure the quality of network connectivity. ⁶ The largest magnitude eigenvalue of the probabilistic connectivity matrix was proved to be a good measurement of network connectivity. However, the major focus of the literature works mentioned above is on the connectivity between any two nodes within the network. The measurement of network connectivity does not care about the network scale which lacks practicability in network planning. As a result, we define the measurement of network connectivity as the probability that a given node has an N-hop route $P_{\mathrm{NC}}$ . Taking hop count into consideration, the network scale is analyzed. Similarly, the greater the value of $P_{\mathrm{NC}}$ , the better the network connectivity, and hence, the network is more stable.

At present, most research works about path reliability focus on the expectancy time of the links.^7,8 Link expectancy time was defined as the stability factor and used as one of the routing metrics. ⁷ Actually, link expectancy time is the result of node mobility. In terms of path reliability, we just lay emphasis on the success probability of routing discovery in a given N-hop path. We define the path reliability as the probability of routing success $P_{\mathrm{NR}}$ between any two nodes connected by N wireless links. Compared with the definition of network connectivity, path reliability focuses on the process of finding a path between any two nodes, while network connectivity cares about the existence of a path between any two nodes. Due to the instability of the wireless links, errors may occur after several times of packet forwarding. Obviously, before data transmission in multi-hop networks, the forwarding of routing overhead such as routing request (RREQ) packet may fail because of the instability of wireless links. As a result, the greater the value of $P_{\mathrm{NR}}$ , the more reliable the path, and hence, the network is more stable.

Node mobility describes the dynamic change of network topology caused by the motion of nodes. Generally, node mobility is measured by the link expectancy time $T_{\mathrm{LET}}$ . There are plenty of the literature works^8–13 concerning on link expectancy time. Link expectancy time was applied in topology control strategy ⁹ and routing scheme^8,10 to prolong the lifetime of routes between source and destination nodes. Moreover, the distribution function of the link expectancy time in MANETs was studied and the closed solution was given.^11–13 In this article, we also apply the link expectancy time to describe the node mobility. To further understand the impact of node mobility, we mainly analyze the expectancy time of a given path, which consists of several consecutive links. Because of the change of the topology, an N-hop path definitely has a duration time called path expectancy time $T_{\mathrm{PET}}$ . When $T_{\mathrm{PET}}$ runs out, the source node will restart the routing discovery, which will obviously cause additional routing overhead. However, due to the instability of the wireless links, nodes may fail in routing discovery. Two or more routing discoveries are necessary before a route from source node to destination node is established. Thus, the routing discovery time $T_{\mathrm{RDT}}$ increases. When $T_{\mathrm{RDT}}$ is greater than or close to $T_{\mathrm{PET}}$ , nodes may be busy at finding a route rather than communicating with each other. As a result, the stronger the node mobility, the more unstable the network.

In wireless multi-hop networks, hop count is an important factor influencing network performance. The impacts of hop count in wireless multi-hop networks were studied.^14–16 Rahmatollahi and Abreu ¹⁴ deduced the close-form of hop count distribution in multi-hop wireless network with arbitrary node distribution and routing scheme. However, they ignored the impact of routing discovery procedure on successfully establishing a usable route. The wireless channel was also assumed ideal. ¹⁴ Similarly, Kuo and Liao ¹⁵ and Yildiz et al. ¹⁶ also studied the existence and the impact of a multi-hop path without considering the routing discovery. Actually, literature works mentioned above analyzed the impact of network connectivity on hop count instead of the impact of hop count on network connectivity. Obviously, as the hop count increases, the network becomes less stable, which is shown in several aspects as follows:

1. In terms of network connectivity, as the hop count increases, the probability of existence of an N-hop route for a node in the network decreases, and the network becomes less stable.

2. In regard to path reliability, with an increase in the hop count, the number of links increases as well as the error probability. Namely, the success probability of routing discovery decreases, and the network becomes less stable.

3. As for node mobility, when the hop count increases, the number of links increases and the path expectancy time decreases. However, an increase in the number of links leads to the instable end-to-end connection. The probability of failure in routing discovery increases. Thus, the routing discovery time increases, and the network becomes less stable.

It can be seen that hop count is one of the most important network features and has significant impact on network stability. To guarantee the network connectivity, link reliability, and node mobility, respectively, the hop count must be lower than the maximum hop count $N_{\max }$ . The main contributions of this article are as follows:

1. We propose a framework for analyzing stability of wireless multi-hop networks and define the stability factors as network connectivity, path reliability, and node mobility.

2. We figure out the relation between hop count and network stability and finally get the maximum hop count which has significant importance on network planning.

3. We provide some optimum proposals and future research directions to deal with hop count limitation problem.

The remainder of this article is organized as follows. Section “Stability components” presents analysis models for network connectivity, path reliability, and node mobility, respectively. Simulation and theoretical results are shown in section “Simulation and theoretical results.” In section “Analysis,” we analyze the maximum hop count deduced from network connectivity, path reliability, and node mobility, respectively. In section “Possible solutions,” we propose some possible solutions to deal with hop count limitations in wireless multi-hop networks. Finally, section “Conclusion” concludes the article.

Stability components

In this section, we mainly analyze the relation between network stability and hop count limitation. As mentioned above, network stability factors include network connectivity, path reliability, and node mobility. By modeling network connectivity, path reliability, and node mobility, respectively, we finally deduced the relations between hop count and network stability factors in wireless multi-hop networks.

Network connectivity

Network connectivity is the precondition of communications between any pair of nodes in the network. It decides whether multi-hop routes exist or not between any pair of nodes. As one of the basic performances of wireless multi-hop networks, network connectivity is determined by more basic network attributes. Such attributes include node distribution, node density, and effective communication radius. If channel fading and interference between nodes are taken into consideration, channel propagation model and medium access protocol also have great impact on network connectivity.

Traditionally, research works on network connectivity mainly focus on the probabilities of interconnection between any pair of nodes under the condition of certain network attributes. Traditional network connectivity is determined by node distribution, node density, channel propagation model, and effective communication radius.

Recent research works about network connectivity seldom analyze the relation between hop count and network connectivity. As a result, we are not able to get the network radius and the impact of network connectivity on a given node. Unlike the traditional definition of network connectivity, we use the probability of existence of N-hop route $P_{\mathrm{NC}}$ for a random node as the measurement of network connectivity. Obviously, with an increase in hop count, the probability of existence of N-hop route decreases, which means that two nodes with N-hop distance have weak connection. For a given threshold, there is a maximum hop count $N_{\max \_c}$ . In order to get $N_{\max \_c}$ , we should find out $P_{\mathrm{NC}}$ first.

For simplicity, we assume that the effective communication radius is $R_{\mathrm{eff}}$ and ignore the channel fading. We also assume that the distribution of the nodes is given by a homogeneous Poisson point process of density $\rho$ nodes per unit area. This process is defined by the following two properties: ¹⁷

1. For a given finite area D of size $|\mathbf{D}|=D$ , the number of nodes in area D follows a Poisson distribution, that is

   $$P(n\mathrm{nodes}\mathrm{in}\mathrm{area}\mathbf{D})=P(N=n)=\frac{{\lambda }^n}{n!}{e}^{-\lambda }$$

   (1)

   where $\lambda =\rho D$ .

2. For disjoint areas ${\mathbf{D}}_i,i\in \mathrm{N}$ , the numbers of nodes $N_i$ in area ${\mathbf{D}}_i$ are independent random variables, that is

   $$\begin{array}{l}P(N_1=n_1\cap N_2=n_2\cap \cdots \cap N_k=n_k)\\ ={\displaystyle \prod _{i=1}^{k}P}(N_i=n_i)\end{array}$$

   (2)

We assume that the nodes distribute in area D of size $|\mathbf{D}|=D$ . For a given node density $\rho$ , the number of nodes in area D depends on the size of D.

Let $N_D$ denote the number of nodes in area D. When $N_D=k,k>2$ , the k nodes satisfy uniform distribution within area D. As shown in Figure 1, if distance between two nodes is less than $R_{\mathrm{eff}}$ , these two nodes are connective. The probability of direct connection between two nodes, when $N_D=k,k>2$ , is

$$P_{\mathrm{ij}}^{(k)}=P(d_{\mathrm{ij}}<R_{\mathrm{eff}}|N_D=k)$$

(3)

where $d_{\mathrm{ij}}$ is the distance between node i and node j, and specially, $P_{\mathrm{ii}}^{(k)}=1$ .

Figure 1.

Distribution of nodes within area D with $\rho =4\times {10}^{-5}\mathrm{nodes}/{\mathrm{m}}^2$ .

If $\pi R_{\mathrm{eff}}^2<<D$ , we have

$$P_{\mathrm{ij}}^{(k)}=\frac{\pi R_{\mathrm{eff}}^2}{D}$$

(4)

We define indicative function $a_{\mathrm{ij}}^{(k)}$ as

$$a_{\mathrm{ij}}^{(k)}=\{\begin{array}{c}1,P(d_{\mathrm{ij}}<R_{\mathrm{eff}}|N_D=k)\hfill \\ \multicolumn{1}{c}{0,P(d_{\mathrm{ij}}\ge R_{\mathrm{eff}}|N_D=k)}\end{array}$$

(5)

which indicates the connection of node i and node j. Therefore, it is easy to get the network adjacent matrix A, and

$$A=\left(\begin{array}{ccc}{a}_{11}^{(k)}\hfill & \dots \hfill & a_{1k}^{(k)}\hfill \\ \multicolumn{1}{c}{⋮}& \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{a_{k1}^{(k)}}& \dots \hfill & a_{\mathrm{kk}}^{(k)}\hfill \end{array}\right)$$

(6)

According to the definition, we know that matrix A is a Boolean and symmetric matrix. For a given A, $A^n$ denotes the n-hop reachable matrix. The operations of matrix A are Boolean operations, which means the addition operation corresponds to OR operation and multiplication operation corresponds to AND operation. Thus, $A^n$ is also a Boolean matrix.

Let $C_n$ denote the n-hop-only reachable matrix. By applying the shortest path–based routing algorithm, we have

$$C_n=\sum _{i=0}^n{A}^i$$

(7)

By changing the non-1 elements to 0, we get the n-hop-only reachable matrix $C_n$ , which is also a Boolean matrix. For a given network adjacent matrix A, we have an n-hop-only reachable matrix $C_n$ uniquely. If elements in the $i\mathrm{th}$ row are all 0, the maximum hop count for the $i\mathrm{th}$ node is less than n.

When $N_D=k$ , the probability of existence of n-hop route for a random node $P(n|N_D=k)$ is easy to deduce from $C_n$ by statistical parametric model. Obviously, when $n>k$ , we have $P(n|N_D=k)=0$ . Let $P_{\mathrm{nC}}$ denote the probability of existence of n-hop route for a random node; then we have

$$\begin{array}{c}\multicolumn{1}{c}{P_{\mathrm{nC}}=\sum _{k=0}^{\infty }P(N_D=k)P(n|N_D=k)}\\ \multicolumn{1}{c}{=\sum _{k=1}^{\infty }\frac{{\lambda }^k}{k!}{e}^{-\lambda }P(n|N_D=k)}\end{array}$$

(8)

where $\lambda =\rho D$ .

$P_{\mathrm{nC}}$ indicates the connectivity of the network. When the threshold of $P_{\mathrm{nC}}$ is set, we then get the maximum hop count $N_{\max \_c}$ .

Path reliability

The measurement of path reliability is defined as the probability of routing success of a given N-hop path in wireless multi-hop networks. For a given path, with an increase in hop count, the number of links between source and destination nodes increases. After multiple forwarding, the packet loss rate increases; thus, the probability of routing success decreases. Despite an appropriate N-hop path between source and destination nodes, the source node may fail to find it because of the low success probability of routing discovery. As a result, for a given multi-hop path, there exists a maximum hop count $N_{\max \_r}$ which satisfies the requirement of path reliability, the minimum probability of routing success. In this subsection, our research focuses on the relation between the probability of routing success $P_{\mathrm{NR}}$ and the hop count n in a given path.

Link model

Let $p(x)$ denote the point-to-point packet delivery ratio between two nodes of distance x. We ignore the interferences between nodes and adopt a log-normal shadow fading channel ¹ as the wireless channel model. We assume that the distance between two nodes is x, the sending signal strength is $P_t$ , and the threshold of received signal strength is $P_{r,\mathrm{th}}$ . From equation (13) in the work by Bettstetter and Hartmann, ¹ we have

$$p(x)=\frac{1}{2}-\frac{1}{2}\mathrm{erf}\left(\frac{10\alpha }{\sqrt{2}\sigma }\mathrm{lo}{\mathrm{g}}_{10}\frac{x}{r_0}\mathrm{dB}\right)$$

(9)

where $\alpha$ is the path loss exponent, $\sigma$ is the standard deviation, $r_0={10}^{{\beta }_{\mathrm{th}}/\alpha 10\mathrm{dB}}$ , and the signal attenuation threshold ${\beta }_{\mathrm{th}}=10\underset{10}{\log }{P}_t/P_{r,\mathrm{th}}\mathrm{dB}$ . The curve of $p(x)$ is shown in Figure 2.

Figure 2.

Delivery ratio of two nodes with distance x.

We consider an N-hop path as shown in Figure 3. Let $d_{\mathrm{ij}}$ denote the distance between node i and node j. In order to ensure the existence of the path, we assume that the distance between neighbor nodes $d_{\mathrm{ii}+1}$ is less than $R_{\mathrm{eff}}$ . Obviously, the point-to-point packet delivery ratio between node i and node j is $p(d_{\mathrm{ij}})$ .

Figure 3.

An overview of N-hop path.

Routing mechanism

At the beginning of routing procedure, the source node broadcasts a RREQ packet. The relay nodes forward the RREQ as long as they receive it. The destination node immediately replies the source node with a routing response (RREP) packet once it has successfully received the RREQ. The RREP follows the path, which consists of nodes that used to forward the RREQ, back to the source node hop by hop. After receiving the RREP in the source node, the routing discovery procedure finishes. In this part, we assume that a shortest path–based routing mechanism is applied. Therefore, the relay node which is the nearest to the destination node has the highest priority to forward the RREQ. The process of routing discovery is shown in Figure 4.

Figure 4.

The process of routing discovery.

Because of the packet loss rate of each link, the RREQ and RREP may lose after several times of forwarding. Especially, for the routing algorithms applying broadcast mechanism, the reliability of RREQ transmission is not guaranteed without retransmission mechanisms. If the routing discovery procedure fails in the source node, the data transmission between source and destination nodes is not available.

The probability of routing success

In order to get the mathematical result of $P_{\mathrm{NR}}$ , we apply a Markov chain–based model to analyze the routing discovery procedure. Three assumptions are considered as follows:

1. The packet transmission processes of nodes are independent. The RREQ broadcast time of node i and node j is separated.

2. The receptions of RREQ of relay nodes are independent. Because of space separation of node i and node j, the reception of RREQ of node i has nothing to do with node j.

3. When two or more relay nodes have successfully received the same RREQ, the relay node that is closer to the destination has higher priority to forward the RREQ.

Let n denote the process of the nth RREQ. We define random variables $\{{\xi }_n\}$ and state space $E=\{{\xi }_n=i_n|i_n=1,2,\dots ,N+2\}$ , where state ${\xi }_n=i_n$ denotes that relay node $i_n$ has successfully received and forwarded the nth RREQ. In other words, state ${\xi }_n=i_n$ denotes the farthest node the nth RREQ can reach. Especially, state ${\xi }_n=N+2$ denotes that no relay nodes have received the nth RREQ and the routing discovery has failed. Actually, the source node of the (n+1)th RREQ is node $i_n$ . In consideration of the assumptions above, we know that the (n+1)th RREQ has nothing to do with the kth RREQ where $k<n$ . So, we have

$$\begin{array}{l}P\left\{{\xi }_{n+1}=i_{n+1}|{\xi }_0=i_0,\dots ,{\xi }_n=i_n\right\}\\ =P\left\{{\xi }_{n+1}=i_{n+1}|{\xi }_n=i_n\right\}\end{array}$$

(10)

Thus, the routing discovery procedure can be modeled as a Markov chain $\{{\xi }_n\}$ . The state transition diagram of Markov chain $\{{\xi }_n\}$ is as shown in Figure 5.

Figure 5.

The state transition diagram of Markov chain.

The transmission route of RREP is the same as RREQ. Here, we consider the transmission of RREQ and RREP at the same time. From Figure 5, for example, ${\xi }_1=3$ denotes that node 3 has successfully received the first RREQ from node 1 and replied RREP to node 1. Especially, ${\xi }_0=1$ denotes the initial state of the network.

In the routing discovery procedure, the condition for a relay node to forward RREQ is that the relay node has successfully received the RREQ from the last relay node (or the source node) and other relay nodes (or the destination node) that are closer to the destination node have failed to received the RREQ. Hence, we have the one-step transition probability of Markov chain $\{{\xi }_n\}$

$$\begin{array}{c}\{\begin{array}{c}P(j|i)=p{\left(d_{\mathrm{ij}}\right)}^2\underset{k=j+1}{\overset{N+1}{\Pi }}\overline{p(d_{\mathrm{ik}})};i=(1,2,\dots ,N-1),j>i\hfill \\ \multicolumn{1}{c}{P(N+1|i)=p{(d_{\mathrm{iN}+1})}^2;i=(1,2,\dots ,N)}\\ \multicolumn{1}{c}{P(N+2|i)=1-\sum _{k=i+1}^{N+1}P(k|i);i=(1,2,\dots ,N)}\\ \multicolumn{1}{c}{P(N+1|N+1)=1;}\\ \multicolumn{1}{c}{P(N+2|N+2)=1;}\\ \multicolumn{1}{c}{P(j|i)=0;\mathrm{else}}\end{array}\hfill \end{array}$$

(11)

The first equation in equation (11) means that node j has received the RREQ from node i and node j has the highest priority to forward it. The second equation means that the destination node has received the RREQ and replied RREP to node i. The third equation means that all relay nodes have failed in processing the RREQ from node i or replying RREP to node i. The fourth and fifth equations denote that once the source node has succeeded or failed in routing discovery, the state will not change any more.

Let Q denote the transition probability matrix and $\overrightarrow{\pi }=[{\pi }_1,{\pi }_2,{\pi }_3,\dots ,{\pi }_{N+2}]$ denote stationary distribution. Then, we have

$$Q=\left(\begin{array}{ccc}{p}_{11}\hfill & \cdots \hfill & p_{1(N+2)}\hfill \\ \multicolumn{1}{c}{⋮}& \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{p_{(N+2)1}}& \cdots \hfill & p_{(N+2)(N+2)}\hfill \end{array}\right)$$

(12)

and

$$\overrightarrow{\pi }=\overrightarrow{\pi }Q$$

(13)

The probability of routing success $P_{\mathrm{NR}}$ is given by

$$P_{\mathrm{NR}}={\pi }_{N+1}$$

(14)

Node mobility

Node mobility is the feature of wireless multi-hop networks, such as MANETs, VANETs, and AANETs, whose nodes are moveable. Node mobility has great effect on wireless multi-hop networks by changing the network topology dynamically. For the communicating nodes, the change of network topology means the rebuilt or repair of the route used. Thus, node mobility inevitably brings the additional routing overhead and delay overhead. As a result, the frequency of the change of the network topology is another important measurement of network stability. In this article, we define node mobility as the frequency of the change of network topology.

Breakage of any links leads to the change of network topology. Therefore, link expectancy time $T_{\mathrm{LET}}$ is one of the best measurements of node mobility. To better understand the relation between node mobility and hop count, we mainly analyze the N-hop path expectancy time $T_{\mathrm{PET}}$ . The distributions of $T_{\mathrm{LET}}$ and $T_{\mathrm{PET}}$ depend on the node mobility model and node mobility parameters.

On the other aspect, because of the unreliability of wireless links, the end-to-end packet loss rate increases with the number of hop count. Therefore, the source node may have to restart the routing discovery procedure again and again which increases the routing discovery time $T_{\mathrm{RDT}}$ . If the routing discovery time for an N-hop route is close to or greater than the path expectancy time, the network becomes instable. As a result, there is a maximum hop count $N_{\max \_m}$ deduced from node mobility.

In order to get $N_{\max \_m}$ , we need to calculate the path expectancy time $T_{\mathrm{PET}}$ and routing discovery time $T_{\mathrm{RDT}}$ , respectively.

Path expectancy time

We consider a wireless multi-hop network and assume that the speed of nodes v uniformly distributes in $(v_{\min },v_{\max })$ . The nodes in the network approximately move in uniform linear motion.

Distribution of relative speed

Let ${\overrightarrow{v}}_1$ and ${\overrightarrow{v}}_2$ denote the velocity vectors of two random nodes in network. Their included angle $\theta$ and their modulus values $v_1$ and $v_2$ are mutually independent random variables. We assume that $\theta$ uniformly distributes in $(0,\pi )$ .

Let $v_r$ denote the modulus value of relative velocity vector of two random nodes, as shown in Figure 6; then, we have

$$\{\begin{array}{c}{v}_r=\sqrt{{v_1}^2+{v_2}^2-2v_1{v}_2\cos \theta }\hfill \\ \multicolumn{1}{c}{f_{\theta ,v_1,v_2}(\theta ,v_1,v_2)=f_{\theta }(\theta )f_{v_1}(v_1)f_{v_2}(v_2)=\frac{1}{\pi {(v_{\max }-v_{\min })}^2}}\end{array}$$

(15)

Figure 6.

Related motion between two nodes.

It is easy to find the probability density function (PDF) of relative velocity $v_r$

$$f_{v_r}(v_r)=\underset{v_{\min }}{\overset{v_{\max }}{\int }}\underset{v_{\min }}{\overset{v_{\max }}{\int }}\frac{2v{f}_{v_1}(v_1)f_{v_2}(v_2)}{\pi \sqrt{4v_1^2{v}_2^2-(v^2-v_1^2-v_2^2)}}d{v}_{1}d{v}_2$$

(16)

Distribution of link expectancy time

Link expectancy time $T_{\mathrm{LET}}$ of two nodes is the duration from the time when the two nodes first meet each other to the time when they leave each other. For simplicity, we use a purely geometric model to characterize the connective relation between two nodes, which means that two nodes are linked as long as they are within effective communication radius of each other. For a given path, after establishing, part of link expectancy time has been consumed. Therefore, in order to get the path expectancy time, we should find the remaining link expectancy time first. In the case of not confusing, we also mark the remaining link expectancy time as $T_{\mathrm{LET}}$ , and our research focuses on the remaining link expectancy time $T_{\mathrm{LET}}$ .

As shown in Figure 6, we assume that the original distance between two neighbor nodes d uniformly distributes in $(0,R_{\mathrm{eff}})$ , and the angle between original distance direction and relative velocity direction $\omega$ uniformly distributes in $(0,\pi )$ .

The remaining link expectancy time is given by

$$T_{\mathrm{LET}}=\frac{d\cos \omega +\sqrt{R_{\mathrm{eff}}^2-d^2\mathrm{si}{\mathrm{n}}^2\omega }}{v_r}$$

(17)

Since $v_r$ , d, and $\omega$ are independent, we have

$$f_{v_r,d,\omega }(v_r,d,\omega )=f_{v_r}(v_r)f_d(d)f_{\omega }(\omega )$$

(18)

From equations (17) and (18), it is easy to find

$$f_{T_{\mathrm{LET}}}(t)=\underset{0}{\overset{R_{\mathrm{eff}}}{\int }}\underset{v_{r\min }}{\overset{v_{r\max }}{\int }}\underset{v_{\min }}{\overset{v_{\max }}{\int }}\underset{v_{\min }}{\overset{v_{\max }}{\int }}\mathrm{Xd}{v}_{1}d{v}_{2}d{v}_r\mathrm{dd}$$

(19)

$$X=\frac{2v_r{f}_{v_1}(v_1)f_{v_2}(v_2)}{R_{\mathrm{eff}}{\pi }^2\sqrt{4v_1^2{v}_2^2-{({v_r}^2-v_1^2-v_2^2)}^2}}\left|J\right|$$

where $|J|=|\partial K/\partial t||-1/\sqrt{1-K^2}|$ and $K=(t^2{v}^2+d^2-R_{\mathrm{eff}}^2)/2\mathrm{tvd}$ .

Distribution of path expectancy time

For a given N-hop route, as shown in Figure 7, the path expectancy time is given by

$$T_{\mathrm{PET}}=\min (T_{\mathrm{LET}1},T_{\mathrm{LET}2},T_{\mathrm{LET}3},\dots ,T_{\mathrm{LETN}})$$

(20)

where $T_{\mathrm{LETi}}$ denotes the remaining link expectancy time of the $i\mathrm{th}$ link. Obviously, the distributions of remaining link expectancy time of all links are identical, and their PDF is given by equation (19). In the following paragraph, the independence of $T_{\mathrm{LETi}}(i=1,2,3,\dots ,N)$ is discussed briefly.

Figure 7.

Expectancy time of links in a given N-hop route.

For the non-adjacent links, like link 1 and link 3 in Figure 7, $T_{\mathrm{LET}1}$ and $T_{\mathrm{LET}3}$ are obviously independent. For the adjacent links, like link 1 and link 2, they share a common node. We make node 2 as the reference point. Therefore, the remaining link expectancy time of link 1 $T_{\mathrm{LET}1}$ is determined by the motion state of node 1, and the remaining link expectancy time of link 2 $T_{\mathrm{LET}2}$ is determined by the motion state of node 3. Hence, $T_{\mathrm{LET}1}$ and $T_{\mathrm{LET}2}$ are independent. Therefore, $T_{\mathrm{LETi}}(i=1,2,3,\dots ,N)$ are independent identically distributed random variables. From equation (20), we get the cumulative distribution function (CDF) of $T_{\mathrm{PET}}$

$$F_{T_{\mathrm{PET}}}(t)=1-{(1-F_{T_{\mathrm{LET}}}(t))}^N$$

(21)

where $F_{T_{\mathrm{LET}}}(t)={\int }_{-\infty }^t{f}_{T_{\mathrm{LET}}}(\tau )d\tau$ .

For a given N-hop route, the average path expectancy time $E[T_{\mathrm{PET}}]$ is given by

$$E\left[T_{\mathrm{PET}}\right]=\underset{-\infty }{\overset{+\infty }{\int }}\mathrm{td}{F}_{T_{\mathrm{PET}}}(t)$$

(22)

Routing discovery time

In wireless multi-hop networks, a multi-hop route must be established before communication. No matter what kind of routing protocol (active, passive, or hybrid routing protocol), there is a period of time, called routing discovery time $T_{\mathrm{RDT}}$ , before the route establishment. Because of the end-to-end packet loss rate, the source node may fail in routing discovery at a certain probability. If the routing discovery is failed, the source node has to wait for a period of time, which is called routing discovery period $T_{\mathrm{RDP}}$ , before restarting the routing discovery procedure. Hence, the routing discovery time $T_{\mathrm{RDT}}$ increases. When the routing discovery time is close to or greater than the path expectancy time, the network becomes instable.

For a given path, with an increase in hop count, the end-to-end packet delay increases inevitably. However, in consideration of that the path expectancy time $T_{\mathrm{PET}}$ is much greater than the end-to-end packet delay, we only consider the impact of the routing discovery time $T_{\mathrm{RDT}}$ on the network stability instead of end-to-end packet delay. In this subsection, we apply the channel model and routing algorithm which are applied in “Path reliability” section. The source node broadcasts a RREQ packet to start the routing discovery procedure. Once the destination node has received the RREQ, it sends back a RREP packet. We apply the results in the previous section to calculate the routing discovery time $T_{\mathrm{RDT}}$ .

Let $T_{\mathrm{RDP}}$ denote the routing discovery period, which lasts from the beginning of routing discovery procedure to the restart of next routing discovery procedure because of the failure of routing discovery. For simplicity, we assume that the source node immediately resends the RREQ after running out of the routing discovery period and the times of restart routing discovery procedure are not limited.

From equation (14), we have the probability of routing discovery failure for a given N-hop path $1-P_{\mathrm{NR}}$ . We ignore the packet delay in a successful routing discovery and assume that routing discovery procedures are independent. Then, we have the probability distribution of $T_{\mathrm{RDT}}$

$$P(T_{\mathrm{RDT}}=n{T}_{\mathrm{RDP}})={(1-P_{\mathrm{NR}})}^n{P}_{\mathrm{NR}}$$

(23)

The average routing discovery time $E[T_{\mathrm{RDT}}]$ is given by

$$\begin{array}{cc}\multicolumn{1}{c}{E\left[T_{\mathrm{RDT}}\right]}& =\sum _{n=0}^{\infty }n{T}_{\mathrm{RDP}}P(T_{\mathrm{RDT}}=n{T}_{\mathrm{RDP}})\hfill \\ \multicolumn{1}{c}{}& =\sum _{n=0}^{\infty }n{T}_{\mathrm{RDP}}{(1-P_{\mathrm{NR}})}^n{P}_{\mathrm{NR}}\hfill \end{array}$$

(24)

Simulation and theoretical results

Simulation parameters

We use MATLAB to simulate the node distribution, the routing discovery procedure, and the node mobility, respectively. We consider a network of size D and a given path of N hops. Some important parameters are shown in Table 1.

Table 1.

Simulation parameters.

Parameters	Values
Effective communication radius $R_{\mathrm{eff}}$	(100/150/200) m
Size of square area D	2000 × 2000 m2
Node density $\rho$	(2/4/6/8) × 10−5 nodes/m2
Signal attenuation threshold ${\beta }_{\mathrm{th}}$	(63/66/69) dB
Path loss exponent $\alpha$	3
Standard deviation $\sigma$	4
Minimum node velocity $v_{\min }$	4 m/s
Maximum node velocity $v_{\max }$	6 m/s
Routing discovery period $T_{\mathrm{RDP}}$	3 s

Network connectivity

The nodes are randomly deployed in area D. Two nodes are considered connective if the distance between them is less than $R_{\mathrm{eff}}$ . Simulation and theoretical results are shown in Figures 8 and 9.

Figure 8.

Probability of existence of n-hop route with $\rho =4\times {10}^{-5}\mathrm{nodes}/{\mathrm{m}}^2$ .

Figure 9.

Probability of existence of n-hop route with $R_{\mathrm{eff}}=100\mathrm{m}$ .

The probability of existence of N-hop route $P_{\mathrm{NC}}$ versus the number of hop count n has been illustrated in Figures 8 and 9. With an increase in hop count n, $P_{\mathrm{NC}}$ decreases. When $P_{\mathrm{NC}}$ meets the threshold, we get the maximum hop count $N_{\max \_c}$ . As shown in Figure 8, for a given node density $\rho$ , $P_{\mathrm{NC}}$ increases with $R_{\mathrm{eff}}$ . Thus, the maximum hop count $N_{\max \_c}$ is positively correlated with $R_{\mathrm{eff}}$ .

Figure 9 shows that, for a given $R_{\mathrm{eff}}$ , the maximum hop count $N_{\max \_c}$ is positively correlated with $\rho$ . As a result, if the threshold of $P_{\mathrm{NC}}$ is set, $N_{\max \_c}$ is decided by both $R_{\mathrm{eff}}$ and $\rho$ in our assumption.

Path reliability

In order to analyze the probability of routing success, we simulate the routing discovery procedure in MATLAB. Nodes are stationary and the source node broadcasts an RREQ to start the routing discovery procedure. The relay nodes forward the RREQ and the destination node replies the source with RREP. We apply the link model in Section “Stability components.” Simulation and theoretical results are shown in Figures 10 and 11.

Figure 10.

Probability of routing success of a given route with $\alpha =3$ , $\sigma =4$ , and ${\beta }_{\mathrm{th}}=69\mathrm{dB}$ . Nodes are deployed in a linear network and the distance between neighbors is randomly distributed in $(0,R_{\mathrm{eff}})$ .

Figure 11.

Probability of routing success of a given route with $\alpha =3$ , $\sigma =4$ , and $R_{\mathrm{eff}}=150\mathrm{m}$ . Nodes are deployed in a linear network and the distance between neighbors is randomly distributed in $(0,R_{\mathrm{eff}})$ .

The probability of routing success of a given N-hop route $P_{\mathrm{NR}}$ versus the hop count n is illustrated in Figures 10 and 11. With an increase in hop count n, $P_{\mathrm{NR}}$ decreases. When $P_{\mathrm{NR}}$ meets the threshold, we get the maximum hop count $N_{\max \_r}$ .

In Figure 10, we keep the signal attenuation threshold ${\beta }_{\mathrm{th}}$ constant, which can be increased by improving the signal transmission power or improving the receiver sensitivity. From Figure 10, we know that $P_{\mathrm{NR}}$ is negatively correlated with $R_{\mathrm{eff}}$ .

In Figure 11, we keep the effective communication radius $R_{\mathrm{eff}}$ constant. By changing ${\beta }_{\mathrm{th}}$ , we know that $P_{\mathrm{NR}}$ is positively correlated with ${\beta }_{\mathrm{th}}$ . As a result, if the threshold of $P_{\mathrm{NR}}$ is set, $N_{\max \_r}$ is decided by both ${\beta }_{\mathrm{th}}$ and $R_{\mathrm{eff}}$ in our assumption.

Node mobility

To study the node mobility, we consider a given path of N moveable nodes. We first analyze the relative speed and remaining link expectancy time. Then, the path expectancy time and the routing discovery time, respectively, are analyzed. Simulation and theoretical results are shown in Figures 12–16.

Figure 12.

PDF of related speed with $v_{\min }=4\mathrm{m}/\mathrm{s}$ and $v_{\max }=6\mathrm{m}/\mathrm{s}$ .

Figure 13.

PDF of link expectancy time with $v_{\min }=4\mathrm{m}/\mathrm{s}$ and $v_{\max }=6\mathrm{m}/\mathrm{s}$ .

Figure 14.

Average path expectancy time.

Figure 15.

Average routing discovery time with $\alpha =3$ , $\sigma =4$ , and ${\beta }_{\mathrm{th}}=69\mathrm{dB}$ .

Figure 16.

The difference between $T_{\mathrm{PET}}$ and $T_{\mathrm{RDT}}$ with $\alpha =3$ , $\sigma =4$ , and ${\beta }_{\mathrm{th}}=69\mathrm{dB}$ .

The PDF of related speed is shown in Figure 12 with $v_{\min }=4\mathrm{m}/\mathrm{s}$ and $v_{\max }=6\mathrm{m}/\mathrm{s}$ . We can see that the simulation results are consistent with the theoretical results.

Figure 13 shows the PDF of $T_{\mathrm{LET}}$ . It can be seen that the curves flatten out with an increase in $R_{\mathrm{eff}}$ .

Simulation and theoretical results are shown in Figure 14. The average $T_{\mathrm{PET}}$ is positively correlated with $R_{\mathrm{eff}}$ . As we can see from Figure 14, when the hop count n increases, $T_{\mathrm{PET}}$ decreases. If the threshold of $T_{\mathrm{PET}}$ is set, there exists a maximum hop count $N_{\max \_m}$ , which is decided by $R_{\mathrm{eff}}$ in our assumption. When $T_{\mathrm{PET}}$ meets the threshold, the network stability becomes unacceptable because of too frequent routing discovery.

Figure 15 shows the simulation and theoretical results of $T_{\mathrm{RDT}}$ versus the hop count n. The average $T_{\mathrm{RDT}}$ is positively correlated with $R_{\mathrm{eff}}$ . In fact, from the relation between $T_{\mathrm{RDT}}$ and $P_{\mathrm{NR}}$ , it is easy to know that the average $T_{\mathrm{RDT}}$ is negatively correlated with ${\beta }_{\mathrm{th}}$ . Moreover, Figure 15 shows that $T_{\mathrm{RDT}}$ increases with hop count n. If the threshold of $T_{\mathrm{RDT}}$ is set, there also exists a maximum hop count $N_{\max \_m}$ , which is decided by both $R_{\mathrm{eff}}$ and ${\beta }_{\mathrm{th}}$ in our assumption. When $T_{\mathrm{RDT}}$ meets the threshold, a too long time has to be waited before the route establishment. Thus, the network stability may become unacceptable.

More importantly, with an increase in hop count n, $T_{\mathrm{PET}}$ decreases, while $T_{\mathrm{RDT}}$ increases. Obviously, $T_{\mathrm{RDT}}$ is getting closer and closer to $T_{\mathrm{PET}}$ . If $T_{\mathrm{RDT}}$ is greater than or close enough to $T_{\mathrm{PET}}$ , the N-hop route breaks before its establishment. In this case, the network is unstable and even unusable.

The difference between $T_{\mathrm{PET}}$ and $T_{\mathrm{RDT}}$ is written as $\epsilon =T_{\mathrm{PET}}-T_{\mathrm{RDT}}$ . As shown in Figure 16, with an increase in hop count n, $\epsilon$ decreases. If a threshold ${\epsilon }_0$ is set, there is a maximum hop count $N_{\max \_m}$ .

Analysis

From the simulation and theoretical results above, we have three maximum hop counts $N_{\max \_c}$ , $N_{\max \_r}$ , and $N_{\max \_m}$ , deduced from network connectivity, path reliability, and node mobility, respectively. The channel fading model and node mobility model are assumed unchanged in the same scene.

For simplicity, $N_{\max \_c}$ is given by

$$N_{\max \_c}=f_c(R_{\mathrm{eff}},\rho )$$

(25)

which denotes that $N_{\max \_c}$ is determined by effective communication radius $R_{\mathrm{eff}}$ and node density $\rho$ .

Similarly, $N_{\max \_r}$ and $N_{\max \_m}$ are, respectively, given by

$$N_{\max \_r}=f_r(R_{\mathrm{eff}},{\beta }_{\mathrm{th}})$$

(26)

and

$$N_{\max \_m}=f_m(R_{\mathrm{eff}},V,{\beta }_{\mathrm{th}})$$

(27)

Through theoretical analysis, we qualitatively know that $N_{\max \_c}$ is positively correlated with $R_{\mathrm{eff}}$ and $\rho$ ; $N_{\max \_r}$ is negatively correlated with $R_{\mathrm{eff}}$ and positively correlated with ${\beta }_{\mathrm{th}}$ . In consideration of that $N_{\max \_m}$ is determined by $T_{\mathrm{PET}}$ and $T_{\mathrm{RDT}}$ , the relations between $N_{\max \_m}$ and network attributes are more complicated, and there still remains some uncertain factors. However, it is clear that $N_{\max \_m}$ is positively correlated with ${\beta }_{\mathrm{th}}$ . The relation between $N_{\max \_m}$ and $R_{\mathrm{eff}}$ is still needed to be researched in detail.

In most of wireless multi-hop networks, node mobility has little impact on network stability. For example, in wireless multi-hop networks, such as WSNs, WMNs, and low-speed MANETs, the impact of node mobility can be ignored to some extent. While in some particular wireless multi-hop networks, AANETs, VANETs, and high-speed MANETs, for example, there is important significance to study the impact of node mobility on wireless multi-hop networks.

First, we analyze the condition without node mobility. Generally, the channel model does not change in the same scene. For a given channel model, the wireless propagation model we apply in this article with given $\alpha$ and $\sigma$ , for example, the point-to-point delivery ratio between neighbor nodes depends on the signal attenuation threshold ${\beta }_{\mathrm{th}}$ and the distance between them. We know from the theoretical analysis above that the probability of routing success $P_{\mathrm{NR}}$ increases as the effective communication radius $R_{\mathrm{eff}}$ decreases or the signal attenuation threshold ${\beta }_{\mathrm{th}}$ increases. Without regard to the signal attenuation threshold ${\beta }_{\mathrm{th}}$ , to achieve a better probability of routing success $P_{\mathrm{NR}}$ or to increase $N_{\max \_r}$ , we need to reduce the effective communication radius $R_{\mathrm{eff}}$ .

However, without considering the node density $\rho$ , we need to increase $R_{\mathrm{eff}}$ to have a larger $N_{\max \_c}$ . As a result, for any given $\rho$ and ${\beta }_{\mathrm{th}}$ , $N_{\max \_c}$ and $N_{\max \_r}$ are negatively correlated, and there is an optimal hop count limitation for an appropriate $R_{\mathrm{eff}}$ . In addition, we can increase the maximum hop count by increasing $\rho$ and ${\beta }_{\mathrm{th}}$ , respectively. Taking node mobility into consideration, we analyze $T_{\mathrm{PET}}$ and $T_{\mathrm{RDT}}$ , respectively.

In general, node mobility model does not change in the same scene. Thus, we just analyze the impact of $R_{\mathrm{eff}}$ and ${\beta }_{\mathrm{th}}$ on $N_{\max \_m}$ . First, by increasing ${\beta }_{\mathrm{th}}$ , $T_{\mathrm{RDT}}$ decreases, while $P_{\mathrm{NR}}$ increases. As a result, $N_{\max \_m}$ increases as well as $N_{\max \_r}$ .

The impact of $R_{\mathrm{eff}}$ on node mobility is much more complicated than ${\beta }_{\mathrm{th}}$ . As $R_{\mathrm{eff}}$ increases, both $T_{\mathrm{PET}}$ and $T_{\mathrm{RDT}}$ increase. The increase in $T_{\mathrm{PET}}$ is good for network stability, while $T_{\mathrm{RDT}}$ is not. The maximum hop count decided by $T_{\mathrm{RDT}}$ decreases.

On the contrary, as $R_{\mathrm{eff}}$ decreases, both $T_{\mathrm{PET}}$ and $T_{\mathrm{RDT}}$ decrease. The maximum hop count decided by $T_{\mathrm{PET}}$ decreases. From analysis above, an optimal maximum hop count can be achieved by setting an appropriate $R_{\mathrm{eff}}$ . Of course, that $T_{\mathrm{PET}}$ greater than $T_{\mathrm{RDT}}$ in a certain extent must be satisfied first.

Possible solutions

Form the analysis above, there is a maximum hop count if network connectivity, path reliability, and node mobility of wireless multi-hop networks are satisfied. The maximum hop count $N_{\max }=\min (N_{\max \_c},N_{\max \_r},N_{\max \_m})$ . When the hop count between source node and destination node meets or exceeds the hop count limitation, the network becomes unstable or even unusable.

In order to overcome restrictions brought by the hop count limitation, one of the most direct ways is to reduce the hop count in a route. Adding a few base stations in wireless multi-hop networks could be a feasible scheme. Communication between the base stations is wired communication with high reliability and low latency. Since the base stations have stronger communication abilities, they have higher priorities to act as relay nodes than ordinary nodes, and two base stations, together with base stations between them, can be seen as an ordinary node. As a result, the number of relay nodes between source node and destination node in a route decreases. However, by adding base stations into network, we actually add diversities into nodes in the network. The routing strategy may be completely different from the ordinary routing strategies, and the deployment strategy of base stations is also a new research point. This may be unfeasible in some kind of networks, such as MANETs, that base stations are not allowed. In such kind of networks, network stability may never be achieved unless hop count limitation problem is settled.

In view of non real-time services in networks with node mobility, delay tolerate networks (DTNs) ¹⁸ may be a feasible solution to deal with the restrictions of hop count limitation. In DTN, nodes send packets in store-carry-forward way. On one hand, without considering the end-to-end delay, the impact of node mobility can be ignored. To a certain extent, node mobility is helpful for DTN. On the other hand, despite the low density of nodes in DTN, as long as the nodes have chances to meet each other, the non real-time services are guaranteed. As a result, the impact of network connectivity can also be ignored. In fact, a real-time multi-hop route is not necessary in DTN, and because of the carry-and-forward strategy, DTN could be seen as a one-hop wireless communication network. In other words, for the maximum hop count 1, network connectivity, path reliability, and node mobility are all out of consideration. However, limited to the type of service, the application area of DTN in wireless multi-hop networks is relatively small.

For wireless multi-hop networks whose nodes remain static, such as WSNs and WMNs, we do not need to care about the impact of node mobility. If the nodes are not stochastically deployed, an optimal node deployment strategy^19,20 is easy to meet the requirements of network connectivity and path reliability, which can greatly increase network stability. From the analysis above, we know that path reliability and network connectivity are negatively correlated in some cases. We can increase path reliability without affecting network connectivity and then appropriately relax the requirement of path reliability to increase network connectivity. For example, we can increase path reliability by applying more advanced modulation technologies or increasing the wireless signal transmission power. And then we appropriately increase the effective communication radius to increase maximum hop count deduced form network connectivity.

Another solution to increase the maximum hop count is to apply central control routing algorithms such as software-defined wireless sensor networks (SDWSNs).^21,22 By avoiding routing discovery procedure, the path reliability will be greatly improved. As a result, wireless multi-hop networks whose nodes remain static, optimal node deployment strategies, advanced physical layer technologies, and central control routing algorithms may be the keys to achieve high network stability.

Conclusion

In this article, we mainly analyze the relation between expected hop count and network stability in wireless multi-hop networks. We finally find out the hop count limitation of certain wireless multi-hop networks by analyzing stability factors including network connectivity, path reliability, and node mobility. Relations between hop count limitations deduced from network connectivity, path reliability, and node mobility have been analyzed comprehensively. Meanwhile, to deal with the hop count limitation, we proposed some practical schemes, which aim at reducing the hop count in wireless multi-hop networks. The hop count limitation of wireless multi-hop networks also has reference significance in network planning when determining the coverage radius of networks, the minimum number of nodes, and so on.

The main purpose of this article is to provide a framework for analyzing stability of wireless multi-hop networks and point out the relation between hop count limitation and network stability. In our further study, more details about relations between hop count limitations deduced from different aspects will be analyzed. More basic network attributes will be taken into consideration to improve the accuracy and scalability of theoretical model for hop count limitation research. The final goal of hop count research is to find out the limitations of network performances in wireless multi-hop networks and provide the basis of network planning.