王 浩 李知航 蔣慧琳 潘志文 尤肖虎
(東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室,南京 210096)
全負(fù)載場景中最優(yōu)調(diào)度算法長時(shí)平均性能分析
王 浩 李知航 蔣慧琳 潘志文 尤肖虎
(東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室,南京 210096)
首先分析了全負(fù)載場景中輪詢調(diào)度、最大速率調(diào)度、比例公平調(diào)度和速率累積分布調(diào)度這4種常用調(diào)度算法.結(jié)果顯示,速率累積分布調(diào)度在保證公平的基礎(chǔ)上可以得到最好的效率,是4種調(diào)度算法中的最優(yōu)算法.然后采用概率推導(dǎo)法給出了該調(diào)度算法的長時(shí)平均性能分析,即以輪詢調(diào)度為比較基準(zhǔn)的多用戶分集增益的理論推導(dǎo).該分集增益可通過短時(shí)統(tǒng)計(jì)結(jié)果預(yù)測長時(shí)平均性能,且可適用于任意實(shí)際場景.計(jì)算機(jī)仿真結(jié)果驗(yàn)證了對于該調(diào)度算法所產(chǎn)生的多用戶分集增益理論分析的準(zhǔn)確性,理論分析結(jié)果與實(shí)際調(diào)度結(jié)果的誤差低于0.1%.
輪詢調(diào)度;最大速率調(diào)度;比例公平調(diào)度;速率累積分布調(diào)度;多用戶分集增益
下一代基于包交換的無線通信網(wǎng)絡(luò)將采用合適的機(jī)會(huì)調(diào)度方法為用戶提供服務(wù)[1-3].在系統(tǒng)中用戶都為無服務(wù)質(zhì)量要求,且有無限下行業(yè)務(wù)需求的全負(fù)載場景下,較好的機(jī)會(huì)調(diào)度算法則需要同時(shí)兼顧效率及公平,即在系統(tǒng)總吞吐量盡可能大的同時(shí),要保證不同位置用戶得到的資源數(shù)盡可能相等.對于全負(fù)載場景中現(xiàn)有機(jī)會(huì)調(diào)度算法中,比例公平調(diào)度已被深入研究,該算法可在效率和公平之間得到一個(gè)較好的折中[4-5].假設(shè)所有用戶經(jīng)歷獨(dú)立同分布信道,比例公平調(diào)度在公平分配資源的同時(shí)可較好地利用信道動(dòng)態(tài)變化.但在實(shí)際系統(tǒng)中,它會(huì)偏愛離基站較近的用戶,并給這些用戶分配較多資源[6-7].而基于用戶自身速率特性的調(diào)度,如基于“得分”的調(diào)度[7]或基于用戶自身速率累積分布的調(diào)度[8-9]就不存在這個(gè)問題.從較長的時(shí)間來看,它們可在公平分配系統(tǒng)資源的同時(shí)較好地利用信道的動(dòng)態(tài)變化.本文首先通過計(jì)算機(jī)數(shù)值仿真,比較了輪詢調(diào)度、最大速率調(diào)度、比例公平調(diào)度和基于用戶自身速率累積分布調(diào)度.仿真結(jié)果顯示,比例公平調(diào)度和基于用戶自身速率累積分布調(diào)度都可做到一定程度上效率與公平的折中.兩者相比,后者效率略低,但公平性更好.當(dāng)所有用戶以絕對的公平方式分配相等資源時(shí),后者可得到最大的吞吐量,說明該方法相比較其他三者可更好地利用信道的動(dòng)態(tài)變化,得到更高的效率.從這個(gè)意義上講,基于用戶自身速率累積分布調(diào)度是上述4種調(diào)度算法中的最優(yōu)算法.
對于采用機(jī)會(huì)調(diào)度算法系統(tǒng)中的任意用戶,通過短時(shí)間內(nèi)的檢測結(jié)果預(yù)測其長時(shí)平均性能十分重要,在該系統(tǒng)的算法設(shè)計(jì)中必不可少.因此,本文推導(dǎo)了以上4種調(diào)度算法中的最優(yōu)算法,即基于用戶自身速率累積分布調(diào)度算法的多用戶分集增益[10].多用戶分集增益是指以輪詢調(diào)度為基準(zhǔn),每個(gè)用戶由于采用了機(jī)會(huì)調(diào)度算法利用信道動(dòng)態(tài)變化可以得到的吞吐量與采用輪詢調(diào)度可以得到的吞吐量之比.現(xiàn)有的多用戶分集增益研究,僅對比例公平調(diào)度在所有用戶經(jīng)歷獨(dú)立同分布瑞利衰落信道時(shí)進(jìn)行了推導(dǎo),而缺乏對于其他調(diào)度算法及比例公平調(diào)度在實(shí)際的非獨(dú)立同分布場景中的研究.這是由于不同調(diào)度算法本身特性的差異,因此多用戶分集增益是與參與調(diào)度的總用戶數(shù)及所有用戶信道特性相關(guān)的復(fù)雜多重積分[11].而對于基于用戶自身速率累積分布的調(diào)度算法,理論分析結(jié)果顯示其多用戶分集增益只與參與競爭的用戶數(shù)及每個(gè)用戶自身經(jīng)歷的信道狀態(tài)特性有關(guān),且可適用于用戶經(jīng)歷任意分布的獨(dú)立信道,并不局限于同分布的信道.仿真結(jié)果驗(yàn)證了該多用戶分集增益數(shù)學(xué)推導(dǎo)結(jié)果的準(zhǔn)確性,可用于系統(tǒng)級(jí)的算法設(shè)計(jì),如呼叫準(zhǔn)入控制算法、動(dòng)態(tài)負(fù)載均衡算法等.
1)輪詢調(diào)度 該算法使得參與調(diào)度的每個(gè)用戶依次得到調(diào)度機(jī)會(huì),從用戶可得資源的角度來說是最為公平的方式.
2)最大速率調(diào)度 該算法在每個(gè)調(diào)度機(jī)會(huì)上都選擇瞬時(shí)速率最大的用戶進(jìn)行調(diào)度,從系統(tǒng)總吞吐量角度來說是效率最優(yōu)的方式.該算法計(jì)算式為
式中,rk為用戶k在當(dāng)前調(diào)度機(jī)會(huì)上的瞬時(shí)可得速率;n為參與調(diào)度的用戶數(shù).
3)比例公平調(diào)度 該算法在每個(gè)調(diào)度機(jī)會(huì)上選擇當(dāng)前瞬時(shí)速率與前一段調(diào)度機(jī)會(huì)上平均實(shí)際可得速率之比最大的用戶進(jìn)行調(diào)度,在一定程度上做到了效率與公平的折中.該算法計(jì)算式為
式中表示用戶k在前一段調(diào)度機(jī)會(huì)上的平均
式中,F(xiàn)k(rk)表示用戶k對應(yīng)于瞬時(shí)可得速率rk的速率累積分布函數(shù)值.
假設(shè)由用戶反饋到基站的信道狀態(tài)信息無誤差且無延時(shí),使用香農(nóng)容量來進(jìn)行分析,忽略由于實(shí)際的調(diào)制編碼方案帶來的量化誤差.每次調(diào)度機(jī)會(huì)對應(yīng)的調(diào)度單位大小符合LTE系統(tǒng)中物理資源塊的定義,即頻域上180 kHz,時(shí)域上為1 ms.每次仿真有10個(gè)用戶參與調(diào)度,競爭10 000個(gè)調(diào)度機(jī)會(huì),每個(gè)用戶的平均信干噪比在-10~+20 dB間隨機(jī)取值,參考的快衰落模型為瑞利衰落.使用所有用戶總吞吐量及每用戶實(shí)際得到的調(diào)度機(jī)會(huì)數(shù)來比較4種調(diào)度算法的性能,并進(jìn)行1 000次仿真來得到這4種調(diào)度方法的統(tǒng)計(jì)性能.
圖1顯示了4種調(diào)度算法下,所有用戶的平均總吞吐量,此處總吞吐量是指所有用戶在各自被調(diào)度單位上的可得速率之和.如圖1所示,采用輪詢調(diào)度時(shí),系統(tǒng)實(shí)際得到的總吞吐量最低,這是由于輪詢調(diào)度按先后順序依次調(diào)度每個(gè)用戶,并沒有利用信道快衰落帶來的動(dòng)態(tài)變化.而最大速率調(diào)度,由于其在每個(gè)調(diào)度機(jī)會(huì)上都選擇當(dāng)前可得速率最大的用戶,所以該調(diào)度算法的總吞吐量最大.比例公平調(diào)度和基于用戶自身速率累積分布調(diào)度,其系統(tǒng)總吞吐量居于最大速率調(diào)度與輪詢調(diào)度之間,其中基于用戶自身速率累積分布調(diào)度的總吞吐量略低于比例公平調(diào)度,這說明比例公平調(diào)度的效率略高,但代價(jià)是圖2中公平性的損失較大.實(shí)際可得速率.
4)速率累積分布調(diào)度 該算法在每個(gè)調(diào)度機(jī)會(huì)上選擇瞬時(shí)速率所對應(yīng)的速率累積分布函數(shù)值最大的用戶進(jìn)行調(diào)度,最好地利用了信道的動(dòng)態(tài)變化.該算法計(jì)算式為
圖1 4種調(diào)度算法下用戶總吞吐量
圖2 4種調(diào)度算法下調(diào)度機(jī)會(huì)的累積分布
圖2給出了4種調(diào)度算法下用戶得到調(diào)度機(jī)會(huì)的累積分布曲線,反映了不同用戶得到調(diào)度機(jī)會(huì)的公平程度.由圖可見,輪詢調(diào)度時(shí)所有用戶得到的調(diào)度機(jī)會(huì)都為1 000,這與仿真場景設(shè)置參數(shù)一致,即所有用戶都公平地得到被調(diào)度的機(jī)會(huì),這也是該調(diào)度算法的本質(zhì),保證了用戶間得到調(diào)度機(jī)會(huì)的絕對公平性.而最大速率調(diào)度,由于其一直調(diào)度有最大瞬時(shí)速率的用戶,其累積分布曲線在0~10 000間分布較廣,并有50%以上的用戶得到的調(diào)度機(jī)會(huì)為0,其用戶間得到調(diào)度機(jī)會(huì)的公平性最差.比例公平調(diào)度和基于用戶自身速率累積分布調(diào)度,兩者在一定程度上都較好地保證了不同位置用戶得到調(diào)度機(jī)會(huì)的公平性,這2條曲線都在標(biāo)準(zhǔn)值1 000附近.從圖2中的放大圖中可以看到,相對于比例公平調(diào)度,基于用戶自身速率累積分布調(diào)度中用戶得到的調(diào)度機(jī)會(huì)更接近標(biāo)準(zhǔn)值1 000,說明其對公平性的保證更好.參考圖1與圖2,相對于基于用戶自身速率累積分布調(diào)度,比例公平調(diào)度公平性較差,而效率略高,說明該調(diào)度算法也會(huì)偏愛平均信干噪比較高的用戶,并給其分配較多的調(diào)度機(jī)會(huì),這與文獻(xiàn)[6-7]中的結(jié)論是一致的.也就是說,相對于前者,比例公平調(diào)度以損失公平性為代價(jià),得到總吞吐量上的略微增益.
圖3顯示了當(dāng)用戶間絕對公平分配調(diào)度機(jī)會(huì)時(shí),所有用戶可以得到的總吞吐量.所謂絕對公平地分配調(diào)度機(jī)會(huì),就是按各自的調(diào)度算法實(shí)際調(diào)度,當(dāng)某用戶得到1 000個(gè)調(diào)度機(jī)會(huì),它就退出調(diào)度過程.圖3充分說明了基于用戶自身速率累積分布調(diào)度相對于其他3種調(diào)度方法的優(yōu)越性.可以看到,該調(diào)度算法的總吞吐量最大,說明在保證用戶間資源分配絕對公平時(shí),該調(diào)度算法相對于其他三者,能更好地利用信道快衰落帶來的動(dòng)態(tài)變化,得到更好的調(diào)度效率.
圖3 絕對公平調(diào)度時(shí)4種調(diào)度算法下用戶總吞吐量
基于以上仿真結(jié)果,可認(rèn)為基于用戶自身速率累積分布的調(diào)度算法是上述4種調(diào)度算法中的最優(yōu)算法,它可以在保證用戶間資源分配公平性的同時(shí)達(dá)到最大的吞吐量.而對于該調(diào)度算法,缺乏其長時(shí)平均性能的分析,而這在采用該調(diào)度算法的系統(tǒng)算法設(shè)計(jì)過程中是必不可少的,所以本文將對該調(diào)度算法的長時(shí)平均性能,即以輪詢調(diào)度為比較基準(zhǔn)的多用戶分集增益進(jìn)行理論推導(dǎo).
用Rk,fRk和FRk來分別表示任意用戶k速率的隨機(jī)變量,以及該隨機(jī)變量的概率密度函數(shù)和累積分布函數(shù).基于用戶自身速率累積分布的調(diào)度,其主要思想是在每個(gè)調(diào)度機(jī)會(huì)上,選擇速率累積分布函數(shù)值最大的用戶進(jìn)行調(diào)度,即相對于其他用戶,被選用戶的瞬時(shí)速率更接近于其自身由于快衰落可得的最高速率.假設(shè)Rk在一個(gè)調(diào)度單元上的瞬時(shí)值為rk,則在所有參與調(diào)度用戶中,F(xiàn)Rk*(rk*)值最大的用戶k*被選擇為服務(wù)用戶.假設(shè)系統(tǒng)中共有n個(gè)服務(wù)用戶,則基于用戶自身速率累積分布的調(diào)度方法如式(3)所示.
眾所周知,F(xiàn)Rk(Rk)在[0,1]之間是均勻分布的[12].令 Uk=FRk(Rk),則 Uk也是[0,1]之間的均勻分布.對于用戶k,當(dāng)其瞬時(shí)速率為rk時(shí),它被選中進(jìn)行調(diào)度的概率為
式中,uk=FRk(rk).則用戶k得到服務(wù)的概率為這表示基于用戶自身速率累積分布的調(diào)度將給系統(tǒng)中的所有用戶平均分配資源.該結(jié)論也可以由圖2中每個(gè)用戶得到調(diào)度機(jī)會(huì)的累積分布曲線得到驗(yàn)證.假設(shè)FRk(·)是一個(gè)連續(xù)單調(diào)上升函數(shù),對于實(shí)際的物理信道,該假設(shè)是合理的.對于FRk(·)必然有唯一的反函數(shù)F-1Rk(·),則用戶k在其得到服務(wù)的每個(gè)調(diào)度單元上的速率分布與F-1Rk(·)是一致的.因此,采用基于用戶自身速率累積分布的調(diào)度時(shí),用戶k的長時(shí)平均吞吐量為
用Dn,k表示相同場景下,采用輪詢調(diào)度用戶k可以得到的長時(shí)平均吞吐量.則Dn,k可以看作式(5)在服務(wù)用戶數(shù)n=1,可用資源數(shù)為1/n時(shí)的情況,即
定義當(dāng)存在n個(gè)服務(wù)用戶,并采用基于用戶自身速率累積分布調(diào)度時(shí),對于任一用戶k的多用戶分集增益為 Gn,k,其為 Tn,k與 Dn,k之比,即
式(7)推導(dǎo)的多用戶分集增益適用于現(xiàn)實(shí)中所有的物理信道,只需統(tǒng)計(jì)該用戶經(jīng)歷的快衰落信道所對應(yīng)的通信速率的累積分布特性,就可以得到采用基于用戶自身速率累積分布調(diào)度方法時(shí)的多用戶分集增益.下面以瑞利衰落信道為例進(jìn)行說明.
當(dāng)用戶k只考慮路徑損耗和陰影衰落時(shí)的平均信干噪比λk和信道經(jīng)歷瑞利快衰落時(shí),用戶k的實(shí)際瞬時(shí)信干噪比t滿足均值為λk的指數(shù)分布,其相應(yīng)的累積分布函數(shù)為則對應(yīng)于信干噪比t,在參考帶寬為B時(shí),用戶k的速率Y為
其相應(yīng)的累積分布函數(shù)為
對式(10)求反函數(shù),就可以得到多用戶分集增益 Gn,k計(jì)算中所需的 F-1Rk(uk),即
在快衰落為瑞利衰落的情況下,式(7)的多用戶分集增益為
由式(12)可見,當(dāng)采用基于用戶自身速率累積分布調(diào)度時(shí),對其中任意用戶k的多用戶分集增益,只與參與調(diào)度的用戶數(shù)n、用戶k自身由于路徑損耗和陰影衰落得到的平均信干噪比λk,及用戶k本身由于所處位置與周圍環(huán)境帶來的信道快衰落特性有關(guān),與調(diào)度單位的帶寬及其他用戶的快衰落環(huán)境無關(guān).
本節(jié)對于式(12)中推導(dǎo)得到的多用戶分集增益Gn,k進(jìn)行仿真驗(yàn)證.將式(12)通過數(shù)值積分計(jì)算出的結(jié)果作為理論值,將實(shí)際采用基于用戶自身速率累積分布調(diào)度與輪詢調(diào)度得到的吞吐量之比作為實(shí)際結(jié)果,并比較實(shí)際結(jié)果與理論分析結(jié)果的一致性,并假設(shè)最小調(diào)度單元滿足3GPP LTE物理資源塊的定義標(biāo)準(zhǔn).
圖4驗(yàn)證了某一特定用戶的分集增益隨總用戶數(shù)的變化情況.對應(yīng)于每個(gè)用戶數(shù)進(jìn)行了100次仿真.由圖4可發(fā)現(xiàn),隨著用戶數(shù)的增多,該用戶的多用戶分集增益的理論值與實(shí)際均值逐步上升.這是由于隨著用戶增多,每個(gè)用戶有更多的機(jī)會(huì)等到其信道狀態(tài)足夠好時(shí)才被調(diào)度,這樣被調(diào)度時(shí)其實(shí)際可得速率更接近其速率分布的峰值速率,相應(yīng)的調(diào)度效率也越高,多用戶分集增益也越大.從圖4還可發(fā)現(xiàn),該用戶分集增益的理論值與實(shí)際均值兩者吻合得非常好,誤差低于0.1%,很好地驗(yàn)證了式(12)的正確性.
圖5顯示的是任選10個(gè)用戶(用戶序號(hào)1~10,對應(yīng)的平均信干噪比分別為1,2,…,10 dB),每個(gè)用戶的多用戶分集增益的理論值與實(shí)際值的比較.可看出,實(shí)際仿真100次后平均的結(jié)果與理論值基本重合,說明式(12)對于相同數(shù)目的服務(wù)用戶,由于用戶所處位置不同帶來的不同平均信干噪比的多用戶分集增益預(yù)估的準(zhǔn)確性.還可以發(fā)現(xiàn),隨著1~10號(hào)用戶平均信干噪比的上升,其相應(yīng)的多用戶分集增益是在逐步降低的.這說明基于用戶自身速率累積分布的調(diào)度方法,在保證用戶間可得資源的公平性的同時(shí),對于平均信干噪比較低也即信道條件較差的用戶(如邊緣用戶)有較大的增益.
圖4 特定用戶隨用戶數(shù)增加時(shí)的多用戶分集增益
圖5 多個(gè)用戶分集增益實(shí)際值與理論值比較
首先比較了全負(fù)載場景下的4種常用調(diào)度算法(輪詢調(diào)度、最大速率調(diào)度、比例公平調(diào)度和基于用戶自身速率累積分布的調(diào)度),分析結(jié)果顯示,基于用戶自身速率累積分布的調(diào)度在保證公平性的前提下可以達(dá)到最高的效率,是以上4種調(diào)度算法中的最優(yōu)算法.然后,對該調(diào)度算法的長時(shí)平均性能即其多用戶分集增益進(jìn)行了理論推導(dǎo).該分集增益可以利用短時(shí)間內(nèi)對用戶信道的檢測結(jié)果預(yù)測用戶的長時(shí)平均性能,從而進(jìn)行系統(tǒng)級(jí)的算法設(shè)計(jì),且可適用于實(shí)際系統(tǒng)中用戶經(jīng)歷任意分布的獨(dú)立信道情況.計(jì)算機(jī)仿真結(jié)果驗(yàn)證了對于該調(diào)度算法多用戶分集增益理論分析的準(zhǔn)確性.
[1]Kwan R,Leung C.A survey of scheduling and interference mitigation in LTE [J].Journal of Electrical and Computer Engineering,2010,2010:273486.
[2]Li L,Pesavento M,Gershman Alex B.Downlink opportunistic scheduling with low-rate channel state feedback:error rate analysis and optimization of the feedback parameters[J].IEEE Transactions on Communications,2010,58(10):2871-2880.
[3] Oyman O.Opportunistic scheduling and spectrum reuse in relay-based cellular networks[J].IEEE Transactions on Wireless Communication,2010,9(3):1074-1085.
[4] Viswanath P,Tse D N C,Laroia R.Opportunistic beamforming using dumb antennas[J].IEEE Transactions on Information Theory,2002,48(6):1277-1294.
[5] Andrews M.Instability of the proportional fair scheduling algorithm for HDR [J].IEEE Transactions on Wireless Communication,2004,3(5):1422-1426.
[6] Wang H,Ding L,Pan Z,et al.QoS guaranteed call admission control with opportunistic scheduling[C]//IEEE Global Telecommunications Conference.Houston,USA,2011:1-5.
[7] Bonald T.A score-based opportunistic scheduler for fading radio channels[C]//Proceedings of European Wireless Conference.Barcelona,Spain,2004:283-292.
[8]Park D,Seo H,Kwon H,et al.Wireless packet scheduling based on the cumulative distribution function of user transmission rates[J].IEEE Transactions on Communications,2005,53(11):1919-1929.
[9]Patil S,de Veciana G.Measurement-based opportunistic scheduling for heterogeneous wireless systems [J].IEEE Transactions on Communications,2009,57(9):2745-2753.
[10]Soydan Y,Candan C.A feedback quantization scheme leveraging fairness and throughput for heterogeneous multi-user diversity systems[J].IEEE Transactions on Vehicular Technology,2010,59(5):2610-2614.
[11]Combes R,Altman Z,Altman E.On the use of packet scheduling in self-optimization processes:application to coverage-capacity optimization[C]//Symposium on Modeling and Optimization in Mobile,Ad Hoc,and Wireless Networks.Avignon,F(xiàn)rance,2010:98-107.
[12] Angus J E.The probability integral transform and related results[J].SIAM Review,1994,36(4):652-654.
Analysis of long-term average performance of optimal scheduling scheme in full-load scenario
Wang Hao Li Zhihang Jiang Huilin Pan Zhiwen You Xiaohu
(National Mobile Communications Research Laboratory,Southeast University,Nanjing 210096,China)
Four well-known scheduling schemes in full-load scenario,namely,round robin scheduling,max-rate scheduling,proportional fairness scheduling and cumulative rate distribution based scheduling are investigated.Results show that the last one achieves the best efficiency with a relative better fairness guarantee,which is the optimal scheme among all the four ones.Then,the probability deduction method is adopted to analyze its multi-user diversity gain,which uses round robin scheduling as the benchmark.The result can be used to predict the long-term average performance of the scheme through short-time statistical results and is applicable to all practical scenarios.The accuracy of the analysis results are verified by numerical simulations,in which the error between theory analysis and actual scheduling is less than 0.1%.
round robin scheduling;max-rate scheduling;proportional fairness scheduling;rate cumulative distributed function based scheduling;multi-user diversity gain
TN92
A
1001-0505(2012)02-0199-05
10.3969/j.issn.1001 -0505.2012.02.001
2011-10-18.
王浩(1983—),男,博士生;尤肖虎(聯(lián)系人),男,博士,教授,博士生導(dǎo)師,xhyu@seu.edu.cn.
國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃)資助項(xiàng)目(2012CB316004)、國家科技重大專項(xiàng)資助項(xiàng)目(2011ZX03003-002-02)、江蘇省“六大人才”高峰資助項(xiàng)目、江蘇省普通高校研究生科研創(chuàng)新計(jì)劃資助項(xiàng)目(CXLX_0116)、東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目(2010A02,2011A02).
王浩,李知航,蔣慧琳,等.全負(fù)載場景中最優(yōu)調(diào)度算法長時(shí)平均性能分析[J].東南大學(xué)學(xué)報(bào):自然科學(xué)版,2012,42(2):199-203.[doi:10.3969/j.issn.1001 -0505.2012.02.001]