【文章內(nèi)容簡介】 14]、DSDV[15]、FSR[16]、OLSR[17]協(xié)議等。 WRP[14]路由協(xié)議WRP(Wireless Routing Protocol)協(xié)議即無線路由協(xié)議，是一種基于距離矢量的表驅(qū)動路由協(xié)議。WRP利用bellmanford的基本算法通告距離矢量信息來維護路由表，每個節(jié)點保存在路由表中的信息如下：距離、路由、鏈路開銷和重傳計數(shù)器、每一個節(jié)點正確應答所需的標識和更新消息的更新列表(MRL)等。MRL記錄關于消息序列號、重傳計數(shù)器、每一個鄰節(jié)點正確應答所需的標識和更新消息的列表等信息。這就使得節(jié)點可以決定何時發(fā)送更新消息以及發(fā)送給哪個節(jié)點。更新消息包括目的節(jié)點的地址、到目的節(jié)點的距離和目的節(jié)點的上游節(jié)點，然后鄰節(jié)點就可以修改自己的路由表并試圖建立新的路由。由于無線鏈路的特性或網(wǎng)絡擁塞，更新分組可能丟失或者過期，需要采用重傳機制來保證更新分組的可靠傳輸。節(jié)點正確地收到更新分組之后需要發(fā)送一個ACK進行確認。如果節(jié)點沒有轉(zhuǎn)發(fā)數(shù)據(jù)分組或者更新消息，則要定期發(fā)送HELLO分組，以確保節(jié)點間的連通性。節(jié)點在一段時間內(nèi)沒有收到鄰節(jié)點發(fā)送的任何分組，就認為和該節(jié)點的鏈路失敗。 WRP路由表條目格式Dest idDistancePredecessorSuccessorTagWRP協(xié)議中，節(jié)點為每個目的節(jié)點保存一個路由條目。Dest id：目的節(jié)點j的id。Distance：i到目的節(jié)點j的距離。Predecessor：節(jié)點i到目的節(jié)點j的最短路徑上j的上一跳節(jié)點。Successor：節(jié)點i到目的節(jié)點j的最短路徑上的i的下一跳節(jié)點。Tag：標志位，標志節(jié)點i和j之間的路由無環(huán)路、有環(huán)路和無路由。WRP協(xié)議中，通過路由表中的Successor位可以解決距離矢量算法中的無窮計算問題。同時，為了限制路由信息周期性發(fā)送所帶來的網(wǎng)絡開銷，WRP的拓撲更新采用周期觸發(fā)和事件觸發(fā)相結合的方式。即節(jié)點在發(fā)現(xiàn)鏈路故障后主動發(fā)起拓撲更新消息，而在無故障的情況下以較小的頻度周期發(fā)送拓撲更新消息。 DSDV[15]路由協(xié)議另外一種先應式路由協(xié)議為DSDV(DestinationSequenced DistanceVector Routing)協(xié)議，該協(xié)議是一種基于bellmanford算法的距離矢量協(xié)議。每個節(jié)點都維護一張路由表，表中記錄到其他節(jié)點的路由信息，包括目的節(jié)點的標識以及距離(即跳數(shù)，Number of Hops)，當節(jié)點發(fā)現(xiàn)目的節(jié)點不可達時，將距離設為無窮大。DSDV與有線網(wǎng)絡中的距離矢量協(xié)議大致相同，但是增加了目的節(jié)點序號的記錄、路由增量的更新和延時路由表更新等策略。DSDV中主要是通過在拓撲更新消息中引入序列號的機制來區(qū)分路由的新舊，節(jié)點收到路由更新之后，比較其中的目的節(jié)點序列號和自己保存的同一目的節(jié)點的序列號，如果前者大，就更新自己的路由；如果路由序列號相同，則選擇具有較少跳數(shù)的路由。DSDV協(xié)議中通過延時路由表更新的策略防止路由表的波動。，節(jié)點B有一條路由經(jīng)12跳到達節(jié)點A，節(jié)點C有一條11跳到達節(jié)點A的路由，且節(jié)點D先收到節(jié)點B的路由更新分組，經(jīng)過10s后又收到節(jié)點C的路由更新分組。如果節(jié)點D一收到B的路由更新分組就更新自己的路由表，并廣播路由更新分組，節(jié)點D在短短的10s內(nèi)就更新了兩次路由表，并且還廣播了很多路由更新分組。這就是路由表波動問題。 路由波動問題示例圖在DSDV中采用觸發(fā)更新和穩(wěn)定時間機制來解決此類問題。當節(jié)點收到新的路由信息時，可分為兩種情況：一是鏈路失敗，二是調(diào)整已存在的路由。對于第一種情況需要立即發(fā)送路由更新分組，這就是所謂的觸發(fā)更新；而對于第二種情況則需要等待一段時間再發(fā)送路由更新分組，這就是所謂的穩(wěn)定時間機制。 FSR[16]路由協(xié)議FSR(Fisheye State Routing)協(xié)議是一種先應式鏈路狀態(tài)協(xié)議，但是其綜合采用了距離矢量和鏈路狀態(tài)兩種協(xié)議思想。其來源于基于全局鏈路狀態(tài)的GSR(Global State Routing)協(xié)議，并在拓撲更新和路由維護方面進行了改進。FSR協(xié)議中每個節(jié)點通過幾張表來維護一張網(wǎng)絡拓撲圖，包括鄰居表、拓撲表、下一跳表和距離表，用來計算到目的節(jié)點的最短路徑。FSR協(xié)議中節(jié)點周期性地發(fā)送鏈路狀態(tài)分組來更新路由表，但是不同于一般的鏈路狀態(tài)協(xié)議，F(xiàn)SR協(xié)議的鏈路狀態(tài)分組僅在鄰節(jié)點之間交換，而普通的鏈路狀態(tài)協(xié)議采用全網(wǎng)廣播的方法。為降低鏈路狀態(tài)信息通告開銷，F(xiàn)SR利用距離長度限制路由表項的更新頻度。跳數(shù)較遠的路由表項被包含在拓撲更新消息中的頻度較小，反之較大，這樣就控制了路由信息占用的開銷，節(jié)省了部分網(wǎng)絡資源。，由于其拓撲結構像魚的眼睛，所以稱之為FSR(Fisheye State Routing，魚眼協(xié)議)。 FSR路由協(xié)議“魚眼”圖 OLSR[17]路由協(xié)議OLSR(Optimized Link State Routing)協(xié)議是一種基于鏈路狀態(tài)算法的先應式路由協(xié)議。OLSR協(xié)議的核心是多點中繼(Multipoint Relay)機制。多點中繼的思想是通過減少同一區(qū)域內(nèi)相同控制分組的重復轉(zhuǎn)發(fā)次數(shù)來減少網(wǎng)絡中廣播分組數(shù)量。網(wǎng)絡中的每一個節(jié)點選取其鄰節(jié)點的一個子集用于轉(zhuǎn)發(fā)該節(jié)點的控制分組。這些被選中的節(jié)點就稱為該節(jié)點的MPR，該節(jié)點就稱為這些MPR的多點中繼選擇節(jié)點(MPR Selector)。節(jié)點A的MPR集合是滿足下面條件的節(jié)點集合：(1) MPR 中的每個節(jié)點都是 A 的一跳鄰居節(jié)點；(2) 通過MPR 中的節(jié)點，A 可以將信息傳播到所有兩跳節(jié)點。同時，OLSR協(xié)議規(guī)定，節(jié)點廣播的鏈路狀態(tài)消息僅被其MPR節(jié)點轉(zhuǎn)發(fā)，非MPR集合中的節(jié)點不轉(zhuǎn)發(fā)。：(a)(b) (c) OLSR路由更新過程?？梢钥吹?，僅A、C、E、H轉(zhuǎn)發(fā)了鏈路狀態(tài)更新報文，而其它節(jié)點都沒有轉(zhuǎn)發(fā)。OLSR協(xié)議利用這種MPR機制有效抑制了路由信息的擴散，降低路由開銷。上邊介紹的WRP、DSDV和OLSR都屬于先應式路由協(xié)議，先應式路由協(xié)議由有線網(wǎng)中的路由協(xié)議發(fā)展而來，其優(yōu)勢在于能為上層服務提供較小的時延。下邊將要介紹另一類路由協(xié)議反應式路由協(xié)議，相比于先應式路由協(xié)議，反應式路由協(xié)議有著截然不同的路由方式。 反應式路由協(xié)議除前邊介紹的各種先應式路由協(xié)議外，還存在一類專門針對Ad Hoc網(wǎng)絡的特點而提出的路由協(xié)議反應式路由協(xié)議。反應式路由協(xié)議中節(jié)點并不周期性地維護到目的節(jié)點的路由信息，而是當有上層業(yè)務到達時，再發(fā)起到目的節(jié)點的路由尋找。這種路由協(xié)議的優(yōu)勢在于：路由與業(yè)務緊密相關，網(wǎng)絡沒有業(yè)務請求時，無需路由維護開銷；并且由于反應式路由協(xié)議對路由處理的即時性，協(xié)議中不易引入環(huán)路和過期路由，具有較好的健壯性。所以，越來越多的人把目光投向了反應式路由協(xié)議。目前有代表性的反應式路由協(xié)議有DSR[18]、AODV[19]以及TORA[20]協(xié)議，下面分別對這些路由協(xié)議加以簡要的介紹。 DSR[18]路由協(xié)議DSR(Dynamic Source Routing)協(xié)議是一種反應式源路由協(xié)議。源節(jié)點通過洪泛路由請求消息(RREQ)發(fā)起路由尋找，收到請求的中間節(jié)點將自身地址添加到DSR報頭的源路由選項中并轉(zhuǎn)發(fā)，直到該路由請求消息抵達目的節(jié)點。目的節(jié)點通過RREQ中的節(jié)點列表信息獲取到RREQ源節(jié)點的路由，然后目的節(jié)點向RREQ的源節(jié)點發(fā)送RREP，RREP中包含了從源節(jié)點到目的節(jié)點的路由信息，所以源節(jié)點收到RREP之后形成到達目的節(jié)點的路由。DSR的路由查詢流程如圖5所示。 DSR路由過程，節(jié)點K為目的地址。節(jié)點A發(fā)送RREQ分組發(fā)起路由查找，中間節(jié)點E和H收到之后把自己的地址添加到RREQ的源路由選項并轉(zhuǎn)發(fā)，最終RREQ到達目的節(jié)點K，目的節(jié)點K根據(jù)RREQ中路徑信息的逆序向節(jié)點A發(fā)送RREP，節(jié)點A收到RREP后形成到節(jié)點K的路由。需要注意的是，諸如RREQ報文、RREP報文以及源路由數(shù)據(jù)報文中均攜帶路由信息，所有監(jiān)聽到上述報文的節(jié)點將提取其中的路由信息，更新本地路由表，以節(jié)省路由查詢的時延和開銷。由于DSR路由查詢和應答的多路徑傳輸特性，一次路由申請可能獲取多條源路由，這為流量均衡以及QoS服務等方面提供了較大的便利。在不需要多路徑路由的應用場景下，可以采用一些廣播風暴抑制的策略限制RREQ和RREP消息在全網(wǎng)的擴散。[19]路由協(xié)議另外一種較為有代表性的反應式路由協(xié)議是AODV(Ad Hoc On Demand Distance Vector)協(xié)議，AODV協(xié)議由DSDV算法發(fā)展而來。AODV協(xié)議采用與DSR協(xié)議相似的路由發(fā)現(xiàn)與查找過程。，節(jié)點A廣播RREQ分組發(fā)起到目的節(jié)點K的路由尋找，AODV的RREQ分組中并沒有DSR中RREQ那樣的源路由字段選項，而是只有一個上一跳節(jié)點選項，中間節(jié)點H收到節(jié)點E轉(zhuǎn)發(fā)的RREQ，那么其能夠獲知自己到節(jié)點A的路由下一跳節(jié)點是E，并把此路由信息保存在路由緩存表中。RREQ在網(wǎng)絡中不斷的擴散，每個收到RREQ的節(jié)點都像節(jié)點H一樣根據(jù)上一跳節(jié)點構造一個反向路由并保存。目的節(jié)點K收到RREQ后用構建的反向路由回送RREP，從而使源節(jié)點A獲得到節(jié)點K的路由。AODV協(xié)議中，節(jié)點獲得到目的節(jié)點的路由之后，不再把路由信息放到數(shù)據(jù)分組的首部，而是利用逐跳轉(zhuǎn)發(fā)的方式把數(shù)據(jù)分組路由到目的節(jié)點。由于AODV的數(shù)據(jù)包中不攜帶源路由信息，所以相對DSR具有較好的可擴展性，比較適合節(jié)點容量大的網(wǎng)絡。但是同時，去除源路由信息也導致了節(jié)點監(jiān)聽信息量的減少，無法應用監(jiān)聽的信息獲取多跳以外的路由。[20]路由協(xié)議反應式路由家族中的另外一個協(xié)議為TORA(Temporally Ordered Routing Algorithm)協(xié)議，該協(xié)議借鑒圖論中的有向圖概念，利用傳播、維護和修改節(jié)點在鏈路中的相對高度值構建從源到目的節(jié)點的多徑路由。TORA采用鏈路翻轉(zhuǎn)的分布式算法，該協(xié)議為每個節(jié)點分配一個相對目的節(jié)點的高度值，作為路由度量值。相鄰兩個路由節(jié)點之間直接通信時，具有較大高度值的節(jié)點被規(guī)定為上游節(jié)點，TORA規(guī)定被路由的分組只能從上游節(jié)點流向下游節(jié)點。當發(fā)生鏈路斷裂時，協(xié)議賦給斷裂處節(jié)點一個比其鄰節(jié)點都高的高度值，這樣分組就在此處返回，這一過程稱之為反轉(zhuǎn)，并在斷裂處附近查找可用路由，協(xié)議的控制報文只在最靠近拓撲變化的地方產(chǎn)生。此種算法中路由不一定是最優(yōu)的，其常常使用次優(yōu)路由以減少路由發(fā)現(xiàn)過程帶來的開銷。但是當拓撲較為復雜并且移動性較強時，其收斂較慢，開銷較大；并且TORA協(xié)議是基于同步時鐘的，所以時鐘的時間不同步可能導致路由協(xié)議故障。綜上所述，反應式路由依靠應用層數(shù)據(jù)驅(qū)動協(xié)議的運行，因此一般認為反應式路由協(xié)議比先應式更適合Ad Hoc網(wǎng)絡。但是根據(jù)具體應用場合和應用需求不同，兩類協(xié)議各有所長，也都有自己的局限。先應式路由協(xié)議需要不斷的交互路由信息來維護路由表，所以協(xié)議開銷較大 (尤其在拓撲變化較頻繁、劇烈時)，但是尋路時延較小且受上層業(yè)務流量的影響較??；反應式路由協(xié)議僅在需要時才搜索路由，開銷相對較小，但是尋路時延較大，并且受數(shù)據(jù)突發(fā)影響較嚴重，即如果相鄰節(jié)點幾乎同時發(fā)起路由查找請求，往往尋路失敗的概率較大。為了彌補雙方的不足，出現(xiàn)了先應式和反應式路由協(xié)議的結合體混合式路由協(xié)議?；旌鲜铰酚蓞f(xié)議的基本思想是結合先應式和反應式路由的尋路方式，在部分區(qū)域內(nèi)采用先應式路由，而在另一部分區(qū)域內(nèi)則采用反應式，從而獲得高效與低開銷的統(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)跳以內(nèi)的路由，而當需要尋址到d跳以外時，再利用反應式路由算法尋找路由，其反應式路由機制類似DSR。先應式半徑區(qū)域內(nèi)的路由稱為Intrazone路由，而先應式半徑區(qū)域外的路由稱為Interzone路由。，節(jié)點S 的一個半徑為2的路由區(qū)域。與節(jié)點的距離等于區(qū)域半徑的點稱為邊界點，如節(jié)點K即為S的邊界點。S維護在虛線以內(nèi)(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)調(diào)整先應式區(qū)域半徑大小的路由協(xié)議，其特點體現(xiàn)在如下幾個方面：協(xié)議可以根據(jù)網(wǎng)絡流量特性來動態(tài)調(diào)整先應式半徑的大小。SHARP協(xié)議中考察節(jié)點作為目的節(jié)點的屬性，對于繁忙的目的地節(jié)點(即有多個源發(fā)送數(shù)據(jù)給它)，其設置先應式的半徑較大，而對于不繁忙的目的節(jié)點，其設置先應式半徑較小。這樣在網(wǎng)絡流量較小的時候，全網(wǎng)退化成反應式的尋路，而當全網(wǎng)流量較大且分布均勻時，則全網(wǎng)退化成先應式路由。SHARP的區(qū)域內(nèi)先應式協(xié)議借鑒了DSDV（序號機制）、TORA的有向圖機制、以及piggyback技術，其反應式的路由基于AODV協(xié)議；SHARP的先應式路由維護、半徑調(diào)整以及維護都是通過鄰近節(jié)點之間交互信息實現(xiàn)的，交互的信息包括先應式半徑、丟包率等信息。 SHARP的區(qū)域調(diào)整示意圖如圖7所示，S為源節(jié)點，D為目的節(jié)點，r先應式半徑。目的節(jié)點D根據(jù)自己統(tǒng)計的信息計算出最佳先應式半徑為r。源節(jié)點采用AODV的方式發(fā)起到目的節(jié)點D的路由查找，到達hr跳之后路由查找結束，路由變?yōu)橄葢健HARP基于先應式引入開銷而反應式引入時延的假設，通過動態(tài)調(diào)整節(jié)點的先應式區(qū)域半徑，達到降低開銷和控制時延以及限制丟包率的目的(開銷、時延以及丟包率均是先應式區(qū)域半徑R的函數(shù))。上邊介紹了先應式、反應式以及混合式路由協(xié)議和各類中比較典型的路由協(xié)議?？傮w看來，幾類協(xié)議在尋路方式上風格迥異，各有特點。一般我們習慣