无线自组网课件.ppt

《无线自组网课件.ppt》由会员分享，可在线阅读，更多相关《无线自组网课件.ppt（65页珍藏版）》请在沃文网上搜索。

1、基础知识概述：基础知识概述：Ad Hoc路由路由l需要进行通信的两个节点可能不在需要进行通信的两个节点可能不在相互的无线信号范围内相互的无线信号范围内l需要其它节点承担转发工作需要其它节点承担转发工作l节点移动后需要重新建立新的路由节点移动后需要重新建立新的路由多跳路由多跳路由移动移动传统的路由协议不适用于传统的路由协议不适用于Ad Hoc网络网络l动态变化的网络拓扑结构动态变化的网络拓扑结构节点加入、离开、移动等节点加入、离开、移动等路由算法还未收敛路由算法还未收敛,网络拓扑结网络拓扑结构就发生变化构就发生变化l有限的系统带宽、能量等资源有限的系统带宽、能量等资源周期性地公告路由信息严重降周

2、期性地公告路由信息严重降低系统的性能低系统的性能l间歇性的网络分割间歇性的网络分割传统路由协议容易形成路由回传统路由协议容易形成路由回路路l单向的无线传输信道单向的无线传输信道传统路由协议一般假设链路是传统路由协议一般假设链路是对称的对称的p适应网络动适应网络动态变化态变化p减少路由开减少路由开销销p引入按需路引入按需路由由p在路由时考在路由时考虑能量等约虑能量等约束条件束条件多条路由的发现与维护l常见自组网路由协议：常见自组网路由协议：先应式（表驱动）、反应式（按需驱动）、混合式先应式（表驱动）、反应式（按需驱动）、混合式先应式（表驱动）、反应式（按需驱动）、混合式先应式（表驱动）、反应式（

3、按需驱动）、混合式：l l先应式（表驱动）路由协议先应式（表驱动）路由协议先应式（表驱动）路由协议先应式（表驱动）路由协议：节点无论当前是否有数据需：节点无论当前是否有数据需要发送，都事先计算出到所有节点的路由表，并且周期地要发送，都事先计算出到所有节点的路由表，并且周期地进行维护和更新这些路由表以适应网络拓扑变化。进行维护和更新这些路由表以适应网络拓扑变化。l优点：是优点：是路由发现无延迟路由发现无延迟路由发现无延迟路由发现无延迟l l缺点：是路由表维护花费的系统开销大缺点：是路由表维护花费的系统开销大缺点：是路由表维护花费的系统开销大缺点：是路由表维护花费的系统开销大。多条路由的发现与维护

4、l常见自组网路由协议：常见自组网路由协议：先应式（表驱动）、反应式（按需驱动）、混合式先应式（表驱动）、反应式（按需驱动）、混合式先应式（表驱动）、反应式（按需驱动）、混合式先应式（表驱动）、反应式（按需驱动）、混合式：l l反应式（按需驱动）反应式（按需驱动）反应式（按需驱动）反应式（按需驱动）：只是在源节点有数据通信的需要时：只是在源节点有数据通信的需要时才计算路由才计算路由l优点：节电且不需要花费代价来维护无用的路由优点：节电且不需要花费代价来维护无用的路由l缺点：缺点：路由发现延迟很大且不可预测。路由发现延迟很大且不可预测。路由发现延迟很大且不可预测。路由发现延迟很大且不可预测。l l

5、混合式混合式混合式混合式：局部使用先应式，广域使用按需路由算法：局部使用先应式，广域使用按需路由算法。路由协议路由协议Ad Hoc路由协议路由协议表驱动路由表驱动路由先验式先验式(Proactive)按需路由按需路由反应式反应式(Reactive)ZRPDSDVTBRPFCGSROLSRLMRABRDSRAODVTORASSRDYMOpOLSR:Optimized Link State RoutingpTBRPF:Topology Dissemination Based on Reverse-Path ForwardingpAODV:Ad Hoc On Demand Distance Vect

6、orpDSR:Dynamic Source Routing DTMO:Dynamic MANET On-demand Routing表驱动（表驱动（Table Driven）路由）路由l先验式先验式(Proactive)路由路由传统的分布式最短路径路由协议传统的分布式最短路径路由协议l链路状态或者距离向量链路状态或者距离向量l所有节点周期性更新所有节点周期性更新“可达可达”信息信息每个节点维护到网络中所有其它节点的路由每个节点维护到网络中所有其它节点的路由所有路由都已存在并且随时可用所有路由都已存在并且随时可用DSDV、OLSR、TBRPF路由延时小，但是路由开销大路由延时小，但是路由开销大按

