A cross-layer optimization for delay-aware load balancing in multi-radio wireless mesh networks

Abstract

In this paper, we propose a cross-layer optimization technique for multi-radio Wireless Mesh Networks (WMNs) using new routing metric and load balancing mechanism. WMNs are an emerging technology and are used as a backhaul network to connect various types of networks to the internet. These networks consist of mesh routers with multi-radio support to enhance the capacity. As the traffic density is very high from the client mesh to the gateways, load balancing in these networks has become an important research issue. For this, multipath routing which can exploit the multi-radio capabilities to balance the traffic simultaneously through mesh routers is required. To address this, we analytically derive the routing metric using IEEE 802.11 Distributed Coordination Function (DCF) delay model. Using this model, we propose a routing metric called Passive Interference and Delay Aware (PIDA) metric for multipath routing to find the interference free paths. We extend the work by performing load balancing on multiple paths as well as on multiple interfaces using the proposed metric. We implement our techniques using popular Ad hoc On-demand Multipath Distance Vector (AOMDV) routing protocol in NS2. The results reveal that PIDA performs better in terms of throughput and average delay compared to recently proposed routing metrics with minimal routing overhead. In addition, load balancing mechanism with PIDA metric shows better results depending on the congestion level in the network.

Keywords

Wireless mesh network cross-layer passive metric AOMDV load balancing

1. Introduction

Wireless Mesh Networks (WMNs) [2] are an emerging technology and have attracted much attention in the field of wireless networks. One of the reasons is that they provide a low-cost solution of deploying wide-area network to provide last-mile broadband internet access in urban and rural areas. Interoperability feature has made them to integrate easily with various other wireless technologies such as cellular technologies, wired technologies or combinations of more than one type. These networks are called as infrastructure WMNs or backbone networks. The mesh routers in these networks are equipped with multiple radios to enhance the capacity in a significant way. With two radios, a node may send data on two channels simultaneously. It also allows nodes to receive and transmit data simultaneously, by utilizing more of the radio spectrum. Usually these routers are stationary and do not have energy constraints. With a significant reduction in the 802.11 hardware, many commercial service providers are providing 3 to 4 radio support for each router. However, the presence of inter-flow interference and intra-flow interference has become an important issue in the design of routing protocols in these networks [20,22].

There is a heavy traffic flow between mesh routers and internet gateways in backbone mesh networks. This results in an uneven loading of links and can cause certain paths to be saturated. Likewise, the existence of inter-flow and intra-flow interference may affect traffic loads on these links. Load balancing techniques are thus required to avoid hot spots and to increase network utilization. Towards this, multipath routing protocols combined with better routing metrics are required to effectively distribute the traffic by selecting channel diverse paths with minimal inter/intra flow interference. In this context, many multipath routing metrics with load balancing mechanisms are reported in literature. But most of the studies focus on single radio and single channel case with solutions being developed using the layered architecture [23]. With the distinctive features of backbone networks, joint optimization of routing, load balancing and interface assignment has become an important issue. In addition, most of the multipath routing protocols proposed in the literature use the routing metrics based on probing which incur control overhead [6]. Thus there is need for passive routing metrics.

To address the above issues, a new multipath routing metric called as Passive Interference and Delay Aware (PIDA) is presented. The metric estimates the delay using contention and transmission delay, inter-flow interference using physical model and intra-flow interference using channel diversity. The metric is then used by the Ad hoc On-demand Multipath Distance Vector routing (AOMDV) protocol [21] to compute the multiple paths with minimal interference. The computed multiple paths are used to balance the traffic load when the congestion in the network increases. The unique feature of our approach is along with multiple paths, we exploit the multiple interfaces of each path to effectively forward the traffic based on the least congested interface. This helps in effective utilization of radio resources to the improve performance. The contributions of this paper are three fold.

We analytically derive the delay component of our routing metric using IEEE 802.11 DCF [13] basic access mechanism.

We design and implement the new routing metric considering the parameters from PHY, MAC and Network layer.

Perform load balancing using multiple paths and multiple interfaces.

The rest of the paper is organized as follows. In Section 2, we discuss the related work. In Section 3, we discuss about the 802.11 DCF model and proposed routing metric based on this model. In addition, we discuss load balancing mechanism. We discuss the simulation model and results in Sections 4 and 5 respectively. Finally, in Section 6 we discuss the conclusion and future work.

2. Related work

