小议基于嵌入式Linux操作系统的AODV路由协议
1.引言
无线 Ad Hoc 网，又称移动多跳无线网、移动分组无线网、无线自组网等，是一种无中心、不需要固定基础设施支持的无线网络。它是由一组带有无线收发装置的移动终端组成的一个多跳无线网络，不依赖于固定基础设施，网络中的移动终端通过自身的无线收发设备来收发信息。当通信终端不在彼此通信范围时，可以借助其它的中间终端节点进行数据转发，从而构成多跳网络。因此，Ad Hoc 网络的移动终端兼备主机和路由器的功能。
由于无线 Ad Hoc 网络的无中心、自组织、节点可移动等特点，Ad Hoc 具有可以快速临时组网、无须架设基础设施、网络抗毁性强等优点，目前的应用领域包括军事通信、灾后应急部署与野外作业、传感器网络、个人通信、与移动通信系统结合等。AODV 协议是Ad Hoc网络的主流路由协议之一。
2. AODV 路由协议
AODV 实际上是DSR(Dynamic Source Routing Protocol)和DSDV（Destination-Sequenced Distance-Vector）的综合，以DSDV 为基础，采
用DSR 中的按需路由思想进行改进。它采用了DSR 中路由发现和路由维护的基础原理，结合了DSDV
的逐跳（hop-by-hop）路由，顺序编号和路由维护阶段的周期更新机制。与DSDV 保存完整的路由表不同的是，基于按需路由思想的AODV 只有在有需要的时候才建立路由，这与DSDV 相比的好处是能减少大量维护路由所需的开销。与DSR 相比，AODV 的优势在于源路由并不需要包括在每一个数据分组中，这样能减少路由协议的开销。AODV 协议可以实现在移动终端动态的、自发的路由，使移动终端很快的获得通向所需目的地的路由，而且不用维护当前没有使用的路由信息，还能对链路状态和拓扑的变化做出快速的反应。AODV 使用路由请求序列号来保证无环路。避免了通常Bellman-foul 算法的无穷计数（count-to-infinite）的问题，并且提供了很快的收敛速度。鉴于AODV 路由协议功能强大而又便于实现的优点，故其成为嵌入式系统下移植Ad Hoc 协议的首选。
3.嵌入式Linux 系统
3.1 Linux 系统的网络系统体系结构简介
实现AODV 协议，主要是利用Linux 的网络系统，利用其TCP/IP 协议栈的处理机制。从整体上看，基于TCP/IP 的Linux 网络系统基本可以分
为BSD 套接口层、INET 套接口层、传输层、网络层和设备接口五个部分。
套接字（Socket）的产生是为了方便互联网应用程序的编程，它为应用程序提供统一的接口，应用程
序使用套接字接口来实现网络通信。BSD 套接口就是向上为应用程序提供的一种统一接口。在BSD 套接字下，根据不同的协议族有不同的套接字与之相连。INET 是处理Internet 协议的套接字。它提供处理TCP 和UDP 或直接处理IP 数据报文的接口。网络层用于实现IP 协议。而IP 层与各种网络硬件设备的交互是由设备接口来完成的。
3.2 网络接口Net filter
Net filter是Linux2.4 内核提供的包过滤框架。Net filter 可以在内核空间非常高效地进行包过滤，网络地址转换（NAT）和包重组。它提供了一个抽象、通用化的框架。该框架包括以下三个部分：
1）为每种网络协议（IPv4 等）定义一套钩子函数，这些钩子函数在数据分组流经协议栈的几个关键监测点时被调用。这些关键点称为hook 点。在这几个hook 点中，协议栈将把数据分组及钩子函数标号作为参数调用Net filter 框架。
2）内核的任何模块可以对每种协议的一个或多个钩子进行注册，实现挂接，这样当某个数据分组被传递给Net filter 框架时，内核能检测出是否有
模块对该协议和钩子函数进行了注册。若已经进行注册，则按优先级调用该模块注册时使用的回调函数，这样这些模块就有机会检查、修改、丢弃该分组或指示Net filter 将该分组缓存到用户空间的队列。
linux终端下载软件3）那些被传递到用户空间的数据可以被用户进程处理。处理后将该数据分组重新注入到内核协议栈中进行再次处理。
对于 IPv4 协议Net filter 提供了五个监测点，具体的定义如下：
NF_IP_PRE_RUTING：刚刚进入网络层的数据分组通过此监测点（刚刚进行完版本号，校验和等检测），源地址转换在此点进
行；NF_IP_LOCAL_IN：经路由查后，送往本机的数据包通过此监测点；NF_IP_FORWARD：要转发的数据分组通过此检测
点；NF_IP_POST_ROUTING：所有马上将要通过网络设备出去的数据分组通过此检测点，内置的目的地址转换功能（包括地址伪装）在此点进行；NF_IP_LOCAL_OUT：本机进程发出的数据分组通过此检测点。
这些监测点在内核中己经定义好，内核模块可以注册在这些监测点上的钩子函数，完成特定的功能。钩子函数返回固定的值，Net filter 根据这些值来判断应该对数据包做出什么样的处理，这些返回值是：
NF_DROP：禁止包通过，将包丢弃；NF_ACCEPT：允许包通过，将包传递给下一个钩子函数；NF-
_STOLEN：通知Net filter 钩子函数将会处理该数据包；NF_QUEUE：把分组缓存到队列中，该队列的分组可以被用户空间程序进行处理，通过调用nf_reinject（）函数将分组返回给Linux 内核以供Net filter 做进一步的处理；NF_REPEAT：重复调用钩子函数。
3.3 Linux 操作系统的路由转发功能
在嵌入式 Linux 操作系统下实现AODV 路由协议，主要是利用Linux 操作系统的路由转发功能。在Linux 操作系统中，路由功能一般分成两个部分。一部分驻留在操作系统内核中，这部分的任务是基于表驱动的进程，根据路由表的信息，设定正确的地址，将数据分组发往对应的网络接口，这部分称为“分组转发功能模块”。另一部分是实现路由协议的逻辑计算，根据与其它主机交换信息，计算出到其它节点的正确路由，实现真正的寻路由和维护路由的功能，这部分为“分组寻路功能模块”。
分组转发功能模块在内核中基于一个内核路由表来工作，每次发送一个数据分组，都要向内核路由表查询，取得对应的下一跳邻居节点的地址和对应的网络接口。内核路由表一般由分组寻路功能模块来操作维护。在查内核路由表的时候，根据路由表项的最佳匹配原则进行转发。如果不到匹配的路由表项，则按缺省路由发送，一般是将网关作为缺省路由的下一跳节点。如果缺省路由不存在，则当数据分组在不到相匹配的路由表项的时候，操作系统将简单的把这个数据分组抛弃。
分组寻路功能模块负责寻路，它和其它节点交换信息，采用一定的路由协议算法来计算和维护内核路
由表。分组寻路功能模块既可以在内核中实现，也可以在用户空间实现，Linux系统自带的分组寻路模块是在内核中的。这样将分组转发功能和分组寻路功能分开以后，可以在分组转发功能模块保持不变的情况下，通过修改分组寻路功能模块，用其它路由协议来替代现有的路由协议。
4.AODV 路由协议的移植
4.1 AODV 路由协议的软件实现
系统运行 AODV 协议以后，应用程序通过BSD 套接字发送数据。当数据分组通过Socket进入到Linux 协议栈，将进入Netfilter 的第一个hook
点NF_IP_LOCAL_OUT。程序在模块初始化的时候已经在该hook 点注册了钩子函数为Output_hander（）。在Output_hander（）函数内，首先判断该数据分组是否为广播分组，若是，则接受该分组，返回NF_ACCEPT；否则的话，查AODV 路由表，若存在AODV 路由，则接受该分组，让其通过该hook 点，若不存在，首先发起一个路由请求（也就是要发送一个RREQ 控制分组），然后将数据分组缓存到数据缓存队列中，只要返回NF_QUEUE，Netfilter 框架将该数据分组进行缓存。随后发起路由请求，首先产生一个任务结构体对象task，然后将该task 加入到任务队列中，然后唤醒aodv 线程，aodv 线程查任务队列，将该任务从队列中取出，根据任务的类型来发送RREQ 请求。
当节点接收到来自别的节点的分组，分组通过系统的硬中断和软中断机制，将分组发送至协议栈中处理。此时，Netfilter 框架会检查它的第一
个hook 点NF_IP_PRE_ROUTING。
程序在模块初始化的时候在该hook 点注册了，钩子函数为input_hander （）。该函数在Netfilter收到数据时被调用。此时，收到的数据可能有两
种：第一种是AODV 控制消息分组，例如请求建立路由的RREQ 分组一种是转发其它节点的数据分组。因此，在Input_hander（）函数当中，首先判断该分组是AODV 控制消息分组还是普通数据分组。若是AODV 控制分组，则将该分组加入到任务队列中，然后唤醒aodv 线程，对该控制分组进行分析处理；若是用户数据分组，则先查 AODV 路由表是否有到目的节点的路由，如果有则让数据分组通过Netfilter，然后Linux 协议栈中的数据转发模块会将该数据分组正确转发。如果没有路由，则先将该数据分组进行缓存，然后发起一个到目的节点的路由请求分组RREQ。当该节点收到路由回复分组RREP，则表明到目的节点的路由己经建立，则调用nf_reinject（）将刚才缓存的用户数据分组重新注入到该hook 点中，通过Linux 的数据转发模块进行转发。
4.2 AODV 路由协议移植的硬件平台
AODV 路由协议移植的硬件平台是定制的ARM 开发板，其核心模块是PXA270。
4.3 USB 无线网卡驱动移植
在开发板上移植AODV 路由协议以后，开发板之间的通信通过无线网卡来实现，本文所用的无线网卡是雷凌公司的RT73。RT73 无线网卡完全遵循IEEE802.11b/g标准，可以实现较远距离、高质量的数据传输。
应用层程序首先要加载驱动骨架程序模块，然后进行初始化工作，主要是初始化全局数据、tty_driver、设备接口等。初始化工作结束之后，便会进行USB 驱动的注册，注册完成之后，当有USB 无线网卡插入设备时，便会通过已经注册的驱动进行工作。应用程序还负责网卡驱动读写操作和卸载驱动的骨架程序。
4.4 AODV 协议移植编译
1、基于PC 机的实现。首先配置USB 无线网卡，对网卡的网络进行设置，主要命令为：
#iwconfig wlan0 mode managed essid//设置wlan0 的essid 为 managed然后安装 ad hoc 路由协议 aodvd-uu。在进行aodvd-uu 安装之前，要对里面的主要函数进行修改，修改的内容根据PC 所安装的Linux 操作系统内核版本而定，编译通过后便可以进行安装。
2、基于PXA270 的实现。修改内核目录下的配置文件fig，主要是配置与网络相关选项，
然后装载。配置完成后，将内核压缩成开发板可以应用的映像文件，主要命令行如下：
#./mkimage -A arm -O linux -T kernel -C none -a 0xa0007fc0 -e 0xa0008000 -n "LinuxKernel Image" -d zImage uImage//压缩内核映像所用程序然后将内映像下载到开发板中，重新烧写内核。
3、aodvd-uu 的移植。首先配置内核，将与AODV 路由协议移植有关的选项开启，主要是网络选项。然后进行交叉编译，主要命令为：
#make KERNEL_DIR=/home/liuxue/sbs/liuxue-1386 arm//生成所需的arm 开发板的运行模块最后加载刚生成的路由协议模块。当启动开发板，运行命令后，判定移植成功。
5.实验测试及分析
建立一个测试环境，其中，节点A、B、C 是PXA270 开发板，并且A、B、C 都装有无线网卡。由于通信范围的限制，A 与B、B 与C 之间可以直接相互通信，而A 与C 之间不可以直接进行通信。测试的目标是AODV 协议移植的效果，检测AODV 协议是否可以顺利实现。程序运行的软件平台是Fedora10 版本的Linux 操作系统，内核版本为2.6.20。PXA270 开发板采用移植的嵌入式Linux 操作系统，内核版本为2.4.20。
开发板开发套件中包含内核源码，ARM 交叉编译器、汇编器、以及网卡驱动。Linux 操作系统安装时
选择基本的网络组件和Netfilter 功能，开启数据转发功能。
从上面的测试结果可以看出，当所有节点打开AODV 路由功能时，节点能够自动发现邻居节点，建立路由信息，同时，源节点也能顺利的建立到目的节点的路由。当网络拓扑结构发生变化时，当时测试的是关闭一个节点，AODV 程序能够及时的做出变化，更新路由信息。这些说明，AODV 路由协议的移植成功，并且功能顺利的实现。
6.结束语
本文在嵌入式Linux 系统上实现AODV 路由协议的移植。鉴于IEEE802.11 己经成为一个成熟的无线局域网标准，而AODV 是IETF 提出的RFC 标准，因此，本文在802.11b 网卡的基础上，在嵌入式Linux 系统上实现了AODV 路由协议的移植。搭建一个无线Ad Hoc网络平台，并在这个平台上测试了AODV 路由程序的功能和性能。
目前，对无线Ad Hoc 的研究主要集中在仿真层面上，而实际开发Ad Hoc 网络产品相对较少。通过本文对AODV 路由移植的实现，为今后研究Ad Hoc 路由提供一个小小的基础平台，为Ad Hoc 的其他技术，如物理层、MAC 层技术的研究提供一个实际的网络平台。
在本程序的基础上，可以继续深入学习，提出自己的设计方案及仿真办法。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。