MrFair: Misbehavior-resistant fair scheduling in wireless mesh networks

It is a critical issue to ensure that nodes and/or flows have fair access to the network bandwidth in wireless mesh networks (WMNs). However, current WMNs based on IEEE 802.11 exhibit severe unfairness. Several scheduling schemes have been proposed to ensure fairness in WMNs. Unfortunately, all of them implicitly trust nodes in the network, and thus are vulnerable to the misbehavior of nodes participating in scheduling. In this paper, we address the threats to fair scheduling in WMNs resulting from node misbehavior and present a generic verification framework to detect such misbehavior. Moreover, we develop two verification schemes based on this framework for distributed and centralized authentication environments, respectively. We validate our approach by extending an existing fair scheduling scheme and evaluating it through simulation. The results show that our approach improves misbehavior detection with light performance overhead.     

Price-based max-min fair rate allocation in wireless multi-hop networks

The interaction between links in wireless multihop networks introduces extra constraints on the combinations of achievable flow rates. Algorithms have been proposed to achieve max-min fairness under these additional constraints. This letter provides a simple price-based max-min fair rate allocation scheme, building on a utility maximization scheme recently proposed for such networks.     

Cross-layer adaptive control for wireless mesh networks

This paper investigates optimal routing and adaptive scheduling in a wireless mesh network composed of mesh clients and mesh routers. The mesh clients are power constrained mobile nodes with relatively little knowledge of the overall network topology. The mesh routers are stationary wireless nodes with higher transmission rates and more capabilities. We develop a notion of instantaneous capacity regions, and construct algorithms for multi-hop routing and transmission scheduling that achieve network stability and fairness with respect to these regions. The algorithms are shown to operate under arbitrary client mobility models (including non-ergodic models with non-repeatable events), and provide analytical delay guarantees that are independent of the timescales of the mobility process. Our control strategies apply techniques of backpressure, shortest path routing, and Lyapunov optimization.     

Existence and uniqueness of fair rate allocations in lossy wireless networks

To extend established concepts of fair resource allocation in wired networks to wireless networks, wired model assumptions must be adapted to be relevant for wireless networks as for example, in wireless networks losses due to environmental conditions may occur even in the absence of queueing congestion. Thus fundamental questions of the existence and uniqueness of fair rate allocations must be reconsidered. We treat wireless networks characterized by lossy channels, spatial channel reuse, multiple routes and multiple frequencies. We establish the existence and uniqueness of utility fair and max-min fair solutions and that, as loss rates decrease, fair allocations converge to the loss-less ones.     

无线mesh网络中多跳数据流的拥塞控制

提出了一种无线mesh网络的拥塞控制机制LAP(link layer adaptive pacing),利用mesh网关控制有线到无线数据流的发送速率,避免过多数据传输产生跳路间的严重干扰.算法以每个数据流为对象,在改进多跳数据流性能的同时,还很好地保证了网络公平性.此外,控制机制在链路层完成,不需要修改现有传输或路由协议.仿真结果表明LAP控制下的网络性能远远胜过802.11网络,而且较目前主流算法也有明显改善.     

Cross-layer optimization for end-to-end rate allocation in multi-radio wireless mesh networks

