ad hoc路由算法综述

表驱动

Destination-Sequenced Distance-Vector Routing（DSDV） 目的序列距离矢量路由

在DSDV中，每个移动节点都需要维护一个路由表。路由表表项包括目的节点、跳数和目的节点序号，其中目的节点序号由目的节点分配，主要用于判别路由是否过时，并可防止路由环路的产生。每个节点周期性与邻节点交换路由信息，当然也可以根据路由表的改变来触发路由更新。路由表更新有两种方式：一种是全部更新（Fulldump），即拓扑更新消息中将包括整个路由表，主要应用于网络变化较快的情况；另一种方式是部分更新（Incrementalupdate），更新消息中仅包含变化的路由部分，通常适用于网络变化较慢的情况。在DSDV中只使用序列号最高的路由，如果两个路由具有相同的序列号，那么将选择最优的路由（如跳数最短）。其缺点就是在源和目的节点之间只提供一条路由且不支持单向连接。

Clusterhead Gateway Switch Routing（CGSR） 簇头网关交换路由

这是一个分层路由协议，簇头控制一个节点群，如信道接入，路由，带宽分配。簇内会执行簇头选择算法，簇头选择算法过多执行会导致性能下降，因此使用最小簇头改变算法（LCC）：只当两个簇头相接或者有节点脱离所有簇头时执行。CGSR使用DSDV作为底层协议与邻居节点定期交换群成员表信息和LCC的集群计划，以形成集群和选举簇头。每个节点维护两个表：集群成员表（记录每个目的节点以及节点的簇头）和距离矢量路由表（记录簇头的下一跳）。集群成员表周期更新，节点将更新其相邻的一个新的集群成员表中的信息。为了传送 一个数据包,当前节点首先在群成员表中查找目标节点所在群的簇头节点,然后在路由表中查找去往目标簇头的下一跳节点，数据包在簇头和网关之间交替传递，一个包先送到簇头，再由簇头发给网关节点，由网关节点发给另一个簇头，依次直至到达目的节点。协议使用一个序列号，以获得无环路的路线，避免陈旧的路由条目。此协议的优点就是大大减小了一般 DSDV协议路由表的大小,因为它为所有处 于同一个群的节点只提供一个路由条目。但它在移动环境下维持簇比较困难。

The Wireless Routing Protocol（WRP） 无线路由协议

每个节点维持四个表：距离表，路由表，链路代价表，重发信息单（MRL）表。每个MRC包含更新消息序列号，重发计数器，邻节点确认消息标志向量，更新消息中的需要发送的数据。MRC记录每个需要重发的更新数据和需要确认重发的邻节点。节点通过更新消息通知每个链路变化，且只在相邻节点间发送。更新消息包含目的节点，距离，目的节点的前跳信息。以及标志哪个节点需要确认。节点在处理来自邻节点的更新消息或者检测到邻节

点的链路变化时发送更新消息。当检测到两个节点的链路断掉时，相邻节点修改距离表并查看是否有通过其他节点的新链路。新链路的信息会中继回源节点以便其更新路由表。节点通过回复确认信息和其他消息得知邻节点的存在。节点若没有信息发送，则需定期发送hello信息确认连接，否则意味着链路断开。WRP中，要求路由节点交换每个目标节点的距离及倒数第二跳信息，可以保证网络无环。WRP属于path-finding算法，它强制每个节点对所有邻居节点关于倒数第二跳信息进行一致性检查,避免了“count-to-infinity”问题。它解决了环路问题并且连接失败时可以加快收敛速度。缺点就是不能及时解决环路问题

比较

DSDV对任意给定目的节点只提供一条最短路由，由于其无论网络拓扑是否发生变化都要周期更新，因此效率会降低。

在CGSR中，DSDV作为基础协议旨在簇头和网关节点执行。除路由表外还需簇头表。其优点是可以使用协议启发式算法，如优先调度，网关编码，路径反转。

WRP需要保持四个表，需要大量的存储设备，尤其是网路规模大时，而且无论是否有信息发送，WRP需要发送hello消息，耗费带宽并且不允许节点休眠。但是由于其属于path finding算法，他可以通过确认前趋节点信息的方式避免产生暂时的路由环路。

