一种面向WiMAX的呼叫接纳控制算法*

张青波 ， 何加铭

(1.浙江工商职业技术学院，浙江 宁波 315012；2.宁波大学，浙江 宁波 315211)

WiMAX无线网络中，呼叫接纳控制机制是保证服务质量QoS(Quality of Service)的关键。目前已有大量的呼叫接纳控制算法被提出，典型的有：利用资源预留机制切换连接请求的截止优先权方式[1]、新连接按概率接纳的分段预留信道方式[2]。资源预留机制以提高低优先级业务拒绝率和降低系统资源利用率为代价，降低高优先级的拒绝率，但设定的预留资源不能很好地适应业务量的实时变化。KIM S等[3]提出的基于本地业务量的预测估计自适应接纳控制算法，不仅复杂度和代价较高，同时依赖于一定的流量模型,具体实施有一定的困难。Fmanuele[4]、Jiongkuan Hou[5]等分别把价格机制引入到呼叫接纳控制机制算法中，有一定的借鉴意义。本文利用经济学概念，提出了一种基于基尼系数作为判决准则的呼叫接纳控制机制，使系统在繁忙时获得最大效率。

1 Wimax业务QoS说明

WiMAX系统有详尽的QoS参数设定，但其接纳控制等策略则交由设备提供商自行决定。协议规定了4种业务流 QoS类型：UGS、rtPS、nrtPS、BE,其类型特征如表1所示。发起端在业务流建立时确定流传输的最小忍受带宽bmin和最大满意带宽bmax，业务流被接纳后实际获得的带宽介于bmin和bmax之间，并且可由系统的带宽分配策略来调整所获得带宽的大小。

不同业务类型、不同传输速率，以及切换连接与新连接的区别，使同一个系统内的服务类型繁多。接纳控制算法要能够对繁多的业务类型进行统一的判决和管理，以参数区分业务类型。在优先考虑高优先级业务的同时又要兼顾所承载业务的多样化，保证各业务之间接纳的公平性。

表1 QoS业务类型特征

2 基于基尼系数的呼叫接纳控制机制

2.1 呼叫接纳模型的建立

基尼系数（Gini Coefficient）是意大利经济学家基尼于1912年提出的[6]，用以定量测定收入分配差异程度的分析指标。本文从WiMAX系统业务角度出发，引入基尼系数作为呼叫接纳控制的判决依据，保证各业务之间接纳的公平性,由于WiMAX系统呼叫接纳控制机制的目标是在提高接纳率的同时，有效利用系统资源，因此利用基尼系数作为判决依据是合理的。设业务的带宽范围为[bi,min,bi,max]，业务的优先级为 pi，其中 i为业务流 QoS类型，各业务流所获得的带宽由系统带宽分配策略决定。设系统总带宽为btotal,第i类业务的第j个业务流分配带宽为bi,j,因BE业务所需带宽极小,所以这里不考虑BE业务,只考虑 UGS、rtPS、nrtPS业务。定义第 i类业务的第j个业务流权重wi,j=epi,则其呼叫接纳时所需带宽Ai,j=wi,jbi,j=epibi,j，若系统已接纳业务流个数为 N，将所有业务流的带宽分配以升序排列得到序列x1,x2,…，xN，其平均带宽分配为，则基于基尼系数的呼叫接纳模型为：

式(1)模型表示呼叫接纳时系统带宽分配的公平程度。因业务流的权重随优先级的增大呈指数增长，而高优先级业务与低优先级业务的带宽要求差距小于其权重之间的差距，模型将在优先接纳高优先级业务的同时提高低优先级业务的接纳率,保证各业务之间接纳的公平性，同时提高系统带宽利用率。

2.2 接纳控制算法实现

假设网络中基站BS(Base Station)已接纳的业务流数量为N，它为各业务流均预留其最大带宽，最大带宽总和为∑bi,max。设定带宽门限bth和公平门限 Gth时，Gth的设定需根据对各时期的基尼系数进行大量统计，选取合适的基尼系数作为公平门限。若公平门限设置过大，则公平门限不起作用，各业务的接纳率过高，将超过BS所能容纳的最大业务数，使得BS在下行链路处理业务流的时间增加，各业务流延时剧增；若公平门限设定过小，则BS将对各业务流的接纳进行严格的限制,导致各类业务的接纳率和带宽利用率大大降低。对于新到达业务流fN+1，设其申请带宽为[bN+1,min,bN+1,max],在总最大带宽Σbi,max+bN+1,max≥bth时，采用基于基尼系数的接纳控制。接纳控制算法流程如图1所示。

图1 接纳控制算法实现流程

接纳控制算法启动后按以下流程进行：

(1)首先求出当前未接纳新业务流时系统的基尼系数Gongoing和预接纳新业务流后系统的基尼系数Gnew,其中业务流实际获得的带宽由系统的带宽分配策略决定，这里假设采用均匀分配策略。

(2)当Gongoing＞Gth时，系统应接纳能降低系统带宽分配不公平性的业务流，且根据对不公平性的降低幅度来决定接纳概率,选择经过修正的Sigmoid函数作为接纳概率函数：

当Gonging≤Gth时,系统应接纳使系统收入分配公平值不超过公平阈值的业务流，且根据此时的公平值与公平阈值的接近程度来决定接纳概率，选择经过修正的Sigmoid函数作为接纳概率函数：

