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

1、自組織網(wǎng)絡(luò)路由協(xié)議自組織網(wǎng)絡(luò)路由協(xié)議課程主要內(nèi)容課程主要內(nèi)容l概述概述l體系結(jié)構(gòu)體系結(jié)構(gòu)lAd Hoc網(wǎng)絡(luò)路由網(wǎng)絡(luò)路由內(nèi)容提要內(nèi)容提要l概述概述l體系結(jié)構(gòu)體系結(jié)構(gòu)lAd Hoc網(wǎng)絡(luò)路由網(wǎng)絡(luò)路由基于預(yù)先架設(shè)網(wǎng)絡(luò)基礎(chǔ)設(shè)施的無線網(wǎng)絡(luò)基于預(yù)先架設(shè)網(wǎng)絡(luò)基礎(chǔ)設(shè)施的無線網(wǎng)絡(luò)l 蜂窩網(wǎng)絡(luò)蜂窩網(wǎng)絡(luò) 移動終端通過基站接入移動終端通過基站接入移動通信網(wǎng)絡(luò)移動通信網(wǎng)絡(luò)l 無線局域網(wǎng)無線局域網(wǎng) 移動終端通過無線接入移動終端通過無線接入點接入點接入Internet依賴于基站、無線接入點等現(xiàn)有基礎(chǔ)設(shè)施網(wǎng)絡(luò)依賴于基站、無線接入點等現(xiàn)有基礎(chǔ)設(shè)施網(wǎng)絡(luò)自組織網(wǎng)絡(luò)的應(yīng)用需求自組織網(wǎng)絡(luò)的應(yīng)用需求l臨時會議臨時會議/緊急情況緊急情況l科

2、學(xué)考察科學(xué)考察/探險探險/軍事戰(zhàn)軍事戰(zhàn)場場l接入網(wǎng)絡(luò)服務(wù)商所需的接入網(wǎng)絡(luò)服務(wù)商所需的時間和成本時間和成本l現(xiàn)有服務(wù)和架構(gòu)的性能現(xiàn)有服務(wù)和架構(gòu)的性能或者能力或者能力l遠(yuǎn)離網(wǎng)絡(luò)基礎(chǔ)設(shè)施而希遠(yuǎn)離網(wǎng)絡(luò)基礎(chǔ)設(shè)施而希望保持與網(wǎng)絡(luò)的連接望保持與網(wǎng)絡(luò)的連接無網(wǎng)絡(luò)基礎(chǔ)設(shè)施可用無網(wǎng)絡(luò)基礎(chǔ)設(shè)施可用不想使用網(wǎng)絡(luò)設(shè)施不想使用網(wǎng)絡(luò)設(shè)施網(wǎng)絡(luò)基礎(chǔ)設(shè)施范圍外網(wǎng)絡(luò)基礎(chǔ)設(shè)施范圍外自自組組織織網(wǎng)網(wǎng)絡(luò)絡(luò)自組織網(wǎng)的起源自組織網(wǎng)的起源l 1972年分組無線網(wǎng)（年分組無線網(wǎng)（PRNET）戰(zhàn)場環(huán)境下的數(shù)據(jù)通信戰(zhàn)場環(huán)境下的數(shù)據(jù)通信l 1983年抗毀自適應(yīng)網(wǎng)絡(luò)（年抗毀自適應(yīng)網(wǎng)絡(luò)（SURAN）支持大規(guī)模網(wǎng)絡(luò)支持大規(guī)模網(wǎng)絡(luò)適應(yīng)戰(zhàn)場快速變化環(huán)境需要的自

3、適應(yīng)網(wǎng)適應(yīng)戰(zhàn)場快速變化環(huán)境需要的自適應(yīng)網(wǎng)絡(luò)協(xié)議絡(luò)協(xié)議l 1994年全球移動通信系統(tǒng)（年全球移動通信系統(tǒng)（GloMo）滿足軍事應(yīng)用需要的、可快速展開、高滿足軍事應(yīng)用需要的、可快速展開、高抗毀星的移動信息系統(tǒng)抗毀星的移動信息系統(tǒng)DARPA資助資助Defense Advanced Research Project Agency自組織網(wǎng)絡(luò)研究自組織網(wǎng)絡(luò)研究l1991年年IEEE 802.11首次提出首次提出“Ad Hoc網(wǎng)絡(luò)網(wǎng)絡(luò)”自組織、對等式、多跳無線移動通信網(wǎng)絡(luò)自組織、對等式、多跳無線移動通信網(wǎng)絡(luò)l1997年年IETF成立成立MANET工作組工作組基于基于IP的無線多跳網(wǎng)絡(luò)路由的無線多跳網(wǎng)絡(luò)路由l

4、2003年年IRTF成立成立ANS研究組研究組l其它研究機(jī)構(gòu)其它研究機(jī)構(gòu)ClosedAd Hoc：For the specific purpose onlyMANET：Mobile Ad-hoc NetworksANS：Ad Hoc Networks ScalabilityAd Hoc網(wǎng)絡(luò)的定義網(wǎng)絡(luò)的定義l 由一組帶有無線通信收發(fā)裝置的由一組帶有無線通信收發(fā)裝置的(移動移動)終端節(jié)點終端節(jié)點組成的一個多跳臨時性自治系統(tǒng)組成的一個多跳臨時性自治系統(tǒng)l 每個每個(移動移動)終端同時具有路由器和主機(jī)兩種功能：終端同時具有路由器和主機(jī)兩種功能：作為主機(jī)，終端需要運(yùn)行面向用戶的應(yīng)用程序；作為主機(jī)，終端需

5、要運(yùn)行面向用戶的應(yīng)用程序；作為路由器，終端需要運(yùn)行相應(yīng)的路由協(xié)議作為路由器，終端需要運(yùn)行相應(yīng)的路由協(xié)議l 節(jié)點間路由通常由多跳節(jié)點間路由通常由多跳(Hop)組成組成l 不需要網(wǎng)絡(luò)基礎(chǔ)設(shè)施，可以在任何地方、任何地不需要網(wǎng)絡(luò)基礎(chǔ)設(shè)施，可以在任何地方、任何地點快速構(gòu)建點快速構(gòu)建多跳無線網(wǎng)絡(luò)、自組織網(wǎng)絡(luò)、無固定設(shè)施的網(wǎng)絡(luò)或者對等網(wǎng)絡(luò)多跳無線網(wǎng)絡(luò)、自組織網(wǎng)絡(luò)、無固定設(shè)施的網(wǎng)絡(luò)或者對等網(wǎng)絡(luò)Ad Hoc網(wǎng)絡(luò)的特點（網(wǎng)絡(luò)的特點（1）l獨立組網(wǎng)獨立組網(wǎng)不需要任何預(yù)先網(wǎng)絡(luò)基礎(chǔ)設(shè)施不需要任何預(yù)先網(wǎng)絡(luò)基礎(chǔ)設(shè)施l動態(tài)拓?fù)鋭討B(tài)拓?fù)涔?jié)點移動節(jié)點移動/開機(jī)開機(jī)/關(guān)機(jī)關(guān)機(jī)節(jié)點無線發(fā)送功率變化、無線信道干擾或者地形節(jié)點無線發(fā)送功

6、率變化、無線信道干擾或者地形等因素影響等因素影響l自組織自組織無控制中心無控制中心節(jié)點故障不會影響到整個網(wǎng)絡(luò)節(jié)點故障不會影響到整個網(wǎng)絡(luò)節(jié)點之間通過無線連接形成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨時可能節(jié)點之間通過無線連接形成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨時可能發(fā)生變化，而且變化的方式和速度可能都是無法預(yù)測的發(fā)生變化，而且變化的方式和速度可能都是無法預(yù)測的Ad Hoc網(wǎng)絡(luò)的特點（網(wǎng)絡(luò)的特點（2）l多跳路由多跳路由接收端和發(fā)送端可使用比兩接收端和發(fā)送端可使用比兩者直接通信小得多的功率進(jìn)者直接通信小得多的功率進(jìn)行通信，因此節(jié)省了能量消行通信，因此節(jié)省了能量消耗耗通過中間節(jié)點參與分組轉(zhuǎn)發(fā)，通過中間節(jié)點參與分組轉(zhuǎn)發(fā)，能夠有效降低對無線傳

