一種基于LTE業(yè)務(wù)特征的調(diào)度算法切換系統(tǒng)

李校林,2，付 澍，胡 楠

(1.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究所，重慶 400065；2.重慶郵電大學(xué) 重慶信科設(shè)計(jì)有限公司，重慶 400065)

1 引 言

LTE采用了扁平化全I(xiàn)P網(wǎng)絡(luò)架構(gòu)，其業(yè)務(wù)對(duì)丟包率、時(shí)延和吞吐量等QoS指標(biāo)要求提升。而對(duì)于不同的業(yè)務(wù)其實(shí)時(shí)性與非實(shí)時(shí)性不同，因此對(duì)于不同QoS指標(biāo)的要求也有所不同。由于LTE系統(tǒng)時(shí)頻二維結(jié)構(gòu)的特性，其系統(tǒng)性能的好壞很大程度上取決于資源調(diào)度算法的高效性。目前的資源調(diào)度算法主要有最大載干比算法、公平算法、輪詢調(diào)度算法和比例公平調(diào)度算法，其中，比例公平算法是最大載干比算法和公平算法的結(jié)合。文獻(xiàn)[1]分析了最大載干比算法、公平算法和比例公平調(diào)度算法吞吐量、延遲等指標(biāo)的差異，根據(jù)其結(jié)果可知比例公平調(diào)度算法要明顯優(yōu)于其余3種算法。但比例公平調(diào)度(PF)算法的優(yōu)先級(jí)計(jì)算中并未考慮到用戶緩存隊(duì)列長度為零時(shí)的情況，從而在該情況下用戶優(yōu)先級(jí)仍有可能很高，從而造成了系統(tǒng)資源的浪費(fèi)，并且PF算法沒有考慮到隊(duì)列丟包率、隊(duì)列時(shí)延等對(duì)調(diào)度規(guī)則的作用。文獻(xiàn)[2]對(duì)PF算法進(jìn)行了改性，但并未考慮到不同業(yè)務(wù)的收費(fèi)等級(jí)不同且業(yè)務(wù)本身對(duì)QoS指標(biāo)的要求并不相同。本文首先介紹了LTE系統(tǒng)資源調(diào)度的基本概念，在文獻(xiàn)[1，2]的基礎(chǔ)上針對(duì)LTE系統(tǒng)根據(jù)不同業(yè)務(wù)的QoS特點(diǎn)，基于其不同的付費(fèi)優(yōu)先級(jí)提出了一套新的算法，并設(shè)計(jì)了一個(gè)基于Matlab的LTE調(diào)度算法仿真平臺(tái)，最后對(duì)所提出的算法與比例公平算法在吞吐量、丟包率、排隊(duì)時(shí)延、公平性等方面進(jìn)行了比較分析。

2 LTE系統(tǒng)資源調(diào)度基本概念與參數(shù)設(shè)置

在LTE系統(tǒng)中，業(yè)務(wù)信道完全是共享的概念，不同用戶所占用的資源塊數(shù)目、MCS(調(diào)制編碼方式)是可變的，具體的物理層規(guī)范見文獻(xiàn)[3，4]。當(dāng)選定業(yè)務(wù)的MCS后，只要系統(tǒng)帶寬足夠大，隊(duì)列中的各個(gè)業(yè)務(wù)將完全能從隊(duì)列中發(fā)送出去，也就不存在調(diào)度的問題?？墒钱?dāng)系統(tǒng)帶寬資源不夠時(shí)，將不能發(fā)送該時(shí)刻的所有業(yè)務(wù)，因此如何選擇調(diào)度方式，對(duì)LTE系統(tǒng)性能的影響將至關(guān)重要，它直接決定了各業(yè)務(wù)的QoS指標(biāo)是否能被滿足。

(1)如文獻(xiàn)[5]所述，在LTE系統(tǒng)中把調(diào)度器放置在基站側(cè)的MAC層從而可以根據(jù)信道的信息進(jìn)行快速地調(diào)度。本文根據(jù)3GPP中LTE物理層協(xié)議的要求和參數(shù)，采用文獻(xiàn)[6]所述的M/M/1/m隊(duì)列作為算法模型。

