移動計算技術(shù)AdHoc網(wǎng)絡(luò)路由

課程主要內(nèi)容概述體系結(jié)構(gòu)AdHoc網(wǎng)絡(luò)路由第一頁，共七十九頁。內(nèi)容提要概述體系結(jié)構(gòu)AdHoc網(wǎng)絡(luò)路由第二頁，共七十九頁?；陬A(yù)先架設(shè)網(wǎng)絡(luò)基礎(chǔ)設(shè)施的無線網(wǎng)絡(luò)蜂窩網(wǎng)絡(luò)移動終端通過基站接入移動通信網(wǎng)絡(luò)無線局域網(wǎng)移動終端通過無線接入點(diǎn)接入Internet依賴于基站、無線接入點(diǎn)等現(xiàn)有基礎(chǔ)設(shè)施網(wǎng)絡(luò)第三頁，共七十九頁。自組織網(wǎng)絡(luò)的應(yīng)用需求臨時會議/緊急情況科學(xué)考察/探險/軍事戰(zhàn)場接入網(wǎng)絡(luò)服務(wù)商所需的時間和成本現(xiàn)有服務(wù)和架構(gòu)的性能或者能力遠(yuǎn)離網(wǎng)絡(luò)基礎(chǔ)設(shè)施而希望保持與網(wǎng)絡(luò)的連接無網(wǎng)絡(luò)基礎(chǔ)設(shè)施可用不想使用網(wǎng)絡(luò)設(shè)施網(wǎng)絡(luò)基礎(chǔ)設(shè)施范圍外自組織網(wǎng)絡(luò)第四頁，共七十九頁。自組織網(wǎng)的起源1972年分組無線網(wǎng)（PRNET）戰(zhàn)場環(huán)境下的數(shù)據(jù)通信1983年抗毀自適應(yīng)網(wǎng)絡(luò)（SURAN）支持大規(guī)模網(wǎng)絡(luò)適應(yīng)戰(zhàn)場快速變化環(huán)境需要的自適應(yīng)網(wǎng)絡(luò)協(xié)議1994年全球移動通信系統(tǒng)（GloMo）滿足軍事應(yīng)用需要的、可快速展開、高抗毀星的移動信息系統(tǒng)DARPA資助DefenseAdvancedResearchProjectAgency第五頁，共七十九頁。自組織網(wǎng)絡(luò)研究1991年IEEE802.11首次提出“AdHoc網(wǎng)絡(luò)”自組織、對等式、多跳無線移動通信網(wǎng)絡(luò)1997年IETF成立MANET工作組基于IP的無線多跳網(wǎng)絡(luò)路由2003年IRTF成立ANS研究組其它研究機(jī)構(gòu)ClosedAdHoc：ForthespecificpurposeonlyMANET：MobileAd-hocNetworksANS：AdHocNetworksScalability第六頁，共七十九頁。AdHoc網(wǎng)絡(luò)的定義由一組帶有無線通信收發(fā)裝置的(移動)終端節(jié)點(diǎn)組成的一個多跳臨時性自治系統(tǒng)每個(移動)終端同時具有路由器和主機(jī)兩種功能：作為主機(jī)，終端需要運(yùn)行面向用戶的應(yīng)用程序；作為路由器，終端需要運(yùn)行相應(yīng)的路由協(xié)議節(jié)點(diǎn)間路由通常由多跳(Hop)組成不需要網(wǎng)絡(luò)基礎(chǔ)設(shè)施，可以在任何地方、任何地點(diǎn)快速構(gòu)建多跳無線網(wǎng)絡(luò)、自組織網(wǎng)絡(luò)、無固定設(shè)施的網(wǎng)絡(luò)或者對等網(wǎng)絡(luò)第七頁，共七十九頁。AdHoc網(wǎng)絡(luò)的特點(diǎn)（1）獨(dú)立組網(wǎng)不需要任何預(yù)先網(wǎng)絡(luò)基礎(chǔ)設(shè)施動態(tài)拓?fù)涔?jié)點(diǎn)移動/開機(jī)/關(guān)機(jī)節(jié)點(diǎn)無線發(fā)送功率變化、無線信道干擾或者地形等因素影響自組織無控制中心節(jié)點(diǎn)故障不會影響到整個網(wǎng)絡(luò)節(jié)點(diǎn)之間通過無線連接形成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨時可能發(fā)生變化，而且變化的方式和速度可能都是無法預(yù)測的第八頁，共七十九頁。AdHoc網(wǎng)絡(luò)的特點(diǎn)（2）多跳路由接收端和發(fā)送端可使用比兩者直接通信小得多的功率進(jìn)行通信，因此節(jié)省了能量消耗通過中間節(jié)點(diǎn)參與分組轉(zhuǎn)發(fā)，能夠有效降低對無線傳輸設(shè)備的設(shè)計難度和成本，同時擴(kuò)大了自組織網(wǎng)絡(luò)的覆蓋范圍第九頁，共七十九頁。AdHoc網(wǎng)絡(luò)的特點(diǎn)（3）特殊的無線信道特征無線信道提供的網(wǎng)絡(luò)帶寬比有線信道低得多競爭無線共享信道產(chǎn)生碰撞信號衰落、噪聲干擾以及信道之間的干擾等終端的局限性能量、存儲、計算等資源受限安全性差無線鏈路的開放性移動性導(dǎo)致節(jié)點(diǎn)之間信任關(guān)系的變化可擴(kuò)展性不強(qiáng)節(jié)點(diǎn)之間的相互干擾造成網(wǎng)絡(luò)容量下降各節(jié)點(diǎn)吞吐量隨網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的增加而下降存在單向無線信道終端發(fā)射功率的不同及地形環(huán)境的影響第十頁，共七十九頁。AdHoc網(wǎng)絡(luò)與Sensor網(wǎng)絡(luò)Sensor網(wǎng)絡(luò)可以看作是一種特殊類型的AdHoc網(wǎng)絡(luò)各個無線節(jié)點(diǎn)靜態(tài)地隨機(jī)分布在某一區(qū)域。傳感器負(fù)責(zé)收集區(qū)域內(nèi)的傳感信號，將它們發(fā)到網(wǎng)關(guān)節(jié)點(diǎn)網(wǎng)關(guān)具有更大的處理能力，能進(jìn)一步處理信息，并且具有更大的發(fā)送范圍，可將信息送往某個大型網(wǎng)絡(luò)（Internet）并且到達(dá)最終的用戶與一般AdHoc網(wǎng)絡(luò)相比：節(jié)點(diǎn)數(shù)量多、分布稠密節(jié)點(diǎn)的能量、計算、存儲等資源進(jìn)一步受限第十一頁，共七十九頁。AdHoc網(wǎng)絡(luò)與無線局域網(wǎng)單跳與多跳研究重點(diǎn)不同通信模式不同主要研究集中在物理層和數(shù)據(jù)鏈路層移動終端的所有通信必須經(jīng)過無線接入點(diǎn)進(jìn)行無線局域網(wǎng)為單跳網(wǎng)絡(luò)，不存在路由問題AdHoc網(wǎng)絡(luò)的研究內(nèi)容主要以路由協(xié)議為核心的網(wǎng)絡(luò)層設(shè)計AdHoc網(wǎng)絡(luò)中移動終端的通信是對等的第十二頁，共七十九頁。移動AdHoc網(wǎng)絡(luò)(MANET)與移動IPMANET移動IP第十三頁，共七十九頁。AdHoc網(wǎng)絡(luò)所面臨的問題(1)特殊的信道共享方式共享信道隱藏節(jié)點(diǎn)問題/暴露節(jié)點(diǎn)問題動態(tài)變化網(wǎng)絡(luò)拓?fù)鋫鹘y(tǒng)路由協(xié)議花較高代價獲取的路由信息可能已經(jīng)陳舊有限的無線傳輸帶寬減少節(jié)點(diǎn)之間的交換的消息減少控制消息帶來的額外開銷有限的能量能量管理機(jī)制，各層考慮能量控制，包括網(wǎng)絡(luò)層路由安全問題無線信道的開放性更容易受到各種攻擊移動性使得節(jié)點(diǎn)的信任關(guān)系不斷變化由于節(jié)點(diǎn)資源受限，安全機(jī)制應(yīng)該是分布式的RTS/CTS，CSMA/CA網(wǎng)絡(luò)路由時需考慮第十四頁，共七十九頁。AdHoc網(wǎng)絡(luò)所面臨的問題(2)網(wǎng)絡(luò)管理拓?fù)涔芾泶_定將一組節(jié)點(diǎn)組織成網(wǎng)絡(luò)的機(jī)制移動性管理跟蹤網(wǎng)絡(luò)中移動節(jié)點(diǎn)的位置服務(wù)質(zhì)量管理多跳拓?fù)鋭討B(tài)變化的移動AdHoc網(wǎng)絡(luò)使得服務(wù)質(zhì)量保證更加困難自動配置…第十五頁，共七十九頁。實(shí)現(xiàn)AdHoc網(wǎng)絡(luò)的關(guān)鍵技術(shù)路由協(xié)議服務(wù)質(zhì)量管理功率控制傳輸層性能AdHoc網(wǎng)絡(luò)互聯(lián)安全問題網(wǎng)絡(luò)管理感知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化維護(hù)網(wǎng)絡(luò)拓?fù)涞倪B接高度自適應(yīng)性能量、服務(wù)質(zhì)量等約束信道接入技術(shù)節(jié)能機(jī)制多個AdHoc網(wǎng)絡(luò)互聯(lián)AdHoc內(nèi)部節(jié)點(diǎn)訪問Internet第十六頁，共七十九頁。內(nèi)容概述體系結(jié)構(gòu)AdHoc網(wǎng)絡(luò)路由第十七頁，共七十九頁。節(jié)點(diǎn)結(jié)構(gòu)主機(jī)：運(yùn)行應(yīng)用程序，完成數(shù)據(jù)處理等功能路由器：運(yùn)行路由協(xié)議，完成路由選擇、轉(zhuǎn)發(fā)分組等功能無線收發(fā)裝置：完成數(shù)據(jù)傳輸功能第十八頁，共七十九頁。網(wǎng)絡(luò)結(jié)構(gòu)平面結(jié)構(gòu)所有節(jié)點(diǎn)地位平等層次結(jié)構(gòu)網(wǎng)絡(luò)被劃分為簇（Cluster）每個簇由簇首節(jié)點(diǎn)(ClusterHead)和簇成員節(jié)點(diǎn)(ClusterMember)構(gòu)成簇首節(jié)點(diǎn)可形成更高一級的網(wǎng)絡(luò)平面結(jié)構(gòu)層次結(jié)構(gòu)第十九頁，共七十九頁。平面結(jié)構(gòu)和層次結(jié)構(gòu)比較平面結(jié)構(gòu)層次結(jié)構(gòu)完全分布式的網(wǎng)絡(luò)多個簇組成的網(wǎng)絡(luò)所有節(jié)點(diǎn)的地位是平等的節(jié)點(diǎn)被分為簇首和簇成員，簇首預(yù)先指定或者由選擇算法產(chǎn)生不存在網(wǎng)絡(luò)瓶頸，可存在多條路徑，網(wǎng)絡(luò)健壯性好簇首節(jié)點(diǎn)可能成為網(wǎng)絡(luò)瓶頸，所有到簇外的通信必須通過簇首節(jié)點(diǎn)進(jìn)行可擴(kuò)展性差，每個節(jié)點(diǎn)都需要知道到達(dá)所有其它節(jié)點(diǎn)的路由，適用于中小規(guī)模的網(wǎng)絡(luò)可擴(kuò)展性好，簇內(nèi)路由信息局部化，適用于大規(guī)模網(wǎng)絡(luò)第二十頁，共七十九頁。網(wǎng)絡(luò)協(xié)議棧基于TCP/IP體系結(jié)構(gòu)與Internet互聯(lián)傳統(tǒng)路由協(xié)議需要修改，以適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化傳輸層實(shí)現(xiàn)適應(yīng)于無線網(wǎng)絡(luò)的端到端可靠服務(wù)AdHoc網(wǎng)絡(luò)多用于能量受限的環(huán)境，能量管理尤為重要，因此各層都定義相應(yīng)的節(jié)能機(jī)制可選功能第二十一頁，共七十九頁。AdHoc網(wǎng)絡(luò)中的跨層設(shè)計嚴(yán)格分層的體系結(jié)構(gòu)(OSI參考模型，TCP/IP模型)協(xié)議的設(shè)計缺乏足夠的適應(yīng)性，不能滿足AdHoc網(wǎng)絡(luò)動態(tài)變化的需求，特別是在能量或者QoS等約束條件下跨層體系結(jié)構(gòu)任意層之間能夠進(jìn)行信息交互協(xié)作在動態(tài)環(huán)境下，根據(jù)能量或者QoS等約束條件自適應(yīng)調(diào)節(jié)避免重復(fù)的功能，減少開銷減少反應(yīng)時間，快速適應(yīng)網(wǎng)絡(luò)動態(tài)變化第二十二頁，共七十九頁。內(nèi)容概述體系結(jié)構(gòu)AdHoc網(wǎng)絡(luò)路由第二十三頁，共七十九頁。AdHoc路由概述需要進(jìn)行通信的兩個節(jié)點(diǎn)可能不在相互的無線信號范圍內(nèi)需要其它節(jié)點(diǎn)承擔(dān)轉(zhuǎn)發(fā)工作節(jié)點(diǎn)移動后需要重新建立新的路由多跳路由移動第二十四頁，共七十九頁。MANET路由面臨的問題路由信息不易獲得定期交換路由信息或者按需搜索路由的開銷大網(wǎng)絡(luò)資源有限，并且必須被所有節(jié)點(diǎn)共享節(jié)點(diǎn)資源（電池、CPU）等有限也許不能接收到所有的路由信息路由信息不完整移動和分區(qū)很難將信息分發(fā)到一個沒有固定成員網(wǎng)絡(luò)的所有節(jié)點(diǎn)路由信息可能過期不可能連續(xù)的或者立即交換信息節(jié)點(diǎn)隨時移動無線傳播變化大第二十五頁，共七十九頁。MANET對路由協(xié)議的需求收斂迅速提供無環(huán)路由避免無窮計算控制管理開銷小對終端無過高要求支持單向信道盡量簡單實(shí)用路由機(jī)制必須適應(yīng)網(wǎng)絡(luò)三個不斷變化的基本特征移動節(jié)點(diǎn)的總體密度節(jié)點(diǎn)到節(jié)點(diǎn)的拓?fù)渚W(wǎng)絡(luò)的使用模式第二十六頁，共七十九頁。傳統(tǒng)的路由協(xié)議不適用于AdHoc網(wǎng)絡(luò)動態(tài)變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)節(jié)點(diǎn)加入、離開、移動等路由算法還未收斂,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)就發(fā)生變化有限的系統(tǒng)帶寬、能量等資源周期性地公告路由信息嚴(yán)重降低系統(tǒng)的性能間歇性的網(wǎng)絡(luò)分割傳統(tǒng)路由協(xié)議容易形成路由回路單向的無線傳輸信道傳統(tǒng)路由協(xié)議一般假設(shè)鏈路是對稱的適應(yīng)網(wǎng)絡(luò)動態(tài)變化減少路由開銷引入按需路由在路由時考慮能量等約束條件第二十七頁，共七十九頁。路由協(xié)議AdHoc路由協(xié)議表驅(qū)動路由先應(yīng)式(Proactive)按需路由反應(yīng)式(Reactive)ZRPDSDVTBRPFCGSROLSRLMRABRDSRAODVTORASSRDYMOOLSR:OptimizedLinkStateRoutingTBRPF:TopologyDisseminationBasedonReverse-PathForwardingAODV:AdHocOnDemandDistanceVectorDSR:DynamicSourceRoutingDTMO:DynamicMANETOn-demandRouting第二十八頁，共七十九頁。第二十九頁，共七十九頁。表驅(qū)動（TableDriven）路由先應(yīng)式(Proactive)路由傳統(tǒng)的分布式最短路徑路由協(xié)議鏈路狀態(tài)或者距離向量所有節(jié)點(diǎn)周期性更新“可達(dá)”信息每個節(jié)點(diǎn)維護(hù)到網(wǎng)絡(luò)中所有其它節(jié)點(diǎn)的路由所有路由都已存在并且隨時可用DSDV、OLSR、TBRPF路由延時小，但是路由開銷大第三十頁，共七十九頁。按需(On-demand)路由反應(yīng)式(Reactive)路由源節(jié)點(diǎn)根據(jù)需要通過路由發(fā)現(xiàn)過程來確定路由控制消息采用泛洪（Flooding）方式兩種實(shí)現(xiàn)技術(shù)源路由（分組攜帶完整的路由信息）逐跳（Hop-by-Hop）路由DSR、AODV、DYMO路由延時大，但是路由開銷小第三十一頁，共七十九頁。混合路由AdHoc網(wǎng)絡(luò)劃分為區(qū)域每個節(jié)點(diǎn)在區(qū)域內(nèi)部采用表驅(qū)動路由對于區(qū)域外節(jié)點(diǎn)采用按需路由簇和區(qū)域的不同簇內(nèi)所有節(jié)點(diǎn)都與簇首直接通信，簇內(nèi)節(jié)點(diǎn)間的通信一般是兩跳區(qū)域的大小沒有限制，區(qū)域內(nèi)的節(jié)點(diǎn)通信可以多跳ZRP：ZoneRoutingProtocol減少了域內(nèi)的路由延時減少了域外的路由開銷區(qū)域半徑的選擇小:節(jié)點(diǎn)移動快的密集網(wǎng)絡(luò)大:節(jié)點(diǎn)移動慢的稀疏網(wǎng)絡(luò)第三十二頁，共七十九頁。AdHoc路由協(xié)議的性能指標(biāo)端到端數(shù)據(jù)吞吐量和延時反映了數(shù)據(jù)的傳輸質(zhì)量路由獲取時間有數(shù)據(jù)要發(fā)送到發(fā)送出去的時間亂序分組發(fā)送率衡量無連接路由協(xié)議應(yīng)用于需要有序發(fā)送的傳輸層協(xié)議例如TCP時的性能路由協(xié)議的效率路由控制消息/發(fā)送數(shù)據(jù)路由協(xié)議的性能在不同環(huán)境表現(xiàn)不同,因此需要根據(jù)環(huán)境特點(diǎn)使用不同的路由協(xié)議第三十三頁，共七十九頁。表驅(qū)動（先應(yīng)式）路由協(xié)議第三十四頁，共七十九頁。帶目的地序列號的距離向量協(xié)議(DSDV)Destination-SequencedDistance-VectorDV(DistanceVector)算法DSDV協(xié)議第三十五頁，共七十九頁。DV算法概述基于分布式Bellman-Ford算法尋找從源點(diǎn)到某個點(diǎn)的最短路徑每個節(jié)點(diǎn)都維護(hù)一張路由表所有可達(dá)的目的地到達(dá)目的地的下一跳到達(dá)目的地的“距離”（開銷）節(jié)點(diǎn)向鄰居節(jié)點(diǎn)發(fā)送路由更新消息定期更新：即使節(jié)點(diǎn)路由表無變化觸發(fā)更新：節(jié)點(diǎn)路由表中某條路由發(fā)生變化路由更新消息包含列表格式<目的地，開銷>節(jié)點(diǎn)在收到“更好”路由的情況下更新路由表具有更小的開銷：對于同一個目的地，來自不同的下一跳更新開銷：對于同一目的地，來自相同的下一跳DV:DistanceVector

