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

　　摘要： 针对无线信道中与时间和位置相关性错误，本文简要介绍了IEEE 802.16d协议的QoS服务模型，在对WiMax的QoS机制和调度策略进行了深入的研究后，提出了一种新的MAC层分级分组调度架构。以满足不同类型业务的QoS需求，解决了无线信道特殊性带来的调度问题。

　　关键词： 无线城域网规范;服务质量;调度;无线信道

　　引言

　　随着VoIP电话、视频会议和在线视频等多媒体业务迅猛发展，对网络性能提出了与传统的网页浏览、FTP服务、E-mail等业务不同的需求，不同类型的业务具有各自明确的服务质量(QoS，Quality of Service)成为现代通信网络的一大特征。旨在提供传输距离更远、速度更高的无线城域网规范—WiMax标准中，无线信道的位置依赖性、突发和高的信道误码也成为其QoS要面对的首要问题。针对不同的应用需求，802.16d标准中为QoS定义了四种业务类型，明确规范了交互机制，但将调度等内容留待开发者自行解决。

　　文献[2]提出一种新型的CIF-Q调度算法，能够较好地适应无线特性、满足实时要求，但缺乏对多类型业务的区别服务。文献[3]提出的CSDPS算法能够不依赖于信道特性，却无法保证时延限制。将文献[4]提出的分级体系结构应用到WiMax的QoS调度架构中，提出了两层的分组调度算法，针对不同类型业务的QoS需求，在良好适应无线特性的同时，实现对不同业务应用的支持。

　　IEEE 802.16d的服务类型

　　主动授予服务(UGS，Unsolicited Grant Service)

　　UGS业务用于传输周期性的、包大小固定的实时数据业务，其典型业务是VoIP电话。UGS业务一旦申请成功，在传输过程中就不需要再去申请。BS周期性地强制调度，不接收来自SS的竞争请求机会，同时禁止使用捎带请求，这样避免了带宽请求引入的开销和时延。

　　实时轮询服务(rtPS，Real-time Polling Service)

　　rtPS主要用于支持周期性的、包大小可变的实时业务，如MPEG视频业务。rtPS提供周期性的单播轮询带宽请求机会，从而使得该连接能够周期地改变带宽请求。BS也不接收来自SS的其他竞争请求机会和捎带请求。这种服务比UGS的请求开销大，但能按需动态分配带宽。

　　非实时轮询服务(nrtPS，Non-Real-time Polling Service)

　　nrtPS主要用于支持非周期、变长分组的非实时VBR服务流，如高带宽的FTP业务流，它有最小速率要求。BS提供比rtPS轮询间隔更长的周期或不定期的单播请求机会，SS也可以使用竞争和捎带请求的方式来请求带宽。

　　尽力而为服务(BE，Best Effort Service)

　　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(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业务的需求;③系统整体具有较高吞吐量、公平性和较小时延。但在无线功耗、分布式无线网络的位置相邻等问题，还需要进一步探讨。

　　参考文献：

　　1. IEEE 802.16-2004. Part 16: Air Interface for Fixed Broadband Wireless Access Systems[S]. Apr, 2004. http://www.ieee802.org/16/tg1/docs/802161-99_00.pdf.

　　2. T.S.Eugene Ng, Ion Stoica, Hui Zhang，. Packet Fair Queueing Algorithms for Wireless Networks with Location-Dependent Errors[C]. Proc Of IEEE INFOCOM'98. 1998,3(3):103-1 111.

　　3. Bhagwat P, Bhattacharya P, Krishna A, et， Enhancing Throughput over Wireless LANs Using Channel State Dependent Packet Scheduling[J]. INFOCOM'96, San Francisco, California. 1996:1133-1140.

　　4. Bennett JCR, Zhang Hui， Hierarchical Packet Fair Queuing Algorithms [EB/OL]. 1997.

　　5. 宣孝英，石冰心，邹玲，无线网络包调度算法综述[J].计算机工程与应用，2003，39(17):20-21.

　　6. Lyu-han Chen，Credit-based Low Latency Packet Scheduling Algorithm for Real-time Applications[D]. Master. Computer Science and Information Engineering. 2007,6.

　　7. M. Hawa ，D.W. Petr.，Quality of service scheduling in cable and broadband wireless access systems[C]. In IEEE International Workshop on Quality of Service. 2002,5:247-255.

　　8. S Walsh, E Garcia-Palacios, S Sezer， Delay-bound Preservation through Packet Scheduling at Wireless Access Point Nodes, EE Mobility Conference, Bangkok, Oct 2006.

　　9. 崔维嘉，刘勤让，一种基于业务分类的大规模用户高速流量监控策略[J]，电信科学,2006,22(10):51-54.

　　10. 彭木根，李茗，王文博，WiMax系统中QoS机制研究[J]，中兴通讯技术，2005,11(2):25-30.

　　11. NS-2 simulator. http://www.isi.edu/nsnam/ns.