一种无线自组织网络适应性路由构造方法

摘要

本发明提供一种无线自组织网络中的路由构造方法，包括：根据节点可达性等价划分构造虚拟节点，并以虚拟节点为基础构造源节点到目标节点的虚拟路由；在数据传递过程中，动态选择可用的虚拟节点成员来即时配置虚拟路由，适应性更新虚拟节点，局部修复虚拟路由。本发明所述方法克服了主动协议路由维护代价高的缺点，提高了路由适应性；克服了按需协议因按需路由发现引起的延迟，减少了由节点失效引起的路由重发现；克服了混合协议集成路由片段而产生的问题，提高了对路由片段节点失效及网络结构变化的适应性。

说明书

技术领域

本发明涉及无线自组织网络技术领域，更具体地，本发明涉及无线自组织网络中的路由构造方法，特别涉及无线自组织网络可动态调整的适应性路由方法。

背景技术

无线自组织网络由一组不需要任何硬件设施的动态节点组成，由于其灵活、扩展性强的特点，在家庭网络、应急救灾等领域具有广阔的应用前景。虽然无线自组织网络本身具有突出的动态性，但实际上这类网络并不总能持续、稳定地工作，通常很多因素会造成无线自组织网络的不稳定，例如：节点位置的变化会造成网络拓扑结构的变化及节点失效；网络不稳定造成的节点失效会导致网络路由的失效。

目前，尽管已有不少无线自组织网络路由协议，但如何高效、低代价地构造基于虚拟节点的适应性路由，使路由适应网络结构变更、节点失效等变化的问题并没有得到解决。常用的无线自组织网络路由协议主要包括AODV、AOMDV、DSR、TEEN、Flooding、Rumor Routing。这些协议分为主动协议、按需协议和混合协议三类。主动协议需要事先建立路由，路由事先建立之后，若网络节点发生变化而路由未能及时更新，事先建立的路由将会失效；主动协议(诸如，TEEN)如果期望适应变化就需要及时更新事先建立的路由，频繁周期性地路由更新大大增加了路由代价。按需协议只有在数据传递时才创建路由，这类路由使用较新的网络信息，因在使用时才建立，故数据传递延迟较大；按需协议(诸如AODV、AOMDV)虽然对网络拓扑变化有一定适应性，但路由按需建立之后，网络结构变动及节点失效会导致路由重发现，这大大增加了数据传递延迟，严重影响了网络性能。混合协议融合了主动协议和按需协议的特点，同时也包括了二者的缺陷；混合协议(诸如Rumor routing)需要事先建立路由片段，使用时建立路由片段的连接，需要维护事先建立的路由片段代价较高，而且对路由片段中以及片段间的节点失效、网络结构变化的适应能力很弱。

发明内容

为克服现有无线自组织网络中路由重发现代价大、路由重发现加大数据传输延迟以及路由对网络拓扑结构变化适应能力差的缺陷，解决虚拟节点构造、更新及虚拟路由即时装配、配置的问题，本发明提出了一种无线自组织网络路由构造方法。

根据本发明的一个方面，提出了一种无线自组织网络适应性路由构造方法，包括：

步骤10)、根据节点可达性等价划分来构造虚拟节点，并以虚拟节点为基础来构造从源节点到目标节点的虚拟路由；

步骤20)、在数据传递过程中，动态选择可用的虚拟节点成员来即时配置虚拟路由。

其中，步骤10)之后还包括：适应性更新虚拟节点，局部修复虚拟路由。

其中，步骤10)中，所述可达性等价划分包括：在源节点向目标节点的链路中，相对于上游中间节点可转发其消息并到达目标节点的两个或者多个直接下游中间节点可达性等价。

其中，步骤10)还包括：路由请求消息传递过程中消息发送者将成为消息接收者通向源节点路由上的下一跳虚拟节点的成员；

