一种分布式的无线传感器网络拓扑重构方法

摘要

本发明公开了一种分布式的无线传感器网络拓扑重构方法，包括：初始配对阶段，每个支援节点通过所获取的局部信息与网络中的失效固定节点进行一一配对；从任意一个支援节点开始，该支援节点选择距离自己最近的失效节点进行初始配对；配对调整阶段，每个支援节点通过与其通讯可达支援节点交流配对信息进行配对调整；若两个支援交换彼此的初始配对失效节点将使它们移动的总距离缩短，则它们将交换彼此的初始配对节点；每两个支援节点之间进行配对交换都会使两者的移动距离减少，因此所有支援节点的移动总距离也减少，在所有支援节点完成上述过程之后，将得到所设前提下的最优分配结果。通过仿真实验对所提出的方法进行验证和分析。

说明书

技术领域

本发明涉及一种分布式的无线传感器网络拓扑重构方法，能够实现无线传感 器网络中支援节点的优化分配，对网络中的失效节点进行替换和修复，保证网络 的监测性能。

背景技术

无线传感器网络与传统网络相比具有组网方式灵活、监测信息全面、智能化 程度高的特点，是一种全新的信息采集和处理技术，大大地扩展了人类获取信息 的能力。基于无线传感器网络的诸多优点，它在工农业生产、国防军事、交通物 流、医疗卫生、空间探索，以及楼宇管理、灾情预报等多个领域具有广阔的应用 前景和巨大的应用价值。尽管有效的节点部署策略能够在网络初始部署时对网络 监测性能进行优化，然而由于单个节点结构简单、能量有限，常因环境干扰、能 量耗尽等原因而失效，这使网络的拓扑结构发生变化，网络监测性能受到显著影 响。

发明内容

发明目的：针对无线传感器网络中部分节点失效，网络监测性能下降的问题， 如果在出现节点失效时，本发明提供一种分布式的无线传感器网络拓扑重构方 法，利用冗余的支援节点移动到失效节点位置对失效节点进行修复或者替代，从 而改善或恢复网络的监测性能。每个支援节点接收周围固定节点对环境的感知信 息并对它们的状态进行监测，检测是否有失效的节点。当失效节点数目超过能够 维持最低网络覆盖性能要求所允许的失效节点数目时，支援节点将与失效节点进 行配对修复或者替代。为了节约能量，每个支援节点将限制自身的通讯距离，只 能与其通讯范围内的节点进行信息传递，同时与其通讯范围内的支援节点交换失 效节点的信息并进行优化配对。虽然由于仅基于局部的节点信息，该算法可能不 能得到节点分配的最优结果，但不需要依赖于单一的汇聚中心来收集网络全局信 息，为网络的实际应用提供了方便。

技术方案：一种分布式的无线传感器网络拓扑重构方法，所述无线传感器网 络包括多个无线传感器节点，简称节点。节点根据是否具有移动能力分为固定节 点和支援节点。固定节点被部署在网络中后始终处于活跃状态，在网络运行过程 中会因能量耗尽及外界干扰而失效。支援节点在网络初始部署时处于休眠状态以 节约能量，在出现固定节点失效的情况下可以转为活跃状态，用于修复失效的固 定节点。

一、网络特点说明

(1)任一节点i都能进行全方向感知，其覆盖范围是一个以节点为圆心，以 节点的感知距离r为半径的圆，即

(2)任一节点i都能进行全方向通讯，其通讯范围是一个以节点为圆心，以 节点的通讯距离R为半径的圆，即

(3)所有节点的感知距离r和通讯距离R分别相同；

(4)所有节点满足R≥2r的条件；

(5)所有节点具有位置意识；

(6)所有节点都在同一个二维平面内。

二、节点优化分配方法

每个支援节点都可以获得自身周围的信息，所有支援节点通力合作收集所有 失效节点信息。当网络覆盖性能低于应用需求时，支援节点将主动与失效节点进 行配对并对其进行修复。为了节约能量，每个支援节点将限制自身的通讯距离， 只能与其通讯范围内的节点进行信息传递，同时与其通讯可达支援节点交换失效 节点的信息并进行优化配对。虽然由于仅基于局部的节点信息，该算法可能不能 得到节点分配的最优结果，但不需要依赖于单一的汇聚中心，为网络的实际应用 提供了方便。

为便于说明，定义某一支援节点u的通讯可达支援节点集合如下： $N_c^u=\{v\in M|D(u,v)\le R,v\ne u\}---\left(1\right)$

其中，D(u,v)表示支援节点u与支援节点v之间的欧氏距离。R表示支援节点的 通讯距离。显然地，支援节点的通讯连通关系与R的大小密切相关。通常情况下， R越大，每个支援节点的通讯可达支援节点越多，所能获得的网络信息越多，越 容易得到较优的节点分配结果。当然，R的大小也受到支援节点能量的限制。

