水下传感器网络自组织连通恢复仿真

赵高丽，宋军平

(1.河南科技学院信息工程学院，河南 新乡 453003；2.武汉理工大学信息工程学院，湖北 武汉 430070；3.河南科技学院新科学院，河南 新乡 453003)

1 引言

水下传感器网络最引人注目的是可以在无人值守的水下严酷环境里工作、减少人力成本，同时提供一种完全自动化的数据收集系统，在水下传感器网络应用里，传感器节点的处理能力是有限的，因此期望部署的传感器组成了一种连通的网络，在运行任务时，互相协作，把采集到的数据输送至基站，因为传感器节点的能量来源是电池供电设备，导致水下传感器会受到能量耗尽导致设备停运的影响，并且，水下恶劣环境与恶意攻击也容易使节点出现大规模损坏，在这些情况中，水下传感器网络的通信就容易断开，数据的传输就会收到限制。对此国内外学者提出了以下解决方法。

文献[1]使用拓扑分析法对传感器检测，确定受损区域，并更新主网络拓扑参数，之后通过孤岛方案提升DG的利用率同时恢复最大负荷量，最后将DG并网从而恢复传感器网络连通。但是该方法只是单纯的通过检测来判断受损区域，并未对受损区域进行划分，在恢复时这就需要对所有水下传感器区域进行检测，导致资源大量消耗。文献[2]通过谱类算法对传感器网络的拓扑结构优化，进而缩短连通恢复的时间，之后构建恢复路径与负荷恢复模型，再从连通性恢复时间、路径非连通修正与不确定负荷恢复效率的角度，再次进行针对性优化，最后在融入电压强约束从而完成对传感器网络连通的恢复。但是该方法并没有精准的获得受损坏的传感器区域，这就导致了在最后完成连通恢复后，容易出现传感器网络遗留的问题。文献[3]首先通过联合稀疏分解方法，融合所有传感器受损的信号，并进行分类，进而确定传感器受损的区域，之后提取共通分量，利用信号分块方法，减少起始稀疏度和步长所带来的影响，最后将共通分量融入到受损的传感器网络节点内，进而恢复传感器的连通性。但是该方法只是对网络的连通性数据进行了恢复，并没有对整体传感器进行受损预防和实体恢复，导致后期传感器网络可能会出现二次受损。

上述问题中存在的资源消耗大、损毁检测不精准与二次损坏问题，对此本文提出了一种水下传感器网络自组织连通恢复方法，通过MACRA算法和第二备用节点选择够有效的对传感器网络的自组织连通恢复，并且恢复的效率较高，不会出现大量的资源浪费情况。

2 水下传感器网络自组织连通恢复

2.1 水下传感器网络破坏分析

本文研究的是部署在水下环境内监控指定区域的传感器，节点即静态的，其感知半径与通信半径是不会出现变化的，传感器节点只要位于通信半径的范围里就能够互相通信，并把获得的数据传输至基站内进行对应的处理，传感器节点[4]可以使用相关的定位方法得到自身坐标信息，整体网络使用分簇式层次拓扑结构。

通常情况下，传感器节点有可能因为资源的消耗而失效，但一般状态下只会导致少数的节点失效，如果不干扰网络的连通，就能够不做任何处理；反之也只是需要探测找出对应的失效节点，然后在重新放置节点即可。但在本文关注的水下环境里，除了能量消耗失效外，传感器网络节点也可能会受到水下环境的干扰，导致大规模失效，在此状态下可能会出现整体网络遭到破坏，具体场景如图1所示。

图1 水下传感器网络遭到破坏场景图

在该状态下，实现网络连通[5]要求部署新的节点，不论是特定的用在通信的中继节点，还是新部署和初始节点同样的传感器节点，增加节点同时对其进行部署都是需要大量成本的，所以通过最少的节点来完成网络连通恢复是本文主要目的。把每一个新部署的节点叫做中继节点，同时拟定这些节点在水下同为静止不懂，并拥有相同的通信半径R。传感器网络受到破坏后被划分的独立子网络叫做分区。

在传感器网络划分为多种独立的分区后，节点经过互相通信就可以得到处理相同分区的其它节点[6]信息，同时选择适合的代替节点，把分区拟定成代替节点的位置。网络连通问题拟定成图连通问题，同时拟定n种分区，然后通过网络的全局分区信息，借助特定的巡视装置把分区的信息输送至基站。

2.2 分区搜索和代替节点确定

怎样搜索独立的分区和找到所有分区的代替传感器节点，是在部署中继节点之前就需要解决的两种问题。对此，本文利用构造连通支配集方法建造出所有独立分区的连通子树[7]，通过所有没被破坏的节点确定自身属于的分区，同时了解分区的信息。对于每一个独立的分区，本文取连通子树里节点度最大的节点当做所有分区的代替节点，大致流程如下所示：

