ad-hoc网络AODV路由协议算法设计

1、筋南科啟丈曇 毕业设计（论文）题目名称：ad-hoc网络a0dv路由协议算法设计年 级：2003级学生学号：20035233/本科专科学生姓名:虞静学生单位：信息工程学院 学生专业：通信专业指导教师：江虹技术职称：副教授教师单位：信息工程学院西南科技大学教务处制ad-hoc网络aodv路由协议算法设计摘ad-hoc无线自组织网络技术是近来出现的不同于传统网络的一种新技术, 受到国内外的广泛关注，其路由技术是无线自组网的一个重耍研究领域。为适 应不同的应用场合，已出现了诸如aodv等针对性较强的路由协议。本文根据aodv路由协议的规范，设计和实现了相应的原理性算法，利用 rreq, rrep和r

2、err等协议帧进行路由查找和维护.并通过hello包维持链 路的联接。同时，为提高处理效率，该原理性算法使用linux操作系统用户态 与内核态实现相应的路由表管理，并使用钩子函数对网络中不同主机产生的包 进行处理。在pc 104操作平台上进行的大量实验验证了该原理性算法的可行性, 证明其达到了相应的设计目标。论文最后简述了 aodv路由协议的研究方向, 并对以后的研究作出了展望。关键字：aodv；无线自组网；路由；linuxaodv routing protocol algorithm design of ad-hocwireless networkabstract: ad-hoc wirel

3、ess network is a new network technology, which has received great consideration, being different from the traditional ones. routing is a very important research field in wireless self-organizing network. in order to adapt various occasions, there appears many specific routing protocols such as aodv(

4、ad hoc on-demand distance vector).according to the aodv route protocol specification, this thesis designs and realizes the corresponding implementation of principle algorithm. the design uses rreq, rrep and rerr frames to discover and maintain routing, and keeps the link connectivity by using the he

5、llo packets- meanwhile, in order to improve the efficiency, the principle algorithm manages routing table with kernel and user mode in linux operating system, and deals with packets from different hosts by hook functions. great many experiments based on pc 104 platform proved that the principle algo

6、rithm is feasible, and the design goal is achieved. finally, the thesis shows some suggestions and further research directions.key words： aodv, wireless self-organizing network, route, linux第1章绪论11.1课题背景、目的及意义11.1.1课题的背景11.2课题的目的及意义1第2章aodv路由协议算法原理22.1 aodv路由协议概述22.2 aodv路由协议使用的专业术语32.3帧的格式42.3.1 rr

7、eq协议帧的格式42.3.2 rrep协议帧的格式52.3.3 rerr协议帧的格式52.4 aodv的操作62.4.1序列号的维护62.4.2 路由表项和先驱表62.4.3产生路由请求72.4.4处理和转发路由请求72.4.5 产生路由应答82.4.6 接收和转发路由应答82.4.7 hello 协议帧92.4.8 rerr协议帧，路由过期和路由删除92.4.9接口信息9第3章linux操作系统的网络功能103linux操作系统的总体介绍103.2 linux操作系统网络功能的实现103.3 linux操作系统路由转发功能的实现11第4章 aodv路由协议的实现134.1 aodv路由协议实

8、现的框架结构134.2 aodv协议实现的难点及其解决方法154.2.1记录每条路由的最后使用时间154.2.2用户空间和内核空间的信息交互实现164.2.3 对内核路由表的操作174.3参数的设置174.4路由协议中的主要流程184.4.1 主程序工作流程184.4.2 rreq帧的接收处理流程204.4.3 hello帧的接收处理流程214.4.4 rrep帧的接收处理流程234.4.5 rerr帧的接收处理流程244.4.6 生成rreq帧的函数流程274.4.7 生成rrep帧的函数流程284.4.8生成rerr帧的函数流程29第5章 aodv路由协议的实验研究315测试环境315.2

9、 性能指标测试315.2.1路由查找时间及时延数据分析325.2.2 ftp传输速率数据分析345.2.3 aodv背景流量数据分析35总结37致谢38参考文献39附 录41第1章绪论1.1课题背景、目的及意义1丄1课题的背景自七十年代世界上第一个分组无线网络aloh在美国夏威夷大学研制成功 之后，分组网就受到了军方的高度重视。国内从八十年代起开始关注无线网的研 究，经过二十年来的努力，已经取得了很多进步和成果。而近几年，由于军用和 民用需求的增加，大大促进了无线自组网络的硏究。无线自组网现在广泛用于自 然灾害抢险，科学考察，以及战场等通信场合。在任何时刻，任何地点，不需要 现有信息基础网络设

