Wireless Packet Scheduling Algorithm for OFDMA System Based on Time‐Utility and Channel State

In this paper, we propose an urgency‐ and efficiencybased wireless packet scheduling (UEPS) algorithm that is able to schedule real‐time (RT) and non‐real‐time (NRT) traffics at the same time while supporting multiple users simultaneously at any given scheduling time instant. The UEPS algorithm is designed to support wireless downlink packet scheduling in an orthogonal frequency division multiple access (OFDMA) system, which is a strong candidate as a wireless access method for the next generation of wireless communications. The UEPS algorithm uses the time‐utility function as a scheduling urgency factor and the relative status of the current channel to the average channel status as an efficiency indicator of radio resource usage. The design goal of the UEPS algorithm is to maximize throughput of NRT traffics while satisfying quality‐of‐service (QoS) requirements of RT traffics. The simulation study shows that the UEPS algorithm is able to give better throughput performance than existing wireless packet scheduling algorithms such as proportional fair (PF) and modifiedlargest weighted delay first (M‐LWDF), while satisfying the QoS requirements of RT traffics such as average delay and packet loss rate under various traffic loads.     

Opportunistic delay‐margin‐based resource allocation for next‐generation wireless networks

This paper studies and develops efficient traffic management techniques for downlink transmission at the base station (BS) of multi‐service IP‐based networks by combining quality‐of‐service (QoS) provision and opportunistic wireless resource allocation. A delay‐margin‐based scheduling (DMS) for downlink traffic flows based on the delays that each packet has experienced up to the BS is proposed. The instantaneous delay margin, represented by the difference between the required and instantaneous delays, quantifies how urgent the packet is, and thus it can determine the queuing priority that should be given to the packet. The proposed DMS is further integrated with the opportunistic scheduling (OPS) to develop various queueing architectures to increase the wireless channel bandwidth efficiency. Different proposed integration approaches are investigated and compared in terms of delay outage probability and wireless channel bandwidth efficiency by simulation. Copyright © 2010 John Wiley & Sons, Ltd.     

An Improved Round Robin Packet Scheduler for Wireless Networks

Scheduling algorithms are important components for providing quality-of-service (QoS) guarantees in wireless networks. The design of such algorithms need to take into account bursty errors and location-dependent channel capacity that are characteristics of wireless networks. In this paper, a new scheduling algorithm for packet cellular networks, wireless deficit round robin (WDRR), is proposed. WDRR is a round robin scheduler that has low implementation complexity and offers a low delay bound, tight fairness index, and good isolation property. In error-prone channels, the algorithm provides short-term fairness among sessions that perceive a clean channel, long-term fairness among all sessions, ability to meet specified throughput objectives for all sessions, and graceful service degradation among sessions that received excess service. Both analysis and simulation are used to verify the WDRR properties.     

Self-coordinating localized fair queueing in wireless ad hoc networks

Distributed fair queueing in a multihop, wireless ad hoc network is challenging for several reasons. First, the wireless channel is shared among multiple contending nodes in a spatial locality. Location-dependent channel contention complicates the fairness notion. Second, the sender of a flow does not have explicit information regarding the contending flows originated from other nodes. Fair queueing over ad hoc networks is a distributed scheduling problem by nature. Finally, the wireless channel capacity is a scarce resource. Spatial channel reuse, i.e., simultaneous transmissions of flows that do not interfere with each other, should be encouraged whenever possible. In this paper, we reexamine the fairness notion in an ad hoc network using a graph-theoretic formulation and extract the fairness requirements that an ad hoc fair queueing algorithm should possess. To meet these requirements, we propose maximize-local-minimum fair queueing (MLM-FQ), a novel distributed packet scheduling algorithm where local schedulers self-coordinate their scheduling decisions and collectively achieve fair bandwidth sharing. We then propose enhanced MLM-FQ (EMLM-FQ) to further improve the spatial channel reuse and limit the impact of inaccurate scheduling information resulted from collisions. EMLM-FQ achieves statistical short-term throughput and delay bounds over the shared wireless channel. Analysis and extensive simulations confirm the effectiveness and efficiency of our self-coordinating localized design in providing global fair channel access in wireless ad hoc networks.     

