一種針對用戶數量變化而改進的比例公平算法

張 祎，梁進波，王荊寧

(中國電子科技集團公司第五十四研究所，河北 石家莊 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