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