分組數(shù)據(jù)業(yè)務(wù)調(diào)度算法課件

1、分組數(shù)據(jù)業(yè)務(wù)調(diào)度算法王亞峰 wangyf9/22/20221BUPT-QUALCOMM RESEARCH CENTER 前向鏈路9/22/20222BUPT-QUALCOMM RESEARCH CENTER 提綱調(diào)度算法的研究背景調(diào)度算法原理 最大C/I算法輪循算法正比公平算法公平性與累積分布函數(shù)曲線(xiàn)參考文獻(xiàn)9/22/20223BUPT-QUALCOMM RESEARCH CENTER 調(diào)度算法的研究背景（一）數(shù)據(jù)業(yè)務(wù)和話(huà)音業(yè)務(wù)的特點(diǎn)傳輸速率時(shí)延特性傳輸?shù)恼_性9/22/20224BUPT-QUALCOMM RESEARCH CENTER 調(diào)度算法的研究背景（三）快速小區(qū)交換技術(shù)類(lèi)似于硬切換技

2、術(shù)，在每一時(shí)刻移動(dòng)臺(tái)只同信號(hào)最好的基站通信最佳扇區(qū)的指示由R-CQICH信道反饋由于沒(méi)有軟切換的宏分集增益，處于小區(qū)邊緣的用戶(hù)C/I很低9/22/20226BUPT-QUALCOMM RESEARCH CENTER 調(diào)度算法的研究背景（四）速率控制的基本思想每個(gè)時(shí)隙移動(dòng)臺(tái)測(cè)量其C/I，經(jīng)量化后通過(guò)R-CQICH信道反饋至基站基站根據(jù)反饋的C/I、可供分配的Walsh碼、待傳輸數(shù)據(jù)隊(duì)列的長(zhǎng)度確定最大可支持的數(shù)據(jù)速率然后從所有請(qǐng)求傳輸?shù)挠脩?hù)中，按照一定的調(diào)度算法選出其中的一個(gè)用戶(hù)，給予傳輸機(jī)會(huì)9/22/20227BUPT-QUALCOMM RESEARCH CENTER 調(diào)度算法原理（一）最大C/

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

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

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

6、 CENTER 調(diào)度算法原理（八）正比公平算法算法2（針對(duì)不提供實(shí)時(shí)視頻業(yè)務(wù)的系統(tǒng)）5 算法1和算法2的區(qū)別算法2提高了公平性算法1保證了實(shí)時(shí)視頻業(yè)務(wù)的時(shí)延要求9/22/202216BUPT-QUALCOMM RESEARCH CENTER 調(diào)度算法原理（九）正比公平算法在計(jì)算 時(shí)，是以時(shí)隙為單位的，如下式如果在上一時(shí)隙用戶(hù)k 沒(méi)有被調(diào)度上如果在上一時(shí)隙用戶(hù)k被調(diào)度上 的值為如果用戶(hù)隊(duì)列滿(mǎn)時(shí)的分組大小9/22/202217BUPT-QUALCOMM RESEARCH CENTER 調(diào)度算法原理（十一）正比公平算法對(duì)調(diào)度算法進(jìn)行簡(jiǎn)化，可以得到下式由此可以看出，正比公平算法的實(shí)質(zhì)是兩個(gè)因素共同起作

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

