跨層多徑AOMDV路由協議的研究

鐘 輝,周甜甜

(沈陽建筑大學 信息與控制工程學院,沈陽 110168)

1 引 言

無線路由協議由先驗式和和按需路由協議組成.按需路由協議不需要周期性與鄰接點交換路由信息來維護整個網絡的路由表,而是在節點需要給目的節點發送數據分組時來尋找到達目的節點的路由,因此控制開銷較小.路由信息可以得到有效的利用[1].在按需路由協議中,AODV(Ad Hoc on-demand distance vector)協議的路由開銷相對較少,收斂性快,有明顯的優勢,但隨著數據量的激增,單路徑路由協議AODV顯然已不能滿足需求,在基于AODV擴展的多路徑路由協議中,AOMDV多路徑路由協議在AODV協議基礎上,實現了獲取多條無環路、且節點不相交路徑完成路由表包含多條有效路徑[2].其主要缺點是沒有考慮鏈路的傳輸壓力,緩存隊列長度有限,若隊列中緩存的分組沒有被及時發送出去,后到達的分組將會因為當前隊列占有率過大而被丟棄,造成數據包的丟失,降低網絡的吞吐量,隊列中沒有被及時發送出去的分組也會增加不必要的排隊時延,增加端到端延時,浪費網絡資源.針對AOMDV路由協議對此造成的不良影響,本文提出一種基于啟用實時監測鏈路傳輸壓力的多路徑路由協議QE_AOMDV.

2 AOMDV路由協議

AOMDV路由協議是對AODV單路徑路由協議進行了多路擴展,它是充分將RREQ請求分組的泛洪特性使用在路由請求過程,促使多條節點不相交路徑在廣播中建立[3].

在路由請求過程中,AOMDV多路徑路由協議和AODV協議相似,基于序列號來表明路徑的新舊,以保證不產生環路路徑.AOMDV協議中為了使目的節點序列號保持單調遞增,協議定義了“廣告跳數(Advertised HopCount)”的概念來產生目的節點序列號.任何源節點到目的節點的廣告跳數使用其間多條路徑中有“最大”跳數的有效路徑來表達.確定了最大跳數,任何目的節點序列號廣告跳數都始終不變.而AOMDV協議只使用跳數小于最大跳數的備選路由表項.源節點尋早目的節點路由時就開始廣播 RREQ 分組,當RREQ分組到達中間節點時,可能有多個RREQ分組到達,檢查每個RREQ分組中firsthop字段和節點的最后一跳列表,檢查此路由是否來自源節點的不同鄰居節點,因此來判斷RREQ分組內容能否提供沒有使用過的節點不相交路徑[4].據此目的節點或者具有有效路由中間節點產生RREP分組,將RREP 分組單播回傳到源節點.多個RREP分組到達源節點,最后多條節點不相交路徑在源節點路由表中產生出來.AOMDV協議的路由發現機制選擇跳數最少的路徑作為傳輸主路徑,剩余的路徑稱為備份路徑.若輸主路徑失效,分組的傳輸就用備份路徑來代替主路徑進行,一直至運行至路由表中所有備份路徑都失效,再由源節點開啟一輪新的尋路過程[5].

路由維護發生在鏈路斷裂時,如果當前節點到目的節點的跳數小于源節點到當前節點的跳數,則進行本地路由修復.即如果當前節點正在傳輸數據,鏈路發生異常,則緩存數據,將該節點標記為RTF_IN_REPAIR,并向目的節點發送一個路由發現請求.如果在定時器規定時間內,沒有找到當前節點到目的節點的有效路由,將該路由釋放,丟棄緩存的數據包,發送RRER錯誤分組至上流節點,通知上游節點避免使用所有經過該節點的路由[6].

3 AOMDV協議在NS2上的運行

3.1 包在NS2中的流程

