0929Ad hoc网络两种按需路由协议性能仿真分析.doc

Ad hoc网络两种按需路由协议性能仿真分析赵 迪 陈向东（西南交通大学信息科学与技术学院，四川 成都 610031 zhaodi_2006163.com）摘要：Ad hoc网络是一种无需依赖于事先布设的基础设施，而仅依靠网络内部节点之间的协作，就能够完成节点间通信的网络。本文比较了Ad hoc网络两种主流的按需路由协议：动态源路由（DSR, Dynamic Source Routing）协议，自组网按需距离矢量路由（AODV, Ad-hoc On-Demand Distance Vector Routing）协议。本文使用基于ns-2的仿真模型进行仿真，并通过分组交付率、平均端到端时延、标准化路由负荷、标准化MAC负荷对两种按需路由协议进行评估。实验结果表明即使DSR和AODV协议都是按需路由协议，但它们采取的路由机制的不同，导致它们的性能表现的巨大差异。关键词：Ad hoc，路由协议，NS21 引言Ad hoc网络是一种没有预设基础设施的网络，它工作于无线环境，通信带宽受限，而且节点具有移动性。有鉴于此，为Internet设计的许多路由协议（如RIP、OSPF等）并不能直接适用于Ad hoc网络，主要原因如下：在网络拓扑结构快速变化的情况下，协议无法及时收敛，产生大量的不可靠路由和路由环路，而且路由开销过大。为了适应Ad hoc网的需要，必须设计新的路由协议。路由协议的研究成为当前Ad hoc网络研究的一个热点。2 Ad hoc路由协议的分类根据网络节点获取路由信息的方法来对移动Ad hoc网络的路由算法进行分类，移动Ad hoc网络的路由算法大致可以分成两大类：一类称作表格驱动类路由协议，一类称作源节点初始化按需驱动类路由协议。表格驱动类路由协议采用周期性的路由分组广播，来交换路由信息。尽力维护网络中每个节点至所有其他节点的一致的最新路由信息。源节点一旦要发送报文，可以立即获得到达目的节点的路由。因此这种路由协议的时延较小，但是路由协议的开销较大, 如DSDV、WRP、DBF等。源节点初始化按需驱动类路由协议简称为按需路由协议。按需路由协议只有在源节点需要的时候，才创建路由，这也正是“按需”的含义所在。当网络中一个源节点需要一条路由到达某个目的节点的时候，源节点就初始化网络内的路由寻找进程。一旦找到一条路由，或者所有可能的路由重新排列都已检测完毕，则结束网络内路由寻找进程。与表格驱动类路由协议相比,按需路由协议的开销较小，但是数据报传送的时延较大，如AODV、DSR等1。3 AODV与DSR协议概述AODV（Ad hoc ON Demand Distance Vector）路由算法是专为移动Ad hoc网设计的一种路由协议，它可以说是按需式和表驱动式的一种结合，具备了两种方式的优点。它的处理过程简单，存储开销很小，能对链路状态的变化做出快速反应。AODV通过引入序列号的方法解决了传统DV协议中的一些问题，如“计算到无穷”，确保了在任何时候都不会形成路由环。AODV路由算法属于按需路由算法，即仅当有源节点需要向某目的节点通信时，才在节点间建立路由，路由信息不会一直被保存，具有一定的生命期（TTL），这是由移动Ad hoc网本身的特点所决定的。若某条路由已不需要，则会被删除。另外，在建立路由时，除了路由控制分组外，没有其他的网络开销，路由开销也很小。DSR(Dynamic Source Routing, DSR)也是一种按需路由协议，它允许节点动态地发现到达目的节点的多条路由。所谓源路由，是指在每个数据分组的头部携带有在到达目的节点之前所有分组必须经过的节点的列表，即分组中含有到达目的节点的完整路由。这一点与AODV不同，在AODV中，分组中仅包含下一跳节点和目的节点的地址。在DSR中，不用周期性地广播路由控制信息，这样就能减少网络的带宽开销，节约了电池能量消耗，避免了移动Ad hoc网中大范围的路由更新。4 对AODV和DSR的仿真对比1 仿真模型采用ns-2扩展版仿真器作为仿真模型。使用IEEE802.11无线局域网的分布式协调功能作为MAC层协议。应用非时隙的载波侦听多址访问（CSMA）技术结合碰撞避免（CSMA/CA）机制来发送分组。电台模型具有商用无线接口Lucent公司的WaveLAN特性。将WaveLAN模拟为共享媒介的电台，标称比特率2Mb/s，标称传输距离250m2。通信模型是连续比特速率（CBR）通信源。在网络中随机选择源节点与目的节点对。源节点与目的节点对数量可变，用于改变网络的承载载荷。移动模型是随机点模型（Random Waypoint Model），仿真网络在一个1500m300m矩形区域，分布的50个节点。每个节点按照随机选定的移动速度（均匀分布在020m/s）从一个随机位置开始朝着一个随机目的移动。一旦到达目的节点，停顿一段时间后，朝另外一个随机目的节点移动。暂停时间影响移动节点的相对移动速度，改变暂停时间进行实验.3本文使用的仿真模型和参数如表1所示：表1 仿真模型及参数协议AODV, DSR仿真时间100s节点数50矩形区域范围1500m300m节点最大移动速度20m/s通信源模型连续比特速率（CBR）通信源分组长度512bytes分组发送速率2packets/s暂停时间0，10，20，40，70，100通信源节点数20，40性能指标参数：使用如下4个重要的性能指标对两种按需路由协议进行评估：1分组投递率（Packet Delivery Fraction）。分组投递率定义为目的节点接受的分组数与CBR源发送的分组数的百分比。2数据分组端到端的平均时延（Average end-to-end delay of data packets）数据分组端到端的平均时延包括：发现路由所引起的时延、在队列中等待的时延、MAC层的重传时延、无线传输时延等所有可能的时延之和。3标准化路由负荷（Normalized Routing Load）。标准化路由负荷定义为路由分组总数与数据分组总数的比值，即每个数据分组所承担的路由分组数。在这里，路由分组按跳计算，即，若一个路由分组传了4跳，则会被计算4次。4标准化MAC负荷（Normalized MAC Load）。标准化MAC负荷定义为平均为每个到达目的节点的数据发送的路由报文，ARP包，控制报文（RTS、CTS、ACK）的个数。该指标考虑了路由开销和 MAC 层的控制开销。以上报文的每一跳传输被作为一次传输计数4。2 仿真结果与分析：（1）分组投递率。从图1中可以看出当暂停时间为100时，即节点不产生移动，此时DSR协议和AODV协议均表现出令人满意的分组投递率，接近100%。图1（a）所示在20个源节点的时候，DSR和AODV两种协议的分组投递率非常相似。图1（b）所示在40个源节点的时候，当暂停时间较短（移动性较强）时，AODV协议的分组投递率要高于DSR协议。但是，当暂停时间较长（移动性较弱）时则恰恰相反，DSR协议的分组投递率高于AODV协议。产生这种现象的根本原因是DSR协议利用的路由存储机制。在载荷较重的情况下，路由存储的范围过大，而路由长度是存储路由的唯一比照依据，导致常常选择过时的失效路由，最终导致分组的丢弃。（a）20个源节点（b）40个源节点图1 分组投递率（2）数据分组端到端的平均时延。从图2（a）、（b）可以看出，在暂停时间较短时AODV协议的数据分组端到端的平均时延比DSR协议要低，但在暂停时间较长时DSR协议的分组时延要好于AODV协议。在低速移动的情况下，DSR的延时特性优于AODV是由于，DSR更可能在路由存储中找到有效的路由，减少路由发现时间，从而降低了端到端时延。而在高速移动的条件和较重的网络载荷下，DSR协议的路由存储策略就有些不尽如人意，由于链路的频繁中断，DSR协议存储路由过时失效的概率非常高，一旦选取了失效路由，导致分组丢失，却仍然消耗量额外的网络带宽和接口排队时间，并且由于AODV协议中目的节点只对第一个到达的RREQ分组做出反应，所以其更可能选择拥塞最轻的路由，而DSR协议中目的节点对所有到达的RREQ分组做出回应，并且路由长度是DSR协议选择路由的唯一标准，源节点可能选择路由长度最短，但拥塞较重的路由通路，最终都导致其更多的时延。（a）20个源节点（b）40个源节点图2 延迟特性（3）标准化路由负荷。从图3（a）、（b）可以看出，在所有的仿真实验中，DSR协议的路由负载均比AODV协议要低。这是因为DSR协议采用的缓存技术和混杂接收方式侦听路由请求分组，大大降低了路由开销，所以DSR的路由开销比AODV表现得要低。随着移动速度的增加，DSR和AODV路由开销也相应增加，这主要与缓存中路由失效有关，需要重新寻找新的路由，启动新的路由发现过程。（a）20个源节点（b）40个源节点图3 标准化路由负荷（4）标准化MAC负荷。如图4所示，与路由负荷不同，在暂停时间较短的情况下AODV协议的性能要好于DSR，当暂停时间较长时两种协议的标准化MAC负荷趋于相同。产生这种现象的原因是RERR分组在两种协议中处理方式的差异，在AODV中RERR分组采用与RREQ相同的广播方式，不需要IEEE802.11MAC协议中使用的RTS/CTS/DATA/ACK交互方式，因此在MAC层开销低的多，而在DSR协议中RERR分组与RREP分组采用相同的单目标方式，所以比起AODV协议要有额外的MAC层开销。（a）20个源节点（b）40个源节点图4 标准化MAC负荷5 结论本文使用ns-2仿真器对Ad hoc网络的两种按需路由协议AODV和DSR进行了分析比较，虽然两种协议均使用按需路由的策略，但是路由算法机制的不同，也导致它们性能之间的差异。仿真中发现，由于DSR协议使用了路由存储，以及为每个目的节点维护多条路由，在节点数较少和载荷较轻和或者移动性较弱的环境下DSR协议的分组投递率和时延特性均优于AODV协议。但随着源节点数的增多，移动性的增强，链路的频繁中断，往往导致DSR协议存储过时失效的路由，使得在较为苛刻的环境下其性能要逊色于AODV协议。并且虽然DSR协议路由负荷性能要超越AODV协议，但由于其在802.11MAC层付出了很高的代价，最终并未使网络中的真正载荷得到预期的降低。参考文献1. 陈林星，曾曦，曹毅移动Ad Hoc网络-自组织分组无线网络技术M北京：电子工业出版社，20062. Geetha Jayakumar, G. GopinathPerformance comparison of two on-demand routing protocols for ad-hoc networks based on random way point mobility modelJAmerican Journal of Applied Sciences, 2008, 5(6): 659-6643. 于斌，孙斌，温暖，等NS2与网络模拟M北京：人民邮电出版社，20084. Namit Mishra, AmitPandey, Naveen Nahata, et alSelection of Ad Hoc Network Routing Protocols by Performance AnalysisCProc of 2nd National Conf on Challenges & Opportunities in Information Technology (COIT-2008), Mandi Gobindgarh.: IMT-IET, 2008: 113-1165. Josh Broch David A. Maltz David B. JohnsonA Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing ProtocolsCProc of the Fourth Annual ACM/IEEE International Con on Mobile Computing and Networking (MobiCom98),Dallas, Texas, USA: ACM, 1998作者简介：赵迪（1981-），男，硕士研究生，研究方向：无线自组织网路由协议。陈向东(1967-)，男，教授、博士生导师，研究方向为无线传感器网络，微电子技术。本文所属领域：计算机网络A Performance Comparison of Two On-demand Routing Protocols for Ad-hoc NetworksZhao DiSchool of Information Science and Technology, Southwest Jiaotong University, Chengdu, 610031, zhaodi_2006163.comAbstract: Ad hoc networks are self-organizing networks that can be organized anywhere and at any time without the aid of any established infrastructure and centralized administration. We compares the performance of two prominent on-