Exploiting path diversity in the link layer in wireless ad hoc networks

We develop an anycast mechanism at the link layer for wireless ad hoc networks. The goal is to exploit path diversity in the link layer by choosing the best next hop to forward packets when multiple next hop choices are available. Such choices can come from a multipath routing protocol, for example. This technique can reduce transmission retries and packet drop probabilities in the face of channel fading. We develop an anycast extension of the IEEE 802.11 MAC layer based on this idea. We implement the protocol in an experimental proof-of-concept testbed using the Berkeley motes platform and S-MAC protocol stack. We also implement it in the popular ns-2 simulator and experiment with the AOMDV multipath routing protocol and Ricean fading channels. We show that anycast performs significantly better than 802.11 in terms of packet delivery, particularly when the path length or effect of fading is large. Further we experiment with anycast in networks that use multiple channels and those that use directional antennas for transmission. In these networks, deafness and hidden terminal problems are the main source of packet loss. We implemented anycast as extension of 802.11 like protocols that were proposed for these special networks. We are able to show that anycast is capable of enhancing the performance of these protocols by simply making use of the path diversity whenever it is available.     

Estimating the channel capacity of multi-hop IEEE 802.11 wireless networks

In IEEE 802.11 wireless networks, the residual capacity of the wireless links should be accurately estimated to realize advanced network services such as flow admission control or load balancing. In this paper, we propose an algorithm that estimates the packet delivery failure probability by collecting transmission statistics from nearby nodes, and by using a basic collision detection mechanism. This probability is then used in an analytical model to calculate the maximum allowable traffic needed to reach the saturation condition. We show by simulations that estimation error is within 0.5–5.0%, which is significantly lower than the best performance of prior estimation methods. We also demonstrate that the flow admission control is successfully achieved in a realistic wireless network scenario by the help of accurate link residual bandwidth estimation, where the unsatisfied traffic demand remain bounded at a negligibly low level. A routing algorithm that finds max–min residual bandwidth path between source and destination nodes is also implemented, and simulation results show that the network throughput achieved by this algorithm significantly exceeds that of other popular mesh routing protocols. Finally, we provide test results from the real implementation of our algorithm on 802.11 wireless equipment, which are consistent with the simulations.     

Improving routing performance in wireless ad hoc networks using cross-layer interactions

This article presents a combined layer two and three control loop, which allows prediction of link breakage in wireless ad hoc networks. The method monitors the physical layer transmission mode on layer two and exploits the gained knowledge at layer three. The mechanism bases on link adaptation, which is used in IEEE 802.11a WLAN to select the transmission mode according to the link quality. The process of link adaptation contains information that is useful to predict link stability and link lifetime. After introducing the IEEE 802.11a Medium Access Control (MAC) and PHY layer, we present insight to the IEEE 802.11a link adaptation behaviour in multi-hop ad hoc networks. The link adaptation algorithm presented here is derived from Auto Rate Fallback (ARF) algorithm. We survey the performance gain of two newly developed route adaptation approaches exploding the prediction results. One approach is Early Route ReArrangement (ERRA) that starts a route reconstruction procedure before link breakage. Hence, an alternative route is available before connectivity is lost. Early Route Update (ERU) is a complementing approach that enhances this process, by communications among routing nodes surrounding the breaking link. The delay caused by route reconstruction can be significantly reduced if prediction and either of our new route discovery processes is used.     

EFT: a high throughput routing metric for IEEE 802.11s wireless mesh networks

In this paper, we present a throughput-maximizing routing metric, referred to as expected forwarding time (EFT), for IEEE 802.11s-based wireless mesh networks. Our study reveals that most of the existing routing metrics select the paths with minimum aggregate transmission time of a packet. However, we show by analyses that, due to the shared nature of the wireless medium, other factors, such as transmission time of the contending nodes and their densities and loads, also affect the performance of routing metrics. We therefore first identify the factors that hinder the forwarding time of a packet. Furthermore, we add a new dimension to our metric by introducing traffic priority into our routing metric design, which, to the best of our knowledge, is completely unaddressed by existing studies. We also show how EFT can be incorporated into the hybrid wireless mesh protocol (HWMP), the path selection protocol used in the IEEE 802.11s draft standard. Finally, we study the performance of EFT through simulations under different network scenarios. Simulation results show that EFT outperforms other routing metrics in terms of average network throughput, end-to-end delay, and packet loss rate.     

