李精華,嵇建波

(桂林航天工業(yè)高等?？茖W(xué)校 電子工程系, 廣西 桂林541004)

1 引 言

無線網(wǎng)狀網(wǎng)作為下一代的無線網(wǎng)絡(luò)技術(shù),必然要求它能夠傳輸高速的多種數(shù)據(jù)業(yè)務(wù),支持這些業(yè)務(wù)關(guān)鍵就是要保證業(yè)務(wù)的QoS 要求[1],與QoS 密切相關(guān)的技術(shù)就是如何為網(wǎng)絡(luò)設(shè)計合適的包調(diào)度算法。包調(diào)度算法就是通過對數(shù)據(jù)包進(jìn)行緩存,控制數(shù)據(jù)包的發(fā)送時間和發(fā)送次序。

目前的無線包調(diào)度算法主要集中在保障網(wǎng)絡(luò)各連接的QoS 前提下,追求系統(tǒng)吞吐量極大化,是基于數(shù)據(jù)包所屬的“類”或“流”來進(jìn)行調(diào)度的,在進(jìn)行調(diào)度時,調(diào)度器首先會把應(yīng)用業(yè)務(wù)分成不同的“類”或“流”,并給這些業(yè)務(wù)流賦予不同的優(yōu)先級,然后調(diào)度器根據(jù)這個優(yōu)先級來對數(shù)據(jù)包進(jìn)行調(diào)度,比如EDF調(diào)度算法就屬于這種。這樣的調(diào)度策略有一個典型的缺點,就是當(dāng)網(wǎng)絡(luò)增加一類新的服務(wù)時就需要對調(diào)度器進(jìn)行相應(yīng)的配置,使它能支持相應(yīng)的服務(wù),因此傳統(tǒng)調(diào)度算法的可擴(kuò)展性是一個不容忽視的問題。另外,傳統(tǒng)調(diào)度器對應(yīng)用業(yè)務(wù)的分類不細(xì),從而會導(dǎo)致一些低優(yōu)先級的包長時間得不到服務(wù)。

基于以上算法的弱點,本文提出一種分布式隊列服務(wù)算法(DQS),能根據(jù)數(shù)據(jù)包所經(jīng)過端到端的變化情況進(jìn)行動態(tài)的調(diào)度。DQS 算法為網(wǎng)絡(luò)提供更為細(xì)化的應(yīng)用業(yè)務(wù),在保證實時用戶的QoS 需求的前提下,充分考慮用戶的公平性,實現(xiàn)最大化系統(tǒng)的吞吐量。

2 分布式隊列服務(wù)算法(DQS)描述

差分隊列服務(wù)算法[2]目的是為了在有線網(wǎng)絡(luò)中為各類數(shù)據(jù)業(yè)務(wù)提供更加細(xì)化的QoS,主要優(yōu)點是能夠根據(jù)資源的利用情況給業(yè)務(wù)應(yīng)用提供更加細(xì)化的端到端QoS 服務(wù)。其算法的基本原理是:設(shè)一個網(wǎng)路由n 個節(jié)點組成,數(shù)據(jù)包的傳輸路徑是固定不變的,在不考慮傳播延時,當(dāng)一個數(shù)據(jù)包到達(dá)節(jié)點i時,該數(shù)據(jù)包端到端的剩余延時為

其中,T 為數(shù)據(jù)包的最大的端到端延時, τi為數(shù)據(jù)包經(jīng)過i 所花費的實際延時。這樣,數(shù)據(jù)包在某個節(jié)點所允許最大有效延時δi為

如果上游的節(jié)點都按固定的算法限制了每個數(shù)據(jù)包的延時,那么就可以得:

其中,yi為數(shù)據(jù)包到達(dá)某個節(jié)點的時間;xi為數(shù)據(jù)包離開某個節(jié)點最近的時間,這個時間被用來作為包在緩存中排隊順序的依據(jù)。

由式(1)～(3)可以看出,差分隊列服務(wù)算法對數(shù)據(jù)包進(jìn)行調(diào)度的依據(jù)是端到端的延時而不是根據(jù)數(shù)據(jù)包所屬的數(shù)據(jù)流或類。通過這種方式,差分隊列服務(wù)算法可以為應(yīng)用業(yè)務(wù)提供更加細(xì)化的QoS 支持。在無線網(wǎng)格網(wǎng)中利用差分隊列服務(wù)算法為應(yīng)用業(yè)務(wù)提供端到端QoS 的支持是很有益處的,但公式(2)中節(jié)點i 是利用δj(j >i)來推導(dǎo)公式(3)中的xi,這在無線網(wǎng)絡(luò)中是很困難的,因為δj只能在將來的某個時刻得到,而不可能在數(shù)據(jù)包到達(dá)本節(jié)點時計算出來。因此實現(xiàn)DQS 算法一個很重要的問題就是如何在節(jié)點i 去估計δj的值,也就是說如何去估計數(shù)據(jù)包在剩余路徑的延時情況。

