无线移动自组网中容错及连接恢复方法

摘要

一种无线移动自组网中容错及连接恢复方法,在簇首之间直连链路的基础上，维持了一条多跳路径，如果直连链路因发送簇首和接收簇首之间距离增加而断开，则通过发送簇首和接收簇首之间的多跳路径维持发送簇首和接收簇首之间的连接；如果发送簇首发现连接在其与接收簇首之间的最后一条多跳路径在下一时隙将要断开或者已经断开时，相应节点将促发级联运动，在确保簇内所有节点连通的前提下，维持发送簇首和接收簇首之间的最后一条多跳路径完整或者恢复一条发送簇首和接收簇首之间的多跳路径。本发明增加了系统的鲁棒性，同时还提出了三种级联运动方法，保持簇内连通性，降低修复过程对簇内成员的影响。

说明书

技术领域

本发明属于无线通信网络技术领域，涉及无线移动自组网中容错及连接恢复方法。

背景技术

无线移动自组网由于不需要中心控制节点、能够多跳传递信息以及可以自行组网等特点，在军事、农业、环保等领域都得到了广泛的应用。

在节点较多的情况下，为了减少网络负担，充分利用节点自身资源，常常选择部分能力较强的节点作为簇首，其它节点作为成员组成分级网络。簇首负责信息的汇聚和转发，因此簇首之间的连接至关重要。

但是由于网络的动态特性，部分簇首之间由于距离的增加而导致连接断开。尤其是一些簇首处于关键位置，该簇首失效或者部分簇首与其之间的链路断开，网络将会被分成几个互不相连的部分，此时网络性能急剧退化。在一些延时敏感的网络中，比如无人机自组网，部分节点与网络失去连接将会造成严重后果。因此，无线移动自组网需要增强网络鲁棒性，提升自我修复能力，

在已有的研究中，拓扑控制能够有效解决上述问题。目前许多研究集中于控制发射功率来改变拓扑。由于距离的增大导致链路中断，因此需要增加发射功率去修复。但是发射功率不可能无限增大，并且大功率会引入额外的干扰。因此增加发射功率并不能从根本上解决问题。

运动管理也是一种有效的拓扑控制方法，目前主要是无线传感器网络使用关键节点进行控制。关键节点是网络内处于特殊位置的节点，如果该关键节点失效，则网络将会被分为若干个相离的分片。每个关键节点在自己邻居中选择一个替补节点，一旦关键节点失效，替补节点则运动到关键节点原来的位置去恢复连接。由于在无线传感器网络中，大部分节点大部分时间处于静止状态，只有在需要恢复连接时部分节点参与运动，这并不完全适应于无线移动自组网。

发明内容

针对现有技术存在的缺陷，本发明提供一种无线移动自组网中容错及连接恢复方法。本发明要解决的技术问题是：最小化参与恢复连接过程的节点数目，并且最小化节点偏离原方向的距离。同时，在级联运动过程中，要保持簇内成员节点之间的连通性。

为实现上述技术目的，本发明采用的技术方案是：

一种无线移动自组网中容错及连接恢复方法，在无线移动自组网的发送簇首和接收簇首之间建立一条直连链路，同时还在发送簇首和接收簇首之间维持一条以上的多跳路径，多跳路径由发送簇首、接收簇首以及连接在发送簇首和接收簇首之间的其它成员节点组成；

如果无线移动自组网的发送簇首和接收簇首之间的直连链路因为发送簇首和接收簇首之间距离增加而断开，则通过发送簇首和接收簇首之间的多跳路径维持发送簇首和接收簇首之间的连接；

如果发送簇首发现连接在其与接收簇首之间的最后一条多跳路径在下一时隙将要断开或者已经断开时，相应节点将促发级联运动，在确保簇内所有节点连通的前提下，维持发送簇首和接收簇首之间的最后一条多跳路径完整或者恢复一条发送簇首和接收簇首之间的多跳路径。

在本发明中，如果发送簇首a发现连接在其与接收簇首b之间的最后一条多跳路径在下一时隙将要断开，由于簇内所有节点之间是连通的，则在下一时隙将要断开的最后一条多跳路径必然是在该多跳路径的两个簇边缘成员节点之间断开。假设在下一时隙将要断开连接的两个簇边缘成员节点分别为c和d，其中节点c为发送簇的边缘成员节点，节点d属于接收簇的边缘成员节点；节点c根据卡尔曼滤波预测节点d在下一时隙的位置，并向该位置(即预测到的节点d在下一时隙的位置)移动。此时是由发送簇的边缘成员节点c促发级联运动。