路由请求响应消息传递过程中消息发送者将成为消息接收者通向目标节点路由上的下一跳虚拟节点的成员。

其中，步骤10)还包括：将可达性等价节点作为虚拟节点成员，在从源节点到达目标节点的路径上，虚拟节点动态选择属于该虚拟节点的成员节点相互替代实现数据传递。

其中，步骤10)包括：

步骤110)、消息接收者收到路由请求消息之后，确定其路由表中存在通向源节点的虚拟节点或者创建新虚拟节点并将消息发送者添加为虚拟节点成员；

步骤120)、确定消息接收者存在通向目标节点的路由，其路由表中存在通向源节点的虚拟节点，消息接收者将向该虚拟节点发出路由请求响应消息；

步骤130)、收到路由请求响应消息的节点确定路由表中存在通向目标节点的虚拟节点，将消息发送者添加为虚拟节点成员，消息接收者确定为源节点，实现源节点与目标节点之间的虚拟路由。

其中，步骤130)还包括：收到路由请求响应消息的节点不是源节点，且确定路由表中不存在通向目标点的虚拟节点，创建新虚拟节点并将消息发送者添加为虚拟节点成员，转发路由请求响应消息。

其中，步骤20)还包括：在数据传递过程中，上游节点在虚拟路由下一跳的虚拟节点成员中根据其传输能力及可用性动态选择可用节点传递数据直至目标节点，实现虚拟路由即时装配、配置。

其中，所述适应性更新虚拟节点和局部修复虚拟路由的步骤包括：

步骤11)、虚拟路由中的中间节点以显式组播方式向虚拟节点成员发送寿命消息，中间节点根据未监听到虚拟节点成员返回的确认消息来确定虚拟节点成员失效；

步骤12)、虚拟节点成员被发现预定次数的失效后，被标识为失效节点；

步骤13)、当虚拟节点成员减少到不多于1个时，所述虚拟节点成员根据自身记录的目标节点信息向邻居节点发送路由请求消息，将消息接收者添加为虚拟节点成员。

其中，步骤12)还包括：虚拟节点成员被发现低于预定次数的失效时标识为假死节点。

与现有的主动协议相比，本发明所述方法建立的是基于虚拟节点的虚拟路由，虚拟节点的适应性更新及虚拟路由的即时装配、配置可动态产生工作路由，克服了主动协议路由维护代价高的缺点，提高了路由适应性；与按需路由相比，本发明所述方法在数据传递时并不触发路由发现过程，而是即时装配、配置虚拟路由，克服了按需协议因按需路由发现引起的延迟，减少了由节点失效引起的路由重发现；与混合协议相比，本发明并不预先建立路由片段，而是建立完整的虚拟路由，虚拟路由即时装配、配置克服了混合协议集成路由片段而产生的问题，提高了对路由片段节点失效及网络结构变化的适应性。

附图说明

图1示出本发明的基于虚拟节点的无线自组织网络适应性路由构造方法的总体流程图；

图2示出构造虚拟节点及基于虚拟节点的虚拟路由的示例流程图；

图3示出在孤立失效节点情况中实施本发明的方法的一个应用实例；

图4示出在区域失效节点情况中实施本发明的方法的一个应用实例。

具体实施方式

下面结合附图和具体实施实例对本发明提供的一种无线自组织网络的路由构造方法进行详细描述。

图1示出基于虚拟节点的无线自组织网络中适应性路由构造方法的总体流程图。本实施实例所述的方法以节点可达性等价关系来构造虚拟节点、以虚拟节点为基础来构造虚拟路由；按需即时装配虚拟路由，获得工作路由，以避免节点失效、网络结构变化对路由的负面影响；同时可以在路由构造完成后的任何时间来适应性更新虚拟节点，局部修复虚拟路由。

参见图1，本实施实例所述的方法包括两个阶段：1、虚拟节点和虚拟路由构造，2、虚拟节点适应性更新和虚拟路由局部修复以及虚拟路由的即时组装。

