基于Mesh的CS_AODV路由協(xié)議的設計與仿真

　　0 引言

　　無線Mesh 網絡是一種多跳、自組織和自愈性的分布式寬帶無線網絡，由于部署簡單、使用方便而被廣泛應用。但由于無線鏈路的不穩(wěn)定性以及帶寬資源的有限性，其網絡性能無法滿足用戶對帶寬、時延、路由穩(wěn)定性以及丟包率的需求，這需要提供一定的QoS 保證，而QoS 路由是實現(xiàn)QoS 保證的一個關鍵因素。目前國內外文獻中已經提出很多基于無線Mesh網絡的QoS 路由協(xié)議。文獻[2] 中提出一種基于帶寬的QoS路由協(xié)議-QRBC,協(xié)議應用于實時數(shù)據服務環(huán)境，為實時數(shù)據流選擇一條干擾小，保證帶寬的穩(wěn)定路由;文獻[3],應用數(shù)據傳輸失敗概率去估算路由的有效帶寬，這種估算方法主要用于接入控制算法和QoS 路由協(xié)議;文獻[4] 提出一種多徑QoS 路由協(xié)議AODV_MQ,采用同時多徑機制并以時延為QoS 參數(shù);艦船編隊無線移動網絡是一種專用網絡，應用環(huán)境以及傳輸數(shù)據類型都有其特殊性，本文針對艦船編隊間的無線移動網絡對路由穩(wěn)定性以及不同數(shù)據類型進行分級的QoS 保證要求，通過對現(xiàn)有移動自組網路由協(xié)議-AODV 進行改進，提出一種基于AODV 的QoS 機制改進路由協(xié)議-CS_AODV( ClassificaTIonand Path Stability Routin gProtocol based on AODV)。

　　1 AODV 協(xié)議

　　AODV是一種源路由按需路由協(xié)議，實質是DSDV與DSR結合，已被IETF MANET工作組于2003年7月正式公布為自組網路由協(xié)議的RFc標準。只要兩個節(jié)點都都有通向對方的正確路由，AODV是不工作的。當某節(jié)點需要同某個目的節(jié)點通信而本身沒有到該目的節(jié)點的路由時，它將廣播一個RREQ(路由請求消息)來嘗試找到一條到目的節(jié)點的路由，所有接到請求的節(jié)點都會緩存一條回到發(fā)起節(jié)點的路由，通過比較分組中的序列號丟棄重復收到的RREQ.如果RREQ消息到達目的節(jié)點，這條路由將被找到，目的節(jié)點朝源節(jié)點單播一個RREP后，這條路由就建立了。中間節(jié)點收到RREP 后會建立一條到源節(jié)點的前向路由。如果收到RREQ的中間節(jié)點擁有到目的節(jié)點的路由，且該路由的序列號足夠大，則該路由也就被找到，同樣返回RREP.如果該路徑上某個節(jié)點下一跳變得不可達，它就向上游節(jié)點發(fā)送RERR 分組，通知源節(jié)點鏈路斷裂，源節(jié)點重新開始路由發(fā)現(xiàn)。

　　2 CS_AODV 協(xié)議設計

　　2.1 優(yōu)先級設置

　　艦船編隊無線Mesh 組網主要是實現(xiàn)艦船編隊統(tǒng)一高效的指揮控制，傳輸信息主要是指控指令以及各種傳感器信息，多媒體業(yè)務較少，但對實時性要求很高。網絡中不同的節(jié)點具有不同的業(yè)務優(yōu)先級別，同一節(jié)點的不同數(shù)據類型也有不同的級別。而且由于無線移動網絡的帶寬資源相對有限，信道間控制指令所消耗的帶寬必須控制在一定范圍內，數(shù)據業(yè)務等級劃分不能太過復雜。CS_AODV 將節(jié)點劃分為2 個等級(如旗艦和非旗艦)，節(jié)點產生的數(shù)據業(yè)務流也劃分為4 個等級(如指控、探測、圖像及一般業(yè)務等)，共有8 個等級;等級高的業(yè)務先發(fā)送，業(yè)務等級相同則節(jié)點級別高的先發(fā)送。協(xié)議將AODV 的RREQ 分組中3 個保留位定義為優(yōu)先級區(qū)，如表1,其中3~4 位設為業(yè)務等級，級別由高到低依次設為00、01、10、11 ;第5 位設為節(jié)點級別，優(yōu)先級高的節(jié)點設為0 ;通過比較優(yōu)先級區(qū)的值來區(qū)分不同節(jié)點和業(yè)務的級別，分組級別越低，其值越大。AODV 的路由表中有到目的節(jié)點的路由，也需要對Data 分組增加類似的優(yōu)先級設置。

