基于嵌入式Linux的AODV路由协议设计与实现*

周锦阳 宋 广

（92785部队 葫芦岛 125200）

1 引言

随着信息技术的不断发展，人们对移动通信的需求越来越强。传统移动通信网络一般基于预设基础设施，对于某些特殊场合，预设基础设施不可能存在。比如，战场上部队快速展开和推进、地震或水灾后的营救、野外科学考察等［1]。这就需要一种能够快速部署、无需基础设施、组网便捷的移动通信网络，即移动自组织网络。

移动自组织网络作为一种无中心、分布式和自组织的无线移动通信网络，源自美国夏威夷大学于1968年构建的无线自组织网络—ALOHA系统［2]，其应用领域包括传感器网络［3]、灾后紧急救援［4]、车辆通信和无线局域网等［5～6]。移动自组织网络的一种重要研究领域就是路由技术，为了适应不同应用场合，研究人员设计了许多路由协议［7]。其中AODV路由协议是IETF推荐的无线自组织路由协议之一，它简单实用且性能优越［8]。

本文依托嵌入式平台，提出了一种基于Linux系统的AODV路由协议实现方法，并将AODV路由协议应用于移动自组织网络视频通信中。通过路由协议测试，验证了所设计AODV路由协议通信的稳定性和及时性，为进一步探索和研究相关内容提供有益参考，具有重要的工程应用价值。

2 AODV路由协议

AODV路由协议作为按需路由协议［9]，该协议依据通信需求按需启动路由发现过程，其节点路由表和网络拓扑结构按需建立，所以节点路由表内容可能仅为整个网络拓扑结构的一部分。相对于先应式路由协议，按需路由协议具有路由开销小、节省网络带宽资源等优点，缺点为传播时延较大［10]。

AODV路由协议可分为路由建立和路由维护两个过程［11]。当源节点需要与目的节点通信，但路由表无到目的节点路由时，源节点启动路由建立过程。路由建立过程采用洪范方式，向全网广播路由请求分组。当发现通信链路中断时，节点启动路由维护过程。

3 AODV路由协议设计

本文设计的AODV路由协议包括四种控制报文：路由请求（RREQ）报文、路由应答（RREP）报文、HELLO报文和路由出错（RERR）报文。RREQ报文和RREP报文用于自组织网络的路由建立，HELLO报文和RRER报文用于自组织网络的路由维护。

3.1 控制报文设计

1）RREQ报文

RREQ报文格式如图1所示，包括Type字段、跳数、目的节点IP地址、源节点IP地址、源节点序列号及保留字段，总共16个字节。

图1 RREQ报文格式

2）RREP报文

RREP报文报文格式如图2所示，包括Type字段、跳数、目的节点IP地址、源节点IP地址、目的节点序列号及保留字段，总共16个字节。

3）HELLO报文

HELLO报文格式如图3所示，包括Type字段和保留字段，总共4个字节。

4）RERR报文

RERR报文格式如图4所示，包括Type字段、失效IP个数及失效IP地址。

图2 RREP报文格式

图3 HELLO报文格式

图4 RERR报文格式

3.2 报文处理策略设计

3.2.1 RREQ报文处理策略

RREQ报文用于建立从目的节点到源节点的反向路由，其处理策略包括报文发送策略和报文接收处理策略。

图5 RREQ报文发送策略

1）RREQ报文发送策略

当源节点需与目的节点进行通信，但其路由表中没有到达目的节点的路由时，源节点会启动RREQ报文的发送策略。RREQ报文发送策略如图5所示。如果在规定时间内收到目的节点回复的RREP报文，则建立从目的节点到源节点的反向路由。

2）RREQ报文接收处理策略

当节点收到RREQ报文时，启动RREQ报文接收处理策略，建立到源节点的反向路由。RREQ报文接收处理策略如图6所示。节点收到RREQ报文，则添加或更新到源节点的反向路由。如果本节点是RREQ报文的目的节点，则本节点向RREQ报文源节点单播回复RREP报文；如果本节点不是RREQ报文的目的节点，则广播转发该RREQ报文。

图6 RREQ报文接收处理策略

3.2.2 RREP报文处理策略

RREP报文用于建立从源节点到目的节点的正向路由。当目的节点收到有效RREQ报文时，则沿着新建立的反向路由单播回复RREP报文。收到RREP报文的节点，启动RREP报文处理策略，建立到目的节点的正向路由。RREP报文处理策略如图7所示。节点收到RREP报文时，添加或更新到目的节点的正向路由，如果本节点不是RREP报文的目的节点，则单播转发RREP报文。

3.2.3 HELLO报文处理策略

HELLO报文用于向邻居节点通报自身节点的存在，每一个收到HELLO报文的邻居节点，如果存在到此节点的路由，都会更新此路由条目的本地时间。如果路由条目的本地时间长期不更新，路由表就认为此路由条目为失效路由条目。当节点路由表中有需要维护的路由条目时，节点周期性广播HELLO报文，收到HELLO报文的邻居节点启动HELLO报文处理策略，进行路由维护。HELLO报文处理策略如图8所示。

图7 RREP报文处理策略

图8 HELLO报文处理流程

3.2.4 RERR报文处理策略

