移動互聯(lián)網(wǎng)：原理、技術(shù)與應(yīng)用 第3版 課件 CH3 移動自組織網(wǎng)絡(luò)-2

CS80240333CUIYong1移動自組織網(wǎng)絡(luò):MANETCS80240333CUIYong2課程大綱

MANET中的路由MANET路由協(xié)議設(shè)計先應(yīng)式協(xié)議DSR和優(yōu)化AODV反應(yīng)式協(xié)議OLSRDSDV混合協(xié)議ZRP,LANMAR總結(jié)CS80240333CUIYong3MANET單播路由主機(jī)的移動性因移動而導(dǎo)致的鏈路失效/恢復(fù)可能與其他原因?qū)е碌耐悊栴}具有不同的特性不穩(wěn)定性

當(dāng)節(jié)點快速移動時鏈路失效/恢復(fù)的概率可能會更高需要新的性能標(biāo)準(zhǔn)

不管如何移動路由都要保持穩(wěn)定能量消耗提出的方法有些專門適用MANET的方法其他的是對舊協(xié)議進(jìn)行修改，并應(yīng)用于有線網(wǎng)絡(luò)的沒有一個協(xié)議是運(yùn)行良好的一些研究者嘗試開發(fā)自適應(yīng)協(xié)議CS80240333CUIYong4典型的協(xié)議按需/反應(yīng)式

當(dāng)需要傳輸數(shù)據(jù)時，源節(jié)點通過一種路由發(fā)現(xiàn)過程來計算路由;全局/預(yù)計算

從一開始就計算出到所有目的節(jié)點的路由

通過周期性的路由更新來維護(hù)路由表混合式

結(jié)合上述兩種技術(shù)來實現(xiàn)網(wǎng)絡(luò)的路由.優(yōu)勢&不足?互聯(lián)網(wǎng)路由器?BGP/OSPF/ISIS/RIP?CS80240333CUIYong5如何權(quán)衡路由發(fā)現(xiàn)的延遲預(yù)計算協(xié)議因為維護(hù)著包含所有路由的路由表所以延遲較低反應(yīng)式協(xié)議因為只有在X試圖向Y發(fā)送數(shù)據(jù)時才計算X到Y(jié)的路由，所以可能會產(chǎn)生很大的延遲路由發(fā)現(xiàn)/維護(hù)的開銷反應(yīng)式路由因為只有在有需求時才計算路由，所以開銷會較小預(yù)計算協(xié)議因為需要不斷進(jìn)行路由更新，所以開銷可能（但不是必須的）會很大取決于流量類型和移動方式CS80240333CUIYong6如何向目的節(jié)點發(fā)送消息路由反應(yīng)式預(yù)計算事先沒有路由呢?有什么簡單的解決方法?CS80240333CUIYong7數(shù)據(jù)洪泛

BASEFHJDCGIK表示相連的節(jié)點在彼此的傳輸范圍內(nèi)ZY表示已經(jīng)收到數(shù)據(jù)包P的節(jié)點MNL從S向D發(fā)送一個數(shù)據(jù)包CS80240333CUIYong8數(shù)據(jù)洪泛BASEFHJDCGIK表示數(shù)據(jù)包P的傳輸方向表示首次接收到數(shù)據(jù)包P的節(jié)點ZY廣播MNLCS80240333CUIYong9數(shù)據(jù)洪泛

BASEFHJDCGIK節(jié)點H從兩個鄰居處都接收到數(shù)據(jù)包P:潛在的沖突ZYMNLCS80240333CUIYong10數(shù)據(jù)洪泛BASEFHJDCGIK節(jié)點C從G和H接收到數(shù)據(jù)包P,但不再繼續(xù)轉(zhuǎn)發(fā)下去,因為節(jié)點C已經(jīng)轉(zhuǎn)發(fā)過一次數(shù)據(jù)包P了ZYMNLCS80240333CUIYong11數(shù)據(jù)洪泛BASEFHJDCGIKZYM節(jié)點J和K都向節(jié)點D廣播數(shù)據(jù)包P

因為節(jié)點J和K互為隱藏節(jié)點,它們的傳輸可能會產(chǎn)生沖突=>

盡管使用洪泛的方法，但數(shù)據(jù)包P可能不會被發(fā)送給節(jié)點DNLCS80240333CUIYong12數(shù)據(jù)洪泛

BASEFHJDCGIKZY因為節(jié)點D是接收數(shù)據(jù)包P的目的節(jié)點，

所以節(jié)點D不會轉(zhuǎn)發(fā)數(shù)據(jù)包PMNLCS80240333CUIYong13數(shù)據(jù)洪泛

BASEFHJDCGIK

洪泛完成

從節(jié)點S無法到達(dá)的節(jié)點接收不到數(shù)據(jù)包P(例如,節(jié)點Z)

