基于IEEE802.16m的一種改進比例公平調度算法

劉海林，張新有，邢煥來

(西南交通大學信息科學與技術學院，四川成都 610031)

基于IEEE802.16m的一種改進比例公平調度算法

劉海林，張新有，邢煥來

(西南交通大學信息科學與技術學院，四川成都 610031)

比例公平調度算法在系統吞吐量和公平性之間能取得較好的權衡，它在無線網絡資源分配中已經成為一個突出的候選方案。但比例公平調度算法本身存在一些缺陷，如無法反映用戶的信道狀態，沒有考慮不同業務的服務質量等。考慮用戶的信道狀態，針對比例調度算法在分配資源時會抑制不良信道用戶的吞吐量，進而影響整個系統的吞吐量的問題，提出了一種改進的比例公平調度算法，以提高IEEE802.16m下行OFDMA系統的吞吐量。該算法根據用戶的信道速率將用戶分成多個組。先計算每組的調度優先級，然后選擇調度優先級最高的組進行調度，最后在選擇的組中根據輪詢調度算法對用戶進行資源分配。仿真結果表明，改進的比例公平調度算法在吞吐量、公平性、時延、丟包率等方面優于傳統的比例調度算法。

IEEE802.16m;OFDMA;資源分配;比例公平調度算法

1 概述

全球微波互聯接入是互聯網市場的一種性能優異的帶寬無線接入技術。IEEE802.16m是IEEE802.16e的增強標準［1］。由于正交頻分多址(Orthogonal Frequency Division Multiple Access，OFDMA)在寬帶無線系統中具有抗多徑衰落的能力、靈活的資源分配方式、易與多天線結合、易于擴展帶寬等優點，被IEEE802. 16m標準采用作為多址接入方式［2］。

日益增長的帶寬需求迫切需要有效地利用IEEE802.16m OFDMA系統中的資源單元(Resource Unit，RU)。在IEEE802.16m下行 OFDMA系統中，RU是基站(Base Station，BS)傳輸數據到用戶的基本單元。在多信道多速率的無線網絡中存在各種各樣的多載波調度算法，如果總是分配RU給最佳信道的用戶以使系統吞吐量最大化，則會導致不良信道的用戶饑餓。如果802.16的介質訪問控制層協議提供同等的接入概率給所有用戶，會導致不良信道的用戶占據大部分的通話時間，這樣為達到用戶吞吐量公平，反而嚴重降低了系統吞吐量。而比例公平(Proportional Fair，PF)調度算法［3］在公平性和系統吞吐量之間能取得相對比較好的折中，且比較適用于實際系統。但PF調度算法本身存在一些缺陷:如用戶的優先級只是根據用戶實際需要傳輸的數據大小來決定，沒有考慮用戶的信道狀態;不同的用戶經歷的信道狀態不同時，用戶能獲得的數據傳輸速率也會顯示出不公平性，信道狀態經歷最高變化的用戶會得到更高的調度機會。此外，PF調度算法也沒有考慮服務時延等。因此，出現了大量基于PF的改進方案，定義了各種基于PF的改進函數。

文獻［4-5］在系統可以接受的最低吞吐量的情況下采用比例公平的思想來消除饑餓，該方案實現了用戶吞吐量之間的公平性。文獻［6-7］結合PF調度算法和儲備最小帶寬的思想來調度多種業務，取得了更高的吞吐量公平。文獻［8］在分配資源時先儲備每個業務流的最小帶寬請求，然后針對實時業務的服務質量(Quality of Service，QoS)定義了延遲約束和損失概率，提出了比例損失調度算法，最大限度地提高了系統的吞吐量。文獻［9］考慮用戶的數據包延遲信息，分配最好的資源塊給最高分組延遲的用戶。該算法只考慮了分組延遲信息這一準則，因此資源塊的分配會傾向于不良信道的用戶，從而會降低整個系統的吞吐量。文獻［10］基于用戶的瞬時信道狀態和隊列長度，針對多載波系統提出了一種跨層的QoS感知的PF調度算法。該算法在系統吞吐量、丟包率和時延方面取得了較好的性能。

