摘 要： 研究了CDMA2000 1x EVDO系統(tǒng)一種支持VideoStream業(yè)務的調度算法及FPGA實現(xiàn)；通過大量研究和設計，得到一種能保證性能和速度，又適合硬件實現(xiàn)的調度算法。綜合時選用Altera公司的StratixII 系列EP2S60F484C4芯片，并通過功能仿真驗證了硬件實現(xiàn)的可行性和正確性。
關鍵詞： 視頻流; 調度; 現(xiàn)場可編程陣列
?
隨著固網和移動網的融合，為適應新的業(yè)務應用需求，提高無線網絡資源利用率，滿足業(yè)務的QoS要求，對現(xiàn)有網絡架構提出了實質性的改變，更是對網絡性能提出的挑戰(zhàn)。作為CDMA2000 1x EVDO 系統(tǒng)關鍵技術之一的多用戶調度越來越引起學者的關注。本文在已有參考文獻的基礎上提出一種針對視頻流業(yè)務的無線分組調度算法，并用FPGA予以實現(xiàn)，證明其可行性。
1 多用戶調度原理
CDMA2000 1x EVDO系統(tǒng)的前向由導頻信道、MAC信道、控制信道和業(yè)務信道采用時分復用(TDM)的方式組成[1]。業(yè)務信道用來傳輸業(yè)務數(shù)據,由系統(tǒng)中的所有用戶共享使用；控制信道用于廣播系統(tǒng)開銷消息以及發(fā)送尋呼消息；而MAC信道通過碼分的方式將用于過載控制的反向活動指示、反向功率控制和輔助實現(xiàn)虛擬軟切換的DRCLock三個子信道復用在一起。在時間軸上，CDMA2000 1x EVDO將前向信道分為長1.67ms的時隙，每個時隙由2 048個碼片構成，每個時隙又分為兩個1/2時隙，其結構如圖1所示。
?
?
CDMA2000 1x EVDO的前向始終以最大功率發(fā)射，當系統(tǒng)處于空閑狀態(tài)時，前向僅發(fā)射導頻和MAC信道，而當系統(tǒng)中的用戶有數(shù)據需要傳輸時，業(yè)務信道以時隙為單位在不同用戶之間通過調度分配使用。同一時刻，系統(tǒng)只向一個用戶發(fā)射數(shù)據，避免了小區(qū)內的多用戶干擾，而且采用了自適應調制編碼以適應時變的信道，表1列出了Rlease 0系統(tǒng)前向采用的可變數(shù)據速率集。CDMA2000 1x EVDO在反向引入數(shù)據速率控制信道(DRC)，移動臺根據測量的載干比來向基站申請能夠實現(xiàn)數(shù)據可靠接收的最大前向傳輸速率；基站中的調度程序根據終端申請的速率以及一段時間內時隙分配的情況來決定下一個時隙給哪一個移動臺使用。一般當移動臺處于深衰落狀態(tài)時，調度程序就不給它分配傳輸時隙或少分配傳輸時隙，而更多地為申請高傳輸速率的移動臺服務，從而實現(xiàn)系統(tǒng)數(shù)據吞吐量的提高，這個過程就是本文將要重點研究的多用戶調度。多用戶調度作為CDMA2000 1x EVDO關鍵技術之一直接影響到系統(tǒng)性能和業(yè)務及用戶的QoS要求，因此對調度算法的研究勢在必行。系統(tǒng)前向分組發(fā)送調度的示意見圖2。
?
圖2中，用戶信息模塊一般保存有用戶的權限、業(yè)務的QoS需求等相關信息；信道狀態(tài)信息模塊從反向的邏輯信道中提取各用戶上報的狀態(tài)信息（如DRC）；用戶隊列一般采用先進先出原則緩存發(fā)送到用戶的數(shù)據分組，并將分組排隊信息反饋到調度模塊；分組模塊綜合利用業(yè)務的QoS需求、分組隊列信息以及用戶信道狀態(tài)信息等來決定傳輸時隙的分配。
2 基于回播緩存的調度
參考文獻[2]結合了視頻流自身的業(yè)務特性， 在M-LWDF、EXP算法基礎上，提出了PB-M-LWDF、PB-EXP算法。該算法考慮了接收端回播緩存（Play—Buffer）空間的大?。寒斁彺鏀?shù)據量小于某個門限值時，增加優(yōu)先權，反之降低優(yōu)先權。具體數(shù)學描述如下。
(1) M-LWDF算法調度準則[3]：
(2) EXP算法調度準則[4]：
(3)以上兩種算法的Wi權重兼指用戶i隊列頭部數(shù)據分組(HOL)的最大時延，而Karina Gribanova等學者不僅考慮了HOL時延，還加入了視頻回播參數(shù)， 如下：????????????????????????????????????????????????????????????????????????
式(3)中l(wèi)(t)為回播緩存數(shù)據量，Rd(t)為回播速率，于是可以得出在Wi(t)及Rd(t)相等的情況下，當緩存數(shù)據多時就會相應地降低優(yōu)先權，反之增加優(yōu)先權。最后得到PB-M-LWDF、PB-EXP調度準則。
參考文獻[2]仿真驗證了PB-M-LWDF、PB-EXP調度準則，與M-LWDF及EXP算法相比改善了丟包率。
3 基于發(fā)送緩存的調度算法
基于回播緩存，顧名思義，基站需要得到接收端的緩存信息，而CDMA2000 1x EVDO標準沒有此項開銷消息的配置，更改規(guī)范也是不合理的，因此該算法在實際應用中不可能實施，針對該缺點，本節(jié)提出一種基于發(fā)送緩存的調度算法。
一般地，基站發(fā)送緩存量與終端回播緩存量存在一定的關系[5]：當發(fā)送緩存較少時，接收端的回播緩存一般較多，而不需要立即發(fā)送；換個角度來說就是，如果發(fā)送緩存較大，就意味著接收緩存很少，需立即發(fā)送數(shù)據以避免出現(xiàn)回播緩存的餓死現(xiàn)象。但數(shù)據發(fā)送并不僅僅與緩存量有關，還與用戶數(shù)據之前是否被調度的歷史信息有關。例如，有兩用戶數(shù)據，其中一個用戶被連續(xù)調度，而另一用戶則被間斷調度，但發(fā)送緩存量相等，這時該調度哪個分組數(shù)據就成了問題。
3.1 優(yōu)先權函數(shù)
(1) 最能體現(xiàn)用戶被調度狀況的就是用戶的平均吞吐量
，其更新過程如下：???
優(yōu)先權與該值成反比。
很明顯i用戶t+1時隙的信道平均狀態(tài)與t時隙是否分配給i用戶無關，因此其更新較為簡單，式中β是平滑因子。DRC(t)/
表征信道當前狀態(tài)與平均狀態(tài)的比值，優(yōu)先權與該值成正比。
? 同樣i用戶t+1時隙發(fā)送緩存的平均存儲量也與t時隙是否分配給i用戶無關，因此其更新也較為簡單，式中bi(t)為i用戶n時隙緩存量，λ是平滑因子。
??? (5)根據當前緩存量給出用戶權重因子wi(t)，更新如下：
3.2 算法流程
假設系統(tǒng)僅支持后臺類及視頻流業(yè)務，根據經典PF算法及(11)式給出的優(yōu)先權函數(shù)，算法流程如下：
(1)給每個用戶分別設立后臺類及視頻流業(yè)務兩隊列，對每個分組按業(yè)務及用戶輸入相應的隊列，如圖3所示。
?
(2) 將不同業(yè)務類型的用戶根據不同的調度準則，對權值進行比較。
后臺類業(yè)務調度準則，PF算法：
(3) 比較(12)、(13)式權值大小，將時隙分配給權值最高的用戶。
? (4) 根據式(6)、(7)、(8)、(9)、(10)更新各參數(shù)值，進行下一時隙的權值比較。
3.3 仿真驗證
小區(qū)采用單扇區(qū)配置，多用戶在小區(qū)內均勻分布，仿真時用戶數(shù)量為8，信道模型為瑞利衰落，路損指數(shù)為4，用戶移動速度為3km/h，基站發(fā)射功率為20W，小區(qū)半徑為1km；分組發(fā)送規(guī)格及速率集以CDMA2000 1x EVDO Rlease 0 技術規(guī)范為準，見表1，傳輸速率與信噪比的對應關系見表2，分組大小為128bit，且在仿真過程中不考慮分組到達過程的影響，并假定用戶的數(shù)據緩存足夠大且用戶數(shù)據隊列中有足夠多的分組以供下載。
?
調度器的調度周期為一個時隙，并假設用戶的DRC在一個時隙內是不變的。時隙長是1.667ms。仿真時所用的用戶權重因子wi(t)更新參數(shù)：bimax=32KB，bihigh=0.5，bilow=0.2；各參數(shù)更新的平滑因子α、β、λ固定為0.001，而μ為0.01。假設所有用戶僅接受后臺類及視頻流業(yè)務服務，與EXP指數(shù)算法、參考文獻[2]提出的PB算法的性能進行比較。
(1)將時隙分配概率作為仿真結果進行比較，如圖4。
由仿真結果可以看出，在滿足視頻流業(yè)務QoS的前提下，系統(tǒng)為后臺類業(yè)務提供了更高的吞吐率，而且比PB算法的資源利用率還有效。
(2)將系統(tǒng)吞吐量作為仿真結果進行比較，如圖5。
由仿真結果可以看出，隨著視頻流業(yè)務的增多，系統(tǒng)吞吐量呈下降趨勢，本文提出的基于發(fā)送緩存的調度算法與PB算法具有相似的系統(tǒng)吞吐量。
4 算法的硬件實現(xiàn)
仿真結果表明，本文的調度算法具有比PB算法更高的系統(tǒng)性能，由此本文根據該算法設計出一高速可行的調度器。在硬件設計中，根據扇區(qū)內的激活用戶數(shù)來設計FPGA模塊，給每個用戶分配 PF權值計算和基于發(fā)送緩存的權值計算模塊各一塊，將計算結果送入頂層的權值比較器，由比較結果來控制最終的發(fā)送分組。圖6給出了頂層設計模塊圖。
?
4.1 算法模塊FPGA實現(xiàn)
本文的硬件實現(xiàn)方法是基于DSPbuilder的建模方式[6]，在建模時也盡量采納庫里包含的計算模塊。
(1) PF算法比較簡單，其結構框圖如圖7。
PF算法的缺點是：DSPbuilder庫里的除法器運算結果是商和余數(shù)，將該值送入權值比較器會出現(xiàn)比較錯誤，因此考慮將除數(shù)擴大1 024倍來近似消除余數(shù)的影響，而只將商送入權值比較器。
(2)基于發(fā)送緩存的算法，其結構框圖如圖8。
?
????為降低運算流程的復雜度，設計緩存監(jiān)視模塊時，考慮隊列緩存直接使用DSPbuilder庫里的FIFO模塊，再利用查表方式得到緩存利用率，從而提高運算速度，對于除法運算的設計技巧同樣采用方式(1)。
4.2 調度器功能仿真
用QuartusII綜合由DSPbuilder編譯完成工程項目，并對該項目進行波形功能仿真。由于QuartusII庫I/O資源有限，因此只對兩個用戶的業(yè)務分組調度進行波形仿真，結果如圖9。
?
仿真結果與理論結果完全一致，圖9中Input、Input2分別為用戶1、用戶2的DRC輸入；Input1、 Input7分別為用戶1、用戶2的數(shù)據源，包含后臺類及視頻流兩種數(shù)據業(yè)務，用第一比特的0、1區(qū)別，0表示視頻流，1表示后臺類業(yè)務；Output1、Output7分別為用戶1、用戶2的被調分組的輸出。
本文針對視頻流這一主流多媒體業(yè)務，提出一種基于發(fā)送緩存的調度算法，該算法克服了PF的固有缺點（基站側要有終端回播緩存的反饋信息），在理論上也有比PF算法較好的系統(tǒng)性能，通過功能仿真也證明了設計的調度器的可行性。
參考文獻
[1]?3GPP2 C.S0024 v4.0. CDMA2000 high rate packet data air interface specification[S]. March 2004.
[2] GRIBANOVA K， J?魧NTTI R. On scheduling video?streaming data in the HDR system.IEEE 2004:2572-2576.
[3]?ANDREWS M, KUMARAN K, RAMANAN K,et al.?Providing quality of service over a shared wireless link[J]. IEEE Communications Magazine,2001:150-154.
[4] SHAKKOTTAI S, STOLYAR A. Scheduling algorithms for a mixture of real-time and non-real-time data in HDR
[J].Proc. Int. Teletrafic Congress, Sept. 2001:793-804.
[5]?KOTO H, FUKUSHIMA M, NOMOTO S. et al.Scheduling?algorithm for real-time application in mobile packet
networks[J]. IEEE Communications Society,2005.
[6]?DSP Builder Reference Manual. http://www.altera.com.