第2章Ad-hoc网络的路由协议分类
2.2 单路径和多路径
传统Ad Hoc网络单路径路由
Ad Hoc移动网络中单路径路由主要分成基于表驱动的被动路由¨,2j(如DSDV(Destination-Se．
quencedDistance-VectorRouting))和按需主动路由协议¨(如DSR(DynamicSourceRouting)J，AODV(AdHocOnDemandDistanceVectorRouting))两种。被动路由跟传统Intemet网络中的距离矢
量算法类似，都是通过节点周期性交换路由表来实现的，只需稍做修改便可用于AdHoc移动网络。主动路由一般都基于按需路由方式，通过泛洪广播实现，主要分为路由发现(RD：RouteDiscovery)和路由维护(RM：RouteMaintenance)两个阶段。
DSDV协议DSDV协议是一种基于Bellman-Ford路由机制的，表驭动路由协议，是为移动AdHoc网络制定的。最早的路由协议之一。每个节点都维护一张路由表，节点通过与目的节点相关的序列号判断路由的新旧，并依此避免路由环路的产生。每个节点周期性的将自己的路由表广播给其邻节点，其邻节点根据收到的路由表来更改自己的路由表。
DSR协议动态资源路由协议DSRl3是用于移动节点多跳无线AdHoc网络的简单和有效的主动路由协议。使用DSR时，网络是自组织和自配置的，要求无既定的网络结构和管理。DSR协议有两个主要的机制路由发现和路由维护一起工作，以实现AdHoc网络中源路由的发现和维护。
路由发现。路由发现阶段主要由路由请求和路由响应两个阶段组成。只有当源节点s试图向目的节点D发送数据，并且尚不知道S和D之间的路由时，启动路由发现机制。具体包括RREQ(Routerequest)分组．对各节点对RREQ分组的处理，对信宿的路由回答RREP(Routereply)。
路由维护。如果网络拓扑发生改变比如说链路中断导致S和D之间的路由无法再使用，此时启动路由维护十JL制。DSR协议通过MAC层检测到链路断开，节点将“路由错误分组”RREQ到发送信源，信源节点将删除该路由，重新进行路由发现，称为“逐跳MAC确认”的网络。此外还有“逐跳MAC不确认”的网络和利用“端到端确认”的路由维护。DSR不使用任何定期路由广告、链路状态感应、或者是邻居检测数据包，也不会依赖网络的下一层得到这些功能。DSR使用外部“源路由”，即当要发一个数据包时，该数据包所需要经过的所有节点序列均包含在该数据包的包头中。
7
电子科技大学成都学院课程设计论文
AODV协议。AODV路由协议是由DSDV改进得到的，与DSDV不同，它是按需路由协议。AODV采用逐跳转发。报文的方式。另外AODV还支持组播路由和支持QoS，其缺点是不支持单向信道，原因是路由回答报文。直接沿着路由请求的反向回到源节点。AODV协议由路由发现过程和路由维护过程组成。
单路径评价及问题分析。单路协议的优势在于它的简单性。但是这种简单性从根本上限制了单路协议性能的提升空间。Ad Hoc网络中的带宽、节点能量等资源是相当有限的。同时，在链路上以及在路由器处的拥塞，也是造成Ad Hoc网络中较大延迟的主要原因。
在Ad Hoc网络中使用单路路由协议，如果目的节点相同的数据包全部都在同一条路径上发送，当某条链路拥塞或者断开时，通过该链路发送的所有数据就都必须由新的路径发送，网络不能在轻载时充分利用资源，不能当网络发生拥塞或者链路断开时也较好地重新选择合适路径。在最近Ad Hoc路由研究中，人们提出了多路径路由方法来解决上述问题。
多路径协议介绍。多路路由是指为任意一对节点同时提供多条可用的路径，并允许节点主机[或应用程序)选择如何使用这些路径。多路路由算法为节点间提供多条路径，并确保发往其中一条路径的数据经由该路径到达目的地。多路路由网络是其中的路由器执行多路路由算法的网络。从理论上证明了按需多路径拥有较长的路径存活时间和更可靠路由信息，而且拥有良好的性能，并能减少部分拥塞。因此近年来多路径研究得到广泛关注，主
要
分
为
2
大
类
：
多
路
径
被
动
路
由
(
如
DSDVM(Destination-Se-quencedDistance．VectorRoutingMulti．path))和多路径主动路由协议(SMRJ7j，AOMDVJ)。如基于被动路由DSDV基础上扩展DSDVM通过修改内部数据结构等方法获取多路径支持；基于主动路由DSR扩展的SMR，通过修改DSR路由发现机制，并通过目的节点获取最大不相交路径；出了基于AODV协议的多路径协议AOMDV。
DSDVM协议DSDVM是在DSDV基础上扩展的多路径路由协议。该协议通过获取和维护多条Quasi最短路径实现多路径路由协议。所谓Quasi最短路径是指该路径中除第1跳以外到目的节点距离最短的路径，Quasi多路径是指从源节点到目的节点的一系列Quasi最短路径集合。最短路径仅是Quasi最短路径的特例，称之为主路径，其他的Quasi最短路径称之为冗余路径，DSDVM通过在源节点把数据分布在Quasi多条路径上来实现负载平衡。DSDVM与DSDV不同之处在于内部数据结构和多路径计算。
8
第2章Ad-hoc网络的路由协议分类
内部数据结构。DSDVM跟DSDV类似，都是通过周期性跟相邻活动节点交换路由信息更新路由表，所不同的是内部数据结构。DSDVM每个节点的路由表中都包含如下的路由信息：目的节点地址，下跳地址(主路径的下跳地址)，主路径到达目的节点的跳数，目的序列号，前置节点地址和一个包含Quasi冗余路径下跳地址的集合。每次路由更新都把新检测到的相邻节点按照一定的计算添加到Quasi冗余路径。
多路径计算。DSDVM通过判断相邻节点(非主路径上的下跳地址)是否在主路径上，如果不是在主路径上，将该地址添加到下跳地址的链接表中，否则丢弃，从而实现无环多路径。
SRM协议。SRM是DSR协议的一个扩展，其研究侧重点是频繁发生的路由发现所带来的开销。协议的主要思想是为源节点和中间节点提供一条以上的替换路径(AlternateRoute)。由于替换路径与主路径是独立路径，当主路径失效时，数据传输不会被打断，而是换用替换路径来继续发送数据包，属于按需多路径路由协议。
路由发现。SRM的路由发现过程和DSR基本相似，不同的是，当第1个路由请求RREQ包到达目的节点后，目的节点除了向源节点发送路由应答RREP包外，还记录下这条路径作为主路径。对于随后到达的路由请求包，如果其中的路径和所记录的所有路径都是独立路径，目的节点就发送相应的路由应答包，同时记录下这条路径；否则，直接丢掉该路由请求包。这样既可以保证当主路径失效时，其他路径还可以发包(因为它们和主路径是相互独立的)，又避免了目的节点因发送路由应答包过多而带来不必要的网络拥塞。
路由维护。当中间节点检测到链路断开后，利用替换路径把数据包重新发送出去，并且向上游节点和源节点发送RRER，请求它们把包含该链路的路径删除；当源节点收到RRER后，使用以下两种路由策略重新做
路由发现：
1)只要收到路径断开消息，就重新做路由发现，这样可以获取最新的网络信息； 2)只有收到两条(或多条)路径都断开的消息后，才重新做路由发现，这样可以减少部分路由开销。SMR试验表明，使用第2种路由，发现策略性能较好。
AODVM协议。AODVM(AdHocOn．demandDistanceVectorMulti—path)多路路由协议也是在AODV的基础上进行扩展的，与AODV协议中直接丢弃RREQ包的拷贝不同，中间节点会将包含在这些包中的信息记录在一个表(RREQ表)中。对每个接收到的RREQ消息的拷贝，接收的中间节点将产生该RREQ消息的信源，该RREQ要去的信宿；把该RREQ的邻居，以及其他的一些额外信息记录传输到该RREQ表中，但不能直接向信源发送RREP消息。
9
电子科技大学成都学院课程设计论文
路由发现。AODVM路由发现阶段与AODV类似，当信宿从其某个邻居处接收到第1个RREQ包时，它便更新自己的序列号同时产生一个RREP消息。RREP包包含一个额外的域“LasthopID”，用来说明该RREQ的拷贝来自哪个邻居。该RREP包沿传输过该RREQ拷贝的路径反向发送到信源。当信宿从其他邻居处接收到该RREQ包的拷贝时，每次都更新其序列号，同时产生一个RREP包。同第1个RREP包一样，这些RREP包也包含对应的最后一跳节点的ID(LasthopID)。当一个中间节点从它的邻居处接收到一个RREP包时，它便从它的RREQ表中删除掉对应该邻居的表目，同时在路由表中增加一个路由表目，以 显示到己经发现的RREP包发起者(即信宿)的路由；然后该节点通过RREQ表，识别一条到信源最近的路径，将该RREP消息传输到相应的邻居。RREQ表中对应该邻居的条目即被删除。为了确保一个节点没有被多条路径共享，即保证路径的节点不相关，当节点侦听任一其他节点广播RREP消息时，它们便从RREQ表中删除对应该传输节点的条目。
路由维护。当一个中间节点接收到RREP消息而无法继续往前传输(其RREQ表所有下跳地址的路径都失效时)，便产生一个路由发现错误消息(RDER：RouteDiscoveryError)，并把该消息发送到将RREP消息发送给其邻居节点。邻居一旦接收到该RDER消息，便将RREP消息发送给另外的邻居，以便在可能时将RREP消息传输至信源。RDER消息的数量会受到限制，以避免该数据包的大量产生和交换。
其他多路径路由协议。MSR是在DSR基础上扩展的，利用中间节点和目的节点反馈多条路径，并使用路径探测来减少网络拥塞和网络延迟；AODV．BR在AODV基础上建立多条路径来为路由出错的数据包提供替换路径支持；通过在路由响应阶段重定向响应路径实现多条节点不相交路径；ARP通过路径拆分来实现多路径；提出一种基于多样性编码的方法来建立多条路径，并把数据包分发到多条路径发送，藉此来提高可靠性和发送率。M—MPRE提供了基于网眼的多路径寻径和包发送。AMR[2-23]使用网络最大流获取多条节点不相交路径，并利用多条路径并行或者并发发送数据来提高网络流通量和负载平衡。
多路径协议应用。以上多路径协议主要集中于如何提高网络传输率，降低网络延迟以及提高网络负载平衡，但多路径协议在QoS、能源、安全等方面也有自身的优势。如TBP提出通过发送选票来并行探测多条较优的路径，并通过资源预留方式实现QoS；提出在多项式复杂度内找到多条链路不相交或者节点不相交路径减少源消耗。文献[11]提出一种基
10
第2章Ad-hoc网络的路由协议分类
于并行网络流方式的自适应多路径路由协议，并通过时间限制来避免恶意DOS攻击，以提高网络安全性。
2.3 几种典型的无线自组网路由协议
2.3.1 目的序列距离矢量路由协议DSDV
DSDV(Destination-Sequenced Distance-Vector)是基于经典Bellman-Ford路由选择过程的改进型路由表算法。DSDV以路由信息协议为基础。是无线自组网协议发展较早的一种。
使用DSDV时，网络中的每一个移动节点都需要维护一个路由表。路由表表项包括目的节点、跳数和一个由目的节点注明的序列号，序列号能帮助节点区分有效和过期的路由信息，并可防止路由环路的发生。标有更大序列号的路由信息总是被接收。如果两个更新分组有相同的序列号，则选择跳数最小的，使路由最优（最短）。每个节点必须周期性地与邻节点交换路由信息，当然也可以根据路由表的改变来触发路由更新。路由表更新有两种方式：一种是全部更新，即拔掉更新消息中将包括整个路由表，主要应用于变化较快的情况；另一种是增量更新，更新消息中仅包含变化的路由部分，通常适用于变化较慢的情况。
2.3.2 按需平面距离矢量路由协议AODV
AODV(Ad hoc On-demand Distance Vector Routing)由DSDV发展而来，不同的是AODV为反应式路由协议。源节点首先广播一个携带目的节点信息的路由分组（RREQ），其邻居节点依次向周围节点广播此路由分组，广播RREQ前会建立此节点到源节点的路由，直到路由分组到达目的节点或者一个中间节点，这个节点包含目的节点的路由信息，就不再广播RREQ。此过程中，会建立一个从源节点到目的节点的反向路由，也就是从目的节点到源节点的路由。然后该节点将沿着反向路由发回一个RREP，RREP到达源节点后路由发现过程结束。为避免路由循环，每一个路由分组中都包括一个sequence ID（SID）作为唯一标识，如果一个节点收到一个SID比它当前保留的SID小的数据包，表明该数
11