Slot allocation algorithms in centralized scheduling scheme for IEEE 802.16 based wireless mesh networks

In IEEE 802.16 based wireless mesh networks (WMNs), TDMA (Time Division Multiple Access) is employed as the channel access method and only TDD (Time Division Duplex) is supported and there are no clearly separate downlink and uplink subframes in the physical frame structure. As the uplink and downlink traffic has different characteristics in that the uplink traffic decentralizes in each MSS (Mesh Subscriber Station) and the downlink traffic centralizes in the MBS (Mesh Base Station), different scheduling methods should be taken in the uplink and downlink. This paper presents a uniform slot allocation algorithm which is suitable for both uplinks and downlinks. To achieve higher spatial reuse and greater throughput and to avoid switching frequently between receiving and transmitting within two adjacent time slots when a relay node forwards traffic, different link selection criteria are taken into account when allocating slots for uplinks and downlinks. A combined uplink and downlink slot allocation algorithm is proposed for further improving the spatial reuse and network throughput. The proposed algorithms are evaluated by extensive simulations and the results show that it has good performance in terms of spatial reuse and network throughput. To the best of the authors’ knowledge, this work is the first one that considers combined uplink and downlink slot allocation on the centralized scheduling scheme in IEEE 802.16 based WMNs.     

Power-aware opportunistic downlink scheduling in IEEE 802.16 wireless networks

The IEEE 802.16 is a standard for fixed and mobile Broadband Wireless Access (BWA). In this paper, we deal with two key challenges of 802.16-based networks. First, terminals close to cell edge experience poor channel quality, due to severe path-loss and high interference from concurrent transmissions in nearby cells. To address this issue, we propose a framework based on a static partitioning of bandwidth into chunks with different transmission power levels. Terminals with impaired channel conditions can then benefit from being allocated a higher amount of transmission power than the others. Secondly, transmissions should be scheduled according to Quality of Service (QoS) requirements to keep users with real-time video or voice calls satisfied, while best-effort connections should fairly share the remaining capacity. To this aim, we propose a scheduling algorithm, called Power-aware Opportunistic Downlink Scheduling (PODS), that aims at meeting both the QoS and fairness requirements, while taking into account the different power levels of the bandwidth chunks. The performance of the proposed scheduler is assessed through detailed packet-level simulation in realistic scenarios and compared with well-known scheduling algorithms. Results confirm that PODS is able to exploit power boosting to provide real-time connections with the desired level of QoS, irrespectively of their MSs’ channel quality.     

DTSMA: Distributed time-spread multiple access for wireless mesh networks with IEEE 802.16d MAC protocol

This paper studies the use of IEEE 802.16d mesh MAC protocol for multi-hop networking in an indoor domestic environment. The mesh network is expected to support time-sensitive audio–video applications with stringent QoS requirement. In the literature, time-spread multiple access (TSMA) is a promising technology to provide a minimum throughput guarantee in a multi-hop mesh network with dynamic topology. However, existing TSMA schemes require the number of nodes in the entire network and their global maximum node degree, be known a priori to a central controller. The requirement is not practical. In view of this problem, this paper proposes a distributed time-spread multiple access (DTSMA) scheme. The proposed DTSMA has the following main contributions: (a) A method for each node to determine locally its polynomial coefficients without a priori global knowledge of node number and maximum node degree, and (b) A method to distribute to neighbours the locally determined polynomial coefficients, and to resolve collision between two sets of identical polynomial coefficients from two neighbouring nodes. The proposed DTSMA has been evaluated through extensive simulations to confirm that it can indeed preserve the capability of providing a minimum throughput guarantee in the absence of the a priori global knowledge. In benchmark against the de facto distributed coordinated scheduling (DCS) in the original IEEE 802.16d mesh MAC protocol under various domestic wireless channel conditions, DTSMA outperforms in terms of packet delivery ratio and average end-to-end packet delay which are important metrics for time-sensitive audio–video applications. Simulation results also show that DTSMA outperforms TSMA in terms of average end-to-end packet delay and average delay jitter when the severity of propagation impairment is high.     

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.     

