Delay and capacity in MANETs under random walk mobility model

Abstract

The closed-form results for delay and capacity in mobile ad hoc networks are important for the performance analysis of different transmission protocols. Most existing works focus on independent and identically distributed mobility model, which is always regarded as an idealized global model. In this paper, we extend the investigation to the random walk model, which characterizes practical situations more accurately. Some local movements cause a series of complicated probabilistic problem, we develop a method to calculate the meeting probability between two randomly selected nodes under random walk mobility model. Targeting at the most commonly used routing schemes which are modeled by 2HR-f algorithm, we obtain the closed-form solutions for delay and capacity, where the wireless interference and medium access contention among nodes are considered. Extensive simulations demonstrate the accuracy of our theoretical results.

1 Introduction

A mobile ad hoc network (MANET) is a self-configurable network consisting of mobile devices without infrastructure support. In such a network, every terminal user can act as a relay. Users can communicate with each other via multihop wireless transmissions [1].

Delay and capacity are two important metrics to evaluate the performance of MANETs. The former represents the average time it takes for a packet to be delivered from a sender to a receiver, and the latter represents the expected number of packets that can be successfully delivered in a unit time. Analysis of these two metrics, especially their closed-form solutions, can help the design of optimized transmission protocols. Grossglauser and Tse [2] considered a single copy based transmission protocol and proved that the capacity of MANETs is scalable. After that, researchers have investigated these two metrics of MANETs under different mobility models. However, most work focuses on the order sense results. Liu et al. [3] modeled the two-hop relay algorithms and gave the corresponding closed-form expressions on delay and capacity. Their work is based on independent and identically distributed (i.i.d.) mobility model. Because their i.i.d. mobility model is global in the sense that nodes can move to any position in the area after a single step, their results are not valid under the local mobility models, such as the random walk mobility model [4]. Here we focus on the random walk mobility model. In this model, each movement of node is dependent on the previous position which is much more realistic compared with i.i.d. model.

In random walk mobility model, nodes move on to a nearby area in each step. Comparing with i.i.d. mobility model, it describes the movement of humans more accurately. There have been many variants in the literature, e.g., random waypoint mobility model [5] and random direction mobility model [6]. These models have been widely used in the theoretical analysis and simulations of different protocols in MANETs [7, 8].

Since mobility model determines how locations and velocities of mobile nodes change over time, it plays a significant role in the performance of MANETs. Relaxing the mobility model from i.i.d. to random walk in the analysis is nontrivial because we have to deal with the accurate description of the meet events between nodes for information exchange and the discrete high-dimensional probability distribution.

In the practical application, MANETs achieve communication with the help of node mobility. The mobile users prefer to change their locations timely and enter or leave the network at any time, so the wireless network topology may change quickly and the connectivity is always difficult to maintain. It is noted that many routing protocols or relay algorithms have been widely adopted for MANETs, whose implementation involves acquiring the information on which cell a node stays within a certain time slot and how long the pause interval time is taken for each move. Such information should be obtained before communication is set up to facilitate routing, and all of them are part of the node meet events. By means of node encounters within a location range, the routing scheduling can be easily implemented as follows. Each transmitter first knows which nodes are its neighbors currently, and thus can determine if it has opportunities to transmit data and who is the communication target. Moreover, the meet events among any nodes play a significant role in the performance analysis of the MANETs, but are difficult to characterize accurately. Since the mobility model is available to every mobile node in the MANET, the movement for each node is independent of each other and random. Thus, the location distributions of mobile nodes present discrete characteristics in the network. If we build up a one-dimensional probability space for each mobile node, the probabilistic characteristics of mobility behaviors in the network range tend to be a summation of the high-dimensional probability distribution and therefore it is difficult to achieve dimensionality reduction.

In this paper, we focus on the two-hop relay algorithms [9, 10] (modeled by 2HR-f algorithm) which are widely used in MANETs. We propose a method to calculate the probability that two randomly selected nodes meet at the kth time slot and the contention probability when wireless medium access contention is considered. Based on these results, we derive the closed-form solution for delay and capacity of MANETs under the random walk mobility model. Our main contributions are summarized as follows.