這些方案在某些方面都比原來的PF算法有更好的性能，但它們都沒有考慮在長時間內提升不良信道用戶的吞吐量。在無線網絡的某些情況下，如用戶從一個良好信道的位置移動到一個不良信道的位置也需要保證其QoS要求。從理論上講，為了滿足不同的QoS要求，基站必須考慮整個系統的狀態，然后做出接納控制決定。PF調度算法在長時間內可以認為分配了相等的通話時間給每個用戶。因此，通過PF調度算法來調度會抑制不良信道用戶的吞吐量，進而限制整個系統的吞吐量。

針對不良信道的用戶會限制整個系統的吞吐量，考慮長時間內用戶的信道狀態，文中提出一種改進的比例公平(Improved Proportional Fairness，IPF)調度算法，提高IEEE802.16m下行OFDMA系統的吞吐量，同時仍然保持其公平性。

2 OFDMA系統模型

IEEE802.16m支持TDD和FDD兩種雙工方式。文中采用TDD方式，并以10 M帶寬作為研究對象。對類型1子幀來說，其相應的資源單元在頻率上有18個連續的子載波，在時域上有6個正交頻分復用(Orthogonal Frequency Division Multiplexing，OFDM)符號［11］。RU又分為物理資源單元(Physical Resource U-nit，PRU)和邏輯資源單元(Logical Resource Unit，LRU)。PRU和LRU大小相等，在頻域上都是18個子載波，在時域上是6個符號長度。IEEE802.16m將資源在時域和頻域上同時進行劃分，并以LRU作為最小分配單元。在帶寬資源分配中，系統根據相關信息以LRU為單元進行分配，在完成數據分配后需要將LRU映射到PRU中，然后才能發送出去。

下面考慮單蜂窩場景中的 IEEE802.16m下行OFDMA系統，假設所有用戶都和一個BS通信。用戶估計其瞬時信道狀態，并且向BS發送其信道質量指示符［12］。通過信道狀態信息，信噪比和誤碼率，自適應調制編碼動態地確定每個用戶的瞬時數據傳輸速率。其中用戶的信道狀況是隨時間變化的。

BS包含一個集中分組調度器，它負責小區內所有用戶的帶寬資源分配［13］。BS分配無線資源是基于一個基本的時頻資源單元(稱為RU)。每個RU的確定都可能受到信道狀況的影響，但整個RU的發送持續時間保持不變。在每個傳輸時間間隔(Transmission Time Interval，TTI)，BS調度RU給所有用戶。

3 算法描述

3.1 經典比例公平調度算法

IEEE802.16m EMD(Evaluation Methodology Document)文檔［14］建議的調度算法就是PF調度算法，因為其綜合考慮了優先級、公平性，是調度算法的衡量標準［15］。PF調度算法在分配資源之前先計算各個用戶的優先級，在每個傳輸時刻最先調度優先級最高的用戶。假設系統中有M個用戶，用戶的優先級計算如式(1)所示。

其中，Rk(t)為在t時刻用戶k的請求數據傳輸速率;(t)為在 t時刻截至之前用戶 k的平均傳輸速率。

在t時刻，PF調度算法根據式(2)最先調度優先級最高的用戶。

每一次調度完成后，用戶k的平均傳輸速率按式(3)更新，即每個TTI更新一次。

其中，Rck(t)是在t時刻用戶k的實際數據傳輸速率;參數T是滑動時間窗長度，其大小根據調度過程中每個用戶閑置的最大時間確定。

PF調度算法流程如圖1所示。其中在分配RU的過程中，優先級高的用戶優先選擇對其具有最大數據傳輸速率的RU。

