路由

路由是寻找网络或跨多个网络流量的最佳路径的过程。路由的作用类似于酒店的路线图。在两种情况下，我们都需要以适当的方式将消息传递到正确的位置。

移动自组网中的路由取决于许多因素，例如

• 拓扑建模，
• 路由器选择，
• 发起路由请求，
• 以及可以作为有效寻路启发式的特定底层特征。

在 MANET 中，每个节点或设备都应充当路由器，并且所有路由器在计算通过整个网络的路径时都执行相同的路由算法，因此它们是无法区分的。

路由需求

路由有以下需求

• 由于中心化路由在动态网络甚至小型网络中都是不可能的，因此路由计算必须是分布式的。
• 路由计算不应添加过多节点。
• 如果任何主机需要路由，它们必须能够快速访问。
• 路由计算不应涉及全局状态的维护。
• 每个节点都应关注其到目标的路由，并且不应频繁参与对网络中没有流量的那些部分的拓扑更新。
• 由于广播对于 MANET 来说可能非常耗时，因此应尽可能避免。
• 在路由中，当主路由过时时，必须有一个备用路由。

路由分类

路由协议可分为

1. 主动协议
2. 响应式协议
3. 混合协议

1. 主动协议

主动协议试图持续评估网络内的路由。这意味着主动协议持续维护路由信息，以便在需要转发数据包时，路径已经已知并且可以立即使用。距离矢量协议系列是主动方案的一个例子。

主动方案的优点是，每当需要路由时，确定路由的延迟就可以忽略不计。

不幸的是，在 MANET 环境中维护路由表是一项繁重的开销。因此，这种类型的协议具有以下常见缺点

• 需要大量数据来维护路由信息。
• 对网络重组和单个节点故障的反应迟钝。

2. 响应式协议

响应式协议不维护路由，而仅在需要时调用路由确定过程，或者我们可以说响应式协议仅在需要时构建路由。因此，当需要路由时，会启动某种全局搜索过程。经典洪泛算法系列属于响应式协议组。响应式自组网路由协议的例子包括按需距离矢量（AODV）和时间顺序路由算法（TORA）。

这些协议具有以下优点

• 不像主动协议那样，全局路由表维护的开销很大。
• 对网络重组和节点故障的反应迅速。
  尽管响应式协议已成为 MANET 路由的主流，但它们仍存在以下缺点
• 路由查找时延迟时间长
• 过度的洪泛可能导致网络拥塞。

3. 混合协议

混合协议试图利用响应式和主动方案的优点。此类协议的基本思想是以有限的搜索成本按需启动路由发现。区域路由协议（ZRP）是最受欢迎的混合协议之一。

路由协议还可以按以下方式分类

1. 表驱动协议
2. 源发起的按需协议

1. 表驱动路由协议

• 这些协议称为表驱动，因为每个节点都需要维护一个或多个包含网络中每个其他节点路由信息的表。
• 它们本质上是**主动的**，因此路由信息始终是一致且最新的。
• 协议通过在整个网络中传播更新来响应网络拓扑的变化，以便每个节点对网络都有一致的视图。

表驱动路由协议的分类如下

目的序列距离矢量路由

• 目的序列距离矢量路由（DSDV）是基于 Bellman-Ford 算法的 MANET 表驱动路由协议。
• DSDV 由**C. Perkins 和 P. Bhagwat 于 1994 年**开发。该算法的主要贡献是，即使路由表中存在环路，该算法也能正确工作。
• 众所周知，每个移动节点都维护一个路由表，其中包含到网络中每个可能目的地的路由以及到目的地的跳数。
• 表中的每个条目都包含由目的节点分配的序列号。
• 序列号允许节点区分旧路由和新路由，并有助于避免路由环路的形成。
• 新的路由广播包含
  • 目的地址。
  • 到达目的地所需的跳数。
  • 有关目的地的已收到信息序列号以及一个唯一分配给本次广播的新序列号。
• 如果存在多个到达同一目的地的路由，则使用具有最新序列号的路由。如果两个更新具有相同的序列号，则使用具有较小度量的路由来优化路由。

例如，上面网络中节点 A 的路由表是

基本上，该表存储了节点 A 可达的所有可能路径的描述，以及跳数、跳数、序列号和安装时间。

优点

• 目的序列距离矢量路由是最早可用的算法之一。它适用于创建节点数量很少的自组网。

缺点

• 目的序列距离矢量路由需要定期更新其路由表，即使在网络空闲时，这也会消耗更多电池电量和少量带宽。
• 该算法不适用于高度动态的网络。

集群头网关交换路由

