3G系統(tǒng)中的分組調(diào)度算法

摘　要　無線分組調(diào)度算法的功能是為無線用戶的各種分組業(yè)務(wù)合理分配無線資源，在滿足用戶間公平性前提下有效提高移動(dòng)信道利用率和服務(wù)質(zhì)量（QoS）。本文介紹并比較了3G系統(tǒng)的三類經(jīng)典分組調(diào)度算法，分析了新一代無線通信系統(tǒng)中分組調(diào)度算法所面臨的問題。

關(guān)鍵詞　分組調(diào)度算法　輪循調(diào)度　最大載干比調(diào)度　比例公平調(diào)度

1　前言

無線通信系統(tǒng)是資源受限的，如何利用有限的系統(tǒng)資源滿足日益增長的用戶需求，已經(jīng)成為移動(dòng)通信系統(tǒng)制造商和運(yùn)營商亟需解決的問題。沒有有效的無線資源管理策略，再先進(jìn)的傳輸技術(shù)也會(huì)因受到資源的限制而不可能充分發(fā)揮其優(yōu)勢(shì)。作為一項(xiàng)關(guān)鍵技術(shù)，無線資源管理已經(jīng)成為衡量一個(gè)移動(dòng)通信系統(tǒng)體制是否可行、系統(tǒng)服務(wù)質(zhì)量優(yōu)劣的準(zhǔn)則。無線資源管理主要包括切換控制、功率控制、接入控制、負(fù)荷控制以及分組調(diào)度等方面的內(nèi)容。

無線資源管理是3G系統(tǒng)無線網(wǎng)絡(luò)控制器（RNC）的重要組成部分，其主要作用是負(fù)責(zé)空中接口資源的分配和使用，確保用戶業(yè)務(wù)的服務(wù)質(zhì)量、系統(tǒng)規(guī)劃的覆蓋區(qū)域以及提高系統(tǒng)容量。在3G的演進(jìn)過程中，標(biāo)準(zhǔn)化組織3GPP和 3GPP2也在不斷完善和增強(qiáng)相關(guān)技術(shù)。對(duì)于分組調(diào)度算法，一方面要考慮到算法實(shí)現(xiàn)的復(fù)雜度，另一方面需要注意對(duì)系統(tǒng)性能指標(biāo)的影響，如公平性、時(shí)延、業(yè)務(wù)的服務(wù)質(zhì)量（QoS）等。目前采用比較多的調(diào)度算法主要有輪循調(diào)度、最大載干比調(diào)度、比例公平調(diào)度三種類型。本文主要在介紹它們的基本工作原理以及它們的改進(jìn)型調(diào)度算法并進(jìn)行比較。

2　3G系統(tǒng)中的無線分組調(diào)度算法

在分組通信中，為了獲得統(tǒng)計(jì)復(fù)用增益，需要多個(gè)業(yè)務(wù)流共享帶寬。因此，當(dāng)多個(gè)用戶爭用資源時(shí)，就需要有一種機(jī)制來確定服務(wù)次序，有效地分配無線資源，這就是分組調(diào)度。由于無線信道時(shí)變特性、帶寬資源有限和移動(dòng)臺(tái)功率受限等因素的影響，無線網(wǎng)絡(luò)中的分組調(diào)度算法有別于有線網(wǎng)絡(luò)。

圖1描述了無線分組調(diào)度機(jī)制的基本原理。調(diào)度器首先根據(jù)信道狀態(tài)監(jiān)視/預(yù)測(cè)模塊提供的信道信息和用戶的隊(duì)列狀態(tài)，依據(jù)一定的調(diào)度算法，計(jì)算出每個(gè)用戶的優(yōu)先級(jí)，然后根據(jù)優(yōu)先級(jí)對(duì)用戶數(shù)據(jù)排隊(duì)，并分配無線資源，最后送到發(fā)射機(jī)。

2.1　輪循調(diào)度算法