Spectrum sharing in IEEE 802.11s wireless mesh networks

With current amendments, transmission rates of 100 Mb/s and more become possible with IEEE 802.11 WLANs. On the one hand, this allows the end user to change from wired to wireless infrastructure in even more application scenarios; on the other hand interference sensitive modes reduce the maximum range between the mobile station and the access point (AP). To extend the transmission range transparently, relay APs form a mesh network and provide wireless connection over large areas.Besides path selection, a crucial capability of a wireless mesh network is the ability to share the available spectrum among the participants. In this work, we classify two inherently different MAC protocols according to this ability. The well-known IEEE 802.11 DCF takes the position of a typical CSMA/CA protocol, whereas the Mesh Network Alliance (MNA) represents a distributed, reservation-based approach.To assess their performance, we follow a dual approach: first we develop a method to compute the capacity bounds of the protocols in the considered scenarios. It helps to estimate the absolute gain of spectrum sharing in wireless mesh networks. Second, the WARP2 simulation engine is used to compare the distributed behaviour of both protocols. This results in a relative evaluation. A final conclusion is drawn by combining the simulation and the theoretical results. It underlines the significant possibilities of the MNA approach and shows future directions for capacity gains.     

Genetic algorithm approach for QoS-based tree topology construction in IEEE 802.16 mesh networks

The topological characteristics of an IEEE 802.16 mesh network including the tree’s depth and degree of its nodes affect the delay and throughput of the network.To reach the desired trade-off between delay and throughput,all potential trees should be explored to obtain a tree with the proper topology.Since the number of extractable tree topologies from a given network graph is enormous,we use a genetic algorithm(GA) to explore the search space and find a good enough trade-off between per-node,as well as network-wide delay and throughput.In the proposed GA approach,we use the Pruefer code tree representation followed by novel genetic operators.First,for each individual tree topology,we obtain expressions analytically for per-node delay and throughput.Based on the required quality of service,the obtained expressions are invoked in the computation of fitness functions for the genetic approach.Using a proper fitness function,the proposed algorithm is able to find the intended trees while different constraints on delay and throughput of each node are imposed.Employing a GA approach leads to the exploration of this extremely wide search space in a reasonably short time,which results in overall scalability and accuracy of the proposed tree exploration algorithm.     

A rule-based inter-session network coding scheme over IEEE 802.16(d) mesh CDS-mode networks

In the literature, an opportunistic inter-session network coding scheme needs to exchange extra control messages to maintain traffic flow states to operate. However, such a requirement increases the implementation complexity of a network coding scheme. In this paper, we propose a rule-based network coding scheme (RNC) that performs opportunistic inter-session network coding using a stateless design. By exploiting this stateless design, the proposed coding scheme is easy to implement and deploy.In addition, in this paper based on RNC we study the hidden terminal problems between different coding structures. Such a problem may result in severe packet collisions in a network-coding-based network and thus degrade network coding performance. To alleviate this problem, based on RNC we propose a smart handshake procedure (called RNC-SHP) over the IEEE 802.16(d) mesh coordinated distributed scheduling (CDS) mode to reduce the number of hidden terminals between pairwise network coding structures. Our simulation results show that the proposed RNC schemes can greatly outperform the original routing-based scheme on end-to-end flow goodputs and packet delays.     

On the performances of IEEE 802.16(d) mesh CDS-mode networks using Single-Switched-Beam Antennas

