Distributed scheduling based on polling policy with maximal spatial reuse in multi-hop WMNs

The scheduling algorithm based on the three-way handshaking scheme in IEEE 802.16d-2004 standard has some serious problems because of the complexity of the algorithm and low scheduling efficiency.To enhance the scheduling efficiency and improve the performance of multi-hop wireless mesh networks (WMNs), one distributed scheduling algorithm that can maximize the spatial and time reuse with an interference-based network model is proposed.Compared to the graph-based network model, the proposed network model can achieve a better throughput performance with maximal spatial reuse.Furthermore, this proposed scheduling algorithm also keeps fairly scheduling to all links, with a priority-based polling policy.Both the theoretical analysis and simulation results show that this proposed distributed scheduling algorithm is simple and efficient.     

IEEE 802.16网络中保障QoS的多用户业务调度算法

基于IEEE 802.16协议,研究了宽带无线接入网中保障Qos的上行多用户多业务资源分配和调度问题.首先,对该问题建立跨层分析模型,即基于TDM-OFDMA物理层的多址接入队列调度模型.随后提出了基于凸优化方法的最小剩余聚合工作负载算法.可以证明,只要到达业务的QOS参数值在该算法的稳定域内,那么它就能渐进地保证业务的QoS要求,同时还能最小化调度系统的剩余聚合工作负载.仿真实验的数值结果进一步证明了本算法的确能够在可接受的复杂度范围内保证4类服务的Qos要求.     

Application of IEEE 802.16 Mesh Networks as the Backhaul of Multihop Cellular Networks

Cellular networks have been widely used to support many new audio-and video-based multimedia applications. The demand for higher data rate and diverse services has driven the research on multihop cellular networks (MCNs). With its ad hoc network features, an MCN can offer many additional advantages, such as increased network throughput, scalability and coverage. However, providing ad hoc capability to MCNs is challenging as it may require proper wireless interfaces. In this article, the architecture of IEEE 802.16 network interface to provide ad hoc capability for MCNs is investigated, with its focus on the IEEE 802.16 mesh networking and scheduling. Several distributed routing algorithms based on network entry mechanism are studied and compared with a centralized routing algorithm. It is observed from the simulation results that 802.16 mesh networks have limitations on providing sufficient bandwidth for the traffic from the cellular base stations when a cellular network size is relatively large.     

Proportional fairness in MAC layer channel access of IEEE 802.11s EDCA based wireless mesh networks

Fairness provisioning in IEEE 802.11s EDCA based Wireless Mesh Networks (WMNs) is a very challenging task due to relayed traffic and traffic load variation among mesh routers. Because of bursty traffic in general purpose community wireless mesh networks, proportional fairness is more suited than max–min fairness, where mesh routers and clients should get channel access proportional to their traffic load. However, proportional fairness is hard to achieve by solving optimization function because of non-linearity and non-concave property of the objective function. In this paper, a probabilistic approach is proposed to provide proportional fairness without solving global non-linear and non-concave optimization. Every mesh node use a load estimation strategy to estimate total traffic load that it needs to forward. The required channel share of a mesh node should be proportional to its traffic load, whereas, the total normalized channel share for all the contending mesh nodes should be kept less than unity to satisfy the clique constraint. The network architecture and contention property in WMN are explored to deduce the required channel share of mesh nodes. A probabilistic approach is used to tune the contention window based on the difference between actual channel share and required channel share, so that the node with more traffic load gets more channel share. A discrete time Markov Chain based modeling is used to deduce the overall network throughput for the proposed scheme. Simulation result shows that the proposed scheme works better than the standard IEEE 802.11s based EDCA MAC in terms of fairness and throughput.     

An Effective QoS Differentiation Scheme for Wireless Mesh Networks

Wireless mesh networking is emerging as an important architecture for future-generation wireless communications systems. Quality of service provisioning is a challenging issue in WMNs. In this article we study an effective QoS differentiation scheme for IEEE 802.16 WiMAX mesh networks. Both collocated and general topologies are exploited. Illustrative numerical examples are presented to demonstrate the effectiveness of the proposed strategy. The impact of key parameters on performance is discussed for differentiating various services. Moreover, with the proposed scheme, WMN scalability can be greatly improved. The challenges with respect to the integration of WMN and cooperative transmission are discussed, and the fairness problem is addressed with potential solutions.     

