AODV与DSDV路由协议性能仿真与比较

第２３卷　第２期　计　算　机　仿　真　２００６年２月　文章编号：１００６—９３４８（２００６）０２—０１１８—０３　ＡＯＤＶ与ＤＳＤＶ路由协议性能仿真与比较　刘洛琨　，张远　，许家栋　（１．西北工业大学通信Ｔ程系，陕西西安７１００７２；　２．信息＿亡程大学信息工程学院通信Ｔ程系，河南郑州４５０００２）　摘要：文章首先介绍了自组网的概念和特点以及表驱动与源驱动两类路由协议，然后概述了这两类协议中比较经典的　ＡＯＤＶ和ＤＳＤＶ路由协议。为了对这两种路由协议的性能进行比较，使用　Ｎｓ一２网络仿真软件，仿真时选取了分组平均递　交率、端到端的平均时延、平均跳数和归一化的路由协议开销这四个衡量指标对ＡＯＤＶ与ＤＳＤＶ路由协议进行了性能评估，　并通过改变业务源连接数目、节点的移动速度和业务源的发包率等参数分析比较ｒ这些参数对这两个协议性能的影响，仿　真结果表明ＡＯＤＶ适合于中小规模，业务源发包率较低的场合，ＤＳＤＶ适合于网络规模小且节点移动速度较低的场合。文章　的最后对全文进行了总结。　关键词：自组网；表驱动；源驱动；仿真　中圈分类号：ＴＮ９１５．０４　文献标识码：Ａ　Ｓｉｍｕｌａｔｉｏｎ　ａｎｄ　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｔｈｅ　Ｐｅｒｆｏｒｍａｎｃｅ　０ｆ　ＡｏＤＶ　ａｎｄ　ＤＳＤＶ　Ｐｒｏｔｏｃｏｌｓ　ＬＩＵ　Ｌｕｏ—ｋｕｎ　，ＺＨＡＮＧ　Ｙｕａｎ　，ＸＵ　Ｊｉａ—ｄｏｎｇ　（１．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎｏｒｔｈｗｅｓｔ　Ｉｎｄｕｓｔｒｙ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ　Ｓｈａｎｘｉ　７　１００７２Ｃｈｉｎａ；　２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，　ＰＬＡ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ　Ｈｅｎａｎ　４５０００２，Ｃｈｉｎａ）　ＡＢＳＴＲＡＣＴ：Ｆｉｒｓｔ　ｔｈｅ　ｐａｐｅｒ　ｉｎｔｒｏｄｕｃｅｓ　ｔｈｅ　ｃｏｎｃｅｐ　ｏｆ　ｔｈｅ　Ａｄ　ｈｏｅ　ｎｅｔｗｏｒｋ　ａｎｄ　ｉｔｓ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ａｎｄ　ｔｈｅ　ｔａｂｌｅ—　ｄｒｉｖｅｎ　ａｎｄ　ｔｈｅ　ｓｏｕｒｃｅ—ｄｒｉｖｅｎ　ｐｒｏｔｏｃｏｌｓ．ｔｈｅｎ　ｓｕｍｍａｒｉｚｅｓ　ｔｈｅ　ＡＯＤＶ　ａｎｄ　ＤＳＤＶ　ｒｏｕｔｅ　ｐｒｏｔｏｃｏｌｓ　ｗｈｉｃｈ　ａｒｅ　ｔｙｐｉｃａｌ　ｒｏｕｔｅ　ａｌｇｏｒｉｔｈｍｓ．Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｃｏｍｐａｒｅ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　ｔｗｏ　ｒｏｕｔｉｎｇ　ｐｒｏｔｏｃｏｌｓ，ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｓｏｆｔ　ｔｏｏｌ　ＮＳ一２　ｉｓ　ｕｓｅｄ　ａｎｄ　ｔｈｅ　ａｖｅｒａｇｅ　ｐａｃｋｅｔ　ｄｅｌｉｖｅｒｉｎｇ　ｒａｔｅ，ｅｎｄ—ｔｏ—ｅｎｄ　ｄｅｌａｙ，ｍｅａｎ　ｈｏｐｓ　ａｎｄ　ｔｈｅ　ｎｏｒｍａｌｉｚｅｄ　ｒｏｕｔｉｎｇ　ｌｏａｄ　ａｒｅ　ｃｈｏｓｅｎ　ｔｏ　ｅｖａｌｕａｔｅ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　ＡＯＤＶ　ａｎｄ　ＤＳＤＶ．Ｔｈｅｎ　ｔｈｅ　ｅｆｆｅｃｔｓ　ｏｆ　ｔｈｅｓｅ　ｐａｒａｍｅｔｅｒｓ　ｏｎ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ａｒｅ　ａｎａｌｙｚｅｄ　ａｎｄ　ｃｏｍｐａｒｅｄ　ｂｙ　ｃｈａｎｇｉｎｇ　ｔｈｅ　ｃｂｒ　ｃｏｎｎｅｃｔｉｏｎ　ｎｕｍｂｅｒｓ，ｔｈｅ　ｍｏｂｉｌｅ　ｓｐｅｅｄ　ｏｆ　ｔｈｅ　ｎｏｄｅ　ａｎｄ　ｃｂｒ　ｓｅｎｄｉｎｇ　ｐａｃｋｅｔ　ｉｎｔｅｒｖａ１．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔ　ｉｎｄｉｃａｔｅｓ　ｔｈａｔ　ｔｈｅ　ＡＯＤＶ　ｉｓ　ｓｕｉｔａｂｌｅ　ｔｏ　ｓｍａｌｌ　ａｎｄ　ｍｉｄｄｌｅ　ｓｃａｌｅ　ａｎｄ　ｌｏｗｅｒ　ｓｅｎｄｉｎｇ　ｐａｃｋｅｔ　ｉｎｔｅｒｖａｌ　ａｎｄ　ｔｈｅ　ＤＳＤＶ　ｉＳ　ｓｕｉｔａｂｌｅ　ｔｏ　ｓｍａｌｌ　ｓｃａｌｅ　ａｎｄ　ｌｏｗｅｒ　ｎｏｄｅ　ｍｏｂｉｌｅ　ｓｐｅｅｄ．　ＫＥＹＷＯＲＤＳ：Ａｄ　ｈｏｃ（Ｍａｎｅｔ）；Ｔａｂｌｅ—ｄｒｉｖｅｎ；Ｓｏｕｒｃｅ—ｄｒｉｖｅｎ；Ｓｉｍｕｌａｔｉｏｎ　可以提供临时通信便利。　１　引育　目前，ＩＥＴＦ公布了一系列的有关Ａｄ　ｈｏｃ路由的草案：　目前蜂窝移动通信网络和无线局域网正在快速发展与　ＡＯＤＶ、ＴＯＲＡ、ＤＳＲ、ＯＬＳＲ　ＤＤＭ　ＭＡＯＤＶ　ＴＢＲＰＦ　ＬＡＮＭＡＲ　普及，但它们都属于现有网络基础设施范畴，需要类似基站　ＦＳＲ等，根据路由的驱动方式可以把路由选择协议分成表驱　或访问服务点这样的中心控制设备。在某些特殊的场合并不　动路由协议（叉称先应式路由协议）和源驱动按需路由协议　能使用，例如发生自然灾害时，基础通信设施遭到破坏，在这　（叉称反应式路由协议）。其中ＡＯＤＶ是经典的源驱动路由算　些环境下，自组网（Ａｄ　ｈｏｅ）这种无中心的分布式控制网络就　法，ＤＳＤＶ是经典的表驱动路由算法。　人们在实际工作中需要实现自组网的路由协议时，必须　收稿日期：２００４—１０—３０　先了解协议的性能如何，在不同的参数下性能有何改变，尤　—１１８一　维普资讯 http://www.cqvip.com

