课堂论文

第2章Ad Hoc网络路由协议分析

化，在节点拓扑结构变化频繁的网络环境下容易出现路由更新速度跟不上网络拓扑变化速度的情况，协议始终处于不能达到收敛的状态，严重的影响到网络的性能。

下面简要介绍一下几种典型的Ad Hoc表驱动路由协议：

DSDV（Destination Sequenced Distance Vector）协议[24]是一种无环距离矢量路由协议，采用了经典的Bell-Ford路由算法，并做了相应的改进。通过目的节点序列号来解决路由环路和无穷计算问题。该协议减小了协议的负荷以及路由收敛的时间，然而不能够支持节点的快速移动，也不具有扩展性。

WRP（Wireless Routing Protocol）[25]也是一种距离矢量路由协议，网络中的每个节点维持4个表结构，分别是距离表、路由表、链路权值表和消息重传表。该算法特点是节点每次探测到邻居的链路改变时，检查所有邻居的一致性。这种方式一致性检查可以消除环路的情况并且收敛更快。

OLSR（Optimized Link State Routing）[26]协议是由IETF MANET工作组提出的一种表驱动式的链路状态路由协议，是对纯链路状态算法进行优化而形成的，它采用多点接力（Multipoint Relays）机制缩小了控制分组泛洪范围，OLSR在稳定状态下是无环的。OLSR非常适用于大型密集的移动网络。网络规模越大节点越密集，与传统的链路状态算法相比就越能取得最佳化。

2. 按需路由协议

按需路由协议又称反应式（或被动式）路由协议。这类路由协议的基本思想是：当源节点需要发送数据包且当前路由表中没有通往目的节点的路由时才按需查找通往目的节点的路由。在这类路由协议中，网络中的节点不需要实时地维护路由信息，也不需要实时的了解当前网络的拓扑情况和保持各个节点路由信息的同步性，只有当向目的节点发送数据包时，源节点才激活路由发现机制寻找相应的路由。与表驱动式路由协议相比，反应式路由协议的开销较小，路由协议效率较高。这类路由协议的缺点是由于发包时才进行路由发现过程，数据报传送所需的时延较大。

下面简要介绍一下具有代表性的Ad Hoc按需路由协议：

DSR（Dynamic Source Routing）[27]路由协议是一种基于源路由方式的按需路由协议。每一个给定路线的数据分组都在头部带有完整有序的此分组必须经过的节点列表，还引入了路由缓冲等优化技术。DSR不需要周期性的发送广播信息，

11

客户服务系统的设计与开发

节省了节点能量和网络带宽，尤其是没有节点要发送数据时，网络中没有通信开销；支持节点睡眠，并且支持中间节点回答，能使源节点快速获得路由，但同时会引起过时路由问题。缺点是当网络的规模较大时，每个数据分组都携带了路径信息，造成开销过大而影响可扩展性。

AODV（Ad Hoc On-Demand Vector Algorithm）[28]是在DSDV和DSR的基础上发展而来的按需路由协议。它借鉴了DSR中按需进行路由发现和路由维护机制，以及DSDV中的逐跳路由、序列号、定期/触发广播。AODV协议基于传统的距离向量路由机制，通过使用目的序列号有效地防止了循环的发生，解决了传统的基于距离向量路由协议存在的无限计数问题。支持中间主机回答，能使源主机快速获得路由，但需要周期性地广播报文，要消耗一定的电池能源和网络带宽，还存在过时路由问题。

TORA（Temporally Ordered Routing Algorithm）[29]协议是具有高度自适应性的分布式路由算法，它的原理是把路由更新信息限制在一个很小的范围之内，这个范围是以发生状态变化的节点为中心的一个节点集合，这样就可以快速地跟踪节点的变化。每个节点维护有关相邻节点的路由信息，协议具有路由产生、路由维护和路由删除三个基本功能。TORA协议比较适合高度动态移动、多跳的无线网络，但是存在的一个问题是当多个节点同时进行选路和删除路由时会产生路由振荡现象。

3. 混合路由协议

除了上面介绍的两种路由协议之外，还有将按需和表驱动结合起来的混合式路由协议。这类协议综合了按需和表驱动的优点，但是缺点是协议比较复杂，计算开销较大。其主要的代表性协议为ZRP协议[30]。