首先數據包在應用層(Application::send)向下發送到代理Agent層;代理Agent層(UdpAgent::sendmsg)初始化Agent代理生成其代理對象UdpAgent.UdpAgent對象產生對應的數據分組,并將分組傳入到Node節點的分類器Classifier(Classifier::recv)對象,該對象調用find()函數返回下一跳地址.在Packet包對象內容中是由Find()函數查找獲得Packet包的下一跳地址的,分類器recv 函數分組的下一跳地址后調用節點node->recv()函數進入connector對象;然后再調用connector::recv函數和 connector::send函數后確定數據包是否可發送,之后進入Trace::recv函數,此時將這個數據包加入隊列的記錄保存起來;之后再由 connector::send函數進入Queue::recv 函數,將數據包正式加入發送隊列,判定是否加入隊列成功或被丟棄;然后再調用 DequeTrace::recv函數將數據包彈出隊列的記錄保存起來;最后再通過connector::send函數調用進入LinkDelay::recv方法,首先進行目的節點是否可達的判斷,再根據不同結果將事件寫入scheduler對象,等待NS事件調度執行.

3.2 隊列管理

隊列代表存放(或者丟棄)包的地方,在網絡中DropTail管理機制是最廣泛使用的隊列管理機制[7].當某個數據包到達隊列時,增加包到隊列尾部而等待,考慮存儲空間限制造成等待隊列長度設置有限,大量數據流通過網絡時,由于隊列沒有足夠的空間,這些剛到達的數據包就無法進入隊列保存,因此簡單的將隊列尾部的數據包丟棄,稱這樣的管理機制為DropTail.整個運作方式為:包傳送的順序與包進入隊列的順序相同,先進入隊列的包先傳送出去,后進入隊列的包等待前面的包傳送完成后再傳送出去.如果隊列長度超過暫存空間的大小,就會把隊列最尾端的包丟棄[8].

DropTail在丟棄包時,并不會去考慮要丟棄的包屬于哪個數據流,只是單純的把超過暫存空間大小的數據流丟棄,因此DropTail隊列管理機制的最大優點就是實際操作簡單.但是,有利有弊,在相當長一段時間內,這種單一特性的操作使得隊列處于滿負荷或幾乎滿負荷狀態.本文提出的隊列管理機制最重要目的是降低穩定狀態下隊列的長度,因為大部分端點到端點的延遲其主要原因是數據包在緩存隊列中排隊等待造成的[9].

DropTail隊列列管理也容易產生TCP全局同步(TCP Global Synchronization)現象.因為網絡上數據流都具有突發性,因此到達每個路由器的包也是突發的.當每個路由器暫存隊列處于滿負荷或幾乎滿負荷狀態,大量的數據包會在短時間內被丟棄.而在TCP協議下數據流具有自適應特性,發送端檢測出數據包丟失就會立刻降低發送速度,緩解網絡擁塞狀況.發送端發現網絡擁塞緩解后又開始增加發送速度,最終又造成網絡擁塞.這種現象形成一個循環,周而復始的進行下去,會致使網絡長期處于鏈路利用率很低的狀態,降低了整體的吞吐量[10].為了克服這種TCP全局同步現象,如果能實時檢測到隊列中緩存區的狀態,則可以及時掌握網絡擁塞情況,對全局同步現象做出預判,改善網絡性能.對此在第4部分提出基于DropTail的主動丟包隊列管理機制.

4 基于DropTail的主動丟包隊列管理機制

4.1 RED隨機提前檢測

本文提出的基于DropTail的主動丟包隊列管理機制吸取了RED算法的思想,事先在隊列中隨機檢測隊列容量.隨機提前檢測RED算法使用主動的管理隊列的方式.其主要算法過程是:在網絡路由器存滿接收到的包之前隨機檢測隊列容量,按事先確定的規則隨機丟棄包分組,這樣能夠事先告訴發送端縮小擁塞窗口,對進入網絡包分組加以控制,防止路由器將更多的分組隨意丟棄.