In this section we discuss the related work in the areas of routing metrics for unipath and multipath routing. Later we discuss the load balancing mechanisms reported in the literature.

2.1. Unipath routing metrics

Several routing metrics [6,27] have been proposed for WMNs in the literature. Here we mention few of them related to our work. The most popular routing metric which is deployed in the WMN testbeds is Expected Transmission Count [8]. 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 problem with ETX is that it does not consider the differences in multiple transmission rates which are very important in multi-rate mesh networks. To address the limitations of ETX, authors in [10] propose Expected Transmission Time (ETT) metric which considers the transmission rate of each individual link in multi-rate networks. ETT estimates the link quality of each individual link using packet losses, packet size and available bandwidth. However, ETT inherits the drawbacks of ETX as it does not consider load and interference. The authors in [18] propose interference aware routing metric called as Interferer Neighbors Count (INX) that incorporates the interference on each link using protocol interference model along with expected transmission time. However, it assumes that all the neighbors are interfering links irrespective of whether the neighbor is transmitting or no which can overestimate the link cost. In [29], authors propose probabilistic routing mechanism based on condensation phenomenon for efficient broadcasting. The technique computes the probabilistic broadcast forwarding strategy based on the available bandwidth, power levels and interfering nodes.

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. 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. Another routing metric which estimates the inter-flow interference in realistic way using physical interference model is proposed in [32]. 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 uses passive monitoring mechanism is Metric for Interference and Channel Diversity (MIND) [7]. It considers the interflow 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. However the metric does not estimate the delay effectively. In addition, these metrics lack analytical model for the choice of link quality estimators in their design.

2.2. Multipath routing metrics based load balancing

In the past few years, lot of research is carried out using multipath routing for load balancing. Some approaches use the backup route in the event of congestion. Others use multiple paths to distribute the traffic simultaneously based on congestion. Some of the popular approaches are based on estimating load using different routing metrics [3,4,16,33,34]. However, all the works are carried out for single-radio networks. With the popularity of multi-radio network for backbone networks, there is need to optimize the load balancing mechanism using multipath and multiple radios along with better routing metric. Some works are reported in the literature on multipath routing metrics for multi-radio WMNs. In [30], authors propose the selection of multiple paths using a new metric (channel aware multipath) CAM. This metric is based on WCETT. An optimal path is selected among multiple paths based on the metric calculated and load is balanced using multiple paths. In [14], authors propose a spectrum-aware routing protocol. It estimates the delay using RREQ packets for assigning the interface to a route. Later it uses throughput increment as metric to select the optimal route. In [19], authors propose a multi-path routing protocol for tactical ad hoc networks which computes the multiple routes using the link quality and channel diversity. In [15], authors propose a cognitive multipath multi-channel routing protocol. Authors use cognitive functions to make nodes intelligently select multiple node-disjoint, edge-disjoint and frequency-disjoint paths using machine learning techniques.

In [35], authors propose a new metric called as Weighted Interference Multipath Metric (WIM), using which multiple routes are found. It aims to minimize the intra-flow and inter-flow interference between multiple routes. Authors conclude that in multi-radio environment, WIM metric provides lower delay and higher reliability paths than CAM and simple maximally disjoint selection algorithm. In [9], authors propose heuristic multipath discovery algorithm to find multiple independent paths. The algorithm consider wireless interference caused by multi-radio in the multipath discovery. All the metrics discussed above use active probing mechanism which incurs a control overhead in the network in congested networks. As the multipath routing itself introduces lot of control overhead in finding multiple paths, there is a need for routing metric which incurs less routing overhead i.e. passive routing metric. In addition, there is a need for load balancing mechanism to exploit the multiple paths and multiple radios.

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 AOMDV routing protocol using mechanism.

3.1. Delay model for 802.11 DCF mechanism

We use the model presented in [36] 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 [P_{D}]$ 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}{rcl} E [P_{D}] & = & α (\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}{rcl} E [P_{D}] & = & \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 [P_{D}] = \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 [P_{D}] = (\frac{(1 - p) (1 - {(2 p)}^{m^{'}})}{(1 - p^{m^{'}}) (1 - 2 p)} {CW}_{min} + \frac{1}{2}) . \end{array}$

Average length of back-off 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 Eq. (11). This parameter estimates time required to transmit a frame.