The IEEE 802.16(d) mesh coordinated distributed scheduling (CDS) mode is a novel technology for future fixed wireless backbone networks and designed for the use of omnidirectional antennas. The use of Single-Switched-Beam Antennas (SSBAs) may have great potential to increase network capacity due to the antenna directivity. However, a network designed for omnidirectional antennas usually cannot operate well or achieve good performance with the presence of antenna directivity.In this paper, we review the designs of the IEEE 802.16 mesh CDS-mode network, study the issues of this network with the use of Single-Switched-Beam Antennas (SSBAs), and propose a complete solution to solve these issues. The performances of our proposed scheme is evaluated using simulations. The simulation results show that our proposed scheme can effectively solve the issues of using SSBAs in the IEEE 802.16 mesh CDS-mode network and greatly increase its network capacity.     

On the nominal capacity of multi-radio multi-channel wireless mesh networks

Wireless mesh networking is an emerging technology with a wide range of applications, from community to metropolitan area networking. Mesh networks consist of wireless routers and access points that make up the network backbone which is connected to the wired infrastructure. Client devices are located at the edge. The capacity of a wireless mesh network is an important performance indicator as well as design parameter. It depends on various factors such as network size and topology, expected traffic patterns, number of interfaces per node, number of channels, routing and channel assignment etc. In this paper, we present an analytical framework for estimating the capacity of wireless mesh networks, based on the concept of collision domains. The capacity of grid-oriented mesh networks is investigated for various scenarios to study the impact of different network parameters.     

An efficient bandwidth allocation algorithm for real-time VBR stream transmission under IEEE 802.16 wireless networks

This paper investigates variable rate control strategies for real-time multimedia variable bit rate (VBR) services over IEEE 802.16 broadband wireless networks. A data rate control mechanism is derived for the case where the uplink channel provides real-time services and the traffic rate parameter remains constant. This paper shows that the common queuing scheduling algorithms have some bandwidth allocation fairness problems for the real-time polling service (rtPS) in the MAC layer. In other words, the use of a VBR for the rtPS by a WiMAX system results in additional access latency jitter and bandwidth allocation disorder in the transmitted multimedia streams during the regular time interval polling of subscribe stations (SSs) for the contention bandwidth request period. However, the proposed scheduling algorithm solves these SSs contending with bandwidth resource allocation problems based on an extended rtPS (ertPS) of quality-of-service (QoS) pre-programming for a ranging response non-contention polling period. The adopted bandwidth allocation of max–min fairness queue scheduling uses a time constraint condition to transmit real-time multimedia VBR streaming in an IEEE 802.16 broadband wireless environment. In addition, we use the ns-2 simulation tool to compare the capacity of multimedia VBR stream and show that the proposed ertPS scheduling algorithm outperforms other rtPS scheduling algorithms.     

Multiple frequency reuse schemes in the two-hop IEEE 802.16j wireless relay networks with asymmetrical topology

In this paper, throughput performance of the access links (i.e., base station to mobile station and relay station to mobile station) is analyzed for the two-hop IEEE 802.16j wireless relay networks with asymmetrical topology. In specific, three frequency reuse schemes are proposed to improve the spectrum efficiency of the access links: (1) an isolation band based frequency reuse scheme (IBFRS) which introduces an isolation band surrounding each relay station (RS) cluster (i.e, a separate RS or several adjacent RSs) so that the throughput of the access link can be improved by allowing frequency reuse between RSs and the base station (BS); (2) the dynamic frequency power partition (DFPP) scheme for reusing the frequency among RSs; (3) the selective reuse (SR) scheme for the RSs to further selectively reuse the frequency in the isolation band according to the interference measurement. Comprehensive simulation shows that by applying the proposed IBFRS+DFPP+SR, the throughput of the access link can be significantly improved.     

Interconnection of CAN segments through IEEE 802.16 wireless MAN

The Controller Area Network (CAN) is a high-performance and highly reliable advanced serial communication protocol, which efficiently supports distributed real-time control. CAN-based distributed control systems have generally two main problems that are the size of distributed area and the need for communication with other LANs and with remote CAN segments. A straightforward solution is to use internetworking devices with wireless support to extend CAN segments. In this paper, a new solution to interconnect CAN segments is proposed, which uses a wireless MAN based on the IEEE 802.16 standard as a backbone system. Also, the solution describing a model for internetworking unit integrates the traffic generated by CAN segments into IEEE 802.16 wireless MAN using encapsulation technique.     