對于所有到S的路徑都經(jīng)過D的節(jié)點，也接收不到數(shù)據(jù)包P(例如:節(jié)點N)ZYMNLCS80240333CUIYong14數(shù)據(jù)洪泛

BASEFHJDCGIK洪泛的方法可能會把數(shù)據(jù)包發(fā)給太多節(jié)點(在最壞的情況下,所有可達(dá)節(jié)點都可能會受到數(shù)據(jù)包)ZYMNLCS80240333CUIYong15數(shù)據(jù)洪泛:優(yōu)勢簡單比較高效，當(dāng)…信息傳輸率足夠低

顯示路由發(fā)現(xiàn)/維護(hù)的開銷相當(dāng)大例子節(jié)點頻繁傳輸小數(shù)據(jù)包網(wǎng)絡(luò)拓?fù)渥兓l繁高可靠性的數(shù)據(jù)傳輸因為數(shù)據(jù)包可能通過多條路徑發(fā)往目的節(jié)點CS80240333CUIYong16數(shù)據(jù)洪泛:不足高開銷數(shù)據(jù)包可能會被發(fā)送給許多不想要接收的節(jié)點數(shù)據(jù)傳輸潛在低可靠性可靠的廣播?洪泛使用廣播—在不明顯增加開銷的前提下很難實現(xiàn)可靠的廣播傳輸CS80240333CUIYong17課程大綱

MANET中的路由MANET路由協(xié)議設(shè)計先應(yīng)式協(xié)議DSR和優(yōu)化AODV反應(yīng)式協(xié)議OLSRDSDV混合協(xié)議ZRP,LANMAR總結(jié)CS80240333CUIYong18數(shù)據(jù)洪泛BASEFHJDCGIK如果持續(xù)有數(shù)據(jù)要傳輸將會怎么樣?

如何擴(kuò)展洪泛路由?ZYMNL誰應(yīng)該存儲路由?發(fā)現(xiàn)一條路由并存儲在源節(jié)點在路徑上的節(jié)點或數(shù)據(jù)包中存儲路由CS80240333CUIYong19課程大綱

MANET中的路由MANET路由協(xié)議設(shè)計先應(yīng)式協(xié)議DSR和優(yōu)化AODV反應(yīng)式協(xié)議OLSRDSDV混合協(xié)議ZRP,LANMAR總結(jié)CS80240333CUIYong20動態(tài)源路由(DSR)DSR的三個步驟路由發(fā)現(xiàn)數(shù)據(jù)傳輸

路由維護(hù)路由發(fā)現(xiàn)

當(dāng)節(jié)點S想要往節(jié)點D發(fā)送數(shù)據(jù)，但是不知道到節(jié)點D的路由,節(jié)點發(fā)起路由發(fā)現(xiàn)過程源節(jié)點S洪泛路由請求消息(RREQ)

每一個節(jié)點在轉(zhuǎn)發(fā)RREQ消息時都在消息中添加自己的標(biāo)識Johnson@MobileComputing’96CS80240333CUIYong21DSR的路由發(fā)現(xiàn)過程

BASEFHJDCGIKZY表示收到從S發(fā)往D的RREQ消息的節(jié)點MNLCS80240333CUIYong22DSR路由發(fā)現(xiàn)過程

BASEFHJDCGIK表示RREQ的傳輸方向ZY廣播MNL[S][X,Y]表示添加到RREQ消息中的節(jié)點標(biāo)識表CS80240333CUIYong23DSR的路由發(fā)現(xiàn)過程BASEFHJDCGIK節(jié)點H接收到兩個鄰居發(fā)來的RREQ消息:

潛在的沖突ZYMNL[S,E][S,C]CS80240333CUIYong24DSR的路由發(fā)現(xiàn)過程BASEFHJDCGIK節(jié)點C從G和H處接收到RREQ消息，但是不能再轉(zhuǎn)發(fā)出去，因為節(jié)點C已經(jīng)轉(zhuǎn)發(fā)過一次該消息ZYMNL[S,C,G][S,E,F]CS80240333CUIYong25DSR的路由發(fā)現(xiàn)過程BASEFHJDCGIKZYM節(jié)點J和K都向節(jié)點D廣播RREQ消息

因為節(jié)點J和K互為隱藏節(jié)點，它們的

傳輸可能存在沖突

