Scalable Multiple Channel Scheduling with Optimal Utility in Wireless Local Area Networks

This paper studies scheduling algorithms for an infra-structure based wireless local area network with multiple simultaneous transmission channels. A reservation-based medium access control protocol is assumed where the base station (BS) allocates transmission slots to the system mobile stations based on their requests. Each station is assumed to have a tunable transmitter and tunable receiver. For this network architecture, the scheduling algorithms can be classified into two categories: contiguous and non-contiguous, depending on whether slots are allocated contiguously to the mobile stations. The main objective of the scheduling algorithms is to achieve high channel utility while having low time complexity. In this paper, we propose three scheduling algorithms termed contiguous sorted sequential allocation (CSSA), non-contiguous round robin allocation (NCRRA) and non-contiguous sorted round robin allocation (NCSRRA). Among these, CSSA schedules each station in contiguous mode, while other two algorithms, NCRRA and NCSRRA, schedule stations in non-contiguous mode. Through extensive analysis and simulation, the results demonstrate that the CSSA with only slightly increased complexity can achieve much higher channel utility when compared to the existing contiguous scheduling algorithms. The NCRRA and NCSRRA on the other hand, results in significantly lower complexity, while still achieving the optimal channel utility compared to existing non-contiguous scheduling algorithms. Chonggang Wang received a B.Sc. (honors) degree from Northwestern Polytechnic University, Xi'an, China, in 1996, and M.S. and Ph. D. degrees in communication and information system from University of Electrical Science and Technology in China, Chengdu, China, and Beijing University of Posts and Telecommunications, Beijing, China, in 1999 and 2002, respectively. From September 2002 to November 2003 he has been with the Hong Kong University of Science and Technology, Hong Kong, where he is an associate researcher in the Department of Computer Science. He is now a post-doctoral research fellow in University of Arkansas, Arkansas. His current research interests are in wireless networks with QoS guarantee, sensor networks, peer-to-peer and overlay networks. Bo Li received the B.S. (summa cum laude) and M.S. degrees in the Computer Science from Tsinghua University, Beijing, P. R. China, in 1987 and 1989, respectively, and the Ph.D. degree in the Electrical and Computer Engineering from University of Massachusetts at Amherst in 1993. Between 1994 and 1996, he worked on high performance routers and ATM switches in IBM Networking System Division, Research Triangle Park, North Carolina. Since January 1996, he has been with Computer Science Department, the Hong Kong University of Science and Technology, where he is an associated professor and co-director for the ATM/IP cooperate research center, a government sponsored research center. Since 1999, he has also held an adjunct researcher position at the Microsoft Research Asia (MSRA), Beijing, China. His current research interests include wireless mobile networking supporting multimedia, video multicast and all optical networks using WDM, in which he has published over 150 technical papers in referred journals and conference proceedings. He has been an editor or a guest editor for 16 journals, and involved in the organization of about 40 conferences. He was the Co-TPC Chair for IEEE Infocom'2004. He is a member of ACM and a senior member of IEEE. Krishna M. Sivalingam (ACM ‘93) is an Associate Professor in the Dept. of CSEE at University of Maryland, Baltimore County. Previously, he was with the School of EECS at Washington State University, Pullman from 1997 until 2002; and with the University of North Carolina Greensboro from 1994 until 1997. He has also conducted research at Lucent Technologies' Bell Labs in Murray Hill, NJ, and at AT&T Labs in Whippany, NJ. He received his M.S. and Ph.D. degrees in Computer Science from State University of New York at Buffalo in 1990 and 1994 respectively; and his B.E. degree in Computer Science and Engineering in 1988 from Anna University, Chennai (Madras), India. While at SUNY Buffalo, he was a Presidential Fellow from 1988 to 1991. His research interests include wireless networks, optical wavelength division multiplexed networks, and performance evaluation. He holds three patents in wireless networks and has published several research articles including more than twenty-five journal publications. He has published an edited book on Wireless Sensor Networks in 2004 and on optical networks in 2000 and in 2004. He is a member of the Editorial Board for ACM Wireless Networks Journal, IEEE Transactions on Mobile Computing, and KICS Journal of Computer Networks. He has served as a Guest Co-Editor for special issues of ACM MONET on “Wireless Sensor Networks” in 2003 and 2004 and an issue of IEEE Journal on Selected Areas in Communications on optical WDM networks (2000). He is co-recipient of the Best Paper Award at the IEEE International Conference on Networks 2000 held in Singapore. His work has been supported by several sources including AFOSR, NSF, Cisco, Intel and Laboratory for Telecommunication Sciences. He is a member of the Editorial Board for ACM Wireless Networks Journal, IEEE Transactions on Mobile Computing, and KICS Journal of Computer Networks. He is serving as Technical Program Co-Chair for the First IEEE Conference on Sensor Communications and Networking to be held in Santa Clara, CA in 2004. He has served as General Co-Chair for SPIE Opticomm 2003 (Dallas, TX) and for ACM Intl. Workshop on Wireless Sensor Networks and Applications (WSNA) 2003 held on conjunction with ACM MobiCom 2003 at San Diego, CA. He served as Technical Program Co-Chair of SPIE/IEEE/ACM OptiComm conference at Boston, MA in July 2002; and as Workshop Co-Chair for WSNA 2002 held in conjunction with ACM MobiCom 2002 at Atlanta, GA in Sep 2002. He is a Senior Member of IEEE and a member of ACM. Kazem Sohraby received the BS, MS and PhD degrees in electrical engineering and the MBA from the Wharton School, University of Pennsylvania, Philadephia. He is a Professor of the Electrical Engineering Department, College of Engineering, University of Arkansas, Fayetteville. Prior to that, he was with Bell Laboratories, Holmdel, NJ. His areas of interest include computer networking, signaling, switching, performance analysis, and traffic theory. He has over 20 applications and granted patents on computer protocols, wireless and optical systems, circuit and packet switching, and on optical Internet. He has several publications, including a book on The Performance and Control of Computer Communications Networks (Boston, MA: 1995). Dr Sohraby is a Distinguished Lecturer of the IEEE Communications Society, and serves as its President's representative on the Committee on Communications and Information Policy (CCIP). He served on the Education Committee of the IEEE Communications Society, is on the Editorial Boards of several publications, and served as Reviewer and Panelist with the National Science Foundation, the US Army and the Natural Sciences and Engineering Research Council of Canada.     

