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