ZRP协议是第一个利用分簇结构混合使用按需和表驱动路由策略的自组网路由协议。在ZRP中，簇被称作域（Zone）。域形成算法较为简单，它是通过区域半径（以跳数为单位）参数指定每个节点维护的区域大小，即所有距离不超过区域半径的节点都属于该区域。一个节点可能同时从属于多个区域。将整个网络划分成个N互相重叠的区域。在区域内部，采用IARP（IntrAzone Routing Protocol）协议，区域间路由采用IERP（IntErzone Routing Protocol）协议。此外，在ZRP路由中还使用到一种BRP（Bordercast Resolution Protocol）协议，用于降低区域间路由发现过程中的冗余转发。

12

第2章Ad Hoc网络路由协议分析

ZRP协议的性能很大程度上由区域半径参数值决定。通常，小的区域半径适合在移动速度较快的节点组成的密集网络中使用；大的区域半径适合在移动速度慢的节点组成的稀疏网络中使用。目前ZRP采用预置固定区域半径值的做法，限制了它的可适应性。

2.3 AODV路由协议分析

2.3.1 AODV路由协议原理

AODV路由协议是一种按需的距离向量路由协议，具有按需路由协议的特点，即在AODV路由协议中，网络中的每个节点在需要进行通信时才发送路由分组，而不会周期性地交互路由信息以得到所有其它主机的路由；同时具有距离向量路由协议的一些特点，即各节点路由表只维护本节点到其他节点的路由，而无需掌握全网拓扑结构。

AODV路由协议中有三种类型的消息控制帧：路由请求RREQ，路由应答RREP和路由错误RERR消息。当源节点需要发送数据而又没有到目的节点的有效路由时，启动一个路由发现过程：向网络广播一个路由请求分组RREQ，AODV允许中间节点响应RREQ，当收到请求的中间节点或目的节点有一条“足够新”的路由到达目的地时（“足

够新”的意思是这条路由对应的目的序列号大于或等于RREQ中的目的序列号），中间节点或目的节点以单播的方式向源节点返回一个RREP分组，RREP沿着刚建立的逆向路径传输回源节点，源节点收到该RREP后则开始向对应目的节点发送数据。在数据传输过程中，当中间节点检测到一条正在传输数据的活动路由的下一跳链路断开或者节点收到去往某个目的地节点的数据报文，而节点没有到该目的地节点的有效路由时，中间节点向源节点单播或多播路由错误消息RERR，源节点收到RERR后就知道存在路由错误，并根据RERR中指示的不可达目的地重新找路。

2.3.2 AODV路由协议路由表结构

AODV路由协议中定义的路由表项包含以下信息： 1）目的节点IP地址

13

客户服务系统的设计与开发

2）目的节点序列号 3）目的节点序列号有效标志 4）下一跳节点IP地址 5）跳数值 6）先驱链表指针 7）生存期值 8）状态标志

每个表项都具有不同的目的节点IP地址，以此作为区别和查找网络路由的关键字。目的节点的序列号可防止网络产生环路，只有当收到的RREP和RREQ中传送的序列号比本节点对应路由表项中的目的序列号大时才能被接收并用于更新路由表项。目的节点序列号有效标志显示此路由表项的目的序列号是否有效。下一跳节点IP地址域保存到达目的节点的路径上的下一跳节点的地址。跳数值域保存了从本节点到达目的路由器所需要的跳数（每经过一个无线路由器则计算一跳）。先驱链表指针指向使用此路由表项的所有可能的邻居节点地址。生存期值域保存了该路由表项的过期时间或者是删除该表项的时间。状态标志域则表明该表项是有效或者是已过期又或是已删除。当状态标志是有效时，生存期值表示的是该表项的过期时间；当状态标志是已过期时，生存期值域表示的是删除该表项的时间。

对路由中的目的序列号的管理是避免路由环路出现的关键。一个节点在以下两种情况下增加自己的序列号：

1）在节点产生RREQ之前，立即增加它自己的序列号

2）在目的节点产生一个RREP对RREQ进行应答之前，必需更新自己的序列号，更新值为当前序列号与RREQ中的目的序列号之间的最大值。

当链路失效或者某个节点已经无法提供其本身目的序列号信息的时候（如脱离移动Ad Hoc网络或者关机），则将使中断链路作为下一跳的表项的目的序列号加1，并将状态标志域置为“无效”，使对应的网络路由表项失效。当节点收到任何关于受影响目的地的足够新的路由信息时，节点按照更新报文中的信息来更新路由表项。

2.3.3 AODV路由协议控制分组格式

AODV路由协议包括3种基本的控制分组：路由请求（RREQ）分组、路由应

14