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