1. 传统Internet网络路由协议

目前在Internet中常用的内部网关路由协议主要由两种。一种是基于距离矢量的路由协议（如RIP协议），一种是基于链路状态的路由协议（如OSPF协议）。

1.1 距离矢量路由协议（Distance Vector）

在该协议中，每个路由器都维护一张距离向量表，表中记录着本路由器到每个目的节点的最佳路由（通常是最短路由）。通过与相邻路由器交换距离信息来更新路由表的信息。该路由协议算法采用的是“Bellman-Ford”最短路由算法。

1.2 链路状态路由协议（Link State）

与距离矢量路由协议不同的是，在该协议中，所有路由器不必以分布方式计算“最短路由”，而是通过可靠地发布链路状态分组来维护一张完整的网络拓扑结构图，并按照该拓扑结构计算出至目的节点的最短路由。该协议采用的是Dijkstra最短路径优先算法。

1.3 在Ad hoc网络中的不适用性

上述两类路由协议都是针对固定网络而设计的，都需要周期性地交换信息来维护网络正确的路由表或网络拓扑结构图。由于Ad hoc网络带宽有限，拓扑变换频繁，传统的用于固定网络的路由协议不适用于Ad hoc网络，主要体现在以下几个方面：

1.3.1 动态变化的网络拓扑结构

这些变化主要体现在节点加入、离开网络以及链路权值系数的变化。而对于常规的有限网络，网络拓扑结构则表现较为稳定，拓扑结构的变化通常是由于链路状态的变化（如链路拥塞，或是设备故障等）所引起的。

1.3.2 周期性的广播拓扑信息

周期性的广播拓扑信息会占用大量的无线信道资源，耗费电池能源，会严重降低系统的性能。尤其是在拓扑变化频繁的Ad hoc网络环境中，可能当路由算法还未收敛时，网络的拓扑结构就又发生了变化。

1.3.3 单向的无线传输信道

在传统的网络路由协议中，通常认为节点间的链路是对称的双向链路。而在Ad hoc网络中，由于无线收发设备不同或周围环境对无线信道的影响，可能会造成单向的无线传输信道。如图1所示，假设节点B的传输范围较大，可以和节点A和C直接通信，而节点A由于传输范围的限制不能将报文直接发送到节点C。节点A在收到节点B的拓扑信息（节点B可到达节点C）时，就不能简单地认为它可以通过节点B的转发实现与节点C的通信。

图1 单向的无线传输信道

正是由于以上的一些问题，如果直接将传统路由协议应用于Ad hoc网络，这些周期性的控制信息会占用大量的无线信道资源，降低系统效率。其中在RIP中还会遇到无穷计数和临时环路等问题，算法收敛速度慢，使得传统的路由协议在Ad hoc网络中不再适用。因此路由选择和路由协议成为当前Ad hoc网络研究的一个重点问题。

2. Ad hoc网络路由协议

根据是否使用地理位置进行辅助，Ad hoc网络路由协议可分为地理定位辅助路由(geographic-location assisted routing protocol)和非地理定位辅助路由(non-geographic-location assisted routing protocol)。根据网络拓扑结构，可以分为平面结构的路由协议(flat routing protocol)和层次结构/分簇的路由协议(hierarchical/cluster routing protocol)。根据源节点发现路由的驱动模式不同，又可以分为表驱动路由协议(table driven routing protocol)和按需路由协议(source-initiated on-demand routing protocl)，分类方法如图2所示。

图2 Ad hoc网络路由协议的分类

2.1 地理定位辅助路由协议

广播在移动Ad hoc网络通信中起着极其重要的作用。通过广播把信息从一个节点向整个网络中的所有节点发送。因而不但可以向全网发送简单的控制命令，而且在许多的网络层的单播和多播协议寻找路由的过程中起关键作用。比如DSR，AODV，ZRP，LAR等都是用广播来发现节点间的路径或更新网络节点的状态。当前，这些协议依赖于广播的一种简单形式——洪泛。但洪泛会引起网络的拥塞和数据冲突，从而降低网络资源利用率。