7、輸設(shè)能夠有效降低對無線傳輸設(shè)備的設(shè)計難度和成本，同時備的設(shè)計難度和成本，同時擴(kuò)大了自組織網(wǎng)絡(luò)的覆蓋范擴(kuò)大了自組織網(wǎng)絡(luò)的覆蓋范圍圍Ad Hoc網(wǎng)絡(luò)的特點（網(wǎng)絡(luò)的特點（3）l 特殊的無線信道特征特殊的無線信道特征無線信道提供的網(wǎng)絡(luò)帶寬比有線信道低得多無線信道提供的網(wǎng)絡(luò)帶寬比有線信道低得多競爭無線共享信道產(chǎn)生碰撞競爭無線共享信道產(chǎn)生碰撞信號衰落、噪聲干擾以及信道之間的干擾等信號衰落、噪聲干擾以及信道之間的干擾等l 終端的局限性終端的局限性能量、存儲、計算等資源受限能量、存儲、計算等資源受限l 安全性差安全性差無線鏈路的開放性無線鏈路的開放性移動性導(dǎo)致節(jié)點之間信任關(guān)系的變化移動性導(dǎo)致節(jié)點之間信任關(guān)系的

8、變化l 可擴(kuò)展性不強(qiáng)可擴(kuò)展性不強(qiáng)節(jié)點之間的相互干擾造成網(wǎng)絡(luò)容量下降節(jié)點之間的相互干擾造成網(wǎng)絡(luò)容量下降各節(jié)點吞吐量隨網(wǎng)絡(luò)節(jié)點總數(shù)的增加而下降各節(jié)點吞吐量隨網(wǎng)絡(luò)節(jié)點總數(shù)的增加而下降l 存在單向無線信道存在單向無線信道終端發(fā)射功率的不同及地形環(huán)境的影響終端發(fā)射功率的不同及地形環(huán)境的影響Ad Hoc網(wǎng)絡(luò)與網(wǎng)絡(luò)與Sensor網(wǎng)絡(luò)網(wǎng)絡(luò)lSensor網(wǎng)絡(luò)網(wǎng)絡(luò)可以看作是一種特殊類型的可以看作是一種特殊類型的Ad Hoc網(wǎng)絡(luò)網(wǎng)絡(luò)各個無線節(jié)點靜態(tài)地隨機(jī)分布在某一區(qū)域。傳感各個無線節(jié)點靜態(tài)地隨機(jī)分布在某一區(qū)域。傳感器負(fù)責(zé)收集區(qū)域內(nèi)的傳感信號，將它們發(fā)到網(wǎng)關(guān)器負(fù)責(zé)收集區(qū)域內(nèi)的傳感信號，將它們發(fā)到網(wǎng)關(guān)節(jié)點節(jié)點網(wǎng)關(guān)具有更

9、大的處理能力，能進(jìn)一步處理信息，網(wǎng)關(guān)具有更大的處理能力，能進(jìn)一步處理信息，并且具有更大的發(fā)送范圍，可將信息送往某個大并且具有更大的發(fā)送范圍，可將信息送往某個大型網(wǎng)絡(luò)（型網(wǎng)絡(luò)（Internet）并且到達(dá)最終的用戶）并且到達(dá)最終的用戶p與一般與一般Ad Hoc網(wǎng)絡(luò)相比：網(wǎng)絡(luò)相比：p節(jié)點數(shù)量多、分布稠密節(jié)點數(shù)量多、分布稠密p節(jié)點的能量、計算、存儲等資源進(jìn)一步受限節(jié)點的能量、計算、存儲等資源進(jìn)一步受限Ad Hoc網(wǎng)絡(luò)與無線局域網(wǎng)網(wǎng)絡(luò)與無線局域網(wǎng)l單跳與多跳單跳與多跳l研究重點不同研究重點不同l通信模式不同通信模式不同主要研究集中在物主要研究集中在物理層和數(shù)據(jù)鏈路層理層和數(shù)據(jù)鏈路層移動終端的所有通信必移

10、動終端的所有通信必須經(jīng)過無線接入點進(jìn)行須經(jīng)過無線接入點進(jìn)行無線局域網(wǎng)為單跳網(wǎng)無線局域網(wǎng)為單跳網(wǎng)絡(luò)，不存在路由問題絡(luò)，不存在路由問題Ad Hoc網(wǎng)絡(luò)的研究網(wǎng)絡(luò)的研究內(nèi)容主要以路由協(xié)議內(nèi)容主要以路由協(xié)議為核心的網(wǎng)絡(luò)層設(shè)計為核心的網(wǎng)絡(luò)層設(shè)計Ad Hoc網(wǎng)絡(luò)中移動網(wǎng)絡(luò)中移動終端的通信是對等的終端的通信是對等的移動移動Ad Hoc網(wǎng)絡(luò)網(wǎng)絡(luò)(MANET)與移動與移動IPMANET移動移動IPAd Hoc網(wǎng)絡(luò)所面臨的問題網(wǎng)絡(luò)所面臨的問題(1)l 特殊的信道共享方式特殊的信道共享方式 共享信道共享信道 隱藏節(jié)點問題隱藏節(jié)點問題/暴露節(jié)點問題暴露節(jié)點問題l 動態(tài)變化網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化網(wǎng)絡(luò)拓?fù)?傳統(tǒng)路由協(xié)議花較高代

11、價獲取的路由信息可能已經(jīng)陳舊傳統(tǒng)路由協(xié)議花較高代價獲取的路由信息可能已經(jīng)陳舊l 有限的無線傳輸帶寬有限的無線傳輸帶寬 減少節(jié)點之間的交換的消息減少節(jié)點之間的交換的消息 減少控制消息帶來的額外開銷減少控制消息帶來的額外開銷l 有限的能量有限的能量 能量管理機(jī)制，各層考慮能量控制，包括網(wǎng)絡(luò)層路由能量管理機(jī)制，各層考慮能量控制，包括網(wǎng)絡(luò)層路由l 安全問題安全問題 無線信道的開放性更容易受到各種攻擊無線信道的開放性更容易受到各種攻擊 移動性使得節(jié)點的信任關(guān)系不斷變化移動性使得節(jié)點的信任關(guān)系不斷變化 由于節(jié)點資源受限，安全機(jī)制應(yīng)該是分布式的由于節(jié)點資源受限，安全機(jī)制應(yīng)該是分布式的RTS/CTS，CSMA

12、/CA網(wǎng)絡(luò)路由時需考慮網(wǎng)絡(luò)路由時需考慮Ad Hoc網(wǎng)絡(luò)所面臨的問題網(wǎng)絡(luò)所面臨的問題(2)l網(wǎng)絡(luò)管理網(wǎng)絡(luò)管理拓?fù)涔芾硗負(fù)涔芾韑確定將一組節(jié)點組織成網(wǎng)絡(luò)的機(jī)制確定將一組節(jié)點組織成網(wǎng)絡(luò)的機(jī)制移動性管理移動性管理l跟蹤網(wǎng)絡(luò)中移動節(jié)點的位置跟蹤網(wǎng)絡(luò)中移動節(jié)點的位置服務(wù)質(zhì)量管理服務(wù)質(zhì)量管理l多跳拓?fù)鋭討B(tài)變化的移動多跳拓?fù)鋭討B(tài)變化的移動Ad Hoc網(wǎng)絡(luò)使得服務(wù)質(zhì)量保網(wǎng)絡(luò)使得服務(wù)質(zhì)量保證更加困難證更加困難自動配置自動配置實現(xiàn)實現(xiàn)Ad Hoc網(wǎng)絡(luò)的關(guān)鍵技術(shù)網(wǎng)絡(luò)的關(guān)鍵技術(shù)l路由協(xié)議路由協(xié)議l服務(wù)質(zhì)量管理服務(wù)質(zhì)量管理l功率控制功率控制l傳輸層性能傳輸層性能lAd Hoc網(wǎng)絡(luò)互聯(lián)網(wǎng)絡(luò)互聯(lián)l安全問題安全問題l網(wǎng)絡(luò)管理網(wǎng)

