Reinforcement learning based routing in wireless mesh networks

This paper addresses the problem of efficient routing in backbone wireless mesh networks (WMNs) where each mesh router is equipped with multiple radio interfaces and a subset of nodes serve as gateways to the Internet. Most routing schemes have been designed to reduce routing costs by optimizing one metric, e.g., hop count and interference ratio. However, when considering these metrics together, the complexity of the routing problem increases drastically. Thus, an efficient and adaptive routing scheme that takes into account several metrics simultaneously and considers traffic congestion around the gateways is needed. In this paper, we propose an adaptive scheme for routing traffic in WMNs, called Reinforcement Learning-based Distributed Routing (RLBDR), that (1) considers the critical areas around the gateways where mesh routers are much more likely to become congested and (2) adaptively learns an optimal routing policy taking into account multiple metrics, such as loss ratio, interference ratio, load at the gateways and end-to end delay. Simulation results show that RLBDR can significantly improve the overall network performance compared to schemes using either Metric of Interference and Channel switching, Best Path to Best Gateway, Expected Transmission count, nearest gateway (i.e., shortest path to gateway) or load at gateways as a metric for path selection.     

Comparative analysis of link quality metrics and routing protocols for optimal route construction in wireless mesh networks

We provide a comparative analysis of various routing strategies that affect the end-to-end performance in wireless mesh networks. We first improve well-known link quality metrics and routing algorithms to enhance performance in wireless mesh environments. We then investigate the route optimality, i.e., whether the best end-to-end route with respect to a given link quality metric is established, and its impact on the network performance. Network topologies, number of concurrent flows, and interference types are varied in our evaluation and we find that a non-optimal route is often established because of the routing protocol’s misbehavior, inaccurate link metric design, interflow interference, and their interplay. Through extensive simulation analysis, we present insights on how to design wireless link metrics and routing algorithms to enhance the network capacity and provide reliable connectivity.     

Routing metric of interference-aware link quality： an improved ETX in wireless mesh networks

This article addresses the problem of route selection in wireless mesh networks （WMNs）. The traditional routing metrics adopt packet delivery ratio （PDR） as a representative metric of wireless link quality assessment. However, PDR measured by the broadcast-based probe method is affected by the size, number and transmission rate of probe packets, which influences the metric accuracy. In this paper, improved expected transmission count （iETX）, a new routing metric of interference-aware link quality, is proposed for WMNs. Dispensing with traditional broadcast-based probing method, the iETX uses regional physical interference model to obtain PDR. Regional physical interference model is built upon the relationship between signal to interference plus noise ratio （SINR） and PDR, which contributes to the improvement of metric accuracy. The iETX comprehensively considers the effects of interference and link quality and minimizes the expected number of packet transmissions required for successful delivery, which helps find a path with minimum interference and high throughput. Simulation shows that the proposed metric can significantly improve the network performance.     

An adaptive load-aware routing algorithm for multi-interface wireless mesh networks

In wireless mesh networks, the number of gateway nodes are limited, when the nodes access to the internet by fixed gateway node, different requirements of nodes lead to the dataflow shows heterogeneity. Many new routing metrics and algorithms existing in traditional wired networks and the Ad Hoc network, can not be directly applied to wireless mesh networks, so how to design a routing metric and algorithm which can dynamically adapt to current networks topology and dataflow changes, avoid bottleneck node, and select the most stable and least congestion link to establish a route is very important. In this paper, we presented a new dynamic adaptive channel load-aware metric (LAM) to solve the link load imbalance caused by inter-flow and inner-flow interference, designed a self-adaptive dynamic load balancing on-demand routing algorithm through extending and improving AODV routing method with the LAM, to achieve flow balance, reduce the high packet loss ratio and latency because congestion and Packet retransmission, and can increase Network Throughput.     

基于可靠路径稳定性估计的MANET路由发现算法研究