• To accurately describe the characteristics of node movement under random walk mobility model, we develop a method to calculate the meeting probability between nodes in a time slot.

• Taking interference and wireless medium access contention into consideration, we derive closed-form solutions for delay and capacity of MANETs based on random walk mobility model.

• Through extensive simulation studies, we show the correctness of our theoretical results, and the difference of network performance under different mobility models.

The rest of this paper is organized as follows. Section 2 reviews the related work. Section 3 presents the models and assumptions used in this paper. In Sect. 4, we calculate the meeting probabilities between two nodes under random walk mobility model. In Sect. 5, we give the closed-form results of delay and capacity. Various simulation results are given in Sect. 6. Finally, we give the concluding remarks in Sect. 7.

2 Related work

In the landmark paper, Gupta and Kumar [11] showed that per-node throughput scales as $\varTheta\left(\frac{1}{\sqrt{n \log n}}\right)$ in a random static wireless network. It can be increased to $\varTheta(1)$ when i.i.d. mobility was introduced by Grossglauser and Tse [2]. However, Grossglauser and Tse [2] does not address the delay issue. Since then, the i.i.d. mobility model is used in most research [12–14].

Regarding the case that no copies are transmitted for packets in two-hop relay, Wang et al. [15] proposed that the network capacity is $\varTheta\left(\frac{1}{n \log k}\right)$ and the network delay is $\varTheta\left(\frac{1}{k}\right)$, where k is the total number of distinctive destinations and n is the number of nodes in the network. Regarding the case with packet copies, Neely and Modiano [12] proposed a packet scheduling scheme to achieve the trade-off $\lambda(n) \leq O\left(\frac{D(n)}{n}\right)$, where λ(n) is the per-node throughput and D(n) is the average end-to-end delay. The throughput capacity and delay in [15] turn to be $\varTheta\left(\frac{1}{\sqrt {n \log k}}\right)$ and $\varTheta\left(\frac{1}{k \sqrt {n \log k}}\right)$, respectively. Incorporating the multiuser reception and power control, a better capacity-delay trade-off $\lambda^{2}(n) \leq \varTheta\left(\frac{D(n)}{n}\right)$ is achieved [13]. In [14], Lin and Ness established the upper bound of the maximum per-node throughput under a delay constraint, and proposed the scheduling schemes which can approach the bound up to some logarithmic factor. Liu et al. [3] gave the closed-form theoretical results for two-hop relaying based mobile wireless networks under the i.i.d. mobility model.

Besides, there has been substantial work investigating the trade-offs between delay and capacity in mobile wireless networks under different non-i.i.d. mobility models [7, 8]. Gamal et al. [16] and Lin et al. [17] investigated the problem under Brownian motion model. EI Gamal et al. described a scheme to achieve the optimal order of delay for any given throughput in [16].

With regard to the random walk mobility model, EI Gamal et al. [18, 19] and Mammen et al. [20] discussed the problem under random walk mobility model and restricted mobility model individually. From a global perspective, Sharma et al. established the relationship between critical delay and first exit/hitting time [21]. Critical delay means the minimum delay that has to be tolerated in mobile networks to achieve the same throughput in the order sense as in static wireless networks. They showed that when the network is divided into n ^β × n ^β cells, the two-hop delay is θ(n) for β < 1/2 and θ(n log n) for β = 1/2 when the hybrid random walk models are considered. More recently, Wang et al. [22] gave the asymptotic capacity and delay bounds for two different mobility models under Gaussian Channel Model, where the two mobility models are hybrid random walk mobility model and discrete random direction mobility model. Zhuo and Ying [23] presented the two-hop capacity for multi-cast session, which is suitable for both the i.i.d. mobility model and the random walk mobility model.

