常用路由方式

在组建网络时，选择路由方法是不可避免的问题。一般所说的路由就是为消息的传输选择一条路径，使得要传输的数据沿着这条路径从源节点发送到目的节点。

路由协议分类

分类依据 路由类型 特点 优点 缺点 典型路由算法
根据路由发现策略 主动路由 维护路由表，包含邻居节点探测和路由广播 查表寻径，所需时间较少 开销较大，路由协议不收敛 OSPF等
被动路由 在有需求时会按需进行路由发现 不需周期性的路由信息广播，节省网络资源 路由发现时存在延时 DSR、IP、IPX、APPLE TALK
根据网络管理的逻辑结构 平面路由 网络中所有的节点在路由功能上地位相同 无特殊节点，流量分布均匀，算法易于实现 扩展性弱，没有对通信资源的管理 洪泛、SAR、定向扩散
分层路由 采用簇的概念对网络节点进行层次划分 满足无线网络的扩展性，延长网络的生命周期 在分簇的过程中会消耗能量 LEACH、TEEN、多层类聚算法

洪泛路由算法

本算法最初应用于交换机和网桥之间的数据传递，即某台设备接收到数据之后再次将此数据发送给除此设备之外的所有设备，类似于洪水流动。采用洪泛路由进行数据传输时，消息会沿着不同的路径进行路由，网络中的所有设备均会收到消息并进行中继，直到消息到达目的设备。

洪泛路由协议方便实现且简单有效，同时还具有较高的鲁棒性。网络中不存在特定的集中式路由器，且网络中的路由状态信息无需维护。网络中所传输的消息在到达其目的地之前有多条路径可以选择。然而，在实现过程中，传统的洪泛路由算法也存在其固有的缺点。进行洪泛广播时，网络中所有的节点都会对接收到的消息进行中继，这种中继方式很容易产生大量的消息导致广播风暴，同时网络中消息数量的增多还有可能导致消息碰撞。

连接状态路由协议

连接状态选路协议（Link State Routing Protocol）为整个拓扑结构保持了一张路由表（routing table），通过这张表来找到拥有最少连接消耗的路径。所有的节点使用 flooding technique定期地发送连接消耗的信息。每一个节点使用收集的新的连接消耗信息来更新自己的路由表。由于拓扑结构的动态行为或无线媒介，连接消耗信息可能是不一致的，例如突如其来的不正确的传播时延。这可能造成在连接更新时发生短暂的路由循环。

距离向量路由协议

距离向量路由协议（Distance Vector Routing Protocol）通过使得每个节点i保持一张含有距离或耗费集合{dij(x)}的表来进行操作，其中节点j是节点i的相邻节点。在将数据包发给目的节点x时，如果节点i的相邻节点k是i的所有相邻节点中的最小值，则将节点k当做是节点i的下一跳。这张路由表给出了每个目的节点的最佳距离以及哪个路由可以到达。为了保持最新的距离结合，每个路由器与它所有的相邻节点定期交换信息。如果交换结束后，一个节点 到任何一个相邻节点的最短距离将发生变化，这个过程经一直重复知道所有的节点完成路由表的更新。但是，由于旧的的信息，在更新路由表时，DV路由算法可能引起短暂的或长期的循环。

OSPF协议与链路状态算法