Opportunistic packet scheduling algorithm for non-real-time service with a soft QoS requirement in a mobile broadband wireless access system

In this paper, we present a packet scheduling algorithm for a non-real-time service, with soft QoS requirements, which allows for degrading the QoS level, e.g., typically the packet delay, whenever necessary, in mobile broadband wireless Internet access systems. This algorithm is designed to properly trade off system throughput and delay performance, which can improve the system capacity by relaxing the delay constraint with respect to the underlying soft QoS requirement. This is as opposed to most of the existing packet scheduling algorithms for non-real-time service which are simply designed to maximize the system throughput without a delay constraint. The proposed adaptive exponential scheduling algorithm intentionally introduces additional delay to some users, especially under bad channel conditions, opportunistically allowing for serving users only under good channel conditions, as long as the resulting QoS degradation is acceptable for non-real-time service users. The results from a system-level simulation demonstrate that the system capacity can be significantly increased over existing algorithms, by as much as 65%, using the adaptive exponential scheduling algorithm while satisfying the given QoS-level requirements.     

QoS-guaranteed packet scheduling in wireless networks

To guarantee the quality of service (QoS) of a wireless network, a new packet scheduling algorithm using cross-layer design technique is proposed in this article. First, the demand of packet scheduling for multimedia transmission in wireless networks and the deficiency of the existing packet scheduling algorithms are analyzed. Then the model of the QoS-guaranteed packet scheduling (QPS) algorithm of high speed downlink packet access (HSDPA) and the cost function of packet transmission are designed. The calculation method of packet delay time for wireless channels is expounded in detail, and complete steps to realize the QPS algorithm are also given. The simulation results show that the QPS algorithm that provides the scheduling sequence of packets with calculated values can effectively improve the performance of delay and throughput.     

Cross-Layer MAC Protocol and Holistic Opportunistic Scheduling with Adaptive Power Control for QoS in WiMAX

Providing quality of service (QoS) to different service classes with integrated real-time and non-real-time traffic is an important issue in broadband wireless access networks. Opportunistic MAC (OMAC) is a novel view of communication over spatiotemporally varying wireless link whereby the multi-user diversity is exploited rather than combated to maximize bandwidth efficiency or system throughput. It combines cross-layer design features and opportunistic scheduling scheme to achieve high utilization while providing QoS support to various applications. Channel characteristics, traffic characteristics and queue characteristics are the essential factors in the design of opportunistic scheduling algorithms. In this paper, we propose a cross-layer MAC scheduling framework in WiMAX point-to-multipoint (PMP) systems and a corresponding opportunistic scheduling algorithm with an adaptive power control scheme to provide QoS support to the heterogeneous traffic. Extensive simulation experiments have been carried out to evaluate the performance of our proposal. The simulation results show that our proposed solution can improve the performance of the WiMAX PMP systems in terms of packet loss rate, packet delay and system throughput.     

QoS-, Queue-and Channel-Aware Packet Scheduling for Multimedia Services in Multiuser SDMA/TDMA Wireless Systems

With the growing demand for wireless multimedia services and continuing emergence of new multimedia applications, it is necessary for the network to provide various levels of quality of service (QoS) while maximizing the utilization of channel resources. This paper presents an adaptive queuing model and a novel cross-layer packet scheduling algorithm for providing differentiated QoS and effective channel utilization in a space-division-multiple-access/time-division-multiple-access (SDMA/TDMA) system. At the medium access control (MAC) layer, we take into consideration the heterogeneous and bursty nature of multimedia traffic and provide for QoS requirements. At the physical (PHY) layer, we exploit the randomness of the physical channel by incorporating opportunistic scheduling and adopting adaptive modulation and coding (AMC). Performance results obtained by simulations show that by employing the proposed queuing model and packet scheduling algorithm, the system is able to provide for diverse QoS and achieve high throughput.     

