A joint approach to routing metrics and application-aware rate adaptation in multi-radio wireless mesh networks

Abstract

In this paper, we address a joint problem of routing and application-aware rate adaptation for multi-radio Wireless Mesh Networks (WMNs). WMNs are emerging as wireless backhaul technology to connect wired and wireless networks to the internet in a cost-effective way. These networks use multi-radio capabilities of mesh routers to achieve high performance. However supporting the quality of service (QoS) of real-time multimedia applications is still an important research issue as there is need for the cross-layer optimization strategies involving application, routing, MAC and physical layers. Towards this, we analytically derive our routing metric by using 802.11 Distributed Coordination Function (DCF) basis access mechanism. Using this model, we design a novel cross-layer routing metric called Interference and Contention Aware (ICA) metric by considering delay, channel utilization, inter-flow interference and intra-flow interference to find the optimal path. We extend the work by adapting the traffic rate at the application layer of a source node by using the statistics provided by the routing metric. We implement this joint approach using Optimized Link State Routing (OLSR) in NS2. The results reveal that ICA routing metric performs better in terms of throughput and delay compared to Metric for Channel Diversity (MIND), Contention-Aware Transmission Time (CATT) and Interference Aware Routing (iAWARE). Further, cross-layer approach of routing and rate adaptation helps the applications to adapt the transmission rate based on the congestion at the network layer.

Keywords

Wireless mesh networks multi-radio routing metric cross layer design rate adaptation

1. Introduction

Wireless Mesh Networks (WMNs) [3] are an emerging technology and are making significant progress in the field of wireless networks in recent years. These networks are becoming more popular as backbone networks to provide ubiquitous internet access and broadband wireless coverage to large areas with minimal upfront-investments and infrastructure. WMNs are composed of gateways, mesh routers and mesh clients. Mesh routers generally have the minimal mobility and are used to form backhaul network. These routers acts as access point for mesh clients or forward packets from other routers in the backbone network. The gateways allow backbone WMN to connect to other types of networks like the internet. Recently, many real-time traffic applications like Voice over IP, online gaming and video streaming are becoming popular in WMNs. These applications depend on adequate QoS support with strict delay requirements. Thus providing QoS for these applications has become an important research issue [6,18,21].

With the reduction in hardware cost of 802.11 standards, mesh routers in backhaul networks are equipped with one or more radios that enhance the network capacity and improve QoS. However, it is quite challenging to effectively utilize these multiple radios to minimize the delay and interference thereby improving network throughput. The multi-hop mesh networks are realized using IEEE 802.11 MAC with Distributed Coordination Function (DCF) for medium access control [14]. Every mesh router in these networks forward heavy traffic from mesh client to the internet gateways. As the traffic increases, contention among the nodes increases as nodes spends considerable amount of time in binary exponential backoff process. The contention depends on the collision probability and channel holding time. This increases the effective packet delay at the network layer. Thus there is need to effectively measure the effective packet delay for each link considering the service time of MAC protocol. The routing protocols which calculates the optimal path considering effective packet delay and interference normally finds the least congested path and thus balances the load. Thus, the design of routing metrics considering delay and interference is an important issue in WMNs.

In addition to optimal routing, providing QoS for multimedia applications at application layer is challenging issue due to varying characteristics of wireless channel and dynamic requirements of these applications. Configuring the parameters of applications at design time may lead to poor performance and inefficient resource utilization. Thus there is need for joint cross layer approach where the dynamic rate allocation is performed based on the behaviors of different layers of the protocol stack. Towards this, many cross-layer design mechanisms are proposed in literature [13,15,29]. In these works, based on the lower layer statistics rate adaptation is carried out at the application layer. However none of these studies have addressed the joint problem of routing metrics and application-aware rate adaptation for multi-radio networks. This is an important issue as the interference at the nodes is an important parameter for improving QoS in multi-radio mesh networks.

To address the above issues, we propose a joint approach of routing and application-aware rate adaptation. The contributions of this paper are three fold.

We analytically derive a delay component of our routing metric by considering MAC service time of IEEE 802.11 DCF model.

Design and implement the new routing metric by estimating the link quality parameters using the above model by accessing PHY, MAC and Network layers

Carry out the rate adaptation at the application layer using the statistics provided by the routing metric

The rest of the paper is organized as follows. Section 2 gives the related work with regard to the routing metrics and joint approaches to routing and rate adaptation. Section 3 discusses about the 802.11 DCF model, proposed routing metric based on this model and the rate adaptation mechanism. Section 4 presents the simulation model and Section 5 presents results and discussion. Finally, the conclusion and future work is discussed in Section 6.

2. Related work

Since we propose joint cross layer approach which combines both routing metrics and rate adaptation, we discuss the work reported in the literature about these two topics separately.

2.1. Routing metrics

Several routing metrics have been proposed for WMNs. Here we mention few of them related to our work. The most popular routing metric which is deployed in the WMN test beds is expected transmission count [9]. ETX is the expected total number of packet transmissions (including retransmissions) required to send the packet to the destination through a wireless link successfully. It is computed as the product of forward delivery ratio $d_{f}$ and reverse delivery ratio $d_{r}$ for a link. The $d_{f}$ is the measured probability that the packet is successfully received at destination node and $d_{r}$ is the probability that acknowledgment of the packet is successfully received. The authors demonstrate through testbed results that ETX computes higher throughput routes than the hop count based routing. The problem with ETX is that it does not consider the differences in multiple transmission rates which are very important in multi-rate mesh networks. Furthermore, it does not explicitly calculate the inter-flow interference experienced by the links. To address the limitations of ETX, authors in [10] proposed Expected Transmission Time (ETT) metric which considers the transmission rate of each individual link in multi-rate networks. ETT estimates the link quality using packet losses, packet size and available transmission rate of each individual link. However, ETT inherits the drawbacks of ETX as it does not consider load and interference.