In this paper, we study rate allocation for a set of end-to-end communication sessions in multi-radio wireless mesh networks. We propose cross-layer schemes to solve the joint rate allocation, routing, scheduling, power control and channel assignment problems with the goals of maximizing network throughput and achieving certain fairness. Fairness is addressed using both a simplified max-min fairness model and the well-known proportional fairness model. Our schemes can also offer performance upper bounds such as an upper bound on the maximum throughput. Numerical results show that our proportional fair rate allocation scheme achieves a good tradeoff between throughput and fairness. Jian Tang is an assistant professor in the Department of Computer Science at Montana State University. He received the Ph.D. degree in Computer Science from Arizona State University in 2006. His research interest is in the area of wireless networking and mobile computing. He has served on the technical program committees of multiple international conferences, including ICC, Globecom, IPCCC and QShine. He will also serve as a publicity co-chair of International Conference on Autonomic Computing and Communication Systems (Autonomics’2007). Guoliang Xue is a Full Professor in the Department of Computer Science and Engineering at Arizona State University. He received the Ph.D. degree in Computer Science from the University of Minnesota in 1991 and has held previous positions at the Army High Performance Computing Research Center and the University of Vermont. His research interests include efficient algorithms for optimization problems in networking, with applications to fault tolerance, robustness, and privacy issues in networks ranging from WDM optical networks to wireless ad hoc and sensor networks. He has published over 150 papers in these areas. His research has been continuously supported by federal agencies including NSF and ARO. He is the recipient of an NSF Research Initiation Award in 1994 and an NSF-ITR Award in 2003. He is an Associate Editor of Computer Networks (COMNET), the IEEE Network Magazine, and Journal of Global Optimization. He has served on the executive/program committees of many IEEE conferences, including INFOCOM, SECON, IWQOS, ICC, GLOBECOM and QShine. He is the General Chair of IEEE IPCCC’2005, a TPC co-Chair of IPCCC’2003, HPSR’2004, IEEE Globecom’2006 Symposium on Wireless Ad Hoc and Sensor Networks, IEEE ICC’2007 Symposium on Wireless Ad Hoc and Sensor Networks, and QShine’2007. He is a senior member of IEEE. Weiyi Zhang received the M.E. degree in 1999 from Southeast University, China. Currently he is a Ph.D. student in the Department of Computer Science and Engineering at Arizona State University. His research interests include reliable communication in networking, protection and restoration in WDM networks, and QoS provisioning in communication networks.     

Securing wireless mesh networks

Using wireless mesh networks to offer Internet connectivity is becoming a popular choice for wireless Internet service providers as it allows fast, easy, and inexpensive network deployment. However, security in WMNs is still in its infancy as very little attention has been devoted thus far to this topic by the research community. In this article we describe the specifics of WMNs and identify three fundamental network operations that need to be secured.     

Distributed multichannel assignment with congestion control in wireless mesh networks

In Multichannel Wireless Mesh Network architecture, topology discovery, traffic profiling, channel assignment and routing are essential. From the existing work done so far, we can observe that no work has been carried out on the combined solution of multichannel assignment with routing protocol and congestion control. In this paper, we propose to design a Distributed Multichannel Assignment with Congestion control (DMAC) routing protocol. In this protocol, a traffic‐aware metric provides the solution for multichannel assignment and congestion control. Hence, the proposed protocol can improve the throughput and channel utilization to a very high extent. The proposed algorithm avoids self‐interference by not assigning a channel to any link whose incident links have already been assigned channels. By our simulation results, we show that our proposed protocol attains high throughput and delivery ratio along with reduced delay. Copyright © 2011 John Wiley & Sons, Ltd.     

分布式多网关无线mesh网公平协作路由算法

现有的协作路由协议不能公平地分配无线网络资源,无法满足网络最小流的吞吐量需求。将多并发流的协作路由问题形式化成一个最大化网络整体效用的凸优化问题,并基于对偶分解和子梯度,提出一种分布式的多网关无线mesh网公平协作路由算法FCRMG。实验结果表明,与基于期望传输时间的非协作路由和基于竞争感知的协作路由相比,FCRMG算法在保证网络吞吐量的前提下,能显著提高最小业务流的吞吐量。     

MARS: Link-layer rate selection for multicast transmissions in wireless mesh networks

IEEE 802.11 devices dynamically choose among different modulation schemes and bit-rates for frame transmissions. This rate adaptation, however, is restricted only to unicast frames. Multicast (and broadcast) frames are constrained to use a fixed low bit-rate modulation, resulting in low throughput for multicast streams. Availability of high bandwidth and efficient use of the medium is crucial to support multimedia multicast streaming applications such as IPTV, especially in multihop mesh networks. To address this problem, we propose a rate adaptation algorithm for multicast transmissions in these networks. The proposed algorithm, MARS, is distributed in nature, and relies on local network measurements to select a transmission bit-rate for a given multicast group. The algorithm also facilitates the joint use of bit-rate selection and link-layer mechanisms such as acknowledgements and retransmissions to improve reliability of high throughput multicast streams. Based on implementation and evaluation on a testbed, the algorithm provides up to 600% gain in throughput compared to traditional 802.11 networks in some scenarios. Additionally, the algorithm can support multicast streams while consuming a small fraction (20%) of the resources compared to the basic 802.11 operation.     