基于上述说明，每个支援节点接收周围固定节点对环境的感知信息并对它们 的状态进行监测，检测是否有失效的节点。当失效节点数目超过能够维持最低网 络覆盖性能要求所允许的失效节点数目时，每个支援节点将按照如下的分布式次 优节点分配方法进行节点配对，具体步骤为：

1)初始配对阶段。在这一过程中，每个支援节点通过所获取的局部信息与网 络中的失效固定节点进行一一配对。从任意一个支援节点开始，该支援节点选择 距离自己最近的失效节点进行初始配对，且尽量选择距离自己最近的感知可达失 效节点进行初始配对。然后，下一个支援节点在剩余未配对的失效节点中选择距 离最近的节点进行初始配对。按照这种原则，所有支援节点逐一与失效节点进行 初始配对。最后，每个支援节点都有一个初始配对的失效节点与其一一对应。

2)配对调整阶段。在这一过程中，每个支援节点通过与其通讯可达支援节点 交流配对信息进行配对调整。若两个支援节点发现，如果它们交换彼此的初始配 对失效节点将使它们移动的总距离缩短，则它们将交换彼此的初始配对节点。具 体地，以支援节点u为例，这一过程可描述如下：设支援节点u在初始阶段的配 对节点为失效节点j_u，支援节点u的某一通讯可达支援节点v的初始配对失效节 点为j_v。用表示支援节点u与失效节点j_u之间的欧式距离，为支援节点 v与失效节点j_v之间的欧式距离，表示支援节点u与失效节点j_v之间的欧式 距离，为支援节点v与失效节点j_u之间的欧式距离。若式(2)成立，则支援节 点u与v将交换各自的初始配对节点，否则u将保持现有配对状态。

$w_{u,j_u}+w_{v,j_v}>w_{u,j_v}+w_{v,j_u}---\left(2\right)$

支援节点u将逐一对其通讯可达支援节点集合中的所有节点重复上述配对调 整过程，直到移动距离不再减少为止。在所有支援节点完成上述过程之后，将得 到所设前提下的最优分配结果。

显而易见，每两个支援节点之间进行配对交换都会使两者的移动距离减少， 因此所有支援节点的移动总距离也减少，这意味着移动总距离是随支援节点之间 配对调整通讯次数增加的递减函数。由于移动总距离必然大于0，即移动总距离 函数的下界为0，因此，移动总距离将会在支援节点之间有限的配对通讯次数之 后收敛到最小值。然而，需要说明的是，由于该方法仅基于网络局部信息，同时， 支援节点与失效节点的初始配对具有很大的随机性，并且受到假设条件的限制， 因此在理论上，尽管每次配对调整通讯都会使得总距离减小，但不能保证所得节 点配对结果是所有可能配对中的最优结果，即最终获得的节点分配结果的移动总 距离值不一定为最小。

本发明采用上述技术方案，具有以下有益效果：能够充分利用网络中的剩余 节点资源对网络拓扑结构进行重新调整，即通过网络拓扑重构来改善网络的监测 性能，不仅可以最大程度地延长网络寿命，还可以显著提高网络的自适应性和容 错性，这对于无线传感器网络的实际应用是十分有意义的。

附图说明

图1为网络中出现节点失效时的初始情况图；

图2为本发明实施例的节点分配的初始情况图；

图3为本发明实施例中R＝4r(20m)时支援节点的连通图；

图4为本发明实施例的20个失效节点被修复的节点分配情况图；

图5为随机拓扑结构的网络图；

图6为随机拓扑结构的网络有节点失效的情况图；

图7为本发明实施例的节点分配的初始情况图；

图8为本发明实施例的20个失效节点被修复的节点分配情况图。

具体实施方式

下面结合具体实施例，进一步阐明本发明，应理解这些实施例仅用于说明本 发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发 明的各种等价形式的修改均落于本申请所附权利要求所限定的范围。

分布式的无线传感器网络拓扑重构方法，利用冗余的支援节点移动到失效节 点位置对失效节点进行修复或者替代，从而改善或恢复网络的监测性能。

一、网络特点说明

(1)任一节点i都能进行全方向感知，其覆盖范围是一个以节点为圆心，以 节点的感知距离r为半径的圆，即

(2)任一节点i都能进行全方向通讯，其通讯范围是一个以节点为圆心，以 节点的通讯距离R为半径的圆，即

(3)所有节点的感知距离r和通讯距离R分别相同；

(4)所有节点满足R≥2r的条件；

(5)所有节点具有位置意识；

(6)所有节点都在同一个二维平面内。

