A cross-layer optimization framework for joint channel assignment and multicast routing in multi-channel multi-radio wireless mesh networks

Existing literature on multicast routing protocols in wireless mesh networks (WMNs) from the view point of the links involved in routing are divided into two categories: schemes are aimed at multicast construction with minimal interference which is known as NP hard problem. In contrast, other methods develop network-coding-based solutions with the main objective of throughput maximization, which can effectively reduce the complexity of finding the optimal routing solution from exponential to polynomial time. The proposed framework in this paper is placed in the second category. In multi-channel multi-radio WMNs (MCMR WMNs), each node is equipped with multiple radios, each tuned on a different channel. In this paper, for the first time, we propose a cross-layer convex optimization framework for joint channel assignment and multicast throughput maximization in MCMR WMNs. The proposed method is composed of two phases: in the first phase, using cellular learning automata, channels are assigned to the links established between the radios of the nodes in a distributed fashion such that the minimal interference coefficient for each link is provided. Then, the resultant channel assignment scheme is utilized in the second phase for throughput maximization within an iterative optimization framework based on Lagrange relaxation and primal problem decomposition. We have conducted many experiments to contrast the performance of our solution against many representative approaches.     

Enhancing multi-hop communication over multi-radio multi-channel wireless mesh networks: A cross-layer approach

The multi-channel multi-radio technology represents a straightforward approach to expand the capacity of wireless mesh networks (WMNs) in broadband wireless access scenarios. However, the effective leveraging of this technology in WMNs requires (i) enhanced MAC protocols, to coordinate the access to multiple channels with a limited number of radio interfaces, and (ii) efficient channel allocation schemes, to mitigate the impact of co-channel interference. The design of channel assignment schemes and MAC protocols is strictly interrelated, so that joint design should be considered to optimize the mesh network performance. In this paper, a channel assignment and fast MAC architecture (CAFMA) is proposed, which exploits the benefits provided by the multi-channel multi-radio technology to (i) enhance the performance of multi-hop communications, (ii) maximize the resource utilization, and (iii) support differentiation of traffic classes with different quality of service (QoS) requirements. CAFMA is designed with a cross-layer approach and includes (1) a novel MAC scheme, which provides multi-channel coordination and fast data relaying over multi-hop topologies, and (2) a distributed channel allocation scheme, which works in cooperation with the routing protocol. Simulation results confirm the effectiveness of CAFMA when compared with other single-layer and cross-layer solutions for multi-radio multi-channel WMNs.     

On-line joint QoS routing and channel assignment in multi-channel multi-radio wireless mesh networks

We study the problem of on-line joint QoS routing and channel assignment for performance optimization in multi-channel multi-radio wireless mesh networks, which is a fundamental issue in supporting quality of service for emerging multimedia applications. To our best knowledge, this is the first time that the problem is addressed. Our proposed solution is composed of a routing algorithm that finds up to k but not necessarily feasible paths for each demand and an on-demand channel (re)assignment algorithm that adapts network resources to maintain feasibility of one of the paths. We also study the problem of obtaining an upper bound on the network performance. First, we consider an artificial version of the problem, in which all demands arrive at the same time, and formulate it as a mixed integer linear programming model. To tackle the complexity of the model, it is relaxed that provides a tight upper bound while improves solution time up to 3.0e+5 times. Then, we model the original problem by extending the relaxed model to consider dynamic demands, it leads to a huge model; thus, we develop another model, which is equivalent to the first one and is decomposable. It is broken down by a decomposition algorithm into subproblems, which are solved sequentially. Our extensive simulations show that the proposed solution has comparable performance to the bound obtained from the decomposition algorithm; it efficiently exploits available channels, and needs very few radios per node to achieve high network performance.     

A hierarchical architecture for detecting selfish behaviour in community wireless mesh networks

Wireless mesh networks (WMNs) consist of dedicated nodes called mesh routers which relay the traffic generated by mesh clients over multi-hop paths. In a community WMN, all mesh routers may not be managed by an Internet Service Provider (ISP). Limited capacity of wireless channels and lack of a single trusted authority in such networks can motivate mesh routers to behave selfishly by dropping relay traffic in order to provide a higher throughput to their own users. Existing solutions for stimulating cooperation in multi-hop networks use promiscuous monitoring or exchange probe packets to detect selfish nodes and apply virtual currency mechanism to compensate the cooperating nodes. These schemes fail to operate well when applied to WMNs which have a multi-radio environment with a relatively static topology. In this paper we, propose architecture for a community WMN which can detect selfish behaviour in the network and enforce cooperation among mesh routers. The architecture adopts a decentralized detection scheme by dividing the mesh routers into manageable clusters. Monitoring agents hosted on managed mesh routers monitor the behaviour of mesh routers in their cluster by collecting periodic reports and sending them to the sink agents hosted at the mesh gateways. To make the detection more accurate we consider the quality of wireless links. We present experimental results that evaluate the performance of our scheme.     