RED算法主要分為兩種計算內容:1)平均隊列長度計算,指在時間上平均,該算法路由器的各個接口只有一個隊列;2)分組丟失概率計算.第一部分決定了路由器能夠允許的突發分組發送的程度,第二部分決定了路由器在當前滿隊列狀態下分組丟棄的頻度,主要目的是讓路由器在時間間隔均勻的情況下丟棄分組,避免對突發性數據流的不公平性,同時防止TCP全局同步產生,還要能足夠頻繁地丟棄分組以控制隊列的平均長度.使用平均隊列長度比使用隊長的瞬時值更能準確的觀測到網絡的擁塞情況[11].

4.2 Drop Tail隊列長度管理機制

Drop Tail是廣泛使用的隊列管理機制.它類似于FIFO(先入先出)的管理,先到達路由器的分組先被傳輸,原理相對簡單.路由器緩存隊列充滿數據時,利用丟包進行擁塞檢測.但路由器隊列緩存空間收大小限制,如果在路由緩存充滿時還有分組到達,那就丟棄該分組.若發生丟棄分組現象,立即告知發送端網絡出現擁塞,調整發送速率.這種方法的缺點是不考慮被丟棄包的重要程度.

隊列類是由一個連接器基類派生的,該基類可以派生出各種隊列類.隊列類Queue部分偽代碼如下:

Queue 繼承Connector{

純虛函數enque()

純虛函數deque()

接收函數recv()

獲取隊列初始長度limit()

獲取隊列實時長度length()

隊列最大包個數qlim_

……

}

enque和deque函數是純虛函數,代表包的入列和出列,任何類型的隊列在實現Queue這個基類時,都必須實現enque和deque兩個函數.其中,qlim_代表隊列所允許的最大的包的個數,limit()函數返回值是qlim_,即limit()函數的返回值是隊列設定的初始長度,length()函數返回當前隊列中緩存區的包的個數,即緩存區的隊列長度.DropTail繼承自Queue類,本文通過調用limit()和length()這兩個函數在路由層跨層獲取MAC層的隊列長度來改進包的發送策略.

網絡Mac層就是用接收來的包充滿緩沖區時,看是否丟棄包來判斷網絡擁塞.遵循先進先出原則,位于隊列中前面的包將率先被發送出去[12].如果此時隊列緩沖區已滿,那么后到達的包將被丟棄.

只有一個先進先出(FIFO)隊列存在于DropTail管理機制,由包隊列類的對象實現.DropTail隊列機制實現了自己的enque()函數和deque()函數.enque()函數首先在隊列內部判斷qlim_參數檢測隊列的容量,當隊列中的包數量達到或者超過隊列最大長度時,丟棄最近接收的包.隊列類實現了緩沖區管理,但是卻不能在特定隊列上實現低層次的操作.解決這個問題的有效方法是使用包隊列類.

該類是設置成一個包的鏈表,包的順序一般用特殊的調度和緩沖管理規則用來存儲.其中,length()函數返回當前隊列中包的數量,即隊列此時緩沖區的長度,enque()函數將特定的包加在隊尾并修改成員變量len_,deque()函數返回隊列頭部的包.lookup()函數返回從隊列首部第n個包,若找不到,則返回空.

原始的隊列管理機制DropTail原理非常簡單,就是當路由器緩沖存滿時用丟包來警示網絡擁塞,包先到先被傳輸,若包到達時緩存已滿,丟棄分組,告知發送端網絡擁塞,調整發送端發送速率[13].

綜上所述,在原AOMDV路由協議中,包隊列始終處于隊列達到最大值就丟棄后來的包,無法利用隊列狀態對即將到來的包做出預判.無論當前節點是否處于滿載狀態,都將采用當前節點進行包的傳輸.如果節點此時的隊列緩沖區空閑,即時發送,如果有未發送的包且隊列未達到最大長度,則將該包入列,等待前向包發送完成之后在發送.如果此時隊列中已達到最大長度,則直接丟棄該包.原始的隊列管理機制沒有充分利用隊列狀態,對節點是否是傳輸包的適宜節點作出明確說明.導致后到的包仍然選擇負載較大的節點參與傳輸,造成不必要的丟包,降低網絡性能.