其是需要获得分组递交率、端到端的平均时延、平均跳数、归　一业务源如ＦＴＰ、Ｔｅｌｎｅｔ、Ｗｅｂ、ＣＢＲ及ＶＢＲ等；路由器队列管理　机制；路由算法等。此外，Ｎｓ一２还能仿真多播及一些局域网　的ＭＡＣ协议。Ｎｓ一２仿真的基本步骤：①创建网络；②建立　节点间的连接；③创建流量；④创建事件调度器，即规定节　点何时采取什么动作（包括发数据包、移动等）；⑤跟踪仿真　过程，提取重要数据作为仿真结果输出到ｔｒａｃｅ文件中保存，　仿真结果是进行参数分析的基础。　对于无线网络的仿真，创建网络之前需要配置节点参　数。　化的路由开销等指标的性能，因此，可以利用ＮＳ一２仿真　软件对这两种路由协议的性能进行仿真与比较，这对实际工　作中选择何种协议及合适的参数值提供了很大的参考。　２　ＡＯＤＶ与ＤＳＤＶ路由协议算法介绍　２．Ｉ　Ａ０ＤＶ路由协议算法介绍　路由表信息：网络中每个节点维护路由缓存表，表的内　容是到达源节点已知节点的路由。　路由发现过程：节点发信息时，先在路由表中查找路由，　３．２　性能指标与仿真参数的选择　有则按照路由发送信息，没有就进行路由发现过程。节点广　播路由请求包（ＲＲＥＱ）给自己所有的邻节点，邻节点在接收　到ＲＲＥＱ后，先在自己的路由表中查找是否有到目的节点路　由，如果有则将路由信息写入ＲＲＥＰ包（路由回复包）发给源　节点；如果没有，再将ＲＲＥＱ转发给自己所有的邻节点。以此　类推，直到到达目的节点或是中间某个节点知道到达目的节　点的路由。　路由维护过程：如果某发起路由请求的源节点移动了，　它能够再次发起一个路由发现过程，以找到到达目的节点的　新路由。如果沿着路由的某个节点移动了，在移动节点的“上　游”邻节点Ａ注意到此节点的移动，Ａ节点会传播一个链路　断开信息给Ａ节点的每一个有效的“上游”节点通知他们删　除路由表中的对应无效路由。这些邻节点依次传播这个链路　断开信息给“上游”节点，一直达到源节点。源节点会再次发　起路由发现过程。　２．２　ＤＳＤＶ路由协议算法介绍　ＤＳＤＶ是一种无环路距离向量路由协议，它是传统的　Ｂｅｌｌｍａｎ—Ｆｏｒｄ路由协议的改进。　路由表的信息：到网络内部所有可能的目的节点的路由　（具体需要的跳数），路由表的每一项都被目的节点赋予一个　序号，以区分新旧路由。　路由表的更新方式：路由表周期进行更新，通过“全　播”（ｆｕｌｌ　ｄｕｍｐ）的方式，把完整的路由信息传送出去。两次　“全播”之间，如果有更新信息则用小的“增长”数据包　（ｉｎｃｒｅｍｅｎｔａｌ　ｕｐｄａｔｅ　ｐａｃｋｅｔ）传送。　路由广播的内容：包括目的节点地址、下一跳地址、到目　的节点的跳数、请求信息的编号、新的路由广播发送序号。新　路由的序号比旧路由的序号大，如果路由序号相同，则选择　跳数更少的路由。路由更新信息要延迟发送，以防止发送以　后不久得到更好的路由。　３　ＡＯＤＶ与ＤＳＤＶ性能仿真与比较　３．Ｉ　ＮＳ一２仿真工具介绍　我们使用ＮＳ一２（ｎｅｔｗｏｒｋ　ｓｉｍｕｌａｔｏｒ—ｖｅｒｓｉｏｎ　２），　ｖｅｒｓｉｏｎ２．２６仿真软件，操作系统为Ｒｅｄｈａｔ　Ｌｉｎｕｘ８．０。它是面　向对象的离散事件驱动的网络仿真器，由ＵＣ　Ｂｅｒｋｅｌｅｙ研发，　能够仿真多种ＩＰ网络。它能实现运输层协议如ＴＣＰ、ＵＤＰ等；　依照ＲＦＣ　２５０１对自组网路由的评价标准，选取如下四　个衡量指标进行性能评估：　●分组平均递交率：即目的节点接收到的数据包个数　与源发送的数据包个数之比，反映了网络传输的可靠性，递　交率越高可靠性越大。　ｄｅｌｉｖｅ　＝　●端到端的平均时延：包括路由查找时延、数据包在接　口队列中的等待时延，传输时延及ＭＡＣ层的重传时延，反映　了路由有效性，尤其对话音包来说，时延太大会严重影响通　信质量。　ｅｎｄ－—ｔｏ－—ｅｎｄ－—ｄｅｌａｙ　∑（接收到数据包的时间一发送数据包的时间）　一　发送的数据包个数　●平均跳数：即仿真过程中，数据包从源节点到目的节　点所经过的平均跳数，反映ｒ网络拓扑结构、节点通信范围　及路由效率。　ｍｅａｎｈ。ｐ＝童童　堕　；；ｉｉ；２｛　；　ｌ　●归一化的路由协议开销：即为传递数据包，平均每个　数据包所需要的路由包的个数。它反映了网络的拥塞程度和　节点电源的效率，开销大的协议拥塞的概率就大，且会延迟　接口队列中数据包的发送。　ｌｏａｄ＝　仿真时节点配置的参数如下：仿真环境是３５个移动节　点，其运动的拓扑范围为１５００ｍ　３００ｍ，节点移动速度选择　２ｍ／ｓ，业务源连接数为１５个，业务源发包率为１　ｐａｃｋｅＷｓ，　数据包长为６４ｂｙｔｅｓ。基于该基本条件，分别改变某个参数　（保证在某个参数改变时，其他参数保持不变），来分析比较　各项参数对ＡＯＤＶ与ＤＳＤＶ协议性能的影响。　３．３　仿真结果分析与比较　横坐标１—７分别表示ｐａｕｓｅｔｉｍｅ为０ｓ、１００ｓ、２００ｓ、３００ｓ、　４００５、５００ｓ、６００Ｓ，它反映了网络拓扑变化的频繁程度。　由图１可以看出，ＡＯＤＶ的分组递交率比ＤＳＤＶ要高，当　ＣＢＲ连接增加时，两个协议的分组的递交率都有所下降，但　都保持在８４％以上；ＡＯＤＶ端到端的平均延时比ＤＳＤＶ略大　一ｌｌ９一　维普资讯 http://www.cqvip.com