Different new mobility models have been proposed and the corresponding delay-capacity trade-offs have been investigated. Ying et al. [24] proposed four new mobility models, and investigated the maximum throughput per node with a delay constraint. In [25], mobility characteristics are exploited and a routing algorithm is designed to achieve the optimal capacity while keeping the delay low. Garetto et al. [26, 27] analyzed the results under the mobility models where each node moves around its home-points. In [28], it is found that spatial heterogeneity improves the delay-capacity scaling laws. In [29], the trade-off under the reference point group mobility model is investigated, and it is shown that the movement relevance of different nodes improves the performance. Based on the work of [21], Lee et al. [30] derived the critical delay under Lévy mobility model.

Most afore mentioned works mainly focus on unicast. Li [31] derived the asymptotic bounds of multicast capacity in wireless networks under protocol interference model. The results generalized the ones for unicast [11] and broadcast [32, 33]. Li et al. [34] also offered the bounds under Gaussian Channel Model. Wang et al. [15] found that the ratio between delay and capacity in multicast is smaller than that directly extended from the result in [12]. Targeting at the mobility models similar to [24], they gave a global perspective of the delay-capacity trade-off of multicast in mobile wireless networks [35].

Since the global i.i.d. mobility model is often used in the scenario that nodes can move to any position in the network area after a single step, the performance results based on this idealized mobility model are invalid. Nevertheless, under the local random walk mobility model, each movement of node is dependent on the previous position, which can be applied in some more realistic scenarios. So different from existing works, in this paper, we attempt to derive closed-form solutions for delay and capacity in MANETs under the random walk mobility model.

Table 1 lists frequently used notations and parameters in this paper.

Table 1 Summary of notations and parameters

3 Models and assumptions

3.1 Network model

As shown in Fig. 1, the network we consider consists of n mobile nodes which are in a finite square region of unit torus. The area is evenly divided into m × m cells. Besides, two cells are called adjacent if they share a common point. For a given cell X, we define the eight cells that located in its surround as the eight adjacent cells, which consist of the nine one-hop cells with the cell X. Every node follows the fast-moving pattern [29]. It is located in a particular cell at the beginning of each time slot and will stay there for the whole slot.

Fig. 1

An example of nine different transmission-groups with α = 3. At a time slot, n = 5 nodes are randomly located in a square region of unit area, which is evenly divided into 9 × 9 cells

Similar to [24, 27, 36], we choose the permutation traffic pattern and consider a worst-case uni-cast scenario, which points out that there are n distinct flows (source-destination pairs), i.e., each node is the source of its locally generated traffic flow, a potential relay for other n − 2 flows and at the same time the destination of a flow originated from other node. The traffic generated at the sources is a Poisson stream with rate λ (packets/slot). In addition, we assume that the length of a time slot equals to that it takes for a packet transmission between two nodes when they contact.

3.2 Transmission model

There are usually two ways for a destination to receive data: neighbor-capture and multi-hop capture [21, 30]. In the former, it gets data when the source or a relay node carrying the data is in its neighborhood. In the latter, when there is a multi-hop path from the source, data can be successfully delivered and transmission delay is negligent comparing with the time interval between two consecutive appearance of a path. Because we assume the mobility models belong to fast mobility, neighbor-capture is adopted in this paper.

In order to avoid the interference among simultaneous transmissions, we introduce the transmission-group [3], i.e. a subset of cells in which any two cells have a vertical and horizontal distance of some multiple of α cells. As illustrated in Fig. 1, all cells that have the same number belong to a transmission-group. The parameter α should be set as $\alpha=\hbox{min}\{\lceil (1+\triangle)\sqrt8 \rceil +2,m\}$. It is obvious that there are α ² transmission-groups in total. To make it fair, each group (i.e. some specific cells) will be activated in every α ² time slots. For the proof of this formula, please refer to [3].

In this case, we consider a local transmission scenario, each node in the same transmission group can simultaneously send packets to its one-hop neighbors (nodes located in the same cell and the eight adjacent cells) without wireless transmission interference. Also note that if m ≤ 3, the network users communicate at any time slot successfully without being affected by mobility models or node positions on the request of this one-hop transmission range. Thus, we only consider m > 3 in this paper.

3.3 Random walk mobility model

