一种适应信道的WiMax分级调度架构

流量监控

为了使上游流量适应可用的带宽资源，避免不必要的报文丢弃和拥塞，系统要对分类后的业务流进行流量监控。本模块采用令牌桶算法，策略如下：当报文到来后，只要令牌桶中有令牌，无论数量是否足够，都可以转发报文，同时令牌桶中的令牌量按报文的长度做相应的减少。当令牌数量小于报文长度时，就可以欠债转发，即转发后令牌桶中令牌数目为负，在下次添加令牌的时候，先还清所欠债务，再继续转发报文。这种借贷处理方法在处理突发报文时有优势，能够在限制流量的同时，保证报文发送的连续性，很好地除抖动的影响。系统为实时业务流预留一定的带宽，并优先处理实时业务。非实时业务流和BE业务流的突发性较高，业务量相对繁重，这类业务是流量监控的工作主要对象。

实时调度器

实时调度器负责对带宽和延时要求比较严格的实时业务流，包括UGS业务流、rtPS业务流和nrtPS业务的轮询流。由于业务的实时性，在业务延时后，无法也无需补偿其带宽。也就是说一定要保证实时业务的时延需要，尽量避免某一实时业务长时间等待现象，同时使各业务流的延时在可容忍的门限内。考虑到这些因素，实时调度器中采用不依赖于信道状态的包公平排队CIF-Q(Channel Independent Fair Queuing)算法。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;

其中：Vi：业务流i的虚拟时间

lagi：业务流i的落后/领先度

packetik：业务流i的第k个包

ratei：业务流i的速率

非实时调度器

非实时调度器主要负责实时性较弱的nrtPS业务流。非实时业务对延时的要求不高，更加关注的是在适应无线链路特性的同时，如何应对繁重的业务流、保证吞吐量。基于这些理由，非实时调度器采用基于业务类型排队(CBQ，Class-Based Queuing)的适应无线信道状态调度算法CSDPS(Channel State Dependent Packet Scheduling)。CSDPS部分用于处理无线链路的变化，它将每一个SS的分组数据信息都保存在一个独立的队列中，并按照先入先出(FIFO)顺序处理每个队列中的分组数据。设置一个链路状态监视器，用来监视所有SS的链路状态信息，当某无线链路处于异常状态时，则标记该队列，使之暂停服务。一段时间后取消对它的标记，该队列可以重新进行资源调度。CBQ跟踪每个SS队列在确定时间间隔内收到的业务数量，并且限制超过应分配共享带宽的SS在未来分配资源的大小，提供整个无线信道共享的公平性机制。

参数初始化：

blocktimei=0

consumei=0

参数更新：

blocktimei+=d

consumei+= packetik·length

业务调度：

每间隔d时间重新初始化consumei;更新blocktimei;blocktimei >a，取消对队列SSi的标注;选择未被标注且consumei未超标的队列SSi;若队列SSi的数据流可正常发送，则调度packetik，并更新consumei;若队列SSi的数据流不可正常发送，则标注SSi，并初始化blocktimei;

其中：blocktimei：队列SSi的暂停时间

consumei：队列SSi已消耗的数据量

packetik：队列SSi的第k个数据包

a：当队列被标注后，恢复正常所需时间

d：时间间隔量

BE调度器

BE调度器主要负责对服务质量不作要求的BE业务流，不须为其提供完备的QoS保证。考虑到BE业务流的典型业务是Internet网络浏览等，实时性要求较低，无须考虑服务中断的应对，采用简单的先入先出(FIFO，First In First Out)算法即可满足其需求。

总调度器

总调度器负责对不同类型的业务进行调度，在体现各种业务享有不同级别服务质量的同时，还要在三种子调度之间找到一个平衡点，达到相对公平的目的，防止诸如实时业务垄断带宽或实时业务被阻塞等现象的发生。这包含两个方面的内容：一、稳定三类业务间的结构;二、适应业务流变化。为此，总调度器采取如下策略和措施：为实时业务预留一部分带宽BUGS，为突发流预留一部分带宽Bburst，其余的带宽按一定比例分配给三类业务流。当请求比例外带宽时，优先授权予实时业务，非实时业务次之，BE业务最低优先级。当三类业务流间的带宽需求结构发生变化时，要适当调整带宽的分配比例。考虑到对带宽的充分利用，当由于无线信道误码或其他原因造成某一正在传递数据的连接暂时中断，系统会将连接所占带宽临时分配给别的连接，为了实现公平性，在暂时中断服务的连接恢复正常后，系统应对中断连接作出带宽补偿。UGS等业务流实时性很强，若连接恢复后再对连接作出带宽补偿没有多大意义。对于BE业务，调度不保证其服务质量，因此BE业务也无补偿。而nrtPS流业务量繁重，一旦中断连接必然导致大量数据滞留，必须考虑连接恢复后的带宽补偿问题。

