基于Voronoi 图的无线传感网络覆盖盲区检测方法

陈振峰，陈纪鑫

(1.广州番禺职业技术学院财经学院，广东 广州 511483；2.华南理工大学建筑学院，广东 广州 510614)

近年来，无线传感网络(Wireless Sensor Network，WSN)[1]逐渐普及到人类生活的各行各业，成为当今社会的研究热点。公共区域监控、黑客入侵检测、智能机械操作、智慧城市建设均离不开无线传感网络的参与，可见无线传感网络已成功依靠其优质的网络服务质量和高效的节点传输能力，成为21 世纪最有价值的计算机科研项目之一。然而无线传感网络内部分节点长期处于无覆盖的活跃度低迷的休眠状态，对网络的连通性造成不可估量的影响。因此，相关的无线传感网络覆盖盲区检测与修复研究引起了学者的关注。

王寒露等[2]通过超声检测方法对扩散场扇扫重建，并利用10 MHz 超声相控阵探头搜查重建区域的时间宽窗，以获取有效扩散时间内较为全面的网络近表面盲区缺陷。但是该方法存在检测效率低的问题。Iqbal 等[3]提出了基于复回波状态网络预测原理的正交幅度调制信号在线盲均衡算法。通过调整振幅和相位，实现由非线性信道引起的传输信号失真检测。但是该方法存在检测场景受限的问题。李志军等[4]通过孤岛检测方法将无线传感网络节点映射至Q×C坐标系中，并利用真实校验方法获取坐标系内单位节点的负载品质因数，通过观察横、纵坐标下各节点的负载品质因网络覆盖盲区检测数对应的节点活跃度，实现无线传感网络覆盖盲区检测。但是该方法存在检测能耗高的问题。董鑫等[5]提出了装有鱼眼镜头的传感器网络连通保持覆盖控制策略。在建立有向视觉传感器节点覆盖性能函数的基础上，利用控制器约束节点的转动角度、运动步长，从而确保整个网络的连通性，以此提升覆盖连通度，减少盲区的产生。但是该方法主要针对的是优化传感器连通度提升策略，对其应用后是否依旧会产生覆盖盲区，盲区出现数量等问题未进行分析。Kishk 等[6]利用可重构智能表面技术在移动用户和没有直接视线信道的基站之间提供间接视线链路。通过提供额外的间接视线链路来提高蜂窝网络的覆盖概率。但是该方法受节点冗余度影响，造成覆盖检测能耗较高。蒋世华等[7]提出了基于轴面对称机制的物联网节点覆盖算法。该方法通过对称分布簇头节点分割物联网，以提高覆盖效率。利用镜像节点、簇头轮询方法增强网络传输能力。该方法降低了簇头受限概率，但是受盲区的影响，造成检测能耗较高。

为了提高无线传感网络通信效率，准确检测盲区，提出基于Voronoi 图的无线传感网络覆盖盲区检测方法。

1 无线传感网络覆盖率

从宏观视角观察无线传感网络，其由传感器节点[8]和网络用户共同组成。想要检测无线传感网络覆盖盲区，需要优先了解无线传感网络节点的分布关系和网络大体覆盖情况。

1.1 无线传感网络节点的分布关系

根据无线传感网络几何判定理论可知，无线传感网络中的节点[9]不是无规则散乱分布，而是遵循极坐标平面极轴关系以三角形及三角形外接圆半径的形式首尾相连。这种有规律的分布形式能够最大限度提升节点间的通信半径T和感知半径U:

式中:f2表示无线传感网络选定平面的坐标原点；s表示相邻节点的欧氏距离；d表示三角形边长；i表示外接圆半径；lo表示目标范围内的节点数量；l3表示节点虚拟距离；l5表示节点移动步长；τ表示无线传感网络通信执行次数。

无线传感网络节点分布关系如图1 所示。

图1 无线传感网络节点分布关系

1.2 无线传感网络覆盖情况

