一种分级WFQ的宽带无线接入系统QoS架构

文章介绍了加权公平排队(WFQ)分组调度算法和IEEE 802 16的QoS架构.在此基础上,文章结合分级WFQ分组调度算法和IEEE 802 16协议中所提供的控制机制提出了一种适合于BWA系统的QoS架构.该架构充分利用IEEE 802.16提供的控制机制,结合分级WFQ公平队列调度算法,在主动授予业务(UGS)、实时轮询业务(rtS)、非实时轮询业务(nrtPS)和尽力传输业务(BE)之间公平分配带宽,并保证各种业务的QoS特性,完成了在IEEE 802 16协议中留给用户自己定义的调度策略.     

Deterministic Time-Varying Packet Fair Queueing for Integrated Services Networks

In integrated services networks, the provision of Quality of Service (QoS) guarantees depends critically upon the scheduling algorithm employed at the network layer. In this work we review fundamental results on scheduling, and we focus on Packet Fair Queueing (PFQ) algorithms, which have been proposed for QoS wireline-wireless networking. The basic notion in PFQ is that the bandwidth allocated to a session is proportional to a positive weight _i . Because of the fixed weight assignment, the inherent in PFQ delay-bandwidth coupling imposes limitations on the range of QoS that can be supported. We develop PFQ with deterministic time-varying weight assignments, and we propose a low-overhead algorithm capable of supporting arbitrary piecewise linear service curves which achieve delay-bandwidth decoupling. Unlike existing service-curve based algorithms, our time-varying PFQ scheme does not exhibit the punishment phenomenon, and allows sessions to exploit the extra bandwidth in under-loaded networks.     

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.     

A Packet Scheduling Approach to QoS Support in Multihop Wireless Networks

Providing packet-level quality of service (QoS) is critical to support both rate-sensitive and delay-sensitive applications in bandwidth-constrained, shared-channel, multihop wireless networks. Packet scheduling has been a very popular paradigm to ensure minimum throughput and bounded delay access for packet flows. This work describes a packet scheduling approach to QoS provisioning in multihop wireless networks. Besides minimum throughput and delay bounds for each flow, our scheduling disciplines seek to achieve fair and maximum allocation of the shared wireless channel bandwidth. However, these two criteria can potentially be in conflict in a generic-topology multihop wireless network where a single logical channel is shared among multiple contending flows and spatial reuse of the channel bandwidth is possible. In this paper, we propose a new scheduling model that addresses this conflict. The main results of this paper are the following: (a) a two-tier service model that provides a minimum fair allocation of the channel bandwidth for each packet flow and additionally maximizes spatial reuse of bandwidth, (b) an ideal centralized packet scheduling algorithm that realizes the above service model, and (c) a practical distributed backoff-based channel contention mechanism that approximates the ideal service within the framework of the CSMA/CA protocol.     

基于帧的ATM层次调度机制性能界及其仿真研究

对网络交换节点中所采用的调度机制的研究是网络提供QoS保证的一个重要课题.在本文中,结合基于帧调度器的简单性和GPS(generalized processor sharing)算法的良好性能,提出了一种新颖的基于帧的层次调度算法HFFQ(Hierarchical Frame-based Fair Queueing).HFFQ能同时支持实时业务和非实时业务,另外采用了简单计数的方法来替代复杂的系统虚拟时间的计算过程,大大减少了算法的实现复杂度.最后,用理论分析和仿真的方法,对HFFQ的公平性、服务率等指标的性能进行了论证.结果显示,它和PGPS(Packet-by-packet GPS)相比,在性能上有很大的提高.     

A Distributed Fair Queueing (DFQ) Architecture for Wireless ATM Local Access Networks

The application of Asynchronous Transfer Mode (ATM) to a Wireless Local Area Network (WLAN) environment is an undertaking that poses many problems not encountered in either wireline ATM or data-only WLAN. Wireline ATM networks do not have to transmit over multiple-access, unreliable transmission media while data-only WLANs do not have to satisfy heterogeneous Quality of Service (QoS) contracts for multimedia services. To address this issue, we propose in this paper a DFQ-based WLAN architecture, designed as a centrally controlled network where a complex base station polls simpler mobile terminals for channel access.DFQ is an implementation of Fair Queueing (FQ) algorithm to schedule the access to the transmission channel among the mobile terminals. The implementation of DFQ introduces new design challenges, mainly in the packet scheduler. A DFQ scheduler is designed to allow fast and efficient processing of scheduling data. The DFQ algorithm is introduced and simulated for delay-sensitive connections, and the hardware implementation of the packet scheduler is discussed.The Centre for Wireless Communications is a national R&D Centre funded by the Singapore National Science and Technology Board     

