On Channel Assignment for Multicast in Multi-Radio Multi-Channel Wireless Mesh Networks:A Survey

The major challenge faced by wireless mesh networks is the capacity reduction caused by interference,and interference can be reduced or even eliminated through appropriate channel assignment.This article presents a comprehensive survey of channel assignment schemes for multicast in multi-radio multi-channel wireless mesh networks.We analyze the state-of-the-art channel assignment schemes for multicast and provide comprehensive taxonomy of the latest work.In general,we classify the channel assignment schemes for multicast into two types,that is,sequential multicast routing and channel assignment(SMRCA)and joint multicast routing and channel assignment(JMRCA).Detailed review of channel assignment schemes in each category is provided.Possible future research directions and corresponding solutions are also explored to motivate research interests in the field of channel assignment for multicast in wireless mesh networks.     

Channel Assignment and Link Scheduling in Multi-Radio Multi-Channel Wireless Mesh Networks

Capacity limitation is one of the fundamental issues in wireless mesh networks. This paper addresses capacity improvement issues in multi-radio multi-channel wireless mesh networks. Our objective is to find both dynamic and static channel assignments and corresponding link schedules that maximize the network capacity. We focus on determining the highest gain we can achieve from increasing the number of radios and channels under certain traffic demands. We consider two different types of traffic demands. One is expressed in the form of data size vector, and the other is in the form of data rate vector. For the first type of traffic demand, our objective is to minimize the number of time slots to transport all the data. For the second type of traffic demand, our objective is to satisfy the bandwidth requirement as much as possible. We perform a trade-off analysis between network performance and hardware cost based on the number of radios and channels in different topologies. This work provides valuable insights for wireless mesh network designers during network planning and deployment.     

Partially Overlapped Channels- and Flow-Based End-to-End Channel Assignment for Multi-Radio Multi-Channel Wireless Mesh Networks

Capacity reduction is a major problem faced by wireless mesh networks. An efficient way to alleviate this problem is proper channel assignment. Current end-toend channel assignment schemes usually focus on the case where channels in distinct frequency bands are assigned to mesh access and backbone, but actually backbone network and access network can use the same IEEE 802.11 technology. Besides, these channel assignment schemes only utilize orthogonal channels to perform channel assignment, and the resulting network interference dramatically degrades network performance. Moreover, Internet-oriented traffic is considered only, and peerto-peer traffic is omitted, or vice versa. The traffic type does not match the practical network. In this paper, we explore how to exploit partially overlapped channels to perform endto-end channel assignment in order to achieve effective end-to-end flow transmissions. The proposed flow-based end-to-end channel assignment schemes can conquer the limitations aforementioned. Simulations reveal that loadaware channel assignment can be applied to networks with stable traffic load, and it can achieve near-optimal performance; Traffic-irrelevant channel assignment is suitable for networks with frequent change of traffic load,and it can achieve good balance between performance and overhead. Also, partially overlapped channels’ capability of improving network performance is situation-dependent, they should be used carefully.     

Joint Channel Assignment and Routing for Throughput Optimization in Multiradio Wireless Mesh Networks

Multihop infrastructure wireless mesh networks offer increased reliability, coverage, and reduced equipment costs over their single-hop counterpart, wireless local area networks. Equipping wireless routers with multiple radios further improves the capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing is essential for throughput optimization of mesh clients. Efficient channel assignment schemes can greatly relieve the interference effect of close-by transmissions; effective routing schemes can alleviate potential congestion on any gateways to the Internet, thereby improving per-client throughput. Unlike previous heuristic approaches, we mathematically formulate the joint channel assignment and routing problem, taking into account the interference constraints, the number of channels in the network, and the number of radios available at each mesh router. We then use this formulation to develop a solution for our problem that optimizes the overall network throughput subject to fairness constraints on allocation of scarce wireless capacity among mobile clients. We show that the performance of our algorithms is within a constant factor of that of any optimal algorithm for the joint channel assignment and routing problem. Our evaluation demonstrates that our algorithm can effectively exploit the increased number of channels and radios, and it performs much better than the theoretical worst case bounds     

多射频无线Mesh网中的接口分域信道分配

在多射频多信道无线Mesh网中,是无线宽带接入的重要候选技术之一.为了满足无线宽带接入的容量要求,Mesh路由器节点常需要配置多个无线接口并使用多个正交信道.已有的信道分配方法虽能减少干扰和碰撞,但不能完全避免.本文提出一种域内中心式调度的接口分域信道分配(ICCA)方案,旨在完全避免干扰与碰撞以提高网络吞吐量,尤其能...     

CBLA:多信道无线网状网络负载感知的分簇式信道分配