4.3 基于DropTail的主動丟包隊列管理機制的算法

通過3.2的分析,本文發現在DropTail類中定義了指向PacketQueue的對象,通過該對象可以獲取包隊列中的隊列長度及初始長度.原AOMDV路由協議的隊列管理機制也采用了這一點.在原DropTail隊列管理機制基礎上,引進主動丟包思想,改進隊列管理機制.

4.3.1 設定節點的隊列接收閾值

由上所述,隊列的初始長度手動設置為N.獲取到的實時的隊列長度為n.定義:如果獲取的實時隊列長度n小于0.9*N,即n∈0.9*N認為當前隊列滿足傳輸要求,可以參與傳輸.

4.3.2 跨層獲取隊列緩沖區長度

1)配置用于運行的tcl腳本文件,在tcl腳本中進行初始化.首先找到對應的路由層協議,set router [$n0 agent 255].其中255是端口號,agent 255代表是路由代理.其次初始化queue對象,set queue [$n0 set ifq_(0)].ifq_(0)中一般情況默認為0(單信道).最后,綁定路由和隊列,$router attach-queue $queue.在路由層訪問隊列信息.

2)在QE_AOMDV頭文件中加入“drop-tail.h”.在QE_AOMDV類中定義DropTail的指針queue_,以便操作DropTail的屬性.

3)修改command函數,增加if(argc == 3)

{

if(strcmp(argv[1],"attach-queue")== 0){

queue_=(DropTail*)TclObject::lookup(argv[2]);

printf("I have attach to the queue! ");

return(TCL_OK);

}

}

通過tcl腳本建立的TclObject,建立實例過程cmd()激活影子對象的方法command(),并將定義的queue參數以向量形式傳遞給command()方法.

4)當節點收到一個包時,首先用queue_指針調用基類的limit()函數即queue_->limit()獲取隊列的初始長度.然后用指針queue_調用基類的length()函數即queue_->length()獲取隊列的實時長度,計算隊列緩沖區長度的占有率.具體過程會在第5部分敘述.

4.3.3 基于DropTail的主動丟包的隊列管理

當得到隊列緩沖區長度的占有率后,與隊列的接收閾值進行比較,如果達到接收閾值,表明隊列當前的緩沖區長度較長,負載較大,鏈路壓力較大,則丟棄數據包;反之,將該包放在隊列尾部,等待發送.

本文提出的隊列管理機制吸取了RED隨機提前檢測隊列思想.在隊列長度達到閾值90%*N時,提前檢測出隊列負載,不使其達到滿負荷;閾值也不宜過小,使數據包丟棄數量過大,以免影響網絡傳輸速度.和RED隨機提前檢測隊列不同的是,本文改進后的隊列管理機制只丟棄在接收閾值以外的數據包,不是隨機丟棄,而且,不需要定時丟棄包,只在需要時進行丟包,既考慮到盡量減少丟失隊列數據,又要防止隊列充滿后造成網絡擁塞,是一個綜合利弊因素后的一個擇中選擇,從而達到提高網絡性能.

5 NS2隊列與QE_AOMDV路由協議隊列

5.1 節點

5.1.1 節點結構

在NS2中,節點和鏈路都占用適當的存儲空間.一個單播節點由地址分類器和端口分類器組成.節點一般表示主機或路由器,有些節點會根據需要綁定相關代理和應用[14].

本文中,建立節點以set node($i)[$ns node]執行.實例過程node建立包含多個classifier對象的節點,該節點本身也是OTcl中單獨的一個類.單播節點包含一個地址分類器(classifier_)和一個端口分類器(dmux_).這些分類器的功能是將包分派到相應的代理或鏈路中去.但要注意的是,Node_entry僅是一個標志變量,而不于classifier,是一個真實的對象.