分布式貝爾曼-福特算法[3]是在貝爾曼-福特算法基礎(chǔ)上演進(jìn)出來的可預(yù)測表驅(qū)動路由算法,也就是說每一個節(jié)點都會維護(hù)一個路由表,每一個節(jié)點都會初始化一個到它相鄰節(jié)點的距離矢量表。比如有一條鏈路,它由6 個節(jié)點組成,節(jié)點1 在某個時刻t 1發(fā)送出去一個探測包,在時刻t 2節(jié)點2 收到這個探測包,則節(jié)點1 到節(jié)點2 的單步延時為t1-t2,此時為節(jié)點2 創(chuàng)建一個時延表,這個表用來記錄經(jīng)過節(jié)點2 的所有數(shù)據(jù)包的延時情況。同時,為了讓節(jié)點2 能夠知道其他節(jié)點間的延時情況,必須要求每個節(jié)點在發(fā)送探測包的同時把自己的時延表也發(fā)送出去。這樣經(jīng)過一段時間后節(jié)點2 就能夠知道這條鏈路中任意兩個節(jié)點之間的延時了,這個時延表如表1 所示。

表1 節(jié)點2 中的時延表Table 1 Delay table at node 2

根據(jù)表1 所示的時延表,當(dāng)一個數(shù)據(jù)包到達(dá)節(jié)點時DQS 調(diào)度器可以通過查詢表1 所示的延時表來知道數(shù)據(jù)包在剩余路徑的延時情況,然后通過公式(2)計算出數(shù)據(jù)包在本節(jié)點的最遲離開時間,DQS調(diào)度器會根據(jù)離開時間的大小對數(shù)據(jù)包進(jìn)行排隊。離開時間越小表示數(shù)據(jù)包需要越早得到服務(wù),反之說明數(shù)據(jù)包可以在節(jié)點里停留相對較長的時間,因此可以把它放在隊列的后面。

3 分布式隊列服務(wù)算法性能分析

這里使用Ad Hoc 網(wǎng)絡(luò)仿真模型[4],在NS2 仿真平臺上進(jìn)行仿真分析[5]。

3.1 探測包性能

數(shù)據(jù)包在剩余路徑所經(jīng)歷的時延估計主要是通過路由層發(fā)送探測包得到的,探測包發(fā)送的目的是為了估計當(dāng)前網(wǎng)絡(luò)的延時情況,即探測包的延時反映了網(wǎng)絡(luò)當(dāng)前的延時情況,探測包的延時小網(wǎng)絡(luò)則當(dāng)前的擁塞小,探測包的延時大則網(wǎng)絡(luò)擁塞也大。一般探測包的數(shù)量隨著探測周期的變大而減少,探測包的數(shù)量可以通過理論公式(4)計算:

式中,N 表示節(jié)點數(shù),L 表示仿真的時間長度, T 表示探測包的發(fā)送周期, n 表示仿真過程中總共發(fā)送多少探測包。

在NS 仿真平臺上對7 個節(jié)點的探測包數(shù)量在不同的發(fā)送周期下進(jìn)行仿真分析,仿真場景采用CBR 流和VBR 流共存的方式,使用線性拓?fù)浣Y(jié)構(gòu),路徑長度為6,仿真時間為500 s。圖1 是7 個節(jié)點的探測包的數(shù)量在不同發(fā)送周期下的曲線變化圖。從圖1 可以看出,當(dāng)時延探測包發(fā)送周期為1 s時,節(jié)點在仿真過程中總共發(fā)送出約3 500個探測包;當(dāng)時延探測包發(fā)送周期為12 s時,節(jié)點在仿真過程中總共發(fā)送出290 個探測包。仿真結(jié)果與公式(4)計算出來的結(jié)果是相吻合的,從而驗證了DQS 調(diào)度算法的探測包的延時符合設(shè)計需求。

圖1 不同探測周期下的探測包數(shù)量Fig.1 The number of hello packet in different period

3.2 緩沖區(qū)的使用率

