TD-HSUPA的自適應調度算法

李方偉，王可，朱江，陳善學

（重慶郵電大學 移動通信重點實驗室，重慶 400065）

1 引言

隨著數據業務的急劇增加，要求系統提供更高的傳輸速率和更小的傳輸時延，3GPP提出了HSUPA系統的概念[1]。對于TD-HSUPA而言，主要增加了基于Node B的快速調度和混合自動重傳請求(HARQ, hybrid automatic repeat request)技術。在 TD-HSUPA系統中提供了更多的多媒體業務，如視頻電話、移動電視、游戲、電子商務、VoIP和FTP等。多樣化的業務使網絡變得更加復雜、多變，這樣對于如何在復雜、多變的網絡環境下保證不同業務的服務質量(QoS, quality of service)[2～4]就有了更高的要求。

在3GPP協議中根據用戶端到端的QoS要求定義了4種基本業務類型：會話類業務、流類業務、交互類業務和后臺類業務。對于傳統的調度算法[5]，只是注重吞吐量與公平性的調節，如最大載干比算法、輪詢算法和正比公平算法，它們不能保證實時業務對時延(會話類和流類)的要求，而M_LWDF算法和 EXP算法雖然可以較好地解決實時業務 QoS的保證，但是都不能對變化的網絡進行調整。本文提出了一種自適應的調度算法，根據不同的網絡環境對調度的參數進行微調，以更好地保證各業務的QoS。

2 TD-HSUPA調度過程

TD-HSUPA調度過程[6,7]如圖1所示。

當UE有資源要傳輸但又沒有獲得授權時，UE通過E-DCH隨機接入上行控制信道(E-RUCCH，E-DCH random access uplink control channel)發送調度信息(SI,scheduling information)給Node B。SI如下。

最高優先級邏輯信道的 ID(HLID, highest priority logical channel ID)：4 bit，在HSUPA中不同的業務映射不同的優先級的邏輯信道，以提高QoS。

圖1 TD-HSUPA調度過程

最高優先級邏輯信道的緩存狀態(HLBS, highest priority logical channel buffer status)：4bit，最高優先級邏輯信道的緩存大小占總緩存大小的比例。

總緩存狀態(TEBS, total E-DCH buffer status)：5bit。

UE 凈空功率(UPH,UE power headroom)：5bit，UE發送功率與其最大發送功率之比。

服務小區與臨小區的路損(SNPL, serving and neighbor cell path loss)：5 bit，服務小區與同頻臨小區的接收信號碼功率(RSCP, received signal code power)，有2種定義方式。

式(1)、式(2)中的Lserv表示服務小區路損，Ln表示同頻臨小區路損。

Node B根據接收到的調度請求，綜合考慮RoT[8](rise over thermal)、功率控制和SI因素，進行資源分配，Node B不能精確得到UE緩存狀態與其所有業務的信息，所以 Node B不直接決定 UE傳輸塊大小，而是通過對UE的功率、時隙和碼道資源的限制進行調度。在 E-DCH絕對授權信道(E-AGCH, E-DCH absolute grant channel)上進行授權，授權信息如下。

功率資源相關信息(PRRI, power resource related information)：5 bit，E-DCH 物理上行信道(E-PUCH, E-DCH physical uplink channel)上的期望接收功率與參考值Pe-base的比值。

時隙資源相關信息(TRRI, timeslot resource related information)：5 bit，最多對應5個時隙。

碼道資源相關信息(CRRI, code resource related information)：5bit，終端可使用的碼字只能在給定的32種中取一種。

資源持續因子(RDI)：3bit，指示資源持續時間，為可選項。

E-HICH指示(EI)：2bit，給出在下一個調度周期時，使用哪一個E-DCH HARQ指示信道(E-HICH,E-DCH hybrid ARQ indicator channel)傳輸確認信息。

E-DCH 上行控制信道的個數(ENI)：3 bit，E-DCH上行控制信道(E-UCCH)的個數，系統最多有8個E-UCCH。

UE將一直保持著對E-AGCH的監控，如果沒有接收到授權，UE將重新發送SI。而在接收到授權后，UE根據Node B的授權信息，進行E-TFC選擇。然后根據E-TFC選擇結果組裝MAC-e PDU，在上行物理信道(E-PUCH, E-DCH physical uplink channel)上發送給 Node B，并且 UE周期性地向Node B上報SI。

Node B在E-HICH上向UE返回ACK/NACK信息。

3 一種自適應的調度算法

在3GPP R99中，UE傳輸速率的調度由RNC控制，UE可用的最高傳輸速率在傳輸信道建立時由RNC確定。但是，RNC無法根據小區負載和UE的信道狀況變化靈活控制 UE的傳輸速率。而在HSUPA中，為了更好、更靈活地控制UE的傳輸速率，RNC將調度工作下放到Node B進行。

在WCDMA系統中使用的是FDD模式，由于多了E-DCH相對授權信道(E-RGCH，E-DCH relative grant channel)來輔助下傳功率授權信息，Node B通過控制 E-DCH專用物理數據信道(E-DPDCH,E-DCH dedicated physical data channel)的最大功率比來控制UE的調度。