• 集群头（CH）网关交换路由（CGSR）协议与目的序列距离矢量路由在寻址类型和使用的网络组织方案方面有所不同。
• CGSR 不使用扁平网络，而是使用集群头，集群头控制一组自组网节点，从而为集群之间的代码分离、路由、信道访问和带宽分配实现分层框架。
• 识别合适的集群和选择集群头非常复杂。一旦定义了集群，就希望在集群内使用分布式算法来选举一个节点作为集群头。
• 使用集群头方案的缺点是频繁更改会对性能产生不利影响，因为节点花费更多时间来选择集群头而不是转发数据包。因此，使用最少集群更改（LCC）聚类算法，而不是每次集群成员更改时都选择 CH。使用 LCC，CH 仅在两个 CH 接触时，或当一个节点与所有其他 CH 失去联系时才会更改。

• 在此方案中，每个节点必须维护一个集群成员表（CMT），其中存储网络中每个节点的目的 CH。集群成员表由节点使用 DSDV 算法定期广播。
• 当一个节点从邻居接收到这样的表时，它可以更新自己的信息。正如预期的那样，每个节点还维护一个路由表以确定到达任何目的地的下一个跳。

无线路由协议（WRP）

无线路由协议是一种用于 MANET 的主动单播路由协议。它使用距离矢量路由协议的增强版本，该版本使用 Bellman - Ford 算法来计算路径。

对于无线路由协议（WRP），每个节点维护 4 个表

• 距离表
• 路由表
• 链路成本表
• 消息重传列表（MRL）表

消息重传列表中的每个条目包含更新消息的序列号、重传计数器、每邻居一个条目的确认所需标志向量，以及更新消息中发送的更新列表。当任何节点收到新节点的 hello 消息时，它会将新节点添加到其路由表中，并向新节点发送其路由表的副本。节点必须在一定时间内向其邻居发送消息以确保连接性。

优点

• WRP 的优点与 DSDV 类似。此外，它收敛速度更快，并且表更新次数更少。

缺点

• 维护多个表会增加 MANET 中节点的内存需求和处理能力。
• 由于其可扩展性有限，WRP 不适用于高度动态和非常大的自组无线网络。

2. 源发起的按需协议

• 与表驱动路由不同，源发起的按需路由本质上是**响应式的**。此类协议仅在源请求时生成路由。
• 换句话说，当源节点需要到目的地的路由时，源节点会启动网络中的路由发现过程。此过程在发现到目的地的路由或检查所有可能的路由而未成功后结束。
• 发现的路由由路由维护过程维护，直到不再需要或目的地变得不可访问。

源发起的按需路由分类如下

自组网按需距离矢量路由（AODV）

• AODV 是 MANET（移动自组网）和其他无线自组网的路由协议。
• 它是一种响应式路由协议；这意味着它仅在需要时才建立到目的地的路由。
• AODV 路由建立在 DSDV 算法之上。它是 DSDV 的重大改进。
• 不在特定路径上的设备不维护路由信息，也不参与路由表交换。
• 当源需要发送消息到目的地但没有到后者的有效路由时，源会启动路由发现过程。
• 源向其所有邻居发送路由请求（RREQ）包，后者将其请求转发给所有邻居，依此类推，直到到达目的地或到达具有到目的地“足够新”路由的中间移动节点。

上图说明了广播请求（RREQs）在网络中的传播。由于在 DSDV 中，使用目的序列号来确保所有路由无环路并包含最新的路由信息。每个节点都有一个唯一的序列号和一个广播 ID，当节点发起 RREQ 时，该 ID 会递增。

广播 ID 与节点的 IP 地址一起唯一标识每个 RREQ。

中间移动节点仅在其到目的地的路由的序列号大于或等于 RREQ 中包含的序列号时才回复。为了优化路由性能，中间节点会记录地址。

从上图可以看出，由于 RREP（路由回复包）沿着反向路径回传，因此该路径上的节点会设置其前向路由条目，使其指向刚刚接收到 RREP 的节点。这些前向路由记录指示了活动的前向路由。RREP 继续沿着反向路径回传，直到到达路由发现的启动者。因此，AODV 只能支持对称链路的使用。

动态源路由（DSR）

• 动态源路由是一种基于源路由的按需路由协议。
• 它与 AODV 非常相似，因为它在传输计算机请求路由时按需形成路由。但是，它使用源路由，而不是依赖于每个中间设备的路由表。动态源路由已经进行了许多连续的改进。
• 该协议分两个主要阶段工作
  • 路由发现
  • 路由维护
• 当节点有消息要发送时，它会联系路由缓存以确定它是否具有到目的地的路由。如果存在到达目的地的活动路由，则将其用于发送消息。
• 否则，节点通过广播路由请求包来启动路由发现。路由请求存储目的地地址、源地址和一个唯一的标识号。
• 接收到路由请求的每个设备都会检查它是否具有到目的地的路由。如果没有，它会将自己的地址添加到数据包的路由记录中，然后将其重新广播到其传出链路上。
• 为了最小化广播次数，移动设备仅在尚未见过该数据包且其自己的地址未在路由记录中时才重新广播数据包。