7、需按需(On-demand)路由路由l反应式反应式(Reactive)路由路由源节点根据需要通过路由发现过源节点根据需要通过路由发现过程来确定路由程来确定路由控制消息采用泛洪（控制消息采用泛洪（Flooding）方式方式l两种实现技术两种实现技术源路由（分组携带完整的路由信源路由（分组携带完整的路由信息）息）逐跳（逐跳（Hop-by-Hop）路由）路由lDSR、AODV、DYMO路由延时大，但是路由开销小路由延时大，但是路由开销小混合路由混合路由lAd Hoc网络划分为区域网络划分为区域每个节点在区域内部采用表驱动路由每个节点在区域内部采用表驱动路由对于区域外节点采用按需路由对于区域外节点采用

8、按需路由l簇和区域的不同簇和区域的不同簇内所有节点都与簇首直接通信，簇内节点间的通信一般簇内所有节点都与簇首直接通信，簇内节点间的通信一般是两跳是两跳区域的大小没有限制，区域内的节点通信可以多跳区域的大小没有限制，区域内的节点通信可以多跳lZRP：Zone Routing Protocolp减少了域内的路由延时减少了域内的路由延时p减少了域外的路由开销减少了域外的路由开销p区域半径的选择区域半径的选择p小小:节点移动快的密集网络节点移动快的密集网络p大大:节点移动慢的稀疏网络节点移动慢的稀疏网络Ad Hoc路由协议的性能指标路由协议的性能指标l端到端数据吞吐量和延时端到端数据吞吐量和延时反映了

9、数据的传输质量反映了数据的传输质量l路由获取时间路由获取时间有数据要发送到发送出去的时间有数据要发送到发送出去的时间l乱序分组发送率乱序分组发送率衡量无连接路由协议应用于需要有序发送的传输层协衡量无连接路由协议应用于需要有序发送的传输层协议例如议例如TCP时的性能时的性能l路由协议的效率路由协议的效率路由控制消息路由控制消息/发送数据发送数据路由协议的性能在不同环境表现不同路由协议的性能在不同环境表现不同,因此需要根据环境特点使用不同的路由协议因此需要根据环境特点使用不同的路由协议Ad Hoc的协议与协议栈l自组网中必须在一次通信时解决的问题：自组网中必须在一次通信时解决的问题：1.如何将数据

10、分组包含的比特转化为信号发送和如何将数据分组包含的比特转化为信号发送和接收？接收？2.如何能够保证传输的信息比特可靠？如何能够保证传输的信息比特可靠？3.多节点共享信道时，这些节点如何分配使用信多节点共享信道时，这些节点如何分配使用信道？道？4.路由表如何生成？路由表如何生成？5.网络拓扑变化的时候如何修改路由表？网络拓扑变化的时候如何修改路由表？6.自组网研究过程中采用将协议栈分层的方法将自组网研究过程中采用将协议栈分层的方法将问题分解到各个层分别加以研究。问题分解到各个层分别加以研究。7.自组网采用自组网采用ISO七层协议模型加以分析和研究。七层协议模型加以分析和研究。8.最具特色的两层：

11、最具特色的两层：MAC和网络层。和网络层。7应用层应用层6表示层5会话层4传输层3网络层2链路控制层MAC子层1物理层OSI 网络网络七层协议模型七层协议模型 Ad Hoc的协议与协议栈l自组网通信采用分组传输方式：首先将传输的数据打成若自组网通信采用分组传输方式：首先将传输的数据打成若干个分组，然后依次传输干个分组，然后依次传输l例例 A-B-C-D-E，B接收，查路由表，确定下一跳接收，查路由表，确定下一跳C，直至发给直至发给El数据分组结构数据分组结构=控制部分控制部分+数据部分。其中，数据部分。其中，l控制部分控制部分=源地址源地址+目的地址目的地址+其它控制信息其它控制信息l数据部分

12、数据部分=数据部分数据部分2.3.3 多条路由的发现与维护l l自组网路由协议的设计目标自组网路由协议的设计目标自组网路由协议的设计目标自组网路由协议的设计目标：1.要求计算出的路由具有良好的性质，例如跳数少、链路稳定要求计算出的路由具有良好的性质，例如跳数少、链路稳定可靠、传输时延小等可靠、传输时延小等2.要求协议能够快速地适应网络拓扑的变化要求协议能够快速地适应网络拓扑的变化3.要求路由计算与维护引入的控制的开销小要求路由计算与维护引入的控制的开销小移动移动表驱动（先验式）路由协议表驱动（先验式）路由协议带目的地序列号的距离向量协议带目的地序列号的距离向量协议(DSDV)lDestinat