NL[S,C,G,K][S,E,F,J]CS80240333CUIYong26DSR的路由發(fā)現(xiàn)過程BASEFHJDCGIKZY節(jié)點D不轉(zhuǎn)發(fā)RREQ消息,因為節(jié)點D是路由發(fā)現(xiàn)的目的節(jié)點MNL[S,E,F,J,M]CS80240333CUIYong27DSR的路由發(fā)現(xiàn)過程路由回復(fù)目的節(jié)點D在第一次收到RREQ消息時,發(fā)送路由回復(fù)消息(RREP)RREP的發(fā)送路由是由RREQ消息中的路由反轉(zhuǎn)得到的RREP包含節(jié)點D從RREQ消息中獲取的從S到D的路由CS80240333CUIYong28DSR的路由回復(fù)BASEFHJDCGIKZYMNLRREP[S,E,F,J,D]表示RREP控制消息如何實現(xiàn)單向（不對稱）鏈路?CS80240333CUIYong29動態(tài)源路由(DSR)DSR的三個步驟路由發(fā)現(xiàn)數(shù)據(jù)傳輸

路由維護(hù)數(shù)據(jù)傳輸節(jié)點S收到RREP消息,將其中的路由緩存下來當(dāng)節(jié)點S向節(jié)點D發(fā)送數(shù)據(jù)包時，完整的路由就被加到數(shù)據(jù)包頭因此命名為源路由中間節(jié)點通過數(shù)據(jù)包中包含的源路由來決定下一步要把數(shù)據(jù)包轉(zhuǎn)發(fā)給誰CS80240333CUIYong30DSR的數(shù)據(jù)傳輸BASEFHJDCGIKZYMNLDATA[S,E,F,J,D]有什么問題?包頭大小隨著路由的長度而增加可能會發(fā)生路由失效產(chǎn)生路由失效后誰該來進(jìn)行恢復(fù)？CS80240333CUIYong31路由維護(hù)BASEFHJDCGIKZYMNLRERR[J-D]當(dāng)D試圖轉(zhuǎn)發(fā)S發(fā)來數(shù)據(jù)包（按照SEFJD路徑）并在J-D上發(fā)生鏈路錯誤時，它會按照J(rèn)-F-E-S路徑向S發(fā)送路由錯誤(RERR)CS80240333CUIYong32DSR優(yōu)化:路由緩存BASEFHJDCGIKZYMNLDATA[S,E,F,J,D]可以緩存什么?什么時候緩存?CS80240333CUIYong33DSR優(yōu)化:路由緩存每個節(jié)點都緩存一條新的路由，無論它是如何學(xué)到該路由的什么時候?當(dāng)節(jié)點S找到到節(jié)點D的路由[S,E,F,J,D]

，它還會學(xué)習(xí)到節(jié)點F的路由[S,E,F]當(dāng)節(jié)點K收到[S,C,G]

的路由請求，W節(jié)點K學(xué)習(xí)到到節(jié)點S的路由[K,G,C,S]當(dāng)節(jié)點F轉(zhuǎn)發(fā)包含[S,E,F,J,D]的路由回復(fù)RREP消息,

節(jié)點F學(xué)習(xí)到到節(jié)點D的路由[F,J,D]當(dāng)節(jié)點E轉(zhuǎn)發(fā)包含[S,E,F,J,D]的數(shù)據(jù)包，它學(xué)習(xí)到到節(jié)點D的路由[E,F,J,D]節(jié)點也可以通過監(jiān)聽數(shù)據(jù)包來學(xué)習(xí)其中包含的路由信息CS80240333CUIYong34路由緩存的使用多徑緩存當(dāng)一條到節(jié)點D的路由失效，如果本地緩存中存在到節(jié)點D的路由，它就會使用該路由.否則，節(jié)點S發(fā)送一個路由請求消息，發(fā)起路由發(fā)現(xiàn)過程途中的回復(fù)

節(jié)點X如果知道到達(dá)節(jié)點D的路由，當(dāng)它收到路由請求消息時，就會發(fā)送路由回復(fù)消息優(yōu)勢

可以加速路由發(fā)現(xiàn)可以減少路由請求消息的擴(kuò)散CS80240333CUIYong35路由緩存的使用BASEFHJDCGIK[X,X,X]表示在節(jié)點處緩存的路由(DSR中使用樹的形式來緩存路由)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]ZCS80240333CUIYong36路由緩存的使用:

可以加快路由發(fā)現(xiàn)的速度BASEFHJDCGIKZMNL[S,E,F,J,D][E,F,J,D][C,S][G,C,S][F,J,D],[F,E,S][J,F,E,S]RREQ當(dāng)節(jié)點Z發(fā)送一條目的節(jié)點為節(jié)點C的路由請求消息,

節(jié)點K回復(fù)一條包含自己本地緩存路徑[Z,K,G,C]的路由回復(fù)消息[K,G,C,S]RREPCS80240333CUIYong37路由緩存的使用:

C可以減少路由請求消息的擴(kuò)散BASEFHJDCGIKZYMNL[S,E,F,J,D][E,F,J,D][C,S][G,C,S][F,J,D],[F,E,S][J,F,E,S]RREQ假定節(jié)點D和Z之間沒有鏈路.節(jié)點K發(fā)送的路由回復(fù)消息可以限制RREQ消息的洪泛.通常，限制的效果可能并不明顯.[K,G,C,S]RREP緩存問題?很古老!CS80240333CUIYong38動態(tài)源路由優(yōu)勢

