无线Ad Hoc网络中一种多路径路由协议仿真研究

1、摘要移动 Ad Hoc 网络由一组由无线收发装置的移动节点组成的一个多跳的、不需要固定中心接入点的自治系统。网络搭建方便，不需要基础设施，并且网络节点地位对等，可以自由移动。Ad hoc 网络在现代社会越来越多的运用于各个领域，如军事、医学、空间探测等。无线 Ad hoc 网络作为一种典型的自组织网络，其路由协议一直是研究的重点。Ad Hoc 网络的特殊性使得传统有线网络的技术无法在 Ad Hoc 网络使用，因此需要设计新的协议和技术，如 MAC 协议，路由技术，QoS 体系，安全技术，信道接入技术等。本文通过网络仿真软件 NS-2 以仿真 AOMDV 协议为例介绍了 NS-2 仿真路由协议的

2、详细步骤，并给出了 DSR、DSDV、AODV 三种路由协议的仿真结果图和一些性能分析。关键词：Ad hoc 网络,NS-2 仿真,DSDV 协议,DSR 协议,AOMDV 协议ABSTRACTThe mobile Ad Hoc network is an autonomous system, which is multi-hopped and with no fixed center access points, consisting of a set of mobile nodes of wireless transceiver. Network established without a

3、ny aid of infrastructure is convenient and also has equivalent node status which are free to move. The Ad Hoc is widely used in many fields such as military, medicine and space exploration etc. The routing protocol is always the focus of Ad Hoc as a typical self-organized network. The reason designi

4、ng new agreement and specification such as MAC protocol, routing protocol, QoS system, security technology, channel access technology etc is the particularity which makes the traditional wired network not available. In this paper, NS-2 network simulation software to simulate AOMDV agreement as an ex

5、ample of the NS-2 simulation routing protocol detailed steps, and gives the DSR, DSDV, AODV simulation results of three routing protocols and some performance analysis chart.Key words: Ad Hoc network ,Simulation,NS-2,DSDV,AOMDV,DSR,Agreement目录摘要 .IABSTRACT .II第 1 章 引言 .- 1 -1.1 无线自组网的产生和发展 .- 1 -1.2

6、 无线自组网的特征 .- 1 -1.3 无线自组网应用领域 .- 2 -1.4 无线自组网体系结构 .- 2 -1.5 文章研究内容 .-3 -1.6 本文研究的应用 .- 4 -第 2 章 AD-HOC 网络的路由协议分类.- 5 -2.1 表驱动路由协议.- 5 -2.2 单路径和多路径 .-7 -2.3 几种典型的无线自组网路由协议 .- 11-2.3.1 目的序列距离矢量路由协议 DSDV.- 11 -2.3.2 按需平面距离矢量路由协议 AODV.- 11 -2.3.3 临时排序路由算法 TORA.- 12 -2.4 路由协议性能评标准 .- 12 -第 3 章 网络模拟器 NS2

7、.- 2 -3.1 NS2 简介.- 2 -3.2 NS2 组成部分.- 2 -3.3 NS2 模拟基本流程.- 2 -第 4 章 ADAD HOCHOC 网络多路径仿真网络多路径仿真研研究究.- 2 -4.1 多路径协议介绍 .- 2 -4.1.1 AOMDV 协议 .- 2 -4.1.2 移动节点的创建.- 1 -4.1.3 多路径计算 .- 1 -4.2 无线自组网路由模拟的实现 .- 2 -4.2.1 无线自组网路由协议场景的构建.- 2 -4.2.2 TCP 代理的创建和设置.- 2 -4.2.3 仿真参数的设置.- 3 -4.3 仿真结果分析 .- 1 -4.3.1 动画演示工具

8、nam.- 1 -4.3.2 无线 Trace 文件格式.- 2 -4.3.3 数据分析工具 gawk.- 1 -4.3.4 绘图工具 gnuplot.- 1 -4.3.5 仿真结果分析 .- 2 -第 5 章 结论 .- 2 -参考文献 .- 2 -致 谢.- 1 -第 1 章 引言1.1 无线自组网的产生和发展“Ad Hoc”一词来源于拉丁语，意思是“专用的、特定的” 。无线自组网通常也可称为“无固定设施网”或“自组织网” 。由于组网快速、灵活、使用方便，目前无线自组网已经得到了国际学术界和工业界的广泛关注，其应用也越来越广泛，已经成为移动通信技术向前发展的一个重要方向，将在未来的通信技术

9、中占据重要地位。无线自组网的前身是分组无线网(Packet Radio Network,PRNET)，对分组无线网的研究源于军事通信的需要。早在 1972 年，美国的 DARPA 就启动了分组无线网项目 PRNET，研究战场环境下利用分组无线网进行数据通信。在此之后，DARPA 于 1983 年启动了高残存性自适应网(Survivable Adaptive Network,SURAN)项目，研究如何将 PRNET 的研究成果加以扩展，以支持更大规模的网络，1994 年，DARPA 又启动了全球移动信息系统(Global Mobile Information Systems,GloMo) 项目，