13、絡(luò)管理p感知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化感知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化p維護(hù)網(wǎng)絡(luò)拓?fù)涞倪B接維護(hù)網(wǎng)絡(luò)拓?fù)涞倪B接p高度自適應(yīng)性高度自適應(yīng)性p能量、服務(wù)質(zhì)量等約束能量、服務(wù)質(zhì)量等約束p信道接入技術(shù)信道接入技術(shù)p節(jié)能機(jī)制節(jié)能機(jī)制p多個多個Ad Hoc網(wǎng)絡(luò)互聯(lián)網(wǎng)絡(luò)互聯(lián)pAd Hoc內(nèi)部節(jié)點訪問內(nèi)部節(jié)點訪問Internet內(nèi)容內(nèi)容l概述概述l體系結(jié)構(gòu)體系結(jié)構(gòu)lAd Hoc網(wǎng)絡(luò)路由網(wǎng)絡(luò)路由節(jié)點結(jié)構(gòu)節(jié)點結(jié)構(gòu)l主機(jī)：運(yùn)行應(yīng)用程序，完成數(shù)據(jù)處理等功主機(jī)：運(yùn)行應(yīng)用程序，完成數(shù)據(jù)處理等功能能l路由器：運(yùn)行路由協(xié)議，完成路由選擇、路由器：運(yùn)行路由協(xié)議，完成路由選擇、轉(zhuǎn)發(fā)分組等功能轉(zhuǎn)發(fā)分組等功能l無線收發(fā)裝置：完成數(shù)據(jù)傳輸功能無線收發(fā)裝置

14、：完成數(shù)據(jù)傳輸功能網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)l 平面結(jié)構(gòu)平面結(jié)構(gòu)所有節(jié)點地位平等所有節(jié)點地位平等l 層次結(jié)構(gòu)層次結(jié)構(gòu)網(wǎng)絡(luò)被劃分為簇（網(wǎng)絡(luò)被劃分為簇（Cluster）每個簇由簇首節(jié)點每個簇由簇首節(jié)點(Cluster Head)和簇成員和簇成員節(jié)點節(jié)點(Cluster Member)構(gòu)構(gòu)成成簇首節(jié)點可形成更高一級簇首節(jié)點可形成更高一級的網(wǎng)絡(luò)的網(wǎng)絡(luò)平面結(jié)構(gòu)平面結(jié)構(gòu)層次結(jié)構(gòu)層次結(jié)構(gòu)平面結(jié)構(gòu)和層次結(jié)構(gòu)比較平面結(jié)構(gòu)和層次結(jié)構(gòu)比較平面結(jié)構(gòu)平面結(jié)構(gòu)層次結(jié)構(gòu)層次結(jié)構(gòu)完全分布式的網(wǎng)絡(luò)完全分布式的網(wǎng)絡(luò)多個簇組成的網(wǎng)絡(luò)多個簇組成的網(wǎng)絡(luò)所有節(jié)點的地位是平等的所有節(jié)點的地位是平等的節(jié)點被分為簇首和簇成員，簇首預(yù)先指定或節(jié)點被分為簇

15、首和簇成員，簇首預(yù)先指定或者由選擇算法產(chǎn)生者由選擇算法產(chǎn)生不存在網(wǎng)絡(luò)瓶頸，可存在多條路徑，網(wǎng)絡(luò)健不存在網(wǎng)絡(luò)瓶頸，可存在多條路徑，網(wǎng)絡(luò)健壯性好壯性好簇首節(jié)點可能成為網(wǎng)絡(luò)瓶頸，所有到簇外的簇首節(jié)點可能成為網(wǎng)絡(luò)瓶頸，所有到簇外的通信必須通過簇首節(jié)點進(jìn)行通信必須通過簇首節(jié)點進(jìn)行可擴(kuò)展性差，每個節(jié)點都需要知道到達(dá)所有可擴(kuò)展性差，每個節(jié)點都需要知道到達(dá)所有其它節(jié)點的路由，適用于中小規(guī)模的網(wǎng)絡(luò)其它節(jié)點的路由，適用于中小規(guī)模的網(wǎng)絡(luò)可擴(kuò)展性好，簇內(nèi)路由信息局部化，適用于可擴(kuò)展性好，簇內(nèi)路由信息局部化，適用于大規(guī)模網(wǎng)絡(luò)大規(guī)模網(wǎng)絡(luò)網(wǎng)絡(luò)協(xié)議棧網(wǎng)絡(luò)協(xié)議棧l 基于基于TCP/IP體系體系結(jié)構(gòu)結(jié)構(gòu)l 與與Internet互

16、聯(lián)互聯(lián)l 傳統(tǒng)路由協(xié)議需傳統(tǒng)路由協(xié)議需要修改，以適應(yīng)要修改，以適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化態(tài)變化l 傳輸層實現(xiàn)適應(yīng)傳輸層實現(xiàn)適應(yīng)于無線網(wǎng)絡(luò)的端于無線網(wǎng)絡(luò)的端到端可靠服務(wù)到端可靠服務(wù)l Ad Hoc網(wǎng)絡(luò)多用網(wǎng)絡(luò)多用于能量受限的環(huán)于能量受限的環(huán)境，能量管理尤境，能量管理尤為重要，因此各為重要，因此各層都定義相應(yīng)的層都定義相應(yīng)的節(jié)能機(jī)制節(jié)能機(jī)制可選功能可選功能Ad Hoc網(wǎng)絡(luò)中的跨層設(shè)計網(wǎng)絡(luò)中的跨層設(shè)計l 嚴(yán)格分層的體系結(jié)構(gòu)嚴(yán)格分層的體系結(jié)構(gòu)(OSI參考模型，參考模型，TCP/IP模型模型) 協(xié)議的設(shè)計缺乏足夠的適應(yīng)協(xié)議的設(shè)計缺乏足夠的適應(yīng)性，不能滿足性，不能滿足Ad Hoc網(wǎng)絡(luò)網(wǎng)絡(luò)動態(tài)變

17、化的需求，特別是在動態(tài)變化的需求，特別是在能量或者能量或者QoS等約束條件下等約束條件下l 跨層體系結(jié)構(gòu)跨層體系結(jié)構(gòu)任意層之間能夠進(jìn)行信息交任意層之間能夠進(jìn)行信息交互協(xié)作互協(xié)作l在動態(tài)環(huán)境下，根據(jù)能量或在動態(tài)環(huán)境下，根據(jù)能量或者者QoS等約束條件自適應(yīng)調(diào)等約束條件自適應(yīng)調(diào)節(jié)節(jié)l避免重復(fù)的功能，減少開銷避免重復(fù)的功能，減少開銷l減少反應(yīng)時間，快速適應(yīng)網(wǎng)減少反應(yīng)時間，快速適應(yīng)網(wǎng)絡(luò)動態(tài)變化絡(luò)動態(tài)變化內(nèi)容內(nèi)容l概述概述l體系結(jié)構(gòu)體系結(jié)構(gòu)lAd Hoc網(wǎng)絡(luò)路由網(wǎng)絡(luò)路由Ad Hoc路由概述路由概述l需要進(jìn)行通信的兩個節(jié)點可能不在需要進(jìn)行通信的兩個節(jié)點可能不在相互的無線信號范圍內(nèi)相互的無線信號范圍內(nèi)l需要其

18、它節(jié)點承擔(dān)轉(zhuǎn)發(fā)工作需要其它節(jié)點承擔(dān)轉(zhuǎn)發(fā)工作l節(jié)點移動后需要重新建立新的路由節(jié)點移動后需要重新建立新的路由多跳路由多跳路由移動移動MANET路由面臨的問題路由面臨的問題l 路由信息不易獲得定期交換路由信息或者按需搜索路由的開銷大網(wǎng)絡(luò)資源有限，并且必須被所有節(jié)點共享節(jié)點資源（電池、CPU）等有限也許不能接收到所有的路由信息l 路由信息不完整移動和分區(qū)很難將信息分發(fā)到一個沒有固定成員網(wǎng)絡(luò)的所有節(jié)點l 路由信息可能過期不可能連續(xù)的或者立即交換信息節(jié)點隨時移動無線傳播變化大MANET對路由協(xié)議的需求對路由協(xié)議的需求l 收斂迅速l 提供無環(huán)路由l 避免無窮計算l 控制管理開銷小l 對終端無過高要求l 支持