图１　业务源连接数不同时ＡＯＤＶ与ＤＳＤＶ的性能　一点，两个协议端到端的平均延时基本无变化；两个协议的　有一定影响。当ｐａｕｓｅｔｉｍｅ为６００ｓ时，网络的各项指标略优于　平均跳数变化范围都在２跳与４跳之间；对于开销，ＤＳＤＶ的　ｐａｕｓｅｔｉｍｅ为Ｏｓ时的情况。很明显，网络拓扑变化的频繁程度　开销明显比ＡＯＤＶ要大很多，当ＣＢＲ连接增加时，ＤＳＤＶ开销　对ＤＳＤＶ的影响要比ＡＯＤＶ明显。当ｐａｕｓｅｔｉｍｅ为６００ｓ时，　有所下降，ＡＯＤＶ变化不大。　ＤＳＤＶ的分组平均递交率明显优于ｐａｕｓｅｔｉｍｅ为０ｓ时的情况。　从曲线走势可看出，网络拓扑变化的频繁程度对该网络　ｆｉ｝　｝。　｝；　ｌ｝，｝　ｌ圈２　节点移动速度和业务源发包率不同时ＡＯＤＶ与ＤＳＤＶ的性能　由图２可以看出，节点移动速度由２ｍ／ｓ增大到２０ｍ／ｓ　时，和图１中的分组递交率相比，ＡＯＤＶ　（下转第１９１页）　．．．——１２０－－－——　　ｌ　；维普资讯 http://www.cqvip.com