Another routing metric called Channel utilization and Contention Window (C2WB) is proposed in [24]. The metric is derived using 802.11 MAC delay model but lacks many details. The metric estimates the link service time using three parameters namely transmission time, bakeoff time and defer time. Using these parameters, authors estimate the link quality as a product of channel utilization and average contention window. The metric considers logical interference implicitly using channel contention; it increases the network capacity and balances the load. However, it does not consider interference explicitly with respect to each node and uses static value for available bandwidth in transmission time estimation. Another routing metric QUIT which estimates the link quality parameters namely link quality, utilization, interference and traffic load us proposed in [4]. The metric is derived using non-utilized outage capacity analysis but metric is basically designed for single-radio network.

All the above metrics are proposed for single-radio wireless networks. With the demand for high capacity multi-radio wireless networks, designing the routing metrics for these networks has become an important research issue. Towards this, many routing metrics are proposed. The most popular and the first routing metric proposed for multi-radio networks is the Weighted Cumulative Expected Transmission Time (WCETT) [10]. The metric explicitly estimates the intra-flow interference among links that uses the same channel. It captures the intra-flow interference of a route by giving low weight to the paths that have more diversified channel assignments on their links. However, WCETT does not incorporate the inter-flow interference and load. The Metric of Interference and Channel-switching (MIC) [32] metric addresses the drawback of The WCETT. It scales up ETT by capturing inter-flow interference using protocol interference model. It also estimates the intra-flow interference using the virtual node concept. It computes inter-flow interference by measuring the number of neighboring links that can interfere with each other during the transmission of packets. However, it does not consider interference in dynamic way as all the neighboring nodes may not be involved in the transmission. This may overestimate the link cost.

Another routing metric which estimates the inter-flow interference in realistic way using physical interference model was proposed in [30]. The metric Interference Aware Routing (iAWARE) estimates both inter-flow and intra-flow interference. The metric gives more weightage to ETT compared to inter-flow interference on the wireless link. However, it does not consider the effect of contention delay in estimation of ETT. The Contention-Aware Transmission Time (CATT) metric which estimates the contention over wireless channel and rate diversity is proposed in [11]. It captures the interfering links between 1 and 2 hop neighbors using ETT. Hence, the CATT metric avoids the congested paths and provides better performance. CATT metric also has disadvantage as it assumes that all the neighboring nodes are participating in the interference (whether or not they are involved in transmitting the data), which may overestimate the link quality.

Another routing metric which used passive monitoring mechanism is Metric for Interference and Channel Diversity (MIND) [7]. It considers the inter-flow interference in a more realistic way using physical interference model similar to iAWARE and calculates the intra-flow interference based on the local information. The traffic load is estimated based on channel busy time. This metric also has some disadvantages since the metric does not perform well in the lighter traffic networks. In [22] authors propose new routing metric called Cross-Layer Interference, Load and Delay aware metric (CL-ILD). The metric computes the optimal path by measuring inter-flow interference at physical layer, load at MAC layer, and delay by computing Expected Transmission Time at network layer. It improves the C2WB metric by estimating inter-flow interference using protocol interference model. But the interference measurement is static and metric lacks analytical model. All the above metrics except CATT, C2WB, QUIT are based on computing routes based on measurement based approach and lack analytical model. The CATT, C2WB and QUIT derive the routing metrics using the analytical model but lack in-depth analysis in choosing the link quality parameters in the metric design.

2.2. Joint approaches

The cross-layer design involving application layer has been exploited in a number of research efforts. One of the initial work on application-layer video rate adaptation using cross-layer optimization is reported in [15]. The information is exchanged among the application, MAC and physical layers. The application layer dynamically adapts the source rate based on the frame losses at the MAC layer. In [13], authors develop a application-networks interaction framework to dynamically adapt the network resources based on the QoE requirement of Youtube user. The authors select the least congested gateway to enable smooth video playback. Authors in [29] propose a generalized framework for cross-layer optimization of video streaming in mult-hop wireless networks which can exploit interaction between application layer and any other lower layers. In all these works, there is no close interaction between application and network layer routing metrics. As the routing metrics in multi-radio networks computes link quality parameters as part of routing process at regular intervals, these parameters can be used to adapt the rate at the application layer. As a strong relation is needed between the application-layer rate allocation and routing metrics, this cross-layer optimization needs to be explored.

The joint approaches to routing, rate adaptation, load balancing and channel assignment for multi-hop wireless networks are explored in the literature. With the multi-radio capabilities, these joint approaches are becoming more popular as lot of complexity is involved with increased capacity. The only three approaches which address the joint problem of routing metrics and MAC layer rate adaptation are reported in [16,17,26]. In [17], authors propose Multi-rate Anypath routing algorithm where they consider link rate in finding the route. Authors extend the ETT metric to compute the link costs for each available PHY rate. In [26], authors propose the joint approach to routing metrics and rate adaptation. The routing parameters statistics are used to adapt the MAC layer transmission rate of a node. Authors in [16] propose a similar joint approach. We take a different approach to joint problem by adapting the Constant Bit Rate (CBR) traffic at the application layer using routing metric parameters as the indicator of congestion. This concept can be extended to video rate adaptation to improve the Quality of Experience (QoE) for the end-user as video is transferred over UDP.

3. Proposed work

In this section we discuss the 802.11 DCF delay model which is used to derive our routing metric. Later, we discuss the design and implementation of our routing metric in OLSR routing protocol using cross layer mechanism.

3.1. Delay model for 802.11 DCF mechanism