19、單向信道l 盡量簡單實用l 路由機(jī)制必須適應(yīng)網(wǎng)絡(luò)三個不斷變化的基本特征移動節(jié)點的總體密度節(jié)點到節(jié)點的拓?fù)渚W(wǎng)絡(luò)的使用模式傳統(tǒng)的路由協(xié)議不適用于傳統(tǒng)的路由協(xié)議不適用于Ad Hoc網(wǎng)絡(luò)網(wǎng)絡(luò)l 動態(tài)變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)節(jié)點加入、離開、移動等節(jié)點加入、離開、移動等路由算法還未收斂路由算法還未收斂,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)就發(fā)生變化就發(fā)生變化l 有限的系統(tǒng)帶寬、能量等資源有限的系統(tǒng)帶寬、能量等資源周期性地公告路由信息嚴(yán)重降低周期性地公告路由信息嚴(yán)重降低系統(tǒng)的性能系統(tǒng)的性能l 間歇性的網(wǎng)絡(luò)分割間歇性的網(wǎng)絡(luò)分割傳統(tǒng)路由協(xié)議容易形成路由回路傳統(tǒng)路由協(xié)議容易形成路由回路l 單向的無線傳輸信道單

20、向的無線傳輸信道傳統(tǒng)路由協(xié)議一般假設(shè)鏈路是對傳統(tǒng)路由協(xié)議一般假設(shè)鏈路是對稱的稱的p適應(yīng)網(wǎng)絡(luò)動態(tài)變適應(yīng)網(wǎng)絡(luò)動態(tài)變化化p減少路由開銷減少路由開銷p引入按需路由引入按需路由p在路由時考慮能在路由時考慮能量等約束條件量等約束條件路由協(xié)議路由協(xié)議Ad Hoc路由協(xié)議路由協(xié)議表驅(qū)動路由表驅(qū)動路由先應(yīng)式先應(yīng)式(Proactive)按需路由按需路由反應(yīng)式反應(yīng)式(Reactive)ZRPDSDVTBRPFCGSROLSRLMRABRDSRAODVTORASSRDYMOpOLSR: Optimized Link State RoutingpTBRPF: Topology Dissemination Based o

21、n Reverse-Path ForwardingpAODV: Ad Hoc On Demand Distance VectorpDSR: Dynamic Source Routing DTMO: Dynamic MANET On-demand Routing表驅(qū)動（表驅(qū)動（Table Driven）路由）路由l先應(yīng)式先應(yīng)式(Proactive)路由路由傳統(tǒng)的分布式最短路徑路由協(xié)議傳統(tǒng)的分布式最短路徑路由協(xié)議l鏈路狀態(tài)或者距離向量鏈路狀態(tài)或者距離向量l所有節(jié)點周期性更新所有節(jié)點周期性更新“可達(dá)可達(dá)”信息信息每個節(jié)點維護(hù)到網(wǎng)絡(luò)中所有其它節(jié)點的路由每個節(jié)點維護(hù)到網(wǎng)絡(luò)中所有其它節(jié)點的路由所有路由都已

22、存在并且隨時可用所有路由都已存在并且隨時可用DSDV、OLSR、TBRPF路由延時小，但是路由開銷大路由延時小，但是路由開銷大按需按需(On-demand)路由路由l 反應(yīng)式反應(yīng)式(Reactive)路由路由 源節(jié)點根據(jù)需要通過路由發(fā)現(xiàn)過程來源節(jié)點根據(jù)需要通過路由發(fā)現(xiàn)過程來確定路由確定路由 控制消息采用泛洪（控制消息采用泛洪（Flooding）方式）方式l 兩種實現(xiàn)技術(shù)兩種實現(xiàn)技術(shù) 源路由（分組攜帶完整的路由信息）源路由（分組攜帶完整的路由信息） 逐跳（逐跳（Hop-by-Hop）路由）路由l DSR、AODV、DYMO路由延時大，但是路由開銷小路由延時大，但是路由開銷小混合路由混合路由l A

23、d Hoc網(wǎng)絡(luò)劃分為區(qū)域網(wǎng)絡(luò)劃分為區(qū)域 每個節(jié)點在區(qū)域內(nèi)部采用表驅(qū)動路由每個節(jié)點在區(qū)域內(nèi)部采用表驅(qū)動路由 對于區(qū)域外節(jié)點采用按需路由對于區(qū)域外節(jié)點采用按需路由l 簇和區(qū)域的不同簇和區(qū)域的不同 簇內(nèi)所有節(jié)點都與簇首直接通信，簇內(nèi)節(jié)點間的通信一般是兩跳簇內(nèi)所有節(jié)點都與簇首直接通信，簇內(nèi)節(jié)點間的通信一般是兩跳 區(qū)域的大小沒有限制，區(qū)域內(nèi)的節(jié)點通信可以多跳區(qū)域的大小沒有限制，區(qū)域內(nèi)的節(jié)點通信可以多跳l ZRP：Zone Routing Protocolp減少了域內(nèi)的路由延時減少了域內(nèi)的路由延時p減少了域外的路由開銷減少了域外的路由開銷p區(qū)域半徑的選擇區(qū)域半徑的選擇p小小: 節(jié)點移動快的密集網(wǎng)絡(luò)節(jié)點移動

24、快的密集網(wǎng)絡(luò)p大大: 節(jié)點移動慢的稀疏網(wǎng)絡(luò)節(jié)點移動慢的稀疏網(wǎng)絡(luò)Ad Hoc路由協(xié)議的性能指標(biāo)路由協(xié)議的性能指標(biāo)l 端到端數(shù)據(jù)吞吐量和延時端到端數(shù)據(jù)吞吐量和延時反映了數(shù)據(jù)的傳輸質(zhì)量反映了數(shù)據(jù)的傳輸質(zhì)量l 路由獲取時間路由獲取時間有數(shù)據(jù)要發(fā)送到發(fā)送出去的時間有數(shù)據(jù)要發(fā)送到發(fā)送出去的時間l 亂序分組發(fā)送率亂序分組發(fā)送率衡量無連接路由協(xié)議應(yīng)用于需要有序發(fā)送的傳輸層協(xié)議衡量無連接路由協(xié)議應(yīng)用于需要有序發(fā)送的傳輸層協(xié)議例如例如TCP時的性能時的性能l 路由協(xié)議的效率路由協(xié)議的效率路由控制消息路由控制消息/發(fā)送數(shù)據(jù)發(fā)送數(shù)據(jù)路由協(xié)議的性能在不同環(huán)境表現(xiàn)不同路由協(xié)議的性能在不同環(huán)境表現(xiàn)不同,因此需要根據(jù)環(huán)境特點

25、使用不同的路由協(xié)議因此需要根據(jù)環(huán)境特點使用不同的路由協(xié)議表驅(qū)動（先應(yīng)式）路由協(xié)議表驅(qū)動（先應(yīng)式）路由協(xié)議帶目的地序列號的距離向量協(xié)議帶目的地序列號的距離向量協(xié)議(DSDV)lDestination-Sequenced Distance-VectorDV (Distance Vector)算法算法DSDV協(xié)議協(xié)議DV算法概述算法概述l 基于分布式基于分布式Bellman-Ford算法算法 尋找從源點到某個點的最短路徑尋找從源點到某個點的最短路徑l 每個節(jié)點都維護(hù)一張路由表每個節(jié)點都維護(hù)一張路由表 所有可達(dá)的目的地所有可達(dá)的目的地 到達(dá)目的地的下一跳到達(dá)目的地的下一跳 到達(dá)目的地的到達(dá)目的地的“距

