李方偉，王可，朱江，陳善學(xué)

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

1 引言

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

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

2 TD-HSUPA調(diào)度過程

TD-HSUPA調(diào)度過程[6,7]如圖1所示。

當(dāng)UE有資源要傳輸?shù)譀]有獲得授權(quán)時，UE通過E-DCH隨機接入上行控制信道(E-RUCCH，E-DCH random access uplink control channel)發(fā)送調(diào)度信息(SI,scheduling information)給Node B。SI如下。

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

圖1 TD-HSUPA調(diào)度過程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 一種自適應(yīng)的調(diào)度算法

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

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

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

傳統(tǒng)的調(diào)度算法主要有最大C/I算法、輪詢算法和正比公平算法。

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

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

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

其中，(C/I)i(t)指第i個用戶在t時刻的載干比；而Ri(t)指該用戶的平均傳輸速率?？梢钥闯霎?dāng)用戶連續(xù)被調(diào)度時Ri(t)上升，使得優(yōu)先級pi(t)下降。

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

M_LWDF算法的優(yōu)先級表示為

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

EXP算法的優(yōu)先級表示為

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

該算法的優(yōu)先級表示為

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

圖2 自適應(yīng)調(diào)度過程

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

同時，網(wǎng)絡(luò)端也根據(jù)不同網(wǎng)絡(luò)情況，用遺傳算法[9,10]對λi進行調(diào)整。其具體步驟如圖3所示。

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

3) 進行二進制編碼。

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

其中，βi為系數(shù)，作用同αi。

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

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

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

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

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

10) 調(diào)整權(quán)值λi。

圖3 遺傳算法

4 仿真結(jié)果

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

表1 仿真參數(shù)

圖4顯示了2種算法的系統(tǒng)吞吐量隨用戶數(shù)量的變化情況?？梢钥闯鲈谟脩魯?shù)不多的時候，由于系統(tǒng)對公平性要求不高，本文算法增加了權(quán)值λ1(其值與吞吐量成正比)的值，減小了λ2(其值與公平性成正比)的值，使得吞吐量優(yōu)于M-LWDF算法；而在用戶很多的時候，由于系統(tǒng)對公平性要求加大，該算法減小了λ1的值，增加了λ2的值，雖然在吞吐量上進行了一定的犧牲，但是提高了公平性，保證各用戶的QoS。

圖4 吞吐量比較

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

公平性準(zhǔn)則由表2的3個點表示。

表2 CDF準(zhǔn)則

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

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

圖5 公平性比較

圖6為用戶數(shù)從8個增加到12個時，權(quán)值λi的變化情況?？梢钥闯霰疚乃惴ㄓ泻芎玫倪m應(yīng)性，能夠根據(jù)不同的網(wǎng)絡(luò)環(huán)境改變權(quán)值λi，以達到最優(yōu)化的調(diào)度。

圖6 權(quán)值λi的改變

5 結(jié)束語

調(diào)度算法對于整個 TD-HSUPA系統(tǒng)來說是一個很重要的環(huán)節(jié)，但是傳統(tǒng)的調(diào)度算法不是沒有考慮實時業(yè)務(wù)的QoS，就是在復(fù)雜、多變的無線網(wǎng)絡(luò)環(huán)境不能很好地進行資源分配。

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

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

[2] 王民. 移動網(wǎng)絡(luò)多媒體業(yè)務(wù) QoS保障關(guān)鍵技術(shù)的研究[D]. 北京:北京郵電大學(xué), 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] 馮光升, 王慧強, 馬春光等. 面向認(rèn)知網(wǎng)絡(luò)的用戶QoS動態(tài)自配置方法[J]. 通信學(xué)報, 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] 宋艦, 李樂民. 無線網(wǎng)絡(luò)中的分組調(diào)度算法[J]. 通信學(xué)報, 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系統(tǒng)中E-TFC選擇的研究[J].重慶郵電大學(xué)學(xué)報(自然科學(xué)版), 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基于系統(tǒng)RoT調(diào)度的干擾控制策略[J]. 電子與信息學(xué)報, 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ì)淞. 遺傳算法的性能分析研究[J]. 軟件學(xué)報,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.