[最新版]基于aodv的无线传感器路由协议的研究毕业论文

4.3.4 RREP-ACK分组格式

表 4.4 RREP-ACK分组格式

Type 4

Reserved 保留字段，设为0

4.4 AODV路由算法的原理

AODV路由协议是一种按需距离矢量路由，和表驱动路由协议不同，按需路由协议只有需要一个源节点到目的节点的路由，或者当一个节点想要加入一个多播组才进行路由发现[12]。AODV路由在Ad Hoc移动网络中单播，组播或广播的移动网络协议。当源节点需要一条通往目的节点，将发起一个网络路由发现过程。当寻找到一条路径，或所有可能的路径已被检查后，路径发现过程完成。一旦路径建立，路由表将维持到不再需要该路径、该条路由失效或超过生存期。AODV路由查找使用广播机制。除了源路由，AODV协议还依靠中间节点动态创建路由表项。该协议借用DSDV中的目的序列号机制，每个节点维护一个单调递增序列号计算器，用它来标记在缓存中路由的新旧。

4.5 AODV路由算法基本操作

4.5.1 维护序列号

一个节点只有在以下3种情况中会改变路由表项中的目的节点序列号： (1) 它自己本身就是目的节点；

(2) 它收到了一个更新的有关目的节点序列号的信息。 (3) 到目的节点的链路终止或中断。

目的序列号会在接收到RREQ,RREP或RERR中新的信息时更新。AODV依靠网络中的每个节点去保存和维护它的目的节点序列号，以保证没有环路。一个目的节点会在两种情况下增加它自己的序列号：

(1) 当需要对同一个目的节点启动新的路由发现(route discovery)时，它必须增加它自己的序列号。这会防止与之前建立的到源节点的反向路径出现冲突。

(2) 当目的节点即将发送的RREQ消息响应一个RREP，必须更新自己的序列号，使当前的RREQ分组的序列号和目的节点是序列号最大的一个[13]。

为了保证关于目的节点的信息不会变得陈旧，节点比较当前的序列号和从分组中获得的序列号。这种比较必须使用32位的有符号整数，这是为了实现序列号的轮转。如果新获得的序列号减去当前的序列号结果小于0，那么新获得的序列号就会被忽略。

另一种会改变路由表项中目的节点序列号的情况是当去往下一跳的链路中断或终止时，节点会把相应的路由项置为无效，同时增加这些路由项的序列号。 4.5.2 产生路由请求

当目的节点未知、原路径失效或终止，且节点（即源节点）在需要发现路由的时候会发送RREQ分组。RREQ中的目的节点序列号域先设为最后所知道的序列号，若序列号未知，则必须设置未知序列号标识。节点自己的序列号在复制到RREQ中后自我增值。RREQ ID域设为最后使用的RREQ ID加一。跳数域设为0。

广播RREQ消息前,源节点将缓存的RREQ ID和自己的IP地址的PATH_DISCOVERY_TIME长时间，这样，当它从邻居节点接收到相同的RREQ分组，不要发送，处理重复[14]。

当源节点期望能和目的节点进行双向通信时，源节点会设置G标识位。这样目的节点就能接收到反向路径的通报。

一个源节点每秒内不应发送超过设置的请求分组带宽的RREQ。如果在等待了NET_TRAVERSAL_TIME毫秒后节点还没收到相关路由信息，节点会再次尝试发送RREQ,最多尝试RREQ_RETRIES次。

为了减少网络的拥塞，同一个节点重复的请求会利用利用二元指数后退算法。即节点第一次发送RREQ时，等待NET_TRAVERSAL_TIME毫秒，随后的每次尝试等待的时间都是前一次等待时间乘2。 4.5.3 路由请求消息的控制传播