当链路失败时，WRP比DSDV有较小的时间复杂度，由于它只需要通知相邻节点拓扑的变化。当增加节点时，hello也可以用作出现标志使信息更新，并且只影响相邻节点。CGSR算法的复杂度取决于具体的节点，簇头节点失败由于要执行簇头选择协议，因此比DSDV复杂。

按需路由

Ad Hoc On-Demand Distance Vector Routing（AODV） Ad Hoc按需距离矢量路由

AODV建立在DSDV的基础上。但它与DSDV的区别在于它是反应式路由协议。 路径发现：当源节点需要发送信息，且没有有效的路由信息，则启动路径发现过程，其广播一个路由请求（RREQ），邻节点不断广播，直至到达目的节点或者中间节点有足够新的目的节点路由信息。AODV通过目的节点序列号来保证网络无环和路由信息最新。每个节点维持一个序列号和广播ID。广播ID随着RREQ而增加，它和节点IP地址来唯一标识一个RREQ。源节点将包含最新序列号的RREQ发给目的节点，中间节点有到达目的节点的比RREQ中更大的序列号时可以应答源节点。在前向传播RREQ的过程中，中间节点将RREQ来源节点的地址加入自己的路由表，然后建立反向路由，并将后边到达的同一RREQ丢弃。当RREQ到达目的节点或者有有效路由信息的中间节点时，会通过点播的方式反向应答（RREP）源节点。RREP反向经过个节点，各节点建立前向路由并激活。每个路由实体伴随着一个路由计时器，负责当该实体超过生存时间时将其删除。由于RREP沿着RREQ建立的路径传播，因此AODV只支持对称链路。

路径维持：当源节点移动时，它可以重新启动路由发现过程。当路由上的节点移动时，其上游邻居节点将意识到并且向上游节点发送一个链路失败通知消息通知他们这段消失的路由，直至到达源节点。若源节点仍有需要，可重新启动路由发现程序。

另外，AODV周期向邻节点广播hello消息来保持本地连接性。

Dynamic Source Routing（DSR） 动态源路由

路由发现： DSR是一种基于源路由的按需路由协议而不是逐跳路由的方法。DSR主要包括两个过程：路由发现和路由维护。当节点S向节点D发送数据时，它首先检查缓存是否存在未过期的到目的节点的路由，如果存在，则直接使用可用的路由，否则启动路由发现过程。具体过程如下：源节点S将使用洪泛法发送路由请求消息（RREQ），RREQ包含源和目的节点地址以及唯一的标志号，每个收到请求信息的节点检查自己是否有到目的节点的路由，若没有，则把自己的地址加入到路由记录（route record）中，然后前向转发。节点只转发没有收到过的路由信息和没有自己地址的路由信息。当RREQ消息到达目的节点D或任何一个到目的节点路由的中间节点时（此时，RREQ中已记录了从S到D或该中间节点的所经过的节点标识），D或该中间节点将向S发送路由应答消息（RREP），该消息中将包含S到D的路由信息，若该节点有通往源节点的路由路径，使用该路由传递路由应答，否则查看对称信道是否可用，若仍不可用，则启动路由发现程序。此外，中间节点也可以使用路由缓存技术（Routing Cache）来对协议作进一步优化。

路由维持：路由维持是通过路由错误消息（route error）和应答信息来完成。当链路层发生严重错误是会产生route error消息，节点收到该消息，会将出错节点以及所有包含出错节点的路由从缓存中删除。应答消息包括被动应答，即节点可以听到下一跳节点的前向发送。

DSR的优点：①节点仅需要维护与之通信的节点的路由，减少了协议开销；②使用路由缓存技术减少了路由发现的耗费；③一次路由发现过程可能会产生多条到目的点的路由。DSR的缺点：①每个数据报文的头部都需要携带路由信息，数据包的额外开销较大；②路由请求消息采用洪泛方式，相邻节点路由请求消息可能发生传播冲突并可能会产生重复广播；③由于缓存，过期路由会影响路由选择的准确性。