This paper focuses on the random walk mobility model [23], where each node independently and uniformly selects a destination cell among the nine one-hop cells at the beginning of each time slot and will stay there for the remaining time of the slot. To be specific, if a node moves to the eight adjacent cells, it means that one movement does happen along one of the eight directions. But if the node still stays in the same cell after movement, we say that its destination cell happens to be the central cell among the one-hop mobility range. So the probability for each one-hop cell to be selected as the destination cell is 1/9.

Note that the relative position between every two nodes S and D at time slot k is closely related to their relative positions at time slot k − 1. We denote their positions at slot k as S _k and D _k (k ≥ 0), respectively. Figure 2 gives an example of the node movement following this model. It is easy to see that the model is a local mobility model.

Fig. 2

An example of node movement following RWM. The shadow denotes the direction of node S. S and D will meet in three time slots

3.4 2HR-f algorithm

In the common two-hop relay algorithm [12] with f-cast (2HR-f), as shown in Fig. 1, every packet originated from S will go through at most two hops to reach its destination node D. Each packet can be delivered to at most f distinct relay nodes and should be received in order at its destination. We denote the relay node as R. Hereon, in order to avoid situation that excessive packet copies are transmitted to the relay nodes, which may lead to unnecessary extra communications, we use the number of mobile nodes (i.e., n) to restrict the upper bound of the number of packet copies (i.e., $0 \leq f \leq \lfloor \sqrt n \rfloor$), which is a common assumption and is similar to the research in [3].

In the two-hop relay algorithm, there are only three kinds of one-hop transmission, i.e., S-to-D, S-to-R and R-to-D, and the R-to-R transmission that appears in the multi-hop relay scheme is thus not included. Obviously, S-to-D transmission has the highest priority, and the other two have the same priority. When there are multiple possible senders (receivers) in an active cell (cells), one of them is chosen according to uniform distribution.

4 Probability computations

In this section, we develop methods to compute probabilities in 2HR-f algorithm under the random walk model, and then provide some basic theoretical results.

4.1 Mobility model assumptions

The theoretical model developed under the i.i.d. model in Liu’s work cannot be directly applied to the random walk model. As for this reason, we first analyze the meet events between S and D.

We elaborate the memory condition for random walk model, which is shown as in Fig. 3. At time slot k − 1, D _k−1 must belong to the nine one-hop cells of S _k−1 (k ≥ 1). After a walk, there are three kinds of meet events between S and D at time slot k, which are defined, respectively, as follows.

• Event X: S _k and D _k belong to the same cell.

• Event Y: D _k belongs to the eight adjacent cells of S _k .

• Event Z: D _k belongs to the nine one-hop cells of S _k .

Fig. 3

The illustration of memory condition and a classification of possible meeting positions

We then use P _x , P _y and P _z to denote the probabilities of the corresponding events, respectively.

Remark 1

As the situation of one walk at any other time slot is approximately equivalent to that at the initial time [37], we only need to consider one walk to characterize the overall behaviors of mobility models.

4.2 Probabilistic characterization

We start with the probabilities of meet events. First of all, since each node randomly selects an initial position from m × m cells at the initial time slot, we have

$$ P_x=1/m^2, P_y=8/m^2, P_z=9/m^2,\quad where\,k=0. $$

Regarding the case k ≥ 1, we establish the following results.

Lemma 1

The probability that S _k and D _k belong to the same cell is

$$ P_x=49/(81m^2) \, (m \geq 5) $$

(1)

Proof

The memory condition of meet events is shown in Fig. 3(a), where the possible D _k−1 belongs to the nine one-hop cells of S _k−1. Afterwards, in a network range with space boundary interoperability, drawing support from plane symmetry in the position distribution of destination cells, we first divide the subset of cells that contain the possible S _k into three categories according to the proportions 4, 4 and 1, as shown in Fig. 3(b–d) with the probabilities 4/9, 4/9 and 1/9, respectively, as each of the nine one-hop cells has the probability 1/9 to become S _k . Then we focus on each type of meeting positions to simplify the analysis on the different meet events, and finally integrate all of the meeting probabilities proportionally.