提出一种基于可靠路径剩余生存期（RPL, residual path lifetime）估计的MANET路由发现算法（RLE-RPLP）,该算法充分考虑相邻链路剩余生存期相关性,建立优化的多跳路径RPL统计特性分析,提供了更可靠的路由稳定性评估。通过仿真分别与忽略链路RLL相关性的源路由协议及已有稳定性路由协议进行对比。仿真结果表明,RLE-RPLP算法能有效提高网络吞吐量并减少路由重建次数;当节点移动度较高或网络负载较大时,在吞吐量、路由开销等方面均优于已有的稳定性路由对比算法。     

M_CSPF: A Scalable CSPF Routing Scheme with Multiple QoS Constraints for MPLS Traffic Engineering

In the context of multi‐protocol label switching (MPLS) traffic engineering, this paper proposes a scalable constraint‐based shortest path first (CSPF) routing algorithm with multiple QoS metrics. This algorithm, called the multiple constraint‐based shortest path first (M_CSPF) algorithm, provides an optimal route for setting up a label switched path (LSP) that meets bandwidth and end‐to‐end delay constraints. In order to maximize the LSP accommodation probability, we propose a link weight computation algorithm to assign the link weight while taking into account the future traffic load and link interference and adopting the concept of a critical link from the minimum interference routing algorithm. In addition, we propose a bounded order assignment algorithm (BOAA) that assigns the appropriate order to the node and link, taking into account the delay constraint and hop count. In particular, BOAA is designed to achieve fast LSP route computation by pruning any portion of the network topology that exceeds the end‐to‐end delay constraint in the process of traversing the network topology. To clarify the M_CSPF and the existing CSPF routing algorithms, this paper evaluates them from the perspectives of network resource utilization efficiency, end‐to‐end quality, LSP rejection probability, and LSP route computation performance under various network topologies and conditions.     

EPTR: expected path throughput based routing protocol for wireless mesh network

For effective routing in wireless mesh networks, we proposed a routing metric, expected path throughput (EPT), and a routing protocol, expected path throughput routing protocol (EPTR), to maximize the network throughput. The routing metric EPT is based on the estimated available bandwidth of the routing path, considering the link quality, the inter- and intra-flow interference and the path length. To calculate the EPT of a routing path, we first calculate the expected bandwidth of the link and the clique, and then consider the decay caused by the path length. Based on EPT, a distributed routing protocol EPTR is proposed, aiming to balance the network load and maximize the network throughput. Extensive simulations are conducted to evaluate the performance of the proposed solution. The results show that the proposed EPTR can effectively balance the network load, achieve high network throughput, and out-perform the existing routing protocols with the routing metrics previously proposed for wireless mesh networks.     

High throughput route selection in multi-rate wireless mesh networks

Most existing Ad-hoc routing protocols use the shortest path algorithm with a hop count metric to select paths. It is appropriate in single-rate wireless networks, but has a tendency to select paths containing long-distance links that have low data rates and reduced reliability in multi-rate networks. This article introduces a high throughput routing algorithm utilizing the multi-rate capability and some mesh characteristics in wireless fidelity （WiFi） mesh networks. It uses the medium access control （MAC） transmission time as the routing metric, which is estimated by the information passed up from the physical layer. When the proposed algorithm is adopted, the Ad-hoc on-demand distance vector （AODV） routing can be improved as high throughput AODV （HT-AODV）. Simulation results show that HT-AODV is capable of establishing a route that has high data-rate, short end-to-end delay and great network throughput.     

An efficient cooperative hybrid routing protocol for hybrid wireless mesh networks

Hybrid wireless mesh networks are the most generic types of wireless mesh networks. Unlike static mesh routers, which have multiple radio interfaces and almost no energy constraint, mobile mesh clients are usually equipped with a single radio interface and have energy limitations. A cooperative hybrid routing protocol (CHRP) combining advantages of proactive and reactive routing protocols by letting them work cooperatively is proposed in this paper, which can adapt to features of both routers and clients. In CHRP, in order to make a proper route selection, channel condition, interference and constrained energy of clients are considered in the node-aware routing metric. Besides, a cross-layer approach is used in CHRP. Both gateway and client oriented data flows are considered comprehensively. The simulation results using ns-3 show the advantage of the proposed CHRP in terms of average packet loss rate, average latency, average network throughput, average energy consumption of clients and the minimum residual energy of clients.     