第三十六頁，共七十九頁。DV算法過程初始化ABCDest.NextMetricAA0BB3C-∞32Dest.NextMetricBB0AA3CC2Dest.NextMetricCC0BB2A-∞路由更新ABCDest.NextMetricAA0BB3CB532Dest.NextMetricBB0AA3CC2Dest.NextMetrictCC0BB2AB5<B,0><A,3><C,2><B,0><A,3><C,2>路由更新消息第三十七頁，共七十九頁。DV算法中的計數(shù)到無窮問題ABC32Dest.NextMetricBB0AA3CC2Dest.NextMetricCC0BB2AB5Dest.NextMetricBB0AA∞CC2<A,5>Dest.NextMetricBB0AC7CC2<A,7>Dest.NextMetricCC0BB2AB9<A,9>無窮計數(shù)！第三十八頁，共七十九頁。DV算法不能直接用于AdHoc網(wǎng)絡(luò)計數(shù)到無窮問題部分解決方法選擇一個相對較少的數(shù)作為無窮大水平分割(splithorizon)：當(dāng)一個節(jié)點(diǎn)把路由更新發(fā)送給相鄰節(jié)點(diǎn)時，它并不把從各個相鄰節(jié)點(diǎn)處學(xué)到的路由再回送給該節(jié)點(diǎn)無法發(fā)現(xiàn)路由循環(huán)限制了網(wǎng)絡(luò)的可擴(kuò)展性對兩個節(jié)點(diǎn)的路由循環(huán)有效，更大的路由循環(huán)需要更強(qiáng)的措施第三十九頁，共七十九頁。DSDV協(xié)議概述基于DV算法簡單，易于實(shí)現(xiàn)需要的存儲空間?。ㄖ豁毢袜従庸?jié)點(diǎn)交換路由信息）確保無路由回路路由表中的每個表項(xiàng)都帶有目的地序列號（由目的節(jié)點(diǎn)生成）對拓?fù)渥兓茏鞒隹焖俜磻?yīng)路由表有顯著變化時立即啟動路由公告(RouterAdvertisement)但是等待不穩(wěn)定路由的公告，以減緩路由波動(dampingfluctuations)先應(yīng)式（表驅(qū)動）路由節(jié)點(diǎn)維護(hù)到所有目的地的路由信息路由信息必須周期性的更新（無休眠節(jié)點(diǎn)）即使網(wǎng)絡(luò)拓?fù)錈o變化也存在著通信開銷維護(hù)的路由可能從不使用DSDV:Destination-SequencedDistanceVector

