一、Ad hoc网络的基本概念
随着社会的进步，人们对灵活、快捷、方便的通信方式要求越来越高;而全球化进程的加快又进一步刺激了通信与网络技术的发展，人们不断追求任何人可以在任何时间、任何地点与任何人进行任何种类的信息交换。个人业务需求无论是在支持范围上还是种类、质量要求上都大大的增加，极大地刺激了无线通信网络的迅速发展。蜂窝移动通信系统、无线局域网 (IEEE802.11)、蓝牙技术(Blue tooth)、家庭无线网(HomeRF)等移动通信新技术纷纷涌现，而Ad hoc网络技术作为无线通信领域一种新的网络技术，正在很快地从军事通信渗透到相关的各个民用通信领域。这些新技术的出现，极大的方便了人们的生活，同时也推动了无线通信技术的发展。无线通信技术和计算机网络技术的发展为无线移动 Ad hoc网络的产生奠定了基础，而这种自组织对等式多跳移动通信网络，不需要依赖于固定的基础结构，既可以与现有的网络结合形成多跳网络，从而有效延伸传统网络的覆盖范围，同时也可以通过临时组网的方式在恶劣环境中支持移动节点之间的数据、话音、图像和图形等业务的无线传输。这也使得Ad hoc网络具有极大的灵活性和可扩展性，可以满足不同场合的特殊需要，其应用范围可以覆盖工业、商业、医疗、家庭、办公环境、军事等各种场合和行业。特别是在军事应用领域中，因其特有的无需架设网络设施、可快速展开、抗毁性强等特点，Ad hoc网络已成为数字化战场通信的首选技术。Ad hoc网络不论是军用还是民用，都有着广泛的应用价值和意义。由于组网快速、灵活、使用方便，无线 Ad hoc网络己经得到了国际学术界和工业界的广泛关注，并正在得到越来越广泛的应用，己经成为移动通信技术向前发展的一个重要方向，并将在未来的通信技术领域中占据重要地位。
二、Ad hoc网络的特征
与其他传统通信网络相比，Ad hoc网络具有以下显著特点:
(1)无中心和自组织性:Ad hoc网络中没有绝对的控制中心，所有节点的地位平等，网络中的节点通过分布式算法来协调彼此的行为，无需人工干预和任何其它预置的网络设施，可以在任何时刻任何地方快速展开并自动组网。由于网络的分布式特征、节点的冗余性和不存在单点故障点，使得网络的健壮性和抗毁性很好。
(2)动态变化的网络拓扑:Ad hoc网络中，移动终端能够以任意速度和任意方式在网中移动，并可以随时关闭电台，加上无线发送装置的天线类型多种多样、发送功率的变化、无线信道间的互相干扰;地形和天气等综合因素的影响，移动终端间通过无线信道形成的网络拓扑随时可能发生变化，而且变化的方式和速度都难以预测。
(3)多跳路由:由于节点发射功率的限制，节点的覆盖范围有限。当它要与其覆盖范围之外的节点进行通信时，需要中间节点的转发，即要过多跳。此外，Ad hoc网络中的多跳路由是由普通节点协作完成的，而不是由专用的路由设备(如路由器)完成的。反过来，如果可以使用多跳路由，节点的发射功率可以很低，从而达到节省电能延长电池工作时间的目的。
(4)无线信道传输：
Ad hoc网络采用无线传输技术作为底层通信手段，由于无线信道本身的物理特性，它所能提供的网络带宽相对有线信道要低得多，并且无线信道的质量较差。考虑到竞争共享无线信道产生的冲突、信号衰减、噪音和信道之间干扰等多种因素，移动终端得到的实际带宽远远小于理论上的最大带宽，并且会随时间动态变化。传统的共享广播式信道是一跳共享的，而在Ad hoc网络中，广播信道是多跳共享的。一个节点的发送，只有其一跳相邻节点可以听到，而此范围之外的其他节点觉察不到。此外，地形或发射功率等因素影响使得Ad hoc网络中可能产生单向无线信道。
(5)移动终端的局限性:Ad hoc网络中，移动终端具有携带方便、轻便灵巧等好处。但是也存在固有缺陷，例如能源受限、内存较小、CPU性能较低等，从而给应用程序设计开发带来一定的难度，同时屏幕等外设较小，不利于开展功能较复杂的业务。
(6)安全性较差:Ad hoc网络是一种特殊的无线移动网络，由于采用无线信道、有限电源、分布式控制等技术，它更加容易受到被动窃听、主动入侵、拒绝服务、剥夺“睡眠”等网络攻击。信道加密、抗干扰、用户认证、密钥管理、访问控制和其它安全措施都需要特别考虑。如图1所示的表中列出了Ad hoc网络与现有无线网络的主要区别。
图1： Adhoc网络与现有无线网络的主要区别
三、Ad hoc网络路由技术研究热点
由于Ad hoc网络(又称为MANET网络，Mobile Ad hoc Network)具有广阔的应用前景，它吸引了越来越多网络研究人员的关注。国际上对Ad hoc网络的研究早己成为无线计算机网络研究的热点，因此Internet工程工作组 (IETF)也成立了MANET工作小组，大量研究人员通过这个组织协作研究MANET的路由协议等多方面内容。Ad hoc网络的研究成果主要在以下几个方面:
(1)现有Ad hoc网络的路由协议的研究与优化，包括对IETF的MANET工作组提出的MANET路由协议草案和RFC文档进行研究并具体实现，构建实验和应用网络。
(2)节能路由
在Ad hoc网络中，所有结点都依靠有限的电池能量操作。一旦电池耗尽，移动结点将随即失效，并可能导致网络分割甚至不可用。虽然随着工业技术的进步，电池寿命有所增加，但还远远满足不了需要。因此，在 Ad hoc网络中有效的节省能量非常重要，在协议栈的各个层次可以使用不同的方法来达到这个目的。目前网络层的节能路由协议主要可分为两类:一是最小化传送包/流的能量消耗率;二是最大化系统生存时间。
(3)多播路由
在典型的 Ad hoc环境中，网络结点按组工作以完成给定的任务，因此多播在 Ad hoc网络中扮演了重要的角色。Ad hoc网络固有的资源的限制和结点移动性使得多播路由协议的设计尤其具有挑战性。目前提出的多播路由协议有MAODV，ODMRP，CAMP等。
(4)基于地理位置信息的路由
Ad hoc网络中节点的移动性给设计路由算法带来了很大的困难，而现在的定位技术(如GPS)已经比较先进。将二者结合，在自组网中利用位置信息，可以使节点在寻找路由时避免简单的洪泛;利用相邻节点或目的节点的位置信息，可以提高路由寻找的效率。典型的利用地理位置信息的路由协议有LAR，GPSR，DREAM，GRID等。
(5)路由协议的安全性由于Ad hoc网络利用无线信道传输信息，使得自组网比固定网络更容易遭到入侵破坏。 Ad hoc网络中对路由协议的攻击通常分为两类:路由破坏攻击和资源消耗攻击。在路由破坏攻击中，攻击者通过发送伪造的路由包试图引起合法的数据包以紊乱的方式被转发，而不能到达它们的目的地，如创建路由循环、路由黑洞等。在资源消耗攻击中，攻击者向网络中插入包试图消耗宝贵的网络资源或结点资源。1999年1月发布的RFC25OI明确提出，自组网路由协议必须提供安全机制。
(6)多路径路由技术
大多数已提出的MANET路由协议没有考虑公平性，它们倾向于把重的负载分布到源一目的对的路径最短的主机上。结果，超重负载的主机会迅速耗尽能源，这将导致网络分离，应用会话失败。多路径路由在有效使用带宽、对付拥塞和突发流量、增加传输可靠性方面是有效的。多路径路由的目标是在源一目的对之间建立多条路径，要求更多的主机来承担路由任务，它作为的一个最短路径的替代而被提出用来分布流量，减轻拥塞。在多路径路由中，流量通过多条路径分流传输到目标。换句话说，多路径路由是用多条好的路径来代替单条最好的路径。多路径路由可分为两大类:一类是在同一时刻对于每个源一目的对只能在一个连接上发布流量，当这条路径中断时，可以用其他备用路径来发送数据，一般称之为备份多路径;另一类是同时使用两条或两条以上的路径来传输流量，一般称之为并行多路径。此外，还出现了一些安全多路径路由的研究。
(7)QoS路由
在 Ad hoc网络中，由于频繁的网络拓扑的改变和不准确的路由状态信息，使得选择满足QoS需求的路由是困难的但又是重要的。Qos路由的工作包括两个方面:一是选择一条能满足一定QoS需求(带宽、延迟、能量等)的网络路径，二是提高网络资源的利用率。广义的Qos要求针对不同的业务需求，尽量提供最优的服务。典型的Qos路由协议有CEDAR，QoS-OLSR，TBP等。
第二部分 Ad hoc网络基础
一、Ad hoc网络的发展历史与定义
无线Ad hoc网络的前身是分组无线网 (Paeket Radio Network)。早在1972年，美国DARPA(美国国防高级研究计划局，Defense Advanced Research Project Ageney)就启动了分组无线网项目 PRNET(Packet Radio Network)，研究在战场环境下利用分组无线网进行数据通信。在此之后，DARPA于1983年启动了高残存性自适应网络项目SURAN(Survivable Adaptive Network)，研究如何将PRNET的研究成果加以扩展，以支持更大规模的网络。成立于1991年5月的IEEE8O2.ll标准委员会采用了“Ad hoc网络”一词来描述这种特殊的自组织对等式多跳移动通信网络，Ad hoc网络就此诞生。IETF也将Adhoe网络称为MANET(移动Ad hoc网络)。
Ad hoc一词来源于拉丁语，意思是“专用的、特定的”意思，即 Ad hoc网络是一种有特殊用途的网络。无线 Ad hoc网络是由一组带有无线收发装置的移动终端组成的一个多跳临时性自治系统，移动终端具有路由功能，可以通过无线连接构成任意的网络拓扑，这种网络可以独立工作，也可以与Internet或蜂窝无线网络连接。在后一种情况中，无线 Ad hoc网络通常是以末端子网(树桩网络)的形式接入现有网络。无线 Ad hoc网络中，每个移动终端兼备路由器和主机两种功能:作为主机，终端需要运行面向用户的应用程序;作为路由器，终端需要运行相应的路由协议，根据路由策略和路由表参与分组转发和路由维护工作。在无线Ad hoc网络中，节点间的路由通常由多个网段(跳)组成，由于终端的无线传输范围有限，两个无法直接通信的终端节点往往要通过多个中间节点的转发来实现通信。所以，它又被称为多跳无线网、自组织网络、无固定设施的网络或对等网络。Ad hoc网络同时具备移动通信和计算机网络的特点，可以看作是一种特殊类型的移动计算机通信网络。
二、Ad hoc网络的体系结构
节点结构:
Ad hoc网络的节点不仅要具备普通移动终端的功能，还要具有报文转发能力，即要具备路由器的功能。因此，就完成的功能而言可以将节点分为主机、路由器和电台三部分。其中主机部分完成普通移动终端的功能，包括人机接口、数据处理等应用软件。而路由器部分主要负责维护网络的拓扑结构和路由信息，完成报文的转发功能。电台部分为信息传输提供无线信道支持。
图2：Adhoc网络节点的结构
从物理结构上分，节点可以如图2所示，分为以下几类:单主机单电台、单主机多电台、多主机单电台和多主机多电台。一般的Ad hoc网络中的节点，如PDA、笔记本、无线传感器节点等大都采用图2.a的单主机单电台的简单结构。作为复杂的车载台，一个节点可能包括通信车内的多个主机，它可以采用图2.c的结构，以实现多个主机共享一个或多个电台。多电台不仅可以用来构建叠加(overlay)的网络，还可用作网关节点来互联多个Ad hoc网络。
Ad hoc网络结构:
图3
Ad hoc网络一般有两种结构:平面结构(图3)和分级结构(图4和图5)。在平面结构中，所有节点的地位平等，所以又可以称为对等式结构。而分级结构中，网络被划分为簇(cluster)。每个簇由一个簇头(cluster header)和多个簇成员 (cluster member)组成。
图4
图5
平面结构 图4单频分级 图5多频分级
这些簇头形成了高一级的网络。在高一级网络中，又可以分簇，再次形成更高一级的网络，直至最高级。在分级结构中，簇头节点负责簇间数据的转发，它可以预先指定，也可以由节点使用算法选举产生。
根据不同的硬件配置，分级结构的网络又可以被分为单频分级和多分级两种单频率分级网络(图4)中，所有节点使用同一个频率通信。为了实现簇头之间的通信，要有网关节点(同时属于两个簇的节点)的支持。簇头和网关形成了高一级的网络，称为虚拟骨干。而在多频率分级网络中(图5)，不同级采用不同的通信频率。低级节点的通信范围较小，而高级节点要覆盖较大的范围。高级的节点同时处于多个级中，有多个频率，用不同的频率实现不同级的通信。在图3所示的两级网络中，簇头节点有两个频率。频率1用于簇头与簇成员的通信。而频率2用于簇头之间的通信。分级网络的每个节点都可以成为簇头，所以需要适当的簇头选举算法，算法要能根据网络拓扑的变化重新分簇。平面结构的网络比较简单，网络中所有节点是完全对等的，原则上不存在瓶颈，所以比较健壮。它的缺点是可扩充性差:每一个节点都需要知道到达其它所有节点的路由。维护这些动态变化的路由信息需要大量的控制消息。当平面结构网络的规模增加到某个程度时，所有的带宽都可能会被路由协议消耗掉。在分级结构的网络中，簇成员的功能比较简单，不需要维护复杂的路由信息，这大大减少了网络中路由控制信息的数量。因此具有很好的可扩充性，网络规模不受限制。可以简单地通过增加簇的个数和网络的级数来增加网络的规模。簇头节点要维护到达其它簇头的路由信息，它还要知道网络中所有节点与簇的所属关系。由于簇头节点可以随时选举产生，分级结构也具有很强的抗毁性。分级结构也有它的缺点。首先，维护分级结构需要节点执行簇头选举算法。其次，簇间的信息都要经过簇头寻路，不一定能使用最佳路由。比如在不同簇中但互为邻居的节点，在平面结构中可以直接通信，但分簇后要通过两个簇的簇头转交。最后，簇头节点可能会成为网络的瓶颈。总之，当网络的规模较小时，可以采用简单的平面式结构;而当网络的规模增大时，应采用分级结构。美军在其战术互联网中使用近期数字电台NTD(Near Term Digital Radio)组网时采用的就是如图5所示的双频分级结构。
三、Ad hoc网络的应用
Ad hoc网络的许多优良特性为它在民用和军事通信领域占据一席之地提供了有利的依据。首先，网络的自组织性提供了廉价而且快速部署网络的可能。其次，多跳和中间节点的转发特性可以在不降低网络覆盖范围的条件下减少每个终端的发射范围，从而降低设计天线和相关发射/接收部件的难度，也降低了设备的功耗，从而为移动终端的小型化、低功耗提供了可能。从共享无线信道的角度来看，Ad hoc网络降低了信号冲突的几率，提高了信道利用率。从对使用者的保护来看，高功率的无线电波产生的电磁辐射对用户的身体健康也有影响。另外，网络的鲁棒性、抗毁性满足了某些特定应用需求。它的应用场合可以归纳为以下几类:
(1)军事应用:军事应用是Ad hoc网络技术的主要应用领域。因其特有的无需架设网络设施、可快速展开、抗毁性强等特点，它是数字化战场通信的首选技术，并已经成为战术互联网的核心技术。为了满足信息战和数字化战场的需要，美军研制了大量的无线自组织网络设备，用于单兵、车载、指挥所等不同的场合，并大量装备部队。美军的近期数字电台NTDR和无线互联网控制器等通信装备都使用了Ad hoc网络技术。
(2)传感器网络:传感器网络是Ad hoc网络技术应用的另一大领域。对于很多应用场合来说传感器网络只能使用无线通信技术，并且传感器的发射功率很小。分散的传感器通过Ad hoc网络技术组成一个网络，可以实现传感器之间和与控制中心之间的通信。这种网络具有非常广阔的应用前景。
(3)紧急和突发场合:在发生了地震、水灾、火灾或遭受其它灾难后，固定的通信网络设施都可能无法正常工作。此时Ad hoc网络能够在这些恶劣和特殊的环境下提供通信支持，对抢险和救灾工作具有重要意义。此外当刑警或消防队员紧急执行任务时，可以通过Ad hoc网络来保障通信指挥的顺利进行。
(4)偏远野外地区:当处于边远或野外地区时，无法依赖固定或预设的网络设施进行通信。Ad hoc网络技术具有单独组网能力和自组织特点，是这些场合通信的最佳选择。
(5)临时场合:Ad hoc网络的快速、简单组网能力使得它可以用于临时场合的通信。比如会议、庆典、展览等场合，可以免去布线和部署网络设备的工作。
(6)动态场合和分布式系统:通过无线连接远端的设备、传感节点和激励器，Ad hoc网络可以方便地用于分布式控制，特别适合于调度和协调远端设备的工作，减少分布式控制系统的维护和重配置成本。Ad hoc无线网络还可以用于在自动高速公路系统(AHS)中协调和控制车辆，对工业处理过程进行远程控制等。
(7)个人通信:个人局域网(PAN)是 Ad hoc网络技术的又一应用领域，用于实现PDA、手机、掌上电脑等个人电子通信设备之间的通信，并可以构建虚拟教室和讨论组等崭新的移动对等应用(MPZP)。考虑到电磁波的辐射问题，个人局域网通信设备的无线发射功率应尽量小，这样 Ad hoc网络的多跳通信能力将再次展现它的独特优势。
(8)商业应用:组建家庭无线网络、无线数据网络、移动医疗监护系统和无线设备网络，开展移动和可携带计算以及无所不在的通信业务等。
(9)其它应用:考虑到 Ad hoc网络具有很多优良特性，它的应用领域还有很多，这需要我们进一步去挖掘。比如它可以用来扩展现有蜂窝移动通信系统的覆盖范围，实现地铁和隧道等场合的无线覆盖，实现汽车和飞机等交通工具之间的通信，用于辅助教学和构建未来的移动无线城域网和自组织广域网等。
第三部分 无线自组网路由技术
本部分主要介绍自组网路由所面临的问题、目前己经提出的各种主要的路由协议，并对各种主要路由协议的设计思路和解决策略进行比较、分析和分类阐述。
一、路由概述
路由技术主要是为数据分组以最佳路径通过通信子网到达目的节点提供服务，从而使得网络用户不必关心网络的拓扑构型和使用的通信介质。在传统的OSI参考模型中，网络层实现路由功能。OSI中的网络层定义操作系统通用的协议，为信息确定地址，把逻辑地址和名字翻译成物理地址，它也确定从源节点沿着网络到目标节点的路由选择，并处理业务流问题，例如交换、路由和对数据分组阻塞的控制。网络层也许是OSI参考模型中最复杂的一层，部分原因在于，现有的各种通信子网事实上并不遵循OSI网络层服务定义。同时，网络互联问题也为网络层的制定增加了很大难度。在实际应用中，一般使用路由器实现网络层的路由转发功能。路由器可以将子网连接在一起，它依赖于网络层将子网之间的流量进行路由。数据链路层协议是相邻两直接连接节点间的通信协议，它不能解决数据经过通信子网多个转接节点的通信问题。而路由是把信息从源穿过网络传递到目的的行为，在传输途中至少遇到一个中间节点。桥接发生在OSI参考协议的第二层(链路层)，而路由发生在第三层(网络层)。这一区别使二者在传递信息的过程中使用不同的信息，从而以不同的方式来完成其任务。
二、路由算法及协议
路由算法可以根据多个特性来加以区分。首先，算法设计者的特定目标影响了该路由协议的操作;其次，存在着多种路由算法，每种算法对网络和路由器资源的影响都不同，路由算法使用多种Metric(跳数)，影响到最佳路径的计算。
下面是对路由算法的上述特性的分析。
路由算法的设计目标
路由算法通常具有下列设计目标的一个或多个:
(a)无环路、快速收敛
路由算法必须能够保证不会产生路由环路，并且能快速收敛，收敛是所有路由器对最佳路径达成一致的过程。当某网络事件使路径断掉或不可用时，路由器通过网络分发路由更新信息，促使最佳路径的重新计算，最终使所有路由器达成一致。收敛很慢的路由算法可能会产生路由环或网络中断。
(b)健壮、稳定
路由算法必须健壮，即在出现不正常或不可预见事件的情况下仍能正常处理，例如硬件故障、高负载和不正确的实现方法。因为路由器位于网络的连节点，当它们失效时会产生重大的问题。最好的路由算法通常是那些经过了时间考验，证实在各种网络条件下都很稳定的算法。
(c)简单、高效、低耗
路由算法应该设计的尽量简单。即路由协议必须高效的提供其功能，尽量减少软件和应用的开销。当路由协议软件运行在物理资源有限的计算机上时，高效低耗尤其重要。
(d)灵活性
图6 几种常用固定网络动态路由协议的比较
路由算法还应该是灵活的，即它们应该迅速、准确地适应各种网络环境。例如，假定某网段断掉了，当知道问题后，很多路由算法对通常使用该网段的路径迅速选择次佳的路径。路由算法可以设计得可适应网络带宽、路由器队列大小和网络延迟。路由协议是实现路由算法的协议，几种常用固定网络动态路由协议的比较如图6中列表所示。
三、自组网路由
1.自组网路由协议面临的问题
路由协议是自组网体系结构中不可或缺的重要组成部分，其主要作用是发现和维护路由。具体的说主要有以下几个方面:监控网络拓扑结构的变化:交换路由信息;确定目的节点的位置;产生、维护以及取消路由;选择路由并转发数据。常规的路由协议主要有两种:一种是基于距离矢量的路由协议，如RIP。一种是基于链路状态的路由协议，如OSPF。这两类协议都是针对有线固定网络而设计的，它们的拓扑结构是固定的，不会出现大的网络结构变化。 Ad hoc网络中由于节点的任意移动性导致拓扑结构动态、随机且快速地变化，这样常规路由在拓扑结构变化时，就会花很大的代价重新路由，而且协议状态将始终处于不收敛状态，占用大量的网络资源，致使信息的传输无法实现。另外，Ad hoc网络不能采用常规路由协议主要由于以下因素:
(a)Ad hoc网络中无线传输设备功率的差异以及无线信道中的大量干扰导致单向信道的存在。
(b)无线信道的广播特性使得常规路由的网络选路过程产生许多冗余链路。
(c)常规路由的周期性广播路由更新分组会消耗大量的网络带宽。
(d)常规路由协议周期性的路由更新分组会消耗大量的节点能源。此外，某些常规路由协议需要的复杂计算使得CPU始终处于很高的负载之下，这也同样消耗了大量的能源，并将对有限的节点能源带来更多的压力。因此需要适用于Ad hoc。网络自身的路由协议。
2.自组网对路由协议的要求
自组网路由协议的任务是实现路由。但由于自组网具有动态拓扑、有限带宽、终端受限、存在单向信道等特点，对在其上运行的路由协议便提供出了许多具体而严格的要求。相对于有线网络，有些要求是自组网特有的，这些要求主要有:
(a)收敛迅速:自组网的拓扑结构是动态的，随时处于变化之中，这就要求路由协议必须对拓扑的变化具有快速反应能力，在计算路由时能够迅速收敛。
(b)提供无环路由:无论在有线网络还是无线网络，提供无环路由都是对路由协议的一项基本要求。但在自组网中，由于拓扑结构动态变化会导致大量已有路由信息在短时间内作废，从而更容易产生路由环路。在自组网中提供无环路由就显得尤为重要而且更难做到。
(c)避免计数到无穷:经典的距离矢量算法在某条链路失效时，有可能出现计数到无穷的情况。在自组网中，链路失效是经常发生的，这就要求在自组网中运行的路由协议必须能够避免计数到无穷，不采用或者改进会出现计数到无穷的算法。
(d)控制管理开销小:自组网中无线传输带宽有限，传送控制管理分组不可避免地会消耗掉一部分带宽资源。为了更有效地利用宝贵的带宽资源，需要尽可能地减小控制管理的开销。
(e)对终端性能无过高要求:无线移动终端使用可耗尽能源、CPU性能、内存大小、外部存储容量等都低于固定的有线终端，因此在自组网中不能对端性能要求过高。有线网络中用计算的复杂度来换取路由协议性能的做法，在自组网中不再适用。
(f)支持单向信道:在自组网中，有可能出现单向信道。支持单向信道，也是对路由协议的要求之一。
(g)尽量简单实用:简单有助于提高可靠性，有助于减少各种开销。在实现路由功能的前提下，力求简单，应是设计自组网路由协议的原则之一。但目前提出的路由协议都未达到以上所有要求，提出一种适应性强的路由协议是Adho。网络未来研究的一个具有挑战性的课题。
3.自组网路由协议的分类
传统的路由协议无法适应 Ad hoc网络的需要，因此必须选择或设计适用于 Ad hoc网络环境特点的路由协议。经过多年的研究，许多协议方案相继被提出。除了MANET WG(Work Group)发布的DSR，AODV，ZRP (Zone Routing Protocol)等路由协议草案外，研究人员还发表了许多关于自组网路由协议的学术论文，如DSDV(Destination-Sequenced-Distance-Vector Routing，目的节点序列距离矢量路由协议)、WRP(Wireless Routing protocol，无线路由协议)、CGSR(Cluster-head Gateway switch Routing，分簇网关交换路由)、轻型移动路由协议LMR和RDMAR(Relative Distance Miero-discovery Ad hoc Routing)等。根据发现路由的策略，可以将其分为主动路由和按需路由协议:根据网络逻辑结构，可以将其分为平面结构和分级结构两种;从网络逻辑角度出发，可分为平面路由和分级(层、簇、群)路由，如图7和图8列表所示。
图7
图8
图7 路由协议分类 图8 自组网中路由技术
另外，从是否使用GPS系统作为路由辅助条件的角度出发，还可分为地理定位辅助路由与非地理定位辅助路由。需要注意的是，分级路由中的分簇与网络管理控制中管理分簇不同。管理分簇引入簇首为中间节点，以减少管理消息开销，其目标与路由分簇不同，功能更弱。路由分簇中簇首负责跨簇分组的路由，其分簇基本目标为维护路由;网络管理控制协议为应用层协议，若低层路由协议也是基于分簇的，则可利用低层分簇，否则依赖于路由支持以交换控制消息。
1.主动路由协议和按需路由协议
主动路由协议采用周期性的路由分组广播，交换路由信息。每个节点维护去往全网所有节点的路由。主动路由的优点是当节点需要发送一个去往其他节点的数据分组时，只要路由存在，发送分组的延时很小。缺点是主动路由协议需要花费较高代价(带宽、电源及cPu资源等)，尽量使得路由表能够跟上当前网络拓扑结构的变化。但动态变化的拓扑结构可能使得花费较高代价得到的路由表中的内容变成无效信息，路由协议始终处于不收敛状态。目前，这种类型的自组网路由协议提出了各种机制改善在这些方面的性能。按需路由协议是根据发送数据分组的需要按需进行路由发现的过程，网络拓扑结构和路由表内容也是按需建立的，所以其内容可能仅仅是整个网络拓扑结构信息的一部分。按需路由的优点是不需要周期性的路由信息广播，节省了一定的网络资源。缺点是如果发送数据分组时，没有去往目的节点的路由，数据分组需要等待一定的时间和延时。并且由于相应路由发现过程通常采用了全网洪泛机制进行搜索，这在一定程度上抵消了按需机制带来的好处。
2.平面结构和分级结构
对于平面结构的路由协议，网络的逻辑视图是平面结构，网络结构简单，路由协议在平面的逻辑空间里运作，移动节点的地位是平等的，它们所具有的功能完全相同。共同协作完成节点间的通信。平面结构路由的优点是完全分布式控制，没有特殊节点，路由协议的可靠性较好，网络通信流量平均地分散在网络中，路由协议没有管理节点移动性的任务。其缺点是可扩展性不好，限制了网络的规模。随着网络规模的逐渐扩大，网络中节点个数不断增加，每个节点要维护整个网络的拓扑信息或选择合适的路由到远端节点将十分困难，由此产生了分级(层、簇、群)路由协议。对于分级结构的路由协议，网络节点按照不同的分簇算法分成相应的簇(级、层)，网络的逻辑视图是层次性的。层次划分的依据可以是信道编码、协同工作关系、地理位置等因素。分级结构通常有骨干网与分支子网组成的两层网络结构和多级分级结构。在两级网络结构中，骨干网由较为稳定、综合性能较好的骨干节点(簇首)组成，其他移动节点按照某种策略组成每个分支子网络。分支子网络又称为簇。在同一个簇的移动节点之间的通信只经过簇内部;在不同簇的移动节点之间的通信需要跨越骨干网，如通过网关节点实现。分级结构路由协议的优点是适合大规模的自组网环境，可扩展性较好。但是由于簇首节点负责管理和维护本簇节点的通信，当簇首节点出现故障时，可能会影响整个网络的通信，即簇首节点的稳定性和可靠性将在很大程度上决定着整个系统的稳定性和可靠性。同时随着节点的不断移动，簇的维护和管理比平面式路由协议复杂得多。根据簇的划分方法、簇首的选择方式以及簇首的职责不同，出现了一些不同的基于分簇结构的路由协议，如:R.Sivakumar提出的CEDAR，A.Iwata提出HSR，Joa-Ng提出的ZHLS等。
四、主动路由协议、按需路由协议
在此我们主要讲解学习主动路由协议、分级路由协议，具体包括DSDV(主动路由协议)，DSR和AODV(按需路由协议)。
1.主动路由协议
主动路由协议也被称为表驱动路由 (TableDriven)协议、先应式路由协议，其路由发现策略类似于传统的路由协议。在主动路由协议中，网络的每一个节点都要周期性的向其他节点发送最新的路由信息，并且每一个节点都要保存一个或更多的路由表来存储路由信息。当网络拓扑结
构发生变化时，节点就在全网内广播路由更新信息，这样每一个节点就能连续不断地获得网络信息。典型的主动路由协议有DSDV、FSR、WRP等。
DSDV(Destination Sequenced Distance Vector，目的节点序列距离矢量协议)是一个基于传统的Bellman-Ford路由选择机制的驱动算法，它被认为是最早的自组网路由协议，通过给每个路由设定序列号避免了路由环路的产生。
DSDV在传统的Distance一vector算法的基础上，采用了序列号机制，通过给每个路由设定序列号来区分新旧路由，防止Distance一vector算法可能产生的路由环路。DSDV采用时间驱动和事件驱动技术控制}路由表的传送，即每个移动节点在本地都保留一张路由表，其中包括所有有效目的节点、路由跳数、目的节点路由序列号等信息，目的节点路由序列号用于区别有效和过期的路由信息以避免环路的产生。路由表更新分组在全网内周期性地广播而使路由表保持连贯性。每个节点周期性地将本地路由表传送给邻近节点，或者当其路由表发生变化时，也会将其路由信息传给邻近节点。当无节点移动时，DSDV使用间隔较长、包含多个数据单元的大数据分组进行路由更新;在节点移动时使用较小的数据分组，并且只对移动的节点更新路由，这样降低了整体的开销。当邻近节点收到包含修改的路由表信息后，先比较源节点、目的节点路由序列号的大小，标有更大序列号的路由信息总是被接收，目的节点路由序列号小的路由被淘汰。如果两个更新分组有相同的序列号，则选择跳数(Metric)最小的，而使路由最优(最短)。为了消除最优路由的频繁变化，节点首先根据历史一记录，估计产生路由所需的保留时间(settle time)，推迟一个T再发送修改的路由信息。
DSDV的优点是原理及操作简单，缺点是不适应快速变化的网络，不支持单向信道。
2.按需路由协议
按需路由也被称为反应式路由协议、源启动按需路由协议〔Source-Initiated on-Demand Driven)。与主动路由协议不同的是，按需路由协议仅当源节点需要到目的节点的路由信息发送数据时，源节点才发起创建路由。因此，路由表内容是按需建立的，它可能仅仅是整个拓扑结构信息的一部分。通信过程中维护路由，通信完毕后便不再进行维护。
下面介绍几种主要的按需路由协议。
第一种 DSR协议：
DSR(动态源路由协议)协议是一个典型的按需路由协议，也是最早采用按需路由思想的协议。DSR是基于源路由概念的按需自适应路由协议。移动节点需保留存储节点所知的源路由的路由缓冲器。当新的路由被发现时，缓冲器内的条目随之更新。它的最大特点是使用了源路由机制，每一个分组的头部都包含整条路由信息。这种机制最初被 IEEE802.5协议用在由网桥互连的多个令牌环网中寻找路由。DSR借鉴该机制，并结合了按需路由的思想。采用Cache(缓冲器)存放路由信息，且中间节点不必存储转发分组所需的路由信息，网络开销较少，但存在陈旧路由。
①DSR协议操作
DSR的特点在于使用了源路由机制，在分组头部携带要经过的路由，路由器按照该路由序列来转发分组。DSR协议包括两个过程:路由发现和路由维护。
(1)路由发现
当一个节点欲发送数据到目的节点时，它首先查询路由器看是否有到达目的节点的路由发现程序。如果有，则采用此路由发送数据。如果没有，源节点就开始启动路由发路由发现过程使用洪泛路由。当节点S需要到节点D的路由时，节点S广播“路由请求”分组(RREQ)，每个请求分组通过序列号和节点S标识惟一确定。收到“路由请求”分组的节点，若满足:
- 该节点不是目的节点D；
- 请求分组头部的源路由序列中不包含该节点；
- 该节点没有接收过同样的路由请求分组；
- 节点的路由表中没有到目的节点D的路由信息；
节点将自己的地址附加到“路由请求”分组头部的路由序列中，并将分组转发给所有相邻的节点。若请求分组头部的源路由序列中不包含一该节点，而该节点接收过同样的路由请求分组，则节点将删除该请求分组，防止循环处理和出现路由环路。若该节点不是目的节点D，节点自己路由表中记录有到目的节点D的路由信息，节点将发送“路由应答”给节点S，应答中包含了从节点S到节点D的路由。节点S获取路由后，使用源路由进行数据通信。
(2)路由维护
DSR支持主动应答和被动应答两种链路状态监测方法，路由维护通过路由错误分组和确认分组来实现。一旦节点在发送数据时发现需要使用的邻节点断开，它发送“路由出错”分组给这些断开路由的节点，源节点收到分组后，将失效路由从路由表中删除。沿途转发“路由出错”的节点也从自己的路由表中删除包含该断开链路的所有路由。除路由错误分组外，确认分组可以用来验证路由连接的正确运行。路由维护过程中，源节点监测网络拓扑的变化。若有变化导致源路由中断，源节点就尝试用缓存中的路由信息;如果不成功，就重新启动路由发现过程。为减少路由开销，节点缓存学习到的或用过的路由信息，并通过随机收听的方式来获取路由信息。
DSR协议主要具有如下特点:
- 节点不需要周期性地发送路由广播分组，无需维持去往全网所有节点的路由信息，能自然而完全地消除路由环路，而且还能提供多条路由，可用于单向信道。节省了电池能源和网络带宽，尤其是当没有节点要发送数据时，网络中没有通信开销。支持节点睡眠。
- 支持中间节点的应答，能使源节点快速获得路由，但会引起过时路由问题。
- 每个分组都需要携带完整的路由信息，造成开销较大，降低了网络带宽的利用率，不适合网络直径大的自组网，网络可扩展性不强。为了进一步提高按需路由协议的效率，许多研究人员对DSR路由协议进行了改进:
(a)采用路由缓存技术，以加快路由发现过程，通过限制路由请求消息传播，来减少路由请求消息的洪泛，如R.Castaneda于1999年提出的Query Localization协议等。
(b)通过使用位置信息减少路由请求消息的洪泛，如:Young-Bae Ko于1998年提出的LAR协议等。
(c)当链路出错时，出错点的中间节点可以从自己的路由列表中选出另一个可选路由，完成到目的节点的数据传输。
第二种 AODV协议：
①AODV协议概述
AODV是由Nokia研究中心的 Charles E.Perkins和加利福尼亚大学Santa Barbara的 Elizabeth M.Belding-Roryer以及Cincinnati大学Samir R.Das等共同开发，已经被 IETF MANET工作组于2003年7月正式公布为自组网路由协议的RFc标准。AODV实质上就是DSR和DSDV的综合，它借用了DSR中路由发现和路由维护的基础程序，及DSDV的逐跳(Hop-by-HoP)路由、目的节点序列号和路由维护阶段的周期更新机制，以DSDV为基础，结合DSR中的按需路由思想并加以改进。AODV在每个中间节点隐式保存了路由请求和应答的结果，并利用扩展环搜索的办法来限制搜索发现过的目的节点的范围。AODV支持组播功能，支持Qos，而且AODV中可以使用IP地址，实现同Internet连接，但是不支持单向信道。和DSDV保存完整的路由表不同的是，AODV通过建立基于按需路由来减少路由广播的次数，这是AODV对DSDV的重要改进。和DSR相比，AODV的好处在于源路由并不需要包括在每一个数据分组中，这样会使路由协议的开销有所降低。AODV是一个纯粹的按需路由系统，那些不在路径内的节点不保存路由信息，也不参与路由表的交换。AODv协议可以实现在移动终端间动态的、自发的路由，使移动终端很快获得通向所需目的的路由，同时又不用维护当前没有使用的路由信息，并且还能很快对断链的拓扑变化做出反应。AODV的操作是无环路的，在避免了通常Bellman-ford算法的无穷计数问题的同时，还提供了很快的收敛速度。AODv的路由表中每个项都使用了目的序列号(Destination Sequence Number)。目的序列号是目的节点创建，并在发给发起节点的路由信息中使用的。使用目的序列号可以避免环路的发生。
AODV使用3种消息作为控制信息 :RouteRequest(RREQ)，RouteReply(RREP)和 RouteError(RERR)。这些消息都在UDP上使用654端口号。
当源节点需要和目的节点通信时，如果在路由表中已经存在了对应的路由时，AODV不会进行任何操作。当源节点需要和新的目的通信时，它就会发起路由发现过程，通过广播RREQ信息来查找相应路由。当这个RREQ到达目的节点本身，或者是一个拥有足够新的到目的节点路由的中间节点时，路由就可以确定了。所谓“足够新”就是通过目的序列号来判断的。目的节点或中间节点通过原路返回一个RREP信息来向源节点确定路由的可用性。在维护路由表的过程中，当路由不再被使用时，节点就会从路由表中删除相应的项。同时，节点会监视一个活动路由(activeroute，有限跳的，可用于数据转发的路由表)中，下一跳节点的状况。当发现有链路断开的情况时，节点就会使用RERR通知上游的节点，而上游的节点就会使用该RERR分组拷贝通知更上游的节点。在RERR消息中，指明了由于断链而导致无法达到目的节点。每个节点都保留了一个“前驱列表”(precursor list)来帮助完成错误报告的功能，这个列表中保存了把自己作为到当前不可达节点的下一跳的相邻节点(可以通过记录RERR很容易地获得)。在路由表中，针对每一个表项，需要记录相应的的特征内容。其中，序列号是防止路由环路的关键所在。当发生断链时，通过增加序列号和度量值(跳数)来使路由表项无效。
②AODV路由协议的运行方式
(a)AODV路由发现
AODV路由协议是一种典型的按需驱动路由协议，该算法可被称为纯粹的需求路由获取系统，那些不在活跃路径上的节点不会维持任何相关路由信息，也不会参与任何周期路由表的交换。此外，节点没有必要去发现和维持到另一节点的路由，除非这两个节点需要进行通信。移动节点间的局部连接性可以通过几种方法得到，其中包括使用局部广播Hello消息。这种算法的主要目的是:在需要时广播路由发现分组一般的拓扑维护;区别局部连接管理(邻居检测)和一般的拓扑维护;向需要连接信息的邻居移动节点散播拓扑变化信息。AODV使用广播路由发现机制，它依赖中间节点动态建立路由表来进行分组的传送。为了维持节点间的最新路由信息，AODV借鉴了DSDV中的序列号的思想，利用这种机制就能有效地防止路由环的形成。当源节点想与另外一个节点通信，而它的路由表中又没有相应的路由信息时，它就会发起路由发现过程。每一个节点维持两个独立的计数器:节点序列号计数器和广播标识。源节点通过向自己的邻居广播 RREQ(Route Requests)分组来发起一次路由发现过程。
(b)反向路由的建立
在RREQ分组中包含了两个序列号:源节点序列号和源节点所知道的最新的目的序列号。源节点序列号用于维持到源的反向路由的特性，目的序列号表明了到目的地的最新路由。当RREQ分组从一个源节点转发到不同的目的地时，沿途所经过的节点都要自动建立到源节点的反向路由。节点通过记录收到的第一个RREQ分组的邻居地址来建立反向路由，这些反向路由将会维持一定时间，一该段时间足够RREQ分组在网内转发以及产生的RREP分组返回源节点。当RREQ分组到达了目的节点，目的节点就会产生RREP分组，并利用建立的反向路由来转发RREP。
(c)正向路由的建立
RREQ分组最终将到达一个节点，该节点可能就是目的节点，或者这个节点有到达目的节点的路由。如果这个中间节点有到达目的的路由项，它就会比较路由项里的目的序列号和RREQ分组里的目的序列号的大小来判断自己已有的路由是否是比较新的。如果RREQ分组里的目的序列号比路由项中的序列号大，则这个中间节点不能使用己有的路由来响应这个RREQ分组，只能是继续广播这个RREQ分组。中间节点只有在路由项中的目的序列号不小于RREQ中的目的序列号时，才能直接对收到的RREQ分组做出响应。如果节点有到目的地的最新路由，而且这个RREQ还没有被处理过，这个节点将会沿着建立的反向路由返回RREP分组。
在RREP转发回源节点的过程中，沿着这条路径上的每一个.节点都将建立到目的节点的同向路由，也就是记录下RREP是从哪一个邻居节点来的地址，然后更新有关源和目的路由的定时器信息以及记录下RREP中目的节点的最新序列号。对于那些建立了反向路由，但RREP分组并没有经过的节点，它们中建立的反向路由将会在一定时间(Active-Route-Timeout)后自动变为无效。收到RREP分组的节点将会对到某一个源节点的第一个RREP分组进行转发，对于其后收到的到同一个源的RREP分组，只有当后到的RREP分组中包含了更高的目的序列号或虽然有相同的目的序列号但所经过的跳数较少时，节点才一会重新更新路由信息，以及把这个RREP分组转发出去。这种方法有效地抑制了向源节点转发的RREP分组数，而且确保了最新及最快的路由信息。源节点将在收到第一个RREP分组后，就开始向目的节点发送数据分组。如果以后源节点了解到的更新的路由，它就会更新自己的路由信息。
③AODV路由表的管理
节点的路由中除了存储源和目的节点的序列号外，还存储了其他有用的信息，这些信息成为有关路由项的软状态。与反向路由相关的是路由请求定时器，这些定时器的目的是清除一定时间内没有使用的反向路由项。定时器的设置依赖于自组网的规模大小，与路由表相联系的另外一个重要的参数是路由缓存时间，即在超过这个时间之后，对应的路由表就变为无效。
此外，在每一个路由表中，还要记录本节点用于转发分组的活跃邻居。如果节点在最近一次活跃期间(Active-Timeout)发起或转发了到某个目的节点的分组，那么就可以称这个节点为活跃节点。这样，当到达某一个目的节点的链路有问题时，所有与这条链路有关的活跃节点都可以被通知到。一个路由表还有活跃邻居在使用，就可以认为是有效的。通过各个活跃路由项所建立的源节点到目的节点的路径，也就是一条活跃路径。路由表中的目的节点序列号，正如在DSDV路由协议中所使用的那样，可以在无序分组的传送和节点高度移动的极端条件下避免路由环路的产生。
移动节点为每一个相关的目的节点维护了一个路由表。每一个路由表包含以下一些信息:目的地址、下一跳地址、跳数、目的序列号及路由项的生存时间。路由表在每一次被用来传送一个分组时，它的生存时间都要重新开始计算，也就是用当前时间加上Aetive-Route-Timeout。如果一个移动节点被提供了到达某一个目的节点的新路由，那么它就会把这个新路由的目的序列号与自己路由表中己有的目的序列号做比较，并将目的序列号大的作为到达目的节点的路由表。如果目的序列号相同，则采用到目的节点所经过的节点数(跳数)最少的那个路由。
④AODV路由维护
如果节点的移动不是沿着活跃路径进行的，那么就不会影响己经建立的路由。如果一个源节点在活跃路径上移动，它就要向目的节点重新发起一次路由发现过程。如果移动的节点是中间节点或目的节点，那么一个特殊的RREP分组将转发到那些受移动影响的源节点。周期性发送的Hello分组可以用来确保链路的对称性，并检测不能用的链路。如果不用Hello分组，也可以采用链路层通告机制来报告链路的无效性，这样可以减少延迟。此外，节点在尝试向下一跳节点转发分组失败后，也能检测出链路的不可用性。
一旦一个节点的下一跳节点变得不可达，这时它就要向利用该损坏链路的活跃上游节点发送未被请求的RREP分组，这个RREP分组带有一个新的序列号(即在的序列号上加1)，并将跳数值设置为二。收到这个RREP分组的节点再依次将RREP分组转发到它们各自的活跃邻居，这个过程持续到所有的与损坏链路有关的活跃节点都被通知到为止。源节点在收到断链的通知后，如果它还要与目的节点联系，它就需要再次发起新的路由发现过程。这时，它将会广播一个RREQ分组，这个RREQ分组中的目的序列号要在源节点已知的最新目的序列号之上加1，以确保那些还不知道目的节点最新位置的中间节点对这个RREQ分组做出响应，从而能保证建立一条新的、有效的路由。
⑤AODV协议评价
总之，AODV是一种距离矢量路由协议，采用的算法克服了以前提出的一些算法(如DSDV)的缺点，具有如下优点:
(a)基于传统的距离向量路由机制，思路简单、易懂。
(b)支持中间节点应答，能使源节点快速获得路由，有效减少了广播数，但存在过时路由问题。
(c)节点只存储需要的路由，减少了内存的需求和不必要的复制。
(d)快速响应活跃路径上断链。
(e)通过使用目的序列号来避免路由环路，解决了传统的基于距离向量路由协议存在的无限计数问题。
(f)具有网络的可扩充性。
(g)需要周期性地广播分组，需要消耗一定的电池能源和网络带宽。与DSDV以及其他持续存储更新路由信息的算法相比，AODV需要相对较长的路由建立时延，不过AODV采取了以下的一些措施来加以改善:
(a)到某个目的节点的路由可以由知道路由的中间节点进行响应。
(b)链路失效能够被立即报告，这样路由可重新建立。
(c)不活跃的路由在一定时间后会被删除。
五、路由协议的定性分析
在理解前述三种路由协议(DSDV，DSR，AODV)的基础上，可以对各个协议做定性比较。参看图9列表。由于移动自组网的拓扑变化，因此在定性指标方面实现无环路由和分布式运行是路由协议的基本要求，在满足了基本要求和特性的基础上，提供节能策略、安全性、组播功能和Qos支持是协议评价的重要方面。读者在今后的深入学习中，可以不断的开拓视野，尝试在三种简单路由协议(DSDV，DSR，AODV)的基础上学习研究更加完善的实现方案。
图9 移动自组网路由协议比较
最后，笔者再向读者提一建议，如果在阅读本文学习Ad hoc网络时觉得内容太过抽象，难以形成直观学习对象的化，不妨自己亲自动手，来进行协议仿真实验。这需要我们进一步查阅具体的文献资料，并要熟悉掌握我们以前讲解过的Opnet等仿真工具的使用。这样，在实践的基础上，你将在网络技术的学习上真真正正迈上一大步。由于篇幅有限，本文对仿真过程将不做详述，如果有可能，在今后的后续文章中，将针对Ad hoc网络仿真做一专题讲解。