《高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)》課程報(bào)告研究生楊光雨adhoc路由協(xié)議簡(jiǎn)介

Adhoc路由協(xié)議簡(jiǎn)介楊光雨2014-12-22現(xiàn)有Adhoc路由協(xié)議分類(lèi)平面路由無(wú)需建立具有特殊cluster頭功能節(jié)點(diǎn)的層次結(jié)構(gòu)所有節(jié)點(diǎn)在路由機(jī)制中地位平等尋址方式是平面的層次路由節(jié)點(diǎn)功能不同尋址方式是分層進(jìn)行的地理信息輔助路由利用地理信息進(jìn)行路由選擇表驅(qū)動(dòng)路由先驗(yàn)式(proactive)路由傳統(tǒng)的分布式最短路徑路由協(xié)議鏈路狀態(tài)或者距離向量所有節(jié)點(diǎn)連續(xù)更新“可達(dá)”信息每個(gè)節(jié)點(diǎn)維護(hù)到網(wǎng)絡(luò)中所有節(jié)點(diǎn)的路由所有路由都已經(jīng)存在并且隨時(shí)可用路由請(qǐng)求延時(shí)低路由開(kāi)銷(xiāo)高

表驅(qū)動(dòng)路由協(xié)議特點(diǎn)初期，主要是修改有線網(wǎng)絡(luò)路由協(xié)議以適應(yīng)Adhoc網(wǎng)絡(luò)環(huán)境，大多屬于表驅(qū)動(dòng)路由協(xié)議。表驅(qū)動(dòng)路由協(xié)議的路由查找策略與傳統(tǒng)路由協(xié)議類(lèi)似，節(jié)點(diǎn)通過(guò)周期性廣播路由信息報(bào)文，交換路由信息，主動(dòng)發(fā)現(xiàn)路由；同時(shí)，節(jié)點(diǎn)須維護(hù)去往網(wǎng)絡(luò)中所有節(jié)點(diǎn)路由。優(yōu)點(diǎn)：當(dāng)節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)報(bào)文時(shí)，只要去往目標(biāo)節(jié)點(diǎn)的路由存在，所需的延時(shí)很小；缺點(diǎn)：需要花費(fèi)較大開(kāi)銷(xiāo)，盡可能使得路由更新能夠緊隨當(dāng)前拓?fù)浣Y(jié)構(gòu)的變化。然而，動(dòng)態(tài)變化拓?fù)浣Y(jié)構(gòu)可能使得路由更新變成過(guò)時(shí)信息，路由協(xié)議始終處于不收斂狀態(tài)。主要的表驅(qū)動(dòng)路由協(xié)議：DBF(DistributedBellman-Ford)、DSDV(Destination-SequencedDistance-VectorRouting)、WRP(WirelessRoutingProtocol)。

主要的表驅(qū)動(dòng)路由協(xié)議DSDV(Destination-SequencedDistance-VectorRouting)

目標(biāo)序列距離向量路由

表驅(qū)動(dòng)路由協(xié)議--DSDV每個(gè)終端維護(hù)一張到網(wǎng)中每一個(gè)目標(biāo)終端的路由信息：

–下一跳終端,到目標(biāo)終端的跳數(shù)；

–目標(biāo)終端指定（生成）的序列號(hào)；每個(gè)終端周期性的向相鄰節(jié)點(diǎn)發(fā)送路由表；

—每個(gè)終端所能到達(dá)的目標(biāo)終端、到目標(biāo)終端的跳數(shù)、序列號(hào)（保持最大的，即最新的）；

—每個(gè)終端廣播時(shí)單調(diào)遞增序列號(hào)接收路由更新包時(shí)，終端將該包報(bào)文與當(dāng)前路由表比較，舊的（較小的）序列號(hào)路徑將被刪除。Destinationadvertisesnewsequencenumber

表驅(qū)動(dòng)路由協(xié)議--DSDVDSDV協(xié)議特點(diǎn)1、DSDV路由協(xié)議需要每個(gè)節(jié)點(diǎn)向其鄰居公告路由表，隨著時(shí)間的流逝，路由記錄常常會(huì)發(fā)生改變，因此這種對(duì)路由表的公告必須可靠地反映移動(dòng)節(jié)點(diǎn)的位置。2、每個(gè)節(jié)點(diǎn)必須根據(jù)需要同意向其它節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)報(bào)文。3、任意時(shí)刻不會(huì)產(chǎn)生環(huán)路。4、周期性或觸發(fā)式更新路由信息可能引起過(guò)大的通信負(fù)載。5、不支持多路徑的路由。DSDV協(xié)議路由表記錄結(jié)構(gòu)每個(gè)移動(dòng)節(jié)點(diǎn)廣播數(shù)據(jù)包含其新的序列號(hào)以及下列新的路由信息：