Effectiveness of Reliable Routing Protocols in Mobile Ad Hoc Networks

Due to unpredictable topology change and frequent link failure, it becomes evident major challenge to provide the stable route between source and destination in mobile ad hoc networks. Unlike previous multipath routing schemes for redundancy and unicast routing protocol utilizing the longest route expiration time measured by geographical information supported by Global Positioning System (GPS), we develop a framework to establish the most stable route based on measured frequency of link failure, available battery as well as the number of actual connections. To evaluate performance of proposed scheme, we provide practical simulation results for multipath and unicast routing protocol in terms of packet delivery ratio, control overhead, average hop length as well as end-to-end delay. Through analysis of simulation results, we demonstrate that our scheme shows better performance than general unicast routing protocol as well as similar packet delivery ratio to multipath routing protocol with less maintenance overhead. Ki-Il Kim received the M.S. and Ph.D. degrees in computer science from the Chungnam National University, Daejeon, Korea, in 2002 and 2005, respectively. He is currently with Department of Information Science, Gyeongsang National University as a faculty member. His research interests include routing for MANET, QoS in wireless network, multicast, and sensor networks. Sang-Ha Kim received the B.S. degree in chemistry from Seoul National University, Seoul, Korea, in 1980. He received the M.S. and Ph.D. degrees in quantum scattering and computer science from the University of Houston, Houston, TX, in 1984 and 1989, respectively. From 1990 to 1991, he was with the Supercomputing Center, SERI, Korean Institute of Science and Technology (KIST) as Senior Researcher. He joined Chungnam National University, Daejeon, Korea, in 1992, where he is a Professor. His current research interests include wireless networks, ad hoc networks, QoS, optical networks, and network analysis.     

Graph coloring based channel assignment framework for rural wireless mesh networks

IEEE 802.11 based wireless mesh networks with directional antennas are expected to be a new promising technology and an economic approach for providing wireless broadband services in rural areas. In this paper, we discuss interference models and address how they can affect the design of channel assignment in rural mesh networks. We present a new channel assignment framework based on graph coloring for rural wireless mesh networks. The goal of the framework is to allow synchronously transmitting or receiving data from multiple neighbor links at the same time, and continuously doing full-duplex data transfer on every link, creating an efficient rural mesh network without interference. Channel assignment is shown to be NP-hard. We frame this channel allocation problem in terms of Adjacent Vertex Distinguishing Edge Coloring （AVDEC）. Detailed assignment results on grid topology are presented and discussed. Furthermore, we design an algorithm. Finally, we evaluate the perform- ance of the proposed algorithm through extensive simulations and show the algorithm is effective to the regular grid topologies, and the number of colors used by the algorithm is upper bounded by A ~ 1. Hence the algorithm guarantees that the number of channels available in standards such as IEEE 802.11a is sufficient to have a valid AVDEC for many grid topologies. We also evaluate the proposed algorithm for arbitrary graphs. The algorithm provides a lower upper bound on the minimum number of channels to the AVDEC index channel assignment problem.     

Assessing the IEEE 802.11e QoS effectiveness in multi-hop indoor scenarios

The IEEE 802.11e technology is receiving much interest due to the enhancements offered to wireless local area networks in terms of QoS. Other application fields for this technology are wireless ad hoc networks, wireless mesh networks, and vehicular ad hoc networks. In the literature, most of the research works available focusing on the IEEE 802.11e technology offer simulation results alone, being hard to find empirical results of implementations that prove its effectiveness in realistic scenarios. Additionally, we consider that studies of IEEE 802.11e based on simulation platforms have not been thoroughly validated using real-life results. In this work we analyze the performance of the IEEE 802.11e technology in real multi-hop ad hoc networks. With this purpose we first we devise a set of experiments where we compare the results obtained on a small testbed to those from the ns-2 simulation platform. A significant consistency in terms of overall trends is found, although remarkable differences can be appreciated in terms of both delay and throughput results. Afterward we proceed with a full deployment of IEEE 802.11e enabled stations throughout the floor of an university building, performing several experiments using both static and dynamic routing. Experimental results show that QoS can be reasonably sustained for both voice and video traffic in multi-hop ad hoc networks, although dynamic routing protocols can hinder performance by provoking frequent on-off connectivity problems.     

