HSDPA分組調(diào)度算法實(shí)現(xiàn)簡(jiǎn)析

摘　要　 HSDPA（高速下行分組接入，High Speed Downlink Packages Access）技術(shù)是3GPP在R5協(xié)議中提出來(lái)的提高WCDMA網(wǎng)絡(luò)下行數(shù)據(jù)容量和傳輸速率的重要技術(shù)。分組調(diào)度是HSDPA的重要組成部分，負(fù)責(zé)分組業(yè)務(wù)傳輸塊的調(diào)度和管理，對(duì)于網(wǎng)絡(luò)性能有重要影響。本文在扼要描述HSDPA分組調(diào)度功能和過(guò)程的基礎(chǔ)上，重點(diǎn)分析對(duì)比了3種經(jīng)典分組調(diào)度算法原理以及在系統(tǒng)中的實(shí)現(xiàn)過(guò)程，并給出了測(cè)試結(jié)果。

關(guān)鍵詞　HSDPA　MAC　分組調(diào)度算法　公平性　吞吐量

1　引言

HSDPA（高速下行分組接入，High Speed Downlink Packages Access）是實(shí)現(xiàn)提高WCDMA網(wǎng)絡(luò)下行數(shù)據(jù)容量和傳輸速率的最為重要的技術(shù)。它是3GPP在R5協(xié)議中為滿足上下行數(shù)據(jù)業(yè)務(wù)非對(duì)稱(chēng)的需求提出來(lái)的。它在不改變已有WCDMA網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上，大大提高下行數(shù)據(jù)業(yè)務(wù)速率（理論最大值可達(dá)14.4Mbit/s）。

為改善WCDMA系統(tǒng)性能，HSDPA采用了如下幾項(xiàng)重要的新技術(shù)，涉及物理層和傳輸層：流控制；縮短了的無(wú)線電幀；新增加的物理信道HS-PDSCH（High Speed Physical Downlink Shared Channel）、  HS-SCCH（Shared Control Channel for HS-DSCH）、  HS-DPCCH（High Speed Dedicated Physical Control Channel）；自適應(yīng)調(diào)制和編碼（AMC）；混合自動(dòng)重復(fù)請(qǐng)求（HARQ）；增量冗余；快速分組調(diào)度功能等。

HSDPA支持高速數(shù)據(jù)業(yè)務(wù)的能力彌補(bǔ)了WCDMA的不足，為運(yùn)營(yíng)商開(kāi)展豐富新穎的數(shù)據(jù)業(yè)務(wù)提供了廣闊的空間；而且HSDPA向后兼容R99版本，大部分廠商的WCDMA設(shè)備只需要軟件升級(jí)就可以實(shí)現(xiàn)HSDPA�？深A(yù)見(jiàn)在今后一段時(shí)間內(nèi)，HSDPA將是移動(dòng)通信發(fā)展的主流。

本文重點(diǎn)探討HSDPA快速分組調(diào)度功能的實(shí)現(xiàn)。

2　HSDPA分組調(diào)度算法概述

分組調(diào)度（Packet Scheduling，PS）是無(wú)線資源管理的一個(gè)重要組成部分，從協(xié)議框架上來(lái)看它位于L2、L3層。

相比于R99，HSDPA把分組調(diào)度功能從RNC移植到了Node B的MAC（Media Access Control）層，大幅度減少了延遲，更好地適應(yīng)信道的快速變化，更大可能地匹配不同無(wú)線信道條件下的數(shù)據(jù)速率。傳輸層上，在Node B中引入MAC實(shí)體MAC-hs來(lái)控制HS-DSCH�？焖俜纸M調(diào)度能根據(jù)終端的CQI（Channel Quality Indicator）報(bào)告決定下一個(gè)2ms時(shí)間間隔應(yīng)該調(diào)度給哪個(gè)用戶，并向具有瞬間最好信道條件的用戶發(fā)送數(shù)據(jù)，使得每個(gè)瞬間都可以達(dá)到最高的用戶數(shù)據(jù)速率和系統(tǒng)吞吐量。同時(shí)，2ms的短時(shí)間間隔又增加了調(diào)度進(jìn)程的精確度。

在調(diào)度算法的研究中，需要考慮的兩個(gè)重要因素是：吞吐量和公平性。吞吐量包括小區(qū)吞吐量和用戶吞吐量，公平性可認(rèn)為是各用戶或不同分組業(yè)務(wù)占用信道資源的統(tǒng)計(jì)結(jié)果。

分組調(diào)度要解決的基本問(wèn)題：當(dāng)多個(gè)分組業(yè)務(wù)流等待接受服務(wù)時(shí)，必須確定合理的服務(wù)規(guī)則，安排流的服務(wù)順序和服務(wù)時(shí)間，以滿足各個(gè)業(yè)務(wù)流的QoS要求。