Gateway Placement for Throughput Optimization in Wireless Mesh Networks

In this paper, we address the problem of gateway placement for throughput optimization in multi-hop wireless mesh networks. Assume that each mesh node in the mesh network has a traffic demand. Given the number of gateways to be deployed (denoted by k) and the interference model in the network, we study where to place exactly k gateways in the mesh network such that the total throughput is maximized while it also ensures a certain fairness among all mesh nodes. We propose a novel grid-based gateway deployment method using a cross-layer throughput optimization, and prove that the achieved throughput by our method is a constant times of the optimal. Simulation results demonstrate that our method can effectively exploit the available resources and perform much better than random and fixed deployment methods. In addition, the proposed method can also be extended to work with multi-channel and multi-radio mesh networks under different interference models.     

Enhancing the Performance of Video Streaming in Wireless Mesh Networks

Multihop wireless mesh networks (WMNs) provide ubiquitous wireless access in a large area with less dependence on wired networks. However, some emerging applications with high bandwidth requirement and delay and loss constraints, such as video streaming, suffer poor performance in WMNs, since high compression rates and/or high packet loss rates deteriorate the video quality. In this paper, we propose a novel mechanism composed of (1) a network route selection scheme which provides paths for multiple video streams with the least interference, called Minimum Interference Route Selection (MIROSE) and (2) an optimization algorithm that determines the compression rates depending on the network condition, called Network State Dependent Video Compression Rate (NSDVCR) algorithm. Simulation results of the proposed mechanisms show the significant improvement of the video quality measured with a popular metric, Peak-Signal-to-Noise Ratio (PSNR), compared with standard routing and default compression rates.     

Interference aware routing for mobile ad hoc networks based on node＇s sending and receiving capabilities

How to efficiently build routes among nodes is increasing important for mobile ad hoc networks （MANETs）. This paper puts forward an interference aware routing protocol called Interference aware cross layer routing protocol （IA-CLR） for MANETs based on the IEEE 802.11 medium access layer （MAC）. By defining the node＇s sending and receiving capabilities, IA-CLR can indicate the interference strength of the link in a real and comprehensive way. Further more, in order to choose the route with minimum bottleneck link interference, a new routing metric is proposed by combining the MAC layer and the network layer for cross layer design. Simulation results show that IA-CLR can significantly improve the performances of network such as the average end-to-end delay, the packets loss ratio and the throughput.     

Weighted dominating set based routing for ad hoc communications in emergency and rescue scenarios

Disasters create emergency situations and the services provided must be coordinated quickly via a communication network. Mobile adhoc networks (MANETs) are suited for ubiquitous communication during emergency rescue operations, since they do not rely on infrastructure. The route discovery process of on-demand routing protocols consumes too much bandwidth due to high routing overhead. Frequent route changes also results in frequent route computation process. Energy efficiency, quick response time, and scalability are equally important for routing in emergency MANETs. In this paper, we propose an energy efficient reactive protocol named Weighted-CDSR for routing in such situations. This protocol selects a subset of network nodes named Maximum Weighted Minimum Connected Dominating Set (MWMCDS) based on weight, which consists of link stability, mobility and energy. The MWMCDS provides the overall network control and data forwarding support. In this protocol, for every two nodes u and v in the network there exists a path between u and v such that all intermediate nodes belong to MWMCDS. Incorporating route stability into routing reduces the frequency of route failures and sustains network operations over an extended period of time. With fewer nodes providing overall network control and data forwarding support, the proposed protocol creates less interference and consumes less energy. The simulation results show that the proposed protocol is superior to other protocols in terms of packet delivery ratio, control message overhead, transmission delay and energy consumption.     

Calcul des métriques de routage pour Internet