一种环境感知的无线Mesh网络自适应QoS路径选择算法

本文针对如何改善无线多跳Mesh网络的服务质量,满足无线多媒体业务对数据传输的带宽、时延、抖动的要求等问题,研究了一种基于无线信道状态和链路质量统计的MAC层最大重传次数的自适应调整算法。该算法通过对无线Mesh网络的无线信道环境的动态感知,利用分层判断法区分无线分组丢失的主要原因是无线差错还是网络拥塞导致,实时调整MAC层的最佳重传次数,降低无线网络中的分组冲突概率。基于链路状态信息的统计和最大重传策略,提出了一种启发式的基于环境感知的QoS路由优化机制HEAOR。该算法通过动态感知底层链路状态信息,利用灰色关联分析法自适应选择最优路径,在不增加系统复杂度的基础上,减少链路误判概率,提高传输效率。NS2仿真结果表明,HEAOR算法能有效减少重路由次数,降低链路失效概率,提高网络的平均吞吐率。本文提出的方法不仅能够优化MAC层的重传,而且通过发现跨层设计的优化参数实现对路径的优化选择。      

Multi-radio multi-channel routing metrics in IEEE 802.11s based wireless mesh networks

IEEE 802.11s is one of the emerging standards designed to build wireless mesh networks which may serve to extend the coverage of access networks. The default IEEE 802.11s path selection protocol Hybrid Wireless Mesh Protocol (HWMP) is based on the radio-aware airtime link metric (ALM) that outperforms the hop-count metric in single channel multi-hop wireless networks. However, this metric may lead to capacity degradation when multiple channels and/or multi-radio are used. To fully exploit the capacity gain of multiple channels use, new routing metrics have been proposed such as weighted cumulative expected transmission time, metric of interference and channel switching, interference aware routing metric, exclusive expected transmission time, and normalized bottleneck link capacity. These metrics distribute the data traffic load among channels and/or radios to reach the final destination. In this paper, we provide a qualitative comparison study that considers the characteristics of these metrics. Indeed, we substitute ALM by these different metrics, and we evaluate the performance of HWMP through simulation. Obtained results allow us to identify the appropriate use case of each metric.     

Route selection in IEEE 802.11 wireless mesh networks

This paper addresses the problem of route selection in IEEE 802.11 based Wireless Mesh Networks (WMNs). Traditional routing protocols choose the shortest path between two routers. However, recent research reveals that there can be enormous differences between links in terms of quality (link loss ratio, interference, noise etc) and therefore selecting the shortest path (hop count metric) is a poor choice. We propose a novel routing metric—Expected Link Performance (ELP) metric for wireless mesh networks which takes into consideration multiple factors pertaining to quality (link loss ratio, link capacity and link interference) to select the best end-to-end route. Simulation based performance evaluation of ELP against contemporary routing metrics shows an improvement in terms of throughput and delay. Moreover, we propose an extension of the metric called ELP-Gateway Selection (ELP-GS) which is an extension meant for traffic specifically oriented towards the gateway nodes in the mesh network. We also propose a gateway discovery protocol which facilitates the dissemination of ELP-GS in the network. Simulation results for ELP-GS show substantial improvement in performance.     

Goodput analysis and link adaptation for IEEE 802.11a wireless LANs