(2)對(duì)于不同的業(yè)務(wù)，理論上業(yè)務(wù)的QoS服務(wù)速率(對(duì)應(yīng)于業(yè)務(wù)的QoS吞吐量)應(yīng)大于或等于業(yè)務(wù)的到達(dá)速率，此時(shí)業(yè)務(wù)的等待隊(duì)列才不會(huì)總是滿棧而導(dǎo)致丟包和時(shí)延。但是在系統(tǒng)帶寬資源有限的情況下，該指標(biāo)往往不能完全達(dá)到，因此應(yīng)當(dāng)通過合理的調(diào)度方式來最優(yōu)化各個(gè)業(yè)務(wù)的相對(duì)吞吐量，使之在達(dá)到最低吞吐量要求的同時(shí)最大化付費(fèi)用戶的吞吐量并同時(shí)保證各用戶的丟包率、時(shí)延等指標(biāo)達(dá)到要求。

(3)假設(shè)隊(duì)列最大長度為Qmax，顯然，若到達(dá)包長L大于隊(duì)列最大長度Qmax則會(huì)直接產(chǎn)生丟包現(xiàn)象，因此應(yīng)當(dāng)使得該情況發(fā)生的概率盡可能地小(1%)。假設(shè)隊(duì)列到達(dá)的包長服從參數(shù)為λ的指數(shù)分布，則由：

得到Qmax/λ>-ln(0.01)=4.6，可取

Qmax/λ=5

(1)

即最大隊(duì)列長度設(shè)置為業(yè)務(wù)平均包長的5倍。

(4)各隊(duì)列過去時(shí)間窗長度TW內(nèi)的平均速率根據(jù)指數(shù)平滑法的思想得到。首先，由業(yè)務(wù)QoS服務(wù)速率RQoS得到當(dāng)前調(diào)度子幀內(nèi)應(yīng)傳送的數(shù)據(jù):

(2)

式中，R(t-TS)表示上一調(diào)度時(shí)刻隊(duì)列的過去時(shí)間窗平均速率，TS表示調(diào)度間隔，即一個(gè)時(shí)隙長度，TW表示統(tǒng)計(jì)時(shí)間窗長度。由于業(yè)務(wù)每次調(diào)度的實(shí)際比特?cái)?shù)Nd還同時(shí)受到來自該業(yè)務(wù)本次調(diào)度中的調(diào)度優(yōu)先級(jí)所對(duì)應(yīng)的可用資源塊數(shù)目和隊(duì)列狀態(tài)的限制，因此該式只是業(yè)務(wù)所調(diào)度比特?cái)?shù)目的上限。每次調(diào)度后，都應(yīng)當(dāng)更新隊(duì)列過去時(shí)間窗內(nèi)的平均速率為

R(t)=(R(t-TS)×(TW-TS)+Nd)/TW

(3)

(5)信道選擇：若將信道質(zhì)量不高的頻段分配給數(shù)據(jù)包長度較大的業(yè)務(wù)，則其占用資源塊數(shù)目將很大，因此應(yīng)當(dāng)將信道質(zhì)量不高的頻段盡量分配給數(shù)據(jù)包長度較小的業(yè)務(wù)隊(duì)列，而將信道質(zhì)量高的頻段留給數(shù)據(jù)包長度較大的業(yè)務(wù)。

3 一種基于不同業(yè)務(wù)付費(fèi)優(yōu)先級(jí)與QoS特點(diǎn)的算法

傳統(tǒng)的PF調(diào)度算法的優(yōu)先級(jí)可表示為

GPF=BPRB/R(t)

(4)

