基于路径收集的Ad Hoc网络按需路由协议的建立和维护方法

摘要

本发明公开了一种基于路径收集的Ad Hoc网络按需路由协议的建立和维护方法，包括：建立基于链路不相交多路径算法的多条路径；记录每条路径中整条路径的有序节点ID，利用下游节点发送标识的无环机制达到路由无环；在多条路径中选择时，优先选择最新建立的路径；只维护使用过的路径。本发明能够提高路由发现效率，减少路由开销；能够提高通信路径的稳定性，减少节点运动导致通信路径断裂的影响；能够提高获取路由信息的能力。

说明书

技术领域

    本发明涉及网络路由协议，具体涉及一种基于路径收集的Ad Hoc网络按需路由协议的建立和维护方法。

背景技术

Ad Hoc网络是由许多带有无线收发装置的通信终端组成，无需现有基础设施、可动态重构的自治网络，具有建立快捷、灵活、抗毁性强等优点，适用于战场、救灾、环境监测等领域，具有广阔的发展前景。然而Ad Hoc网络在具有上述优点的同时，高度动态、能量有限、无线带宽低下等特点也给Ad Hoc路由协议的设计提出了巨大的挑战。Ad Hoc网络中按需路由协议存在“广播风暴”以及由节点移动造成的通信路径中断的问题。不加限制的泛洪广播引起大量的冗余分组转发，浪费了宝贵的无线带宽资源和节点有限的能量，同时还加剧了无线信道竞争访问、信号冲突的概率，进一步地增加了数据通信时延。由节点移动导致的通信路径中断则降低了数据分组的投递率，还会引发路由维护以及路由重构，增加路由协议的开销，降低了整个网络的工作效率。

AODV协议是Ad Hoc网络中按需路由协议，AODV协议采用DSR协议的按需发现、建立、维护路由的策略，同时又具有与DSDV协议相同的序列号机制。序列号机制用于保证路由无环。AODV是单路径路由、逐跳按需路由协议。

AOMDV协议是在AODV协议的多路径版本，AOMDV协议在一次路由建立的过程中建立多条链路不相交的路径，在路由维护时，只有当所有的路径都失效后才重新发起路由建立过程。

AODV_PA协议是在AODV协议的基础上，添加路径收集机制的协议，在一次路由建立过程中建立起路径中每个节点的路由。

    现有技术的客观缺点：

AODV协议一次路由建立时，不记录沿途节点的路由，路由发现效率低，并且AODV协议只保存一条活动路径，活动路径断裂时，通信路径断裂，增加丢包率、通信时延、路由开销。

AOMDV协议虽然一次建立了多条路径，但是AOMDV协议在选择路径的策略是选择最短路径，但是最短路径的稳定性并不是很好，同样易受到节点运动导致通信路径断裂的影响。

AODV_PA协议是单路径、路径收集协议，但是在路由发现的过程中，中间节点只接收第一个路由请求分组，忽略其他路由请求分组，造成协议获取路由信息的能力下降，同样地，AODV_PA协议的路由选择策略是最短路径，此策略未考虑节点运动对路由协议的影响。

发明内容

针对现有技术的不足，本发明提供一种基于双向链路、链路不相交多路径、逐跳传输的Ad Hoc网络按需路由协议。

本发明可以获得如下有益效果：

    （1）能够提高路由发现效率，减少路由开销；

（2）能够提高通信路径的稳定性，减少节点运动导致通信路径断裂的影响；

    （3）能够提高获取路由信息的能力。

本发明的技术方案如下：

一种基于路径收集的Ad Hoc网络按需路由协议的建立和维护方法，包括：

建立基于链路不相交多路径算法的多条路径；

记录每条路径中整条路径的有序节点ID，利用下游节点发送标识的无环机制达到路由无环；

在多条路径中选择时，优先选择最新建立的路径；

只维护使用过的路径。