二、节点优化分配方法

每个支援节点都可以获得自身周围的信息，所有支援节点通力合作收集所有 失效节点信息。当网络覆盖性能低于应用需求时，支援节点将主动与失效节点进 行配对并对其进行修复。为了节约能量，每个支援节点将限制自身的通讯距离， 只能与其通讯范围内的节点进行信息传递，同时与其通讯可达支援节点交换失效 节点的信息并进行优化配对。虽然由于仅基于局部的节点信息，该算法可能不能 得到节点分配的最优结果，但不需要依赖于单一的汇聚中心，为网络的实际应用 提供了方便。

为便于说明，定义某一支援节点u的通讯可达支援节点集合如下：

$N_c^u=\{v\in M|D(u,v)\le R,v\ne u\}---\left(1\right)$

其中，D(u,v)表示支援节点u与支援节点v之间的欧氏距离。R表示支援节点的 通讯距离。显然地，支援节点的通讯连通关系与R的大小密切相关。通常情况下， R越大，每个支援节点的通讯可达支援节点越多，所能获得的网络信息越多，越 容易得到较优的节点分配结果。当然，R的大小也受到支援节点能量的限制。

基于上述说明，每个支援节点接收周围固定节点对环境的感知信息并对它们 的状态进行监测，检测是否有失效的节点。当失效节点数目超过能够维持最低网 络覆盖性能要求所允许的失效节点数目时，每个支援节点将按照如下的分布式次 优节点分配方法进行节点配对，具体步骤为：

1)初始配对阶段。在这一过程中，每个支援节点通过所获取的局部信息与网 络中的失效固定节点进行一一配对。从任意一个支援节点开始，该支援节点选择 距离自己最近的失效节点进行初始配对，且尽量选择距离自己最近的感知可达失 效节点进行初始配对。然后，下一个支援节点在剩余未配对的失效节点中选择距 离最近的节点进行初始配对。按照这种原则，所有支援节点逐一与失效节点进行 初始配对。最后，每个支援节点都有一个初始配对的失效节点与其一一对应。

2)配对调整阶段。在这一过程中，每个支援节点通过与其通讯可达支援节点 交流配对信息进行配对调整。若两个支援节点发现，如果它们交换彼此的初始配 对失效节点将使它们移动的总距离缩短，则它们将交换彼此的初始配对节点。具 体地，以支援节点u为例，这一过程可描述如下：设支援节点u在初始阶段的配 对节点为失效节点j_u，支援节点u的某一通讯可达支援节点v的初始配对失效节 点为j_v。用表示支援节点u与失效节点j_u之间的欧式距离，为支援节点 v与失效节点j_v之间的欧式距离，表示支援节点u与失效节点j_v之间的欧式 距离，为支援节点v与失效节点j_u之间的欧式距离。若式(2)成立，则支援节 点u与v将交换各自的初始配对节点，否则u将保持现有配对状态。

$w_{u,j_u}+w_{v,j_v}>w_{u,j_v}+w_{v,j_u}---\left(2\right)$

支援节点u将逐一对其通讯可达支援节点集合中的所有节点重复上述配对调 整过程，直到移动距离不再减少为止。在所有支援节点完成上述过程之后，将得 到所设前提下的最优分配结果。

显而易见，每两个支援节点之间进行配对交换都会使两者的移动距离减少， 因此所有支援节点的移动总距离也减少，这意味着移动总距离是随支援节点之间 配对调整通讯次数增加的递减函数。由于移动总距离必然大于0，即移动总距离 函数的下界为0，因此，移动总距离将会在支援节点之间有限的配对通讯次数之 后收敛到最小值。然而，需要说明的是，由于该方法仅基于网络局部信息，同时， 支援节点与失效节点的初始配对具有很大的随机性，并且受到假设条件的限制， 因此在理论上，尽管每次配对调整通讯都会使得总距离减小，但不能保证所得节 点配对结果是所有可能配对中的最优结果，即最终获得的节点分配结果的移动总 距离值不一定为最小。

三、仿真分析

3.1规则拓扑结构网络

本发明基于MATLAB7.0平台对上述所提算法进行仿真验证，传感器节点的 感知距离均为r＝5m，所有节点以的间隔被规则地部署于被监测区域中， 被监测区域面积为假设在某一重构周期内，网络中有20个固定 节点失效，如图1所示，图中“×”表示失效节点。