IEEE 802．16中基于信道状态的改进分组调度算法

为适应IEEE802．16无线网路的特点,降低数据的分组超时率,提高数据的平滑性,在基于信道状态的分组调度算法（CSDPS算法）的基础上,提出了一种基于信道状态的改进分组调度算法。该算法把业务区分与信道状态结合起来,既考虑了不同业务的QoS需求,也考虑了无线网络的信道特点。在降低发送速率上,给出降低速率的具体计算公式。通过理论分析,用改进算法与原有CSDPS算法进行了对比。可以发现,改进算法在分组超时率和数据平滑性上都有较大改善。     

一种具有小尺度公平的无线分组调度算法

本文在调度判决时考虑到用户的访问时延限制,比例公平调度算法基础上提出了M-PF算法。本文建立了无线分组调度系统模型,通过仿真对新算法在小尺度服务时间保证、大尺度服务时间公平和系统吞吐量等方面的性能进行分析,研究了系统参数对算法性能的影响。结果证明,新算法在保证系统吞吐量和大尺度公平性的同时可以提供更好的小尺度服务时间保证。     

Packet Loss Fair Scheduling Scheme for Real‐Time Traffic in OFDMA Systems

In this paper, we propose a packet scheduling discipline called packet loss fair scheduling, in which the packet loss of each user from different real‐time traffic is fairly distributed according to the quality of service requirements. We consider an orthogonal frequency division multiple access (OFDMA) system. The basic frame structure of the system is for the downlink in a cellular packet network, where the time axis is divided into a finite number of slots within a frame, and the frequency axis is segmented into subchannels that consist of multiple subcarriers. In addition, to compensate for fast and slow channel variation, we employ a link adaptation technique such as adaptive modulation and coding. From the simulation results, our proposed packet scheduling scheme can support QoS differentiations while guaranteeing short‐term fairness as well as long‐term fairness for various real‐time traffic.     

Packet Scheduling Algorithm Considering a Minimum Bit Rate for Non‐realtime Traffic in an OFDMA/FDD‐Based Mobile Internet Access System

In this letter, we consider a new packet scheduling algorithm for an orthogonal frequency division multiplexing access/frequency division duplex (OFDMA/FDD)‐based system, e.g., mobile broadband wireless access or high‐speed portable internet systems, in which the radio resources of both time and frequency slots are dynamically shared by all users under a proper scheduling policy. Our design objective is to increase the number of non‐realtime service (e.g., WWW) users that can be supported in the system, especially when the minimum bit rate requirement is imposed on them. The simulation results show that our proposed algorithm can provide a significant improvement in the average outage probability performance for the NRT service, i.e., significantly increasing the number of NRT users without much compromising of the cell throughput.     