For the category (b–d) in Fig. 3, select a S _k from each of them as an example, the possible D _k−1 and its moving path (i.e. from a D _k−1 to the suitable D _k which is same as S _k ) are shown as in Fig. 4(a–c), respectively. The first factor stands for the number of cells that D _k−1 might belong to and the second factor stands for the number of possible cells after one walk of D. Next, if we take Fig. 4(a) as an example, the number of all possible state D _k is m ² × 9, and only 4 × 1 states can meet the requirements of event X, so the corresponding probability of situation in Fig. 4(a) is (4 × 1)/(m ² × 9). The rest can be done in the same manner.

Fig. 4

The illustration of all possible movement process from D _k−1 to D _k , where the blackspots represent possible D _k−1, the shaded areas represent S _k and the arrows take example for corresponding moving path

Thus, combining all the situations in Figs. 3 and 4, we have

$$ P_x=\frac{1}{m^2} \left(\frac{4}{9} \times \frac{4\times1}{m^2\times9} + \frac{4}{9} \times \frac{6\times1}{m^2\times9} + \frac{1}{9} \times \frac{9\times1}{m^2\times9} \right) m^2 $$

then (1) follows. $\square$

Lemma 2

The probability that D _k belongs to the eight adjacent cells of S _k is

$$ P_y=312/(81m^2)\, (m \geq 5) $$

(2)

Proof

The possible D _k−1 and its moving path (i.e. from a D _k−1 to the suitable D _k which belongs to the eight adjacent cells of S _k ) are shown as Fig. 5. The rest can be done in the same manner as in the proof of Lemma 1, thus we have

$$ \begin{aligned} P_y &= \frac{1}{m^2} \left(\frac{4}{9} \times \frac{1\times8 + 2\times5 + 3\times3 + 2\times2 + 1\times1}{m^2\times9} \right. \\ &\quad\left. + \frac{4}{9} \times \frac{3\times5 + 1\times8 + 3\times3 + 2\times2}{m^2\times9} \right. \\ &\quad\left. + \frac{1}{9} \times \frac{4\times3 + 4\times5 + 1\times8}{m^2\times9} \right) m^2 \\ \end{aligned} $$

then (2) follows. $\square$

Fig. 5

The illustration of all possible movement process from D _k−1 to D _k , where the blackspots represent possible D _k−1, the shaded areas represent eight adjacent cells of S _k that D _k might belong to and the arrows take example for corresponding moving path

Lemma 3

The probability that D _k belongs to the nine one-hop cells of S _k is

$$ P_z=361/(81m^2) \, (m \geq 5) $$

(3)

Proof

The possible D _k−1 and its moving path (i.e. from a D _k−1 to the suitable D _k which belongs to the nine one-hop cells of S _k ) are shown as in Fig. 6. The rest can be done in the same manner as in the proof of Lemma 1, thus we have

$$ \begin{aligned} P_z& = \frac{1}{m^2} \left( \frac{4}{9} \times \frac{3\times6 + 1\times9 + 2\times4 + 2\times2 + 1\times3}{m^2\times9} \right. \\ &\quad\left.+\frac{4}{9} \times \frac{1\times9 + 2\times6 + 2\times3 + 1\times4 + 2\times2 + 1\times1}{m^2\times9} \right. \\ &\quad\left.+\frac{1}{9} \times {4\times4 + 4\times6 + 1\times9}{m^2\times9} \right) m^2 \\ \end{aligned} $$

then (3) follows. $\square$

Fig. 6

The illustration of all possible movement process from D _k−1 to D _k , where the blackspots represent possible D _k−1, the shaded areas represent nine one-hop cells of S _k that D _k might belong to and the arrows take example for corresponding moving path

Remark 2

If the network size m = 4, different conclusions are suggested, i.e., $P_x=49/\left(81m^2\right),P_y=392/\left(81m^2\right),P_z=441/\left(81m^2\right)$, and the proof is omitted here.