10、旨在对能够满足军事应用需要的、高抗毁性的移动信息系统进行全面深入的研究。1991 年成立的 IEEE 802.11 标准委员会采用了“Ad Hoc”一词来描述这种特殊的自组织对等式多跳移动网络，无线自组网就此诞生。IETF 专门成立了(Mobile Ad Hoc Network,MANET) 小组来研究无线自组网的相关问题1。1.2 无线自组网的特征无线自组网由一组带有无线通信收发装置的移动终端节点组成，网络中每个终端可以自由移动且地位相等，是一个多跳、临时、无中心网络，因此它具有以下主要特征：（1）自组织：即网络的布设无需依赖于任何预先架设的网络设施。节点开机后就可以快速、自动地组成一个独立

11、的网络。（2）动态拓扑：即网络中的节点可以任意移动，并且可以随时关闭电台。发送装置的天线类型多种多样，发送功率的变化，无线信道间的相互干扰，地形和天气等综合因素的影响，造成网络的拓扑结构变化难测。（3）多跳路由：由于节点发射功率的限制，节点的覆盖范围是有限的。当要与其覆盖范围之外的节点进行通信时，需要中间节点的转发，即要经过多跳才能到达目的节点。（4）无中心且所有节点地位平等：节点可以随时加入或离开网络，任意节点故障不会影响整个网络运行，是一个无中心结构的对等式网络，抗毁性强。（5）灵活性好：无线自组网中的工作站可以随时加入或离开，这对于一些根据需求而需要随时组建网络的应用非常适合。1.3 无

12、线自组网应用领域由于无线自组网的特殊性，它适合用于无法或不便预先铺设网络设施的场合，以及其他需要快速自动组网的场合等。目前为止，其主要的应用领域有：（1）军事应用：军事应用是无线自组网技术的主要应用领域。因其特有的无需架设网络设施、可快速展开、抗毁性强等特点，无线自组网是数字化战场通信的首选技术。（2）无线传感器网络：传感器网络是无线自组网技术应用的另一大领域。采用传感器网络能够跟踪从天气到企业商品库存等各种动态事物，极大的扩充互联网的功能。对于很多应用场合来说传感器网络只能使用无线通信技术，并且传感器的发射功率很小。分散的传感器通过无线自组网技术组成一个网络，可以实现传感器之间和与控制中心之

13、间的通信。（3）个人通信：个人局域网(Personal Area Network,PAN)是无线自组网技术的又一应用领域，用于实现 PDA、手机、掌上电脑等个人电子通信设备之间的通信，并可以构建虚拟教室和讨论组等崭新的移动对等(Mobile Peer-To-Peer)应用。（4）移动会议：在室外临时环境中，工作团体的所有成员可以通过无线自组网方式组成一个临时网络来协同完成一项大的任务，或协同完成某个计算任务。在室内办公环境中，办公人员携带的包含无线自组网收藏器的 PDA 可以通过无线方式自动从台式机上下载电子邮件，更新工作日程表等。（5）其他应用：可应用于紧急和突发场合，如在发生了地震、水灾、

14、火灾或遭受其它灾难后，固定的通信网络设施无法正常工作的情况下组建无线自组网。还可与蜂窝移动通信系统等现有移动通信系统相结合，利用移动的多跳转发能力来扩展现有蜂窝移动通信系统的覆盖范围等。1.4 无线自组网体系结构参照 OSI/RM，无线自组网体系结构如图 2.1 所示2。图 1.4 无线自组网体系结构下面介绍各层的基本情况：（1）物理层：物理层包括射频(RF)电路、调制和信道编码系统。IEEE802.11b/a/g、蓝牙(Bluetooth)和超宽带(LJwB:ultr-awideband)等规范都是具体的物理层协议。（2）数据链路层:：数据链路层负责在不可靠的无线链路上建立可靠和安全的逻辑链

15、路。其分为逻辑链路控制子层(LLC)和媒介访问子层(MAC)。以 IEEE802.11 为例，其 LLC子层负责无线链路差错控制、流量控制、将网络层的分组组帧以及重传等，而 MAC 子层负责节点对无线媒介访问的控制和帧的加解密操作等。（3）网络层：网络层负责分组的路由，建立网络服务类型以及在传输与链路层之间传输分组。考虑到无线自网的动态性，网络层需要负责分组的重新路由和移动管理等。无线自组网在网络层的一个重要问题是路由协议。（4）传输层：传输层负责提供端到端的可靠数据传输服务。然而，由于无线链路的不稳定，传统的有线网传输层协议，在无线环境下性能下降明显，所以必须改进。（5）应用层：无线自组网的

16、应用层指定的是各种各样类型的业务。在实际实施的时候，可以采用各种各样的应用层协议和标准，比如 WAP(无线应用协议)协议等。1.5 文章研究内容1、查阅 Ad Hoc 路由协议文献，了解典型多路径路由协议工作原理，并了解其优缺点；2、深刻理解 AOMDV 协议的实现过程和所需条件；3、通过 NS2 仿真实现 AOMDV 协议；1.6 本文研究的应用Ad Hoc 网络的许多特点使它能应用于民用和军事等领域。首先网络的自组性为网络快速部署提供了可能。其次，网络多跳转发的特点可以在不降低网络覆盖范围的条件下减少每个终端的发射功率，从而为移动终端的小型化、低功耗提供了可能。从无线信道共享的角度来看，A