Temporally Ordered Routing Algorithm（TORA） 临时按序路由算法

TORA是一个基于链路反转方法的自适应的分布式路由算法，主要用于高速动态的多跳无线网络。作为一个由源端发起的按需路由协议，它可以找到从源到一个目的节点的多条路由。TORA的主要特点是：当拓扑发生改变时，控制消息只在拓扑发生改变的局部范围传播。因此，节点只需维护相邻节点的路由信息。协议由3部分构成：路由产生、路由维护和路由删除。初始化时，目的节点的高度（即传播序列号）被置为0。然后由源端广播一个含有目的节点ID的QRY分组，一个高度不为0的节点响应一个UPD分组。收到UPD分组的节点的高度将比产生该UPD分组的节点的高度大1，并且具有较大高度值的节点被规定为上游节点。通过这种方式能够创建一个从源到目的节点的一个有向无环路图（DAG）。

当节点移动导致DAG被破坏时，需要路由维持程序来重新建立一个根为同一目的节点的DAG。当节点的下游链路失败时，会产生一个新的参考标准，导致相邻节点传播这个参考标准，有效的应对失败。链路会反转来响应这种变化以适应新的参考标准。这和当节点没有下游链路是反转一个或者几个链路的方向有相同的作用。时间是TORA的一个重要参量，因为“高”权重取决于链路失败的逻辑时间。TORA假设网络中所有节点均时钟同步。其权重由五部分组成：链路失败逻辑时间、定义新参考标准节点的唯一的ID、一个反映标识bit、一个传播序列参数、节点的唯一ID。前三个参数一起用来反映参考标准。当任何节点由于链路失败失去下游节点时一个新的参考标准就会定义。TORA路由删除阶段通过泛洪广播一个clear packet(CLR)来删除无效路由。

TORA存在的一个问题是当多个节点同时进行选路和删除路由时会产生路由振荡现象。

Associativity-based Routing（ABR） 基于结合性的路由

本算法避免了环，死锁，分组复制，并定义了一种新的度量：degree of association stability(相关性稳定度)。每个节点周期的产生一个beacon来表示它的存在。邻节点受到此beacon消息后更新associativity table。当收到所有的beacon后，该节点的associativity标识增加。Association stability定义两个节点在时间和空间上的连接稳定性。一个高水平的association stability意味着节点移动性低。反之亦然。当相邻节点或者节点自身移动时，association ticks 重置。ABR的一个基本目标是使用生存时间长的路由。包括三个阶段：路由发现、路由重构（RRC）、路由删除。

路由发现过程是通过广播路由请求和等待应答（BQ-REPLY）的过程完成。当一个节点需要路由时广播一个BQ消息来寻找含有去目的地的节点。收到该信息的中间节点将自己的地址和它与邻节点的association ticks 加入路由请求信息，下一接收节点删去上一节点association ticks中除去自己和上一节点的其他记录，这样，每一个到达目的节点的请求包含着本路径上所有节点的association ticks，目的节点可以通过比较个路径来选择最佳的路由。当几条路由有相同的association stability时，目的节点选择跳数较少的路由。然后目的节点通过该条路径来回复RREP信息。回复RREP的节点被标识为有效，其他节点仍为未激活，避免了目的节点收到多个复制信息。

RRC根据是哪个节点移出可以包含了部分的路由发现，无效路由删除，有效路由更新和新路由发现。源节点移动导致新的BQ-RREP，RN[1]表示删除下游链路。目的节点移动导致上游节点删除链路并通过本地请求（LQ[N]）检测是否仍可到达目的节点。H表示从上游节点到目的节点的最大跳数。若目的节点收到LQ消息，则回复RREP消息连接。否则，退回到上一节点执行LQ，该节点执行RN[1]，若LQ在一半节点上仍无效，则返回源节点重新执行BQ-RREP。

当路由不再需要时，源节点广播路由删除（RD）消息使路由节点更新其路由表。本消息为全网广播，因为源节点不知道RRC过程改变的路由信息。

Signal Stability Routing（SSR） 信号稳定性路由