每個用戶的數據傳輸速率和其他用戶使用的數據傳輸速率是獨立的。由分析可知，PF調度算法是根據當前時刻歸一化了的瞬時數據傳輸速率來選擇用戶，用戶的瞬時數據傳輸速率在滑動窗口時間T內通過平均傳輸速率歸一化了，所以從長遠看每個用戶都獲得了相等的通話時間。這表明，通過PF調度算法來分配資源，會抑制不良信道用戶的吞吐量。因此，不良信道的用戶通過PF調度算法來分配資源無疑會限制整個系統的吞吐量。

3.2 改進的比例公平調度算法

為了解決PF調度算法中不良信道用戶的吞吐量問題，首先BS根據用戶相應的信道瞬時數據傳輸速率把用戶分成不同的組，簡化多信道的調度算法，然后導出改進的基于PF調度算法的IPF函數。

首先BS根據用戶信道的數據傳輸速率分成相應的k個區間。在每個TTI，根據用戶的信道瞬時數據傳輸速率把用戶分成k個組，把第k組中第一個到達的用戶的瞬時數據傳輸速率作為該組的瞬時數據傳輸速率Rk(t)。組的數量等于OFDMA系統中可能的數據傳輸速率集。G={1，2，…，k}表示組集，k表示組號，每個組在t時刻都有一個對應的瞬時數據傳輸速率Rk(t)。Grk(t)是在t時刻k組的隊列長度，即每組的用戶數。根據式(4)計算G中各組的優先級。

其中，Rck(t)是在t時刻第k組所有用戶的實際數據傳輸速率之和，沒有接受服務的用戶，其實際數據傳輸速率等于0。

αk(t)表示t時刻第k組用戶數占總用戶數的比例，其計算如式(6)所示。

RUk(t)表示在t時刻截至之前第k組的RU平均使用速率，根據式(7)更新。

在資源分配過程中，一個用戶可能被分配多個RU，且分配的RU可能不連續，先選擇對該用戶具有最大數據傳輸速率的RU。xk(t，m)表示RU的使用狀態，如果RUm被第k組中的用戶使用，其值則為1，反之為0。假設每幀中有M個RU，所以xk(t，m)表示t時刻第k組使用的RU數目。

在每個TTI，IPF調度算法根據式(8)選擇函數值最大的第k組。

然后從選擇的第k組中按照輪詢(Round-Robin，RR)調度算法依次分配RU給第k組中的用戶，直到所有的RU被分配或者所有的用戶都調度完了，最后更新平均速率(t)和RU平均使用速率RUk(t)。

假設所有的用戶與BS通信，IPF調度算法流程如圖2所示。BS分配RU給每個用戶，其中在分配RU的過程中，先調度的用戶從未使用的RU中選擇對該用戶具有最大數據傳輸速率的RU。

為了提高不良信道用戶的吞吐量，IPF調度算法考慮了隊列的長度比和RU平均使用速率。此外，在二級調度中使用RR調度算法來提高用戶之間的公平性。由分析可知不良信道的用戶在隊列中需要更多的緩沖區，從而會增加其隊列長度比，增加IPF函數的值，增加調度機會，同時IPF調度算法是先以組為單位進行調度，相對剩余的RU也較多，有更多的機會選擇較高數據傳輸速率的RU，所以能提高整個系統的吞吐量。另一方面，當RU平均使用速率較大時，IPF的值會降低，減少了不良信道的用戶在下次調度中的機會，以免降低系統的吞吐量。

4 仿真分析

4.1 仿真環境

以IEEE802.16m EMD文檔建議的系統參數為仿真參數，在Matlab中進行仿真。假設所有的用戶與BS通信，IEEE802.16m OFDMA系統中的無線信道模型服從瑞利分布，文中只考慮下行鏈路和實時業務。仿真的有關參數設置見表1。

4.2 實驗結果分析

