无线自组织网络中的多径路由

无线自组织网络中的多径路由苏静凯北京邮电大学电子工程学院，北京(100876)E-mail：[e-mail]摘要：本文中主要研究了无线自组织（Adhoc）网络中现有的几种多径路由协议，分析了多径路由协议的设计和应用中几个值得注意问题，和对这些问题的不同解决方法对Adhoc网络性能各方面的影响。关键词：无线自组织网络，多径，路由协议中图分类号：TN921.引言移动自组织网络（即移动AdHoc网络）是一个移动的，多跳的无线网络，其主要特点有动态的网路拓扑结构，有限带宽，不需要预先建设基础网络设备等等。在此类网络中，设计路由协议是网络的关键问题。Adhoc的网络协议要求合理使用带宽，减少建立和维护路由的开销；快速发现路径，减少传输的延时；防止建立的路由出现环路，等等。根据目前的国内外的研究，采用多径路由协议，可能带来诸如延长路由生存的时间，缩短端到端延时等网络性能的改善。本课题主要关注adhoc网络中多径路由的实现方法，和其带来的网络性能改变。在研究中选取了目前较有代表性的几种多径路由协议进行研究和比较，以深入了解几种不同的实现多径的方法的特点和对网络性能的改变。从结果中可以看到不同的多径路由协议的性能有一定的差别，但都对Adhoc网络的性能有所的改善。2.无线自组织网络的路由协议2.1无线自组织网络概述AdHoc网络是一种不需要有线基础设施支持的移动网络，网络中的节点均由移动主机构成。AdHoc网络昀初应用于军事领域，由于无线通信和终端技术的不断发展，AdHoc网络在民用环境下也得到了发展，如需要在没有有线基础设施的地区进行临时通信时，可以很方便地通过搭建AdHoc网络实现。在AdHoc网络中主机同时还是路由器，担负着寻找路由和转发报文的工作。在AdHoc网络中，每个主机的通信范围有限，因此路由一般都由多跳组成，数据通过多个主机的转发才能到达目的地。AdHoc网络也被称为多跳无线网络。2.2无线自组织网络的路由协议AdHoc网络设计中的一个关键问题是开发能够在两个节点之间提供高质量高效率通信的路由协议。网络节点的移动性使得网络拓扑结构不断变化，传统的基于因特网的路由协议无法适应这些特性，需要有专门的应用于AdHoc网络的路由协议，一般来说，AdHoc网络可以应用的三种基本类型的路由选择协议：表驱动；需求驱动；混合表型。在表驱动的路由协议中每个节点不断地更新到网络中任何其他节点的路由信息，这样在建立路由时，建立延迟会较小。但是对于拓扑结构经常发生变化的网络，这种机制要求使用大量的资源，用以维护这些路由表的正确性和可靠性。在需求驱动的路由协议中，节点只需要维护到达活动目的节点的路由即可。当节点需要与新的目的节点通信时，路由协议会启动一个路由选择过程。这样用于更新拓扑变化的通信开销减少，进行路由搜索带来的路由建立延迟会增大；另外快速变化的拓扑结构可能会破坏现有的路由而导致新的路由选择过程。减小发起建立路由的频率对于Adhoc网络的路由协议的设计有重要的意义。合理设计多径路由协议可以减少发起建立路由的频率。不仅如此，合理设计多径路由协议还可以有效提高吞吐量和降低网络的传输延时。因此，研究多径路由协议具有重要意义。3.无线自组织网络的多径路由协议现在研究中的路由协议大多以普通的单径的路由协议为基础设计，一般采用单径路由协议中的路由的发现和维护的基本手段。其中AOMDV[6]协议和AODV－BR[14]协议是在AODV[4]协议基础之上产生的，而SMR[3]协议，MSR[9]协议的路由发现方法是在基于类似DSR[5]协议的源路由方法的。CHAMP[15]协议采用了节点中缓存路由和数据信息的方法。本文中介绍了AOMDV和MSR两种典型的多径路由协议，在此基础之上对以上几种路由协议进行了分析。3.1多径路由协议的基础知识3.1.1路径独立程度对于多径路由来说，链路分离（link-disjoint）和节点分离（node-disjoint）是两个重要的概念。引入这两个概念，是为了表示建立的两点间的多条不同路径的独立（分离）程度。图2分别具体描述了链路分离和节点分离的路径。对于图2所示的两条路径ABCDE和AGFE除了源和目的节点之外，没有共同的部分，称这两条路径为节点分离的路径，而对于图中的两条路径ABCDE和ABCFE，虽然它们有共同的节点C，但是并没有共用的链路，称这样的两条路径为链路分离的路径。在多径路由中，路径的分离性是一个非常重要的方面，因为，一个路径集越独立，该路径集在节点对之间提供的物理资源就越有效，亦即一条路径的性能影响另一条路径性能的可能性就越小。根据[7]中的研究，路径的独立性越强，多径路由越能充分地利用网络资源，增大节点对之间的有效带宽，并且减轻网络的拥塞程度从而降低丢包率。节点独立的多路径必然也是链路独立的，前者的独立性更强。图1链路分离和节点分离的示意图在路由协议中会涉及判断两条路径是否link-disjoint或node-disjoint的问题，对于采用源路由的多径路由方法来说，由于采用了源路由的方式，源和目的节点存储了所有路径的路由信息，只需一一比较就可判断两条路径的分离程度，但是对于未采用源路由的多径路由方法，由于源和目的节点无法获得整个路径的信息，需要在建立路由时由节点采取一定的措施来保证路径分离的程度。关于具体的方法在后面有关AOMDV协议和CHAMP协议的叙述中有详细的说明。3.1.2数据传输和路由维护多径路由的建立只是多路由协议的第一个步骤，建立路由之后，路由的维护和数据的传送方式也是多径路由协议所要设计重要的内容。这两方面的具体设计因不同的多径路由建立方法而各有所不同，但是基本的思想不外乎以下两种。一种是多径路由建立之后数据可以只在一条路径中传输，而其他的路径作为备份路径，待传输数据的路径中的链路出现错误时，可继续通过备份路径传输，另一种是几条建立起的路径并行传送数据，但是，这种传输方式有一个问题需要解决－不同路径数据传输的负载如何分担，采用这种数据传输方式的不同的多径路由协议都分别提出了不同的方法，后文中有叙述。3.2两种多径路由协议3.2.1AOMDV协议AOMDV建立路由的方式与AODV基本相同。在建立路由的过程中，AODV仅保留一条路由，对于其他可能建立的路由，AODV协议中以序列号和保存在RREQ中的跳数信息屏蔽掉。而在AOMDV中，为了建立多径路由，只是设定一些条件，满足条件的路由则得以保留。这些条件包括两个方面：第一，不出现环路；第二，链路分离。与AODV协议相似，为防止环路的出现，AOMDV协议采用了两个值作为判断是否建立路由的标准，包括：目的序列号和advertisedhopcount。同时采用下一跳和昀后一跳来判断链路分离（link-disjoint）。Advertisedhopcount是对于某一个目的序列号而言第一次建立路由得到的值。一个节点不接受值大于其路由表项中advertisedhopcount的值的消息建立路由的请求。如果一条路径上的每个节点路由表项中的所有节点中的下一跳和昀后一跳中的任何一个都没有相同的，则这条路径与其它路径是链路分离的。一个节点当接受到需要建立路由的消息时，首先比较序列号，当消息中的序列号较大时，则写入路由信息，若相等时则需要比较advertisedhopcount的值，若消息中的较小，则不会构成回路，此时比较下一跳和昀后一跳，若没有相同值，则建立路由。建立路由时的节点每一次接收到消息，都会进行上述步骤。以上步骤为建立多径路由的关键步骤之一。除了以上的判断过程外，AOMDV在建立路由的过程中还有一些不同于AODV方面，和其他特有的需要注意的方面。需要注意的是，虽然AOMDV协议规定只要满足要求的消息都可以建立路由，但是对于RREQ消息来说，仅有第一次送到某个节点的某个RREQ消息会被重新广播，其他后来被接受到的同一个RREQ消息虽然有可能导致反向路由的建立，但不会被重新广播。与AODV协议不同，在目的节点接收到一个RREQ之后，它返回任何一个满足通过不构成环路的路径RREP，并不判断链路分离，但是，中间节点仍然以前述的规则判断是否建立路由，如不满足规则，RREP则被抛弃。这样做的原因在于，有些链路虽然是链路分离的，但不满足节点分离的条件，当沿不同的路径的RREQ通过他们之间共同的节点I时，由于不重，仅有一个RREQ可以继续传送，这样导致目的节点看到的I之前的路径仅有一条，因此也仅有一条链路分离的路径。但实际上，不仅仅只存在一条链路分离的路径，这称作路由剪断（route-cutoff）效应。为避免此效应，目的节点发送RREP时不判断链路分离，以期建立尽可能多的符合条件的路由。图2路由剪断效应的示意图:在路由的维护方面，AOMDV同样采用了RERR消息来报告路由连接的错误。并且采用了与DSR相似的救包（salvagepackets）的方式，在连接断开处的节点缓存数据包，并查看是否有其他可用的通向节点的路由，若没有则由该节点发起新的路由建立过程。AOMDV协议是一种有效和成熟的多径路由协议，其性能比较AODV协议有了较大的提高。3.3.2MSR路由协议对于MSR协议可以主要关注多条路径同时传输数据时负载分担的问题，其路由建立的过程与SMR协议十分类似。MSR使用DSR的路径发现机制，DSR在路由发现过程中可以返回多条路径，搜索到的所有路径都保存在路由缓存中，每条路径都具有一个唯一的路由索引，这样,就能很容易从缓存中挑出多条路径。与DSR相比，MSR并没有增加太多的路由的存储开销，因为这些路径本身在DSR的缓存中存在，DSR仅使用其中的一条路径，而MSR使用了多条路径。实际上在两个终端节点之间会存在比较多的路径，在选择路径时：首先要保证所选择的路径是node-disjoint的；一方面,路径数量不能太少，否则不能充分利用潜在路径；另一方面,路径数量不能太多，否则探测包的网络开销就比较大，一般把可探测的路径维持在3条以内。测量任意两个节点之间的路由往返时间（routetriptime）。探测也是对DSR路由维护机制的改进。在DSR中，通常情况下，一个节点仅当路由错误消息返回时才得知某个链路失效。但是，在无线移动环境里，路由错误消息本身经常有可能到达不了源主机。虽然可以在分组头中包括进一位，以允许传送分组的主机向下一跳的接收者请求一个显式的应答，但是，仅仅为了测试某条路径的有效性而频繁地探测该路径的代价过高。因为MSR使用源路由，所有的路径计算都在源主机完成，中间节点在包转发时不做任何处理，只按照分组报头所指示的路由路径转发该分组，与DSR相比，并没有增加处理复杂性。对于MSR，在源主机上要进行负载平衡的处理。为了进行负载平衡的处理，源节点中需要建立一个特殊的表，包含着到达目标节点的多个路径信息：index、Dest、Delay、Weight。Dest是一条路由路径的目标节点，Index是该路由路径在缓存中的当前索引，Delay是的当前估计值。Weight是所有到达同一个目标节点的不同路径的负载平衡加权系数，也就是说，Weight是每一次在同一条路由路径上连续发送的分组数。Weight的值根据以下公式确定minminmin,1,iiiddRUdddUdWi⎛⎞×≥⎜⎟⎝⎠⎧⎪=⎨−⎪⎩（1）其中Wi为当前路径i的权重，dmin为所有路径中昀小的路径时延，di为当前路径的路径时延，R是控制着在路由路径之间调度切换频率的因子，参数U保证Wi所选用的路径不会太差于昀优路径。当dmin/diU时,该路径不再有正权值,即通常不再使用该路径。R用来控制每条路径上的负载分配的粒度，R的值越大，单条路径一次分到的负载越多，多条路径之间切换的频率越低。DSR加入路径探测功能后则成为