所述的多路径算法，在节点收到路由请求分组时的具体步骤如下：

（1）当节点收到一个路由请求分组时，如果路由请求分组提供的反向路径和本次路由请求中节点已经收到的所有反向路径链路不相交，转到步骤（3）；

（2）当节点收到一个路由请求分组时，如果路由请求分组提供的反向路径和本次路由请求中节点已经收到的任何一条或者多条反向路径链路相交，转到步骤（4）；

（3）若该节点是目的节点，则只应答前三个路由请求分组，处理结束；若该节点是中间节点，则在路径表中查找该节点到达目的节点的正向路径，找到的路径必须和本次路由请求中节点已经使用的所有正向路径链路不相交，如果存在这样一条正向路径，该节点则使用此正向路径形成路由应答分组，并沿着刚刚收到的反向路径回传给源节点，处理结束；若不存在这样的正向路径，则转到步骤（4）；

（4）若收到的是第一个路由请求分组，则广播转发，处理结束；若不是第一到达的路由请求分组，则只是缓存收到的反向路径，然后直接丢弃路由请求分组，不应答也不转发，处理结束。

所述的多路径算法，在节点收到路由应答分组时的具体步骤如下：

（1）当节点收到一个路由应答分组时，若本节点是源节点，则缓存收到的路径，处理结束；若本节点不是源节点，则转到下一步骤；

    （2）本节点是中间节点，若收到的路由应答分组提供的正向路径和本次路由请求中节点已经收到的所有正向路径链路不相交，转到步骤（4）；

    （3）本节点是中间节点，若收到的路由应答分组提供的正向路径和本次路由请求中节点已经收到的任何一条或者多条正向路径链路相交，则丢弃收到的路由应答分组，处理结束；

    （4）在路径表中查找到达源节点的反向路径，找到的路径必须和本次路由请求中节点已经使用的所有反向路径链路不相交，如果存在这样一条反向路径，则中间节点沿此反向路径向源节点单播收到的路由应答分组，处理结束；如果不存在这样一条反向路径，则丢弃收到的路由应答分组，处理结束。

    所述的下游节点发送标识的无环机制，是在现有AODV协议的基础上，其路由表项以及数据分组结构作如下修改：

    （1）路由表项去掉“下一跳”字段，取而代之的是整条路径的有序节点ID列表；

    （2）在数据分组中添加“发送标识”字段，该字段指出数据分组所经过的关键中间节点；

（3）路由表项添加“路径变换标记”字段，只要路径发生了更新，此字段就被标记；如果“路径变换标记”为真，则在数据分组的“发送标识”字段中添加本节点ID，然后转发，同时清除“路径变换标记”；如果“路径变换标记”没有标记，节点不对数据分组做任何改动，直接转发。

附图说明

图1为本发明所述协议的功能方框图。

图2描述了路径收集与非路径收集路由请求过程的区别。

图3描述了链路相交与链路不相交的区别。

图4为本发明中的链路不相交的多路径算法示意图。

图5描述了路径维持时间的概率密度函数关系。

具体实施方式

下面对本发明作进一步的详细描述。

基于路径收集的Ad Hoc网络按需路由协议（以下称基于路径收集的路由协议：PABR协议）是基于双向链路、链路不相交多路径、逐跳传输的Ad Hoc网络按需路由协议。PABR协议主要包括路由建立和路由维护两个过程，整个PABR协议的功能方框图如图1所示。

1.路径收集机制

路径收集的主要思想是在路由控制分组（路由请求分组RREQ和路由应答分组RREP）中记录分组所经过的中间节点，收到路由控制分组的节点不仅得到源节点或者目的节点的路由，同时也额外地得到了路径中间节点的路由。图2显示了带路径收集协议和非路径收集协议的路由请求过程的区别。在非路径收集协议中，收到RREQ分组的节点B、C、D、E，仅得到了源节点A的路由，收到RREP分组的节点A、B、C、D，也只能获取目的节点E的路由。在带路径收集的情况下，收到RREQ或者RREP分组的节点得到了整条路径节点的路由信息。

