Impact of Link Lifetime on QoS in Mobile Ad-Hoc Networks

Abstract

The provision of quality of service (QoS) in mobile ad hoc networks is a challenging task. Several factors such as node mobility, propagation environment, interference and access medium impact the link characteristics and may cause radio links to break frequently. Contributing to the understanding of the link properties is a key element to achieve efficiency and network performance in ad-hoc networks. In this paper, we present an analytical framework which determines the link lifetime and path lifetime by taking into consideration both node mobility and interference. This result is used in order to investigate the network connectivity properties by analyzing the link availability of a given node. Furthermore, to further understand the implication of link properties, analytical results are used to investigate network metrics that can be used in the ad-hoc routing design and the analysis of associated performance.

1 Introduction

Mobile Ad-hoc network (MANET) is a set of mobile nodes, which are dynamically communicating through wireless links without the need for any static infrastructure. Among the limiting factors that impact the network performance and the quality of service is the mobility of nodes. In fact, nodes in MANET are free to move randomly and can enter and leave the network dynamically. The random mobility makes the topology of MANET dynamic and unpredictable. In this case, link breakage can occur when nodes move out of range of each other. Aside from node mobility, interference is an inherent characteristic of mobile ad-hoc networks. It is a major impact factor on the network performance because of the broadcast nature of the wireless medium and random propagation conditions. Communication between nodes are achieved through a single channel protocol and therefore potentially interfere with each other. In fact, mobile nodes in ad-hoc networks do not have a separate interface for each operation of data transmission and all stations must switch the channel regulatory. These are achieved by defining time slots which are switched periodically.

Many issues related to the link behavior are largely explored in the literature. However, existing works on link properties are based only on node mobility and do not take into account interference. Several studies analyze the impact of node mobility on the network performance [1, 2]. Other simulation-based studies provide empirical distribution of link and multi-hop path lifetime [5, 10] by considering mobility models such as Random Waypoint and Random Walk [3].

The properties of wireless links can be determined by link availability [21], link lifetime and link residual time [9, 20]. In this context, authors of [25] provide an approximation of the distribution of the link lifetime due to linked nodes mobility. In this study, time is divided into equal length time steps $\varDelta$t and a distance transition probability matrix is used in order to model the distance after every discrete time step based on a smooth mobility model [24]. The main result is an approximation of the link lifetime due to linked nodes mobility by an exponential distribution with parameter $\frac{\bar{V}}{R}$, where $\bar{V}$ is the mean of speed and R the transmission range. Understanding radio interferences is also important for the design and analysis of wireless network performance. Aside from node mobility, radio channel is subject to interferences in which the signal received is impacted by transmission from other nodes. Several studies have been focused on the prediction of interference in ad-hoc networks with general mobility models [13, 22]. In this context, paper [6] investigates interference prediction using a general-order linear model for node mobility in order to give an estimation of the time-varying interference at a given time. Moreover, Authors of [23] model the interference field as a Poisson Point Process in order to derive the lower and upper bounds of the signal-to-interference ratio.

Other studies derived methods for evaluation outage probability given fading and shadowing [14] in order to add interference-awareness to the control function so that to enhance the overall network performance [11, 19]. In a recent work [18], we have showed that the link lifetime due to interference can be approximated by an exponential distribution with parameter $\lambda = \frac{\bar{V}}{R}.\frac{N}{\alpha }.\frac{\beta }{\beta + 1}$ where $\bar{V}$ is the average speed, R is the transmission range of the mobile node, $\beta$ is an SINR threshold corresponding to an acceptable BER, $\alpha$ is the path loss exponent and N is the maximum number of interfering nodes.

The goal in this paper is to provide understanding of the link lifetime characteristics and to study various aspects related to the QoS and the network connectivity. The problem of connectivity in mobile ad-hoc networks has been widely investigated through several analytical and simulation studies [7, 8]. The main contributions concern usually the mobility as the main factor which causes link breakage and its impact on the network connectivity [4, 5]. From a connectivity point-of-view, the impact of interference on the network connectivity needs further discussion.