17、d Hoc 网络降低了信号冲突的概率，提高了信道利用率。另外，网络的抗毁性、鲁棒性满足了某些特定应用的需求。目前，Ad Hoc 网络主要应用场合包括：军事应用紧急和突发场合偏远野外山区移动会议和临时场合个人通信和网络商业应用 第 2 章 Ad-hoc 网络的路由协议分类由于 Ad hoc 网络的无线多跳转发、移动、带宽以及能量受限等特点，如何设计良好的路由策略是建立 Ad Hoc 网络的关键问题。目前 MANET WG 已经提出了许多协议草案，如 DSR、AODV、ToRA、ZRP 等。此外，国内外研究人和机构也发表了许多关于 Ad Hoc 网络路由协议的学术论文，比如 DSDV、WRP、QA

18、ODV、FSR、LANMAR、EAODV 等。这些路由协议根据路由建立的方和时间可以分为表驱动路由策略(TableDrive)和按需路由策略(OnDemand)两大类，如图 2.1 所示Ad Hoc 路由协议表驱动路由按需路由协议DSDVWRPDSRAODVTORAZRP 图 2.1 Ad hoc 路由协议分类2.1 表驱动路由协议 表驱动路由协议的路由发现策略与传统的路由协议类似，各移动节点通过周期性地广播路由信息分组来交换路由信息、主动发现路由。同时，节点必须维护到达网内所有节点的路由。它的优点是当节点需要发送数据分组时可以快速得到准确的路由信息，所需要的延时小；缺点是需要大量的控制分组来

19、尽可能保证路由的更新能够即时反应当前拓扑结构的变化，花费开销较大；而且，动态变化的拓扑结构可能使得这些路由更新变成过时的信息，路由协议将一直处于不收敛状态,不适合应用于无线网络。在早期的自组网路由协议的研究中，主要思路是修改有线网络的路由协议用以适应在自组网环境中运行。这些路由协议大部分属于表驱动路由协议。下面将介绍几种典型的表驱动路由协议。DSDV(Destination Distance Sequence Vector)是一种基于 Bellman Ford 算法的主动路由协议。它被认为是最早的 Ad Hoc 网络路由协议。DSDV 是一种无环路矢量距离路由AODV 也是一种典型的按需路由协

20、议。AODV 实质上就是 DSR 和 DSDV 的综合，它借用了 DSR 中路由发现和路由维护的基础程序，及 DSDV 的逐跳(H 叩一 by-HoP)路由、顺序编号和路由维护阶段的周期更新机制，以 DSDV 为基础，结合 DSR 中的按需路由思想并加以改进。AODV 包括 3 种基本的路由控制分组:路由请求分组(RREQ)、路由应答分组(RREP)、路由出错分组(RERR)。另外，AODV 还包括邻节点探测分组(HELLO)。其中，RREQ 包含的主要信息有源节点 IP 地址、源节点序列号、广播 D、目的节点正地址、目的节点序列号和源节点到当前接收到 RREQ 的节点的跳数:RREP 包含的

