目前的无线自组网络路由协议，依据路由生成的时间来划分,可分为先验式/表驱动路由协议、反应式/按需驱动路由协议和混合式路由协议[1]，如图1所示。先验式路由协议也称表驱动路由协议，在这种路由协议中，无论是否有通信要求，每个节点均采用周期性的路由分组广播，交换路由协议，维护一张包含到达其他节点的路由信息的路由表。当检测到网络拓扑结构发生变化时，节点在网络中发送更新消息，收到更新消息的节点将更新自己上的路由表，以维护准确的路由信息[3]。源节点一旦要送分组，可以立即获得指向目的节点的路由。反应式路由协议又称按需驱动路由协议，是一种当需要时才查找路由的路由选择方式。节点不需要及时维护准确的路由信息，只有当需要发送数据时才发起路由查找过程。与先验式路由协议相比，反应式路由协议的开销小，但是数据报传送的时延较大，不适合于实时性的应用[3]。有关路由算法有DSDV、CGSR、OLSR、AODV、DSR、TORA等,以下将分别一一介绍。63780

图1.1 无线自组网络路由协议分类

1.1.1  目的序列距离矢量路由协议DSDV

DSDV(Destination-Sequenced Distance-Vector)是基于经典Bellman-Ford路由选择过程的改进型路由表算法[3]。DSDV以路由信息协议为基础。是无线自组网协议发展较早的一种。

使用DSDV时，网络中的每一个移动节点都需要维护一个路由表。路由表表项包括目的节点、跳数和一个由目的节点注明的序列号，序列号能帮助节点区分有效和过期的路由信息，并可防止路由环路的发生。标有更大序列号的路由信息总是被接收。如果两个更新分组有相同的序列号，则选择跳数最小的，使路由最优（最短）。每个节点必须周期性地与邻节点交换路由信息，当然也可以根据路由表的改变来触发路由更新。路由表更新有两种方式：一种是全部更新，即拔掉更新消息中将包括整个路由表，主要应用于变化较快的情况；另一种是增量更新，更新消息中仅包含变化的路由部分，通常适用于变化较慢的情况[4]。

1.1.2  群首网关交换路由协议CGSR

CGSR(cluster head gateway switch routing)协议是在DSDV协议基础上结合集群路由机制设计的[3]。CGSR采用LCC(least cluster change)算法形成集群结构。为了尽量避免群首节点频繁更替，保障群首节点身份的稳定性，LCC规定:只在两个群首节点相互靠近，或者一个节点离开所有群首节点的通信范围的这两种情况下才会发生群首节点身份的变化。除了群首节点外，CGSR还规定了其他两种类型的节点。一个群首的内部节点是指位于该群首的无线通信范围内的节点。网关节点则是指同时位于多个群首的无线通信范围之内的节点。论文网

当节点移动导致集群结构被破坏的时候，CGSR通过集群维护算法重新构造集群结构。在这个过程中，一些节点会从当前集群转移到邻居集群。为了尽量减少转移节点的个数，它将具有最多邻居节点和它的邻居保留在当前集群中[11,13]。

1.1.3  动态源路由协议DSR

DSR（Dynamic Source Routing)[3]是一种基于源路由的按需路由协议，它使用源路由算法而不是逐跳路由的方法。DSR主要包括两个过程：路由发现和路由维护。当源节点S向目的节点D发送数据时，它首先检查缓存是否存在未过期的到目的节点的路由，如果存在，则直接使用可用的路由，否则启动路由发现过程。具体过程如下：源节点S将使用洪泛法发送路由请求消息（RREQ），RREQ包含源和目的节点地址以及唯一的标志号，中间节点转发RREQ，并附上自己的节点标识。当RREQ消息到达目的节点D或任何一个到目的节点路由的中间节点时，D或该中间节点将向S发送路由应答消息（RREP），该消息中将包含到S到D的路由信息，并反转S到D的路由供RREP消息使用。此外，中间节点也可以使用路由缓存技术（Routing Cache）来对协议作进一步优化[9]。