　　艦船編隊網絡的數(shù)據類型以指控和探測消息等為主，以單個分組形式在網絡中傳送。分組發(fā)送過程占用整條路徑，在發(fā)送分組競爭信道時進行優(yōu)先級區(qū)分。源節(jié)點發(fā)送分組，先判斷網絡中是否存在其他高級別分組，若有，在等待NET_TRYTIME = 基本等待時間+ random(class,class+1)(優(yōu)先級別加上隨機退避時間)時間后再次探測，若無，則開始發(fā)送分組;否則要繼續(xù)等待NET_TRYTIME 時間，直到沒有更高級別分組發(fā)送為止。參數(shù)class 表示服務級別，范圍：0~7,級別越高，class 值就越小，保證級別高的數(shù)據業(yè)務優(yōu)先建立路由。

　　2.2 引入多點中繼

　　AODV 協(xié)議的路由發(fā)現(xiàn)以洪泛方式進行，沒有給QoS 路由提供引導作用，占用大量網絡資源，容易造成網絡風暴。為此，本文引入多點中繼(Multi-Point Relaying,MPR)[6-7],網絡節(jié)點在自己的一跳鄰節(jié)點中選擇一部分節(jié)點作為自己的MPR,由MPR 轉發(fā)鏈路狀態(tài)消息，實現(xiàn)路由控制消息的選擇性洪泛;通過對HELLO 消息進行改進，只傳遞MPR 選擇節(jié)點與MPR 之間的鏈路信息，實現(xiàn)鏈路狀態(tài)信息的壓縮。

　　引入MPR 需要對HELLO 消息進行改進。AODV 協(xié)議中HELLO 分組只包含了本節(jié)點IP 地址、本節(jié)點序列號、跳數(shù)、發(fā)送周期、TTL 以及保留位等信息，鄰居節(jié)點只能夠檢測跟本節(jié)點的鏈路信息，因此需要對HELLO 消息進行擴充，添加鄰節(jié)點地址以及轉發(fā)分組意愿、鏈路代碼、鏈路信息大小等狀態(tài)信息。

　　定義N1(a) 和N2(a) 為節(jié)點a 的一跳和二跳鄰居節(jié)點表，D(b) 為a 的一跳鄰居的出度，MPR(a) 為a 的多點中繼站的集合，定義Stab(a)是為了得到節(jié)點的相對穩(wěn)定度。MPR 選擇實現(xiàn)算法如下：

　　1)MPR(a) 初始化為空。

　　2)計算N1(a) 中每個節(jié)點的出度D(b)(以及Stab(a))。

　　3)能提供唯一可達性到N2(a) 中某些N1(a) 節(jié)點的節(jié)點添加到MPR(a) ;并將已經添加到MPR(a) 的N2(a) 節(jié)點刪除。

　　4)當N2(a) 中仍剩有節(jié)點，則計算N1(a) 中未選為MPR的節(jié)點的所屬N2(a) 節(jié)點中仍未覆蓋的節(jié)點數(shù)目，將覆蓋最多剩余兩跳節(jié)點的鄰節(jié)點加到MPR(a)，若出現(xiàn)相同情況，選擇出度較大鄰節(jié)點的作為MPR,并刪除相應的N2(a) 節(jié)點。

　　5)比較MPR(a) 所覆蓋的N2(a) 節(jié)點。若MPR(a) 中某節(jié)點的兩跳鄰居節(jié)點是其他MPR(a) 節(jié)點的兩跳鄰節(jié)點，則將此節(jié)點刪除。

　　2.3 路徑穩(wěn)定性度量

　　艦船編隊組成網絡各個節(jié)點通常處于移動狀態(tài)，以某個節(jié)點的移動速度來衡量此節(jié)點的穩(wěn)定性并不可靠，但要計算整個網絡中每個節(jié)點的相對移動速度又比較困難，實現(xiàn)難度大，而且同網絡性能提升相比，所增加的網絡負荷可能更大。[!--empirenews.page--]