Furthermore, providing guaranteed QoS in ad-hoc networks is a complex task to achieve. In fact, the link quality in mobile ad-hoc networks does not depend only on the bandwidth of that link, but also on many factors including the dynamic topology due to mobility and the unreliability of wireless medium which cause frequent link breakage. These limitations make the QoS provisioning difficult and we believe that understanding link properties, including link lifetime and link residual lifetime, is the key element to achieve efficiency and network performance in ad-hoc networks. Such understanding is helpful to gain insights through which the link properties can be used as link quality indicators for the network design and performance evaluation.

The rest of the paper is organized as follows. We present in Sect. 2 our approach used for modeling the lifetime of wireless links and multi-hop paths by taking into consideration interference and node mobility. In this section, the distribution of link lifetime due to interference is derived based on a transition probability matrix which models the link state after every discrete time step. Section 3, provides understanding of how link properties can be used as link quality metrics for the network design and performance evaluation. Finally, Sect. 4 concludes the paper.

Fig. 1.

Link breakage due to linked nodes mobility and interference

2 Link Lifetime Modeling in the Presence of Interference

2.1 Assumptions

The link lifetime is the period of time between the establishment of the link until its breakage due to a failure. In this subsection, we consider the interference as the only factor that causes link breakage.

We denote by $d_{u,v}$ the distance between the node-pair (u, v), where u is the sender and v the receiver. The corresponding relative distance after k time steps is denoted by $d_{u,v}^{(k)}$. And let ${SINR}_{u,v}^{(k)}$ be the Signal-to-Interference Noise-Ratio at the $k^{th}$ time steps (the duration of the time step is denoted by $\varDelta t$). Figure 1, shows that the link failure occurs in the presence of interference when the relative distance between the interferer and the receiver nodes is bellow the transmission range.

Definition 1

The link lifetime due to interference, denoted by $T_{link, I}$, is the period of time between the establishment of the link until its breakage due to interference coming from other nodes. In this case, the Signal-to-Interference Noise-Ratio (SINR) is less than an SINR threshold $\beta$ corresponding to an acceptable BER.

$$\begin{aligned} T_{link, I} \triangleq \sup _{k}\{k.\varDelta t \mid SINR _{u,v}^{(k)} \ge \beta \} \end{aligned}$$

(1)

Consider a mobile ad-hoc network consisting of N nodes which choose a common power level $P_e$ for all their transmissions. We focus on a particular link, called the tagged link whose receiver node is considered as the reference. Let L represents the subset of interferer nodes. The reference physical model that determines whether a transmission is successfully received or not is the Signal-to-Interference Noise-Ratio (SINR). In our analysis, we adopt the interference model introduced in [12].

$$\begin{aligned} SINR_{u,v}^{(k)}(m)= \frac{P_{e}.\gamma _{u,v}^{(k)}}{N_{T} + \sum \limits _{\begin{array}{c} i\in L, i \ne u\\ |L|=m \end{array}} P_{e}.\gamma _{i,v}^{(k)}} \end{aligned}$$

(2)

where ${SINR}_{u,v}^{(k)}(m)$ is the Signal-to-Interference Noise-Ratio after k time steps and in presence of m interferer nodes, $P_{e}$ is the transmit power of nodes, $N_{T}$ is the noise power supposed constant and $\gamma _{i,j}^{(k)}$ is the channel gain from node i to node j after k time steps, such that the received power at node j is $P_{e}.\gamma _{i,j}$. In this paper, the channel gain between a node pair (i, j) is given by:

$$\begin{aligned} \gamma _{i,j}^{(k)} = \frac{P_{e}.E(R^{2}).E(\zeta )}{(d_{i,j}^{(k)})^{\alpha }} \end{aligned}$$

(3)

