摘要：文章介绍了加权公平排队(WFQ)分组调度算法和IEEE 802.16的QoS架构。在此基础上，文章结合分级WFQ分组调度算法和IEEE 802.16协议中所提供的控制机制提出了一种适合于BWA系统的QoS架构。该架构充分利用IEEE 802.16提供的控制机制，结合分级WFQ公平队列调度算法，在主动授予业务(UGS)、实时轮询业务(rtPS)、非实时轮询业务(nrtPS)和尽力传输业务(BE)之间公平分配带宽，并保证各种业务的QoS特性，完成了在IEEE 802.16协议中留给用户自己定义的调度策略。
要害词：IEEE 802.16协议；宽带无线接入；加权公平排队；服务质量
Abstract:The (WFQ) packet scheduling algorithm and the QoS architecture of IEEE 802.16 are introdUCed. Based on the control mechanism supported by the Hierarchical WFQ packet scheduling algorithm and IEEE 802.16 protocols, a QoS architecture for Broadband Wireless Access Systems (BWA) is proposed. This architecture can make better use of IEEE 802.16 control mechanism and realize fair bandwidth allocation among the Unsolicited grant Service (UGS), Real Time Polling Service (rtPS), non-Real Time Polling Service (nrtPS) and Best Effort (BE) transmission service. It can also guarantee the QoS of various services, thus implementing the scheduling reserved by IEEE 802.16 for users to make specific definitions.
Key Words:IEEE 802.16 protocol; broadband wireless access; weighted fair queueing (WFQ); QoS
在不久的将来，宽带城域无线接入(BWA)系统将成为全球通信架构中的一个重要的组成部分。随着无线数据服务越来越受欢迎以及用户多媒体业务需求的不断增长，人们提出了对不同层次的业务提供不同QoS服务的要求。在所有需要被解决的技术问题中，分组调度是最重要的(调度算法提供了带宽控制、拥塞控制机制)。在传统的有线网络中人们已经设计了许多性能优异的公平队列分组调度算法，如加权公平排队(WFQ)。IEEE 802.16协议中定义了业务流的分类和带宽请求方法，但没有对具体的调度算法做出规定而是将其留给设备制造商来解决。由于控制消息的统一性，因此采用不同调度算法的不同厂商的设备依然可以通用。
1 WFQ分组调度算法
假设一个队列系统总的出口容量为C，F 是建立在这个链路上的流的集合，rf, (f∈F )为与每一个流的服务速率。每一个业务f∈F 建立一个分组队列，到达的分组以先入先出(FIFO)的顺序加入到队列中，f 中的第i个到达分组的时间戳为t i，第i 个分组的长度为p i(计算单位为字节)，时间戳的计算公式为：
其中VF 为系统的参考虚时钟，它是由调度器所保存的变量，F 中所有的队列都公用一个VF，它是F 中传输最后一个分组的时间戳。;;;;;
是队列f中的第i -1个分组的时间戳，该时间戳定义了分组被调度的先后顺序，WFQ调度器为每一个到达的分组计算一个时间戳，并以时间戳的顺序为服务的顺序。虚时钟VF 是一个分段线性函数，它用数学表达式为：
其中B(t 1, t 2)是在时间(t 1, t 2)内有业务的业务流。当调度器服务完一个分组后，选择各个队列中时间戳最小的分组来服务。
2 IEEE 802.16的QoS架构
IEEE 802.16的具体内容参见文献[1]。IEEE 802.16协议将业务分为4类：主动授予业务(UGS)、实时轮询业务(rtPS)、非实时轮询业务(nrtPS)和尽力传输业务(BE)。
在文献[2]中，UGS业务被设计用来支持实时的、周期性的、固定包大小的业务流，例如IP语音(VoIP)业务。在UGS业务中用户站(SS)禁止使用任何竞争请求机会，基站(BS)不提供任何单播请求机会给SS，也不答应使用捎带请求(PiggyBack)。UGS业务主要的服务参数为：授予大小、授予间隔、授予抖动。ti为第i个数据包被发送的时间。要求：
t 0+i×授予间隔≤ti≤t 0+i×授予间隔+抖动。
;RTPS业务被设计用来支持实时的、周期性的、可变包大小的业务流，例如MPEG流。这项服务需要BS给SS提供周期性的单播轮询机会以满足业务流的实时需要，以便SS去指定想要授予的数据传输机会的大小。这项服务中SS禁止使用竞争请求和捎带请求。主要的服务参数为：轮询间隔、轮询抖动、最小预约速率。
nrtPS流被设计用来支持非实时的、可变包大小的、有一定规则性的业务，如高带宽的FTP。这项服务由BS为其提供单播轮询请求机会，同时也被答应使用竞争和捎带请求。要害的服务参数是：轮询间隔、最小预约速率、业务优先级。
BE业务只答应使用竞争和捎带请求，不答应使用周期性单播请求。主要的QoS参数是：最小预约业务速率、业务优先级。
3 WFQ分级分组调度算法
在文献[3]中提到了WFQ分级分组调度算法，其中将业务分为BE业务、严格的QoS (Hard-QoS)业务和稍宽松的QoS(Soft-QoS)业务。
分组调度算法分两级共4个部分(见图1)：
(1)Hard-QoS服务器中的调度。
(2)Soft-QoS服务器中的调度。
(3)BE服务器中的调度。
(4)3个服务器之间的调度。
(1)、(2)、(3)属于第二级调度，(4)属于第一级调度。所有这4个部分都是运用WFQ算法来完成的。
文献[3]中的调度算法是对分组进行调度的。IEEE 802.16中最重要的是上行链路的带宽分配策略，本文通过用分级WFQ算法对时隙资源进行调度来保证各个业务的QoS。
将IEEE 802.16的QoS定义与分级WFQ算法的定义对应起来，将UGS、rtPS、nrtPS和BE业务也分为三大类：第一类为周期性固定分配的业务，这类业务的B min = B max，包括UGS业务、rtPS和nrtPS的单播轮询带宽请求机会；第二类为有最小带宽预约的业务，这类业务的B min <B max，包括rtPS和nrtPS，这类业务为了保证rtPS的实时性，并将rtPS和nrtPS业务进行隔离，对rtPS设计了比nrtPS更高的优先权，即当rtPS的时间戳和nrtPS的时间戳一样的时候，优先选择rtPS来传输；第三类为没有最小带宽预约的业务，这类业务B min=0，因此这类业务包括BE业务和最小预约带宽为0的nrtPS业务。
4 WFQ分级调度QoS架构
本文设计的结合WFQ分级调度算法的QoS架构如图2所示。
WFQ分级调度算法的QoS架构主要由两个部分组成：调度控制器、调度器。
调度控制器的主要功能包含两部分：
(1)依据单播轮询、竞争、捎带请求收到的带宽请求给各个队列填充适当大小的传输机会。调度器根据WFQ算法对这些传输机会进行调度。对UGS业务和周期性的单播轮询传输机会填充特征表[4]。
通过填充特征表，来模拟Hard-QoS周期性规则数据源，只不过在这里数据源产生的不是分组，而是一个个的传输机会。
对于第二类队列和第三类队列，在调度完一个传输机会后必须通过竞争、单播轮询或捎带请求来决定下一个传输机会的大小，因此调度控制器负责翻译接收到的带宽请求并给各个队列提供传输机会。
(2)调度控制器根据收到的各种形式的带宽请求来控制各个队列的权重。第一类队列中的权重是以每个第一类队列的业务的最小预约带宽Bmin(f )为权重。第二类队列的权重是以Bmin(f )和priorityf为权重的。第三类队列以priorityf为权重。以上是第二级调度的权重分配原则。总调度器即第一级调度的权重分配原则为：Hard-QoS调度器的权重是
即包括UGS业务的总带宽和周期性单播轮询业务所占的带宽；Soft-QoS调度器的权重是
即第二类业务的预约总带宽；BE调度器的权重为：
即除去第一类和第二类业务所占的带宽剩余的带宽。调度控制器根据网络控制消息和带宽请求控制所有的队列和调度器的权重。
;调度器的主要功能是根据各个队列的权重对传输机会进行二级WFQ调度。调度器分4个部分：
(1)Hard-QoS调度器。
(2)Soft-QoS调度器。
(3)BE调度器。
(4)总调度器。
其中(1)、(2)、(3)属于第二级调度，(4)负责对(1)、(2)、(3)调度器进行第一级调度。第一类队列中分组的调度准则为：;;;
;;
f∈第一类队列，其中Bmin(f; )为第一类队列中各个业务流的最小预约带宽，对于UGS业务和周期性授予的单播轮询机会，其最小预约带宽是Bmin(f; )=Bmax(f; )，
因此这类业务所预约的带宽作为公平排队算法的权重经过WFQ算法运算过后，选择所有第一类队列中的时间戳t i 最小的传输机会映射到上行映射(UL-MAP)中去。第二类队列中分组的调度准则为：为第二类队列中的分组计算两个时间戳
f∈第二类队列，Vf为第二类队列中保存的全局虚拟时间变量；
f∈第三类队列，Vf为第三类队列中保存的全局虚拟时间变量，priorityf为第三类队列的优先级。通过比较这两个时间戳选择一个最小的进行调度，若该传输机会是由Soft-QoS调度器负责调度，则只增加Soft-QoS调度器中的虚拟时间变量；若BE调度器负责调度，则只增加BE调度器中的虚拟时间变量，调度器间互相不影响。这样第二队列中的分组就做到了由Soft-QoS调度器和BE调度器联合调度。
第三类队列中的分组的调度原则为：
f∈第三类队列，priorityf 为业务f的优先级参数。通过给不同的业务分配不同的优先级参数来给不同的队列分配不同的加权值，从而在业务之间按优先级不同分配不同的带宽资源。
总调度器给Hard-QoS调度器选择出来的分组计算一个时间戳：
给Soft-QoS调度器选择出来的分组计算一个时间戳：
给BE调度器选择出来的分组计算一个时间戳：
上面3个时间戳中Vf为总调度器中保存的传输的最后一个分组的时间戳，是一个参考虚时间。;是分组所在的第二级调度器中上一个分组的时间戳。经过上面的计算调度器选择一个最小的时间戳的分组(即传输机会)安排到UL-MAP中。这样既做到了在3种队列之间按照权重分配带宽又不会造成带宽的浪费。
5 系统性能分析
WFQ分组调度算法基于文献[5]中Bennett和Zhang提出的分级调度体系结构，将算法应用到IEEE 802.16中，算法本身分析所得到的性能是一样的。分级公平调度所采用的算法不一定要限制到WFQ算法上，成熟的公平队列调度算法还有改进加权公平队列算法(WF2Q)、自时钟公平队列算法(SCFQ)、开始时间公平队列算法(SFQ)等，相应的结合分级调度后的算法有分级加权公平队列算法(H-WFQ)、分级自时钟公平队列算法(H-SCFQ)、分级开始时间公平队列算法(H-SFQ)、分级改进加权公平队列算法(H-WF2Q)等。文献[4]对各种算法的性能有具体的仿真结果。
6 结论
本文结合分级WFQ调度算法，提出了一种适合于IEEE 802.16的有QoS保证的调度体系结构。该体系结构充分利用IEEE 802.16提供的控制机制，结合分级WFQ公平队列调度算法，在UGS、rtPS、nrtPS和BE业务之间公平分配带宽，并保证各种业务的QoS特性，完成了在IEEE 802.16协议中留给用户自己定义的调度策略。本文只提供一种思路，下一步还应考虑竞争时隙资源的分配和内存治理等问题[6]。
7 参考文献
[1] IEEE 802.16-2001 IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems [S].
[2] Janez Bostic, Gorazd Kandus. MAC Scheduling for Fixed Broadband Wireless Access Systems [EB/OL]. http://www.cs.ucr.edu/~michalis/COURSES/260-03/papers/janez802-16.pdf.
[3] 李蕾,张晓敏. 应用WFQ的分级、分组调度算法 [J]. 山东大学学报(工学版),2002,32(4): 167—171.
[4] Chu Guosong, Wang Deng, Mei Shunliang. A QoS Architecture for the MAC Protocol of IEEE 802.16 BWA System [C]. ICCCAS2002.
[5] Bennett J C R, Zhang Hui. Hierarchical Packet Fair Queuing Algorithms [EB/OL]. http://www.acm.org/sigs/sigcomm/ccr/archive/1996/conf/
bennett.pdf.
[6] Performance Evaluation of Scheduling Mechanisms for Broadband Networks [EB/OL]. Performance Evaluation of Scheduling Mechanisms for Broadband Networks.
杨博，西安电子科技大学ISN国家重点实验室在读硕士生，主要从事无线宽带城域网络的研究。
刘琰，西安电子科技大学ISN国家重点实验室在读硕士生，主要从事无线宽带城域网络和扩频通信方面的研究。
刘乃安，西安电子科技大学ISN国家重点实验室MCN室主任，教授。主要从事移动计算网络、扩展频谱通信、无线通信、移动通信的研究工作。已发表论文20余篇，出版教材和著作3部、译著1部，承担国家自然科学基金项目、国家“863”计划项目及中外合作项目多项。