一般來(lái)說(shuō)，HSDPA的分組調(diào)度算法一般分為3類(lèi)：

· 最大信號(hào)/干擾（Max C/I）方式：系統(tǒng)跟蹤每個(gè)用戶的無(wú)線信道衰落特征，依據(jù)無(wú)線信道C/I的大小順序，確定給每個(gè)用戶的優(yōu)先權(quán)，保證每一時(shí)刻服務(wù)的用戶獲得的C/I都是最大的。這是一種極端的分配方式，可得到理想的最大吞吐量，但是對(duì)于用戶之間體現(xiàn)了服務(wù)的最不公平性，可能有部分用戶一直得不到滿意的服務(wù)。實(shí)現(xiàn)方法簡(jiǎn)單。

· 基于時(shí)間的輪循（Round Robin，RR）方式：每個(gè)用戶按順序被服務(wù)，得到同樣的平均分配時(shí)間，但每個(gè)用戶由于所處環(huán)境不同，得到的流量并不一致。用戶間的公平性高，但系統(tǒng)吞吐量最低。實(shí)現(xiàn)方法簡(jiǎn)單。

· 正比公平的（Proportional Fair）方式：綜合了以上方式的優(yōu)點(diǎn)，給予當(dāng)前信道條件逐步變好的用戶以比較高的優(yōu)先級(jí)，既照顧到大部分用戶的滿意度，也能從一定程度上保證比較高的系統(tǒng)吞吐量，是一種實(shí)用的調(diào)度方法。實(shí)現(xiàn)部分公平有很多算法，一般需要考慮到下行信道質(zhì)量、用戶緩沖隊(duì)列長(zhǎng)度、用戶平均調(diào)度時(shí)間等諸多參量。實(shí)現(xiàn)方法復(fù)雜。

3種分組調(diào)度算法的對(duì)比如表1所示。

3　HSDPA 分組調(diào)度功能實(shí)現(xiàn)

HSDPA 的分組調(diào)度功能在Node B中實(shí)現(xiàn)，主要機(jī)制如下：

Node B中的每一塊基帶處理單元（BBU）都配置了MAC-hs 調(diào)度功能，為該BBU板控制的所有HSDPA小區(qū)服務(wù)。即：MAC-hs將為所有UE ID與Priority Queue ID的組合或者UE ID 與H-ARQ Process ID的組合（簡(jiǎn)稱(chēng)為“元素”）生成一個(gè)調(diào)度列表。然后TFRC考慮UE服務(wù)小區(qū)的可用HS-DSCH資源，來(lái)為這些元素分配無(wú)線資源。一旦選好了TFRC，MAC-hs 就將MAC-d PDU（一個(gè)或多個(gè)）組裝進(jìn)一塊MAC-hs PDU中，完成調(diào)度列表更新，然后開(kāi)始下一次調(diào)度�？傮w流程如圖1所示。

調(diào)度列表生成（SLG）每TTI（2ms）運(yùn)行一次，選擇在下一個(gè)TTI中要調(diào)度的UE。根據(jù)調(diào)度算法對(duì)每個(gè)UE及其相關(guān)的數(shù)據(jù)流排序，每個(gè)入口都是UE ID和Priority Queue ID（初次傳送）或者UE ID和H-ARQ ID（重傳）的組合，如圖1所示。

對(duì)于每個(gè)元素，都會(huì)分配一個(gè)優(yōu)先級(jí)。具有最高優(yōu)先級(jí)的元素將被首先調(diào)度，然后是次高優(yōu)先級(jí)的元素，依次類(lèi)推。通過(guò)對(duì)輸入?yún)��?shù)使用不同的權(quán)重因子集，可調(diào)整調(diào)度算法。

生成調(diào)度列表需要輸入優(yōu)先級(jí)、CQI、調(diào)度周期、數(shù)據(jù)流優(yōu)先級(jí)等參數(shù)。SLG的策略是給予重傳MAC-hs PDU相比新傳MAC-hs PDU更高的權(quán)限。

首先要決定一臺(tái)UE是否可在一個(gè)特定的TTI中被調(diào)度。如果滿足以下條件，MAC-hs將調(diào)度一臺(tái)UE：

（1）自從該UE上一次被調(diào)度的TTI算起的時(shí)間等于或者長(zhǎng)于“effective inter TTI interval”（如果“effective inter TTI interval”等于1，則一臺(tái)UE可以在每個(gè)TTI內(nèi)被調(diào)度）。（2）從該UE中仍能夠接收到有效的CQI。

否則將把UE從此次TTI中的調(diào)度列表中排除。

SL元素的優(yōu)先級(jí)計(jì)算分為2個(gè)部分：