13、ion-Sequenced Distance-VectorDV(Distance Vector)算法算法DSDV协议协议DV算法概述算法概述l基于分布式基于分布式Bellman-Ford算法算法寻找从源点到某个点的最短路径寻找从源点到某个点的最短路径l每个节点都维护一张路由表每个节点都维护一张路由表所有可达的目的地所有可达的目的地到达目的地的下一跳到达目的地的下一跳到达目的地的到达目的地的“距离距离”（开销）（开销）l节点向邻居节点发送路由更新消息节点向邻居节点发送路由更新消息定期更新：即使节点路由表无变化定期更新：即使节点路由表无变化触发更新：节点路由表中某条路由发生变化触发更新：节点路由表

14、中某条路由发生变化l路由更新消息包含列表格式路由更新消息包含列表格式l节点在收到节点在收到“更好更好”路由的情况下更新路由表路由的情况下更新路由表具有更小的开销：对于同一个目的地，来自不同的下一跳具有更小的开销：对于同一个目的地，来自不同的下一跳更新开销：对于同一目的地，来自相同的下一跳更新开销：对于同一目的地，来自相同的下一跳DV:Distance Vector DV算法过程算法过程l初始化初始化ABCDest.NextMetricAA0BB3C-32Dest.NextMetricBB0AA3CC2 2Dest.NextMetricCC0BB2A-l路由更新ABCDest.NextMetri

15、cAA0BB3CB5 532Dest.NextMetricBB0AA3CC2 2Dest.NextMetrictCC0BB2AB5 5路由更新消息路由更新消息DV算法中的计数到无穷问题算法中的计数到无穷问题ABC32Dest.NextMetricBB0AA3CC2 2Dest.NextMetricCC0BB2AB5 5Dest.NextMetricBB0 0AACC2 2Dest.NextMetricBB0AC7CC2 2Dest.NextMetricCC0BB2AB9 9无穷计数！无穷计数！DV算法不能直接用于算法不能直接用于Ad Hoc网络网络l计数到无穷问题计数到无穷问题l部分解决方法部

16、分解决方法选择一个相对较小的数作为无穷大选择一个相对较小的数作为无穷大水平分割水平分割(split horizon)：当一个节点把路由更新：当一个节点把路由更新发送给相邻节点时，它并不把从各个相邻节点处发送给相邻节点时，它并不把从各个相邻节点处学到的路由再回送给该节点学到的路由再回送给该节点无法发现路由循环无法发现路由循环限制了网络的可扩展性限制了网络的可扩展性对两个节点的路由循环有效，更大的路由循环需要更强的措施对两个节点的路由循环有效，更大的路由循环需要更强的措施DSDV协议概述协议概述l基于基于DV算法算法简单，易于实现简单，易于实现需要的存储空间小（只须和邻居节点交换路由信息）需要的存

17、储空间小（只须和邻居节点交换路由信息）l确保无路由回路确保无路由回路路由表中的每个表项都带有目的地序列号（由目的节路由表中的每个表项都带有目的地序列号（由目的节点生成）点生成）l对拓扑变化能作出快速反应对拓扑变化能作出快速反应路由表有显著变化时立即启动路由公告路由表有显著变化时立即启动路由公告(Router Advertisement)但是等待不稳定路由的公告，以减缓路由波动但是等待不稳定路由的公告，以减缓路由波动(damping fluctuations)l先验式（表驱动）先验式（表驱动）路由路由节点维护到所有目的地的路由信息节点维护到所有目的地的路由信息路由信息必须周期性的更新（无休眠节点

18、）路由信息必须周期性的更新（无休眠节点）利弊？利弊？即使网络拓扑无变化也存在着通信开销即使网络拓扑无变化也存在着通信开销维护的路由可能从不使用维护的路由可能从不使用DSDV:Destination-Sequenced Distance Vector DSDV路由表路由表l序列号（序列号（Sequence number）由目的端产生，用来防止出现路由回路，并确保路由信由目的端产生，用来防止出现路由回路，并确保路由信息是最新的息是最新的；格式：格式：Dest_NNNl加入时间（加入时间（Install Time）路由表项的创建时间，用来删除过期表项路由表项的创建时间，用来删除过期表项lStable