We use the model presented in [31] to analytically derive our routing metric. The model is modified version of Bianchi model [5] considering the frame retries limits. We use 802.11 MAC Distributed Coordination Function (DCF) which has two mechanisms for frame transmission namely basic access mechanism and using RTS/CTS. We use the basis access method with two-way handshaking mechanism using the DATA and ACK packets. In this mechanism, access to wireless channel is controlled using two Inter-frame Space (IFS) intervals namely short IFS (SIFS), and DCF-IFS (DIFS). This mechanism is designed to avoid collisions using exponential backoff algorithm. In DCF basic access mechanism, if the channel is busy, a backoff time is chosen randomly in the interval [0, CW], where CW is a contention window. This timer is decreased by one when the station senses the channel as idle for a period known as distributed interframe spacing time (DIFS). The timer stops when the channel is busy and resumes when channel is idle again. CW is an integer value determined by physical layer characteristics such as CWmin and CWmax. After each unsuccessful transmission, CW is doubled up to the maximum value CWmax. When the backoff timer reaches zero, source transmits the data packet when channel is idle. The receiver transmits the ACK after waiting for SIFS. When a data packet is transmitted, all other stations hearing this transmission adjusts their Net Allocation Vector (NAV). We consider the saturated scenario for all our derivations as all of the nodes in backhaul mesh network will be sending frames.

Average packet delay: The average packet delay is defined as the time when the packet becomes the head of the queue and when a positive acknowledgment is received. The average packet delay experienced by a transmitted frame for a station can be estimated as follows. Let $P D$ be the packet delay, $N B$ be the number of backoff stages each with a length of $L B$ , then the average delay experienced by a transmitted frame for a station is given by $\begin{matrix} (1) & E [P D] = E [N B] \cdot E [L B] \end{matrix}$ where $E [N B]$ is the average number of backoff stages and $E [L B]$ is the average length of each backoff stage. These two parameters are derived as follows.