10、施的支持就能快速构建起一个移动通信网络。无线ad-hoc 网络的商业应用发展越来越快，应用范围越来越广。但是，目前无线自组网还缺 乏很成熟的商业产品，它还面临着许多问题需要加以解决，比如对路由算法低功 耗性能的要求、对qos的支持、采用方位辅助路由方式等。由于受到手持设备 电源供给的限制，路由算法的低能耗性能就显得尤为重要。在对路由算法的解决 方案中，有的对硬件的要求比较高，并不能发挥很好的市场优势，这给实际应用 带来了不便，于此同时如何在移动中保持连接成为无线自组网的一个重要研究方 向。因此现阶段有许多科研机构对无线路由进行研究，当今已经提出许多路由 算法，各个路由算法有各自的优缺点，适合于

11、不同场合。其中，aodv路由技 术发展尤为迅速，目前己经形成了 rfc3561协议草案。1.1.2课题的目的及意义无线自组网ad-hoc有灵活、机动组网、迅速适应能力强的特点可应用于野 外工作环境，在有限的地域内提供适应机动条件的移动通信装备以满足特殊需求。 如：国防战备、灾难救助、偏远地区等无法得到有线网络支持、或者某些只是临 时需要的通信环境。考虑到ad-hoc网络具有很多优良特性，因此它的应用领域需要进一步去挖 掘。比如：ad-hoc网络可以用来扩展现有蜂駕移动通信系统的覆盖范围，实现 地铁和隧道等场合的无线覆盖，实现汽车和飞机等交通工具之间的通信，用于辅 助教学和构建未来的移动无线城域

12、网和自组织广域网等。第2章aodv路由协议算法原理2.1 aodv路由协议概述aodv路由协议是为ad-hoc网络节点设计的，它提供对动态链路状况的快 速自适应，处理开销和存储开销低，网络利用率低(路由开销低)确定到达ad-hoc 网络内的目的节点的单目标传输路由。aodv路由协议明显的特征是每个路由 条目均使用一个目的节点序列号。使用目的节点序列号能够确保路由是开环的。 在选择路由时，要求路由请求节点选择序列号较大的那条路由。aodv路由协议定义了三种控制消息叫 路由请求(route request, rreq)、 路由应答(route reply, rrep)路由错误(route err,

13、 rerr)。对于广播消息并 不是盲目发送，而是使用ip有限广播地址(55),广播帧通过使用 ip头部的ttl域来限定广播帧的传播范围。aodv协议是按需路由协议，即当节点接收或者发送业务包时，才会进行 路由查找和建立。在没有接收到数据时主要用hello消息来保持相邻节点的链 接和系统维护，当收到业务包数据时，在没有路由的情况下，协议将会发起rreq、 rrep等控制消息来建立路由。只要两个通信连接的节点有相互到达的有效路由，则aodv路由协议不起 作用。当一个节点需要一条路由达到一个新目的节点时，该节点广播一条rreq 控制消息来寻找一条到达目的节点的反向路由，通过

14、给该rreq控制消息，源 节点回送一条单目标rrep控制消息来确定正向路由。如图21中图a所示，当 源节点a没有到目的节点g的有效路由时，便启动查找路由过程。源节点a广 播一个路由请求(rreq),其中包含源节点地址、源节点序列号、目的节点地 址、目的节点序列号和跳数等参数。中间节点收到b、c、d、e、f和j收到rreq 时，建立或更新到源节点a的反向路由，若中间节点回发路由应答消息(rrep), 并且rreq帧没有设置d标志，则向上一跳节点回发应答消息(rrep),其中 包含源节点地址、目的节点地址、目的节点序列号、跳数和生存时间参数，并经 若干中间节点到达源节点a。否则继续广播rreq消息

15、，一直到目的节g收到 rreq后，向源节点a回发rrepo如图21中图b所示，经过若干中间节点转 发后到源节点，确认路由建立。其中rreq沿多条路径传播，但rrep只沿最 先到达的路径(a、b和g)传回源节点，即选择时间度量最短的路由。路由表项建立以后，路由中的每个节点都要执行路由维护、路由表管理。在维护路由表的过程中，当路由不再被使用时，节点就会从路由表中删除相应项。 同时，节点会通过hello消息来监视一个活动路由下一跳节点的状况，当发现 有链路断开时，就用rerr控制消息来通知其他节点以及修复路由。每个节点 都保留了一个“先驱列表(precursorlist) ”来帮助完成错误报告。图a

