—ISN10—00-0054清华大学学报(自然科学版)2008年第48卷第7期
CN11-2223/NJTsinghuaUniv(Sci&Tech),2008,V01.48,No.7
IEEE802.16宽带无线接入网的成比例带宽分配
贺媛,刘佳,曾烈光
(清华大学电子工程系,北京100084)
摘要:为了改进亏空公平优先队列算法,提出一种成比例
带宽分配算法。基站将服务连接的带宽请求按照优先级排
队,根据服务质量参数先分配部分带宽,超出的请求基于子
站总请求带宽的大小成比例分配给服务连接。仿真采用2维
离散时间Markov调制Poisson过程的模型产生实时轮询服
务和非实时轮询服务连接的数据源。与亏空公平优先队列算
法相比,该算法不仅满足各类服务连接的服务质量要求,而
且改善子站总的吞吐量和流量突发增加的问题。该算法还提
高了子站间及不同优先级服务连接间的公平性。
关键词:无线接入网,媒体接入控制,服务质量(QoS),带
宽分配
中图分类号:TN925+.93文献标识码:A
文章编号:1000—0054(2008)07—1131—04
Proportionalbandwidthallocation
forIEEE802.16broadbandwireless
accessnetworks
HEYuan,LIUJia,ZENGLieguang
(DepartmentofElectronicEngineering,TsinghuaUniversity,
Beijing100084,China)
Abstract:Aproportionalbandwidthallocationalgorithmwas
developedtOimprovethedeficitfairpriorityqueue(DFPQ)
algorithm.Thebasestationservicesthebandwidthrequestsofthe
serviceconnectionsinqueueaccordingtOtheprioritiesandgrants
somebandwidthtotheserviceconnectionsbasedonthequality0f
service(QoS)parameters.Theexcessrequestsareproportionally
allocatedrelativetothetotalbandwidthrequestsofthesubscriber
stations.Simulationsuseddataforthereal—timeandnon—real—time
pollingserviceconnectionsgeneratedusingatwo—dimension
discrete—timeMarkov?modulatedPoisson
process
model.The
algorithmnotonlysatisfiestheQoSrequirementsoftheservice
connections。butalsoimprovesthetotalthroughputsOfthe
subscriberstationsandtheproblemscausedbysuddentraffic
increasescomparedwiththeDFPQalgorithm.Furthermore.the
algorithmimprovesthefairnessbetweenthesubscribersandthe
fairnessbetweentheserviceconnectionsfordifferentpriorities.
Keywords:wirelessaccessnetworks-mediumaccesscontroll
qualityofservice(QoS)lbandwidthallocation
17/411131—1134
基于IEEE802.16标准的宽带无线接入
(broadbandwirelessaccess,BWA)技术具有传输
速率高和确保服务质量(qualityofservice,QoS)的
优点,是城域范围内最后1.609km接入的优良选
择[1]。尽管标准定义了媒体接入控制(medium
accesscontrol,MAC)的信令机制,但对于IEEE
802.16系统的服务质量保证起着重要作用的无线
资源管理仍属于开放性的研究问题。由于不同的服
务类型(如固定比特速率,实时,尽力而为)对服务质
量有不同的需求,基站在做好接纳控制的同时,需要
采用合适的带宽分配策略,对每个连接已准备传输
的实际数据的带宽请求进行及时处理。
文[2]提出了亏空公平优先队列(deficitfair
priorityqueue,DFPQ)算法,它以最小保留速率为
门限进行各类服务连接的接纳控制,以最大持续速
率总和的亏空量进行多轮带宽分配。和传统的固定
带宽分配相比,DFPQ算法能动态调配上行和下行
子帧中不均衡的数据流。然而,它仅对单个连接的带
宽请求消息进行先到先服务的处理,没有考虑子站
总的吞吐量和子站间的公平性。当高优先级服务连
接数据增加时,绝对优先级算法会出现严重的带宽
占用的情况。虽然DFPQ算法能够满足低优先级服
务连接的最小保留速率要求,但是高优先级服务连
接占用带宽的情况仍然严重影响了低优先级服务连
接的数据传输。
为了解决以上问题,本文提出一种成比例带宽
分配(proportionalbandwidthallocation,PBA)算
法。在接纳控制阶段,基站对于实时服务连接以最大
持续速率为门限,对于非实时服务连接以最小保留
速率为门限,从而较好地考虑了整个系统长时期的
带宽利用率。在带宽分配阶段,基站将各类服务连接
收稿日期:2007—05—14
作者简介:贺嫒(1981一),女(汉),湖北,博士研究生。
通讯联系人:曾烈光,教授,E—mail:zenglg@mail.tsinghua.edu.cn万方数据
清华大学学报(自然科学版)
的带宽请求按照优先级排队,根据QoS参数先分配部分带宽,超出的请求在可用带宽不够的情况下基于子站总请求带宽的大小成比例分配。
1成比例带宽分配算法
MAC层一般设计为点到多点的拓扑结构,起中心控制作用的基站负责管理其辖区内各个独立的子站。MAC层提供服务质量分级,规定4类服务L4J,主动授权服务(UGS)、实时轮询服务(rtPS)、非实时轮询服务(nrtPS)和尽力而为服务(BE)。各类服务连接的优先级按照从高到低的顺序可排列为:主动授权服务连接、实时轮询服务连接、非实时轮询服务连接、尽力而为服务连接。
1.1接纳控制
假设基站管理Ⅳ个子站,总带宽为B。。叫。对于任意一个子站挖,咒∈N,B7。表示第i个主动授权服务连接的最大所需带宽,B.7。表示第_『个实时轮询服务连接的最大所需带宽(字节数),与最大持续速率相对应,B:“为第是个非实时轮询服务连接的最小所需带宽,与最小保留速率相对应。
当子站有新的服务连接请求加入协商QoS参数时,基站对于实时服务UGS、rtPS连接,以最大所需带宽为基准接入,非实时服务nrtPS连接以最小所需带宽为基准接入,非实时服务BE连接当预留带宽不为零时接入。系统总带宽需要满足以下必要条件:
∑(∑B≯+∑B≯+∑B纠≤B。划,
nEN
iEIn』∈jn^EKn
其中J。、L,。、K。分别是系统中第r1个子站已接纳各类服务连接的总数。接纳控制为各类服务连接预留了带宽,但没有为每一帧实际需要传输的数据分配带宽。
1.2带宽分配
IEEE802.16宽带无线接入网系统中,主动授权服务连接无需任何带宽请求,基站周期的分配固定带宽。实时轮询服务、非实时轮询服务连接使用单播轮询方式周期地发送带宽请求,尽力而为服务连接使用基于竞争的方式请求带宽。在生成每一帧的上行映射之前,基站将各类服务连接的带宽请求按照优先级排队,根据QoS参数和可用带宽的情况作及时处理。系统中各类服务连接的带宽请求是基于连接的,而带宽分配是基于子站的。
对于任意一个子站刀,砚∈N,有:
1)基站分配给第i个主动授权服务连接的带宽G。=B:=B1;
2)如果第-『个实时轮询服务连接的带宽请求R。,≤B.71,那么,基站分配的带宽G。,=R。f;若R。,>B筹1,则G。』一B.71,E。j=R。J—B:≯,其中E唧为超出最大所需带宽的请求;
3)如果第k个非实时轮询服务连接的带宽请求R杜≤B:“,那么,基站分配的带宽G柚一R越;若R曲>B:“,则Gd—B:“,E柚=R柚--B.3“,其中E越为超出最小所需带宽的请求I
4)如果第z个尽力而为服务连接的带宽请求尺“>0,那么,超出的部分E“一R村。
根据以上所述,基站已经分配的总带宽为
G。“=∑∑G耐+∑∑G。,+∑∑G“,
4∈NIiE7:n∈NjJ∈J:nENKkE。K:
其中:ⅣJ、.Ⅳ^ⅣK分别是已分配UGS、rtPS、nrtPS连接带宽的子站数;I:、J:、K:分别是第,1个子站已分配UGS、rtPS、nrtPS连接带宽的连接数。
基站额外需要分配的总带宽
E涮=∑∑E可+∑∑E“+∑∑E“,
n∈—吁,∈J:nE^k‘∈x:n∈Nile《
其中:村、Ⅳ:、Ⅳ:分别是额外需要分配rtPS、nrtPS、BE连接带宽的子站数;∥、K:、z分别是第咒个子站额外需要分配rtPS、nrtPS、BE连接带宽的连接数。
当系统带宽足够时,即E。。试≤B涮一Gt咖l,基站最终分配给第咒个子站的总带宽
q一∑吒+∑G可+∑G柚+
iE7:jeJ'I∈to,
∑‰+∑如+∑如.
J∈J:‘∈K:o∈工:
当带宽不足时,即E。甜>B。砌一G。oIal,基站最终分配给第咒个子站的总带宽
G。一∑G耐+∑G。,+∑G靠+
iE2:J∈o:^∈x:
坠蠹等(∑E。,+∑‰+∑岛).
一”“
.IEo:‘EK:‘∈‘:
2仿真结果
用Matlab仿真工具模拟1个基站管理2个子站的2类服务连接的带宽请求和分配过程,将该算法的性能与亏空公平优先队列算法进行比较。
假设系统总带宽B涮为5Mb/s,每个MAC帧长为10ms,则一帧可以分配的总带宽为50kb。仿真中采用2维离散时间Markov调制Poisson过程
万方数据
贺媛,等:IEEE802.16宽带无线接入网的成比例带宽分配
(dMMPP2)的模型产生实时轮询服务和非实时轮
询服务连接的数据源‘引,系统参数见表1。
表1系统参数
kb
.图1为DFPQ和PBA算法下2个子站总吞吐量的比较。从图中可以看出,DFPQ算法中,子站1的带宽请求获得了全部响应,而子站2的带宽分配远达不到数据变化的要求。这是因为对于rtPS和nrtPS连接子站采用单播轮询的带宽请求方式,基站每帧依次为子站1和子站2提供轮询请求的机会,因而,先轮询到的子站的带宽请求会排在请求消息队列的前端,被基站先分配带宽。虽然请求消息队列是按照服务优先级处理,但是队列中的带宽请求却采用先轮询先分配的方式。由于子站间没有优先级,因而导致了不公平的情况。PBA算法在考虑子站总吞吐量的基础上,公平对待各个子站的带宽请求,即按需分配。
算法的公平性体现在不同实体间的差异是受限的,即控制在一定范围之内,如果差异越小,则公平性越好。假设∑T小∑丁社分别是第,z个子站全
面。压i。
部rtPS、nrtPS连接的总吞吐量,∑5小∑5“分
羁k—EK.
别是第,1个子站全部rtPS、nrtPS连接的总数据源流量,∑丁一f、∑丁小分别是第力’个子站全部J—EJd?I百0
rtPS、nrtPS连接的总吞吐量,∑S由、∑S枷分
J。C。:。:—J—rgk‘E。。。K’n
别是第行7个子站全部rtPS、nrtPS连接的总数据源流量,由于基站管辖的各个子站的性质是相同的哺3,则定义任意2个子站间的公平性
∑丁。』+∑丁社∑丁州+∑丁小
1EJ^^∈KnJ∈jn,kEK∥
∑S。,+∑S“∑S析+∑S小
JC=J。胙K。J∈jn,kEKⅣ
若口越接近于0,则两者间的公平性越好;反之越差。
图2为DFPQ和PBA算法下2个子站公平性的比较。可以看到,PBA算法中,子站公平性控制在0.1以下,和DPFQ算法相比,它既保持了各个子站较高的数据吞吐量,又兼顾了子站间的公平性。
t/帧
(a)子站1的总吞吐量
f/帧
(b)子站2的总吞吐量
图1子站的总吞吐量
图3为rtPS连接流量突然增加时DFPQ和PBA算法下2类服务连接总吞吐量的比较。从表2中可以看到,子站2的rtPS连接建立时的最大、最小所需带宽分别为12kb和8kb,假设50帧后增加到24kb和16kb,那时超出了连接建立时协商的QoS要求。虽然一般情况下,QoS资源分配的目的是用牺牲低优先级nrtPS连接来保证高优先级rtPS连接的QoS,但是图3中反映的rtPS连接超出最大所需带宽的流量突然增加的情况应该采取其他的处理方式。从图中可以看出,DFPQ算法虽然满足了nrtPS连接的最小保留速率要求,但是出现的rtPS连接占用nrtPS连接带宽的情况仍然严重影响了低优先级服务连接的吞吐量。PBA算法在保证各类服务连接QoS参数的前提下,不仅努力维持低优先级nrtPS连接的吞吐量,而且考虑了高优先级rtPS连接超出协商QoS要求的情况,并对超出的带宽请求进行统一的成比例分配。
假设∑∑TⅣ、∑∑T柚分别是所有子站全nEN
JE』^^∈NkEK“
部rtPS、nrtPS连接的总吞吐量,≥:>:5。i、
n‘。E—。N
j‘E‘—J‘n
。
万方数据
清华大学学报(自然科学版)
∑∑s吐分别是所有子站全部rtPS、nrtPS连接的n∈NkEK。
总数据源流量,则定义服务公平性
l∑∑丁。,∑∑丁“l
卢一I!三兰!三!!一!!!!!生J.
I∑∑s可∑∑s杜I
”∈NJ∈J^“∈N^∈K^
若p越接近于0,则两者间的公平性越好;反之
越差。
t/帧
(a)rcPS总吞吐量
f/帧
(b)nnPS总吞吐量
图3rtPS流量增加时服务连接的总吞吐量图4为rtPS连接流量突然增加时DFPQ和PBA算法下2类服务公平性的比较。可以看到,PBA算法中,服务公平性控制在0.1以下,和DFPQ算法相比,它既满足了各类服务连接的带宽需求又明显改善了不同优先级服务连接间的公平性。
0.3
掣O?2
*
盘
淼
丝
4
o.1
050100
t/帧
图4rtPS流量增加时的服务公平性
在运算复杂度方面,DFPQ和PBA算法都先按照服务优先级将服务内部各个连接的带宽请求与亏空量或者QoS参数进行比较,然后DFPQ算法采用多轮分配的方式,而PBA算法则是进行了2次分配。当服务连接的带宽请求数较小时,DFPQ算法只需1轮分配,运算简单。但当带宽请求数较大时,1轮分配变成多轮分配,其运算复杂度与PBA算法相当或更甚。考虑到PBA算法显著提高了子站间及不同优先级服务连接间的公平性,因而可以容忍其增加一定的运算复杂度。
3结论
本文提出一种成比例带宽分配算法,解决亏空公平优先队列算法的问题。仿真结果表明:该算法不仅满足各类服务连接的QoS要求,而且改善子站的总吞吐量和流量突发增加的问题,提高了子站间及不同优先级服务连接间的公平性。该算法也可应用于其他类似具有服务质量分级的宽带无线接入网中。’
参考文献(References)
[1]EklundC,MarksRB,StanwoodKL,eta1.IEEEstandard802.16:Atechnicaloverviewofthe
WirelessMANTMairinterfaceforbroadbandwirelessaccess[J].IEEE
CommunicationsMagazine,2002.40(6):98—107.
[23CHENJianfeng,JIAOWenhua,WANGHongxi.Aservice
flowmanagement
strategy
forIEEE802.16broadbandwirelessaccesssystemsinTDDmodeEC]//International
ConferenceonCommunications2005.Piscataway,NJlIEEE
Press,2005:3422—3426.
[3]WongthavarawatK,GanzA.IEEE802.16basedlastmilebroadbandwirelessmilitarynetworkswithqualityofservice
support[C]//MilitaryCommunicationsConference2003.
Piscataway,NJ:IEEEPress.2003l779—784.
r4]IEEEStd802.16—2004.IEEEstandardforlocalandmetropolitanareanetworkspart16;Airinterfaceforfixedbroadbandwirelessaccesssystems[S].Piscataway,NJ:
IEEE,2004.‘
[5]NiyatoD,HossainE.Queue-awareuplinkbandwidthallocationandratecontrolforpollingserviceinIEEE802.16
broadbandwirelessnetworks[J].IEEETransactionson
Moln'leComputing,2006,5(6):668—679.
[6]WANGHaitang,LIWei,AgrawalDP.DynamicadmissioncontrolandQoSfor802.16
wirelessMAN[c]//WirelessTelecommunicationsSymposium.Piscataway2005,NJ:
IEEEPress。2005:60一66.
万方数据