A Unified Architecture for the Design and Evaluation of Wireless Fair Queueing Algorithms

Fair queueing in the wireless domain poses significant challenges due to unique issues in the wireless channel such as location-dependent and bursty channel errors. In this paper, we present a wireless fair service model that captures the scheduling requirements of wireless scheduling algorithms, and present a unified wireless fair queueing architecture in which scheduling algorithms can be designed to achieve wireless fair service. We map seven recently proposed wireless fair scheduling algorithms to the unified architecture, and compare their properties through simulation and analysis. We conclude that some of these algorithms achieve the properties of wireless fair service including short-term and long-term fairness, short-term and long-term throughput bounds, and tight delay bounds for channel access.     

Efficient Packet Scheduling Using Channel Adaptive Fair Queueing in Distributed Mobile Computing Systems

In a distributed mobile computing system, an efficient packet scheduling policy is a crucial component to achieve a high utilization of the precious bandwidth resources while satisfying users' QoS (quality of service) demands. An important class of scheduling techniques, namely, the wireless fair queueing algorithms, have been extensively studied recently. However, a major drawback in existing approaches is that the channel model is overly simplified – a two-state channel (good or bad) is assumed. While it is relatively easy to analyze the system using such a simple model, the algorithms so designed are of a limited applicability in a practical environment, in which the level of burst errors is time-varying and can be exploited by using channel adaptive coding and modulation techniques. In this paper, we first argue that the existing algorithms cannot cater for a more realistic channel model and the traditional notion of fairness is not suitable. We then propose a new notion of fairness, which bounds the actual throughput normalized by channel capacity of any two data connections. Using the new fairness definition, we propose a new fair queueing algorithm called CAFQ (Channel Adaptive Fair Queueing), which, as indicated in our numerical studies, outperforms other algorithms in terms of overall system throughput and fairness among error prone connections.     

Soft QoS provisioning using the token bank fair queuing scheduling algorithm

Future-generation wireless packet networks will support multimedia applications with diverse QoS requirements. Much of the research on scheduling algorithms has been focused on hard QoS provisioning of integrated services. Although these algorithms give hard delay bounds, their stringent requirements sacrifice the potential statistical multiplexing performance and flexibility of the packet-switched network. Furthermore, the complexities of the algorithms often make them impractical for wireless networks. There is a need to develop a packet scheduling scheme for wireless packet-switched networks that provides soft QoS guarantees for heterogeneous traffic, and is also simple to implement and manage. This article proposes token bank fair queuing (TBFQ), a soft scheduling algorithm that possesses these qualities. This algorithm is work-conserving and has a complexity of O(1). We focus on packet scheduling on a reservation-based TDMA/TDD wireless channel to service integrated real-time traffic. The TBFQ scheduling mechanism integrates the policing and servicing functions, and keeps track of the usage of each connection. We address the impact of TBFQ on mean packet delay, violation probability, and bandwidth utilization. We also demonstrate that due to its soft provisioning capabilities, the TBFQ performs rather well even when traffic conditions deviate from the established contracts.     

PSHO-HF-PM: An Efficient Proactive Spectrum Handover Mechanism in Cognitive Radio Networks

In the paper, we develop an efficient proactive spectrum handover mechanism by using packet scheduling algorithm, called PSHO-HF-PM, to reduce unusable channel. It effectively integrates several mechanisms (hole filling and packet migration) to reduce the bandwidth fragment and support QoS. Its basic idea is in that a new packet is scheduled by migrating some packets to other channels if none of holes in any channels can accommodate it; otherwise repeating the above processes after random waiting time. Meanwhile under an effective data structure, such as the balanced binary search tree, its computational complexity will be \(O(2n\log n)\) at most. In the proposed packet scheduling algorithm, packet migration plays a key role in the improvement of bandwidth efficiency and QoS. We also evaluate the performance of total service time for proactive spectrum handover mechanism based on a Preemptive Resume Priority M/G/1 queuing network model. The performance analysis and simulation results show that it performs much better than other proactive and reactive handover mechanism in collision rate, total service time, packet loss probability and bandwidth fragment ratio.     