A Hybrid Centralized Routing Protocol for 802.11s WMNs

Wireless mesh networks (WMNs) are being widely accepted as a critical wireless access solution for various applications. Due to minimal mobility in mesh nodes, a backbone topology can be effectively maintained in WMN using a proactive routing protocol. In IEEE 802.11s standard, a tree-based routing (TBR) protocol is adopted as a viable proactive routing protocol for a WMN with user traffic flowing to/from a wired network through a root (i.e., a mesh portal). However, the performance of the TBR protocol degrades rapidly as the user traffic becomes dominated by intra-mesh traffic. The reason is that the routing path through the root even for intra-mesh traffic unnecessarily overloads the root. Furthermore, the TBR performance becomes more severe when the network size of WMN is large, which could lead to the huge amount of intra-mesh traffic towards the root. To overcome these problems, we propose a new routing mechanism, root driven routing (RDR) protocol, for the root to quickly determine the best-metric route for any source-destination pair of intra-mesh traffic. For inter-mesh traffic, the original TBR protocol is employed. Thus, the hybrid centralized routing protocol that combines TBR and RDR and is adaptive to all traffic scenarios. Our simulation results reveal that the proposed RDR protocol outperforms the TBR protocol with much lower average end-to-end delay and much higher packet delivery ratio for intra-mesh traffic. The simulation results also provide some insight into the right tradeoff between the TBR protocol and the RDR protocol to achieve the best performance of the hybrid centralized routing protocol for WMNs.     

Adaptive scheduling mechanism for IPTV over WiMAX IEEE 802.16j networks

A WiMAX technology is a very promising Broadband Wireless Access technology that is able to transmit different service types. This latter can have different constraints such as traffic rate, maximum latency, and tolerated jitter. The IEEE 802.16 Medium Access Control specifies five types of QoS classes: UGS, rtPS, ertPS, nrtPS, and BE. However, the IEEE 802.16 standard does not specify the scheduling algorithm to be used. Operators have the choice among many existing scheduling techniques. Also, they can propose their own scheduling algorithms. In this paper, we propose a scheduling strategy (Adaptive Weighted Round Robin, AWRR) for various Internet Protocol Television (IPTV) services traffic over 802.16j networks. Our scheme adapts dynamically the scheduler operation to according queue load and quality of service constraints. In particular, the proposed mechanism gives more priority to high definition television and standard definition television traffic by using two schedulers. The proposed scheduling algorithm has been simulated using the QualNet network simulator. The experimental results show that our scheduler schemes AWRR have a better performance than the traditional scheduling techniques for rtPS traffic, which allows ensuring QoS requirements for IPTV application. Copyright © 2012 John Wiley & Sons, Ltd.     

On the impact of physical layer awareness on scheduling and resource allocation in broadband multicellular IEEE 802.16 systems [Radio Resource Management and Protocol Engineering for IEEE 802.16]

Multicellular networks based on the IEEE 802.16 standard appear to be very promising candidates to provide end users with broadband wireless access. However, they also pose interesting challenges in terms of radio resource management, where several design choices are not specified in the standard, intentionally left open to implementors. For this reason, we focus in this article on scheduling and resource allocation, and investigate how they could operate in a cross-layer fashion. In particular, we describe the principles of joint scheduling and resource allocation for IEEE 802.16 operating in AMC mode, and discuss the critical role played by physical layer considerations, especially intercell interference estimation and channel state awareness, in the obtained performance. This leads to identifying key open issues and possible general solutions     

Efficient routing and centralized scheduling algorithms for IEEE 802.16 Mesh Networks

An IEEE 802.16 wireless system can provide broadband wireless access to subscriber stations and operate in mesh mode. The communication between a subscriber station and a base station can pass through one or more intermediate subscriber stations. The IEEE 802.16 standard provides a centralized scheduling mechanism that supports contention‐free and resource‐guarantee transmission services in mesh mode. However, the corresponding algorithm to this schedule is quite primitive in the standard. In this paper, we propose a more efficient way to realize this schedule by maximizing channel utilization. Our designs are divided into two phases: routing and scheduling. First, a routing tree topology is constructed from a given mesh topology by our proposed tree construction algorithm. Secondly, we allocate channel resources to the edges in the routing tree by our proposed scheduling algorithm. To further support the quality‐of‐service schedule, we extend our designs by addressing some issues such as service class, admission control and fairness. Simulation results show the superiority of our proposed algorithms over others. Copyright © 2011 John Wiley & Sons, Ltd.     

