李彬,鄧華陽(yáng)

摘 要：隨著移動(dòng)通信技術(shù)的飛速發(fā)展, 未來(lái)的移動(dòng)通信系統(tǒng)將以數(shù)據(jù)業(yè)務(wù)為主，所以無(wú)線分組調(diào)度算法將成為影響系統(tǒng)性能和保證用戶服務(wù)質(zhì)量的關(guān)鍵所在。在HSDPA系統(tǒng)中無(wú)線資源管理是通過(guò)分組調(diào)度算法來(lái)實(shí)現(xiàn)的。理想的調(diào)度算法應(yīng)滿足各類業(yè)務(wù)的QoS要求和用戶之間的公平性，使系統(tǒng)資源利用率達(dá)到最大。主要介紹了EXP算法和M-LWDF算法，并對(duì)兩種算法在吞吐量方面進(jìn)行了仿真分析，說(shuō)明了M-LWDF算法具有更高的吞吐量。

關(guān)鍵詞：HSDPA; M-LWDF算法; EXP算法; 吞吐量

中圖分類號(hào)：TN911-34

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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 引 言

隨著移動(dòng)通信技術(shù)的飛速發(fā)展，移動(dòng)用戶急劇增加，通信系統(tǒng)容量不斷加大，所支持的業(yè)務(wù)類型除了傳統(tǒng)的語(yǔ)音業(yè)務(wù)外，還包括低/高速數(shù)據(jù)、圖像等數(shù)據(jù)業(yè)務(wù)。不同的業(yè)務(wù)具有不同的服務(wù)質(zhì)量(QoS)要求，如對(duì)分組時(shí)延、丟包率、數(shù)據(jù)速率的要求都各不相同。無(wú)線網(wǎng)絡(luò)設(shè)計(jì)有三大目標(biāo):一是保證各類業(yè)務(wù)的QoS要求;二是保證用戶之間的公平性;三是使系統(tǒng)的資源利用率達(dá)到最大。這都需要借助于無(wú)線資源管理來(lái)完成。未來(lái)的移動(dòng)通信系統(tǒng)以數(shù)據(jù)業(yè)務(wù)為主，所以無(wú)線分組調(diào)度算法將成為影響系統(tǒng)性能和保證用戶服務(wù)質(zhì)量的關(guān)鍵。

1 實(shí)時(shí)業(yè)務(wù)調(diào)度算法的基本要求

HSDPA中實(shí)時(shí)數(shù)據(jù)業(yè)務(wù)的QoS可以采用兩種方式定義［1-3］。

一種是對(duì)傳輸時(shí)延進(jìn)行限制。傳輸時(shí)延參數(shù)用來(lái)保證流業(yè)務(wù)分組的時(shí)間波動(dòng)，為了限制最大時(shí)間波動(dòng)，3GPP規(guī)定了傳輸時(shí)延要求，也就是所有分組時(shí)延的一定比例要小于傳輸時(shí)延要求，用公式表示如下：

Pr{Wi＞Ti}≤ξi

(1)

即用戶所接收分組的時(shí)延Wi大于門(mén)限Ti的概率應(yīng)小于門(mén)限ξi。在UE側(cè)存在去抖動(dòng)緩沖器，其用來(lái)彌補(bǔ)端到端的時(shí)延抖動(dòng)。由于用戶希望較短的時(shí)間流業(yè)務(wù)的連續(xù)播放以及緩沖器存儲(chǔ)空間大小的限制，去抖動(dòng)緩沖器中出現(xiàn)斷續(xù)，影響用戶感受。因此除了用去抖動(dòng)緩沖器來(lái)彌補(bǔ)時(shí)延，還要求Node B盡量降低用戶的時(shí)延抖動(dòng)，在Node B側(cè)盡量降低用戶的時(shí)延抖動(dòng)，這就需要通過(guò)分組調(diào)度來(lái)實(shí)現(xiàn)。因此，HSDPA實(shí)時(shí)調(diào)度算法的基本要求之一就是保證用戶的傳輸時(shí)延要求。這是在統(tǒng)計(jì)意義上對(duì)分組時(shí)延進(jìn)行限制。

另一種QoS定義方式是對(duì)保證比特速率進(jìn)行限制。保證比特速率是用來(lái)保證流業(yè)務(wù)的傳輸速率的波動(dòng)。同樣3GPP也規(guī)定了保證比特速率要求，用公式表示如下：