Verifying Delivered QoS in Multihop Wireless Networks

The question that we consider here is the following: "How can a source verify the quality of service (QoS) experienced by its packet(s) at each hop to the destination in a multihop wireless network?" For example, if Bob needs to forward packets within some maximum delay of delta _B , how can the source verify that Bob in fact forwarded the packets within this bound? Answering this question will enable innovations in multihop wireless network deployments, where nodes may receive payment not only for forwarding packets but also for meeting some QoS guarantees. In this paper, we present protocols that enable verification of delivered QoS for individual packets, as well as verification of statistical QoS for groups of packets. The protocols are proven to be cheat proof. We also provide expressions for the minimum verifiable delay.     

Havana: Supporting Application and Channel Dependent QoS in Wireless Packet Networks

For wireless channels, interference mitigation techniques are typically applied at the packet transmission level. In this paper, we present the Havana framework which supports integrated adaptive-QoS in wireless packet networks by responding to impairments over multiple time scales that are present at the flow/session level. The Havana framework is based on three different control mechanisms that operate over distinct adaptation time scales. At the packet transmission time scale, a packet-based channel predictor determines whether to transmit a packet or not depending on the state of the wireless channel. At the packet scheduling time scale, a compensator credits and compensates flows that experience bad link quality. Over even longer time scales an adaptor regulates flows taking into account the ability of wireless applications to adapt to changes in the available bandwidth and channel conditions. We present the design and implementation of our framework and evaluate each of the proposed control mechanisms using the ns-2 simulator.     

The impact of multihop wireless channel on TCP performance

This paper studies TCP performance in a stationary multihop wireless network using IEEE 802.11 for channel access control. We first show that, given a specific network topology and flow patterns, there exists an optimal window size W* at which TCP achieves the highest throughput via maximum spatial reuse of the shared wireless channel. However, TCP grows its window size much larger than W* leading to throughput reduction. We then explain the TCP throughput decrease using our observations and analysis of the packet loss in an overloaded multihop wireless network. We find out that the network overload is typically first signified by packet drops due to wireless link-layer contention, rather than buffer overflow-induced losses observed in the wired Internet. As the offered load increases, the probability of packet drops due to link contention also increases, and eventually saturates. Unfortunately the link-layer drop probability is insufficient to keep the TCP window size around W'*. We model and analyze the link contention behavior, based on which we propose link RED that fine-tunes the link-layer packet dropping probability to stabilize the TCP window size around W*. We further devise adaptive pacing to better coordinate channel access along the packet forwarding path. Our simulations demonstrate 5 to 30 percent improvement of TCP throughput using the proposed two techniques.     

QoS Provisioning in Wireless IP Networks

This paper deals with quality of service (QoS) provision in wireless IP networks. QoS provision is particularly challenging in wireless networks, where network resources are generally limited, variable over time and shared. In the design of possible measures to assure QoS one should consider that standardization is well established for the network layer Internet Protocol and for many underlying technologies of frequent use (e.g. IEEE 802.11, BLUETOOTH or HIPERLAN II). Therefore, as far as research on QoS is concerned, there is little room in both the IP and the link-layers for improved IP over wireless interfaces. In this paper we illustrate a solution in which an intermediate Wireless Adaptation Layer (WAL) is transparently interposed between the IP layer and specific link-layer technologies as a solution to provide QoS. The WAL addresses two main issues: (i) compensation for channel impairments in different platforms in order to enhance wireless channel reliability and (ii) implementation of traffic control and packet scheduling mechanisms to satisfy bandwidth and delay requirements, as well as to enforce a general principle of fairness among the IP associations contending for network resources and achieve optimal exploitation of transmission capacity. The WAL consists of a set of modules, each one in charge of a specific task, which can be enabled or disabled depending on the specific network environment. The novelty of the WAL approach is its capability of adapting itself to different wireless interfaces selecting performance enhancing modules for specific networks. This requires to modify the standard TCP/IP protocol stack by introducing an intermediate layer between the IP layer and the Data Link layer, with performance enhancement purposes. This paper focuses on two modules in particular, namely a traffic control module, which is in charge of performing congestion control and channel state dependent scheduling (CSD) packet scheduling, and a forward error correction (FEC) module, which compensates for channel impairments. This paper presents the proposed architecture provided with these modules and reports some measurements and simulations highlighting benefits resulting from the use of such modules.     

