无线自组织网络第2章补充

1、MANET路由张建辉 内容DSDVDSRAODV带目的地序列号的距离向量协议(DSDV)Destination-Sequenced Distance-VectorDV (Distance Vector)算法DSDV协议DV算法概述基于分布式Bellman-Ford算法寻找从源点到某个点的最短路径每个节点都维护一张路由表所有可达的目的地到达目的地的下一跳到达目的地的“距离”（开销）节点向邻居节点发送路由更新消息定期更新：即使节点路由表无变化触发更新：节点路由表中某条路由发生变化路由更新消息包含列表格式节点在收到“更好”路由的情况下更新路由表具有更小的开销：对于同一个目的地，来自不同的下一跳更新开

2、销：对于同一目的地，来自相同的下一跳DV: Distance Vector DV算法过程初始化ABCDest.NextMetricAA0BB3C-32Dest.NextMetricBB0AA3CC2Dest.NextMetricCC0BB2A-路由更新ABCDest.NextMetricAA0BB3CB532Dest.NextMetricBB0AA3CC2Dest.NextMetrictCC0BB2AB5路由更新消息DV算法中的计数到无穷问题ABC32Dest.NextMetricBB0AA3CC2Dest.NextMetricCC0BB2AB5Dest.NextMetricBB0AACC2D

3、est.NextMetricBB0AC7CC2Dest.NextMetricCC0BB2AB9无穷计数！DV算法不能直接用于Ad Hoc网络计数到无穷问题部分解决方法选择一个相对较少的数作为无穷大水平分割 (split horizon)：当一个节点把路由更新发送给相邻节点时，它并不把从各个相邻节点处学到的路由再回送给该节点无法发现路由循环限制了网络的可扩展性对两个节点的路由循环有效，更大的路由循环需要更强的措施DSDV协议概述基于DV算法简单，易于实现需要的存储空间小（只须和邻居节点交换路由信息）确保无路由回路路由表中的每个表项都带有目的地序列号（由目的节点生成）对拓扑变化能作出快速反应路由表

4、有显著变化时立即启动路由公告(Router Advertisement)但是等待不稳定路由的公告，以减缓路由波动(damping fluctuations)先验式（表驱动）路由节点维护到所有目的地的路由信息路由信息必须周期性的更新（无休眠节点）即使网络拓扑无变化也存在着通信开销维护的路由可能从不使用DSDV: Destination-Sequenced Distance Vector DSDV路由表序列号（Sequence number ）由目的端产生，用来防止出现路由回路，并确保路由信息是最新的格式： Dest_NNN加入时间（Install Time）路由表项的创建时间，用来删除过期表项S

5、table Data 指向一个包含有路由稳定状态信息的表目的节点地址最近沉淀时间（last settling time）平均沉淀时间 (average settling time) 用于缓解网络中的路由波动Dest.MetricNextSeq. NrInstall TimeStable DataAA0A-550001000Ptr_ABB1B-102001200Ptr_BCB3C-588001200Ptr-CDB4D-312001200Ptr_D对于同一个目的地，节点可能接收到来自其它节点的多条路由信息，settling time定义为第一条路由和最佳路由之间的时间间隔DSDV路由公告向每个邻居

6、公告自己的路由信息目的节点地址Metric：到目的节点的开销，一般为到目的节点的跳数目的地序列号其它信息（例如硬件地址等）设置序列号信息的规则每次公告增加自己的目的地序列号（只使用偶数值）如果一个节点不再可达（timeout）,则将该节点的序列号加1（奇数序列号），并且设置metric为DSDV路由选择将更新信息与自己的路由表比较选择具有更大目的地序列号的路由，这将保证始终使用来自目的地的最新信息当序列号相等时，选择具有更好metric的路由DSDV协议操作：更新前路由表Dest.NextMetricSeqAA1A-550BB0B-100C C1C-588Dest.NextMetricSeqA

7、A0A-550BB1B-100C B2C-588Dest.NextMetricSeq.AB2A-550BB1B-100C C0C-588ABCDSDV协议操作：路由公告B递增序列号 100 - 102B向邻居A、C广播路由信息，其中包含有目的地序列号Dest.NextMetricSeqAA0A-550BB1B-100C B2C-588Dest.NextMetricSeqAA1A-550BB0B-102C C1C-588Dest.NextMetricSeq.AB2A-550BB1B-100C C0C-588ABCDSDV协议操作：更新后路由表Dest.NextMetricSeqAA0A-550B

8、B1B-102C B2C-588Dest.NextMetricSeqAA1A-550BB0B-102C C1C-588Dest.NextMetricSeq.AB2A-550BB1B-102C C0C-588ABC对拓扑变化的反应立即公告有关新路由、链路断开和metric变化的信息立即传递给邻居节点完全/增量更新完全更新：发送自己路由表中的所有路由信息增量更新：只发送路由表中那些发生变化的表项（能包含在一个单独的分组中发送）DSDV总结优点简单（基本上与DV算法一致）通过目的地序列号避免了路由循环，解决了DV算法中的计数到无穷问题无路由发现延时（先验式路由）缺点所有节点都必须公告路由，因此不支持

9、休眠（不能直接用于传感器网络）收敛慢（DV路由的特性）开销大：大部分的路由信息从不使用可扩展性是一个主要问题（所有先验式路由都存在的问题）动态源路由协议(DSR)Dynamic Source Routing按需路由节点需要发送数据时才进行路由发现过程反应型路由，仅维护活跃的路由源路由发送节点在分组中携带到达目的节点的路由信息（转发分组的完整的节点序列）不需要中间节点维护路由信息节点缓存到目的节点的多条路由避免了在每次路由中断时都需要进行路由发现，因此能够对拓扑变化作出更快的反应，DSR协议组成路由发现（Route Discovery）只有在源节点需要发送数据时才启动帮助源节点获得到达目的节点的