低開銷可靠

不足

數(shù)據(jù)包頭較大緩存的路由信息較陳舊可能會發(fā)生沖突網(wǎng)絡(luò)風(fēng)暴問題CS80240333CUIYong39DSR的優(yōu)化進(jìn)一步的問題接收到無用的數(shù)據(jù)包不止一次接收到相同的數(shù)據(jù)包數(shù)據(jù)包轉(zhuǎn)發(fā)中產(chǎn)生的沖突兩方面?如何減小路由請求消息洪泛的范圍?LARKo@Mobicom’98位置請求Castaneda@Mobicom’99如何解決廣播風(fēng)暴問題?Ni@Mobicom’99CS80240333CUIYong40優(yōu)化方法1:

位置輔助路由協(xié)議(LAR)使用位置信息

利用位置信息來限制路由請求消息洪泛的范圍位置信息可以通過GPS獲得預(yù)期域包含當(dāng)前目的節(jié)點位置的一個區(qū)域基于潛在的舊的位置信息和目的節(jié)點的速度來決定預(yù)期域請求域路由請求只發(fā)送給包含在預(yù)期域和發(fā)送者的位置內(nèi)的節(jié)點CS80240333CUIYong41LAR的預(yù)期域XYrX=最近一次獲得的節(jié)點D的位置,在時間t0Y=在當(dāng)前時間t1時節(jié)點D的位置,節(jié)點S并不知道r=(t1-t0)*估計的節(jié)點D的速度預(yù)期區(qū)域CS80240333CUIYong42LAR的請求域XYrS請求域網(wǎng)絡(luò)空間BA請求域直接在路由請求消息中指定節(jié)點A不轉(zhuǎn)發(fā)RREQ消息,但節(jié)點B轉(zhuǎn)發(fā)每個節(jié)點必須知道自己的物理位置以此來確定自己是否在請求域內(nèi)CS80240333CUIYong43LAR分析優(yōu)勢?不足?如果請求域失效?如果使用過小的請求域而沒有找到合適的路由然后發(fā)送者使用更大的請求域發(fā)起一次新的路由發(fā)現(xiàn)(在超時后)請求域最大可能是整個網(wǎng)絡(luò)域CS80240333CUIYong44LAR變形:自適應(yīng)請求域更改區(qū)域

每個節(jié)點都可能會更改轉(zhuǎn)發(fā)的請求消息中的請求域使用近期/準(zhǔn)確的信息來決定如何更改請求域,可能會比原始請求域小SB節(jié)點B更改的請求域發(fā)送者S定義的請求域CS80240333CUIYong45位置輔助路由(LAR)假設(shè)基本的假設(shè)：最初,

只有在路由發(fā)現(xiàn)過程中節(jié)點X的位置信息才會讓節(jié)點Y知道這一位置信息用于下一步進(jìn)行路由發(fā)現(xiàn)每次路由發(fā)現(xiàn)產(chǎn)生更多更新信息用于下一步的路由發(fā)現(xiàn)變形位置攜帶

位置信息可以攜帶在從Y發(fā)送到X的任何信息中Y也可能會主動擴(kuò)散它的位置信息類似于以后要討論的其他的一些協(xié)議(例如,DREAM,GLS)CS80240333CUIYong46基于移動的距離影響路由算法(DREAM)與LAR類似使用位置和速度信息特性DREAM使用數(shù)據(jù)包洪泛作為路由機(jī)制(不同于LAR)DREAM使用位置信息將數(shù)據(jù)包洪泛控制在一個小范圍內(nèi)Basagni@Mobicom’98CS80240333CUIYong47基于移動的距離影響路由策算法(DREAM)預(yù)期域(LAR術(shù)語)SDA節(jié)點A收到數(shù)據(jù)包后將它轉(zhuǎn)發(fā)給在自己的錐形區(qū)域中的鄰居節(jié)點節(jié)點S向所有在它錐形區(qū)域內(nèi)的鄰居節(jié)點發(fā)送數(shù)據(jù)包CS80240333CUIYong48基于移動的距離影響路由算法(DREAM)位置廣播