16、 a到g的广播査找过程(rreq)、一'图b rrep建立确认过程图21正反向路由查找建立过程在aodv路由协议中为了避免单向链路引起错误操作，协议引入了一个黑 名单，把是单向链路的邻居节点放入黑名单中。通过无法接收链路层应答或者网 络应答(例如rrep-ack应答)来检测传输失败，如果接收的rreq分组是从 黑名单节点中发送来的，就不予处理这些rreq分组。2.2 aodv路由协议使用的专业术语active route (有效路由)通往目的节点的有效路由，只有有效路由可以用来转发用户数据分组。broadcast（广播）发送至ip地址为55的广播报文。并且对它

17、的转发会有限 制。但有时将某些aodv协议帧广播发送到全网。destination（目的节点地址）用户数据分组将被发送到的ip地址，其通过执行aodv协议算法获得。forwarding node（转发节点）转发用户数据分组的中间节点。沿着路由查找过程已经建立好的路径, 转发到距离目的节点较近的下一跳节点。forwarding route （转发路由）为了从源节点发送用户数据分组到目的节点而建立起来的一条路由。invalid route （无效路由）已经过期的路由，通过在路由表中的无效状态来标识。source node（源节点）发起aodv协议帧的节点。reverse route（反向路由）为了

18、将rrep协议帧从目的节点转发至源节点，建立起的一条路由。sequence number（序列号）每帧源节点维护的一个数字，它帮助其他节点判断信息的新旧程度。2.3帧的格式2.3.1 rreq协议帧的格式aodv路由协议的路由请求rreq消息的格式如图2-2所示，对其组成域 说明如下：表2-1 rreq帧组成域说明组成域名称功能type长度8比特；取值为1j加入标志，保留用于多日标传输r修复标志，保留用于多目标传输g同时发送rrep到源节点和目的地址d指出只有目的节点才可以响应本rrequ表示本目的节点序列号是未知序列号hop count从源节点到处理该请求的节点的跳数rreq idrreq帧

19、id,与源节点的ip地址一起标识rreqdestination ip address所寻找的目的节点的ip地址originator sequence number源节点序列号2.3.2 rrep协议帧的格式aodv路由协议的路由应答rrep消息的格式如图2-3所示，对其组成域说明如下：表2-2 rrep帧组成域说明组成域名称功能type长度8比特；取值为2r修复标志，保留用于多目标传输a当节点收到这个rrep帧后需要给于应答prefix size这个字段用于分群的无线自组网hop count从rrep源节点到处理该请求的节点的跳数destination ip address所寻找的目的节点的i

20、p地址destination sequence number目的节点的序列号originator ip address发起这个路由请求的ip地址lifetime节点收到rrep后记录的这条路由有效时间0 1 2 3 4 5 |6 7 8 9 |p 1 2 3 4 5 ” 7 8 9 ” 1 2 3 4 5 ” 7 8 9 |p 1类(type)| r | a | 保留(reserved)|前缀长度|跳数计算器(hop count)目的节点ip地址 目的节点序列号路由请求rreq源节点的ip地址寿命(lifetime )图2-3 rrep帧结构2.3.3 rerr协议帧的格式aodv路由协议的路

21、由错误rerr消息的格式如图2-4所示，对其组成域 说明如下：表2-3 rerr帧组成域说明组成域名称功能type长度8比特；取值为3n本地链路修复吋，删除标志dest count不可达目的节点的数目unreachable destination ip address不可达目的节点的ip地址unreachable destination sequence numbe不可达目的节点对应序列号。0123456789()12345 b789 |o12345 |6789()1类(type)| n |保留(reserved)|跳数计算器(hopcount)不可达目的节点ip地址(1)不可达目的节点序列号

22、(1)英他不可达目的节点ip地址(假如需要的话)其他不可达目的节点序列号(假如需要的话)图2-4 rerr帧结构2.4 aodv的操作2.4.1序列号的维护路由条目中的目的节点序列号越大就越能反映网络当前拓扑情况。路由协议 通过节点交互路由信息来建立和维护路由，目的节点序列号决定是否接收一个路 由消息。在路由消息中目的节点序列号比自己所知序列号大，则根据该消息更新 路由表；反之，不予处理。在以下几种情况下，节点增加自己的序列号：(1) 节点发起路由查找前，须增加序列号，该节点以前的反向路径冲突;(2) 目的节点响应rreq发起rrep前，目的节点须更新序列号，使序 列号等于当前序列号和rreq

23、中目的节点序列号较大值；(3) 节点发现邻节点的链路中断或过期吋，把相应失效的路由条目中目的 节点序列号加lo节点在下列情况下可以改变路由表项中目的节点的序列号：(1) 节点本身是目的节点，并向其他站点提供了一条新的到自己的路由;(2) 节点收到aodv协议帧，协议帧中有关于目的节点序列号较新信息;(3) 通往目的节点的路径过期或中断。2.4.2路由表项和先驱表当节点收到来自相邻节点发送的aodv控制分组，或为特定目的节点建立、 更新路由时，路由表中若如无该目的节点表项，则新建该表项。并在下列情况更 新：(1) 协议帧中的新序列号高与本机路由表中的目的节点序列号；(2) 协议帧中序列号与路由表