文中從公平性、吞吐量、平均時延、丟包率等方面分析改進算法的性能，并且和原算法進行對比。

圖3使用Jain Fairness指數比較了IPF調度算法和PF調度算法的公平性。仿真中設置的用戶數是50。由Jain Fairness公式可知，公平指數越高，系統的公平性越好。仿真結果顯示，公平指數在幀數較多的情況下更接近1。表明在調度開始時，只有部分用戶得到了資源調度，還有部分用戶沒有分配到資源，所以用戶公平性較差;在幀數較多的情況下，即隨著時間的增加，所有的用戶都得到了資源調度，所以用戶的公平性趨于穩定。此外，從圖3中還可以看出，IPF調度算法公平指數大于PF調度算法。這是因為IPF調度算法在二級調度中使用了RR。RR有較高的公平性，由此取得了更好的公平性。

圖3 公平性指數比較

圖4顯示了系統的吞吐量和幀數的性能。仿真中設置的用戶數也是50。如圖4所示，IPF調度算法比PF調度算法有更高的系統吞吐量。同時在調度開始時，只有部分用戶得到了資源調度，系統吞吐量還不穩定，隨著時間的增加，所有的用戶都得到了資源調度，系統的吞吐量趨于穩定。主要是因為IPF考慮了隊列的長度比以提高不良信道用戶的吞吐量，同時IPF調度是先以組為單位進行，剩余的RU相對較多，有更多的機會選擇較高數據傳輸速率的RU。另一方面考慮了RU的平均使用速率，以避免不良信道的用戶降低系統的吞吐量。

圖5比較了兩種調度算法的平均時延。

如圖5所示，IPF調度算法和PF調度算法的平均時延分別在用戶數為60和30處突然增加。PF調度算法的平均時延快速增加，主要是由于沒有考慮不良信道用戶的影響。此外也表明IPF調度算法可以容納比PF調度算法更多的實時業務。

圖6比較了兩種調度算法的丟包率。

圖6 丟包率比較

如圖6所示，IPF調度算法的丟包率小于PF調度算法。這是因為IPF調度算法比PF調度算法能容納更多的實時業務。IPF調度算法和PF調度算法的丟包率在用戶數較少時都較低，隨著用戶數的增加丟包率也增加。這是因為當用戶數較少時，系統中有足夠的RU來滿足用戶，用戶在較短時間內能夠得到調度;隨著用戶數的增加，系統容量也增加，當系統容量達到最大時，數據包得不到及時傳輸而被丟棄，從而導致丟包率增大。

5 結束語

為了提高IEEE802.16m下行OFDMA系統中不良信道用戶的吞吐量，文中提出一種IPF調度算法。算法根據用戶相應的信道數據傳輸速率把用戶分成若干個組，以簡化多信道OFDMA系統的調度。此外，算法還綜合考慮了瞬時數據傳輸速率、平均數據傳輸速率、隊列長度比和RU平均使用速率等因素，以提高不良信道用戶的吞吐量，從而最大限度地提高系統的吞吐量。仿真結果表明，IPF調度算法在公平性、平均時延、丟包率方面也優于PF調度算法。

［1］ 焦慧穎，董曉魯.IEEE802.16m標準的最新進展［J］.世界電信，2007，20(11):52-55.

［2］ 杜 瀅，方惠英，劉 揚，等.IEEE802.16m寬帶無線技術與系統設計［M］.北京:人民郵電出版社，2010.

［3］ 蔡靈靈，趙建立，宋榮方.提供QoS保證的比例公平調度改進算法及其應用［J］.中國電子科學研究院學報，2009，4 (1):67-71.

［4］ Kaneko M，Popovski P，Dahl J.Proportional fairness in multicarrier system with multi-slot frames:upper bound and user multiplexing algorithms［J］.IEEE Transactions on Wireless Communications，2008，7(1):22-26.