如发送簇首a发现连接在其与接收簇首b之间的最后一条多跳路径已经断开，此时发送簇首a根据卡尔曼滤波预测接收簇首b在下一时隙的位置，并选择与接收簇首b距离最近的成员节点向预测位置(即预测到的接收簇首b在下一时隙的位置)移动。由与接收簇首b距离最近的成员节点促发级联运动。

在本发明中，设计了三种级联运动方式，在确保簇内所有节点连通的前提下，完成以上两种情况下级联运动。具体如下：

第一种级联运动方法：基于最近节点的级联运动方法。

该方法由以上两种情况下符合条件的成员节点促发。该方法由发送簇的所有成员节点依次根据自己邻居节点发送来的邻居信息自主决定自身在下一时隙运动方式。所有计算在每个成员节点本地完成。具体步骤如下：

(1)发送簇内的每个成员节点u接收所有自己邻居节点发送的运动状态信息，包括级联运动状态以及下一时隙即将运动到的位置。成员节点u的所有邻居节点中参与级联运动的节点构成集合M。

(2)如果集合M不为空，进入第(3)步，否则，成员节点u按照原任务继续运动，不设置级联运动状态。

(3)计算集合M中所有节点在下一时隙位置时通信范围的公共区域。成员节点u从公共区域内选择一点作为下一时隙运动到的位置，该位置使成员节点u改变运动方向最小。

(4)成员节点u向其各邻居节点发送自己的级联运动状态以及将要运动到的位置。

第二种级联运动方法：基于强连通控制吸入集的级联运动方法。该方法由以上两种情况下符合条件的成员节点促发。

该方法完全利用节点周围两跳邻居的信息，在节点本地判断自己是否属于强连通控制吸入集(SCDAS)。强连通控制吸入集(SCDAS)是属于连通控制集(CDS)的一种，是连通控制集(CDS)的一个特例。其集合外部每个节点至少可以在集合内部找到一个控制节点和吸入节点。本发明采用的是强连通控制吸入集(SCDAS)构造方法Rule1，Rule2规则(参考文献：J.Wu,“Extended dominating-set-based routing in ad hoc wireless networks withunidirectional links,”IEEE Transactions on Parallel and Distributed Systems,vol.13,no.9,pp.866–881,Sep 2002)。

该级联运动方法由发送簇的每个成员节点u依次根据自己的邻居信息自主决定自身在下一时隙运动方式。所有计算在每个成员节点本地完成。具体步骤如下:

(1)发送簇内的每个成员节点u接收邻居节点发送的运动状态信息，包括邻居节点的级联运动状态以及下一时隙即将运动到的位置；成员节点u的所有邻居节点中参与级联运动的节点构成集合M；

(2)如果集合M不为空，进入第(3)步；否则，节点u按照原任务继续运动，不设置级联运动状态；

(3)如果成员节点u的邻居节点中存在一个节点w，节点w尚未参与级联运动并且属于强连通控制吸入集；同时，集合M中存在一个节点m，节点m不属于强连通控制吸入集；节点u和节点m在下一时隙仍然能够保持与节点w之间的连接，则节点m参与级联运动对节点u不产生影响；将所有不对节点u产生影响的节点从集合M中剔除；

(4)计算集合M中剩余节点在下一时隙位置时通信范围的公共区域；节点u从公共区域内选择一点作为下一时隙运动到的位置，该位置使节点u改变运动方向最小；

(5)节点u向其各邻居节点发送自己的级联运动状态以及将要运动到的位置。

第三种级联运动方式：基于关键节点的级联运动。该方法由以上两种情况下符合条件的成员节点促发。

如果一个节点失效，则整个连通的网络被分为若干个分片，那么该节点是关键节点。判断一个节点是否是关键节点，需要全网信息。在动态网络中获取全网信息是非常困难的，因此，本发明根据一跳邻居信息判断每个节点是否是关键节点，得到一个次优结果。采用深度优先搜索算法，如果一个节点的所有邻居都可以遍历到，则该节点不是关键节点，否则，该节点是关键节点。该方法得到的不是最优解，但是需要较少的邻居信息，网络负担较小，适用于动态网络。