where, $E(R^{2})$ is the expectation value of the Rayleigh fading, $E(\zeta )$ is the expectation value of the log-normal shadowing and $\alpha$ is the path loss exponent, which ranges from 2 to 5 depending on the environment. At each time step, a transmission from u to the intended node v is considered successful in the presence of simultaneous transmission of interferer nodes if:

$$\begin{aligned} \frac{P_{e}.E(R^{2}).E(\zeta ).d_{u,v}^{-\alpha }}{N_{T} + \sum \limits _{i \ne u} P_{e}.E(R^{2}).E(\zeta ).d_{i,v}^{-\alpha }} \ge \beta \end{aligned}$$

(4)

where $\beta$ is the minimum signal-to-interference ratio requirement for successful transmission. By defining $J_e = P_{e}.E(R^{2}).E(\zeta )$, from Eq. 4, the availability of communication link can be expressed as:

$$\begin{aligned} \frac{d_{u,v}^{-\alpha }}{\beta } \ge \frac{N_T}{J_e} + \sum \limits _{i \ne u} d_{i,v}^{-\alpha } \end{aligned}$$

(5)

Definition 2

Let $f_{u,v}(m)$ be the probability that the transmission between the node pair (u, v) in the presence of m interfering nodes is successful:

$$\begin{aligned} f_{u,v}(m)&\triangleq \Pr [SINR_{u,v}(m) \ge \beta \mid d_{u,v} \le R] \nonumber \\&= \Pr [\frac{d_{u,v}^{-\alpha }}{\beta } \ge \frac{N_T}{J_e}+\sum \limits _{\begin{array}{c} i\in L, i \ne u\\ |L|=m \end{array}} d_{i,v}^{-\alpha } \mid d_{u,v} \le R] \end{aligned}$$

(6)

2.2 Distribution of Link Lifetime

A transmission between a node pair is successfully received by the intended node in the presence of interference, if the SINR is greater than its minimum requirement. The loss of connectivity after k time steps means that the SINR has become greater than its threshold $\beta$.

We denote by X the random process which undergoes transitions from a state to another in discrete time. X is a stochastic process which describes the link availability in presence of a given number of interfering nodes. This behavior is captured by comparing the SINR with its minimum requirement. Furthermore, link availability can be interpreted as sequential state transitions, in which the SINR is greater than $\beta$ in presence of a number of interfering nodes which vary from a state to another until the link fails (absorbing state).

We denote by $P=(p_{(i,j)})_{i,j}$ the probability transition matrix which model, at each time step, the quality of the communication link in the existence or the absence of interfering nodes. $p_{(i,j)}$ is the transition probability from a state $S_{i}$ to a state $S_{j}$ after one time step. The link between the node pair (u, v) fails due to interference when the system reaches the absorbing state $S_{N+1}$. In other words, the link duration expire after k time steps if the event $({SINR}_{u,v}(l) < \beta ; \forall l \in [0,N])$ first occurs. The transition probability $p_{(i,j)}$ is defined as follow:

$$\begin{aligned} p_{(i,j)} = \Pr [X \in S_{j} \mid X \in S_{i}] \end{aligned}$$

(7)

We denote by $\pi ^{(0)}$, the probability of the initial state and $\pi ^{(0)} = (\pi _{0}^{(0)},\ldots ,\pi _{N+1}^{(0)})$. Furthermore, we denote, by $\pi _{i}^{(k)}$ the probability that the system lies in the state $S_{i}$ after k time steps and $\pi ^{(k)} = (\pi _{0}^{(k)},\ldots ,\pi _{N+1}^{(k)})$ the row vector whose $k^{th}$ element is $\pi _{i}^{(k)}$.

The probability that the link fails due to interference after k time steps is $(\pi ^{(0)}.P^{k})_{N+1}$. Consequently, the complementary density function of the link lifetime due to interference is:

$$\begin{aligned} \Pr [T_{link, I} \le k] = [\pi ^{(0)}.P^{k}]_{N+1} = \pi _{N+1}^{(k)} \end{aligned}$$

(8)

The corresponding PDF is presented as follow:

$$\begin{aligned} f_{T_{link, I}}(k)&= \Pr [T_{link, I} \le k] - \Pr [T_{link, I} \le k-1] \nonumber \\&= (\pi ^{(0)}.P^{k})_{N+1} - (\pi ^{(0)}.P^{k-1})_{N+1} \end{aligned}$$

(9)

Proposition 2

[18]. The link lifetime due to only interference, denoted by $T_{link, I}$, can be approximated by an exponential distribution with parameter $\lambda = \frac{\bar{V}}{R}.\frac{N}{\alpha }.\frac{\beta }{\beta + 1}$:

$$\begin{aligned} f_{T_{link, I}}(t) \approx \frac{\bar{V}}{R}.\frac{N}{\alpha }.\frac{\beta }{\beta + 1}.exp(-\frac{\bar{V}}{R}.\frac{N}{\alpha }.\frac{\beta }{\beta + 1}.t) \end{aligned}$$

(10)

Proposition 3

[18]. The overall link lifetime due to both mobility and interference, denoted by $T_{link}$, can be approximated by a Rayleigh distribution with parameter $\rho = \frac{R}{\bar{V}}.\sqrt{\frac{\alpha .(\beta + 1)}{2.\beta .N}}$:

$$\begin{aligned} f_{T_{link}}(t) \approx \frac{t}{\rho ^{2}}.exp(-\frac{t^{2}}{2.\rho ^{2}}) \end{aligned}$$

(11)

This result is in harmony with previous simulation based-studies which concern the examination of the performance of routing protocols in multi-hop wireless networks and the identification of stable link based on the analysis of link durations under different mobility scenarios. In this context, authors of [9, 15] show by simulation that there is a peak in the distribution of the link lifetime. Results of these simulations are obtained by considering several parameters including mobility and radio propagation. Moreover, paper [16] investigates how well an analytical model fits the link lifetime measurements obtained from simulation. They showed, by observation, that the Weibull distribution is a best approximation of the link lifetime. This approximation is argued by the fact that Weibull is among the distributions which are widely used in reliability theory to model the lifetime of objects.

3 QoS Provisioning in Mobile Ad-Hoc Networks

3.1 Bandwidth Reservation

Wired networks provide the possibility to make bandwidth reservation in order to guarantee the quality of service required by applications. The reservation of a certain amount of bandwidth requires that the node has the possibility to control the bandwidth. In this case, the source is responsible for determining the required bandwidth based on the residual capacity of links defining the path to the destination. MLPS is an example of networks which make bandwidth reservation. It is considered as a suitable architecture to support traffic engineering and which provide guaranteed bandwidth for flows. In this area, there has been much work which develop models to determine the amount of bandwidth required to transmit the data. Our previous work [17] is an example of such proposals which formulates several nonlinear objective functions according to the sensitivity of the application and which aims to determine bandwidth allocation as well as traffic flow routing through the network based on the optimization of the network link utilization. Approaches for bandwidth reservation used in wired networks are not directly applicable for wireless networks especially for Manets because many wired QoS characteristics do not hold in wireless networks. In fact, the available bandwidth of a given link do not depend only on the activity of this link, but also on many factors including the dynamic topology that changes over time, less battery power of the nodes, less bandwidth and transmission quality enhancement. These limitations make the reservation of bandwidth difficult in ad hoc networks.

Various factors must be taken into account in order to provide quality-of service (QoS) guaranteed in ad hoc networks. These factors include in particular the node mobility and interference which impact directly the characteristics of the link. In this case, it is important to understand the link properties, including link lifetime and link residual lifetime, in order to achieve efficiency and network performance in mobile ad hoc networks.

In this section, we intend to provide understanding of link properties by considering linked nodes mobility and interference as factors that cause link breakage and which can be used as link quality indicators for the network design and performance evaluation.

3.2 Link Lifetime and Route Selection