24、中序列号相等，但跳数+1小于路由表中跳 数；(3) 本机路由表项中的目的序列号未知。路由表项中生存字段由控制报文确定或初始化为active-route-timeouto 用路由进行数据转发时，它到源、目的节点和通往目的节点路径的下一跳的 有效路由生存期更新为大等于当前加上active-route-timeout。节点维护有效路由表项的同时，还维护用来转发报文的先驱列表。节点检测 到下一跳链路丢失时，通知先驱列表。先驱列表是使用这条路由的所有邻居节点。2.4.3产生路由请求当节点需到达某个目的节点而无可用路由时，则该节点发布一个rreqo这 种情况可能是：当前节点对目的节点未知，或者它们之间路由

25、过期或无效。在rreq协议帧中的目的序列号从路由表中复制并设成最后知道的目的节 点序列号。如果源节点无目的节点序列号则在rreq中设置未知序列号标记。 rreq协议帧中源节点序列号是节点自身序列号，填入rreq之前要将其增加1。在广播rreq以前，源节点在path-discovery-time时间内缓存rreq id和rreq源节点的ip地址。如果节点收到同样的rreq,不对此进行处理节点每秒种不因该产生多于rreq-ratelimit次的rreq协议帧。广播出 一个rreq以后，节点等待rrepo如果在net-traversal-time时间内仍 获得路由，则节点广播一个rreq重新进行路由

26、查找过程，直到在最大ttl值 时到达了 rreq-retries次重传。2.4.4处理和转发路由请求当节点收到rreq,首先建立或更新路由。并检查是否在相应时间内，收到 相同rreq报文。如果收到，则节点丢弃新收到的rreq。相反则进行以下处理：首先，rreq中跳数加1。然后，节点使用rreq中的源节点序列号作为路 由表项中的目的节点序列号，在路由表中建立或者更新到rreq源节点的反向 路由。在反向路由建立或更新的时候，反向路由表项需要进行下列操作：(1) 从rreq中拷贝源节点序列号至路由表项中对应的目的节点序列号；(2) 路由表中的下一跳设置为向它发出rreq的节点；(3) 跳数值等于接收

27、到的rreq协议帧的跳数字段中的值加lo一个节点只有在下列两种情况下才产生rrep：(1) 节点本身是目的节点；(2) 节点具有到目的节点的有效路由同时目的节点序列号有效，并大于或 者等于rreq目的节点序列号，且rreq中的“d”标记没有被设置。如果上述任何一种情况满足，则节点不再重新广播rreqo2.4.5产生路由应答如果节点收到到目的节点的路由请求，当节点具有有效路由来满足路由请求, 或它本身就是目的节点，那么这个节点产生一个rrep的对应节点字段。一旦建立了 rrep,就把rrep单播至通往rreq源节点的下一跳。随着 rrep逐步被转发回发起rreq协议帧的源节点，跳数也每中转一次就

28、增加1。 这样，当rrep到达发起rreq的节点，跳数就代表从目的节点到源节点的距 离。2.4.6接收和转发路由应答当节点收到rrep协议帧，它首先建立或更新无有效序列号的到上一跳的路 由表项，然后rrep中的跳数值加1。随后，rrep目的节点序列号和路由表中 目的节点序列号进行比较。此时现存的表项在下列情况下进行更新：(1) 现存路由表项中的序列号无效；(2) 现存路由表项中的序列号有效，但rrep的目的节点序列号大于路由 表项中的目的节点序列号；(3) 序列号相同，但是路由不再有效；(4) 序列号相同，但rrep中标明的“新跳数”小于路由表项中的跳数。如果需要对到目的节点的表项进行建立或者

29、更新，路由表项的下一跳就设置 为刚才发出rrep的节点。过期时间为当前时间加上rrep协议帧的生存期。目 的节点序列号为rrep协议帧中的目的节点序列号。任何节点传送rrep的时候，把rrep被转发到的下一跳节点加入到通往 rreq目的节点的路由表项的先驱列表中，对该先驱列表进行更新。同时，往本 节点发送rrep的上一跳节点也将加入到通往rreq源节点的路由表项的先驱 列表中。每个节点上用来转发rrep的路由的生存期变为现有生存期，当前时 间+ active-route-timeout两者之间的最大值。2.4.7 hello 协议帧节点可通过广播本地hello协议帧来提供连接信息。每h ell

