小议基于嵌入式Linux操作系统的AODV路由协议.pdf

小议基于嵌入式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 将该分组缓存到用户空间的队列 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 的实现 修改内核目录下的配置文件sbs 270 config 主要是配置与网络相关选项 然后装载 配置完成后 将内核压缩成开发 板可以应用的映像文件 主要命令行如下 mkimage A arm O linux T kernel C none a 0 xa0007fc0 e 0 xa0008000 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 己经成为一个成熟的无线局