張 祎，梁進波，王荊寧

(中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

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

張 祎，梁進波，王荊寧

(中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

針對復(fù)雜環(huán)境下用戶數(shù)量改變的情況，對用戶數(shù)量和不同資源分配算法吞吐量之間的關(guān)系進行了分析，找出其變化趨勢，在現(xiàn)有比例公平算法的基礎(chǔ)上，提出了一種調(diào)節(jié)因子，在公平性指標(biāo)可以接受的范圍內(nèi)，使得改進后的比例公平算法可以良好適應(yīng)100以內(nèi)的用戶數(shù)量變化，避免過于逼近吞吐量的理論下限值，在吞吐量較低時最高可以獲得接近9%的性能提升。提出的算法將能夠更好地適應(yīng)時變環(huán)境，有效改善用戶數(shù)激增帶來的系統(tǒng)性能下降問題。

資源調(diào)度；比例公平算法；吞吐量；調(diào)節(jié)因子

0 引言

在無線通信中，頻帶資源和功率資源是有限的[1]，要想在保證各個用戶之間公平性的同時努力使系統(tǒng)內(nèi)總吞吐量最大化是我們需要解決的重要問題[2]。最大載干比(MAX C/I)算法保證好的信道上的用戶可以獲得資源，其吞吐量是理論上的上限；輪詢(Round Robin,RR)算法則保證每個用戶都有相同的幾率被調(diào)度，所以其吞吐量在理論上是下限[3]。在這2種算法的基礎(chǔ)上，比例公平(Proportional Fair,PF)算法是目前被普遍應(yīng)用的一種調(diào)度算法，同時兼顧了吞吐量和公平性[4]，但是在用戶數(shù)量增加時，其吞吐量也不斷下降直至逼近輪詢算法，所以在復(fù)雜環(huán)境發(fā)生變化時的應(yīng)用受到一定的限制，使得系統(tǒng)性能有所下降[5]。

在現(xiàn)有PF算法的理論基礎(chǔ)上，提出了一種具體可行的改進方案，通過設(shè)置合理的調(diào)節(jié)因子[6]，改變用戶速率分布，可以在用戶數(shù)量增加時，防止PF算法的平均吞吐量過快下降逼近理論下限值，從而更有效地利用有限的資源，提高系統(tǒng)的整體性能。

1 現(xiàn)有算法

1.1 Max C/I算法

Max C/I算法的主要目標(biāo)是提高整個系統(tǒng)的吞吐量，其調(diào)度原則是[7]：在每一時刻調(diào)度都會選擇C/I值大的用戶，這樣可以保證信道質(zhì)量最好的用戶能夠分得最多的資源[8]。假設(shè)有N個用戶申請調(diào)度[9]，在t時刻，用戶i的載干比為γi(t)，那么符合最大載干比算法的用戶為：

(1)

MAX C/I調(diào)度算法能夠獲得比其他算法更高的吞吐量，達到理論上的極限值，但是該算法系統(tǒng)吞吐量的最大化是以犧牲用戶間的公平性為代價的[10]。

1.2 RR算法

RR算法的主要目標(biāo)是保證系統(tǒng)中所有用戶具有相同的機會來獲得系統(tǒng)資源，是公平性的極限。在進行調(diào)度時，所有用戶會按照某個特定的順序循環(huán)占用系統(tǒng)的無線資源，并且占用資源的時間長度相等[11]，N個用戶被調(diào)度的概率相同，都是1/N。所以該算法具有很高的公平性，可以保證用戶同時具有長期公平性和短期公平性，但是該算法是在犧牲系統(tǒng)吞吐量的基礎(chǔ)上保證各個用戶之間的公平性，故而RR算法具有最低的吞吐量[12]。

1.3 PF算法

MAX C/I算法和RR算法都是在犧牲系統(tǒng)吞吐量或用戶公平性中的某個指標(biāo)來保證另一個指標(biāo)，為了取得二者的折中平衡，提出了PF算法。不同于MAX C/I算法或者RR算法只考慮調(diào)度用戶的信道狀況或者用戶間的公平性，PF算法充分利用信道的時頻特性盡可能調(diào)度信道狀況較好的用戶，同時盡可能調(diào)度到每一個用戶，兼顧吞吐量和公平性兩方面的要求[13]。

(2)

但是PF算法同樣存在一些問題，在用戶數(shù)量較少時，其吞吐量接近MAX C/I調(diào)度算法，可以保證系統(tǒng)性能，但是當(dāng)用戶數(shù)增加時，其吞吐量快速下降直至逼近RR算法，這時的用戶平均吞吐量已經(jīng)不能用于正常通信[15]。

2 改進算法

2.1 改進公式

在整個系統(tǒng)中，用戶數(shù)量的不確定性很強，數(shù)值通常會在0～100之間浮動，為了保證在各種數(shù)量的情況下都能使系統(tǒng)正常運轉(zhuǎn)，需要設(shè)置一個動態(tài)參數(shù)，可以隨著用戶數(shù)量的變化而滑動，動態(tài)調(diào)節(jié)PF算法的偏向[16-17]，在用戶數(shù)量增加時大幅提高吞吐量，使其在整個范圍區(qū)間內(nèi)達到很好的效果，避免過于接近RR算法的吞吐量下限值。

對優(yōu)先級公式的改進：

(3)

已知公式中當(dāng)α=1,β=0時，為MAX C/I算法；

α=0,β=1時，為RR算法；

α=β=1時，為PF算法。

現(xiàn)在為了方便計算，令α+β=1，則：

α=1,β=0時，為MAX C/I算法；

α=0,β=1時，為RR算法；

α=β=0.5時，為PF算法。

此時β=1-α。

根據(jù)實際應(yīng)用和初步計算，本文設(shè)定α的取值區(qū)間為0.2～0.8，當(dāng)用戶數(shù)量等于40時，α=0.5；當(dāng)用戶數(shù)量大于等于100時，α=0.8；當(dāng)用戶數(shù)量小于等于10時，α=0.2，即:

(4)

式中，N代表用戶數(shù)量。

為了提高吞吐率，對優(yōu)先級公式進行如下改進：

(5)

用來改變用戶速率分布，比平均請求傳輸速率高的用戶優(yōu)先級相對更高，這樣就能夠使處于較好的信道狀況的用戶被調(diào)度的機會提高，與此同時降低處于較差信道狀況用戶被調(diào)度的機會。

綜合上述分析，為了達到在用戶數(shù)量變化的情況下提高系統(tǒng)吞吐量的目的，最終采用的優(yōu)先級公式為：

(6)

本文將其命名為改進型輪詢(Proportional Fair-Advanced，PFa)算法。

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

圖1 PFa算法流程圖

2.2 吞吐量仿真及分析

本文分別在用戶數(shù)量為10、40、100時進行Matlab仿真，將PFa算法與經(jīng)典算法進這行吞吐量比較，仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

本文分別在用戶數(shù)量為10、40、100時進行Matlab仿真，將PFa算法與經(jīng)典算法進行吞吐量比較，仿真結(jié)果如圖2、圖3和圖4所示。

圖2 10個用戶

圖3 40個用戶

圖4 100個用戶

Matlab仿真吞吐量統(tǒng)計如表2所示。

表2 Matlab仿真吞吐量統(tǒng)計表(30 dB)

由表2可以看出：

① 隨著用戶數(shù)量的增加，3種算法的吞吐量都在下降；② 在用戶數(shù)量從10增加到40時，吞吐量下降了大約73%，較為顯著，而用戶數(shù)從40提高到100時下降約60%；③ PF算法在用戶數(shù)量不斷增加的同時在向RR算法逼近，當(dāng)數(shù)量足夠大時最終會與RR算法重合。

既PF算法的公平性在不斷提高，但是犧牲了整體的吞吐量。

而在Mtlab仿真中可以看出，PFa算法使得用戶的吞吐量得到提高，而且在用戶數(shù)量增大時效果尤為明顯，在10名用戶時性能大約提升3.8%，而在100名用戶時吞吐量性能提升了約8.7%。說明PFa算法在用戶數(shù)量增加時改善效果更為顯著，可以有效根據(jù)用戶數(shù)量做出調(diào)整，使系統(tǒng)的性能得到提升。

2.3 公平性仿真及分析

以公平性的角度來看，本文以最小最大公平性準(zhǔn)則(Min-max Fairness)作為參考指標(biāo)。Min-max公平性準(zhǔn)則描述為：當(dāng)一種有效地資源分配方案[R1,R2,...,RN]符合該準(zhǔn)則時，對于任意一個用戶i，其所分配的資源Ri都不可能再變大，除非使得Rj

Min-max準(zhǔn)則公式:

(7)

即分配資源數(shù)最小與最大值的比值。

圖5、圖6和圖7為Min-max準(zhǔn)則的仿真結(jié)果。從圖表中可以看出，以Min-max準(zhǔn)則為標(biāo)準(zhǔn)，PFa算法會小幅度降低用戶間的公平性，但是基本還與PF算法相當(dāng)，在可以接受的范圍之內(nèi)，而在與MAX C/I算法比較時明顯可以看出PFa算法遠(yuǎn)高于理論下限值。

圖5 10個用戶

圖6 40個用戶

圖7 100個用戶

因此，本文提出的PF改進算法是合理的，能夠緩解用戶增加所帶來的吞吐量減少問題，與此同時又能適當(dāng)兼顧公平性準(zhǔn)則，避免極端分配所導(dǎo)致的“餓死”現(xiàn)象發(fā)生。

3 結(jié)束語

本文在現(xiàn)有PF算法的基礎(chǔ)上，根據(jù)用戶數(shù)量與吞吐量的關(guān)系變化趨勢，提出了一種PFa算法，在Matlab仿真中可以看出，由于有滑動系數(shù)的存在，可以保證用戶數(shù)量在100以內(nèi)變化時獲得可觀的吞吐量增益，避免過于逼近吞吐量的理論下限值。以Min-max準(zhǔn)則衡量，PFa算法的公平性在可以通信的范圍內(nèi)，故可行性沒有問題。當(dāng)用戶數(shù)量增加到100時可以獲得接近9%的性能提升，所以PFa算法是提高通信質(zhì)量的一種有效方式。

[1] 章 歡.LTE系統(tǒng)資源調(diào)度算法的研究[D].哈爾濱：哈爾濱工程大學(xué)，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寬帶數(shù)字集群通信發(fā)展分析及建議[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下行資源調(diào)度算法研究[D].西安：西安電子科技大學(xué)，2013.

[8] 李 俏.LTE無線通信系統(tǒng)中的無線資源調(diào)度技術(shù)研究[D].南京：南京郵電大學(xué)，2010.

[9] 任 敏.LTE-A中的小區(qū)選擇和用戶調(diào)度算法研究[D].西安：西安電子科技大學(xué)，2010.

[10] 黃明娟.單用戶OFDM系統(tǒng)中動態(tài)資源分配算法的研究[D].濟南：山東大學(xué)，2011.

[11] 趙希鵬，張 欣，楊大成，等.基于QoE的無線網(wǎng)絡(luò)資源調(diào)度優(yōu)化研究[J].移動通信，2014,38(22):8-13.

[12] 何 怡.一種多用戶OFDM系統(tǒng)的資源調(diào)度算法[J].北京：計算機仿真,2008,25(4):99-101.

[13] 李文宇.LTE/LTE-advanced自組織網(wǎng)絡(luò)的自優(yōu)化理論和關(guān)鍵技術(shù)研究[D].北京：北京郵電大學(xué)，2013.

[14] 袁天星.MIMO-OFDM系統(tǒng)下行鏈路自適應(yīng)資源分配算法研究[D].南京：東南大學(xué)，2010.

[15] 虎 威.TD-LTE特殊子幀配比的優(yōu)化設(shè)計[J].移動通信,2014,38(6):9-13.

[16] 張瀚峰.寬帶OFDMA系統(tǒng)無線資源管理技術(shù)研究[D].北京：北京郵電大學(xué)，2007.

[17] 趙志信.非理想信道狀態(tài)信息下OFDMA系統(tǒng)自適應(yīng)資源分配技術(shù)研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，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

張 祎，梁進波，王荊寧.一種針對用戶數(shù)量變化而改進的比例公平算法[J].無線電通信技術(shù),2017,43(1):47-50，72.

2016-09-19

國家部委基金資助項目

張 祎(1991—)，男，碩士研究生，主要研究方向：無線通信。梁進波(1966—)，男，研究員,主要研究方向：通信與信息系統(tǒng)、對流層散射通信技術(shù)。王荊寧(1981—)，男，博士,主要研究方向：寬帶無線通信。

TN911

A

1003-3114(2017)01-47-5