在成功了解无线传感网络节点分布关系的基础上，推测无线传感网络大体覆盖情况。考虑到单个节点不受通信半径和感知半径的约束，能在初始能量的支持下围绕稳态范围移动，且网络节点分布关系在节点周期性运行途中不会发生离散现象。在推测无线传感网络大体覆盖情况时，需要追踪传感器节点运行轨迹，并在不干扰传感器节点拓扑结构的同时，沿追踪路径构建栅栏[10]，使传感器节点在运行过程中覆盖的网络区域得以保留。

传感器节点作为暴露在网络通信地带，随不同应用场合改变二维空间曲线的信息传输载体，能够通过解耦合的方式移动节点传输贡献量[11]对应的欧几里德距离，实现传感器节点的周期性运行。正常情况下，传感器节点的邻近节点受到节点分布关系的限制，必须保持固定部署位置完成网络通讯任务。这种限定条件使得传感器节点在一次运行周期内的传输贡献量固定不变，极大程度降低了节点运行轨迹的追踪难度。极坐标[12]不同于传统二维坐标，其坐标系极角升序排列关系与无线传感网络节点分布关系一一对应，将无线传感网络与极坐标结合，通过追踪坐标系内传感器节点的运行轨迹，即可实现实际应用中网络节点运行轨迹的追踪。传感器节点传输贡献量，如式(2)所示:

式中:T表示节点通信半径；U表示节点感知半径；xi表示放置策略；n表示无线传感网络顶端和底端的中心位置；表示节点冗余度；u表示节点在目标区域中的最小收敛时速。

传感器节点解耦合，如式(3)所示:

式中:ceil(·)表示取整函数，∂表示跟踪过程中传感器节点理想轨迹偏移率；c表示传感器节点垂足坐标；x表示传感器节点备选路段。

极坐标中传感器节点在横、纵坐标上移动的欧几里德距离，如式(4)所示:

式中:σ表示节点传输贡献量在横坐标上的对应位移；qn表示节点传输贡献量在纵坐标上的对应位移；qn＋1表示全轨迹划分交点数；q2表示传感器源点和目的地的垂直距离；η表示无线传感网络的全局拓扑信息；sn表示邻近节点的联通半径；sm表示起点集合节点数量；f3表示终点集合节点数量；B表示同构节点数据传输速率。

在成功获取传感器节点运行轨迹的基础上，沿追踪路径构建栅栏。根据Gage 机器人在网络通信背景下获取的有效追踪检测区域内节点移动轨迹，可知传感器节点的运行轨迹多呈现多边形结构，因此在沿途构建栅栏过程中，应优先确定多边形结构的形心位置，以达到网络覆盖区域的无穷方向取整估算。多边形结构形心位置，如式(5)所示:

式中:Δω表示多边形面积；z表示节点多数性能指标；Δj表示虚线圆圆心所标记的中心位置；r表示传感器节点当前位置。

栅栏公式如式(6)所示:

多边形结构的二维平面图如图2 所示。

图2 多边形结构的二维平面图

栅栏能够保留传感器节点运行途中覆盖的网络区域，通过统计栅栏在平面中的全部位置，即可得到无线传感网络的大体覆盖情况。

2 无线传感网络覆盖盲区检测

Voronoi 图[13]又称Dirichlet 图，是由来自俄国的Voronoi Diagram 教授就几何晶体、信息系统、建筑理论等一系列问题提出的全景分割算法[14]，该算法因其优越的网络空间分割能力和节点调度能力被广泛应用于各种科研领域当中。由于Voronoi 图与无线传感网络节点运行轨迹在行为逻辑表现出高度一致性，Voronoi 图也常被应用于无线传感网络相关的研究当中。采用Voronoi 图检测无线传感网络覆盖盲区的基本思路围绕排除已覆盖区域和具备检测条件的未覆盖无线传感网络空洞特征展开。

2.1 排除已覆盖区域

掌握了无线传感网络的大体覆盖情况，以此为基础，在Voronoi 图的指导下通过排除已覆盖区域，获取具备检测条件的未覆盖无线传感网络空洞，其具体过程如下:首先将无线传感网络与Voronoi 图结合，然后过滤已覆盖区域。考虑到无线传感网络已覆盖区域和未覆盖区域存在数学理论和物理特性的差异，在获取网络空洞的过程中，应忽略两区域差异引发的节点感知强度和通信能力随节点活性丧失而产生的能量损耗，如式(7)所示:

式中:kϑ表示已覆盖区域和未覆盖区域的垂直平分线；t3表示两区域的数学理论差异；t6表示两区域的物理特性差异；yn表示覆盖区域的节点数量；ym表示空洞节点数量；α表示节点感知精度；ε2表示已覆盖区域的节点稀疏性。

无线传感网络空洞的表达式:

式中:ψk表示空洞圆盘面积；δ表示取余数；e表示空洞圆心距。

2.2 未覆盖无线传感网络空洞特征

未覆盖的无线传感网络空洞之所以具备盲区检测价值，是因为其空洞暴露程度和节点能量均与已覆盖的无线传感网络不同，即未覆盖的无线传感网络空洞具有检测效果显著的盲区特征。以上述无线传感网络空洞为基础，分别计算空洞区域的暴露程度和节点能量，作为检测无线传感网络覆盖盲区的特征样本。空洞区域暴露程度，如式(9)所示:

式中:κ表示空洞区域内节点的给定HBN 序列；γ2表示邻近节点覆盖矛盾；b表示空洞有向链路；hij表示空洞数量。

空洞区域节点能量，如式(10)所示:

式中:p2表示顺时针节点序列；dij表示负无穷方向取整；cosμ表示目标点到空洞区域的最近距离。

粒子群分类器[15]是由粒子群编码和分类规则适应度共同组成的择优信任匹配算法，常被应用于多种领域的数据集分类工作中。将空洞区域的暴露程度和节点能量作为特征样本输入粒子群分类器中，根据分类器的输出结果，即可实现无线传感网络覆盖盲区的有效检测。粒子群分类器如式(11)所示:

式中:pvj表示粒子的适应度；dirs表示粒子的速度；I表示分类器迭代次数。

粒子群分类器检测特征样本的表达式，如式(12)所示:

式中:ζ表示特征样本均匀性；sinθi表示矛盾数据剔除率；cosθj表示特征样本分类敏感度。根据上述过程中，实现基于Voronoi 图的无线传感网络覆盖盲区检测，并将其总结为下述步骤:

步骤1:明确无线传感网络节点的分布关系和当前覆盖情况；

步骤2:融合无线传感网络与Voronoi 图:忽略已覆盖区域和未覆盖区域差异引发的节点感知强度和通信能力随节点活性丧失而产生的能量损耗上，根据式(8)获取无线传感网络空洞，并利用Voronoi图生成无线传感网络覆盖盲区示意图；

步骤3:计算空洞区域的暴露程度和节点能量，作为检测无线传感网络覆盖盲区的特征样本；

步骤4:将获取的特征样本输入粒子群分类器中，根据式(11)输出无线传感网络覆盖盲区检测结果。

3 仿真与结果

为了验证基于Voronoi 图的无线传感网络覆盖盲区检测方法的整体有效性，需要对其进行测试。

3.1 仿真设置

利用MATLAB2020B 软件，在200 m×200 m 的无线传感网络区域中，以20 m 为节点通信半径随机部署10×105 个传感器节点。在无线传感网络中采取随机部署的方式，部署传感器节点，由于所使用路由算法、环境等因素的影响，导致部分节点失效，造成无线传感网络存在覆盖盲区。其他相关参数如表1所示，无线传感网络覆盖盲区如图3 所示。

表1 仿真环境的相关参数

图3 无线传感网络覆盖盲区示意图

图3 矩形区域是需要被无线传感网络传感器检测的目标区域，灰色的部分为覆盖盲区。

3.2 仿真结果分析

根据上述参数设置，将文献[2]扩散场扇扫重建格林函数实现近表盲区缺陷检测方法、文献[3]基于复回波状态网络预测的覆盖盲区检测方法作为对比方法进行测试，结果如下。

3.2.1 检测效率

分别采用所提方法、文献[2]方法和文献[3]方法检测设定仿真环境的覆盖盲区数量，分别为5、15、20、25、30 个，并记录不同方法的检测时长，每种情况下分别进行多次运算，取其时间平均值，得到的结果如图4 所示。