第四十頁，共七十九頁。DSDV路由表序列號（Sequencenumber）由目的端產(chǎn)生，用來防止出現(xiàn)路由回路，并確保路由信息是最新的格式：Dest_NNN加入時間（InstallTime）路由表項(xiàng)的創(chuàng)建時間，用來刪除過期表項(xiàng)StableData指向一個包含有路由穩(wěn)定狀態(tài)信息的表目的節(jié)點(diǎn)地址最近沉淀時間（lastsettlingtime）平均沉淀時間(averagesettlingtime)用于緩解網(wǎng)絡(luò)中的路由波動Dest.NextMetricSeq.NrInstallTimeStableDataAA0A-550001000Ptr_ABB1B-102001200Ptr_BCB3C-588001200Ptr-CDB4D-312001200Ptr_D對于同一個目的地，節(jié)點(diǎn)可能接收到來自其它節(jié)點(diǎn)的多條路由信息，settlingtime定義為第一條路由和最佳路由之間的時間間隔第四十一頁，共七十九頁。DSDV路由公告向每個鄰居公告自己的路由信息目的節(jié)點(diǎn)地址Metric：到目的節(jié)點(diǎn)的開銷，一般為到目的節(jié)點(diǎn)的跳數(shù)目的地序列號其它信息（例如硬件地址等）設(shè)置序列號信息的規(guī)則每次公告增加自己的目的地序列號（只使用偶數(shù)值）如果一個節(jié)點(diǎn)不再可達(dá)（timeout）,則將該節(jié)點(diǎn)的序列號加1（奇數(shù)序列號），并且設(shè)置metric為∞第四十二頁，共七十九頁。DSDV路由選擇將更新信息與自己的路由表比較選擇具有更大目的地序列號的路由，這將保證始終使用來自目的地的最新信息當(dāng)序列號相等時，選擇具有更好metric的路由第四十三頁，共七十九頁。DSDV協(xié)議操作：更新前路由表Dest.NextMetricSeqAA1A-550BB0B-100CC1C-588Dest.NextMetricSeqAA0A-550BB1B-100CB2C-588Dest.NextMetricSeq.AB2A-550BB1B-100CC0C-588ABC第四十四頁，共七十九頁。DSDV協(xié)議操作：路由公告<A,1,A-550><B,0,B-102><C,1,C-588><A,1,A-550><B,0,B-102><C,1,C-588>B遞增序列號100->102B向鄰居A、C廣播路由信息，其中包含有目的地序列號Dest.NextMetricSeqAA0A-550BB1B-100CB2C-588Dest.NextMetricSeqAA1A-550BB0B-102CC1C-588Dest.NextMetricSeq.AB2A-550BB1B-100CC0C-588ABC第四十五頁，共七十九頁。DSDV協(xié)議操作：更新后路由表Dest.NextMetricSeqAA0A-550BB1B-102CB2C-588Dest.NextMetricSeqAA1A-550BB0B-102CC1C-588Dest.NextMetricSeq.AB2A-550BB1B-102CC0C-588ABC第四十六頁，共七十九頁。對拓?fù)渥兓姆磻?yīng)立即公告有關(guān)新路由、鏈路斷開和metric變化的信息立即傳遞給鄰居節(jié)點(diǎn)完全/增量更新完全更新：發(fā)送自己路由表中的所有路由信息增量更新：只發(fā)送路由表中那些發(fā)生變化的表項(xiàng)（能包含在一個單獨(dú)的分組中發(fā)送）第四十七頁，共七十九頁。DSDV協(xié)議操作：新節(jié)點(diǎn)加入<D,0,D-000>Dest.NextMetricSeq.AA0A-550BB1B-104CB2C-590Dest.NextMetricSeq.AA1A-550BB0B-104CC1C-590Dest.NextMetricSeq.AB2A-550BB1B-104CC0C-5901.D第一次廣播,