Link adaptation to dynamically select the data transmission rate at a given time has been recognized as an effective way to improve the goodput performance of the IEEE 802.11 wireless local-area networks (WLANs). Recently, with the introduction of the new high-speed 802.11a physical layer (PHY), it is even more important to have a well-designed link adaptation scheme work with the 802.11a PHY such that its multiple transmission rates can be exploited. In this paper, we first present a generic method to analyze the goodput performance of an 802.11a system under the distributed coordination function (DCF) and express the expected effective goodput as a closed-form function of the data payload length, the frame retry count, the wireless channel condition, and the selected data transmission rate. Then, based on the theoretical analysis, we propose a novel MPDU (MAC protocol data unit)-based link adaptation scheme for the 802.11a systems. It is a simple table-driven approach and the basic idea is to preestablish a best PHY mode table by applying the dynamic programming technique. The best PHY mode table is indexed by the system status triplet that consists of the data payload length, the wireless channel condition, and the frame retry count. At runtime, a wireless station determines the most appropriate PHY mode for the next transmission attempt by a simple table lookup, using the most up-to-date system status as the index. Our in-depth simulation shows that the proposed MPDU-based link adaptation scheme outperforms the single-mode schemes and the autorate fallback (ARF) scheme-which is used in Lucent Technologies' WaveLAN-II networking devices-significantly in terms of the average goodput, the frame drop rate, and the average number of transmission attempts per data frame delivery.     

On selecting the best transmission mode for WiFi devices

The design of efficient IEEE 802.11 physical (PHY) rate adaptation algorithms is a challenging research topic and usually the issues surrounding their implementations on real 802.11 devices are not disclosed. In this paper, we identify and evaluate the key parameters to design such algorithms. We then present a survey on existing PHY rate adaptation mechanisms and discuss their advantages and drawbacks. We also propose three new 802.11 PHY rate adaptation mechanisms, named adaptive auto rate fallback (AARF), closed loop adaptive rate allocation (CLARA), and adaptive multi‐rate retry (AMRR). AARF, proposed for low‐latency systems, has low complexity and obtains similar performance than RBAR in stationary and non‐fading wireless channels. CLARA is a culmination of the best attributes of the transmitter‐based ARF and RBAR control mechanisms with additional practical features such as adaptive fragmentation to improve multipath‐fading channel sensing and to provide feedback control signaling. AMRR is designed for high‐latency systems; it has been implemented and evaluated on an AR5212‐based device. Experimentation results show more than 20% performance improvement in throughput over the default algorithm implemented in the AR5212 MADWIFI driver. Copyright © 2008 John Wiley & Sons, Ltd.     

Diverse routing in optical mesh networks

We study the diverse routing problem in optical mesh networks. We use a general framework based on shared risk link groups to model the problem. We prove that the diverse routing problem is indeed NP-complete, a result that has been conjectured by several researchers previously. In fact, we show that even the fiber-span-disjoint paths problem, a special case of the diverse routing problem, is also NP-complete. We then develop an integer linear programming formulation and show through numerical results that it is a very viable method to solve the diverse routing problem for most optical networks found in many applications which typically have no more than a few hundred nodes and fiber spans.     

Efficient routing for wireless mesh networks using a backup path

Wireless mesh networks (WMNs) have a proven record in providing viable solutions for some of the fundamental issues in wireless networks such as capacity and range limitations. WMN infrastructure includes clusters of mobile ad‐hoc networks connected through a fixed backbone of mesh routers. The mesh network can be constrained severely because of various reasons, which could result in performance degradation such as a drop in throughput or long delays. Solutions to this problem often focus on multipath or multichannel extensions to the existing ad‐hoc routing protocols. In this paper, we propose a novel solution by introducing an alternative path to the mesh backbone that traverses the mobile ad‐hoc networks part of the WMN. The new routing solution allows the mobile nodes (MNs) to establish direct communication among peers without going through the backbone. The proposed alternative ad‐hoc path is used only when the mesh backbone is severely constrained. We also propose, for the first time in WMNs, using MNs with two interfaces, one used in the mesh backbone communication and the other engaged in the ad‐hoc network. A scheme is presented for making the MN aware of link quality measures by providing throughput values to the ad‐hoc on‐demand distance vector protocol. We use piggybacking on route reply messages in ad‐hoc on‐demand distance vector to avoid incurring additional costs. We implemented our solution in an OPNET simulator and evaluated its performance under a variety of conditions. Simulation results show that the alternative ad‐hoc path provides higher throughput and lower delays. Delay analysis show that the throughput improvement does not impose additional costs. Copyright © 2012 John Wiley & Sons, Ltd.     

