Routing and transmission scheduling for minimizing broadcast delay in multirate wireless mesh networks using directional antennas

Using directional antennas to reduce interference and improve throughput in multihop wireless networks has attracted much attention from the research community in recent years. In this paper, we consider the issue of minimum delay broadcast in multirate wireless mesh networks using directional antennas. We are given a set of mesh routers equipped with directional antennas, one of which is the gateway node and the source of the broadcast. Our objective is to minimize the total transmission delay for all the other nodes to receive a broadcast packet from the source, by determining the set of relay nodes and computing the number and orientations of beams formed by each relay node. We propose a heuristic solution with two steps. Firstly, we construct a broadcast routing tree by defining a new routing metric to select the relay nodes and compute the optimal antenna beams for each relay node. Then, we use a greedy method to make scheduling of concurrent transmissions without causing beam interference. Extensive simulations have demonstrated that our proposed method can reduce the broadcast delay significantly compared with the methods using omnidirectional antennas and single‐rate transmission. In addition, the results also show that our method performs better than the method with fixed antenna beams. Copyright © 2012 John Wiley & Sons, Ltd.     

A cross‐layer optimization for maximum‐revenue‐based multicast in multichannel multiradio wireless mesh networks

Given a video/audio streaming system installed on a multichannel multiradio wireless mesh network, we are interested in a problem concerning about how to construct a delay‐constrained multicast tree to support concurrent interference‐free transmissions so that the number of serviced mesh clients is maximized. In this paper, we propose a heuristic approach called cross‐layer and load‐oriented (CLLO) algorithm for the problem. On the basis of the cross‐layer design paradigm, our CLLO algorithm can consider application demands, multicast routing, and channel assignment jointly during the formation of a channel‐allocated multicast tree. The experimental results show that the proposed CLLO outperforms the layered approaches in terms of the number of serviced mesh clients and throughputs. This superiority is due to information from higher layers can be used to guide routing selection and channel allocation at the same time. As a result, the CLLO algorithm can explore more solution spaces than the traditional layered approaches. In addition to that, we also propose a channel adjusting procedure to enhance the quality of channel‐allocated multicast trees. According to our simulations, it is proved to be an effective method for improving the performance of the proposed CLLO algorithm. Copyright © 2013 John Wiley & Sons, Ltd.     

Multi‐channel power‐controlled directional MAC for wireless mesh networks

Wireless Mesh Networks (WMNs) have emerged recently as a technology for providing high‐speed last mile connectivity in next‐generation wireless networks. Several MAC protocols that exploit multiple channels and directional antennas have been proposed in the literature to increase the performance of WMNs. However, while these techniques can improve the wireless medium utilization by reducing radio interference and the impact of the exposed nodes problem, they can also exacerbate the hidden nodes problem. Therefore, efficient MAC protocols need to be carefully designed to fully exploit the features offered by multiple channels and directional antennas. In this paper we propose a novel Multi‐Channel Power‐Controlled Directional MAC protocol (MPCD‐MAC) for nodes equipped with multiple network interfaces and directional antennas. MPCD‐MAC uses the standard RTS‐CTS‐DATA‐ACK exchange procedure. The novel difference is the transmission of the RTS and CTS packets in all directions on a separate control channel, while the DATA and ACK packets are transmitted only directionally on an available data channel at the minimum required power, taking into account the interference generated on already active connections. This solution spreads the information on wireless medium reservation (RTS/CTS) to the largest set of neighbors, while data transfers take place directionally on separate channels to increase spatial reuse. Furthermore, power control is used to limit the interference produced over active nodes. We measure the performance of MPCD‐MAC by simulation of several realistic network scenarios, and we compare it with other approaches proposed in the literature. The results show that our scheme increases considerably both the total traffic accepted by the network and the fairness among competing connections. Copyright © 2010 John Wiley & Sons, Ltd.     

An overview of using directional antennas in wireless networks