5.1.2 節點設置

本文的節點參數如表1所示.

表1 節點參數表
Table 1 Node parameter table

參數類型參數值路由協議QE_AOMDV鏈路類型llMac類型Mac/802_11隊列類型Queue/DropTail隊列長度30天線類型Antenna/OmniAntenna無線信號傳輸模型Propagation/TwoRayGround物理類型Phy/WirelessPhy信道Channel/WirelessChannel拓撲new Topography路由跟蹤ON代理跟蹤ONMAC跟蹤OFF場景跟蹤OFF

節點初始化已經設置了仿真參數,所以節點要運行的路由協議隊列長度等參數已經在仿真參數中獲得.所有在node-config 命令執行之后創建的節點都擁有同樣的性質,直到node-config命令中的一部分參數發生改變且執行之后.

5.2 NS2的隊列

NS是一個事件(event)驅動模擬器,利用一個名為Simulator的Tcl類來定義和控制整個模擬過程.

圖1 事件調度示意圖Fig.1 Event scheduling diagram

NS2實際仿真時,調度對象的Scheduler::run()函數不間斷處理隊列中事件,將隊列中的其它事件派出并放入事件隊列中,Scheduler::run()再調用Scheduler::dispatch()函數將一個事件從隊列中彈出來,執行事件中Handler句柄處理函數handle()處理該事件.完成一個事件產生、排隊、彈出被處理過程,值得注意的是,ns只支持單線程,故在任何時刻只有一個事件執行.圖1為事件調度器的工作過程示意圖.首先從事件隊列中找到時間最先事件,用本身handler()函數處理完畢,在處理下一事件,不斷重復執行最早事件,若有事件時間相同,按事件代碼進入隊列順序執行.

5.3 網絡協議的隊列

NS2鏈路仿真包含部分網絡層、鏈路層和物理層功能.仿真鏈路由DelayLink,Queue,TTL等多個組件(連接器子類)組合形成,如圖2所示,它以隊列緩存方式管理包到達、離開和丟棄,接收節點上層發來的數據,經過傳播和發送延遲,將包發給下一節點或丟棄.

圖2 鏈路中包傳輸示意圖Fig.2 Packet transmission in the link

包在鏈路中的傳輸過程如下:來自節點的包先由Queue隊列處理,隊列不滿則排隊,否則丟棄.服務器判斷鏈路Queue隊列是否包發送,有包就根據相關包調度策略發給DelayLink對象.DelayLink對象計算所需要的傳輸延遲,將包傳給調度器.調度器負責調度事件隊列的調度,包在相應時間延遲后,發給TTL對象,調度器改變鏈路狀態,鏈路便可處理下一個包.TTL收到包,將包的ttl值減1,判斷ttl值若ttl大于0,則將包傳給下一節點,否則將包丟棄.

而在實現上,LL類繼承自LinkDelay類,聲明Queue的指針ifq_,Queue的子類DropTail中又聲明了PacketQueue類的指針q_,從而可以通過q_來獲取到隊列中的長度.

6 基于隊列長度的QE_AOMDV路由協議算法

6.1 QE_AOMDV路由協議的理論依據

隨著網絡負荷的增加,吞吐量與網絡負荷大致成正比遞增[12].

Smax=

(1)

Smax表示當前節點的最大歸一化吞吐量.E[P]表示鏈路層平均分組負荷.公式(1)表征802.11協議吞吐量Smax隨著鏈路層平均分組負荷E[P]的增加而增加.假設節點處理數據的能力相同,節點負荷越大,節點越繁忙,網絡出現擁塞的可能性越大[13].網絡各層之間息息相關,彼此聯系.每一層都留有各自的隊列棧和緩存區.同一節點在同一時間既是數據包的承載者又是控制包的承載者.在同一時間維度內,共享該層的隊列資源.網絡層通過實時監控鏈路層的隊列資源,動態調整本層數據包和控制包的發送策略,最有效的利用鏈路層資源.既不因為頻繁發包使鏈路層應接不暇而丟包也不至于使鏈路層隊列處于空閑狀態等待時間過長而浪費資源[14].