／／循环求出交点ｖＣｕｔｐｏｌｎｔ与三角形三个顶点夹角之／／　要的运算，提高运行速度。　和，函数ＡｎｇｌｅＢｅｔｗｅｅｎ用来求两个向量之间的夹角　Ａｎｇｌｅ＋＝ＡｎｇｌｅＢｅｔｗｅｅｎ（ｖｅｃｔｏｒ　ｖＡ，ｖｅｃｔｏｒ　ｖＳ）；　参考文献：　｝　［１］　石教英．虚拟现实基础及实用算法［Ｍ］．科学出版社。２００２．　如果夹角之和大于等于３６０。，交点在三角形内部，说明　２１６．　视点与三角形发生了碰撞；　［２］　魏迎梅，王涌，吴泉源。石教英．碰撞检测中的层次包围方法　如果夹角小于３６０。，交点不再三角形内部，说明视点并　［Ｊ］．计算机应用，Ａｕｇ．２０００，２０（１）：２４１．　未与三角形发生碰撞。　［３］　曾芬芳．虚拟现实技术［Ｍ］．上海交通大学出版社，１９９７．８６．　［４］　熊伟，毛善君，马蔼乃．基于观察者的碰撞检测技术在虚拟环　４算法优化　境漫游中的应用［Ｊ］．计算机应用，２００２．２２（１１）：６．　［５］　涂超，颜辉武．碰撞检测技术研究［Ｊ］．计算机工程与应用，　上述算法只适合于三角形数量比较少、比较简单的场景　２００１．１４２　中，如果场景中的三角形数量比较多，场景又复杂，这样的方　法就会降低运行速度。对其进行改造的一种方法是对其进行　［作者简介］　“过滤”，滤去不需要的数据，以减少不必要的计算。例如，分　高丽娜（１９８１一），女（汉族），吉林舒兰人。南京工　割过滤法　Ｊ，此方法是将虚拟空间划分成规则的格网，以此　业大学硕士研究生，主要方向：虚拟现实。　将空间中的物体分割成更小的群组，此方法的目的是为了减　马尧海（１９５７一），男（汉族），浙江慈溪人。南京工　少系统进行碰撞检测时，实体一实体比较的次数。通过分割，　业大学信息工程学院副教授，主要研究方向：虚拟　进行碰撞检测的三角形数量会大大减少，从而可以避免不必　现实，影视动画。　（上接第１２０页）　数值提供了很大的参考。　仍保持在较高的水平，而ＤＳＤＶ分组递交率明显下降，由　８８％下降到７８％，ＡＯＤＶ的分组递交率仍比ＤＳＤＶ要高，当　参考文献：　业务源发包率由１　ｐｋｔ／ｓ增大到４ｐｋｔ／ｓ时，ＡＯＤＶ分组递交率　［１］　彭伟刚＋Ａｄ　Ｈｏｃ网络中的路由技术［Ｊ］．江苏通信技术，２００２—　基本不变，ＤＳＤＶ略有下降；当网络拓扑变化较频繁，节点移　８，１８（４）：２０—２４．　动速度增大到２０ｍ／ｓ时，ＤＳＤＶ的延时较大，ＡＯＤＶ的延时基　［２］　刘强．基于免费软件ｎｓ２的网络仿真［Ｊ］＋电子技术应用，２００１，　本无变化，而业务源发包率的变化对两个协议影响不大；两　（２）：６３—６４．　个协议的平均跳数变化范围仍在２跳与４跳之间；对于开销，　［３］　孙荷琨，郑家玲，张云峰．Ａｄ　Ｈｏｃ网络路由协议设计及性能评　节点移动速度和发包率增大时，和图１相比两个协议的开销　估问题［Ｊ］．中国数据通信，２００２，７：７１—７４．　都明显增大，其中ＡＯＤＶ受发包率影响更大，ＤＳＤＶ受节点移　［４］　任智，郭伟．多跳无线网络路由协议研究进展［Ｊ］．电信科学，　２００３。（８）：１０—１７．　动速度影响大一些。　【５］Ｅ　Ｍ　Ｒｏｙｅｒ＆Ｃ　Ｋ　Ｔｏｈ．Ａ　Ｒｅｖｉｅｗ　ｏｆ　Ｃｕｒｒｅｎｔ　Ｒｏｕｔｉｎｇ　Ｐｒｏｔｏｃｏｌｓ　综上所述，ＡＯＤＶ分组递交率要优于ＤＳＤＶ，而ＤＳＤＶ的　ｆｏｒ　Ａｄ—Ｈｏｅ　Ｍｏｂｉｌｅ　Ｗｉｒｅｌｅｓｓ　Ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ　Ｐｅｒｓｏｎａｌ　平均时延略低于ＡＯＤＶ，两者的平均跳数范围基本相同。当　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｍａｇａｚｉｎｅ．Ａｐｒｉｌ　１９９９．４６—５５．　节点移动速度和发包率增大时，ＡＯＤＶ和ＤＳＤＶ的开销都明　显增加，但ＡＯＤＶ仍保持了较高的分组递交率，而节点的移　［作者简介］　动速度对ＤＳＤＶ的性能影响最大。网络拓扑变化的频繁程度　刘洛琨（１９６３一），男（汉族），河南洛阳人，　对两个协议的分组递交率和负载也有一定影响。因此ＡＯＤＶ　信息工程大学通信工程系副教授，西北工业大学在　适合于中小规模，业务源发包率较低的场合，ＤＳＤＶ适合于网　读博士，主要研究方向为微波通信系统、无线移动　络规模小且节点移动速度较低的场合。　自组织网络；　张　远（１９８０一），女（汉族），陕西西安人，就读于　４　结束语　信息工程大学信息工程学院通信工程系，在读硕士，主要研究　本文利用Ｎｓ一２仿真软件对自组网中比较经典的　方向为无线移动自组织网络；　ＡＯＤＶ和ＤＳＤＶ路由协议的性能进行了仿真，并在不同条件　许家栋（１９４８一），男（汉族），陕西西安人，西北工业大学教授、博士　下分析比较了几个重要参数对这两个协议的影响，指出了它　生导师，硕士，主要研究方向为计算电磁场、雷达成像、微波通信。　们各自适用的场合，为实际工作中选择何种协议及合适的参　－－－——１９１－－－——