无线Mesh网络综述

无线Mesh网络是无线局域网和移动自组织网络相结合的产物,是一种全新的网络架构,有着极大的应用前景。简要介绍了无线Mesh网络体系结构、特点和应用领域,总结了无线Mesh网络路由协议的研究状况,探讨了存在的问题和今后发展的方向。     

Multi-gateway association in wireless mesh networks

Most traditional models of wireless mesh networks involve a mobile device connecting to the backbone through one of the available gateways in a wireless mesh network. In this paper, we present an alternate model, in which mobile devices are allowed to connect through more than one of the available gateways. We call the model multi-gateway association (MGA). We present arguments for why such a model can result in better capacity, fairness, diversity and security when compared to the default single-association model. We also identify the primary challenges that need to be addressed when using multiple-gateway associations, and propose solutions to handle these challenges. Using simulations, we show that throughput benefits ranging from 10% to 125% can be obtained by the proposed model as compared to a default single association model with just two gateways and more importantly, benefits linear in the number of gateways are obtainable. Through simulations and analysis, we establish why only intelligent multi-gateway association and neither single or simple multi-gateway association strategies can yield significant benefits.     

Oblivious routing in wireless mesh networks

As new network applications have arisen rapidly in recent years, it is becoming more difficult to predict the exact traffic pattern of a network. In consequence, a routing scheme based on a single traffic demand matrix often leads to a poor performance. Oblivious routing (Racke in Proceedings of the 43rd annual IEEE symposium on foundations of computer science 43–52, 2002) is a technique for tackling the traffic demand uncertainty problem. A routing scheme derived from this principle intends to achieve a predicable performance for a set of traffic matrixes. Oblivious routing can certainly be an effective tool to handle traffic demand uncertainty in a wireless mesh network (WMN). However, a WMN has an additional tool that a wireline network does not have: dynamic bandwidth allocation. A router in a WMN can dynamically assign bandwidth to its attached links. This capability has never been exploited previously in works on oblivious routing for a spatial time division multiple access (STDMA) based WMN. Another useful insight is that although it is impossible to know the exact traffic matrix, it is relatively easy to estimate the amount of the traffic routed through a link when the routing scheme is given. Based on these two insights, we propose a new oblivious routing framework for STDMA WMNs. Both analytical models and simulation results are presented in this paper to prove that the performance—in terms of throughput, queue lengths, and fairness—of the proposed scheme can achieve significant gains over conventional oblivious routing schemes for STDMA based WMNs.     

Towards combining admission control and link scheduling in wireless mesh networks

Wireless mesh networks (WMNs) have emerged recently as a key solution for next-generation wireless networks; they are low cost and easily deployed technology. However, WMNs have to deal with a low bandwidth which prevents them from guaranteeing the requirements of applications with strict constraints. To overcome this limitation, we propose in this paper a new admission control model which integrates a dynamic link scheduling scheme, named ACLS, in order to optimize the network bandwidth use. We formulate the admission control problem as a binary linear programming problem (BL2P). The proposed admission control integrates an algorithm, based on the Dakin’s branch and bound (B&B) method, which respects the bandwidth and delay required by the flows. The proposed ACLS solution has been validated on ns2, and the simulation results showed that ACLS model has better performance than the reference solution BRAWN; it accepts more flows while guaranteeing their delay and bandwidth.     

Admission control on multipath routing in 802.11-based wireless mesh networks

Admission control (AC) is a mechanism for meeting bandwidth requirements of data transmissions. Early research on admission control for wireless mesh networks (WMNs) was centered around single-path routing. Compared to single-path routing, parallel multipath routing may offer more reliable network services and better load balancing. Applying admission control to multipath routing could further improve service quality, but it also faces a number of challenges. For example, transmission on one path may affect transmission on a neighboring path. Addressing these challenges, this paper presents an AC algorithm on parallel multipath routing for WMNs. In particular, we formulate an optimization problem for achieving the best service based on available bandwidth and bandwidth consumption of to-be-admitted data sessions. While solving this problem is a complex task, we devise an optimal algorithm for selecting two node-disjoint paths with rate allocation, and propose a distributed multipath routing and admission control protocol to achieve a near-optimal solution. Simulations show that MRAC is efficient and effective in meeting bandwidth requirements.     