Achieving efficiency and network performance requires a deep comprehension of link properties. Factors such as node mobility and interference generally come into play in the determination of the link availability. The link lifetime is the period of time between the establishment of the link until its breakage due to a failure. The link lifetime can be classified into two main classes. Link duration in which the failure is caused by movement of the linked nodes and link lifetime in which the failure is due to interference. Results of [25] show that the link lifetime due to mobility of the linked nodes, denoted by $T_{link, Mvt}$, follows an exponential distribution with parameter $\varphi = \frac{\bar{V}}{R}$, where $\bar{V}$ is the mean speed and R the transmission range. Note that this study considers the mobility of the linked nodes as the only factor which causes link failures. In this regards, we had shown that the link lifetime due to interference follows an exponential distribution with parameter $\lambda = \frac{\bar{V}}{R}.\frac{N}{\alpha }.\frac{\beta }{\beta + 1}$ and the overall link lifetime due both mobility and interference can be approximated by a Rayleigh distribution with parameter $\rho = \frac{R}{\bar{V}}.\sqrt{\frac{\alpha .(\beta + 1)}{2.\beta .N}}$, where $\beta$ is the SINR threshold, N is the maximum number of nodes which can interfere with the receiver node and $\alpha$ the path loss exponent. The mean value of $T_{link, I}$, $T_{link, Mvt}$ and $T_{link}$ are given by:

$$\begin{aligned} E[T_{link, I}] = \frac{1}{\lambda } = \frac{R.\alpha .(\beta + 1)}{\bar{V}.\beta .N} \end{aligned}$$

(12)

$$\begin{aligned} E[T_{link, Mvt}] = \frac{1}{\varphi } = \frac{R}{\bar{V}} \end{aligned}$$

(13)

$$\begin{aligned} E[T_{link}] = \rho \sqrt{\frac{\pi }{2}} = \frac{R}{\bar{V}}.\sqrt{\frac{\alpha .(\beta + 1)}{2.\beta .N}}\sqrt{\frac{\pi }{2}} \end{aligned}$$

(14)

Fig. 2.

Average link lifetime in function of speed

In order to investigate the impact of node mobility and interference on the link lifetime, we have plotted $T_{link, I}$, $T_{link, Mvt}$ and $T_{link}$ by considering low mobility. Also, we have assumed that $\beta = 10$ and $\alpha = 2$. Results of Fig. 2 are obtained by considering a transmission range of 250 m and varying the average speed from $5\,\text {m}/\text {s}$ to $25\,\text {m}/\text {s}$. We find that link breakage can be caused by node mobility when the number of interferer node is small. In this case, the link lifetime is simply the time a sender or receiver node take to move across the radius of the transmission zone of each other at their average speed $\bar{V}$. However, in the case of a high node density network, the link breakage can occur first due to interference and this becomes more important when the number of interferer nodes increases.

Moreover, Fig. 3 shows the effect of the transmission range on the average link lifetime due to interference and linked nodes mobility, and by considering $\bar{V}=5\,\text {m}/\text {s}$. The main result is that when the transmission range is small, the impact of interference and nodes mobility are nearly the same but the probability of link breakage due to interference remains high at high node density network. We can conclude that the link lifetime is an important link property which can be considered as a link quality to use in the design of routing protocols in order to improve the network performance.

Routing Protocols are used to discover and maintain routes between the source and destination nodes. These protocols are designed to provide a multi-hop wireless link between the sender and the receiver nodes. Generally, the sender node initiates the route discovery by broadcasting a route request packet, RREQ, through the network. Several copies of RREQ packet can be received by the receiver node coming through several routes. The receiver sends a route reply packet, RREP, back to the source node following the same path. The source node chooses the route in which the corresponding RREP packet was received first (Figs. 2 and 3).

Fig. 3.

Average link lifetime in function of transmission range

The route selection is generally based on the number of hops or path delay as metrics and do not take into account the path lifetime which is a deterministic element to avoid failures. In fact, the path lifetime, denoted by $T_{Path}$, is directly associated with the failures of links defining that path and which are caused by interferences or linked nodes mobility. If M is the number of links forming a path, then

