1. AODV

自适应按需距离矢量路由（Ad hoc On-Demand Distance Vector，AODV）算法能够实现动态的、自启动的、多跳路由，让希望建立和维护自组网的移动节点之间实现通信。AODV允许移动节点为新目的地快速获得路由，并且不需要节点维护到不在活跃通信中的目的地的路由。AODV允许移动节点及时响应链路中断和网络拓扑的变化。

AODV算法的操作是无环的，通过避免贝尔曼-福特（Bellman-Ford）的“计数至无穷”问题，在自组网拓扑发生变化时（通常是节点在网络中移动时）实现快速收敛。当链路断开时，AODV会通知受影响的节点集合，使它们能够使失去连接的路由失效。

AODV的一个显著特点是它为每个路由条目使用目标序列号。目标序列号由目的地节点生成，并与发送给请求节点的任何路由信息一起包含。使用目标序列号可以确保无环路由，并且编程简单。在选择到达目的地的两条路由时，请求节点需要选择具有较大序列号的那条路由。

1.1. 相关术语

• active rout：AODV中，一条指向目的地的路由，其路由表项被标记为有效，称为活动路由（active route）。只有活动路由才能用于转发数据包。

• broadcast：广播意味着向 IP 有限广播地址 255.255.255.255 发送。广播数据包可能不会被盲目转发，但广播对于实现 AODV 消息在整个自组织网络中的传播是有用的。

• destination：一个需要传输数据包的 IP 地址。与”目标节点”相同。当节点的地址出现在 IP 报头的相应字段中时，节点知道它是典型数据包的目标节点。目标节点的路由由 AODV 协议提供，它在路由发现消息中携带所需目标节点的 IP 地址。

• forwarding node：一个同意转发目标为另一个节点的数据包的节点，通过将它们重新传输到沿着使用路由控制消息建立的路径上更靠近单播目标的下一跳来实现。

• forward route：一条发送数据包的且根据路由发现从一个节点发往下一个更靠近目标节点的路由。

• invalid route：一条已过期的路由，由路由表项中的无效状态表示。无效路由曾经存储先前有效的路由信息。无效路由不能用于转发数据包，但它可以为路由修复提供有用的信息，同时还可为未来的RREQ消息提供参考。

• originating node：一个发起AODV路由发现消息的节点，该消息将被处理并可能被其他自组织网络中的节点转发。例如，发起路由发现过程并广播RREQ消息的节点被称为RREQ消息的起始节点。

• reverse route：一条建立用于将回复（RREP）数据包从目的地或者拥有到目的地路由的中间节点回传给发起者的路由。

• sequence number：一个单调递增的数字，由每个发起节点维护。在AODV路由协议消息中，其他节点使用它来确定来自发起节点的信息的新鲜程度。

• valid route：同 active rout

1.2. 报文结构 Message Formats

1.2.1. Route Request (RREQ) Message Format

Type:1

J:Join Flag；预留给组播使用

R:Repaire Flag；预留给组播使用

G:Gratuitous RREP flag

D:Destination only flag；表示只有目的地可能响应此RREQ

U:Unknown sequence number；指示目的序列号未知

Reserved:Sent as 0；接收时忽略

Hop Count:从发起者IP地址到处理请求的节点的跳数。

RREQ ID:当与原始节点的IP地址结合使用时，唯一标识特定RREQ的序列号。

Destination IP Address:需要路由的目的IP地址。

Destination Sequence Number:指向目的地节点的，当前最新序列号。

Originator IP Address:发起路由请求的节点的IP地址。

Originator Sequence Number:在指向发起路由请求的节点的路由表条目中，当前正在使用的序列号。

1.2.2. Route Reply (RREP) Message Format

Type:2

R:Repaire Flag；预留给组播使用

A:Acknowledgment required

Reserved:Sent as 0；接收时忽略

Prefix Size: 如果前缀大小非零，具有相同路由前缀的节点可以共享该下一跳，以便将数据包传输到目的地

Hop Count:从发起者IP地址到处理请求的节点的跳数。

Destination IP Address:需要路由的目的IP地址。

Destination Sequence Number:指向目的地节点的，当前最新序列号，与路由相关联

Originator IP Address:发起路由请求的节点的IP地址。

Lifetime:在接收到路由回复（RREP）之后，节点会将该路由视为有效一段时间（以毫秒计），在这段时间内，该路由可用于数据传输。

1.2.3. Route Error (RERR) Message Format

1.3. AODV具体操作

1.3.1. 路由表

每个节点维护自己的路由表

1.3.2. 维护Sequence Numbers

每个节点的每个路由表项都必须包含关于维护该路由表项的目的节点IP地址的序列号的最新信息。这个序列号就是目的序列号。

当一个节点接收到与该目的地相关的新的（即非过时的）RREQ、RREP或RERR消息中的序列号信息时，它会进行更新。AODV依赖于网络中的每个节点拥有并维护其目的序列号，以确保指向该节点的所有路由都不会出现环路。

以下情况，节点会改变目的序列号：

1. 一个节点发起RREQ之前，它必须增加序列号。

2. 节点生成RREP消息以响应RREQ消息之前，需要更新序列号的值为当前序列号和RREQ消息中序列号的较大值。

3. 节点收到AODV控制消息，即RREQ、RREP、RERR。若控制消息中的序列号更大，就用控制消息中的路由更新，此时序列号也选用更大的。如果一样大，看跳数，选跳数短的。反之，如果自己的序列号更大，即接收到的序列号减去当前序列号小于0，此时接收到的AODV信息必须被丢弃。因为跟节点当前保存信息相比，接收到的信息更陈旧。

4.到目的节点的路径过期或者损坏。在没有收到下一节点回复的RREP-ACK或者链路层通知发生链路损坏时，需要把所有受链路影响不可达的路由表条目中的目的序列号都加一，并设置标志位不合法，这样可以避免后续该节点重新使用损坏的链路。

1.3.3. 生成路由请求

RREQ消息的构建方式如下：

当一个节点找不到一个可用路由时，他就会广播一个RREQ消息。出现这种情况可能是这个节点并不知道有这个目的节点，也有可能是有效路由过期了或被标记为无效。

无法路由时，源节点打开定时器，构建好RREQ消息后，想IP地址255.255.255.255发送RREQ消息。发送后等待NET_TRAVERSAL_TIME毫秒内等待相关节点恢复RREP消息，如果收到，过程结束。如果超时仍未收到，则采用二进制指数退避方法更新等待时间。重新开启定时器和发送RREQ消息，直到发送次数超过RREQ_RETRIES。数据被丢弃并通知上层协议无法建立连接。

TTL?

控制路由请求消息的转播

当节点收到RREQ消息，他会判断在过去的PATH_DISCOVERY_TIME时间内判断是否收到具有相同源IP地址和RREQ ID的RREQ消息，如果有，则丢弃新收到的RREQ消息，过程结束。

控制

2. 参考文献

[1]史美林,荚春.自组网路由协议综述[J].通信学报,2001(11):93-103.

[2]Johnson, David B., and David A. Maltz. “Dynamic source routing in ad hoc wireless networks.” Mobile computing (1996): 153-181.

[3]Perkins, Charles, Elizabeth Belding-Royer, and Samir Das. Ad hoc on-demand distance vector (AODV) routing. No. rfc3561. 2003.