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.     

Efficient link scheduling for online admission control of real-time traffic in wireless mesh networks

Link scheduling is used in wireless mesh networks (WMNs) to guarantee interference-free transmission on the shared wireless medium in a time division multiple access approach. Several papers in the literature address the problem of link scheduling guaranteeing a minimum throughput to the flows traversing the WMN. However, none of the existing works address the problem of computing a schedule that guarantees that pre-specified end-to-end delay constraints are met. In this paper, we make a first step forward in this direction by defining a link scheduling algorithm that works in sink-tree WMNs, i.e. those whose traffic is routed towards a common sink (i.e. the Internet gateway). Our iterative algorithm exploits a delay-based admission control procedure, devised through Network Calculus, which solves an optimization problem and tests the feasibility of a schedule from the point of view of delay guarantees. Thanks to a clever solution approach for the optimization problem, the iterative algorithm computes feasible solutions in affordable times for networks of several tens of nodes, and is thus amenable to online admission control of real-time traffic.     

REUSE: A combined routing and link scheduling mechanism for wireless mesh networks

Increasing the capacity of wireless mesh networks has motivated numerous studies. In this context, the cross-layer optimization techniques involving joint use of routing and link scheduling are able to provide better capacity improvements. Most works in the literature propose linear programming models to combine both mechanisms. However, this approach has high computational complexity and cannot be extended to large-scale networks. Alternatively, algorithmic solutions are less complex and can obtain capacity values close to the optimal. Thus, we propose the REUSE algorithm, which combines routing and link scheduling and aims to increase throughput capacity in wireless mesh networks. Through simulations, the performance of the proposal is compared to a developed linear programming model, which provides optimal results, and to other proposed mechanisms in the literature that also deal with the problem algorithmically. We observed higher values of capacity in favor of our proposal when compared to the benchmark algorithms.     

Approximate linear programming for networks: Average cost bounds

This paper uses approximate linear programming (ALP) to compute average cost bounds for queueing network control problems. Like most approximate dynamic programming (ADP) methods, ALP approximates the differential cost by a linear form. New types of approximating functions are identified that offer more accuracy than previous ALP studies or other performance bound methods. The structure of the infinite constraint set is exploited to reduce it to a more manageable set. When needed, constraint sampling and truncation methods are also developed. Numerical experiments show that the LPs using quadratic approximating functions can be easily solved on examples with up to 17 buffers. Using additional functions reduced the error to 1–5% at the cost of larger LPs. These ALPs were solved for systems with up to 6–11 buffers, depending on the functions used. The method computes bounds much faster than value iteration. It also gives some insights into policies. The ALPs do not scale to very large problems, but they offer more accurate bounds than other methods and the simplicity of just solving an LP.     

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.     

基于TDMA方式WMN中一种链路调度机制研究

基于TDMA方式的无线网状网中,链路调度对网络性能起着重要作用.针对固定顺序的待调度链路集,提出求解最优调度周期的启发式算法;基于链路顺序对算法性能的影响,从全局优化的角度对全网链路进行排序,提出基于遗传算法的最优链路调度机制.仿真结果表明,该算法能快速收敛于全网链路的最小调度周期,具有比现有算法更高的传输效率和更低的实施复杂度.     

Large-scale access scheduling in wireless mesh networks using social centrality

Wireless mesh networking is an economic and convenient way to provide last mile Internet access through ad hoc peer-to-peer communication links. However, without systematic network configuration and channel resource management, these networks suffer from scalability, performance degradation and service disruption issues due to overwhelming co-channel interference, unscrupulous channel utilization and inherent network mobility. The IEEE 802.11 DCF and EDCA mechanisms based on CSMA/CA are the most widely used random channel access mechanisms, but unfortunately these cannot effectively eliminate hidden terminal and exposed terminal problems in multi-hop scenarios. Social network analysis techniques proposed for economic and social studies have recently been shown to be a successful approach for characterizing information propagation in multi-hop wireless networks. We propose a set of efficient resource allocation algorithms and channel access scheduling protocols based on Latin squares and social centrality metrics for wireless mesh networks (WMNs) with multi-radio multi-channel (MRMC) communication capabilities, called LaSo$LaSo$, which can coexist with IEEE 802.11 DCF and be effectively applied in large scale WMNs. Based on interference information provided by the interference graph, LaSo$LaSo$ uses nodal degree centrality to form cliques for intra-cluster communication, and betweenness centrality to choose bridge nodes to form cliques for inter-cluster communication in WMNs, and then applies Latin squares to map the clique-based clustering structure to radios and channels for wireless communication purposes. Afterwards, LaSo$LaSo$ again applies Latin squares to schedule the channel access amongst nodes within each cluster in a collision-free manner. We evaluate LaSo$LaSo$ using simulations, and results show that LaSo$LaSo$ achieves much better performance than existing IEEE 802.11 standards and other multi-channel access control protocols.     

无线网状网络的多路径路由与调度算法

提出了一种保障服务质量的多路径路由算法,数据分组可通过多条不同的路径进行传输,以提升网络总吞吐量性能.进一步提出了一种多路径调度策略.通过使用调度策略,基于当前可用带宽信息和路径所引入的时延信息,数据分组在传输前可被分成多段并通过不同的路径发送,根据路径时延调整优化调度策略,从而使得数据可通过在不同的路径上进行更高效地传输.仿真实验进一步验证了本文提出的路由机制和调度策略在不同网络负载下的优越性.     

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.