在DQS 調(diào)度算法中使用了控制包隊列和數(shù)據(jù)包隊列兩個隊列,NS 仿真使用CBR 流和VBR 流,線性拓?fù)浣Y(jié)構(gòu),7 個節(jié)點數(shù),仿真總時間是500 s,每個隊列的最大長度為50 個包,探測包的發(fā)送周期每3 s發(fā)送一次。對控制包隊列和數(shù)據(jù)包隊列在每個節(jié)點的使用情況進(jìn)行統(tǒng)計,計算每個節(jié)點隊列的平均使用率和最大使用長度。圖2 為控制包隊列中每個節(jié)點在整個仿真周期內(nèi)的使用情況。從圖2(a)可以看出,中間節(jié)點隊列的使用率最高,這也表明中間節(jié)點最可能成為網(wǎng)絡(luò)的瓶頸節(jié)點。圖2(b)是每個節(jié)點中控制隊列的最大使用長度,最大使用長度是指節(jié)點在最繁忙時最多需要處理多少個包,圖2(b)的中間部分最高,表明需要處理的包數(shù)量最多。因此從圖2 中可以看出,控制包在中間節(jié)點會等待較長的時間,這與實際情況也是吻合的。

圖2 控制包隊列的統(tǒng)計Fig.2 Statistic of control packet queue

圖3 為數(shù)據(jù)包隊列在每個節(jié)點的使用情況,其曲線的趨勢與控制包隊列基本相似。在DQS 調(diào)度算法中,由于控制包和數(shù)據(jù)包的發(fā)送速率以及處理優(yōu)先級是不同的,其中數(shù)據(jù)包的優(yōu)先級比控制包的優(yōu)先級低,因此從圖2 和圖3 可以看出,數(shù)據(jù)包隊列的平均利用率比較高,但數(shù)據(jù)包隊列要比控制包隊列要長。

圖3 數(shù)據(jù)包隊列的統(tǒng)計Fig.3 Statistic of data packet queue

從圖2 和圖3 中可以看出,DQS 算法對緩存的要求不高,這樣可以節(jié)省更多的緩存空間。

3.3 實際平均吞吐量分析

實際平均吞吐量[6]是指數(shù)據(jù)發(fā)送者成功地傳輸給接收者的度量標(biāo)準(zhǔn),即接收端成功接收到的包個數(shù)與發(fā)送端發(fā)送的包個數(shù)的一個比值。為了便于仿真分析,在這里接收端只計算那些滿足端到端延時的數(shù)據(jù)包個數(shù)。在NS 仿真中采用隨機(jī)拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu),運用恒速比特率(CBR)和變速比特率(VBR)兩種數(shù)據(jù)源,每一個隊列的長度是50 個數(shù)據(jù)包,通過改變數(shù)據(jù)源的個數(shù)和節(jié)點的個數(shù)來模擬真實網(wǎng)絡(luò)中的情景。這里以EDF 調(diào)度算法作為參照算法與DQS 算法進(jìn)行對比分析。圖4 為DQS 調(diào)度算法和EDF 調(diào)度算法的平均實際吞吐量曲線圖,其中圖4(a)使用CBR 流,圖4(b)使用VBR 流,這兩種數(shù)據(jù)源的前6 跳EDF 調(diào)度性能與DQS 調(diào)度性能相差不大,一旦數(shù)據(jù)包的路徑長度大于6 以后,DQS 調(diào)度算法平均實際吞吐量下降的程度明顯要低于EDF 調(diào)度算法。最好的情況是DQS 調(diào)度算法的實際平均吞吐量比EDF 調(diào)度算法的實際平均吞吐量性能提高了16%。其原因是DQS 調(diào)度算法充分考慮了應(yīng)用業(yè)務(wù)的端到端情況,它可以根據(jù)數(shù)據(jù)包端到端的變化來對其進(jìn)行調(diào)度;而EDF 只是在每一跳給數(shù)據(jù)包一個固定的延時,并且是基于這個延時來對數(shù)據(jù)包進(jìn)行調(diào)度,它并沒有把數(shù)據(jù)包端到端的變化情況考慮進(jìn)去。所以當(dāng)數(shù)據(jù)包路徑長度發(fā)生變化時,EDF 調(diào)度算法的實際平均吞吐量性能比DQS 調(diào)度算法的性能下降得快。

圖4 平均實際吞吐量Fig.4 Average throughput

3.4 平均端到端延時分析