輪循調(diào)度算法（RR）假設(shè)所有用戶具有相同的優(yōu)先級(jí)，保證以相等的機(jī)會(huì)為系統(tǒng)中所有用戶分配相同數(shù)量的資源，使用戶按照某種確定的順序占用無線資源進(jìn)行通信。其主要思想是，以犧牲吞吐量為代價(jià)，公平地為系統(tǒng)內(nèi)的每個(gè)用戶提供資源。由于RR算法不考慮不同用戶無線信道的具體情況，雖然保證了用戶時(shí)間公平性，但吞吐量是極低的。通常RR調(diào)度算法的結(jié)果被作為時(shí)間公平性的上界。為了改善RR算法的時(shí)延特性、無線信道自適應(yīng)特性及其在變長分組環(huán)境下的公平性，由它產(chǎn)生了一系列改進(jìn)型算法，如機(jī)會(huì)差額輪循（ODRR）、無線差額輪循（WDRR）等。ODDR算法對(duì)于用戶i引入了定值計(jì)數(shù)器Qi和變值計(jì)數(shù)器DCi，當(dāng)輪循道用戶i時(shí)，DCi＝DCi+Qi。每次輪循發(fā)送的數(shù)據(jù)量p不超過DCi，并更新DCi，令DCi = DCi- PenaltyFactor·Size（p）。其中PenaltyFactor是根據(jù)無線信道狀況調(diào)整的參數(shù)，例如可以定義為理想傳輸速率與實(shí)際傳輸速率之比或每單位功耗的理想傳輸比特?cái)?shù)與實(shí)際傳輸比特?cái)?shù)之比，這樣就使得信道狀況好的用戶可以傳輸更多的數(shù)據(jù)。WDDR在某些方面和ODDR類似，在每個(gè)輪循周期內(nèi)它將每個(gè)用戶的數(shù)據(jù)分成更小的子塊，依次發(fā)送每個(gè)用戶的序號(hào)最小的子塊，當(dāng)用戶i不存在第j個(gè)子塊時(shí)則跳過，繼續(xù)發(fā)送用戶i+1的第j個(gè)子塊�？傊�，它們都盡量保持RR算法實(shí)現(xiàn)簡單的特點(diǎn)，同時(shí)又努力提高吞吐量。

2.2　最大載干比調(diào)度算法

最大載干比（max C/I）調(diào)度算法保證具有最好鏈路條件的用戶獲得最高的優(yōu)先級(jí)：

無線信道狀態(tài)好的用戶優(yōu)先級(jí)高，使得數(shù)據(jù)正確傳輸?shù)膸茁试黾樱�錯(cuò)誤重傳的次數(shù)減少，整個(gè)系統(tǒng)的吞吐量得到了提升。顯然，精確的信道預(yù)測(cè)算法則會(huì)帶來更高的增益。

雖然max C/I能夠適應(yīng)無線信道的時(shí)變性，但是完全不考慮用戶間的公平性。為了保證每個(gè)用戶達(dá)到最低吞吐量，同時(shí)對(duì)于信道條件好的用戶的吞吐量也有一定限制，文獻(xiàn)[1]提出了速率受限最大載干比調(diào)度算法。其主要思想是設(shè)定速率門限值，限制高傳輸速率用戶的傳輸機(jī)會(huì)，補(bǔ)償速率較低的用戶。若設(shè)傳輸速率的上限為Rth_max，下限為Rth_min。當(dāng)用戶平均速率大于Rth_max時(shí)，用戶優(yōu)先級(jí)設(shè)為最低（值為0），而用戶平均速率小于Rth_min時(shí)，該用戶享有最高優(yōu)先級(jí)（值為∞）。

......
......
......

2.4　三種主要分組調(diào)度算法的比較

RR和max C/I算法實(shí)現(xiàn)簡單，分別考慮的是時(shí)間公平性和最大吞吐量兩種極限情況下的系統(tǒng)性能，其主要用作評(píng)估其他調(diào)度算法性能的參考，而在實(shí)際系統(tǒng)并不采用。表1主要對(duì)三種基本調(diào)度算法進(jìn)行了簡單比較。

RR算法的優(yōu)點(diǎn)是從資源占用的角度保證了用戶間的公平性，缺點(diǎn)是不考慮用戶間的信道差異，不利于改善系統(tǒng)吞吐量。max C/I算法完全根據(jù)時(shí)變的信道狀況進(jìn)行用戶調(diào)度，可以最大限度的提高頻譜利用率，缺點(diǎn)是用戶間的公平性無法得到保證。由于信道的陰影效應(yīng)、多徑衰落的影響，有時(shí)處于小區(qū)半徑中間地區(qū)的移動(dòng)臺(tái)的C/I也可能會(huì)高于離基站較近的移動(dòng)臺(tái)，但是位于小區(qū)邊緣的移動(dòng)臺(tái)由于路徑損耗大，可能在很長的時(shí)間內(nèi)都得不到系統(tǒng)服務(wù)。另外，RR算法和max C/I算法在進(jìn)行資源調(diào)度時(shí)，都不考慮以前的調(diào)度狀況，因此是無記憶的。PF調(diào)度算法綜合考慮了用戶的信道條件差異和對(duì)于公平性的要求，是對(duì)吞吐量和公平性的折中，同樣適用于高速下行分組接入（HSDPA）等各種無線通信系統(tǒng)。PF調(diào)度算法是目前公認(rèn)比較好的調(diào)度算法，但它是以提高算法復(fù)雜度為代價(jià)的。