Ri≥GBRi

(2)

式中:Ri表示第i個(gè)用戶的比特速率;GBRi表示第i個(gè)用戶的保證比特速率，這兩個(gè)速率都是應(yīng)用層的。這意味著應(yīng)用層的速率要大于應(yīng)用層的保證速率，但不一定要過(guò)大，過(guò)多超過(guò)保證比特速率是沒(méi)有必要的。 實(shí)時(shí)業(yè)務(wù)的傳輸速率保證也要在Node B調(diào)度執(zhí)行，因此，HSDPA實(shí)時(shí)業(yè)務(wù)調(diào)度算法的另一個(gè)基本要求就是保證用戶的傳輸速率。這是在統(tǒng)計(jì)意義上對(duì)傳輸速率進(jìn)行限制。

假設(shè)在給定小區(qū)內(nèi)，有一組流業(yè)務(wù)用戶集{i},i=1,2,…,N。對(duì)每一個(gè)用戶i，其相關(guān)的數(shù)據(jù)流為由遠(yuǎn)端服務(wù)器傳來(lái)的M個(gè)分組流{p琲j},j=1,2,…,M，隨后這些分組流將被送到終端進(jìn)行解碼。在經(jīng)過(guò)無(wú)線接入網(wǎng)時(shí)，分組{p琲j}在網(wǎng)絡(luò)中會(huì)經(jīng)歷延時(shí)。因此HSDPA的大部分功能在基站實(shí)現(xiàn)。分組流經(jīng)過(guò)Iub流量控制功能實(shí)體由無(wú)線網(wǎng)絡(luò)控制器傳到基站后進(jìn)入基站的一系列{Qj}隊(duì)列中。為了限制分組{p琲j}的最大隊(duì)列長(zhǎng)度，每個(gè)分組從到達(dá)基站開(kāi)始就會(huì)被設(shè)置一個(gè)時(shí)間標(biāo)簽，當(dāng)分組等待時(shí)間超過(guò)時(shí)間標(biāo)簽設(shè)置的時(shí)間期限后，分組被丟掉。分組在基站的隊(duì)列中等待，之后或者通過(guò)HS-DSCH信道成功地傳送出去，或者等待時(shí)間超過(guò)時(shí)間標(biāo)簽設(shè)置的時(shí)間期限則被丟棄。分組的丟棄條件為：

d琲j≥Ti

(3)

式中:d琲j表示在隊(duì)列中的等待時(shí)間；Ti代表用戶i的丟棄時(shí)間期限。對(duì)于不同的業(yè)務(wù)類型，分組被丟的時(shí)間期限不同。通常，實(shí)時(shí)業(yè)務(wù)的丟棄時(shí)間會(huì)較短，而非實(shí)時(shí)業(yè)務(wù)的丟棄時(shí)間會(huì)很長(zhǎng)。

在HSDPA中，分組調(diào)度功能包括每個(gè)小區(qū)中用戶的無(wú)線資源的分配。因此，調(diào)度器不僅對(duì)小區(qū)性能有直接影響，而且對(duì)終端用戶也有影響，如傳輸時(shí)延和接收比特率，這兩個(gè)參數(shù)最終決定了終端用戶接收到的QoS水平。

假設(shè)用戶集{i}的時(shí)變信道的瞬時(shí)特性服從統(tǒng)計(jì)規(guī)律：

{Ri[n]},i=1,2,…,N

(4)

假設(shè)式(4)中沒(méi)有碼字復(fù)用，即在一個(gè)TTI內(nèi)所有的功率和資源全部分給了一個(gè)用戶。

在上述假設(shè)條件下，HSDPA中分組調(diào)度器的任務(wù)就簡(jiǎn)化為在每一個(gè)TTI選擇被服務(wù)的用戶。給定小區(qū)的用戶集i=1,2,…,N，定義分組調(diào)度器的目標(biāo)是最大化小區(qū)吞吐量，同時(shí)滿足用戶的QoS要求。

HSDPA系統(tǒng)中針對(duì)實(shí)時(shí)業(yè)務(wù)無(wú)線分組調(diào)度算法，提出了EXP算法和M-LWDF算法。這兩個(gè)調(diào)度算法的基本要求就是要滿足兩個(gè)QoS要求：傳輸時(shí)延和保證比特速率。因此，理論上基于QoS的HSDPA調(diào)度算法可以用于流業(yè)務(wù)。

