自组织网络Ad Hoc之AODV协议详解

一、AODV 概念

AODV 是按需路由协议，当一个节点需要给网络中的其他节点传送信息时，如果没有到达目标节点的路由，则必须先以多播的形式发出 RREQ 报文，邻居节点收到 RREQ，首先判断目标节点是否是自己，如果是，则向发起节点发送 RREP，如果不是，首先在路由表中查找是否有到达目标节点的路由，如果有，则向源节点单播 RREP，否则继续转发 RREQ 进行查找。

在网络资源充分的情况下，AODV 协议可以通过定期广播 HELLO 报文来维护路由，一旦发现某一个链路断开，节点就发送 ERROR 报文通知那些因为链路断开而不可到达的节点，删除相应的记录或者对已经存在的路由修复。

AODV 特点如下：

• 节点只存储需要的路由

• 尽量减少广播的需要

• 减少内存需求和不必要的重复

• 对活动路由中链路断裂的快速响应

• 使用目标序列号维护的无循环路由

• 可扩展到大量节点群

二、AODV 功能

AODV 是在多个移动节点中建立和维护一个动态的、自启动的、多跳路由的专属网络，使得移动节点能够快速获得通向新的目的节点的路由，并且节点仅需要维护通向邻居节点的路由，更远节点的路由信息则不需要维护。

其路由表字段包括：

• 目的节点IP地址
• 目的节点序列号
• 目的节点序列号的有效标志位
• 下一跳节点IP地址
• 本节点到达目的节点的跳数
• 前驱节点列表
• 生存时间
• 网络层接口
• 其他的状态和路由标志位（比如：有效，无效，可修复，正在修复）。

路由表特征如下：

• 路由表每项只记录下一跳路由信息，而不是整条路由信息，简化了路由表的建立和维护。

• 源节点和目的节点都维护各自的序列号，序列号是用来标识路由信息新旧程度，当源节点发起路由请求RREQ或者目的节点返回路由应答RREP时，都要更新各自的序列号。

• 中间节点依据序列号的大小判断路由的新旧。

三、AODV 术语

• 发起节点：发出 AODV 路由请求消息的节点

• 转发节点：愿意为其他节点转发数据包的节点，转发节点会将数据包转发给下一个节点。

• 目的节点：当一个节点看到自己的 IP 地址和数据包 IP 头特定字段的 IP 地址一样时，认定自己是数据包的目的节点。

• 活跃路由：能够有效通向目的节点的路由，只有活跃路由能够转发数据包

• 返回路由：用于转发回复包的路由，就是从目的节点返回到发起节点的路由。

• 无效路由：有效路由失效以后，会作为无效路由在路由表中保存一段时间，并不能转发数据包。

四、AODV 消息格式

AODV 有三种基本的协议报文类型：RREQ（路由请求）报文、RREP（路由应答）报文和 RRER（路由错误）报文。

4.1 RREQ 路由请求报文

在两个节点之间的路由有效，通信正常的情况下，AODV 路由协议不起任何作用，只有当源节点 S 需要向目的节点 D 发送数据包，但是又没有 D 节点的路由入口时，才会发起路由请求（RREQ）。

当 RREQ 在网络中传播时，中间节点会更新各自到源节点的路由，称为反向路由，RREQ 请求报文中包含源节点以前记录的到目的节点的序列号，但是此序列号可能不是最新的，中间节点如果有到目的节点的路由时，只有该节点记录的目的节点的序列号比 RREQ 中目的节点序列号更大，才认为这条路由是有效的。

报文格式说明：

• Type：1
• J：加入标志，为多播保留。
• R：修复标志，为多播保留。
• G 免费路由回复标志：是否向目标节点IP地址域指定的节点发一个免费路由回复消息。
• D 仅允许目的节点回复标志：标志位则仅允许目的节点回复本条路由请求。
• U 未知序列号：指的是目标节点序列号未知。
• Reserved：填充0，接收端忽略此字段。
• 跳数：从发起节点到处理该请求的节点的跳数。
• 路由请求标识：这是一个序列号，用它和源节点IP可以唯一标识一个RREQ消息。

4.2 RREP 路由应答报文

当 RREQ 最终到达目的节点时，目的节点通过向该反向路由（RREQ 传播路线）发送 RREP 应答报文，建立通向目的节点的前向路由。

只有以下的情况节点才会产生 RREP 报文：

1. 该节点本身就是目的节点。