第一阶段为虚拟节点和虚拟路由构造。源节点发出路由请求消息，进行源节点与目标节点之间的中间节点的可达性等价划分，可达性等价划分按照如下步骤进行：在源节点向目标节点发送数据的过程中，A是一个上游中间节点，若A转发的消息能经A的直接下游中间节点B、C转发并最终到达目标节点，则中间节点B、C相对节点A在从源节点到目标节点的路由上是可达性等价的。所以节点的可达性等价划分通过在源节点和目标节点间发送路由请求\响应消息实现。其中，路由请求消息传递过程实现从目标节点到源节点间节点的可达性等价划分，在消息传递过程中消息发送者将成为消息接收者通向源节点路由上的下一跳虚拟节点的成员；路由请求响应消息传递过程实现从源节点到目标节点间节点的可达性等价划分，在消息传递过程中消息发送者将成为消息接收者通向目标点路由上的下一跳虚拟节点的成员。

根据节点可达性构造虚拟节点，构造虚拟节点时，首先根据节点可达性对源节点与目标节点间可能路径上的节点进行等价划分，然后以节点等价集为基础构造虚拟节点，节点等价集中的节点将作为虚拟节点成员。在从源节点到达目标节点的路径上，属于同一虚拟节点的成员节点具有相同的数据传递能力，虚拟节点成员可以相互替代完成数据传递，虚拟节点可以动态选择参加数据传递的成员节点。每个虚拟节点以路由请求接收者、路由请求源节点和虚拟节点集中第一个被发现的成员的IP地址组成的三元组标识。

在虚拟节点构造的同时实现基于虚拟节点的虚拟路由的构造。基于虚拟节点的虚拟路由的构造包括如下步骤：(1)、源节点向其邻居节点发送路由请求消息，若收到请求的邻居节点属于一个能够向源节点发送数据的虚拟节点，而且路由请求发送者不是该虚拟节点的成员，那么路由请求接收者将该发送者添加为接收者所属虚拟节点的成员；(2)、路由请求接收者不属于能够向源节点发送数据的虚拟节点，则它创建一个新的虚拟节点并将路由请求发送者添加为虚拟节点成员；(3)、如果路由请求接收者是目标节点或者存在一条从它到目标节点的路由，则将根据步骤(1)、(2)更新或创建虚拟节点，然后向它所知道的通往路由请求源节点的节点或虚拟节点发送路由请求响应消息；(4)、如果路由请求接收者不是目标节点而且也没有一条从它到目标节点的路由，则它将根据步骤(1)和(2)更新或创建虚拟节点，然后向其邻居节点发送路由请求，直至建立路由请求源节点和目标节点之间的路由。

第二阶段包括两个子阶段，第一个子阶段是适应性更新，该阶段包括失效节点局部探测，节点假死判定，虚拟节点适应性更新及虚拟路由局部修复：

(1)、每个节点根据自己的路由表获取虚拟节点信息，以显式组播方式向虚拟节点成员发送寿命消息。虚拟节点成员收到寿命消息后返回确认消息，寿命消息发出者根据是否能监听确认消息判断虚拟节点成员是否失效，若虚拟节点成员没有返回寿命消息的响应消息，则判定节点失效；该方法是一种局部组播的方法，避免了像心跳消息这样的消息在整个路由上的传播。

(2)、采用节点假死判定方法实现虚拟节点适应性更新，虚拟节点成员第一次被发现失效时，并不立即标记为失效节点，而是被标记成假死节点，直至第三次被发现失效，才最终被标识为失效节点。在此，虚拟节点成员失效检测的次数设定为三次，也可以设置为四次、五次，但随着次数的增加判断时间会加长。在虚拟节点适应性更新过程中将根据实际情况动态确定检测次数。节点假死判定有效地避免了因网络动态变化产生的节点暂时失效所引起的不必要的、频繁的路由重发现或路由修复。