基于IEEE802.16e的多级别业务调度算法研究

在IEEE802.16e标准中,保证QoS的调度算法一直是人们研究的热点,它涉及到从单一业务到多级别业务的调度服务.对多级别业务调度的支持是保证系统性能的重要技术之一.本文针对多级别业务常用的分层调度和联合调度策略,从系统吞吐量、QoS性能和公平性等方面对之进行的仿真分析和性能比较.仿真结果表明联合调度策略综合性能较好.     

Improving Delay and Jitter Performance in Wireless Mesh Networks for Mobile IPTV Services

Wireless mesh networking has recently emerged as a promising technology for the next-generation wireless networks. In wireless mesh networks (WMNs), it is practically attractive to support the low-cost quality-of-service (QoS) guaranteed mobile TV service. To meet this need, our study addresses how to improve the delay and jitter performance of mobile IPTV services over IEEE 802.11 based WMN. Particularly, we first discuss the adaptation of IEEE 802.11 MAC layer to construct a WMN with emphasis on mobile IPTV service; we then develop an enhanced version of Guaranteed-Rate (GR) packet scheduling algorithm, namely virtual reserved rate GR (VRR-GR), to further reduce the delay and suppress the jitter in multiservice network environment. Simulation results show that our proposed approach can satisfyingly prioritize mobile IPTV services in WMN, while providing non-IPTV services with what they need as well.      

A novel routing algorithm in distributed IEEE 802.16 mesh networks

In this paper, we propose a novel distributed routing algorithm for IEEE 802.16/WiMax based mesh networks. Our algorithm aims at providing routes for traffic flows with minimum end-to-end delays. Based on the underlying IEEE802.16 standard distributed scheduling mechanism, our routing algorithm is incorporated into the medium access control (MAC) layer. Each node determines the next-hop nodes for the passing flows according to the scheduling information and attempts to forward packets in the very earliest slots. In addition, a loop cancelation mechanism is proposed to avoid being trapped in path loops and thus guarantees the accessibility of our algorithm. The simulation results show that our proposal can considerably reduce the delay of traffic flows and also achieve load balance to a certain degree.     

Proportional bandwidth allocation with consideration of delay constraint over IEEE 802.11e-based wireless mesh networks

Wireless mesh networks (WMNs) extend the limited transmission coverage of wireless LANs by enabling users to connect to the Internet via a multi-hop relay service provided by wireless mesh routers. In such networks the quality of experience (QoE) depends on both the user location relative to the Internet gateway and the traffic load. Various channel access or queue management schemes have been proposed for achieving throughput fairness among WMN users. However, delay and bandwidth utilization efficiency of such schemes may be unacceptable for real-time applications. Accordingly, the present study proposes a proportional bandwidth allocation scheme with a delay constraint consideration for enhancing the QoE of users of WMNs based on the IEEE 802.11e standard. An analytical model of the proposed scheme is provided. Moreover, the performance of the proposed scheme is systematically compared with that of existing bandwidth allocation methods. The simulation results show that the proposed scheme outperforms previously proposed schemes in terms of both an improved throughput fairness among the WMN users and a smaller end-to-end transmission delay.     

Centralized Resource Allocation for Multimedia Traffic in IEEE 802.16 Mesh Networks

The IEEE 802.16 standard provides a high degree of flexibility for setting up and operating wireless broadband networks in metropolitan environments. The standard supports numerous capabilities, including mesh topologies and multimedia communications. In this paper, we study these two features by investigating how efficiently an IEEE 802.16 mesh network can treat distributed multimedia traffic by providing differentiated quality of service (QoS). A key component of the system is the ldquoenhanced frame registry tree schedulerrdquo (E-FRTS) that provides QoS-aware resource allocation using a tree structure to prepare the creation of time frames and reduce processing requirements at the beginning of each frame. Simulation results show that distributed multimedia traffic can be efficiently supported in mesh 802.16 networks, provided efficient scheduling and a reasonable number of hops.     

Dynamic frame partitioning scheme for IEEE 802.16 mesh networks