首先利用关联分簇方法选择节点，之后簇头节点传输信息至其周围的邻居节点，通过一段时间收敛获得所有邻居节点的回复信息，凭借接收的回复信息取距离簇头节点距离最长的邻居节点当做支配节点。对应的支配节点继续运行上述流程，直至确定所有独立分区的支配集，从而形成多种连通子树。最后取连通子树立节点度最大的节点当做所有分区的代替节点，如果存在多种节点度同等的节点，就取ID最小的节点当做代替节点。

确定了所有分区的代替节点之后，把代替节点的坐标信息和节点的ID传输至分区里所有节点内，使得相同分区所有节点都储存有代替节点的ID与坐标信息。

在巡视装置对所部署监控区进行巡视采集时，巡视装置只要接到分区里任意一种节点就能够得到该分区的代替节点的ID与位置，最后把每一个分区代替节点信息传输至基站。

2.3 MACRA算法描述

本文提出的MACRA算法，即完成水下传感器网络的自组织连通恢复，使用多种节点在多种独立分区之间进行移动，进而将连通恢复。MACRA算法拥有模糊连通恢复机制[8]与精确连通恢复机制两个部分，这两种部分的目标就是找出适合的水下传感器节点和在分区之间定位合适的移动路线终点与起点位置。下面详细描述MACRA的模糊连通恢复机制与精准连通恢复机制。

2.3.1 模糊连通恢复机制

模糊连通恢复首先通过网络分割技术把整体水下传感器网络分割成多种具有一定规则的区域，并使用A1，A2，A3来代替，每种网络点都归属至一种特定的区域Ak，区域的尺寸通过用户的需求来拟定，在网络里多种独立分区组成后对所有分区进行所占区域的编号标记。如图2所示，分区G1占A1与A2两种区域。相较于随机一种独立分区需要选取一种中继分区Gy来完成连通，基站sink能够当做为一种独立的中继分区。

图2 区域划分

MACRA算法的模糊连通机制是以网络区域当做估算单位，首先定位选择连接的两种分区Gx与Gy所占据的区域，对这两种区域的确定需要在两点要求之间进行权衡。这两种要求为两种区域长度尽量短与重新连接[9]方位应该符合现实输送目的，即新的传输方位应该尽可能的偏向基站传输。用数学公式介绍就是选择满足模糊定位函数f1(Gx)最小值的两种区域，函数f1(Gx)表示成

minf1(Gx)=αD(Ai，Aj)+βD(Aj，Ak)

(1)

式中D(Ai，Aj)代表Ai至Aj的欧式长度，D(Aj，Ak)代表Aj至Ak的欧式长度，此处通过区域的中心代替区域的坐标[10]，而α与β即常系数。如图3所示，白色的点表示区域的中心位置，相较于独立分区G3选取G2当做中继分区，而Ai至Aj即水下传感器节点的连接区域。

2.3.2 精准连通恢复机制

模糊定位函数在很大程度上减少了移动节点的选取范围，只需要在大体定位的合适的传感器节点进行辅助移动[11]至指定位置来恢复网络的连通，精准连通恢复机制即同于完成这种目的，大致传感器节点与移动位置的选择综合考虑尺寸与节点局部密度两种因素。相较于随机传感器节点i，以该节点为中心的一种指定范围的圆形区域里，部署的传感器节点的总数量定义成该节点的局部密度，以σi来代替。选取节点的移动长度应该尽量缩短，这样就能够降低传感器节点的移动质量要求，并且移动节点的终点与起点局部密度最好尽量扩大。如果某一种传感器节点的局部密度变大，就证明节点对网络连通性的干扰越小，因为在该节点遭到破坏导致失效后，能够代替该节点的节点数越多，那么该节点对其邻居们的数据传输的干扰越小，该节点对网络的连通性干扰越小。

在运行模糊连通恢复机制之后，Ai与Aj两种区域被拟定成水下移动传感器节点移动的终点位置pi与起点位置pj所处的区域，精准定位函数f2(Gx)表示成

minf2(Gx)=μD(pi，pj)+φ/p(pi)

(2)

minf2(Gy)=μD(pi，pj)+φ/p(pj)

(3)

因此，水下传感器节点的源与目的坐标就在短尺寸与大局部密度之间进行权衡，在节能的同时满足网络的二次抗毁性。如图4所示，G2与G3之间最短的尺寸即M与N点，可是这两种点的坐标并不是本文指定的区域，所以在这两点里的随机[12]一点的邻居节点受到破坏时，那么该水下传感器网络的连通性就会出现二次毁坏的状况。

图4 精准连通恢复机制

2.4 相邻两种节点遭受二次损坏的状况

2.4.1 选择第二备用节点

针对两种相邻节点出现二次损毁的问题，选取备用节点的指标如下所示：

1)两种关键节点不可以互相当做备用节点。