(3)、当一个虚拟节点的有效成员减少到不多于1个时，它将触发虚拟节点成员重发现，开始局部修复虚拟路由。这种局部修复并不是重新构建虚拟路由，而是重新发现虚拟节点成员。虚拟节点成员根据自身记录的目标节点信息向邻居节点发送路由请求消息，并将消息接收者添加为虚拟节点成员。当虚拟节点数增至2个以上时，重发现将结束。虚拟节点重发现将虚拟路由的修复局限在虚拟节点范围内，降低了路由修复、维护的代价。

第二个子阶段是虚拟路由的即时组装，如下步骤进行：工作路由通过在数据传递过程中即时装配、配置虚拟路由动态生成，在数据传递过程中，上游节点在虚拟路由下一跳的虚拟节点成员中动态选择一个可用节点，将数据传递至该节点，如此反复直至数据到达目标节点。虚拟路由的即时装配、配置在数据传递过程中根据虚拟节点成员的实际情况即时确定参与数据传递的工作节点，从而有效地避免了节点失效、网络拓扑结构变化对路由的负面影响。

图2示例性描述虚拟节点构造及基于虚拟节点的路由流程。如图2所示，消息接收者收到路由请求消息之后，首先判断路由表中是否有通向源节点的虚拟节点。若无，则创建新虚拟节点并将消息发送者添加为虚拟节点成员；然后判断消息接收者是否为目标节点或有通向目标节点的路由，若否，则转发路由请求消息。若路由表中有通向源节点的虚拟节点，则判断消息发送者是否是该虚拟节点的成员。若否，则将消息发送者添加为虚拟节点成员；然后判断消息接收者是否为目标节点或有通向目标节点的路由，若否，则转发路由请求消息。若消息接收者是目标节点或有通向目标节点的路由，则消息接收者将发出路由请求响应消息。某节点收到该消息后将判断路由表中是否有通向目标点的虚拟节点。若无，则创建新虚拟节点并将消息发送者添加为虚拟节点成员。若有，则判断消息发送者是否是该虚拟节点的成员。若无，则将消息发送者添加为虚拟节点成员。然后消息接收者判断是否已达源节点。若否，则转发路由请求响应消息。若是，则终止消息转发，完成源节点与目标节点的之间的虚拟节点及虚拟路由构造。

图3示出在孤立节点失效情况下实施本发明所述方法的一个实例，如图3所示，node₀为源节点，node₆为目标节点。通过发送路由请求/响应消息，node₀与node₆之间建立了一条包含虚拟节点vn₁的虚拟路由。其中，vn₁的成员包括node₂、node₃、node₄。当node₀向node₆发送数据时虚拟节点vn₁将即时选择虚拟节点成员，组装工作路由，参与数据传递。此时，节点node₂失效，vn₁选择有效节点node₃，即时组装成工作路由(node₀->node₁->node₃->node₅->node₆)。

图4示出当一个区域内多个节点失效时实施本发明所述方法的一个实例。如图4所示，node₀为源节点，node₈为目标节点。通过发送路由请求/响应消息，node₀与node₈之间建立了一条虚拟路由。该虚拟路由包含了两个虚拟节点vn₂和vn₃。在node₀向node₈发送数据的过程中，区域A范围内不只一个节点发生了失效。区域A被虚拟节点vn₂和vn₃的成员所覆盖。此时，虚拟节点vn₂选择成员节点node₃代替失效节点node₂，虚拟节点vn₃选择node₆代替失效节点node₅，即时组装生成工作路由(node₀->node₁->node₃->node₄->node₆>node₇->node₈)，完成数据传递。

最后应说明的是，以上实施实例仅用以描述本发明的技术方案而不是对本技术方法进行限制，本发明在应用上可以延伸为其他的修改、变化、应用和实施实例，并且因此认为所有这样的修改、变化、应用、实施实例都在本发明的精神和教导范围内。