多信道无线网状网跨层优化研究

针对多网卡多信道无线Mesh网络容量问题,基于无线信道干扰模型,在给定各节点物理层发射功率的条件下,联合考虑无线Mesh网络传输层的流速控制、网络层的路由算法和MAC层的信道分配等问题,通过采用二次路由计算策略,提出了一个跨层联合优化算法,仿真结果表示,提出的算法能提高网络吞吐量。     

Channel switching control policy for wireless mesh networks

Dynamic channel assignment algorithms allow wireless nodes to switch channels when their traffic loads exceed certain thresholds. These thresholds represent estimations of their throughput capacities. Unfortunately, the threshold estimation may not be accurate due to co-channel interference (CCI) and adjacent-channel interference (ACI), especially with high traffic loads in dense networks. When the link capacity is over-estimated, these channel assignment algorithms are not effective. This is because the channel switch is not triggered even with overloaded data traffic and the link quality decreases significantly as the channel is overloaded. When the link capacity is under-estimated, the link is under-utilized. Moreover, when link traffic load increases from time to time, channel switch occurs frequently. Such frequent channel switches increase latency and degrade throughput, and can even cause network wide channel oscillations. In this paper, we propose a novel threshold-based control system, called balanced control system (BCS). The proposed threshold-based control policy consists of deciding, according to the real time traffic load and interference, whether to switch to another channel, which channel should be switched to and how to perform the switch. Our control model is based on a fuzzy logic control. The threshold which assists to make the channel switch decisions, could be deduced dynamically according to the real-time traffic of each node. We also design a novel dynamic channel assignment scheme, which is used for the selection of the new channel. The channel switch scheduler is provided to perform channel-switch processing for sender and receiver over enhanced routing protocols. We implement our system in NS2, and the simulation results show that with our proposed system, the performance improves by 12.3%–72.8% in throughput and reduces 23.2%–52.3% in latency.     

Routing protocols in wireless mesh networks: challenges and design considerations

Wireless Mesh Networks (WMNs) are an emerging technology that could revolutionize the way wireless network access is provided. The interconnection of access points using wireless links exhibits great potential in addressing the “last mile” connectivity issue. To realize this vision, it is imperative to provide efficient resource management. Resource management encompasses a number of different issues, including routing. Although a profusion of routing mechanisms has been proposed for other wireless networks, the unique characteristics of WMNs (e.g., wireless backbone) suggest that WMNs demand a specific solution. To have a clear and precise focus on future research in WMN routing, the characteristics of WMNs that have a strong impact on routing must be identified. Then a set of criteria is defined against which the existing routing protocols from ad hoc, sensor, and WMNs can be evaluated and performance metrics identified. This will serve as the basis for deriving the key design features for routing in wireless mesh networks. Thus, this paper will help to guide and refocus future works in this area.

认知无线mesh网中联合路由的分布式信道分配算法*

多信道技术通过对数据流量进行分流,能够减少链路间干扰,从而提升网络容量。首先针对认知无线mesh网络提出一种有效的联合路由的分布式信道分配策略,该信道分配策略主要宗旨是维持邻域内信道差异。仿真结果表明,新的信道分配算法相比于无线多信道网络中基于链接的信道分配算法,平均吞吐量大约提高了50%,平均时延降低了约50%。在信道约束的情况下,进一步引入了信道合并算法。仿真结果表明,执行信道合并算法后,网络平均吞吐量、时延性能得到了进一步改善。     

A weight-aware channel assignment algorithm for mobile multicast in wireless mesh networks

Wireless mesh networks (WMNs) are one of key technologies for next generation wireless networks. In this paper, we propose a heuristic channel assignment algorithm with weight awareness to support mobile multicast in WMNs. To enhance network throughput, our algorithm is based on the path forwarding weight to perform channel assignment. In addition to non-overlapping channels, partially-overlapping channels are also used in channel assignment. To fully exploit all available channels in channel assignment, we devise a new channel selection metric to consider the channel separation and the distance between nodes. In mobile multicast, the multicast tree structure cannot be fixed due to receiver (multicast member) mobility. The change of the multicast tree structure will result in channel re-assignment. The proposed algorithm is based on a critical-event driven manner to reduce the times of channel re-assignment as much as possible. Finally, we perform simulation experiments to show the effectiveness of the proposed channel assignment algorithm.     