21、主要信息有源节点到目的节点的跳数、目的节点 IP 地址、目的节点序列号、源节点 IP 地址、路由生存时间;RERR 包含的主要信息有不可达的节点个数、不可达的目的节点正地址、不可达的目的节点序列号。AODV 由路由建立和路由维护两个过程组成。AODV 也是一种典型的按需路由协议。AODV 实质上就是 DSR 和 DSDV 的综合，它借用了 DSR 中路由发现和路由维护的基础程序，及 DSDV 的逐跳(H 叩一 by-HoP)路由、顺序编号和路由维护阶段的周期更新机制，以 DSDV 为基础，结合 DSR 中的按需路由思想并加以改进。AODV 包括 3 种基本的路由控制分组:路由请求分组(RREQ

22、)、路由应答分组 RREP)、路由出错分组(RERR)。另外，AODV 还包括邻节点探测分组(HELLO)。其中，RREQ 包含的主要信息有源节点 IP 地址、源节点序列号、广播 D、目的节点正地址、目的节点序列号和源节点到当前接收到 RREQ 的节点的跳数:RREP 包含的主要信息有源节点到目的节点的跳2.2 单路径和多路径 传统 Ad Hoc 网络单路径路由Ad Hoc 移动网络中单路径路由主要分成基于表驱动的被动路由,2j(如DSDV(Destination-SequencedDistance-VectorRouting)和按需主动路由协议(如DSR(DynamicSourceRouti

23、ng)J，AODV(AdHocOnDemandDistanceVectorRouting)两种。被动路由跟传统 Intemet 网络中的距离矢量算法类似，都是通过节点周期性交换路由表来实现的，只需稍做修改便可用于AdHoc 移动网络。主动路由一般都基于按需路由方式，通过泛洪广播实现，主要分为路由发现(RD：RouteDiscovery)和路由维护(RM：RouteMaintenance)两个阶段。 DSDV 协议 DSDV 协议是一种基于 Bellman-Ford 路由机制的，表驭动路由协议，是为移动 AdHoc 网络制定的。最早的路由协议之一。每个节点都维护一张路由表，节点通过与目的节点相关

24、的序列号判断路由的新旧，并依此避免路由环路的产生。每个节点周期性的将自己的路由表广播给其邻节点，其邻节点根据收到的路由表来更改自己的路由表。 DSR 协议动态资源路由协议 DSRl3 是用于移动节点多跳无线 AdHoc 网络的简单和有效的主动路由协议。使用 DSR 时，网络是自组织和自配置的，要求无既定的网络结构和管理。DSR 协议有两个主要的机制路由发现和路由维护一起工作，以实现 AdHoc 网络中源路由的发现和维护。路由发现。路由发现阶段主要由路由请求和路由响应两个阶段组成。只有当源节点s 试图向目的节点 D 发送数据，并且尚不知道 S 和 D 之间的路由时，启动路由发现机制。具体包括 R

25、REQ(Routerequest)分组对各节点对 RREQ 分组的处理，对信宿的路由回答RREP(Routereply)。路由维护。如果网络拓扑发生改变比如说链路中断导致 S 和 D 之间的路由无法再使用，此时启动路由维护十 JL 制。DSR 协议通过 MAC 层检测到链路断开，节点将“路由错误分组”RREQ 到发送信源，信源节点将删除该路由，重新进行路由发现，称为“逐跳MAC 确认”的网络。此外还有“逐跳 MAC 不确认”的网络和利用“端到端确认”的路由维护。DSR 不使用任何定期路由广告、链路状态感应、或者是邻居检测数据包，也不会依赖网络的下一层得到这些功能。DSR 使用外部“源路由” ，

26、即当要发一个数据包时，该数据包所需要经过的所有节点序列均包含在该数据包的包头中。 AODV 协议。AODV 路由协议是由 DSDV 改进得到的，与 DSDV 不同，它是按需路由协议。AODV 采用逐跳转发。报文的方式。另外 AODV 还支持组播路由和支持 QoS，其缺点是不支持单向信道，原因是路由回答报文。直接沿着路由请求的反向回到源节点。AODV 协议由路由发现过程和路由维护过程组成。单路径评价及问题分析。单路协议的优势在于它的简单性。但是这种简单性从根本上限制了单路协议性能的提升空间。Ad Hoc 网络中的带宽、节点能量等资源是相当有限的。同时，在链路上以及在路由器处的拥塞，也是造成 Ad

27、 Hoc 网络中较大延迟的主要原因。在 Ad Hoc 网络中使用单路路由协议，如果目的节点相同的数据包全部都在同一条路径上发送，当某条链路拥塞或者断开时，通过该链路发送的所有数据就都必须由新的路径发送，网络不能在轻载时充分利用资源，不能当网络发生拥塞或者链路断开时也较好地重新选择合适路径。在最近 Ad Hoc 路由研究中，人们提出了多路径路由方法来解决上述问题。多路径协议介绍。多路路由是指为任意一对节点同时提供多条可用的路径，并允许节点主机或应用程序)选择如何使用这些路径。多路路由算法为节点间提供多条路径，并确保发往其中一条路径的数据经由该路径到达目的地。多路路由网络是其中的路由器执行多路路由

28、算法的网络。从理论上证明了按需多路径拥有较长的路径存活时间和更可靠路由信息，而且拥有良好的性能，并能减少部分拥塞。因此近年来多路径研究得到广泛关注，主要分为 2 大类：多路径被动路由(如 DSDVM(Destination-Se-quencedDistanceVectorRoutingMultipath)和多路径主动路由协议(SMRJ7j，AOMDVJ)。如基于被动路由 DSDV 基础上扩展 DSDVM 通过修改内部数据结构等方法获取多路径支持；基于主动路由 DSR 扩展的 SMR，通过修改 DSR 路由发现机制，并通过目的节点获取最大不相交路径；出了基于 AODV 协议的多路径协议 AOMD

29、V。DSDVM 协议 DSDVM 是在 DSDV 基础上扩展的多路径路由协议。该协议通过获取和维护多条 Quasi 最短路径实现多路径路由协议。所谓 Quasi 最短路径是指该路径中除第 1 跳以外到目的节点距离最短的路径，Quasi 多路径是指从源节点到目的节点的一系列 Quasi最短路径集合。最短路径仅是 Quasi 最短路径的特例，称之为主路径，其他的 Quasi 最短路径称之为冗余路径，DSDVM 通过在源节点把数据分布在 Quasi 多条路径上来实现负载平衡。DSDVM 与 DSDV 不同之处在于内部数据结构和多路径计算。内部数据结构。DSDVM 跟 DSDV 类似，都是通过周期性跟

30、相邻活动节点交换路由信息更新路由表，所不同的是内部数据结构。DSDVM 每个节点的路由表中都包含如下的路由信息：目的节点地址，下跳地址(主路径的下跳地址)，主路径到达目的节点的跳数，目的序列号，前置节点地址和一个包含 Quasi 冗余路径下跳地址的集合。每次路由更新都把新检测到的相邻节点按照一定的计算添加到 Quasi 冗余路径。多路径计算。DSDVM 通过判断相邻节点(非主路径上的下跳地址)是否在主路径上，如果不是在主路径上，将该地址添加到下跳地址的链接表中，否则丢弃，从而实现无环多路径。SRM 协议。SRM 是 DSR 协议的一个扩展，其研究侧重点是频繁发生的路由发现所带来的开销。协议的主

31、要思想是为源节点和中间节点提供一条以上的替换路径(AlternateRoute)。由于替换路径与主路径是独立路径，当主路径失效时，数据传输不会被打断，而是换用替换路径来继续发送数据包，属于按需多路径路由协议。路由发现。SRM 的路由发现过程和 DSR 基本相似，不同的是，当第 1 个路由请求RREQ 包到达目的节点后，目的节点除了向源节点发送路由应答 RREP 包外，还记录下这条路径作为主路径。对于随后到达的路由请求包，如果其中的路径和所记录的所有路径都是独立路径，目的节点就发送相应的路由应答包，同时记录下这条路径；否则，直接丢掉该路由请求包。这样既可以保证当主路径失效时，其他路径还可以发包(

32、因为它们和主路径是相互独立的)，又避免了目的节点因发送路由应答包过多而带来不必要的网络拥塞。路由维护。当中间节点检测到链路断开后，利用替换路径把数据包重新发送出去，并且向上游节点和源节点发送 RRER，请求它们把包含该链路的路径删除；当源节点收到RRER 后，使用以下两种路由策略重新做路由发现：1)只要收到路径断开消息，就重新做路由发现，这样可以获取最新的网络信息；2)只有收到两条(或多条)路径都断开的消息后，才重新做路由发现，这样可以减少部分路由开销。SMR 试验表明，使用第 2 种路由，发现策略性能较好。 AODVM 协议。AODVM(AdHocOndemandDistanceVector

33、Multipath)多路路由协议也是在 AODV 的基础上进行扩展的，与 AODV 协议中直接丢弃 RREQ 包的拷贝不同，中间节点会将包含在这些包中的信息记录在一个表(RREQ 表)中。对每个接收到的 RREQ 消息的拷贝，接收的中间节点将产生该 RREQ 消息的信源，该 RREQ 要去的信宿；把该 RREQ 的邻居，以及其他的一些额外信息记录传输到该 RREQ 表中，但不能直接向信源发送 RREP 消息。路由发现。AODVM 路由发现阶段与 AODV 类似，当信宿从其某个邻居处接收到第 1个 RREQ 包时，它便更新自己的序列号同时产生一个 RREP 消息。RREP 包包含一个额外的域“L