Number of interfering nodes: As shown in Eq. (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. Passive interference and delay aware (PIDA) routing metric

We propose a new routing metric called PIDA 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. PIDA for path p is defined as follows: $\begin{array}{rcl} PIDA (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 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 Eq. (1). These two estimations are described in detail as follows.

Average contention delay. 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 Eq. (5) with PEP. Considering a link l from node m to n, the average contention window is calculated using Eq. (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 Eq. (13), average contention window is calculated in terms of PEP, 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 back-off stage increases, the average contention window value increases indicating congestion in network. ${PEP}_{i}$ is of a given link i, which represents the probability of the packets loss. PEP for node i is calculated as, $\begin{matrix} (14) & {PEP}_{i} = α \frac{{Qlen}_{i}}{{Qlen}_{max}} + (1 - α) \frac{{RTC}_{i}}{{RTC}_{max}} . \end{matrix}$

As shown in Eq. (14), the PEP is normalized to depict congestion at each node by considering the average queue length and retransmission count. We estimate average queue length using exponentially weighted moving average (EWMA) as follows: $\begin{matrix} (15) & {Qlen}_{i} = α \cdot Q_{cur} + (1 - α) \cdot {Qlen}_{i - 1}, \end{matrix}$ where ${Qlen}_{i}$ is the average queue length and $Q_{Cur}$ is the current queue length. We give more weightage to the current queue length by setting α value as 0.6.

PEP considers another parameter the Re-transmission count (RTC) to derive the link quality. In 802.11 unicast, if the sender does not receive an ACK for transmitted packet, it retransmits the packet using binary exponential back-off algorithms as discussed above. The Re-transmission count (RTC) defines number of transmissions required by a source node for successful transmission to the next hop at MAC layer. If the RTC value is more, there are more packets losses mainly due to a collision or poor channel conditions. Thus RTC indicates the congestion at the node. To obtain the MAC layer RTC, each node maintains a table of RTC for its neighbors. When a packet is retransmitted, the node records the RTC for that packet to the destination node. For each neighbor, we set a sliding window of 5 (i.e. ${RTC}_{max}$ ) consecutive samples of RTC. The actual ${RTC}_{i}$ used by the upper layers is the moving average of these 5 samples which smoothens the transient change of the RTC. $\begin{matrix} (16) & {RTC}_{i} = α \cdot {RTC}_{cur} + (1 - α) \cdot {RTC}_{i - 1}, \end{matrix}$ where ${RTC}_{i}$ is the average RTC value and ${RTC}_{cur}$ is the current RTC value. We give more weightage to the current RTC value by setting α value as 0.6.

Thus, average Contention Delay (CD) is computed by multiplying average contention window by slot duration $T_{slot}$ as follows. $\begin{matrix} (17) & {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 Eq. (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$ 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} (18) & 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} (19) & {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 [1,12]. We use this to compute the inter-flow interference based on the ratio of SINR and SNR as shown in the Eq. (20). If the

{IR}_{i}

value is 1, there is no interflow 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

i = (u, v)

is defined as

\begin{matrix} (20) & {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 [21]. The contention among the nodes (CBT) estimates the logical interference.

Intra-path Channel Diversity (ICD)

ICD captures the intra-flow Interference in PIDA. Considering a scenario where source node has two paths to the destination that have same values with regards to the first component of Eq. (7), the path that use 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. Load balancing

We use AOMDV routing protocol to find the multiple paths and hence perform load balancing. The proposed passive metric is used to find the interference free multiples paths. We perform the load balancing as reported in our work [24]. The load for each node is estimated using queue occupancy of all the interfaces of a node. The queue occupancy is calculated by adding queue length of all the interfaces. The neighbor’s queue occupancy information is stored in node’s routing table. Whenever a node broadcasts Hello packet it piggybacks its queue occupancy information in the reserved bit of Hello packet and receiving nodes stores the queue occupancy information of the respective neighbor in routing table. The load balancing is performed based on queue occupancies of neighboring nodes as shown in Algorithm 1.

In addition to the normal load balancing, we perform the load balancing on each interface of the chosen next-hop based on the interface load as shown in Algorithm 1. This is important in multi-radio environment as by default the packet is forwarded on the first interface irrespective of the load on the other interface i.e. packet is queued on second interface only when first interface’s buffer is full. Thus packet may incur delay if packet is queued in the congested interface. Thus we used the mechanism used by us in [25] to queue the packet in the least congested interface. This decreases the delay of the packet. The less congested interface is calculated based on the channel busy time (CBT). We assume static channel assignment with N interfaces and each interface assigned to one channel.

Algorithm 1.

Load-Balancing (Packet p)

3.4. Implementation

We use the well-known reactive protocol AOMDV for implementation of our metric. We use the AOMDV-MR patch for multi-radio extension in NS2. Later, we extract the various parameters from network, MAC and physical layers in AOMDV-MR to calculate the PIDA metric. The proposed implementation architecture using cross-layer is shown in the Fig. 1.

Fig. 1.

Proposed architecture.

As shown in the Fig. 1, AODMV has five important functions namely recvRREQ, recvRREP, recvERR, recvHello which process four control messages as part of routing process and forward function. We modify mainly the recvRREQ, recvHello and Forward functions to implement the routing metric and load balancing mechanism. The parameter acquisition module helps recvRREQ function to estimate routing metric by accessing parameters from different layers. The parameter RSSI is accessed from PHY layer which is used to calculate SNR and SINR which in turn estimates the Interference Ratio (IR) at MAC layer. The parameters Channel Utilization and IR are accessed from MAC layer and passed to network layer. In network layer, parameter Channel switching cost is calculated at each node over the path using virtual node concept. Each node checks for the interface used by the previous node whenever RREQ packet arrives. If both nodes use the same interface, higher weight is assigned by incrementing the ICD variable in RREQ packet otherwise CSC value is not changed. All these parameters from three layer are accessed by parameter acquisition module in recvRREQ() of aomdv.cc. This module estimates the link cost using Eq. (10). Every time RREQ is received, its link cost is updated using routing metric. The routing process continues till the RREQ reaches destination and receiver gets RREP message. In the whole process, all the intermediate nodes update their link cost to the destination. Hello messages are used to exchange queue occupancy level of neighboring nodes. The Forward() function is used to forward the data packets by AOMDV. In this function, we perform load balancing based on multiple paths as well as multiple interfaces.

4. Simulation model

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

4.1. Simulation environment

We use NS2 [26] to carry out extensive simulation and evaluate our routing metric. The CMU tools [28] are used to create the wireless network scenario with the random traffic flows and node locations. The topologies are created using CMU tool ‘setdest’ to generate number of nodes with random and fixed locations. We also set up random CBR traffic connections between nodes using a traffic-scenario generator script cbrgen.tcl. The packet size of all the flows is 512 bytes. The queue type used is DropTail and the maximum queue size is set as 50 packets. We evaluate the performance of our routing metric and joint approach using five scenarios with all static nodes, representing the backhaul mesh network. The type of topologies and unique parameters used to create these scenarios are listed in Table 1 and Table 2 respectively. The other parameters used for simulation are listed in Table 2. We use the MAC and PHY layer parameters as specified in 802.11b Proxim ORiNOCO client PC card.

Table 1
Simulation scenarios

Parameters Scen 1 Scen 2 Scen 3 Scen 4 Scen 5

No. of Nodes 40 40 30 30 20

Type of Topology Random Grid Random Grid Random

Number of Flows 30–50 30–50 30–50 25 15

Packet Rate 70 70 70 50–100 30–50

Congestion Level High Medium High Medium Medium

Parameters	Scen 1	Scen 2	Scen 3	Scen 4	Scen 5
No. of Nodes	40	40	30	30	20
Type of Topology	Random	Grid	Random	Grid	Random
Number of Flows	30–50	30–50	30–50	25	15
Packet Rate	70	70	70	50–100	30–50
Congestion Level	High	Medium	High	Medium	Medium

Table 2

Simulation parameters

Parameters	Values
MAC protocol	802.11 b
Data Rate	11 Mbps
Simulation Time	50 s
Environment Size	750 m × 750 m
Transmission Range	250 m
Traffic Type	CBR (Constant Bit rate)
Number of interfaces	2

4.2. Performance metrics

The following performance metrics are used to evaluate proposed routing metric and load balancing mechanism.

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.

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

5. Results and discussion

This section presents the performance evaluation of proposed routing metric and the load balancing mechanism separately. We consider 5 different scenarios as listed in Table 1. The scenarios are created to evaluate the effect of different level of congestion and interference by varying the transmission rate and CBR traffic flows. Additionally, they are created to evaluate the effectiveness of interference and contention delay on the routing metrics and load balancing mechanisms. We have chosen the combination of routing metrics which estimate the three different types of inter-flow interferences namely protocol, physical and logical interference. We also consider both categories of routing metrics namely the active (iAWARE, CATT) as well as passive metric (MIND) to compare the performance of the proposed passive routing metric. CBR flows carry the UDP traffic. The locations of nodes are random and fixed based on the scenario. The flows introduce inter-flow interference in the network. The packet rate introduces the different levels congestion in the network. The number of source/destination traffic sources assigned to the nodes varies in the area of 750 m × 750 m in each of the scenario. The flows cover the whole width of the network to reach 12 nodes in 20 nodes scenario, 15–20 nodes in 30 node scenarios and 25 nodes in case of 40 node scenarios. This allows for longer path lengths routes giving more routing choices for the implemented routing metrics of AOMDV. The 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. We present the results for routing metrics and load balancing separately in the following sections.

Fig. 2.

Throughput vs scenarios.

5.1. Routing metrics results

Throughput and delay

As shown in Fig. 2, throughput of PIDA routing metric is better compared to other metrics depending on the congestion. PIDA metric estimates both logical and physical interference using contention delay and IR respectively. The metric estimates the delay using the channel busy time along with the contention delay. In addition, metric estimates the intra-flow interference to compute the channel diverse paths. As the congestion level in the tested scenarios varies from medium to high, the effect of logical interference is important in the estimation of routing metric. CBT and contention delay estimate the logical interference as well as delay. Thus, PIDA helps AOMDV protocol to choose the least congested and non-interfering routes thus improving the overall throughput of the network. The MIND metric performs better compared to iAWARE and CATT as it captures delay using Channel Busy Time (CBT) and considers both logical as well as physical interference. However, it does not consider the average backoff time which results in routes that suffer from high contention level. The CATT metric considers the effect of interflow 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 physical interference using the SNR and SINR in dynamic way. It also estimates the 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 congestion in the network is increased. In addition, the estimation of ETT using packet loss ratios and available BW estimation becomes inaccurate as the load in the network is increased.

Another observation about the results is that the passive metrics PIDA and MIND are performing very well in heavily loaded scenarios such as Scen 1 and 3. However, the improvement in throughput is relatively less in Scen 2, 4 and 5 where level of congestion is medium. Thus, there is a tradeoff between throughput gain and routing control overhead of passive metrics in medium level of congestion. The same is true with low level of congestion scenarios. However, the proposed passive metric PIDA is suitable for backhaul mesh networks as there is always heavy traffic from mesh clients to internet gateways through the backbone mesh routers. In summary, there is a need for hybrid routing metric design which will use the combination of active and passive monitoring in the estimation of link quality parameters which will suit all types of congestion [31].

As shown in Fig. 3, the average end-to-end delay of PIDA is improved compared to other three routing metrics. This is because the PIDA estimates the delay accurately using transmission, backoff and queuing delay over a period of time. The delay estimation for each link is based on delay model of IEEE 802.11 MAC. This helps PIDA to find the least congested path depending on the congestion in the network. The average delay of MIND is better than iAWARE and CATT as it estimates the delay using CBT. But the CBT is estimated for each packet sent and rather than over a time interval. In addition, it does not consider the contention delay. The delay of iAWARE and CATT is the worst as they do not consider the effect of contention delay. They give more weightage to ETT and do not perform well in highly loaded scenarios.

Routing Overhead

One more differentiating parameter for the evaluation of routing metrics is the routing overhead. This QoS parameter is very important for routing protocol as it affects the performance of the network in a congested 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. As shown in Fig. 4, the routing overhead of MIND and PIDA are almost same as metrics uses passive mechanism and does not introduce any control packets. The iAWARE and CATT metrics use the probe packets and hence incur a control overhead. Both metrics use ETX which are implemented using probe packets. In addition, available bandwidth estimation in iAWARE is implemented using packet pair technique. Thus these two metrics introduce maximum control overhead. Thus, this parameter plays an important role in the design of routing metric when there is always congestion in the network such as backbone mesh networks.

Packet Delivery Fraction (PDF)

One more important parameter for the evaluation of network performance is the PDF. This QoS parameter is very important for load balancing routing protocol as it indicates the level of congestion in the network. Generally, the passive routing metrics are suitable for medium to heavily congested networks such as backbone networks. We created scenarios with two levels of congestion namely medium and high. The Scen 1 and 3 have the average PDF of 70% and 46% respectively and the Scen 2, 4 and 5 have the average PDF as 84%, 77% and 75% respectively. Thus we categorize Scen 1 and 3 with high level of congestion and Scen 2, 4, 5 with medium level of congestion as shown in Table 1. The number of CBR flows and packet rate introduce the congestion level in the network. The PDF of IDA is better compared to all other metrics as it finds the non-interfering multiples paths as shown in Fig. 5. The similar performance is observed with other metrics depending on the throughput gain.

Fig. 3.

Delay vs scenarios.

Fig. 4.

Routing overhead vs scenarios.

Fig. 5.

Packet delivery fraction vs scenarios.

5.2. Load balancing results

The average packet losses of the tested topologies vary from 16% to 54% as per PDF results of the Fig. 5. The routing metric results discussed in the Section 5.1 compute the optimal multipath routes but do not use the alternate paths in the event of congestion. Thus multiple paths can be used to balance the load effectively. In our work, we perform load balancing both on multiple paths and multiple interfaces. Thus, the results of PIDA-LB are improved depending on the congestion level in the network as shown in Figs 6 and 7. The first level of load balancing is carried out by choosing least congested next-hop among the multiple paths available. This is computed using the queue occupancy levels of neighbors. This helps the protocol to reduce the packet losses if the current next-hop is congested. This type of load balancing is effective in higher level of congestion. Thus, the average throughput and delay are better for Scen 1 and 3 as the level of congestion in these scenarios is high compared to other scenarios.

Fig. 6.

Average Throughput Vs Scenarios (Load Balancing).

The next level of load balancing is on multiple interfaces of chosen next hop. The interface load balancing is an important technique to improve end-to-end delay and utilize the radio resources efficiently. As discussed in Section 3.3, by default the packets are scheduled always on the first interface even if the other interfaces are free which can lead to more packet delay. This is the per-flow packet scheduling which is used in all the evaluated metrics. This technique increases the average delay and does not utilize the radio resources efficiently [17]. In interface load balancing, we use per-packet scheduling mechanism to schedule the packets in least congested interface. This factor mainly contributes to the lower delay of PIDA-LB when the network gets congested on the interfaces. In medium level of congestion scenarios like Scen 2, 4 and 5, the improvement in average delay is more compared to throughput because of effective interface management as shown in Fig. 7. In summary, the combined load balancing approach of PIDA-LB results in better performance compared to PIDA depending on the congestion level in the network as shown in Figs 6 and 7.

Fig. 7.

Average Delay Vs Scenarios (Load Balancing).

6. Conclusion and future work

Wireless mesh networks need new routing metrics for multipath routing which can estimate the delay and interference accurately. In addition, effective load balancing mechanisms are required to utilize the multi-radio capabilities. Towards this, we propose optimization technique which performs efficient routing decisions and load balancing. A new passive metric PIDA based on 802.11 DCF model is proposed to compute non-interfering multiple paths. The PIDA metric estimates the packet delay, inter-flow and intra-flow interference using the parameters from PHY, MAC and Network layers. We extend the work by performing load balancing both on the basis of multiple paths and multiple interfaces using the parameters of this metric. Simulations results using NS2 reveal that the cross optimization technique improves the QoS parameters in terms of throughput, average end-to-end delay compared to other techniques with minimal routing control overhead in the congested network.

We plan to extend the work with coordinated load balancing and dynamic channel assignment mechanism for multi-radio multi-channel mesh networks.

References

[1]

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.

[2]

I.F.

Akyildiz and

Wang , A survey on wireless mesh networks, IEEE Communications Magazine 43(9) (2005), S23–S30.

[3]

Ali ,

B.G.

Stewart ,

Shahrabi and

Vallavaraj , Congestion adaptive multipath routing for load balancing in mobile ad hoc networks, in: 2012 International Conference on Innovations in Information Technology (IIT), IEEE, 2012, pp. 305–309.

[4]

Bhattacharjee and

Bandyopadhyay , Interference aware energy efficient multipath routing in multihop wireless networks, Journal of High Speed Networks 20(4) (2014), 263–276.

[5]

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

[6]

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.

[7]

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.

[8]

D.S.J.

De ,

D.S.J.

Couto ,

Aguayo ,

Morris and

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

[9]

Ding ,

Yang and

Xiao , Multisource video on-demand streaming in wireless mesh networks, IEEE/ACM Transactions on Networking 20(6) (2012), 1800–1813.

10.

[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.

[11]

Genetzakis and

V.A.

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

12.

[12]

Gupta and

P.R.

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

13.

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

14.

[14]

Ju and

J.B.

Evans , Spectrum-aware routing protocol for cognitive ad-hoc networks, in: GLOBECOM 2009. IEEE Global Telecommunications Conference, 2009, IEEE, 2009, pp. 1–6.

15.

[15]

Ju and

J.B.

Evans , Scalable cognitive routing protocol for mobile ad-hoc networks, in: 2010 IEEE Global Telecommunications Conference (GLOBECOM 2010), IEEE, 2010, pp. 1–6.

16.

[16]

J.-Y.

Kim ,

G.S.

Tomar ,

Shrivastava ,

S.S.

Bhadauria and

W.-H.

Lee , Load balanced congestion adaptive routing for mobile ad hoc networks, International Journal of Distributed Sensor Networks 2014 (2014), Article ID 532043, 10 pp., doi: 10.1155/2014/532043.

17.

[17]

Köbel ,

W.B.

García and

Habermann , Definition of an 802.11 interface management process in a proposed system for transmission capacity enhancement in wireless mesh networks, Journal of Computer Networks and Communications 2015 (2015), Article ID 898365, 13 pp., doi: 10.1155/2015/898365.

18.

[18]

Langar ,

Bouabdallah and

Boutaba , Mobility-aware clustering algorithms with interference constraints in wireless mesh networks, Computer Networks 53(1) (2009), 25–44.

19.

[19]

S.-W.

Lee ,

J.Y.

Choi ,

K.W.

Lim ,

Y.-B.

Ko and

B.-H.

Roh , A reliable and hybrid multi-path routing protocol for multi-interface tactical ad hoc networks, in: 2010-MILCOM, 2010 Military Communications Conference, IEEE, 2010, pp. 2237–2242.

20.

[20]

Liu and

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

21.

[21]

M.K.

Marina and

S.R.

Das , Ad hoc on-demand multipath distance vector routing, ACM SIGMOBILE Mobile Computing and Communications Review 6(3) (2002), 92–93.

22.

[22]

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.

23.

[23]

N.S.

Nandiraju ,

D.S.

Nandiraju and

D.P.

Agrawal , Multipath routing in wireless mesh networks, in: 2006 IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS), IEEE, 2006, pp. 741–746.

24.

[24]

D.G.

Narayan ,

Nivedita ,

Kiran and

Uma , Congestion adaptive multipath routing protocol for multi-radio wireless mesh networks, in: 2012 International Conference on Radar, Communication and Computing (ICRCC), IEEE, 2012, pp. 72–76.

25.

[25]

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: 2nd International Conference on Advanced Computing, Networking and Security (ADCONS), 2013, IEEE, 2013, pp. 181–186.

26.

[26]Network simulator ns-2, available at: http://www.isi.edu/nsnam/ns.

27.

[27]

M.A.

Ngadi ,

Ali ,

A.H.

Abdullah and

R.H.

Khokhar , A taxonomy of cross layer routing metrics for wireless mesh networks, EURASIP J. Wireless Comm. and Networking 2012 (2012), 177.

28.

[28]Ns-2 with wireless and mobility extensions, available at: http://www.monarch.cs.cmu.edu.

29.

[29]

Palmieri and

Castiglione , Condensation-based routing in mobile ad-hoc networks, Mobile Information Systems 8(3) (2012), 199–211.

30.

[30]

Sheriff and

Belding-Royer , Multipath selection in multi-radio mesh networks, in: BROADNETS 2006. 3rd International Conference on Broadband Communications, Networks and Systems, IEEE, 2006, pp. 1–11.

31.

[31]

R.K.

Sheshadri and

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

32.

[32]

A.P.

Subramanian ,

M.M.

Buddhikot and

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

33.

[33]

C.K.

Toh ,

A.-N.

Le and

Y.-Z.

Cho , Load balanced routing protocols for ad hoc mobile wireless networks, IEEE Communications Magazine 47(8) (2009), 78–84.

34.

[34]

D.A.

Tran and

Raghavendra , Congestion adaptive routing in mobile ad hoc networks, IEEE Transactions on Parallel and Distributed Systems 17(11) (2006), 1294–1305.

35.

[35]

J.W.

Tsai and

Moors , Interference-aware multipath selection for reliable routing in wireless mesh networks, in: MASS 2007. IEEE International Conference on Mobile Adhoc and Sensor Systems, 2007, IEEE, 2007, pp. 1–6.

36.

[36]

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.