In spite of the development of Internet networks and the important volume of literature dealing with Internet routing, many fundamental topics were not addressed. Traffic is, in principle, routed through shortest paths, in sense of a set of link weights (a metric). These weights do not necessarily have a physical significance and could be modified by the network administrator to change the routing policy and the network cost. In this paper, we give precise answers for the following questions: 1/ Given a network topology, is there a metric such that, first, the shortest path between any pair of vertices is unique and, second, every link belongs to at least one shortest path ? 2/ How can we compute such a metric ? 3/ Can we choose a metric satisfying these constraints and whose values are small integers ? 4/ If the routers of the network have differents functions and caracteristics, is it possibe to determine a metric which allows to route traffic, taking into account these heteregeneous caracteristics ? 5/ If some routing paths are seleceted due to technical or economical reasons, can we find a metric enforcing this given routing policy ? 6/ If this is not possible, what should we do to compute a metric that is as close as possible to the selected routing paths ?     

Tandem Queue Models with Applications to QoS Routing in Multihop Wireless Networks

We consider the problem of quality of service (QoS) routing in multi-hop wireless networks where data are transmitted from a source node to a destination node via multiple hops. The routing component of a QoS-routing algorithm essentially involves the link and path metric calculation which depends on many factors such as the physical and link layer designs of the underlying wireless network, transmission errors due to channel fading and interference, etc. The task of link metric calculation basically requires us to solve a tandem queueing problem which is the focus of this paper. We present a unified tandem queue framework which is applicable for many different physical layer designs. We present both exact and approximated decomposition approaches. Using the queueing framework, we can derive different performance measures, namely, end-to-end loss rate, end-to-end average delay, and end-to-end delay distribution. The proposed decomposition approach is validated and some interesting insights into the system performance are highlighted. We then present how to use the decomposition queueing approach to calculate the link metric and incorporate this into the route discovery process of the QoS routing algorithm. The extension of the queueing and QoS routing framework to wireless networks with class-based queueing for QoS differentiation is also presented.     

Design and Performance Evaluation of IAR: Interference-Aware Routing Metric for Wireless Mesh Networks

Multihop wireless mesh networks are an attractive solution for providing last-mile connectivity. However, the shared nature of the transmission medium makes it challenging to fully exploit these networks. In an attempt to improve the radio resource utilization, several routing metrics have been specifically designed for wireless mesh networks. However none of these routing metrics efficiently tackles interference issues. Moreover, although some evaluations have been conducted to assess the performance of these metrics in some contrived scenarios, no overall comparison has been performed. The contributions of this paper are consequently twofold. First, we propose a new routing metric, Interference-Aware Routing metric (IAR), specifically designed for WMNs. IAR uses MAC-level information to measure the share of the channel that each link is able to utilize effectively. As a result, paths that exhibit the least interference will be selected to route the data traffic. Then we evaluate the performance of IAR against some of the most popular routing metrics currently used in wireless mesh networks: Hop Count, Blocking Metric, Expected Transmission Count (ETX), Expected Transmission Time (ETT), Modified ETX (mETX), Network Allocation Vector Count (NAVC) and Metric of Interference and Channel-Switching (MIC). We show under various simulation scenarios that IAR performs the best in terms of end-to-end delay and packet loss, and provides the fairest resource utilization.     

Integrating machine learning in ad hoc routing: A wireless adaptive routing protocol

The nodes in a wireless ad hoc network act as routers in a self‐configuring network without infrastructure. An application running on the nodes in the ad hoc network may require that intermediate nodes act as routers, receiving and forwarding data packets to other nodes to overcome the limitations of noise, router congestion and limited transmission power. In existing routing protocols, the ‘self‐configuring’ aspects of network construction have generally been limited to the construction of routes that minimize the number of intermediate nodes on a route while ignoring the effects that the resulting traffic has on the overall communication capacity of the network. This paper presents a context‐aware routing metric that factors the effects of environmental noise and router congestion into a single time‐based metric, and further presents a new cross‐layer routing protocol, called Warp‐5 (Wireless Adaptive Routing Protocol, Version 5), that uses the new metric to make better routing decisions in heterogeneous network systems. Simulation results for Warp‐5 are presented and compared to the existing, well‐known AODV (Ad hoc On‐Demand Distance Vector) routing protocol and the reinforcement‐learning based routing protocol, Q‐routing. The results show Warp‐5 to be superior to shortest path routing protocols and Q‐routing for preventing router congestion and packet loss due to noise. Copyright © 2011 John Wiley & Sons, Ltd.     

