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

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

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

1　引言

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

為改善WCDMA系統(tǒng)性能，HSDPA采用了如下幾項重要的新技術(shù)，涉及物理層和傳輸層：流控制；縮短了的無線電幀；新增加的物理信道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）；混合自動重復(fù)請求（HARQ）；增量冗余；快速分組調(diào)度功能等。

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

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

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

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

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

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

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

一般來說，HSDPA的分組調(diào)度算法一般分為3類：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

UE和與MAC-hs PDU重傳相關(guān)的H-ARQ進程將根據(jù)重傳的調(diào)度優(yōu)先級來排序，優(yōu)先級高的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的生存時間，當(dāng)相關(guān)的T1 timer過期時，MAC-hs PDU 會被丟棄。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（注：在Iub接口，每條MAC-d 數(shù)據(jù)流都有一個優(yōu)先級隊列；在Iub/Iur HS-DSCH 幀協(xié)議中，會使用Common Channel Priority Indicator（Cm-CH PI）來標(biāo)識數(shù)據(jù)幀優(yōu)先級，范圍從0到15，0的優(yōu)先級最低，15的優(yōu)先級最高。在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)重因子對調(diào)度算法有重要的影響，通過修改這些因子，可得到不同的算法類型�？紤]HSDPA的3大類分組調(diào)度算法，我們有如下預(yù)期結(jié)果：

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

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

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

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

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

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

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

1. 測試步驟

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

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

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

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

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

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

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

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

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

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

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

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

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