搜索
第四章MANET路由MANET－MobileAdhocNETworkMANET路由概述通信两点可能不再相互的无线传输范围内需要其他节点承担路由器的转发工作节点移动需要发现新路由MANET路由概述多条链组成路径移动导致路径变化MANET路由面临的困难路由信息不易获得–定期交换路由信息或者按需搜索路由的开销大–网络资源有限，并且必须被所有节点共享–节点资源（电池、CPU等）也是有限的–也许不可能收集齐所有的路由信息路由信息不完整–移动和分区很难将信息分发到一个没有固定成员网络的所有节点路由信息可能过期–不可能连续地或者立即交换信息–节点随时移动–无线传播变化很大常规路由协议是否可用？常规路由协议不是为高移动性和低带宽网络设计的DV算法存在“无穷计算”问题和慢收敛采用洪泛技术的（链路状态）协议造成额外的通信和控制开销常规路由协议周期性的路由更新消耗大量的网络带宽和节点能源当网络节点失效和网络分区时形成路由回路无线终端功率的差异以及无线信道的干扰导致单向信道的存在Adhoc网络对路由协议的要求收敛迅速提供无环路由避免无穷计算控制管理开销小对终端无过高要求支持单向信道尽量简单实用路由机制必须适应网络三个不断变化的基本特征–移动节点的总体密度–节点到节点的拓扑–网络的使用模式Adhoc路由协议分类平面路由–无需建立具有特殊cluster头功能节点的层次结构–不划分区域以及所谓的区内/外不同路由–所有的节点在路由机制中地位平等–寻址方式是平面的层次路由–节点功能不同–寻址方式是分层进行的地理信息辅助路由–利用地理信息进行路由选择按需（on-demand）路由协议反应式（reactive）路由–在源端需要时候通过路由发现过程来确定路由»控制信息采用洪泛（flooding）方式»路由请求延迟高»路由开销低–两种实现技术»源路由（报文头携带完整的路由信息）»逐跳路由（类似现有的Internet路由）•洪泛技术（Flooding）在自组网路由中具有广泛应用工作原理：（1）源节点向所有的邻居节点广播分组。（2）中间节点判断自己是否是目的节点，如果不是，而且是第一次收到该分组，则继续广播；否则，直接丢弃（3）目的节点接收分组，不广播。改进：在分组中加入TTL（TimeToLive）字段，将分组的传播限制在一定范围内。效果：洪泛使分组像辐射波一样从源节点已波浪形式向外传播，最终到达目的节点（如果目的节点是可达的话）最健壮最基本的方法表驱动（tabledriven）路由先应式（proactive）路由–传统的分布式最短路径路由协议»链路状态或者距离向量»所有节点连续更新“可达”信息–每个节点维护到网络中所有节点的路由–所有路由都已经存在并且随时可用–路由请求的延迟低–路由开销高两种路由机制的权衡路由发现的延迟–主动协议因全程维护所有的路由而具备低延迟–按需协议因只在需要时才发现所需路由而导致高延迟路由发现/维护的开销–按需协议因只在需要时才维护路由而具备低开销–主动协议因连续更新路由可能导致高开销那种途径表现更好取决于流量和移动模式分层路由协议层次（hierarchical）路由–一些节点组成一个cluster或则zone–这些cluster或则zone可组成较大的supercluster或则superzoneCluster和zone的不同–Cluster内所有节点都与clusterhead直接通信，cluster内节点间的通信一般是两跳–Zone的大小没有限制，zone内节点的通信可多跳ZRP两层路由协议概念描述分层路由协议的优缺点优点–网络拓扑结构的细节通过节点的层层聚合都被隐藏起来，因此大大降低大型网络的存储要求–路由信息分层传播，需要在全局传播的路由信息较少–有限的链路状态维护缺点–分层路由协议的移动管理比较复杂–某些节点（clusterhead/gateway）比其他节点承担更多的通信和计算负载评价MANET路由协议的指标端-端的数据吞吐量和延迟–反映了数据报的传输质量路由请求的时间–有数据需要发送到发送出去的时间路由协议的效率–路由控制信息与数据信息的比率MANET路由主动路由表驱动（Tabledriven）/先应式路由机制–传统的分布式最短路径路由协议»链路状态或则距离向量»所有节点连续更新“可达”信息每个节点维护到网络中所有节点的路由所有路由都已经存在并且随时可用优点：路由请求的延迟低缺点：路由开销大距离矢量（DistanceVector）基于分布式的Bellman-Ford算法每个节点维持一张路由表–所有可达目的地–到目的地的下一跳–达到目的地的跳计数定期把路由表发给所有的邻居DV算法过程初始化ABCDest.NextMetricAA0BB3C-∞32Dest.NextMetricBB0AA3CC2Dest.NextMetricCC0BB2A-∞路由更新ABCDest.NextMetricAA0BB3CB532Dest.NextMetricBB0AA3CC2Dest.NextMetricCC0BB2AB5B,0A,3C,2B,0A,3C,2路由更新消息DV算法无穷计算问题DV算法无穷计算问题（续）DV算法不能直接用于AdHoc网络计数到无穷问题部分解决方法–选择一个相对较少的数作为无穷大–水平分割(splithorizon)：当一个节点把路由更新发送给相邻节点时，它并不把从各个相邻节点处学到的路由再回送给该节点无法发现路由循环限制了网络的可扩展性对两个节点的路由循环有效，更大的路由循环需要更强的措施DSDV协议—Destination-SequencedDistanceVector目的序列距离矢量路由协议基于DV算法–简单、易于实现–需要的存储空间小（只和邻居节点交换信息）确保无路由回路–措施：新的路由表带有目标序列号（由目的节点生成）对于拓扑变化能快速反应–当路由表发生重大变化时立即启动routeadvertisement–延迟不稳定路由的通告（减缓路由波动）先验式（表驱动）路由–节点维护到所有目的地的路由信息–路由信息必须周期性的更新（无休眠节点）–即使网络拓扑无变化也存在着通信开销–维护的路由可能从不使用•DSDV协议细节DSDV要求每个节点保存路由表，表中列出了所有可达的目的节点及到达该目的节点的跳数。每个路由条目包含目的节点产生的序列号，用来区分新旧路由。节点间通过周期性地发布路由更新分组来交互路由信息，以保证路由表的正确性。当有重要的新信息是也广播路由更新分组。*移动节点收到新的路由信息分组时，路由的更新遵循以下两个原则：1.比较该更新分组中携带的路由信息和节点保存的路由条目。如果节点收到的路由的目的节点序列号大于路由表中相应的目的节点的序列号，则采用有更新序列号的路由而丢弃原有的旧序列号的路由。2.如果更新分组中目的节点序列号与现存的序列号相同，则选择具有较好度量的路由条目，若新路由有较好度量，则丢弃现存的路由或将其存储为次之路由。为了减轻网络的负担，路由更新分组采用两种形式：第一种为“fulldump”,它携带节点所有的路由表信息；另一种为“增长（Incremental）”型数据分组，它携带的信息是自上次发送fulldump以后节点的路由表中发生变化的哪些路由条目的信息。移动节点还保存一个附加表来存储已经在增长型路由信息数据内传送的数据。DSDV算法采用以下两种方法来检测链路的中断：1）链路层检测到某条链路中断时，向路由层报告。2）通过时间推断，即节点在过了一段时间后仍没有收到某个节点发送的分组，就自动认为本节点到该节点的链路中断，将相应的路由条目设置为无穷大（实际中，若链路度量为跳数，则经常设置为N+1，N为网络的节点数）来描述断开的链路。检测出链路中断的节点会发送一个更新分组，该分组有一个新的序列号，跳数为无穷大。这会引起网络中路由表的更新，只有当再次收到丢失节点的信息后新的路由才会重新建立起来。虽然在网络拓扑变化频繁的情况下，DSDV协议的收敛性能不好，但在一般情况下，收敛还是相当快的。但是，当加入网络的节点越来越多，路由表容量及开销和带宽也相应的增加。节点不一定用到至所有目的节点的路由条目，多余的路由条目也会造成资源的浪费。DSDV协议仅支持双向链路，这就限制了其在无线网络中的使用。最后，当节点的移动率较高时，DSDV协议的性能将急剧恶化DSDV路由表Sequencenumber–由目标节点生成，用来保证不出现路由回路Installtime–该表项创建时间（用来删除表中过时路由信息）Stabledata–指向一个包含有路由稳定状态信息的表–用来缓解路由波动路由通告（routeadvertisement）向每个邻居通告自己的路由信息–目标地址–Metric=到目标的跳计数–目的节点序列号设置序号的规则–每次通告递增自己的目标序号（只用偶数值）–如果一个节点不再可达（timeout），则将该节点的序号递增1（奇数值）并置metric=∞路由选择（routeselection）将收到的路由更新信息与自己的路由表比较–选择目标序号大的路由（这样能确保使用的总是来自目的地的最新路由信息）–如果目标序号相同，则选择具有较好metric值的路由DSDV实例DSDV实例（续）DSDV对拓扑变化的响应立即通告–有关新路由、链路中断、metric变化的信息立即传播给邻居完全/增量更新–完全（FullUpdate）»发送路由表的全部路由信息–增量（IncrementalUpdate）»仅发送路由表中有变化的表项使得可用一个分组完成更新增加一个新节点-1增加一个新节点-2如何解决路由回路和无穷计算？拓扑变化时的立即通告DSDV协议操作：路由波动2.A收到来自P的路由更新消息D,14,D-10211Hops12HopsD,0,D-102APQDDest.NextMetricSeq.………DQ14D-100DP15D-1021.D公告序列号为D-102的路由D,0,D-102更新路由表中到D的表项立即进行路由公告3.A收到来自Q的路由更新消息D,13,D-102DQ14D-102更新路由表中到D的表项立即进行路由公告由于D或者任何一个节点的路由更新消息到达节点A时存在着时间差,就会导致不必要的路由公告路由表波动DSDV协议操作：减缓路由波动在一个单独的表中记录每条路由的最近的和平均的SettlingTime–SettlingTime：第一条路由和最佳路由之间的时间间隔–路由表中的stabledata指向该表A在包含新序列号的第一条路由到达时更新路由表，但是等待一段时间再广播该条路由–等待时间=2*(avg.SettingTime)10Hops11HopsD,0,D-102APQDD,0,D-102可缓解大型网络的路由波动问题，从而避免不必要的公告，节约了带宽DSDV总结优点–简单（几乎与DV算法一致）–通过目的地赋予的序号值来防止出现路由回路–不存在路由发现带来的延迟缺点–没有节点睡眠–收敛慢–开销：多数路由信息从不使用DSDV总结1）DSDV能迅速地为节点建立路由并发送数据，在任何情况下都能避免路由环路。2）在网络拓扑变化频繁的情况下，DSDV收敛性并不好3）由于要求节点定期广播路由更新消息，当加入的节点越来越多时，路由表的容量，开销和带宽要求也急剧上升，这是DSDV的主要缺点。4）DSDV要求节点保存到网络中所有节点的路由，造成很大的浪费。5）当节点的移动率较高时，DSDV协议的性能将急剧恶化•WRP协议（WirelessRoutingProtocol）无线路由协议WRP协议中，节点保存的信息表包括距离表、路由表、链路开销表、分组重传列表4个部分。节点通过获得邻节点的状态变化信息来维护自己的信息表，并通知邻节点；收到来自邻节点的信息后，要更改保存的信息表，节点需要发送一个回复分组（ACK）说明已经收到并处理了某个更新消息。