该级联运动方法由发送簇的每个成员节点u依次根据自己的邻居信息自主决定自身在下一时隙运动方式。所有计算在每个成员节点本地完成。具体步骤如下：

(1)发送簇内的每个成员节点u接收邻居节点发送的运动状态信息，包括邻居节点的级联运动状态以及即将运动到的位置；节点u的所有邻居节点中参与级联运动的节点构成集合M；

(2)如果集合M不为空，进入第(3)步；否则，节点u按照原任务继续运动，不设置级联运动状态；

(3)如果节点u的邻居中存在一个节点w，节点w尚未参与级联运动；同时，集合M中存在一个节点m，节点m不是关键节点；节点u和节点m在下一时隙仍然能够保持与节点w之间的连接，则节点m参与级联运动对节点u不产生影响；将所有不对节点u产生影响的节点从集合M中剔除；

(4)计算集合M中剩余节点在下一位置时通信范围的公共区域；节点u从公共区域内选择一点作为下一时刻运动到的位置，该位置使节点u改变运动方向最小；

(5)节点u向其各邻居节点发送自己的级联运动状态以及将要运动到的位置。

本发明的有益效果如下：

本发明采用了运动管理的方式对无线移动自组网进行拓扑控制，提出了三种级联运动方法，分别为基于最近节点的级联运动、基于强连通控制吸入集的级联运动以及基于关键节点的级联运动。

在本发明中，三种级联运动方法均使用邻居信息对自身运动进行控制，不需要全局信息，适用于动态网络。同时，三种方法采用的是级联运动，尽可能的减少参与修复过程的节点数目，降低了对节点原任务的影响。

本发明在簇首之间直连链路的基础上，维持了一条多跳路径，增加了系统的鲁棒性。采用级联运动的方式保持簇内连通性，降低修复过程对簇内成员的影响。同时，本发明后两种方法在构造SCDAS以及关键节点的基础上，减少了参与级联运动的节点数目，进一步降低了本发明对簇内成员的影响。

附图说明

图1是本发明的流程图；

图2是基于最近节点的级联运动方法的流程图；

图3是基于强连通控制吸入集的级联运动方法的流程图；

图4是基于关键节点的级联运动方法的流程图；

图5是不同成员节点密度下平均每次参与级联运动成员节点数目比较，节点速度为15m/s；

图6是不同成员节点密度下平均每个成员节点偏移距离比较，节点速度为15m/s；

图7是不同速度下平均每次参与级联运动成员节点数目比较，成员节点数目为20；

图8是不同速度下平均每个成员节点偏移距离比较，成员节点数目为20。

具体实施方式

为了使本发明的技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用于解释本发明，并不用于限定本发明。

参照图1，为本发明的流程图。一种无线移动自组网中容错及连接恢复方法，在无线移动自组网的发送簇首和接收簇首之间建立一条直连链路，同时还在发送簇首和接收簇首之间维持一条以上的多跳路径，多跳路径由发送簇首、接收簇首以及连接在发送簇首和接收簇首之间的其它成员节点组成；

如果无线移动自组网的发送簇首和接收簇首之间的直连链路因为发送簇首和接收簇首之间距离增加而断开，则通过发送簇首和接收簇首之间的多跳路径维持发送簇首和接收簇首之间的连接；

如果发送簇首发现连接在其与接收簇首之间的最后一条多跳路径在下一时隙将要断开或者已经断开时，相应节点将促发级联运动，在确保簇内所有节点连通的前提下，维持发送簇首和接收簇首之间的最后一条多跳路径完整或者恢复一条发送簇首和接收簇首之间的多跳路径。

在本发明中，如果发送簇首a发现连接在其与接收簇首b之间的最后一条多跳路径在下一时隙将要断开，由于簇内所有节点之间是连通的，则在下一时隙将要断开的最后一条多跳路径必然在该多跳路径的两个簇边缘成员节点之间断开。假设在下一时隙将要断开连接的两个簇边缘成员节点分别为c和d，其中节点c为发送簇的边缘成员节点，节点d属于接收簇的边缘成员节点。节点c根据卡尔曼滤波预测节点d在下一时隙的位置，并向该位置(即预测到的节点d在下一时隙的位置)移动。此时是由发送簇的边缘成员节点c促发级联运动。