Channel allocation in multi-channel wireless mesh networks

In this article, we survey the latest progress in multi-channel wireless mesh networks, focusing on wireless interference models and channel allocation algorithms with the goal of maximizing the network performance. We present the studies of different interference models and illustrate how they could affect the design of channel assignment. We also summarize channel allocation algorithms with different strategies in both omni-directional and directional antenna networks. We conclude that both static and dynamic channel allocation strategies have advantages and disadvantages, and the design of channel allocation algorithms strongly depends on the interference model and the assumption of network traffic.     

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.     

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.     

Complexity and design of QoS routing algorithms in wireless mesh networks

Quality of service (QoS) provisioning in wireless mesh networks (WMNs) is an open issue to support emerging multimedia services. In this paper, we study the problem of QoS provisioning in terms of end-to-end bandwidth allocation in WMNs. It is challenging due to interferences in the networks. We consider widely used interference models and show that except a few special cases, the problem of finding a feasible path is NP-complete under the models. We propose a k-shortest path based algorithmic framework to solve this problem. We also consider the problem of optimizing network performance by on-line dynamic routing, and adapt commonly used conventional QoS routing metrics to be used in WMNs. We find the optimal solutions for these problems through formulating them as optimization models. A model is developed to check the existence of a feasible path and another to find the optimal path for a demand; moreover, an on-line optimal QoS routing algorithm is developed. Comparing the algorithms implemented by the proposed framework with the optimization models shows that our solution can find existing feasible paths with high probability, efficiently optimizes path lengths, and has a comparable performance to the optimal QoS routing algorithm. Furthermore, our results show that contrary to wireline networks, minimizing resource consumption should be preferred over load distribution even in lightly loaded WMNs.     

Wireless mesh networks based on CDMA

In this paper, we study hybrid contention-free/contention-based traffic management schemes in presence of delay-sensitive and delay-insensitive data in multihop CDMA wireless mesh networks. We suggest a greedy incremental contention-based ordering algorithm for contention-free schedules and also propose a time-scale-based framework for integration of contention and contention-free traffic management schemes. Further, for the contention-free phase, we propose a power control algorithm that gives an end-to-end throughput guarantee. With the aid of simulation, we observe the additional end-to-end throughput that can be achieved when scheduling and tight power control are applied.     

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.     

Approximate dynamic programming with a fuzzy parameterization

Dynamic programming (DP) is a powerful paradigm for general, nonlinear optimal control. Computing exact DP solutions is in general only possible when the process states and the control actions take values in a small discrete set. In practice, it is necessary to approximate the solutions. Therefore, we propose an algorithm for approximate DP that relies on a fuzzy partition of the state space, and on a discretization of the action space. This fuzzy Q-iteration algorithm works for deterministic processes, under the discounted return criterion. We prove that fuzzy Q-iteration asymptotically converges to a solution that lies within a bound of the optimal solution. A bound on the suboptimality of the solution obtained in a finite number of iterations is also derived. Under continuity assumptions on the dynamics and on the reward function, we show that fuzzy Q-iteration is consistent, i.e., that it asymptotically obtains the optimal solution as the approximation accuracy increases. These properties hold both when the parameters of the approximator are updated in a synchronous fashion, and when they are updated asynchronously. The asynchronous algorithm is proven to converge at least as fast as the synchronous one. The performance of fuzzy Q-iteration is illustrated in a two-link manipulator control problem.     

An effective scheduling scheme for multi-hop multicast in wireless mesh networks

With the utilization of concurrent transmission strategy, a throughput-enhanced scheduling scheme is devised for multicast service in wireless multi-hop mesh networks. Since the performance of a multicast mechanism is constrained in a wireless setting due to the interference among local wireless transmissions, the interference relationships are first characterized by introducing a graph transformation method. Based on the graph transformation, the multicast scheduling problem is converted to the graph coloring problem, and then a capacity greedy algorithm is designed to provide concurrent transmission scheduling so that the demanded multicast transmission rate can be achieved. Moreover, the necessary and sufficient conditions of multicast schedulable feasibility are derived. Through corresponding simulations, it is shown that the proposed strategy can enhance the throughput of wireless multi-hop multicast systems significantly.     

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.     

Joint gateway selection,transmission slot assignment,routing and power control for wireless mesh networks

Wireless mesh networks (WMNs) provide cost effective solutions for setting up a communications network over a certain geographic area. In this paper, we study strategic problems of WMNs such as selecting the gateway nodes along with several operational problems such as routing, power control, and transmission slot assignment. Under the assumptions of the physical interference model and the tree-based routing restriction for traffic flow, a mixed integer linear programming (MILP) formulation is presented, in which the objective is to maximize the minimum service level provided at the nodes. A set of valid inequalities is derived and added to the model in an attempt to improve the solution quality. Since the MILP formulation becomes computationally infeasible for larger instances, we propose a heuristic method that is aimed at solving the problem in two stages. In the first stage, we devise a simple MILP problem that is concerned only with the selection of gateway nodes. In the second stage, the MILP problem in the original formulation is solved by fixing the gateway nodes from the first stage. Computational experiments are provided to evaluate the proposed models and the heuristic method.