8、PT-QUALCOMM RESEARCH CENTER 調(diào)度算法原理（十四）用戶(hù)吞吐量和距離的散點(diǎn)圖由于輪詢(xún)算法不考慮用戶(hù)的信道狀況，所以離基站近的用戶(hù)其吞吐量也不是很高隨著距離增加，單用戶(hù)的吞吐量緩慢下降但相對(duì)而言，邊緣用戶(hù)的吞吐量還是比較低，這不是因?yàn)楣絾?wèn)題，而是前面提到的效用問(wèn)題，離基站遠(yuǎn)的用戶(hù)，他請(qǐng)求傳輸?shù)乃俾时旧砭筒桓?/22/202222BUPT-QUALCOMM RESEARCH CENTER 調(diào)度算法原理（十五）圖 2 用戶(hù)數(shù)據(jù)吞吐量和其到最佳服務(wù)扇區(qū)距離的散點(diǎn)圖(輪詢(xún)調(diào)度算法）9/22/202223BUPT-QUALCOMM RESEARCH CENTER 調(diào)度算法原理（十

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

10、函數(shù) (二)公平性準(zhǔn)則該準(zhǔn)則由下表的3個(gè)點(diǎn)表示歸一化吞吐量累積分布函數(shù)9/22/202227BUPT-QUALCOMM RESEARCH CENTER 公平性準(zhǔn)則和累積分布函數(shù) (四)圖 4 各種調(diào)度算法的累積分布函數(shù)曲線(xiàn)9/22/202229BUPT-QUALCOMM RESEARCH CENTER 公平性準(zhǔn)則和累積分布函數(shù) (五)公平性準(zhǔn)則和累積分布函數(shù)的關(guān)系上頁(yè)的累積分布函數(shù)曲線(xiàn)表明，輪詢(xún)算法和正比公平算法都滿(mǎn)足公平性要求，而最大C/I算法不滿(mǎn)足從系統(tǒng)吞吐量角度來(lái)看，正比公平算法大于輪詢(xún)算法，而最大C/I算法是各種算法中最大的 隨著累積分布函數(shù)曲線(xiàn)的底

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

12、境和數(shù)值結(jié)果（一）仿真環(huán)境每扇區(qū)20個(gè)FTP用戶(hù)，業(yè)務(wù)模型為數(shù)據(jù)隊(duì)列全滿(mǎn)基站功率有20的開(kāi)銷(xiāo)信道模型是單徑Rayleigh，120kmph其它參數(shù)見(jiàn)參考文獻(xiàn)39/22/202232BUPT-QUALCOMM RESEARCH CENTER 仿真環(huán)境和數(shù)值結(jié)果（二）圖5 各種調(diào)度算法的吞吐量9/22/202233BUPT-QUALCOMM RESEARCH CENTER 參考文獻(xiàn)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 提綱調(diào)度算法的研究背景調(diào)度算法原理參考文獻(xiàn)9/22/202236BUPT-QUALCOMM RESEARCH CENTER 調(diào)度算法的研究背景（一）前向和反向數(shù)據(jù)業(yè)務(wù)的特點(diǎn)前向和反向數(shù)據(jù)速率不對(duì)稱(chēng)，一般前向高于反向前向數(shù)據(jù)業(yè)務(wù)在分組數(shù)據(jù)業(yè)務(wù)信道（PDCH）傳輸，而反向則在SCH信道上傳輸SCH信道上的數(shù)據(jù)傳輸有兩種，一是自發(fā)傳送，針對(duì)低時(shí)延要求的低速數(shù)據(jù)業(yè)務(wù)，二是調(diào)度傳送，針對(duì)時(shí)延要求不高的業(yè)務(wù)19/22/202237BUPT-QUALC

15、OMM RESEARCH CENTER 調(diào)度算法的研究背景（二）前向和反向數(shù)據(jù)業(yè)務(wù)的特點(diǎn)不同于前向數(shù)據(jù)業(yè)務(wù)的速率控制，反向采用功率控制反向在速率申請(qǐng)時(shí)，和前向也有所不同不同于前向數(shù)據(jù)業(yè)務(wù)的快速小區(qū)交換，反向仍采用軟切換9/22/202238BUPT-QUALCOMM RESEARCH CENTER 調(diào)度算法的研究背景（三）反向調(diào)度算法的特點(diǎn)反向由于單用戶(hù)申請(qǐng)的速率不高，所以可以同時(shí)選多個(gè)用戶(hù)選擇多少用戶(hù)同時(shí)傳輸，依賴(lài)于基站端的ROT值9/22/202239BUPT-QUALCOMM RESEARCH CENTER 調(diào)度算法的研究背景（四）反向調(diào)度算法的意義使可達(dá)到的時(shí)分調(diào)度增益最大，同時(shí)最充分

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

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

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

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