26、離距離”（開銷）（開銷）l 節(jié)點向鄰居節(jié)點發(fā)送路由更新消息節(jié)點向鄰居節(jié)點發(fā)送路由更新消息 定期更新：即使節(jié)點路由表無變化定期更新：即使節(jié)點路由表無變化 觸發(fā)更新：節(jié)點路由表中某條路由發(fā)生變化觸發(fā)更新：節(jié)點路由表中某條路由發(fā)生變化l 路由更新消息包含列表格式路由更新消息包含列表格式 l 節(jié)點在收到節(jié)點在收到“更好更好”路由的情況下更新路由表路由的情況下更新路由表 具有更小的開銷：對于同一個目的地，來自不同的下一跳具有更小的開銷：對于同一個目的地，來自不同的下一跳 更新開銷：對于同一目的地，來自相同的下一跳更新開銷：對于同一目的地，來自相同的下一跳DV: Distance Vector DV算法過

27、程算法過程l初始化初始化ABCDest.NextMetricAA0BB3C-32Dest.NextMetricBB0AA3CC2 2Dest.NextMetricCC0BB2A-l路由更新ABCDest.NextMetricAA0BB3CB5 532Dest.NextMetricBB0AA3CC2 2Dest.NextMetrictCC0BB2AB5 5路由更新消息路由更新消息DV算法中的計數(shù)到無窮問題算法中的計數(shù)到無窮問題ABC32Dest.NextMetricBB0AA3CC2 2Dest.NextMetricCC0BB2AB5 5Dest.NextMetricBB0 0AACC2 2De

28、st.NextMetricBB0AC7CC2 2Dest.NextMetricCC0BB2AB9 9無窮計數(shù)！無窮計數(shù)！DV算法不能直接用于算法不能直接用于Ad Hoc網(wǎng)絡(luò)網(wǎng)絡(luò)l計數(shù)到無窮問題計數(shù)到無窮問題l部分解決方法部分解決方法選擇一個相對較少的數(shù)作為無窮大選擇一個相對較少的數(shù)作為無窮大水平分割水平分割 (split horizon)：當(dāng)一個節(jié)點把路由更：當(dāng)一個節(jié)點把路由更新發(fā)送給相鄰節(jié)點時，它并不把從各個相鄰節(jié)點新發(fā)送給相鄰節(jié)點時，它并不把從各個相鄰節(jié)點處學(xué)到的路由再回送給該節(jié)點處學(xué)到的路由再回送給該節(jié)點無法發(fā)現(xiàn)路由循環(huán)無法發(fā)現(xiàn)路由循環(huán)限制了網(wǎng)絡(luò)的可擴(kuò)展性限制了網(wǎng)絡(luò)的可擴(kuò)展性對兩個節(jié)點的

29、路由循環(huán)有效，更大的路由循環(huán)需要更強(qiáng)的措施對兩個節(jié)點的路由循環(huán)有效，更大的路由循環(huán)需要更強(qiáng)的措施DSDV協(xié)議概述協(xié)議概述l 基于基于DV算法算法 簡單，易于實現(xiàn)簡單，易于實現(xiàn) 需要的存儲空間?。ㄖ豁毢袜従庸?jié)點交換路由信息）需要的存儲空間?。ㄖ豁毢袜従庸?jié)點交換路由信息）l 確保無路由回路確保無路由回路 路由表中的每個表項都帶有目的地序列號（由目的節(jié)點生成）路由表中的每個表項都帶有目的地序列號（由目的節(jié)點生成）l 對拓?fù)渥兓茏鞒隹焖俜磻?yīng)對拓?fù)渥兓茏鞒隹焖俜磻?yīng) 路由表有顯著變化時立即啟動路由公告路由表有顯著變化時立即啟動路由公告(Router Advertisement) 但是等待不穩(wěn)定路由的公

30、告，以減緩路由波動但是等待不穩(wěn)定路由的公告，以減緩路由波動(damping fluctuations)l 先應(yīng)式（表驅(qū)動）路由先應(yīng)式（表驅(qū)動）路由 節(jié)點維護(hù)到所有目的地的路由信息節(jié)點維護(hù)到所有目的地的路由信息 路由信息必須周期性的更新（無休眠節(jié)點）路由信息必須周期性的更新（無休眠節(jié)點） 即使網(wǎng)絡(luò)拓?fù)錈o變化也存在著通信開銷即使網(wǎng)絡(luò)拓?fù)錈o變化也存在著通信開銷 維護(hù)的路由可能從不使用維護(hù)的路由可能從不使用DSDV: Destination-Sequenced Distance Vector DSDV路由表路由表l 序列號（序列號（Sequence number ） 由目的端產(chǎn)生，用來防止出現(xiàn)路由回路

31、，并確保路由信息是最新的由目的端產(chǎn)生，用來防止出現(xiàn)路由回路，并確保路由信息是最新的 格式：格式： Dest_NNNl 加入時間（加入時間（Install Time） 路由表項的創(chuàng)建時間，用來刪除過期表項路由表項的創(chuàng)建時間，用來刪除過期表項l Stable Data 指向一個包含有路由穩(wěn)定狀態(tài)信息的表指向一個包含有路由穩(wěn)定狀態(tài)信息的表l 目的節(jié)點地址目的節(jié)點地址l 最近沉淀時間（最近沉淀時間（last settling time）l 平均沉淀時間平均沉淀時間 (average settling time) 用于緩解網(wǎng)絡(luò)中的路由波動用于緩解網(wǎng)絡(luò)中的路由波動Dest.NextMetricSeq. N

32、rInstall TimeStable DataAA0A-550001000Ptr_ABB1B-102001200Ptr_BCB3C-588001200Ptr-CDB4D-312001200Ptr_D對于同一個目的地，節(jié)點可能接對于同一個目的地，節(jié)點可能接收到來自其它節(jié)點的多條路由信收到來自其它節(jié)點的多條路由信息，息，settling time定義為第一條定義為第一條路由和最佳路由之間的時間間隔路由和最佳路由之間的時間間隔DSDV路由公告路由公告l 向每個鄰居公告自己的路由信息向每個鄰居公告自己的路由信息目的節(jié)點地址目的節(jié)點地址Metric：到目的節(jié)點的開銷，一般為到目的節(jié)點的跳數(shù)：到目的節(jié)點

33、的開銷，一般為到目的節(jié)點的跳數(shù)目的地序列號目的地序列號其它信息（例如硬件地址等）其它信息（例如硬件地址等）l 設(shè)置序列號信息的規(guī)則設(shè)置序列號信息的規(guī)則每次公告增加自己的目的地序列號（只使用偶數(shù)值）每次公告增加自己的目的地序列號（只使用偶數(shù)值）如果一個節(jié)點不再可達(dá)（如果一個節(jié)點不再可達(dá)（timeout）,則將該節(jié)點的序列號則將該節(jié)點的序列號加加1（奇數(shù)序列號），并且設(shè)置（奇數(shù)序列號），并且設(shè)置metric為為DSDV路由選擇路由選擇l將更新信息與自己的路由表比較將更新信息與自己的路由表比較選擇具有更大目的地序列號的路由，這將保證始選擇具有更大目的地序列號的路由，這將保證始終使用來自目的地的最新信

34、息終使用來自目的地的最新信息當(dāng)序列號相等時，選擇具有更好當(dāng)序列號相等時，選擇具有更好metric的路由的路由DSDV協(xié)議操作：更新前路由表協(xié)議操作：更新前路由表Dest. Next Metric SeqAA1A-550BB0B-100C C1C-588Dest. Next Metric SeqAA0A-550BB1B-100C B2C-588Dest. Next Metric Seq.AB2A-550BB1B-100C C0C-588ABCDSDV協(xié)議操作：路由公告協(xié)議操作：路由公告B遞增序列號遞增序列號 100 - 102B向鄰居向鄰居A、C廣播路由信息，廣播路由信息，其中包含有目的地序列號

35、其中包含有目的地序列號Dest. Next Metric SeqAA0A-550BB1B-100C B2C-588Dest. Next Metric SeqAA1A-550BB0B-102C C1C-588Dest. Next Metric Seq.AB2A-550BB1B-100C C0C-588ABCDSDV協(xié)議操作：更新后路由表協(xié)議操作：更新后路由表Dest. Next Metric SeqAA0A-550BB1B-102C B2C-588Dest. Next Metric SeqAA1A-550BB0B-102C C1C-588Dest. Next Metric Seq.AB2A-55