30、o-interval 微妙内，节点检查最近的hellointerval是否发送了一个广播报文（比如 rreq或者其它可以完成hello协议帧功能的帧），如果没有发送，它会广播 一个ttl值为1的rrep,称为hello协议帧。如果在连续发送3次hello 协议，即3*hello-interval微妙内节点仍没有收到hello包，则认为该节 点与相应邻居节点的链路已经断开。并在邻居节点列表中删除该邻居。2.4.8 rerr协议帧，路由过期和路由删除rerr协议帧可以广播，可以是单播，或者交互式的单播至所有不可达节点。 节点每一秒钟不应该产生超过rerr-ratelimit个rerr协议帧。在re

31、rr中不可达目的节点列表中的一些节点可能会被邻居使用，所以需 要发送一个新的rerr帧。新的rerr帧中的不可达目的节点列表是有满足下 面条件的节点组成：节点在已经建立的不可达目的节点链表中，并且这个节点在 本机路由表中具有非空的先驱列表。应收到rerr的邻居节点是：存在于新建立的rerr节点的先驱列表中。 如果只有一个邻居需要接收rerr,则rerr应该单播至目的节点，否则将rerr 协议帧发送到本地广播地址（目的节点ip地址=55, ttl=1 ）。rerr 报文中的destcount自动指出报文中包含的不可达目的节点的数目。2.4.9接口信息aodv须知道分组从

32、哪个网络接口中来，当从一个新邻居节点收到分组时， 须在路由表中记录下这个邻居节点及其它对应的网络接口。同样发现到某个新的 目的节点的路由时，须在对应的路由表项中记录下对应的网络接口。当存在多个网络接口的时候，节点在所有使用aodv协议的接口上广播 rreq帧。只有一种情况除外：在这个接口上的所有邻居节点己经收到了这个 rreq则不在这个接口上广播。linux操作系统的网络功能本设计中，aodv路由协议是在linux操作系统上实现的。在实现方案中，充分 利用了操作系统自身的特点。因此，在介绍设计方案前先对linux操作系统，进行总 体说明。3.1 linux操作系统的总体介绍linux操作系统是

33、从minix操作系统发展起来的一种类unix操作系统。后来发 展成为一个多用户开源操作系统。由于其源代码开放性、廉价性、安全性以及优越的 性能，现在得到了越来越广泛的应用，尤其是在服务器操作系统领域。从操作系统的功能角度来看，linux的核心由五大部分组成：进程管理、存储管 理、文件管理、设备管理和网络管理。3.2 linux操作系统网络功能的实现本设计在实现的时候，主要是利用linux的网络系统。从整体角度考虑linux网 络系统基本可以分为硬件层/数据链路层、ip层、iner socket层、bsd socket层和 应用层五个部分。其中在linux内核中包括了前四个部分，在应用层和bsd

34、 socket 层之间的应用程序接都以4.4bsd为模板。inet socket层实现比ip协议层次高，实 现对ip分组排序、控制网络系统效率等功能。图31说明了 linux基于tcp/ip协议 的网络系统体系结构。从应用层到网络设备接都硬件之间的数据流程走向的观点来分析，应用曾中的操 作对象是socket文件描述符，通过文件系统定义的通用接口，使用系统调用从用户空 间切换到内核空间。对socket文件描述符的操作传递给对应的bsd socket操作，从 而进入到bsd socket层的操作。在bsd socket层中，操作的对象是socket结构，每 一个这样的结构对应的是一个网络连接，通过

35、网络地址族的不同来区分不同的操作方 法，判断是否应该进入到inet socket层，这一层的数据存放在msghdr结构的变量 中，在inet socket层，根据建立连接的类型，分成面向无连接和连接两种类型，这 是区分tcp和udp协议的主要原则。在这一层中的操作对象是sock类型的数据， 而数据存放在sk-buff结构中。从iner socket层到ip层，主要是路由过程，发送时 根据发送的目标地址确定需要使用的网络设备接口和下一跳的主机地址；接收数据的 时候需要在ip层判断该数据分组是要发送给上一层协议还是需要做一个ip转发，将数据传递给下一台机器。从ip层到硬件层，也就是到网络接口设备驱

36、动程序，即是 有关硕件的控制方法，其驱动程序负责将数据发送出去。图3-1 linux基于tcp/ip协议的网络系统体系结构3.3 linux操作系统路由转发功能的实现在linux的路由功能子系统中，主要保存了三种与路由相关的数据。第一种是在 物理上和本机相连接的主机地址信息表，第二种是保存了在网络访问中判断网络地址 应该走什么路由的数据表，第三种是保存最新使用过的路由信息的缓存信息数据表。 第一种被称为相邻表，由neigh-table数据结构的链表表示，以neighbor结构为节点。 第二种表是保存路由规则，用fib-table数据结构的链表表示。第三中表被称作路由缓 存表，用rtable数据