OSPF(Open Shortest Path First开放式最短路径优先）是一个内部网关协议(Interior Gateway Protocol，简称IGP），用于在单一自治系统（autonomous system,AS）内决策路由。是对链路状态路由协议的一种实现，隶属内部网关协议（IGP），故运作于自治系统内部。著名的迪克斯加算法（Dijkstra）被用来计算最短路径树。与RIP相比，OSPF是链路状态协议，而RIP是距离矢量协议。

链路状态算法（也称最短路径优先算法）用于更新路由表。其基本思想是互联网上的每个路由器周期性的向其他路由器广播自己与相邻路由器的连接关系，以使各个路由器都可以画出一张互联网拓扑结构图。利用这张图和最短路径优先算法，路由器就可以计算出自己到达各个网络之间的最短路径。适用于大型网络。收敛速度快。

DSR路由协议

动态源路由协议(Dynamic Source Routing, DSR)是在移动自组网(MANET)中使用的一种路由协议。它工作在TCP/IP协议族的网络层。

DSR路由协议是属于按需路由协议的一种，基础为源路由寻径机制，网络中的节点可以动态的发现从源节点到目的节点之间完整的路由信息。在每个分组的头部都具备
包含整条路由的信息，在进行分组转发时，路由器首先会获取分组头部的缓存记录，之后按照缓存记录来转发分组。源节点在进行数据发送之前，会先将源节点到目的节点之间的完整路由信息放入需要发送的数据包中，数据包在被转发时免去了路由表查询过程，只需从数据包中取得下一跳节点进行转发即可，同时所有经过的中间节点都不需要为转发数据储存所需的路由消息，这在一定程度上减少了网络的开销。

1.产生路由请求
当源节点需要与某目的节点进行通信时，它首先在本节点维护的路由缓存中查找是否有到达该目的节点的路由。若路由缓存中已包含了到达该目的节点的有效路由，则立即使用此路由发送数据分组，否则它将向所有邻居广播RREQ(Route Request)分组，以启动一个路由发现过程来找到一条到达该目的节点的可用路由。

2.节点对路由请求的处理

  • 1.如果接收RREQ的节点是该路由请求的目的节点，则向发起RREQ的源节点返回RREP分组。将收到的RREQ分组的源节点地址、RREQ分组中携带的源路由节点地址列表和本节点的地址按顺序排列作为源路由封装在RREP(Route Reply)分组中发送给源节点，并将处理后的RREQ分组删除。
  • 2.收到RREQ的节点检查自己是否已经包含在RREQ携带的源路由节点列表中，如果是则将RREQ分组丢弃。
  • 3.如果协议要求使用双向链路，节点要检查前一节点是否在自己的通信范围内，如果不在则丢弃该RREQ包；如果不确定则向前一节点发送一TTL值为“1”的RREQ分组，如果收到前一节点回复的RREP这表示两节点之间是双向链路，继续处理RREQ分组，否则表示两节点之间为单向链路则将RREQ分组丢弃。
  • 4.接收RREQ的节点必须要查找当地的路由请求表看有无发起此RREQ的源节点所对应的路由请求表入口。如果有则在当地缓存中查看有无与(此RREQ路由请求号，此RREQ目的节点IP地址)对相对应的入口，如有则将现在收到的RREQ分组丢弃。
  • 5.如果接受RREQ的节点的路由请求表中没有和此RREQ对应的表项，说明以前没收接受过此RREQ，则按以下步骤处理该RREQ请求分组：利用此RREQ的(路由请求序号，目的节点IP地址)值，为此RREQ分组在节点的路由请求表中创建一入口；对此RREQ分组做一个完整的拷贝；将节点自己的IP地址追加到RREQ分组的源路由节点列表中；节点在自己的路由缓存中查找到RREQ分组中目的节点的路由，有则向发起RREQ的源节点回复一RREP分组，称为“缓存路径回复(cached Route Reply)”；如果节点在自己的路由缓存中没有找到通往RREQ目的节点的路径，则将新改好的RREQ拷贝广播发送出去。

3.中间节点回复RREP分组
在2中讲到如果接收RREQ的中间节点在自己的路由缓存中找到通往RREQ分组目的节点的路径则要向源节点回复一cached Route Reply分组。这种机制可以大大减小网络中因为路由发现过程所造成的开销，因为这种机制可以大大减少路由发现过程中的RREQ广播报文。

下面详细叙述向源节点回复cached Route Reply的过程:

  • 1.中间节点在回复RREP之前首先要检查被回复的源路由中不会出现节点重复出现的情况。即查看由RREQ原节点地址、RREQ中已经积累的节点IP地址列表、本节点路由缓存中找到的路径中的IP地址顺序排列下来的地址列表中有无重复出现的IP地址，如果有则不能继续进行缓存路径回复，而转到2中步骤5的最后一步继续执行。如不存在重复出现的IP地址就向下执行。
  • 2.中间节点将从自己路由缓存中得到的路径cached-route追加到RREQ分组头中的源路由地址列表中，这样就得到要发给RREQ源节点的完整路由：<源节点IP地址、RREQ分组头携带的节点的IP地址列表、cached-route>。此中间节点的IP地址已经在RREQ分组头中，不需再追加。将得到的源路由封装在RREP包中发送给发起RREQ的源节点。
  • 3.中间节点发送完路由缓存回复后，就不再继续广播RREQ分组了。此时如果RREQ数据分组头中除了已经处理过的RREQ选项外不再含有其他任何选项，并DSR选项头后面也不含有其他数据负载(TCP或UDP数据)，则中间节点可将此RREQ分组丢弃。否则作如下处理：将RREQ DSR选项头中的目的节点IP地址作为RREQ IP分组的目的IP地址，即置换掉RREQ分组的广播地址；将RREQ分组中的路由请求选项移除；将从中间接点路由缓存中得到地路径作为源路由添加到新的RREQ分组头中；将重新创建的RREQ数据分组按分组头中的源路由转发出去。

4.处理并转发路由回复
目的节点收到RREQ分组得到完整的源节点到目的节点的路由后，将此路由封装在RREP分组中，然后发送给源节点。RREP分组可以封装成一个单独的IP分组传递给源节点，或封装在其他有数据要传输给源节点的IP分组中被捎带回源节点。 目的节点将自己的IP地址追加到RREQ携带的节点的IP地址列表中，将得到的IP地址列表作为返回给源节点的完整路由封装在RREP分组中。RREP数据分组的源IP地址设为发送RREP分组的节点的IP地址，目的IP地址设为发起RREQ的源节点的IP地址。如果使用的底层MAC协议支持双向路由，RREP数据分组可沿RREP选项中携带的源路由的逆向路由依次传输，否则目的节点为此RREP选项发起新的路由发现过程，且要将RREP选项封装在新产生的RREQ数据分组中以防止出现路由发现过程的反复进行。

DSDV路由协议

DSDV （Destination sequenced distance vector routing,目的节点序列距离矢量）路由协议可以用于Ad hoc网络。Ad hoc网络是从传统网络演变而来的，它的不同之处在于相互连接的动态拓扑结构以及设置网络的自动管理。从图论的角度来看，ad hoc网络是由一个节点集合N，一个边的集合E(t)构成的图G(N, E(t))。E(t)中的每条边由两个节点构成，并在一定服务范围之内，它既可以是单向的也可以是双向的。当可移动节点在ad hoc网络中自由移动时，E(t)随着时间发生变化。同时，ad hoc的拓扑结构在任意时间是不定的。由于ad hoc网络拓扑结构的变化性，网络中的节点不得不总是自动更新它们的路由信息。

以往，分组交换网络中的路由协议使用的是DV（distance-vector）或LS（link-state）路由算法。它们都允许一个主机通过“最短路径”到达目的节点时的下一跳。它们最短路径的形式可能是跳数、延迟时间（以ms为单位）、路径中排队的包的数量或其他类似的信息。这种最短路径协议在许多动态的分组交换网络中被成功应用。原则上，任何一个这样的协议也可以被用于ad hoc网络。而DV和LS协议的主要不足之处在于，他们花费了太长的时间去会聚，以及高度复杂的信息。而由于ad hoc网络中无线连接的带宽限制，信息的复杂性一定要被控制在一个较低的程度。另外，快速变化的拓扑结构需要路由协议快速找到相应的路由器。因此，新的路由协议需要满足这样一个基本的哲学体系。DSDV协议是对传统的BF路由协议的变形，它专注于ad hoc网络，解决了传统的DV路由协议中长期存在的循环和无限技术的问题。

DSDV路由协议基于 Bellman-ford 算法实现，为了防止产生路由环路和死锁等问题，该路由协议采用序列号来进行路由新旧的区分。网络中的每个节点都具备一张路由表，而且需要对其进行管理更新，该路由表包含目的节点、下一跳节点、路由计量标准及该路由序列号等信息。当网络中的每个节点都要管理更新一张包含大量信息的路由表时，势必会增大网络的整体开销，所以为了避免该缺点，DSDV 路由协议采用了周期更新和触发更新两种更新方式。

在DSDV中，ad hoc网络中的每个可移动节点保持着一张路由表，它列出了所有有效的目的节点，metric值、到达目的节点的下一跳节点以及由目的节点产生的一个序列号码。利用这样一张存储在每一个可移动节点中的路由表，数据包得以在ad hoc网络的节点之间传送。Ad hoc网络中的每个节点利用定期的广播或当新的重要的信息有效时更新各自的路由表，来保持动态变化的拓扑结构下路由表的一致性。

当检测到网络拓扑变化时，每个移动节点定期或立即使用广播或多播路由表更新包发布路由信息。更新包从metric为1的直连相邻节点开始发送。接收到更新包后，相邻节点更新路由表，将metric增加1，并将更新包重新发送到本节点的相邻节点。这个过程将重复进行，直到ad hoc网络中的所有节点都收到具有相应metric的更新包。更新包还将保留一段时间，以等待本节点与每个特定目标节点的最佳路由包数据到达，然后更新其路由表并重新传输更新包。如果一个节点在等待时间内接收到同一目的地的多个更新数据包，则通常首选序列号较近的路由作为数据包转发决策的基础，但如果仅更改了序列号，则不必立即公布路由信息。如果更新包具有具有相同节点的相同序列号，则将使用具有最小metric的更新包，并将丢弃现有路由或将其存储为不太可取的路由。在这种情况下，更新包将与序列号一起传播到ad hoc网络中的所有移动节点。路由变化的广播可能会被延迟，直到找到最优路径为止。延迟可能不稳定路径的广播可以抑制路由表的波动，减少可能到达的具有相同序列号的路由条目的重复数。

每个移动节点的路由表中的元素都是动态变化的，以保持与ad hoc网拓扑动态变化的一致性。为了达到这种一致性，路由信息广播必须足够频繁或快速，以确保每个移动节点几乎总是能够定位到动态的ad hoc网中的所有其他移动节点。在更新路由信息后，每个节点必须根据动态创建的ad hoc网中的请求将数据包中继到其他节点。

ZigBee路由协议分析

ZigBee协议采用以下两种算法的结合体作为自身的路由算法。

  • AODV：Ad-Hoc On-Demand Distance Vector（按需距离矢量路由）
  • Cluster-Tree algorithm（树型网络结构路由）

其中AODV路由协议是一种按需路由协议，利用扩展环搜索的办法来限制搜索发现过的目的节点的范围，支持组播，可以实现在ZigBee节点间动态的，自发的路由，使节点很快的获得通向所需目的的的路由。这也是ZigBee路由协议的核心。针对自身的特点，ZigBee网络中使用一种简化版本的AODV协议（AODV Junior，AODVjr）。

Cluster-Tree算法包括地址的分配（configuration of addresses）与寻址路由两部分（addresses routing）。包括子节点的16位网络短地址的分配，以及根据目的节点的网络地址来计算下一跳的算法。

作为两种算法的结合体，ZigBee网络中，节点可以按照网络树状结构的父子关系使用Cluster-Tree算法选择路径。即每一个节点都会试图将收到的信息包转发给自己的后代节点，如果通过计算发现目的地址不是自己的一个后代节点，则将这个数据包转发给自身上一级的父节点，由父节点进行类似的判断处理，直到找到目的节点。Cluster-Tree算法的特点在于使不具有路由功能的节点间通过与各自的父节点间的通信仍然可以发送数据分组和控制分组，但它的缺点是效率不高。为了提高效率，ZigBee中允许具有路由功能的节点使用AODVjr算法去发现路由，让具有路由功能的节点可以不按照父子关系而直接发送信息到其通信范围内的其他节点。

AODVjr路由算法

AODVjr路由时一种按需分配的路由协议，只有在路由节点接收到网络数据包，并且网络数据包的目的地址不在节点的路由表中时才会进行路由发现过程。也就是说，路由表的内容是按照需要建立的，而且它可能仅仅是整个网络拓扑结构的一部分。

AODVjr的优点是，相对于有线网络的路由协议而言，它不需要周期性的路由信息广播，节省了一定的网络资源，并降低了网络功耗。缺点是在需要时才发起路由寻找过程，会增加数据到达目的地址的时间。由于ZigBee网络中对数据的实时性要求不大，而更重视对网络能量的节省，因此AODVjr非常适合应用在ZigBee网络中。

一次路由建立由以下三个步骤组成：

  • 1.路由发现
  • 2.反向路由建立
  • 3.正向路由的建立

经过这三个步骤，即可建立起一条路由节点到目的节点的有效传输路径。在这个路由建立过程中，AODVjr使用3种消息作为控制信息：

  • 1.Route Request(RREQ)，路由请求
  • 2.Route Replies(RREP)，路由回复
  • 3.Route Error(RERR)，路由错误

以下将对路由建立的三个过程进行详细描述。

(1)路由发现过程

对于一个具有路由能力的节点，当接收到一个从网络层的更高层发出的发送数据帧的请求，且路由表中没有和目的节点对应的条目时，它就会发起路由发现过程。源节点首先创建一个路由请求分组(RREQ)，并使用多播(Multi．Broadcast)的方式向周围节点进行广播。

如果一个节点发起了路由发现过程，它就应该建立相应的路由表条目和路由发现表条目，状态设置为路由发现中。任何一个节点都可能从不同的邻居节点处接收到广播的RREQ。接收到后节点将进行如下分析：

  • 1.如果是第一次接收到这个RREQ消息，且消息的目的地址不是自己，则节点会保留这个RREQ分组的信息用于建立反向路径，然后将这个RREQ消息广播出去。
  • 2.如果之前已经接受过这个RREQ消息，表明这是由于网络内多个节点频繁广播产生的多余消息，对路由建立过程没有任何作用，则节点将丢弃这个消息。

(2)反向路由建立过程

当RREQ消息从一个源节点转发到不同的目的地时，沿途所经过的节点都要自动建立到源节点的反向路由。也就是记录当前接收到的RREQ消息是由哪一个节点转发而来的的。通过记录收到的第一个RREQ消息的邻居地址来建立反向路由，这些反向路由将会维持一定时间，该段时间足够RREQ消息在网内转发以及产生的RREP消息返回源节点。

当RREQ消息最终到达了目的节点，节点验证RREQ中的目的地址为自己的地址之后，目的节点就会产生RREP消息，作为一个对RREQ消息的应答。由于之前已经建立了明确的反向路由，因此RREP无需进行广播，只需按照反向路由的指导，采取单播的方式即可把RREP消息传送给源节点。

(3)正向路由建立过程

在RREP以单播方式转发回源节点的过程中，沿着这条路径上的每一个节点都会根据PREP的指导建立到目的节点的路由，也就是说确定到目的地址节点的下一跳(next-hop)。方法就是记录RREP是从哪一个节点传播而来．然后将该邻居节点写入路由表中的路由表项。一直到RREP传送到源节点。至此．一次路由建立过程完毕。源节点与目标节点之间可以开始数据传输。可以看出，AODV是按照需求驱动的、使用RREQ．RREP控制实现的、先广播，后单播的路由的路由建立过程。

附：
动态路由中选择最佳路由的几种常见metric

当到达一个网络有多条路径的时候，路由器会根据甚么来选择最优路径，一般来讲路由器会根据以下几种度量值来选择最佳路由。

  • 1、跳数
    它可以简单的记录经过路由器的个数。例如，数据从路由器A发出，经过路由器B到达其他网络，那么其跳数为1，如果经过C到达其他网络，它经过的路由器为2，那么其跳数为2.在RIP中，跳数是衡量路径的主要标准，其最大跳数16，超过16即为不可达。
  • 2、带宽
    一般会选择带宽高的路径，但是不是主要标准，如果在T1线路上，链路带宽占用过多，那么它就可能不会选择这个链路了。
  • 3、负载
    负载反映了沿途链路的流量大小。最优路径应该是负载最低的路径。负载不会像带宽或者跳数那样，路径上的负载变化，那么度量也会跟着变化。这里需要当心，如果度量变化过于频繁，那么会引起路由振荡，路由振荡会对路由器的CPU、数据链路的带宽和拳王稳定性产生负面影响。
  • 4、时延
    时延是报文经过链路经过的时间，使用时延作为度量的路由协议会使用时延较低的链路最为最佳路径。有多种方法可以计算时延，时延不仅要考虑链路时延，而且还要考虑路由器的处理时延和队列时延等因素。另一方面，路由的时延可能根本无法度量。因此，时延可能是沿路各个接口所定义的静态时延的总和。
  • 5、可靠性
    此独联是用以度量链路在某种情况下发生故障的可能性。可靠性是可以变化的或者固定的。可靠性高的链路将被优先选择。
  • 6、花费
    此度量有管理员设置，可以反映路由的登记。通过任何策略或者链路特性对链路的cost进行定义。同时，花费也可以反映出网络管理员的主观意识。

一般以上几种度量不是单独使用，一般是综合使用，通过某种算法来计算最佳路径。

参考内容：
OSPF路由协议分析
OSPF协议与链路状态算法
距离矢量路由协议和链路状态路由协议
目的节点序列距离矢量（DSDV)协议
DSDV协议
动态路由中选择最佳路由的几种常见metric
ZigBee路由协议分析