With P _x , P _y and P _z , we can find other important probabilities used in performance evaluation. For a given active cell, we first define two contention probabilities.

Definition 1

Contention probability for transmitting opportunity is defined as the probability that there are at least two nodes inside the active cell, which is given by

$$ 1-\left(1-P_x\right)^n-C_n^1P_x\left(1-P_x\right)^{n-1} \to 1-1.60e^{-49/81}, $$

when $m=\sqrt n$ and → means n approaches to infinity.

Definition 2

Contention probability for receiving opportunity is defined as the probability that aside from the selected transmitter, the active cell has at least two other nodes inside its nine one-hop cells, which is given by

$$ \begin{aligned} 1-(1-P_x)^n-\sum_{k=1}^2 C_n^k {P_x}^k (1-P_z)^{n-k} -C_n^2 C_2^1 P_x P_y (1-P_z)^{n-2} \to 1-e^{-49/81}-3.12e^{-361/81}, \end{aligned} $$

when $m=\sqrt n$.

Definition 3

For a given n time slots and a tagged flow, we define P ₁ as the transmission probability from source node S to destination D (we denote by S-to-D for short), and define P ₂ as the transmission probability from the source node S to relay node R(or from the relay node R to destination node D) (we denote by S-to-R(or R-to-D) for short).

The details are as follows.

For P ₁, the S-to-D packet transmission happens iff the following three events happen simultaneously.

• 1. S is in an active cell,

• 2. D is in the nine one-hop cells of S,

• 3. S is selected as the transmitter.

Thus, we have

$$ \begin{aligned} P_1 =& \frac{1}{\alpha^2} \left[ \sum_{k=0}^{n-2} C_{n-2}^k {P_x}^k \left(1-P_x\right)^{n-2-k} P_x \frac{1}{k+2} \right.\\ &\quad\left. + \sum_{k=0}^{n-2} C_{n-2}^k {P_x}^k (1-P_x)^{n-2-k} P_y \frac{1}{k+1} \right]\\ =& \frac{1}{\alpha^2} \left[ \frac{nP_y+nP_x-1}{n(n-1)P_x} -\left(1-P_x\right)^{n-1}\frac{nP_y+P_x-1}{n(n-1)P_x} \right].\\ \end{aligned} $$

(4)

For P ₂, S-to-R (or R-to-D) transmission happens iff the following four events happen simultaneously.

• 1. S is in an active cell,

• 2. At least one other node is in nine one-hop cells of S,

• 3. S is selected as the transmitter,

• 4. D is not in the nine one-hop cells of S.

Thus, we obtain

$$ \begin{aligned} P_{2} & = \frac{1}{{\alpha ^{2} }}(1 - P_{z} )\left[ {\sum\limits_{{k = 1}}^{{n - 2}} {C_{{n - 2}}^{k} } P_{x} ^{k} \left( {1 - P_{x} } \right)^{{n - 2 - k}} \frac{1}{{k + 1}}} \right. \\ & \quad \left. { + \sum\limits_{{k = 1}}^{{n - 2}} {C_{{n - 2}}^{k} } P_{y} ^{k} (1 - P_{z} )^{{n - 2 - k}} } \right] \\ & = \frac{1}{{\alpha ^{2} }}\left( {1 - P_{z} } \right)\left[ {\frac{{1 - (1 - P_{x} )^{{n - 1}} }}{{(n - 1)P_{x} }} - \left( {1 - P_{z} } \right)^{{n - 2}} } \right]. \\ \end{aligned} $$

(5)

Similarly, we can also obtain the probability P _r (j) (1 ≤ j ≤ f + 1) that D will receive P and P _d (j) (j ≤ f) that S will successfully deliver a new copy of P in the next time slot.

$$ P_r(j)=P_1+ \frac{j-1}{2(n-2)} P_2, \quad P_d(j)=\frac{n-j-1}{2(n-2)} P_2. $$

(6)

The proof is similar to that in [3].

5 Throughput capacity and expected end-to-end delay under RWM

