AdHoc網(wǎng)絡路由PPT學習教案

1、會計學1AdHoc網(wǎng)絡路由網(wǎng)絡路由第1頁/共82頁l 無線局域網(wǎng) 移動終端通過無線接入點接入Internet依賴于基站、無線接入點等現(xiàn)有基礎設施網(wǎng)絡第2頁/共82頁施而希望保持與施而希望保持與網(wǎng)絡的連接網(wǎng)絡的連接無網(wǎng)絡基礎設施可用不想使用網(wǎng)絡設施網(wǎng)絡基礎設施范圍外自組織網(wǎng)絡第3頁/共82頁DARPA資助Defense Advanced Research Project Agency第4頁/共82頁ClosedAd Hoc：For the specific purpose onlyMANET：Mobile Ad-hoc NetworksANS：Ad Hoc Networks Scalabilit

2、y第5頁/共82頁多跳無線網(wǎng)絡、自組織網(wǎng)絡、無固定設施的網(wǎng)絡或者對等網(wǎng)絡第6頁/共82頁節(jié)點之間通過無線連接形成的網(wǎng)絡拓撲結構隨時可能發(fā)生變化，而且變化的方式和速度可能都是無法預測的第7頁/共82頁自組織網(wǎng)絡的覆蓋自組織網(wǎng)絡的覆蓋范圍范圍第8頁/共82頁第9頁/共82頁p與一般Ad Hoc網(wǎng)絡相比：p節(jié)點數(shù)量多、分布稠密p節(jié)點的能量、計算、存儲等資源進一步受限第10頁/共82頁主要研究集中在物理層和數(shù)據(jù)鏈路層移動終端的所有通信必須經(jīng)過無線接入點進行無線局域網(wǎng)為單跳網(wǎng)絡，不存在路由問題Ad Hoc網(wǎng)絡的研究內(nèi)容主要以路由協(xié)議為核心的網(wǎng)絡層設計Ad Hoc網(wǎng)絡中移動終端的通信是對等的第11頁/共8

3、2頁MANET移動IP第12頁/共82頁RTS/CTS，CSMA/CA網(wǎng)絡路由時需考慮第13頁/共82頁第14頁/共82頁p感知網(wǎng)絡拓撲結構的變化p維護網(wǎng)絡拓撲的連接p高度自適應性p能量、服務質(zhì)量等約束p信道接入技術p節(jié)能機制p多個Ad Hoc網(wǎng)絡互聯(lián)pAd Hoc內(nèi)部節(jié)點訪問Internet第15頁/共82頁第16頁/共82頁第17頁/共82頁平面結構層次結構第18頁/共82頁平面結構平面結構層次結構層次結構完全分布式的網(wǎng)絡完全分布式的網(wǎng)絡多個簇組成的網(wǎng)絡多個簇組成的網(wǎng)絡所有節(jié)點的地位是平等的所有節(jié)點的地位是平等的節(jié)點被分為簇首和簇成員，簇首預先指定或節(jié)點被分為簇首和簇成員，簇首預先指定或者

4、由選擇算法產(chǎn)生者由選擇算法產(chǎn)生不存在網(wǎng)絡瓶頸，可存在多條路徑，網(wǎng)絡健不存在網(wǎng)絡瓶頸，可存在多條路徑，網(wǎng)絡健壯性好壯性好簇首節(jié)點可能成為網(wǎng)絡瓶頸，所有到簇外的簇首節(jié)點可能成為網(wǎng)絡瓶頸，所有到簇外的通信必須通過簇首節(jié)點進行通信必須通過簇首節(jié)點進行可擴展性差，每個節(jié)點都需要知道到達所有可擴展性差，每個節(jié)點都需要知道到達所有其它節(jié)點的路由，適用于中小規(guī)模的網(wǎng)絡其它節(jié)點的路由，適用于中小規(guī)模的網(wǎng)絡可擴展性好，簇內(nèi)路由信息局部化，適用于可擴展性好，簇內(nèi)路由信息局部化，適用于大規(guī)模網(wǎng)絡大規(guī)模網(wǎng)絡第19頁/共82頁可選功能第20頁/共82頁第21頁/共82頁第22頁/共82頁多跳路由移動第23頁/共82頁第2

5、4頁/共82頁第25頁/共82頁p適應網(wǎng)絡動態(tài)變化p減少路由開銷p引入按需路由p在路由時考慮能量等約束條件第26頁/共82頁Ad Hoc路由協(xié)議表驅動路由先應式(Proactive)按需路由反應式(Reactive)ZRPDSDVTBRPFCGSROLSRLMRABRDSRAODVTORASSRDYMOpOLSR: Optimized Link State RoutingpTBRPF: Topology Dissemination Based on Reverse-Path ForwardingpAODV: Ad Hoc On Demand Distance VectorpDSR: Dynam

6、ic Source Routing DTMO: Dynamic MANET On-demand Routing第27頁/共82頁第28頁/共82頁路由延時小，但是路由開銷大第29頁/共82頁路由延時大，但是路由開銷小第30頁/共82頁p減少了域內(nèi)的路由延時p減少了域外的路由開銷p區(qū)域半徑的選擇p小: 節(jié)點移動快的密集網(wǎng)絡p大: 節(jié)點移動慢的稀疏網(wǎng)絡第31頁/共82頁路由協(xié)議的性能在不同環(huán)境表現(xiàn)不同,因此需要根據(jù)環(huán)境特點使用不同的路由協(xié)議第32頁/共82頁第33頁/共82頁第34頁/共82頁DV: Distance Vector 第35頁/共82頁ABCDest.NextMetricAA0BB3

