AD HOC 路由协议_20101020101034478

AD-HOC路由协议•在AdHoc网络中，随着节点移动，网络拓扑结构在不断变化。如何迅速准确地选择到达目的节点的路由（即网络的路由选择问题），是AdHoc网络的一个重要和核心的问题。1.AdHoc网络与传统移动通信系统在路由问题上的区别•1．AdHoc网络与蜂窝移动通信系统的区别•蜂窝移动通信系统网络结构比较稳定。而在AdHoc网络环境下，节点的频繁随意移动，造成网络拓扑结构发生经常性的变化，使得路由表项经常改变。•2．AdHoc网络与无线局域网的区别–无线局域网是一个单跳的网络。而AdHoc网络则是一个多跳的网络。2.传统Internet网络路由协议•目前在Internet中常用的内部网关路由协议主要有两种。–基于距离矢量的路由协议（如RIP协议）–基于链路状态的路由协议（如OSPF协议）。•这两类协议都是针对固定网络而设计的，它们都需要周期性地交换信息维护网络正确的路由表或网络拓扑结构图。•AdHoc网络带宽有限、拓扑变化频繁，这些传统的用于固定网络的路由协议不适用于AdHoc网络，主要体现在以下几个方面。•（1）动态变化的网络拓扑结构。•（2）周期性地广播拓扑信息会占用大量的无线信道资源，耗费电池能源，将会严重降低系统的性能。尤其是在拓扑变化频繁的AdHoc网络环境中，可能当路由算法还未收敛时，网络的拓扑结构就又发生了变化。•（3）单向的无线传输信道。3.AdHoc网络路由协议的分类•根据发现路由的驱动模式的不同，可以将这些路由协议分为–表驱动路由协议（TableDrivenProtocols）在表驱动路由协议中，每个节点需要实时地维护路由信息，当网络规模较大、拓扑变化较快的环境中，大量的拓扑更新信息会占用过多的信道资源，使得系统效率下降。–按需路由协议（Source-InitiatedOn-DemandProtocols）按需路由协议的路由发现过程•根据网络拓扑结构的差异，又可以将它们分为–平面结构的路由协议（FlatProtocols）–分簇路由协议（ClusteredProtocols）。AdHoc网络拓扑结构•在平面结构的路由协议中–网络结构简单–网络中的节点都处于平等的地位–它们所具有的功能完全相同–各节点共同协作完成节点间的通信。•随着网络规模的逐步扩大，网络中节点个数不断增加，每个节点要想维护整个网络的拓扑信息或选择到远端节点合适的路由将十分困难，由此产生了分簇式路由协议。•在分簇式路由协议中，网络节点按照不同的分簇算法分成相应的簇（或群）。簇中的每个节点完成的功能是不相同的–簇首节点维护和管理本簇范围内节点，负责簇内节点的通信，同时为簇间节点通信提供合适的路由信息；–网关节点负责与相邻簇节点通信。分簇式路由协议中分层结构图4.评价AdHoc网络路由协议的标准•评价一种AdHoc网络路由协议的性能主要包括以下几个方面的指标–端到端的数据吞吐量和时延：通过报文传输质量的好坏来衡量路由协议性能的好坏。–路由请求的时间：即统计节点有数据需要发送到数据成功发送的时间，这主要用于按需路由方式的AdHoc网络路由协议的性能评价；–路由协议的效率：即完成路由任务的控制信息与用户数据信息的比率。尤其是在控制信息与数据信息共享同一信道的情况下，该性能将直接影响到整个系统效率的高低。•需要注意的是：即使是同一个路由协议，在不同的环境中，其性能好坏可能有很大的差异•AdHoc网络组网环境主要涉及的内容有：–网络的规模大小，即网络中节点个数的多少；–网络的拓扑结构变化速度；–节点的移动速度；–信道的传输带宽和单向信道的比率–“休眠”节点的比率等。•因此，在分析比较各种AdHoc网络路由协议性能时,要注意环境因素对各路由协议的影响。5.几种典型的AdHoc网络路由协议•DSDV（Destination-SequencedDistance-VectorRouting）路由协议•DSDV协议是基于传统Bellman-Ford路由选择算法经改良而发展出来的，是一个基于表驱动的路由协议，它的最大优点是解决了传统距离矢量路由协议中的无穷环路问题。•在DSDV路由协议中，每个节点都维护一张路由表，该路由表表项包括–目的节点–跳数–下一跳节点–目的节点序号•每个节点周期性地与邻节点交换路由信息，或者根据路由表的改变来触发路由更新。•路由表更新有两种方式：–一种是全部更新（Fulldump），即拓扑更新消息中将包括整个路由表，主要应用于网络变化较快的情况；–另一种方式是部分更新（Incrementalupdate），更新消息中仅包含变化的路由部分，通常适用于网络变化较慢的情况。•在DSDV中只使用序列号最高的路由，如果两个路由具有相同的序列号，那么将选择最优的路由（如跳数最短）。DSDV优缺点•DSDV路由协议中，节点维护着整个网络的路由信息，这样在有数据报文需要发送时，可以立即进行传送，因而适用于一些对实时性要求较高的业务和网络环境。•但是在拓扑结构变化频繁的无线网络环境中，DSDV可能存在一定的问题，–一是节点维护准确路由信息的代价高，要频繁地交换拓扑更新信息；–二是有的时候可能刚得到的路由信息随即又失效了。•因此，DSDV协议主要用于网络规模不是很大，网络拓扑变化相对不是很频繁的网络环境，而在拓扑变化频繁的网络中必须采用其他的方法。•DSR（DynamicSourceRouting）路由协议•DSR协议是一种基于源路由方式的按需路由协议。•在DSR协议中，当发送者发送报文时，在数据报文头部携带到达目的节点的路由信息，该路由信息由网络中的若干节点地址组成，源节点的数据报文就通过这些节点的中继转发到达目的节点。•与基于表驱动方式的路由协议不同的是，在DSR协议中，节点不需要实时维护网络的拓扑信息，因此在节点需要发送数据时，如何能够知道到达目的节点的路由是DSR路由协议需要解决的核心问题。•DSR路由协议主要由路由发现和路由维护两部分组成。–路由发现过程主要用于帮助源节点获得到达目的节点的路由。–DSR协议通过路由维护过程来监测当前路由的可用情况，当监测到路由故障时，将调用新的一轮路由发现过程。如路由中的节点由于移动、关机等原因无法保证到达目的节点时，当前的路由就不再有效了。–同时为了提高系统性能，在DSR协议中，还引入了一系列的优化技术，如路由缓冲（RouteCache）等。下面分别介绍这三部分内容。1．路由发现•节点通过路由发现过程获得到达其他节点的路由。•源节点首先向其邻节点广播“路由请求”（RouteRequest）报文。报文中包括“目的节点地址”、“路由记录”以及“请求ID”等字段。–其中“路由记录”字段用于记录从源节点到目的节点路由中的中间节点地址，当路由请求报文到达目的节点时，该字段中的所有节点地址即构成了从源节点到目的节点的路由。–“请求ID”字段由源节点管理分配–中间节点维护源节点地址，请求ID序列对列表，源节点地址，请求ID序列用于惟一标识一个路由请求报文，防止收到重复的路由请求。•中间节点在收到源节点的路由请求报文后，按照以下步骤处理报文：–（1）如果路由请求报文的源节点地址，请求ID存在于本节点的序列对列表中，表明此请求报文已经收到过，节点不用处理该请求；否则转步骤（2）；–（2）如果节点的地址已在路由记录字段中存在，节点不用处理该请求；否则转步骤3；–（3）如果请求报文的目的节点就是本节点，则路由记录节点中的节点地址序列构成了从源节点到目的节点的路由。节点向源节点发送“路由响应”报文，同时将该路由拷贝到“路由响应”报文中；否则转步骤（4）；–4）该节点是中间节点。将节点地址附在报文的“路由记录”字段后，同时向邻节广播该路由请求。•通过这种方法，路由请求报文将最终到达目的节点。•如下图所示为节点A到节点D的路由请求过程。虚线箭头代表路由请求消息发送，括号中的内容代表消息中的路由记录。DSR路由请求过程•几个注意的问题：•（1）由于节点B已经收到节点A的路由请求，因此不再处理节点F的路由请求消息；•（2）节点D可能会同时收到节点C和E的路由请求消息，造成消息碰撞，反而收不到正确的路由请求，因此在AdHoc网络中，广播并非完全可靠。可以采用一定的策略来避免，如节点随机延时发送，或者节点间采用证实机制等。•目的节点根据收到的源节点路由请求报文回送“路由响应”报文。目的节点在将“路由响应”报文转发到源节点时，需要考虑这样几种情况：–（1）目的节点有到达源节点的路由。此时目的节点可以直接使用该路由回送响应报文；–（2）如果目的节点没有到源节点的路由，此时需要考虑节点通信信道问题：•①如果网络中所有节点间的通信信道是对称的，此时目的节点到源节点的路由即为源节点到目的节点的反向路由；•②如果信道是非对称的，目的节点就需要发起到源节点的路由请求过程，同时将路由响应报文捎带在新的路由请求中。•如下图所示为DSR的路由响应过程。假设信道是双向信道，节点D根据最短路由原则选择了路由（A-B-C-D）作为最终路由，将此信息通过反向路由发送至源节点A。DSR路由响应过程•如果信道是单向呢？2．路由维护•传统的路由协议中通过周期性广播路由更新消息将路由发现和路由维护过程合二为一。而在DSR协议中，由于没有这种周期性的广播，节点必须通过路由维护过程检测路由的可用性。•按照路由维护的不同检测方法，可以将路由维护分为以下两种：•（1）点到点证实机制，又称为逐跳证实机制。–即相邻节点间通过数据链路层的消息证实或者高层应用层之间的消息证实机制，来检测路由中各邻节点的可达性。当发现节点间的传输故障，即路由不再有效时，向上级节点发送“路由差错”报文，收到路由差错报文的节点根据此信息将该路由从本节点的路由缓冲区中删除。•（2）端到端证实机制。在有些应用中要求端到端节点间的证实，通过端到端的证实机制可以用来检测整个路由的有效性。3．路由缓冲技术优化策略•在DSR协议中，为了提高系统效率，协议中采用了路由缓冲优化策略。–由于无线广播信道的特点，节点可以处于“混合监听”状态，即可以听到相邻节点发出的所有报文，包括路由请求、路由响应等。这些报文中携带了网络的一些路由信息，节点通过缓存这些路由信息，可以尽量减少每次发送新报文时启动的路由发现过程，以提高系统的效率。•如下图所示，节点A通过发起目的节点为D的路由请求过程，获得路由A-B-C-D，同时节点A也获得了到达该路由中所有节点（如节点B、C）的路由，节点B等中间节点也获得了到达节点D的路由。DSR路由缓冲技术•同时，中间节点在收到源节点的路由请求时，如果本节点路由缓冲区中有到目的节点的路由，可以直接回复路由响应消息。–如节点F在发起到节点D的路由请求时，当报文到达节点B时，节点B中有缓冲路由B-C-D，此时节点B可以直接回复路由响应（F-B-C-D）。这样一方面加快了路由请求的响应，同时也减少了路由请求消息的广播。•尽管路由缓冲技术能够在一定程度上提高系统的效率，但同时一些错误或过期的路由缓冲信息（如由于某些节点的移动使得路由失效）也会对网络带来负面影响，这些错误的路由信息可能会影响和感染其他节点。•对此，可以采用一定的策略来减少其影响。–如为缓冲路由设定有效期，超过有效期的路由将被认为无效，将其从缓冲区中删除。4．DSR协议的优缺点•DSR协议具有以下几个优点：•（1）仅在需要通信的节点间维护路由，减少了路由维护的代价；•（2）路由缓冲技术可进一步减少路由发现的代价；•（3）由于采用了路由缓冲技术，因此在一次路由的发现过程中，会产生多种到达目的节点的路径；•（4）支持非对称传输信道模式。•DSR协议存在一些问题和不足：•（1）由于采用源节点路由，每个数据报文的头部都要携带路由信息，增加了报文长度；•（2）用于路由发现的控制报文可能会波及全网各节点，造成一定的耗费；–一种可行的优化方法是控制路由发现报文的传输距离（如跳数），如果本轮路由发现失败，后续的路由发现过程中再加大传输距离；•（3）“路由响应风暴”（RouteReplyStorm）问题。由于采用路由缓冲技术，中间节点根据自己的缓冲路由，对