1、Abstract: Ad Hoc network is a new technique in wireless communication field which develops rapidly in recent years. As it does not depend on fixed network infrastructure, and has no central controlling node as well as good in resisting destructions, it is applicable to many situations that have diff
2、iculties in wiring networks. Based on these special advantages, Ad hoc plays an important part in military applications, and it also has a good prospect in civil applications. DSR protocol is an on-demand routing protocol that is specifically designed for Ad hoc. It attracts widely attention because
3、 of its advantages such as its simplicity, low network overhead, low algorithm complexity, supporting unidirectional routes and so on. So DSR protocol will probably play an important role in future Ad hoc application. NS2 （Network Simulator Version 2）, developed by UC Berkeley, is a simulator driven
4、 by discrete events. It can simulate a routing protocol operation process of Ad Hoc network, and export simulation results to a trace file. From the trace file, we can know the operation process of routing protocol, then analyze and evaluate the performance of routing protocol. This paper, first of
5、all, introduces the basic concept, key technologies and routing protocols of Ad Hoc Network. Secondly, for the concept, feature and working principle of DSR，the paper gives a detailed introduction and analysis. Then, to evaluate the performance of DSR and AODV, we established a simulation platform o
6、f wireless network model based on the NS2。The simulator results show that compared with AODV, DSR performs better in the network with dynamic topology. At last, the paper analyzes the improvement and makes a summary of DSR.Key words：Ad Hoc, DSR protocol，Optimization，Network simulation，NS2第一章 绪论1.1 A
7、d hoc网络1.1.1 Ad hoc网络的产生与发展我们经常提及的移动通信网络一般都是有中心的，要基于预设的网络设施才能运行。例如，蜂窝移动通信系统要有基站的支持；无线局域网一般也工作在有AP接入点和有线骨干网的模式下。但对于有些特殊场合来说，有中心的移动网络并不能胜任。比如，战场上部队快速展开和推进，地震或水灾后的营救等。这些场合的通信不能依赖于任何预设的网络设施，而需要一种能够临时快速自动组网的移动网络。Ad hoc网络可以满足这样的要求。 Ad hoc网络的前身是分组无线网（Packet Radio Network）。对分组无线网的研究源于军事通信的需要，并已经持续了近20年。早在19
8、72年，美国DARPA（Defense Advanced Research Project Agency）就启动了分组无线网（PRNET,Packet Radio NETwork）项目，研究分组无线网在战场环境下数据通信中的应用。项目完成之后，DAPRA又在1993年启动了高残存性自适应网络（SURAN,SURvivable Adaptive Network）项目。研究如何将prnet的成果加以扩展，以支持更大规模的网络，还要开发能够适应战场快速变化环境下的自适应网络协议。1994年，DARPA又启动了全球移动信息系统（GloMo,Globle Mobile Information Syste
9、ms）项目。在分组无线网已有成果的基础上对能够满足军事应用需要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究，并一直持续至今。1991年成立的IEEE802.11标准委员会采用了“Ad hoc网络”一词来描述这种特殊的对等式无线移动网络。在Ad hoc网络中，结点具有报文转发能力，结点间的通信可能要经过多个中间结点的转发，即经过多跳（MultiHop），这是Ad hoc网络与其他移动网络的最根本区别。结点通过分层的网络协议和分布式算法相互协调，实现了网络的自动组织和运行。因此它也被称为多跳无线网（MultiHop Wireless Network）、自组织网络（SelfOrganiz
10、ed Network）或无固定设施的网络（Infrastructureless Network）。1.1.2 Ad hoc网络的特点Ad hoc网络是一种特殊的无线移动网络。网络中所有结点的地位平等，无需设置任何的中心控制结点。网络中的结点不仅具有普通移动终端所需的功能，而且具有报文转发能力。与普通的移动网络和固定网络相比，它具有以下特点：（1）无中心Ad hoc网络没有严格的控制中心。所有结点的地位平等，即是一个对等式网络。结点可以随时加入和离开网络。任何结点的故障不会影响整个网络的运行，具有很强的抗毁性。（2）自组织网络的布设或展开无需依赖于任何预设的网络设施。结点通过分层协议和分布式算法
11、协调各自的行为，结点开机后就可以快速、自动地组成一个独立的网络。（3）多跳路由当结点要与其覆盖范围之外的结点进行通信时，需要中间结点的多跳转发。与固定网络的多跳不同，Ad hoc网络中的多跳路由是由普通的网络结点完成的，而不是由专用的路由设备（如路由器）完成的。（4）动态拓扑Ad hoc网络是一个动态的网络。网络结点可以随处移动，也可以随时开机和关机，这些都会使网络的拓扑结构随时发生变化。 这些特点使得Ad hoc网络在体系结构、网络组织、协议设计等方面都与普通的蜂窝移动通信网络和固定通信网络有着显著的区别。1.1.3 Ad hoc网络的应用领域由于Ad hoc网络的特殊性，它的应用领域与普通
12、的通信网络有着显著的区别。它适合被用于无法或不便预先铺设网络设施的场合、需快速自动组网的场合等。针对Ad hoc网络的研究是因军事应用而发起的。因此，军事应用仍是Ad hoc网络的主要应用领域，但是民用方面，Ad hoc网络也有非常广泛的应用前景。它的应用场合主要有以下几类：（1）军事应用军事应用是Ad hoc网络技术的主要应用领域。因其特有的无需架设网络设施、可快速展开、抗毁性强等特点，它是数字人战场通信的首选技术。Ad hoc网络技术已经成为美军战术互联网的核心技术。美军的近期数字电台和无线互联网控制器等主要通信装备都使用了Ad hoc网络技术。（2）传感器网络传感器网络是Ad hoc网络
13、技术的另一大应用领域。对于很多应用场合来说传感器网络只能使用无线通信技术。而考虑到体积和节能等因素，传感器的发射功率不可能很大。使用Ad hoc网络实现多跳通信是非常实用的解决方法。分散在各处的传感器组成Ad hoc网络，可以实现传感器之间和与控制中心之间的通信。这在爆炸残留物检测等领域具有非常广阔的应用前景。（3）紧急和临时场合在发生了地震、水灾、强热带风暴或遭受其他灾难打击后，固定的通信网络设施（如有线通信网络、蜂窝移动通信网络的基站等网络设施、卫星通信地球站以及微波接力站等）可能被全部摧毁或无法正常工作，对于抢险救灾来说，这时就需要Ad hoc网络这种不依赖任何固定网络设施又能快速布设的
14、自组织网络技术。类似地，处于边远或偏僻野外地区时，同样无法依赖固定或预设的网络设施进行通信。Ad hoc网络技术的独立组网能力和自组织特点，是这些场合通信的最佳选择。（4）个人通信个人局域网（PAN,Personal Area Network）是Ad hoc网络技术的另一应用领域。不仅可用于实现PDA、手机、手提电脑等个人电子通信设备之间的通信，还可用于个人局域网之间的多跳通信。蓝牙技术中的超网（Scatternet）就是一个典型的例子。（5）与移动通信系统的结合Ad hoc网络还可以与蜂窝移动通信系统相结合，利用移动台的多跳转发能力扩大蜂窝移动通信系统的覆盖范围、均衡相邻小区的业务、提高小区
15、边缘的数据速率等。 在实际应用中，Ad hoc网络除了可以单独组网实现局部的通信外，它还可以作为末端子网通过接入点接入其他的固定或移动通信网络，与Ad hoc网络以外的主机进行通信。因此，Ad hoc网络也可以作为各种通信网络的无线接入手段之一。1.2 Ad Hoc研究的问题和技术挑战1.2.1进行相关研究的主要大学和组织无线Ad Hoc网络的诸多优良特性，使其在军事及民用领域都有着广阔的发展前景。目前Ad Hoc技术是无线通信领域的一门热门技术，国际上有许多研究机构致力于研究适用于具体应用的Ad Hoc无线网络技术，这些机构包括：美国加州大学洛杉矶分校的“Wireless Adaptive
16、Mobility Lab”；美国加州大学圣克鲁兹分校的“The Computer Communications Research Group”；美国康奈尔大学的“Wireless Networks Laboratory”；美国伊利诺斯大学Urbana-Champaign分校的“Wireless Networking Group of Coordinated Science Laboratory” 和“Multimedia Operating Systems and Networking Group”；美国加州大学圣巴巴拉分校的“The Mobility Management and Netwo
17、rking Lab”；Internet工程任务组（IETF）也成立专门的研究小组MANET（Mobile Ad Hoc Networks）工作组，负责Ad Hoc网络路由协议的标准化工作。随着Ad Hoc网络技术不断发展，目前已有一些产品面市，例如：由NCR公司生产的Ad Hoc设备在商场内利用RFID技术很容易地找到某种商品和价格；在日本的Nankoku市已经使用Wireless Mesh连接了13个小学、4个中学和18个市政建筑；美国的MeshNetworks公司开发出的无线硬件和智能路由软件，可以构建Wireless Mesh网络支持诸如手机和笔记本等移动终端自由接入或退出网络。国内对A
18、d Hoc网络的研究起步较晚，研究机构主要是高校和研究所，如解放军理工大学、清华大学、北京交通大学、西安电子科技大学等，目前的研究还处于理论和技术跟踪分析的初级阶段，成果主要集中在路由协议和MAC协议的研究上。1.2.2研究问题和技术挑战由于Ad Hoc网络无中心、自组织、动态拓扑等特殊性，传统固定网络和移动通信网中使用的各种协议和技术无法直接应用于Ad Hoc网络中，因此需要为Ad Hoc网络设计专门的协议和技术。目前Ad Hoc网络研究所面临的主要问题和技术挑战包括：MAC协议、路由协议、安全问题和功率控制等。（1）MAC协议MAC协议是Ad Hoc网络协议的重要组成部分，是分组在无线信道
19、上发送和接收的主要控制者。Ad Hoc网络采用多跳共享的多点信道，当一个节点发送分组时，只有在它覆盖服务内的节点才能收到。这种共享广播信道的方式，导致Ad Hoc网络存在隐藏终端、暴露终端和入侵终端等问题。（2）路由协议Ad Hoc网络的特殊性使得路由协议的设计面临着非常艰巨的技术挑战。从无线信道带宽窄的角度来看，路由协议在节点间交互的信息应尽量少，以减小路由协议的开销，提高信道的效率；而从网络拓扑的角度来看，节点的移动、无线信道的不规则性、发射功率的变化等特点，使得无线自组网的拓扑变化比较频繁，为了能够尽快、尽可能精确地反映网络拓扑的变化，就需要更加频繁地在节点间交互控制报文。这本身就是一对
20、矛盾。因此，设计一个在所有情况下都普遍适用的Ad Hoc网络路由协议基本上是不太可能的。目前，针对Ad Hoc网络已提出了许多路由协议。这些路由协议从不同的角度对无线多跳路由问题进行分析和研究，对某一个或几个指标进行优化，以适用于不同的应用环境。主要包括以下几方面：可靠性、可扩展性、QoS路由、组播路由、网络互联、定位辅助等。（3）安全问题Ad Hoc网络是通过移动节点间的相互协作保持网络互联，它不具备传统网络的安全策略。如传统网络拥有专门的路由器、专门的密钥管理中心和分发公用密钥的目录服务机构来管理加密、认证、访问、控制、权限管理和防火墙等。因此Ad Hoc网络比一般的网络更容易受到安全方面
21、的攻击。目前已经提出的安全策略有：基于密码的认证协议、“复活鸭子”的安全模式、异步的分布式密钥管理等。（4）功率控制Ad Hoc网络的多跳转发特性使得节点以较小的功率就可以实现网络在较大范围内的覆盖，通过节点的功率控制来提高信道的空间复用度，同时减小对邻近节点的干扰，达到增加网络容量的目的。此外，Ad Hoc网络中的大多数节点是以电池供电，因此需要进行功率控制，来减少网络的能量消耗，延长网络的寿命。1.3 Ad hoc网络路由协议Ad hoc网络中，路由协议的主要作用是监控网络拓扑结构变化，交换路由信息，产生、选择和维护路由，并根据选择的路由转发数据，以提供网络的连通性。然而，由于终端的移动性
22、、网络拓扑结构的可变性、传输的多跳性、无线信道的不可靠性、网络资源的有限性等众多移动自组网特性，使得 Ad hoc网络路由协议的研究面临着巨大挑战。因此，路由协议成为Ad hoc网络研究的焦点问题之一。 传统路由协议，如 RIP（Routing Information Protocol）协议和 OSPF（Open Shortest Path First）协议，都是针对拓扑结构固定的有线网络设计的，并不适用于拓扑结构动态、随机变化的移动自组网，因此必须设计适合 Ad hoc 网络环境特点的新的路由协议。多年来，研究者们已提出数十种 Ad hoc 路由协议方案。可从不同角度对这些协议进行分类：根据
23、路由发现策略的不同，可将其分为表驱动路由（Table Driven Protocols）、按需驱动路由（On-Demand Driven Protocols）和混和路由；根据网络拓扑结构的差异，可将其分为平面结构路由（Flat Protocols）和分簇路由（Clustered Protocols）；根据是否使用 GPS（Global Position System）系统作为路由辅助条件，可将其分为地理定位辅助路由和无地理定位辅助路由。1.3.1表驱动路由协议表驱动路由（又称先验路由、主动路由）继承了传统的路由算法，但在消除路由环路和已过时路由等方面进行了适应于自组网特性的改进。传统有线网络的
24、经典路由算法包括链路状态协议和距离矢量两种。链路状态协议中每个节点都要保存整个网络的拓扑信息以及每条链路的开销，为了使所有节点中保存的路由保持一致，每个节点必须周期性地广播其与周围邻居节点的路由信息，其它节点在收到这些信息时更新网络拓扑，以最短路径算法来计算到达目的节点的下一跳节点。然而，某些节点保存的路由可能因为传播的延迟等原因与实际网络中的状态不一致，这时就可能会在网络中生成路由环路。距离矢量算法也会导致路由环路的生成。路由环路问题在无线环境下表现地更为明显，所以继承传统路由协议的表驱动路由协议需在此方面进行了改进。表驱动路由协议中无论路由是否被用到，每个节点都要进行周期性地路由信息交换以
25、维护路由表。表驱动路由协议的优点是在有信息传送时不需要等待建立路由，源节点一旦要发送报文，可以立即获得到达目的节点的路由。而其在无需通信节点之间的路由维护则浪费了大量的网络带宽。常见的表驱动路由协议有DSDV、HSR、GSR、WRP和FSR等。DSDV（Destination-Sequenced Distance-Vector Routing）协议通过修改RIP协议而得到，它基于Bellman-Ford算法。DSDV在每条路由信息中加人由目的节点产生的序列号，以避免路由环。在DSDV协议中，每个节点周期性地广播它当前的路由表（路由信息包括对应于每个目的节点的距离及最大序列号，还包含发送者自身的
26、序列号，每广播一次就自动加1）。每个收到该广播报文的节点将报文中的对应各目的节点的序列号与自身路由表中相应表项比较，如果报文中的序列号较高，则更新自己的路由表，将发送者指定为下一跳，并将距离增加一跳。在序列号相等但是报文中路由距离更小的情况下，节点也要更新自己的路由表。当一个节点发现链路失效时，它将所有通过该节点转发的路由的距离设为无穷并将其序列号加1。由于更新了序列号，因此这一消息会传播到整个网络。这样所有这些目的路由指向的目的节点都有效地与此节点断开，直到有新的序列号产生并包含新的路由信息。HSR（Hierarchical State Routing）是一种用于分级网络的路由协议，高级节点
27、保存它所有子孙节点的位置信息，沿从最高级的根节点到最低级的叶节点的路径为节点分配逻辑序列地址，可以用序列地址进行节点寻址。GSR（Global State Routing）协议的工作原理与DSDV协议类似，在该算法中，每个节点维护邻居列表、拓扑表、下一跳节点表和距离表。邻居列表记录所有能侦听到该节点信息的节点列表。对于每个目标节点，拓扑表记录链路状态信息和该信息的时间戳（timestamp），下一跳节点表记录分组转发的下一跳节点，而距离表则记录到达目的节点的最短路径。当链路的状态发生变化时，通过比较报文与本地拓扑表中的目的节点路由序列号大小，决定网络拓扑表的修改，若拓扑表发生变化则广播给其它节
28、点。GSR协议中，较长的路由修改报文会浪费相当大的网络带宽，针对这一缺陷，FSR（Fisheye State Routing）对GSR进行了修改，FSR的路由信息报文中并不包含所有节点的信息，因此可大大缩短报文的大小。与中心节点的距离越近，信息交换越频繁，每个节点都可获得其邻近节点准确详尽的信息；而随着与中心节点距离的加大，交换频率开始减小，超过节点的鱼眼范围时，信息的准确性降低，但并不影响路由的正确选择。通过这种算法，可大大降低路由修改信息对网络的负荷。这种算法的拓扑组织结构像鱼的眼睛,所以称之为FSR。WRP（Wireless Routing Protocol） 是一种距离向量路由算法,每
29、个节点维护距离表、路由表、链路开销表和信息重传列表。信息重传节点列表记录信息更新报文中需要传送的信息序列以及需要对该信息更新报文作出确认的节点列表。节点周期性或者在链路状态改变的情况下交换路由表，信息更新报文中反馈节点列表中的节点需要确认其接收。如果从上次广播更新报文后节点没有新的路由信息需广播，则其需发送HELLO报文，以确认节点之间的连通性。如果节点没有发送HELLO信息,则认为节点的链路信息无效。当节点收到来自邻居节点的信息更新报文后,修改自身的距离表依据该报文寻找更好的路由。如果某个移动节点收到了新节点的HELLO信息,则把新节点信息填入路由表,并且把它自己的路由表发给新节点。1.3.
30、2按需驱动路由协议与表驱动路由相反，源始发的按需驱动路由（又称反应路由）认为在动态变化的自组网环境中，没有必要维护去往其它所有节点的路由。按需驱动路由因其更适合自组网特性，近些年来更被关注。按需路由一般分为路由建立和路由维护两个过程。它仅在需要给目的节点发送报文而又没有去往目的节点路由的时候才按需进行路由发现。因此，路由表是按需建立的，它可能仅仅是整个拓扑结构信息的一部分。它的优点是不需要周期性的路由信息广播，节省了一定的网络资源。缺点是发送数据分组时，如果没有去往目的节点的路由，数据分组需要等待因路由发现引起的延时，不适合于实时性要求高的应用。常用的按需驱动路由协议有DSR、AODV、TORA和LAR等。本文将在第二章重点介绍DSR路由协议，下面简单介绍AODV、TORA和LAR等按需路由协议。AODV（Ad hoc On demand Distance