如发送簇首a发现连接在其与接收簇首b之间的最后一条多跳路径已经断开，此时发送簇首a根据卡尔曼滤波预测接收簇首b在下一时隙的位置，并选择与接收簇首b距离最近的成员节点向预测位置(即预测到的接收簇首b在下一时隙的位置)移动。由与接收簇首b距离最近的成员节点促发级联运动。

在本发明中，设计了三种级联运动方式，在确保簇内所有节点连通的前提下，完成以上两种情况下级联运动。具体如下：

第一种级联运动方法：基于最近节点的级联运动方法。参照图2，图2是基于最近节点的级联运动方法的流程图。

该方法由以上两种情况下符合条件的成员节点促发，发送簇的所有成员节点依次根据自己邻居节点发送来的邻居信息自主决定自身在下一时隙运动方式。所有计算在每个成员节点本地完成。具体步骤如下：

(1)发送簇内的每个成员节点u接收所有自己邻居节点发送的运动状态信息，包括级联运动状态以及下一时隙即将运动到的位置。成员节点u的所有邻居节点中参与级联运动的节点构成集合M。

(2)如果集合M不为空，进入第(3)步，否则，成员节点u按照原任务继续运动，不设置级联运动状态。

(3)计算集合M中所有节点在下一时隙位置时通信范围的公共区域。成员节点u从公共区域内选择一点作为下一时隙运动到的位置，该位置使成员节点u改变运动方向最小。

(4)成员节点u向其各邻居节点发送自己的级联运动状态以及将要运动到的位置。

第二种级联运动方法：基于强连通控制吸入集的级联运动方法。参照图3，图3是强连通控制吸入集的级联运动方法的流程图。

一个网络的连通控制集(CDS)是指一个节点集合，该集合内任意两个成员节点之间至少存在一条路径，同时网络中不在连通控制集内的其他成员节点至少拥有一个在连通控制集内的邻居节点。由于网络是分级的，节点通信半径不同，本发明采用的是强连通控制吸入集(SCDAS)构造方法Rule1，Rule2规则。该方法完全利用节点周围两跳邻居的信息，在节点本地判断自己是否属于强连通控制吸入集(SCDAS)。强连通控制吸入集(SCDAS)是属于连通控制集(CDS)的一种，是连通控制集(CDS)的一个特例。其集合外部每个节点至少可以在集合内部找到一个控制节点和吸入节点。

该级联运动方法由发送簇的每个成员节点u依次根据自己的邻居信息自主决定自身在下一时隙运动方式。所有计算在每个成员节点本地完成。具体步骤如下：

(1)发送簇内的每个成员节点u接收邻居节点发送的运动状态信息，包括邻居节点的级联运动状态以及下一时隙即将运动到的位置。节点u的所有邻居节点中参与级联运动的节点构成集合M。

(2)如果集合M不为空，进入第(3)步；否则，节点u按照原任务继续运动，不设置级联运动状态。

(3)如果节点u的邻居节点中存在一个节点w，节点w尚未参与级联运动并且属于强连通控制吸入集。同时，集合M中存在一个节点m，节点m不属于强连通控制吸入集。节点u和节点m在下一时隙仍然能够保持与节点w之间的连接，则节点m参与级联运动对节点u不产生影响。将所有不对节点u产生影响的节点从集合M中剔除。

(4)计算集合M中剩余节点在下一时隙位置时通信范围的公共区域。节点u从公共区域内选择一点作为下一时隙运动到的位置，该位置使节点u改变运动方向最小。

(5)节点u向其各邻居节点发送自己的级联运动状态以及将要运动到的位置。

第三种级联运动方式：基于关键节点的级联运动。参照图4，图4是基于关键节点的级联运动方法的流程图。

如果一个节点失效，则整个连通的网络被分为若干个分片，那么该节点是关键节点。判断一个节点是否是关键节点，需要全网信息。在动态网络中获取全网信息是非常困难的，因此，本发明根据一跳邻居信息判断每个节点是否是关键节点。采用深度优先搜索算法，如果一个节点的所有邻居都可以遍历到，则该节点不是关键节点，否则，该节点是关键节点。该方法得到的不是最优解，但是需要较少的邻居信息，网络负担较小，适用于动态网络。