Compared with omni‐directional antennas, directional antennas have many merits, such as lower interference, better spatial reuse, longer transmission range, and improved network capacity. Directional antennas enable numerous emerging outdoor and indoor applications, which have been addressed in many recent studies. Despite the advances in wireless networks with directional antennas (DAWNs), there are many research challenges in all layers of DAWNs. This paper presents a detailed study on recent advances and open research issues on DAWNs. Firstly, we briefly introduce the classification of directional antennas, antenna radiation patterns, antenna modes, and the challenges in the physical layer of DAWNs. We then present research issues on the medium access control (MAC) layer, followed by the current solutions as well as open research problems on the MAC layer of DAWNs. In addition, we also discuss the research issues on the routing layer and the transport layer. Moreover, other research challenges on the performance evaluation of DAWNs and a brief introduction of indoor DAWNs are given in this paper as well. In conclusion, we summarize the current research issues on DAWNs as well as prospects in the future. Copyright © 2011 John Wiley & Sons, Ltd.     

Distributed channel assignment combined with routing over multi-radio multi-channel wireless mesh networks

In order to realize the reduction of equipment cost and the demand of higher capacity,wireless mesh network(WMN) router devices usually have several interfaces and work on multi-channels.Jointing channel allocation,interface assignment and routing can efficiently improve the network capacity.This paper presents an efficient channel assignment scheme combined with the multi-radio link quality source routing(MR-LQSR) protocol,which is called channel assignment with MR-LQSR(CA-LQSR).In this scheme,a physical interference model is established:calculated transmission time(CTT) is proposed as the metric of channel assignment,which can reflect the real network environment and channel interference best,and enhanced weighted cumulative expected transmission time(EWCETT) is proposed as the routing metric,which preserves load balancing and bandwidth of links.Meantime,the expression of EWCETT contains the value of CTT,thus the total cost time of channel assignment and routing can be reduced.Simulation results show that our method has advantage of higher throughput,lower end-to-end time delay,and less network cost over some other existing methods.     

On the performance and fairness of dynamic channel allocation in wireless mesh networks

Channel assignment in multichannel multiradio wireless mesh networks is a powerful resource management tool to exploit available multiple channels. Channels can be allocated either statically on the basis of long‐term steady state behavior of traffic or dynamically according to actual traffic demands. It is a common belief that dynamic schemes provide better performance; however, these two broad classes of channel allocation schemes have not been compared in detail. In this paper, we quantify the achievable performance gain and fairness improvement through an optimal dynamic channel allocation scheme. We develop optimal algorithms for a dynamic and three static schemes using mixed integer linear programming and compare them in the context of QoS provisioning, where network performance is measured in terms of acceptance rate of QoS sensitive traffic demands. Our extensive simulations show that static schemes should optimize channel allocation for long‐term traffic pattern and maintain max–min fairness to achieve acceptable performances. Although the dynamic and max–min fair static schemes accomplish the same fairness, the dynamic channel allocation outperforms the static scheme about 10% in most cases. In heavily overloaded regimes, especially when network resources are scarce, both have comparable performances, and the max–min fair scheme is preferred because it incurs less overhead. Copyright © 2011 John Wiley & Sons, Ltd.     

基于最大化网络吞吐量的WMN信道分配算法

为了解决无线Mesh网络中的信道分配问题,提出了一种基于博弈论的信道分配算法.该算法将网络中每一个节点模型化为一个博弈者,每个博弈者的策略为信道的分配方案,并将整个网络的吞吐量作为效用函数的目标,效用函数的物理意义则是在给定流量需求矩阵下传输的成功率.博弈者通过相互博弈来优化收益函数以最大化网络吞吐量.通过NS2.34仿真分析得出,GBCA算法在收敛性、丢包率和吞吐量上都要优于当前的算法.     

A fast and reliable routing technique for wireless mesh networks

In wireless mesh networks (WMNs), real time communications (e.g., Voice over IP (VoIP) and interactive video communications) may often be interrupted as packets are frequently lost or delayed excessively. This usually happens due to the unreliability of wireless links or buffer overflows along the routing paths. The mesh connectivity within the WMN enables the capability to enhance reliability and reduce delay for such applications by using multiple paths for routing their packets. The vital components in multi‐path routing for achieving this are the pre‐determined formation of paths and the technique that the paths are deployed for packet traversal. Therefore, we propose a novel multi‐path routing protocol by introducing a new multi‐path organization and a traffic assignment technique. The designed technique dubbed as FLASH (Fast and reLiAble meSH routing protocol) discovers one primary path between a pair of source and destination based on a new proposed metric, and thereafter selects mini‐paths, which connect pairs of intermediate nodes along the primary path. The primary path and mini‐paths are concurrently deployed, as multiple copies of packets are routed through. This technique compensates for possible outage at intermediate wireless nodes or their corresponding wireless links along the primary path. Routing along mini‐paths is performed in such a way that redundant copies do not cause an excessive congestion on the network. The effectiveness of the proposed scheme is evaluated analytically and through extensive simulations under various load conditions. The results demonstrate the superiority of the proposed multi‐path organization in terms of reliability and satisfactory achievements of the protocol in enhancing delay and throughput compared to the existing routing protocols, especially for long distances and in congested conditions. Copyright © 2010 John Wiley & Sons, Ltd.     