平均端到端延時是指數(shù)據(jù)包從原節(jié)點到目的節(jié)點所經(jīng)歷的平均端到端延時[7]。使用的仿真條件和2.3 節(jié)的仿真條件一樣, 圖5 為DQS 調(diào)度算法和EDF 調(diào)度算法[8]的端到端延時曲線圖。

圖5 端到端延時Fig.5 The delay of end-to-end

從圖5 可以看出,DQS 調(diào)度算法的端到端延時性能比EDF 調(diào)度算法的性能好,這主要是由于DQS調(diào)度算法會把數(shù)據(jù)包的端到端延時作為一個調(diào)度因素來考慮,所以它具有更好的端到端延時性能。

4 總 結(jié)

無線網(wǎng)狀網(wǎng)作為下一代無線網(wǎng)絡(luò)的關(guān)鍵技術(shù),為其設(shè)計合適的包調(diào)度算法是一項很有挑戰(zhàn)性的工作。DQS 包調(diào)度算法解決了無線網(wǎng)狀網(wǎng)為多個等待接收服務(wù)的分組業(yè)務(wù)流安排合理的服務(wù)規(guī)則,特別是DQS 包調(diào)度算法在緩沖區(qū)的使用率、實際平均吞吐量性能和平均端到端延時性能上具有較高的性能。但還存在一些不夠完善及有待改進(jìn)的地方,比如在DQS 調(diào)度算法中控制包和業(yè)務(wù)數(shù)據(jù)包在網(wǎng)絡(luò)傳輸過程中的相互影響,如何在環(huán)境變化的無線鏈路中使探測包的周期控制在一個合適的范圍之內(nèi),在高速運動情況下的性能情況有何區(qū)別等,這些問題還需要深入研究。

[1] 劉俊芳,趙爾敦,劉巍.小無線網(wǎng)絡(luò)中基于BLUF 的包調(diào)度算法[J] .計算機(jī)工程與應(yīng)用,2008,44(16):108-110.

LIU Jun-fang, ZHAO Er-dun, LIU Wei.Wireless packet scheduling algorithm based on BLUF in wireless networks[J] .Computer Engineering and Applications, 2008,44(16):108-110.(in Chinese)

[2] Jiang S M.Granular Differentiated Queueing Services for QoS:Structure and Cost Model[ J] .ACM SIGCOMM Computer Communication Review, 2005, 35(2):13-22.

[3] Bertsekas D, Gallager R.Data Networks[ M] .Englewood Cliffs, NJ:Prentice-Hall,1987.

[4] 錢權(quán).無線Ad Hoc 網(wǎng)絡(luò)安全[M] .北京:清華大學(xué)出版社,2009.

QIAN Quan.Wireless Ad Hoc Network Security[M] .Beijing:Tsinghua University Press,2009.(in Chinese)

[5] 時慧晶, 趙燁.基于NS2 的Ad Hoc 網(wǎng)絡(luò)路由協(xié)議性能研究[C]//全國第21 屆計算機(jī)技術(shù)與應(yīng)用學(xué)術(shù)會議(CACIS·2010)暨全國第2 屆安全關(guān)鍵技術(shù)與應(yīng)用學(xué)術(shù)會議論文集.上海:[ s.n.] ,2010:17-131.

SHI Hui-jing, ZHAO Ye.Research on Performance of Ad Hoc Routing Protocol Using NS2[ C]//Proceedings of the 21th National Computer Technology and Application Conference and the National 2nd safety -critical Technology and App lication Conference.Shanghai:[ s.n.] , 2010:17 -131.(in Chinese)

[6] 顧金媛, 章國安, 包志華.認(rèn)知無線mesh 網(wǎng)中聯(lián)合路由的分布式信道分配算法[J] .計算機(jī)應(yīng)用研究,2010(9):3476-3479.

GU Jin-yuan,ZHANG Guo-an, BAO Zhi-hua.Distributed joint routing and channel assignment algorithm in cognitive wireless mesh networks[ J] .App lication Research of Computers, 2010(9):3476-3479.(in Chinese)

[ 7] 陳潛,劉云.動態(tài)高速環(huán)境下Ad Hoc 路由協(xié)議研究[J] .中北大學(xué)學(xué)報(自然科學(xué)版),2011(10):579-582.

CHEN Qian,LIU Yun.Research on Ad Hoc Routing Protocol in High Speed Dynamic Environment[ J] .Journal of North University of China(Natural Science Edition), 2011(10):579-582.(in Chinese)

[ 8] Guerin R,Peris V.Quality-of-service in packet networks:Basic mechanisms and directions [ J] .Computer Networks,1999, 31(3):169-189.