总调度器算法模型伪代码描述如下：

检查进入调度的数据流的类型，确定此类型的比例带宽(Brt或Bnrt或BBE)是否有剩余：若有，则进入相应的子调度器，并更新剩余的比例带宽;若无，则进入brust业务处理方法。

brust业务：若Bbrust+Bremain>0，则按照rtPS>nrtPS >BE的优先顺序处理数据流，并更新Bbrust、Bremain。对未取得Bbrust的业务标识为NeedCompensate。

业务补偿：若Bremain>0，则对标识为NeedCompensate的业务分配Bremain的带宽，进入相应子调度，并更新Bremain。

BUGS：UGS业务保留带宽

Brt、Bnrt、BBE：实时业务、非实时业务和BE业务的比例带宽

Bremain：剩余带宽

仿真结果

由UC Berkeley开发的免费、开源的多协议网络仿真软件NS-2是一个事件驱动的模拟器，它可以屏蔽对操作系统的实际访问，近乎真实地模拟网络环境。由于NS-2本身中不包含WiMax模块，这里采用对QoS支持较为完善的长庚大学开发的WiMax 2.03模块。本文对调度架构中所涉及的调度算法用C++进行描述，然后采用Otcl脚本语言建立WiMax模拟场景，并获取的仿真数据结果。针对无线信道特性导致的高误码率，本文模拟1个BS(Base Station)和4个SS(subscriber station)组成的WiMax网络，仿真场景如图 2所示。误码率设为1%，最大误码时长16个时间间隔。通过对仿真数据的分析和对比，可以得到算法的吞吐量、延时和速率等性能参数。本架构算法与通常调度算法的对比见图 3、图 4(取样时间为0.1秒)。

图 2 仿真场景图

图 3是UGS、rtPS等实时业务在采用CIFQ算法和FIFO算法时的延时对比。可以看出，在业务拥挤，出现信道错误时，FIFO算法会产生峰值毛刺，出现长延时现象。相比之下，虽然CIFQ算法的总延时增加2%，但延时波动较为平稳，且无长延时现象，这证明CIF-Q算法能够在有效应对信道错误的同时，满足了实时业务的延时和抖动需求。

图3 实时业务延时对比图

表1 主要性能参数对比表

　　图4是非实时业务在采用CBQ-CSDPS算法和FIFO算法时的吞吐量对比。明显可以看出，在信道现在错误时，FIFO算法会导致吞吐量急剧下降。而CBQ-CSDPS算法能够很好应对信道错误，持续高吞吐量作业，总的吞吐量比FIFO算法多出近15%。这证明CBQ-CSDPS算法更有利于非实时业务高效率地使用带宽。

图4 非实时业务吞吐量对比图

在仿真无线特性的高误码的场景下，本架构的延时、吞吐量和丢包等方面的表现见表 1。采用本架构后，实时业务的延时/抖动有明显改善的同时，吞吐量有了一定的提升，丢包率减少了约30%;对于非实时业务在采用本架构后吞吐量提升十分显著，丢包率也减少了约30%，但代价是延时增加了近15%。表面上看，本架构似乎有得有失，但内在却有了质的变化：本架构以总延时的少量增加换得对延时抖动的限制、丢包率和吞吐量的提升，从而满足实时业务的延时和抖动需求;非实时业务以其非注重的总延时兑得吞吐量的极大提升，满足了非实时业务的高速率畅行。这说明本调度架构的算法在高误码率的状况下，能够较好地满足各类型业务需求。

结语

本文结合CIF-Q和CBQ-CSDPS等调度算法，提出一种适合于WiMax的MAC层QoS调度架构。该架构结合分级分组调度算法，充分利用带宽控制、资源预留和流量监控等策略和机制。通过NS仿真对算法进行仿真，得出如下结论：①能够适应时间、位置相关的等无线信道特性的高误码率;②为不同类型业务采用相应算法，满足UGS和rtPS业务的实时性，保证了nrtPS业务的最小速率，兼顾了BE业务的需求;③系统整体具有较高吞吐量、公平性和较小时延。但在无线功耗、分布式无线网络的位置相邻等问题，还需要进一步探讨。