IEEE 802.16 Mesh模式下的跨层拥塞控制

基于IEEE802.16Mesh网络,提出了一种拥塞控制策略.每个节点通过自身拥塞情况进行局部拥塞控制,同时利用节点间的协同能力在每相邻两跳内的3个结点间进行拥塞控制.通过跨层机制反馈整条传输链路的拥塞情况,并在链路源节点进行数据发送调节.仿真结果表明,这种基于跨层反馈的拥塞控制策略(CLFC2)能有效缓解链路拥塞状况,在负荷严重的情况下能提供更好的通信质量.     

IEEE 802.16 Mesh网基于区分服务的拥塞控制机制

提出一种基于区分服务的拥塞控制机制(DiffServ congestion control,DSCC)用于解决Mesh网拥塞问题.该机制首先对到达节点的实时业务、非实时业务到达率进行周期性的统计,依据统计值对节点下一时段到达的主流业务类型进行预测,同时动态地调整缓存队列长度的阈值以监测拥塞.最后DSCC根据未来到达的主流业务类型,自适应地为节点设定传输避让指数,公平有效地缓解了网络拥塞.实验结果表明DSCC可以显著地缓解拥塞,提高数据传输性能.     

Backpressure scheduling in IEEE 802.11 wireless mesh networks: Gap between theory and practice

Achieving efficient bandwidth utilization in wireless networks requires solving two important problems: (1) which packets to send (i.e., packet scheduling) and (2) which links to concurrently activate (i.e., link scheduling). To address these scheduling problems, many algorithms have been proposed and their throughput optimality and stability are proven in theory. One of the most well-known scheduling algorithms is backpressure scheduling which performs both link and packet scheduling assuming a TDMA (Time Division Multiple Access) MAC (Medium Access Control) layer. However, there has been limited work on realizing backpressure scheduling with a CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) MAC layer (e.g., IEEE 802.11). In IEEE 802.11 networks, it is expected that the throughput optimality will not be achieved. In this paper, we investigate the extent of this throughput gap between theoretical TDMA-based backpressure scheduling and an approximation of it for IEEE 802.11 WMNs (Wireless Mesh Networks). Through extensive testbed measurements, we verify that there is indeed a non-negligible throughput gap. We present two main reasons behind this gap: Control inaccuracy that results from approximation of link scheduling and information inaccuracy that results from late or incorrect information, for instance, about queue lengths or network topology. Our results show that losses by MAC-layer collisions and backoff, which mainly occur due to control inaccuracy plays a major role for the throughput gap. On the other hand, while losses by queue drops, typically due to information inaccuracy, do occur, their effect can be tolerated. Nevertheless, both types of inaccuracies need to be mitigated in order to improve throughput.     

支持QoS的IEEE 802.16的带宽调度算法

给出了IEEE 802.16 PMP支持QoS的带宽调度算法,此算法由BS scheduler和SS scheduler共同实现,带宽的分配单位是时隙,并在NS-2上实现了该算法。通过建立仿真环境,对各种数据流的端到端的延时进行比较,结果表明算法的有效性。     

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.     

Average end-to-end delay computation in IEEE 802.11 ad hoc networks

In this study, we present a new analytic model for evaluating average end-to-end delay in IEEE 802.11 multihop wireless networks. Our model gives closed expressions for the end-to-end delay in function of arrivals and service time patterns. Each node is modelled as a G/G/1/K queue from which we can derive expressions for service time via queueing theory. By combining this delay evaluation with different admission controls, we design a protocol called DEAN (Delay Estimation in Ad hoc Networks). DEAN is able to provide delay guarantees for quality of service applications in function of the application level requirements. Through extensive simulations, we compare the performance evaluation of DEAN with other approaches.