（1）重傳MAC-hs PDU 的優(yōu)先級(jí)計(jì)算

重傳優(yōu)先級(jí)基于接收到的CQI變化值以及T1剩余時(shí)間（the time before T1 elapse）的組合來(lái)決定：Retransmission= f( CQI variation，time before T1 timer elapse) 。

如果在CQI變化值中應(yīng)用一個(gè)高值的因子，重傳的可能性就高，因?yàn)闊o(wú)線條件改善了。CQI變化值定義為當(dāng)前CQI與該傳輸塊初次傳送時(shí)CQI值之間的差值；如果在T1剩余時(shí)間上應(yīng)用一個(gè)高值的因子，在達(dá)到最大重傳次數(shù)（一般是4次）之前丟棄MAC-hs PDU的可能性就小了。

UE和與MAC-hs PDU重傳相關(guān)的H-ARQ進(jìn)程將根據(jù)重傳的調(diào)度優(yōu)先級(jí)來(lái)排序，優(yōu)先級(jí)高的UE調(diào)度的可能性高。算法樣本舉例如下：

SP_Ret= RetransmissionPrioOffset +（Absolute CQI - initial transmission CQI）/30×HSDPA.CQIVariation.Factor + HSDPA.TimerT1.Factor/time before T1 elapses
　　T1 timer：控制MAC-hs PDU在HARQ Process的生存時(shí)間，當(dāng)相關(guān)的T1 timer過(guò)期時(shí)，MAC-hs PDU 會(huì)被丟棄。

CQI  variation : 重傳CQI與初次傳送的CQI之間的變化值。

預(yù)期結(jié)果：

如果同前一次調(diào)度事件相比無(wú)線條件改善，CQI variation 會(huì)得到較高的權(quán)重，從而在重傳中獲得高的優(yōu)先級(jí)。

如果HARQ buffer中的MAC-PDU即將被丟棄的話，time before T1 elapses會(huì)獲得較高的權(quán)重，獲得較高的優(yōu)先級(jí)。

權(quán)重因子取值舉例如下：  

權(quán)重因子以百分比的形式表示出來(lái)，范圍從0到100，這些因子之和等于100。

（2）新傳MAC-hs PDU 的優(yōu)先級(jí)計(jì)算

新傳MAC-hs PDU 的調(diào)度優(yōu)先級(jí)基于如下參數(shù)： New Transmission= f（Normalized Delta Time、AbsCQI、RelCQI、Buffer Time、Scheduling Priority Indicator）

①標(biāo)準(zhǔn)差時(shí)間（Normalized Delta Time）是從上次調(diào)度事件之后過(guò)去的時(shí)間（以TTI來(lái)計(jì)算），再除以優(yōu)先級(jí)隊(duì)列的數(shù)量。時(shí)間越長(zhǎng)，優(yōu)先級(jí)越高。

②絕對(duì)CQI（AbsCQI），也就是UE上報(bào)的當(dāng)前CQI值。

③相關(guān)CQI值（RelCQI），也就是絕對(duì)CQI與平均CQI之間的差值。值越高，優(yōu)先級(jí)越高。

④緩存時(shí)間（Buffer Time）是自從接收到數(shù)據(jù)的時(shí)間，與丟棄計(jì)時(shí)器（Discard Timer）有關(guān)。BT距離丟棄計(jì)時(shí)器截止時(shí)間近的（UE，Priority  Queue）會(huì)比其他BT值較小的元素有更高的優(yōu)先級(jí)。

（注：Discard timer：控制MAC-d PDU在Priority Queue中的生存時(shí)間，由優(yōu)先級(jí)隊(duì)列處理器來(lái)計(jì)算。對(duì)于一個(gè)HS-DSCH幀中每一塊來(lái)自RNC的MAC-d PDU ，都會(huì)分配一個(gè)新的discard timer。）

⑤相關(guān)隊(duì)列的調(diào)度優(yōu)先級(jí)指示（Scheduling Priority Indicator）：提高SPI將增加在一個(gè)TTI內(nèi)調(diào)度的可能性，可使操作員引入對(duì)用戶的分類(lèi)（舉例：SPI 4：“金牌用戶”；2：“銀牌用戶”；1：“銅牌用戶”。）

（注：在Iub接口，每條MAC-d 數(shù)據(jù)流都有一個(gè)優(yōu)先級(jí)隊(duì)列；在Iub/Iur HS-DSCH 幀協(xié)議中，會(huì)使用Common Channel Priority Indicator（Cm-CH PI）來(lái)標(biāo)識(shí)數(shù)據(jù)幀優(yōu)先級(jí)，范圍從0到15，0的優(yōu)先級(jí)最低，15的優(yōu)先級(jí)最高。在NBAP協(xié)議中使用與Cm-CH PI相同值的SPI，輸入到調(diào)度算法。）