節(jié)點周期性的廣播它們的物理位置靠近該節(jié)點的鄰居節(jié)點更新頻繁，遠(yuǎn)離該節(jié)點的鄰居節(jié)點更新不頻繁距離影響遠(yuǎn)處的節(jié)點和近處的相比就好像是以一個較低的角速度移動TTL位置更新的生存時間字段用來控制信息擴(kuò)散的距離CS80240333CUIYong49LAR變形:隱式請求域在原來的方法中，路由請求消息中直接指定請求域可選的方法如果節(jié)點X被視為比Y更靠近預(yù)期域，則節(jié)點X轉(zhuǎn)發(fā)從Y發(fā)來的路由請求消息這樣做的目的是為了是路由請求消息經(jīng)過轉(zhuǎn)發(fā)后在物理位置上更接近目的節(jié)點CS80240333CUIYong50位置輔助路由(LAR)優(yōu)勢減小路由請求消息洪泛的范圍降低路由發(fā)現(xiàn)開銷不足節(jié)點需要知道它們的物理位置沒有考慮無線傳輸路徑中可能存在的障礙物可達(dá)性進(jìn)一步優(yōu)化?CS8024033351地理距離路由(GEDIR)Lin’98目的節(jié)點的地理位置假設(shè)為已知每個節(jié)點知道它的鄰居節(jié)點的地理位置每個節(jié)點都向離目的節(jié)點最近的鄰居節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包從S到D的路由如下所示SABDCFE障礙物HGCUIYongCS8024033352地理距離路由(GEDIR)Stojmenovic’99策略無法實現(xiàn)從S到E的路由節(jié)點G是節(jié)點C離目的節(jié)點E最近的鄰居節(jié)點，但是C沒有到E的路由繞過障礙物的改進(jìn)算法[Bose99]@DIALM,[Karp00]@MobicomSABDCFE障礙物HGCUIYongCS80240333CUIYong53優(yōu)化方法2:請求定位

主要的區(qū)別不使用物理位置信息來限制路由請求消息的洪泛范圍路由請求消息只沿著靠近原本已知的路由的路徑傳播“接近”這一屬性不基于物理位置信息來確定啟發(fā)式路徑選擇機(jī)制尋找一條新的路徑，該路徑中至多包含k個不存在于原已知路由中的節(jié)點

在舊路由上記錄新的路由請求信息路由請求只有當(dāng)累計的路由中至多包含k個不存在于原路由的新節(jié)點時才會被轉(zhuǎn)發(fā)Castaneda@Mobicom’9954請求定位:示例BEASDCGF從S到D的起始路由BEASDCGF允許的路徑withk=2節(jié)點F不轉(zhuǎn)發(fā)路由請求，因為它不在任何S到D之間至多包含兩個新節(jié)點的路徑上節(jié)點D移動CS80240333CUIYongCS80240333CUIYong55請求定位優(yōu)勢不需要依靠地址位置信息來降低路由發(fā)現(xiàn)的開銷

當(dāng)出現(xiàn)障礙物時可以更好的實現(xiàn)在舊路由附近尋找新的路由不足可能會生成比LAR方法更長的路由(短路由可能會包含多于K個的新節(jié)點)CS80240333CUIYong56優(yōu)化方法3:廣播風(fēng)暴問題

Ni@Mobicom’99高概率的沖突

當(dāng)節(jié)點A廣播一個路由請求消息,節(jié)點B和C都能接收到B和C都向他們的鄰居節(jié)點廣播該消息因為對來自于A的相同的路由請求消息同時作反應(yīng)，所以B和C幾乎同時轉(zhuǎn)發(fā)該消息冗余一個特定節(jié)點可能從許多節(jié)點接收到相同的路由請求消息，而該消息其實收到一次就夠了的

節(jié)點D可能從節(jié)點B和C都收到了消息DBCA只選擇一個?CS80240333CUIYong57廣播風(fēng)暴的解決方法概率方法一旦首次接收到一個路由請求消息，節(jié)點就會以概率P重廣播（轉(zhuǎn)發(fā)）該消息沖突避免技術(shù)

相同的,當(dāng)信道空閑時，不同節(jié)點的重廣播需要等待一個隨機(jī)時延

這會降低在原來的那個例子里節(jié)點B和C同時轉(zhuǎn)發(fā)一個數(shù)據(jù)包的概率CS80240333CUIYong58BDCAFE廣播風(fēng)暴的解決方法基于計數(shù)的方法節(jié)點E在要轉(zhuǎn)發(fā)一個路由請求之前，如果發(fā)現(xiàn)超過K個鄰居節(jié)點都廣播該消息，則自己不會轉(zhuǎn)發(fā)該消息判斷依據(jù)

k

個鄰居節(jié)點共同轉(zhuǎn)發(fā)該消息時可能已經(jīng)把該消息發(fā)往E的所有鄰居節(jié)點了CS80240333CUIYong59廣播風(fēng)暴的解決方法基于距離的方法如果節(jié)點E在物理距離d內(nèi)偵聽到某些節(jié)點Z的RREQ消息的廣播,則E不會重廣播該消息

判斷依據(jù)Z和E太靠近了，所以Z和E的覆蓋范圍沒有什么區(qū)別

