一种针对用户数量变化而改进的比例公平算法

张 祎，梁进波，王荆宁

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

一种针对用户数量变化而改进的比例公平算法

张 祎，梁进波，王荆宁

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

针对复杂环境下用户数量改变的情况，对用户数量和不同资源分配算法吞吐量之间的关系进行了分析，找出其变化趋势，在现有比例公平算法的基础上，提出了一种调节因子，在公平性指标可以接受的范围内，使得改进后的比例公平算法可以良好适应100以内的用户数量变化，避免过于逼近吞吐量的理论下限值，在吞吐量较低时最高可以获得接近9%的性能提升。提出的算法将能够更好地适应时变环境，有效改善用户数激增带来的系统性能下降问题。

资源调度；比例公平算法；吞吐量；调节因子

0 引言

在无线通信中，频带资源和功率资源是有限的[1]，要想在保证各个用户之间公平性的同时努力使系统内总吞吐量最大化是我们需要解决的重要问题[2]。最大载干比(MAX C/I)算法保证好的信道上的用户可以获得资源，其吞吐量是理论上的上限；轮询(Round Robin,RR)算法则保证每个用户都有相同的几率被调度，所以其吞吐量在理论上是下限[3]。在这2种算法的基础上，比例公平(Proportional Fair,PF)算法是目前被普遍应用的一种调度算法，同时兼顾了吞吐量和公平性[4]，但是在用户数量增加时，其吞吐量也不断下降直至逼近轮询算法，所以在复杂环境发生变化时的应用受到一定的限制，使得系统性能有所下降[5]。

在现有PF算法的理论基础上，提出了一种具体可行的改进方案，通过设置合理的调节因子[6]，改变用户速率分布，可以在用户数量增加时，防止PF算法的平均吞吐量过快下降逼近理论下限值，从而更有效地利用有限的资源，提高系统的整体性能。

1 现有算法

1.1 Max C/I算法

Max C/I算法的主要目标是提高整个系统的吞吐量，其调度原则是[7]：在每一时刻调度都会选择C/I值大的用户，这样可以保证信道质量最好的用户能够分得最多的资源[8]。假设有N个用户申请调度[9]，在t时刻，用户i的载干比为γi(t)，那么符合最大载干比算法的用户为：

(1)

MAX C/I调度算法能够获得比其他算法更高的吞吐量，达到理论上的极限值，但是该算法系统吞吐量的最大化是以牺牲用户间的公平性为代价的[10]。

1.2 RR算法

RR算法的主要目标是保证系统中所有用户具有相同的机会来获得系统资源，是公平性的极限。在进行调度时，所有用户会按照某个特定的顺序循环占用系统的无线资源，并且占用资源的时间长度相等[11]，N个用户被调度的概率相同，都是1/N。所以该算法具有很高的公平性，可以保证用户同时具有长期公平性和短期公平性，但是该算法是在牺牲系统吞吐量的基础上保证各个用户之间的公平性，故而RR算法具有最低的吞吐量[12]。

1.3 PF算法

MAX C/I算法和RR算法都是在牺牲系统吞吐量或用户公平性中的某个指标来保证另一个指标，为了取得二者的折中平衡，提出了PF算法。不同于MAX C/I算法或者RR算法只考虑调度用户的信道状况或者用户间的公平性，PF算法充分利用信道的时频特性尽可能调度信道状况较好的用户，同时尽可能调度到每一个用户，兼顾吞吐量和公平性两方面的要求[13]。

(2)

但是PF算法同样存在一些问题，在用户数量较少时，其吞吐量接近MAX C/I调度算法，可以保证系统性能，但是当用户数增加时，其吞吐量快速下降直至逼近RR算法，这时的用户平均吞吐量已经不能用于正常通信[15]。

2 改进算法

2.1 改进公式

在整个系统中，用户数量的不确定性很强，数值通常会在0～100之间浮动，为了保证在各种数量的情况下都能使系统正常运转，需要设置一个动态参数，可以随着用户数量的变化而滑动，动态调节PF算法的偏向[16-17]，在用户数量增加时大幅提高吞吐量，使其在整个范围区间内达到很好的效果，避免过于接近RR算法的吞吐量下限值。