图4 不同方法的检测时长

如图4 可见，采用所提方法检测无线传感网络覆盖盲区，其检测时长仅有0.2 s，说明所提方法的效率较高。因为所提方法以无线传感网络大体覆盖情况为基础，在Voronoi 图的指导下通过排除已覆盖区域，获取具备检测条件的未覆盖无线传感网络空洞，并将网络空洞的暴露程度和节点能量作为样本特征输入粒子群分离器中，进一步提高了检测结果的可信度和检测效率。采用文献[2]方法和文献[3]方法检测无线传感网络覆盖盲区，二者检测时长均与所提方法存在较大差距，说明文献[2]方法和文献[3]方法的效率较低。经上述对比，可知所提方法的检测效率明显优于对比方法。

3.2.2 检测能耗

在算法检测过程中，参与检测的无线传感网络面积越大、节点数量越多，检测所消耗的能耗越高。检测能耗的增高不仅会使算法冗余信息处理误差升高，还会增加检测负担，使检测效率大幅度下降。分别采用所提方法、文献[2]方法和文献[3]方法检测上述仿真环境的覆盖盲区，并记录无线传感网络检测面积增大的过程中，节点数量为10×102、10×103、10×104、10×105时的检测能耗，上述数量分别标记为A～D。以检测能耗为指标，判断不同方法应用后的盲区检测性能。不同方法的检测能耗如图5所示。

图5 不同方法的检测能耗

由图5 可见，采用所提方法检测无线传感网络覆盖盲区，随着网络检测面积的增大、节点数量的增多，其检测能耗正比上升，且始终不超过20 J，说明所提方法的检测能耗不仅稳定，而且维持在较低水平，不会由于计算负担增大而产生检测效率低下等问题。采用文献[2]方法和文献[3]方法检测无线传感网络覆盖盲区，随着网络检测面积的增大、节点数量的增多，二者检测能耗上升明显且无等价关系，说明文献[2]方法和文献[3]方法的检测能耗较高，极易由于计算负担增大而产生检测效率低下等问题。经上述对比，可知所提方法的检测能耗明显优于对比方法。

3.2.3 检测差异度

检测率即所提方法应用后的无线传感网络覆盖盲区检测效果，以检测差异度为指标进行测试。差异度作为反映算法检测结果与实际结果相似度的评估指标，主要用于体现检测结果的精确度。差异度越大，检测结果与实际结果的相似度越小，算法精确度越小；差异度越小，检测结果与实际结果的相似度越大，算法精确度越高。差异度计算公式见式(13):

式中:ξm表示差异度阈值；κ表示检测结果；iimage表示实际结果。

分别采用所提方法、文献[2]方法和文献[3]方法检测上述仿真环境的覆盖盲区，得到不同空洞圆心距下的覆盖盲区检测差异度。结果如图6 所示。

图6 不同方法的差异度

由图6 可见，所提方法检测结果的差异度较低，低于0.24，说明所提方法检测结果与实际结果较为相符。文献[2]方法和文献[3]方法检测结果的差异度较高，说明文献[2]方法和文献[3]方法检测结果与实际结果的相似度较小。经上述对比，可知所提方法的检测精确度明显优于对比方法。

4 结束语

无线传感网络是具有节点组织性、通信可靠性、联通自主性的高功能无线覆盖网络。为了使无线传感网络不受覆盖盲区的阻碍，提出基于Voronoi 图的无线传感网络覆盖盲区检测方法。在明确无线传感网络空洞覆盖情况的基础上，利用Voronoi 图排除已覆盖区域，提取未覆盖无线传感网络空洞。通过将空洞暴露程度和节点能量输入粒子群分离器中，实现无线传感网络覆盖盲区检测。仿真结果表明，所提方法在提高网络覆盖盲区检测效率的同时，降低了检测能耗和检测差异度。由此验证了所提方法可以有效提高无线传感网络节点通信能力，减少覆盖盲区对通信质量造成的影响。实时监控网络覆盖盲区检测过程，将是研究人员下一步工作的重点。