如果E重廣播該消息，那么沒有多少沒接收到Z的相同廣播消息的節(jié)點會接收到該廣播消息EZ<dCS80240333CUIYong60總結(jié):廣播風(fēng)暴問題問題在哪里?洪泛，例如，在動態(tài)源路由協(xié)議中(DSR)問題是什么?洪泛冗余洪泛沖突可能的解決方法隨機(jī)等待沖突可能通過“抖動”的方法來解決(等待一個隨機(jī)事件后再進(jìn)行洪泛)位置/距離感知冗余可以通過選擇一個子集中的節(jié)點來重廣播的方法來降低CS80240333CUIYong61課程大綱

MANET中的路由MANET路由協(xié)議設(shè)計先應(yīng)式協(xié)議DSR和優(yōu)化AODV反應(yīng)式協(xié)議OLSRDSDV混合協(xié)議ZRP,LANMAR總結(jié)CS80240333CUIYong62按需路由向量路由協(xié)議(AODV)

Perkins@WMCSA’99DSR協(xié)議的不足和它的變型DSR協(xié)議在數(shù)據(jù)包頭中包含源路由由此產(chǎn)生的大包頭可能會降低性能特別是當(dāng)包里的數(shù)據(jù)內(nèi)容比較小時更為明顯如何改進(jìn)DSRAODV在節(jié)點處維護(hù)路由表,所以數(shù)據(jù)包中無需加入路由信息AODV保留DSR中路由只在需要通信時才在對端兩個節(jié)點上保存的特性CS80240333CUIYong63AODV機(jī)制路由請求(RREQ)消息的轉(zhuǎn)發(fā)方式與DSR類似路由發(fā)現(xiàn)和路徑反轉(zhuǎn)當(dāng)節(jié)點重廣播一個路由請求消息時，它會建立一條指向源節(jié)點的反向路徑AODV假定鏈路是（雙向）對稱的當(dāng)目的節(jié)點接收到一個路由請求，它會發(fā)送一個路由回復(fù)消息路由回復(fù)沿著根據(jù)路由請求發(fā)送路徑建立的反向路徑傳播CS80240333CUIYong64AODV的路由請求過程

BASEFHJDCGIKZY表示已經(jīng)接收到從S發(fā)往D的RREQ消息的節(jié)點MNLCS80240333CUIYong65AODV的路由請求過程

BASEFHJDCGIK表示RREQ消息的傳播方向ZY廣播MNLCS80240333CUIYong66AODV的路由請求過程

BASEFHJDCGIK表示反向路徑鏈路ZYMNLCS80240333CUIYong67AODV的反向路徑建立

BASEFHJDCGIK節(jié)點C接收到從G和H發(fā)送來的RREQ消息,但是并不轉(zhuǎn)發(fā)它,

因為自己已經(jīng)轉(zhuǎn)發(fā)過該RREQ消息ZYMNLCS80240333CUIYong68AODV的反向路徑建立

BASEFHJDCGIKZYMNLCS80240333CUIYong69AODV的反向路徑建立

BASEFHJDCGIKZY節(jié)點D不轉(zhuǎn)發(fā)RREQ消息,因為節(jié)點D是該消息的目的節(jié)點

MNLCS80240333CUIYong70AODV的路由回復(fù)

BASEFHJDCGIKZY表示RREP消息傳播的路徑

MNLCS80240333CUIYong71AODV的路由回復(fù)類似于緩存方法中間節(jié)點（不是目的節(jié)點）如果知道比原路徑更新的到發(fā)送者S的路徑，它也可以發(fā)送路由回復(fù)(RREP)

消息CS80240333CUIYong72AODV的轉(zhuǎn)發(fā)路徑建立