19、 Data 指向一个包含有路由稳定状态信息的表指向一个包含有路由稳定状态信息的表l目的节点地址目的节点地址/最近沉淀时间最近沉淀时间/平均沉淀时间平均沉淀时间 用于缓解网络中的路由波动用于缓解网络中的路由波动Dest.MetricNextSeq.NrInstall TimeStable DataAA0A-550001000Ptr_ABB1B-102001200Ptr_BCB3C-588001200Ptr-CDB4D-312001200Ptr_D对于同一个目对于同一个目的地节点可能的地节点可能接收到来自其接收到来自其它节点的多条它节点的多条路由信息，路由信息，settling time为第一条路

20、由为第一条路由和最佳路由之和最佳路由之间的时间间隔间的时间间隔DSDV路由公告路由公告l向每个邻居公告自己的路由信息向每个邻居公告自己的路由信息目的节点地址目的节点地址Metric：到目的节点的开销，一般为到目的节点的跳数：到目的节点的开销，一般为到目的节点的跳数目的地序列号目的地序列号其它信息（例如硬件地址等）其它信息（例如硬件地址等）l设置序列号信息的规则设置序列号信息的规则每次公告增加自己的目的地序列号（只使用偶数值）每次公告增加自己的目的地序列号（只使用偶数值）如果一个节点不再可达（如果一个节点不再可达（timeout）,则将该节点的序列则将该节点的序列号加号加1（奇数序列号），并且设

21、置（奇数序列号），并且设置metric为为DSDV路由选择路由选择l将更新信息与自己的路由表比较将更新信息与自己的路由表比较选择具有更大目的地序列号的路由，这将保证始选择具有更大目的地序列号的路由，这将保证始终使用来自目的地的最新信息终使用来自目的地的最新信息当序列号相等时，选择具有更好当序列号相等时，选择具有更好metric的路由的路由DSDV协议操作：更新前路由表协议操作：更新前路由表Dest.Next Metric SeqAA1A-550BB0B-100C C1C-588Dest.Next Metric SeqAA0A-550BB1B-100C B2C-588Dest.Next Metr

22、ic Seq.AB2A-550BB1B-100C C0C-588ABCDSDV协议操作：路由公告协议操作：路由公告B递递增序列号增序列号 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-588ABCDSDV协议操作：更新后路由表协议操作：更新后路由表Dest.Next Met

23、ric SeqAA0A-550BB1B-102C B2C-588Dest.Next Metric SeqAA1A-550BB0B-102C C1C-588Dest.Next Metric Seq.AB2A-550BB1B-102C C0C-588ABC对拓扑变化的反应对拓扑变化的反应l立即公告原则立即公告原则有关新路由、链路断开和有关新路由、链路断开和metric变化的信息立即变化的信息立即传递给邻居节点传递给邻居节点l两种更新模式（完全更新两种更新模式（完全更新/增量更新）增量更新）完全更新：发送自己路由表中的所有路由信息完全更新：发送自己路由表中的所有路由信息增量更新：只发送路由表中那些发

24、生变化的表项增量更新：只发送路由表中那些发生变化的表项（能包含在一个单独的分组中发送）（能包含在一个单独的分组中发送）DSDV协议操作：新节点加入协议操作：新节点加入Dest.Next Metric Seq.AA0A-550BB1B-104C B2C-590Dest.Next Metric Seq.AA1A-550BB0B-104CC1C-590Dest.Next Metric Seq.AB2A-550BB1B-104CC0C-5901.D第一次广播第一次广播,发发送序列号送序列号D-000ABCDDSDV协议操作：新节点加入协议操作：新节点加入Dest.Next Metric Seq.AB2

25、A-550BB1B-104CC0C-590DD1D-0002.插入到插入到D的表的表项项，序列号序列号为为D-000Dest.Next Metric Seq.AA0A-550BB1B-104C B2C-590Dest.Next Metric Seq.AA1A-550BB0B-104CC1C-590ABCDDSDV协议操作：新节点加入协议操作：新节点加入C,0,C-592)Dest.Next Metric Seq.AB2A-550BB1B-104CC0C-592DD1D-0003.C递递增自己的序列号到增自己的序列号到C-592，然后然后立即广播立即广播自己的新路由表自己的新路由表Dest.Ne