多信道技术能够显著提升无线网状网络的容量,合理高效的信道分配方案是多信道网状网络的核心问题。本文提出了一种分布式的信道分配方法CBLA（Cluster-Based Load-Aware）,结合了静态信道分配简单和动态信道分配灵活的特点;借助簇结构降低了问题的规模;根据统计开销小的局部信息监测链路负载;自适应的动态分配有效减轻了链路负载;采用了一种新的结合跳步数、信道分布情况和簇信息的选路指标。实验结果表明CBLA有效降低了数据包的平均延迟,并显著提升了网络吞吐量。     

无线Mesh网络路由协议——多射频质量源路由（MR-LQSR）协议

无线Mesh网络使用传统的基于最短路径的移动Ad Hoc网络路由协议并不能获得良好的性能,为此提出了一种新的无线Mesh网路由协议——MR—LQSR算法及新的路由判据——WCETT．能在吞吐量与延时之间获得一种平衡。     

一种基于博弈论的无线Mesh网信道分配算法

为解决无线Mesh网络中的信道分配问题,提出了基于博弈论的信道分配(GBCA)算法。该算法将无线Mesh网中各节点的信道分配过程作为一个博弈过程,信道分配策略作为博弈者的策略选择,信噪比函数为博弈的效用函数。基于NS2的仿真结果表明该算法在吞吐量和丢包率方面都有较好的性能。     

A Multi-Objective Optimization Scheme for Multicast Routing: A Multitree Approach

In this paper, we propose a multi-objective traffic engineering scheme using different distribution trees to multicast several flows. The aim is to combine into a single aggregated metric, the following weighting objectives: the maximum link utilization, the hop count, the total bandwidth consumption, and the total end-to-end delay. Moreover, our proposal solves the traffic split ratio for multiple trees. We formulate this multi-objective function as one with Non Linear programming with discontinuous derivatives (DNLP). Results obtained using SNOPT solver show that several weighting objectives are decreased and the maximum link utilization is minimized. The problem is NP-hard, therefore, a novel SPT algorithm is proposed for optimizing the different objectives. The behavior we get using this algorithm is similar to what we get with SNOPT solver. The proposed approach can be applied in MPLS networks by allowing the establishment of explicit routes in multicast events. The main contributions of this paper are the optimization model and the formulation of the multi-objective function; and that the algorithm proposed shows polynomial complexity.     

Adaptive Distributed Channel Assignment in Wireless Mesh Networks

From the channel assignment schemes in time division multiple access (TDMA) slot assignment protocols developed in previous studies, we have found that these protocols do not have a convenient frame length reduction scheme after the expansion of the frame length. As the network size grows, the frame length expands rapidly, particularly when we set it as a power of two. A very long frame may result in poor channel utilization when it contains many unused slots. In this paper, we consider a wireless mesh network with a TDMA structure. We divide each code into time slots to form the channels. We propose a dynamic frame length expansion and recovery method termed adaptive distributed channel assignment (ADCA). This strategy is designed to enhance the utilization of the available channels by taking advantage of the spatial reuse concept. In ADCA, an increase in spatial reuse is achieved by adding a certain amount of control overhead. We show that the bandwidth saved due to the channel spatial reuse is larger than the additional bandwidth spent on the control overhead.

Distributed Contention-Aware Call Admission Control for IEEE 802.11 Multi-Radio Multi-Rate Multi-Channel Wireless Mesh Networks

In this paper, we focus on call admission control (CAC) in IEEE 802.11 multi-radio multi-rate multi-channel (MR²-MC) wireless mesh networks (WMNs). CAC is the key component of QoS routing protocols. The goal of CAC is to protect existing flows from QoS violations and fully utilize available radio resource on channels. We propose a CAC mechanism, called Contention-Aware Multi-channel Call Admission Control (CMC), for MR²-MC WMNs based on IEEE 802.11 DCF. CMC is fully distributed, relies on local information to estimate the residual bandwidth of a path, and can be integrated into existing routing protocols for MR²-MC WMNs to provide QoS. We evaluate the performance of CMC via ns-2 simulations. The results show that CMC can precisely predict the end-to-end residual bandwidths of paths, successfully protects existing flows from QoS violations, and fully utilizes the bandwidths on channels.     

多接口多信道无线网状网中流量感知的信道带宽调制算法

 如何合理分配使用有限的频谱资源是无线网状网研究中的一个重要议题。近来有研究开始采用动态信道带宽调制来提升无线网络性能。本文将最优信道带宽调制归结为“装箱压缩”问题,并结合多接口技术提出分布式流量感知的信道带宽调制算法,最后将算法应用于多接口多信道无线网状网。模拟表明我们的算法能有效增加频谱使用效率和提升网络性能。     

802.11无线网状网中基于时频信道的准动态信道分配算法

该文首次在多天线多信道802.11无线网状网中提出了时频信道的概念。时频信道是通过在时间和频率两个维度划分无线资源取得的。这种划分方法增加了信道数量,使信道划分更加精细,为提高系统的信道利用率做了准备。在时频信道的基础上,提出了准动态信道分配算法。该算法可以和现有的固定信道分配算法结合,实现准动态信道分配,根据链路上负载变化,取得最大的吞吐量。该算法先根据固定信道分配算法为各链路分配相同数量的时频信道,剩余部分当作公共信道。在通信过程中,各链路首先使用分配给自己的信道和空闲的公共信道。如果分配给一个链路的信道不够,且别的链路上的信道有空闲,该链路还可以暂时使用这些空闲信道。理论分析和仿真结果证明该算法可以有效提高系统的吞吐量。     