Maxmin fair scheduling in wireless ad hoc networks

We investigate from an algorithmic perspective the maxmin fair allocation of bandwidth in wireless ad hoc networks. We formalize the maxmin fair objective under wireless scheduling constraints, and present a necessary and sufficient condition for maxmin fairness of a bandwidth allocation. We propose an algorithm that assigns weights to the sessions dynamically such that the weights depend on the congestion in the neighborhood, and schedules the sessions that constitute a maximum weighted matching. We prove that this algorithm attains the maxmin fair rates, even though it does not use any information about the statistics of the packet arrival process.     

Topology control for multi-channel multi-radio wireless mesh networks using directional antennas

Directional antennas are widely used technologies for reducing signal interference and increasing spatial reuse. In this paper, we propose a topology control method for multi-channel multi-radio wireless mesh networks that use directional antennas. We are given a set of mesh routers installed in a region and some of them are gateway nodes that are connected to the Internet via wired lines. Each router has a traffic demand (Internet access traffic) generated from the end-users. The problem is how to adjust antenna orientations of radios and assign channels to them to construct a logical network topology, such that the minimum delivery ratio of traffic demands of routers is maximized. We first formulate the problem to an equivalent optimization problem with a clearer measurable metric, which is to minimize the largest interfering traffic of links in the network. We then propose a three-step solution to solve the problem. Firstly, we construct a set of routing trees, with the objective to balance the traffic among tree links. Secondly, we assign the radios of a node to the links it needs to serve, such that the total traffic load of the links that each radio serves is as balanced as possible. Thirdly, we do a fine-grained adjustment of antenna orientations and assign channels to them, such that the transmission area of each antenna will cover all the links it serves and the largest interfering traffic of links is minimized.     

Seeker: A bandwidth-based association control framework for wireless mesh networks

The rapid deployment of wireless mesh networks across universities and enterprises, and the pervasiveness of mobile devices equipped with Wi-Fi connectivity, has resulted in a scenario wherein end users have the option to choose from a multitude of access points at any given location. Moreover, with the increasing availability of rich online content, there has been a steady increase in mobile Internet traffic. Since the choice of access point that a user associates with will directly impact his performance, it is imperative that there exist an efficient association control mechanism, in order to enhance the end user’s experience. As part of this work, we propose Seeker, a novel framework for association control in wireless networks that utilizes “available bandwidth” as the design metric. The goal of Seeker is to assist the mesh network in making an intelligent decision regarding which access point a client should associate with. As part of our scheme, we implement and evaluate a passive tool to estimate available bandwidth in wireless networks. We then describe how we use this tool to implement our association control scheme, and evaluate it via extensive experiments on an outdoor testbed. Seeker takes into consideration the performance of the mesh backhaul, in addition to the client-to-AP link quality, thereby achieving significant advantages over traditional association control schemes for wireless-LANs.     

End-to-end fair rate optimization in wired-cum-wireless networks

In this paper, we address the end-to-end rate optimization problem in a wired-cum-wireless network, where CSMA/CA based wireless LANs extend a wired backbone and provide access to mobile users. The objective is to achieve proportional fairness amongst the end-to-end sessions in the network. Since the network contains wireless links whose attainable throughput is a (non-convex and non-separable) function of MAC protocol parameters, the problem requires joint optimization at both the transport and the link layers. A dual-based algorithm is proposed in this paper to solve this cross-layer rate optimization problem. It is implemented in the distributed manner, and works at the link layer to adjust scheduling rates for the wireless links in the basic service sets, and at the transport layer to adjust end-to-end session rates. We prove rigorously that the proposed algorithm converges to the globally optimal rates. Simulation results are provided to support our conclusions.     

无线Mesh网络中基于链路负载估算的拥塞控制策略

针对无线Mesh网络的网络特性,提出了一种基于链路负载估算的拥塞控制策略LLECC。LLECC算法计算有效链路带宽和链路负载估算确定RED算法中的调整因子,通过调整因子调整RED算法中的参数从而实现动态的对无线网络拥塞控制。详细讨论了LLECC算法的实现过程和相关参数的计算方法,通过仿真分析验证了该算法对无线Mesh网络性能的提高。