一种适用于宽带无线IP网络的分组调度算法

自适应调制技术在许多新型的无线分组网络如WCDMA HSDPA、HiperLAN/2中得到广泛采用.本文在充分考虑自适应调制系统链路带宽随时隙呈不平均分布特点的基础上,提出一种全新的调度算法,自适应区分补偿公平队列(ADCFQ).该算法采用了基于工作量的分析方法,设计了不同功能的多个子队列,可以为系统所有待发流提供基本的QoS保证,为各个流公平共享剩余带宽,并能够通过合理的补偿机制克服无线环境中突发错误影响.分析和仿真结果表明,这一算法可以满足目标要求.此外,仿真中,针对自适应链路的特点,本文还提出了一种基于多状态Markov链的信道建模方法.     

Temporal fairness guarantee in multi-rate wireless LANs for per-flow protection

Wireless LAN technologies such as IEEE 802.11a and 802.11b support high bandwidth and multi-rate data transmission to match the channel condition (i.e., signal to noise ratio). While some wireless packet fair queuing algorithms to achieve the per-flow throughput fairness have been proposed, they are not appropriate for guaranteeing QoS in multi-rate wireless LAN environments. We propose a wireless packet scheduling algorithm that uses the multi-state (multi-rate) wireless channel model and performs packet scheduling by taking into account the channel usage time of each flow. The proposed algorithm aims at per-flow protection by providing equal channel usage time for each flow. To achieve the per-flow protection, we propose a temporally fair scheduling algorithm called Contention-Aware Temporally fair Scheduling (CATS) which provides equal channel usage time for each flow. Channel usage time is defined as the sum of the packet transmission time and the contention overhead time due to the CSMA/CA mechanism. The CATS algorithm provides per-flow protection in wireless LAN environments where the channel qualities of mobile stations are dynamic over time, and where the packet sizes are application-dependent. We also extend CATS to Decentralized-CATS (D-CATS) to provide per-flow protection in the uplink transmission. Using an NS-2 simulation, we evaluate the fairness property of both CATS and D-CATS in various scenarios. Simulation results show that the throughput of mobile stations with stable link conditions is not degraded by the mobility (or link instability) of other stations or by packet size variations. D-CATS also shows less delay and less delay jitter than FIFO. In addition, since D-CATS can coordinate the number of contending mobile stations, the overall throughput is not degraded as the number of mobile stations increases. This work was supported in part by the Brain Korea 21 project of Ministry of Education and in part by the National Research Laboratory project of Ministry of Science and Technology, 2004, Korea.     

Analysis of M-LWDF fairness and an enhanced M-LWDF packet scheduling mechanism

Modified largest weighted delay first(M-LWDF)is a typical packet scheduling algorithm for supporting hybrid real-time services over wireless networks.However,so far,there is little literature available regarding the theoretic analysis of M-LWDF fairness.This paper gives a theoretic analysis of M-LWDF fairness,which shows that M-LWDF fairness is related to channel condition,packet’s arrival process and the ratio of quality of service(QoS)requirements of different service queues.Given service QoS requirements and other parameters related to channel model and packet’s arrival process,the fairness is merely related to the ratio of the number of users in the service queues.Based on the analysis,an enhanced M-LWDF algorithm(EM-LWDF)is proposed and demonstrated in this paper.EM-LWDF is strictly designed in light of the fairness criteria of QoS requirements,so its fairness is almost not related to the ratio of the number of users in the service queues,and the theoretical value of fairness index is equal to 1.Simulation results validate the theoretic analysis and show the effectiveness of EM-LWDF in improving fairness.