法律状态公告日
法律状态信息
法律状态
2016-10-12
未缴年费专利权终止 IPC(主分类):H04L12/24 授权公告日:20100929 终止日期:20150818 申请日:20060818
专利权的终止
2010-09-29
授权
授权
2008-03-12
实质审查的生效
实质审查的生效
2008-01-23
公开
公开
技术领域
本发明设计一种IEEE 802.16宽带无线接入(BWA)系统中资源调度的方法,属于无线通信技术领域。
背景技术
IEEE 802.16标准是无线城域网的空中接口规范,在未来的宽带无线接入中有着十分重要的意义和广阔的应用前景。802.16标准不但允许非视距连接、支持大容量用户,而且可以提供电信级的QoS保证,全面支持语音、视频、数据等丰富的多媒体业务的应用。
有效的QoS保证体系必须对无线资源进行合理分配,尤其是针对无线通信环境下的复杂环境,无线接入系统的QoS体系面临很多挑战。802.16标准在MAC层实施了一系列的机制。资源调度算法是宽带无线接入系统QoS保证体系中不可缺少的一环。而802.16标准仅仅提出由基站或用户根据各业务的Qos请求和优先级进行资源调度,没有规定具体的资源调度算法。而现有的资源调度算法都没有考虑算法的公平性问题,在高优先级业务负载很重的情况下,容易造成低优先级业务长时间得不到带宽而“饿死”。本算法通过采用一定的平衡机制,在首先保证各业务服务质量的前提下对资源进行合理分配,从而改善算法的公平性。
IEEE 802.16系统有四种不同服务等级的业务,分别是非申请授予业务(unsolicitedgrant service,UGS)、实时轮询业务(real-time polling service,rtPS)、非实时轮询业务(non-real-time polling service,nrtPS)、尽力而为的业务(best effort service,BE)。
现有的资源调度算法是基于严格优先级的调度算法,其具体的实现流程如下:
一级调度算法:在各个不同优先级种类的业务之间,采用SPQ(strict priority queue:严格优先级队列)策略,先满足优先级高的业务的带宽请求,在带宽还有剩余的情况下再依次满足低优先级业务的带宽请求;
二级调度算法:在同一优先级种类的业务之间,根据业务的特点采用不同的带宽分配策略:对于rtPS业务,采用EDF(earliest deadline first)策略;对于nrtPS业务,采用WFQ(weightedfair queue)策略;对于BE业务,采用RR(round robin)策略或均分带宽策略。
由于第一级调度使用SPQ策略,在高优先级业务负载很重的情况下,容易造成高优先级业务过多的占用低优先级业务资源,从而使低优先级业务得不到必要的带宽而出现“饿死”的情况,无法满足低优先级业务的服务质量要求,对低优先级业务来说失去公平性;
资源预留,就是系统在业务接入时预留一部分资源(如带宽、缓冲区或处理器能力等等)来保证业务的Qos需求。基于资源预留的思想,在业务接入时,就为预留它一部分带宽,并对剩余的带宽按一定的算法在各业务之间实施灵活而公平的分配,这样既可以有效的保证业务的Qos需求,又实现了各业务之间带宽分配的公平性。
发明内容:
本发明的目的是提出一种应用在IEEE 802.16宽带无线接入系统中的基于资源预留的公平性资源调度算法,可以在保证各业务服务质量的前提下减少高优先级业务过多占用低优先级业务带宽的情况,改善公平性,获得更好的系统性能。
本发明的特性在于,依次会有以下步骤:
步骤(1),当新业务到来后,该基于IEEE802.16宽带无线接入系统的基站根据不同业务的Qos参数,计算为满足不同的Qos参数所需的带宽,设为rres,其中包括已建立连接预留的带宽和新建立连接所需的预留带宽。若∑rres≤rtotal,则允许接入,否则,拒绝接入,rtotal为系统总带宽;
对于非申请授予业务,rres=rmax,rmax为最大输入数据率,设定值;
对尽力而为的业务,rres=0;
对于实时轮询业务,
其中,rmin为最小输入数据率,设定值;
P0为丢包率门限,设定值;
λ为实施轮询业务的包的到达率,已知值;
为最大时延,TS为一帧的时间,均为设定值;
对于非实时轮询业务,rres=rmin;
步骤(2),基站根据IEEE802.16规定的媒体访问控制层机制,周期性的根据各业务所要求的带宽和系统已有带宽要下达方式对系统带宽进行分配,并把分配结果在下行子帧的媒体访问控制信息UL-MAP中通知各用户站:
第一步:一级调度
先把系统预留带宽满足优先级从高到低的业务的带宽请求,若业务所要求的带宽rres小于预留带宽,则使一级调度的带宽rallo_1=rreq,否则使rallo_1=rres,所述优先级最高的业务是指非申请授予业务,其余依次为实时轮询、非实时轮询以及尽力而为业务;
第二步:二级调度
再把一级调度之后的剩余带宽按加权循环转移法分配给各个业务,各业务的权重因子为:
ki=λigdi;
其中,λi为各业务剩余要求带宽占总剩余要求带宽的比例:即
j=1,2,...,n,为要求分配剩余带宽的业务数,
di为优先级因子,设定值,实时业务的优先级因子应大于非实时业务的优先级因子,对于各非实时业务应设定不同的优先级因子;
二级调度所得到的带宽为:rallo_2=(rtotal-∑rallo_1)·ki/∑ki,
经过两级分配,各业务获得的带宽为rallo=rallo_1+rallo_2。
这种基于资源预留的调度方法有以下优点:
1.Qos保证:接纳控制和一级调度中的分配预留带宽的策略,使业务的Qos参数能得到保证;
2.公平性:二级调度中采用加权循环转移WRR算法,提高了调度的公平性;
3.效率:由于计算rtPS业务的预留带宽rres时,将rtPS业务的时延要求也考虑进去,而不是以最大数据输入率rmax作为判断标准,因此在保证Qos的条件下,减少了带宽的浪费,可以接入更多的业务,从而提高了带宽利用率;
4.简单性:与赤字公平优先级队列DFPQ等算法相比,这种算法更直观,无论理解还是操作都更简单;
5.灵活性:可对不同的业务根据负载等情况设定不同的WRR算法中的优先级因子,这体现了算法的灵活性。
附图说明
图1.IEEE 802.16系统的QoS保证体系;
图2.现有资源调度算法流程图;
图3.本发明提出的资源调度算法流程图;
图4.rtPS业务增长时各业务获得带宽的变化图;
图5.nrtPS业务增长时各业务获得带宽的变化图;
图6.采用本发明前后的公平性指数对比图。
具体实施方式
为实现本发明要解决的技术问题,本发明采用一种引入资源预留思想并与接纳控制算法相结合的资源调度算法,包括如下步骤:
(1)在每个业务申请接入时,用户站SS向基站BS报告业务所要求的Qos参数,BS根据这些参数确定业务所需的预留带宽,若已接入业务的预留带宽总和加上申请接入业务的预留带宽之和小于系统总的带宽,则允许业务接入,否则拒绝接入;
(2)BS在每一帧开始前对系统带宽进行动态分配,分配方法是:
一级调度:先给各个业务分配预留带宽,从而使各业务的服务质量得到保证;
二级调度:对系统剩余带宽按WRR算法在各业务间进行分配,WRR的权重因子由业务所要求带宽以及业务本身的特性决定;
下面对本发明的具体实施方式作进一步的描述。
图3给出了新算法的流程图,具体说明如下:
(1)新业务到来后,首先根据业务的Qos参数,计算业务的预留带宽我们的算法是:当一个业务要求建立连接时,BS根据它的Qos参数,计算为满足这些参数所需的带宽,设为rres,若所有为已建立连接预留的带宽加上新连接所需的预留带宽之和小于总带宽rtotal,即∑rres≤rtotal,则允许接入。rres的计算如下:
1.对于UGS业务,由于所有Qos参数均需满足,因而rres=rmax;
2.对于rtPS业务,rres应为介于rmin和rmax之间的一个值,当BS提供给此业务rres的带宽时,可使此业务的时延和丢包率满足要求;可通过一定的数学方法计算出来,也可跟根据实际系统进行测量;
3.对于nrtPS业务,由于没有时延要求,rres=rmin;
4.对于BE业务,由于没有任何Qos要求,rres=0;
(2)根据IEEE 802.16系统规定的MAC层机制,BS将周期性的根据各业务所要求的带宽和系统已有带宽对系统带宽进行分配,并将分配结果在下行子帧的MAC控制信息UL_MAP中通知各个SS;
带宽分配方法是:
a.一级调度:
先将预留带宽按优先级从高到低的顺序分配给各个业务,但若业务所要求的带宽rreq小于预留带宽rres,则只需要分配预留带宽rres;即若rreq<rres,则一级调度得到的带宽rallo_1=rreq;否则rallo_1=rres;
b.二级调度:
将一级调度之后的剩余带宽按WRR算法分配给各个业务;
各业务的权重因子为:
ki=λigdi;
其中,λi为各业务剩余要求带宽占总剩余要求带宽的比例:即
(若rreq,i<rres,i,令rreq,i-rres,i=0;)
di为优先级因子,具体值可根据系统实际各业务流的业务量多少来决定,同时应满足以下两条原则:
1.实时业务的优先级因子应大于非实时业务的优先级因子,以减少因时延超过Qos要求而丢包的概率;
2.对于非实时业务,也可以对不同业务设定不同的优先级因子,以保证优先级高的业务获得更大的带宽。
二级调度得到的带宽为:rallo_2=(rtotal-∑rallo_1)·ki/∑ki
于是,经过两级分配,各业务获得的带宽为:rallo,i=rallo_1,i+rallo_2,i。
为了对比本发明实施前后的效果,对本发明的算法进行了仿真,仿真参数如下:总带宽B=10Mbps,帧长tf=10ms
图4表示了在rtPS业务量增大的情况下各业务流所得到带宽的情况。在这里,我们把原有算法称为SPQ(严格优先级队列算法),把新算法称为RFPQ(预留式公平优先级队列算法)。由图可知,当总业务量不超过系统总带宽时,两种分配方案所得到的结果一样;当rtPS业务量达到一定程度时,采用现有算法,rtPS业务将挤占BE业务的带宽,造成BE业务线性减少,以致最后达不到Qos要求;而在本发明中,rtPS业务所获得的带宽不再线性增加,其增长趋势变缓;而nrtPS和BE业务的带宽则缓慢减少。与现有算法相比,三种业务的带宽分配趋向均衡,这样即便rtPS业务的流量很重,系统也可以在保证Qos的前提下容纳更多的低优先级业务。
图4表示了在nrtPS业务量增大的情况下各业务流所得到带宽的情况。由图可知,采用现有算法,nrtPS业务的增多不会对rtPS业务造成影响,而会使BE业务大幅下降;采用本算法,nrtPS业务量增大时,rtPS所获得的带宽会有小幅下降,但在可接受的范围之内,不会降低业务的服务质量保证;BE业务的带宽下降趋势相对于现有算法明显减缓,这说明本算法可使低优先级业务得到一定的照顾。
图5表示了在rtPS业务量增大的情况下公平性指标的变化。公平性指标参照文献,定义为各业务带宽满足度的均方差:
其中,S=rallo/rreq,为业务的带宽满足度;
rtPS业务预留带宽计算方法如下:
首先我们建立一个近似的数学模型。从最保守的情况考虑,假定系统每帧分配给某个rtPS业务的带宽均为rres,设数据输入率为rin,rmin≤rin≤rmax,数据输出率为rres,rtPS业务数据包到达是泊松过程,到达率为λ,则在一段时间[t0,t0+t]内到达的字节数为
事实上,我们可以把包的到达、等待与服务过程看成一个批处理系统,包的到达是泊松过程,服务者每隔一帧(TS)处理一次,一次处理一批数据包,处理包的个数设为Y(t),应满足以下关系:
其中,rmax和rmin分别为最大带宽和最小带宽,λ为RtPS业务的包的到达率,P0为丢包率门限,t为最大时延,TS为一帧的时间。RtPS业务的预留带宽就可以由上式根据业务的各个Qos参数计算得到。
机译: 资源调度装置,资源调度系统和资源调度方法
机译: 使用多用户多输入多输出方法的无线电通信系统中的资源调度设备,及其方法,尤其是与在减少系统传输效率的同时进行资源调度的过程中最小化延迟有关的方法
机译: 资源调度信息发送/接收方法以及资源调度方法和装置