一种新型的OFDMA系统调度算法

近年来正交频分多址接入（OFDMA,Orthogonal Frequency Division Multiplexing Access）技术在无线通信中的应用越来越广泛。针对OFDMA系统中的资源调度问题,介绍和分析了OFDMA系统中常见的分组调度算法-轮询算法、最大载干比算法和比例公平算法,并且提出了一种结合了遗传搜索的自适应调度算法。最后在此基础上对这四种分组调度算法进行了仿真和分析,仿真结果表明,不管是系统吞吐量还是公平性,自适应调度算法都有较好的性能提升。     

应用网络编码的分组交换调度算法

网络编码理论与交换调度算法相结合重点是实现在联合输入输出排队（CIOQ）交换结构中提供组播服务。文章证明了对一个流中的分组进行线性网络编码可以承载不允许网络编码时不能够承载的交换流量模式,也就是说,网络编码允许CIOQ交换结构在实现组播服务时有更大的速率区域,并给出了基于图论方法的描述。运用增强冲突图的稳定集多面体等概念,文章证明了计算离线调度的问题可以简化成某种图染色问题,同时,也针对组播调度提出了一个称之为最大权重稳定集的在线调度算法。     

下行SDM/OFDMA系统中基于效用函数的多用户调度算法

该文研究了空分复用/正交频分多址(SDM/OFDMA)无线通信系统中的多用户调度问题,针对该系统的空时频三维调度特点,提出一种基于效用函数的多用户调度算法。该算法利用空间多用户分集获得增益,同时兼顾系统的整体效率和用户的个体效用。通过计算机仿真验证了算法具有和穷举搜索算法相近的性能,但算法复杂度大大降低。     

HSDPA系统中分组调度方法的性能比较

讨论了高速下行链路分组接入(HSDPA)系统中适合采用的分组调度方法。依据HSD-PA系统的特点,讨论了MaxC/I、RoundRobin和Max/Min三种调度方法,并通过计算机仿真,对其性能进行了分析、比较。结果表明,Max/Min调度是一种适合于HSDPA系统的调度方法。     

基于VirtualClock调度算法的接入允许控制算法

本文针对于Virtual Clock调度算法提出了一种基于生存期的接入允许控制算法.原有Virtual Clock的接入允许控制算法没有考虑到系统中在有连接建立和拆除的情况下如何动态分配带宽,致使分组的时延无法确保.本文从Virtual Clock算法的参考模型出发,对带宽释放和分配的时机作出规定.理论分析和仿真结果表明,本文的算法能够保证Virtual Clock算法的时延特性.本文的思路对于其他调度算法的接入允许算法也具有参考意义.     

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

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

基于不完备CSI的OFDMA公平资源分配算法

针对在信道状态信息不完备时,很难兼顾系统容量和公平性这一问题,通过引入公平松弛因子,提出一种公平性可调的遍历容量最大化资源分配算法。为了降低计算复杂度,在利用对偶优化方法求解拉格朗日算子过程中,提出同层循环迭代的搜索方式以代替传统的内外层循环迭代方式。通过仿真和分析表明,该算法在满足公平性的同时实现了遍历容量最大化,且计算复杂度明显降低。     

Joint Downlink Scheduling and Radio Resource Allocation for User-Individual QoS in Adaptive OFDMA Wireless Communication Systems

1Introduction Futurewirelessandmobilecommunicationsystems areexpectedtoofferhigherdatarates,tosupporta largenumberofsubscribersandtoensurethefulfillment ofQualityofService(QoS)requirements,giventhe limitedavailabilityoffrequencyspectrumandtimevary ingchan…     

OFDM系统分组调度算法仿真与分析

对于蜂窝正交频分复用(OFMA)系统,分组调度技术是影响系统性能提升的重要因素。分组调度算法是为分组业务提供资源分配及复用的方法。这里介绍了分组调度技术原理及几种经典的调度算法,并通过Matlab仿真,对几种调度算法的公平性和吞吐量进行了比较。通过仿真可知,比例公平算法(PF,Proportional Fair)平衡考虑了系统吞吐量与公平性,取得了较好的效果。     

非理想状态信息下SC-FDMA上行链路的信道调度