34、asthopID” ，用来说明该 RREQ 的拷贝来自哪个邻居。该 RREP 包沿传输过该 RREQ 拷贝的路径反向发送到信源。当信宿从其他邻居处接收到该 RREQ 包的拷贝时，每次都更新其序列号，同时产生一个 RREP 包。同第 1 个 RREP 包一样，这些 RREP 包也包含对应的最后一跳节点的 ID(LasthopID)。当一个中间节点从它的邻居处接收到一个 RREP 包时，它便从它的 RREQ 表中删除掉对应该邻居的表目，同时在路由表中增加一个路由表目，以显示到己经发现的 RREP 包发起者(即信宿)的路由；然后该节点通过 RREQ 表，识别一条到信源最近的路径，将该 RREP 消息

35、传输到相应的邻居。RREQ 表中对应该邻居的条目即被删除。为了确保一个节点没有被多条路径共享，即保证路径的节点不相关，当节点侦听任一其他节点广播 RREP 消息时，它们便从 RREQ 表中删除对应该传输节点的条目。路由维护。当一个中间节点接收到 RREP 消息而无法继续往前传输(其 RREQ 表所有下跳地址的路径都失效时)，便产生一个路由发现错误消息(RDER：RouteDiscoveryError)，并把该消息发送到将 RREP 消息发送给其邻居节点。邻居一旦接收到该 RDER 消息，便将RREP 消息发送给另外的邻居，以便在可能时将 RREP 消息传输至信源。RDER 消息的数量会受到限制

36、，以避免该数据包的大量产生和交换。其他多路径路由协议。MSR 是在 DSR 基础上扩展的，利用中间节点和目的节点反馈多条路径，并使用路径探测来减少网络拥塞和网络延迟；AODVBR 在 AODV 基础上建立多条路径来为路由出错的数据包提供替换路径支持；通过在路由响应阶段重定向响应路径实现多条节点不相交路径；ARP 通过路径拆分来实现多路径；提出一种基于多样性编码的方法来建立多条路径，并把数据包分发到多条路径发送，藉此来提高可靠性和发送率。MMPRE 提供了基于网眼的多路径寻径和包发送。AMR2-23使用网络最大流获取多条节点不相交路径，并利用多条路径并行或者并发发送数据来提高网络流通量和负载平衡

37、。多路径协议应用。以上多路径协议主要集中于如何提高网络传输率，降低网络延迟以及提高网络负载平衡，但多路径协议在 QoS、能源、安全等方面也有自身的优势。如TBP 提出通过发送选票来并行探测多条较优的路径，并通过资源预留方式实现 QoS；提出在多项式复杂度内找到多条链路不相交或者节点不相交路径减少源消耗。文献11提出一种基于并行网络流方式的自适应多路径路由协议，并通过时间限制来避免恶意 DOS 攻击，以提高网络安全性。2.3 几种典型的无线自组网路由协议2.3.1 目的序列距离矢量路由协议 DSDVDSDV(Destination-Sequenced Distance-Vector)是基于经典

38、Bellman-Ford 路由选择过程的改进型路由表算法。DSDV 以路由信息协议为基础。是无线自组网协议发展较早的一种。使用 DSDV 时，网络中的每一个移动节点都需要维护一个路由表。路由表表项包括目的节点、跳数和一个由目的节点注明的序列号，序列号能帮助节点区分有效和过期的路由信息，并可防止路由环路的发生。标有更大序列号的路由信息总是被接收。如果两个更新分组有相同的序列号，则选择跳数最小的，使路由最优（最短） 。每个节点必须周期性地与邻节点交换路由信息，当然也可以根据路由表的改变来触发路由更新。路由表更新有两种方式：一种是全部更新，即拔掉更新消息中将包括整个路由表，主要应用于变化较快的情况；