26、xt Metric Seq.AA0A-550BB1B-104C B2C-590Dest.Next Metric Seq.AA1A-550BB0B-104CC1C-590ABCDDSDV协议操作：新节点加入协议操作：新节点加入4.B获获取新的路由信取新的路由信息并且更新路由表息并且更新路由表Dest.Next Metric Seq.AC3A-550BC2B-104CC1C-592DD0D-000D从从C获获取路由表信息并取路由表信息并且生成自己的路由表且生成自己的路由表ABCDDest.Next Metric Seq.AB2A-550BB1B-104CC0C-592DD1D-000Dest.Ne

27、xt Metric Seq.AA0A-550BB1B-104C B2C-590Dest.Next Metric Seq.AA1A-550BB0B-104CC1C-592DC2D-000DSDV协议操作：链路断开协议操作：链路断开Dest.Next Metric Seq.DC2D-100Dest.Next Metric Seq.DB3D-100Dest.Next Metric Seq.DD1D-100因因为为B广播的到达广播的到达D的路由信息中的序列的路由信息中的序列号小于号小于C维护维护的的D的序列号，因此的序列号，因此C认为认为B的广播的是的广播的是过过期路由信息，不予采期路由信息，不予采纳

28、纳1.C检测检测到到链链路断开路断开-序列号序列号递递增增1(当且当且仅仅当当这这种情况不是目的种情况不是目的节节点点设设置序列号置序列号-奇数序列号奇数序列号)2.B广播到达广播到达D的路由信息的路由信息ABCD避免了循避免了循环环避免了避免了计计数到数到无穷无穷DD D-101DSDV协议操作：立即公告协议操作：立即公告4.B立即立即传传送更新消息送更新消息给给A(更新信息具有更大的序列号，更新信息具有更大的序列号，因此将取代因此将取代A中原有表中原有表项项)3.C立即立即传递传递更新信息更新信息给给B(更新信息具有更大的序列号，更新信息具有更大的序列号，因此将取代因此将取代B中原有表中原

29、有表项项)ABCDDest.Next Metric Seq.DC2D-100Dest.Next Metric Seq.DB3D-100Dest.Next Metric Seq.DD D-101(D,D-101)DB D-101DC D-101DSDV协议操作：路由波动协议操作：路由波动2.A收到来自收到来自P的路由更新消的路由更新消息息10 Hops11 HopsAPQDDest.Next Metric Seq.DQ14D-100DP15D-1021.D公告序列号公告序列号为为D-102的的路由路由更新路由表中到更新路由表中到D的表项的表项立即进行路由公告立即进行路由公告3.A收到来自收到来自

30、Q的路由更新消的路由更新消息息DQ14D-102更新路由表中到更新路由表中到D的表项的表项立即进行路由公告立即进行路由公告由于由于D或者任何一个节点的路由更新消息到或者任何一个节点的路由更新消息到达节点达节点A时存在着时间差时存在着时间差,就会导致不必要的就会导致不必要的路由公告路由公告路由表波动路由表波动DSDV协议操作：减缓路由波动协议操作：减缓路由波动l在一个单独的表中记录每条路在一个单独的表中记录每条路由的最近的和平均的由的最近的和平均的Settling TimeSettling Time：第一条路由和最第一条路由和最佳路由之间的时间间隔佳路由之间的时间间隔路由表中的路由表中的stab

31、le data指向该表指向该表lA在包含新序列号的第一条路在包含新序列号的第一条路由到达时更新路由表，但是等由到达时更新路由表，但是等待一段时间再广播该条路由待一段时间再广播该条路由等待时间等待时间=2*(avg.Setting Time)10 Hops11 HopsAPQD可缓解大型网络的路由波动问题，可缓解大型网络的路由波动问题，从而避免不必要的公告，节约了带宽从而避免不必要的公告，节约了带宽DSDV总结总结l优点优点简单（基本上与简单（基本上与DV算法一致）算法一致）通过目的地序列号避免了路由循环，解决了通过目的地序列号避免了路由循环，解决了DV算法中的算法中的计数到无穷问题计数到无穷问

32、题无路由发现延时（先验式路由）无路由发现延时（先验式路由）l缺点缺点所有节点都必须公告路由，因此不支持休眠（不能直接用所有节点都必须公告路由，因此不支持休眠（不能直接用于传感器网络）于传感器网络）收敛慢（收敛慢（DV路由的特性）路由的特性）开销大：大部分的路由信息从不使用开销大：大部分的路由信息从不使用可扩展性是一个主要问题（所有先验式路由都存在的问题）可扩展性是一个主要问题（所有先验式路由都存在的问题）优化链路状态路由协议优化链路状态路由协议(OLSR)lOptimized Link State Routing Protocol先验式的链路状态路由协议先验式的链路状态路由协议基于多点中继（基