發(fā)送序列號D-000ABCD第四十八頁，共七十九頁。DSDV協(xié)議操作：新節(jié)點(diǎn)加入Dest.NextMetricSeq.AB2A-550BB1B-104CC0C-590DD1D-0002.插入到D的表項(xiàng)，序列號為D-000Dest.NextMetricSeq.AA0A-550BB1B-104CB2C-590Dest.NextMetricSeq.AA1A-550BB0B-104CC1C-590ABCD第四十九頁，共七十九頁。DSDV協(xié)議操作：新節(jié)點(diǎn)加入<A,2,A-550><B,1,B-104><C,0,C-592><D,1,D-000><A,2,A-550><B,1,B-104><C,0,C-592)<D,1,D-000>Dest.NextMetricSeq.AB2A-550BB1B-104CC0C-592DD1D-0003.C遞增自己的序列號到C-592，然后立即廣播自己的新路由表Dest.NextMetricSeq.AA0A-550BB1B-104CB2C-590Dest.NextMetricSeq.AA1A-550BB0B-104CC1C-590ABCD第五十頁，共七十九頁。DSDV協(xié)議操作：新節(jié)點(diǎn)加入4.B獲取新的路由信息并且更新路由表Dest.NextMetricSeq.AC3A-550BC2B-104CC1C-592DD0D-000D從C獲取路由表信息并且生成自己的路由表ABCDDest.NextMetricSeq.AB2A-550BB1B-104CC0C-592DD1D-000Dest.NextMetricSeq.AA0A-550BB1B-104CB2C-590Dest.NextMetricSeq.AA1A-550BB0B-104CC1C-592第五十一頁，共七十九頁。DSDV協(xié)議操作：鏈路斷開<D,2,D-100><D,2,D-100>Dest.NextMetricSeq.………DC2D-100Dest.NextMetricSeq.………DB3D-100Dest.NextMetricSeq.………DD1D-100因?yàn)锽廣播的到達(dá)D的路由信息中的序列號小于C維護(hù)的D的序列號，因此C認(rèn)為B的廣播的是過期路由信息，不予采納1.C檢測到鏈路斷開-〉序列號遞增1(當(dāng)且僅當(dāng)這種情況不是目的節(jié)點(diǎn)設(shè)置序列號-〉奇數(shù)序列號)2.B廣播到達(dá)D的路由信息ABCD避免了循環(huán)避免了計數(shù)到無窮DDD-101第五十二頁，共七十九頁。DSDV協(xié)議操作：立即公告4.B立即傳送更新消息給A

