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