近年来，提出了许多广播协议，希望在保证网络中的每个节点得到广播报文的同时尽量减少数据重传的数量。广播协议分为以下几类：基于概率的协议、基于计数的协议、基于距离的协议、基于位置的协议以及基于分簇的协议。尽管前三类协议提供了较高的递交率和较低的重传率，但不是可靠的。分簇技术被用来解决无线网络的许多问题。但它要求额外的数据收发以进行簇首的选举及簇结构的维护。另外，由于基本所有的通信都要通过簇首进行，簇首的能量会迅速消耗，从而减少网络的生存时间。

另一种解决方案就是基于位置辅助的局部洪泛路由协议。随着全球定位系统的广泛应用，GPS技术与Ad hoc网络路由技术的结合使得这种Ad hoc网络的路由技术更加灵活。依靠GPS技术，发送源节点可以很容易知道目的节点的位置，另用己知的网络的位置信息，划定洪泛的范围，使得洪泛在局部范围内进行，从而降低了广播报文的开销。基于此，许多研究者提出了利用地理位置信息的路由协议。这种类型的路由协议具有更好的可扩展性和对网络更好的适应性。

根据节点在发送数据前是否建立路由，可以将利用位置信息的路由协议分为两类：(1)位置辅助的路由协议。特点是，节点在发送数据前先寻找路由，并保存路由表。典型代表是LAR(Location-aided routing)。(2)基于位置信息的路由协议。特点是，节点在发送数据前不寻找路由，不保存路由表，节点直接根据位置信息指定数据转发策略。基于位置信息的路由协议一般可分为三类：贪婪路由(如GPSR、GEDIR和GRA)、定向洪泛路由(如DREAM)和分层路由(如Terminodes Routing和GRID)。

2.2 平面路由协议和分簇路由协议

目前Ad hoc网络的拓扑结构主要由平面结构和分簇结构，如图3所示。

图3 Ad hoc网络拓扑结构

在平面结构的路由协议中，网络结构简单，所有节点处在平等的地位，它们具有的功能完全相同，各节点共同协作完成节点间的通信。

随着网络规模的的逐步扩大，网络中节点个数不断增加，每个节点想要维护整个网络的拓扑信息或选择到远端节点的合适路由将十分困难，因此产生了分簇式路由协议。

在分簇式路由协议中，网络节点按照不同的分簇算法分成相应的簇（或群）。簇中的每个节点完成的功能是不相同的，有的节点被赋予一些特别的功能，如簇首节点维护和管理本簇范围内节点，负责簇内节点的通信，同时为簇间节点通信提供合适的路由信息；网关节点负责与相邻簇节点通信。由底层簇的簇首节点可以进一步组成高一层的簇，如图4所示。

图4 分簇式路由协议中的分层结构图

根据簇的划分方法、簇首的选择方式以及簇首职责的不同，出现了一些不同的基于分簇结构的路由协议，如CEDAR、HSR及ZHLS等。

2.3 表驱动路由协议和按需路由协议

表驱动路由协议又称为主动式（或先验式）的路由协议（proactive protocols）。该路由协议试图维护网络中从各个节点到所有其余节点的最新路由信息。所有路由信息保持一致。每个节点都维护一张或几张到网络中其他节点的路由信息表。当网络拓扑结构发生变化时，节点通过交互信息来实时地维护网络路由信息表。目前常见有DSDV协议等，这类路由协议通常是通过修改常规的Internet路由协议以适应Ad hoc网络环境，如DSDV协议是在RIP协议的基础上，通过引入序列号机制解决了“路由环路”和“计数到无穷”的问题；通过采用“时间驱动”和“事件驱动”机制更新路由信息。尽量减少路由等控制信息对无线信道的占用，以提高系统效率。

在表驱动路由协议中，由于每个节点需要实时地维护路由信息，这样在网络规模较大、拓扑变化较快的环境中，大量的拓扑更新消息会占用过多的信道资源，使得系统效率下降。

为此，按需路由协议被提出。按需路由协议又称为反应式路由协议（reactive protocol）。它是一种被动式的路由协议，与主动式路由协议相比，在这类协议中，节点平时并不实时地维护网络路由，只有在节点有数据要发送时，才激活路由发现机制寻找到达目的节点的路由，常见的有DSR路由协议和AODV路由协议。路由发现过程如图5所示。当节点1有数据要向节点8发送且无路由时，节点1启动路由发现过程：