The IEEE 802.16 mesh network is a promising next generation wireless backbone network. In the network, the allocation of minislots is handled by centralized scheduling and distributed scheduling, which are independently exercised. However, the standard does not specify how the frame can be partitioned among its centralized and distributed schedulers. Through efficient partitioning that dynamically adapts the partitioning based on demand, network can support more user applications. Although a dynamic frame partitioning scheme to use Markov model has been studied, the dynamic frame partitioning method has not been fully investigated. This paper proposes two novel and general dynamic frame partitioning scheme for IEEE 802.16 mesh networks so that the minislot allocation can be more flexible and the utilization is increased. The two schemes respectively use GM(1,1)‐Markov model and Grey–Verhulst–Markov model to predict efficient partitions for future frames according to the minislot utilization in current frames. Our study indicates that the two proposed schemes outperform the scheme of using Markov model. Copyright © 2012 John Wiley & Sons, Ltd.     

A fair optimization scheduling scheme for IEEE 802.16 networks in multimedia applications

IEEE 802.16 networks are designed based on differentiated services concept to provide better Quality of Service (QoS) support for a wide range of applications, from multimedia to typical web services, and therefore they require a fair and efficient scheduling scheme. However, this issue is not addressed in the standard. In this paper we present a new fair scheduling scheme which fulfills the negotiated QoS parameters of different connections while providing fairness among the connections of each class of service. This scheme models scheduling as a knapsack problem, where a fairness parameter reflecting the specific requirements of the connections is defined to be used in the optimization criterion. The proposed scheduler is evaluated through simulation in terms of delay, throughput and fairness index. The results show fairness of the scheduling scheme to all connections while the network guarantees for those connections are fulfilled.     

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.     

A near-optimum cross-layered distributed queuing protocol for wireless LAN [medium access control protocols for wireless LANs]

Distributed queuing collision avoidance (DQCA) is a distributed MAC protocol for WLAN systems that offers near optimum performance. The protocol implements a reservation scheme that ensures collision-free data transmissions for high traffic load and switches smoothly and automatically to a random access mechanism when the traffic load is light, improving the delay performance for this situation. In this article the DQCA protocol operation is thoroughly described, and its algorithm rules are given. Furthermore, an enhanced cross-layer scheduling mechanism is also proposed for inclusion in the protocol procedure. This mechanism employs a virtual priority function to reschedule transmissions according to a cross-layer design. Two possible configurations are described in this article by including a PHY-MAC dialog involving channel stale information and the waiting time of the packets in the system, offering a trade-off between throughput maximization and fairness. The performance in terms of throughput and mean delay of DQCA and the two cross-layer schemes has been evaluated through simulations, and a significant enhancement over legacy IEEE 802.11 operation is achieved. The obtained results emphasize the advantages of the proposed schemes and the importance of cross-layer design in wireless communication systems.     

Multi-hop wireless backhaul networks: a cross-layer design paradigm

Multihop wireless backhual networks are emerging as a cost-effective solution to provide ubiquitous and broadband access to meet the rapidly increasing demands of multimedia applications. In this paper, we consider the joint optimal design of routing, medium access control (MAC) scheduling and physical layer resource allocation for such networks, where beamforming antenna arrays are equipped at the physical layer. The notion of transmission set (TS) is introduced to separate the physical layer operations from those at the upper layers; and a column generation approach is employed to efficiently identify the TSs. We then apply the dual decomposition method to decouple the routing and scheduling subproblems, which are performed at different layers and are coordinated by a pricing mechanism to achieve the optimal overall system objective. To efficiently support multimedia traffic, an admission control criterion is considered for the system objective. The performance of the proposed scheme is verified by simulation results, and the impact of the physical layer capabilities on the network performance is evaluated. We also discuss the implementation issues of the cross-layer scheme based on the IEEE 802.16 mesh mode.     

一种用于IEEE 802.16无线城域网TDD模式中的带宽调度方案

该文提出了一种用于IEEE 802.16宽带无线接入系统TDD模式下的公平而有效的带宽分配调度体系。与该领域中传统的固定带宽分配方式相比,该文提出的调度体系结构综合考虑了上下行链路不同业务带宽需求并进行动态带宽分配。该文提出一种新的亏空公平优先级队列(DFPQ)算法来调度不同优先级的业务流,可以为系统提供更好的公平性。仿真结果显示该文提出的调度体系结构能够很好地满足所有类型业务的服务质量(QoS)需求,并提供较好的公平性。