算法樣本舉例如下：

SP=initialTransmissionPrioOffset + （Absolute CQI /3）×HSDPA.AbsCQIFactor+（Relative CQI/3）×HSDPA.RelCQI.Factor + Normalized Delta time×HSDPA. DeltaTime.Factor×■×（1 +（HSDPA.SPI.Factor×（SPI-1）/50）+ BT×HSDPA.BT.Factor

權(quán)重因子對(duì)調(diào)度算法有重要的影響，通過(guò)修改這些因子，可得到不同的算法類(lèi)型�？紤]HSDPA的3大類(lèi)分組調(diào)度算法，我們有如下預(yù)期結(jié)果：

所有的權(quán)重因子設(shè)為0 ( 或者除了HSDPA.DeltaTime.Factor以外的因子) ，以達(dá)到Round Robin 調(diào)度。

給予Absolute CQI較高的權(quán)重因子，將得到Max C/I調(diào)度。高小區(qū)吞吐量，但是公平性降低。

給予Relative CQI 較高的權(quán)重因子，將兼顧吞吐量和公平性，實(shí)現(xiàn)PF調(diào)度。

優(yōu)先級(jí)高的元素首先被調(diào)度；在優(yōu)先級(jí)相同的情況下，則未被調(diào)度時(shí)間最長(zhǎng)的元素被首先服務(wù)。

權(quán)重因子取值舉例如下：　　

4　HSDPA調(diào)度算法驗(yàn)證

在以上理論研究的基礎(chǔ)上，在實(shí)驗(yàn)室中我們進(jìn)行了測(cè)試，來(lái)驗(yàn)證調(diào)度算法的實(shí)際表現(xiàn)。簡(jiǎn)單描述如下:

1. 測(cè)試步驟

（1）在Max C/I、RR和PF 3種不同算法下分別進(jìn)行（2）～（4）的操作。

（2）將4個(gè)2Mbit/s業(yè)務(wù)的UE接入到R5 HSDPA小區(qū)，小區(qū)分配一條HS-SCCH信道。

（3）4個(gè)UE均啟動(dòng)FTP下傳，同時(shí)啟動(dòng)4個(gè)UE的log記錄，記錄1min后結(jié)束。

（4）統(tǒng)計(jì)各個(gè)UE的調(diào)度次數(shù)，并記錄每個(gè)UE的平均速率。

2. 測(cè)試結(jié)果及分析

在3種調(diào)度算法下測(cè)試結(jié)果如表2所示。

從上表得出在3種不同算法下總吞吐量＆調(diào)度次數(shù)最大最小差結(jié)果如下：

總吞吐量： Max C/I > PF > RR

調(diào)度次數(shù)最大最小差：Max C/I > PF > RR

我們不難看出測(cè)試結(jié)果與3種調(diào)度算法的理論描述及預(yù)期是非常吻合的。在實(shí)際網(wǎng)絡(luò)中，我們可以通過(guò)參數(shù)調(diào)整來(lái)達(dá)到不同的調(diào)度目的，優(yōu)化網(wǎng)絡(luò)。

通過(guò)以上HSDPA分組調(diào)度算法和調(diào)度過(guò)程的扼要分析，我們已能夠比較清楚地了解HSDPA分組調(diào)度功能。近年來(lái)，HSDPA的分組調(diào)度算法越來(lái)越被關(guān)注，研究人員也提出了許多新的算法和設(shè)想，比如自適應(yīng)比例公平（APF）算法，修改后的最大權(quán)重延遲優(yōu)先（M-LWDF）算法、估計(jì)優(yōu)先權(quán)調(diào)度（EPS）算法等。這些算法各具特點(diǎn)：APF是公平算法，但其考慮到了不同用戶的信道條件，需要對(duì)每一用戶進(jìn)行監(jiān)控以便更新用戶控制參數(shù)；M-LWDF需要和接納控制一起工作，它將不同用戶分組數(shù)據(jù)包的時(shí)延和當(dāng)前信道質(zhì)量信息綜合考慮，是針對(duì)流業(yè)務(wù)提出的一種吞吐量最佳算法；EPS對(duì)于系統(tǒng)包時(shí)延特性的改善效果很突出。

相信隨著HSDPA的持續(xù)演進(jìn)和系統(tǒng)商用程度的日益提高，作為HSDPA關(guān)鍵部分的分組調(diào)度算法會(huì)引發(fā)更多的關(guān)注與研究，也會(huì)涌現(xiàn)出更多新穎且實(shí)用的算法。

由于本網(wǎng)頁(yè)不支持圖片與公式效果，如有需要請(qǐng)參閱雜志。