39、另一种是增量更新，更新消息中仅包含变化的路由部分，通常适用于变化较慢的情况。2.3.2 按需平面距离矢量路由协议 AODV AODV(Ad hoc On-demand Distance Vector Routing)由 DSDV 发展而来，不同的是AODV 为反应式路由协议。源节点首先广播一个携带目的节点信息的路由分组（RREQ） ，其邻居节点依次向周围节点广播此路由分组，广播 RREQ 前会建立此节点到源节点的路由，直到路由分组到达目的节点或者一个中间节点，这个节点包含目的节点的路由信息，就不再广播 RREQ。此过程中，会建立一个从源节点到目的节点的反向路由，也就是从目的节点到源节点的路由。

40、然后该节点将沿着反向路由发回一个 RREP，RREP 到达源节点后路由发现过程结束。为避免路由循环，每一个路由分组中都包括一个 sequence ID（SID）作为唯一标识，如果一个节点收到一个 SID 比它当前保留的 SID 小的数据包，表明该数据包是过时的，它将不予处理，而是简单的丢弃。发现多条路由时，源节点会选择一条 SID 大、跳数少的最优路由。 源节点移动后会重新启动路由发现过程，中间节点移动，那么其邻居节点会发现链路失效并向上游节点发送链路失效消息（RERR） ，一直传到源节点，然后源节点重新发起路由发现，或者也可以由发现链路失效的节点自己发起路由发现，此称为自修复。只要路由是活动

41、的，路由表就要一直维护下去。活动的意思是有数据包从源节点发往目的节点，如果链路上不再有数据包传递，一段时间之后，链路就会过期，最终路由信息将会从中间节点的路由表中删除6。2.3.3 动态源路由协议 DSRDSR(Dynamic Source Routing)是一种基于源路由的按需路由协议，它使用源路由算法而不是逐跳路由的方法。DSR 主要包括两个过程：路由发现和路由维护。当源节点 S向目的节点 D 发送数据时，它首先检查缓存是否存在未过期的到目的节点的路由，如果存在，则直接使用可用的路由，否则启动路由发现过程。具体过程如下：源节点 S 将使用洪泛法发送路由请求消息（RREQ） ，RREQ 包含

42、源和目的节点地址以及唯一的标志号，中间节点转发 RREQ，并附上自己的节点标识。当 RREQ 消息到达目的节点 D 或任何一个到目的节点路由的中间节点时，D 或该中间节点将向 S 发送路由应答消息（RREP） ，该消息中将包含到 S 到 D 的路由信息，并反转 S 到 D 的路由供 RREP 消息使用。此外，中间节点也可以使用路由缓存技术（Routing Cache）来对协议作进一步优化。2.3.4 临时排序路由算法 TORA TORA(Temporally Ordered Routing Algorithm)协议称为临时排序路由算法，是一种源初始化按需路由选择协议，它采用链路反转的分布式算法

43、，具有高度自适应、高效率和较好的扩充性，比较适合高度动态移动、多跳的无线网络，其主要特点是控制报文定位在最靠近拓扑变化的一小部分节点处，因此节点只保留邻近点的路由信息。该算法中路由不一定是最优的，常常使用次优路由以减少发现路由的开销。TORA 协议包括 3 个基本模块：路由的创建、路由的维护和路由的删除。在路由的建立和路由维护过程中，节点应用“高度”Metric 来建立一个以目的节点为根的有向非循环图。这样链路根据相邻两个节点的高度值来确定向上或向下的方向。2.4 路由协议性能评标准主要包括以下几个方面的指标7：（1）丢包率：网络中数据传输是以发送和接收数据包的形式进行的，理想状态下发送了多少

44、数据分组就能接收多少数据分组，但是由于信号衰减、网络质量等诸多因素影响下，可能产生数据分组丢失。在单位时间内未收到的数据分组与发送的数据分组的比率就是丢包率，当然这个数字越小越好。丢包率的计算公式见式（4.1） 。丢包率= （4.1）发送分组数未接收到的分组数 （2）端到端平均时延：指单位数据包从源节点到目的节点所用的时间，时延越小，说明响应越快，网络质量越令人满意。该统计量反应了网络的拥塞状况，计算公式见式（4.2） 。端到端平均时延= （4.2）数据包总数所用时间源节点数据包成功传输 （3）路由开销：单位数据包个数所引起的额外路由分组个数，包括 RREQ（Route Request，路由请

45、求） 、RREP（Route Reply，路由应答） 、RRER（Route Error，路由错误）等，该统计量反应了路由协议的效率，计算公式见式（4.3） 。路由开销= （4.3）发数的数据分组数发送的路由分组数(4)平均吞吐量：该参数是在接收数据时由网络层的上层统计的，是指节点单位时间内收到的数据分组数，它是一个容量概念，表示数据传输的总量。第 3 章 网络模拟器 NS23.1 NS2 简介NS2（Network Simulator Version2）是一款开放源代码的网络模拟软件，最初由加州大学伯克分校（UC Berkeley）开发。它最初的开发目的是为了研究大规模网络以及当前和未来网络