系数 a1,b1,c1和 a2,b2,c2满足式(2)当 Gth≤Gnew≤Gongoing时概率 P1∈(0,1)且在 x1∈(0,1)内单调增，满足式(3)当Gonging≤Gnew≤Gth时 概 率 P2∈(0,1)且 在 x2∈(0,1)且 在 内 单调减。

(3)最后根据接纳概率P来决定是否接纳新到业务，用服从均匀分布的随机数产生器产生0～1之间的随机数α，取接纳概率P和拒绝概率1-P两者的最大值，并与概率0和1组合成累积概率区间 [0,max(P,1-P)]和(max(P,1-P),1]，当 α∈[0,max(P,1-P)]时，若 max(P,1-P)=P，则接纳该业务，反之则拒绝该业务；当 α∈(max(P,1-P),1)]时，若 max(P,1-P)=P，则拒绝该业务，反之则接纳该业务。

3 仿真及性能分析

选用Matlab作为仿真工具，按照WiMAX的QoS设定，模拟1个SS连接到1个BS，SS产生 UGS、rtPS、nrtPS业务，其优先级 p={5,4,3}，以均值 λ={2,2,4}个/s的泊松分布产生。各业务的服务时间服从均值为1/μ=5 s的指数分布，最大带宽bmax={0.2,0.3,0.6}Mbit/s，最小带宽 bmin=δbmax，其中 δ={1,0.8,0.5}。系统总带宽btotal为75 Mb/s，带宽门限bth=0.8btotal，基尼门限 Gth=0.4，仿真时间为 50 s，接纳概率公式中，取a1=a2=6，b1=b2=2，c1=-1，c2=0。系统对已接纳的业务采取均匀带宽分配策略，当出现带宽降级时，采取降低已接纳业务流的最大带宽的方法。

仿真通过调节负载比例系数α改变业务的到达率λ，以此表征系统资源紧张程度。仿真时将典型的截止优先算法(以下简称CP算法)与本文提出的带宽分配公平算法(以下简称 EDI算法)做比较。

如图2所示，EDI算法的平均带宽利用率从负载比例系数为4处开始大于截止优先算法的带宽利用率，且随着负载的增大，CP算法的带宽利用率增长缓慢，而EDI算法的带宽利用率将趋近于100%。这是因为CP算法始终按照最大带宽要求进行接纳控制并预留带宽，且不存在带宽降级的情况，因此带宽浪费严重，而EDI算法根据当前资源状况，一开始为各业务预留带宽很大，之后逐渐减小以接纳更多的业务，最终每个业务的带宽接近最小带宽要求，因而随着负载的增大其带宽利用率比CP算法要高很多。

从图3和图4来看，CP算法的 UGS、rtPS、nrtPS业务在大负载下，其接纳率均远远小于EDI算法的各业务的接纳率，这是因为CP算法在整个接纳过程中始终为新到业务按照其最大带宽要求预留带宽，并且在已接纳业务的总带宽超过门限时，只接纳高优先级业务而拒绝低优先级业务，大大降低了低优先级业务的接纳率。而EDI算法从每个业务的收入出发，在保证系统带宽分配公平化的原则下，相对CP算法大大提高了低优先级业务的接纳率。在系统资源紧张的时候，又能通过带宽降级，以接纳更多业务，这就使得各类业务的接纳率都能有明显的提升。从图5和图6又可看出，高优先级业务和低优先级业务的接纳率的差距大大缩小了，这是因为EDI算法为了保证接纳的公平性，对能缩小收入差距的业务以较高概率接纳，EDI模型中低优先级业务的带宽是最低的，为了避免带宽分配差距的拉开，EDI算法将限制高优先级业务的接纳率，提高低优先级业务的接纳率，又因为低优先级业务的带宽可调范围大，接纳后可动态压缩其带宽为其他业务服务，可见接纳更多的低优先级业务从带宽分配公平的角度和带宽利用率的角度来看都是有意义的。

本文提出的算法可以根据系统负载的变化和当前的带宽资源状况自适应地改变接纳策略。相比典型的截止优先算法，新算法在提高系统平均带宽利用率的同时，大大提高了低优先级业务的接纳率，保障系统所接纳业务之间带宽分配的公平性，使得系统承载业务多样化。

[1]LIN Y B,MOHAN S,NOERPEL A.Queueing prioritychannel assignment strategies for handoff and initial accessfor a PCS network[J].IEEE Truns.on Veh.Technol.,1994,43(3):704-712.

[2]RAMJEE R,TOWSLEY D,NAGARAJAN R.On optimal call admission control in cellular networks[J].Wireless Networks,1997,3(1):29-41.

[3]LI Bo,LI Yin,WANG K Y.An efficient and adaptive bandwidth allocation scheme for mobile wireless networks using a non-line local estimation technique[J].Wireless Networks,2001,7(1):107-116.

[4]VITERBO F,CHIASSERINI C F.Dynamic pricing for connection-oriented service in wireless networks[A].Indoor and Mobile Radio Communications[C].USA,2001:A68-A72.

[5]HOU Jiong Kuan,YANG Jie,PAPAVASSILIOU S.Papavassiliou.Integration of Pricing with Call Admission Control to Meet QoS Requirements in Cellular Networks[J].IEEE Transactions on Parallel and Distributed Systems,2007,13(9):898-910.

[6]VASA R,LUMPE M,BRANCH P,et al.Comparative analysis of evolving software systems using the Gini coefficient[C].IEEE International Conference on Software Maintenance,Canada,2009:179-188.