33、于多点中继（MPR）的概念的优化）的概念的优化l只有只有MPR转发广播消息，减少了消息开销转发广播消息，减少了消息开销l只有只有MPR产生链路状态信息，减少了网络中广播消息产生链路状态信息，减少了网络中广播消息的数量的数量lMPR可能选择只报告它和该可能选择只报告它和该MPR选举节点之间的链路，选举节点之间的链路，因此在网络中只散发部分链路状态信息因此在网络中只散发部分链路状态信息RFC3626基于拓扑广播的反向路径转发基于拓扑广播的反向路径转发TBRPFlTopology Broadcast based on Reverse-Path Forwarding本质上是一种链路状态协议本质上是一种

34、链路状态协议协议组成协议组成l邻居发现模块邻居发现模块l路由模块路由模块与传统链路状态协议的差别与传统链路状态协议的差别l拓扑更新消息更小拓扑更新消息更小l路由开销更少路由开销更少l更适合拓扑迅速变化的无线网络更适合拓扑迅速变化的无线网络RFC3684按需（反应式）路由协议按需（反应式）路由协议动态源路由协议动态源路由协议(DSR)lDynamic Source Routing按需路由按需路由l节点需要发送数据时才进行路由发现过程节点需要发送数据时才进行路由发现过程l反应型路由，仅维护活跃的路由反应型路由，仅维护活跃的路由源路由源路由l发送节点在分组中携带到达目的节点的路由信息发送节点在分组中

35、携带到达目的节点的路由信息（转发分组的完整的节点序列）（转发分组的完整的节点序列）不需要中间节点维护路由信息不需要中间节点维护路由信息l节点缓存到目的节点的多条路由节点缓存到目的节点的多条路由避免了在每次路由中断时都需要进行路由发现，避免了在每次路由中断时都需要进行路由发现，因此能够对拓扑变化作出更快的反应，因此能够对拓扑变化作出更快的反应，DSR协议组成协议组成l路由发现（路由发现（Route Discovery）只有在源节点需要发送数据时才启动只有在源节点需要发送数据时才启动帮助源节点获得到达目的节点的路由帮助源节点获得到达目的节点的路由l路由维护（路由维护（Route Maintenan

36、ce）在源节点在给目的节点发送数据时监测当前路由的可在源节点在给目的节点发送数据时监测当前路由的可用情况用情况当网络拓扑变化导致路由故障时切换到另一条路由或当网络拓扑变化导致路由故障时切换到另一条路由或者重新发起路由发现过程者重新发起路由发现过程路由发现和路由维护都是按需进行的路由发现和路由维护都是按需进行的p不需要周期性路由公告不需要周期性路由公告p不需要感知链路状态不需要感知链路状态p不需要邻居检测不需要邻居检测DSR路由发现：路由请求路由发现：路由请求l源节点向邻居节点广播路由请求源节点向邻居节点广播路由请求（RREQ：Route Request）消消息息源节点地址源节点地址目的节点地址

37、目的节点地址路由记录：纪录从源节点到目的节点路由中的中间节点路由记录：纪录从源节点到目的节点路由中的中间节点请求请求IDl中间节点接收到中间节点接收到RREQ后，将自己的地址附在路由纪录中后，将自己的地址附在路由纪录中ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)DSR路由发现：中间节点处理路由发现：中间节点处理l中间节点维护中间节点维护序列对列表序列对列表l重复重复RREQ检测检测如果接收到的如果接收到的RREQ消息中的消息中的存在于本节点的序列对列表中存在于本节点的序列对列表中如果接收到的如果接收到的RREQ消息中的路由纪录中包含本节