而在TD-SCDMA系統中使用的是TDD模式，Node B不能直接決定UE傳輸塊大小，而是通過對UE的功率、時隙和碼道資源的限制來控制UE的最大傳輸速率。Node B根據UE上報的SI、RoT等情況，通過調度算法來決定是否允許UE的調度請求。本文重點對調度算法進行研究，提出了一種新的自適應調度算法。

傳統的調度算法主要有最大C/I算法、輪詢算法和正比公平算法。

最大C/I算法始終選擇信道條件最好的用戶傳輸數據，這就使得系統的總體吞吐量達到最大，但是這種算法多數用戶有可能得不到系統服務，公平性最差。

輪詢算法不考慮信道情況，循環地調度每個用戶，因此這種算法是最公平的，但是如果被調度到的用戶信道條件差，就無法高速傳輸數據，所以這種算法的吞吐量是比較差的。

正比公平算法是目前所廣泛采用的調度算法，它既考慮了用戶信道條件，還考慮了公平性，達到了系統吞吐量最大化和用戶公平性之間的一個折衷。其優先級計算式為

其中，(C/I)i(t)指第i個用戶在t時刻的載干比；而Ri(t)指該用戶的平均傳輸速率。可以看出當用戶連續被調度時Ri(t)上升，使得優先級pi(t)下降。

但上述調度算法都無法適用于對時延要求高的業務，所以又提出了M_LWDF算法和EXP算法，這2種算法考慮了用戶排隊隊列的時延情況，能夠滿足實時業務對時延的要求。

M_LWDF算法的優先級表示為

其中，αi為時延相關約束因子；wi(t)為對頭時延；ri(t)表示用戶傳輸速率；Ri(t)表示用戶平均傳輸速率。

EXP算法的優先級表示為

上述算法雖然可以較好地滿足實時業務對時延的要求，但是，對于非實時業務來說過于復雜，本文提出了一種自適應調度算法，其調度過程如圖2所示。

該算法的優先級表示為

其中，αi為系數，用于調整ri(t)、Ri(t)和ch_pi(t)的大小，使得在加權時某一項因子的作用不會過于明顯；λi為權值，滿足λ1+λ2+λ3=1，λi越大，其對應的因子在計算pi(t)時的貢獻也越大；ri(t)表示用戶傳輸速率；Ri(t)表示用戶平均傳輸速率；ch_pi(t)表示業務的優先級，ch_pi(t) =Rwi(t)HLBS，其中，當業務為實時業務時，R為1，否則為0，HLBS表示最高優先級邏輯信道的緩存大小占總緩存大小的比例。

圖2 自適應調度過程

由于 TD-HSUPA是根據不同的業務來映射不同優先級的邏輯信道，業務分為：會話類、流類、交互類和后臺類。它們對時延的要求依次降低，會話類和流類業務被定義為實時業務，交互類和后臺類被定義為非實時業務。

同時，網絡端也根據不同網絡情況，用遺傳算法[9,10]對λi進行調整。其具體步驟如圖3所示。

2) 以現有和過去的權值λi作為初始種群，而不是隨機生成初始種群，以提高計算的精確度和效率。

3) 進行二進制編碼。

4) 計算初始種群的適應度，并找出適應度最高的染色體：

其中，βi為系數，作用同αi。

5) 進行選擇運算，選出適應度高的染色體作為交叉運算的父體：

6) 進行交叉運算，交換2個父體的部分值得到新的個體，如父體s1=100101，s2=010111，則在交換后s1’=010101，s2’=100111。

7) 以0.01的變異率進行變異運算，即將0變為1，1變為0，得到新的染色體。

8) 計算所有的新染色體的適應度，找出適應度最高和最低的染色體，用原有最優染色體替換新的最差染色體，同時比較新的與原有的最優染色體，若優于原有最優染色體的適應度，則替代其值，若差于則進行計數。

9) 重復步驟 5)～8)，本文算法中最優個體參與了交換運算，如果計數值過小，就容易使其解逼近第二峰，由于該算法對計算時間要求不高，可以通過增加迭代次數來增加變異發生的概率，從而找到最優解[11]，本文在計數超過100時結束遺傳算法。

10) 調整權值λi。

圖3 遺傳算法

4 仿真結果

本文使用Opnet對M_LWDF算法和自適應算法進行了仿真，比較了它們的吞吐量和公平性。仿真參數如表1所示。

表1 仿真參數

圖4顯示了2種算法的系統吞吐量隨用戶數量的變化情況。可以看出在用戶數不多的時候，由于系統對公平性要求不高，本文算法增加了權值λ1(其值與吞吐量成正比)的值，減小了λ2(其值與公平性成正比)的值，使得吞吐量優于M-LWDF算法；而在用戶很多的時候，由于系統對公平性要求加大，該算法減小了λ1的值，增加了λ2的值，雖然在吞吐量上進行了一定的犧牲，但是提高了公平性，保證各用戶的QoS。