2. 该节点为中间节点，但是它有通向目的节点的活跃路径。

当 RREP 传播到源节点时，中间节点根据该 RREP 更新他们各自指向目的节点的路由信息。节点只对第一次收到的 RREQ 发送 RREP 应答报文。

报文格式说明：

• Type：2
• R：修复标志，用于多播
• A：需要确认
• Reserved：填充0，接受端忽略此字段。
• Prefix Size：前缀长度，如果非零，代表下一跳节点可以作为任有具有相同路由前缀的节点被请求时的目的节点。
• 跳数：从发起节点到目的节点的跳数。
• 生命期：路由生命时间，在这个时间内，接收RREP的节点会认为这条路由是有效的。

4.3 RERR 路由错误报文

报文格式说明：

• Type：3
• N：不必删除标志，当一个节点已经对这条连接做了本地修复时，上游的几点就不用删除这条路由。
• Reserved：保留字段，填充0，接收端不做处理。
• DestCount：本消息内包含的不可达的目的节点的数目，至少为1。
• Unreachable Destination IP Address：因为连接断开而不可达的目的节点的IP地址。
• Unreachable Destination Sequence Number：路由表项里不可达目的节点的序列号。

五、AODV 工作过程

5.1 AODV 工作流程图

5.2 路由发现过程

• 广播 RREQ 路由请求帧。

• 中间节点更新各自到源节点的路由表。

• 如果收到 RREQ 的节点不是目的节点，并且没有到达目的节点的更新的有效路由，则转发该 RREQ。

• 中间节点维护指向路由源节点的反向路由。

• 目的节点或存在到目的节点有效路由的中间节点产生 RREP 路由应答帧。

• RREP 通过之前建立的反向节点单播至源节点。

• 源节点收到 RREP 应答帧，至此源节点可以向目的节点发送数据包。

5.3 路由发现算法

源节点：应用层有数据发送请求，并且指向目的节点的路由有效，直接通过该路由发送数据包，如果没有到达目的节点的有效路径，则产生 RREQ 广播帧，RREQ 的序列号、ID 字段加1，将源节点的 IP，序列号、目的节点的 IP、序列号等信息添加到 RREQ 中，广播至网络。

中间节点：如果中间节点路由表中记录的到目的节点的路由有效，并且记录的目的节点的序列号大于或者等于 RREQ 中的目的节点序列号，则该中间节点可以产生路由应答帧。如果该中间节点不产生应答帧，更改RREQ 中的目的节点序列号至当前最大，跳数字段加1，然后转发。

目的节点：目的节点的序列号加1，产生 RREP 应答帧（包括源节点 IP、目的节点 IP 和更新后的序列号），单播发送至源节点。

5.4 路由维护算法

Hello 消息：Hello 消息帧就是 TTL=1时的 REEP 帧，Hello 消息帧用于检测活跃路径上相邻节点的链接状况。只有当某节点位于某活跃路径之上时，他才能发送 Hello 消息帧。活跃路径节点以 HELLO_INTERVAL 为周期发送 Hello 消息。

• 在DELETE_PERIOD的时间内没有收到来自邻居节点的Hello消息，则认为 该链路失效；发起一次指向该邻居节点的局部修复。

• 路由修复超时以后，路有错误信息RERR向源节点和目的节点发送。

• RERR在传播过程中，各中间节点删除该失效路径上相应的路由信息。

5.5 路由信息新旧判断

AODV 依赖网络中每个节点维护自身的序列号，源节点在广播路由请求帧 RREQ 之前要更新自己的序列号，即将序列号加1，目的节点在产生 RREP 应答帧之前也要将自身的序列号加1，每个节点在对各自的序列号加1的时候，是将其视为无符号数进行的。

通过比较来自目的节点路由控制帧中的序列号 SN1 和本节点维护的目的节点的序列号 SN2，就可以确定本链路的新旧程度。如果 SN2-SN1<0(有符号数相减)，说明路由表中的维护信息已过时，应将路由信息更新至路由控制帧最新的路由信息。

六、拥塞控制

源节点在发送 RREQ 后，在规定的时间内没有收到来自目的节点的RREP时，他可以选择再次发送 RREQ 路由请求帧。

在尝试了 RREQ_RETRIES 次之后，如果依旧收不到 RREP，则在路由表中标记该目的节点不可达，通知应用层。每次在重新发送 RREQ 请求帧时，等待 RREP 应答帧的时间要在原来时间的基础上乘以2，避免拥塞。