37、结构的链表表示凶。linux系统中路由采取的策略是,先到路由缓存表中查找表项，如果能够查找到，就直接将对应的一项取出来作为路由的规则；如果找不到，那么就根据fib-table链表中的内容，利用特定规则换算出来，并且在路由缓存中将这一项添加进去。linux操作系统中，路由功能一般分为两个部分。一部分驻留在操作系统内核中， 这部分的认识是基于表驱动的进程，根据路由表的信息，设定正确的地址，将数据分 组发往对应的网络接口，这部分称为“分组转发功能模块”。另一部分是实现路由协 议的逻辑计算，根据与其它主机交换信息，计算出到其它节点的正确路由，实现真正 的寻找路由和维护路由的功能，这部分称为“分组寻找路

38、由功能模块”。分组转发功能模块在内核中基于一个内核路由表来工作，每次发送一个数据分组, 都耍向内核路由表查询，取得对应的下一跳邻居节点的地址和对应的网络接口。内核 路由表一般由分组寻路由功能模块来操作维护。在查找内核路由表的时候，根据路由 表项的最佳匹配原则进行转发。如果找不到匹配的路由表项，则按照缺省路由发送， 一般是将网关作为缺省路由的下一跳节点。如果缺省路由不存在，则当数据分组在找 不到匹配的路由表项的时候，操作系统将简单都把这个数据分组抛弃。分组寻路功能模块负责寻路，它和其他节点交换信息，采用一定的路由协议算法 来计算了维护内核路由表。linux操作系统中自带的分组寻路功能模块在内核空

39、间实 现。第4章aodv路由协议的实现4.1 aodv路由协议实现的框架结构与传统的有线路由协议相比较，实现aodv协议会有很多地方不同。本设计对aodv路由协议实现的方案中，将尽可能的利用linux操作系统现有 的路由机制。实现方案不改变linux操作系统的分组转发功能模块，而是利用它的分 组转发功能模块的实现机制，用自己的分组寻路功能模块来代替linux操作系统现有 的分组寻路功能模块i。方案实现的基本思路是：用一个接收模块虚拟一个节点，将缺省的路由表项指向 这个节点，从而由这个接收模块发起路由查找请求。考虑到程序的移植性和扩展的方 便性，方案采用在用户空间实现分组寻路功能模块。本aodv

40、路由协议的原理性算法设计拟在linux2.4操作系统平台上实现， linux2.4分为三个主要部分：第一部分是接口部分，第二部分是aodv路由算法部 分，第三部分是内核模块部分。其中，前两个部分是在用户空间实现的，第三部分是 内核实现的。其中用户空间和内核空间各有一个路由表，在用户空间路由表建立的同 时通过相应的系统调用在内核空间建立路由表。这三个部分的功能分别是口»第一部分：接口部分接口部分的主要功能是利用linux系统提供的应用程序接口，为实现aodv路 由协议提供所需要的各种信息和服务。例如：在现实方案里当用户分组到达时，首先 查询内核路由表，如果数据分组的目的节点在内核的路由

41、表中已经存在，并且路由表 项有效，则由linux内核中的发送机制接发送，不发起aodv路由查找过程。如果 数据分组的目的节点地址在内核路由表中不存在，通过接口部分从内核空间进入用户 空间进行路由查找建立，路由建立后，如果aodv成功查找出路径，则要利用ioctl 系统调用将这条路由表的时间，记录在时间链表中，接着netlinksocket通知内核接 收该数据包以备进行下步处理。如果没有找到路径，则将缓存的数据分组释放，通知 用户程序出错。第二部分：aodv路由算法部分从第一部分提取出用户分组数据的目的地址，就可有足够的信息来进行aodv 路由查找。这部分涉及到rreq的广播，rrep,rerr

42、帧的处理等等。这部分功能就 是实现aodv路由协议，基本不涉及和linux的交互性问题。aodv各种数据帧（控 制包）的接受和发送可以利用普通的udp套接口实现，根据aodv协议，套接口使 用的是udp协议并在654端口进行收发。每当收发一个帧，都需要对对应的数据结 构进行更新。在各种数据结构中，最重要的是一个时间列队。各种aodv时间的管 理用了一个时间列队，每个时间发生的时候，都需要更新这个列队。这个列队记录了 这个事件的超时时间。插入时间类队的时候，根据要求发生时间在前的事件插在列队 的前面。第三部分：内核部分在linux内核设计中，为了扩展内核功能，方便的加载各种驱动程序，设计了 内核