因此,本算法引入節點的實時隊列長度即當前節點的實時負荷提前檢測.探討在均衡網絡負載狀態下的網絡性能.隊列閾值設置0.9×N是根據隨機提前檢測度列原理,既考慮到少丟失隊列數據,又要防止隊列充滿后造成網絡擁塞,是一個綜合利弊因素后的一個擇中選擇.隊列數據充滿90%以上的機會在一般網絡流量下很小,所以包丟棄概率也很小.從實驗結果證明看,在一定的網絡流量下,該閾值取值效果最好.如果閾值取0.8N,數據包丟失過大造成網速減慢,流量減少.

6.2 QE_AOMDV路由協議的數據結構

QE_AOMDV路由協議主要修改了RREP和路由表的數據結構,新增“隊列緩存區長度累加和”字段表征鏈路壓力大小.

RREQ數據結構如表2所示.在正向轉發RREQ包時,通過實時監測獲取鏈路層隊列資源情況,決定當前節點是否參與轉發并設置延時.

表2 RREQ消息格式
Table 2 RREQ message format

類型JRGDU保留跳數目的節點IP地址目的節點序列號源節點IP地址源節點序列號路由請求識別碼第一跳

RREP數據結構如表3所示.若當前節點即為目的節點或有到目的節點的有效路由項,需要將路徑上節點的隊列緩存區長度依次累加在一起,向源節點沿反向路徑發送RREP應答消息.

表3 RREP消息格式
Table 3 RREP message format

類型RA保留前綴長度跳數目的節點IP地址目的節點序列號源節點IP地址壽命第一跳隊列緩存長度累加和

路由表結構如表4所示.節點的緩存路由表中記錄多條路徑,當源節點收到多條路徑時,選擇隊列緩存區長度累加和最小即鏈路壓力最小的路徑作為主路徑進行數據的傳輸.

表4 路由表格式
Table 4 Routing table format

目的節點IP地址目的節點序列號廣告跳數路由列表{(第一條路徑下一跳,最后一跳,跳數,隊列緩存區長度累加和),(第二條路徑下一跳,最后一跳,跳數,隊列緩存區長度累加和)…}壽命

6.3 QE_AOMDV路由協議的鏈接背景

AOMDV協議主要過程是:為了尋找到目的節點的路由,源節點廣播RREQ 請求分組,節點路由表使用lasthop 和nexthop來唯一表示某條路徑,通過該標志判斷是否與其它路徑相交.中間節點收到各鄰居節點發送的RREQ分組,并檢查RREQ分組的firsthop標識和節點的最后一跳列表,以此來判斷該RREQ分組是否從源節點的不同鄰居節點發送出來,即是否是一條新路徑.中間節點收到來自上游的RREQ請求報文后,會向源節點發送RREP分組;而目的節點收到來自源節點的請求報文后,會馬上向源節點發送RREP回復,RREP沿著正向路徑逆向發送到源節點,當源節點收到第一個來自于目的節點的RREP后,正向路徑便建立.把收到的第一條路徑設為主路徑[14,15].

如圖3所示,原AOMDV多路徑路由協議找到S-1-3-5-7-D,S-11-9-D,S2-4-6-8-10-D三條節點不相交路徑.其中S-11-9-D為4跳路徑,跳數最小,將此路徑作為主路徑,優先主路徑傳輸.通過對AOMDV多路徑路由協議的分析,當路由表中存在有效路由時,可以利用已有的路由傳輸數據,而當前路由中9號節點可能正在參與其他傳輸任務,路徑負載較大,這就可能造成這條路徑的擁堵,造成網絡擁塞.難以保證數據的穩定傳送,而此時適宜的空閑路徑可能存在卻沒有得到有效利用,造成資源浪費.為解決以上問題,QE_AOMDV路由協議對AOMDV多徑路由協議的路由發現過程提出以下兩點改進,路由維護過程提出一點改進.