A Cross-Layer Optimization Framework for Multihop Multicast in Wireless Mesh Networks

The optimal and distributed provisioning of high throughput in mesh networks is known as a fundamental but hard problem. The situation is exacerbated in a wireless setting due to the interference among local wireless transmissions. In this paper, we propose a cross-layer optimization framework for throughput maximization in wireless mesh networks, in which the data routing problem and the wireless medium contention problem are jointly optimized for multihop multicast. We show that the throughput maximization problem can be decomposed into two subproblems: a data routing subproblem at the network layer, and a power control subproblem at the physical layer with a set of Lagrangian dual variables coordinating interlayer coupling. Various effective solutions are discussed for each subproblem. We emphasize the network coding technique for multicast routing and a game theoretic method for interference management, for which efficient and distributed solutions are derived and illustrated. Finally, we show that the proposed framework can be extended to take into account physical-layer wireless multicast in mesh networks     

用于多信道无线网络的综合链路速率分配算法

This paper presents a link allocation and rate assignment algorithm for multi-channel wireless networks. The objective is to reduce network conflicts and guarantee the fairness among links. We first design a new network model. With this network model, the multi-channel wireless network is divided into several subnets according to the number of channels. Based on this, we present a link allocation algorithm with time complexity O(l2 ) to allocate all links to subnets. This link allocation algorithm adopts conflict matrix to minimize the network contention factor. After all links are allocated to subnets, the rate assignment algorithm to maximize a fairness utility in each subnet is presented. The rate assignment algorithm adopts a near-optimal algorithm based on dual decomposition and realizes in a distributed way. Simulation results demonstrate that, compared with IEEE 802. 11b and slotted seeded channel hopping algorithm, our algorithm decreases network conflicts and improves the network throughput significantly.     

Joint Throughput Optimization for Wireless Mesh Networks

In this paper, we address the problem of joint channel assignment, link scheduling, and routing for throughput optimization in wireless networks with multiradios and multichannels. We mathematically formulate this problem by taking into account the interference, the number of available radios the set of usable channels, and other resource constraints at nodes. We also consider the possible combining of several consecutive channels into one so that a network interface card (NIC) can use the channel with larger range of frequencies and thus improve the channel capacity. Furthermore, we consider several interference models and assume a general yet practical network model in which two nodes may still not communicate directly even if one is within the transmission range of the other. We designed efficient algorithm for throughput (or fairness) optimization by finding flow routing, scheduling of transmissions, and dynamic channel assignment and combining. We show that the performance, fairness and throughput, achieved by our method is within a constant factor of the optimum. Our model also can deal with the situation when each node will charge a certain amount for relaying data to a neighboring node and each flow has a budget constraint. Our extensive evaluation shows that our algorithm can effectively exploit the number of channels and radios. In addition, it shows that combining multiple channels and assigning them to a single user at some time slots indeed increases the maximum throughput of the system compared to assigning a single channel.     

On the Relationship Between Transmission Rate and Network Capacity in Multi-Radio Multi-Channel Wireless Mesh Networks

This paper quantitatively investigates the relationship between physical transmission rate and network capacity in multi-radio multi-channel wireless mesh networks by using mixed-integer linear programming to formulate the joint channel assignment and routing problem. The numerical results show that the rate lower than the highest available one can improve the network capacity due to increased connectivity. It is also shown that the lower transmission rate is able to utilize abundant channels more effectively due to the higher degree of freedom in channel assignment. Finally, it is shown that joint rate, channel assignment and routing improves the network capacity further.     

Minimum Interference Channel Assignment in Multiradio Wireless Mesh Networks

In this paper, we consider multi-hop wireless mesh networks, where each router node is equipped with multiple radio interfaces and multiple channels are available for communication. We address the problem of assigning channels to communication links in the network with the objective of minimizing overall network interference. Since the number of radios on any node can be less than the number of available channels, the channel assignment must obey the constraint that the number of different channels assigned to the links incident on any node is atmost the number of radio interfaces on that node. The above optimization problem is known to be NP-hard. We design centralized and distributed algorithms for the above channel assignment problem. To evaluate the quality of the solutions obtained by our algorithms, we develop a semidefinite program and a linear program formulation of our optimization problem to obtain lower bounds on overall network interference. Empirical evaluations on randomly generated network graphs show that our algorithms perform close to the above established lower bounds, with the difference diminishing rapidly with increase in number of radios. Also, ns-2 simulations as well as experimental studies on testbed demonstrate the performance potential of our channel assignment algorithms in 802.11-based multi-radio mesh networks.