自組織網中的路由選擇

2019-11-05 00:39:51

字體：大中小

來源：轉載

供稿：網友

　　1.引言
　　自從無線網絡在70年代產生后,它在計算機領域里日趨流行，尤其是最近十年無線移動通信網絡的發展更是一日千里。目前存在的無線移動網絡有兩種：第一種是基于網絡基礎設施的網絡，這種網絡的典型應用為無線局域網（WLAN）。第二種為無網絡基礎設施的網絡，一般稱之為自組織網（AD HOC）。這種網絡沒有固定的路由器，網絡中的節點可隨意移動并能以任意方式相互通信。每一個節點都能實現路由器的功能而在網絡中搜尋、維護到另一節點的路由。自組織網可用在事故的突發現場以及人們希望能迅速共享信息的會議、辦公室等場所。
　　2.現有的路由協議
　　路由選擇在自組織網中非常重要，它既是信息的傳輸策略問題，也涉及到網絡的治理問題。目前自組織網的路由協議一般分為兩種：路由表協議（table driven）和源始發的按需路由協議（source-initiated on-demand driven）。路由表協議包括有：DSDV、CGSR、WRP等，源始發的按需路由協議有：DSR、AODV、LMR、TORA、ABR、SSR等。
　　2.1路由表協議
　　路由表協議需網絡中的每一個節點都要周期性的向其它節點發
　　送最新的路由信息，并且每一個節點都要保存一個或更多的路由表來存儲路由信息。當網絡拓撲結構發生改變時，節點就在全網內廣播路由更新信息，這樣每一個節點就能連續不斷地獲得網絡信息。
　　2.1.1序列目的節點距離矢量路由協議(Destination-Sequenced
　　Distance-Vector Routing)
　　DSDV是基于經典Bellman-Ford路由選擇過程的改進型路由表
　　算法。DSDV以路由信息協議為基礎。它僅適用于雙向鏈路，是AD HOC 路由協議發展較早的一種。
　　依據DSDV，網絡中的每一個節點都保存有一個記錄所有目的節點和到目的節點跳數的路由表(routing table)。表中的每一個條目都有一個由目的節點注明的序列號（sequence number），序列號能幫助節點區分有效和過期的路由信息。標有更大序列號的路由信息總是被接收。假如兩個更新分組有相同的序列號，則選擇跳數（metric）最小的，而使路由最優（最短）。路由表更新分組在全網內周期性的廣播而使路由表保持連貫性。
　　2.1.2群首信關切換路由協議（Clusterhead Gateway Switch
　　Routing）
　　CGSR和DSDV的不同之處在于尋址方式和網絡組織過程。CSGR是有幾種路由選擇方式的分群的多跳移動無線網絡。通過群首控制網絡節點，信關隔離群，信道接入可以分配路由和帶寬。群首選擇算法用來選擇一個節點作為群首并在群內應用分布式算法。信關為那些在兩個或多個群首的通信半徑之內的節點。節點發送數據包首先把它傳送到群首，通過信關到另一個群首，一直重復此過程直到目的節點所在群的群首收到此數據包。然后，數據被傳送到目的節點。用此方式，每個節點必須保存一個群成員表（cluster member table）和路由選擇表（routing table）。群首方式的缺陷在于當群首頻繁的變換時，節點忙于選擇群首而不是數據轉發，這樣反而會影響路由協議的實行。因此，當群內成員發生變化時，產生了最小群變化協議（Least Cluster Change）。利用LCC，只有當一個群內有兩個群首或一個節點在所有的群首通信范圍之外時，群首才發生變換。
　　2.1.3無線路由協議（The Wireless Routing PRotocol）
　　WRP是以維護網絡中所有節點間的路由信息為目的的基于表的協議。依據WRP，每一個節點都需保存距離表、路由表、鏈路開銷表以及信息轉發表（Message Retransmission List）。
　　節點通過更新分組告知其它節點鏈路的變化狀況，通過接收相鄰節點的確認分組以及其它信息來獲知其它節點的情況。在WRP中，節點為網絡中的每一個目的節點交流距離和下一跳到最后一跳的路由信息。WRP屬于有非凡例外的路徑搜尋算法。它通過強迫每一節點檢查所有相鄰節點發送的信息記錄來避免無窮計（count-to-infinity）問題。這最終會消除環路現象和當鏈路斷開時提供更快的路由收斂。
　　2.2源始發按需路由選擇（Source-Initiated On Demand Routing）
　　這種路由選擇方式只有當源節點需要時才建立路由。當一個節點需要到目的節點的路由時，它會在全網內開始路由發現過程。一旦檢驗完所有可能的路由排列方式或找到新的路由后就結束路由發現過程。路由建立后，由路由維護程序來維護這條路由直到它不再被需要或發生鏈路斷開現象。
　　2.2.1自適應源路由協議（Dynamic Source Routing）
　　DSR是基于源路由概念的按需自適應路由協議。移動節點需保留存儲節點所知的源路由的路由緩沖器。當新的路由被發現時，緩沖器內的條目隨之更新。
　　DSR主要由兩部分組成：路由發現和路由維護。當一個節點欲發送數據到目的節點，它首先查詢路由緩沖器看是否有到目的節點的路由。假如有，則采用此路由發送數據。另一方面，假如沒有，源節點就開始路由發現程序。
　　路由維護通過路由錯誤分組（route error）和確認分組來實現。當鏈路層碰到傳輸問題時，錯誤分組開始傳送。一旦收到錯誤分組，節點就會把發生錯誤的那一跳從路由存儲緩沖器移走，并會在所有包含那一條的路由里刪掉那一跳。除路由錯誤分組外，確認分組用來驗證路由連接的正確運行。
　　2.2.2自組織網按需距離矢量路由協議（Ad Hoc On-Demand Distance Vector Routing）
　　AODV實質上就是DSR和DSDV的綜合，它借用了DSR中路由發現和路由維護的基礎程序以及DSDV中跳到跳的路由選擇、序列號碼及周期性的更新信息的用法。
　　和DSDV保存完整的路由表不同的是，AODV通過建立基于按需的路由來減少路由廣播的次數，這是AODV對DSDV的重要改進。和DSR相比，AODV的好處在于源路由并不需包括在每一個數據包中，這樣會使路由協議的開銷有所降低。AODV是一個純粹的按需路由系統，那些不在路徑內的節點不保存路由信息也不參與路由表的交換。
　　2.2.3臨時排序路由算法（Temporally-Ordered Routing Algorithm）
　　TORA是基于‘逆向連接’概念的高度自適應、環路開放、分布式路由算法。TORA主要應用在動態移動網絡環境內。它是源始發的路由協議，能向每一對源-目的節點提供多徑路由。TORA的要害思想是把路由信息的傳送限制在網絡拓撲結構變化處四周較小的范圍內。為了實現這一點，節點必需保留一跳之遠的節點的路由信息。TORA主要實現三個基本功能：路由建立、路由維護、路由刪除。
　　在路由建立和路由維護的過程中，節點應用‘高度（height）’ metric來建立一個以目的節點為根部的指導性的非循環的圖表（Directed Acyclic Graph）。這樣鏈路根據相鄰兩個節點的高度值來確定向上或向下的方向。
　　2.2.4基于聯合的路由協議（Associativity-Based Routing）
　　ABR協議是環路開放的、分組復用的，它為自組織網定義一個新的度量（metric）。這個metric就是聯合穩定性程度（dgree of associativity stability）。在ABR，路由的選擇基于節點的聯合穩定性程度。節點周期性地發送信標來表明自身的情況。一旦相鄰節點收到信標，它們的聯合路由表就會被更新。每接收一個信標，節點就增加一個關于發送信標的節點的聯合條目。聯合穩定性通過節點和其它節點在時間和空間的連接穩定性來定義。高聯合穩定性也許意味著節點的低移動率，而低穩定性意味著高移動率。當節點的相鄰節點或節點本身移動出相鄰的范圍時，聯合條目會被刷新。ABR的基本目標是為自組織網找出生命時間更長的路由。
　　2.2.5信號穩定性路由協議（Signal Stability Routing）
　　SSR是基于自適應路由協議的按需路由協議。SSR選擇路由是基于節點間信號的強度以及節點位置的穩定性。這種路由選擇標準有選擇強連接性路由的作用。SSR可分成兩部分:DRP(Dynamic Routing Protcol)動態路由協議和SRP靜態路由協議(Static Routing Protcol)。
　　DRP主要負責路由表(Routing Table)和信號穩定程度表(Signal Stability Table)的維護。所有的傳送過程及接收都在DRP進行。SRP則負責處理節點接收的數據。
　　3.結論
　　目前，國內外對自組織網的研究還很不成熟，仍處于理論探索和各種網絡協議的實驗模擬、分析修改階段，尚未形成相應的標準。但AD HOC技術的應用和市場前景都不可估量，它在無線通信的家庭產品（HomeRF）及軍事通信等領域中已經得到了廣泛的應用和發展，為各大通信廠商創造了巨大的利潤。

上一篇：尋找智能路由

下一篇：藍牙路由機制