戴翠琴, 王 亮, 王海寶
重慶郵電大學移動通信技術(shù)重慶市重點實驗室,重慶400065
隨著無線用戶和多媒體業(yè)務(wù)的急劇增加,無線通信系統(tǒng)對時間、空間、頻譜和功率等資源的高效利用提出了更高要求.合理有效的資源調(diào)度技術(shù)不僅能夠提升小區(qū)邊緣性能和系統(tǒng)吞吐量,還能更好地滿足用戶服務(wù)質(zhì)量(quality of service,QoS)、公平性等方面的需求.因此,新一代寬帶無線通信中的資源調(diào)度技術(shù)受到研究者的廣泛關(guān)注,被視為提高無線系統(tǒng)性能的關(guān)鍵技術(shù)之一.
在正交頻分復用(orthogonal frequency division multiple,OFDM)中繼系統(tǒng)中,中繼作為一種空間分集技術(shù)可以顯著增加網(wǎng)絡(luò)覆蓋范圍,還能進一步提高系統(tǒng)吞吐量,極大地提高了無線資源的利用率.因此,為了更合理而有效地利用系統(tǒng)資源,基于OFDM中繼系統(tǒng)的資源調(diào)度算法成為近年來的研究熱點.文獻[1]在傳統(tǒng)比例公平(proportional fair,PF)算法的基礎(chǔ)上加入了速率比值因子,提出了兩跳比例公平(two hop proportional fair,THPF)算法,并應(yīng)用于OFDM中繼系統(tǒng),在一定程度上提升了用戶的公平性,卻不能充分保證用戶的吞吐性能.文獻[2]針對OFDM中繼系統(tǒng)提出了一種基于目標用戶功率的調(diào)度算法,解決了系統(tǒng)吞吐性能問題,但該算法是一個廣義層次上的調(diào)度,并沒有區(qū)分兩個時隙的調(diào)度.文獻[3]對文獻[2]的算法進行改進,在調(diào)度的兩個時隙中通過路由選擇獲得最佳用戶并為其分配資源,大大提高了資源利用率,解決了文獻[2]中未區(qū)分時隙進行調(diào)度的問題.文獻[1-3]提出的調(diào)度算法在一定程度上改進了中繼系統(tǒng)性能,但均為針對實時業(yè)務(wù)的調(diào)度算法,并沒有考慮到非實時業(yè)務(wù)的調(diào)度問題.文獻[4]針對非實時業(yè)務(wù)進行研究,提出了最大加權(quán)時延優(yōu)先(largest wait delay first,LWDF)算法,雖然提升了非實時業(yè)務(wù)的系統(tǒng)吞吐量,但不能保證非實時業(yè)務(wù)的丟包率和時延要求.文獻[5]針對非實時業(yè)務(wù)中的丟包問題,提出了基于隊列長度的混合調(diào)度算法,在一定程度上改善了調(diào)度過程中的丟包問題.基于文獻[5]的研究,文獻[6]提出了一種優(yōu)化算法,不僅將丟包率控制在一定的范圍內(nèi),而且提高了非實時業(yè)務(wù)的時延特性.分析上述文獻可知,目前已有的OFDM中繼系統(tǒng)的資源調(diào)度算法主要針對單一類型的業(yè)務(wù)進行調(diào)度,并未解決如何更有效地應(yīng)對混合業(yè)務(wù)的調(diào)度問題.
隨著寬帶無線通信系統(tǒng)的發(fā)展,通信業(yè)務(wù)由單一型向混合型過渡,于是用戶QoS要求成為衡量通信質(zhì)量的一個很重要的性能指標.混合型業(yè)務(wù)可以分為實時業(yè)務(wù)和非實時業(yè)務(wù),實時業(yè)務(wù)的用戶QoS要求主要表現(xiàn)為用戶對速率的要求,非實時業(yè)務(wù)的用戶QoS要求主要表現(xiàn)為用戶對丟包率和時延特性的要求.因此,如何在混合業(yè)務(wù)中采用合理的調(diào)度算法的同時保證用戶QoS要求的問題變得十分重要,目前已有相關(guān)文獻對混合業(yè)務(wù)的資源調(diào)度問題進行了研究.文獻[7-8]較早地在OFDM中繼系統(tǒng)中提出了區(qū)分混合業(yè)務(wù)的調(diào)度算法,為后續(xù)研究奠定了理論基礎(chǔ).文獻[9]提出了一種在混合業(yè)務(wù)下基于效用函數(shù)的調(diào)度算法,提升了系統(tǒng)調(diào)度性能,但在兩個時隙中要采用統(tǒng)一的調(diào)度方式,使系統(tǒng)的資源能得以充分利用.基于文獻[9]的研究,文獻[10]提出了分步跨層調(diào)度算法,不僅在兩個時隙中采用了不同的調(diào)度策略,而且對混合業(yè)務(wù)區(qū)分調(diào)度,為不同業(yè)務(wù)提供了合理的資源利用.文獻[11]針對混合型業(yè)務(wù)的調(diào)度提出了一種時域自適應(yīng)的調(diào)度(adaptive time domain scheduling algorithm,ATDSA)算法,在區(qū)分混合業(yè)務(wù)的同時能充分利用資源,提升系統(tǒng)的公平性和吞吐量.以上研究僅針對混合業(yè)務(wù)進行區(qū)分調(diào)度,但都沒有考慮到如何保證混合業(yè)務(wù)用戶的QoS要求.
為了對混合業(yè)務(wù)進行區(qū)分調(diào)度的同時保證用戶QoS要求,本文在OFDM中繼系統(tǒng)中提出相對最長隊列優(yōu)先/相對比例公平(relative largest queue aware first/relative proportional fair,R-LQAF/RPF)的調(diào)度算法.相比于傳統(tǒng)PF和LWDF算法,R-LQAF/RPF算法既能區(qū)分調(diào)度混合型業(yè)務(wù)(對實時型業(yè)務(wù)采用RPF算法保證了用戶對速率的要求,對非實時業(yè)務(wù)采用R-LQAF算法減少了用戶的丟包率),又能充分保證混合業(yè)務(wù)的QoS要求.
單個小區(qū)的系統(tǒng)模型如圖1所示[12],圖中有一個基站(base station,BS)、K(文中的K取6)個固定的中繼節(jié)點(relay station,RS)和M個用戶(mobile station,MS),MS隨機地分布在小區(qū)內(nèi),調(diào)度時采用集中式調(diào)度模型,即資源的調(diào)度統(tǒng)一由BS管理,RS不具有調(diào)度的功能.假設(shè)BS到六邊形頂點的距離為R,每個RS位于BS和六邊形頂點的連線上,且與基站的距離為2R/3.如圖1所示,小區(qū)分為七部分,最中間的部分為直傳用戶分布的區(qū)域,剩下的六個形狀相同的區(qū)域是以六邊形的每個頂點為圓心,以2R/3為半徑的圓交織組成.這六個區(qū)域為中繼用戶分布的區(qū)域,每個區(qū)域內(nèi)均有一個RS采用解碼轉(zhuǎn)發(fā)(decoding forward,DF)方式為分布在其覆蓋區(qū)域內(nèi)的MS提供服務(wù).RS采用時分雙工(time division duplexing,TDD)模式,每個時隙分為兩個子時隙.對于直傳用戶,由BS在第1時隙直接給其分配資源;對于中繼用戶,BS第1時隙給RS分配資源,第2時隙再由RS轉(zhuǎn)發(fā)相應(yīng)的資源到相應(yīng)的MS.
圖1 系統(tǒng)模型Figure 1 System model
系統(tǒng)中的調(diào)度機制不考慮協(xié)作傳輸,故最大的鏈路數(shù)為L=M+K.假設(shè)系統(tǒng)總帶寬為B,系統(tǒng)中有N個子載波,則每個子載波的帶寬為B/N[13];直傳用戶M和中繼節(jié)點K在子信道N上的信道增益分別為、,通過中繼K傳輸?shù)闹欣^用戶M在子信道N上的增益為;和ρn分別表示中繼和基站在子信道N上的發(fā)送功率;dm,n、dm,k,n、dk,n分別表示直傳用戶、中繼用戶、中繼子信道的分配標示,若dm,n=1,則表示子信N分配給用戶M,若dm,n=0,則表示用戶沒有得到分配,標示dm,k,n、dk,n的取值與之類似;?!?ln(5BER)/1.6,系統(tǒng)加性高斯白噪聲為w=N0B/N,其中N0為噪聲功率譜密度.
直傳用戶M在時隙t內(nèi)的速率為
中繼節(jié)點K在時隙t內(nèi)第1子時隙的速率為
中繼用戶M在時隙t內(nèi)第2子時隙的速率為
在實際的無線通信系統(tǒng)中,兩跳鏈路的傳輸速率等于兩跳鏈路容量的最小值,則中繼用戶M的實際速率為
在OFDM系統(tǒng)中,無線資源是一個時域和頻域?qū)?yīng)的二維塊狀結(jié)構(gòu).在時域方面,無線資源劃分為多個時隙;在頻域方面,無線資源劃分為多個子信道,每個子信道由多個子載波組成.在多用戶OFDM系統(tǒng)中,一個時隙中的子信道是一個最小資源劃分單位,被稱為資源塊(resource block,RB)[14].文中的算法即實現(xiàn)對不同用戶合理的分配RB.
混合業(yè)務(wù)的場景設(shè)定如下:實時業(yè)務(wù)(real time,RT)分組和非實時業(yè)務(wù)(non-real time,NRT)分組按照1:1的比例組成混合業(yè)務(wù),實時業(yè)務(wù)最大允許時延服從5~10ms的均勻分布,非實時業(yè)務(wù)的最大允許時延服從10~20ms的均勻分布.
調(diào)度模型圖如圖2所示.首先,系統(tǒng)以10ms為界限將混合業(yè)務(wù)分為實時和非實時業(yè)務(wù),然后將不同類型的業(yè)務(wù)送入調(diào)度器,針對不同的業(yè)務(wù)采取不同的調(diào)度算法并為其分配RB.調(diào)度算法根據(jù)用戶位置判斷用戶的類型,若為直傳用戶,基站通過無線信道發(fā)送對應(yīng)的信號;若為中繼用戶,基站首先發(fā)送信號給中繼,中繼接收到信號后立刻轉(zhuǎn)發(fā)給中繼用戶.用戶接收到信號后,將信道狀態(tài)信息反饋給基站,基站接收到用戶的反饋信號后進行資源再次分配.
圖2 調(diào)度模型圖Figur e 2 Scheduling model
文獻[1]提到目前針對實時業(yè)務(wù)應(yīng)用較多的PF算法,其調(diào)度準則的表達式為
式中,ji表示算法最終選擇的用戶,ri(t)表示t時刻第i個用戶的實際速率,表示t時刻用戶i的平均傳輸速率,的更新如式(6)所示,其中T表示窗口長度
文獻[4]針對非實時業(yè)務(wù)提出了LWDF算法,其調(diào)度優(yōu)先級表達式為
式中,ai=-lgδi/τi為與非實時業(yè)務(wù)QoS要求相關(guān)的優(yōu)先級因子,其中τi為用戶i能容忍的最大分組時延,δi為可容忍的超出最大時延的分組比例上限;ri,k(t)表示t時刻第i個用戶在子載波k上的實際速率,表示t時刻用戶i的平均傳輸速率,Wi(t)為用戶i在t時刻緩沖區(qū)的隊頭時延.最終選擇的用戶可表示為
針對實時業(yè)務(wù)的用戶,用戶的實時速率是用戶QoS的重要指標,PF算法不能充分滿足用戶的實時速率的要求;針對非實時業(yè)務(wù),丟包率是一個很重要的衡量用戶QOS的標準,LWDF算法雖能在一定程度上提高系統(tǒng)的時延性能,但系統(tǒng)的丟包率相對較差.針對以上問題,文中引入了R-LQAF/RPF算法,其優(yōu)點是不僅能針對混合業(yè)務(wù)進行調(diào)度,而且能較好地滿足混合業(yè)務(wù)QoS要求.
R-LQAF/RPF算法的優(yōu)先權(quán)表達式為
式中,F(xiàn)(x)的表達式為ζi的表達式為ψi的表達式為
則最終的調(diào)度目標可表示為
如式(9)所示,R-LQAF/RPF調(diào)度算法針對不同業(yè)務(wù)采取不同的調(diào)度算法,可以區(qū)分混合業(yè)務(wù).R-LQAF/RPF算法引入了相對變化函數(shù)F(x),其中ri,k(t)、ai、與式(7)中的定義相同,α為可調(diào)優(yōu)先級因子,Qi(t)表示用戶i在t時刻用戶隊列的長度.式(10)中的ε、φ是決定曲線變化的參數(shù),通過改變ε的值能改變函數(shù)縱向的變化尺度,通過改變φ的值可以改變曲線的變化急緩程度.F(x)函數(shù)的部分截圖如圖3所示,其中ε=1,φ=0.3,x∈[0,3].當x=1時,F(xiàn)(x)的值為1;當x∈[0,1]時,F(xiàn)(x)為單調(diào)遞增凸函數(shù);當x∈[1,+∞)時,F(xiàn)(x)為單調(diào)遞增凹函數(shù).
圖3 函數(shù)F(x)的曲線圖Figure 3 Curve of function F(x)
對非實時業(yè)務(wù)而言,式(9)引入了相對變化函數(shù)F(ψi),ψi為變化因子,其表達式見式(12).由ψi的表達式可知ψi>0,其中Qi(t)、ri,k(t)與式(9)中的定義相同,Tht為系統(tǒng)中時延門限.如果Qi(t)>ri,k(t)Tht,則表示時刻t用戶i的隊列長度已經(jīng)超過了系統(tǒng)此時所能處理的隊列長度,此時系統(tǒng)通過函數(shù)F(ψi)函數(shù)特性增加非實時業(yè)務(wù)用戶調(diào)度的優(yōu)先級,反之可降低其優(yōu)先級.
系統(tǒng)中每個調(diào)度周期分兩個階段(即兩個子時隙)進行,資源先分配給第2個時隙,再分給第1個時隙.
第1階段 第2時隙的資源分配
步驟1 根據(jù)系統(tǒng)模型,首先判斷單個小區(qū)內(nèi)的用戶是中繼用戶還是直傳用戶,選擇其中的中繼用戶,記作用戶集合K={1,2,3,···,k1,···,k2},初始化系統(tǒng)的資源塊(RB),記作N={1,2,3,···,n}.
步驟2 根據(jù)業(yè)務(wù)的時延特性,以10ms為界限將混合業(yè)務(wù)分為實時業(yè)務(wù)和非實時業(yè)務(wù),根據(jù)式(9)對實時業(yè)務(wù)用戶采取RPF調(diào)度算法;根據(jù)RPF算法計算出其優(yōu)先級較大的用戶k1,給用戶k1分配一個RB,對非實時業(yè)務(wù)采取R-LQAF算法;根據(jù)R-LQAF算法計算出其優(yōu)先級較大的用戶k2,給用戶k2分配一個RB.
步驟3 將已經(jīng)分配的RB從資源塊集合N中清除,同時從用戶集合中清除已分配的用戶.
步驟4 更新資源塊N和用戶集合K,然后轉(zhuǎn)向步驟2,直到每個用戶都被分配RB.
第2階段 第1時隙的資源分配
采用SPSS19.0的統(tǒng)計學軟件對數(shù)據(jù)進行分析處理,計量資料以均數(shù)±標準差(±s)表示,采用t檢驗,計數(shù)資料以率(%)表示,采用χ2檢驗,P<0.05為差異有統(tǒng)計學意義。
步驟1 根據(jù)小區(qū)模型,判斷在單個小區(qū)內(nèi)的用戶是中繼用戶還是直傳用戶,選擇其中的中繼和直傳用戶,分別記為R={1,2,3,···,r}和M={1,2,3,···,m1,···,m2}.
步驟2 針對中繼用戶,首先給小區(qū)內(nèi)每個中繼分配RB并計算中繼第1時隙和第2時隙的容量.
步驟3 比較中繼第1時隙和第2時隙的容量,如果中繼第1時隙的容量比第2時隙小,則繼續(xù)給中繼用戶分配RB,直到中繼的第1時隙的容量大于第2時隙的容量.
步驟4 根據(jù)業(yè)務(wù)的時延特性,以10ms為界限將混合業(yè)務(wù)分為實時業(yè)務(wù)和非實時業(yè)務(wù),根據(jù)式(9)對實時業(yè)務(wù)用戶采取RPF調(diào)度算法;根據(jù)RPF算法計算出其優(yōu)先級較大的用戶m1,給用戶m1分配一個RB;對非實時業(yè)務(wù)采取R-LQAF算法;根據(jù)RLQAF算法計算出其優(yōu)先級較大的用戶m2,給用戶m2分配一個RB.
步驟5 將已經(jīng)分配的RB從資源塊集合N中清除,并將已分配資源的用戶從集合M中清除.
步驟6 如果第1時隙有多余的RB,則將剩下的RB全部分給直傳用戶;如果第1時隙的RB不足,可將任意一個分配給中繼用戶的RB分配給直傳用戶.
步驟7 返回步驟1,準備下一次調(diào)度.
下面通過MATLAB進行了數(shù)值仿真分析,驗證上述推導和算法分析.假設(shè)在單個小區(qū)模型內(nèi),用戶數(shù)目為50個,隨機分布在小區(qū)內(nèi),設(shè)置小區(qū)的半徑為600m,基站和中繼的發(fā)射功率分別為36d Bm和18d Bm,調(diào)度資源數(shù)目為10個RB,載波數(shù)量為128,即子信道的數(shù)目為128,調(diào)度周期為t= 5×10-3s,子信道帶寬為120kHz,噪聲功率譜密度為-174d Bm/Hz.仿真模型采用六徑瑞利衰落模型,每條路徑中采用Clarke平坦衰落模型[15].數(shù)據(jù)包采用泊松模型,數(shù)據(jù)包到達速率為104bit/s,隊列中的數(shù)據(jù)包采用先進先出的方式,時延門限為50ms.若數(shù)據(jù)包等待時間超過50ms.則會產(chǎn)生丟包.
針對實時業(yè)務(wù),為滿足其QoS要求,須對用戶速率的要求達到一定滿意程度,才能保證用戶的實時性.圖4比較了PF算法、RPF算法以及文獻[1]提到的THPF算法的用戶速率需求滿意度.由圖4可以看出,PF算法不能很好地區(qū)分第1時隙和第2時隙的資源分配,因此PF算法對用戶速率的滿意度不如THPF算法;同時,THPF算法和PF算法的用戶速率需求滿意度明顯低于RPF算法,這是因為THPF和PF算法沒有考慮用戶需求速率,而RPF算法由于加入了對用戶需求速率的考慮,對用戶的速率需求滿意度大大增加.
圖5描述了THPF算法、PF算法和RPF算法的吞吐性能.如圖5所示,PF算法在每次調(diào)度過程中將最好的信道資源分配給速率較大的直傳用戶和中繼用戶,故PF算法具有最好的吞吐性能;THPF算法兼顧第1時隙和第2時隙的對用戶速率需求滿意度性能的把握,其吞吐量有所下降;RPF算法忽略了用戶吞吐性能,但保證了用戶實際速率的需求,從而充分保證實時業(yè)務(wù)對實時速率的要求.
針對非實時業(yè)務(wù),要盡量使用戶丟包率降到最最小,才能保證非實時業(yè)務(wù)QoS指標.圖6對比了LWDF算法和R-LQAF算法的丟包率.從圖6中可以看出,R-LQAF算法的丟包率明顯低于LWDF算法的丟包率.因為在R-LQAF算法中加入了相對變化函數(shù),如果某用戶隊列的實際長度大于系統(tǒng)中此時刻所能處理的隊列長度,則增加此用戶的優(yōu)先級,否則就降低該用戶的調(diào)度優(yōu)先級,相對變化函數(shù)的加入大大減少了系統(tǒng)丟包率.
圖4 實時業(yè)務(wù)用戶速率需求滿意度的比較Figure 4 Comparison of real-time business users'satisfaction of demanded rate
圖5實時業(yè)務(wù)用戶系統(tǒng)吞吐量的比較Figure 5 Comparison of real-time business system throughput
圖7 比較了LWDF算法和R-LQAF算法的吞吐性能,可以看出R-LQAF算法的吞吐量性能明顯優(yōu)于LWDF算法的吞吐量性能.因為R-LQAF算法相比LWDF算法丟包率較低,系統(tǒng)在單個調(diào)度周期內(nèi)包裹丟失的數(shù)量較少,系統(tǒng)中存在的包裹總數(shù)較多,所以采用R-LQAF算法使得系統(tǒng)吞吐量相對較大.
圖6 非實時業(yè)務(wù)用戶丟包率的比較Figure 6 Comparison of non-real-time business users'packet loss rate
圖7 非實時業(yè)務(wù)用戶系統(tǒng)吞吐量的比較Figure 7 Comparison of non-real-time business system throughput
基于OFDM中繼系統(tǒng),研究了如何保證混合業(yè)務(wù)中用戶QoS要求的問題.通過建立OFDM中繼協(xié)作系統(tǒng)模型,采用Clarke平坦衰落模型模擬了系統(tǒng)中的各個信道,推導了系統(tǒng)信道容量的表達式,提出了R-LQAF/RPF算法.仿真結(jié)果表明,通過分析比較非實時用戶實際隊列長度和系統(tǒng)所能處理的隊列長度,采用R-LQAF算法可以進一步降低系統(tǒng)丟包率;結(jié)合實時用戶需求速率,采用RPF算法可使系統(tǒng)最大程度地滿足實時業(yè)務(wù)用戶對速率需求.所提出的R-LQAF/RPF算法在有效分配資源的同時,能夠更好地保障混合業(yè)務(wù)下不同用戶QoS要求.
[1]LINX,CUTHBERT L.A twohop proportional fairness scheduling algorithm for relay based OFDMA systems[C]//WiCO-M'08.4 International Conference on Wireless Communications,Beijing:2008:165-168.
[2]BYUNG G K,JANG W L.Joint opportunistic subchannel and power scheduling for relay-based OFDMA networks with scheduling at relay stations[J].IEEE Transactions on Vehicular Technology,2010,59(5):2138-2148.
[3]NG D W K,SCHOBER R.Resource allocation and scheduling in multicell OFDMA systems with decode and forward relaying[J].IEEE Transactions on Wireless Communications,2011,10(7):2246-2258.
[4]ANDREw SM,KUMARANK,RAMANAN K.Providing quality of serviceover a shared wireless link[J].IEEE Communications Magazine,2001,39(2):150-154.
[5]KAE W C,WHA S J,DONG G J.Resource allocation in OFDMA wireless communications systems supporting multimedia services[J].IEEE/ACM on Networking,2009,17(3):926-935.
[6]CHANDUR P,KARTHIK R M.Performance evaluation of scheduling algorithms for mobile WiMAX networks[C]//2012 IEEE International Conference on Pervasive Computing and Communications Workshops,India:2012:764-769.
[7]SEUNGwAN R,BYUNGHAN R,HYUNHwA S.Urgency and efficiency based packet scheduling algorithm for OFDMA wireless system[C]//2005 IEEE International Conference on Com Munications,Korea,2005:2779-2785.
[8]RUI Z,HOANG N N,SASASE I.Packet scheduling for cellular networks with relaying to support user QoS and fairness[C]//IEEE Wireless Communications and Networking Conference(WCNC).Kowloon:2007:3896-3900.
[9]CHIY H,AIC P.3-approximation algorithm for joint routing and link scheduling in wireless relay networks[J].IEEE Transactions on Wireless Communications,2009,8(2):856-861.
[10]韓智,郭愛煌.中繼OFDMA系統(tǒng)混合業(yè)務(wù)的分步跨層調(diào)度算法[J].計算機應(yīng)用研究,2011(7):36-39.HAN Zhi,GUO Aihuang.Step-by-step cross-layer scheduling algorithm for mixed services in relay OFDMA system[J].Application Research of Computers,2011(7):36-39.(in Chinese)
[11]KAUSAR R,CHENY,CHAI K K.Adaptive time domain scheduling algorithm for OFDMA based LTEadvanced networks[C]//2011 IEEE 7th International Conference on Wireless and Mobile Computing,2011:476-482.
[12]HUINING H,Performance analysis of cellular networks with digital f ixed relays[D].Canada:Carleton University,2003:20-40.
[13]RUIW,CUIY.Decentralized fair scheduling in twohop relay-assisted cognitive OFDMA systems[J].IEEE Journal of Selected Topics in Signal Processing,2011,5(1):171-181.
[14]FOUAD Y M M.An autonomous resource block assignment scheme for OFDMA-based relay-assisted cellular networks[J].IEEE Transactions on Wireless Communications,2012,11(2):637-647.
[15]DANHUAZ.Dynamic resourceallocation for real-time services in cooperative OFDMA systems[J].IEEE Communications Letters,2011,15(5):497-499.