ad-hoc网络AODV路由协议算法设计.docx
《ad-hoc网络AODV路由协议算法设计.docx》由会员分享，可在线阅读，更多相关《ad-hoc网络AODV路由协议算法设计.docx（53页珍藏版）》请在冰点文库上搜索。
西南科技大学本科生毕业论文V
西南科技大学
毕业设计（论文）
题目名称：
ad-hoc网络AODV路由协议算法设计
年级：
2003级□本科□专科
学生学号：
20035233
学生姓名：
虞静指导教师：
江虹
学生单位：
信息工程学院技术职称：
副教授
学生专业：
通信专业教师单位：
信息工程学院
西南科技大学教务处制
ad-hoc网络AODV路由协议算法设计
摘要：
Ad-hoc无线自组织网络技术是近来出现的不同于传统网络的一种新技术,受到国内外的广泛关注，其路由技术是无线自组网的一个重要研究领域。
为适应不同的应用场合，已出现了诸如AODV等针对性较强的路由协议。
本文根据AODV路由协议的规范，设计和实现了相应的原理性算法，利用RREQ,RREP和RERR等协议帧进行路由查找和维护.并通过HELLO包维持链路的联接。
同时，为提高处理效率，该原理性算法使用Linux操作系统用户态与内核态实现相应的路由表管理，并使用钩子函数对网络中不同主机产生的包进行处理。
在PC104操作平台上进行的大量实验验证了该原理性算法的可行性，证明其达到了相应的设计目标。
论文最后简述了AODV路由协议的研究方向，并对以后的研究作出了展望。
关键字：
AODV；无线自组网；路由；Linux
AODVRoutingProtocolAlgorithmDesignofAd-HocWirelessNetwork
Abstract：
Ad-Hocwirelessnetworkisanewnetworktechnology,whichhasreceivedgreatconsideration,beingdifferentfromthetraditionalones.Routingisaveryimportantresearchfieldinwirelessself-organizingnetwork.Inordertoadaptvariousoccasions,thereappearsmanyspecificroutingprotocolssuchasAODV（AdhocOn-DemandDistanceVector）.
AccordingtotheAODVRouteprotocolspecification,thisthesisdesignsandrealizesthecorrespondingimplementationofprinciplealgorithm.ThedesignusesRREQ,RREPandRERRframestodiscoverandmaintainrouting,andkeepsthelinkconnectivitybyusingtheHELLOpackets.Meanwhile,inordertoimprovetheefficiency,theprinciplealgorithmmanagesroutingtablewithkernelandusermodeinLinuxoperatingsystem,anddealswithpacketsfromdifferenthostsbyhookfunctions.Greatmanyexperimentsbasedonpc104platformprovedthattheprinciplealgorithmisfeasible,andthedesigngoalisachieved.Finally,thethesisshowssomesuggestionsandfurtherresearchdirections.
Keywords：
AODV,WirelessSelf-OrganizingNetwork,Route,Linux
目录
第1章绪论 1
1.1课题背景、目的及意义 1
1.1.1课题的背景 1
1.1.2课题的目的及意义 1
第2章AODV路由协议算法原理 2
2.1AODV路由协议概述 2
2.2AODV路由协议使用的专业术语 4
2.3帧的格式 4
2.3.1RREQ协议帧的格式 4
2.3.2RREP协议帧的格式 5
2.3.3RERR协议帧的格式 5
2.4AODV的操作 6
2.4.1序列号的维护 6
2.4.2路由表项和先驱表 6
2.4.3产生路由请求 7
2.4.4处理和转发路由请求 7
2.4.5产生路由应答 8
2.4.6接收和转发路由应答 8
2.4.7HELLO协议帧 8
2.4.8RERR协议帧，路由过期和路由删除 9
2.4.9接口信息 9
第3章LINUX操作系统的网络功能 10
3.1Linux操作系统的总体介绍 10
3.2Linux操作系统网络功能的实现 10
3.3Linux操作系统路由转发功能的实现 11
第4章AODV路由协议的实现 13
4.1AODV路由协议实现的框架结构 13
4.2AODV协议实现的难点及其解决方法 15
4.2.1记录每条路由的最后使用时间 15
4.2.2用户空间和内核空间的信息交互实现 16
4.2.3对内核路由表的操作 17
4.3参数的设置 17
4.4路由协议中的主要流程 18
4.4.1主程序工作流程 18
4.4.2RREQ帧的接收处理流程 20
4.4.3HELLO帧的接收处理流程 21
4.4.4RREP帧的接收处理流程 23
4.4.5RERR帧的接收处理流程 24
4.4.6生成RREQ帧的函数流程 27
4.4.7生成RREP帧的函数流程 28
4.4.8生成RERR帧的函数流程 29
第5章AODV路由协议的实验研究 31
5.1测试环境 31
5.2 性能指标测试 31
5.2.1路由查找时间及时延数据分析 32
5.2.2ftp传输速率数据分析 33
5.2.3AODV背景流量数据分析 35
总结 37
致谢 38
参考文献 39
附录 41
西南科技大学本科生毕业论文
第1章绪论
1.1课题背景、目的及意义
1.1.1课题的背景
自七十年代世界上第一个分组无线网络ALOH在美国夏威夷大学研制成功之后，分组网就受到了军方的高度重视。
国内从八十年代起开始关注无线网的研究，经过二十年来的努力，已经取得了很多进步和成果。
而近几年，由于军用和民用需求的增加，大大促进了无线自组网络的研究。
无线自组网现在广泛用于自然灾害抢险，科学考察，以及战场等通信场合。
在任何时刻，任何地点，不需要现有信息基础网络设施的支持就能快速构建起一个移动通信网络。
无线ad-hoc网络的商业应用发展越来越快，应用范围越来越广。
但是，目前无线自组网还缺乏很成熟的商业产品，它还面临着许多问题需要加以解决，比如对路由算法低功耗性能的要求、对QoS的支持、采用方位辅助路由方式等。
由于受到手持设备电源供给的限制，路由算法的低能耗性能就显得尤为重要。
在对路由算法的解决方案中，有的对硬件的要求比较高，并不能发挥很好的市场优势，这给实际应用带来了不便，于此同时如何在移动中保持连接成为无线自组网的一个重要研究方向[1]。
因此现阶段有许多科研机构对无线路由进行研究，当今已经提出许多路由算法，各个路由算法有各自的优缺点，适合于不同场合。
其中，AODV路由技术发展尤为迅速，目前已经形成了rfc3561协议草案[2]。
1.1.2课题的目的及意义
无线自组网ad-hoc有灵活、机动组网、迅速适应能力强的特点可应用于野外工作环境，在有限的地域内提供适应机动条件的移动通信装备以满足特殊需求。
如：
国防战备、灾难救助、偏远地区等无法得到有线网络支持、或者某些只是临时需要的通信环境。
考虑到Ad-Hoc网络具有很多优良特性，因此它的应用领域需要进一步去挖掘。
比如：
Ad-Hoc网络可以用来扩展现有蜂窝移动通信系统的覆盖范围，实现地铁和隧道等场合的无线覆盖，实现汽车和飞机等交通工具之间的通信，用于辅助教学和构建未来的移动无线城域网和自组织广域网等[3]。
第2章AODV路由协议算法原理
2.1AODV路由协议概述
AODV路由协议是为ad-hoc网络节点设计的，它提供对动态链路状况的快速自适应，处理开销和存储开销低，网络利用率低（路由开销低）确定到达Ad-Hoc网络内的目的节点的单目标传输路由。
AODV路由协议明显的特征是每个路由条目均使用一个目的节点序列号。
使用目的节点序列号能够确保路由是开环的。
在选择路由时，要求路由请求节点选择序列号较大的那条路由。
AODV路由协议定义了三种控制消息[4]：
路由请求（RouteRequest,RREQ）、路由应答（RouteReply,RREP）、路由错误（RouteErr,RERR）。
对于广播消息并不是盲目发送，而是使用IP有限广播地址（255.255.255.255），广播帧通过使用IP头部的TTL域来限定广播帧的传播范围。
AODV协议是按需路由协议，即当节点接收或者发送业务包时，才会进行路由查找和建立。
在没有接收到数据时主要用HELLO消息来保持相邻节点的链接和系统维护，当收到业务包数据时，在没有路由的情况下，协议将会发起RREQ、RREP等控制消息来建立路由。
只要两个通信连接的节点有相互到达的有效路由，则AODV路由协议不起作用。
当一个节点需要一条路由达到一个新目的节点时，该节点广播一条RREQ控制消息来寻找一条到达目的节点的反向路由，通过给该RREQ控制消息，源节点回送一条单目标RREP控制消息来确定正向路由。
如图2-1中图a所示，当源节点A没有到目的节点G的有效路由时，便启动查找路由过程。
源节点A广播一个路由请求（RREQ），其中包含源节点地址、源节点序列号、目的节点地址、目的节点序列号和跳数等参数。
中间节点收到B、C、D、E、F和J收到RREQ时，建立或更新到源节点A的反向路由，若中间节点回发路由应答消息（RREP），并且RREQ帧没有设置D标志，则向上一跳节点回发应答消息（RREP），其中包含源节点地址、目的节点地址、目的节点序列号、跳数和生存时间参数，并经若干中间节点到达源节点A.。
否则继续广播RREQ消息，一直到目的节G收到RREQ后，向源节点A回发RREP。
如图2-1中图b所示，经过若干中间节点转发后到源节点，确认路由建立。
其中RREQ沿多条路径传播，但RREP只沿最先到达的路径（A、B和G）传回源节点，即选择时间度量最短的路由[5]。
路由表项建立以后，路由中的每个节点都要执行路由维护、路由表管理。
在维护路由表的过程中，当路由不再被使用时，节点就会从路由表中删除相应项。
同时，节点会通过HELLO消息来监视一个活动路由下一跳节点的状况，当发现有链路断开时，就用RERR控制消息来通知其他节点以及修复路由。
每个节点都保留了一个“先驱列表（PrecursorList）”来帮助完成错误报告。
C
B
G
J
D
E
A
F
图aA到G的广播查找过程（RREQ）
C
B
G
J
D
E
A
F
图bRREP建立确认过程
图2-1正反向路由查找建立过程
在AODV路由协议中为了避免单向链路引起错误操作，协议引入了一个黑名单，把是单向链路的邻居节点放入黑名单中。
通过无法接收链路层应答或者网络应答（例如RREP-ACK应答）来检测传输失败，如果接收的RREQ分组是从黑名单节点中发送来的，就不予处理这些RREQ分组。
2.2AODV路由协议使用的专业术语
Activeroute（有效路由）
通往目的节点的有效路由，只有有效路由可以用来转发用户数据分组。
Broadcast（广播）
发送至IP地址为255.255.255.255的广播报文。
并且对它的转发会有限制。
但有时将某些AODV协议帧广播发送到全网。
Destination（目的节点地址）
用户数据分组将被发送到的IP地址，其通过执行AODV协议算法获得。
Forwardingnode（转发节点）
转发用户数据分组的中间节点。
沿着路由查找过程已经建立好的路径，转发到距离目的节点较近的下一跳节点。
Forwardingroute（转发路由）
为了从源节点发送用户数据分组到目的节点而建立起来的一条路由。
Invalidroute（无效路由）
已经过期的路由，通过在路由表中的无效状态来标识。
Sourcenode（源节点）
发起AODV协议帧的节点。
Reverseroute（反向路由）
为了将RREP协议帧从目的节点转发至源节点，建立起的一条路由。
Sequencenumber（序列号）
每帧源节点维护的一个数字，它帮助其他节点判断信息的新旧程度。
2.3帧的格式
2.3.1RREQ协议帧的格式
AODV路由协议的路由请求RREQ消息的格式如图2-2所示，对其组成域说明如下：
表2-1RREQ帧组成域说明
组成域名称
功能
Type
长度8比特；取值为1
J
加入标志，保留用于多目标传输
R
修复标志，保留用于多目标传输
G
同时发送RREP到源节点和目的地址
D
指出只有目的节点才可以响应本RREQ
U
表示本目的节点序列号是未知序列号
HopCount
从源节点到处理该请求的节点的跳数
RREQID
RREQ帧ID，与源节点的IP地址一起标识RREQ
DestinationIPAddress
所寻找的目的节点的IP地址
OriginatorSequenceNumber
源节点序列号
类（type）|J|R|G|D|U|保留（Reserved）|跳数计算器（HopCount）
路由请求识别（RREQID）
目的节点IP地址
目的节点序列号
路由请求RREQ源节点的IP地址
路由请求RREQ源节点的序列号
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
图2-2RREQ帧结构
2.3.2RREP协议帧的格式
AODV路由协议的路由应答RREP消息的格式如图2-3所示，对其组成域说明如下：
表2-2RREP帧组成域说明
组成域名称
功能
Type
长度8比特；取值为2
R
修复标志，保留用于多目标传输
A
当节点收到这个RREP帧后需要给于应答
PrefixSize
这个字段用于分群的无线自组网
HopCount
从RREP源节点到处理该请求的节点的跳数
DestinationIPAddress
所寻找的目的节点的IP地址
DestinationSequenceNumber
目的节点的序列号
OriginatorIPAddress
发起这个路由请求的IP地址
Lifetime
节点收到RREP后记录的这条路由有效时间
类（type）|R|A|保留（Reserved）|前缀长度|跳数计算器（HopCount）
目的节点IP地址
目的节点序列号
路由请求RREQ源节点的IP地址
寿命（Lifetime）
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
图2-3RREP帧结构
2.3.3RERR协议帧的格式
AODV路由协议的路由错误RERR消息的格式如图2-4所示，对其组成域说明如下：
表2-3RERR帧组成域说明
组成域名称
功能
Type
长度8比特；取值为3
N
本地链路修复时，删除标志
DestCount
不可达目的节点的数目
UnreachableDestinationIPAddress
不可达目的节点的IP地址
UnreachableDestinationSequenceNumbe
不可达目的节点对应序列号。
类（type）|N|保留（Reserved）|跳数计算器（HopCount）
不可达目的节点IP地址
（1）
不可达目的节点序列号
（1）
其他不可达目的节点IP地址（假如需要的话）
其他不可达目的节点序列号（假如需要的话）
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
图2-4RERR帧结构
2.4AODV的操作
2.4.1序列号的维护
路由条目中的目的节点序列号越大就越能反映网络当前拓扑情况。
路由协议通过节点交互路由信息来建立和维护路由，目的节点序列号决定是否接收一个路由消息。
在路由消息中目的节点序列号比自己所知序列号大，则根据该消息更新路由表；反之，不予处理。
在以下几种情况下，节点增加自己的序列号：
（1）节点发起路由查找前，须增加序列号，该节点以前的反向路径冲突；
（2）目的节点响应RREQ发起RREP前，目的节点须更新序列号，使序列号等于当前序列号和RREQ中目的节点序列号较大值；
（3）节点发现邻节点的链路中断或过期时，把相应失效的路由条目中目的节点序列号加1。
节点在下列情况下可以改变路由表项中目的节点的序列号：
（1）节点本身是目的节点，并向其他站点提供了一条新的到自己的路由；
（2）节点收到AODV协议帧，协议帧中有关于目的节点序列号较新信息；
（3）通往目的节点的路径过期或中断。
2.4.2路由表项和先驱表
当节点收到来自相邻节点发送的AODV控制分组，或为特定目的节点建立、更新路由时，路由表中若如无该目的节点表项，则新建该表项。
并在下列情况更新：
（1）协议帧中的新序列号高与本机路由表中的目的节点序列号；
（2）协议帧中序列号与路由表中序列号相等，但跳数+1小于路由表中跳数；
（3）本机路由表项中的目的序列号未知。
路由表项中生存字段由控制报文确定或初始化为ACTIVE-ROUTE-TIMEOUT。
用路由进行数据转发时，它到源、目的节点和通往目的节点路径的下一跳的有效路由生存期更新为大等于当前加上ACTIVE-ROUTE-TIMEOUT。
节点维护有效路由表项的同时，还维护用来转发报文的先驱列表。
节点检测到下一跳链路丢失时，通知先驱列表。
先驱列表是使用这条路由的所有邻居节点。
2.4.3产生路由请求
当节点需到达某个目的节点而无可用路由时，则该节点发布一个RREQ。
这种情况可能是：
当前节点对目的节点未知，或者它们之间路由过期或无效。
在RREQ协议帧中的目的序列号从路由表中复制并设成最后知道的目的节点序列号。
如果源节点无目的节点序列号则在RREQ中设置未知序列号标记。
RREQ协议帧中源节点序列号是节点自身序列号，填入RREQ之前要将其增加1。
在广播RREQ以前，源节点在PATH-DISCOVERY-TIME时间内缓存RREQID和RREQ源节点的IP地址。
如果节点收到同样的RREQ，不对此进行处理
节点每秒种不因该产生多于RREQ-RATELIMIT次的RREQ协议帧。
广播出一个RREQ以后，节点等待RREP。
如果在NET-TRAVERSAL-TIME时间内仍获得路由，则节点广播一个RREQ重新进行路由查找过程，直到在最大TTL值时到达了RREQ-RETRIES次重传。
2.4.4处理和转发路由请求
当节点收到RREQ，首先建立或更新路由。
并检查是否在相应时间内，收到相同RREQ报文。
如果收到，则节点丢弃新收到的RREQ。
相反则进行以下处理：
首先，RREQ中跳数加1。
然后，节点使用RREQ中的源节点序列号作为路由表项中的目的节点序列号，在路由表中建立或者更新到RREQ源节点的反向路由。
在反向路由建立或更新的时候，反向路由表项需要进行下列操作：
（1）从RREQ中拷贝源节点序列号至路由表项中对应的目的节点序列号；
（2）路由表中的下一跳设置为向它发出RREQ的节点；
（3）跳数值等于接收到的RREQ协议帧的跳数字段中的值加1。
一个节点只有在下列两种情况下才产生RREP：
（1）节点本身是目的节点；
（2）节点具有到目的节点的有效路由同时目的节点序列号有效，并大于或者等于RREQ目的节点序列号，且RREQ中的“D”标记没有被设置。
如果上述任何一种情况满足，则节点不再重新广播RREQ。
2.4.5产生路由应答
如果节点收到到目的节点的路由请求，当节点具有有效路由来满足路由请求，或它本身就是目的节点，那么这个节点产生一个RREP的对应节点字段。
一旦建立了RREP，就把RREP单播至通往RREQ源节点的下一跳。
随着RREP逐步被转发回发起RREQ协议帧的源节点，跳数也每中转一次就增加1。
这样，当RREP到达发起RREQ的节点，跳数就代表从目的节点到源节点的距离。
2.4.6接收和转发路由应答
当节点收到RREP协议帧，它首先建立或更新无有效序列号的到上一跳的路由表项，然后RREP中的跳数值加1。
随后，RREP目的节点序列号和路由表中目的节点序列号进行比较。
此时现存的表项在下列情况
升级会员 