3　未來分組調(diào)度算法發(fā)展趨勢(shì)

隨著無線數(shù)據(jù)業(yè)務(wù)的普及和多媒體應(yīng)用需求的增長，未來的無線通信網(wǎng)絡(luò)將為多種業(yè)務(wù)類型提供接入服務(wù)，同時(shí)用戶對(duì)于QoS的要求也越來越高。網(wǎng)絡(luò)中的用戶將不受時(shí)間、地點(diǎn)網(wǎng)絡(luò)類型的限制，根據(jù)業(yè)務(wù)類型和接入成本自定義服務(wù)等級(jí)，因此分組調(diào)度算法必須引入QoS的區(qū)分和確保機(jī)制。但是現(xiàn)有的算法均沒有考慮到實(shí)際系統(tǒng)中多業(yè)務(wù)QoS要求，只適用于單業(yè)務(wù)的傳輸。因此，為了滿足多業(yè)務(wù)混合傳輸，提供QoS確保機(jī)制也是今后算法改進(jìn)需要關(guān)注的一個(gè)主要方面。此外，傳統(tǒng)無線資源管理算法的功能是比較清晰和獨(dú)立的，各種算法在完成自己的功能外，很少和其他無線資源管理算法進(jìn)行交互。但是在未來無線通信系統(tǒng)中，要求無線資源管理算法進(jìn)行綜合設(shè)計(jì)，充分考慮各個(gè)功能塊之間的相互聯(lián)系和影響，以適應(yīng)物理信道和業(yè)務(wù)需求的變化。

另一方面，為了使移動(dòng)用戶峰值傳輸速率比3G系統(tǒng)提高1~2個(gè)數(shù)量級(jí)，新一代無線通信系統(tǒng)空中接口的物理層將采用多輸入多輸出（MIMO）、正交頻分復(fù)用（OFDM）、混合自動(dòng)重傳請(qǐng)求（HARQ）、自適應(yīng)調(diào)制編碼技術(shù)（AMC）等無線增強(qiáng)新技術(shù)，這給無線資源管理帶來了新的機(jī)遇和挑戰(zhàn)。例如，當(dāng)系統(tǒng)采用AMC時(shí)，max C/I算法可使系統(tǒng)獲得最高的吞吐量。OFDM技術(shù)會(huì)使得無線資源呈時(shí)頻二維結(jié)構(gòu)——在時(shí)間上將無線資源劃分為多個(gè)時(shí)隙，每個(gè)時(shí)隙由多個(gè)OFDM符號(hào)組成，在頻率上將無線資源劃分為多個(gè)子信道。OFDM系統(tǒng)的調(diào)度算法不僅要考慮用戶間的服務(wù)次序，更重要的是考慮在同時(shí)進(jìn)行分組傳輸?shù)挠脩糸g如何合理配置時(shí)隙與子載波資源。同一時(shí)隙下同一用戶的數(shù)據(jù)不僅可以分布在不同的子載波上，還可以分布在不同OFDM符號(hào)內(nèi)。而MIMO又引入了可供分配的空間域資源。因此，新一代的無線調(diào)度策略需要考慮包括時(shí)域、頻域、空間域在內(nèi)的多維無線資源的合理調(diào)配，使無線資源的使用能夠適應(yīng)于業(yè)務(wù)承載要求和無線信道質(zhì)量的變化，以較低的無線分組調(diào)度算法獲得較高的頻譜利用率和較好的用戶公平性，最大限度的共享無線資源。

4　總結(jié)

本文主要闡述了三類主流的無線分組調(diào)度算法，分析了未來無線通信技術(shù)引進(jìn)OFDM、MIMO新技術(shù)對(duì)于無線分組調(diào)度算法的影響。無論是簡單RR算法、能夠動(dòng)態(tài)跟蹤信道信息的max C/I算法、綜合考慮性能與復(fù)雜度的PF算法，還是未來無線通信系統(tǒng)引進(jìn)新技術(shù)后的改進(jìn)的分組調(diào)度算法，其主要思想都是結(jié)合系統(tǒng)可用的無線資源、信道狀況、業(yè)務(wù)的QoS需求等因素確定用戶優(yōu)先級(jí)順序，然后依據(jù)排隊(duì)結(jié)果分配無線資源，發(fā)送分組數(shù)據(jù)，盡可能地使系統(tǒng)的吞吐量獲得較大的改善，并使用戶公平地共享無線頻譜資源，保證業(yè)務(wù)的QoS。

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