为了防止的RREQ分布扩展至整个网络，源节点将使用扩展环式搜索技术。在这种技术，为源节点的RREQ分组的IP中初始化一个TTL=TTL_START，并设置收到RREP时间为RING_TRAVERSAL_TIME毫秒。用来计算RING_TRAVERSAL_TIME的TTL_VALUE设置为IP头中TTL的值。当RREQ超时，重发RREQ时，TTL增加TTL_INCREMENT。如此继续，直到TTL达到TTL_THRESHOLD，此后的重试中设TTL=NET_DIAMETER。每一次等待RREQ的计时时间都为RING_TRAVERSAL_TIME，当需要重试的分组跨越整个Ad hoc网时，可以把TTL_START和TTL_INCREMENT都设为NET_DIAMETER。

当需要对同一个目的节点启动新的路由发现时，RREQ中的TTL将被初始化，成

为原有失效的跳数加上TTL_INCREMENT。

一个过期的路由表项在DELETE_PERIOD的时间内都不能被擦除。另外还能够设置更长的擦除时间。任何一个正在等待RREQ的路由表项在2*NET_TRAVERSAL_TIME的时间内都不能被擦除。 4.5.4 处理和转发路由请求

当一个节点接收到RREQ消息时，它首先创建或更新没有有效的路由表项。然后查看在至少PATH_DISCOVERY_TIME是否收到相同的源IP地址和RREQ ID消息的RREQ分组，如果有的话，忽略目前收到的RREQ分组。当收到的RREQ不被忽略时，首先把RREQ中的跳数增1，然后在路由表中搜寻到源节点的反向路径，使用最长匹配原则，如果有需要，则创建新的反响路由表项，或者用RREQ中的源节点序列号更新原有路由表项。当反向路径被创建或更新时，将会执行下面的操作：如图4.5图所示。

(1) 将RREQ消息源节点序号的和相对应的反向路由中的目的节点序列号作比较，如果前者比后者大，前者将取代后者。

(2) 路由项的有效序列号域被设为真。

(3) 路由项的下一条设为向该节点传送RREQ的节点，这个从IP头部中的源地址IP中获得。

不管何时收到一个RREQ,反向路由项的生存期都会被设为ExistingLifetime和MinimalLifetime中的较大者，其中

MinimalLifetime=(当前时间+2*NET_TRAVERSAL_TIME. 2*HopCount*NODE_TRAVERSAL_TIME).

如果一个节点不产生一个RREP，且收到的RREQ的IP头中的TTL大于1，则这个节点向它的每一个接口用255.255.255.255作为目的地址广播RREQ。这些RREQ的TTL减1，而跳数则增1。最后，目的节点接收到RREQ分组设置为自己的节点和目的节点序列号中最大的序列号值。然而，即使收到的RREQ目标节点序列，它比目前的保存自己的目标序列号大，也不能修改其保存的值。

如果一个节点会产生RREP，则可忽略它收到的RREQ。注意，如果一个中间节点对每一个RREQ都作出回复，那么目的节点可能收不到任何路由发现的信息。在这种情况下，目标节点无法从RREQ分组中获取源节点的路由。这将导致目标节点也该发起路由发现过程。为了避免这种情况，当目的节点可能需要一条到源节点的路径时，源节点会设置RREQ中的G标志域。当一个节点收到设置了G域的RREQ，当它回复RREP

给源节点时，它也必须同时单播一个非必要RREP给目的节点。

开始建立或更新上一跳的无效序列号的反向路径是否收到带相同源IP和RREQ IP 的RREQ Y丢弃新收到的RREQNRREQ中跳数值加1把RREQ源IP地址序列号作为路由表项中的目的序列号路由表中下一跳设置为向他发出RREQ的节点跳数从RREQ中拷贝（加1后的值）结束

图4.5 节点收到RREQ处理过程

4.5.5 产生路由应答

一个节点在以下2种情况会产生RREP： (1) 它本身就是目的节点

(2) 它有一个有效的路由到达目的节点，而路由表项的目标序号大于等于RREQ消息序列数目，且D标志未设置。

当产生RREP时，节点复制RREQ中的目的节点IP地址和源节点序列号到RREP中的相应域中，其余的操作，视上述两种情况有细微的不同，下面将作仔细的说明。

因为RREP是反向发送到源节点，因此在每一跳的过程中，跳数都会被增1。 因此，当RREP到达源节点，源节点跳数表示到目的节点的距离。 4.5.5.1 目的节点产生的RREP