10、路由路由维护（Route Maintenance）在源节点在给目的节点发送数据时监测当前路由的可用情况当网络拓扑变化导致路由故障时切换到另一条路由或者重新发起路由发现过程路由发现和路由维护都是按需进行的不需要周期性路由公告不需要感知链路状态不需要邻居检测DSR路由发现：路由请求源节点向邻居节点广播路由请求（RREQ：Route Request）消息源节点地址目的节点地址路由记录：纪录从源节点到目的节点路由中的中间节点请求ID中间节点接收到RREQ后，将自己的地址附在路由纪录中ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)DSR路由发现：中

11、间节点处理中间节点维护序列对列表重复RREQ检测如果接收到的RREQ消息中的存在于本节点的序列对列表中如果接收到的RREQ消息中的路由纪录中包含本节点的地址如果检测到重复，则中间节点丢弃该RREQ消息ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)丢弃F转发的RREQDSR路由发现：路由应答目的节点收到RREQ后，给源节点返回路由应答（RREP：Route Reply）消息拷贝RREQ消息中的路由纪录源节点收到RREP后在本地路由缓存中缓存路由信息(A-B-C-D)ABCDEF(A-B-C-D)(A-B-C-D)DSR路由发现：非对称信道对

12、称信道目的节点到源节点的路由即为源节点到目的节点的反向路由非对称信道如果目的节点的路由缓存中有到达源节点的路由，则直接使用否则目的节点需要发起到源节点的路由请求过程，同时将RREP消息稍带在新的RREQ消息中DSR路由维护逐跳证实机制链路层确认被动确认（监听其它节点间的数据发送）其它高层要求DSR软件返回确认端到端证实机制无法确定故障发生的位置DSR逐跳证实机制如果数据分组被重发了最大次数仍然没有收到下一跳的确认，则节点向源端发送路由错误（Route Error）消息，并且指明中断的链路源端将该路由从路由缓存中删除如果源端路由缓存中存在另一条到目的节点的路由则使用该路由重发分组否则重新开始路由

13、发现过程ABCDEF(A-B-C-E-)Route ErrorDSR优化：路由缓存(1) 每个节点缓存它通过任何方式获得的新路由转发RREQ获得从本节点到RREQ路由记录中所有节点的路由，例如E转发RREQ(A-B-C)获得到到A的路由(C-B-A)转发RREP获得本节点到RREP路由纪录中所有节点的路由，例如B转发RREP(A-B-C-D)获得到D的路由(C-D)转发数据分组获得从本节点到数据分组节点列表中所有节点的路由，例如E转发数据分组(A-B-C)获得到A的路由(C-B-A)监听相邻节点发送的分组RREQ、RREP、数据分组等(A-B-C-D)ABCDEF(A-B-C-D)(A-B-C

14、-D)ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)以上均假设信道是对称的!DSR优化：路由缓存(2)中间节点使用缓存的到目的节点的路由响应RREQRREP中的路由纪录=RREQ中的路由纪录+缓存的到目的节点的路由ABCDEF(B-C-D)(A-B-C-D)(A-)DSR优化：路由缓存(3)错误路由缓存网络拓扑的变化使得缓存的路由失效影响和感染其它节点，使用该路由缓存的路由将不可用当节点根据路由缓存回应RREP时，其它监听到此RREP的节点会更改自己缓存的路由，从而感染错误路由缓存设置缓存路由的有效期，过期即删除DSR优化：路由缓存(4)

15、RREP风暴节点广播到某个目的节点的RREQ，当其邻居节点的路由缓存中都有到该目的节点的路由时，每个邻居节点都试图以自己缓存的路由响应，由此造成RREP风暴RREP风暴将浪费网络带宽，并且加剧消息冲突ABCDEF(B-A)G(C-B-A)(F-A)(E-C-B-A)G发起到A的路由发现过程DSR优化：路由缓存(5)预防RREP风暴每个节点延时D发送RREPD与节点到目的节点的跳数成正比，使得到目的节点有最短路径的RREP最先发送节点将接口设置成混杂模式(promiscuous)，监听是否存在有比自己更短的到目的节点的路径，如果有，则不发送本节点的RREPD=H*（h-1+r）其中H是每条链路的

16、传播延时h是自己返回的路径长度，即到目的节点的跳数r是0或者1DSR总结优点仅在需要通信的节点间维护路由，减少了路由维护开销路由缓存技术能够进一步减少路由发现的代价通过采用路由缓存技术，能够发现多条到达目的节点的路由支持非对称信道缺点采用源节点路由，每个数据分组头标中都要携带路由信息，增加了网络开销由于采用广播，用于路由发现的控制消息可能波及到全网节点，需要这些消息的传输距离（跳数）RREP风暴问题错误路由缓存问题AODV协议Ad Hoc On Demand Distance Vector RoutingAODV结合了DSR和DSDV使用DSR中基于广播的路由发现机制每个节点都维护路由表，采用DSDV逐跳(Hop-by-Hop)路由、序列号数据分组不再携带完整的路由信息仅维护活跃的路由AODV特点与DSDV协议相比,采用按需路由,不需要维护整个网络的拓扑信息,只有在发送分组且没有到目的节点的路由时才发起路由发现过程与DSR协议相比,由于节点建立和维护路由表,分组中不需携带完整的路由信息仅适用于对称信道路由表仅维护一条到目的节点的路由RFC3561混合路由协议区域路由协议(ZRP)Zone Routing Protocol区域