信道依赖调度(CDS)通过在信道里使用多用户分集和频率选择性来增加蜂窝系统的数据吞吐量,主要研究非理想信道状态信息(CSI)对CDS的影响。具体来说,当CSI有反馈延时,分析具有未编码自适应调制及CDS的上行链路单载波频分多址(SC-FDMA)系统的数据吞吐量。频域资源分配采用集中式和分布式的子载波映射方案。通过仿真可以看到在应用CDS时,集中式的子载波映射产生最高的总数据吞吐量,然而,当信道迅速变化时,集中式映射对CSI的质量以及信道容量增益的迅速减少非常灵敏。对于高机动性的用户来说,具有静态轮询调度方案的分布式映射更加合适。     

认知无线电网络中基于包调度算法的主动频谱切换

认知无线电网络中,主用户出现在自己的授权频段,但被次用户占用,此时次用户进行频谱切换.主动频谱切换机制是一种可以提高网络的带宽利用率,同时降低丢包率的方法.基于一个有效的包调度算法,提出一个主动频谱切换机制,以期减少频谱切换发生时的不可用信道.该包调度算法有效地集成了两个算法:频谱空洞填充算法和包迁移算法,来减少丢包率和带宽碎片.实验仿真结果验证了该主动频谱切换机制的有效性.     

基于优先级的包插入队列调度算法仿真研究

提出一种高优先级数据包插入到低优先级数据包中发送的新型队列调度算法,该算法不仅较大幅度地降低了高优先级数据包的时延和时延抖动,同时不会降低带宽利用率,具有很强的实用性.通过OPNET建模验证了此种算法的有效性.     

无线环境下失真和时限感知的视频分组调度机制

现有无线分组调度算法一般以最大化系统吞吐量或者保证用户之间公平性为目标。然而,不同视频分组之间存在着重要性差异,使得传统的内容无关调度算法不适用于无线视频传输。充分发掘视频分组之间存在的重要性差异并准确衡量视频分组的传输失真,能够在资源受限的无线环境下更合理地分配资源,提高视频传输质量。该文首先提出一种分组级别视频传输失真衡量模型,用于预测视频分组丢失对视频质量的影响,然后考虑分组时限的影响,提出分组级别的时限扩展模型。在此基础上,利用正交频分复用(OFDM)技术在无线资源(时域、频域及功率)分配上的灵活性,提出一种基于梯度的失真和时限感知调度算法。仿真结果表明该文所提出的调度算法相对于传统内容无关算法最大有4.3 dB的平均峰值信噪比(PSNR)增益。     

Opportunistic scheduling for an OFDMA system with multi‐class services

In this paper, we study an opportunistic scheduling problem in an OFDMA system, in which sub‐carriers of the system are allocated to each user in each time slot considering the time‐varying channel condition and QoS requirement of each user. We consider two different classes of services that are represented with different types of utility functions. The utility function for a user in one class is defined as a function of its average data rate, which can be applicable to best‐effort services and the utility function for a user in the other class is defined as a function of its instantaneous data rate, which can be applicable to rate‐sensitive services. Those two types of utility functions have been extensively considered in opportunistic scheduling in wireless networks. However, in most of the previous work, they are considered separately in different problems. In this paper, we formulate a stochastic optimization problem that can treat those two types of utility functions in a single problem, which enables us to implement an opportunistic scheduling algorithm that can consider those two classes of services in a single system in a unified way. Through simulations, we first show that our algorithm provides a good approximation to the optimal solution. In addition, we also verify the appropriateness of our utility models. Copyright © 2010 John Wiley & Sons, Ltd.     

Beamforming for Downlink Multiuser MIMO Time‐Varying Channels Based on Generalized Eigenvector Perturbation

A beam design method based on signal‐to‐leakage‐plus‐noise ratio (SLNR) has been recently proposed as an effective scheme for multiuser multiple‐input multiple‐output downlink channels. It is shown that its solution, which maximizes the SLNR at a transmitter, can be simply obtained by the generalized eigenvectors corresponding to the dominant generalized eigenvalues of a pair of covariance matrices of a desired signal and interference leakage plus noise. Under time‐varying channels, however, generalized eigendecomposition is required at each time step to design the optimal beam, and its level of complexity is too high to implement in practical systems. To overcome this problem, a predictive beam design method updating the beams according to channel variation is proposed. To this end, the perturbed generalized eigenvectors, which can be obtained by a perturbation theory without any iteration, are used. The performance of the method in terms of SLNR is analyzed and verified using numerical results.