36、0BB1B-102C C0C-588ABC對拓?fù)渥兓姆磻?yīng)對拓?fù)渥兓姆磻?yīng)l立即公告立即公告有關(guān)新路由、鏈路斷開和有關(guān)新路由、鏈路斷開和metric變化的信息立即變化的信息立即傳遞給鄰居節(jié)點傳遞給鄰居節(jié)點l完全完全/增量更新增量更新完全更新：發(fā)送自己路由表中的所有路由信息完全更新：發(fā)送自己路由表中的所有路由信息增量更新：只發(fā)送路由表中那些發(fā)生變化的表項增量更新：只發(fā)送路由表中那些發(fā)生變化的表項（能包含在一個單獨的分組中發(fā)送）（能包含在一個單獨的分組中發(fā)送）DSDV協(xié)議操作：新節(jié)點加入?yún)f(xié)議操作：新節(jié)點加入Dest. Next Metric Seq.AA0A-550BB1B-104C B2C-59

37、0Dest. Next Metric Seq.AA1A-550BB0B-104CC1C-590Dest. Next Metric Seq.AB2A-550BB1B-104CC0C-5901. D第一次廣播第一次廣播, 發(fā)送序列號發(fā)送序列號D-000ABCDDSDV協(xié)議操作：新節(jié)點加入?yún)f(xié)議操作：新節(jié)點加入Dest. Next Metric Seq.AB2A-550BB1B-104CC0C-590DD1D-0002. 插入到插入到D的表項，的表項，序列號為序列號為D-000Dest. Next Metric Seq.AA0A-550BB1B-104C B2C-590Dest. Next Metri

38、c Seq.AA1A-550BB0B-104CC1C-590ABCDDSDV協(xié)議操作：新節(jié)點加入?yún)f(xié)議操作：新節(jié)點加入C, 0, C-592)Dest. Next Metric Seq.AB2A-550BB1B-104CC0C-592DD1D-0003. C遞增自己的序列號到遞增自己的序列號到C-592，然后然后立即廣播立即廣播自己的新路由表自己的新路由表Dest. Next Metric Seq.AA0A-550BB1B-104C B2C-590Dest. Next Metric Seq.AA1A-550BB0B-104CC1C-590ABCDDSDV協(xié)議操作：新節(jié)點加入?yún)f(xié)議操作：新節(jié)點加入4

39、. B獲取新的路由信獲取新的路由信息并且更新路由表息并且更新路由表Dest. Next Metric Seq.AC3A-550BC2B-104CC1C-592DD0D-000D從從C獲取路由表信息并獲取路由表信息并且生成自己的路由表且生成自己的路由表ABCDDest. Next Metric Seq.AB2A-550BB1B-104CC0C-592DD1D-000Dest. Next Metric Seq.AA0A-550BB1B-104C B2C-590Dest. Next Metric Seq.AA1A-550BB0B-104CC1C-592DSDV協(xié)議操作：鏈路斷開協(xié)議操作：鏈路斷開De

40、st. Next Metric Seq.DC2D-100Dest. Next Metric Seq.DB3D-100Dest. Next Metric Seq.DD1D-100因為因為B廣播的到達(dá)廣播的到達(dá)D的路由信息中的序列的路由信息中的序列號小于號小于C維護(hù)的維護(hù)的D的序列號，因此的序列號，因此C認(rèn)為認(rèn)為B的廣播的是過期路由信息，不予采納的廣播的是過期路由信息，不予采納1. C檢測到鏈路斷開檢測到鏈路斷開-序列號遞序列號遞增增1(當(dāng)且僅當(dāng)這種情況不是目的當(dāng)且僅當(dāng)這種情況不是目的節(jié)點設(shè)置序列號節(jié)點設(shè)置序列號-奇數(shù)序列號奇數(shù)序列號)2. B廣播到達(dá)廣播到達(dá)D的路由信息的路由信息ABCD避免了循

41、環(huán)避免了循環(huán)避免了計數(shù)到避免了計數(shù)到無窮無窮DD D-101DSDV協(xié)議操作：立即公告協(xié)議操作：立即公告4. B立即傳送更新消息給立即傳送更新消息給A(更新信息具有更大的序列號，更新信息具有更大的序列號，因此將取代因此將取代A中原有表項中原有表項)3. C立即傳遞更新信息給立即傳遞更新信息給B (更新信息具有更大的序列號，更新信息具有更大的序列號，因此將取代因此將取代B中原有表項中原有表項)ABCDDest. Next Metric Seq.DC2D-100Dest. Next Metric Seq.DB3D-100Dest. Next Metric Seq.DD D-101(D, , D-1

42、01)DB D-101DC D-101DSDV協(xié)議操作：路由波動協(xié)議操作：路由波動2. A收到來自收到來自P的路由更新消的路由更新消息息10 Hops11 HopsAPQDDest. Next Metric Seq.DQ14D-100DP15D-1021. D公告序列號為公告序列號為D-102的的路由路由更新路由表中到更新路由表中到D的表項的表項立即進(jìn)行路由公告立即進(jìn)行路由公告3. A收到來自收到來自Q的路由更新消的路由更新消息息DQ14D-102更新路由表中到更新路由表中到D的表項的表項立即進(jìn)行路由公告立即進(jìn)行路由公告由于由于D或者任何一個節(jié)點的路由更新消息到或者任何一個節(jié)點的路由更新消息到

43、達(dá)節(jié)點達(dá)節(jié)點A時存在著時間差時存在著時間差,就會導(dǎo)致不必要的就會導(dǎo)致不必要的路由公告路由公告路由表波動路由表波動DSDV協(xié)議操作：減緩路由波動協(xié)議操作：減緩路由波動l 在一個單獨的表中記錄每條路在一個單獨的表中記錄每條路由的最近的和平均的由的最近的和平均的Settling Time Settling Time：第一條路由和最第一條路由和最佳路由之間的時間間隔佳路由之間的時間間隔 路由表中的路由表中的stable data指向該表指向該表l A在包含新序列號的第一條路在包含新序列號的第一條路由到達(dá)時更新路由表，但是等由到達(dá)時更新路由表，但是等待一段時間再廣播該條路由待一段時間再廣播該條路由 等待

44、時間等待時間=2*(avg. Setting Time)10 Hops11 HopsAPQD可緩解大型網(wǎng)絡(luò)的路由波動問題，可緩解大型網(wǎng)絡(luò)的路由波動問題，從而避免不必要的公告，節(jié)約了帶寬從而避免不必要的公告，節(jié)約了帶寬DSDV總結(jié)總結(jié)l 優(yōu)點優(yōu)點簡單（基本上與簡單（基本上與DV算法一致）算法一致）通過目的地序列號避免了路由循環(huán)，解決了通過目的地序列號避免了路由循環(huán)，解決了DV算法中的算法中的計數(shù)到無窮問題計數(shù)到無窮問題無路由發(fā)現(xiàn)延時（先應(yīng)式路由）無路由發(fā)現(xiàn)延時（先應(yīng)式路由）l 缺點缺點所有節(jié)點都必須公告路由，因此不支持休眠（不能直接所有節(jié)點都必須公告路由，因此不支持休眠（不能直接用于傳感器網(wǎng)絡(luò)）

45、用于傳感器網(wǎng)絡(luò)）收斂慢（收斂慢（DV路由的特性）路由的特性）開銷大：大部分的路由信息從不使用開銷大：大部分的路由信息從不使用可擴(kuò)展性是一個主要問題（所有先應(yīng)式路由都存在的問可擴(kuò)展性是一個主要問題（所有先應(yīng)式路由都存在的問題）題）優(yōu)化鏈路狀態(tài)路由協(xié)議優(yōu)化鏈路狀態(tài)路由協(xié)議(OLSR)lOptimized Link State Routing Protocol先應(yīng)式的鏈路狀態(tài)路由協(xié)議先應(yīng)式的鏈路狀態(tài)路由協(xié)議基于多點中繼（基于多點中繼（MPR）的概念的優(yōu)化）的概念的優(yōu)化l只有只有MPR轉(zhuǎn)發(fā)廣播消息，減少了消息開銷轉(zhuǎn)發(fā)廣播消息，減少了消息開銷l只有只有MPR產(chǎn)生鏈路狀態(tài)信息，減少了網(wǎng)絡(luò)中廣播消息產(chǎn)生鏈路