RERR报文用于向网络通报已失效的路由条目，每一个收到RERR报文的下一跳节点，都会检查本地路由表是否存在相关失效路由条目，如存在失效路由条目，则转发此RERR报文。当节点本地路由表发现超时路由条目（即认为失效）时，节点会广播发送RERR报文。接收到RERR报文的节点启动RERR报文处理策略，进行路由维护。RERR报文处理策略如图9所示。

4 AODV路由协议实现

AODV路由协议的实现基于嵌入式Linux操作系统，利用Linux内核netfilter框架的包过滤功能，在PRE_ROUTING及LOCAL_OUT两个HOOK点设置钩子函数，对流出（发送数据）和流入（接收数据）节点的数据包进行抓包，针对数据包的不同类型，加载不同报文处理策略，实现AODV路由协议的路由建立、路由维护和数据传输功能。

图9 RERR报文处理流程

4.1 netfilter框架

netfilter框架是Rusty Russell提出的新一代Linux防火墙，该框架基于Linux内核2.4版本，可实现数据包的过滤及处理、地址伪装和网络地址转换等功能［12]。为实现对流经TCP/IP协议栈的数据包进行检测和控制处理，在数据包流经协议栈的线路上，netfilter框架定义了五个钩子点（即HOOK点），如图10所示。在此五个HOOK点上，netfilter框架分别定义了五个钩子函数，用户可设置封装好的钩子函数实现数据包的抓取和处理。

图10 netfilter框架的HOOK点（IPv4）

针对流出平台的发送数据，在LOCAL_OUT钩子点设置钩子函数，进行发送数据的抓包和处理；针对流入平台的接收数据，在PRE_ROUTING钩子点设置钩子函数，进行接收数据的抓包和处理。

4.2 发送数据处理

发送数据作为平台自身产生的数据包，其处理流程如图11所示。依据平台节点是否存在目的路由，决定是否生成RREQ报文，并启用RREQ发送策略。

图11 发送数据处理流程

4.3 接收数据处理

接收数据作为外部节点流入平台节点的数据，其处理流程如图12所示。本文设计数据包类型包括数据报文和控制报文两种，其中控制报文包括RREQ报文、RREP报文、HELLO报文和RERR报文四种。依据数据包的不同类型，调用不同报文处理策略，从而实现AODV路由协议的路由建立、路由维护和数据传输功能。

5 AODV路由协议测试

5.1 静态测试

在静态多跳实验场景下，针对网络时延和丢包率两方面进行性能测试，验证AODV路由协议通信稳定性。静态测试如图13所示，平台S、M1和D均静止。通过平台S发送到平台D的ping扩展指令，记录网络时延和丢包率。

经测试及结果统计，静态测试时延如图14所示，静态测试丢包率如图15所示。依据统计结果可知，对于2跳S-M1-D链路，当发送1KB大小的数据包时，链路平均时延稳定在61ms左右，上下波动不超过3ms。随着测试时间的增加，丢包率从1.6%逐步趋近于0。由此可见，针对节点静止的多跳自组织网络，链路时延稳定性良好，数据包丢失仅出现在路由建立的初始阶段，随着测试时间的增长，丢包率趋近于0，链路通信状态良好。

图12 接收数据处理流程

图13 AODV路由协议静态测试图

图14 静态测试时延

图15 静态测试丢包率

5.2 动态测试

在动态多跳路由切换实验场景下，针对网络时延、丢包率和路由切换时间进行性能测试，验证AODV路由协议通信稳定性和及时性。动态测试如图16所示，平台S、M1和M2均静止，平台D匀速往返运动。通过源节点S发送到目的节点D的ping扩展指令，记录网络时延、丢包率和路由切换时间。

图16 AODV路由协议态测试图

图17 路由切换时延

经测试及结果统计，路由切换时延如图17所示，路由切换丢包率如图18所示。依据统计结果可知，对于多节点路由切换链路，当发送1KB大小的数据包时，链路平均时延在61.5ms左右，上下波动不超过2ms；丢包率稳定在4.7%左右，最大不超过5%。由此可见，针对多节点自组织网络的路由切换，链路时延稳定性良好，数据丢包率较小。

图18 路由切换丢包率

路由切换时间统计结果如图19所示，其中“S-D→S-M1-D”表示路由切换由链路S-D切换到链路S-M1-D，其它路由切换采用相同的表示方式。依据统计结果可知，路由切换平均时长约2.9s，最大不超过3.1s。由此可见，针对多节点自组织网络的路由切换，路由切换及时，上下波动较小，链路通信状态良好。

图19 路由切换时间统计结果

综上所述，分析可知：链路平均时延与所经跳数相关，跳数越多，时延越大；丢包率与路由切换频率相关，路由切换越频繁，丢包率越大；路由切换时间与自组织路由协议路由维护周期相关，维护周期越短，越容易发现失效路由，从而越早重新建立路由，缩短路由切换时间，但路由节点维护成本相应增大。

6 结语

本文基于嵌入式Linux操作系统，利用Linux内核netfilter框架，通过对路由协议报文处理策略的加载，实现了AODV路由协议的自组织路由和数据传输功能。测试结果表明，所设计的AODV路由协议具有良好的通信的稳定性和及时性。随着嵌入式技术的发展和移动自组织网络的应用，未来还需要对自组织路由协议和工程应用进一步研究，使之更广泛应用于车联网、物联网及无线传感器网络等方向。