AdHoc网络路由学习教案

会计学1AdHoc网络网络(wnglu)路由路由第一页，共82页。第1页/共82页第二页，共82页。l无线局域网l移动(ydng)终端通过无线接入点接入Internet依赖于基站、无线接入点等现有基础设施网络第2页/共82页第三页，共82页。施而希望保持与施而希望保持与网络的连接网络的连接无网络(wnglu)基础设施可用不想使用网络设施网络基础设施范围外自组织网络第3页/共82页第四页，共82页。DARPA资助(zzh)Defense Advanced Research Project Agency第4页/共82页第五页，共82页。ClosedAd Hoc：For the specific purpose onlyMANET：Mobile Ad-hoc NetworksANS：Ad Hoc Networks Scalability第5页/共82页第六页，共82页。多跳无线网络、自组织(zzh)网络、无固定设施的网络或者对等网络第6页/共82页第七页，共82页。n节点之间通过无线连接形成的网络拓扑结构随时可能发生变化，而且变化的方式(fngsh)和速度可能都是无法预测的第7页/共82页第八页，共82页。设备的设计难度和设备的设计难度和成本，同时扩大了成本，同时扩大了自组织网络的覆盖自组织网络的覆盖范围范围第8页/共82页第九页，共82页。第9页/共82页第十页，共82页。p与一般Ad Hoc网络相比：p节点数量多、分布稠密(chum)p节点的能量、计算、存储等资源进一步受限第10页/共82页第十一页，共82页。主要研究集中(jzhng)在物理层和数据链路层移动终端的所有通信必须经过无线接入点进行无线局域网为单跳网络，不存在路由问题Ad Hoc网络的研究内容主要以路由协议为核心的网络层设计Ad Hoc网络中移动终端的通信是对等的第11页/共82页第十二页，共82页。MANET移动(ydng)IP第12页/共82页第十三页，共82页。RTS/CTS，CSMA/CA网络(wnglu)路由时需考虑第13页/共82页第十四页，共82页。第14页/共82页第十五页，共82页。p感知网络拓扑结构的变化p维护网络拓扑的连接p高度自适应性p能量(nngling)、服务质量等约束p信道接入技术p节能机制p多个Ad Hoc网络互联pAd Hoc内部节点访问Internet第15页/共82页第十六页，共82页。第16页/共82页第十七页，共82页。第17页/共82页第十八页，共82页。平面(pngmin)结构层次结构第18页/共82页第十九页，共82页。平面结构平面结构层次结构层次结构完全分布式的网络完全分布式的网络多个簇组成的网络多个簇组成的网络所有节点的地位是平等的所有节点的地位是平等的节点被分为簇首和簇成员，簇首预先指定或节点被分为簇首和簇成员，簇首预先指定或者由选择算法产生者由选择算法产生不存在网络瓶颈，可存在多条路径，网络健不存在网络瓶颈，可存在多条路径，网络健壮性好壮性好簇首节点可能成为网络瓶颈，所有到簇外的簇首节点可能成为网络瓶颈，所有到簇外的通信必须通过簇首节点进行通信必须通过簇首节点进行可扩展性差，每个节点都需要知道到达所有可扩展性差，每个节点都需要知道到达所有其它节点的路由，适用于中小规模的网络其它节点的路由，适用于中小规模的网络可扩展性好，簇内路由信息局部化，适用于可扩展性好，簇内路由信息局部化，适用于大规模网络大规模网络第19页/共82页第二十页，共82页。可选功能(gngnng)第20页/共82页第二十一页，共82页。第21页/共82页第二十二页，共82页。第22页/共82页第二十三页，共82页。多跳路由移动(ydng)第23页/共82页第二十四页，共82页。第24页/共82页第二十五页，共82页。第25页/共82页第二十六页，共82页。p适应(shyng)网络动态变化p减少路由开销p引入按需路由p在路由时考虑能量等约束条件第26页/共82页第二十七页，共82页。Ad Hoc路由协议(xiy)表驱动(q dn)路由先应式(Proactive)按需路由反应式(Reactive)ZRPDSDVTBRPFCGSROLSRLMRABRDSRAODVTORASSRDYMOpOLSR: Optimized Link State RoutingpTBRPF: Topology Dissemination Based on Reverse-Path ForwardingpAODV: Ad Hoc On Demand Distance VectorpDSR: Dynamic Source Routing DTMO: Dynamic MANET On-demand Routing第27页/共82页第二十八页，共82页。第28页/共82页第二十九页，共82页。nDSDV、OLSR、TBRPF路由延时小，但是(dnsh)路由开销大第29页/共82页第三十页，共82页。路由延时大，但是(dnsh)路由开销小第30页/共82页第三十一页，共82页。p减少了域内的路由延时p减少了域外的路由开销p区域半径的选择(xunz)p小: 节点移动快的密集网络p大: 节点移动慢的稀疏网络第31页/共82页第三十二页，共82页。路由协议的性能在不同环境表现不同,因此需要根据环境特点(tdin)使用不同的路由协议第32页/共82页第三十三页，共82页。第33页/共82页第三十四页，共82页。第34页/共82页第三十五页，共82页。DV: Distance Vector 第35页/共82页第三十六页，共82页。ABCDest.NextMetricAA0BB3C-32Dest.NextMetricBB0AA3CC2 2Dest.NextMetricCC0BB2A-l 路由更新(gngxn)ABCDest.NextMetricAA0BB3CB5 532Dest.NextMetricBB0AA3CC2 2Dest.NextMetrictCC0BB2AB5 5路由更新(gngxn)消息第36页/共82页第三十七页，共82页。ABC32Dest.NextMetricBB0AA3CC2 2Dest.NextMetricCC0BB2AB5 5Dest.NextMetricBB0 0AACC2 2Dest.NextMetricBB0AC7CC2 2Dest.NextMetricCC0BB2AB9 9无穷(wqing)计数！第37页/共82页第三十八页，共82页。无法(wf)发现路由循环限制了网络的可扩展性对两个节点的路由循环有效，更大的路由循环需要更强的措施第38页/共82页第三十九页，共82页。DSDV: Destination-Sequenced Distance Vector 第39页/共82页第四十页，共82页。Dest.MetricNextSeq. NrInstall TimeStable DataAA0A-550001000Ptr_ABB1B-102001200Ptr_BCB3C-588001200Ptr-CDB4D-312001200Ptr_D对于同一个目的地，节点可能接收到来自其它节点的多条路由信息(xnx)，settling time定义为第一条路由和最佳路由之间的时间间隔第40页/共82页第四十一页，共82页。第41页/共82页第四十二页，共82页。第42页/共82页第四十三页，共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页第四十四页，共82页。B递增(dzng)序列号 100 - 102B向邻居A、C广播路由信息，其中包含有目的地序列号Dest. Next Metric SeqAA0A-550BB1B-100C B2C-588Dest. Next Metric SeqAA1A-550BB0B-102C C1C-588Dest. Next Metric Seq.AB2A-550BB1B-100C C0C-588ABC第44页/共82页第四十五页，共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页第四十六页，共82页。第46页/共82页第四十七页，共82页。Dest. Next Metric Seq.AA0A-550BB1B-104C B2C-590Dest. Next Metric Seq.AA1A-550BB0B-104CC1C-590Dest. Next Metric Seq.AB2A-550BB1B-104CC0C-5901. D第一次广播(gungb), 发送序列号D-000ABCD第47页/共82页第四十八页，共82页。Dest. Next Metric Seq.AB2A-550BB1B-104CC0C-590DD1D-0002. 插入(ch r)到D的表项，序列号为D-000Dest. Next Metric Seq.AA0A-550BB1B-104C B2C-590Dest. Next Metric Seq.AA1A-550BB0B-104CC1C-590ABCD第48页/共82页第四十九页，共82页。C, 0, C-592)Dest. Next Metric Seq.AB2A-550BB1B-104CC0C-592DD1D-0003. C递增自己的序列号到C-592，然后立即(lj)广播自己的新路由表Dest. Next Metric Seq.AA0A-550BB1B-104C B2C-590Dest. Next Metric Seq.AA1A-550BB0B-104CC1C-590ABCD第49页/共82页第五十页，共82页。4. B获取新的路由信息(xnx)并且更新路由表Dest. Next Metric Seq.AC3A-550BC2B-104CC1C-592DD0D-000D从C获取路由表信息并且(bngqi)生成自己的路由表ABCDDest. Next Metric Seq.AB2A-550BB1B-104CC0C-592DD1D-000Dest. Next Metric Seq.AA0A-550BB1B-104C B2C-590Dest. Next Metric Seq.AA1A-550BB0B-104CC1C-592第50页/共82页第五十一页，共82页。Dest. Next Metric Seq.DC2D-100Dest. Next Metric Seq.DB3D-100Dest. Next Metric Seq.DD1D-100因为(yn wi)B广播的到达D的路由信息中的序列号小于C维护的D的序列号，因此C认为B的广播的是过期路由信息，不予采纳1. C检测到链路断开-序列号递增1(当且仅当这种情况不是(b shi)目的节点设置序列号-奇数序列号)2. B广播到达D的路由信息ABCD避免了循环避免了计数到无穷DD D-101第51页/共82页第五十二页，共82页。4. B立即传送更新消息给A(更新信息(xnx)具有更大的序列号，因此将取代A中原有表项)3. C立即传递更新信息给B (更新信息具有更大的序列号，因此(ync)将取代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页第五十三页，共82页。2. A收到来自(li z)P的路由更新消息10 Hops11 HopsAPQDDest. Next Metric Seq.DQ14D-100DP15D-1021. D公告(gnggo)序列号为D-102的路由更新路由表中到D的表项立即进行路由公告3. A收到来自Q的路由更新消息DQ14D-102更新路由表中到D的表项立即进行路由公告由于D或者任何一个节点的路由更新消息到达节点A时存在着时间差,就会导致不必要的路由公告路由表波动第53页/共82页第五十四页，共82页。10 Hops11 HopsAPQD可缓解大型网络(wnglu)的路由波动问题，从而避免不必要的公告，节约了带宽第54页/共82页第五十五页，共82页。第55页/共82页第五十六页，共82页。RFC3626第56页/共82页第五十七页，共82页。RFC3684第57页/共82页第五十八页，共82页。第58页/共82页第五十九页，共82页。nn避免了在每次路由中断时都需要进行路由避免了在每次路由中断时都需要进行路由发现，因此能够对拓扑变化作出更快的反发现，因此能够对拓扑变化作出更快的反应，应，第59页/共82页第六十页，共82页。路由发现和路由维护都是按需进行的不需要周期性路由公告不需要感知链路状态(zhungti)不需要邻居检测第60页/共82页第六十一页，共82页。ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)第61页/共82页第六十二页，共82页。ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)丢弃(diq)F转发的RREQ第62页/共82页第六十三页，共82页。(A-B-C-D)ABCDEF(A-B-C-D)(A-B-C-D)第63页/共82页第六十四页，共82页。同时将同时将RREP消息附加在新的消息附加在新的RREQ消息中消息中第64页/共82页第六十五页，共82页。第65页/共82页第六十六页，共82页。ABCDEF(A-B-C-E-)Route Error第66页/共82页第六十七页，共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-)以上(yshng)均假设信道是对称的!第67页/共82页第六十八页，共82页。ABCDEF(B-C-D)(A-B-C-D)(A-)第68页/共82页第六十九页，共82页。设置(shzh)缓存路由的有效期，过期即删除第69页/共82页第七十页，共82页。ABCDEF(B-A)G(C-B-A)(F-A)(E-C-B-A)G发起到A的路由发现(fxin)过程第70页/共82页第七十一页，共82页。D=H*（h-1+r）其中H是每条链路的传播延时h是自己返回的路径长度，即到目的(md)节点的跳数r是0或者1第71页/共82页第七十二页，共82页。第72页/共82页第七十三页，共82页。RFC3561第73页/共82页第七十四页，共82页。第74页/共82页第七十五页，共82页。第75页/共82页第七十六页，共82页。第76页/共82页第七十七页，共82页。HI路由请求(qngqi)消息路由应答第77页/共82页第七十八页，共82页。由的效率由的效率第78页/共82页第七十九页，共82页。第79页/共82页第八十页，共82页。第80页/共82页第八十一页，共82页。n量的长量的长111( ,)(1)kjiiieT n nkT第81页/共82页第八十二页，共82页。