一种支持服务类别的无线公平调度算法

本文提出了一种支持服务类别的无线公平调度算法:CoSB－WFS(基于服务类别的无线公平调度).算法区分不同的服务类别并可根据其业务需要进行不同的调度.考虑到无线信道的特殊性,算法引入了补偿和再分配模式.在仿真工具OPNET上模拟了算法并得到了性能改良的结果.     

面向WIA-PA工业无线传感器网络的确定性调度算法

WIA-PA （Wireless Networks for Industrial Automation-Process Automation）是我国自主制定的工业无线传感器网络标准,确定性调度技术是其中一项关键技术.但目前已有的确定性调度算法主要集中在通用传感器网络或WirelessHART,ISA100.11a等遵循国外标准的工业无线传感器网络中,未能针对WIA-PA网络进行优化设计.鉴于此,本文提出了一种适用于WIA-PA网络的基于回溯法的最优确定性调度算法,能够获取调度解的最大成功率;并以此为基础,进一步提出了一种基于最小时间裕度优先的时分多址调度算法（Least Slack First on Time Division Multiple Access,LSF-TDMA）.仿真实验结果表明,所提出的LSF-TDMA算法能够满足WIA-PA网络端到端数据传输的确定性需求,在调度解获取成功率接近于最优的同时,有效降低了算法复杂度.     

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.     

Channel-Aware Earliest Deadline Due Fair Scheduling for Wireless Multimedia Networks

Providing delay guarantees to time-sensitive traffic in wireless multimedia networks is a challenging issue. This is due to the time-varying link capacities and the variety of real-time applications expected to be handled by such networks. We propose and evaluate the performance of a channel-aware scheduling discipline and a set of policies that are capable of providing such delay guarantees in TDM-based wireless networks. First, we introduce the Channel-Dependent Earliest-Due-Date (CD-EDD) discipline. In this discipline, the expiration time of the head of line packets of users' queues is taken into consideration in conjunction with the current channel states of users in the scheduling decision. This scheme attempts to guarantee the targeted delay bounds in addition to exploiting multiuser diversity to make best utilization of the variable capacity of the channel. We also propose the violation-fair policy that can be integrated with the CD-EDD discipline and two other well-known scheduling disciplines [1, 2]. In this policy, we attempt to ensure that the number of packets dropped due to deadline violation is fairly distributed among the users. The proposed schemes can provide statistical guarantees on delays, achieve high throughput, and exhibit good fairness performance with respect to throughput and deadline violations. We provide extensive simulation results to study the performance the proposed schemes and compare them with two of the best known scheduling disciplines [1, 2] in the literature. Khaled M. F. Elsayed (S90-M95-SM02) received his B.Sc. (honors) in electrical engineering and M.Sc. in engineering mathematics from Cairo University in 1987 and 1990 respectively. He received his Ph.D. in computer science and computer engineering from North Carolina State University in 1995. He is now an Associate Professor in Cairo University, Egypt and is an independent telecommunications consultant. Between 1995 and 1997, he was a member of scientific staff with Nortel Wireless Systems Engineering in Richardson, TX.Dr. Elsayed was the editor for the Internet technology series of the IEEE Communications Magazine from 1998 until 2002. He has served on technical program committees for several IEEE, IFIP, and ITC conferences. He was the technical co-chair for IFIP MWCN 2003 conference in Singapore. He also served as an expert evaluator for the European Commission FP5 and FP6 programmes. His research interest is in the area of performance evaluation of communication networks including IP, wireless and optical networks. Ahmed Khattab received his B.Sc. (honors) and MS.C in Electronics and Communications Engineering from Cairo University in 2002 and 2004 respectively. Since August 2005, he is pursuing his PhD degree at Rice University, Texas. His research interests are in wireless networking and radio resource management.     

多用户多服务无线网络中感知用户体验的比例公平调度