2 支持實(shí)時(shí)業(yè)務(wù)的調(diào)度算法

2.1 M-LWDF算法

M-LWDF(Modified Largest Weighted Delay First)［4-6］是針對(duì)高速業(yè)務(wù)流而提出的。主要思想是將分組數(shù)據(jù)包的時(shí)延和如何利用信道信息平衡考慮，其用戶優(yōu)先級(jí)的計(jì)算不僅和用戶當(dāng)前的信道質(zhì)量有關(guān)，還和包的隊(duì)列延時(shí)有關(guān)。M-LWDF算法的用戶優(yōu)先級(jí)定義為：

Pi[n]=-log(δi)?Ri[n]λi[n]?Di[n]Ti

(5)

式中:Pi[n]代表用戶i在第n個(gè)TTI的優(yōu)先級(jí)；Ri是每個(gè)TTI所支持的最大用戶數(shù)據(jù)速率;λi是用戶平均吞吐量的估計(jì)，仿真中按照式(5)計(jì)算，時(shí)間窗口長(zhǎng)度為1000 TTI;Di代表用戶i的HOL分組延時(shí)；Di[n]定義為第n個(gè)TTI隊(duì)列的HOL分組的隊(duì)列延時(shí);Ti是用戶i在隊(duì)列中等待的時(shí)延限制;δi是QoS參數(shù)，用來(lái)區(qū)別不同QoS優(yōu)先級(jí)的用戶。

可以這樣理解式(5)，用戶的優(yōu)先級(jí)首先是與它的QoS參數(shù)有關(guān)，不同類型的業(yè)務(wù)對(duì)應(yīng)不同的傳輸?shù)燃?jí)，對(duì)應(yīng)不同的QoS參數(shù)。QoS要求越高，傳輸優(yōu)先級(jí)就越高。Ri反映了用戶瞬時(shí)信道狀況，信道條件越好，所支持的最大傳輸數(shù)據(jù)速率就越高；基于小區(qū)吞吐量最大化的原則，信道條件越好，其傳輸優(yōu)先級(jí)就越高。λi作為用戶平均吞吐量的估計(jì)，與傳輸優(yōu)先級(jí)成反比，考慮用戶的公平性，當(dāng)信道條件總是很好時(shí)，一些用戶就有可能連續(xù)得到服務(wù)，使得其他信道條件差的用戶會(huì)出現(xiàn)“餓死現(xiàn)象”，為了照顧其他用戶的服務(wù)要求，就必須要降低該用戶的傳輸優(yōu)先級(jí)，使得其他用戶可以得到服務(wù)。同時(shí)該算法還考慮到了隊(duì)列時(shí)延，分組在隊(duì)列中等待的時(shí)間越久，其傳輸優(yōu)先級(jí)就越高，這也是考慮到了有的用戶可能會(huì)一直得不到服務(wù)，其分組在隊(duì)列中的等待時(shí)間就會(huì)很長(zhǎng)，而一旦超過(guò)了時(shí)延門(mén)限，該分組就會(huì)被丟棄。所以，考慮分組等待時(shí)間不超過(guò)時(shí)延門(mén)限，就必須增大等待時(shí)間久的分組的優(yōu)先級(jí)。Ti為用戶分組在隊(duì)列中的時(shí)延限制，當(dāng)分組等待時(shí)間超過(guò)該時(shí)延限制，就會(huì)在基站隊(duì)列中被丟棄。因此，時(shí)延限制越大，被丟棄的概率就越小，其傳輸優(yōu)先級(jí)就越小。

2.2 EXP算法

在M-LWDF算法之后，朗訊實(shí)驗(yàn)室又提出了EXP算法，該算法是基于公平比調(diào)度和指數(shù)加權(quán)的時(shí)延平衡機(jī)制的，其調(diào)度優(yōu)先級(jí)公式如下：

j=maxi aiμi(t)μi(t)exp

aiWi(t)-aW1+aW

(6)

aW=1N∑Ni=1aiWi(t)

(7)

式中:μi(t)代表用戶i在時(shí)刻t信道所支持的瞬時(shí)數(shù)據(jù)傳輸速率;μi(t)為信道支持的平均數(shù)據(jù)速率;Wi(t)是用戶i在基站緩沖隊(duì)列HOL分組延時(shí);ai>0,i=1,2,…,N，代表QoS級(jí)別，ai=-log(δi)/Ti，Ti 代表用戶i時(shí)延門(mén)限，δi 是時(shí)延得不到滿足的最大概率。