圖4 吞吐量比較

公平性準則是用各用戶吞吐量歸一化分布函數（CDF, cumulative distribution function）曲線來表示，如果用戶k的吞吐量為Tout(k)，相對于所有用戶平均吞吐量的歸一化吞吐量為

公平性準則由表2的3個點表示。

表2 CDF準則

該準則實質上是限制了低吞吐量用戶占總用戶數的比例，如低于0.1 倍吞吐量的用戶數不能超過總用戶數的10%。

圖5顯示了2種算法的系統公平性的比較。可以看出在有大量用戶同時接入的時候，本文算法對吞吐量做了一定的犧牲，所以系統公平性在總體上要優于M-LWDF算法。

圖5 公平性比較

圖6為用戶數從8個增加到12個時，權值λi的變化情況。可以看出本文算法有很好的適應性，能夠根據不同的網絡環境改變權值λi，以達到最優化的調度。

圖6 權值λi的改變

5 結束語

調度算法對于整個 TD-HSUPA系統來說是一個很重要的環節，但是傳統的調度算法不是沒有考慮實時業務的QoS，就是在復雜、多變的無線網絡環境不能很好地進行資源分配。

本文針對TD-HSUPA系統，提出了一種自適應調度算法，算法綜合考慮了吞吐量和公平性，以及業務的優先級，并通過遺傳算法在后臺調整加權權值，使其可以很好地適用于復雜、多變的無線網絡環境中。該算法的復雜度并不高，因為遺傳算法是在后臺運算，不直接參與計算，并沒有增加算法的復雜度。仿真結果表明，該算法能夠更靈活地運用于調度環節。

[1] 常永宇. TD-HSPA移動通信技術[M]. 北京: 人民郵電出版社,2008.CHANG Y Y. TD-HSPA Technology for Mobile Communications[M].Beijing: Posts & Telecom Press,2008.

[2] 王民. 移動網絡多媒體業務 QoS保障關鍵技術的研究[D]. 北京:北京郵電大學, 2006.WANG M. Studies on QoS Guarantee Technologies for Multimedia Services in the Wireless Networks[D]. Beijing: Beijing University of Posts and Telecommunications, 2006.

[3] 馮光升, 王慧強, 馬春光等. 面向認知網絡的用戶QoS動態自配置方法[J]. 通信學報, 2010, 31(3):133-140.FENG G S, WANG H Q, MA C G,et al. Dynamic self-configuration of user QoS oriented to cognitive network[J]. Journal on Communications, 2010, 31(3): 133-140.

[4] 3GPP TR 25.851 V4.0.0: RAB Quality of Service Renegotiation over Iu[S]. 2001.

[5] 宋艦, 李樂民. 無線網絡中的分組調度算法[J]. 通信學報, 2003,24(3): 42-48.SONG J, LI L M. Packet scheduling algorithms in wireless networks[J]. Journal on Communications, 2003, 24(3):42-48.

[6] 李佩英, 段紅光. TD-SCDMA HSUP系統中E-TFC選擇的研究[J].重慶郵電大學學報(自然科學版), 2009,21(1):6-9.LI P Y, DUAN H G. Research of E-TFC selection in HSUPA TDSCDMA system[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition), 2009,21(1): 6-9

[7] 3GPP TR 25.827: 1.28 Mcps TDD Enhanced Uplink, Physical Layer Aspects[S]. 2009.

[8] 游思晴, 張京, 王亞峰等. TD-SCDMA HSUPA基于系統RoT調度的干擾控制策略[J]. 電子與信息學報, 2008, 30(11): 2561-2564.YOU S Q, ZHANG J, WANG Y F, YANG D C. A novel intercell interference control based on scheduling for TD-SCDMA HSUPA[J].Journal of Electronics & Information Technology, 2008,30(11):2561-2564.

[9] 戴曉暉, 李敏強, 寇紀淞. 遺傳算法的性能分析研究[J]. 軟件學報,2001, 12(5): 742-750.DAI X H, LI M Q, KOU J S. Study on the performance analysis of genetic algorithms[J]. Journal of Software, 2001, 12(5): 742-750.

[10] YU Y, HUANG H. An ensemble approach to intrusion detection based on improved multi-objective genetic algorithm[J]. Journal of Software,2007,18(6):1369-1378.

[11] 何琳, 王科俊, 李國斌等. 最有保留遺傳算法及其收斂性分析[J].控制與決策, 2000, 15(1):63-66.HE L, WANG K J, LI G B,et al. Elitist preserved genetic algorithm and its convergence analysis[J]. Control and Decision, 2000,15(1):63-66.

[12] 3GPP TS 25.105: Base Station (BS) Radio Transmission and Reception (TDD)[S]. 2010.

[13] 3GPP TS 25.123: Requirements for Support of Radio Resource Management (TDD)[S]. 2010.

[14] 3GPP TS25.101: User Equipment (UE) Radio Transmission and Reception[S]. 2010.

[15] 3GPP TR 25.863: Uplink Transmit Diversity for High Speed Packet Access (HSPA) [S]. 2010.