路径收集机制具有以下优点：

（1）额外获得的路径中间节点的路由，能免去以这些中间节点作为目的节点的路由请求过程，减少路由发现的次数，降低了路由开销和路由建立的等待时间；

（2）包含在路径中的大量路由信息不仅能提供新的路由信息，还更新了现有路由，使节点保存的路由信息能更准确地反映当前网络的拓扑结构；

（3）获取的大量路由信息增加了节点的平均有效路由数量，提高了RREQ分组被应答的可能性，缩小了RREQ分组的广播范围和转发次数。

2.链路不相交的多路径算法

假设源节点S和目的节点D之间有n条路径，如果n条路径中的任何两条都没有共同的链路，则这n条路径链路不相交。链路不相交的路径可以有相交节点，图3给出了相交链路与不相交链路的区别。

链路不相交的多路径算法可以描述为：路由请求过程中，对于每一个中间节点而言，所有反向路径之间链路不相交，同时所有正向路径之间链路也不相交，如图4所示。算法的具体执行流程如下：

（1）节点收到RREQ分组时：

步骤1：当节点收到一个RREQ分组时，如果RREQ分组提供的反向路径和本次路由请求中节点已经收到的所有反向路径链路不相交，表明中间节点可以应答此反向路径，转到步骤3；

步骤2：当节点收到一个RREQ分组时，如果RREQ分组提供的反向路径和本次路由请求中节点已经收到的任何一条或者多条反向路径链路相交，转到步骤4；

步骤3：若该节点是目的节点，则只应答前三个路由请求分组，处理结束。若该节点是中间节点，则在路径表中查找该节点到达目的节点的正向路径，找到的路径必须和本次路由请求中节点已经使用的所有正向路径链路不相交，如果存在这样一条正向路径，该节点则使用此正向路径形成RREP分组，并沿着刚刚收到的反向路径回传给源节点，处理结束。若不存在这样的正向路径，则转到步骤4；

    步骤4：若收到的是第一个RREQ分组，则广播转发，处理结束。若不是第一到达的RREQ分组，则只是缓存收到的反向路径，然后直接丢弃RREQ分组，不应答也不转发，处理结束。

（2）节点收到RREP分组时：

步骤1：当节点收到一个RREP分组时，若本节点是源节点，则缓存收到的路径，处理结束；若本节点不是源节点，则转到下一步骤；

    步骤2：本节点是中间节点，若收到的RREP分组提供的正向路径和本次路由请求中节点已经收到的所有正向路径链路不相交，转到步骤4；

    步骤3：本节点是中间节点，若收到的RREP分组提供的正向路径和本次路由请求中节点已经收到的任何一条或者多条正向路径链路相交，则丢弃收到的路由应答分组，处理结束；

步骤4：在路径表中查找到达源节点的反向路径，找到的路径必须和本次路由请求中节点已经使用的所有反向路径链路不相交，如果存在这样一条反向路径，则中间节点沿此反向路径向源节点单播收到的RREP分组，处理结束；如果不存在这样一条反向路径，则丢弃收到的RREP分组，处理结束。

3.路由选择策略

路径的稳定性用其维持时间来描述。路径从建立到它出现链路断裂所经过的时间t就是路径的维持时间，t越大说明路径的稳定性越好。现有的研究使用统计方法分析了不同运动模型（随机路点移动模型、参考点群组移动模型、公路移动模型、曼哈顿移动模型）对路径维持时间的影响，并进一步指出，在节点相对运动速度较高（10m/s）、路径平均长度较长(2 hops以上)的情况下，图5所示，所有运动模型的路径维持时间的概率密度呈指数分布。

