无线传感器网络山地三维环状栅栏覆盖算法*

郭新明，陈 伟，谢 飞，李 康

(1．咸阳师范学院 计算机学院，陕西 咸阳 712000；2.西安电子科技大学 前沿交叉研究院，陕西 西安 710068)

0 引 言

随着网络技术、传感器技术、微电子等技术的不断发展，无线传感器网络(wireless sensor networks，WSNs)技术及其应用已经成为目前的研究热点，栅栏覆盖是WSNs覆盖技术中一个重要研究方向，该技术重点关注如何能有效监测穿越WSNs覆盖区域的入侵对象[1]。栅栏覆盖技术如今已经被广泛地应用到工业控制、智慧农业、安保防御及军事监测等范畴。栅栏覆盖的概念是由Gage在机器人领域首次提出的[2]，Kumar S等人首次将栅栏覆盖分为强栅栏和弱栅栏两种覆盖方式[3]。栅栏覆盖研究中强栅栏覆盖[4～9]和弱栅栏覆盖[10～13]均取得了一些研究成果。文献[14]将Voronoi图引入WSNs栅栏覆盖的研究中，通过对监测区域进行Voronoi划分，实现WSNs中覆盖漏洞的快速查找。文献[15]针对高效节能的栅栏漏洞修复问题进行研究，通过建立静止节点的权重图，再利用迪杰斯特拉算法寻找所需最少数目的移动节点和构建栅栏覆盖的最短路径，算法明显减少了移动节点的移动距离，实现了高效的栅栏覆盖。为了实现对被监测区域的全方位覆盖，以及能够捕捉到进入该区域目标的有效信息,文献[16]提出了一种基于异构节点的全视角强栅栏覆盖模型，借助红外线传感器辅助相机传感器节点完成对指定区域的监测。采用分治策略和唤醒机制有效延长了网络的生命周期。

以上有关栅栏覆盖的研究均是在带状区域中实现栅栏构建的，但在实际应用中发现监测区域不完全是带状的，如监测野生动物是否进入投饲点，由于无法确定野生动物进入投饲点的方向，因此需在投饲点周围建立环状栅栏。

针对WSNs的山地三维环状栅栏构建问题，本文提出一种基于等位区域的环状栅栏构建算法，算法能够将部署在山体上的WSNs划分为多个等位区域，并在每个等位区域中构建一条栅栏，形成了以山顶为中心的三维多重环状栅栏，从而实现山地中移动目标轨迹的有效追踪。

1 模型构建与问题概述

1.1 山地三维栅栏覆盖问题概述

传统的栅栏覆盖主要在二维空间中进行栅栏构建，但随着WSNs应用范围的不断拓展，许多应用要求在三维环境下实现栅栏覆盖，比如在山区进行野生动物监测和保护。由于山区地表高度落差较大，二维空间的栅栏覆盖技术已经不能满足这种复杂地貌中的数据采集需求，因此需要研究三维空间中的无线网络栅栏覆盖问题，从而有效提高复杂地貌环境下移动目标的监测质量。

1.2 网络模型

本文的仿真平台是一个规整的山体模型，其纵剖面是一个正态分布函数，如式(1)所示，其中σ=1.2

(1)

在上述的山体模型表面随机部署n个无线传感器节点，所有无线节点同构，且部署后位置不再变化，如图1所示。

图1 基于正态分布函数的山体模型

WSNs节点的感知模型可用一个二元组〈Pi，r〉表示，其中Pi=(xi，yi，zi)表示其在山体表面的位置；r为无线节点的最大感知半径，若移动目标与Pi的距离小于r，则其即可被无线节点感知，否则不能被感知，如图2所示。

图2 传感器节点的三维感知模型

1.3 有关定义

定义1等位区域：山体表面高度在[a,b)范围内的环状区域，被称为一个等位区域，其中a为高度下限，b为高度上限，如图3中阴影部分所示。

图3 山体等位区域示意

定义2邻居节点：在一个等位区域中，如果节点b是节点a的邻居节点，那么应满足以下条件：1)节点b与节点a均应位于同一等位区域中；2)节点b与节点a的距离应小于或等于2r；3)节点b应出现在节点a的顺时针方向上。