2)两种相邻的节点一种是非关键节点，一种是关键节点时：

假如非关键节点不是关键节点的备用节点，那么就不在需要第二备用节点。

假如非关键节点为关键节点的备用节点，那么从两个节点的共同邻居里挑选出一个第二备用节点；假如两者没有共通邻居，那么就从关键节点里选择一个节点作为第二备用节点。

3)两种相邻的节点都为关键节点时：

如果两种节点都含有自己独立的备用节点，那么不需要选取第二种备用节点。

如果两种相邻的挂件节点里一种即另一种的备用节点，那么需要选取第二种备用节点。

2.4.2 基于二次损坏的连通性恢复

针对水下传感器网络里两种节点出现二次损坏的状况，有一下几种场景：

1)关键节点n1就是二次损毁的两种相邻节点，n2为非关键节点：

①假如n2不是n1的备用节点，那么n1的备用节点传输至n1的坐标就能够对二次损坏的连通性进行恢复。如图5里非关键节点N与关键节点M出现二次损坏，M的备用节点I转移至M坐标即能够恢复网络连通性。

②如果n2代表n1的备用节点，那么就检测第二备用节点的故障，并开始恢复连通性。如图5里其备用节点R与关键节点L出现二次损坏，那么就通过第二备用节点X搜索非关键节点。进而获得非关键节点C，如果得到非关键节点C，X，C就转移至L级联移动。

图5 二次损坏连通性恢复

2)两种节点n1，n2遭受二次损坏，并且节点都是关键节点：

①如果n1，n2都存在自己单独的备用节点，同时都含有非关键节点，那么平行移动自身至相应的损坏节点就能够恢复连通性。

②如果n1，n2都存在自己单独的备用节点，同时两个节点分别为关键节点与非关键节点，那么将非关键节点传输至关键节点的位置。之后运行非关键节点的搜索算法，从而获得非关键节点，最后运行级联移动，进而恢复网络连通性。

③假如n1，n2都含有单独的备用节点，同时都是关键的节点，那么两种备用节点就同时使用非关键节点的搜索流程。经过防止冲突方式，搜索路径里的每一个节点，如此反复知道完成搜索。

④如果n2是n1的备用节点，那么第二备用节点与n2的备用节点检测到二次损坏出现，激活非关键节点的搜索流程。如图5备用节点R与其关键节点L出现二次损坏，R的备用节点S找出R损坏，因为S即非关键节点，那么直接转移至R坐标即可，节点R，X被第二备用节点B检测到L损坏，并且找到非关键节点Q，然后Q，C，X往L级联转移。

3 仿真证明

仿真环境为Intel Celeron Tulatin1GHz CPU和384MB SD内存的硬件环境和MATLAB6.1的软件环境。

为了证明本文方法的实用性，在水下环境1m*1m的范围里随机安放100种节点，并将其划分为

1)移动尺寸，因为移动会耗费大量的水下传感器资源，因此将水下传感器的移动路径最小化也是本文方法的设计目标之一。

2)最大移动尺寸，水下传感器完成一种最短循环T所移动的最大尺寸L，假如L尺寸过大，就会导致自组织连通恢复出现延迟，因此需要最小化L。

在已经拟定完聚类数量的前提下，把本文方法与文献[1]、文献[2]方法进行对比，文献方法的大体思想即在节点组成指定的数目集群后，每一种集群里选取一种收集点，通过最小生成树对移动路径进行估算，达到水下传感器网络节点移动最小化，进而节省节点的消耗。

表1 不同方法的移动总尺寸对比

通过表1能够看出，本文方法要优于文献方法，就是在水下传感器网络速度确定的状态下，可以更好的恢复网络的自组织连通性，同时节点组成六个集群时，本文方法明显好过文献方法。图6为实验图像。

图6 不同方法的移动总尺寸

表2是两种方法的最大移动尺寸的对比。

表2 不同方法最大移动尺寸对比

通过表2能够看出，本文方法在连通恢复效率上高过文献方法，水下传感器网络运行的速度更快，其实验图像如图7所示。

图7 不同方法最大移动尺寸对比

通过表1、2的实验结果能够得知，在已组成指定聚类数量的前提下，本文方法能够更快的对水下传感器网络自组织连通进行恢复，并且消耗的资源较少，更适合处理在水下环境内无人值守的传感器网络节点大规模损坏的恢复情况。

4 结论

针对水下传感器连通受损恢复的问题，本文提出了一种水下传感器网络自组织连通恢复方法，通过分析水下传感器网络，确定传感器网络节点的中继节点，然后使用MACRA算法对水下传感器网络分块，以及节点密度计算进而恢复传感器网络的连通，并且为了防止二次破坏，还利用拟定阈值来选择传感器网络的备用节点，使传感器网络即使遭受二次损坏也能够及时的对其进行恢复。