Angular MAC: a framework for directional antennas in wireless mesh networks

Capacity of wireless mesh networks can be enhanced through the use of smart directional antennas, which not only enable nodes to have high quality links but also increase network throughput by allowing spatial reuse. This paper proposes a new MAC protocol and framework, called Angular MAC (ANMAC) that enables directional antennas in wireless mesh networks. The protocols and algorithms of the ANMAC framework fit well with the requirements of mesh networks such as neighbor discovery and self-configuration, while providing significant throughput enhancements. The throughput enhancements are proven by comprehensive simulations with realistic antenna patterns, including performance comparisons of ANMAC with directional schemes using a similar node architecture and omni 802.11. Also, the effect of contention window size is analyzed and a dynamic contention window adaptation algorithm is proposed to maximize the throughput of the self-configuring mesh network, by taking instantaneous traffic conditions into account.     

Fairness-oriented routing algorithm joint with power control and channel assignment for multi-radio multi-channel wireless mesh networks

The multi-radio multi-channel wireless mesh network （MRMC-WMN） draws general attention because of its excellent throughput performance, robustness and relative low cost. The closed interactions among power control （PC）, channel assignment （CA） and routing is contributed to the performance of multi-radio multi-channel wireless mesh networks （MRMC-WMNs）. However, the joint PC, CA and routing （JPCR） design, desired to achieve a global optimization, was poor addressed. The authors present a routing algorithm joint with PC and CA （JPCRA） to seek the routing, power and channel scheme for each flow, which can improve the fairness performance. Firstly, considering available channels and power levels, the routing metric, called minimum flow rate, is designed based on the physical interference and Shannon channel models. The JPCRA is presented based on the genetic algorithm （GA） with simulated annealing to maximize the minimum flow rate, an non-deterministic polynomial-time hard （NP-Hard） problem. Simulations show the JPCRA obtains better fairness among different flows and higher network throughput.     

无线mesh网中一种基于博弈论的公平性路由协议

提出一种基于博弈论的以树为拓扑结构的公平性路由协议.新的协议综合了先验式路由和按需路由,并且将路由计算和信道资源分配控制分布到树中的每个枝节点上,降低了根节点的负担,使其更适合于无线 mesh网的通信需求.仿真结果表明,新的路由协议改进了AODV、HWMP路由协议的端到端平均延迟和网络吞吐量,并且网络中各个无线节点占有的信道资源基本相近,满足公平性原则.     

On a joint temporal-spatial multi-channel assignment and routing scheme in resource-constrained wireless mesh networks

Use of multiple orthogonal channels can significantly improve network throughput of multi-hop wireless mesh networks (WMNs). In these WMNs where multiple channels are available, channel assignment is done either in a centralized manner, which unfortunately shows a poor scalability with respect to the increase of network size, or in a distributed manner, where at least one channel has to be dedicated for exchanging necessary control messages or time synchronization has to be utilized for managing the duration of data packet transmission, causing excessive system overhead and waste of bandwidth resource. In this paper, we first formulate multi-channel assignment as a NP-hard optimization problem. Then a distributed, heuristic temporal-spatial multi-channel assignment and routing scheme is proposed, assuming every wireless node in the network is equipped with a single-radio interface. Here the gateway node is set to use all the channels sequentially in a round-robin fashion. This temporal scheme ensures all the nodes that need to directly communicate with the gateway node shall have a fair access to it. For those non-gateway nodes, a spatial scheme where channels are assigned based on their neighbors’ channel usage is adopted to exploit parallel communications and avoid channel interference among nodes. Furthermore, since the routing factors, including channel usage of neighbor nodes, node hop count, node memory size, and node communication history, are all considered along with the channel assignment, network performance, measured by packet delivery latency, channel usage ratio, and memory usage ratio, tends to be considerably enhanced. The simulation results have confirmed that, compared with a couple of well-known multi-channel assignment schemes, such as LCM [21] and ROMA [15], the proposed scheme shows substantial improvement in network throughput with a very modest collision level. In addition, the proposed scheme is highly scalable as the algorithm complexity is only linearly dependent on the total number of channels that are available in the network and the number of neighbors that a network node directly connects to.     