43、可加载模块功能。用户可以通过这个功能想内核中加入新的功能模块卩役这个部分是相对独立的一部分，在内核空间利用加载模块技术实现。这里主要介 绍内核部分的时间提取和超时处理。无线自组网的拓扑结构因为是动态变化的，所以它的路由协议都有一个时间要求, 每一条路径都有一个有效时间，如果超过这个时间路径没有更新就需要将这条路由标 记为不可用。aodv路由协议也一样。它要求记录每条路径的最后使用时间，如果 空闲时间超过一点时间，就需要将这条路由标记为不可用。在aodv路由协议中有多种超时管理，女山 路由超时管理、路由删除超时管理 以及rreq包超时管理等。在本设计中，拟由软件实现所有超时管理，具体分为两 个队

44、列：等待队列和超时队列，例如：每个rreq包都设有相应等待时间，并且这 些包都处于等待队列中，然后依次将包的等待时间与当前时间对比。如果小于当前时 间（即：等待超时），则把包从等待队列中取岀放入超时队列，并执行相应的超时处 理函数；反之则继续在该队列中等待。综上所述aodv协议实现的操作流程可以表示如图4-1：图4-1 aodv路由协议实现的操作流程4.2 aodv协议实现的难点及其解决方法相比传统的有线路由协议或者主动路由协议，实现按需路由协议会遇到更多的问 题。实现aodv主要困难有以下儿点“叫（1）如何记录每条路由的最后使用时间；（2）如何在用户空间和内核空间之间传送数据；（3）对内核路

45、由表的操作。4.2.1记录每条路由的最后使用时间无线自组网的按需路由协议通常自己保存有一个路由表，这个路由表的每一项都 有一个定时器与之相关联。当定时器到期以后，以为着路由表项过期了，则应该将这 个路由表项删除或者标记为过期不可用。aodv路由协议需要记录每条路径的最后 使用时间，而问题是，系统自身并没有提供每条路径的最后使用时间给用户。为了提取每条路由的最后使用时间，本设计使用了 linux操作系统的挂钩函数, netfilter提供了一个分组过滤子系统，在该系统中，ipv4定义了五个挂钩点卩铁内核 模块可在这些挂钩点上注册自己的函数，这样当某个数据分组被传递给netfilter框架 时，内

46、核能检测是否有任何模块对该协议和挂钩函数进行了注册。若注册了，则调用 该模块注册时使用的回调函数。这五个挂钩的结构如图41所示：-> 1 -> route -> 3 -> 5->ilocal|routev24图4-1 linux系统中的五个挂钩点4.2.2用户空间和内核空间的信息交互实现为了实现用户空间和内核空间的信息交互，本设计利用了 linux 2.4内核的防火 墙netfilter提供一个分组过滤子系统并为ipv4定义了五个钩子。它们分别是：(1) nf-ip-pre-routing 1(2) nf-ip-local-in2(3) nf-ip-forward

47、3(4) nf-ip-local-out4(5) nf-ip-post-routing5内核模块可以在这五个挂钩点的任何一个点注册挂钩函数，对数据分组进行检查 过滤，并且记录下路径最后使用时间。如图41所示。数据报从左边进入系统，进行ip校验以后，数据报经过第一个钩子函数 nf-ip-pre-routing1进行处理；然后就进入路由代码，其决定该数据包是需要转 发述是发给本机的；若该数据包是发被本机的，则该数据经过钩子函数 nf-ip-local-in处理以后然后传递给上层协议；若该数据包应该被转发则它被 nf-ip-forward3处理；经过转发的数据报经过最后一个钩子函数 nf-ip-po

48、st-routing处理以后，再传输到网络上。本地产生的数据如果是业务包经过钩子函数nf-ip-local-out 4处理后，进 入用户空间并接收该数据包；然后查找用户空间层路由表项，查询是否有到目的节点 路由，如果存在该路由，则通过netlink socket通知内核接受该数据包，使包顺利通过 钩子4进而进行内核对数据包的后续处理工作，如路由等；反之一旦路由表中不存 在该路径，立即将该数据包进行排队，同时应该通过发送aodv控制包进行路由查 找，如：发送rreq等待目的节点发回rrep给源节点在用户空间建立路由，随后 利用ioctl()在内核空间建.、'/：内核路由表，最后同样将数据

49、包通过netlink-socket通知内 核接受该数据包以备进行下步处理。4.2.3对内核路由表的操作在实现方案中，将不修改linux自身的分组路由转发功能。因此需要做的是：根 据分组寻路模块计算的路由结果，修改linux内核中的路由表。在实现方案中，有两 个路由表，一个是内核的linux自带的称为内核路由表；另外一个是自己在用户层自 己建立的，称为aodv路由表。内核路由表是linux自身的分组路由转发模块工作的基础。aodv路由表结构是 根据aodv协议构造的记录了毎条路由的目的序列号、到目的节点的跳数等信息， 分组路由寻路模块需要利用这些信息，来进行正确的路由查找。程序对用户层的路由 表