式中，BPRB(Bit per RB)表示每個(gè)資源塊對(duì)所能承載的比特?cái)?shù)目(對(duì)應(yīng)于由接收端SINR決定的編碼率大小)，R(t)表示過去時(shí)間窗內(nèi)平均速率。假設(shè)系統(tǒng)帶寬為10 MHz，對(duì)應(yīng)于50個(gè)物理資源塊(Resource Element Block，PRB)；子幀中的控制區(qū)域占3個(gè)OFDM符號(hào)，各業(yè)務(wù)的調(diào)制方式均為QPSK，此時(shí)一個(gè)物理資源塊對(duì)可以最大承載240 bit的數(shù)據(jù)信息，則有：

BPRB=2×編碼率×120 bit

(5)

由于LTE業(yè)務(wù)的多樣性，不同業(yè)務(wù)對(duì)QoS要求不同，尤其是在實(shí)現(xiàn)收費(fèi)業(yè)務(wù)后，即使是相同的業(yè)務(wù)，其用戶付費(fèi)高的享有的資源也理應(yīng)要多一些。但是傳統(tǒng)的PF調(diào)度算法并沒有考慮到諸如丟包率、時(shí)延、隊(duì)列吞吐量、公平性等因素對(duì)調(diào)度優(yōu)先級(jí)的影響，更沒有體現(xiàn)付費(fèi)優(yōu)先級(jí)的影響，因此對(duì)其進(jìn)行改進(jìn)為

(6)

式中，DC表示隊(duì)列平均時(shí)延，由文獻(xiàn)[3]所提出的Little公式得到，且：

(7)

式中，Q表示隊(duì)列狀態(tài)，E(Q)表示隊(duì)列狀態(tài)均值，γ表示業(yè)務(wù)的到達(dá)速率。

當(dāng)隊(duì)列到達(dá)的包長L加上隊(duì)列當(dāng)前狀態(tài)下的比特?cái)?shù)目Q超過最大隊(duì)列長度Qmax時(shí)就會(huì)發(fā)生丟包現(xiàn)象，而隊(duì)列包長服從參數(shù)為λ的指數(shù)分布，得到下式：

(8)

故可用

(9)

反映隊(duì)列的丟包率，其中Q表示隊(duì)列當(dāng)前狀態(tài)，Qmax表示隊(duì)列最大允許長度。

TRelative=Nd/Nb

(10)

表示調(diào)度時(shí)刻內(nèi)，隊(duì)列實(shí)際調(diào)度的比特?cái)?shù)目Nd與由式(2)計(jì)算所得的應(yīng)傳送的比特?cái)?shù)目Nb的比值，它表征了用戶的相對(duì)吞吐量，且TRelative∈[0,1]。

(11)

4 算法性能評(píng)價(jià)方法與算法切換系統(tǒng)的流程圖

為了更好地體現(xiàn)算法性能，本文通過隊(duì)列丟包率、隊(duì)列時(shí)延、相對(duì)平均吞吐量、公平性4項(xiàng)指標(biāo)來衡量該算法，并與傳統(tǒng)的PF算法進(jìn)行性能分析與比較。

隊(duì)列時(shí)延用式(7)所示的Little公式來進(jìn)行描述，隊(duì)列丟包率用式(8)進(jìn)行描述，用戶的平均相對(duì)吞吐量由式(10)表示，算法的公平性用Jain′s Fairness公式進(jìn)行描述：

(12)

式中，n表示具有相同付費(fèi)優(yōu)先級(jí)的隊(duì)列數(shù)目，xi表示隊(duì)列i本次調(diào)度的比特?cái)?shù)目，i表示隊(duì)列編號(hào)，且i所表示的各隊(duì)列必須具有相同的付費(fèi)優(yōu)先級(jí)，當(dāng)各隊(duì)列絕對(duì)公平時(shí)其值為1。