　　對于(絕大多數(shù))節(jié)點具有相似運動模型的移動網絡來說，每個節(jié)點都處于運動狀態(tài)，但對整個網絡來說，其拓撲結構是相對穩(wěn)定，因此可以利用節(jié)點相對穩(wěn)定度事先路由穩(wěn)定性的QoS保證。CS_AODV 協(xié)議引入了MPR 節(jié)點，該協(xié)議依靠選出的MPR轉發(fā)RREQ.但由于MPR 的選擇不僅與該節(jié)點的鄰節(jié)點相關，而且也與兩跳鄰節(jié)點相關，節(jié)點a 的相對穩(wěn)定性應以該節(jié)點兩跳范圍內所有節(jié)點(包括一跳鄰節(jié)點)的變化情況為依據。

　　和為節(jié)點a 的兩跳范圍內的鄰節(jié)點數(shù)量，其相對穩(wěn)定性公式變?yōu)椋?/p>

　　其中∩和∪分別表示為交集和并集。從上式可以看出：鄰節(jié)點數(shù)量變化越小，Stab 值越大，節(jié)點a 的相對穩(wěn)定性也越高。

　　實現(xiàn)節(jié)點穩(wěn)定性判定需要對AODV 的跳數(shù)判據進行改進，加入相對穩(wěn)定性度量值，其聯(lián)合判據函數(shù)表示為：

　　其中：β 為懲罰因子;數(shù)值1 表示為一跳，即通過本節(jié)點一次，跳數(shù)加1.可以看出：Stab 值越大，Metric 值越小。

　　其路徑總度量值為：

　　根據上式對RREQ 消息格式進行擴充，在類型、標志位、跳數(shù)、RREQID、目的節(jié)點地址、目的節(jié)點序列號、源節(jié)點地址以及源節(jié)點序列號等內容的基礎上，將跳數(shù)變?yōu)镸etric(path)。

　　3 仿真分析

　　本文采用NS2 仿真軟件進行仿真，設置場景如下：空間為500m*500m,節(jié)點隨機分布;節(jié)點最大移動速度為20m/s ;CBR 數(shù)據流，發(fā)包率50.0,包大小512byts ;采用802.11 MAC協(xié)議、OminiAntenna 天線，Two-Ray Ground ReflectionModel 無線傳播模型，仿真時間80s.分別設置10、20、30、40、50、60、80、100 個節(jié)點對CS_AODV 和AODV 協(xié)議進行仿真，利用MATLAB 進行計算分析。

　　圖1 表示為分組接收率，節(jié)點個數(shù)小于20 個時，兩種協(xié)議的分組接收率差別在5% 以內;隨著節(jié)點個數(shù)增加， AODV的分組接收率急遽降低，而CS_AODV 下降比較平緩，這是因為CS_AODV 選擇路徑時剔除了那些移動速度快的節(jié)點，選擇的路徑相對比較穩(wěn)定。圖2 為端到端延時，如果節(jié)點個數(shù)比較少，CS_AODV 的延時要高于AODV,隨著節(jié)點個數(shù)的增加，AODV 的時延的增長要比CS_AODV 快得多，節(jié)點數(shù)增至100 時，AODV 的延時比CS_AODV 高出40ms,主要是由于AODV 的路徑相對不穩(wěn)定，分組重發(fā)率高導致延時快速增加。分析圖3 看出，在節(jié)點數(shù)很少的情況下，CS_AODV 的指令開銷要比AODV大得多，這是由于選擇MPR 節(jié)點導致控制開銷大量增加;但隨著節(jié)點數(shù)的增加，CS_AODV 協(xié)議的指令開銷比例慢慢減小，而AODV 的開銷在增加，其原因是由于CS_AODV 選擇的路徑相對穩(wěn)定，路由發(fā)現(xiàn)和重傳的指令相對減少。從以上分析來看，CS_AODV 適合于網絡規(guī)模比較大，拓撲結構動態(tài)變化的網絡環(huán)境中。

　　4 總結

　　本文針對艦船編隊海上無線組網的實際需求，提出一種QoS機制路由協(xié)議-CS_AODV.仿真表明， CS_AODV協(xié)議付出一定開銷后能大幅提高分組接收率，縮短了端到端延時，并一定程度上提高了路由對動態(tài)環(huán)境適應性。