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