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

張 祎，梁進(jìn)波，王荊寧

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

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

張 祎，梁進(jìn)波，王荊寧

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

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

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

0 引言

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

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

1 現(xiàn)有算法

1.1 Max C/I算法

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

(1)

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

1.2 RR算法

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

1.3 PF算法

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

(2)

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

2 改進(jìn)算法

2.1 改進(jìn)公式

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

對(duì)優(yōu)先級(jí)公式的改進(jìn)：

(3)

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

α=0,β=1時(shí)，為RR算法；

α=β=1時(shí)，為PF算法。

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

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

α=0,β=1時(shí)，為RR算法；

α=β=0.5時(shí)，為PF算法。

此時(shí)β=1-α。

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

(4)

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

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

(5)

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

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

(6)

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

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

圖1 PFa算法流程圖

2.2 吞吐量仿真及分析

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

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

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

圖2 10個(gè)用戶

圖3 40個(gè)用戶

圖4 100個(gè)用戶

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

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

由表2可以看出：

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

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

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

2.3 公平性仿真及分析

以公平性的角度來(lái)看，本文以最小最大公平性準(zhǔn)則(Min-max Fairness)作為參考指標(biāo)。Min-max公平性準(zhǔn)則描述為：當(dāng)一種有效地資源分配方案[R1,R2,...,RN]符合該準(zhǔn)則時(shí)，對(duì)于任意一個(gè)用戶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算法會(huì)小幅度降低用戶間的公平性，但是基本還與PF算法相當(dāng)，在可以接受的范圍之內(nèi)，而在與MAX C/I算法比較時(shí)明顯可以看出PFa算法遠(yuǎn)高于理論下限值。

圖5 10個(gè)用戶

圖6 40個(gè)用戶

圖7 100個(gè)用戶

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

3 結(jié)束語(yǔ)

本文在現(xiàn)有PF算法的基礎(chǔ)上，根據(jù)用戶數(shù)量與吞吐量的關(guān)系變化趨勢(shì)，提出了一種PFa算法，在Matlab仿真中可以看出，由于有滑動(dòng)系數(shù)的存在，可以保證用戶數(shù)量在100以內(nèi)變化時(shí)獲得可觀的吞吐量增益，避免過(guò)于逼近吞吐量的理論下限值。以Min-max準(zhǔn)則衡量，PFa算法的公平性在可以通信的范圍內(nèi)，故可行性沒(méi)有問(wèn)題。當(dāng)用戶數(shù)量增加到100時(shí)可以獲得接近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].移動(dòng)通信,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無(wú)線通信系統(tǒng)中的無(wú)線資源調(diào)度技術(shù)研究[D].南京：南京郵電大學(xué)，2010.

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

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

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

[12] 何 怡.一種多用戶OFDM系統(tǒng)的資源調(diào)度算法[J].北京：計(jì)算機(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ì)[J].移動(dòng)通信,2014,38(6):9-13.

[16] 張瀚峰.寬帶OFDMA系統(tǒng)無(wú)線資源管理技術(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

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

2016-09-19

國(guó)家部委基金資助項(xiàng)目

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

TN911

A

1003-3114(2017)01-47-5