1.目標(biāo)節(jié)點(diǎn)地址

2.到達(dá)目標(biāo)節(jié)點(diǎn)的跳數(shù)

3.收到的有關(guān)目標(biāo)節(jié)點(diǎn)的信息序列號(hào)—該序列號(hào)原先被目標(biāo)節(jié)點(diǎn)做了標(biāo)記。在報(bào)文頭中傳送的路由表中包含硬件地址和網(wǎng)絡(luò)地址。路由表同樣包含由發(fā)送者產(chǎn)生的序列號(hào)，更新的序列號(hào)的路由是作為報(bào)文轉(zhuǎn)發(fā)的基礎(chǔ)，但不必公布。對(duì)于序列號(hào)相同的路徑，選距離最小者。

表驅(qū)動(dòng)路由協(xié)議--DSDV當(dāng)接收器隨后公布路由信息時(shí)，將它在廣播報(bào)文中收到的路由信息一起公布。公布之前，接收器給距離增加一個(gè)增量，其原因是收到的報(bào)文需經(jīng)過(guò)多跳才能到達(dá)目的節(jié)點(diǎn)（即從轉(zhuǎn)發(fā)器到接收器）。無(wú)線網(wǎng)絡(luò)由于單向鏈路的普遍存在而產(chǎn)生不對(duì)稱性，從其鄰居節(jié)點(diǎn)接收到一個(gè)報(bào)文時(shí)，不能說(shuō)明它們之間一定存在一條單跳數(shù)據(jù)鏈路。為了避免單向鏈路引起的問(wèn)題，每個(gè)移動(dòng)節(jié)點(diǎn)不能插入從其鄰居節(jié)點(diǎn)接收的路由信息，除非鄰居節(jié)點(diǎn)顯示也能接收該結(jié)點(diǎn)報(bào)文。在本算法中，只考慮雙向鏈的情況。要選擇的最重要的一個(gè)參數(shù)是廣播路由信息報(bào)文間的時(shí)間；當(dāng)移動(dòng)節(jié)點(diǎn)收到實(shí)際已修改過(guò)或新的路由信息時(shí)，立即將其轉(zhuǎn)發(fā)出去。這要求本算法能盡可能快地收斂。

對(duì)拓?fù)渥兓捻憫?yīng)節(jié)點(diǎn)移動(dòng)時(shí)可能引起鏈路中斷，這種情況可能由第二層協(xié)議檢測(cè)到，也可能由于暫時(shí)沒(méi)有從以前的鄰居節(jié)點(diǎn)接收到廣播的報(bào)文而推斷出來(lái)。我們稱中斷。鏈路的距離為∞，當(dāng)?shù)较乱惶鴦?dòng)鏈路中斷時(shí)，經(jīng)過(guò)下一跳的任何路由的距離都被設(shè)置為∞并且被重新分配一個(gè)序列號(hào)（這種修改立即反映在廣播路由信息的報(bào)文中）。任何移動(dòng)節(jié)點(diǎn)（不包括目的節(jié)點(diǎn)）產(chǎn)生序列號(hào)，說(shuō)明必須建立信息來(lái)描述中斷鏈路的產(chǎn)生。為了減少傳輸路由報(bào)文的信息量，定義下列兩個(gè)概念：

1、完全轉(zhuǎn)貯報(bào)文：包含全部有效路由信息的報(bào)文。

2、增量報(bào)文：只包含與上次路由相比改變部分的報(bào)文。

路由選擇標(biāo)準(zhǔn)當(dāng)移動(dòng)節(jié)點(diǎn)收到新（與上次收到的路由信息相比）的路由信息（通常是增量報(bào)文）時(shí)，選擇的標(biāo)準(zhǔn)是：選擇帶有最新序列號(hào)的路由，去掉帶舊序列號(hào)的路由。帶有序列號(hào)的路由意味選擇了一條距離更短的路由。選擇不同節(jié)點(diǎn)間的時(shí)間偏差也是路由選擇的一個(gè)標(biāo)準(zhǔn)。移動(dòng)節(jié)點(diǎn)的路由信息廣播是異步的。采用上述路由選擇的標(biāo)準(zhǔn)可能引起波動(dòng)，可能導(dǎo)致移動(dòng)節(jié)點(diǎn)收到某種形式的新路由信息時(shí)，老是改變下一跳到另一跳的路由，甚至當(dāng)目的節(jié)點(diǎn)沒(méi)有移動(dòng)時(shí)也如此。選擇新的路由有兩種方式：1、更新的序列號(hào)。2、更短的距離。DSDV操作的例子