38、点的消息中的路由纪录中包含本节点的地址地址l如果检测到重复，则中间节点丢弃该如果检测到重复，则中间节点丢弃该RREQ消息消息ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)丢弃丢弃F转发转发的的RREQDSR路由发现：路由应答路由发现：路由应答l目的节点收到目的节点收到RREQ后，给源节点返回路由后，给源节点返回路由应答（应答（RREP：Route Reply）消息）消息拷贝拷贝RREQ消息中的路由纪录消息中的路由纪录l源节点收到源节点收到RREP后在本地路由缓存中缓存后在本地路由缓存中缓存路由信息路由信息(A-B-C-D)ABCDEF(A

39、-B-C-D)(A-B-C-D)DSR路由发现：非对称信道路由发现：非对称信道l对称信道对称信道目的节点到源节点的路由即为源节点到目的节点目的节点到源节点的路由即为源节点到目的节点的反向路由的反向路由l非对称信道非对称信道如果目的节点的路由缓存中有到达源节点的路由，如果目的节点的路由缓存中有到达源节点的路由，则直接使用则直接使用否则目的节点需要发起到源节点的路由请求过程，否则目的节点需要发起到源节点的路由请求过程，同时将同时将RREP消息稍带在新的消息稍带在新的RREQ消息中消息中DSR路由维护路由维护l逐跳证实机制逐跳证实机制链路层链路层l确认确认l被动确认（监听其它节点间的数据发送）被动确

40、认（监听其它节点间的数据发送）其它高层其它高层l要求要求DSR软件返回确认软件返回确认l端到端证实机制端到端证实机制无法确定故障发生的位置无法确定故障发生的位置DSR逐跳证实机制逐跳证实机制l如果数据分组被重发了最大次数仍然没有收到下一跳的确如果数据分组被重发了最大次数仍然没有收到下一跳的确认，则节点向源端发送路由错误（认，则节点向源端发送路由错误（Route Error）消息，）消息，并且指明中断的链路并且指明中断的链路l源端将该路由从路由缓存中删除源端将该路由从路由缓存中删除l如果源端路由缓存中存在另一条到目的节点的路由则使用如果源端路由缓存中存在另一条到目的节点的路由则使用该路由重发分组

41、该路由重发分组l否则重新开始路由发现过程否则重新开始路由发现过程ABCDEF(A-B-C-E-)Route ErrorDSR优化：路由缓存优化：路由缓存(1)l 每个节点缓存它通过任何方式获得的新路由每个节点缓存它通过任何方式获得的新路由转发转发RREQl获得从本节点到获得从本节点到RREQ路由记录中所有节点的路由，路由记录中所有节点的路由，例如例如E转发转发RREQ(A-B-C)获得到到获得到到A的路由的路由(C-B-A)转发转发RREPl获得本节点到获得本节点到RREP路由纪录中所有节点的路由，例路由纪录中所有节点的路由，例如如B转发转发RREP(A-B-C-D)获得到获得到D的路由的路由

42、(C-D)转发数据分组转发数据分组l获得从本节点到数据分组节点列表中所有节点的路由，获得从本节点到数据分组节点列表中所有节点的路由，例如例如E转发数据分组转发数据分组(A-B-C)获得到获得到A的路由的路由(C-B-A)监听相邻节点发送的分组监听相邻节点发送的分组（RREQ、RREP、数据分组等）、数据分组等）(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-)以上均假设信道是对称的以上均假设信道是对称的!DSR优化：路由缓存优化：路由缓存(2)l中间节点使用缓存的到目的节点的路

43、由响应中间节点使用缓存的到目的节点的路由响应RREQRREP中的路由纪录中的路由纪录=RREQ中的路由纪录中的路由纪录+缓存缓存的到目的节点的路由的到目的节点的路由ABCDEF(B-C-D)(A-B-C-D)(A-)DSR优化：路由缓存优化：路由缓存(3)l错误路由缓存错误路由缓存网络拓扑的变化使得缓存的路由失效网络拓扑的变化使得缓存的路由失效l影响和感染其它节点，使用该路由缓存的路由将不影响和感染其它节点，使用该路由缓存的路由将不可用可用当节点根据路由缓存回应当节点根据路由缓存回应RREP时，其它监听到时，其它监听到此此RREP的节点会更改自己缓存的路由，从而感的节点会更改自己缓存的路由，从

44、而感染错误路由缓存染错误路由缓存设置缓存路由的有效期，过期即删除设置缓存路由的有效期，过期即删除DSR优化：路由缓存优化：路由缓存(4)lRREP风暴风暴节点广播到某个目的节点的节点广播到某个目的节点的RREQ，当其邻居节，当其邻居节点的路由缓存中都有到该目的节点的路由时，每点的路由缓存中都有到该目的节点的路由时，每个邻居节点都试图以自己缓存的路由响应，由此个邻居节点都试图以自己缓存的路由响应，由此造成造成RREP风暴风暴RREP风暴将风暴将浪费网络带宽，并且浪费网络带宽，并且加剧消息冲突加剧消息冲突ABCDEF(B-A)G(C-B-A)(F-A)(E-C-B-A)G发起到发起到A的的路由发现