该级联运动方法由发送簇的每个成员节点u依次根据自己的邻居信息自主决定自身在下一时隙运动方式。所有计算在每个成员节点本地完成。具体步骤如下：

(1)发送簇内的每个成员节点u接收邻居节点发送的运动状态信息，包括邻居节点的级联运动状态以及即将运动到的位置。节点u的所有邻居节点中参与级联运动的节点构成集合M。

(2)如果集合M不为空，进入第(3)步；否则，节点u按照原任务继续运动，不设置级联运动状态。

(3)如果节点u的邻居中存在一个节点w，节点w尚未参与级联运动。同时，集合M中存在一个节点m，节点m不是关键节点。节点u和节点m在下一时隙仍然能够保持与节点w之间的连接，则节点m参与级联运动对节点u不产生影响。将所有不对节点u产生影响的节点从集合M中剔除。

(4)计算集合M中剩余节点在下一位置时通信范围的公共区域。节点u从公共区域内选择一点作为下一时刻运动到的位置，该位置使节点u改变运动方向最小。

(5)节点u向其各邻居节点发送自己的级联运动状态以及将要运动到的位置。

图5是不同成员节点密度下平均每次参与级联运动成员节点数目比较。实施例中，节点数目分别为：10，20，30，40。基于关键节点的级联运动方法所得到的结果是最优的。

根据基于最近节点的级联运动方法，一旦某个成员节点u参与级联运动，所有在下一时隙可能与节点u断开连接的邻居节点都会继续参与级联运动。但是部分邻居节点虽然断开了与节点u的直接链路，但是还存在其它路径与节点u相连，这些节点不需要参与级联运动。

其余两种方法就采用了这种策略进行裁减。基于强连通控制吸入集的级联运动方法是在构造SCDAS的基础上进行裁减。假设节点u不属于SCDAS，并且参与级联运动后与邻居w断开连接。如果节点u和w仍然会与SCDAS中某一个节点保持联系，则节点u对节点w就不会产生影响。通过这种方法，可以减少部分参与级联运动的节点。

基于关键节点的级联运动方法根据两跳邻居信息对节点进行判断。如果一个节点属于SCDAS，则它可能不是关键节点。如果一个节点是关键节点，则它一定属于SCDAS。因此，采用此方法进一步裁减了参与级联运动的节点。同时，基于连通控制集的级联运动方法和基于关键节点的级联运动方法得到的结果都是先升后降，说明节点密度越高，性能越好。主要是由于随着节点密度增大，SCDAS以及关键节点数目都会减小，降低了其它节点参与级联运动的可能性。

图6是不同成员节点密度下平均每个成员节点偏移距离比较。三条曲线都是下降的，说明节点密度越大，平均偏移距离越小。这主要是由于在密集网络中，节点之间平均距离小，在级联运动中，只需要调整一小部分方向，就能够满足要求。三种方法中，基于关键节点的级联运动方法所得到的结果是最优的。

图7是不同速度下平均每次参与级联运动成员节点数目比较。实施例中，节点速度分别为：10m/s，15m/s，20m/s，25m/s。随着速度的增加，参与级联运动成员节点数目同时增加。这是由于节点在高速情况下，一个时隙移动出邻居的通信范围的概率增大。同时，三种方法中，基于关键节点的级联运动方法所得到的曲线增长最平缓。这是由于在相同速度相同节点密度的情况下，参与级联运动的节点数目最少。

图8是不同速度下平均每个成员节点偏移距离比较。我们可以看到，节点速度对偏移距离有着较大的影响。尤其是在高速网络中，节点偏移距离明显增多。在节点速度为25m/s时，三种方法引起的平均偏移与速度比分别为90.7％,61.9％,和51.7％，对节点原运动方向改变是较大的。这主要由于节点速度较高，任何一点偏移，在一个时隙内就会造成较大的影响。

综上所述，虽然本发明已以较佳实施例揭露如上，然其并非用以限定本发明，任何本领域普通技术人员，在不脱离本发明的精神和范围内，当可作各种更动与润饰，因此本发明的保护范围当视权利要求书界定的范围为准。