$$\begin{aligned} T_{path} = min\{T^{i}_{link} \mid 1 \le i \le M\} \end{aligned}$$

(15)

where

$$\begin{aligned} T^{i}_{link} = \min \{T^{i}_{link, Mvt} ; T^{i}_{link, I}\} \end{aligned}$$

(16)

Note that $T^{i}_{link, Mvt}$ and $T^{i}_{link, I}$ flow an exponential distribution with parameters, respectively, $\varphi = \frac{\bar{V}}{R}$ and $\lambda _{i} = \frac{\bar{V}.\beta .N_{i}}{R.\alpha .(\beta + 1)}$ and $T^{i}_{link}$ is Rayleigh distributed with parameter $\rho _i = \frac{R}{\bar{V}}\sqrt{\frac{\alpha .(\beta + 1)}{2\beta N_{i}}}$. $N_{i}$ is the number of interfere nodes detected by the intermediate node i. The detection of possible interfere nodes can be performed by broadcasting, periodically, a Hello message through the network. The period of broadcasting this type of message should be defined as small enough in order to ensure efficiency through the dynamics topology of mobile ad-hoc networks.

3.3 Impact of Residual Link Lifetime

The residual link lifetime given in Eq. 17 describes the time interval between a given instant a, after the establishment of the link, until its breakage due to interference or linked nodes mobility. In fact, communication between a node pair can start at an arbitrary moment after connection was already established. In this case, the residual link lifetime can be greatly useful in searching, by the sender node, for a long-living links defining the path through which the data will be transmitted.

$$\begin{aligned} \Pr [T_{link, Res, a} \le t]&= \frac{\Pr [T_{link} \le t+a]}{1-\Pr [T_{link, Mvt} \le a]} \nonumber \\&= \frac{1 - exp(-\frac{(t+a)^{2}}{2.\rho ^{2}})}{exp(-\frac{a^{2}}{2.\rho ^{2}})} \end{aligned}$$

(17)

Fig. 4.

Residual link lifetime

We plot in Fig. 4 the overall residual link lifetime CDF in which the failures can be caused by mobility and interference. Results show that a link has less change to be maintained if the period of time, between its establishment and the beginning of the communication between the linked nodes, is high. In fact, links and paths may exist before a sender establishes a path to the destination for end-to-end communication. In this case, a long living route is the one whose constituent links are recently established.

The use of multi-path routing schemes improve the performance in mobile ad-hoc networks as compared to single path routing protocols. In the context of MANETs, a lot of multi-path routing protocols have been proposed which define multiple disjoint paths, improve resilience to network failures and provide higher aggregate bandwidth especially in networks with high node density. The route selection, in the case of multi-path routing, aims to select a set of paths according to a determined metric such as hop count, path reliability, path disjoints, bandwidth availability and degree of route coupling. The traffic is forwarded using one path which has the best metric and the other paths are kept as backup. The source can send data using an alternate route when the primary route fails. In this context, the selection of an alternate route when the primary route fails should be based on a metric such as residual lifetime instead of an arbitrary choice. In fact, we can talk about the residual path lifetime only after completion of route discovery. A M-hop path may exist before a sender node initiates the route discovery operation. Consequently, the predictive path residual lifetime is an important measure when a sender node need a path to immediately send data packets or caches it as an alternative path to use it if the primary path fails.

4 Conclusion

In this paper, we have given a short summary of the link lifetime model developed in our previous work. This model provides an approximation of the link lifetime PDF by considering interference and node mobility as factors which cause link breakage. We have investigated challenges related to the provision of QoS in mobile ad hoc networks. Most of these challenges are due to the physical characteristics and topological nature of Manets. We have showed that it is important to understand the link properties, including link lifetime and link residual lifetime, and their implication as link quality metrics in order to achieve efficiency and network performance. Several insights are gained which can be helpful for routing optimization, network efficiency and the evaluation of the connectivity of paths, their lengths and their stability.