对优先级公式的改进：

(3)

已知公式中当α=1,β=0时，为MAX C/I算法；

α=0,β=1时，为RR算法；

α=β=1时，为PF算法。

现在为了方便计算，令α+β=1，则：

α=1,β=0时，为MAX C/I算法；

α=0,β=1时，为RR算法；

α=β=0.5时，为PF算法。

此时β=1-α。

根据实际应用和初步计算，本文设定α的取值区间为0.2～0.8，当用户数量等于40时，α=0.5；当用户数量大于等于100时，α=0.8；当用户数量小于等于10时，α=0.2，即:

(4)

式中，N代表用户数量。

为了提高吞吐率，对优先级公式进行如下改进：

(5)

用来改变用户速率分布，比平均请求传输速率高的用户优先级相对更高，这样就能够使处于较好的信道状况的用户被调度的机会提高，与此同时降低处于较差信道状况用户被调度的机会。

综合上述分析，为了达到在用户数量变化的情况下提高系统吞吐量的目的，最终采用的优先级公式为：

(6)

本文将其命名为改进型轮询(Proportional Fair-Advanced，PFa)算法。

PFa算法的流程图如图1所示。

图1 PFa算法流程图

2.2 吞吐量仿真及分析

本文分别在用户数量为10、40、100时进行Matlab仿真，将PFa算法与经典算法进这行吞吐量比较，仿真参数设置如表1所示。

表1 仿真参数设置

本文分别在用户数量为10、40、100时进行Matlab仿真，将PFa算法与经典算法进行吞吐量比较，仿真结果如图2、图3和图4所示。

图2 10个用户

图3 40个用户

图4 100个用户

Matlab仿真吞吐量统计如表2所示。

表2 Matlab仿真吞吐量统计表(30 dB)

由表2可以看出：

① 随着用户数量的增加，3种算法的吞吐量都在下降；② 在用户数量从10增加到40时，吞吐量下降了大约73%，较为显著，而用户数从40提高到100时下降约60%；③ PF算法在用户数量不断增加的同时在向RR算法逼近，当数量足够大时最终会与RR算法重合。

既PF算法的公平性在不断提高，但是牺牲了整体的吞吐量。

而在Mtlab仿真中可以看出，PFa算法使得用户的吞吐量得到提高，而且在用户数量增大时效果尤为明显，在10名用户时性能大约提升3.8%，而在100名用户时吞吐量性能提升了约8.7%。说明PFa算法在用户数量增加时改善效果更为显著，可以有效根据用户数量做出调整，使系统的性能得到提升。

2.3 公平性仿真及分析

以公平性的角度来看，本文以最小最大公平性准则(Min-max Fairness)作为参考指标。Min-max公平性准则描述为：当一种有效地资源分配方案[R1,R2,...,RN]符合该准则时，对于任意一个用户i，其所分配的资源Ri都不可能再变大，除非使得Rj

Min-max准则公式:

(7)

即分配资源数最小与最大值的比值。

图5、图6和图7为Min-max准则的仿真结果。从图表中可以看出，以Min-max准则为标准，PFa算法会小幅度降低用户间的公平性，但是基本还与PF算法相当，在可以接受的范围之内，而在与MAX C/I算法比较时明显可以看出PFa算法远高于理论下限值。

图5 10个用户

图6 40个用户

图7 100个用户

因此，本文提出的PF改进算法是合理的，能够缓解用户增加所带来的吞吐量减少问题，与此同时又能适当兼顾公平性准则，避免极端分配所导致的“饿死”现象发生。

3 结束语

本文在现有PF算法的基础上，根据用户数量与吞吐量的关系变化趋势，提出了一种PFa算法，在Matlab仿真中可以看出，由于有滑动系数的存在，可以保证用户数量在100以内变化时获得可观的吞吐量增益，避免过于逼近吞吐量的理论下限值。以Min-max准则衡量，PFa算法的公平性在可以通信的范围内，故可行性没有问题。当用户数量增加到100时可以获得接近9%的性能提升，所以PFa算法是提高通信质量的一种有效方式。