基于传输路径质量的无线mesh网络可靠多播

提出了一种可靠多播网(RM)模型,探讨了无线链路和节点可靠性对多播路径选择的影响。首先,建立了无线链路的相关性和多播路径的可靠性模型,并提出了多播传输的可靠性判据;同时,结合首树算法和多路径树算法提出了构造可靠多播网的算法。可靠多播网具有并行的多播路径,通过在多播源节点和目的节点之间选择多播链路和节点构成了可靠的多播路径,提供了多播路径的"负荷分担"和"热备份"功能,从而支持了多播业务可靠性。     

VoIP traffic in wireless mesh networks: a MOS‐based routing scheme

Support of Voice over Internet Protocol (VoIP) services in wireless mesh networks requires implementation of efficient policies to support low‐delay data delivery. Multipath routing is typically supported in wireless mesh networks at the network level to provide high fault tolerance and load balancing because links in the proximity of the wireless mesh gateways can be very stressed and overloaded, thus causing scarce performance. As a consequence of using multipath solutions, lower delay and higher throughput can be supported also when a given path is broken because of mobility or bad channel conditions, and alternative routes are available. This can be a relevant improvement especially when assuming that real‐time traffic, such as VoIP, travels into the network. In this paper, we address the problem of Quality of Service (QoS) support in wireless mesh networks and propose a multipath routing strategy that exploits the Mean Opinion Score (MOS) metric to select the most suitable paths for supporting VoIP applications and performing adaptive load balancing among the available paths to equalize network traffic. Performance results assess the effectiveness of the proposed approach when compared with other existing methodologies. Copyright © 2015 John Wiley & Sons, Ltd.     

Optimal frequency assignment for IEEE 802.11 wireless networks

The performance of wireless local area networks (WLANs) is based on the performance of the corresponding access points (APs). Nowadays, network engineers tend to manually assign data channels (frequencies) for each AP. They only use channels 1, 6, and 11 because no interference exists between these channels. But it will be far more efficient if all 11 channels are used. Therefore, the channel allocation problem becomes a major challenge when deploying WLANs. In this paper, we assume that the location of each AP is known. Our objective is to optimally assign a frequency for each AP such that the throughput is maximized and the interference between the various APs is minimized. We also consider a realistic scenario where the APs are not in line of sight of each other, but on the other hand there are different barriers that separate them. We formulate the problem using integer linear programming (ILP) in order to obtain the optimal frequency assignment (OFA). Then, we propose two efficient heuristic algorithms to achieve the same results. Finally, we evaluate the performance of all techniques and make a comparison between them. Copyright © 2008 John Wiley & Sons, Ltd.     

An efficient channel assignment algorithm for multicast wireless mesh networks

Multicast can enhance the performance of wireless mesh networks (WMNs) effectively, which has attracted great attentions in recent years. However, multicast communication in WMNs requires efficient channel assignment strategy to reduce the total network interference and maximize the network throughput. In this paper, the concept of local multicast is proposed to measure interference and solve hidden channel problem in multicast communication. Basing on the concept, we propose a channel assignment algorithm considering the interference of local multicast and forwarding weight of each node (LMFW). The algorithm fully considers partially overlapped channels and orthogonal channels to improve the network performance. Simulations show that the proposed algorithm can reduce interference and improve network capacity of WMNs.     

Fair inter‐TAP routing and backhaul assignment for wireless mesh networks

Although limiting the number of backhauls, specifically chosen transit access points (TAPs) that forward traffic from other TAPs, reduces the overall costs of a wireless mesh network (WMN), an egress bottleneck is induced, which aggregates traffic and limits the bandwidth. To avoid such problems while working to minimize budgetary expenses, we balanced traffic flow on ‘to‐be‐determined’ backhauls and adjacent links, a mixed nonlinear‐and integer‐programming problem that minimizes the aggregated flow subject to budget, backhaul assignment, top‐level load‐balanced routing, and link capacity constraints. Two algorithms are proposed, weighted backhaul assignment (WBA) and greedy load‐balanced routing (GLBR), that operate in conjunction with Lagrangean relaxation (LR), used for constructing LR‐based heuristics and also as a means of quantification and evaluation of the proposed algorithms. Experiment results show that the proposed algorithms achieve near‐optimization, outperforming related solutions. Copyright © 2008 John Wiley & Sons, Ltd.     