BASEFHJDCGIKZYMNL當(dāng)RREP消息沿反向路徑發(fā)送時建立轉(zhuǎn)發(fā)鏈路表示鏈路在轉(zhuǎn)發(fā)路徑上CS80240333CUIYong73AODV的數(shù)據(jù)傳輸BASEFHJDCGIKZYMNL路由表完全用于數(shù)據(jù)轉(zhuǎn)發(fā).路由不用加在數(shù)據(jù)包頭中.DATACS80240333CUIYong74超時設(shè)定反向路徑計時每一個路由表表項對應(yīng)一條反向路徑，當(dāng)計時器超時時刪除該表項超時時間設(shè)置的足夠長，以保證RREP消息能夠返回轉(zhuǎn)發(fā)路徑計時每一個路由表表項對應(yīng)一條轉(zhuǎn)發(fā)路徑，如果在有效路由計時中未被使用，則被刪除如果沒有數(shù)據(jù)使用某一路由表項的路徑進(jìn)行傳輸，則該條目將從路由表中刪除(即使該路由實際上是有效的)CS80240333CUIYong75鏈路失效檢測Hello消息Hello消息:鄰居節(jié)點周期性的交互hello消息沒有收到hello消息表示鏈路失效MAC確認(rèn)消息或者,沒有收到MAC層確認(rèn)消息也被視為鏈路失效CS80240333CUIYong76AODV的序列號目的序列號使用目的序列號來確認(rèn)中間節(jié)點所學(xué)到的路徑是否為最新的使用AODV協(xié)議時中間節(jié)點發(fā)送路由回復(fù)的可能性不像DSR協(xié)議那么高給節(jié)點S向目的節(jié)點發(fā)送的一條新的路由請求賦予一個高序號值.中間節(jié)點如果有一個較小的序號值，那么即使它知道通往目的節(jié)點的路由，也不能發(fā)送路由回復(fù)CS80240333CUIYong77關(guān)于路由錯誤當(dāng)出現(xiàn)路由錯誤的處理過程錯誤發(fā)現(xiàn)當(dāng)節(jié)點X無法在鏈路(X,Y)上轉(zhuǎn)發(fā)數(shù)據(jù)包P(從節(jié)點S到節(jié)點D)，它就生成一個錯誤消息錯誤報告節(jié)點X增加為節(jié)點D緩存的序列號值增加的序列號N包含在錯誤消息中路由恢復(fù)當(dāng)節(jié)點S收到錯誤消息后，它使用至少不小于N的目的序列號來發(fā)起一次新的路由發(fā)現(xiàn)當(dāng)收到包含目的序列號為N的路由請求消息后，如果自己的序列號小于N，則節(jié)點D會把它設(shè)置為NCS80240333CUIYong78為什么要在AODV中使用序列號為什么需要使用序列號?避免使用舊的/錯誤的路由確定哪個路由是新的避免出現(xiàn)路由環(huán)路假定A不知道C-D鏈路失效，因為C發(fā)送的路由錯誤消息丟失了C為D發(fā)起一次路由請求，節(jié)點A接收到RREQ消息（通過路徑C-E-A）節(jié)點A知道經(jīng)過節(jié)點B到D的路由，所以它會回復(fù)該RREQ消息產(chǎn)生環(huán)路(例如,C-E-A-B-C)ABCDECS80240333CUIYong79優(yōu)化方法:擴(kuò)展環(huán)搜索法發(fā)起路由請求時在消息中加入生命周期(TTL)字段,以此來限制該消息的傳播范圍DSR協(xié)議也包含一個類似的優(yōu)化方法如果最后沒收到路由回復(fù)，則設(shè)置更大的TTL重新發(fā)送CS80240333CUIYong80總結(jié):AODV路由信息不加入包頭節(jié)點維護(hù)的路由表中只包含有效路由條目節(jié)點中記錄至多一跳的目的節(jié)點的信息DSR會在單個目的節(jié)點處維護(hù)許多路由條目即使拓?fù)洳话l(fā)生變化，路由條目也會失效

CS80240333CUIYong81許多其他協(xié)議許多變型方法都基于控制路由發(fā)現(xiàn)消息洪泛范圍的基本方法CS80240333CUIYong82面向能耗的路由方法將能耗作為路由優(yōu)化條件的算法例如最小化每個包的能耗最大化節(jié)點在能量耗盡之前的持續(xù)使用時間最小化因能量損耗而導(dǎo)致的網(wǎng)絡(luò)分區(qū)的時間...Singh@Mobicom’98,Chang@Infocom’00CS80240333CUIYong83面向能耗的路由方法

為每條鏈路分配一個權(quán)重權(quán)重函數(shù)能耗剩余能量水平低剩余能量水平對應(yīng)于高cost值更傾向于使用一個具有最小聚合權(quán)重值的路由Singh@Mobicom’98CS80240333CUIYong84基于信號穩(wěn)定性的自適應(yīng)路由(SSA)Dube’97與DSR類似信號穩(wěn)定性節(jié)點X只有在鏈路(X,Y)被認(rèn)定具有較強(qiáng)的信號穩(wěn)定性時才會重廣播從Y發(fā)送過來的路由請求消息如何估計信號穩(wěn)定性?我們利用近段期數(shù)據(jù)包接受時的信號強(qiáng)度的移動平均值來估計信號的穩(wěn)定性。CS80240333CUIYong85課程大綱

MANET中的路由MANET路由協(xié)議設(shè)計先應(yīng)式協(xié)議DSR和優(yōu)化AODV反應(yīng)式協(xié)議OLSRDSDV混合協(xié)議ZRP,LANMAR總結(jié)CS80240333CUIYong86先驗式協(xié)議目前討論過的方法大部分是反應(yīng)式的先驗式的方法基于已經(jīng)提出的距離-向量和鏈路狀態(tài)機(jī)制CS80240333CUIYong87鏈路狀態(tài)路由