7、C-32Dest.NextMetricBB0AA3CC2 2Dest.NextMetricCC0BB2A-l 路由更新ABCDest.NextMetricAA0BB3CB5 532Dest.NextMetricBB0AA3CC2 2Dest.NextMetrictCC0BB2AB5 5路由更新消息第36頁/共82頁ABC32Dest.NextMetricBB0AA3CC2 2Dest.NextMetricCC0BB2AB5 5Dest.NextMetricBB0 0AACC2 2Dest.NextMetricBB0AC7CC2 2Dest.NextMetricCC0BB2AB9 9無窮計數(shù)！第

8、37頁/共82頁無法發(fā)現(xiàn)路由循環(huán)限制了網(wǎng)絡的可擴展性對兩個節(jié)點的路由循環(huán)有效，更大的路由循環(huán)需要更強的措施第38頁/共82頁DSDV: Destination-Sequenced Distance Vector 第39頁/共82頁Dest.MetricNextSeq. NrInstall TimeStable DataAA0A-550001000Ptr_ABB1B-102001200Ptr_BCB3C-588001200Ptr-CDB4D-312001200Ptr_D對于同一個目的地，節(jié)點可能接收到來自其它節(jié)點的多條路由信息，settling time定義為第一條路由和最佳路由之間的時間間隔第

9、40頁/共82頁第41頁/共82頁第42頁/共82頁Dest. Next Metric SeqAA1A-550BB0B-100C C1C-588Dest. Next Metric SeqAA0A-550BB1B-100C B2C-588Dest. Next Metric Seq.AB2A-550BB1B-100C C0C-588ABC第43頁/共82頁B遞增序列號 100 - 102B向鄰居A、C廣播路由信息，其中包含有目的地序列號Dest. Next Metric SeqAA0A-550BB1B-100C B2C-588Dest. Next Metric SeqAA1A-550BB0B-10

10、2C C1C-588Dest. Next Metric Seq.AB2A-550BB1B-100C C0C-588ABC第44頁/共82頁Dest. Next Metric SeqAA0A-550BB1B-102C B2C-588Dest. Next Metric SeqAA1A-550BB0B-102C C1C-588Dest. Next Metric Seq.AB2A-550BB1B-102C C0C-588ABC第45頁/共82頁第46頁/共82頁Dest. Next Metric Seq.AA0A-550BB1B-104C B2C-590Dest. Next Metric Seq.AA

11、1A-550BB0B-104CC1C-590Dest. Next Metric Seq.AB2A-550BB1B-104CC0C-5901. D第一次廣播, 發(fā)送序列號D-000ABCD第47頁/共82頁Dest. Next Metric Seq.AB2A-550BB1B-104CC0C-590DD1D-0002. 插入到D的表項，序列號為D-000Dest. Next Metric Seq.AA0A-550BB1B-104C B2C-590Dest. Next Metric Seq.AA1A-550BB0B-104CC1C-590ABCD第48頁/共82頁C, 0, C-592)Dest.

12、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-590ABCD第49頁/共82頁4. B獲取新的路由信息并且更新路由表Dest. Next Metric Seq.AC3A-550BC2B-104CC1C-592DD0D-000D從C獲取路由表信息并且生成自己的路由表ABCDDest. Next Metric

13、 Seq.AB2A-550BB1B-104CC0C-592DD1D-000Dest. Next Metric Seq.AA0A-550BB1B-104C B2C-590Dest. Next Metric Seq.AA1A-550BB0B-104CC1C-592第50頁/共82頁Dest. Next Metric Seq.DC2D-100Dest. Next Metric Seq.DB3D-100Dest. Next Metric Seq.DD1D-100因為B廣播的到達D的路由信息中的序列號小于C維護的D的序列號，因此C認為B的廣播的是過期路由信息，不予采納1. C檢測到鏈路斷開-序列號遞增1

14、(當且僅當這種情況不是目的節(jié)點設置序列號-奇數(shù)序列號)2. B廣播到達D的路由信息ABCD避免了循環(huán)避免了計數(shù)到無窮DD D-101第51頁/共82頁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-101)DB D-101DC D-101第52頁/共82頁2. A收到來自P的路由更

15、新消息10 Hops11 HopsAPQDDest. Next Metric Seq.DQ14D-100DP15D-1021. D公告序列號為D-102的路由更新路由表中到D的表項立即進行路由公告3. A收到來自Q的路由更新消息DQ14D-102更新路由表中到D的表項立即進行路由公告由于D或者任何一個節(jié)點的路由更新消息到達節(jié)點A時存在著時間差,就會導致不必要的路由公告路由表波動第53頁/共82頁10 Hops11 HopsAPQD可緩解大型網(wǎng)絡的路由波動問題，從而避免不必要的公告，節(jié)約了帶寬第54頁/共82頁第55頁/共82頁RFC3626第56頁/共82頁RFC3684第57頁/共82頁第5

16、8頁/共82頁第59頁/共82頁路由發(fā)現(xiàn)和路由維護都是按需進行的p不需要周期性路由公告p不需要感知鏈路狀態(tài)p不需要鄰居檢測第60頁/共82頁ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)第61頁/共82頁ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)丟棄F轉發(fā)的RREQ第62頁/共82頁(A-B-C-D)ABCDEF(A-B-C-D)(A-B-C-D)第63頁/共82頁第64頁/共82頁第65頁/共82頁ABCDEF(A-B-C-E-)Route Error第66頁/共82頁(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-)以上均假設信道是對稱的!第67頁/共82頁ABCDEF(B-C-D)(A-B-C-D)(A-)第68頁/共82頁設置緩存路由的有效期，