摘 要: 提出了一種結(jié)合預(yù)留資源進(jìn)行補(bǔ)償?shù)臒o線公平調(diào)度算法,。當(dāng)系統(tǒng)呼叫切換頻率很低時，將預(yù)留資源的空閑部分中的一部分用于補(bǔ)償,，以提高系統(tǒng)的資源利用率,；當(dāng)系統(tǒng)呼叫切換頻率很高時,，進(jìn)行補(bǔ)償?shù)臉I(yè)務(wù)流均為那些獲得額外服務(wù)的業(yè)務(wù)流,，本算法應(yīng)用在系統(tǒng)呼叫的切換頻率很低的情況下,，可以充分利用頻帶資源的優(yōu)勢。
關(guān)鍵詞: 預(yù)留資源,；無線網(wǎng)絡(luò),；算法
隨著無線網(wǎng)絡(luò)的發(fā)展，移動通信用戶數(shù)和Internet用戶數(shù)急劇增加,，人們期望新一代移動通信系統(tǒng)不僅具有更大的容量,，還要支持移動多媒體業(yè)務(wù),，除了提供話音業(yè)務(wù)外，還支持低/高速數(shù)據(jù),、圖像等非話音業(yè)務(wù)的傳輸,。不同業(yè)務(wù)有不同的服務(wù)質(zhì)量(QoS)要求,，如對時延,、誤比特率,、數(shù)據(jù)速率的要求不同,。無線網(wǎng)絡(luò)設(shè)計有兩大目標(biāo):一是保證各類業(yè)務(wù)的QoS要求,，二是使網(wǎng)絡(luò)的資源利用率達(dá)到最大，這就需要借助于無線資源管理,。而目前的無線分組調(diào)度算法主要集中在保障各連接的QoS前提下,，追求系統(tǒng)吞吐量極大化,，也就是系統(tǒng)利用率的提高。但是系統(tǒng)吞吐量極大化與公平服務(wù)是一對矛盾,。大多數(shù)算法的公平性主要體現(xiàn)在長期上,，而未考慮短期公平性的問題,，也就是未考慮無線信道特殊性引入的補(bǔ)償問題:當(dāng)一個連接的鏈路從故障恢復(fù)后，如何對這個連接進(jìn)行有效的補(bǔ)償是值得研究的,。這些補(bǔ)償方式從某種程度上說也是不公平的,，因為從完全公平的角度出發(fā),，應(yīng)該是那些得到額外服務(wù)的連接對滯后流做出補(bǔ)償,。因此，在無線網(wǎng)絡(luò)中對預(yù)留資源進(jìn)行補(bǔ)償?shù)臒o線公平調(diào)度算法進(jìn)行研究具有重要意義,。
1 應(yīng)用預(yù)留資源進(jìn)行補(bǔ)償?shù)臒o線網(wǎng)絡(luò)公平調(diào)度算法的描述
由于采用了加權(quán)的調(diào)度算法,，額外帶寬的分配直接隱含在連接獲得的總帶寬分配中,，這是由于加權(quán)調(diào)度算法中每一個連接獲得的帶寬滿足公式(1),。
算法描述如下:
(1)當(dāng)進(jìn)入系統(tǒng)的切換呼叫頻率不高時, 此時預(yù)留資源有部分資源處于空閑狀態(tài),，將這部分資源的一部分用于補(bǔ)償,；
(2)當(dāng)進(jìn)入系統(tǒng)的切換呼叫頻率很高時，預(yù)留資源的使用率很高,，采用領(lǐng)先流釋放一部分帶寬用于補(bǔ)償，而不是將其所有帶寬都用于補(bǔ)償,，直至這個領(lǐng)先流變成同步流,。這樣做的好處是補(bǔ)償時并不中斷對領(lǐng)先流的服務(wù),。補(bǔ)償方式采用針對滯后流固定比例獲得補(bǔ)償?shù)姆绞絒1],。
為了簡化計算，算法定義一個預(yù)留資源空閑率參數(shù)S=空閑預(yù)留資源/總預(yù)留資源,，并且設(shè)定一個預(yù)留資源空閑率門限St,，當(dāng)t時刻S(t) ≥St時,，采用方式1進(jìn)行補(bǔ)償,；當(dāng)t時刻S(t) <St時,，采用方式2進(jìn)行補(bǔ)償[2],。
方式1 的計算較為簡單，滯后流直接獲得一定比例(λ)的空閑預(yù)留資源(BFR)用于補(bǔ)償,，即獲得λ×BFR的額外帶寬,。不將全部預(yù)留資源用于補(bǔ)償?shù)哪康氖菫榱吮苊庠谘a(bǔ)償過程中系統(tǒng)拒絕新的切換呼叫。
可以推得理想模式下(即所有領(lǐng)先流都完全進(jìn)行了補(bǔ)償)補(bǔ)償所需要的時間為：
假設(shè)fi連接從t1時刻開始故障,，故障時間為Ti,，補(bǔ)償時間為Xi，那么fi在Ti時刻以及補(bǔ)償結(jié)束時刻均為同步流狀態(tài),。未發(fā)生故障時間在此期間(Ti+Xi)得到的服務(wù)Si應(yīng)該等于發(fā)生故障后fi在補(bǔ)償過程中(Xi)總共得到的服務(wù)Si*,。
方式2中，算法采用了滯后流固定比例獲得補(bǔ)償?shù)臒o線公平調(diào)度算法,。針對一個滯后流l,，當(dāng)它的鏈路恢復(fù)正常時，算法直接分配其預(yù)約帶寬的固定比例Δi(0<Δi<1)用于補(bǔ)償,。這部分補(bǔ)償帶寬由領(lǐng)先流按照各自權(quán)重分配,。其方法如下列關(guān)系式所示:
式中wla*和wle*代表更新后的滯后流和領(lǐng)先流的權(quán)重，wla和wle代表更新前的滯后流和領(lǐng)先流的權(quán)重,。每當(dāng)有連接狀態(tài)發(fā)生變化時(包括監(jiān)測到故障恢復(fù),、滯后流或者領(lǐng)先流恢復(fù)成同步流)，各個相應(yīng)流的權(quán)重都根據(jù)公式進(jìn)行調(diào)整,。
由公式(1)可知補(bǔ)償時滯后流實際得到的帶寬變大,，而領(lǐng)先流得到的帶寬變小[3]。
2 應(yīng)用預(yù)留資源進(jìn)行補(bǔ)償?shù)臒o線網(wǎng)絡(luò)公平調(diào)度算法的仿真結(jié)果及分析
傳統(tǒng)調(diào)度算法采用了WF2Q+,，并且各個連接的權(quán)重直接等于其預(yù)約速率的大小,，未做歸一化處理。
2.1 所有連接均無差錯
根據(jù)其分配的權(quán)重,，根據(jù)式(1),，可知，其和有線網(wǎng)絡(luò)狀況基本一致,，這證明了系統(tǒng)在無差錯狀態(tài)下工作是正常的,。
2.2 有連接出現(xiàn)鏈路故障
選擇分組數(shù)據(jù)流3來代表出現(xiàn)信道故障的連接，鏈路在時間12 s時出現(xiàn)故障,，14 s時恢復(fù)正常,。
(1)考慮特殊情況，此時預(yù)留帶寬未被使用,，即系統(tǒng)中無預(yù)約切換呼叫,，采用方式1進(jìn)行補(bǔ)償，λ=3/4,，BFR=200 kb/s,， Flow3獲得的補(bǔ)償帶寬為3/4×200=150 kb/s。圖1為采用本算法時的仿真結(jié)果,。通過圖1可以看到,，當(dāng)Flow3的連接發(fā)生故障時（12 s～14 s），這部分額外帶寬將被分配給無故障的連接,，F(xiàn)lowl,、Flow2、Flow4獲得的發(fā)送速率均得到了提高(從圖線的斜率變化可以看出,，斜率變大),，這種變化一直持續(xù)到Flow3的連接恢復(fù)(t= 14 s)。此時Flow3開始獲得補(bǔ)償(發(fā)送速率提高),，直至補(bǔ)償結(jié)束(t=22 s),。整個補(bǔ)償過程中所有領(lǐng)先流均未對Flow3進(jìn)行補(bǔ)償(發(fā)送速率維持在初始狀態(tài))[4]。
Flow 2,、3的傳輸速率曲線如圖2所示,。Flow 1、Flow4與Flow 3類似,。
根據(jù)式(2)可以計算補(bǔ)償時間為8 s,，即補(bǔ)償在14+8=22 s時結(jié)束，圖1和圖2說明了這一點,。從圖2中可以看到,，F(xiàn)low 3在鏈路故障時傳輸速率降為0,，其額外帶寬被分配給了其他鏈路狀態(tài)良好的連接，F(xiàn)low 2的傳輸速率因此得到了提升,，根據(jù)式(1)可以計算出此時Flow 2的傳輸速率為570 kb/s,，這也在圖2中得到印證。當(dāng)Flow 3的鏈路恢復(fù)時,，補(bǔ)償開始,，F(xiàn)low 3得到了150 kb/s的補(bǔ)償帶寬，因此速率上升到750 kb/s,，而此時Flow 2并未對Flow 3進(jìn)行補(bǔ)償,，故它的速率仍然保持為初始傳輸速率400 kb/s。在補(bǔ)償結(jié)束后(22 s),，F(xiàn)low 3的速率恢復(fù)到初始傳輸速率600 kb/s. Flow 1,、Flow4的傳輸速率曲線與Flow 2的類似，這里略過[5],。
(2)系統(tǒng)中無空閑預(yù)留資源,，采用方式2進(jìn)行補(bǔ)償(針對滯后流固定比例獲得補(bǔ)償?shù)姆绞?，Δ3=1/3,。圖3為仿真結(jié)果,。通過圖3可以看到，當(dāng)Flow3的連接恢復(fù)時,，獲得額外服務(wù)的連接將自己的部分帶寬用于補(bǔ)償(斜率變小),，直到補(bǔ)償結(jié)束，各個連接的發(fā)送速率均恢復(fù)到初始狀態(tài)(斜率與原來一致),。由于采用補(bǔ)償策略為針對滯后流固定比例獲得補(bǔ)償,，補(bǔ)償耗費時間為1/Δ3倍故障時間，即6 s,。Flow 3在14+6=20 s時恢復(fù)同步流狀態(tài),。
由于這里采用的是滯后流固定比例獲得補(bǔ)償?shù)臒o線公平調(diào)度算法，因此其結(jié)果與圖1的仿真結(jié)果一致,。
圖4比較了無差錯狀態(tài)與有差錯狀態(tài)(采用方式1和方式2進(jìn)行補(bǔ)償)時Flow 4的仿真結(jié)果,。
由圖4可見，系統(tǒng)一直無差錯時,，仿真結(jié)果為一條直線,；當(dāng)系統(tǒng)有差錯時，F(xiàn)low 4將在差錯狀態(tài)時獲得額外服務(wù)(12 s～14 s),。當(dāng)采用方式1進(jìn)行補(bǔ)償時,，F(xiàn)low 4并未受影響，其獲得的額外服務(wù)未用于補(bǔ)償，這意味著整個系統(tǒng)的資源利用率得到了提高,。當(dāng)采用方式2進(jìn)行補(bǔ)償后,，補(bǔ)償結(jié)束時Flow 4狀態(tài)和無差錯狀態(tài)的仿真結(jié)果一致，也就是說采用方式2補(bǔ)償后連接所得到的實際服務(wù)在補(bǔ)償結(jié)束后與其預(yù)約的服務(wù)是一致的,。這對所有的連接都是公平的,。Flowl、Flow2的結(jié)果與Flow4類似,。
這里沒有比較Flow 3在無差錯狀態(tài)和有差錯狀態(tài)的結(jié)果，需要指出的是,，無論采用方式1還是方式2,，在補(bǔ)償結(jié)束后，F(xiàn)low 3得到的實際服務(wù)與其預(yù)約的服務(wù)是一致的,。
3 應(yīng)用預(yù)留資源進(jìn)行補(bǔ)償?shù)臒o線網(wǎng)絡(luò)公平調(diào)度算法復(fù)雜性分析
從空間復(fù)雜度上看,，算法有3N個固定存儲空間。當(dāng)采用方式1進(jìn)行補(bǔ)償時,，時間復(fù)雜度上僅需計算一次乘法和一次加法,。當(dāng)采用方式2進(jìn)行補(bǔ)償時，時間復(fù)雜度的計算與采用的算法有關(guān),，由于本算法采用了無線公平調(diào)度算法,，因此調(diào)整權(quán)重時最差情況下的時間復(fù)雜度為0(N2)。
綜上所述,，該文提出了一種無線公平調(diào)度算法——應(yīng)用預(yù)留資源進(jìn)行補(bǔ)償?shù)臒o線公平調(diào)度算法,。當(dāng)系統(tǒng)呼叫切換頻率很低時，將預(yù)留資源的空閑部分中的一部分用于補(bǔ)償,；當(dāng)系統(tǒng)呼叫切換頻率很高時,，進(jìn)行補(bǔ)償?shù)臉I(yè)務(wù)流均為那些獲得額外服務(wù)的業(yè)務(wù)流。
當(dāng)采用方式1進(jìn)行補(bǔ)償時,，直接利用預(yù)留資源中的部分空閑帶寬進(jìn)行補(bǔ)償,，這樣可以提高系統(tǒng)的資源利用率。
當(dāng)采用方式2進(jìn)行補(bǔ)償時,，算法實際是通過補(bǔ)償算法和再分配算法對各個連接的權(quán)重進(jìn)行調(diào)整,，從而實現(xiàn)補(bǔ)償。該算法對于系統(tǒng)呼叫的切換頻率很低的情況下,，可以充分利用頻帶資源的優(yōu)勢,。
參考文獻(xiàn)
[1] 紀(jì)陽,李迎陽,鄧鋼,等.一種適用于寬帶無線IP網(wǎng)絡(luò)的分組調(diào)度算法[J].電子學(xué)報,2003,31(05): 103-107.
[2] 宣孝英,石冰心,鄒玲.無線網(wǎng)絡(luò)包調(diào)度算法綜述[J].計算機(jī)工程與應(yīng)用,2003,39(17):23-24+58.
[3] 任艷穎,張文軍,王彬. 無線調(diào)度算法[J].計算機(jī)工程,2004,30(15):102-103+126.
[4] 王燕,伍博,楊豪強(qiáng),等.一種支持多業(yè)務(wù)的調(diào)度算法的研究與仿真[J].河南師范大學(xué)學(xué)報(自然科學(xué)版),2006，34(04):195-197.
[5] 宋艦,李樂民.一種支持服務(wù)類別的無線公平調(diào)度算法[J].電子學(xué)報,2004,32(01):60-64.