因此，从统计意义上来说，新路径的维持时间大于现有路径的剩余维持时间。换言之，新路径比现有路径具有更好的稳定性和持续性。本发明中PABR协议在多条路径中选择时，优先选择最新建立的路径，以提高通信路径的稳定性。

    4.“下游节点发送标识”无环机制

    为实现此机制，路由表项以及数据分组结构在AODV的基础上作如下修改：

（1）路由表项去掉“下一跳”字段，取而代之的是整条路径的有序节点ID列表。节点依据此字段就可以知道其下游节点包含了哪些节点；

（2）在数据分组中添加“发送标识”字段，该字段指出数据分组所经过的关键中间节点；

（3）路由表项添加“路径变换标记”字段，只要路径发生了更新，此字段就被标记。节点依据此字段来决定在转发数据分组时是否需要在数据分组的“发送标识”字段中添加本节点ID。如果“路径变换标记”为真，则在数据分组的“发送标识”字段中添加本节点ID，然后转发，同时清除“路径变换标记”；如果“路径变换标记”没有标记，节点不对数据分组做任何改动，直接转发。

因此，“下游节点发送标识”无环机制可以描述为：节点每收到一个数据分组时，必定检查数据分组的“发送标识”字段，如果“发送标识”字段出现下游节点，则说明此数据分组先经过下游节点，再回传给上游节点（本节点），节点探测到环路产生，随后确定产生环路的路径并使之失效。由此可见，“下游节点发送标识”无环机制是先探测环路，然后使产生环路的路径失效，从而避免环路。

5.路由建立过程

当源节点需要和目的节点进行通信而又没有目的节点的有效路由信息时，PARB协议通过广播RREQ分组发起路由建立过程。RREQ分组以及RREP分组的结构分别是：

表1 RREQ分组包含的字段

表2 RREP分组包含的字段

在RREQ分组的广播过程中，节点使用<Src_ID，BroadCast_ID>元序来唯一标识本次路由建立过程。节点收到RREQ分组时，做如下处理：

步骤1：首先检查RREQ分组的Path_list字段是否已经包括了本节点的ID。若Path_list字段已经包含本节点的ID，说明收到的RREQ分组是本节点之前转发的，应直接丢弃，结束处理；否则转到步骤2；

步骤2：收到的RREQ分组若满足以下3个条件之一，就把RREQ分组提供的路径保存到路径表中：①第一个到达的RREQ分组；②本节没有任何到达源节点的有效路由；③RREQ分组提供的路径长度减去本节点当前知道的、到达源节点的最短路径长度不大于一个常数值（经验值设定为1），并且本次路由建立收集的路径数量少于n（经验值设定为3）。条件③是为了防止保存迂回的路径，同时减少接收的路径数量，减少硬件内存的需求。若RREQ分组未能满足其中任何一个条件，则丢弃RREQ分组，结束处理；否则转步骤3；

步骤3：使用收到的路径更新本地路由表。以路径中的每一个节点作为目的节点，做如下判断，若：①本节点没有到达目的节点的有效路由，或者②RREQ分组提供的路径长度减去本节点当前保存的最短路径长度不大于一个常数值（经验值设定为1），则把目的节点对应的路由表项的路径指针指向新收到的路径，同时修改路由表项的跳数；

步骤4：若本节点是目的节点，应答前k个到达RREQ分组；否则丢弃RREQ分组，处理结束；

步骤5：若本节点是中间节点，则执行链路不相交的多路径算法，从而决定是否能应答以及使用哪条正向路径应答。若不能应答，则只转发第一个RREQ分组：在RREQ分组的Path_list字段追加本节点的ID，修改Path_len，然后广播转发；否则，丢弃其他后到的RREQ分组，处理结束。

RREP分组在回传的过程中同样记录所有经过的中间节点。节点收到RREP分组，就获得了到达目的节点的整条路径。节点处理RREP的方式与RREQ分组的处理方式相似，不同的是RREQ提供的是反向路径，而RREP提供的是正向路径。