46、协议的交互行为。它为模拟研究有线和无线网络上的 TCP/IP、路由和多播等协议提供了强有力的支持。NS2 是一个开放源代码软件，任何人可以获得、使用和修改其源代码。正因为如此，世界各地的研究人员每天都在扩展和更新它的功能，为其添加了新的协议和功能。它也是目前网络研究领域应用最广泛的网络模拟软件之一。NS2 来源于 1989 年的 Real NetWork Simulator 项目，经过多年的发展，于 1995 年得到 Xerox 公司的支持，加入 VINT 项目。NS2 一直以来都在吸收全世界各地研究者的成果3。NS2 是一款面向对象的、离散事件驱动的网络模拟器，可以完整地模拟整个网络环境。N

47、S2 使用一整套 C+类库实现了绝大多数常见的网络协议以及链路层的模型，利用这些类的实例就可以搭建起整个网络的模型。NS2 使用了被称为分裂对象模型的开发机制。采用 C+和 OTcl 两种开发语言进行开发。它们之间采用 TclCL 进行自动连接和映射。考虑效果和操作便利等因素，NS 将数据通道和控制通道的实现相分离。为了减少分组和事件的处理时间，事件调度器和数据通道上的基本网络组件对象都使用 C+编写，这些对象通过 TclCL 映射对 OTcl 解释器可见。NS2 可以说是 OTcl 的脚本解释器，它包含模拟事件高度器、网络组件对象库等。事件调度器控制模拟进程，在适当时间激活事件队列中的当前事

48、件，并执行该事件。网络组件模拟网络设备或节点的通信，它们通过制定模拟场景和模拟进程，交换特定的分组来模拟真实网络情况，并将执行情况记录到日志文件中，供用户分析解读，获取模拟结果。NS2 采用这种分裂模型既提高了模拟效率，加快了模拟速度，又增强了模拟配置的灵活性和操作的简便性。NS2 是在 UNIX 系统上开发的，因此可以在 UNIX 和类 UNIX 系统上安装。另外，NS2也可以在 Windows 平台上运行。表 3.1 和表 3.2 是不同平台对 NS 的支持情况。表 3.1 不同平台对 NS2 的支持情况Tcl-TKOTclTclCNsNamxgraphcwebsgbGt-itm and

49、sgb2nszlibPc+WindowsYYYYYNYNNNPc+LinuxYYYYYYYYYY注：Y支持，N不支持。表 3.2 综合比较 Windows 和 Linux 对 NS2 的支持情况平台特点安装过程模块支持使用过程Pc+Windows优点：界面友好，人性化设计，网络及硬件支持良好，应用程序丰富。缺点：代码冗繁，系统稳定性及自身修复能力差。未安装 Cygwin 时只可用 from all the pieces 方式安装，较为复杂。安装 Cygwin 后可用 allinone 方式安装较为简单。支持 NS2 的必选软件模块，但对可选模块的支持性差。容易引发较多问题，相关帮助文档及可咨询

50、信息较少，解决问题难度较大。Pc+Linux优点：源代码开放，界面友好，网络功能丰富，较稳定。缺点：应用软件及硬件驱动程序缺乏。可选用 from all the pieces 或 allinone方式安装，较为简单。对 NS2 的必选模块和可选模块支持性良好。由于 Linux 完全开放源代码的特性，可根据需要任意修改源代码。相关帮助文档及论坛较多，可获得的帮助较多，使问题解决较为容易。NS2 的模拟分为两部分：用 C+编写特定网络元素的实现；用 OIcl 编写模拟所需的脚模拟本文件，在文件中使用这些网络元素；二者之间的结合由 NS2负责完成，NS2 规定一个固定的步骤，按照规定的步骤去做即可。

51、NS2 可以完成的功能包括：(1)构建网络拓扑。NS2 中网络拓扑是由 node 和 link 构成，其中 node 大约可被看作是对实现网络底三层设备的一个模拟，link 则可被视为是对物理传输链路的模拟。(2)实现 RTP 协议的 Agent。NS2 中，Agent 是对某一个网络协议的模拟，NS2 预先实现了 UDP Agent 和 TCP Agent 以及一些常用网络应用协议的 Agent。(3)加载应用数据流由 ApplicationTraffic 来实现。RTP Agent 本身已实现了产生数据流的工作，无须加载 Application。3.2 NS2 组成部分 Tclobject

52、 在类层次结构中处于最高层，所有其他主要的类都从它派生而来。它有一个静态链表记录了用户创建的所有对象，每一个对象都有一个唯一的标识，记录了每个对象所属的类名。使用这种公共基类的好处是各种对象可以存储在同一个链表中，使用对象的函数知道如何处理对象和简单地进行强制类型转换以满足自己的需要。（1）离散事件调度器（Scheduler）：调度器是仿真器的心脏，它记录当前时间，调度网络事件链表中的事件。它有一个静态成员变量 instance，供所有的类访问同一个调度器，提供函数产生新事件，指定事件发生的时间。目前 NS2 支持四种事件调度器，分别为链表式（linked-list） 、堆式（heap） 、时

53、间队列式（calendar）和实时（real-time）调度器，其中时间队列式为默认的事件调度器。（2）事件处理器(Handler)：Handle 是所有处理事件类的基类，它只是一个虚拟函数，每个继承类实现自己的功能。（3）节点（Node）：节点是对实际网络中分布在不同地理位置的主机、交换机、路由器等网络设备的统一抽象，是构成网络拓扑结构的一个重要组成部分。（4）链路(Link)：链路用来连接节点和路由器。一个节点可以有一条或多条输出链路(如路由器)，所有的链路都以队列的形式来管理分组到达、离开或丢弃，统计并保存字节数和分组数。另外还有一个独立的对象来记录队列日志。（5）代理(Agent)：代

