IEEE80216d上行链路调度服务优化算法

20090375IEEE802.16d上行链路调度服务优化算法施维恭南京邮电大学通信与信息工程学院南京210003摘要调度算法是宽带无线接入系统为分类业务提供QoS保证的重要手段和工具。本文提出一种用于IEEE802.16d宽带无线接入系统TDD模式下的跨层调度服务的改进算法I_DFPQ。仿真结果表明该算法在各个类型业务流的吞吐量、时延、丢包率和公平性方面相比于同类的其他算法具有更优的性能。关键词IEEE802.16d；调度服务；QoS引言随着互联网的不断发展，用户对于宽带网络接入以及宽带多媒体应用的需求与日俱增。在众多“最后一公里”接入技术中，无线宽带接入(BWA,BroadbandWirelessAccess)是近年来无线技术中的研究热点。作为一种城域网无线宽带接入技术，IEEE802.16技术受到通信业界广泛的关注和研究。它是一种适用于2～66GHz频段的空中接口规范，它所提供的无线接入系统覆盖范围可达50KM，每个基站提供的总速率最高可达280Mbps[1]。宽带网络支持多种类型的业务流同时传输，需要对不同类型的业务流提供端到端的服务质量保证(QoS)，满足业务流对宽带、时延抖动、丢包率等方面的要求。在IEEE802.16标准的MAC层协议中，详细规定了业务流的划分以及系统的QoS框架和信令交互机制，但是没有给出具体的实现方案，包括接入控制、流量控制、分组调度算法等。本文分析了IEEE802.16d中MAC层QoS机制，文献[2]所提出的调度算法的基础上，提出了一种新的跨层调度服务体系，研究和分析了其功能和调度策略。1IEEE802.16的MAC层协议IEEE802.16中MAC层协议中定义了一种点到多点的拓扑结构，由一个控制基站BS来连接多个用户站SS，各个SS可以通过BS互相通信并与各种公共网络互连。本文采用协议中TDD双工模式。下行链路时广播信道，BS使用时分复用方式向SS广播消息。而SS则通过时分多址接入，共享上行链路。上行信道被划分为多个的mini-slots，BS为SS分配在每个上行数据帧所占用的时隙，并将结果包含在UL-MAP消息中，通过下行信道广播给SS，SS按照UL-MAP中指定的时隙传输数据。IEEE802.16标准定义了一种面向连接的MAC层协议，为BS和SS之间的各种业务流提供QoS机制，包括连接建立、宽带请求和带宽分配等等。在MAC层中，按照不同业务流对QoS的需求定义了四种类型的业务流：1)主动授权业务(UGS)，用于支持包含了固定长度的、按周期发送的分组包的实时数据流，例如T1/E1，以及没有静默压缩功能的在IP网络上传输语音的技术；2)实时轮询业务(rtPS)，用于支持包含可变长的、按周期发送的分组包的实时数据流，例如移动图片专家组(MEPG)的视频业务；3)非实时轮询业务(nrtPS),用于支持能容忍时延、包含可变大小、满足一个最小速率需要的分组包的数据流，例如FTP业务；4)尽力而为业务(BE)，用于支持无最小业务级别需要的数据流，例如HTTP业务。每类业务流都有相应的一些关键服务参数，如最小保留业务速率(MinimumReservedTrafficRate)，最大可支持的业务速率(MaximumSustainedTrafficBroadAngleforTechnology信息通信技术76Rate)，业务流优先级(TrafficPriority)，最大时延(MaximumLatency)等。所有的这些参数通过动态业务流管理消息来传递。2跨层宽带调度服务体系结构概述IEEE802.16MAC层为每个业务建立一个连接，并建立相应类型的业务流(UGS,rtPS,nrtPS,BE)。BS为每个连接分配一个惟一的连接标识符CID(ConnectionID)用于该连接在上行链路或者下行链路进行数据传输的标识，如图1所示。当一个新的业务流创建或者一个已有的业务流更改参数时，该业务流将发送请求消息给BS。接着由BS上的接入控制模块决定是否批准该请求，如果批准该请求，则由接入控制模块通知调度模块根据请求消息中的参数值来更改当前的调度参数。请求被批准的前提是保证已有的业务服务质量不会降低，同时该新请求所要求的服务质量能够被满足。本文采用一种简单的请求接入控制方法[2]，即通过估算当前系统可用的剩余带宽来判断是否批准请求。具体方法是，当接入控制模块收到DSA,DSC或者DSD请求时，将统计所有已有连接的最小保留业务速率，估计出系统的剩余可用带宽(Ca)。剩余可用带宽的计算公式为其中J是服务类型种类的数量，Ji是第i种服务类型的业务流数量，rmin(i,j)是第i种业务流的第j个连接的最小保留业务速率。如果接入控制模块所收到的DSA或者DSC请求中提出的最小保留业务速率参数值小于Ca，则表明我们所规定的两条接入控制策略都被满足，于是该请求被批准，否则该请求会被拒绝。另外，如果在请求消息中最小保留业务速率参数值为零，则该请求总是被批准，但该连接将被置为最低的优先级，其QoS将不会被保证。这种类型的连接随时都可能被中断，除非其它所有连接的QoS要求都已经被满足。文献[2]提出了一种跨层调度服务结构，对队列之间的数据包和队列之内的数据包采取独立的分层调度算法。在第一层调度时采用DFPQ算法对6个队列进行调度，确定当前被调度的队列。在第二层调度中，采用EDF(EarliestDeadlineFirst)[3]算法来为rtPS队列中的请求进行排队；采用WFQ(WeightedFairQueue)[4]算法来为nrtPS队列中的请求进行排队；采用RR(RoundRobin)[5]算法来为BE队列中的请求进行排队。详细的算法说明和场景举例参照文献[2]。但是在文献[2]中并没有考虑所有四种类型的业务流，缺乏完整性。同时在对时延要求高的rtPS业务流进行调度服务时并没有进行更多的保证，在文献[2]中所举的调度服务中，即使在rtPS队列中仍然存在着即将超时的数据包或者没有剩余的带宽给予这些超时的数据包，调度器将中断服务rtPS业务流，转而开始服务BE业务流，从而导致rtPS中的超时数据包被丢弃，影响了rtPS业务流在吞吐量、丢包率、抖动容限等方面的性能。3I_DFPQ算法(ImprovedDeficitFairPriorityQueue)本文所提到的I_DFPQ算法是对DFPQ算法的一个改进，采用和DFPQ算法中类似的跨层调度服务体系结构(如图2所示)，考虑上行链路中四种类型业务流的调度服务过程，对于第二层中的UGS业务流采用FIFO算法进行调度分配带宽。I_DFPQ算法的流程图如图3所示。在I_DFPQ算法中首先定义以下四种队列：图1BS和SS模块设置(1)技术广角200903771)ActiveList：业务流队列为非空队列且队列的DC[type]＞0；2)BlockedList：业务流队列为非空队列且队列的DC[type]＞0；3)WaitingList：业务流队列空为空队列且队列的DC[type]＞0；4)Non-activeList：业务流队列为空队列且队列的DC[type]＞0。同时在此I_DFPQ算法中规定如下的定义：1)在I_DFPQ算法中的四种服务类型，UGS使用非请求主动授予的带宽，用于支持周期发起固定长度数据包的实时数据流，使用BS给予的固定带宽，是四种类型中优先级最高的，不被任何队列抢占，也不抢占其它三种类型。rtPS使用单播请求，用于支持周期性发起变长数据包的实时数据包，对于时延敏感，故rtPS业务流被设置成具有抢占优先权的队列，在满足某些条件下可以抢占nrtPS和BE业务流，但不可抢占UGS业务流。对于nrtPS和BE业务流能够容忍时延，被设置成可被抢占队列。为保证队列之间被服务的一定量的公平性，这两者之间不相互抢占。2)当rtPS队列中的某些数据包不能及时地被服务而面临超时被丢弃时，我们称这种数据包为CriticalPackets。即当一个数据包满足以下两个条件时，被称为CriticalPackets：其中framen为当前帧号；La为当前帧可用的剩余带宽；sizek为当前数据包k的大小；DC[i]是当前业务流队列i即将被服务的数据包量或者是被具有抢占优先权队列抢占服务的数据包量。3)在每个具有抢占优先权的队列中定义了一个变量Qcrit[i]来使得队列具有更多的机会来服务CriticalPackets，且只能用来服务CriticalPackets。与变量Quantum[i]在每帧的每个调度轮回中都进行更新不同，Qcrit[i]只在每帧开始时更新初始化。下面来举例说明I_DFPQ算法相对于DFPQ算法在某些情况下的优点。假设调度器正在服务可被抢占队列的数据包，一些CriticalPackets来到了具有抢占优先权的WaitingList。如果使用DFPQ算法中的调度服务，则这些CriticalPackets要等到下一帧时间才会被批准发送，这将导致此CriticalPacket超时而被丢弃。接下来我们来看描述I_DFPQ算法来调度这些CriticalPackets来避免它们超时而被丢弃。在图4所示的场景中，假设Ltotal=2500，DC[rtPS]和DC[BE]初始化为：DC[rtPS]=2000，DC[BE]=1000。现在开始从最高优先级的队列开始按照优先级依次访问活动状态列表中的各个队列。在本例中，rtPS中拥有最高优先权。在rtPS队列中的三个数据包被批准服务后，队列变成了WaitingList(队列为空&&DC[rtPS]=500＞0)，而La=1000。接下来，调度器将转移到BE队列进行调度服务。在BE队列中的第一个大小为400bit的数据包被批准服务，第二个大小为300bit数据包F中的前100bit被批准服务后，一个大小为200bit的新rtPS数据包达到了rtPS队列中，此时DC[BE]=500，La=500。由于rtPS队列是WaitingList，应检查一下新到来的rtPS数据包是否为CriticalPacket。假设当前帧为第一帧且帧长为250ms，而此数据包的deadline为450，小于500((1+1)*250=500ms)，而且包的大小为200＞La-DC[Be]=500-500=0。所以满足成为CriticalPackets的两个条件。此时，情况满足算法流程图中图2跨层调度服务体系结构(2)(3)BroadAngleforTechnology信息通信技术78图3I_DFPQ算法流程图“队列可被抢占&&CriticalPackets到达具有抢占优先权的WaitingList”的条件，BE队列中数据包F将被抢占，调度器转而去服务rtPS队列。由于数据包F被抢占，剩余分段F2将等待下一回的调度才有机会被发送。在rtPS队列中的CriticalPackets被调度完后，DC[rtPS]=La=500。由于DC[rtPS]＞0，如果在rtPS队列中仍然存在CriticalPackets，则在调度器返回被抢占队列之前仍然继续服务该具有抢占优先级技术广角20090379的队列。4I_DFPQ算法的仿真结果与分析本文在长庚大学开发的WiMaxversion2.03的Module基础上[6]，使用NS2网络仿真软件来分析I_DFPQ算法的性能，并分析和比较了在相同仿真环境下，I_DFPQ、DFPQ、WRR(WiMaxV2.03版本中Module使用的调度算法)之间的性能差异。仿真参数设置如表1所示。图5～图8分别是UGS、rtPS、nrtPS、BE业务流在I_DFPQ算法下的吞吐量。其中UGS业务流维持恒定的吞吐量。对于rtPS业务流，SS所申请的带宽基本上能够及时得到满足，时延和丢包率性能得到了满足，且吞吐量保持在一个较高的水平线上。对于表1物理层仿真参数设置图5UGS业务流在I_DFPQ算法下的吞吐量图6rtPS业务流在I_DFPQ算法下的吞吐量图7nrtPS业务流在I_DFPQ算法下的吞吐量图4场景说明图BroadAngleforTechnologynrtP