劉海林，張新有，邢煥來

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

基于IEEE802.16m的一種改進比例公平調(diào)度算法

劉海林，張新有，邢煥來

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

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

IEEE802.16m;OFDMA;資源分配;比例公平調(diào)度算法

1 概述

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

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

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

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

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

2 OFDMA系統(tǒng)模型

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

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

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

3 算法描述

3.1 經(jīng)典比例公平調(diào)度算法

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

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

在t時刻，PF調(diào)度算法根據(jù)式(2)最先調(diào)度優(yōu)先級最高的用戶。

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

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

PF調(diào)度算法流程如圖1所示。其中在分配RU的過程中，優(yōu)先級高的用戶優(yōu)先選擇對其具有最大數(shù)據(jù)傳輸速率的RU。

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

3.2 改進的比例公平調(diào)度算法

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

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

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

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

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

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

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

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

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

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

4 仿真分析

4.1 仿真環(huán)境

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

4.2 實驗結(jié)果分析

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

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

圖3 公平性指數(shù)比較

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

圖5比較了兩種調(diào)度算法的平均時延。

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

圖6比較了兩種調(diào)度算法的丟包率。

圖6 丟包率比較

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

5 結(jié)束語

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

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

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

［3］ 蔡靈靈，趙建立，宋榮方.提供QoS保證的比例公平調(diào)度改進算法及其應(yīng)用［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］黃高勇.無線多跳中繼網(wǎng)絡(luò)資源分配與調(diào)度策略研究［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中的協(xié)作中繼技術(shù)研究［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">網(wǎng)絡(luò)出版時間:

時間:2016-08-23

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

劉海林(1989-)，男，碩士，研究方向為無線網(wǎng)絡(luò);張新有，副教授，研究方向為網(wǎng)絡(luò)體系結(jié)構(gòu)、無線網(wǎng)絡(luò)、嵌入式系統(tǒng)等;邢煥來，副教授，研究方向為SDN、無線網(wǎng)絡(luò)。

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