考慮下圖中的MH4，下頁(yè)表為MH4所保存的轉(zhuǎn)發(fā)表可能結(jié)構(gòu)。MH3MH2MH1MH4MH6MH5MH8MH7MH1MHi：節(jié)點(diǎn)i

的地址SNNN_MHi：第i個(gè)計(jì)算機(jī)產(chǎn)生的序列號(hào)SNNN.Ptr1_MHi是指針，在本圖中，由于沒(méi)有任何路由存在，因而，該指針指向空結(jié)構(gòu)。DestinationNextHopMetricSequenceNumberInstallStable_dataMH1MH22S406_MH1T001_MH4Ptr1_MH1MH2MH21S128_MH2T001_MH4Ptr1_MH2MH3MH22S546_MH3T001_MH4Ptr1_MH3MH4MH40S710_MH4T001_MH4Ptr1_MH4MH5MH62S392_MH5T002_MH4Ptr1_MH5MH6MH61S076_MH6T001_MH4Ptr1_MH6MH7MH62S128_MH7T001_MH4Ptr1_MH7MH8MH63S050_MH8T001_MH4Ptr1_MH8MH4轉(zhuǎn)發(fā)表結(jié)構(gòu)字段Install決定何時(shí)刪除舊路由DestinationMetricSequenceNumberMH12S406_MH1MH21S128_MH2MH32S546_MH3MH40S710_MH4MH52S392_MH5MH61S076_MH6MH72S128_MH7MH83S050_MH8MH4公布的路由表DestinationNextHopMetricSequenceNumberInstallStable_dataMH1MH63S516_MH1T810_MH4Ptr1_MH1MH2MH21S238_MH2T001_MH4Ptr1_MH2MH3MH22S674_MH3T001_MH4Ptr1_MH3MH4MH40S820_MH4T001_MH4Ptr1_MH4MH5MH62S502_MH5T002_MH4Ptr1_MH5MH6MH61S186_MH6T001_MH4Ptr1_MH6MH7MH62S238_MH7T002_MH4Ptr1_MH7MH8MH63S160_MH8T002_MH4Ptr1_MH8下表是假設(shè)MH1移到MH8和MH7的附近后的路由轉(zhuǎn)發(fā)表DestinationMetricSequenceNumberMH13S516_MH1MH21S238_MH2MH32S674_MH3MH40S820_MH4MH52S502_MH5MH61S186_MH6MH72S238_MH7MH83S160_MH8MH4公布的路由表（新）