A quality based routing protocol for wireless mesh networks

Wireless mesh networks can provide low-cost solutions for extending the reach of wireless access points by using multi-hop routing over a set of stationary wireless routers. The routing protocol for these networks may need to address quality considerations to meet the requirements of the user. In this paper, we present a quality based routing protocol for wireless mesh networks that tries to maximize the probability of successful transmissions while minimizing the end-to-end delay. The proposed routing protocol uses reactive route discoveries to collect key parameters from candidate routes to estimate the probability of success and delay of data packets transmitted over them. To achieve accurate route quality assessments, a new route quality metric is proposed that uses performance models of data packet transmissions as opposed to estimating route quality from the transmission of control packets, which have different transmission characteristics. These models are developed after careful evaluations of multi-hop wireless transmissions and validated by computer simulations. Relevant parameters that can be used to assess the route quality metric using these models are explained. Extensive performance evaluations of the proposed quality based routing protocol are presented and its benefits in comparison to some other known routing protocols are discussed.     

An interference-aware fair scheduling for multicast in wireless mesh networks

Multicast is a fundamental routing service in wireless mesh networks (WMNs) due to its many potential applications such as video conferencing, online games, and webcast. Recently, researchers proposed using link-quality-based routing metrics for finding high-throughput paths for multicast routing. However, the performance of such link-quality-based multicast routing is still limited by severe unfairness. Two major artifacts that exist in WMNs are fading which leads to low quality links, and interference which leads to unfair channel allocation in the 802.11 MAC protocol. These artifacts cause the multicast application to behave unfairly with respect to the performance achieved by the multicast receivers.     

An overview of Channel Assignment methods for multi-radio multi-channel wireless mesh networks

Channel Assignment (CA) is an active research area due to the proliferating deployments of multi-radio multi-channel wireless mesh networks. This paper presents an in-depth survey of some of the CA approaches in the literature. First, the key design issues for these approaches are identified, laying down the basis for discussion. Second, a classification that captures their essentials is proposed. Third, the different CA approaches are examined individually, with their advantages and limitations highlighted; furthermore, categorical and overall comparisons for them are given in detail, clarifying their sameness and differences. Finally, the future research directions for CA are discussed at length.     

WMN中的干扰避免部分重叠信道分配算法

针对无线mesh网络(wireless mesh networks,WMN)中存在的信道干扰问题,提出一种基于部分重叠信道(partially overlapping channels,POC)的负载平衡且干扰避免的信道分配算法。通过基于Huffman树的通信接口分配方法连接邻居节点的接口;根据网络干扰情况,对链路进行迭代信道分配,使用静态链路调度保证网络连接;利用启发式算法优先为重要程度较高的链路分配无干扰时隙,对链路调度进行优化。仿真结果表明,在具有混合流量的WMN中,所提算法可以显著提升网络吞吐量,降低网络干扰与平均丢包率,改善网络性能。     

A mathematical formulation for joint channel assignment and multicast routing in multi-channel multi-radio wireless mesh networks

Multicast routing is generally an efficient mechanism for delivering identical content to a group of receivers. Multicast is also deemed a key enabling service for a wealth of audio and video applications as well as data dissemination protocols over the last-mile backhaul Internet connectivity provided by multi-channel multi-radio wireless mesh networks (MCMR WMNs). Major prior art multicast protocols in these networks center around heuristic or meta-heuristic initiatives in which channel assignment and multicast routing are considered as two separate sub-problems to be solved in sequence. It might even be the cast that the solution for either of these two sub-problems is assumed to be preparatively calculated and given as input to the other. Within this perspective, however, the interplay between the two sub-problems would essentially be ruled out from the computations, resulting in sub-optimal solutions for network configuration. The work in this article is targeted at promoting the adoption of cross-layer design for joint channel assignment and multicast tree construction problem in MCMR WMNs. In the proposed scheme, contrary to the existing methods, these two sub-problems will be solved conjointly and an optimal solution is provided. In particular, a comprehensive cross-optimization framework based on the binary integer programming (BIP) formulation of the problem is presented which also addresses the hidden channel problem in MCMR WMNs. We have, as well, conducted an extensive series of simulation experiments to verify the efficacy of the proposed method. Also, experimental results demonstrate that the proposed method outperforms the genetic algorithm and the simulated annealing based methods proposed by Cheng and Yang (2011) in terms of interference.     