Average number of backoff stages: The average number of backoff stages $E [N B]$ is calculated using average contention window. In exponential backoff process of DCF, the contention window is initially set to ${CW}_{\min}$ . When the collision occurs, the station reduces its transmission rate by doubling the size of its CW. Larger contention window reduces the collisions but slows down the transmission of packets. Thus, $\begin{matrix} \{\begin{matrix} {CW}_{i} = 2^{i} \cdot {CW}_{\min} & if i < m^{'} \\ {CW}_{i} = 2^{m^{'}} \cdot {CW}_{\min} & if i > m^{'} \end{matrix} \end{matrix}$ where $CW = {CW}_{\min} + 1$ , $2^{m^{'}} CW = {CW}_{\max} + 1$ , $m^{'}$ is backoff stage and m is maximum backoff stage (permitted number of retransmissions). Assuming that p is a collision probability, a packet is transmitted with probability of $(1 - p)$ . The average contention window for this packet is $\frac{{CW}_{\min} + 1}{2}$ . If this transmission fails, the packet will be transmitted successfully with the probability of $p (1 - p)$ . The average contention window for this packet is $(2 \cdot {CW}_{\min} + 1) / 2$ . This is continued till the last (mth) permitted retransmissions. The contention window will be increased till ${CW}_{\max}$ and remains constant thereafter. Thus, the average number of backoff stages can be computed as follows. $\begin{array}{l} E [N B] = & α (\frac{{CW}_{\min} + 1}{2}) + α p (\frac{2 {CW}_{\min} + 1}{2}) + \dots \\ + α p^{m^{'}} (\frac{2^{m^{'}} {CW}_{\min} + 1}{2}) \\ + α p^{m^{'} + 1} (\frac{2^{m^{'} + 1} {CW}_{\min} + 1}{2}) \\ (2) & + α p^{m - 1} (\frac{2^{m} {CW}_{\min} + 1}{2}) \end{array}$ where $α = \frac{1 - p}{1 - p^{m}}$ , m is the backoff stage, $(1 - p^{m})$ is the normalization factor which ensures that probability of each backoff stage follows a valid probability distribution. After some algebraic manipulation, we obtain $\begin{array}{l} E [N B] = & \frac{1}{1 - p^{m}} (\frac{{CW}_{\min} (1 - p) (1 - {(2 p)}^{m^{'}})}{2 (1 - 2 p)} + \frac{1 - p^{m^{'}}}{2}) \\ (3) & + (\frac{(2^{m^{'}} {CW}_{\min} - 1) (p^{m^{'}} - p^{m})}{2}) . \end{array}$

Generally, maximum backoff stage is $m = 5$ or 7 for data packets for basic access mechanism. Assuming finite retransmissions that is $m ⩽ m^{'}$ , we obtain the following (by substituting $m = m^{'}$ ) $\begin{array}{l} (4) & E [N B] = \frac{1}{1 - p^{m^{'}}} (\frac{{CW}_{\min} (1 - p) (1 - {(2 p)}^{m^{'}})}{2 (1 - 2 p)} + \frac{1 - p^{m^{'}}}{2}) \\ (5) & E [N B] = (\frac{(1 - p) (1 - {(2 p)}^{m^{'}})}{(1 - p^{m^{'}}) (1 - 2 p)} {CW}_{\min} + \frac{1}{2}) . \end{array}$

Average length of backoff stage: This is the average time station spends in each backoff stage before decrementing its backoff counter. This time depends on the channel state at new backoff stage as well as previous backoff stage. Generally, the channel at each backoff stage can be in three states namely idle, successful and collision. Thus, the length of each backoff stage is given by $\begin{matrix} (6) & E [L B] = (1 - P_{tr}) \cdot T_{idle} + P_{tr} \cdot P_{s} \cdot T_{succ} + (1 - P_{s}) \cdot P_{tr} \cdot T_{coll} \end{matrix}$ where $P_{tr}$ is the probability that at least one transmission occurs in a given slot time. $P_{s}$ is the probability of successful transmission. It is the probability that a station is transmitting and the remaining $n - 1$ stations remains silent with condition that at least one station must transmit. These two probabilities are given as follows. $\begin{array}{l} (7) & P_{tr} = 1 - {(1 - τ)}^{n} \\ (8) & P_{s} = \frac{n τ {(1 - τ)}^{n - 1}}{1 - {(1 - τ)}^{n}} \end{array}$ where τ is the probability that station attempts to transmit in an arbitrary slot i.e. $1 / E [N_{B}]$ , $T_{succ}$ is the average time of a successful transmission when medium is sensed busy, $T_{coll}$ is the average time of collision when the medium is sensed busy after a collision and $T_{idle}$ is the duration of an idle slot time. The values for $T_{succ}$ and $T_{coll}$ are given as follows. $\begin{matrix} (9) & \{\begin{matrix} T_{succ} = DIFS + H + L + SIFS + ACK + σ, \\ T_{coll} = H + L + DIFS + σ, \end{matrix} \end{matrix}$ where H, L and ACK are the transmission times needed to send packet header (MAC, PHY), the payload and the acknowledgment respectively. σ is the propagation delay. The payload length of transmitted and collided frame is same. All the parameters except L and ACK are constant for a given 802.11 specification. Thus the above equation can be simplified as $\begin{matrix} (10) & E [L B] = P_{idle} \cdot T_{idle} + P_{succ} \cdot T_{succ} + P_{coll} \cdot T_{coll} \end{matrix}$ where $P_{idle}$ is the probability of station being idle, $P_{succ}$ is the probability of successful transmission and $P_{coll}$ is the probability of collision. When a packet is transmitted, the successful transmission occurs when ACK is received. If the ACK is not received the packet transmission results in the collision. In both the cases, channel is busy. Thus the length of each backoff stage depends on the idle and busy time as follows. $\begin{matrix} (11) & E [L B] = P_{idle} \cdot T_{idle} + (P_{succ} + P_{coll}) \cdot T_{busy} \end{matrix}$ where $T_{busy}$ is the sum of time spent in successful transmission and collided transmission when the channel is busy. The average length of backoff stage can be found by estimating the length of each backoff stage over certain time interval.

From the above analysis, we conclude that the link quality depends on the following parameters.

Average Number of Backoff Stages: The average number of backoff stages depends on retransmission attempts, initial contention window and collision probability p. From this, the average backoff time can be computed.

The Channel Busy Time: The average backoff stage depends on average idle and busy transmission periods i.e. channel utilization as shown in equation (11). This parameter estimates time required to transmit a frame.

Number of interfering nodes: As shown in equation (8), as the number as the number of station increases, the conditional collision probability increases. Hence the delay increases. The number of stations here indicates the total number of nodes in the collision domain. Thus in routing process, the number of interfering stations for a given node to find the optimal path is the one important factor to minimize the delay and improve the throughput.

3.2. Interference and contention aware (ICA) routing metric

We propose a new routing metric called ICA based on the proposed analytical model. Our routing metric assigns weights to individual links by estimating link delay, inter-flow interference and intra-flow interference. ICA for path p is defined as follows: $\begin{array}{l} ICA (p) = & α \sum_{link i \in p}^{n} {Delay}_{i} \cdot (1 - {IR}_{i}) \\ (12) & + (1 - α) \sum_{link j \in p}^{m} {ICD}_{j} \end{array}$ where n is the number of links and m is the number of nodes of path p. ${Delay}_{i}$ is the delay on link i, ${IR}_{i}$ is interference ratio which estimates the inter-flow interference on link i and ${ICD}_{j}$ is the Intra-path Channel Diversity (ICD) for link j which computes the intra-flow interference. α gives the weight to the interfering delay component and channel diversity. The optimal path is found using summation the link qualities on path p. After extensive experiments, we choose α as 0.6.

Delay estimation:

Link delay is estimated using average contention delay and channel busy time using the equation (1). These two estimations are described in detail as follows.

Average contention delay (CD): Every node in the network contends for the channel before every successful transmission. Average contention window can be calculated in terms of Packet Error Probability (PEP) and initial contention window. PEP depends on the collision probability, thus we replace p of equation (5) with PEP. Considering a link l from node m to n, the average contention window is calculated using equation (5) as follows: $\begin{matrix} (13) & {CW}_{avg} = (\frac{(1 - PEP) (1 - {(2 PEP)}^{r})}{(1 - {PEP}^{r}) (1 - 2 PEP)} {CW}_{\min} + \frac{1}{2}) . \end{matrix}$

As shown in above, average contention window is calculated in terms of packet error probability, minimum contention window ${CW}_{0}$ and backoff stage r. ${CW}_{0}$ is contention window at stage 1. Average contention window is calculated at each back off stage. As the backoff stage increases the average contention window value increases indicating congestion in network. ${PEP}_{l}$ of a given link l represents the probability of the packets loss. $PEP$ for node i is calculated as, $\begin{matrix} (14) & PEP = 1 - d_{f} \cdot d_{r} \end{matrix}$ where $d_{f} \cdot d_{r}$ is the probability that a packet transmission is successful. $d_{f}$ is the forward delivery ratio, the probability the packet will reach the destination successfully. $d_{r}$ is the reverse delivery ratio, the probability that ACK for packet is received.

Thus, average Contention Delay (CD) is computed by multiplying average contention window by slot duration $T_{slot}$ as follows. $\begin{matrix} (15) & {CD}_{avg} = {CW}_{avg} \cdot T_{slot} . \end{matrix}$

Channel busy time (CBT): The routing metric needs to incorporate the length of each backoff stage as given in equation (11). This mainly consists of channel idle time and busy time. As discussed, idle time is the duration of an empty time slot which is constant and the busy time indicates the node is transmitting or there is a collision. To measure Channel Busy Time ${CBT}_{n}$ for a node n, it periodically senses the shared channel to determine whether it is idle or busy. Two counters are maintained, one for idle sensing times and the other for busy sensing times. After a certain time interval (1 second in our implementation), average channel busy time is computed as follows. $\begin{matrix} (16) & CBT = \frac{Total_Time - Idle_Time}{Total_Time} \end{matrix}$ where $Total_Time$ is the summation of idle time and busy time. The average packet delay for link i is calculated as a product of average contention window and CBT as follows. $\begin{matrix} (17) & {Delay}_{i} = {CD}_{avg} \cdot CBT \end{matrix}$

Inter-flow Interference (IR):

The most widely used and realistic model to estimate the inter-flow interference is physical interference model which is described in [2,12]. We use this to compute the inter-flow interference based on the ratio of SINR and SNR as shown in the equation (18). If the

{IR}_{i}

value is 1, there is no inter-flow interference i.e. no interfering neighbors or no traffic generated by interfering neighbors as the SINR is equal to the SNR. Thus the link i is not dependent on inter-flow interference and the link quality is determined by the delay and intra-flow interference component of the metric. The

{IR}_{i} (u)

for node u on a link

u = (i, u)

is defined as

\begin{matrix} (18) & {IR}_{i} (u) = \frac{{SINR}_{i} (u)}{{SNR}_{i} (u)} . \end{matrix}

The unique feature of our metric is the interference estimation is done using combination of physical and logical interference which is important. The contention among the nodes (CBT) estimates the logical interference.

Intra-path Channel Diversity (ICD)

ICD captures the intra-flow Interference in ICA metric. Considering a scenario where source node has two paths to the destination that have same values with regards to the first component of equation (12), the path that uses different channels to transmit data have less intra-flow interference than the path that always uses the same channel to transmit. The

{ICD}_{i}

for link i is defined as follows:

\begin{matrix} {ICD}_{i} = \{\begin{matrix} w 1 & {CH}_{i - 1} \neq {CH}_{i}, \\ w 2 & {CH}_{i - 1} = {CH}_{i} . \end{matrix} 0 ⩽ w 1 ⩽ w 2 \end{matrix}

where

{CH}_{i}

is channel used by node i,

{CH}_{i - 1}

is channel used by node

i - 1

and

w 1

w 2

are the weights. Node i should transmit data through different channel

({CH}_{i})

than the channel

({CH}_{i - 1})

used by previous node

i - 1

to eliminate intra-flow interference. If the node i uses same channel as the previous node

i - 1

, a higher weight is assigned i.e.

w 2

. Instead, if node i uses two different channels for reception and transmission, a lower weight of

w 1

is assigned such that

0 ⩽ w 1 ⩽ w 2

. In our implementation, we use

w 1

and

w 2

as 0 and 1 respectively.

3.3. Rate adaptation

Recently, different systems are used for video streaming in the internet. Adaptive streaming techniques (e.g. HTTP adaptive streaming) rely on a server hosting multiple copies of a video in different streaming rates and qualities. In wireless networks, the video is sent over a UDP. Thus, we assume the rate adaptation of CBR is similar to the video rate adaptation. We observe the ETX and IR values of the underlying network layer and adapt the CBR rate using the Algorithm 1.

Algorithm 1

Rate adaptation (packet p)

The algorithm adapts the CBR rate based on the summation of ETX and IR values i.e. Link_status. Incr is 4096 bits which corresponds to 1 packet (512 bytes/packet). Thus, the algorithm increases the rate by 1 packet/second each time if the Link_status is less than Threshold. This threshold value is dynamic and needs to be changed based on the type of scenario. The rate is increase or decreased till upper bound or lower bound is reached. The upper bound (UB) is calculated as $oldrate \cdot 1.5$ . This means if CBR rates starts from 50 packtes/seconds, it can be increased till 75 packets/per seconds. Similarly the Lower Bound (LB) is calculated as $oldrate \cdot 0.75$ . This means if CBR rates starts from 50 packets/seconds, it can be decrease till 37 packets/per seconds. These values can be changed based on the scenarios. Thus the rate adaptation of CBR traffic takes place based on increase or decrease in the rate.

3.4. Cross-layer implementation

We use Optimized Link State Routing Protocol (OLSR) [8] to implement our proposed metric. We select OLSR for following two reasons. OLSR uses three kinds of the control messages: Hello, Topology Control (TC) and Multiple Interface Declaration (MID). Hello messages are used for finding the information about the link status and the host’s neighbors. The MID message is used by the multi-radio node to advertise its associate interfaces addresses. The proposed implementation architecture using cross-layered approach and OLSR modification details are shown in the Fig. 1. The architecture shows the various components of OSLR, the cross layer parameters acquisition from PHY, MAC and network layer in the routing protocol and rate adaptation at application layer.

Fig. 1.

Cross-layer implementation architecture.

As shown in Fig. 1, the most important component of routing protocol design is the Parameter acquisition module which extracts parameters such as Contention Delay (CD), CBT and IR from MAC layer and passes it to network layer. PHY layer sends the Received Signal Strength (RSSI) to MAC layer which is used to calculate IR. The network layer computes the expected transmission count using probing mechanism. It also computes the delay using CBT and CD. Further, it estimates the intra-channel interference (ICD) using the virtual node concept. Finally, Updatelinkquality() function of OLSR at network layer calculates the link cost using the parameters of all three layers. The updated link cost is embedded in TC message. TC messages are flooded in the network by MPRs. The OLSR uses Dijkstra’s algorithm which creates a topology with the link costs obtained from TC messages from all other nodes and finds the shortest routes. The statistics of ETX and IR are accessed at the application layer. Based on the type of congestion, the CBR rate is increased or decreased which results in dynamic rate allocation to the applications.

4. Simulation model

This section describes the simulation tool and parameters chosen to simulate the routing protocols. The performance parameters used to compare the routing metrics are also described.

4.1. Simulation environment

We use NS2 [23] to carry out extensive simulation and evaluate our routing metric using OLSR. We use the ns2 code available at [1] and extended by VC Borges [7] to compare the proposed routing metric to other metrics. The CMU tools [25] are used to create the wireless network scenario with the random traffic flows and random node locations. We create the 40 node topology using CMU tool ‘setdest’ to generate large number of nodes with random locations. We also set up random CBR traffic connections between nodes using a traffic-scenario generator script ‘cbrgen.tcl’. We evaluate the performance of our protocol by varying traffic density with static node, the scenario representing the backhaul mesh network. We use the MAC and PHY layer parameters as specified in 802.11b Proxim ORiNOCO client PC card. This card uses the physical layer of Direct Sequence Spread Spectrum (DSSS) with a shadowing propagation model. This helps us to simulate the realistic outdoor mesh network. The other common parameters used for simulation are listed in Tables 1 and 2.

Table 1
Simulation parameters

Parameters Values

MAC protocol 802.11b

Date rate 11 Mbps

Number of Nodes 40

Simulation Time 50 Seconds

Environment Size 750 m × 750 m

Traffic Type CBR (Constant Bit rate)

Number of Flows 20 flows

Packet Rate 50 to 70 pkts/sec

Packet Size 512 Bytes

Queue Size 50 Bytes

Number of interfaces 2

Initial energy 100 Joules

Transmission energy 0.0132 mW

Parameters	Values
MAC protocol	802.11b
Date rate	11 Mbps
Number of Nodes	40
Simulation Time	50 Seconds
Environment Size	750 m × 750 m
Traffic Type	CBR (Constant Bit rate)
Number of Flows	20 flows
Packet Rate	50 to 70 pkts/sec
Packet Size	512 Bytes
Queue Size	50 Bytes
Number of interfaces	2
Initial energy	100 Joules
Transmission energy	0.0132 mW

Table 2

Additional simulation parameters

Parameters	Values
PHY layer	DSSS
Propagation model	Shadowing
Path loss exponent	2.9
Standard deviation	1.2 dB
Shadowing distance	1 m
${CW}_{\min}$	32
${CW}_{\max}$	1024
Maximum backoff stage	5
Hello Interval	2 seconds
TC Interval	5 seconds

4.2. Performance metrics

The performance of proposed routing metric is compared using the following performance metrics.

Throughput: This is the number of packets received by the destination per second. It gives the aggregate throughput for all the traffic flows in the network.

Average End-to-End Delay: The end-to-end delay is the time needed for a data packet to be delivered from the source to the destination node in seconds. The average end-to-end delay is aggregate delay of all the packets of different traffic flows in the network.

Routing Overhead: It is the number of routing packets sent per second in the network as part of routing process.

Energy Consumption: It is the average energy utilized by the nodes of the network for the transmission of data packets. This parameter is very important for analysis of computationally complex routing metrics [19,20].

Packet Delivery Fraction: It defines the ratio of number of packets sent to the received. It indicates the level of congestion in the network.

5. Results and discussions

This section presents the performance evaluation of proposed routing metric and compares the results obtained with the MIND, CATT and iAWARE routing metrics. In our scenario, the number of nodes is fixed as 40, flows are fixed as 20 CBR flows, the packet rate is varied from 50 packets/second to 70 packets/second. UDP as a transport layer protocol carries CBR data flows. The locations of nodes are random. The flows introduce inter-flow interference in the network. The number of source/destination traffic sources assigned to the nodes varies in the area of 750 m × 750 m. The flows cover the whole width of the network to reach 25 nodes. This allows for longer path lengths routes giving more routing choices for the implemented routing metrics of OLSR. The CBR flows start sending the packets at different times during the simulation. Thus the congestion is created in the network at different time during the simulation.

5.1. Routing metrics results

This section presents the performance evaluation of proposed routing metric ICA with three routing metrics MIND, CATT and iAWARE. We discuss the results of cross-layer framework for joint routing and rate adaptation in Section 5.2.

Throughput and Delay

As shown in Fig. 2, throughput of ICA routing metric is better compared to other metrics as the packet rate is increased. ICA metric estimates both logical and physical interference using contention delay and IR respectively. The delay component of metric estimate expected transmission time as well as contention delay and IR using physical interference model. Thus ICA helps OLSR protocol to choose the least congested routes thus improving the overall throughput of the network. The MIND metric performs better compared to iAWARE and CATT as it captures load using Channel Busy Time (CBT) and considers both logical as well as physical interference. CBT estimates the logical interference as well as load. However CBT estimation in MIND cannot estimate the effective frame delay. The CATT metric considers the effect of inter-flow interference using protocol interference model. It considers the physical interference implicitly using link loss ratios and finds the least congested paths. But at the higher level of congestion, the estimation of loss ratios using probes is error prone as the probes packets itself can be lost. In addition, the metric assumes that all the neighboring nodes are interfering nodes irrespective of whether the nodes transmit the packet or not. Thus the interfering delay estimation is not accurate. iAWARE routing metric captures the physical interference using the SNR and SINR in dynamic way. It also estimates these expected transmission time. But it does not consider the logical interference i.e. effect of contention in the routing metric. This is very important factor as the traffic density is increased in the network.

As shown in Fig. 3, the average end-to-end delay of ICA is improved compared to other three routing metrics. This is because the ICA estimate delay accurately using contention delay and CBT. The delay estimation for each link is based on delay model of 802.11 MAC. This helps ICA to find the least congested path as the traffic density is increased. The average delay of MIND is better than iAWARE and CATT as it estimates the load using CBT. But the CBT is estimated for each packet sent and later it is averaged. In addition, it does not consider the transmission delay explicitly. The delay component of CATT does not consider the backoff delay and it does not capture the the interference in realistic way using physical interference model. Thus its delay is better compared to MIND. The delay of iAWARE is the worst as it does not consider the contention delay. It gives more weightage to ETT and does not perform well in the presence of high interference.

Fig. 2.

Throughput vs traffic density.

Routing Overhead

One more differentiating parameter for the evaluation of routing metrics is the routing overhead. This QoS parameter is very important for proactive routing protocol like OLSR as it affects the performance of the network. In our work, we consider the total number of routing packets sent per second instead of well known normalized routing overhead (NRL) as performance parameter. As the NRL depends on the number of packets received, it does not give clear picture of routing overhead. We calculate the number of routing packets sent per second for varying traffic density. The ICA, CATT and iAWARE use the probe packets and hence incur a control overhead. These three metrics use ETX which is implemented using probe packets over a sampling period (10 seconds in our implementation). In addition, available bandwidth estimation in ICA, CATT and iAWARE is implemented using packet pair technique. ICA introduces less routing overhead compared to other metrics as shown in Fig. 4 as it computes stable routes. However, there is little difference in routing overhead of MIND and ICA. This is because; MIND introduces less control overhead as it does not use probe packets for link cost estimation. Further, as shown in Fig. 4, routing overhead of MIND is very less compared to iAWARE and CATT because of the passive mechanism. Thus, routing overhead plays an important role in highly congested networks as the overhead can fuel the congestion. In summary, the results reveal that there is a trade-off between routing overhead and the network performance [27,28].

Fig. 3.

Average delay vs traffic density.

Energy Consumption

The another important parameter for the evaluation of routing metrics is the energy consumption. This QoS parameter is very important as the as the multi-radio metrics consume lot of energy in computation of routing metric values to compute optimal route. We use the initial energy as 100 Joules for all the nodes. The initial power used is 20 dB. We compute the power at PHY layer and MAC layer using EnergyModel of NS2. The average energy consumption per node is computed by dividing the total energy by number of nodes i.e. 40. The average energy consumption per node with four routing metrics is shown in Fig. 5. The figure shows that energy consumption of the metric ICA is better compared to other metrics. This is because; it computes a high throughput and stable routes. MIND has poor throughput compared to ICA. However, the energy consumption per node of MIND is comparatively same as that of ICA. This is because ICA, CATT and iAWARE metrics use probe packets to compute the routing metric values. Thus each node spends more energy in probing and link quality computation. MIND use passive mechanism and consumes less energy. In summary, the results reveal that there is a trade-off between energy consumption and the network performance.

Fig. 4.

Routing overhead vs traffic density.

Packet Delivery Fraction (PDF)

One more important parameter for the evaluation of network performance is the PDF. This QoS parameter is very important for application-layer rate adaptation as it indicates the level of congestion in the network. Based on the congestion level indicated by ETX and IR values, the application decide the rate. The number of CBR flows and packet rate introduce the congestion level in the network. The PDF of ICA is better compared to other three metrics as it computes the higher throughput path as shown in Fig. 6. The similar performance is observed with other metrics depending on the throughput gain. As the average PDF of the tested topology is 85%, the rate adaptation gain is better and stable. However, with other experiments we observed that the performance gain is unstable in high level of congestion in the network.

Fig. 5.

Energy consumption per node vs traffic density.

Fig. 6.

PDF vs traffic density.

5.2. Rate adaptation results

The results of joint approach to routing metric and rate adaptation are shown in Figs. 7 and 8. As expected, throughput with rate adaptation (ICA-RA1) is increased with the increase in packet rate as the congestion in tested topology is less as shown in Fig. 7. Thus the rate adaptation algorithm increased the packet rate till the Threshold (0.3). Based on the congestion level at the node (measured using ETX and IR), the CBR rate is increased. However, as shown in Fig. 8, the delay ICA-RA1 is increased as more number of packets are introduced in the network. The rate adaption is dynamic and depends on the congestion as well as threshold values. As shown in Fig. 8, ICA-RA2 has further increased the rate of packet transmission as the threshold value here is 0.40. The delay is increased with ICA-RA2 as more number of packets are received at receiver. Thus the CBR rate adaptation can be carried out based on the network layer congestion by setting appropriate threshold.

Fig. 7.

Throughput vs traffic density.

Fig. 8.

Average delay vs traffic density.

6. Conclusion and future work

Multi-Radio wireless mesh networks need new cross-layer routing metrics which can find the optimal routes using minimum end-to-end delay and least interference to improve the throughput. Additionally, there is a need for joint cross-layer approach for rate adaptation at the application layer based on the statistics collected by the routing metric. To address this, we analytically derived the delay component of our metric using 802.11 DCF model. Using this model, we proposed a routing metric called Interference and Contention Aware (ICA) that establishes the path between source and destination by considering delay, packet loss and interference of each link. We extended the work using cross-layer mechanism, where the application agent (CBR) at each user adapts its transmission rate based on the changes in the packet losses and interference at the node. These strategies help to increase the network performance and QoS of the applications. We carried out the simulations using NS2 simulator with all nodes as static. The simulation results reveal that joint approach of routing and rate adaptation results in better network throughput and average end-to-end delay.

As a future work, we plan to design and implement joint routing and rate allocation mechanism for video transmission in multi-radio wireless mesh networks.

References

http://www.inf.ufrgs.br/~wlccordeiro/resources/olsr/.

Aguayo,

Bicket,

Biswas,

Judd and

Morris, Link-level measurements from an 802.11 b mesh network, in: ACM SIGCOMM Computer Communication Review, Vol. 34, ACM, 2004, pp. 121–132.

I.F.

Akyildiz and

Wang, A survey on wireless mesh networks, Communications Magazine, IEEE 43(9) (2005), S23–S30. doi:10.1109/MCOM.2005.1509968.

Amiri and

H.R.

Sadjadpour, Quit: A cross-layer routing metric based on non-utilized outage capacity, in: Computing, Networking and Communications (ICNC), 2013 International Conference on, IEEE, 2013, pp. 222–226. doi:10.1109/ICCNC.2013.6504084.

Bianchi, Performance analysis of the ieee 802.11 distributed coordination function, Selected Areas in Communications, IEEE Journal on 18(3) (2000), 535–547. doi:10.1109/49.840210.

V.C.M.

Borges,

Curado and

Monteiro, Cross-layer routing metrics for mesh networks: Current status and research directions, Computer Communications 34(6) (2011), 681–703. doi:10.1016/j.comcom.2010.12.001.

V.C.M.

Borges,

Pereira,

Curado and

Monteiro, Routing metric for interference and channel diversity in multi-radio wireless mesh networks, in: Ad-Hoc, Mobile and Wireless Networks, Springer, 2009, pp. 55–68.

Clausen,

Jacquet,

Adjih,

Laouiti,

Minet,

Muhlethaler,

Qayyum and

Viennot, 2003, Optimized link state routing protocol (olsr).

D.S.J.

De,

D.S.J.

Couto,

Aguayo,

Morris and

Bicket, A high-throughput path metric for multi-hop wireless routing, 2003.

10.

Draves,

Padhye and

Zill, Routing in multi-radio, multi-hop wireless mesh networks, in: Proceedings of the 10th Annual International Conference on Mobile Computing and Networking, ACM, 2004, pp. 114–128.

11.

Genetzakis and

V.A.

Siris, A contention-aware routing metric for multi-rate multi-radio mesh networks, in: Sensor, Mesh and Ad Hoc Communications and Networks, 2008. SECON’08. 5th Annual IEEE Communications Society Conference on, IEEE, 2008, pp. 242–250. doi:10.1109/SAHCN.2008.38.

12.

Gupta and

P.R.

Kumar, The capacity of wireless networks, Information Theory, IEEE Transactions on 46(2) (2000), 388–404. doi:10.1109/18.825799.

13.

C.-H.

Hsu and

Hefeeda, A framework for cross-layer optimization of video streaming in wireless networks, ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM) 7(1) (2011), 5.

14.

IEEE Computer Society LAN MAN Standards Committee et al., 1997, Wireless lan medium access control (mac) and physical layer (phy) specifications.

15.

Khan,

Peng,

Steinbach,

Sgroi and

Kellerer, Application-driven cross-layer optimization for video streaming over wireless networks, Communications Magazine, IEEE 44(1) (2006), 122–130. doi:10.1109/MCOM.2006.1580942.

16.

T.-S.

Kim,

Jakllari,

S.V.

Krishnamurthy and

Faloutsos, An integrated routing and rate adaptation framework for multi-rate multi-hop wireless networks, Wireless Networks 19(5) (2013), 985–1003. doi:10.1007/s11276-012-0513-5.

17.

Laufer,

Dubois-Ferriere and

Kleinrock, Multirate anypath routing in wireless mesh networks, in: INFOCOM 2009, IEEE, IEEE, 2009, pp. 37–45.

18.

Liu and

Liao, On routing in multichannel wireless mesh networks: Challenges and solutions, Network, IEEE 22(1) (2008), 13–18. doi:10.1109/MNET.2008.4435900.

19.

Merlo,

Migliardi and

Caviglione, A survey on energy-aware security mechanisms, Pervasive and Mobile Computing 24 (2015), 77–90. doi:10.1016/j.pmcj.2015.05.005.

20.

Migliardi and

Merlo, Improving energy efficiency in distributed intrusion detection systems, Journal of High Speed Networks 19(3) (2013), 251–264.

21.

P.S.

Mogre,

Hollick and

Steinmetz, Qos in wireless mesh networks: Challenges, pitfalls, and roadmap to its realization, in: 17th International Workshop on Network and Operating Systems Support for Digital Audio & Video, Urbana-Champaign, Illinois, USA, 2007.

22.

D.G.

Narayan,

Uma,

Pavan and

Suraj, Cl-ild: A cross layer interference-load and delay aware routing metric for multi-radio wireless mesh network, in: Advanced Computing, Networking and Security (ADCONS), 2013 2nd International Conference on, IEEE, 2013, pp. 181–186.

23.

Network simulator ns-2, http://www.isi.edu/nsnam/ns.

24.

L.T.

Nguyen,

Beuran and

Shinoda, An interference and load aware routing metric for wireless mesh networks, International Journal of Ad Hoc and Ubiquitous Computing 7(1) (2011), 25–37. doi:10.1504/IJAHUC.2011.037851.

25.

Ns-2 with wireless and mobility extensions, available via web-site http://www.monarch.cs.cmu.edu.

26.

Passos and

C.V.N.

Albuquerque, A joint approach to routing metrics and rate adaptation in wireless mesh networks, IEEE/ACM Transactions on Networking (TON) 20(4) (2012), 999–1009. doi:10.1109/TNET.2011.2170585.

27.

Ramachandran,

Sheriff,

Belding and

Almeroth, Routing stability in static wireless mesh networks, in: Passive and Active Network Measurement, Springer, 2007, pp. 73–82. doi:10.1007/978-3-540-71617-4_8.

28.

R.K.

Sheshadri and

Koutsonikolas, An experimental study of routing metrics in 802.11 n wireless mesh networks, Mobile Computing, IEEE Transactions on 13(12) (2014), 2719–2733. doi:10.1109/TMC.2013.148.

29.

Staehle,

Hirth,

Pries,

Wamser and

Staehle, Aquarema in action: Improving the youtube qoe in wireless mesh networks, in: Internet Communications (BCFIC Riga), 2011 Baltic Congress on Future, 2011, pp. 33–40. doi:10.1109/BCFIC-RIGA.2011.5733220.

30.

A.P.

Subramanian,

M.M.

Buddhikot and

Miller, Interference aware routing in multi-radio wireless mesh networks, in: Wireless Mesh Networks, WiMesh 2006. 2nd IEEE Workshop on, IEEE, 2006, pp. 55–63.

31.

Wu,

Peng,

Long,

Cheng and

Ma, Performance of reliable transport protocol over ieee 802.11 wireless lan: Analysis and enhancement, in: INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, Vol. 2, IEEE, 2002, pp. 599–607.

32.

Yang,

Wang and

Kravets, Interference-aware load balancing for multihop wireless networks, 2005.