45、过程路由发现过程DSR优化：路由缓存优化：路由缓存(5)l预防预防RREP风暴风暴每个节点延时每个节点延时D发送发送RREPD与节点到目的节点的跳数成正比，使得到目的节点有最与节点到目的节点的跳数成正比，使得到目的节点有最短路径的短路径的RREP最先发送最先发送节点将接口设置成混杂模式节点将接口设置成混杂模式(promiscuous)，监听是否存，监听是否存在有比自己更短的到目的节点的路径，如果有，则不发送在有比自己更短的到目的节点的路径，如果有，则不发送本节点的本节点的RREPD=H*（h-1+r）其中其中H是每条链路的传播延时是每条链路的传播延时h是自己返回的路径长度，即到目的节点的跳数是

46、自己返回的路径长度，即到目的节点的跳数r是是0或者或者1DSR总结总结l优点优点仅在需要通信的节点间维护路由，减少了路由维护开销仅在需要通信的节点间维护路由，减少了路由维护开销路由缓存技术能够进一步减少路由发现的代价路由缓存技术能够进一步减少路由发现的代价通过采用路由缓存技术，能够发现多条到达目的节点的通过采用路由缓存技术，能够发现多条到达目的节点的路由路由支持非对称信道支持非对称信道l缺点缺点采用源节点路由，每个数据分组头标中都要携带路由信采用源节点路由，每个数据分组头标中都要携带路由信息，增加了网络开销息，增加了网络开销由于采用广播，用于路由发现的控制消息可能波及到全由于采用广播，用于路由

47、发现的控制消息可能波及到全网节点，需要这些消息的传输距离（跳数）网节点，需要这些消息的传输距离（跳数）RREP风暴问题风暴问题错误路由缓存问题错误路由缓存问题AODV协议协议Ad Hoc On Demand Distance Vector RoutinglAODV结合了结合了DSR和和DSDV使用使用DSR中基于广播的路由发现机制中基于广播的路由发现机制每个节点都维护路由表，采用每个节点都维护路由表，采用DSDV逐跳逐跳(Hop-by-Hop)路由、序列号路由、序列号l数据分组不再携带完整的路由信息数据分组不再携带完整的路由信息l仅维护活跃的路由仅维护活跃的路由lAODV特点特点与与DSDV协

48、议相比协议相比,采用按需路由采用按需路由,不需要维护整个网络不需要维护整个网络的拓扑信息的拓扑信息,只有在发送分组且没有到目的节点的路由只有在发送分组且没有到目的节点的路由时才发起路由发现过程时才发起路由发现过程与与DSR协议相比协议相比,由于节点建立和维护路由表由于节点建立和维护路由表,分组中不分组中不需携带完整的路由信息需携带完整的路由信息仅适用于对称信道仅适用于对称信道路由表仅维护一条到目的节点的路由路由表仅维护一条到目的节点的路由RFC3561混合路由协议混合路由协议区域路由协议区域路由协议(ZRP)lZone Routing Protocol区域区域(zone)的划分的划分l整个网络

49、被划分为若干个以节点为中心整个网络被划分为若干个以节点为中心,一定跳数为一定跳数为半径的区域半径的区域l区域内节点数与设定的区域半径有关区域内节点数与设定的区域半径有关路由策略路由策略l每个节点在区域内部采用表驱动路由每个节点在区域内部采用表驱动路由l对于区域外节点采用按需路由对于区域外节点采用按需路由ZRP路由架构路由架构l区域内路由协议区域内路由协议IARP (IntrAzone Routing Protocol)采用表驱动路由协议，节点之间周期性地交换路由信息获采用表驱动路由协议，节点之间周期性地交换路由信息获得到域内各个节点的最新路由得到域内各个节点的最新路由l距离向量路由协议距离向量

50、路由协议DSDV等等l链路状态路由协议链路状态路由协议OLSR等等完成区域内部节点间的路由功能完成区域内部节点间的路由功能l区域间路由协议区域间路由协议IERP (IntErzone Routing Protocol)采用按需路由协议采用按需路由协议完成与区域外节点间的路由功能完成与区域外节点间的路由功能l边界传播协议边界传播协议BRP (Bordercast Resolution Protocol)BRP协议使得路由查询分组只在边界节点之间广播协议使得路由查询分组只在边界节点之间广播ZRP路由架构路由架构l区域内路由协议区域内路由协议 IARP:IntrAzone Routing Proto