(更新信息具有更大的序列號，因此將取代A中原有表項(xiàng))3.C立即傳遞更新信息給B

(更新信息具有更大的序列號，因此將取代B中原有表項(xiàng))ABCDDest.NextMetricSeq.………DC2D-100Dest.NextMetricSeq.………DB3D-100Dest.NextMetricSeq.………DDD-101<D,,D-101>(D,,D-101)DBD-101DCD-101第五十三頁，共七十九頁。DSDV協(xié)議操作：路由波動2.A收到來自P的路由更新消息<D,15,D-102>10Hops11Hops<D,0,D-102>APQDDest.NextMetricSeq.………DQ14D-100DP15D-1021.D公告序列號為D-102的路由<D,0,D-102>更新路由表中到D的表項(xiàng)立即進(jìn)行路由公告3.A收到來自Q的路由更新消息<D,14,D-102>DQ14D-102更新路由表中到D的表項(xiàng)立即進(jìn)行路由公告由于D或者任何一個節(jié)點(diǎn)的路由更新消息到達(dá)節(jié)點(diǎn)A時存在著時間差,就會導(dǎo)致不必要的路由公告路由表波動第五十四頁，共七十九頁。DSDV協(xié)議操作：減緩路由波動在一個單獨(dú)的表中記錄每條路由的最近的和平均的SettlingTimeSettlingTime：第一條路由和最佳路由之間的時間間隔路由表中的stabledata指向該表A在包含新序列號的第一條路由到達(dá)時更新路由表，但是等待一段時間再廣播該條路由等待時間=2*(avg.SettingTime)10Hops11Hops<D,0,D-102>APQD<D,0,D-102>可緩解大型網(wǎng)絡(luò)的路由波動問題，從而避免不必要的公告，節(jié)約了帶寬第五十五頁，共七十九頁。DSDV總結(jié)優(yōu)點(diǎn)簡單（基本上與DV算法一致）通過目的地序列號避免了路由循環(huán)，解決了DV算法中的計數(shù)到無窮問題無路由發(fā)現(xiàn)延時（先應(yīng)式路由）缺點(diǎn)所有節(jié)點(diǎn)都必須公告路由，因此不支持休眠（不能直接用于傳感器網(wǎng)絡(luò)）收斂慢（DV路由的特性）開銷大：大部分的路由信息從不使用可擴(kuò)展性是一個主要問題（所有先應(yīng)式路由都存在的問題）第五十六頁，共七十九頁。優(yōu)化鏈路狀態(tài)路由協(xié)議(OLSR)OptimizedLinkStateRoutingProtocol先應(yīng)式的鏈路狀態(tài)路由協(xié)議基于多點(diǎn)中繼（MPR）的概念的優(yōu)化只有MPR轉(zhuǎn)發(fā)廣播消息，減少了消息開銷只有MPR產(chǎn)生鏈路狀態(tài)信息，減少了網(wǎng)絡(luò)中廣播消息的數(shù)量MPR可能選擇只報告它和該MPR選舉節(jié)點(diǎn)之間的鏈路，因此在網(wǎng)絡(luò)中只散發(fā)部分鏈路狀態(tài)信息RFC3626第五十七頁，共七十九頁。基于拓?fù)鋸V播的反向路徑轉(zhuǎn)發(fā)(TBRPF)TopologyBroadcastbasedonReverse-PathForwarding本質(zhì)上是一種鏈路狀態(tài)協(xié)議協(xié)議組成鄰居發(fā)現(xiàn)模塊路由模塊與傳統(tǒng)鏈路狀態(tài)協(xié)議的差別拓?fù)涓孪⒏÷酚砷_銷更少更適合拓?fù)溲杆僮兓臒o線網(wǎng)絡(luò)RFC3684第五十八頁，共七十九頁。按需（反應(yīng)式）路由協(xié)議第五十九頁，共七十九頁。動態(tài)源路由協(xié)議(DSR)DynamicSourceRouting按需路由節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)時才進(jìn)行路由發(fā)現(xiàn)過程反應(yīng)型路由，僅維護(hù)活躍的路由源路由發(fā)送節(jié)點(diǎn)在分組中攜帶到達(dá)目的節(jié)點(diǎn)的路由信息（轉(zhuǎn)發(fā)分組的完整的節(jié)點(diǎn)序列）不需要中間節(jié)點(diǎn)維護(hù)路由信息節(jié)點(diǎn)緩存到目的節(jié)點(diǎn)的多條路由避免了在每次路由中斷時都需要進(jìn)行路由發(fā)現(xiàn)，因此能夠?qū)ν負(fù)渥兓鞒龈斓姆磻?yīng)，第六十頁，共七十九頁。DSR協(xié)議組成路由發(fā)現(xiàn)（RouteDiscovery）只有在源節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)時才啟動幫助源節(jié)點(diǎn)獲得到達(dá)目的節(jié)點(diǎn)的路由路由維護(hù)（RouteMaintenance）在源節(jié)點(diǎn)在給目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)時監(jiān)測當(dāng)前路由的可用情況當(dāng)網(wǎng)絡(luò)拓?fù)渥兓瘜?dǎo)致路由故障時切換到另一條路由或者重新發(fā)起路由發(fā)現(xiàn)過程路由發(fā)現(xiàn)和路由維護(hù)都是按需進(jìn)行的不需要周期性路由公告不需要感知鏈路狀態(tài)不需要鄰居檢測第六十一頁，共七十九頁。DSR路由發(fā)現(xiàn)：路由請求源節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播路由請求（RREQ：RouteRequest）消息源節(jié)點(diǎn)地址目的節(jié)點(diǎn)地址路由記錄：記錄從源節(jié)點(diǎn)到目的節(jié)點(diǎn)路由中的中間節(jié)點(diǎn)請求ID中間節(jié)點(diǎn)接收到RREQ后，將自己的地址附在路由記錄中ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)第六十二頁，共七十九頁。DSR路由發(fā)現(xiàn)：中間節(jié)點(diǎn)處理中間節(jié)點(diǎn)維護(hù)<源節(jié)點(diǎn)地址、請求ID>序列對列表重復(fù)RREQ檢測如果接收到的RREQ消息中的<源節(jié)點(diǎn)地址、請求ID>存在于本節(jié)點(diǎn)的序列對列表中如果接收到的RREQ消息中的路由記錄中包含本節(jié)點(diǎn)的地址如果檢測到重復(fù)，則中間節(jié)點(diǎn)丟棄該RREQ消息ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)丟棄F轉(zhuǎn)發(fā)的RREQ第六十三頁，共七十九頁。DSR路由發(fā)現(xiàn)：路由應(yīng)答目的節(jié)點(diǎn)收到RREQ后，給源節(jié)點(diǎn)返回路由應(yīng)答（RREP：RouteReply）消息拷貝RREQ消息中的路由記錄源節(jié)點(diǎn)收到RREP后在本地路由緩存中緩存路由信息(A-B-C-D)ABCDEF(A-B-C-D)(A-B-C-D)第六十四頁，共七十九頁。DSR路由發(fā)現(xiàn)：非對稱信道對稱信道目的節(jié)點(diǎn)到源節(jié)點(diǎn)的路由即為源節(jié)點(diǎn)到目的節(jié)點(diǎn)的反向路由非對稱信道如果目的節(jié)點(diǎn)的路由緩存中有到達(dá)源節(jié)點(diǎn)的路由，則直接使用否則目的節(jié)點(diǎn)需要發(fā)起到源節(jié)點(diǎn)的路由請求過程，同時將RREP消息附加在新的RREQ消息中第六十五頁，共七十九頁。DSR路由維護(hù)逐跳證實(shí)機(jī)制鏈路層確認(rèn)被動確認(rèn)（監(jiān)聽其它節(jié)點(diǎn)間的數(shù)據(jù)發(fā)送）其它高層要求DSR軟件返回確認(rèn)端到端證實(shí)機(jī)制無法確定故障發(fā)生的位置第六十六頁，共七十九頁。DSR逐跳證實(shí)機(jī)制如果數(shù)據(jù)分組被重發(fā)了最大次數(shù)仍然沒有收到下一跳的確認(rèn)，則節(jié)點(diǎn)向源端發(fā)送路由錯誤（RouteError）消息，并且指明中斷的鏈路源端將該路由從路由緩存中刪除如果源端路由緩存中存在另一條到目的節(jié)點(diǎn)的路由則使用該路由重發(fā)分組否則重新開始路由發(fā)現(xiàn)過程ABCDEF(A-B-C-E-)RouteError第六十七頁，共七十九頁。DSR優(yōu)化：路由緩存(1)

