武汉工程大学 毕业设计（论文）
AODVjr算法中只根据收到的AcK消息来判断\假如由于某种原因节点4离开了网络(图b),在AODv算法中,就会发送RERR消息通知所有节点目的节点不可到达。如果源节点想重建到目的节点的路由,则会发送一个带有大于先前序列号的目的地序列号的RREQ。而对于AODVjr算法来说,由于源节点不能收到来自目的节点的ACK消息,一段时间后,源节点检测到链路中断,将停止向目的节点发送数据\如果要继续通信的话,源节点将重新发起路由寻找另外一条路径以完成通信,并及时更新网络拓扑信息。 3) 简化了路由表
在AODvjr算法中,删除了先驱节点列表和跳数信息,RERR仅转发给传输失败的数据分组的源节点,并且目的节点只响应第一个接收到的RREQ。路由过程中总是选择其最快路径,忽略了跳数,从而简化路由表的结构,如下表。
4) 路由环路的避免
AODV路由算法是采用节点序列号(sequenceN切rnber)来决定路由状态的新旧,当路由信息的分组在传输中丢失时,就很可能导致中间节点对RREQ错误应答,这时AODV算法将利用节点序列号的大小来避免路由环路问题,而在AODVjr中,不使用节点序列号,仅规定目的节点回复RREP,这样同样能避免路由环路,同时可以进一步减少开销。AODV算法的路由环路的避免如下图。
- 17 -
武汉工程大学 毕业设计（论文）
如上图:节点1向节点5进行通信,假如路由信息(RREQ)通过节点4传输的时候丢失了,那么4一>5的链路将中断(图a),而源节点1并不知道4->5链路发生中断。此时,节点4发起本地链路修复,向节点5发起路由发现过程,节点1将会收到节点4发来的RREQ(通过4->6->l路径,图b),而节点1原路由表中己经有节点5的信息,那么此时节点1又将沿着1->2->3->4的路径发起RREQ,结果就形成环路4->6->l->2->3->4。在AODV算法当中,采用节点序列号方式(图
c),当4->5的链路发生中断时,节点4把自身的序列号介9)更新为目的节点5的序列号(=10),而此时由于节点6的序列号小于节点4的序列号,那么节点4将放弃向节点6广播RREQ,这样就能避免路由环路问题\而对于AODVjr算法来说,仅允许目的节点回复RREP,当源节点到目的节点的链路发生中断时,假如此时还需要路由的话,源节点将修改路由发现路径,及时更新网络拓扑,这样也能有效的避免路由环路,因此不需要节点序列号机制。
在AODVjr算法中,节点在转发RREQ之前,会计算将RREQ发送给它的邻节点和本节点之间的链路开销,同样在转发RREP之前也会计算反向路径中下一跳节点与本节点之间的链路开销,并将这些开销加到各分组中存储的链路开销上。在路由期间,中间节点和目的节点可能多次收到同一个RREQ,这种情况下采用首接为最优的思想,即只响应第一个收到的RREQ,在该请求中记录的路径即为消息传输的路径,RREP将沿着收到的第一个RREQ中记录的上一级地址发送回去。而在AＯDV算法中,由于采用了序列节点号机制,如果两次的RREQ的序列号相同,那么将丢弃后一个RREQ;如果后一个RREQ的序列号大于先前的序列号,那么将更新路由,选择序列号大的RREQ。AＯDVjr算法流程图如下图。
- 18 -
武汉工程大学 毕业设计（论文）
下图是AODvjr算法数据传输过程的示例图。图中,节点1向节点11发送数据,节点5向节点3发送数据,路由发现过程和图3－2中过程一样,不同的是当中间节点(如节点4)有到目的节点的路由,也不回复RREP,并且路由表中也不存储跳数信息,只存储各节点之间的链路开销(图a),然后选择各路径中总成本最小的那条路径作为数据传输路径。由于节点4要同时处理两组RREQ,很可能导致节点4过载,使得路径1的路由总成本小于路径2,也就是说RREQ沿着路径1比路径2要更快到达节点11,此时将选择路径1作为数据传输的路径(尽管路径2的跳数比路径1小),并且节点n会定期发送ACK消息以维护路由信息(图b)。
- 19 -
武汉工程大学 毕业设计（论文）
从以上分析可以得出:改进的AODVjr算法将使节点避免当节点出现过载的情况下过早的失去作用,当节点想要选择路径时,将考虑路径上的链路开销。在AODV算法只选择最少跳数的路由,而AODvjr算法中,只选择最快的路由,而忽略其跳数信息。当跳数最少的路径上某个(些)中间节点已经严重过载时,如果继续选择使用该路径进行路由,那么将选择其他链路质量较好的路径,这样就可以避免导致大量数据包的丢失和传输延迟的急剧增加。
3.5 ZBR路由算法简介
ZigBee使用Cluster-Tree和AODvjr相结合的路由算法(简称ZBR),将节点分为两类:存储空间有限的不具备路由发现能力的RN一节点和执行AODVjr算法的RN+节点。
使用AODVjr路由算法的RN+节点可以为找到数据传输的最优路径,从而使数据的投递率提高,而且传输时延降低,但过多的路由发现会使得网络中的控制开销增加,从而增加网络的冗余,也会增加节点能量的消耗\而RN一节点在转发数据时不需要进行路由发现,直接按照父子关系来投递数据,不需要控制开销,也降低了节点了能量消耗,但由于传输路径并不是最优的,因此会带来大的数据传输延时和低的数据投递率。
- 20 -
武汉工程大学 毕业设计（论文）
第四章 不同路由算法仿真及分析
4.1NS一2仿真软件简介
仿真主要有以下三点作用:学习算法和协议的实现,包括它们的性能和行为; 对未投入实际应用和未实现的算法和协议进行测试;对各种算法和协议、研究结果 的优缺点进行比较直观与客观的比较。目前主流的仿真软件有下面一些:NS-2, OPNET,MATLAB,QualNet/GloMosim,SPW。表4-1是主流仿真软件的比较
表4-1 主流仿真软件的比较
NS-2是开源免费的仿真软件,且其具有较高的执行效率,丰富的构件库,灵活的配置,良好的可扩展性和开放性等优点,是目前在世界上应用较为广范的仿真软件。在本文中选择NS-2仿真工具进行网络的仿真,下面会对NS-2仿真工具作简要的介绍。
4.2种路由算法仿真
用NS-2仿真软件对三种不同的路由算法分别在星型和树型网络下进行仿真分析比较。仿真主要考查的网络性能指标是: 1) 路由控制开销二路由发送的控制分组个数。
2) 平均端到端时延二所有成功递交的数据分组的端到端时延的总和/所有成功递交的数
据分组的个数。
3) 分组递交率=目的节点成功接收到的数据分组个数/源节点发送的数据分组个数。
星型网:设置仿真时间为500s,采用CBR数据流,分组大小为70Bytes,节点0为RN+节点,节点1-20为RN-节点。设置Cluster-Tree参数为Rm=20,Cm二20,Lm=1。图4.9
- 21 -