【文章內容簡介】 斷裂處節(jié)點一個比其鄰節(jié)點都高的高度值，這樣分組就在此處返回，這一過程稱之為反轉，并在斷裂處附近查找可用路由，協(xié)議的控制報文只在最靠近拓撲變化的地方產(chǎn)生。此種算法中路由不一定是最優(yōu)的，其常常使用次優(yōu)路由以減少路由發(fā)現(xiàn)過程帶來的開銷。但是當拓撲較為復雜并且移動性較強時，其收斂較慢，開銷較大；并且TORA協(xié)議是基于同步時鐘的，所以時鐘的時間不同步可能導致路由協(xié)議故障。綜上所述，反應式路由依靠應用層數(shù)據(jù)驅動協(xié)議的運行，因此一般認為反應式路由協(xié)議比先應式更適合Ad Hoc網(wǎng)絡。但是根據(jù)具體應用場合和應用需求不同，兩類協(xié)議各有所長，也都有自己的局限。先應式路由協(xié)議需要不斷的交互路由信息來維護路由表，所以協(xié)議開銷較大 (尤其在拓撲變化較頻繁、劇烈時)，但是尋路時延較小且受上層業(yè)務流量的影響較小；反應式路由協(xié)議僅在需要時才搜索路由，開銷相對較小，但是尋路時延較大，并且受數(shù)據(jù)突發(fā)影響較嚴重，即如果相鄰節(jié)點幾乎同時發(fā)起路由查找請求，往往尋路失敗的概率較大。為了彌補雙方的不足，出現(xiàn)了先應式和反應式路由協(xié)議的結合體混合式路由協(xié)議?；旌鲜铰酚蓞f(xié)議的基本思想是結合先應式和反應式路由的尋路方式，在部分區(qū)域內采用先應式路由，而在另一部分區(qū)域內則采用反應式，從而獲得高效與低開銷的統(tǒng)一?；旌鲜铰酚蓞f(xié)議中比較有代表性的是ZRP[21]和SHARP[22]。下面分別介紹這兩個路由協(xié)議。[21]路由協(xié)議ZRP(Zone Routing Protocol) 協(xié)議基于近端節(jié)點先應式而遠端節(jié)點反應式的思想，通過定義先應式半徑d區(qū)別維護路由表。先應式半徑d一般以跳數(shù)為單位，節(jié)點利用DV算法維護d(d一般設為2)跳以內的路由，而當需要尋址到d跳以外時，再利用反應式路由算法尋找路由，其反應式路由機制類似DSR。先應式半徑區(qū)域內的路由稱為Intrazone路由，而先應式半徑區(qū)域外的路由稱為Interzone路由。，節(jié)點S 的一個半徑為2的路由區(qū)域。與節(jié)點的距離等于區(qū)域半徑的點稱為邊界點，如節(jié)點K即為S的邊界點。S維護在虛線以內(2跳)的節(jié)點的路由表，而在兩跳以外節(jié)點(如節(jié)點J)的路由通過類似于DSR的反應式機制來發(fā)現(xiàn)和維護。 ZRP半徑為2的路由區(qū)域[22]路由協(xié)議另外一種混合式路由協(xié)議為SHARP(Sharp Hybrid Adaptive Routing Protocol)路由協(xié)議。SHARP是針對ZRP協(xié)議中存在的靜態(tài)半徑和區(qū)域重疊等問題由V. Ramasubramanian等人提出的，其是一種可以根據(jù)網(wǎng)絡流量動態(tài)調整先應式區(qū)域半徑大小的路由協(xié)議，其特點體現(xiàn)在如下幾個方面：協(xié)議可以根據(jù)網(wǎng)絡流量特性來動態(tài)調整先應式半徑的大小。SHARP協(xié)議中考察節(jié)點作為目的節(jié)點的屬性，對于繁忙的目的地節(jié)點(即有多個源發(fā)送數(shù)據(jù)給它)，其設置先應式的半徑較大，而對于不繁忙的目的節(jié)點，其設置先應式半徑較小。這樣在網(wǎng)絡流量較小的時候，全網(wǎng)退化成反應式的尋路，而當全網(wǎng)流量較大且分布均勻時，則全網(wǎng)退化成先應式路由。SHARP的區(qū)域內先應式協(xié)議借鑒了DSDV（序號機制）、TORA的有向圖機制、以及piggyback技術，其反應式的路由基于AODV協(xié)議；SHARP的先應式路由維護、半徑調整以及維護都是通過鄰近節(jié)點之間交互信息實現(xiàn)的，交互的信息包括先應式半徑、丟包率等信息。 SHARP的區(qū)域調整示意圖如圖7所示，S為源節(jié)點，D為目的節(jié)點，r先應式半徑。目的節(jié)點D根據(jù)自己統(tǒng)計的信息計算出最佳先應式半徑為r。源節(jié)點采用AODV的方式發(fā)起到目的節(jié)點D的路由查找，到達hr跳之后路由查找結束，路由變?yōu)橄葢?。SHARP基于先應式引入開銷而反應式引入時延的假設，通過動態(tài)調整節(jié)點的先應式區(qū)域半徑，達到降低開銷和控制時延以及限制丟包率的目的(開銷、時延以及丟包率均是先應式區(qū)域半徑R的函數(shù))。上邊介紹了先應式、反應式以及混合式路由協(xié)議和各類中比較典型的路由協(xié)議?？傮w看來，幾類協(xié)議在尋路方式上風格迥異，各有特點。一般我們習慣從尋路時延、路由開銷以及能量耗費等[23]諸多方面來對路由協(xié)議進行考察比較，（表中標注的高、中、低是相對而言）： 各類路由協(xié)議比較先應式反應式混合式典型協(xié)議DSDV，WRP，F(xiàn)SR，OLSRDSR，AODV，TORAZRP，SHARP尋路時延低高Intrazone低Interzone高路由開銷高低中能量耗費高低中帶寬占用高低中先應式路由協(xié)議之間的比較主要從路由環(huán)路、存儲表的數(shù)目、路由更新方式等方面考察，： 先應式路由協(xié)議比較先應式路由協(xié)議DSDVWRPFSROLSR路由環(huán)路避免是是，不立刻是是存儲表的數(shù)目2445路由更新方式周期+按需周期+按需周期周期是否使用HELLO是是否是反應式路由協(xié)議之間的比較主要從路由開銷、多路徑支持以及復雜度等方面考察，： 反應式路由協(xié)議比較反應式路由協(xié)議DSRAODVTORA復雜度中中高尋路開銷低中中多播支持否是否多路徑支持否是是路由保存路由表路由緩存路由表路由度量最新及最短路徑最短路徑最短路徑本章對課題研究的Ad Hoc網(wǎng)絡路由協(xié)議進行了介紹，包括先應式、反應式和混合式路由協(xié)議，并對各類典型路由協(xié)議的進行了描述和分析。通過本章的分析發(fā)現(xiàn)，雖然目前已經(jīng)誕生了很多路由協(xié)議，但是這些協(xié)議大部分都是針對一般的應用提出的，而與具體應用場景的關聯(lián)不夠緊密。這也使得現(xiàn)有的路由協(xié)議應用在艦船編隊網(wǎng)絡中都有不足之處，難以適應艦船編隊網(wǎng)絡的特點。本文根據(jù)艦船編隊網(wǎng)絡的特點，借鑒現(xiàn)有路由協(xié)議的研究成果，設計了一種適用于艦船編隊網(wǎng)絡的混合式路由協(xié)議，稱之為HSRP(Hybrid Source Routing Protocol)路由協(xié)議，本文將在第三章對其進行詳細的介紹。第三章 艦船編隊無線自組織網(wǎng)絡的路由協(xié)議設計從論文第二章關于Ad Hoc網(wǎng)絡路由協(xié)議的闡述可以看出，研究人員已經(jīng)在此領域取得了豐碩的成果，但是考慮到艦船編隊網(wǎng)絡中物理信道、移動模型和流量分布上的特殊性，這些研究成果難以直接應用，或者說不能很好的適應艦船編隊網(wǎng)絡應用的特點。我們在借鑒論文第二章介紹的相關思想的基礎上，提出并設計了一種專門針對艦船編隊網(wǎng)絡應用的路由協(xié)議，稱之為HSRP(Hybrid Source Routing Protocol)路由協(xié)議。HSRP協(xié)議是以艦船編隊網(wǎng)絡為應用背景的混合式路由協(xié)議，協(xié)議中加入了基于拓撲變化感知的路由更新和基于MRP(Multi Point Relay，多點中繼)[17]的路由開銷控制策略，力求通過簡單有效的機制提高路由協(xié)議的性能，最終達到滿足艦船編隊網(wǎng)絡應用需要的目的。本章第二節(jié)介紹艦船編隊網(wǎng)絡場景的特點，第三節(jié)介紹HSRP協(xié)議的設計，第四節(jié)對HSRP進行仿真及結果分析，最后給出小結。艦船編隊網(wǎng)絡是Ad Hoc網(wǎng)絡的典型應用之一，其場景的諸多特點使其不同于一般地面上的Ad Hoc網(wǎng)絡應用環(huán)境?？偨Y起來，其特點有以下幾個方面：物理信道。水上環(huán)境的特點使水上無線信道有別于陸地。水面相對陸地更加空曠平坦，無線通信受地形影響相對較小；編隊網(wǎng)絡中艦船之間通信設備的性能差異不大，可認為節(jié)點間是雙向鏈路；水面環(huán)境下的信道衰落和多徑等特點也不同于地面。移動模型。艦船編隊網(wǎng)絡中節(jié)點的移動具有顯著的規(guī)律性。多艘艦船執(zhí)行任務時往往編隊行進，而且編隊的隊形有多個，編隊可能經(jīng)常需要從一個隊形變化到另一個隊形。這使得艦船編隊網(wǎng)絡的拓撲變化具有兩個特點，一個是拓撲的階段穩(wěn)定性，另一個是拓撲變化的全局性。艦船以某一個隊形行進時，艦船的位置相對穩(wěn)定；當艦船編隊從一個隊形變化到另一個隊形時，各艦船之間的鄰接關系基本上全部發(fā)生了變化，基本上很少出現(xiàn)拓撲局部變化的情形。流量模型。基于當前的艦隊組織模式可以預見,編隊艦船之間的業(yè)務流量具有顯著的不均衡性。一方面旗艦要經(jīng)常下發(fā)指揮控制信息給其它僚艦，另一方面各僚艦要經(jīng)常向旗艦報告一些信息，這就導致旗艦附近的負載很重而其它僚艦的負載相對較少且分布平均。根據(jù)應用場景的這些特點，我們設計了HSRP路由協(xié)議，第三節(jié)描述該路由協(xié)議的設計。基于艦船編隊網(wǎng)絡的應用，HSRP路由協(xié)議采用混合式的路由策略，同時協(xié)議中融入了跨層設計的思想，以便在得到較好網(wǎng)絡時延的同時控制協(xié)議的開銷。艦船編隊網(wǎng)絡中的MAC協(xié)議采用的是混合式的TDMA協(xié)議(簡稱HTDMA)，其在MAC層保存兩跳范圍鄰居節(jié)點的信息。為節(jié)省無線網(wǎng)絡寶貴的信道資源，HSRP協(xié)議直接從MAC層跨層共享兩跳范圍內的路由信息來構造先應式的路由表。對于2跳范圍外的路由，HSRP采用類似于DSR的反應式路由機制。ZRP協(xié)議中，先應式半徑區(qū)域內的路由一般稱為Intrazone，而先應式半徑區(qū)域外的路由則稱為Interzone，在HSRP協(xié)議中我們也延續(xù)這一說法。同時，HSRP的反應式路由過程中加入了類似OLSR協(xié)議的MPR思想，來限制廣播包在網(wǎng)絡中的擴散，降低協(xié)議的開銷。傳統(tǒng)混合式路由協(xié)議中，先應式半徑內的路由需要通過節(jié)點之間的路由信息交互來實現(xiàn)，一般采用距離矢量(DV)算法或鏈路狀態(tài)(LS)算法，例如ZRP中先應式半徑內的路由維護采用的是距離矢量算法。而HSRP協(xié)議有效利用了艦船編隊網(wǎng)絡體系結構的特點，通過跨層信息共享來減小路由開銷。艦船編隊網(wǎng)絡的MAC層使用的是混合式的TDMA型信道接入控制協(xié)議，該協(xié)議在MAC層維護兩跳范圍內的節(jié)點信息，并且兩跳范圍節(jié)點信息會每隔2秒更新一次。所以，從艦船編隊網(wǎng)絡的整體架構考慮，為有效利用MAC層維護的兩跳范圍節(jié)點信息，HSRP協(xié)議中融入了跨層設計的思想。HSRP通過跨層共享從MAC層獲取兩跳范圍節(jié)點信息，從而構造兩跳范圍的路由表。由于MAC層的兩跳范圍節(jié)點信息會每隔2秒更新一次，更新的頻度足夠快，基本上能夠保證信息的及時準確，所以路由協(xié)議不再單獨通過節(jié)點間信息交互的方式維護兩跳范圍拓撲。同時，也是為了使HSRP協(xié)議簡單實用，將HSRP協(xié)議的先應式半徑設置為2。這樣一來，HSRP完全不用任何其它的耗費就能夠及時準確的更新和維護先應式的路由表，很大程度上降低了協(xié)議的開銷。HSRP協(xié)議采用反應式維護中遠距離(兩跳以外)節(jié)點的路由，其實現(xiàn)方式類似DSR協(xié)議，并且針對本方案的應用背景進行了優(yōu)化，以提高其路由命中率和降低路由開銷。 HSRP反應式路由機制HSRP對于先應式半徑之外的節(jié)點采取反應式的策略路由，其反應式路由機制設計如下：當節(jié)點需要向2跳以外節(jié)點發(fā)送數(shù)據(jù)時，首先在路由緩存中查找是否有到目的節(jié)點的路由，若有則將該路由添加到數(shù)據(jù)包的源路由選項中，然后封裝成HSRP的源路由數(shù)據(jù)包發(fā)送；若緩存中沒有到目的節(jié)點的路由，則發(fā)送RREQ消息開始路由尋找。RREQ消息中含有源地址、目的地址、消息的ID號和RREQ消息所經(jīng)過的節(jié)點等信息。中間節(jié)點收到RREQ消息之后，把RREQ的ID字段信息保存在路由請求表(Route Request Table)表中，但是在具有相同源節(jié)點和目的節(jié)點的RREQ路由請求中，此表只記錄其最新的ID號。于是，當節(jié)點收到RREQ時，其查找Route Request Table表中對應的RREQ項目，把RREQ中的ID號與表中對應項目記錄的ID號對比之后決定是丟棄還是進行處理。中間節(jié)點在轉發(fā)RREQ之前，先查找本地路由緩存。若本地路由緩存中有到目的節(jié)點的路由，則該節(jié)點將比較自己的鄰居和上一個轉發(fā)該RREQ節(jié)點(即上一跳節(jié)點)的鄰居信息。如果本節(jié)點與上一跳轉發(fā)此RREQ節(jié)點具有相同的鄰居，則丟棄該RREQ數(shù)據(jù)包。如果該節(jié)點與上一跳節(jié)點具有不同的鄰居，并且是第一次收到該路由申請的話，節(jié)點將通過一定的算法對該路由申請進行轉發(fā)。如果中間節(jié)點需要對路由申請進行轉發(fā)，那么節(jié)點先隨機的回退一段時間，若在隨機回退期間監(jiān)聽到有其它節(jié)點回送相應的RREP消息，則停止回退并丟棄此RREQ。如果中間節(jié)點收到RREQ消息并且本地先應式路由表中存在通往目的地的路由，則利用該路由和RREQ消息中的源路由構造RREP消息，并發(fā)送給源節(jié)點。目標節(jié)點收到RREQ之后回送RREP消息，RREP數(shù)據(jù)包是HSRP的源路由IP包，其中攜帶的源路由即是RREQ中攜帶路由的逆序(鏈路均為雙向鏈路)。源節(jié)點在沒有獲得正確的路由之前，先把沒來得及發(fā)送的數(shù)據(jù)包緩存在“發(fā)送緩存中，發(fā)送緩存中的每個數(shù)據(jù)包將與數(shù)據(jù)進入緩存的時間相關聯(lián)。在緩存中等待發(fā)送的時間里，源節(jié)點將依照截斷二進制指數(shù)算法向數(shù)據(jù)包的目的節(jié)點連續(xù)發(fā)送RREQ消息，直到路由成功或確信目的端不可達為止。在一定時間之內沒有發(fā)送出去的數(shù)據(jù)包將被從緩存中清除掉，并報告超時。 源節(jié)點反應式路由流程 中間節(jié)點源路由流程研究艦船編隊網(wǎng)絡的移動模型發(fā)現(xiàn)，網(wǎng)絡的拓撲變化具有全局性，主要體現(xiàn)在網(wǎng)絡拓撲的變化一般是全網(wǎng)范圍的，很少出現(xiàn)網(wǎng)絡局部微小變化的情況。而全網(wǎng)的拓撲變化主要是由編隊的隊形發(fā)生變化引起的。針對網(wǎng)絡拓撲變化的這一特點，HSRP協(xié)議中采用了一種能夠快速感知拓撲變化的機制，以使路由協(xié)議能夠盡快更新路由，減小拓撲變化使路由失效帶來的不利影響。HSRP協(xié)議中，節(jié)點利用鄰居節(jié)點的變化程度來感知網(wǎng)絡拓撲的變化。如果全網(wǎng)的拓撲發(fā)生了變化，那么節(jié)點在路由維護過程中通過路由更新前后的對比，能夠發(fā)現(xiàn)鄰居節(jié)點發(fā)生了變化，當變化鄰居節(jié)點的個數(shù)超過了一定的門限時，可以認為全網(wǎng)的拓撲發(fā)生了變化。，圖中虛線圓是節(jié)點A的一跳通信距離?？梢钥吹剑@時節(jié)點A的一跳鄰居節(jié)點分別為節(jié)點B、節(jié)點C、節(jié)點D和節(jié)點E。，這時節(jié)點A的一跳鄰居為節(jié)點D、節(jié)點E、節(jié)點F和節(jié)點G。節(jié)點的移動使節(jié)點F和G成了A的一跳鄰居，而原來的鄰居節(jié)點B和C則移動到了節(jié)點A的一跳范圍之外。節(jié)點A在拓撲變化后兩個鄰居節(jié)點發(fā)生了變化。，此時節(jié)點A可以判斷全網(wǎng)的拓撲已經(jīng)發(fā)生了變化。 拓撲變化前的節(jié)點分布 拓撲變化之后節(jié)點分布節(jié)點根據(jù)鄰居變化度和預置的鄰居變