46、狀態(tài)信息，減少了網(wǎng)絡(luò)中廣播消息的數(shù)量的數(shù)量lMPR可能選擇只報告它和該可能選擇只報告它和該MPR選舉節(jié)點之間的鏈路，選舉節(jié)點之間的鏈路，因此在網(wǎng)絡(luò)中只散發(fā)部分鏈路狀態(tài)信息因此在網(wǎng)絡(luò)中只散發(fā)部分鏈路狀態(tài)信息RFC3626基于拓?fù)鋸V播的反向路徑轉(zhuǎn)發(fā)基于拓?fù)鋸V播的反向路徑轉(zhuǎn)發(fā)(TBRPF)lTopology Broadcast based on Reverse-Path Forwarding本質(zhì)上是一種鏈路狀態(tài)協(xié)議本質(zhì)上是一種鏈路狀態(tài)協(xié)議協(xié)議組成協(xié)議組成l鄰居發(fā)現(xiàn)模塊鄰居發(fā)現(xiàn)模塊l路由模塊路由模塊與傳統(tǒng)鏈路狀態(tài)協(xié)議的差別與傳統(tǒng)鏈路狀態(tài)協(xié)議的差別l拓?fù)涓孪⒏⊥負(fù)涓孪⒏路由開銷更少路由開銷

47、更少l更適合拓?fù)溲杆僮兓臒o線網(wǎng)絡(luò)更適合拓?fù)溲杆僮兓臒o線網(wǎng)絡(luò)RFC3684按需（反應(yīng)式）路由協(xié)議按需（反應(yīng)式）路由協(xié)議動態(tài)源路由協(xié)議動態(tài)源路由協(xié)議(DSR)lDynamic Source Routing按需路由按需路由l節(jié)點需要發(fā)送數(shù)據(jù)時才進(jìn)行路由發(fā)現(xiàn)過程節(jié)點需要發(fā)送數(shù)據(jù)時才進(jìn)行路由發(fā)現(xiàn)過程l反應(yīng)型路由，僅維護(hù)活躍的路由反應(yīng)型路由，僅維護(hù)活躍的路由源路由源路由l發(fā)送節(jié)點在分組中攜帶到達(dá)目的節(jié)點的路由信息（轉(zhuǎn)發(fā)送節(jié)點在分組中攜帶到達(dá)目的節(jié)點的路由信息（轉(zhuǎn)發(fā)分組的完整的節(jié)點序列）發(fā)分組的完整的節(jié)點序列） 不需要中間節(jié)點維護(hù)路由信息不需要中間節(jié)點維護(hù)路由信息l節(jié)點緩存到目的節(jié)點的多條路由節(jié)點緩存到

48、目的節(jié)點的多條路由 避免了在每次路由中斷時都需要進(jìn)行路由發(fā)現(xiàn)，因此能夠避免了在每次路由中斷時都需要進(jìn)行路由發(fā)現(xiàn)，因此能夠?qū)ν負(fù)渥兓鞒龈斓姆磻?yīng)，對拓?fù)渥兓鞒龈斓姆磻?yīng)，DSR協(xié)議組成協(xié)議組成l 路由發(fā)現(xiàn)（路由發(fā)現(xiàn)（Route Discovery）只有在源節(jié)點需要發(fā)送數(shù)據(jù)時才啟動只有在源節(jié)點需要發(fā)送數(shù)據(jù)時才啟動幫助源節(jié)點獲得到達(dá)目的節(jié)點的路由幫助源節(jié)點獲得到達(dá)目的節(jié)點的路由l 路由維護(hù)（路由維護(hù)（Route Maintenance）在源節(jié)點在給目的節(jié)點發(fā)送數(shù)據(jù)時監(jiān)測當(dāng)前路由的可用在源節(jié)點在給目的節(jié)點發(fā)送數(shù)據(jù)時監(jiān)測當(dāng)前路由的可用情況情況當(dāng)網(wǎng)絡(luò)拓?fù)渥兓瘜?dǎo)致路由故障時切換到另一條路由或者當(dāng)網(wǎng)絡(luò)拓?fù)?/p>

49、變化導(dǎo)致路由故障時切換到另一條路由或者重新發(fā)起路由發(fā)現(xiàn)過程重新發(fā)起路由發(fā)現(xiàn)過程路由發(fā)現(xiàn)和路由維護(hù)都是按需進(jìn)行的路由發(fā)現(xiàn)和路由維護(hù)都是按需進(jìn)行的p不需要周期性路由公告不需要周期性路由公告p不需要感知鏈路狀態(tài)不需要感知鏈路狀態(tài)p不需要鄰居檢測不需要鄰居檢測DSR路由發(fā)現(xiàn)：路由請求路由發(fā)現(xiàn)：路由請求l 源節(jié)點向鄰居節(jié)點廣播路由請求（源節(jié)點向鄰居節(jié)點廣播路由請求（RREQ：Route Request）消息）消息 源節(jié)點地址源節(jié)點地址 目的節(jié)點地址目的節(jié)點地址 路由記錄：記錄從源節(jié)點到目的節(jié)點路由中的中間節(jié)點路由記錄：記錄從源節(jié)點到目的節(jié)點路由中的中間節(jié)點 請求請求IDl 中間節(jié)點接收到中間節(jié)點接收到R

50、REQ后，將自己的地址附在路由記錄中后，將自己的地址附在路由記錄中ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)DSR路由發(fā)現(xiàn)：中間節(jié)點處理路由發(fā)現(xiàn)：中間節(jié)點處理l 中間節(jié)點維護(hù)中間節(jié)點維護(hù)序列對列表序列對列表l 重復(fù)重復(fù)RREQ檢測檢測 如果接收到的如果接收到的RREQ消息中的消息中的存在于本節(jié)存在于本節(jié)點的序列對列表中點的序列對列表中 如果接收到的如果接收到的RREQ消息中的路由記錄中包含本節(jié)點的地址消息中的路由記錄中包含本節(jié)點的地址l 如果檢測到重復(fù)，則中間節(jié)點丟棄該如果檢測到重復(fù)，則中間節(jié)點丟棄該RREQ消息消息ABCDEF(A-

51、)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)丟棄丟棄F轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)的的RREQDSR路由發(fā)現(xiàn)：路由應(yīng)答路由發(fā)現(xiàn)：路由應(yīng)答l目的節(jié)點收到目的節(jié)點收到RREQ后，給源節(jié)點返回路后，給源節(jié)點返回路由應(yīng)答（由應(yīng)答（RREP：Route Reply）消息）消息拷貝拷貝RREQ消息中的路由記錄消息中的路由記錄l源節(jié)點收到源節(jié)點收到RREP后在本地路由緩存中緩存后在本地路由緩存中緩存路由信息路由信息(A-B-C-D)ABCDEF(A-B-C-D)(A-B-C-D)DSR路由發(fā)現(xiàn)：非對稱信道路由發(fā)現(xiàn)：非對稱信道l對稱信道對稱信道目的節(jié)點到源節(jié)點的路由即為源節(jié)點到目的節(jié)點目的

