【正文】 強、保密性好。 本章首先介紹 Ad Hoc 網(wǎng)絡(luò)路由協(xié)議設(shè)計目標(biāo)及其所面臨的問題，之后介紹 Ad Hoc 網(wǎng)絡(luò)路由協(xié)議的分類并對其中幾種典型的路由協(xié)議進(jìn)行介紹，最后對這幾種路由協(xié)議進(jìn)行定性比較。 而 設(shè)計滿足 Ad hoc 網(wǎng)絡(luò)環(huán)境下的路由協(xié)議所面臨的困難主要有以下幾點 : (1)頻繁變化的 網(wǎng)絡(luò) 拓?fù)浣Y(jié)構(gòu)。 Ad Hoc 網(wǎng)絡(luò) 自 身的傳輸媒介是 依靠 開放性的無線電波，網(wǎng)絡(luò)本身提供的帶寬 有限以及信號之間的沖突和干擾，使移動節(jié)點可得到的有限的傳輸帶寬 遠(yuǎn)遠(yuǎn)小于理論上的最大帶寬。這就要求路由協(xié)議盡可能簡單，因而增加了路由協(xié)議的設(shè)計難度。如圖 所示。特別是在網(wǎng)絡(luò)規(guī)模比較大的情況下網(wǎng)絡(luò)結(jié)構(gòu)越加頻繁，這樣每個節(jié)點都要維護(hù)一張路由表就沒什么意義，而且資源的浪費也是 越加嚴(yán)重。與主動式路由協(xié)議相比，被動式路由協(xié)議的開銷小，但是數(shù)據(jù)報傳送的時延較大，不適合實時性的通信場合。也就是說，關(guān)于鄰居的信息比遙遠(yuǎn)的目的地節(jié)點的信息更重要。 下面簡單對比一下各類路由協(xié)議的優(yōu)缺點，如表所示： 表 各類路由協(xié)議比較 主動路由協(xié)議 被動路由協(xié)議 混合路由協(xié)議 控制開銷 高 移動越大開銷越大 中等 是否要周期更新 是 否 是 路由時延 小 大 一般 可擴(kuò)展性 弱 一般 強 耗電量 高 低 中等 拓?fù)渥兓m應(yīng)性 弱 強 一般 帶寬開銷 高 低 中等 路由結(jié)構(gòu) 大多數(shù)是平面 平面結(jié)構(gòu) 分級 結(jié)構(gòu) 路由信息可靠性 一直有效 需要時有效 部分一直有效，部分需要時有效 由上表我們可以知道的是，主動路由協(xié)議在移動自主網(wǎng)絡(luò)結(jié)構(gòu)比 較簡單、規(guī)模較小的情況下有較好的性能，被動路由協(xié)議比表路由協(xié)議更適應(yīng)網(wǎng)絡(luò)的動態(tài)變化結(jié)構(gòu)，而混合路由協(xié)議則是前兩種路由協(xié)議各個性能的折中體現(xiàn)。 DSDV 路由協(xié)議 DSDV (DestinationSequenced DistanceVector Routing)路由協(xié)議是基于經(jīng)典BellmanFord路由選擇過程的改進(jìn)型路由表算法。表中的每一個條目都有一個由目的節(jié)點注明的序列號 (Sequence Number)，序列號能幫助節(jié)點區(qū)分有效和過去的路由信息。 OLSR 路由協(xié)議 OLSG(Optimized Link State Routing)路由協(xié)議是由 IETF MANET 工作組提出作為 RFC 標(biāo)準(zhǔn)化的一種基于多點中繼 (Multipoint Relays， MPR)概念的鏈路狀態(tài)協(xié)議。在 OLSR中 MPR 負(fù)責(zé)周期性的向網(wǎng)絡(luò)散布 TC 分組、參與路由計算：而其他非 MPR 節(jié)點則不參與路由計算，也不發(fā)送和轉(zhuǎn)發(fā) TC 分組。 圖 多點中繼示意圖 DSR 路由協(xié)議 DSR(Dynamic Source Routing Protocol)路由協(xié)議，它包括兩個部分：一為路徑尋找 (Route Discovery)，另一部分就是路徑的維持 (Route Maintenance)。 (2) 重新發(fā)出路徑尋找封包：如果發(fā)送端沒有其它可用的路徑又有重新發(fā)送的必要時，可以由發(fā)送端發(fā)出路徑尋找封包，重新尋找新路徑。 AODV 協(xié)議中需要建立路由時，源節(jié)點廣播一個路由請求 RREQ(Route Request)，包括目的節(jié)點地址、目的節(jié)點序號、廣播序號、源節(jié)點地址、源節(jié)點序列號、上一跳地址和跳數(shù)。在 AODV 協(xié)議中，只要有數(shù)據(jù)包從源節(jié)點發(fā)往目的節(jié)點，路由表就要一直維護(hù)下去。 AODV 協(xié)議時依賴于對稱性的鏈路，而不能處理非對稱性鏈路的網(wǎng)絡(luò)。 ZRP 路由協(xié)議 ZRP(Zone Routing Protocol) 協(xié)議時一個主動和被動路由協(xié)議的組合，網(wǎng)絡(luò)內(nèi)的所有節(jié)點都有一個以自己為中心的虛擬區(qū)，區(qū)內(nèi)的節(jié)點數(shù)與設(shè)定的區(qū)半徑有關(guān)，因此區(qū)時重疊的，這是與分層路由的區(qū)別。每個節(jié)點必須記錄區(qū)域半徑內(nèi)所有節(jié)點的信息。 各路由協(xié)議性能比較 前面簡單介紹了幾種具有代表性的 Ad hoc 路由協(xié)議，下面這幾種常見的路由協(xié)議進(jìn)行定性比較。所以主動路由協(xié)議可擴(kuò)展性較差。另外，在按需路由協(xié)議中，節(jié)點采用泛洪的方式發(fā)現(xiàn)和維護(hù)路由，因此在大負(fù)載和拓?fù)渥兓l繁的網(wǎng)絡(luò)中，按需路由的控制開銷較大。而在區(qū)域間通信的時采用按需路由，降低了網(wǎng)絡(luò)開銷，因此， ZRP 協(xié)議在所介紹的協(xié)議中具有最好的可擴(kuò)展性。在 Ad Hoc 網(wǎng)絡(luò)中廣播將一個節(jié)點發(fā)送的消息傳送給網(wǎng)絡(luò)中所有其他節(jié)點，在主動路由協(xié)議中廣播應(yīng)用于節(jié)點拓?fù)湫畔⒏拢诒粍勇酚蓞f(xié)議中廣播廣泛應(yīng)用于路發(fā)現(xiàn)或新網(wǎng)絡(luò)節(jié)點狀態(tài)更新。但研究表明無控制的洪泛會產(chǎn)生大量的冗余轉(zhuǎn)播，加重網(wǎng)絡(luò)的通信負(fù)擔(dān)，消耗大量的網(wǎng)絡(luò)資源。廣播帶來的問題是因廣播有以下特點： (1) 廣播時自發(fā)性的。由于在現(xiàn)有的 MAC 層協(xié)議中，對于廣播信息是不發(fā)送ACK 確認(rèn)幀的。由于廣播轉(zhuǎn)發(fā)的時間選擇湖南人文科技學(xué)院畢業(yè)設(shè)計 是高度相關(guān)的，所以很容易發(fā)生信號碰撞， RTS/CTS 并不適用。由于泛洪式廣播 (Flooding)不需要任何特殊的設(shè)備或算法，因此是廣為采用的一種方法，而在 Ad hoc 網(wǎng)絡(luò)上的廣播，也大多以泛洪式廣播法來進(jìn)行。如果當(dāng)節(jié)點準(zhǔn)備轉(zhuǎn)發(fā)收到的廣播時，其所有的鄰居節(jié)點已經(jīng)收到該廣播包，該廣播稱之為冗余廣播。如圖 中，節(jié)點 A 發(fā)送一個廣播包，而節(jié)點 B 轉(zhuǎn)發(fā)這個廣播包。假設(shè) B 能隨機位于 A 覆蓋范圍中的任意一點，其平均值可以通過圓半徑 x 在 [0, r]上的積分得到： ? ?? ??? ????r rdxr dI N T Crx0 222 )(2 () 由此可見，在前一次廣播后，轉(zhuǎn)發(fā)廣播信息只能提供平均 41%的額外覆蓋面積。 湖南人文科技學(xué)院畢業(yè)設(shè)計 信道競爭分析 廣播風(fēng)暴的另一個問題就是節(jié)點之間對信道的競爭。假定 B 和 C 是兩個接收主機， B 在 A 傳輸范圍內(nèi)的位置隨機。另一方面，有一臺主機發(fā)送時不發(fā)生信道爭搶的概率 CF(n, k)隨著 N 增加迅速下降。 CSMA/CA 機制需要一臺主機在發(fā)送一條消息后，或是當(dāng) 主機有消息發(fā)送并且前面的退避程序已經(jīng)結(jié)束，但是發(fā)現(xiàn)信道媒介正在被占用的時候，立即啟動一個備份程序。首先，如果 x 周圍的信道長時間空閑， x 的鄰居也許都已經(jīng)完成了它湖南人文科技學(xué)院畢業(yè)設(shè)計 們的退避程序。第三，一旦發(fā) 生了碰撞，由于沒有沖突檢測 (CD)機制，即使已經(jīng)發(fā)送的比特已不可 用，主機仍將一直傳輸完該分組，而且分組越長，浪費越大。這里簡單的洪泛法就不做介紹了，下面我們介紹一下這些應(yīng)對廣播風(fēng)暴的方法。顯然， p=1 時，本方案相當(dāng)于洪泛。 基于計數(shù)器算法 計數(shù)器 算法 (CounterBased Scheme)，計數(shù)器的基本思想是節(jié)點收到相同報文的次數(shù)反比于轉(zhuǎn)發(fā)報文所獲得的額外覆蓋面積。如圖，假設(shè)節(jié)點使用計數(shù)器廣播算法且 C=2，節(jié)點 3 相互之間為一跳鄰居。這樣節(jié)點 4 將不會收到來自節(jié)點 1 的報文。當(dāng)這個值太低的時候，我們應(yīng)該禁止該主機轉(zhuǎn)發(fā)，基于計數(shù)器的方案就是基于這一點設(shè)計的。另外，此算法運用在稠密的網(wǎng)絡(luò)環(huán)境中時一些節(jié)點將不會進(jìn)行轉(zhuǎn)發(fā)，在節(jié)點稀疏的環(huán)境中，有可能所有的節(jié)點都參與轉(zhuǎn)發(fā)。極端情況，如果 d=0，湖南人文科技學(xué)院畢業(yè)設(shè)計 則 H 對報文的轉(zhuǎn)發(fā)對于探索新區(qū)域沒有任何貢 獻(xiàn)?；诰嚯x的算法同樣存在覆蓋率 低的問題。否則節(jié)點緩存數(shù)據(jù)并等待一個隨機時間。假設(shè)一個節(jié)點的位置在 (0, 0)處，它從位置為 (x1, y1)， (x2, y2)， … ..， (xn, yn)的 k 的節(jié)點接收相同的消息，我們用 AC((x1, y1)， (x2, y2)， … ..， (xn, yn))來表示該額外覆蓋面積與 πr2 的比值。一個可行的辦法就是用用網(wǎng)格填充來估計 AC 的值。 湖南人文科技學(xué)院畢業(yè)設(shè)計 圖 主機位于有三個發(fā)送主機組成的三角形內(nèi) 圖 主機位于有三個發(fā)送主機組成的三角形之外 圖 使用多邊形測試可獲得的最大額外覆蓋面積分析 我們通過幾何計算來證明采用以上策略的原因。假定 A 和B 是這個邊界的兩個端點，當(dāng) A 和 B 被傳輸半徑為 r 的主機 X 分開如圖 時，X 提供的額外覆蓋最大，該面積為 [15]： 222022222 rrdxxrdxxrr rr ???????? ????????? ???? ? 這種算法雖然具備很高的可達(dá)性，但還需要如 GPS 這種設(shè)備的配合，以便為每個節(jié)點 提供定位信息，這和 Ad Hoc 網(wǎng)絡(luò)不需要預(yù)先設(shè)置的基礎(chǔ)設(shè)施定義不符。 A 和 B 是以 S 和 N 為圓心，以各自的覆蓋半徑 RS， RN為半徑的兩個交點。 基于角度算法 角度算法 (Angle Scheme )，角度算法是利用主機之間的相對角度來判斷是否轉(zhuǎn)發(fā)廣播信息的策略。我們可以注意到，當(dāng) X 落在多邊形的邊界上時。 假定主機 X 收到從 A、 B、 C 發(fā)送的廣播消息各一次，比較圖 和圖 ，容易得到如果 X 不在該多邊形內(nèi)，它將能提供更多的額外覆蓋范圍 (陰影部分所示 )。這種方法的困難之處在于計算 AC，因為我們需要計算一些圓中重疊的面積。如果等待時間到了，并且計算出轉(zhuǎn)發(fā)所獲得的額外覆蓋面積仍大于門限值則轉(zhuǎn)發(fā)這個報文。 基于位置算法 基于位置的算法 (LocationBased Scheme)，在基于位置的廣播算法中，每當(dāng)節(jié)點發(fā)起或轉(zhuǎn)發(fā)一個廣播報文時，節(jié)點將自己的位置信息添加到報文中，這樣接收節(jié)點即可獲得發(fā)送節(jié)點的位置并計算出轉(zhuǎn)發(fā)所獲得的額外覆蓋面積。因此，基于距離的算法以節(jié)點間的距離作為判斷節(jié)點是否轉(zhuǎn)發(fā)廣播的準(zhǔn)則。例如，節(jié)點 H 收到來自其鄰居節(jié)點 S 發(fā)送的廣播報文時， H 得到它與 S 的距離 d。選擇一個計數(shù)器門限值 C，當(dāng) c≥C 時，節(jié)點轉(zhuǎn)發(fā)禁止。如果在按需路由協(xié)議的路由發(fā)現(xiàn)過程中會導(dǎo)致路由查找時間增大。如果節(jié)點 3 的定時器先超時并收到報文，則節(jié)點 2 收到來自節(jié)點 3 的報文后 c 加 1。在此期間，節(jié)點沒收到這個報文一次，計數(shù)器就加 1。本算法的優(yōu)點就是簡單易行，降低了延時和帶寬損耗。在這種情況下，概率 p 的選擇尤為關(guān)鍵。由此出發(fā)，目前對降低廣播風(fēng)暴發(fā)生的研究，大多是從減少報文傳送數(shù)量來著手。特別是由于存儲轉(zhuǎn)發(fā) (RF)延時和傳輸延時造 成載波檢測不及時的時候，這種現(xiàn)象特別明顯。當(dāng) 計數(shù)器值到 0 時，退避程序完成。 信號碰撞分析 在 MANET 中，沒有基站和接入點。 設(shè) A 和 B 的距離為 x，則 C 和 B 產(chǎn)生競爭的概率為： ? ?? ????r dxr rxI N T Cx0 0022 59)(2 () 顯然，當(dāng)轉(zhuǎn)發(fā)節(jié)點個數(shù) N 增加時，競爭的 機會 也變大。 還是圖 ，假設(shè)主機 A 發(fā)送廣播消息以后有 N 個主機接收到這條消息，因為 A 周圍可能有兩個以上的主機很接近，如果這些主機都想轉(zhuǎn)發(fā)這條廣播消息，就可能產(chǎn)生無線信道的爭搶。 對于一般情況，一個主機在收到一條 消息 k 次以后轉(zhuǎn)發(fā)該消息所帶來的覆蓋增用 ECA(k)表示。假設(shè) A 和 B 的半徑為 r， A 和 B 的圓心距為 d，于是 |S ba|= ∏ r2 INTC(d)，其中 INTC(d)是圓心距離為 d 的兩個圓之間的重疊面積： 圖 節(jié)點轉(zhuǎn)發(fā)廣播 信息帶來的覆蓋增益 ? ? dxxrdI N T C rd? ?? 2 224)( () 當(dāng) d=r 是，覆蓋面積 |S ba|最大，此時 |S ba| = ∏ r2 INTC(d) = r2( ∏ /3 + 23 ) ≈ ∏ r2 () 以上分析表明，一次廣播轉(zhuǎn)發(fā)能在以前傳輸?shù)幕A(chǔ)上提供 0~60%的額外覆蓋面積。如圖 所示，節(jié)點 S 將報文廣播出去，周圍節(jié)點都收到了信息報文并進(jìn)行轉(zhuǎn)發(fā)，而此時節(jié)點 2 的廣播就是冗余廣播 (虛線圓內(nèi)為節(jié)點 2的覆蓋地區(qū) )，這是因為節(jié)點 2 廣播所覆蓋的范圍已經(jīng)被其他廣播覆蓋過， 圖中的絕大部分區(qū)域都被重覆蓋過，其中有的區(qū)域被 4 個節(jié)點同時覆蓋，由此產(chǎn)生很大的冗余。這種方法雖然簡單易于實現(xiàn)，但也會造成許多信息重復(fù)的被傳送而產(chǎn)生冗余 (Redundancy)、競爭 (Contention)、以及碰撞 (Collision)，繼而形成廣播 風(fēng)暴 (Broad Cast Storm Problem)。這點對于阻止無止無盡的洪泛是至關(guān)重要的，一種方法是在廣播信息中夾帶一些發(fā)送屬性信息來唯一標(biāo)識一次廣播。但是，對于某些應(yīng)用而言， 100%的傳輸可靠性也是沒有必要的。由于每個移動節(jié)點隨意地加入和離開，所以它們之間的同步非常困難，此外，由于每個節(jié)點是分布式存在的，所以廣播信息是自發(fā)的，并沒有某種調(diào)度機制來分配其發(fā)送時隙。因為無線電波功率的限制、信道的使用以及電池電量等原因，使得節(jié)點無法直接以單一連接方式與其他節(jié)點傳送信息，所以有許多重連 接的情況發(fā)生，在發(fā)送端發(fā)送封包給目的端前，中間必須依賴多個節(jié)點轉(zhuǎn)送封包。在主機高度動態(tài)的情況下，廣播操作會更加頻繁。 總體來說，按需路由協(xié)議是專門針對 Ad hoc 網(wǎng)絡(luò)特點而設(shè)計的路由協(xié)議，因此適用于 Ad hoc 網(wǎng)絡(luò)環(huán)境。同樣， AODV 協(xié)議在大負(fù)載和拓?fù)渥兓?