由于本文所提算法雖然能極大地提高付費(fèi)用戶相應(yīng)的QoS指標(biāo)，但是其余未付費(fèi)用戶的相應(yīng)指標(biāo)將會(huì)下降。因此，當(dāng)其余用戶的指標(biāo)超出該指標(biāo)的允許范圍時(shí)，系統(tǒng)必須立即被切換到不考慮付費(fèi)優(yōu)先級(jí)別的改進(jìn)型PF算法以保證所有用戶的最低QoS需求。另外，付費(fèi)優(yōu)先級(jí)用戶的QoS相應(yīng)指標(biāo)的提升幅度必須有一個(gè)參照，因此系統(tǒng)剛開始必須采用一段時(shí)間的改進(jìn)型PF算法，相應(yīng)的QoS參照指標(biāo)，并確定付費(fèi)用戶在相應(yīng)QoS指標(biāo)的提升量，再切換到本文所提算法；而當(dāng)所有付費(fèi)用戶的該QoS指標(biāo)提升幅度達(dá)到并超過一定限度后，系統(tǒng)將重新切換回不考慮付費(fèi)優(yōu)先級(jí)別的改進(jìn)型PF算法，以避免未付費(fèi)用戶QoS指標(biāo)下降過大。

由此可提出算法總體流程如圖1所示。其中，當(dāng)算法切換到論文所提算法后，每過一段時(shí)間長度仍需要重新進(jìn)行一次算法切換的判定，從而實(shí)現(xiàn)了兩種算法之間的切換。當(dāng)執(zhí)行改進(jìn)型的PF算法時(shí)，應(yīng)調(diào)整各參數(shù)的加權(quán)因子，以盡量使隊(duì)列之間的各項(xiàng)QoS指標(biāo)接近以得到付費(fèi)用戶的QoS提升參照標(biāo)準(zhǔn)，并且在調(diào)度過程中切換到改進(jìn)型的PF算法后也能使得各隊(duì)列的QoS指標(biāo)重新趨于一致，從而在資源非常匱乏的情況下也能使各隊(duì)列盡量同時(shí)達(dá)到最低QoS標(biāo)準(zhǔn)。當(dāng)執(zhí)行所提算法時(shí)，付費(fèi)用戶的優(yōu)先級(jí)參數(shù)S應(yīng)使得付費(fèi)用戶的調(diào)度優(yōu)先級(jí)高于沒有被調(diào)度的用戶，而各隊(duì)列的QoS參數(shù)加權(quán)因子應(yīng)選取合理以使得相同付費(fèi)優(yōu)先級(jí)內(nèi)的隊(duì)列QoS指標(biāo)達(dá)到要求。

圖1 算法流程圖Fig.1 Flowchart of the algorithm

5 算法性能仿真

仿真參數(shù)設(shè)定如表1所示。

表1 仿真各參數(shù)設(shè)定Table 1 Simulation parameter configuration

經(jīng)仿真得到新算法與傳統(tǒng)的PF調(diào)度算法比較如圖2～5所示，隊(duì)列1、2、3、4分別標(biāo)示于圖中，劃線與虛線分別代表本文所提算法與傳統(tǒng)的PF算法。

圖2表示兩種算法下的隊(duì)列平均丟包率。由圖可知，在傳統(tǒng)的PF算法中，隊(duì)列的丟包率隨著時(shí)間延長趨近于與其所獲得的信道質(zhì)量成正比，具有相同信道質(zhì)量的用戶在其包長相差不大時(shí)，丟包率也趨于相等。而在本文所提算法中具有優(yōu)先級(jí)的用戶丟包率明顯減小，但同時(shí)也增加了不具有用戶付費(fèi)優(yōu)先級(jí)用戶的丟包率，因此，必須調(diào)整調(diào)度算法中的各加權(quán)因子，使得各隊(duì)列的丟包率不能超過最大限制(否則系統(tǒng)將切換至不考慮用戶付費(fèi)優(yōu)先級(jí)的改進(jìn)型PF算法)。當(dāng)用戶丟包率超過用戶滿意條件下的最大丟包率后，系統(tǒng)將停止采用考慮用戶付費(fèi)優(yōu)先級(jí)的改進(jìn)型PF算法而只采用不考慮用戶付費(fèi)優(yōu)先級(jí)的改進(jìn)型PF算法，從而使得其余用戶的丟包率得以控制。圖3表示兩種算法下的隊(duì)列平均時(shí)延，本文所提算法具有優(yōu)先級(jí)的用戶時(shí)延明顯減小，但同時(shí)也增加了不具有用戶付費(fèi)優(yōu)先級(jí)用戶的時(shí)延。圖4表示隊(duì)列平均相對(duì)吞吐量TRelative，其計(jì)算如(12)式所示，由圖可知具有用戶付費(fèi)優(yōu)先級(jí)的隊(duì)列1和隊(duì)列3的TRelative得以極大提高，而不具有用戶付費(fèi)優(yōu)先級(jí)用戶的TRelative則相應(yīng)地減小，但也達(dá)到了最低需求。圖5表示隊(duì)列的平均公平性，本文所提出的算法將隊(duì)列按照付費(fèi)優(yōu)先級(jí)分為兩類，分別計(jì)算其公平性，由圖可知具有付費(fèi)優(yōu)先級(jí)的用戶公平性要遠(yuǎn)大于不具有付費(fèi)優(yōu)先級(jí)的用戶，而不具有付費(fèi)優(yōu)先級(jí)的用戶其公平性要略高于采用傳統(tǒng)PF算法的用戶。