該例說(shuō)明，只要一個(gè)節(jié)點(diǎn)的位置變化，其路由信息就會(huì)發(fā)生改變。所有的節(jié)點(diǎn)都傳送新的序列號(hào)。各節(jié)點(diǎn)周期性的向鄰居節(jié)點(diǎn)通告其當(dāng)前的路由表，而不是采用洪泛法。這相當(dāng)于各節(jié)點(diǎn)對(duì)收到的其他節(jié)點(diǎn)的信息進(jìn)行處理以后再進(jìn)行廣播通告，從而大大減少通告的信息量。每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)路由表，每個(gè)路由表項(xiàng)包括：目的地址、到達(dá)目的節(jié)點(diǎn)的度量值（如最小跳數(shù)）、目的節(jié)點(diǎn)相關(guān)的序列號(hào)（由目的節(jié)點(diǎn)發(fā)出）等，該序列號(hào)用以識(shí)別路由的新舊，作為路由更新和分組轉(zhuǎn)發(fā)的依據(jù)。DSDV信息通告舉例DSDV信息通告舉例-有新的節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)鏈路斷如果在相當(dāng)長(zhǎng)的一段時(shí)間內(nèi)不能收到相鄰節(jié)點(diǎn)的廣播消息，可推斷出鏈路斷。（1）在DSDV中，斷的鏈路度量值等于∞;（2）節(jié)點(diǎn)檢測(cè)路由表，下一跳經(jīng)過(guò)該鏈路的路由表項(xiàng)的度量值標(biāo)記為∞，并分配一個(gè)新的序列號(hào)。這種情況下的序列號(hào)為奇數(shù)，以區(qū)別目的節(jié)點(diǎn)為更新報(bào)文分配的序列號(hào)（3）度量值為∞的表項(xiàng)的變化程度足以觸發(fā)“遞增更新”報(bào)文的立即發(fā)送經(jīng)過(guò)上述過(guò)程，在較短的時(shí)間內(nèi)，該鏈路的變化將通告到網(wǎng)絡(luò)的各個(gè)節(jié)點(diǎn).鏈路斷開(kāi)波動(dòng)抑制在一個(gè)單獨(dú)的表（廣播表）中記錄每條路由的最近的和平均的SettlingTimeSettlingTime：第一條路由和最佳路由之間的時(shí)間間隔路由表中的stabledata指向該表A在包含新序列號(hào)的第一條路由到達(dá)時(shí)更新路由表，但是等待一段時(shí)間再?gòu)V播該條路由等待時(shí)間=2*(avg.SettlingTime)可緩解大型網(wǎng)絡(luò)的路由波動(dòng)問(wèn)題，從而避免不必要的公告，節(jié)約了帶寬按需(on-demand)路由協(xié)議反應(yīng)式(reactive)路由在源端需要時(shí)通過(guò)路由發(fā)現(xiàn)過(guò)程來(lái)確定路由控制信息采用泛洪方式路由請(qǐng)求延時(shí)高路由開(kāi)銷(xiāo)低兩種實(shí)現(xiàn)技術(shù)源路由（報(bào)文頭攜帶完整的路由信息）逐跳路由（類(lèi)似于現(xiàn)有的Internet路由）按需路由協(xié)議的特點(diǎn)根據(jù)發(fā)送節(jié)點(diǎn)的需求進(jìn)行路由發(fā)現(xiàn)過(guò)程，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和路由表內(nèi)容也按需建立（只是整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的一部分）。優(yōu)點(diǎn)：不需周期性廣播路由信息，節(jié)省網(wǎng)絡(luò)資源。缺點(diǎn)：發(fā)送分組時(shí)，必須臨時(shí)啟動(dòng)路由發(fā)現(xiàn)過(guò)程來(lái)尋找路由，因而延遲大主要路由協(xié)議：

DSR(DynamicSourceRouting)AODV(AdHoconDemandDistanceVectorRouting)TORA(TemporallyOrderedRoutingAlgorithm)

按需路由協(xié)議表驅(qū)動(dòng)路由協(xié)議的路由查找策略與傳統(tǒng)路由協(xié)議類(lèi)似，節(jié)點(diǎn)通過(guò)周期性廣播路由信息報(bào)文，交換路由信息，主動(dòng)發(fā)現(xiàn)路由；同時(shí)，節(jié)點(diǎn)須維護(hù)去往網(wǎng)絡(luò)中所有節(jié)點(diǎn)路由。當(dāng)節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)報(bào)文時(shí)，只要去往目標(biāo)節(jié)點(diǎn)的路由存在，所需的延時(shí)很小；但需要花費(fèi)較大開(kāi)銷(xiāo)，盡可能使得路由更新能夠緊隨當(dāng)前拓?fù)浣Y(jié)構(gòu)的變化。按需路由協(xié)議根據(jù)發(fā)送節(jié)點(diǎn)的需求進(jìn)行路由發(fā)現(xiàn)過(guò)程，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和路由表內(nèi)容也按需建立。不需周期性廣播路由信息，節(jié)省網(wǎng)絡(luò)資源。但發(fā)送分組時(shí)，必須臨時(shí)啟動(dòng)路由發(fā)現(xiàn)過(guò)程來(lái)尋找路由，因而延遲大。DSR(DynamicSourceRouting)動(dòng)態(tài)源路由

按需路由協(xié)議