每個節(jié)點(diǎn)緩存它通過任何方式獲得的新路由轉(zhuǎn)發(fā)RREQ獲得從本節(jié)點(diǎn)到RREQ路由記錄中所有節(jié)點(diǎn)的路由，例如E轉(zhuǎn)發(fā)RREQ(A-B-C)獲得到到A的路由(C-B-A)轉(zhuǎn)發(fā)RREP獲得本節(jié)點(diǎn)到RREP路由記錄中所有節(jié)點(diǎn)的路由，例如B轉(zhuǎn)發(fā)RREP(A-B-C-D)獲得到D的路由(C-D)轉(zhuǎn)發(fā)數(shù)據(jù)分組獲得從本節(jié)點(diǎn)到數(shù)據(jù)分組節(jié)點(diǎn)列表中所有節(jié)點(diǎn)的路由，例如E轉(zhuǎn)發(fā)數(shù)據(jù)分組(A-B-C)獲得到A的路由(C-B-A)監(jiān)聽相鄰節(jié)點(diǎn)發(fā)送的分組RREQ、RREP、數(shù)據(jù)分組等(A-B-C-D)ABCDEF(A-B-C-D)(A-B-C-D)ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)以上均假設(shè)信道是對稱的!第六十八頁，共七十九頁。DSR優(yōu)化：路由緩存(2)中間節(jié)點(diǎn)使用緩存的到目的節(jié)點(diǎn)的路由響應(yīng)RREQRREP中的路由記錄=RREQ中的路由記錄+緩存的到目的節(jié)點(diǎn)的路由ABCDEF(B-C-D)(A-B-C-D)(A-)第六十九頁，共七十九頁。DSR優(yōu)化：路由緩存(3)錯誤路由緩存網(wǎng)絡(luò)拓?fù)涞淖兓沟镁彺娴穆酚墒в绊懞透腥酒渌?jié)點(diǎn)，使用該路由緩存的路由將不可用當(dāng)節(jié)點(diǎn)根據(jù)路由緩存回應(yīng)RREP時，其它監(jiān)聽到此RREP的節(jié)點(diǎn)會更改自己緩存的路由，從而感染錯誤路由緩存設(shè)置緩存路由的有效期，過期即刪除第七十頁，共七十九頁。DSR優(yōu)化：路由緩存(4)RREP風(fēng)暴節(jié)點(diǎn)廣播到某個目的節(jié)點(diǎn)的RREQ，當(dāng)其鄰居節(jié)點(diǎn)的路由緩存中都有到該目的節(jié)點(diǎn)的路由時，每個鄰居節(jié)點(diǎn)都試圖以自己緩存的路由響應(yīng)，由此造成RREP風(fēng)暴RREP風(fēng)暴將浪費(fèi)網(wǎng)絡(luò)帶寬，并且加劇消息沖突ABCDEF(B-A)