李彬,鄧華陽
摘 要:隨著移動通信技術(shù)的飛速發(fā)展, 未來的移動通信系統(tǒng)將以數(shù)據(jù)業(yè)務(wù)為主,所以無線分組調(diào)度算法將成為影響系統(tǒng)性能和保證用戶服務(wù)質(zhì)量的關(guān)鍵所在。在HSDPA系統(tǒng)中無線資源管理是通過分組調(diào)度算法來實現(xiàn)的。理想的調(diào)度算法應(yīng)滿足各類業(yè)務(wù)的QoS要求和用戶之間的公平性,使系統(tǒng)資源利用率達到最大。主要介紹了EXP算法和M-LWDF算法,并對兩種算法在吞吐量方面進行了仿真分析,說明了M-LWDF算法具有更高的吞吐量。
關(guān)鍵詞:HSDPA; M-LWDF算法; EXP算法; 吞吐量
中圖分類號:TN911-34
文獻標識碼:A
文章編號:1004-373X(2011)09-0042-03
Throughput Simulation of Real-time Service Scheduling Algorithm in HSDPA
LI Bin, DENG Hua-yang
(Chongqing Chongyou Information Technology Design Co. Ltd., Chongqing University of Posts and Telecommunications,
Chongqing 400065, China)
Abstract: With the rapid development of the mobile communication technology, the mobile communication system will be based on data services in the future. Therefore, the wireless packet scheduling algorithm is the key of improving system performance and quality of customer service. In the HSDPA system, radio resource management is achieved through packet scheduling algorithm. An ideal scheduling algorithm should meet QoS requirements of various business and fairness among users to maximize utilization of system resources. The EXP algorithm and M-LWDF algorithm are introduced in this paper. In the aspect of throughput, the simulation analysis of both algorithms was conducted. It shows that M-LWDF algorithm has higher throughput.
Keywords: HSDPA; M-LWDF algorithm; EXP algorithm; throughput
0 引 言
隨著移動通信技術(shù)的飛速發(fā)展,移動用戶急劇增加,通信系統(tǒng)容量不斷加大,所支持的業(yè)務(wù)類型除了傳統(tǒng)的語音業(yè)務(wù)外,還包括低/高速數(shù)據(jù)、圖像等數(shù)據(jù)業(yè)務(wù)。不同的業(yè)務(wù)具有不同的服務(wù)質(zhì)量(QoS)要求,如對分組時延、丟包率、數(shù)據(jù)速率的要求都各不相同。無線網(wǎng)絡(luò)設(shè)計有三大目標:一是保證各類業(yè)務(wù)的QoS要求;二是保證用戶之間的公平性;三是使系統(tǒng)的資源利用率達到最大。這都需要借助于無線資源管理來完成。未來的移動通信系統(tǒng)以數(shù)據(jù)業(yè)務(wù)為主,所以無線分組調(diào)度算法將成為影響系統(tǒng)性能和保證用戶服務(wù)質(zhì)量的關(guān)鍵。
1 實時業(yè)務(wù)調(diào)度算法的基本要求
HSDPA中實時數(shù)據(jù)業(yè)務(wù)的QoS可以采用兩種方式定義[1-3]。
一種是對傳輸時延進行限制。傳輸時延參數(shù)用來保證流業(yè)務(wù)分組的時間波動,為了限制最大時間波動,3GPP規(guī)定了傳輸時延要求,也就是所有分組時延的一定比例要小于傳輸時延要求,用公式表示如下:
Pr{Wi>Ti}≤ξi
(1)
即用戶所接收分組的時延Wi大于門限Ti的概率應(yīng)小于門限ξi。在UE側(cè)存在去抖動緩沖器,其用來彌補端到端的時延抖動。由于用戶希望較短的時間流業(yè)務(wù)的連續(xù)播放以及緩沖器存儲空間大小的限制,去抖動緩沖器中出現(xiàn)斷續(xù),影響用戶感受。因此除了用去抖動緩沖器來彌補時延,還要求Node B盡量降低用戶的時延抖動,在Node B側(cè)盡量降低用戶的時延抖動,這就需要通過分組調(diào)度來實現(xiàn)。因此,HSDPA實時調(diào)度算法的基本要求之一就是保證用戶的傳輸時延要求。這是在統(tǒng)計意義上對分組時延進行限制。
另一種QoS定義方式是對保證比特速率進行限制。保證比特速率是用來保證流業(yè)務(wù)的傳輸速率的波動。同樣3GPP也規(guī)定了保證比特速率要求,用公式表示如下:
Ri≥GBRi
(2)
式中:Ri表示第i個用戶的比特速率;GBRi表示第i個用戶的保證比特速率,這兩個速率都是應(yīng)用層的。這意味著應(yīng)用層的速率要大于應(yīng)用層的保證速率,但不一定要過大,過多超過保證比特速率是沒有必要的。 實時業(yè)務(wù)的傳輸速率保證也要在Node B調(diào)度執(zhí)行,因此,HSDPA實時業(yè)務(wù)調(diào)度算法的另一個基本要求就是保證用戶的傳輸速率。這是在統(tǒng)計意義上對傳輸速率進行限制。
假設(shè)在給定小區(qū)內(nèi),有一組流業(yè)務(wù)用戶集{i},i=1,2,…,N。對每一個用戶i,其相關(guān)的數(shù)據(jù)流為由遠端服務(wù)器傳來的M個分組流{p琲j},j=1,2,…,M,隨后這些分組流將被送到終端進行解碼。在經(jīng)過無線接入網(wǎng)時,分組{p琲j}在網(wǎng)絡(luò)中會經(jīng)歷延時。因此HSDPA的大部分功能在基站實現(xiàn)。分組流經(jīng)過Iub流量控制功能實體由無線網(wǎng)絡(luò)控制器傳到基站后進入基站的一系列{Qj}隊列中。為了限制分組{p琲j}的最大隊列長度,每個分組從到達基站開始就會被設(shè)置一個時間標簽,當(dāng)分組等待時間超過時間標簽設(shè)置的時間期限后,分組被丟掉。分組在基站的隊列中等待,之后或者通過HS-DSCH信道成功地傳送出去,或者等待時間超過時間標簽設(shè)置的時間期限則被丟棄。分組的丟棄條件為:
d琲j≥Ti
(3)
式中:d琲j表示在隊列中的等待時間;Ti代表用戶i的丟棄時間期限。對于不同的業(yè)務(wù)類型,分組被丟的時間期限不同。通常,實時業(yè)務(wù)的丟棄時間會較短,而非實時業(yè)務(wù)的丟棄時間會很長。
在HSDPA中,分組調(diào)度功能包括每個小區(qū)中用戶的無線資源的分配。因此,調(diào)度器不僅對小區(qū)性能有直接影響,而且對終端用戶也有影響,如傳輸時延和接收比特率,這兩個參數(shù)最終決定了終端用戶接收到的QoS水平。
假設(shè)用戶集{i}的時變信道的瞬時特性服從統(tǒng)計規(guī)律:
{Ri[n]},i=1,2,…,N
(4)
假設(shè)式(4)中沒有碼字復(fù)用,即在一個TTI內(nèi)所有的功率和資源全部分給了一個用戶。
在上述假設(shè)條件下,HSDPA中分組調(diào)度器的任務(wù)就簡化為在每一個TTI選擇被服務(wù)的用戶。給定小區(qū)的用戶集i=1,2,…,N,定義分組調(diào)度器的目標是最大化小區(qū)吞吐量,同時滿足用戶的QoS要求。
HSDPA系統(tǒng)中針對實時業(yè)務(wù)無線分組調(diào)度算法,提出了EXP算法和M-LWDF算法。這兩個調(diào)度算法的基本要求就是要滿足兩個QoS要求:傳輸時延和保證比特速率。因此,理論上基于QoS的HSDPA調(diào)度算法可以用于流業(yè)務(wù)。
2 支持實時業(yè)務(wù)的調(diào)度算法
2.1 M-LWDF算法
M-LWDF(Modified Largest Weighted Delay First)[4-6]是針對高速業(yè)務(wù)流而提出的。主要思想是將分組數(shù)據(jù)包的時延和如何利用信道信息平衡考慮,其用戶優(yōu)先級的計算不僅和用戶當(dāng)前的信道質(zhì)量有關(guān),還和包的隊列延時有關(guān)。M-LWDF算法的用戶優(yōu)先級定義為:
Pi[n]=-log(δi)?Ri[n]λi[n]?Di[n]Ti
(5)
式中:Pi[n]代表用戶i在第n個TTI的優(yōu)先級;Ri是每個TTI所支持的最大用戶數(shù)據(jù)速率;λi是用戶平均吞吐量的估計,仿真中按照式(5)計算,時間窗口長度為1000 TTI;Di代表用戶i的HOL分組延時;Di[n]定義為第n個TTI隊列的HOL分組的隊列延時;Ti是用戶i在隊列中等待的時延限制;δi是QoS參數(shù),用來區(qū)別不同QoS優(yōu)先級的用戶。
可以這樣理解式(5),用戶的優(yōu)先級首先是與它的QoS參數(shù)有關(guān),不同類型的業(yè)務(wù)對應(yīng)不同的傳輸?shù)燃墸瑢?yīng)不同的QoS參數(shù)。QoS要求越高,傳輸優(yōu)先級就越高。Ri反映了用戶瞬時信道狀況,信道條件越好,所支持的最大傳輸數(shù)據(jù)速率就越高;基于小區(qū)吞吐量最大化的原則,信道條件越好,其傳輸優(yōu)先級就越高。λi作為用戶平均吞吐量的估計,與傳輸優(yōu)先級成反比,考慮用戶的公平性,當(dāng)信道條件總是很好時,一些用戶就有可能連續(xù)得到服務(wù),使得其他信道條件差的用戶會出現(xiàn)“餓死現(xiàn)象”,為了照顧其他用戶的服務(wù)要求,就必須要降低該用戶的傳輸優(yōu)先級,使得其他用戶可以得到服務(wù)。同時該算法還考慮到了隊列時延,分組在隊列中等待的時間越久,其傳輸優(yōu)先級就越高,這也是考慮到了有的用戶可能會一直得不到服務(wù),其分組在隊列中的等待時間就會很長,而一旦超過了時延門限,該分組就會被丟棄。所以,考慮分組等待時間不超過時延門限,就必須增大等待時間久的分組的優(yōu)先級。Ti為用戶分組在隊列中的時延限制,當(dāng)分組等待時間超過該時延限制,就會在基站隊列中被丟棄。因此,時延限制越大,被丟棄的概率就越小,其傳輸優(yōu)先級就越小。
2.2 EXP算法
在M-LWDF算法之后,朗訊實驗室又提出了EXP算法,該算法是基于公平比調(diào)度和指數(shù)加權(quán)的時延平衡機制的,其調(diào)度優(yōu)先級公式如下:
j=maxi aiμi(t)μi(t)exp
aiWi(t)-aW1+aW
(6)
aW=1N∑Ni=1aiWi(t)
(7)
式中:μi(t)代表用戶i在時刻t信道所支持的瞬時數(shù)據(jù)傳輸速率;μi(t)為信道支持的平均數(shù)據(jù)速率;Wi(t)是用戶i在基站緩沖隊列HOL分組延時;ai>0,i=1,2,…,N,代表QoS級別,ai=-log(δi)/Ti,Ti 代表用戶i時延門限,δi 是時延得不到滿足的最大概率。
EXP算法和M-LWDF算法本質(zhì)上相似,都利用了實時業(yè)務(wù)的時延約束和多用戶分集增益來優(yōu)化系統(tǒng)容量。不同的是,EXP算法對基站緩沖隊列的HOL分組延時做了指數(shù)處理,當(dāng)所有用戶的HOL分組延時比較接近時,指數(shù)系數(shù)接近于1,此時的EXP算法近似于M-LWDF算法;當(dāng)有一個用戶的HOL分組延時變得很大時,指數(shù)項將不顧信道相關(guān)參數(shù),而提升用戶的優(yōu)先級。相比較于M-LWDF算法,EXP算法提升了HOL分組延時在優(yōu)先級中的比例,HOL分組延時比較大的用戶其優(yōu)先級會迅速升高。由于涉及到指數(shù)計算,算法復(fù)雜度較高。
3 支持實時業(yè)務(wù)調(diào)度算法仿真分析
3.1 仿真平臺架構(gòu)
仿真中終端的無線呼叫通過HSDPA網(wǎng)絡(luò)最終到達服務(wù)器節(jié)點,服務(wù)器節(jié)點按照業(yè)務(wù)模型產(chǎn)生數(shù)據(jù)包并送到核心網(wǎng),核心網(wǎng)把拆分為RLC層的數(shù)據(jù)包發(fā)送到RNC,RNC將RLC數(shù)據(jù)包發(fā)送到目的終端用戶所在的節(jié)點B,節(jié)點B負責(zé)將RLC數(shù)據(jù)包組裝成無線傳輸?shù)腗AC包并通過HSDPA采用的新技術(shù)傳輸給目的用戶終端,用戶終端將接收到的MAC包拆分成RLC層數(shù)據(jù)包,再將RLC層數(shù)據(jù)包組裝成高層協(xié)議使用的數(shù)據(jù)包。
本文采用的仿真框架圖如圖1所示。其中,AMC根據(jù)信道的C/I測量報告,查詢速率預(yù)測表找到對應(yīng)且合適的編碼速率和調(diào)制格式,并將當(dāng)前信道所支持的最大傳輸速率、數(shù)據(jù)包大小傳遞給分組調(diào)度器。分組調(diào)度器和資源分配模塊根據(jù)用戶的數(shù)據(jù)信息、AMC以及HARQ反饋信息進行信道資源的分配。HARQ進行重傳數(shù)據(jù)的合并,在接收端把接收的數(shù)據(jù)包與原數(shù)據(jù)進行對比,計算得出的BLER與鏈路級仿真提供的參考BLER相比判斷數(shù)據(jù)包是否需要重傳,并記錄重傳次數(shù),當(dāng)達到最大重傳次數(shù)則丟棄數(shù)據(jù)包。對于超過時延限制的數(shù)據(jù)包則丟棄,而總是優(yōu)先傳輸重傳數(shù)據(jù)包。
3.2 仿真結(jié)果及分析
以下給出了M_LWDF和EXP算法在吞吐量方面的仿真結(jié)果,并把M_LWDF,EXP算法相比較,且給出分析結(jié)論。吞吐量的仿真結(jié)果如圖2,圖3所示。
圖1 分組調(diào)度模型
圖2 平均扇區(qū)吞吐量
圖3 每扇區(qū)10用戶的吞吐量比較
從圖2,圖3可以看出,M_LWDF比EXP算法吞吐量要高,當(dāng)扇區(qū)用戶數(shù)為10的時候,M-LWDF算法的吞吐量為323 Kb/s,而EXP算法的吞吐量為321 Kb/s。由此可以判斷在條件相同的情況下,M_LWDF算法比EXP算法具有更高的吞吐量。
4 結(jié) 語
本文重點分析了支持實時業(yè)務(wù)調(diào)度算法的基本要求,并對M-LWDF和EXP算法進行了詳細分析,在此基礎(chǔ)上對兩種算法在吞吐量方面進行了仿真分析比較。從吞吐量仿真曲線看出,在條件相同的情況下,M_LWDF算法比EXP算法具有更高的吞吐量。
參考文獻
[1]BADER Al-Manthari, HOSSAM Hassanein. Packet sche-duling in 3.5G high-speed downlink packet access networks: breadth and depth [J]. IEEE Network, 2007, 2: 41-46.
[2]AOUDE M,RAHAL K.Scheduling algorithms perfor-mance of HSDPA over wireless channels [C]// Proceedings of 2008 3rd International Conference on Information and Communication Technologies: From Theory to Applications. [S.l.]: ICTTA, 2008: 1-5.
[3]ITO A, SHIMIZU M. Channel estimation for SIR measurement in HSDPA system [C]// Proceedings of IEEE Vehi-cular Technology Conference. [S.l.]: IEEE, 2007: 1012-1016.
[4]ANDREWS M, KUMARAN K. CDMA data QoS scheduling on the forward link with variable channel conditions [R]. [S.l.]: Bell Labs, 2000.
[5]TROELS E Kolding. Link and system performance aspects of proportional fair scheduling in WCDMA/HSDPA [C]// proceedings of 2003 IEEE 58th Vehicular Technology Conference. [S.l.]: IEEE, 2003: 1717-1722.
[6]AMEIGEIRAS P, WIGARD J, MOGENSEN P. Perfor-mance of the M-LWDF scheduling algorithm for streaming services in HSDPA [C]// Proceedings of 2004 IEEE 60th Vehicular Technology Conference. [S.l.]: IEEE, 2004, 2: 999-1003.
注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文