如图4所示，凡是出现在阴影部分的节点均是节点a的邻居节点。

图4 邻居节点示意

定义3无线节点对：如果节点b是节点a的邻居节点，则称节点a和节点b是一个无线节点对，a称为头节点，b称为尾节点。

定义4环状栅栏：在一个等位区域中，由多个互为邻居节点的无线节点对依次首尾相接形成的封闭的环路称为一条环状栅栏。

2 山地三维环状栅栏覆盖算法设计

2.1 算法设计思想

带状区域中构造的栅栏不封闭，因此在无屏障可依时，栅栏两端间的空白区域将成为无法检测到移动目标的漏洞。这种现象在自然环境中表现得尤为突出，例如在野外补饲点周围构建的栅栏如果不封闭，那么就存在遗漏监测到野生动物的可能，如图5所示。

图5 带状栅栏漏洞示意

山地三维环状栅栏覆盖算法首先在山体模型上随机部署n个无线传感器节点，再将山体按照不同的高度范围划分成多个等位区域，然后运用弗洛伊德算法[17]在每个等位区域的无线网络中至少找到一条环状栅栏，最终实现对山体的三维环状栅栏覆盖。

2.2 山地三维环状栅栏覆盖算法

算法的具体步骤如下：

步骤1 将山体表面从山脚到山顶每隔高度d划分一个等位区域。

步骤2 按照定义2建立每个等位区域中无线传感器网络的邻接矩阵。

步骤3 遍历所有等位区域，找到一个未访问过的等位区域执行步骤4，否则执行步骤7。

步骤4 在该等位区域中查找一组未使用过的无线节点对执行步骤5，否则执行步骤3。

步骤5 以无线节点对的尾节点为起点，头节点为终点，采用弗洛伊德算法在该等位区域的无线网络中搜索最短路径，如果最短路径存在，则执行步骤6，否则执行步骤4。

步骤6 将步骤5中求得的最短路径首尾相接形成环路并存入环状栅栏集，执行步骤3。

步骤7 返回环状栅栏集。

3 仿真实验与数据分析

3.1 实验平台构建

本文的仿真平台使用Eclipse4.9进行构建，实验环境是一个底面为700 m×700 m,高为400 m的山体模型，在山体表面部署若干无线传感器节点，每个传感器节点的传感半径r=100 m，山体表面按照从山脚起每上升100 m划分一个等位区域。图6为山体表面无线网络按照等位区域划分后的邻接关系俯视图。

图6 山体等位区域WSNs邻接关系示意

3.2 算法仿真实验

仿真实验结果显示，山体环状栅栏的形成效果直接受网络节点部署密度的影响。如图7中分别显示的是在山体上部署了80个和160个无线传感器节点形成的环形栅栏效果图。

图7 山体表面环状栅栏仿真效果俯视图

3.3 实验数据分析

由实验数据分析可知，在山体表面的WSNs中构造环状栅栏覆盖，无论是形成环状栅栏的节点个数还是环状栅栏的长度，均随着部署在山体表面无线节点个数的增加而增加。如果山体表面无线节点个数保持不变，若将无线节点对间的距离定义为1，所形成的环状栅栏的节点个数要远远小于无线节点对间距离为实际距离的情况，但栅栏长度却大于无线节点对间距离为实际距离的情况。实验数据分析结果如图8、图9所示。

图8 生成环状栅栏的节点数与部署节点数关系

图9 生成环状栅栏的长度与部署节点数关系

4 结束语

本文针对WSNs山地三维栅栏构建问题，提出了一种基于等位区域的环状栅栏构建算法。从实验数据分析表明：形成环状栅栏的节点个数和环状栅栏长度均会随着无线节点部署密度的增大而增加。在山体表面无线节点密度不变的情况下，若只考虑无线节点间的可达性，则所形成的环状栅栏的节点个数要远远小于无线节点对间距离为实际距离的情况，但栅栏长度却大于无线节点对间距离为实际距离的情况。该算法能够在三维空间的山体表面形成环状栅栏覆盖，有效地解决了山地表面高度落差大，传统的栅栏覆盖技术数据采集困难的问题，从而有效提高了复杂地貌环境下移动目标的监测和轨迹追踪质量。