当源节点收到第一个RREP分组时，立刻可以使用此RREP分组提供的正向路径进行通信。此后源节点会接收到多个RREP分组，每一个RREP分组提供了一条链路不相交的路径。

6.路由维护

定义1：

子路径：一条由n个节点组成的完整路径记为P，由连续k个（ ）子节点组成的路径p都是完整路径P的子路径；

定义2： 

路径的有效长度：新收到的路径其有效长度等于路径的实际长度（组成路径的节点数），当路径中发生中断时，处于断开链路的下游子路径不再可达，但是处在断开链路的上游子路径仍然有效，有效的子路径的实际长度就是路径的有效长度；

定义3：

使用过的路径：一条路径，如果曾被用来转发数据分组，则这条路径是使用过的路径。

路由维护由2个通知完成：（1）链路断裂通知；（2）无路由错误通知。所谓无路由错误，即非信源节点收到一个数据分组，却没有相应的有效路由对数据分组进行转发，此时就发生了无路由错误。

当发送链路断裂时，所有包含断开链路的路径其路径长度都应该缩短为实际有效子路径的长度。同样地，如果发生了无路由错误，节点也必须通知其他节点：经过本节点到达不了目的节点。路由维护需要广播RERR（Route Error）分组，其结构如表3所示：

表3 RERR分组的结构

    一个RERR分组可以同时包含“断裂链路”和“无路由错误”两种信息，也可以只包含其中一种。当Up_broken_ID和Down_broken_ID均为有效节点ID时，表明RERR分组包含了断开链路信息；当unreach_node_cnt大于0时，表明RERR分组包含了无路由错误信息。

    当发送无路由错误时：节点广播只包含无路由错误信息的RERR分组。当节点探测到链路断裂时：（1）将所有包含此断开链路的路径的有效长度修改为有效子路径的时间长度；（2）寻找其他路径对数据分组进行补救，若补救成功则转发，否则丢弃数据分组；（3）形成RERR分组并广播。在发生链路断裂时，不管对数据分组的补救是否成功，RERR分组都必定包含断开链路的信息，至于是否包含无路由错误信息，则根据对数据分组的补救结果而定。补救成功则说明经过本节点仍然可以到达目的节点，RERR分组不需要包含无路由错误信息；否则RERR分组将添加无路由错误信息，通知其他节点：“经过本节点不能到达目的节点”。

节点收到RERR分组时，首先根据分组提供的信息更新本地路径表。如果本地路径表受到了影响（某些路径其有效长度变短），则需要广播转发收到RERR分组通知其他节点。考虑到路径收集协议包含数量众多的冗余路径以及维护全部路径所带来的开销问题，在路由维护时，只维护那些必要的路径。因此，只有使用过的路径其有效长度发生了变化，才需要广播转发RERR分组。如果所有受影响的路径都没有使用过，则不需要广播转发RERR分组。节点收到RERR分组时，处理过程如下：

步骤1：若Up_broken_ID以及Down_broken_ID均为有效节点ID，表明RERR分组包含链路断裂信息。路径表中所有包含此断开链路的路径其有效长度修改为实际有效子路径的长度。

步骤2：若unreach_node_cnt大于0，则对unreach_node_list中的每个节点做路径更新：所有先经过“报告错误节点”（转发RERR分组的节点）、再经过不可达节点的路径，其有效长度只能延伸到“报告错误节点”。

步骤3：路径更新完毕后，基于本地路径表寻找其他有效路径，对不可达节点的路由进行预先补救，并记录经路由补救后仍未可达的节点。

步骤4：若在所有受影响的路径中存在一条或者一条以上是使用过的路径，或者存在补救后仍未能到达的目的节点，则广播转发RERR分组。在广播转发的RERR分组中，Up_broken_ID和Down_broken_ID字段不变（和收到的RERR分组相同），而unreach_node_list字段则包含了补救后仍然未能到达的目的节点。