50、定义了各种操作函数，因为分组路由寻路模块和aodv路由表都是在用户空间时 间的，它们之间可以很方便的进行信息交互。对内核路由表则不一样，它们之间涉及 内核和用户空间之间的交互，不能直接交换信息。因此程序利用了 linux的控制函数 ioctl来操作linux内核路由表。同样也利用ioctl来获取网络接口的信息。它能获取 网络接口的地址、是否支持广播、是否支持多播等功能。在获取网络接口信息的时候， ioctl函数使用了一个叫做ifconf的数据结构，而ifconf 乂使用了一个ifreq的数据结 构。每个网络接口用一个ifreq表示，在这个结构里面包含了网络接口的名字、地址 等信息叭4.3参数的

51、设置在程序中使用的协议参数值见下表卩叫表41主要协议参数值parameter namevalueactive-route-timeout3000msallowed-hello-loss2blacklist-timeoutrreq-retries*net-travaersal-timedelete-periodmax(active-route-timeout),(allowed-hello-loss)*(hello-interval)hello-interval1000mslocal-add-ttl2max-repair-ttl0.3*net-diametermin-repair-ttl设置成最

52、后可知的到目的节点的跳数my-route-timeout2*active-route-timeoutnet-diameter35net-traversal-time2*node-traversal-time*net-diameternext-hop-waitnode-traversal-time+10node-traversal-time40mspath-discovery-time2*net-traversal-timererr-ratelimit10ring-traversal-time2*node-traversal-time *(ttl-value+timeout-buffer)rre

53、q-retries2rreq-ratelimit10timeout-buffer2ttl-start1ttl-increment2ttl-threshold74.4路由协议中的主要流程4.4.1主程序工作流程程序开始时，首先读取程序可执行文件名。并对相应链表、堆栈、套接字等部分 初始化。将相应的包设置为可读文件参数组，并开始发送hello包维护链路连接。 然后，判断可读文件标示符，通过文件标示符判断文件类型，如果该文件是业务包, 则被packet-input程序调用。将该业务包根据路由表信息发送到其目的地址，此时如果内核路由表中无相应路由或路由无效，则应将包排队并发起控制消息查找路由，。 一旦

54、查找路由失败，则丢弃该业务包。如果该文件是控制包，则被net -socket调用并 进行路由查找、修复、发送错误信息等刖。其原理性算法流程如图42。图4-2主程序工作流程图4. 4.2 rreq帧的接收处理流程在整个rreq帧的接收处理流程中，当接收到rreq时，首先判断在path-di scovery-time时间内是否已经发送了一个rreq,如果发送了就则将包丢弃。（每 发送一个rreq后都会将其id缓存到rreq-id-queue中,rreq id和源节点的ip地 址联合起来标志一个独一无二的rreq报文）。反之，则将rreq的id和跳数加1 并缓存到rreq-id-queue中。接下来

55、，通过rreq更新止反向路由.到源节点的反向路 由表项的生存期设置为现有生存期，minimallifetime两者之中的最大值。（minima ilifetime =（当前时间 +2*net-traversal-time+2* 跳数 *node-traversal- time）o接着，在路由表中查找目的节点是否时是本机地址或本机有到目的节点的路由， 如果是则产生rrep并发送到发起rreq的节点.如果目的节点不是本机地址则转发 该rreqo如果收到rreq协议帧的ip报文头部的ttl值小于1,则增加ttl的值 直到达到最大ttl值时并尝试了 rreqretries次，却没有收到rrep,则丢弃

56、所 有发往对应目的节点的用户数据分组。为防止网络用塞，每次重传rreq的时候， 等待rrep的超时时间将在上一次的时间基础上乘2o其具体流程图如4-3o4.4.3 hello帧的接收处理流程在整个hello帧的接收处理流程中，当接收到hello时，首先查找邻居列表， 看是否存在这个邻居，如果没有则添加这个邻居。然后查找是否有到这个邻居的路由 表项，如果没有就建立一条这样的路由表项（分别在用户空间和内核空间路由表中建立）。这条新建立的路由如果不被其他活动路由使用，则新建到邻居节点的路由的先 驱列表将为空。当路由表项的先驱列表为空时，这条路由过期无效的时候，将不岀发 rerr帧。如果到这个邻居节点的路由已经存在，那么应该增加这条路由的生存期,生存时间至少增加为allowed-hello-losshello-intervalo到邻居的路由如果存在，必须包含hello协议帧中的最新目的节点序列号（在现在的