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