Huitema’95基本方法節(jié)點周期性的洪泛它的鏈路狀態(tài)節(jié)點重廣播從鄰居節(jié)點處接收到的鏈路狀態(tài)信息節(jié)點跟蹤從其他節(jié)點處接收到的鏈路狀態(tài)信息節(jié)點使用上述信息來確定到各個目的節(jié)點的下一跳有什么問題?我們能降低消息洪泛的開銷么?CS80240333CUIYong88改進(jìn)的鏈路狀態(tài)路由方法(OLSR)Jacquet@IETF’00,Jacquet@INRIA’99降低開銷

通過使用較少節(jié)點來轉(zhuǎn)發(fā)信息的方法來降低鏈路狀態(tài)信息洪泛的開銷來自于節(jié)點X的廣播消息只被它的MPRs(MultipointRelays)轉(zhuǎn)發(fā)節(jié)點X的MPRs是他的鄰接節(jié)點，X的每個兩跳的鄰接節(jié)點會是他的MPRs中至少一個的一跳節(jié)點。節(jié)點通過周期性的發(fā)送信標(biāo)幀來傳輸它的鄰居列表，這樣一來所有節(jié)點都會知道他們的兩跳之內(nèi)的鄰居節(jié)點，并在其中選擇MPRCS80240333CUIYong89改進(jìn)的鏈路狀態(tài)路由方法(OLSR)ABFCDEHGKJ節(jié)點C和E是節(jié)點A的multipointrelays已經(jīng)廣播了A發(fā)來的狀態(tài)消息的節(jié)點CS80240333CUIYong90改進(jìn)的鏈路狀態(tài)路由方法(OLSR)節(jié)點C和E轉(zhuǎn)發(fā)從節(jié)點A接收到的消息ABFCDEHGKJ已經(jīng)廣播了A發(fā)來的狀態(tài)消息的節(jié)點CS80240333CUIYong91改進(jìn)的鏈路狀態(tài)路由方法(OLSR)ABFCDEHGKJ已經(jīng)廣播了A發(fā)來的狀態(tài)消息的節(jié)點CS80240333CUIYong92課程大綱

MANET中的路由MANET路由協(xié)議設(shè)計先應(yīng)式協(xié)議DSR和優(yōu)化AODV反應(yīng)式協(xié)議OLSRDSDV混合協(xié)議ZRP,LANMAR總結(jié)CS80240333CUIYong93目的序列距離矢量路由方法(DSDV)Perkins@Sigcomm’94每個節(jié)點維護(hù)一個存儲以下信息的路由表針對每個目的節(jié)點的下一跳到每個目的節(jié)點的路徑的開銷度量目的節(jié)點自己確定一個目的序列號序列號用于避免出現(xiàn)環(huán)路節(jié)點周期性的將路由表轉(zhuǎn)發(fā)給它的鄰居節(jié)點當(dāng)發(fā)送自己的路由表時每個節(jié)點都附上它的序列號序列號會被附于為該節(jié)點創(chuàng)建的路由條目上CS80240333CUIYong94目的序列距離矢量路由方法(DSDV)假設(shè)節(jié)點X接收到從節(jié)點Y發(fā)來的關(guān)于節(jié)點Z的路由信息讓S(X)和S(Y)分別表示存儲于節(jié)點X的關(guān)于節(jié)點Z的路由表項和節(jié)點Y發(fā)送的關(guān)于節(jié)點X的路由表項的目的序列號XYZCS80240333CUIYong95目的序列距離矢量路由方法(DSDV)節(jié)點X進(jìn)行以下步驟:IfS(X)>S(Y),則X忽略從節(jié)點Y接收到的路由信息

IfS(X)=S(Y),并且經(jīng)過Y的開銷小于已知的經(jīng)過X的開銷，則X將Y設(shè)置為到節(jié)點Z的下一跳IfS(X)<S(Y),則X將Y設(shè)置為到節(jié)點Z的下一跳，同時將S(X)設(shè)置成與S(Y)相等的值XYZCS80240333CUIYong96課程大綱

MANET中的路由MANET路由協(xié)議設(shè)計先應(yīng)式協(xié)議DSR和優(yōu)化AODV反應(yīng)式協(xié)議OLSRDSDV混合協(xié)議ZRP,LANMAR總結(jié)CS80240333CUIYong97混合協(xié)議:區(qū)域路由協(xié)議(ZRP)Haas’98區(qū)域路由協(xié)議先應(yīng)式路由協(xié)議:預(yù)先更新網(wǎng)絡(luò)狀態(tài)并且不論是否有數(shù)據(jù)傳輸都要維護(hù)路由表反應(yīng)式路由協(xié)議:只有當(dāng)有數(shù)據(jù)包發(fā)往某一目的節(jié)點時才確定通往該目的節(jié)點的路由如何構(gòu)造區(qū)域所有到節(jié)點