基于移动 Ad Hoc 网络路由协议的研究与 NS2 仿真

《基于移动 Ad Hoc 网络路由协议的研究与 NS2 仿真》由会员分享，可在线阅读，更多相关《基于移动 Ad Hoc 网络路由协议的研究与 NS2 仿真（9页珍藏版）》请在装配图网上搜索。

1、精品论文基于移动 Ad Hoc 网络路由协议的研究与 NS2 仿真李冬 ，张大波(1.大连理工大学电信学院，大连 116023）E-mail：ledom摘要：本文介绍了 Ad Hoc 网络的三种典型协议 DSDV,AODV 和 DSR。Ad Hoc 是由一组移动 节点在没有任何现存网络基础设施的情况下形成的动态网络，使人们摆脱了有线网络的束 缚，可以随时随地的自由通信。针对 Ad Hoc 网络的特点，为了研究 Ad Hoc 网络路由协议的 性能，采用基于 Unix 平台的免费网络仿真软件 NS2 对三种协议在不同条件下进行仿真。通 过在 NS2 中建立一个三节点的简单运动场景分析了三种协议的工

2、作方式及 Ad Hoc 网络路由 协议的丢包原因。通过一个多节点的复杂网络环境，对三种协议在适应网络拓扑变化，适应 不同业务的能力进行了比较分析。给出了 NS2 的仿真环境和参数，得到了三种协议在不同网 络环境下的性能参数，给出了三种协议的适用环境。关键词：Ad Hoc；路由协议；NS2；仿真;性能 中图分类号：TP393.041. 引言目前，国内外对移动Ad Hoc网的研究主要集中在路由协议、媒体接入控制协议、能量、 连接性等，其中路由协议是人们研究的热点1。Ad Hoc网络即移动自组网，是在没有任何网 络有线基础设施的情况下,通过”多跳”通信形成的动态网络。网络中任何两个移动节点之间 不通

3、过有线设备进行通信，而是采用逐跳转发的方式进行通信。节点既是主机又是路由器。 Ad Hoc网络的出现使得人们摆脱了有线网络的束缚，可随时随地的进行自由的通信。它拥有 以下的特点：（1）动态变化的拓扑结构；（2）节点能量有限；（3）采用多跳通信本文针对这些特点，利用NS2网络仿真软件对三种路由协议进行研究.研究了不同业务速 率和业务流量下三种路由协议的性能，分析了三种路由协议适应网络拓扑变化的能力，得到 了三种协议所适应的不同网络环境。2. Ad Hoc网络典型路由协议Ad Hoc网络路由协议主要分为两类：（a）表驱动路由协议。主要有 DSDV(Destination-Sequenced Dis

4、tance-Vector Routing)和WRP(The Wireless Routing Protocol)等协议。 这类协议的每个节点都保存一个或多个路由表，通过向邻近节点发送路由更新信息来维护路 由表的更新，以适应动态变化的网络拓扑结构。由于要维护路由表，所以这种协议的路由负 荷比较大，同时由于一个节点只与临近节点交换信息，导致这类协议的收敛性比较差。（b） 按需路由协议，也称为反应性路由2。主要有AODV(Ad Hoc On-Demand Distance Vector)、 TORA(Temporally Ordered Routing Algorithm)、DSR(Dynamic

5、Source Routing).这类协议 不需要在每个节点维护一个路由表，只在节点需要的时候才发起路由。这类协议一般分为两 个阶段：路由发现和路由维护。源节点需要路由时先要进行路由发现过程。找到路由后，在 信息发送阶段要对路由进行维护，从而进入路由维护过程。2.1 DSDVDSDV是基于经典Bellman-Ford路由选择过程的改进型路由表算法3。仅适用于双向链- 9 -路。使用DSDV路由协议的节点都维护一个路由表。路由表中包括目的节点、跳数和一个由目的节点标明的序列号。目的序列号用于判断路由是否过时，防止产生路由环路。每个节点周 期性的与临近节点交换路由信息。有两种更新方式：一种是全部更新

6、（Full dump）发送全 部的路由表信息，主要应用于网络变化较快的情况；另一种是增量更新（Incremental upd ate）,更新的消息中只含有变化的路由部分，主要应用于网络变化较慢的情况。2.2 AODVAODV是一种按需路由协议。是由DSDV发展而来的。源节点在路由发现过程中，向周围节 点广播一个RREQ包。周围节点利用RREQ的信息，建立到源发起节点的反向路由，并继续广播 该RREQ包，直到到达目的节点或一个包含目节点路由信息的中间节点，而后该节点将沿着发 送RREP时建立的路径向源节点发送一个RREP包。同样在该RREP包的发送过程中，中间节点建 立了到达目的节点的反向路由，

7、以后源节点发送的信息就依此RREP建立的反向路由向目的节 点发送。可见AODV协议只支持双向链路。每个RREQ都有一个广播ID，转发过此RREQ的节点不 会再次进行转发。在路由分组中还包括一个源序列号SID，用于标识路由的新旧，防止路由 循环3。中间节点在源节点发送信息的过程中维护路由，当源节点没有信息发送后，经过一 段时间的计时后路由过期。在路由维护的过程中，若是源节点移动了位置会重新启动路由发现过程。若是中间节点 移动了位置，该节点相邻的节点发现链路失效后会向源节点发送一个链路失效通知（RERR）, 而后源节点重新发起路由发现，或者也可以由发现链路失效的节点自己发起路由发现，此称 为自修复

8、。2.3 DSR动态源路由协议是一种基于源路由的按需路由协议。在该算法中，节点在高速缓冲区中 存放到达目的节点的完整路径信息，而不仅仅是下一跳信息。当源节点S要向目的节点D发送 信息时，首先检查缓冲区中是否有到达目的节点的路由。若有则使用该路由，在分组头中包 含完整的转发节点序列。若没有则发起路由发现过程，发送RREQ。在RREQ中包含“路由记录”。 每个转发RREQ的节点都在“路由记录”中加入自己的地址。当RREQ到达目的节点或是知道该 路由的中间节点后，该节点发送RREP回应这个请求，并把”路由记录”的信息拷贝到RREP中, 采用同样的过程把携带路由记录的RREP发送给源节点.这样源节点就

9、拥有了到达目的节点的 完整路由信息.DSR允许节点在它们的路由缓冲区中保存多个到目的节点的路由4，这样当一 条路由失效后源节点可以检查其他可用节点而不用重新发起路由发现，所以其路由回复速度 比其他协议要快。3协议仿真与分析仿真实例在 Linux 环境下，用 ns2.33 版本的 NS2 对典型的 Ad Hoc 网络路由协议 DSDV,AODV,DSR 进行仿真。针对 Ad Hoc 网络的不同特性，通过建立不同的仿真场景对网络 协议进行了分析比较。3.1 三节点的简单运动场景设定3个节点0，1，2，试验区域为600*600，仿真时间是200s。节点0，1，2的初始坐标 为（290 200），（3

10、50，200），（500，280）。节点2在第5s以10m/s的速度向（380 250）方向 运动，此时节点0和2通过节点1进行通信。第80s节点2以3m/s的速度向（300 250）移动，这 时节点2和节点0处于一跳范围之内，直接通信。第100s节点0以2m/s的速度向（500 80）移 动。在远离的过程之中，节点0和节点2先是通过节点1通信，而后通信断开。为了对仿真过程进行更好的控制，采用TwoRayGround模型，利用setdest工具设定各节点的通信范围为100m，Phy/Wireless set RXThresh_ 1.42681e-08节点 2节点 0节点 1图 1 Ad Hoc

11、 节点移动场景Fig.1 The movement scence of Ad Hoc nodes3.1.1 仿真结果仿真中采用TCP流，在节点0和2之间建立TCP连接，在8s时启动。仿真过程中分别采用D SDV，AODV，DSR协议，并记录TCP拥塞窗口大小。图 2 采用不同协议拥塞窗口的变化Fig2 The change of cwnd_ with different protocol根据移动场景的设定，初始时节点0和节点2通过节点2进行通信，在80秒左右节点2靠近 节点0，两节点直接进行通信。100s节点0逐渐远离节点2，在140s左右两节点再次通过节点1 进行通信。从图2中可以看出DSD

12、V和DSR的拥塞窗口变化分为3个阶段，对应了节点0和2的三 阶段的通信过程。而AODV的拥塞窗口始终平滑的上升，这是由于AODV的路由维护过程与二者 不同。在AODV建立源节点到目的节点的路由后，各中间节点在路由活动期间检测路由表中的 下一跳路由是否可用，只有当下一跳不可用时中间节点才向源节点发送路由错误信息。在该 场景中中间节点1始终检测到到下一跳节点2的链路可用，所以至始至终节点0发送的信息包 都沿着0-1-2的路径传送。从图中可以看出通信过程中的丢包主要发生在路由变化的时候， 从而对协议的研究主要应主要考虑网络拓扑变化对协议性能的影响。在图中，两种按需路由 协议的拥塞窗口变化要早于表驱动

13、路由协议DSDV的窗口变化，可见在拓扑变化的时候DSR协议的收敛性要好于DSDV协议。3.2 多节点的复杂运动场景3.2.1 仿真性能参数1）分组投递率Packet delivery fraction（分组投递率）是目的节点接收到的数据分组与源节点发送 的数据分组的比值。它是反映路由协议有效性的重要指标，通过在不同仿真场景中对PDF的 比较，得出了路由协议适应各种环境的能力。2）端到端平均时延Average end-to-end delay of data packet(数据报文端到端平均时延)。包含所有的 时延：发现路由引起的时延，接口队列的排队时延，MAC层的重传时延等。3）路由负荷Rou

14、ting load（路由负荷）。路由报文总数与数据报文总数的比值。它是反映协议效率 的重要标志 构建50个节点在1000*1000的场景中随即运动的仿真环境，仿真参数设定如下表所示：表 1 仿真参数Tab.1 Simulation Parameters参数值参数值参数值路由协议DSDV,AODV,DSR队列PriQueue节点数50信道WirelessChannel天线OmniAntenna传输模型TwoRayGround队列长度50场景1000*1000MAC 协议802.11仿真时间200s运动random业务类型CBR3.2.2 不同业务速率下协议性能的分析在Ad Hoc网络中支持多种业

15、务类型。2Kbps支持低话音业务传输速率，8Kbps支持低速分 组数据交换业务传输速率，144Kbps支持准多媒体业务传输速率。设定一个CBR业务的发送速 率分别为2kb，8kb，144kb，1Mb，2Mb，各节点运动停留时间20s。图 3 不同速率下的分组投递率变化Fig.3 The change of PDF with different rate从上面的图中可以看出，在低发送速率的情况下，按需路由协议AODV,DSR的表现都很好， 能较好的适应低速率业务，而DSDV的分组投递率则在70%左右。可见采用按需协议的Ad Hoc 网络能够较的实现低速率业务。DSR协议比其他两种协议更能适应高速

16、率业务。对于超过1M b的业务三种协议都不能得到很好的分组投递率。因而在主要实现低速率业务的无线网络中 选择按需路由协议AODV,DSR都能得到较好的分组投递率。而对于高于144kb的业务，从分组 投递率的角度出发，选择DSR协议要好于选择AODV协议。3.2.3 不同业务流量下协议性能的分析当场景中发送源节点的数目分别为 10，20，30，40，50，发送速率为每秒 1 个 CBR 包， 运动停留时间为 20s，得到分组投递率，路由开销如图 4，图 5 所示。图 4 不同源节点数目下的分组投递率Fig.4 The change of PDF with different source nod

17、es图 5 不同源节点数目下的路由负荷Fig.5 The routing load with different source nodes从上面的图中可以看出，当Ad Hoc网络有较多的节点有通信需要时，aodv和dsr协议的 分组投递率都在90%以上，aodv协议随网络中通信节点数目的增多，变化不大。而DSDV协议 随通信节点数目的增多PDF有上升的趋势，这是因为在Ad Hoc网络动态变化的拓扑中，局部 拓扑的变化要小于整体拓扑的变化。DSDV协议的收敛性不高，但通过周期性的广播能较好的 适应局部拓扑的变化，从而当有更多的节点在局部拓扑范围内通信时，分组投递率有所上升。 在DSR中由于多个节

18、点通信，在大量信息交汇的中间节点的缓存器中可能保存了多条到达同 一目的节点的路由，而DSR过分依赖于路由缓存，当面临多条路由时，只从缓存中选择路径 最短的而非最新的一条，这很可能会挑中已经失效的路由造成TCP包的丢失。而AODV使用的 目的节点序列号机制保证路由信息及时性和不产生循环路由，所以随着节点数目的增多，A ODV协议的性能稳定。从图5中可以看出随着通信节点数目的增多，DSDV的路由开销减少，这 是因为DSDV发送的路由信息与通信节点的数目无关，它只进行周期性的广播。对于按需路由 协议，发送路由信息的数目随着通信节点的增多而增多，所以AODV和DSR路由负荷变化不大。3.2.4 不同拓

19、扑变化情况下的协议性能分析 节点随即运动的停留时间反映了网络拓扑变化的速率，比较极端的情况是当停留时间为0时，网络中各节点不停地运动，网络拓扑不断变化。停留时间为200s时，即网络中的节点都不运动，网络拓扑不发生变化。当节点运动的停留时间为0，10，20，40，80，160，200， 运动速度最大为20m/s得到分组投递率，平均时延，路由开销分别如图6、7、8所示。图 6 分组投递率Fig.6 Packet delivery fraction图 7 端到端平均时延Fig.7 avg end-end delay图 8 路由负荷Fig.8 routing load从上面3个图可以看出，各条曲线的变

20、化趋势都是相似的，随着网络拓扑变化速率的减 慢各项指标都趋于改善。从图六中可以看出，按需路由协议AODV,DSR能适应于网络拓扑快速 变化的情况。DSDV协议当网络变化速率不快时能得到较好的分组投递率。从图7中可以看出， 表驱动路由协议DSDV的延迟最短，按需路由协议的延迟要大的多。这是因为，DSDV协议在路 由表中维护了到目的节点的全部路由，在发送数据时只要查看路由表就能够得到路由信息。 而按需路由协议要先发起路由发现规程才能找到路由。这将引入较大的延迟。另外，按需路由协议不掌握网络整体拓扑结构，按需发现的路由可能因到达时间先后的 原因并不是最优路由，故路径较长，而表驱动路由协议在各节点间交

21、换路由信息，理论上能 够找到最优路径，故路径较短。而路径越长，延时越大。图8中，DSDV的路由开销要远大于A ODV和DSR协议。这是因为在少节点通信的情况下，DSDV的每个节点都要周期性的进行广播。 AODV的路由开销大于DSR的路由开销，这是由于在路由活动期间，采用AODV协议的中间节点 都要维护自己的下一跳路由信息。4 结论通过对三节点的简单运动场景的研究，结果表明网络拓扑的变化造成TCP信号的丢失。 这是动态变化的Ad Hoc网络所不能避免的。DSDV协议的收敛性比较差，不能及时发现网络拓 扑的变化，DSR对拓扑变化的反应较快。通过对多节点运动场景的研究，三种协议都能满足 低速率业务的

22、需求，对于高发送速率的环境，DSR的分组投递率要好于其他两种协议。随着 网络中通信节点数目的增加，AODV协议的分组投递率变化很小，比DSR更适应与多节点通信 的环境。DSR过分依赖于路由缓存，当面临多跳路径时有可能选中失效的路由，随通信节点 数目的增多分组投递率有所下降。DSDV协议收敛性较差，但能较好的维护局部拓扑信息。当 网络中通信的节点大都在一个较小“跳数“的局部范围内通信时，DSDV协议也不失为一种选 择。从不同拓扑变化速率的情况来看，按需路由协议要好于表驱动路由协议，它能更好的适 应网络的高动态性。综上所述，DSDV协议适用于低动态，小范围内通信，低速率的环境。DSR适用于高动态，

23、 对能量损耗控制要求比较高的环境。AODV是从DSDV和DSR发展而来的，因而具备了较强的适应能力，能很好的适应Ad Hoc网络拓扑变化的特点。参考文献1 Martin Mauve,Jorg Widmer,Hanners Hartenstein. A Survey on Position-based Routing in Mobile Ad HocNetworksJ.IEEE Network,2001,15(6):30-392 JOHNSON J,MALTZD.Dynamic source routing in ad hoc wireless networksM.Kluwer Academ i

24、c:MobileComputing,19963 VPark,S.Corson.Temporally-ordered routing algorithm(TORA) version 1 Functional specification.InternetDraft,draft-ietf-manet-tora-spec-04.txt,July 2004.4 吴晗星，付宇卓。无线自组网 AODV 路由协议的实现J.计算机应用与软件，2007，24（12）：1-3.On the Typical Routing Protocols of Mobile Ad HocNetwork and Ns2 Simul

25、ationsDong Li , Dabo Zhang(1.Department of Dalian University of Technology, Dalian 116023, China)Abstract: This paper introduces three typical protocols in detail,namely DSDV,AODV and DSR.Ad Hoc network is a dynamic network consisting of a collection of wireless mobile nodes without using any existi

26、ng network infrastructure,help the people slip the leash of wired network that can easily communicate each other.To the characteristic of Ad Hoc network, and then in order to study the performance of different protocol. NS2 is used in the simulation process under different condition.Through the cons

27、tructed of a scene which has three nodes and the node move simple,I analyzed the working of that three protocols and pointed out the reason of packet loss.And also through the constructed of a complex scene,I compared three protocols under different mobility patterns,operation rates.This paper list the parameters of the simulation and the movement scence that the simulation used.The simulation result shows that every protocol has corresponding network of prominent performance.Key words:Adhoc,routing protocol,NS2,simulation，performance.