Approximate dynamic programming for link scheduling in wireless mesh networks

In this paper a novel interference-based formulation and solution methodology for the problem of link scheduling in wireless mesh networks is proposed. Traditionally, this problem has been formulated as a deterministic integer program, which has been shown to be -hard. The proposed formulation is based on dynamic programming and allows greater flexibility since dynamic and stochastic components of the problem can be embedded into the optimization framework. By temporal decomposition we reduce the size of the integer program and using approximate dynamic programming (ADP) methods we tackle the curse of dimensionality. The numerical results reveal that the proposed algorithm outperforms well-known heuristics under different network topologies. Finally, the proposed ADP methodology can be used not only as an upper bound but also as a generic framework where different heuristics can be integrated.     

Load-balanced mesh router migration for wireless mesh networks

Load-balancing among domains in a wireless mesh network (WMN) is normally achieved by changing the Internet attachment of mesh routers (MRs) that carry the traffic from mobile stations (MSs). The greediness of load-balancing algorithms may force MRs to frequently change their Internet attachments, and thus degrade network performance due to inter-domain mobility of the associated MSs. In this paper, we discuss the negative impact on the performance of MSs’ mobility, due to inter-domain reassignment of MR. A MR migration scheme is proposed to achieve a tradeoff between load-balancing and inter-domain reassignment of MR. The proposed load-balancing scheme for WMNs includes: an initialization procedure to divide a WMN into domains, and a load adjustment procedure to rebalance the traffic load among the neighboring domains when required. We also provide a framework for handling inter-domain mobility in support of multi-hop communication using the Multi-hop cellular IP. Our simulation results show that the proposed protocol effectively controls MR’s change in connectivity as well as MS’s mobility.     

Matrix-based pairwise key establishment for wireless mesh networks

Wireless communication in wireless mesh networks (WMNs), like other types of wireless networks, is vulnerable to many malicious activities such as eavesdropping. As one of the fundamental security technologies, pairwise key establishment has been widely studied to secure wireless communication. In this paper, we propose a new matrix-based pairwise key establishment scheme for mesh clients in WMNs. A fact in WMNs is that mesh routers are more powerful than mesh clients, in both communication and storage. Motivated by this fact, expensive operations can be delegated to mesh routers to alleviate the overhead of mesh clients when establishing pairwise keys between them. Compared with other matrix-based schemes, our scheme has significant advantages: any two mesh clients can directly establish pairwise keys while communication and storage costs of mesh clients are significantly reduced.     

A framework of cross-layer design for multiple video streams in wireless mesh networks

In this paper, a novel cross-layer design framework for multiple realtime video traffics in CDMA wireless mesh networks is proposed. First, the performances of application, physical, MAC, and network layers are modeled by some classical models under reasonable assumptions. Then, we present a framework in which source coding, power control, ARQ control, and delay partitioning functionalities at different layers can be jointly optimized. Our objective is to maximize the video quality under strict end-to-end delay constraints through adjusting source coding rate, end-to-end delay distribution, and each node’s transmit power. This optimization problem is proved to be a nonlinear but log-convex one. Finally, we propose a centralized solution based on the classical convex programming method, as well as a partially distributed solution based on the Lagrangian dual decomposition technique. The both solutions are proved to converge to the global optimum of the above problem.     

Route Maintenance in IEEE 802.11 wireless mesh networks

In this paper, we propose a novel Route Maintenance scheme for IEEE 802.11 wireless mesh networks. Despite lack of mobility and energy constraints, reactive routing protocols such as AODV and DSR suffer from frequent route breakages in 802.11 based infrastructure wireless mesh networks. In these networks, if any intermediate node fails to successfully transmit a packet to the next hop node after a certain number of retransmissions, the link layer reports a transmission problem to the network layer. Reactive routing protocols systematically consider this as a link breakage (and therefore a route breakage). Transmission failures can be caused by a number of factors e.g. interference or noise and can be transient in nature. Frequent route breakages result in significant performance degradation. The proposed mechanism considers multiple factors to differentiate between links with transient transmission problems from those links which have permanent transmission problems and takes a coherent decision on link breakage. The proposed mechanism is implemented in AODV for single-radio single-channel mesh network and an extension is incorporated in multi-radio multi-channel scenarios. Simulation results show substantial performance improvement compared to classical AODV and local route repair schemes.