謝 佳,徐山峰
(中國電子科學(xué)研究院,北京 100041)
無線自組織(Ad Hoc)網(wǎng)絡(luò)是一種特殊的無線移動通信網(wǎng)絡(luò)。網(wǎng)絡(luò)中的節(jié)點(diǎn)不僅具有普通移動終端所需的功能,而且具有報文轉(zhuǎn)發(fā)能力。網(wǎng)絡(luò)中的所有節(jié)點(diǎn)地位平等,無需設(shè)置任何中心控制節(jié)點(diǎn),具有很強(qiáng)的抗毀性。Ad Hoc網(wǎng)絡(luò)與其他移動通信網(wǎng)絡(luò)的最根本區(qū)別是,節(jié)點(diǎn)間的通信可以經(jīng)過多個中間節(jié)點(diǎn)的轉(zhuǎn)發(fā),即報文要經(jīng)過多跳(Hop)到達(dá)目的地[1]。
Ad Hoc網(wǎng)絡(luò)技術(shù)的典型應(yīng)用是2001年由美國國防高級研究項(xiàng)目局(DARPA)提出研制的戰(zhàn)術(shù)瞄準(zhǔn)網(wǎng)絡(luò)技術(shù)(TTNT,tactical targeting networking tech-nology)。TTNT是一種基于IP的嵌入到聯(lián)合戰(zhàn)術(shù)無線電系統(tǒng)(JTRS)中的新型戰(zhàn)場網(wǎng)絡(luò)技術(shù)。TTNT數(shù)據(jù)鏈系統(tǒng)可在戰(zhàn)術(shù)飛機(jī)、武器系統(tǒng)和地面節(jié)點(diǎn)間建立類似互聯(lián)網(wǎng)的無線寬帶通信網(wǎng)[2],從而對時間敏感目標(biāo)的精確打擊起到?jīng)Q定性作用,使美軍的網(wǎng)絡(luò)中心站能力產(chǎn)生質(zhì)的飛躍[3]。
路由協(xié)議是Ad Hoc網(wǎng)絡(luò)的核心,它負(fù)責(zé)完成鄰居發(fā)現(xiàn)、分組路由、接納控制、擁塞控制和網(wǎng)絡(luò)互聯(lián)等功能。針對路由協(xié)議進(jìn)行性能仿真與比較分析,可以針對不同的應(yīng)用場景選擇合適的路由協(xié)議,提高Ad Hoc網(wǎng)絡(luò)的通信性能。
Ad Hoc網(wǎng)絡(luò)路由協(xié)議,大致分為兩類:先驗(yàn)式路由協(xié)議和反應(yīng)式路由協(xié)議。反應(yīng)式路由不會周期性發(fā)送網(wǎng)絡(luò)狀態(tài)控制包,在節(jié)點(diǎn)移動性較強(qiáng)、節(jié)點(diǎn)電池能源有限的情況下,反應(yīng)式路由協(xié)議性能優(yōu)于先驗(yàn)式路由協(xié)議[4]。在反應(yīng)式路由協(xié)議中,按需距離矢量路由協(xié)議(AODV)具有適度的路由開銷和快速收斂性,最有研究價值。
AODV、AOMDV和AODV-UU同屬AODV協(xié)議族,而AOMDV和AODV-UU在AODV基礎(chǔ)上進(jìn)行了改進(jìn)。AOMDV基于無環(huán)、不相交多鏈路技術(shù)。AOMDV的多徑路由之間不共用節(jié)點(diǎn),從而保證了鏈路不相交[5]。AODV-UU是 AODV路由協(xié)議在Linux下的實(shí)現(xiàn)。AODV-UU能夠更好地支持組播和子網(wǎng)絡(luò)。此外,AODV-UU還能夠支持Internet網(wǎng)關(guān)和多種網(wǎng)絡(luò)接口。
AODV綜合使用了目標(biāo)序列距離矢量路由(DSDV,destination-sequenced distance-vector)中目標(biāo)序列號和動態(tài)源路由(DSR,dynamic source routing)中按需路由發(fā)現(xiàn)技術(shù),提供了一種按需單徑距離矢量無環(huán)路由。該協(xié)議分為路由發(fā)現(xiàn)和路由維護(hù)兩部分。
①路由發(fā)現(xiàn):當(dāng)源節(jié)點(diǎn)需要與其他節(jié)點(diǎn)通信但沒有到該目的節(jié)點(diǎn)的路由時,源節(jié)點(diǎn)廣播路由請求RREQ。當(dāng)其他節(jié)點(diǎn)收到這個RREQ時,首先判斷是否收到過具有相同源節(jié)點(diǎn)和目的節(jié)點(diǎn)的RREQ,如果是,則丟棄,如果不是,繼續(xù)廣播該RREQ。當(dāng)目的節(jié)點(diǎn)收到RREQ時,同樣建立反向路由,然后向源節(jié)點(diǎn)發(fā)送RREP,如圖1所示。
②路由維護(hù):節(jié)點(diǎn)通過MAC層周期性廣播hello消息來判斷鏈路狀態(tài),如果該節(jié)點(diǎn)連續(xù)3次未收到hello響應(yīng)消息,就認(rèn)為鏈路已經(jīng)斷開,刪除包含該鏈路的路由信息,并發(fā)送路由錯誤,通知相鄰節(jié)點(diǎn)和相應(yīng)上游節(jié)點(diǎn)刪除因鏈路斷開導(dǎo)致目的節(jié)點(diǎn)不可達(dá)的路由信息,如圖2所示。
圖2 AODV路由維護(hù)示意圖
AOMDV是一種在AODV基礎(chǔ)上擴(kuò)展的按需多徑路由協(xié)議。該協(xié)議通過獲取多條無環(huán)和鏈路不相交的路徑來實(shí)現(xiàn)多路徑協(xié)議。AOMDV主要有兩部分與AODV不同:(1)建立和維護(hù)無環(huán)路徑更新的機(jī)制;(2)獲取多條鏈路不相交路徑分布式協(xié)議的方法。
①路由發(fā)現(xiàn):AOMDV路由發(fā)現(xiàn)階段與AODV類似,為了確保路徑無環(huán),仍使用目的地序列號來表明路由更新情況,并在內(nèi)部數(shù)據(jù)結(jié)構(gòu)增加廣播跳數(shù)代替原來的跳數(shù),以表明到達(dá)目的地節(jié)點(diǎn)的最大跳數(shù)和<nexthop,hopcount>鏈表及一個路由列表。每次路由更新都要對新的目的地序列號和當(dāng)前的目的序列號進(jìn)行比較。如果新的目的地序列號較大,則重新設(shè)置廣播跳數(shù)為無窮,并把相應(yīng)的地址作為到達(dá)目的節(jié)點(diǎn)的下一跳地址;如果兩個目的地序列號相等,且新的廣播跳數(shù)較小,則把該地址作為下一跳地址,以保證不出現(xiàn)回路。為了實(shí)現(xiàn)鏈路不相交,在路由請求階段不是隨意丟棄重復(fù)的RREQ,而是有目的地判斷該RREQ包的第1跳是否與主機(jī)節(jié)點(diǎn)第1跳相同,如果不同,才把該路由信息保存下來,否則丟棄,如圖3所示。
圖3 AOMDV路由發(fā)現(xiàn)示意圖
②路由維護(hù):AOMDV的路由維護(hù)階段與AODV類似,不同的只是當(dāng)路由表中的所有下一跳地址的路徑都失效時,才重新作路由發(fā)現(xiàn),如圖4所示。
圖4 AOMDV路由維護(hù)示意圖
AODV-UU路由進(jìn)程的包處理包括AODV路由協(xié)議控制包的處理和數(shù)據(jù)包處理。
①路由發(fā)現(xiàn):為了讓目的節(jié)點(diǎn)知道到源節(jié)點(diǎn)的路由,如果中間節(jié)點(diǎn)有到目的節(jié)點(diǎn)的路由,中間節(jié)點(diǎn)單播RREP幀到源節(jié)點(diǎn)來響應(yīng)RREQ幀的同時也發(fā)送一個免費(fèi)RREP幀到目的節(jié)點(diǎn),讓目的節(jié)點(diǎn)知道這條新路由。AODV-UU路由發(fā)現(xiàn)示意圖,如圖5所示。每個節(jié)點(diǎn)重啟后在對任何路由信息做出應(yīng)答前等待一個DELETE_PERIOD,以避免路由環(huán)路。
圖5 AODV-UU路由發(fā)現(xiàn)示意圖
②路由維護(hù):為了防止過早刪除在內(nèi)核路由表中的路由,路由表維護(hù)包括內(nèi)核路由表項(xiàng)的定期更新。為了維護(hù)目的節(jié)點(diǎn)與外出接口的交流,在路由表項(xiàng)中加入了interface字段。AODV-UU使用內(nèi)核交互更新內(nèi)核路由表,發(fā)送ICMP幀到應(yīng)用并從Netfilter鉤子接收包。AODV守護(hù)進(jìn)程通過使用netlink套接字來改變IP路由表。
AODV-UU的內(nèi)核模塊使用netfilter鉤子來決定包是到來的還是出去的,并且決定它應(yīng)該被接收還是轉(zhuǎn)發(fā)。投遞到Netfilter鉤子上的IP數(shù)據(jù)包會被捕獲并可以通過添加自定義代碼進(jìn)行修改,如圖6所示。
圖6 Netfilter框架圖
采用NS-2作為仿真工具,NS-2是一款功能強(qiáng)大的網(wǎng)絡(luò)模擬仿真器。它是用C++和OTCL兩種語言完成。C++語言編寫協(xié)議執(zhí)行模塊,OTCL語言編寫模擬任務(wù)。仿真的業(yè)務(wù)場景是:50個移動節(jié)點(diǎn),10/20對通信連接(所有通信模式都是點(diǎn)對點(diǎn)的,即peer to peer),以固定碼率(CBR,constants bit rate)為業(yè)務(wù)源(產(chǎn)生UDP業(yè)務(wù)),每秒鐘發(fā)送2個分組(每個數(shù)據(jù)包512B)。節(jié)點(diǎn)運(yùn)動場景是:每個移動節(jié)點(diǎn)在1000 m×300 m的區(qū)域不停止的隨機(jī)運(yùn)動(random waypoint模型),節(jié)點(diǎn)無線信號通信半徑250 m,仿真時間300 s。仿真參數(shù):radio frequency為2.4 GHz,channel bandwish 為 2 Mb/s,Mac protocol選取802.11。
仿真共使用了6種不同的節(jié)點(diǎn)最大運(yùn)動速度:20/50/100/150/200/250 m/s,它反映了網(wǎng)絡(luò)拓?fù)渥兓念l繁程度。每個數(shù)據(jù)點(diǎn)都是相同業(yè)務(wù)流模型,不同移動模型的5輪仿真結(jié)果的平均值,用xgraph工具繪制仿真結(jié)果圖。AODV、AOMDV和AODVUU在10對連接和20對連接下的平均端到端時延、分組投遞率、路由發(fā)現(xiàn)頻率和歸一化路由開銷,如圖7~圖10所示。
由圖7可以看出,隨著節(jié)點(diǎn)移動性的增大,路由失效次數(shù)增多,各協(xié)議平均端到端時延整體呈現(xiàn)增加趨勢。AODV-UU通過減小分組投遞次數(shù)和路由失效時間,大大降低了平均端到端時延。
由圖8可以看出,隨著節(jié)點(diǎn)移動性增大,路由失效次數(shù)增多,各協(xié)議的路由發(fā)現(xiàn)頻率整體呈增大趨勢,AOMDV在一次路由發(fā)現(xiàn)過程中可以找到多條鏈路獨(dú)立路由作為備份路由,大大降低了路由發(fā)現(xiàn)頻率。而相同連接對數(shù)條件下,AODV-UU的路由發(fā)現(xiàn)頻率低于AODV。
由圖9可以看出,隨著節(jié)點(diǎn)移動性增大,各協(xié)議歸一化路由開銷整體呈現(xiàn)增大趨勢。當(dāng)連接對數(shù)=10,AODV-UU歸一化路由開銷最低。當(dāng)連接對數(shù)=20,AOMDV歸一化路由開銷最低。當(dāng)連接對數(shù)=10時,隨著節(jié)點(diǎn)移動性增大,AOMDV的多徑路由大量失效,同時,多徑機(jī)制的路由控制包更大,產(chǎn)生的路由響應(yīng)RREP更多,計(jì)算多徑有效性的開銷也更大,直接導(dǎo)致AOMDV的歸一化路由開銷偏大。當(dāng)連接對數(shù)=20時,由于隱終端和暴露終端的問題,網(wǎng)絡(luò)中的碰撞和擁塞急劇增多,AOMDV的多徑機(jī)制,一定程度上緩解了信號間的相互干擾,從而獲得了較低的歸一化路由開銷[5]。
由圖10可以看出,隨著節(jié)點(diǎn)移動性增大,各協(xié)議分組投遞率整體呈現(xiàn)減小趨勢。相同連接對數(shù)條件下,AODV的分組投遞率最高,AODV-UU的分組投遞率略低于AODV。隨著節(jié)點(diǎn)移動性增大,AOMDV的多徑路由大量失效,造成分組投遞率急劇下降,已經(jīng)難以接受[5]。
綜上所述,AODV-UU的整體性能優(yōu)于AODV和AOMDV,尤其是在節(jié)點(diǎn)高速運(yùn)動的情況下。因此,AODV-UU對于在高速機(jī)動平臺間建立動態(tài)、健壯和高性能的無線自組織網(wǎng)絡(luò)具有一定的應(yīng)用價值。
為了降低AODV-UU的路由發(fā)現(xiàn)頻率和歸一化路由開銷,可以借鑒AOMDV,在AODV-UU中引入多徑路由機(jī)制。
Ad Hoc網(wǎng)絡(luò)技術(shù)因其無需架設(shè)網(wǎng)絡(luò)設(shè)施、可快速展開和抗毀性強(qiáng)等特點(diǎn),在未來軍用數(shù)據(jù)鏈領(lǐng)域的應(yīng)用前景非常廣闊。路由協(xié)議是Ad Hoc網(wǎng)絡(luò)技術(shù)的核心。而按需距離矢量路由(AODV)因其優(yōu)越的性能,逐步成為研究熱點(diǎn)。通過對AODV、AOMDV和AODV-UU路由協(xié)議的仿真結(jié)果進(jìn)行比較,說明了AODV-UU路由協(xié)議性能的優(yōu)越性,對AODVUU進(jìn)行多徑改進(jìn)是筆者今后研究的方向。
[1]鄭少仁,王海濤,趙志峰,等.Ad Hoc網(wǎng)絡(luò)技術(shù)[M].第1版.北京:人民郵電出版社,2005.
[2]TONY SKINNER.DARPA Successfully Demonstrates Tactical Targeting Network Technology[J].Jane's Defence Weekly,2005,42(44):2.
[3]DARPA.Tactical Targeting Networked Technology(TTNT)Industry Day Sol[EB/OL](2000-10-27)[2007-05-10].http://www.darpa.mil/baa/TTNT-ID-00.htm.
[4]MUHAMMAD ASIM MUBARIK,SHOAB AHMAD KHAN,SYED AYAD HASAN et al.Implementation of Geocast Enhanced AODV-UU in Linux Testbed[C]//2009 Eigth IEEE/ACIS International Conference on Computer and Information Science.Shanghai:IEEE Computer Society,2009:803-807.
[5]GOWRISHANKAR S,SUBIRKUMARSARKAR,G.BASAVARAJU T.Performance Analysis of AODV,AODVUU,AOMDV and RAODV over IEEE 802.15.4 in Wireless Sensor Networks[C]//20092nd IEEE International Conference on Digital Object Identifier,Beijing,2009:59-63.