1、分組數據業務調度算法王亞峰 wangyf9/22/20221BUPT-QUALCOMM RESEARCH CENTER 前向鏈路9/22/20222BUPT-QUALCOMM RESEARCH CENTER 提綱調度算法的研究背景調度算法原理 最大C/I算法輪循算法正比公平算法公平性與累積分布函數曲線參考文獻9/22/20223BUPT-QUALCOMM RESEARCH CENTER 調度算法的研究背景（一）數據業務和話音業務的特點傳輸速率時延特性傳輸的正確性9/22/20224BUPT-QUALCOMM RESEARCH CENTER 調度算法的研究背景（三）快速小區交換技術類似于硬切換技

2、術，在每一時刻移動臺只同信號最好的基站通信最佳扇區的指示由R-CQICH信道反饋由于沒有軟切換的宏分集增益，處于小區邊緣的用戶C/I很低9/22/20226BUPT-QUALCOMM RESEARCH CENTER 調度算法的研究背景（四）速率控制的基本思想每個時隙移動臺測量其C/I，經量化后通過R-CQICH信道反饋至基站基站根據反饋的C/I、可供分配的Walsh碼、待傳輸數據隊列的長度確定最大可支持的數據速率然后從所有請求傳輸的用戶中，按照一定的調度算法選出其中的一個用戶，給予傳輸機會9/22/20227BUPT-QUALCOMM RESEARCH CENTER 調度算法原理（一）最大C/

3、I算法基站總是選擇信道條件最好的用戶，給予傳輸機會如果只在信道條件好的時候傳輸，可以提高傳輸速率、降低編碼的冗余通過實時的改變傳輸方案來適應時變的信道環境，可以提高吞吐量9/22/20229BUPT-QUALCOMM RESEARCH CENTER 調度算法原理（二）最大C/I算法由于具有多用戶分集增益，這種調度算法是所有可能的算法中系統吞吐量最大的但這種算法存在的最大問題是公平性差，接近基站的移動臺吞吐量很大，而小區邊緣的用戶得不到服務機會，存在“餓死”現象。因此，這種算法被認為是最不公平的9/22/202210BUPT-QUALCOMM RESEARCH CENTER 調度算法原理（三）輪

4、詢算法基站不考慮用戶的信道狀況，隨機選取用戶傳輸由于沒有多用戶分集增益，系統吞吐量低每個用戶享有系統資源的機會相同，因此在一定意義上它被認為是最公平的 9/22/202211BUPT-QUALCOMM RESEARCH CENTER 調度算法原理（四）輪詢算法但在固定網方面的研究中提出，在討論公平性問題時，不能只考慮分配資源的方式，還要考慮利用資源的效用，同樣的資源給不同的用戶獲得的效用是不一樣的選擇不同的用戶，由于請求的傳輸速率不同，因此傳輸分組占有的時隙數是不同的，即傳輸速率不同正是由于對資源利用的效用不同，輪詢算法也不是絕對公平的9/22/202212BUPT-QUALCOMM RESE

5、ARCH CENTER 調度算法原理（五）正比公平算法為了做好吞吐量和公平性的折中，Qualcomm在HDR（High Data Rate,即1x EV DO)中提出了一種稱為正比公平的調度算法 在每個時刻t，每個用戶k計算一個優先權函數一個扇區的所有用戶中，優先權最大的將獲得傳輸機會9/22/202213BUPT-QUALCOMM RESEARCH CENTER 調度算法原理（六）正比公平算法在時刻t，用戶k的優先權函數計算如下式中DRC(t) 是可以支持的最大傳輸速率，由R-CQICH反饋的 C/I計算得到 是正比公平吞吐量9/22/202214BUPT-QUALCOMM RESEARCH

6、 CENTER 調度算法原理（八）正比公平算法算法2（針對不提供實時視頻業務的系統）5 算法1和算法2的區別算法2提高了公平性算法1保證了實時視頻業務的時延要求9/22/202216BUPT-QUALCOMM RESEARCH CENTER 調度算法原理（九）正比公平算法在計算 時，是以時隙為單位的，如下式如果在上一時隙用戶k 沒有被調度上如果在上一時隙用戶k被調度上 的值為如果用戶隊列滿時的分組大小9/22/202217BUPT-QUALCOMM RESEARCH CENTER 調度算法原理（十一）正比公平算法對調度算法進行簡化，可以得到下式由此可以看出，正比公平算法的實質是兩個因素共同起作

