下载掌阅APP，畅读海量书库
立即打开
由于移动自组织网络（MANET）的高度动态性和能量有限性，互联网现有路由技术难以适用于移动自组织网络，因此必须开发适合其特点的移动自组织网络路由技术。移动自组织网络路由协议的设计需要考虑众多因素，包括分布式计算、高效性、及时性、自适应性、安全性和能耗等，使得路由成为移动自组织网络的研究难点。在移动自组织网络的概念被提出之后，路由选择算法一直是该领域的研究重点。
本节首先介绍基本路由机制、路由机制优化原则和路由分类方法。根据路由计算的产生时间进行分类是路由协议的一种基础分类方式，本节以该分类为主线介绍表驱动路由协议、按需驱动路由协议和混合路由协议。在上述基本路由协议的基础上，本节详细分析路由选择算法及其在预测模型、能耗模型、位置信息模型等模型方面的最新研究进展。
通常来说，由网络节点（即路由器）组成的通信子网的重要功能是路由和转发，而其中路由是数据转发的基础。移动自组织网络中的节点的移动性较强，使得网络拓扑和路由维护具有很大难度，为此，人们针对这种移动性强的自组织网络设计了很多其特有的路由机制。下面介绍基本路由机制，并分析移动自组织网络的路由机制优化原则和路由分类方法。
1.基本路由机制
计算机网络的数据传送过程是指将消息从源节点通过网络传送到目的节点，数据传送过程包含两个操作：路由和转发 [24] 。借助这两个操作，数据消息可以得知传送的路径并且沿着该路径转发，从而该数据消息从源主机发出，经过一个或多个中间节点的路由转发，最终传送到目的主机。移动自组织网络具有多跳性，通常分组需要经过多跳才能传送到目的节点。
通常来说，广义“路由”包括“路由协议交互”和“本地路由计算”两部分，其中路由协议交互主要负责网络路由信息的传送和在不同节点之间的交互。如图3-4所示，节点借助路由算法确定数据消息传送的路径：主机E→路由器R5→路由器R3→路由器R2→主机B。为了实现上述路由选择，整个路由过程包含两个步骤：首先，路由器之间交互网络的距离向量、路径向量或链路状态等信息，如路由器R3和R5交互各自所了解的距离向量信息；其次，每个路由器根据在上述操作中获得的信息，计算下一跳信息或具体路径。路由器R5根据协议交互过程中所了解到的路由器R4、R3各自的距离向量信息，分别计算经过路由器R4、R3到达目的主机所需的“代价”，最终根据该计算结果选择合适的路由并进行数据消息的传送。
网络各个节点之间由路由协议交互传送的路由信息分为距离向量、路径向量和链路状态等类别。距离向量可以理解为到达网络各个节点的距离和相应的下一跳节点；路径向量是在距离向量的基础上，增加了端到端路径所经过的具体节点；链路状态则为网络节点之间的邻接关系和链路代价。路由选择算法是指为了实现路由功能而设计的算法，负责确定分组应当传送的路径，是网络层的核心部分。
图3-4 基本路由机制
移动自组织网络路由机制的基本原理与互联网的路由机制相同，但移动自组织网络所具有的特点对其路由协议的设计提出了特殊要求。在移动自组织网络中，动态变化的拓扑结构和节点位置、有限的资源和能量、节点间的无线通信等，使得OSPF、RIP等传统的互联网路由协议并不适用于移动自组织网络。
2.路由机制优化原则
在介绍具体路由协议之前，首先根据移动自组织网络的特点，给出移动自组织网络路由机制的优化原则。移动自组织网络的路由协议和互联网的路由协议一样，都是为了实现数据包的高效、快速、准确传送。根据移动自组织网络的特点，其路由机制具有如下特殊要求。
（1）动态适应性
因为移动自组织网络具有高度动态性，所以其路由机制必须能够适应网络拓扑结构的动态变化，具有快速应变的能力。当网络拓扑结构变化导致某些路由不可用时，路由机制能够迅速找到可用的路由，自行恢复数据的传送。对于移动自组织网络，每个移动节点要充当网络的路由器，移动自组织网络的路由机制要求其具有动态适应性，以适应节点移动所带来的网络拓扑结构的动态变化。
（2）节能性
因为移动自组织网络的节点能量有限，所以路由机制必须在节能的前提下实现快速路由。移动自组织网络的移动节点执行路由转发功能，能量供应由自身携带的电池提供。所以，移动自组织网络的路由机制需要具有节能性。例如，在移动自组织网络中，需要降低控制信息与数据信息的比率，高效利用有限的带宽资源，尽量减少消息传送的接转次数，减少数据传送时间和数据量等。
（3）安全性
因为移动自组织网络采用无线通信并具有高度动态性，节点在不安全的环境中使用共享的无线介质传输，所以节点的物理保护有限，易受到各种网络攻击 [25] 。因此，在保证高效、快速、准确路由的前提下，需要尽可能地提高路由机制的安全性，降低路由过程中遭受攻击的可能性。
3.路由分类方法
移动自组织网络的路由与应用密切相关，单一的路由机制无法满足各种应用需求。根据路由协议交互和路由计算的时机、逻辑组织结构、协议的功能等分类原则，下面给出路由的主要分类方法。
（1）表驱动路由、按需路由和混合路由
根据路由表项的产生时间，可以分为表驱动路由、按需路由和混合路由 [26] 。表驱动路由也称为预计算路由、先应式路由。表驱动路由事先维护网络中从一个节点到其他节点的所有路由信息，在数据传输之前计算得到路由表项，然后根据该路由表项进行数据传输。表驱动路由的优点在于节点可以直接根据路由表中的信息进行数据传输，不需要额外的路由建立等待时间；缺点在于建立和维护路由表的开销较大。因此，表驱动路由适用于拓扑结构动态性不强而需要高速数据转发的网络。
按需路由也称为在线路由、反应式路由。按需路由仅在有数据需要传输时，根据所需传输的具体目的地计算相应的路由。节点无须事先维护路由信息表，而仅仅在数据传输过程中形成所需的路由表项。按需路由在一定程度上降低了协议交互的开销，但是路由建立的时延较大，适用于动态性较强的网络。
混合路由则综合上述两种技术的优点，将二者相互结合，实现网络的路由。例如，在规模较大的网络中，采用层次结构的路由技术，不同层次分别采用上述一种路由方案。因此，混合路由往往适用于节点计算能力较强并且规模较大的移动自组织网络。
在当今互联网特别是骨干网的路由体系中，由于网络拓扑结构相对固定，而且需要低延迟的高速转发，因此多采用表驱动路由。相反，移动自组织网络动态性强，路由表的维护代价较高，而传输速率和延迟方面要求却不高，因此多采用按需路由和混合路由。
（2）基于拓扑的路由和基于位置的路由
根据是否使用地理位置信息，可以分为基于拓扑的路由和基于位置的路由。在移动自组织网络中，多数路由机制基于所认知的拓扑结构进行路由选择，被称为基于拓扑的路由。有些应用需要确定节点的地理位置，进而基于该地理位置信息进行路由选择，被称为基于位置的路由。互联网中位置与网络的互联关系之间不具有紧密的联系，所以互联网多采用基于拓扑的路由。移动自组织网络普遍采用无线信道传输，在理想情况下，很容易根据地理位置信息来确定节点之间的互联关系。虽然这类方案需要通过GPS或者其他定位装置获取节点的位置信息，但由于移动自组织网络拓扑结构动态变化，因此基于位置的路由仍然具有广泛的应用前景。
（3）距离向量路由、路径向量路由和链路状态路由
根据协议交互信息的类型，可以分为距离向量路由、路径向量路由和链路状态路由。在距离向量路由中，每个节点维护一张表，该表列出了当前已知的到每个目标节点的最佳距离，以及所使用的下一跳节点。每个节点通过与邻居交换上述信息，移动节点不断更新自己的路由表并实现路由选择。因此，距离向量路由被描述为“将整个世界告诉我的邻居”。路径向量路由以距离向量路由为基础，每个节点不但记录到达目标节点的最佳距离和下一跳节点，而且记录整条路径依次所经过的节点（即路径向量），从而防止在路由计算过程中产生路由回路。
在链路状态路由中，使用反映网络拓扑结构的邻接表来描述网络的链路状态，该邻接表记录了所有节点间的邻接关系和链路代价。在该机制下，当移动节点发现新的邻居节点出现时，将会测量与邻居节点的延迟等信息，并且使用路由公告将上述信息传送到其他节点，其他节点则利用该链路状态信息重新计算最短路径。因此，可以将链路状态路由描述为“将我的邻居告诉整个世界”。
（4）源路由和分布式路由
根据路由信息存储的位置，可以分为源路由和分布式路由。源路由由源节点决定完整路径，在发出的每个消息的消息头中携带路径所经过的节点信息，因而中间节点无须建立和维护路由信息。源路由的路由计算较为简单，减少了通信开销，但是消息头过长。分布式路由则由每个中间节点独立选择传输的下一跳节点，能够避免消息头过长问题，但是中间节点计算负担较大。此外，在分布式路由中，如果各个节点对网络拓扑的认知不一致，则可能会导致路由回路。
（5）单径路由和多径路由
根据数据传输使用路径的数量，可以分为单径路由和多径路由。在单径路由中，源节点发送的数据分组沿着一条路径从源节点到达目的节点。其优点在于路由方案简单，能够较好地避免数据传输乱序；缺点在于路由容错性较差，路径的传送负担不均衡。在多径路由中，源节点发送的数据通过多条路径到达目的节点。该技术容错性较强，能够均衡网络负载，但是路由方案复杂，而且难以避免多条路径传输引入的乱序。
（6）平面路由和层次路由
根据节点的组织是否存在层次结构，可以分为平面路由和层次路由。在平面路由中，所有移动节点地位平等，路由协议设计简单，健壮性好，但是路由维护的代价较大。在层次路由中，节点地位不平等，整个网络划分为不同的簇（或区域），每个簇由簇头和成员组成，簇头负责管理簇内网络和维护簇内路由 [27] 。由于簇头参与网络管理，因此层次路由扩展性好，易于管理，但是簇头的计算代价较大。由于可扩展性是互联网所面临的一个重要问题，因此互联网的路由采用层次路由。移动自组织网络通常具有较强的动态性，因而在可扩展性要求不高的情况下，可以考虑采用平面路由。
（7）单播路由、广播路由和多播路由
根据消息发送的对象，可以分为单播路由、广播路由和多播（组播）路由。单播路由是节点将消息发送给特定节点的机制。虽然单播路由实现简单，但如果多个节点需要接收数据，那么网络需要将相同信息重复传送多次。广播路由是节点将消息广播给在一个子网内所有节点的机制。由于不感兴趣的节点同样会接收到广播的消息，因此广播路由浪费了带宽并且加重了节点的计算负担。多播路由能够将消息发送给某个特定节点集合。相比而言，多播路由的特定组通常具有明确的定义，组内节点的数量比整个网络的规模小很多，因此其路由效率较高，但其实现机制非常复杂。
（8）其他分类方法
路由作为网络层的重要功能，除存在上述分类方法以外，根据路由所具有的特定功能，还可以进一步做出如下分类：根据路由是否支持服务质量控制，可以分为服务质量感知路由和非服务质量感知路由；根据路由是否提供网络安全保障，可以分为安全路由和非安全路由等。由于移动自组织网络所具有的动态性和能量有限性，因此对服务质量感知路由和安全路由需要做进一步研究。
表驱动路由协议，也称为预计算路由协议，它事先维护网络中从一个节点到其他节点的所有路由信息，在数据传输之前形成路由表项，然后根据该数据表项进行数据传输，从而实现快速路由。移动自组织网络的基本表驱动路由协议包括DSDV、WRP、CGSR、OLSR等。
移动自组织网络具有高度动态性，网络的拓扑结构动态改变，消息传送具有一定困难。较为简单的消息传送方法是洪泛方式，也就是说，源节点在发送消息时，将目的节点的地址加载在消息头部，向邻居节点进行广播，中间节点收到消息后进一步向其所有的邻居节点广播该消息，从而最终使该消息抵达目的节点。洪泛方式不但易于实现，而且在拓扑结构不断动态改变的情况下，能够将消息有效地传送到目的地；然而很多节点不必要地参加了消息的转发，增加了节点的计算负担和网络的传送负担。为了解决上述问题，人们提出根据路由表进行数据转发的思想，也就是说，通过路由表的建立与维护，减少洪泛给移动自组织网络带来的影响，这就是表驱动路由协议的核心思想。
1.基于目的序号的距离向量协议DSDV
基于目的序号的距离向量（Destination-Sequenced Distance Vector，DSDV）协议是一种采用传统的Bellman-Ford路由算法的基于距离向量的分布式表驱动路由技术 [28] 。该技术于1994年被提出，是最早为移动网络专门设计的路由协议之一。
每个节点都要维护路由表，该路由表包含能到达的目的节点、到达目的节点的度量值以及该路由表项所对应的序号。其中，度量值一般采用跳数，而序号是这个协议引入的重点。每个路由表项的序号并非由存储这个路由表项的节点所分配，而是由这个路由表项所对应的目的节点所分配的。每个节点定期向所有邻居转发自己当前的路由表，同时将序号值增加1。中间节点将收到的每个目的节点的序号与自己路由表中所存储的该节点序号进行比较。
路由序号的大小说明了该路由表项的新旧（即产生的时间），路由序号越大，说明该路由表项越新。如果收到的路由表项比原有对应表项新，则删除原有的旧路由表项。具体来说，如果收到的路由序号大于所存储的序号，则说明收到的信息为最新路由信息，所以选择发送该信息的节点作为下一跳节点，并且将所存储的路由序号更新为所收到的序号；如果收到的路由序号等于所存储的序号，但度量值较少，则该中间节点同样需要更新自己的路由表。
例如，假设节点A从节点B接收到路由信息，该路由信息涉及到达节点C的路由；假设S（A）代表存储在节点A中的节点C的目的序号，而S（B）代表由节点B发送到节点A的节点C的目的序号。DSDV协议的主要思想就是，如果S（A）>S（B），那么节点A放弃从节点B接收到的路由信息；如果S（A）=S（B），并且通过节点B的度量值低于节点A所存储的路由的度量值，那么节点A将节点B设为到达节点C的下一跳节点；如果S（A）<S（B），那么节点A将节点B设为到达节点C的下一跳节点，并且将S（A）更新为S（B）。
在移动自组织网络拓扑结构动态变化的情况下，为了使路由表的记载与实际网络状况相符，每个节点会定期向邻居节点传送更新消息。每个节点经过固定的时间间隔后，或者当拓扑结构发生改变时，通过广播或者多播的方式向网络上的其他节点发布路由信息。
节点保存每个特定目的节点最早路由到达时间和最优路由到达时间之间的时间差 t ，将路由信息的广播时间延迟长度为 t 的一段时间，从而避免路由表的频繁更新。另外，DSDV协议给出两种更新消息的格式，一种是完全更新格式，用于传输节点当前路由表的所有表项，仅在节点频繁移动的情况下使用；另一种是增量更新格式，用于传输上一次完全更新消息传送之后发生了变化的表项。
本地计算用于在协议交互的基础上选择合适的路径，因此需要建立选择的标准。本地计算的基本参数选择包括：序号较大（表示该路由信息的有效性高）和量度值较小（表示路由优化好）。因此，本地计算可以优先选择序号较大的路由进行数据转发，当多个路径具有相同序号时，则选择其中具有最低量度值的路径。当协议交互过程探测到链路中断时，该中断链路的量度值被定义为∞。当通往下一跳的链路中断时，通过该下一跳的任何路由的量度值被定义为∞，并且被指定一个更新的序号。度量值为∞的表项变化会立即触发增量更新格式的更新消息。
每个节点在完成上述本地计算后，需要将自己所获得的路由信息转发给其他邻居节点。因为各个节点的路由信息广播并不同步，所以可能出现路由表项频繁波动的情况。为了解决该问题，本协议维护两张表：转发表和广播表。广播表具有“平均广播时间间隔”的表项，该表项的值是过去广播时间间隔的加权平均。当需要向邻居节点发送网络信息广播时，节点首先查询广播表的“平均广播时间间隔”表项，如果超过了该表项所对应的时间间隔，则进行转发。
DSDV协议的优点在于节点通过所维护的路由表，能够高效地转发数据。此外，DSDV协议在原有距离向量协议的基础上，引入了路由序号，较好地避免了分布式路由中节点不同步而导致的路由回路问题。DSDV协议的缺点在于算法收敛速度慢，不适用于快速动态变化的移动自组织网络，并且效率较低。
2.无线路由协议WRP
由于DSDV协议不适用于快速动态变化的移动自组织网络并且效率较低，因此Shree等学者提出无线路由协议（Wireless Routing Protocol，WRP） [29] ，它是一种基于距离向量的分布式表驱动路由技术。每个移动节点维护以下四个表：距离表、路由表、链路成本表和消息重发表。移动节点使用更新（UPDATE）消息在相邻节点之间通知链路状态，该节点通过接收应答消息或者其他消息确定其邻居节点的存在。如果没有更新消息需要发送，则需要定期发送HELLO消息。在通过上述方式得知链路状态之后，移动节点先根据邻居节点的最短路径生成树，生成自己的最短路径生成树，再向邻居节点发送更新信息，从而实现路由选择。WRP在计算路径时，规定每一节点检查所有相邻节点所发送的路由信息，从而避免无穷计算（count-to-infinity）问题并减少路由环路。
如果在一定时间间隔内，没有接收到邻居节点的任何消息，则可以确定发送消息的节点与该邻居节点之间的链路出现故障，或者两节点的移动导致其间的链路不可用。如果在一定时间间隔内，收到新的邻居节点发送的消息，则能够确定该节点可以与该邻居节点建立链路，并且该节点需要将自己的路由表通知该邻居节点，该邻居节点据此更新自己的路由表。
3.簇头网关交换路由协议CGSR
DSDV协议和WRP的缺陷在于仅仅适用于平面网络，网络中每个节点的路由功能完全相同，但随着网络规模的扩大，节点数量增加和节点移动性增强，路由维护过程中需要发送的消息越来越多，增加了各个节点的计算负担和存储负担。为了解决该问题，Chiang等学者进一步提出基于距离向量的层次路由技术簇头网关交换路由（Cluster-head Gateway Switch Routing，CGSR）协议 [30] 。
为了解决大规模移动自组织网络中的上述问题，CGSR协议中提出了分簇的思想，将移动节点划分为多个簇，在每个簇内选出簇头节点。由簇头节点负责簇内节点的管理，这些簇头节点组成更高层次的虚拟骨干网，实现网络的层次化管理。需要指出的是，该思想与互联网的骨干网思想不同，因为互联网的骨干网是静态的，而移动自组织网络的骨干网随着拓扑结构的变化而动态改变，其层次结构不固定。也就是说，移动自组织网络的层次路由需要实现动态分簇和簇头选择，动态地确定连接各个簇的网关节点，并且需要建立适宜的簇头更换机制以避免节点充当簇头的时间过长所导致的能量耗尽。
基于上述思想，CGSR协议在DSDV协议的基础上，增加了分层机制。CGSR协议的协议交互和本地计算操作与DSDV协议的相应操作基本相同，下面主要对CSGR协议的特殊之处进行介绍。
节点维护分层成员表和路由表，其路由表的结构与DSDV协议路由表的结构基本相同，分层成员表描述了所有移动节点所在层次的簇头。移动节点使用与DSDV协议交互机制周期性地与邻居节点交换分层成员表，并且更新分层成员表的内容。
当一个节点需要将消息传送到目的节点时，源节点首先将该消息传送到它所在簇的簇头，簇头将该消息传送到相应的网关节点，该网关节点将该簇头与其他簇头连接，并且将消息传送到下一个簇头，直到将该消息传送到目的节点所在的簇头，该簇头将消息传送到目的节点为止。当两个簇头节点距离较近时，只需要一个簇头节点就可以管理该区域的移动节点；或者当一个节点移动到无法与所有簇头节点通信时，则重新选择簇头。当节点的移动使得分层结构被破坏时，使用分层维护算法重新构造分层结构。该算法将邻居数较多的节点以及该节点的邻居保留在当前簇内，同时对其他节点进行调整。
如图3-5所示，当源节点S需要向目的节点D发送数据包时，它首先将路由消息传送到簇头A，簇头A查找簇成员列表，如果目的节点D不在簇成员列表中，则将该消息转送给网关C，由网关C转送给另一个簇头B，直到传送到目的节点D为止。可见，CGSR协议采用了分层查找机制，在网络规模较大时，能够防止大量路由消息的洪泛。但是，该协议的设计实现较为复杂，需要动态地进行簇划分和簇头选取，移动节点也需要定期向簇头发送位置信息。
图3-5 CGSR协议示例
4.优化链路状态路由协议OLSR
为了降低节点之间的通信负担，Clausen等学者基于多点中继站的思想提出了优化链路状态路由（Optimized Link State Routing，OLSR）协议 [31] 。与上述基于距离向量的DSDV或CGSR协议不同，OLSR协议是一种基于链路状态的表驱动协议。该协议建立在链路状态路由（LSR）协议的基础上。链路状态路由协议能够较好地实现路由选择，但是所采用的洪泛机制增加了节点的计算负担和网络的通信负担。在移动自组织网络中，链路状态的不断变化而造成的洪泛则进一步加剧了上述问题。
为了避免链路状态在网络中大规模洪泛，特别是相同的链路状态信息被多个节点冗余重复传输的情况，OLSR协议首先在网络上选取少量的特殊节点（称为多点中继站）。在链路状态洪泛时，OLSR协议规定只有选择出的多点中继站才能向邻居节点洪泛链路状态信息，其他节点不参与链路状态信息的洪泛，从而大幅度减少了将一条消息洪泛到整个网络所需的转发次数，减轻了传统洪泛机制中所有节点参与消息转发所带来的负担。
节点通过周期性地发送HELLO消息实现链路状态的探测，并且从链路探测所交换的消息中获得邻居节点的信息。节点基于从HELLO消息中获取的信息选择多点中继站，该多点中继站用于在网络中广播和转发拓扑控制信息。也就是说，协议交互过程借助HELLO消息实现如下功能：探测链路、探测相邻节点和选择多点中继站。
在链路探测过程中，每个节点从两个方向探测各个相邻节点之间的各条链路，确定该链路属于对称状态或者非对称状态。对称状态是指相邻节点之间的链路是双向链路，可以从两个方向发送数据。非对称状态是指相邻节点能够接收到该节点发送的数据，但是无法确定该节点是否接收到相邻节点发送的数据。在多点中继站的选择过程中，每个节点在自己的对称一跳相邻区域确定多点中继站集合。
下面以图3-6为例进一步说明OLSR协议。在该示例中，节点C和节点E是节点A的多点中继站。当节点A的链路状态信息发生变化时，节点B、C、D、E、F均收到了节点A产生的链路状态信息，但只有节点C和节点E可以作为多点中继站转发从节点A接收到的链路状态信息，从而避免了节点A的其他邻居节点B、D、F进行广播所造成的节点计算负担和网络传送负担。
图3-6 OLSR协议示例
为了减轻所有节点的计算负担，Ying等学者进一步提出了分层次的优化链路状态路由协议HOLSR [32] 。该协议充分利用各个节点的不同能力，动态地将节点组织到簇中，并且簇以层次化的方式组织起来，从而减少需要交换的拓扑控制信息。在簇间，使用OLSR协议进行路由选择。但是，与OLSR协议一样，该协议需要定期更新。
OLSR协议采用优化的洪泛机制作为消息的传送机制。而且，该协议将所有数据采用统一的分组消息格式封装成一条或者多条消息。多点中继站将消息在网络中的重传次数降低到最低程度。由于OLSR协议中只有多点中继站节点参与路由计算，减轻了其他节点的计算负担，因此它适合规模较大、节点密度较高的移动自组织网络。
5.多信道表驱动路由协议
为了充分利用无线传输的特性来提高移动自组织网络的吞吐量，Unghee等学者提出了多信道的DSDV路由协议DSDV-MC [33] 和多信道的OLSR路由协议OLSR-MC [34] 。其中，信道是指两个系统间发送数据的管道，是不同系统的应用程序和过程之间的逻辑链接。DSDV-MC和OLSR-MC将网络层划分为控制平面与数据平面，节点使用一个控制频道传送路由更新信息，使用一个或者多个数据频道传送数据包，实现了多个消息传送操作的同步进行，降低了网络负担，但是频道资源的管理和协调难度较大，并且节点的计算负担较大。
上述表驱动路由技术使用路由表维护网络中从一个节点到其他节点的所有路由信息，因此能够实现快速路由。但是，维护路由表不但增加了节点的存储负担，而且在移动性强的网络中需要不断地交互路由信息，大大增加了节点的路由信息交互负担和计算负担。因此，学者们提出了按需路由协议。该类协议在数据分组要发送时才进行具有针对性的路由交互或路由计算。由于节点无须事先维护全局路由信息表，因此这类路由协议也被称为在线计算路由协议。
上文提到过，移动自组织网络具有高度动态性，网络的拓扑结构不断改变，消息传送具有一定困难。较为简单的消息传送方法是洪泛，然而洪泛过程中，很多节点不必要地参加了消息的转发，增加了节点的计算负担和网络的传送负担。特别是对于由大量分组组成的长时间数据流，如果每个分组都采用洪泛的方式传输，将导致网络传输效率很低。
为了解决上述问题，人们提出了控制消息（路由）与数据传输相分离的思想，仅对控制消息采用洪泛的方式，以确定数据传输的路由。在后续的数据传输过程中，则根据已经确定的路由进行数据转发。对于按需路由协议，通常来说，源节点采用洪泛操作向相邻节点发送路由请求消息，中间节点将转发上述消息的全部或者部分，直到目的节点收到该请求消息为止。然后，目的节点选择合适的路径并且反向转发路由应答消息。当源节点接收到应答消息之后，路由得以建立。常见的按需路由协议有DSR、AODV、TORA、ABR等。
1.动态源路由协议DSR
动态源路由（Dynamic Source Routing，DSR）协议作为一种源路由技术，是最早设计的按需路由协议之一 [35] 。当一个移动节点需要发送新的数据流时，该节点为该数据流的目的地寻找相应的路径。基于路由过程所找到的路径，在数据分组流传送过程中，每个分组的分组头中都包含从源节点到目的节点的完整路由信息，以便路径当中每个节点根据分组所携带的路由信息转发分组。在DSR协议中，由于由源节点获知完整的路径信息并将该信息记录在每个分组的分组头上，网络中间节点不需要维护任何路由信息，因此该协议被称为源路由协议。
该路由过程包括洪泛路由请求（RREQ）报文和回传路由响应（RREP）报文两部分。当节点需要发送数据消息时，首先会动态地广播路由请求RREQ消息。该消息包含目的节点、发送节点地址、消息ID和路由记录。其中，发送节点地址和消息ID共同用于标识RREQ消息。当某节点接收到该消息之后，需要判断该消息是否存储在历史RREQ消息列表之中，如果存储在其中，则丢弃该消息；如果未存储在其中，则需要判断自己是否为目的节点。如果自己并非目的节点，则将本节点添加到路由记录中，并且将该消息向自己的邻居节点进行广播。
由于路由请求报文RREQ在网络中洪泛时，每个节点都将自己的地址增加到数据报文的路由记录中并继续转发该数据报文，因此，当路由请求到达目的节点时，目的节点根据该路由请求报文中的节点列表，就知道了从源节点到达该目的节点的路径。于是，目的节点产生路由响应消息RREP，并将该消息回送到源节点，从而源节点得到完整的路由信息。
在节点之间的可达性维护上，DSR协议不再使用周期性广播这种耗费资源的方式，而是通过节点动态监测可用路由的方式实现路由维护。该协议路由维护的方式包括三种：逐跳验证方式、非逐跳验证方式和端到端验证方式。逐跳验证方式是指，借助于相邻节点之间的MAC子层验证机制，当链路发生故障时，由MAC层发出通告，该节点向前一跳节点发送路由错误消息RERR，收到该消息的节点从路由表中将该路由删除。非逐跳验证方式是指，当节点A将消息转发到下一跳节点B时，节点B到其邻居节点C的消息转发可以被节点A监听到，节点A根据该监听到的消息进行验证。端对端验证方式有TCP下的确认机制等。
为了提高该协议的效率，学术界提出了路由缓冲机制。移动自组织网络节点处于监听状态，节点可以监听邻居节点发出的消息，根据这些消息中记载的路由信息，可以尽量避免每次发送新消息时都启动协议交互过程，从而提高网络的性能。
下面以图3-7中节点S到节点D的路由为例，说明DSR协议的工作过程。首先，节点S以广播的形式向邻居节点广播路由请求消息RREQ。该消息包含目的节点、请求发送该消息的节点地址、消息ID和路由记录。
节点S首先向邻居节点A、C、F广播消息，节点在接收到RREQ消息时，需要判断该消息是否存储在历史RREQ消息列表之中，如果存储在其中，则丢弃该消息，如果未存储在其中并且不是目的节点，则进行消息转发，如节点A向节点J、E转发该消息，而节点C发现该消息已经存储在历史RREQ消息列表之中，所以丢弃该消息。如图3-8所示，节点E接收到该消息之后，进一步以广播的形式进行转发。重复上述操作，直到目的节点收到该消息为止。接着，目的节点D生成路由响应消息RREP，并且将该消息向自己的邻居节点进行广播。当RREP消息被传送到源节点S时，路由得以建立。
图3-7 DSR协议示例1
图3-8 DSR协议示例2
与表驱动路由协议相比，DSR协议能够较好地适应节点的移动性和网络拓扑结构的动态变化，不需要维护路由表来不断交互路由更新消息，节省了网络资源。然而，DSR协议使用源路由方式，在网络规模较大时，分组头中所携带的路径信息将引入较大的传输开销。
2.自组织按需距离向量路由协议AODV
为了解决DSR协议存在的源路由分组头携带路径信息而开销较大的问题，Perkins等学者在DSR协议和DSDV协议的基础上提出了自组织按需距离向量路由（Ad hoc On-demand Distance Vector，AODV）协议 [36] 。AODV协议采用了DSR协议的交互机制，保持了DSDV协议的逐跳路由、顺序号和周期性更新等机制。
每个节点维护路由表，该表以目的节点作为关键字，每个表项指出将消息传送到哪个下一跳节点能够到达目的节点。与表驱动路由协议不同，AODV协议中每个节点仅维护当前使用的路由表项。当源节点需要向目的节点发送数据时，如果源节点发现其路由表中没有到达目的节点的路由，则通过路由协议交互机制建立路径；反之，按照路由表中记载的路由进行数据传输。因此，该协议是节点维护路由表的按需路由协议。
源节点广播RREQ消息，该消息的格式如图3-9所示。当RREQ消息到达中间节点时，中间节点在本地的历史表中查找（源地址、请求ID），以确定是否处理过该请求。如果处理过该请求，则丢弃该消息。如果没有处理过该请求，则将它写入历史表，并且在接收节点的路由表中查找通向目的节点的路由。
图3-9 RREQ消息的格式
如果查到较新的通向目的节点的路径，即路由表中的目标序号大于或等于RREQ消息中目的节点的序号，则给源节点返回RREP消息。如果没有查到较新的通向目的节点的路径，则增加跳数并且广播RREQ消息。目的节点接收到该消息后，向源节点返回RREP消息。RREP消息的格式如图3-10所示。该协议路由表项的结构与DSDV协议类似，主要包括源地址、目的地址、目标序号、跳数和生命周期。
图3-10 RREP消息的格式
下面以图3-11中节点N1到节点N8的路由为例，进一步说明AODV协议。源节点N1广播路由请求数据包，该数据包被邻居节点转发，该协议使用顺序号以保证不会形成环路。路由请求消息RREQ到达目的节点N8之后，目的节点N8向源节点N1返回路由响应消息RREP，路由得以建立，并且该路由表项将分别存储在源节点、中间节点和目的节点的路由表中。
图3-11 AODV协议示例
AODV协议结合了表驱动路由协议和按需路由协议的优点，不但路由维护信息少，而且实现了较高的转发效率。
3.临时排序路由算法协议TORA
为了提高路由效率，Park等学者在有向无环图算法的基础上提出了临时排序路由算法（Temporally Ordered Routing Algorithm，TORA）协议 [37] 。该协议采用势能值确定朝向目的节点的有向无环图，在路由响应消息回到源节点的过程中使用势能值确定路由。
首先，源节点在网络中广播路由请求消息。此时，每个节点具有一个相对于源节点的“势能值”，源节点的势能值最高，目的节点的势能值最低。其次，根据相邻节点之间的势能值的大小，形成一条或者多条有向路径，方向是从势能大的节点指向势能小的节点。也就是说，当节点需要查找到达特定目的节点的路径时，广播含有目的节点地址的路由请求消息。接收到该消息的节点进一步广播该消息，并且列出其到目的节点的势能值。接收节点将消息传送到势能值更低的节点，从而形成方向性路由。当节点发现链路不可用时，则将其势能值调整为比邻居节点大的值，并发送更新消息。
如图3-12所示，节点被设定势能值，图中以节点的纵轴高度表示其势能值，在协议交互过程中，数据消息从高势能的源节点向低势能的目的节点移动。
图3-12 TORA协议示例
TORA协议能够发现到达目的节点的多个可用链路，并且网络的通信负担较轻，无须时刻维护节点之间的链路状态。但是，节点的计算负担较重。
4.基于关联性的路由协议ABR
上述路由协议普遍采用跳数作为本地计算的依据，以最短跳数路径作为路由选择的标准。但是，并非最短路径就是消息传送的最优路径。在无线网络中，节点间的通信都采用无线信道，稳定性是路由选择的重要考虑因素，特别是移动自组织网络具有高度动态性，路由的稳定情况经常变化，甚至最短路径也会经常变化。为此，Toh等学者提出了基于关联性的路由（Associativity-Based Routing，ABR）协议 [38] 。该协议在路由选择标准方面与上述协议不同，它以路由的生命周期作为路由选择的标准。
该协议引入“关联性”的概念，用于描述移动节点与邻居节点之间空间和时间上的连接关系。所有节点定期发送信标消息BEACON，以广播该节点的存在性以及该节点的相关信息。所有节点根据邻居节点发来的信标消息BEACON，衡量邻居节点与自己的关联性。当关联性较小时，表明该邻居节点具有较高的移动性；当关联性较大时，表明该邻居节点具有较低的移动性。关联性较大的节点所在的路由的稳定性较高。ABR协议将路由的生命周期、中间节点的计算负担和通信负担、链路容量作为路由选择的标准，能够选择适合的路由。
表驱动路由技术通过维护路由表实现快速路由，但增加了节点的路由交互和计算负担。按需路由技术仅在源节点需要的时候才进行协议交互，节点无须维护路由信息表，但是路由建立的时延较长。可见，在移动自组织网络中，单纯采用表驱动路由协议或按需路由协议都难以实现高效且高速的路由。因此，学者结合上述两种协议的优点，提出了混合路由协议。
1.区域路由协议ZRP
区域路由协议（Zone Routing Protocol，ZRP） [39] 是最早实现混合式路由技术的协议，所有节点都有一个以自己为中心的重叠虚拟区域，该协议设定以跳数为单位的区域半径，所有距离不超过该区域半径的节点都属于该区域。区域内的节点数与设定的区域半径有关，在区域内使用表驱动路由算法，在区域间则使用按需驱动路由算法进行路由选择。
协议交互过程包括两个部分，区域内协议交互和区域间协议交互。区域内协议交互可以采用基于距离向量的路由或者基于链路状态的路由。不管采用何种路由协议，要求各个节点都能够知道到达区域内部其他节点的路由。区域间协议交互是指某区域的节点与区域外的节点之间的协议交互，类似于DSR协议的广播机制，主要采用广播路由请求消息的方式实现。
具体来说，源节点首先检测目的节点是否在自己所在的区域内。如果在该区域内，那么直接获取到达目的节点的路由。如果不在该区域内，那么源节点将路由请求消息传送到其位于该区域边界的边界节点。边界节点检测目的节点是否在该节点的区域范围内，重复上述过程，直到最终找到目的节点，并且回复路由响应消息。
基于相同的思想，Dai等学者提出先应式路由维护机制 [40] ，该机制将按需路由协议的协议交互技术和表驱动路由协议的路由维护技术结合，从而实现高速路由。由于该类协议中拓扑结构的更新一般在较小的区域范围内进行，所以有效地减轻了网络的传送负担和节点的计算负担，同时加快了路由选择的计算速度。但是，该协议的性能取决于区域半径。在区域半径过大的情况下，路由表维护的代价较高；在区域半径过小的情况下，路由选择的速度较慢。目前，该协议采用预先设定的固定区域半径，效率较低。如何选择合适的区域半径是值得深入研究的问题。
2.LANMAR协议
为了解决ZRP协议预设区域半径所导致的效率低下的问题，Pei等学者提出了基于链路状态和距离向量的混合的路标路由（Landmark Routing，LANMAR）协议 [41] 。该协议按照移动节点的功能和需要，将移动自组织网络划分为多个逻辑子网。由于具有相同功能和需求的节点通常一起移动，因此往往将这些节点划分在一个逻辑子网中。例如战场的移动自组织网络中，将一个班的战士划分为一个逻辑子网。再在每个逻辑子网中选出一个用于在全网范围内进行路由的路标节点。
每个节点维护两个路由：逻辑子网内的链路状态路由和到达所有路标节点的距离向量路由。当源节点向目的节点发送消息时，如果该源节点和目的节点同属于相同的逻辑子网，则根据链路状态信息进行数据转发；如果该源节点和目的节点属于不同的逻辑子网，则根据该源节点存储的距离向量发送消息。
如图3-13所示，节点A、B、C属于路标为节点B的逻辑子网，节点D、E、F、G属于路标为节点G的逻辑子网。每个节点维护着所有路标节点的距离向量路由。如果节点A要向节点C发送数据消息，则由于节点A和节点C属于相同的逻辑子网，因此节点A只需要根据可用的链路状态信息确定到达节点C的路由。
图3-13 LANMAR协议示例
如果节点A要向节点F发送数据消息，那么，由于节点A和节点F属于不同的逻辑子网，因此节点A需要根据它维护的到达路标节点G的距离向量路由进行消息传送。当消息到达节点D时，由于节点D和节点F属于相同的逻辑子网，因此节点D只需要根据可用的链路状态信息确定到达节点F的路由。可见，从源节点A到目的节点F的路由过程中，开始时，源节点A朝着路标节点G进行消息转发，最终该消息可能并不通过路标节点G就能到达目的节点F。
LANMAR协议按照移动节点的功能和需要将移动自组织网络划分为多个逻辑子网，在一定程度上解决了ZRP协议预设区域半径所导致的效率低下问题。但是，该协议需要进一步研究路标节点的选择算法和孤立节点的处理算法，因此该协议适用于节点比较密集的移动自组织网络。
路由选择算法是为了实现上述路由功能而设计的计算方法，负责确定所收到的消息分组应当传送的路径。也就是说，路由选择算法是在路由协议交互的基础上进行本地路由计算，选出最优的路径。路由选择算法是网络层的核心部分，该算法的任务在于确定可用路由，然后根据一定的路由选择标准，采用适合的选择策略选择最优路由。
路由选择算法的输入为网络的拓扑结构，输出为最优路由。移动自组织网络路由选择算法的基本功能与互联网路由选择算法相同。但是，移动自组织网络的拓扑结构和节点位置是动态变化的，节点能量有限，不存在路由器等设备，使得其路由选择算法具有特殊性。近年来，国内外学者在这方面进行了深入研究并取得了大量研究成果。
在DSDV、AODV等路由协议中，协议交互均采用洪泛机制，往往需要将路由消息进行无谓的多次复制传输，具有较高的时间和带宽代价。为此，Yuval等学者提出了基于随机最短路径路由技术的“流言”（gossip）机制 [42] 。该技术是基于扩散理论的，源节点以概率1广播一个消息。当一个中间节点第一次接收到该消息时，它以概率 p 将该消息广播到邻居节点，以概率1 -p 丢弃该消息；若中间节点接收到重复的消息，则它丢弃重复的消息。Yuval等学者认为，通过邻居节点的流言，节点能够获知动态网络的状态信息，从而选择到达目的节点的最短路径。该机制减轻了由洪泛机制导致的数据传送负担，但是滞后性较强。
为了降低“流言”机制的滞后性，Christopher等学者提出了随机路由技术 [43] ，即使用基于概率的本地广播传送模型传送消息，并且基于中间节点的反馈进行路由选择。该技术有利于降低“流言”机制的滞后性，但是路由查找的效率较低。
为了提高路由查找的效率，Haas等学者进一步优化了基于“流言”的Ad Hoc路由技术 [44] 。在对网络动态性要求较低的操作中，“流言”很快被注销，从而很少的节点能够接收到该消息；在对网络动态性要求较高的操作中，“流言”涉及的关键节点接收该消息。上述操作的区分依赖于“流言”可能性和网络的拓扑结构。该技术降低了洪泛机制所造成的时间和带宽代价，但是，由于消息的转发以一定概率进行，因此可能出现转发失效的情况。
在路由选择标准和选择策略方面，DSR和AODV协议中的路由选择均采用跳数作为路由选择的标准，还有学者对其他路由选择的标准进行了研究，如TORA协议将势能值作为路由选择的标准，但是该协议主要考虑转送节点的能量，没有考虑路由本身的稳定程度。ABR协议采用关联性的概念来标识节点以及相应链路在时间和空间上的稳定程度，借助关联性的比较进行路由选择，能够较为准确地反映路由的稳定性。此外，Baruch等学者提出了基于吞吐量的路由选择算法 [45] ，该算法将吞吐量作为路由选择的标准，以期实现网络的负载均衡。该算法能够为服务质量保证提供支持，但是时间代价较高。
为了降低时间代价，三菱电子研究所提出简化的路由选择标准 [46] 。当源节点广播RREQ消息时，接收到该消息的邻居节点首先向源节点发送PING数据包，借助该数据包，可以验证两个节点之间通信信道的完整性。如果该通信信道的完整性较差，则不选择该路由。该方法实现方便，但加重了节点的通信负担。
在选择策略方面，DSDV和AODV协议等选择的策略过于简单。为了解决该问题，Zhong等学者提出移动自组织网络的协作优化路由转发协议Corsac [47] 。该协议采用VCG（Vickrey-Clark-Groves）算法，在加密技术的基础上使得链路的成本由两个节点共同确定，从而加强路由的选择。该协议提供了使用两个节点描述链路成本的思路。
为了进一步描述链路的成本，Du等学者提出了多类别路由 [48] 。首先选择能量较高的节点作为骨干节点B-node，能量较低的节点作为普通节点G-node，由骨干节点承受较多的路由负担。该技术能够实现快速路由，但是各个节点的负载不均衡。为了综合实现以达到负载均衡，并且降低节点的移动距离，Wu等学者提出了基于对数的存储—承载—转发路由技术 [49] ，首先设计节点运动的轨迹和集结点，然后调度消息的传送方式，并且在移动过程中进行节点的重新区分。该技术仍然存在对链路的情况描述不精确的问题。
为了更精确地描述链路状态，日立公司提出了基于链路状态源路由的稳定路由选择算法 [50] 。该算法根据物理层测定的电波强度、信噪比、误比特率确定链路状态值，然后判断该链路状态值是否超过设定的阈值，从而进行路由选择。西门子公司则提出了将路由向量作为路由选择标准的思路 [51] ，由节点计算路由向量，当路由向量在阈值范围之外时，放弃该待选路由。上述技术能够较为精确地描述链路状态，但是节点间的计算负担较重，并且路由操作需要使用大量物理层获得的信息。
上述选择策略没有考虑不同移动自组织网络的不同特性。为此，Du等学者提出了适应性单元延迟路由协议 [52] ，该协议包括：针对稠密网络的单元延迟路由机制CR，针对稀疏网络的大单元路由机制LC，节点稠密程度的变化检测，以及节点稠密程度变化时更改路由策略的机制。CR机制采用面向能耗的按需路由选择算法，使用能量较高的节点执行路由和包转发操作，并且在选中的单元内以洪泛的形式进行路由选择。在稀疏网络的LC机制中，主要考虑如何保证数据包的传送，其次才需要考虑减轻路由负担的问题。当活动节点的数目或者路由的区域改变时，稠密度改变的消息传送到适应性簇头（AH）中，从而适应地改变路由策略。该协议充分考虑了不同移动自组织网络的不同特性，并且区分了稠密网络和稀疏网络，但是稠密度计算的时间代价较高，并且需要大量洪泛操作。
在Du等学者研究的基础上，为了降低时间复杂度，Zhao等学者针对稀疏移动自组织网络提出了基于Hop ID的虚拟协作路由技术 [53] ，从而基于Hop ID平均值的大小选择路由。Hop ID是标识节点与预定路标节点之间相对位置的距离向量，如图3-14中某节点的Hop ID（图中数字）是指该节点分别与路标节点L1、L2和L3的距离。该技术仅适用于稀疏网络，时间复杂度较低。
由于基于Hop ID的虚拟协作路由技术主要针对小规模的稀疏网络，因此，Luke等学者针对大规模移动自组织网络提出了簇覆盖广播技术 [54] 。当源节点传送数据时，首先与簇头交互，簇头将路由请求在所有由簇头构成的覆盖网络上广播。该请求首先向一跳邻居节点广播，如果没有收到回复消息，则依次向二跳、三跳邻居节点等广播。虽然该技术降低了计算的时间复杂度和减轻了广播负担，但簇头节点的计算负担和转送负担较大，同时大大增加了路由失败时的延时。
图3-14 Hop ID示例
为了减轻大规模移动自组织网络的路由计算负担，Jakob等学者提出了对节点动态编址的方法 [55] 。该方法基于节点的位置关系对节点动态编码，根据该编码进行下一跳节点的查找。虽然该技术减轻了洪泛造成的负担，但是需要占用节点的存储空间并带来一定的传送延迟。有些特定应用需要尽量降低传送延迟并且提供并发性支持，为此，Mao等学者针对并发视频会话的要求提出了基于遗传算法的路由技术 [56] 。该技术针对每条路径进行基因编码，然后进行遗传和变异操作，最终获得适合的路由。该方法中节点的计算负担较重。
上述技术没有充分考虑拥塞控制的问题，于是Tran D.A.等学者提出了拥塞适应性路由技术 [57] 。当节点探测到将要发生拥塞时，该节点会通知前一个节点使用其他路由绕过拥塞区域。下面给出连接路由协议（Connected Routing Protocol，CRP）示例。对于图3-15a，当节点C探测到拥塞（见图3-15b）时，通知其前一个节点B，由该节点选择通过节点W的另外一条路径，分别以概率 p 和1 -p 在上述两条路径上传送数据。当节点B发生拥塞时，如图3-15c所示，选择通过节点X的路径，分别以概率 q 和1 -q 在两条路径上传送。可见，该技术不但可以判断网络的拥塞状态，而且可基于网络的拥塞状态进行自适应改变。该技术适用于具有较重传送负担的大规模传送移动自组织网络，如传送多媒体数据的移动自组织网络，能够降低包丢失率和延迟。但是，需要节点具有拥塞探测能力，计算负担较重。
图3-15 CRP协议示例
综上所述，在移动自组织网络的基本路由选择算法中，协议交互中的洪泛操作带来了较重的数据传送负担和节点计算负担，并且仅仅以跳数作为路由选择的标准无法选择出最优路由。因此，如何降低洪泛操作带来的负担以及如何设计更为全面的路由选择标准，是研究较为集中的领域。此外，区分稀疏网络和稠密网络并分别设计路由选择策略也是一个很好的思路。在洪泛操作的优化方面，“流言”机制与概率模型的结合提供了很好的研究思路，在此基础上，学者提出了基于预测的路由选择算法。
由于移动自组织网络的动态性很强，路由失效和路由更新非常频繁，因此，路由选择算法的重要问题在于如何提高路由更新性能。学者对路由算法中的路由更新技术做了很多研究。路由更新主要分为全局更新、局部更新、事件驱动更新、基于移动的更新和移动预测更新等。
在全局更新中，每个节点定期与其他节点交换路由表，如DSDV协议采用了定期更新技术。显然，全局更新的更新代价非常高。
局部更新技术将路由更新信息的传播局限在一定区域之内。例如，在Jacquet等学者提出的FSR协议 [31] 中，以较高的频率更新较近区域中节点的路由表。FSR协议采用如图3-16所示的“鱼眼”范围来定义较近区域。其中，“鱼眼”范围是指从中心节点经过特定跳数能够到达的节点范围。该技术的更新代价较低，但准确性不高。
图3-16 FSR协议中的“鱼眼”范围示例
事件驱动更新技术 [58] 的主要思想：如果特定事件发生，那么节点传送更新消息。该技术的更新代价非常低，但是具有一定的滞后性。移动预测更新主要基于对移动的预测进行路由更新，而采用该更新技术的路由选择算法被称为基于预测的路由选择算法。其更新代价较低，并且具有一定的预测性，因此，近年来学者对它进行了深入研究并取得了大量研究成果。
Basagni等学者提出了基于移动的更新技术DREAM [59] ，以较高的频率更新具有较高运动速度的节点，该技术的更新代价较低，但计算的时间复杂度较高。Mehran等学者在DREAM的基础上，提出最小位移更新路由（MDUR）和最小拓扑改变更新（MTCU） [60] 。在最小位移更新路由中，路由更新依赖于超过阈值的节点的位置改变。最小拓扑改变更新则在最小位移更新路由的基础上，设计了路由更新依赖于网络拓扑结构的改变程度机制。
如图3-17所示，当节点S从位置S i 移动到位置S f 时，节点S的邻居拓扑结构发生改变，从而显著地改变了整个网络的拓扑结构，因此需要在此时发送更新包，网络中的每个节点能够重建路由表并且存储更为准确的路由。如果节点S迅速向节点A移动，但是仍然能够保持与节点B和D的连接，那么节点S的拓扑结构没有改变，网络中无须进行任何更新。在上述方法中，根据拓扑结构改变的情况决定是否更新路由，较大地减小了更新代价，但是，它采用阈值判断更新时机，准确性不高。
为了通过更新预测而减少不必要的路由更新并提供更新的准确性，Jiang等学者提出基于对链路可用性进行预测的可靠路由选择算法 [61] 。首先，在 T p 期间保持节点当前速度不变的情况下，预测链路可用的时间。其次，分析 t 0 （初始时间点）和 t 0 + T p 之间可能的变化，预测该链路保持到时间 t 0 + T p 的概率 L （ T p ），其计算公式为
图3-17 MDUR中的节点位移示例
式（3-1）中，参数 p 难以确定，为了简化，可以将 p 设定为0.5，然后确定 ε 和 λ 的值。 ε 的值由环境因素决定，如节点稠密度、信号范围和空间大小。上述可靠路由选择算法基于节点速度的变化来预测链路的可用时间，能够显著降低路由选择算法带来的更新代价。但是，节点的计算代价和存储代价较高，并且该算法仅仅考虑了链路的可用性，没有考虑延迟和能耗等因素。
为了进一步提高预测更新的准确度，充分考虑延迟和能耗等因素，Guo等学者提出，使用双指数平滑方法与基于链路生存期的启发式算法预测延迟和能耗 [62] 。在每个节点中，路由表基于Dijkstra算法做出修改，集成地评估预测值。双指数平滑方法的主要公式为
S t 是在时间 t +1处的评估值， X t 是在时间 t 处的实际值， α 和 β 是参数。 α 和 β 的确定由Levenberg-Marquardt算法实现。上述方法的更新代价较低，但是节点计算的时间复杂度较高。
为了进一步提高路由更新的效率，Vinh等学者经过实验分析得出，路由更新的时间代价主要集中在数据链路层的队列长度和重新连接的限制上，因此提出了通过适应性重新连接限制以加速队列管理 [63] 。如果重新连接的次数达到重新连接限制，导致具有相同目的MAC地址的数据包被丢弃，那么重新连接的限制被增加1次，直到每个包被重新传送1次为止。该方法降低了节点计算的时间复杂度，但是需要链路层支持，并且会导致资源分配的不公平。
综上所述，学者对基于预测的路由选择算法进行了深入研究，如何降低时间代价并且及时进行路由更新。该问题的关键是建立较好的预测模型，基于节点的历史行为来预测可能的路由变化。移动自组织网络所具有的高动态性使得预测模型的建立存在一定的困难。另外，由于移动自组织网络节点能量有限，因此需要充分考虑预测模型的时间代价和空间代价。
移动自组织网络中的节点能量有限，路由洪泛和路由迂回都会导致不必要的能量消耗，而且基于路由选择的数据转发也会耗费节点的能量。为了避免因节点能量耗尽而导致的网络分割，学者对面向能耗的路由选择算法进行了深入研究并且取得了大量研究成果。
Rodoplu等学者首先提出了面向能耗的路由选择算法 [64] ，在路由计算中结合能耗的情况来考虑节点生命周期，选择生命周期较长的节点作为下一跳。该算法提高了节点的生命周期并且节省了能量，但是没有具体指出如何提高生命周期。在此基础上，Chang等学者提出了基于节点当前的存留能量来最大化网络生命周期，其中考虑了贪婪路由技术的规模和效率对能量消耗的影响 [65] 。Lin等学者则提出了将链路成本定义为节点存留能量的指数函数 [66] 。可见，上述研究关注数据包传送所造成的能耗最小化和能量负担均衡化之间的折中，在一定程度上降低了能量消耗。
为了进一步降低大规模移动自组织网络的能耗，Ahmed提出了移动自组织网络节能事务路由技术TRANSFER [67] 。在该技术中，每个节点使用按需链路状态协议获取 R 跳区域内的节点位置信息，它在无须得知本地信息的情况下按需进行路由选择。如图3-18所示，查询节点Q通过许多边界节点发送查询请求。每个边界节点B i 选择一个联络节点C i 作为在 r 跳内进一步传送查询请求的方向，在到达联络点时，联络点与节点Q之间最多为 R + r 跳，该图中接触节点的数目、 R 和 r 均为3。该技术可降低大规模移动自组织网络的能耗，但是节点的计算负担较大。
图3-18 TRANSFER示例
为了减轻节点的计算负担，Liang等学者提出了虚拟骨干网路由选择算法 [68] 。该算法借鉴ZRP的基本思路，使用虚拟骨干网络降低协议交互产生的能耗和减轻传送负担。通过分布式数据库覆盖启发式算法DDCH（Distributed Database Coverage Heuristic）实现骨干网络中节点的选择和维护。该算法减轻了多数节点的计算负担，但是存在骨干节点计算负担较重的问题。
为了减轻骨干节点的计算负担，Zhao等学者提出了面向能耗的适应性路由技术EAGER [69] 。该技术根据流量情况将网络划分为单元，单元内的节点预计算地维护单元的拓扑结构，单元间的节点实时地维护单元间的拓扑结构，并且将常用节点和常用路由周围的临近单元形成邻居单元，网络的其他部分则保持节能状态。如图3-19所示，阴影部分的单元形成邻居单元，其他单元则处于节能状态。该技术不但可以节省能量，而且能够实现高速路由，但是节点的计算负担较大，并且上述研究没有关注移动自组织网络的空间特性。
为了进一步考虑空间特性，Seung等学者提出了基于节点空间关系的多路径路由技术PBM [70] ，路由通过空间聚簇的会话完成，同一聚簇中的节点集合被称为“空间足迹”。图3-20显示了节点S到节点D的三条不同路由的创建，每条路由以实线形式显示，并且阴影区域是路由中的节点单元，其中箭头标识的节点是簇头。随着延伸程度的提高，阴影单元中的节点对应于会话的空间足迹，从而网络中的通行模式被看成空间足迹的动态集合。该技术基于节点空间关系进行能耗最小化与能量负担均衡之间的权衡，但是计算的时间复杂度较高。
图3-19 EAGER技术下的单元合并
图3-20 PBM技术中的路由建立机制示例
综上所述，由于移动自组织网络节点使用自身带有的电池或者其他易损耗的能源，能量非常有限，因此面向能耗的路由选择算法具有良好的研究前景。该算法的研究重点在于提高节点的生存时间。为此，不仅要考虑路由协议和路由计算本身的能耗，还要重点考虑所选择路径上节点的剩余能量，以及节点在传送单位信息时能量的消耗等因素。
由于移动自组织网络中的节点不断移动，相互的位置关系不断变化，因此获取每个节点的实时位置信息将对了解网络拓扑结构和路由计算提供便利条件。基于位置的路由选择算法通常需要通过全球定位系统（GPS）或者其他定位服务装置获得的节点物理位置信息 [71] ，然后通过上述节点物理位置信息或者节点相对位置关系进行路由计算。每个节点的路由选择由数据包中包含的目的节点位置和转发节点的邻居节点位置决定。该算法无须存储路由表，也无须发送消息来保持路由表的更新，并且支持特定地理区域的数据包传送。
基于位置的路由选择算法需要解决以下两个主要问题：第一，在数据包传送之前，目的节点位置的确定机制，这主要通过位置服务实现；第二，数据包转发机制，这主要基于数据包的目的节点位置和下一跳邻居节点位置确定，其中下一跳邻居节点位置通常通过一跳广播的方式获得。具体转发方式主要包括“流言”转发、严格方向性洪泛和等级化转发。基于位置的路由选择算法的研究主要集中在数据包转发机制上。
为了解决协议交互中的高速转发问题，Fabian等学者提出了基于位置的路由选择算法GOAFR+ [72] 。每个节点使用“流言”机制向邻居节点转发数据包。如果某个节点没有适合的邻居节点，或者数据包到达了网络边缘，“流言”机制难以进一步传播，则该算法使用反馈技术尽快恢复。该算法具有较高的路由效率。
为了减轻网络中的传送负担，Johnson等学者提出了将成功接收数据包的概率定义为两个节点之间距离的对数函数和概率函数的方法 [73] ，在路由计算中计算该概率并将它用于路由选择。该方法减轻了网络传送负担，但节点计算负担较重，在大规模移动自组织网络中尤为明显。为了减轻大规模移动自组织网络的计算负担，Taejoon等学者将位置更新机制与分布式位置服务相结合 [74] ，将优化配置定义为基于位置或者基于时间的位置更新阈值，从而将总体路由代价定义为该阈值的凸函数。该方法在一定程度上减轻了节点的计算负担，但是没有考虑丢包率、延迟和能耗等因素。
此外，Lee等学者提出了高效的位置路由选择算法 [75] 。该算法使用链路矩阵（NADV）选择邻居节点，并选择负担较轻并且跳数较少的路径，而非仅仅选择最短的路径。它使用MAC子层上的无线集成子层扩展（WISE）计算链路成本，如图3-21所示。它基于探测消息信噪比、邻居监测、自监测等方法计算丢包率，基于丢包率、延迟和能耗最终选择最优路径。
上述三种技术充分考虑了移动自组织网络中的数据传送负担，但是计算的时间复杂度较高。与此同时，这些技术需要有类似GPS等设备提供的定位信息。为此，一些学者提出了不使用位置信息，而使用节点之间的相对位置关系的方法 [76] 。
图3-21 无线集成子层扩展
综上所述，基于位置的路由选择算法根据数据包中包含的目的节点位置和转发节点的邻居节点位置进行路由选择，节点通常需要装配GPS或者其他定位服务装置。该算法的研究集中在高速转发和路由选取机制的实现上，尤其是选用时间复杂度较低的数学模型来描述路由，然后根据该数学模型的描述进行路由选择。