The effective radio resource allocation algorithms, which satisfy diversiform requirements of mobile multimedia services in wireless cellular networks, have recently attracted more and more attention. This paper proposes a service-aware scheduling algorithm, in which the Mean Opinion Score (MOS) is chosen as the unified metric of the Quality of Experience (QoE). As the network needs to provide satisfactory services to all the users, the fairness of QoE should be considered. The Proportional Fair (PF) principle is adopted to achieve the trade-off between the network performance and user fairness. Then, an integer programming problem is formed and the QoE-aware PF scheduling principle is derived by solving the relaxed problem. Simulation results show that the proposed scheduling principle can perform better in terms of user fairness than the previous principle maximizing the sum of MOS. It also outperforms the max-min scheduling principle in terms of average MOS.     

分布式系统中多用户网络应用的概率型调度算法研究

多用户网络应用是分布式计算中最主要的形式之一。为了充分挖掘分布式系统中的计算资源,任务调度是解决该问题的关键。然而,由于多用户网络应用中存在的不确定性,使得当前的调度方法在动态性、实时性、适应性等方面都存在诸多不足。考虑到用户实时性需求,本文提出了概率型调度的思想。该思想将任务的分配看作概率事件,以用户角度的最短响应时间为目标,给出了多用户网络应用的排队模型,并进一步将调度定义为一个非线性规划问题。分析表明上述方法在任务到达过程、服务率方面存在限制,进而提出了一个基于强化学习理论自适应调度算法。该算法首先利用Markov决策过程（MDP）描述该调度问题,然后对任务到达过程和服务率知识进行在线的学习。一旦获得任务分配概率,遵从该概率可进行快速的任务调度。实验表明上述两个算法相比于Min-Min、Max-Min、Suffrage、ECT四种经典调度算法具有更短的平均响应时间。除此性能外,通过实验分析了该概率型调度方法的稳定性。     

QoS maintenance for fair queueing algorithms in wireless mobile networks

In order to extend fair queueing algorithms to wireless networks, we propose a channel error and handoff compensation scheme. A compensation is performed by a compensation server and a priority swapping mechanism. The proposed compensation scheme provides a short‐term fairness guarantee for an error‐free session, long‐term fairness guarantee for an erroneous session, fast handoff and traffic‐specific quality of service control. Copyright 2002 John Wiley & Sons, Ltd.     

LHFS-支持公平服务的CICQ混合调度策略

 针对现有联合输入交叉点排队交换结构(CICQ,Combined Input and Cross-point Queuing)调度策略无法提供基于"流"的服务质量保障,探讨了在CICQ交换结构实施基于流调度的可能性,提出一种能够为到达流提供公平服务的分层混合公平服务调度策略—LHFS(Layered and Hybrid Fair Scheduling).LHFS对每个输入、输出端口可独立地进行变长分组交换,其算法复杂度为O(1),具有良好可扩展特性.理论分析结果表明,LHFS能够为业务流提供时延上限和公平性保障.最后,基于SPES(Switching Performance Evaluation System)仿真系统对LHFS的性能进行了评估.     

Wireless Convergence Architecture: A Case Study Using GSM and Wireless LAN

The evolution of wireless networks has motivated the expansion of the static business environment to a mobile and wireless one. However, current and forthcoming wireless technologies are characterized by different attributes, regarding coverage area, offered bandwidth and delay. The transparent conjunction of various wireless technologies into a single mobile terminal can further boost the wireless explosion. This paper presents the Wireless Convergence Architecture (WCA) that incorporates different wireless interfaces under the same mobile terminal. Depending on the location and the availability of the underlying wireless network, automatic and seamless switching is performed to the most appropriate wireless network interface. Special care is taken to maintain continuous connectivity at the transport layer (TCP). WCA introduces software components both at the terminal and network side. A specific implementation is presented, based on two complementary wireless technologies – in terms of coverage area – an IEEE 802.11-compliant in the short local and a GSM in the wide area. To demonstrate the operational correctness of the architecture, experiments were performed using standard and proprietary networking applications.     

一种基于Contact的传感器网络查询策略研究

基于Contact的资源查询机制是依据小世界理论提出来的,该机制要求网络中各个节点不仅维护R跳以内的“邻居”节点的资源状态,而且还选择维护少数较远节点(Contact)的状态。Contact大大降低了查询源与目标的“分离度”。论文提出的SMQM查询机制在CARD和TRANSFER的研究成果基础上,对于Contact的选择方法进行了重要的改进。SMQM性能的仿真试验结论说明,SMQM查询机制的性能优于CARD协议。SMQM查询机制着眼于寻找“可行”的路径,而不是最“优”路径,由此降低了路径建立开销、单次查询的总能耗,提高了网络的生命周期。     