由路由查找和路由維護(hù)兩個(gè)過(guò)程組成：當(dāng)源終端發(fā)現(xiàn)沒(méi)有去往目標(biāo)終端的路由時(shí)，觸發(fā)路由查找過(guò)程。源終端A在網(wǎng)絡(luò)中廣播路由請(qǐng)求報(bào)文(RREQ)，相鄰終端B和C收到路由請(qǐng)求報(bào)文后，記錄報(bào)文經(jīng)過(guò)了該終端，然后繼續(xù)轉(zhuǎn)發(fā)，直到到達(dá)了目標(biāo)終端D。終端D將會(huì)收到來(lái)自多條不同路徑的路由請(qǐng)求報(bào)文，每個(gè)路由請(qǐng)求報(bào)文中包含有相應(yīng)的路徑信息。節(jié)點(diǎn)D根據(jù)一定的選擇原則選取一條從源終端到目標(biāo)終端的最優(yōu)路徑，并將該信息附在向源終端A發(fā)送的路由響應(yīng)報(bào)文中，作為對(duì)路由請(qǐng)求的響應(yīng)。源終端A根據(jù)收到的路由響應(yīng)報(bào)文更新路由信息，從而獲得去往目標(biāo)終端D的路由。

按需路由協(xié)議當(dāng)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，通過(guò)路由維護(hù)過(guò)程刪除失效路由，重新發(fā)起路由請(qǐng)求過(guò)程。路由維護(hù)通常依靠底層提供的鏈路失效檢測(cè)機(jī)制進(jìn)行觸發(fā)。如果某個(gè)終端不能到達(dá)下一跳終端，如圖中終端B在它的通信范圍內(nèi)不能到達(dá)終端C，那么在路由查找過(guò)程后建立的路由信息就需要更新。一般地，鏈路斷開(kāi)的上行終端會(huì)發(fā)起一個(gè)路由錯(cuò)誤報(bào)文，將鏈路失效信息發(fā)送到源終端，源終端再對(duì)目標(biāo)終端的路由進(jìn)行重新查找。

按需路由協(xié)議DynamicSourceRouting(DSR)在進(jìn)行路由查找的過(guò)程中，源終端將一個(gè)RREQ（路由請(qǐng)求）報(bào)文泛洪整個(gè)Adhoc網(wǎng)絡(luò)；每個(gè)RREQ報(bào)文擁有唯一的ID號(hào)和一個(gè)初始值為空的列表，當(dāng)終端接收到RREQ報(bào)文的時(shí)候，如果該終端已經(jīng)見(jiàn)到過(guò)這個(gè)報(bào)文的ID，或者列表中包含該終端，那么終端丟棄該報(bào)文并停止泛洪；否則，終端將自身添加到列表的末端，并且將RREQ報(bào)文繼續(xù)廣播給相鄰終端。目標(biāo)終端需要進(jìn)行選擇。根據(jù)最短路徑原則，當(dāng)路由回復(fù)報(bào)文（RREP）到達(dá)源終端N1后，路由查找過(guò)程結(jié)束。RouteDiscoveryinDSRBASEFHJDCGIKZYRepresentsanodethathasreceivedRREQforDfromSMNLRouteDiscoveryinDSRBASEFHJDCGIKRepresentstransmissionofRREQZYBroadcasttransmissionMNL[S][X,Y]RepresentslistofidentifiersappendedtoRREQRouteDiscoveryinDSRBASEFHJDCGIK

NodeHreceivespacketRREQfromtwoneighbors:potentialforcollisionZYMNL[S,E][S,C]RouteDiscoveryinDSRBASEFHJDCGIK

NodeCreceivesRREQfromGandH,butdoesnotforwarditagain,becausenodeChasalreadyforwardedRREQonceZYMNL[S,C,G][S,E,F]RouteDiscoveryinDSRBASEFHJDCGIKZYM

NodesJandKbothbroadcastRREQtonodeDSincenodesJandKarehiddenfromeachother,theirtransmissionsmaycollideNL[S,C,G,K][S,E,F,J]RouteDiscoveryinDSRBASEFHJDCGIKZY

NodeDdoesnotforwardRREQ,becausenodeDistheintendedtargetoftheroutediscoveryMNL[S,E,F,J,M]RouteReplyinDSRBASEFHJDCGIKZYMNLRREP[S,E,F,J,D]RepresentsRREPcontrolmessageDataDeliveryinDSRBASEFHJDCGIKZYMNLDATA[S,E,F,J,D]PacketheadersizegrowswithroutelengthUseofRouteCachingBASEFHJDCGIK[P,Q,R]Representscachedrouteatanode(DSRmaintainsthecachedroutesinatreeformat)MNL[S,E,F,J,D][E,F,J,D][C,S][G,C,S][F,J,D],[F,E,S][J,F,E,S]ZRouteError(RERR)BASEFHJDCGIKZYMNLRERR[J-D]JsendsarouteerrortoS