该算法是基于相邻节点间信号强度的稳定性作为度量。该算法选择具有最强连接性的路由。它可以分为两个协作的协议：动态路由协议（DRP）和静态路由协议（SRP）。

DRP负责维持信号稳定程度表（SST）和路由表（RT）。SST记录着邻节点通过周期发送beacon测得的信号强度。信号强度会记录为强信道或者弱信道。所有的消息分组都先由DRP接收和处理。在更新所有的表之后，DRP将接收的消息交给SRP。

SRP的处理过程为:若为目的节点，则将消息压入堆中，否则，则在RT中寻找下一跳发送。如果RT中没有找到相应路由，则启动route-search过程。路由请求消息为全网广播，但是为了避免环，只在节点从强信道接收到并且之前没有处理过该消息时发送。目的节点选择最先到达的路径，因为这极有可能是最短路径或者最不拥塞的路径。目的节点沿着该路径反向回复route-reply消息，该路径上的节点更新自己的RT。

若路由请求消息在某个只有弱信道的节点被丢弃，源节点在某个时间内未收到回复，则其修改路由请求头部的PREF域来标识弱信道也是可接受的重新找路。

当检测到失败链路时，内部链路发送一个出错消息通知源节点哪个信道失败了。源节点会启动一个新的找路程序同时发一个删除路由消息通知失败链路上的所有的节点。

AODV和DSR的路由发现过程很相似，但是由于DSR中携带全部的路由信息，而AODV中只携带目的节点信息，因此DSR比AODV的overhead更大。类似的，DSR的应答过程也比AODV的overhead要大。DSR存储需求也比AODV大。AODV还有一个优点是支持多播，上述的其他协议均不支持。但AODV协议要求信道对称，而DSR无此要求。

DSR是用于节点移动速度适中，考虑包的传输时延的网络。其优点是DSR不需要周期广播，从而节省了带宽和能耗。而且DSR允许节点在cache中保持到目的节点的多条路由。当当前路由断掉时，源节点可以检查是否还有有效路由，这样不用再启动路由发现程序，路由恢复比其他协议要快。DSR不适合大规模网络。

TORA是一个非常适合节点密度较大网络的信道反转算法。其创新在于提出了DAG辅助建立路由。它的一个优点是支持多路由。只有它和DSR考虑在在一堆源目的节点间维持多条路由。当路由失败时不一定要启动路由重建，节省了带宽。虽然多播不是TORA的基本功能，但是在其他协议的辅助下也支持多播。但其依赖同步时钟，了其应用。TORA的路由重建比其他协议慢，因为它潜在的存在振荡的可能。

ABR是广播和点对点路由的折中，其使用连接导向的前向方法。路由选择主要看该路径上的association ticks，虽然不一定是最小跳数，但是该路由生存时间最长。一个存在期长的路由需要较少的路由重建，因此吞吐量较高。由于只有最好的路径会被标志为有效，该路由不会产生重复分组。但是ABR依赖周期的beacon消息，其周期必须足够短以保证准确反映空间，时间和节点的连接状态。这会导致一定的能耗。与DSR不同，ABR不需要cache。

SSR是ABR的一个变种，它选路由的标准是信号强度和路由节点位置的稳定性。它的一个缺点是不像AODV和DSR一样，中间节点不能对路由请求应答，路由发现时间较长。而且，当路由失败时，必须从源节点重新启动路由发现程序，而不考虑路由恢复。中间节点修复路由是否合适要取决于网络环境，中间节点修复更优还是源节点修复更优。

Table-Driven vs. On-Demand Routing

表驱动的ad hoc路由方式类似于无连接的方式转发数据包，而不考虑该路由需要的时间和频谱，它基于一个不断传播的路由表更新方案。若使用按需路由，当节点需要一个去往目的节点的路由时，需要等待指导有路由发现。另一方面，由于路由信息需要不断传播并记录在路由表中，去往任何节点的路由都一直是可用的，而不管该路由是否需要，这对数据传播有用，但是却损失了大量的信号和能量。由于带宽和能量都是移动节点的稀有资源，这是一个很大的。

另外平铺路由呢复杂度低，容易使用，但是却了它的规模。