The above probabilities we discussed in Sect. 4 can be used in the theoretical analysis of throughput capacity and expected end-to-end packet delay under random walk mobility model.

The probabilities in (5) and (6) can be regarded as the transition probabilities in two finite-state absorbing Markov chains [38] to describe packet distribution process at S and reception process at D, respectively. An important property is associated with the average service time when 0 ≤ f ≤ f ₀, that is, $\overline X_S \leq \overline X_D$, where $f_0=\max\{f|E\{X_S(f+1)\} \leq E\{X_D(f+1)\}, 0 \leq f \leq \lfloor \sqrt n \rfloor\}$.

Theorem 1

If we denote by μ the per-node throughput capacity in a network with the 2HR- f relay(0 ≤ f ≤ f ₀) under random walk mobility model, then we have

$$ \mu=P_1+\frac{f}{2(n-2)} P_2 $$

(7)

Proof

Per-node throughput can be determined by following the similar procedure in [3]. $\square$

Theorem 2

If we denote by E{T _e } the expect end-to-end packet delay in a network with the 2HR- f relay (0 ≤ f ≤ f ₀), then we have

$$ E\{T_e\} \leq \frac{E\{X_S(f+1)\}}{1-\lambda E\{X_S(f+1)\}} + \frac{E\{X_D(f+1)\}}{1-\lambda E\{X_D(f+1)\}} $$

(8)

where E{X _S (f + 1)} = ∑ ^f _i=1 2(n − 2) / [(n − i − 1)P ₂] and E{X _D (f + 1)} = 2(n − 2) / [2(n − 2)P ₁ + fP ₂].

Proof

Upper bound of the expected end-to-end delay E{T _e } can be determined by following the similar procedure in [3]. $\square$

Based on the Theorems 1 and 2 and any setting of f = n ^τ, 0 < τ < log _n f ₀, we can easily derive the corresponding order sense results of throughput capacity and packet delay. It is known that order sense results of delay and capacity in MANETs under random walk model have been derived. For example, Zhou and Ying [23] obtained a throughput result of $\varTheta \left(\hbox{min} \{ 1, \sqrt{D/n_s} \}\right)$ for a delay-constrained multicast network. El Gamal et al. [18] developed the throughput function $T(n)=\varTheta \left(1/\sqrt{nb(n)\log n}\right)$ and the delay function $D(n)=O\left(n \log (1/b(n))\right)$. However, all abstract asymptotic results fail to describe the precise performance metrics. Hence, as one of the main contributions in this paper, the closed-form results we give here will have more significant impact.

6 Numerical results and analysis

In this section, we design a simulator based on statistical theory in C++ environment to simulate the packet delivery process of 2HR-f algorithm under random walk model in MANETs. In addition to the analysis of simulated performance and the validation of theoretical results, we also investigate the performance difference between random walk mobility model and i.i.d. mobility model.

6.1 Simulation settings

The transmission group is defined with α = min{8,m} on the guard factor Δ = 1. We introduce two specific network scenarios. The first scenario is fixed as n = 64, m = 8, f = 2(f ₀ = 4), μ = 9.47 × 10⁻⁴ (packets/slot), and the second scenario is fixed as n = 240, m = 16, f = 6(f ₀ = 11), μ = 3.40 × 10⁻⁴ (packets/slot). Besides, the total elapsed time in simulation is set to 10⁸ time slots.

6.2 Model validation

We use the simulator to validate results of probabilities. Table 2 indicates clearly that the simulation results match nicely with the theoretical ones for both probabilities of meet events and probabilities of transmissions in Sect. 4.2, so our framework can be used to effectively model the movement process of nodes.

Table 2 Comparison between simulated and theoretical results for probability validation: simulated/theoretical

Next, the corresponding simulation results are summarized in Fig. 7 to verify the theoretical models for per node throughput capacity and expected end-to-end packet delay under the random walk model. We denote system load by ρ = λ/μ (ρ < 1 in stable networks).

Fig. 7

Comparison between simulated and theoretical results for delay validation under random walk model, where simulated results are provided with 95 % CIs. a First network scenario. b Second network scenario