［5］ Ruangchaijatupon N，Ji Y.Simple proportional fairness scheduling for OFDMA frame-based wireless systems［C］//Proc of conference on wireless communications and networking.［s. l.］:［s.n.］，2008:1593-1597.

［6］ Ruangchaijatupon N，Yusheng J I.OFDMA resource allocation based on traffic class-oriented optimization［J］.IEICE Transactions on Communications，2009，92(1):93-101.

［7］ Ruangchaijatupon N，Ji Y.Integrated approach to proportionalfair resource allocation for multiclass services in an OFDMA system［C］//Proc of conference on global telecommunications.［s.l.］:［s.n.］，2009:1-6.

［8］ Lee T H，Huang Y W.Resource allocation achieving high system throughput with QoS support in OFDMA-based system ［J］.IEEE Transactions on Communications，2012，60(3):851 -861.

［9］ Sandrasegaran K，Ramli H A M，Basukala R.Delay-prioritized scheduling(DPS)for real time traffic in 3GPP LTE system［C］//Proc of conference on wireless communications and networking.［s.l.］:［s.n.］，2010:1-6.

［10］Kong Z，Kwok Y K，Wang J.A low-complexity QoS-aware proportional fair multicarrier scheduling algorithm for OFDM systems［J］.IEEE Transactions on Vehicular Technology，2009，58(5):2225-2235.

［11］黃志科.IEEE802.16m控制信道的研究［D］.杭州:浙江大學，2012.

［12］王忠俠.基于OFDM的認知無線電資源分配算法研究［D］.長春:吉林大學，2015.

［13］黃高勇.無線多跳中繼網絡資源分配與調度策略研究［D］.成都:西南交通大學，2014.

［14］ IEEE802.16m Evaluation Methodology Document(EMD) ［EB/OL］.［2009-01-15］.http://grouper.ieee.org/groups/ 802/16/tgm/docs/80216m-08_004r5.zip.

［15］王 瑞.IEEE 802.16m中的協作中繼技術研究［D］.北京:北京郵電大學，2009.

An Improved Proportional Fair Scheduling Algorithm Based on IEEE802.16m

LIU Hai-lin，ZHANG Xin-you，XING Huan-lai
(School of Information Science＆Technology，Southwest Jiaotong University，Chengdu 610031，China)

Proportional fair scheduling algorithm can obtain a good tradeoff between system throughput and fairness.It has become an outstanding candidate scheme in wireless networks resource allocation.However，there are some defects in proportional fair scheduling algorithm.For example，it doesn’t reflect the users’channel state and consider the quality of different service.When it comes to the users’channel state，since the proportional scheduling algorithm will inhibit the throughput of the poor channel users，and then affect the overall system throughput.In view of this problem，an improved proportional fairness scheduling algorithm is proposed，which will improve the throughput of IEEE802.16m downlink OFDMA system.According to the users’channel rate，the scheduling algorithm classifies users into several groups.Firstly，the scheduling priority of each group will be calculated.And then the group with the highest scheduling priority will be scheduled.Finally，according to the round-robin scheduling algorithm，resources will be allocated to users in the selected group.The simulation shows that the improved proportional fairness scheduling algorithm is better than the original in terms of throughput，fairness，delay and packet loss rate.

IEEE802.16m;OFDMA;resource allocation;proportional fair scheduling algorithm

TP393.2

:A

1673-629X(2016)09-0158-05

10.3969/j.issn.1673-629X.2016.09.035

2015-12-14

2016-04-07< class="emphasis_bold">網絡出版時間:

時間:2016-08-23

國家自然科學基金資助項目(61401374)

劉海林(1989-)，男，碩士，研究方向為無線網絡;張新有，副教授，研究方向為網絡體系結構、無線網絡、嵌入式系統等;邢煥來，副教授，研究方向為SDN、無線網絡。

http://www.cnki.net/kcms/detail/61.1450.TP.20160823.1359.058.html