An integrated routing and rate adaptation framework for multi-rate multi-hop wireless networks

In this paper, we propose a new integrated framework for joint routing and rate adaptation in multi-rate multi-hop wireless networks. Unlike many previous efforts, our framework considers several factors that affect end-to-end performance. Among these factors, the framework takes into account the effect of the relative positions of the links on a path when choosing the rates of operation and the importance of avoiding congested areas. The key element of our framework is a new comprehensive path metric that we call ETM (for expected transmission cost in multi-rate wireless networks). We analytically derive the ETM metric. We show that the ETM metric can be used to determine the best end-to-end path with a greedy routing approach. We also show that the metric can be used to dynamically select the best transmission rate for each link on the path via a dynamic programming approach. We implement the ETM-framework on an indoor wireless mesh network and compare its performance with that of frameworks based on the popular ETT and the recently proposed ETOP metrics. Our experiments demonstrate that the ETM-framework can yield throughput improvements of up to 253 and 368 % as compared with the ETT and ETOP frameworks.     

Routing Algorithm for Maximizing Lifetime of Wireless Sensor Network for Broadcast Transmission

This paper addresses the problem of optimal resource allocation in a multi-hop cognitive radio networks. The objective of the present work is to search for the shortest possible path from the source to the destination and explores the scope of the Bellman–Ford and the Dijkstra’s algorithms due to their low runtime complexity and ease of implementation in routing. Searching for the shortest path focuses on minimization to the outage probability, while satisfying simultaneously the limits of the total transmit power and the interference threshold to the primary user (PU). Fuzzy c-means clustering is used to speed up the route selection process for both the routing algorithms. Network lifetime is also studied for both the algorithms considering the link failure situation. Simulation results show that the proposed scheme not only minimizes the outage probability over the existing power allocation strategies but also reduces interference to the PU. Results also show that network lifetime is increased and faster route selection is possible.     

Evaluating a cross-layer approach for routing in Wireless Mesh Networks

Routing in Wireless Mesh Networks is challenging due to the unreliable characteristics of the wireless medium. Traditional routing paradigms are not able to propose an efficient solution to this problem. Further, Gupta et al. demonstrated that the average throughput capacity per node of a wireless multi-hop network decreases as 1/n, where n is the number of nodes in the network. Recent studies have shown that a cross-layer approach is a promising solution to get closer to the theoretic throughput capacity bound. Cross-layer solutions have been already proposed either for specific TDMA/CDMA networks or for power-efficient routing protocols. These proposals are strongly MAC dependent, or suffer from targeting a steady state offering the best trade-off performance. In this paper, the problem we tackle in a more general context, disregarding the specific MAC and Physical layers technologies, can be formulated as follows: How to design a routing algorithm able to increase the average throughput capacity experienced by Wireless Mesh Networks? Starting from a theoretic result, we analyze the gain that a cross-layer approach can deliver, the metrics suitable to improve throughput capacity, and the power control policy that reduces interference. We take a MAC independent approach, focusing on the general characteristics of wireless links, targeting the improvement of throughput capacity in Wireless Mesh Networks. Our proposal performs path selection and power optimization based on three metrics, namely physical transmission rate, interference, and packet error rate. Performances are thoroughly analyzed and evaluated by extensive simulations, with both TCP and UDP traffic, and compared to other multi-hop routing protocols. For both kind of traffic, the simple heuristic we propose here allows to double the average throughput the network is able to route.