摘要：针对无线信道中与时间和位置相关性错误，本文简要介绍了IEEE802.16d协议的QoS服务模型，在对WiMax的QoS机制和调度策略进行了深入的研究后，提出了一种新的MAC层分级分组调度架构。以满足不同类型业务的QoS需求，解决了无线信道特殊性带来的调度问题。
引言
随着VoIP电话、视频会议和在线视频等多媒体业务迅猛发展，对网络性能提出了与传统的网页浏览、FTP服务、E-mail等业务不同的需求，不同类型的业务具有各自明确的服务质量(QoS，QualityofService)成为现代通信网络的一大特征。旨在提供传输距离更远、速度更高的无线城域网规范—WiMax标准中，无线信道的位置依赖性、突发和高的信道误码也成为其QoS要面对的首要问题。针对不同的应用需求，802.16d标准中为QoS定义了四种业务类型，明确规范了交互机制，但将调度等内容留待开发者自行解决。
文献[2]提出一种新型的CIF-Q调度算法，能够较好地适应无线特性、满足实时要求，但缺乏对多类型业务的区别服务。文献[3]提出的CSDPS算法能够不依赖于信道特性，却无法保证时延限制。将文献[4]提出的分级体系结构应用到WiMax的QoS调度架构中，提出了两层的分组调度算法，针对不同类型业务的QoS需求，在良好适应无线特性的同时，实现对不同业务应用的支持。
IEEE802.16d的服务类型
主动授予服务(UGS，UnsolicitedGrantService)
UGS业务用于传输周期性的、包大小固定的实时数据业务，其典型业务是VoIP电话。UGS业务一旦申请成功，在传输过程中就不需要再去申请。BS周期性地强制调度，不接收来自SS的竞争请求机会，同时禁止使用捎带请求，这样避免了带宽请求引入的开销和时延。
实时轮询服务(rtPS，Real-timePollingService)
rtPS主要用于支持周期性的、包大小可变的实时业务，如MPEG视频业务。rtPS提供周期性的单播轮询带宽请求机会，从而使得该连接能够周期地改变带宽请求。BS也不接收来自SS的其他竞争请求机会和捎带请求。这种服务比UGS的请求开销大，但能按需动态分配带宽。
非实时轮询服务(nrtPS，Non-Real-timePollingService)
nrtPS主要用于支持非周期、变长分组的非实时VBR服务流，如高带宽的FTP业务流，它有最小速率要求。BS提供比rtPS轮询间隔更长的周期或不定期的单播请求机会，SS也可以使用竞争和捎带请求的方式来请求带宽。
尽力而为服务(BE，BestEffortService)
BE主要用于支持非实时、无任何速率和时延要求的分组数据业务，其稳定性由高层协议来保证。典型业务是Telnet和Http服务。SS可以随时提出带宽申请，允许使用任何类型的竞争请求机会和捎带请求，但是不允许它们使用任何单播轮询请求机会。
QoS调度架构的设计
本架构的设计见图1。服务请求通过分类器后，按照QoS需求特性，将业务流分组放入不同队列。从队列中取出的请求加以流量监控，保证在对用户流量进行规约的同时，允许保持业务流限定范围内的突发性。通过流量监控后的服务请求先进入下层调度，针对同种排队类型的业务进行调度，包括实时调度、非实时调度和BE调度。上层总调度针对不同种排队类型业务进行总体统筹安排。下面将对这些模块进行深入分析。主要由下面几个部分组成：
图1 调度构架图
调度控制器
四种类型业务的带宽请求方式不同，对时延、抖动和速率等参数的要求也不同。考虑到无线信道特性，采用如下调度控制策略：为UGS业务预留一定带宽BUGS，维持特征表，用于定期给SS分配相应的带宽来发送UGS业务流。对于rtPS业务，通过确定其单播轮询间隔的参数值，可以调整实时业务传输机会的多寡和带宽分配量。对于nrtPS业务，通过确定其单播轮询间隔来调整获取传输机会的周期，保证非实时业务的最小速率。并检查带宽的空余量，决定是否对nrtPS业务的竞争和捎带请求进行授权。按照上述思想，将周期性的、具有恒定速率的UGS业务流、rtPS和nrtPS的轮询流放至实时队列，将nrtPS业务流的带宽请求放至非实时队列，而将没有QoS要求的BE业务流放至BE队列。
流量监控
为了使上游流量适应可用的带宽资源，避免不必要的报文丢弃和拥塞，系统要对分类后的业务流进行流量监控。本模块采用令牌桶算法，策略如下：当报文到来后，只要令牌桶中有令牌，无论数量是否足够，都可以转发报文，同时令牌桶中的令牌量按报文的长度做相应的减少。当令牌数量小于报文长度时，就可以欠债转发，即转发后令牌桶中令牌数目为负，在下次添加令牌的时候，先还清所欠债务，再继续转发报文。这种借贷处理方法在处理突发报文时有优势，能够在限制流量的同时，保证报文发送的连续性，很好地除抖动的影响。系统为实时业务流预留一定的带宽，并优先处理实时业务。非实时业务流和BE业务流的突发性较高，业务量相对繁重，这类业务是流量监控的工作主要对象。
实时调度器
实时调度器负责对带宽和延时要求比较严格的实时业务流，包括UGS业务流、rtPS业务流和nrtPS业务的轮询流。由于业务的实时性，在业务延时后，无法也无需补偿其带宽。也就是说一定要保证实时业务的时延需要，尽量避免某一实时业务长时间等待现象，同时使各业务流的延时在可容忍的门限内。考虑到这些因素，实时调度器中采用不依赖于信道状态的包公平排队CIF-Q(ChannelIndependentFairQueuing)算法。CIF-Q算法的核心是起始时间公平排队(SFQ，Start time Fair Queuing)算法，通过参考无错服务系统，业务流可划分为领先流、落后流和正常流三类。流的落后(领先)度为无错服务和真实服务之差。如果领先流获得了一个调度机会，则以概率α放弃它，被放弃的机会分配给具有最大落后度的落后流。在这种补偿策略下，落后流可以接受额外服务，而同步流不会受到干扰，领先流将会优美地降低它们的服务。概率α的值是由网络状态和实时业务流的QoS参数(授权大小、轮询间隔、最大轮询时延抖动和最小预约速率等)决定的。
下面是对算法模型的伪代码描述，并将在NS2仿真中采用C++实现。
参数初始值：
Vi=max(Vi,min{Vj|j∈A})
lagi=0
参数更新：
Vi+=packetik.length/ratei
lagi±=packetik·length
业务调度：
选择业务流i=min{Vi| iA};若业务流i落后，并可正常发送，则调度业务流i，更新Vi;若业务流i落后，但不可正常发送，则选择业务流j = max{lagk/rk | k∈A ∧packetjk可发送}进行调度，更新Vi、lagi、lagj;若业务流i领先，则以概率1-a正常调度业务流i，更新Vi;概率a放弃调度业务流i，选择业务流j=max{lagk/rk | k∈A ∧packetjk可发送}进行调度，更新Vi、lagi、lagj;