A Cross-Layer Framework for Association Control in Wireless Mesh Networks

The user association mechanism specified by the IEEE 802.11 standard does not consider the channel conditions and the AP load in the association process. Employing the mechanism in its plain form in wireless mesh networks we may only achieve low throughput and low user transmission rates. In this paper we design a new association framework in order to provide optimal association and network performance. In this framework we propose a new channel-quality based user association mechanism inspired by the operation of the infrastructure-based WLANs. Besides, we enforce our framework by proposing an airtime-metric based association mechanism that is aware of the uplink and downlink channel conditions as well as the communication load. We then extend the functionality of this mechanism in a cross-layer manner taking into account information from the routing layer, in order to fit it in the operation of wireless mesh networks. Lastly, we design a hybrid association scheme that can be efficiently applied in real deployments to improve the network performance. We evaluate the performance of our system through simulations and we show that wireless mesh networks that use the proposed association mechanisms are more capable in meeting the needs of QoS-sensitive applications.     

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.     

Understanding interference and carrier sensing in wireless mesh networks [Accepted from Open Call]

Wireless mesh networks aim to provide high-speed Internet service without costly network infrastructure deployment and maintenance. The main obstacle in achieving high-capacity wireless mesh networks is interference between the mesh links. In this article, we analyze the carrier sensing and interference relations between two wireless links and measure the impact of these relations on link capacity on an indoor 802.11a mesh network testbed. We show that asymmetric carrier sensing and/or interference relations commonly exist in wireless mesh networks, and we study their impact on the link capacity and fair-channel access. In addition, we investigate the effect of traffic rate on link capacity in the presence of interference.     

An Investigation of Link Quality Assessment for Mobile Multi-hop and Multi-rate Wireless Networks

Wireless ad hoc networks will be an important component in future communication systems. The performance of wireless ad hoc networks can be improved by link quality-aware applications. Wireless link quality is dynamic in nature, especially in mobile scenarios. Therefore, accurate and fast packet delivery ratio estimation is a prerequisite to good performance in mobile, multi-hop and multi-rate wireless ad hoc networks. In this paper, we propose a novel packet delivery ratio estimation method that improves the accuracy and responsiveness of the packet delivery ratio estimation. The proposed link quality estimation components are implemented in a IEEE 802.11b/g test-bed. The experiment results show that the accuracy of the packet delivery ratio estimation can improve up to 50% in mobile scenarios without introducing overhead. We also show the end-to-end performance impact of this improved estimation on route selection using different routing metrics and configurations. The measurement results show that our packet delivery ratio method leads to better route selection in the form of increased end-to-end throughput compared to traditional methods, which respond slowly to the link dynamics.     

Robust Routing and Scheduling in Wireless Mesh Networks under Dynamic Traffic Conditions

Joint routing-and-scheduling has been considered in wireless mesh networks for its significant performance improvement. While existing work assumes it, accurate traffic information is usually not available due to traffic dynamics, as well as inaccuracy and delay in its measurement and dissemination. In addition, the joint routing and scheduling usually requires a centralized controller to calculate the optimal routing and scheduling and distribute such policies to all the nodes. Thus, even if the accurate traffic information is always available, the central controller has to compute the routing and scheduling repeatedly because the traffic demands change continuously. This leads to prohibitive computation and distribution overhead. Therefore, in this paper, we propose a joint routing-scheduling scheme that achieves robust performance under traffic information uncertainty. In particular, it achieves worst-case optimal performance under a range of traffic conditions. This unique feature validates the use of centralized routing and scheduling in wireless mesh networks. As long as the traffic variation is within the estimation range, the routing and scheduling do not need to be recomputed and redistributed. Through extensive simulations, we show that our proposed scheme meets the objective (i.e., optimizes the worst-case performance). Moreover, although it only guarantees the worst-case performance in theory, its average performance is also good. For example, our proposed scheme can perform better than a fixed optimal routing and scheduling scheme in more than 80 percent of 500 random traffic instances. Our scheme provides insights on the desired properties of multipath routing, namely, spatial reuse and load balancing.