[1] 章 欢.LTE系统资源调度算法的研究[D].哈尔滨：哈尔滨工程大学，2012.

[2] Hui J Y. Resource Allocation for Broadband Networks[J].IEEE Journal on Selected Areas in Communications,1988,6(9):1598-1608.

[3]OdhahNA，DessoukyMI,AI-HanafyWE,etal.C32.GreedyPowerAllocationAlgorithmforProportionalresourceAllocationinMulti-userOFDMSystems[C]∥RadioScienceConference(NRSC),29thNational，2012:421-428.

[4]IanCW,ZuK,BrianL,etal.ALowComplexityAlgorithmforProportionalResourceAllocationinOFDMASystems[C]∥IEEEXploreConference:SignalProcessingSystems,2004:1-6.

[5] 杨 骅,刘劲松.TD-LTE宽带数字集群通信发展分析及建议[J].移动通信,2014,38(1):48-53.

[6]AkramB,RamyH.Gohary,etal.OptimalTradeoffBetweenSum-RateEfficiencyandJain’sFairnessIndexinResourceAllocation[J].IEEETransactionsonWirelessCommunications，2013,12(7):3496-3509.

[7] 孔庆亮.LTE/LTE-A下行资源调度算法研究[D].西安：西安电子科技大学，2013.

[8] 李 俏.LTE无线通信系统中的无线资源调度技术研究[D].南京：南京邮电大学，2010.

[9] 任 敏.LTE-A中的小区选择和用户调度算法研究[D].西安：西安电子科技大学，2010.

[10] 黄明娟.单用户OFDM系统中动态资源分配算法的研究[D].济南：山东大学，2011.

[11] 赵希鹏，张 欣，杨大成，等.基于QoE的无线网络资源调度优化研究[J].移动通信，2014,38(22):8-13.

[12] 何 怡.一种多用户OFDM系统的资源调度算法[J].北京：计算机仿真,2008,25(4):99-101.

[13] 李文宇.LTE/LTE-advanced自组织网络的自优化理论和关键技术研究[D].北京：北京邮电大学，2013.

[14] 袁天星.MIMO-OFDM系统下行链路自适应资源分配算法研究[D].南京：东南大学，2010.

[15] 虎 威.TD-LTE特殊子帧配比的优化设计[J].移动通信,2014,38(6):9-13.

[16] 张瀚峰.宽带OFDMA系统无线资源管理技术研究[D].北京：北京邮电大学，2007.

[17] 赵志信.非理想信道状态信息下OFDMA系统自适应资源分配技术研究[D].哈尔滨：哈尔滨工业大学，2014.

An Improved Proportional Fairness Algorithm for
Changes in Number of Users

ZHANG Yi,LIANG Jin-bo,WANG Jing-ning

(The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China)

In view of the changes in number of users in complex environment,this paper analyzes the relationship between the number of users and the throughput of different resource allocation algorithms,finds out the trends of changes.Based on existing proportional fairness algorithm,this paper puts forward a regulation factor.In acceptable range of fairness specification,a modified proportional fairness algorithm can adapt well to the changes in number of user less than 100,and avoid too close to the theoretical lower bounds on the throughput values,at lower throughput rates,9% performance promotion can be obtained.The algorithm proposed in this paper will be able to better adapt to the time-varying environment,effectively improve the performance degradation of system caused by proliferation in number of users.

resource scheduling;proportional fairness algorithm;throughput;regulation factor

10.3969/j.issn.1003-3114.2017.01.12

张 祎，梁进波，王荆宁.一种针对用户数量变化而改进的比例公平算法[J].无线电通信技术,2017,43(1):47-50，72.

2016-09-19

国家部委基金资助项目

张 祎(1991—)，男，硕士研究生，主要研究方向：无线通信。梁进波(1966—)，男，研究员,主要研究方向：通信与信息系统、对流层散射通信技术。王荆宁(1981—)，男，博士,主要研究方向：宽带无线通信。

TN911

A

1003-3114(2017)01-47-5