在仿真中，考虑对所有20个失效固定节点进行修复时的支援节点的分配策 略。首先，根据分布式节点分配策略的步骤，支援节点按随机顺序进行初始配对。 如图2所示，首先进行初始配对的支援节点为14，它选择距离自己最近的感知 可达失效节点10作为初始配对节点。仿真中，接下来进行初始配对的支援节点 序列为：17，4，20，9，18，3。它们的初始配对失效节点序列为：15，36，22， 25，28，41。从图2可以看到，以上支援节点均选择了距离各自最近的失效节点 作为初始配对节点，其中大部分选择了距离各自最近的感知可达失效节点。接着， 支援节点11进行初始配对，它首先考虑距离自己最近的感知可达失效节点10， 但是由于失效节点10已经与支援节点14进行了初始配对，因此支援节点11不 得不选择除了失效节点10之外距离自己最近的失效节点9。同样，在接下来支 援节点2，13，19，15，6的初始配对过程中也遇到了与支援节点11相同的情况。 所有支援节点的初始配对结果如图2所示。

如前所述，支援节点之间的连通情况与R的大小密切相关。直观上，R越大， 每个支援节点的通讯可达支援节点越多，相互之间能够获得的信息越多，进行配 对调整的机会也越多，因此越容易得到较优的节点分配结果。但是，支援节点的 R应该在能够达到较优的节点分配结果的情况下尽量小，以节约节点能量。因此， 这里对支援节点连通情况及节点分配结果与R的关系进行了研究。基于R≥2r的 假设，分别取R为2r、3r、4r、5r、6r，在如图2中所示的节点初始配对情 况下，对R取不同值时支援节点连通情况及节点分配结果进行比较，结果如表1 所示。表中，配对调整时支援节点通讯次数表示当R取当前值时，在配对调整阶 段中所有支援节点的移动总距离达到最小值时，所有支援节点之间通讯的总次 数。由表可知，随着R增大，每个支援节点的通讯可达支援节点数增多，所以所 有支援节点的通讯总次数也逐渐增大，但在R＝4r后变化幅度很小。相应地，配 对调整后所有移动支援节点中单个支援节点移动距离的最大值在R＝4r时显著 减小后不再变化，所有支援节点移动总距离在R＝4r前显著减小，但在R＝4r后 变化缓慢。这是因为当R刚开始增大时，随着支援节点的通讯可达支援节点增多， 每个支援节点与其他节点进行配对交换的机会也增多，所以通讯次数增多，配对 调整后单个支援节点的移动距离最大值以及所有支援节点移动总距离减小。但 是，当R增大到一定程度时，由于网络拓扑结构和节点初始配对结果是确定的， 因此即使支援节点的通讯可达支援节点数增加，在配对调整时经过一定次数的初 始配对交换，网络中当前的节点配对都不满足交换条件，相应的配对结果不会再 发生变化。综上，从重构后网络的监测性能及支援节点能耗两个角度考虑，R＝4r 时的结果最好。在下面的仿真中，假设每个支援节点的通讯距离均为R＝4r，此 时所有支援节点的连通关系如图3所示。

表1支援节点连通情况及节点分配结果与R的关系

在配对调整阶段，基于上述初始配对结果及支援节点的通讯拓扑关系，每个 支援节点与自己的通讯可达支援节点交流初始配对信息，并对初始配对结果进行 调整。图4所示为利用分布式节点分配方法所能得到的最优的分配结果。采用分 布式方法时，移动总距离将很快收敛于次优值149.1501m。虽然分布式算法难以 获得全局最优结果，但是由于其不需要依赖单一的汇聚中心来对支援节点和失效 节点进行优化配对，而是充分利用支援节点通过局部信息的传递与交换完成节点 配对，从而使得网络在分布式的信息传递情况下具有更高的自适应能力。

3.2随机拓扑结构网络

图5为随机拓扑结构的网络，传感器节点的感知距离均为r＝5m，所有节点 随机地部署于被监测区域中，被监测区域面积为(50×50)m²，图中“○”表示支 援节点。假设在某一重构周期内，网络中有20个固定节点失效，如图6所示，图 中“×”表示失效节点。

这里，首先进行初始配对的支援节点为3，它选择距离自己最近的失效节点 39作为初始配对节点。显然，在初始配对阶段，大部分支援节点能够与它们最近 的失效节点配对。然而，由于支援节点1，2，8，9，14，17的最近的失效节点已 分别与其他支援节点先完成了初始配对，因此，它们与最终初始配对的失效节点 之间的距离明显大于其他配对节点。

仍然设R＝4r，所有支援节点在初始配对完成之后与它们的通讯可达支援节 点之间交换配对信息。图8为分布式方法在图7的初始配对情况下所能获得的最优 配对结果。由图中可以看出，经过配对交换之后大部分支援节点与最终配对的失 效节点之间的距离与初始配对时大大缩短。由于分布式方法不需要依赖单一的汇 聚中心来获得网络全局信息，因此增强网络网络的自组织能力和智能化程度。