EXP算法和M-LWDF算法本質(zhì)上相似，都利用了實(shí)時(shí)業(yè)務(wù)的時(shí)延約束和多用戶分集增益來(lái)優(yōu)化系統(tǒng)容量。不同的是，EXP算法對(duì)基站緩沖隊(duì)列的HOL分組延時(shí)做了指數(shù)處理，當(dāng)所有用戶的HOL分組延時(shí)比較接近時(shí)，指數(shù)系數(shù)接近于1，此時(shí)的EXP算法近似于M-LWDF算法；當(dāng)有一個(gè)用戶的HOL分組延時(shí)變得很大時(shí)，指數(shù)項(xiàng)將不顧信道相關(guān)參數(shù)，而提升用戶的優(yōu)先級(jí)。相比較于M-LWDF算法，EXP算法提升了HOL分組延時(shí)在優(yōu)先級(jí)中的比例，HOL分組延時(shí)比較大的用戶其優(yōu)先級(jí)會(huì)迅速升高。由于涉及到指數(shù)計(jì)算,算法復(fù)雜度較高。

3 支持實(shí)時(shí)業(yè)務(wù)調(diào)度算法仿真分析

3.1 仿真平臺(tái)架構(gòu)

仿真中終端的無(wú)線呼叫通過(guò)HSDPA網(wǎng)絡(luò)最終到達(dá)服務(wù)器節(jié)點(diǎn)，服務(wù)器節(jié)點(diǎn)按照業(yè)務(wù)模型產(chǎn)生數(shù)據(jù)包并送到核心網(wǎng)，核心網(wǎng)把拆分為RLC層的數(shù)據(jù)包發(fā)送到RNC，RNC將RLC數(shù)據(jù)包發(fā)送到目的終端用戶所在的節(jié)點(diǎn)B，節(jié)點(diǎn)B負(fù)責(zé)將RLC數(shù)據(jù)包組裝成無(wú)線傳輸?shù)腗AC包并通過(guò)HSDPA采用的新技術(shù)傳輸給目的用戶終端，用戶終端將接收到的MAC包拆分成RLC層數(shù)據(jù)包，再將RLC層數(shù)據(jù)包組裝成高層協(xié)議使用的數(shù)據(jù)包。

本文采用的仿真框架圖如圖1所示。其中，AMC根據(jù)信道的C/I測(cè)量報(bào)告，查詢速率預(yù)測(cè)表找到對(duì)應(yīng)且合適的編碼速率和調(diào)制格式，并將當(dāng)前信道所支持的最大傳輸速率、數(shù)據(jù)包大小傳遞給分組調(diào)度器。分組調(diào)度器和資源分配模塊根據(jù)用戶的數(shù)據(jù)信息、AMC以及HARQ反饋信息進(jìn)行信道資源的分配。HARQ進(jìn)行重傳數(shù)據(jù)的合并，在接收端把接收的數(shù)據(jù)包與原數(shù)據(jù)進(jìn)行對(duì)比，計(jì)算得出的BLER與鏈路級(jí)仿真提供的參考BLER相比判斷數(shù)據(jù)包是否需要重傳，并記錄重傳次數(shù)，當(dāng)達(dá)到最大重傳次數(shù)則丟棄數(shù)據(jù)包。對(duì)于超過(guò)時(shí)延限制的數(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的時(shí)候，M-LWDF算法的吞吐量為323 Kb/s,而EXP算法的吞吐量為321 Kb/s。由此可以判斷在條件相同的情況下，M_LWDF算法比EXP算法具有更高的吞吐量。

4 結(jié) 語(yǔ)

本文重點(diǎn)分析了支持實(shí)時(shí)業(yè)務(wù)調(diào)度算法的基本要求，并對(duì)M-LWDF和EXP算法進(jìn)行了詳細(xì)分析，在此基礎(chǔ)上對(duì)兩種算法在吞吐量方面進(jìn)行了仿真分析比較。從吞吐量仿真曲線看出，在條件相同的情況下，M_LWDF算法比EXP算法具有更高的吞吐量。

參考文獻(xiàn)

［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)容請(qǐng)以PDF格式閱讀原文