圖2 隊(duì)列平均丟包率Fig.2 The average loss rate of the queue

圖3 隊(duì)列平均延遲Fig.3 The average delay of the queue

圖4 隊(duì)列平均相對(duì)吞吐量TRelativeFig.4 The average relative throughput TRelative of the queue

圖5 隊(duì)列平均公平性Fig.5 The average fairness of the queue

6 結(jié) 論

本文所提出的LTE基站端基于付費(fèi)QoS指標(biāo)的調(diào)度切換算法，不但能保證付費(fèi)用戶相應(yīng)業(yè)務(wù)的各項(xiàng)QoS質(zhì)量得以提高，而且所有用戶的QoS指標(biāo)也得以保證，可以更好地適應(yīng)LTE業(yè)務(wù)多樣性的特征。下一步的研究可以考慮進(jìn)各業(yè)務(wù)信道覆蓋差異的因素，以更加完善所提算法。

參考文獻(xiàn)：

[1] Nararat Ruangchaijatupon，Yusheng Ji.Simple Proportional Fairness Scheduling for OFDMA Frame-based Wireless Systems[C]// Proceedings of Wireless Communications & Networking Conferenc.Las Vegas:IEEE,2008:1593-1597.

[2] 錢耕之,任參軍，唐蘇文，等.基于多業(yè)務(wù)Qos的LTE下行資源分配算法[J].通信技術(shù),2010,43(4)：190-192.

QIAN Geng-zhi,REN Can-jun,TANG Su-wen,et al.Multi-service Qos-based Downlink Cross-layer Resource Block Allocation Algorithm in LTE system[J].Communications Technology,2010,43(4)：190-192.(in Chinese)

[3] 3GPP.TS.36.211 V9.0.0, 3GPP Technical Specification Group Radio Access Network;Evolved Universal Terrestrial Radio Access (E-UTRA);Physical Channels and Modulation[S].

[4] 3GPP.TS.36.212 V9.0.0, 3GPP Technical Speci fication Group Radio Access Network;Evolved Universal Terrestrial Radio Access (E-UTRA);Multiplexing and channel coding[S].

[5] 趙訓(xùn)威,林輝,張明，等.3GPP長期演進(jìn)(LTE)系統(tǒng)架構(gòu)與技術(shù)規(guī)范[M].北京：人民郵電出版社，2010.

ZHAO Xun-wei,LIN Hui,ZHANG Ming,et al.3GPP Long Term Evolution (LTE) System Architecture and Technical Specifications[M].Beijing:People′s Posts & Telecommunications Press,2010.(in Chinese)

[6] 盛友招.排隊(duì)論及其在現(xiàn)代通信中的應(yīng)用[M].北京：人民郵電出版社，2007.

SHENG You-zhao.Queuing theory and its application in modern communication[M].Beijing:People′s Posts & Telecommunications Press,2007.(in Chinese)