一种提高802.11无线Ad Hoc网络公平性的新机制-FFMA

实现多个数据流对无线信道的公平共享是802.11无线Ad Hoc网络中的一个重要议题,但802.11DCF机制在无线Ad Hoc网络中存在严重的公平性问题,甚至有可能出现单个节点或数据流独占信道而其他节点和数据流处于"饥饿"状态的情况.论文提出了一种新颖的保证数据流间公平性的MAC层接入机制FFMA(Flow rate-based Fair Medium Access),通过公平调度和公平竞争的方式,FFMA能够在数据流间公平地分配信道带宽资源.仿真结果表明,在无线Ad Hoc网络中,FFMA可以在保证信道吞吐量的前提下取得远优于802.11 DCF的数据流间的公平性.     

Lightweight Deployment-Aware Scheduling for Wireless Sensor Networks

Wireless sensor networks consist of a large number of tiny sensors that have only limited energy supply. One of the major challenges in constructing such networks is to maintain long network lifetime as well as sufficient sensing areas. To achieve this goal, a broadly-used method is to turn off redundant sensors. In this paper, the problem of estimating redundant sensing areas among neighbouring wireless sensors is analysed. We present simple methods to estimate the degree of redundancy without the knowledge of location or directional information. We also provide tight upper and lower bounds on the probability of complete redundancy and on the average partial redundancy. With random sensor deployment, our analysis shows that partial redundancy is more realistic for real applications, as complete redundancy is expensive, requiring up to 11 neighbouring sensors to provide a 90 percent chance of complete redundancy. Based on the analysis, we propose a scalable Lightweight Deployment-Aware Scheduling (LDAS) algorithm, which turns off redundant sensors without using accurate location information. Simulation study demonstrates that the LDAS algorithm can reduce network energy consumption and provide desired QoS requirement effectively. This research was partially supported by Natural Sciences and Engineering Research Council of Canada. Kui Wu received his Ph.D. in Computing Science from the University of Alberta, Canada, in 2002. He joined the Department of Computer Science at the University of Victoria, Canada in the same year and is currently an Assistant Professor there. His research interests include mobile and wireless networks, network performance evaluation, and network security. Yong Gao received his Master's degree and Ph.D. degree in computer science from University of Alberta, Canada, in 2000 and 2005 respectively. He is currently with the Irving K. Barber School of Arts and Sciences, UBC Okanagan, Canada. His research interests include search algorithms and AI, communication networks, and computational biology. Yang Xiao worked at Micro Linear as an MAC (Medium Access Control) architect involving the IEEE 802.11 standard enhancement work before he joined Department of Computer Science at The University of Memphis in 2002. Dr. Xiao is an IEEE Senior member. He was a voting member of IEEE 802.11 Working Group from 2001 to 2004. He currently serves as Editor-in-Chief for International Journal of Security and Networks (IJSN) and for International Journal of Sensor Networks (IJSNet). He serves as an associate editor or on editorial boards for the following refereed journals: (Wiley) International Journal of Communication Systems, (Wiley) Wireless Communications and Mobile Computing (WCMC), EURASIP Journal on Wireless Communications and Networking, and International Journal of Wireless and Mobile Computing. He serves as five lead/sole guest editor for five journal special issues. He serves as a referee/reviewer for many funding agencies, as well as a panelist for NSF. His research interests are Security/ Reliable Communications, Medium Access Control, Mobility/Location/Paging Managements, Cache Access and Replacement Policies, Quality of Service, Energy Efficiency, and Routing in wireless networks and mobile computing.     

Extended Performance Evaluation of PRADOS: A Scheduling Algorithm for Traffic Integration in a Wireless ATM Network

The MAC protocol, known as MASCARA (Mobile Access Scheme based on Contention And Reservation for ATM), is an infrastructure-based, adaptive TDMA scheme, which combines reservation- and contention-based access methods to provide multiple access efficiency and Quality-of-Service (QoS) guarantees to wireless ATM terminal connections that share a common radio channel. Radio channel sharing is performed by the PRADOS (Prioritized Regulated Allocation Delay Oriented Scheduling) algorithm. In this paper we assess the capability of PRADOS to guarantee to voice and data traffic types the QoS they need. The analysis leads to the conclusion that PRADOS cannot avoid the interference between the various types of traffic. A criterion to alleviate this drawback is also outlined at the end of the paper.