Take the first network scenario in Fig. 7(a) for example, as ρ (resp. λ) gradually increases from 0.2 up to 0.9 (resp. from 1.89 × 10⁻⁴ up to 8.52 × 10⁻⁴), the simulated expected delay (resp. upper bound of theoretical delay) under RWM increases from 1,407.20 up to 11,067.40 (resp. from 1,720.79 up to 11,105.87). The second network scenario in Fig. 7(b) indicates clearly the same trend as well. Without regard to the impact of randomness in simulation programme, our theoretical delay under RWM serves as a safe upper bound for the simulated ones in Fig. 7. Moreover, the skyrocketing behavior of packet delay when ρ approaches 1 can serve as an intuitive validation for theoretical throughput capacity, commonly observed in network delay.

Our primitivistic analysis describes the behaviors of the random walk model accurately and establishes more realistic performance expressions in MANETs, but at the same time, as compared in Fig. 8, such a change of mobility pattern makes the throughput capacity decrease and the expected end-to-end packet delay increase by comparing them with i.i.d. model. As for the reason, although there is no consistent monotone relationship between the meeting probability and the network performance, which has already been discussed in our recent study on random waypoint mobility model, the severe transmission condition in the local movement pattern still reduces the network performance significantly. The difference gap does not mean that i.i.d. model is good or bad, and the significance of our random walk mobility model can be used to captures the movement of users more accurately. So even if the introduction of random walk mobility model results in the reduction of capacity and the increment of delay, it performs better in terms of network performance in a more realistic and meaningful way.

Fig. 8

Comparison of the theoretical upper bound of expected end-to-end packet delay between i.i.d. model (μ = 1.48 × 10⁻³) and random walk model (μ = 9.47 × 10⁻⁴) for the first network scenario setting

If we denote by P _a (f + 1) the probability that a packet is received by its destination after all its f copies have been distributed (i.e., S has been notified the reception of this packet), then P _a (f + 1) will approach 1 on the condition that the vast majority of packets in transmissions have distributed f copies. Since the varying tendencies of P _a (f + 1) about two models in Fig. 9 indicate that the mobile nodes become extraordinarily busy as the system load ρ gradually increases to 1, that is, the maximum capacity of communication network is approximately achieved at this point, so the behaviors of P _a (f + 1) can also serve as a further validation factor for our theoretical throughput capacity. Besides, we can find out from Fig. 9 that the probability P _a (f + 1) in random walk mobility model approaches 1 earlier than i.i.d. mobility model due to severe transmission conditions in the former.

Fig. 9

Comparison of the probability P _a (f + 1) between random walk model and i.i.d. model for the first network scenario

6.3 Performance analysis

Another practical factor we must consider for the random walk model in MANETs is the performance of the above theoretical models to explore maximum throughput capacity. For the general setting of $\triangle=1, m=\lfloor \sqrt n \rfloor$, we summarize in Fig. 10(a) the optimal setting of f (i.e., f ₀) to obtain the corresponding maximum per-node throughput μ ^* in Fig. 10(b), which shows that μ ^* drops towards zero quickly as the number of users n increases from 36 to 1,024. Actually, an optimal setting of f only applies to a small range of n, and it is a step function of n as shown in Fig. 10(a).

Fig. 10

The maximum per-node throughput and corresponding optimum f (i.e., f ₀) with the setting of $m=\lfloor \sqrt n \rfloor$ and 36 ≤ n ≤ 1,024. a The optimum setting of f. b The maximum per node throughput μ ^*

7 Conclusion

In this paper, we develop a method to calculate the meeting probabilities between two randomly selected nodes following random walk mobility model in MANETs, which can be used to characterize the network performance. By considering the wireless medium access contention among different pairs of hosts, we obtain the closed-form results of delay and capacity. We validate the correctness of our results through numerical results. In addition, we compare the network performance with that under i.i.d. mobility model. Our work provides useful theoretical insights on the performance of MANETs where nodes follow local mobility models. Our closed-form results can better capture the network performance.