7、用，相互制約以達到吞吐量和公平性的折中9/22/202219BUPT-QUALCOMM RESEARCH CENTER 調度算法原理（十二）用戶吞吐量和距離的散點圖由于最大C/I算法總是選擇信道最好的用戶，所以離基站近的用戶吞吐量很高處于小區半徑中間的用戶，由于快衰和慢衰的影響，在一些時候C/I可以最高，因此也能被調度上，但下降趨勢很快離基站遠的用戶，由于C/I為最大的概率很小，因此吞吐量接近于09/22/202220BUPT-QUALCOMM RESEARCH CENTER 調度算法原理（十三）圖1 用戶數據吞吐量和其到最佳服務扇區距離的散點圖(最大C/I調度算法）9/22/202221BU

8、PT-QUALCOMM RESEARCH CENTER 調度算法原理（十四）用戶吞吐量和距離的散點圖由于輪詢算法不考慮用戶的信道狀況，所以離基站近的用戶其吞吐量也不是很高隨著距離增加，單用戶的吞吐量緩慢下降但相對而言，邊緣用戶的吞吐量還是比較低，這不是因為公平問題，而是前面提到的效用問題，離基站遠的用戶，他請求傳輸的速率本身就不高9/22/202222BUPT-QUALCOMM RESEARCH CENTER 調度算法原理（十五）圖 2 用戶數據吞吐量和其到最佳服務扇區距離的散點圖(輪詢調度算法）9/22/202223BUPT-QUALCOMM RESEARCH CENTER 調度算法原理（十

9、六）用戶吞吐量和距離的散點圖正比公平算法介于前二者之間，最高吞吐量雖遠低于最大C/I算法，但高于輪詢算法隨著距離增加，單用戶的吞吐量下降速度快于輪詢算法前者說明其吞吐量高，后者保證了它的公平性9/22/202224BUPT-QUALCOMM RESEARCH CENTER 公平性準則和累積分布函數 (一)公平性準則3GPP2為了衡量各算法的公平性，在鼓勵提出新調度算法的同時，確定了一個公平性準則該準則是用相對于所有用戶平均吞吐量歸一化的用戶吞吐量的累積分布函數表示式中的 是指用戶k的實際吞吐量9/22/202226BUPT-QUALCOMM RESEARCH CENTER 公平性準則和累積分布

10、函數 (二)公平性準則該準則由下表的3個點表示歸一化吞吐量累積分布函數9/22/202227BUPT-QUALCOMM RESEARCH CENTER 公平性準則和累積分布函數 (四)圖 4 各種調度算法的累積分布函數曲線9/22/202229BUPT-QUALCOMM RESEARCH CENTER 公平性準則和累積分布函數 (五)公平性準則和累積分布函數的關系上頁的累積分布函數曲線表明，輪詢算法和正比公平算法都滿足公平性要求，而最大C/I算法不滿足從系統吞吐量角度來看，正比公平算法大于輪詢算法，而最大C/I算法是各種算法中最大的 隨著累積分布函數曲線的底

11、端向左，系統吞吐量越大，這是由于越往左，表示低吞吐量用戶占的比例越大，也就是調度算法給信道條件差的用戶給的傳輸機會越少 9/22/202230BUPT-QUALCOMM RESEARCH CENTER 公平性準則和累積分布函數 (六)公平性準則和累積分布函數的關系這也啟發我們，在滿足公平準則的前提下，累積分布函數曲線盡量向左靠近公平準則，這樣的調度算法將是吞吐量和公平性折中最好的 從前面的圖4可以看出，正比公平算法是做好吞吐量和公平性折中的一種嘗試，但不是最優的盡管最優解得到很困難，但近似最優解是可以達到的9/22/202231BUPT-QUALCOMM RESEARCH CENTER 仿真環

12、境和數值結果（一）仿真環境每扇區20個FTP用戶，業務模型為數據隊列全滿基站功率有20的開銷信道模型是單徑Rayleigh，120kmph其它參數見參考文獻39/22/202232BUPT-QUALCOMM RESEARCH CENTER 仿真環境和數值結果（二）圖5 各種調度算法的吞吐量9/22/202233BUPT-QUALCOMM RESEARCH CENTER 參考文獻1 P. Bender et al., “CDMA/HDR: A Bandwidth-Efficient High-Speed Wireless Data Service for Nomadic Users”, IEEE

13、 Communications Magazine 38 7 Jul 2000, pp. 70-77.2 A.Jalali, R. Padovani, R. Pankaj, “Data Throughput of CDMA-HDR, a High Efficiency Data Rate Personal Communication Wireless System”, VTC2000, pp.1854-1858.3 Frank Zhou, 1xEV-DV Evaluation Methodology (Rev.26), WG5 Evaluation AHG, May 9, 20019/22/20

14、2234BUPT-QUALCOMM RESEARCH CENTER 反向鏈路9/22/202235BUPT-QUALCOMM RESEARCH CENTER 提綱調度算法的研究背景調度算法原理參考文獻9/22/202236BUPT-QUALCOMM RESEARCH CENTER 調度算法的研究背景（一）前向和反向數據業務的特點前向和反向數據速率不對稱，一般前向高于反向前向數據業務在分組數據業務信道（PDCH）傳輸，而反向則在SCH信道上傳輸SCH信道上的數據傳輸有兩種，一是自發傳送，針對低時延要求的低速數據業務，二是調度傳送，針對時延要求不高的業務19/22/202237BUPT-QUALC

15、OMM RESEARCH CENTER 調度算法的研究背景（二）前向和反向數據業務的特點不同于前向數據業務的速率控制，反向采用功率控制反向在速率申請時，和前向也有所不同不同于前向數據業務的快速小區交換，反向仍采用軟切換9/22/202238BUPT-QUALCOMM RESEARCH CENTER 調度算法的研究背景（三）反向調度算法的特點反向由于單用戶申請的速率不高，所以可以同時選多個用戶選擇多少用戶同時傳輸，依賴于基站端的ROT值9/22/202239BUPT-QUALCOMM RESEARCH CENTER 調度算法的研究背景（四）反向調度算法的意義使可達到的時分調度增益最大，同時最充分

16、地利用BS的noise-rise資源 限制同時傳輸的數據用戶數，以降低移動臺之間的干擾降低位于小區邊緣用戶的傳輸速率，以降低對鄰小區的干擾9/22/202240BUPT-QUALCOMM RESEARCH CENTER 調度算法簡介（一）調度算法的流程反向功率控制反向pilot由內環功控在一個所希望的門限上為使突發工作的R-SCH獲得所需QoS（設置為5% FER)，各MS還應支持額外的1500bps的R-FCH，功率控制使該R-FCH的FER在1%，這是針對激活集中各BS而言的 為消除在某些信道模型下的高FER，將針對各種turbo碼 速率的IS-2000.2-A規定的pilot參考電平提高

17、了0.25dB29/22/202241BUPT-QUALCOMM RESEARCH CENTER 調度算法簡介（二）調度算法的流程速率申請各MS使用其R-FCH或R-DCCH提供隊列大小信息以申請R-SCH上的數據速率 所申請的速率是基于數據隊列長度及MS可用發射功率確定的，MS可用的發射功率的計算應考慮：最大可用發射功率、當前pilot發射功率、以及為功率控制偏差所留的余量（margin）9/22/202242BUPT-QUALCOMM RESEARCH CENTER 調度算法簡介（三）調度算法的流程速率申請的計算設BS處接收到的RL導頻C/I（即Ec/Io）的目標值為 ，則功率控制的目標是

18、令下式滿足：其中， 表示當前RL導頻信道發射功率，L為損耗，I為干擾功率9/22/202243BUPT-QUALCOMM RESEARCH CENTER 調度算法簡介（四）調度算法的流程速率申請的計算然后，MS用下面的方法來確定要申請的R-SCH速率（對于高速傳輸）求出所能達到的最大R-SCH和導頻功率之比根據這個T/P功率比，查它所能滿足的數據速率，向BS申請39/22/202244BUPT-QUALCOMM RESEARCH CENTER 調度算法簡介（五）調度算法的流程調度和速率分配 每個調度周期的開始，MS被分配一個基于其申請速率和隊列信息的速率調度周期為一幀（20ms），MS在每一幀

19、都可調度為不同速率。這是對于20ms幀結構來說最快的調度周期9/22/202245BUPT-QUALCOMM RESEARCH CENTER 調度算法簡介（六）調度算法的流程調度算法對MS所申請的速率進行優先級排隊，然后使用greedy filling策略調度，在RL上傳送數據的權利先給優先級最高的MS及其后面跟著的優先級略低的MS 只要ROT沒有超過要求的門限，在優先級隊列中排在靠前位置的所有MS將都被賦予傳輸其申請的速率的權利9/22/202246BUPT-QUALCOMM RESEARCH CENTER 調度算法簡介（七）調度算法的流程調度算法這種集中式的調度考慮了MS對其激活集中各扇區的noise-rise的貢獻 優先級函數則在充分保證鏈路質量和公平度之間做出了折中下頁的優先權計算方法是正比公平策略的一種實現方式，而實際的系統中不同的廠商可能會用不同的實現方法9/22/202247BUPT-QUALCOMM RESEARCH CENTER 調度算法簡介（八）優先權函數的計算其中，Rreq為MS所申請的速率Ralloc為過濾（平均）后的所分配給MS的速率 9/22/202248BUPT-QUALCOMM RESEARCH CENTER 調度算法簡介（九）優先權函數的計算續上頁SetPt表示歸一化的功率控制設置點Prx(1)表示激活