54、理是实际产生和消费分组的对象，它们属于传输层实体，运行在端主机，节点的每一个代理自动被赋与一个唯一的端口号(模拟 udp/tcp 端口)，代理知道与它相连的节点，以便把分组转发给节点，它也知道分组大小，业务类型，目的地址。Agent 类是各种 UDP/TCP 实现类的基类，代理被保存在一个称为 demux 的链表中。（6）NS 对象(NsObject)：NsObject 是所有网络实体的基类，包括节点、链路、代理，业务记录(Trace)和数据源等。节点、链路、代理同时继承了 NsObject 和事件处理器类，因为这三种对象要处理多种事件，其他对象则不需要。（7）匹配器类(Matcher)：匹配

55、器类用来标识有实例对象生成的类，用户给出标识匹配器类的关键字，匹配器类返回相应的新建对象。匹配器类被定义成静态的，只允许一个实例对象4。NS 功能非常强大，由 12 个模块组成，下面分别介绍各模块的功能：(1)Tel：Tel 提供了一个强有力的平台，可以生成面向多种平台的应用程序、协议、驱动程序等等。它与 Wk(toolkit)协作，可生成 GUI 应用程序，可在【，c、Unix 和Macintosh 上运行。Tcl 还可用来完成与网页相关的任务，或是为应用程序提供强有力的命令语言。(2)Tk：与 Tel 协调工作的图形工具包。(3)OTcl：即 MIT Object Tcl，是 TclTk

56、面向对象编程的扩展。(4)Tel cl：此目录下含 telC+的接口，vic、vat、ns、rtpplay、和 nam 都会用到。(5)NS：NS 主体代码，内含一个节点移动产生器、两个传输事件产生器。(6)TclDebug：Tcl 调试工具包。(7)Nam：即 UCBLBNL Network AniMator， 占与 NS 协同工作，将 NS 仿真过程动态表现出来。(8)Xgraph：Xgraph 是 X-Windows 应用程序，包含交互式测量和绘制和动画效果。(9)Gtitm：GT Internetwork Topology Models 的简称，产生模拟 j nternt 网络结构的拓

57、扑图，还提供了一些例子。(10)SGB：Standford GraphBase 的简称，图形产生器。(11)Cweb：与网页相关的工具。(12)zlib：通用数据数据压缩库(data compression library)。对于 NS 来说Tel，Tk，Otcl，TclDebug，Nam，Xgraph，Gtitm，SGB，Cweb，zlib 等均为现成工具包。3.3 NS2 模拟基本流程 图 3.1 NS2 进行网络模拟的基本流程是否否否是是问题定义修改源码？修改源码编写 Tcl 脚本执行模拟分析结果结果满意？分析问题重新编译 NS编译通过？调试结束开始 使用 NS2 进行网络模拟的基本操作

58、流程如图 3.1 所示。整个模拟过程主要有三个部分：一为修改源码，二为编写 Tcl 模拟脚本，三为分析结果。（1）源码修改：这一步只有在模拟需要修改源代码时才进行考虑。（2）Tcl/OTcl 模拟代码编写：这是 NS2 模拟中最重要和必不可少的环节，大部分NS2 的模拟工作实际就是编写 Tcl 脚本代码来描述网络结构、网络构件属性和控制调度网络模拟事件的启停过程。（3）模拟结果分析：结果分析是真正体现模拟工作成效的重要一环，模拟结果分析主要是对 trace 文件进行分析。NS 仿真需要 C+编译器和通用的操作系统(如各种 UNIX、Linux 或 Windows 系列)。进行仿真前，首先要分析

59、涉及仿真的哪一个层次。Ns 仿真分两个层次：一个是基于 OTcl 编程的配置、构造层次，利用 Ns 已有的网络仿真元素实现仿真，无需对 Ns 本身进行任何修改，只要编写 OTcl 仿真脚本，如图 42 中流程卜 24；另一个层次是基于 c+和 OTcl 编程的编译、配置层次，如果 Ns 中没有所需的仿真元素，Ns 提供了用户自我升级或修改协议的技术，即利用 OTcl 和 NS 的接口类实现 NS 的更新，新 NS 生成流程如图 42 中 l35，然后再进行卜 26 流程完成仿真。NS 的仿真工作机制如图 42 所示。第 4 章 无线自组网路由协议仿真4.1 多路径协议介绍多路路由是指为任意一对

60、节点同时提供多条可用的路径，并允许节点主机或应用程序)选择如何使用这些路径。多路路由算法为节点间提供多条路径，并确保发往其中一条路径的数据经由该路径到达目的地。多路路由网络是其中的路由器执行多路路由算法的网络。从理论上证明了按需多路径拥有较长的路径存活时间和更可靠路由信息，而且拥有良好的性能，并能减少部分拥塞。因此近年来多路径研究得到广泛关注4.1.1 AOMDV 协议AOMDV(Ad hoc On-demand Multipath Distance Vector)按需多路径距离矢量路由协议是基于 AODV 的扩展，在路由发现过程获取多条无环且链路不相交路径。与 AODV 主要不同有两点：建立