圖3 路由尋路結構圖Fig.3 Route maintenance structure

6.4 QE_AOMDV路由協議的路由發現

在路由發現過程中,中間節點收到來自鄰居節點的RREQ請求報文,根據自身的負載狀態來決定是否轉發該報文或直接響應.如圖4所示.

圖4 中間節點收到RREQ的處理過程Fig.4 Process of receiving the RREQ at the intermediate node

在QE_AOMDV路由協議中,節點的緩存區初始隊列長度為N,若實時的隊列緩存區長度n達到90%*N并且已經收到過相同的RREQ包,那么該節點不適合繼續參與傳輸,丟棄該報文.縱使有到目的節點的有效路由,也不繼續參與傳輸.

i.在路由發現過程中,隊列占有率為獲取的節點實時隊列長度和隊列初始長度的百分比,用rationodei表示,如公式(2):

(2)

其中queuelhcurrent=queue_->length();

queuelhinitial=queue_->limit();

queue_->length()和queue_->limit()在3.3.2部分中已經提到,此不贅述.

ii.在路由發現過程中,報文的轉發延時為節點緩存區實時隊列長度的占比,用e2enodei表示.如公式(3):

e2enodei=rationodei

(3)

圖5 中間節點收到RREP的處理過程Fig.5 Process of receiving the RREP at the intermediate node

如果中間節點通過實時監測隊列獲取到隊列長度在90%*N以下,且沒有到目的節點的有效路由,如圖3所示,那么將RREQ請求報文封裝好,延時轉發給鄰居節點.

通過獲取節點實時的隊列長度,計算隊列占用率,中間節點處理好收到的RREQ包后,將隊列占用率填充到RREP消息中,向源節點發送RREP路由應答.如圖3所示,當目的節點收到RREQ消息后,依次累加路徑上的隊列占用率,用Totalratiopathi表示,如公式(4):

Totalratiopathi=∑rationodei

(4)

中間節點收到RREP后的處理過程如圖5所示.當源節點收到第一條路徑時,第一條路徑是鏈路壓力最小的路徑.最小化延時的同時最優化了路徑負載情況.路徑 S-2-4-6-8-10-D的鏈路壓力為0.8,S-1-3-5-7-D的鏈路壓力為 1.2.如圖3所示.因此,主路徑被確定為 S-2-4-6-8-10-D,次路徑為 S-1-3-5-7-D.

6.5 QE_AOMDV路由協議的路由維護

QE_AOMDV按需多路徑路由協議和AOMDV路由協議的路由維護過程類似.不同的是在QE_AOMDV路由協議中,當一個節點在傳輸報文時,通過Hello包探測到鏈路受損,首先獲取自身的緩存區隊列長度m,如果當前長度m未達到隊列初始長度N的90%,那么進行本地維修,如果達到90%,則向源節點發送RRER錯誤分組包,告訴路徑上游前面的節點,和本節點相連鏈路出現錯誤.為了不再使用這些受損鏈路和節點,必要時由源節點開啟新一輪路由發現過程.

圖3中,Hello包探測到9號節點發生故障,9號節點的隊列緩存區占有率為90%,超過閾值,由9號節點向上游節點沿反向路徑發送RRER包,直至源節點,由源節點開啟一輪新的尋路過程.如果9號節點的隊列占比不超過閾值,那么將由11號節點發起一輪到目的節點的尋路過程.

7 QE_AOMDV路由協議的仿真性能分析

7.1 多節點仿真

本文采用NS-2仿真,仿真節點隨機放置在600m×600m的矩形范圍內,仿真時間為200s,在多節點仿真中,設置10個仿真場景,cbr發送速率恒為30kb/s,節點個數分別為14/24/34/44/54/64/74/84/94/104.將本文提出的改進方法和原AOMDV路由協議從端到端延時,網絡吞吐量以及丟包率三方面進行對比.

