分布式隊列服務算法在無線網狀網包調度中的應用

李精華,嵇建波

(桂林航天工業高等專科學校 電子工程系, 廣西 桂林541004)

1 引 言

無線網狀網作為下一代的無線網絡技術,必然要求它能夠傳輸高速的多種數據業務,支持這些業務關鍵就是要保證業務的QoS 要求[1],與QoS 密切相關的技術就是如何為網絡設計合適的包調度算法。包調度算法就是通過對數據包進行緩存,控制數據包的發送時間和發送次序。

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

基于以上算法的弱點,本文提出一種分布式隊列服務算法(DQS),能根據數據包所經過端到端的變化情況進行動態的調度。DQS 算法為網絡提供更為細化的應用業務,在保證實時用戶的QoS 需求的前提下,充分考慮用戶的公平性,實現最大化系統的吞吐量。

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

差分隊列服務算法[2]目的是為了在有線網絡中為各類數據業務提供更加細化的QoS,主要優點是能夠根據資源的利用情況給業務應用提供更加細化的端到端QoS 服務。其算法的基本原理是:設一個網路由n 個節點組成,數據包的傳輸路徑是固定不變的,在不考慮傳播延時,當一個數據包到達節點i時,該數據包端到端的剩余延時為

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

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

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

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

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

表1 節點2 中的時延表Table 1 Delay table at node 2

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

3 分布式隊列服務算法性能分析

這里使用Ad Hoc 網絡仿真模型[4],在NS2 仿真平臺上進行仿真分析[5]。

3.1 探測包性能

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

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

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

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

3.2 緩沖區的使用率

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

圖2 控制包隊列的統計Fig.2 Statistic of control packet queue

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

圖3 數據包隊列的統計Fig.3 Statistic of data packet queue

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

3.3 實際平均吞吐量分析

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

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

3.4 平均端到端延時分析

平均端到端延時是指數據包從原節點到目的節點所經歷的平均端到端延時[7]。使用的仿真條件和2.3 節的仿真條件一樣, 圖5 為DQS 調度算法和EDF 調度算法[8]的端到端延時曲線圖。

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

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

4 總 結

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

[1] 劉俊芳,趙爾敦,劉巍.小無線網絡中基于BLUF 的包調度算法[J] .計算機工程與應用,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] 錢權.無線Ad Hoc 網絡安全[M] .北京:清華大學出版社,2009.

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

[5] 時慧晶, 趙燁.基于NS2 的Ad Hoc 網絡路由協議性能研究[C]//全國第21 屆計算機技術與應用學術會議(CACIS·2010)暨全國第2 屆安全關鍵技術與應用學術會議論文集.上海:[ 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] 顧金媛, 章國安, 包志華.認知無線mesh 網中聯合路由的分布式信道分配算法[J] .計算機應用研究,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] 陳潛,劉云.動態高速環境下Ad Hoc 路由協議研究[J] .中北大學學報(自然科學版),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.