52、節(jié)點到源節(jié)點的路由即為源節(jié)點到目的節(jié)點的反向路由的反向路由l非對稱信道非對稱信道如果目的節(jié)點的路由緩存中有到達(dá)源節(jié)點的路由，如果目的節(jié)點的路由緩存中有到達(dá)源節(jié)點的路由，則直接使用則直接使用否則目的節(jié)點需要發(fā)起到源節(jié)點的路由請求過程，否則目的節(jié)點需要發(fā)起到源節(jié)點的路由請求過程，同時將同時將RREP消息附加在新的消息附加在新的RREQ消息中消息中DSR路由維護(hù)路由維護(hù)l逐跳證實機(jī)制逐跳證實機(jī)制鏈路層鏈路層l確認(rèn)確認(rèn)l被動確認(rèn)（監(jiān)聽其它節(jié)點間的數(shù)據(jù)發(fā)送）被動確認(rèn)（監(jiān)聽其它節(jié)點間的數(shù)據(jù)發(fā)送）其它高層其它高層l要求要求DSR軟件返回確認(rèn)軟件返回確認(rèn)l端到端證實機(jī)制端到端證實機(jī)制無法確定故障發(fā)生的位置無法

53、確定故障發(fā)生的位置DSR逐跳證實機(jī)制逐跳證實機(jī)制l 如果數(shù)據(jù)分組被重發(fā)了最大次數(shù)仍然沒有收到下一跳的確如果數(shù)據(jù)分組被重發(fā)了最大次數(shù)仍然沒有收到下一跳的確認(rèn)，則節(jié)點向源端發(fā)送路由錯誤（認(rèn)，則節(jié)點向源端發(fā)送路由錯誤（Route Error）消息，）消息，并且指明中斷的鏈路并且指明中斷的鏈路l 源端將該路由從路由緩存中刪除源端將該路由從路由緩存中刪除l 如果源端路由緩存中存在另一條到目的節(jié)點的路由則使用如果源端路由緩存中存在另一條到目的節(jié)點的路由則使用該路由重發(fā)分組該路由重發(fā)分組l 否則重新開始路由發(fā)現(xiàn)過程否則重新開始路由發(fā)現(xiàn)過程ABCDEF(A-B-C-E-)Route ErrorDSR優(yōu)化：路由

54、緩存優(yōu)化：路由緩存(1)l 每個節(jié)點緩存它通過任何方式獲得的新路由每個節(jié)點緩存它通過任何方式獲得的新路由 轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)RREQl 獲得從本節(jié)點到獲得從本節(jié)點到RREQ路由記錄中所有節(jié)點的路由，例如路由記錄中所有節(jié)點的路由，例如E轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)RREQ(A-B-C)獲得到到獲得到到A的路由的路由(C-B-A) 轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)RREPl 獲得本節(jié)點到獲得本節(jié)點到RREP路由記錄中所有節(jié)點的路由，例如路由記錄中所有節(jié)點的路由，例如B轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)RREP(A-B-C-D)獲得到獲得到D的路由的路由(C-D) 轉(zhuǎn)發(fā)數(shù)據(jù)分組轉(zhuǎn)發(fā)數(shù)據(jù)分組l 獲得從本節(jié)點到數(shù)據(jù)分組節(jié)點列表中所有節(jié)點的路由，例如獲得從本節(jié)點到數(shù)據(jù)分組節(jié)點列表中所

55、有節(jié)點的路由，例如E轉(zhuǎn)發(fā)數(shù)據(jù)分組轉(zhuǎn)發(fā)數(shù)據(jù)分組(A-B-C)獲得到獲得到A的路由的路由(C-B-A) 監(jiān)聽相鄰節(jié)點發(fā)送的分組監(jiān)聽相鄰節(jié)點發(fā)送的分組l RREQ、RREP、數(shù)據(jù)分組等、數(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è)信道是對稱的以上均假設(shè)信道是對稱的!DSR優(yōu)化：路由緩存優(yōu)化：路由緩存(2)l中間節(jié)點使用緩存的到目的節(jié)點的路由響中間節(jié)點使用緩存的到目的節(jié)點的路由響應(yīng)應(yīng)RREQRREP中的路由記錄中的路由記錄=RREQ中的路由記錄中的路由記錄+緩

56、存緩存的到目的節(jié)點的路由的到目的節(jié)點的路由ABCDEF(B-C-D)(A-B-C-D)(A-)DSR優(yōu)化：路由緩存優(yōu)化：路由緩存(3)l錯誤路由緩存錯誤路由緩存網(wǎng)絡(luò)拓?fù)涞淖兓沟镁彺娴穆酚墒ЬW(wǎng)絡(luò)拓?fù)涞淖兓沟镁彺娴穆酚墒影響和感染其它節(jié)點，使用該路由緩存的路由將不可影響和感染其它節(jié)點，使用該路由緩存的路由將不可用用 當(dāng)節(jié)點根據(jù)路由緩存回應(yīng)當(dāng)節(jié)點根據(jù)路由緩存回應(yīng)RREP時，其它監(jiān)聽到此時，其它監(jiān)聽到此RREP的節(jié)點會更改自己緩存的路由，從而感染錯誤路由緩存的節(jié)點會更改自己緩存的路由，從而感染錯誤路由緩存設(shè)置緩存路由的有效期，過期即刪除設(shè)置緩存路由的有效期，過期即刪除DSR優(yōu)化：路由緩存優(yōu)化

57、：路由緩存(4)lRREP風(fēng)暴風(fēng)暴節(jié)點廣播到某個目的節(jié)點的節(jié)點廣播到某個目的節(jié)點的RREQ，當(dāng)其鄰居節(jié)，當(dāng)其鄰居節(jié)點的路由緩存中都有到該目的節(jié)點的路由時，每點的路由緩存中都有到該目的節(jié)點的路由時，每個鄰居節(jié)點都試圖以自己緩存的路由響應(yīng)，由此個鄰居節(jié)點都試圖以自己緩存的路由響應(yīng)，由此造成造成RREP風(fēng)暴風(fēng)暴RREP風(fēng)暴將浪費網(wǎng)絡(luò)帶寬，并且加劇消息沖突風(fēng)暴將浪費網(wǎng)絡(luò)帶寬，并且加劇消息沖突ABCDEF(B-A)G(C-B-A)(F-A)(E-C-B-A)G發(fā)起到發(fā)起到A的的路由發(fā)現(xiàn)過程路由發(fā)現(xiàn)過程DSR優(yōu)化：路由緩存優(yōu)化：路由緩存(5)l 預(yù)防預(yù)防RREP風(fēng)暴風(fēng)暴每個節(jié)點延時每個節(jié)點延時D發(fā)送發(fā)送R

58、REPD與節(jié)點到目的節(jié)點的跳數(shù)成正比，使得到目的節(jié)點有最與節(jié)點到目的節(jié)點的跳數(shù)成正比，使得到目的節(jié)點有最短路徑的短路徑的RREP最先發(fā)送最先發(fā)送節(jié)點將接口設(shè)置成混雜模式節(jié)點將接口設(shè)置成混雜模式(promiscuous)，監(jiān)聽是否，監(jiān)聽是否存在有比自己更短的到目的節(jié)點的路徑，如果有，則不存在有比自己更短的到目的節(jié)點的路徑，如果有，則不發(fā)送本節(jié)點的發(fā)送本節(jié)點的RREPD=H*（h-1+r）其中其中H是每條鏈路的傳播延時是每條鏈路的傳播延時h是自己返回的路徑長度，即到目的節(jié)點的跳數(shù)是自己返回的路徑長度，即到目的節(jié)點的跳數(shù)r是是0或者或者1DSR總結(jié)總結(jié)l 優(yōu)點優(yōu)點僅在需要通信的節(jié)點間維護(hù)路由，減少了路由維護(hù)開銷僅在需要通信的節(jié)點間維護(hù)路由，減少了路由維護(hù)開銷路由緩存技術(shù)能夠進(jìn)一步減少路由發(fā)現(xiàn)的代價路由緩存技術(shù)能夠進(jìn)一步減少路由發(fā)現(xiàn)的代價通過采用路由緩存技術(shù)，能夠發(fā)現(xiàn)多條到達(dá)目的節(jié)點的通過采用路由緩存技術(shù)，能夠發(fā)現(xiàn)多條到達(dá)目的節(jié)點的路由路由支持非對稱信道支持非對稱信道l 缺點缺點采用源節(jié)點路由，每個數(shù)據(jù)分組頭標(biāo)中都要攜帶路由信采用源節(jié)點路由，每個數(shù)據(jù)分組頭標(biāo)中都要攜帶路由信息，增加了網(wǎng)絡(luò)開銷