圖6 平均延時、吞吐量、丟包率隨節點個數變化圖Fig.6 Average delay,throughput,and packet loss rate as a function of the number of nodes

在多節點數目的仿真中,圖6顯示協議改進前后分別在平均延時,吞吐量、丟包率三方面的比較.其端到端延時總體降低9.1%.在較少的節點數目下,原有協議和QE_AOMDV路由協議在端到端延時不相上下.當節點數超過44時,隨著節點數目的增多,節點的隨機運動更復雜,碰撞幾率更大,由于考慮了節點的負載情況,緩解了鏈路擁塞,QE_AOMDV路由協議的端到端延時始終小于AOMDV路由協議.

QE_AOMDV路由協議的吞吐量較原AOMDV路由協議提高20.1%.在不同的節點數目下,QE_AOMDV路由協議均呈現出較高的吞吐量,網絡中拓撲環境較復雜時,原AOMDV因鏈路頻繁斷裂,無效路徑的使用導致分組大范圍丟棄,性能的差別變得更明顯.

在網絡中節點個數少于24之前,協議改進前后的丟包率持平.當節點數達到24后,兩種協議的丟包率趨于平穩,且QE_AOMDV路由協議的丟包率始終小于AOMDV路由協議.改進的QE_AOMDV路由協議具有明顯的優勢.

7.2 多速率仿真

在NS-2中仿真參數選擇節點隨機放置在600m×600m的矩形范圍內,仿真時間為200s,在多速率仿真中,設置10個仿真場景,節點數恒為20,cbr發送速率分別為30(kb/s)/40(kb/s)/50(kb/s)/60(kb/s)/70(kb/s)/80(kb/s)/90(kb/s)/100(kb/s)/110(kb/s)/120(kb/s).

在多發送速率的仿真中，圖7顯示協議改進前后分別在平均延時，吞吐量、丟包率三方面的比較。協議改進后其延時降低9.0%。仿真開始時由于節點移動速度緩慢，網絡拓撲相對變化小，節點鏈路出現斷開機會偏小.兩種協議時延較小.當cbr發送速率逐漸變大,隊列的占用率逐漸增加,相應的轉發延時漸增加,兩種協議的端到端延時均呈現上升趨勢.在不同的cbr發送速率下,QE_AOMDV路由協議有較高的吞吐量,吞吐量提高15.7%.隨著發送速率的增加,節點的發送任務繁重,隊列中待發送的數據包堆積,造成后到達的數據包因前向數據包未及時發送出去而被丟棄,造成數據包的意外丟失.QE_AOMDV路由協議將節點的隊列緩存引入到路由發現中,原AODMV因鏈路頻繁斷裂,無效路徑的使用導致分組大范圍丟棄,性能的差別變得更加明顯.改進后的QE_AOMDV路由協議具有明顯的優勢.QE_AOMDV多路徑路由協議較AOMDV路由協議的丟包率總體降低9.0%.QE_AOMDV多路徑路由協議由于將節點的隊列緩存區長度加以考慮,使得部分數據包避免了使用緩存隊列長度較長的節點參與傳送任務,有效降低了丟包率.

圖7 平均延時、吞吐量、丟包率隨發送速率變化圖Fig.7 Average delay,throughput,and packet loss rate as a function of transmission rate

8 結束語

本文結合原有AOMDV多路徑路由協議,將隊列緩存區長度引入QE_AOMDV多路徑路由協議.通過考慮緩存區的隊列空間,避免負載較重的節點參與傳輸,同時,根據負載情況進行延時轉發和鏈路的修復.結果表明:改進后的QE_AOMDV多路徑路由協議較原AOMDV協議相比,吞吐量整體提高,延時大大降低.QE_AOMDV多路徑路由協議的性能優于原AOMDV路由協議.