Nodes organization for channel assignment with topology preservation in multi-radio wireless mesh networks

The wireless mesh network is a new emerging broadband technology providing the last-mile Internet access for mobile users by exploiting the advantage of multiple radios and multiple channels. The throughput improvement of the network relies heavily on the utilizing the orthogonal channels. However, an improper channel assignment scheme may lead to network partition or links failure. In this paper we consider the assignment strategy with topology preservation by organizing the mesh nodes with available channels, and aim at minimizing the co-channel interference in the network. The channel assignment with the topology preservation is proved to be NP-hard and to find the optimized solution in polynomial time is impossible. We have formulated a channel assignment algorithm named as DPSO-CA which is based on the discrete particle swarm optimization and can be used to find the approximate optimized solution. We have shown that our algorithm can be easily extended to the case with uneven traffic load in the network. The impact of radio utilization during the channel assignment process is discussed too. Extensive simulation results have demonstrated that our algorithm has good performance in both dense and sparse networks compared with related works.     

High-throughput multicast routing metrics in wireless mesh networks

The stationary nature of nodes in a mesh network has shifted the main design goal of routing protocols from maintaining connectivity between source and destination nodes to finding high-throughput paths between them. Numerous link-quality-based routing metrics have been proposed for choosing high-throughput routing paths in recent years. In this paper, we study routing metrics for high-throughput tree or mesh construction in multicast protocols. We show that there is a fundamental difference between unicast and multicast routing in how data packets are transmitted at the link layer, and accordingly how the routing metrics for unicast routing should be adapted for high-throughput multicast routing. We propose a low-overhead adaptive online algorithm to incorporate link-quality metrics to a representative multicast routing protocol. We then study the performance improvement achieved by using different link-quality-based routing metrics via extensive simulation and experiments on a mesh-network testbed, using ODMRP as a representative multicast protocol.Our extensive simulation studies show that: (1) ODMRP equipped with any of the link-quality-based routing metrics can achieve higher throughput than the original ODMRP. In particular, under a tree topology, on average, ODMRP enhanced with link-quality routing metrics achieve up to 34% higher throughput than the original ODMRP under low multicast sending rate; (2) the improvement reduces to 21% under high multicast sending rate due to higher interference experienced by the data packets from the probe packets; (3) heavily penalizing lossy links is an effective way in the link-quality metric design to avoid low-throughput paths; and (4) the path redundancy from a mesh data dissemination topology in mesh-based multicast protocols provides another degree of robustness to link characteristics and reduces the additional throughput gain achieved by using link-quality-based routing metrics. Finally, our experiments on an eight-node testbed show that on average, ODMRP using SPP and PP achieves 14% and 17% higher throughput over ODMRP, respectively, validating the simulation results.     

Multi‐cost routing for energy and capacity constrained wireless mesh networks

We propose a class of novel energy‐efficient multi‐cost routing algorithms for wireless mesh networks, and evaluate their performance. In multi‐cost routing, a vector of cost parameters is assigned to each network link, from which the cost vectors of candidate paths are calculated using appropriate operators. In the end these parameters are combined in various optimization functions, corresponding to different routing algorithms, for selecting the optimal path. We evaluate the performance of the proposed energy‐aware multi‐cost routing algorithms under two models. In the network evacuation model, the network starts with a number of packets that have to be transmitted and an amount of energy per node, and the objective is to serve the packets in the smallest number of steps, or serve as many packets as possible before the energy is depleted. In the dynamic one‐to‐one communication model, new data packets are generated continuously and nodes are capable of recharging their energy periodically, over an infinite time horizon, and we are interested in the maximum achievable steady‐state throughput, the packet delay, and the energy consumption. Our results show that energy‐aware multi‐cost routing increases the lifetime of the network and achieves better overall network performance than other approaches. Copyright © 2011 John Wiley & Sons, Ltd.