有向无线传感器网络弱栅栏覆盖构建算法设计

郭新明，李 康，陈 伟，贾 浩

（咸阳师范学院 计算机学院，陕西 咸阳 712000）

随着传感技术的不断进步，无线传感器网络已经成为当前的一个研究热点。无线传感器网络栅栏覆盖技术是其中一个重要的研究方向，目前已经被广泛应用到军事、国防、工业、农业等领域[1]。栅栏覆盖是由Gage首次在机器人研究领域提出来的[2]，Kumar等首次给出了强栅栏和弱栅栏的定义，并设计了一个判定监测区域是否被k条栅栏覆盖的算法[3]。有关栅栏覆盖的研究中，强栅栏覆盖已经取得了许多研究成果[4-7]，而弱栅栏覆盖的研究成果相对较少[8]。弱栅栏覆盖关注移动目标沿垂直于带状区域的路径穿越时能否被监测到，在实际应用中，可利用较少的节点构建栅栏，大大减少网络冗余和节点能耗[3]。有向传感网络由于对环境数据的感知受“视域（field of view，简称FOV）”的限制，具有方向特性，所形成的感知范围是以节点为圆心，其感知距离为半径的扇形区域[9]。有向传感器网络栅栏覆盖研究依然存在强栅栏和弱栅栏两种覆盖方式，文献[9-11]均针对有向传感器网络强栅栏覆盖进行研究，而有向传感器网络弱栅栏覆盖方面的研究依然较少。

针对有向无线传感器网络的弱栅栏覆盖问题，本文提出了一种基于有向无线传感器投影的弱栅栏构建算法，该算法能够实现监控区域的弱栅栏覆盖，从而实现对监测区域中移动目标的有效追踪。

1 网络模型及问题描述

1.1 无线网络模型

本文的监测区域是一个长L宽W的矩形区域，并在其中随机部署N个传感器节点，节点的坐标可以用（x，y）来表示其在矩形区域中的相对位置，并且节点在部署后位置不改变。

定义1有向无线传感器节点感知模型：一般采用四元组＜L，r，V，β＞表示，其中 L=（x ，y）表示传感器节点的位置坐标；r为节点的最大感知半径；单位向量V为节点的感知方向，是扇形感知区域的中轴线；β为感知夹角，即边界偏移感知向量V的角度；2β是感知区域的视角，通常记为FOV，α为扇形感知区域的起始角度，结构如图1所示。

图1 有向传感器节点感知模型

定义2有向无线传感器弱栅栏路径：是监测区域中的一个节点集，若移动目标沿任意垂直于监测区域的方向穿越该区域时，都会被该集合中至少一个有向无线传感器节点监测到。有向无线传感器弱栅栏路径如图2所示，每个传感器节点的FOV=60°。

定义3边界节点：覆盖区域与监测区域左边界相交的有向无线传感器节点称为该监测区域的左边界节点，覆盖区域与监测区域右边界相交的有向无线传感器节点称为该监测区域的右边界节点。

定义4弱栅栏集合：构成一条弱栅栏的所有有向无线传感器节点，称为弱栅栏集合。

图2 FOV=60°的弱栅栏部署图

1.2 有向无线传感器网络弱栅栏覆盖问题

有向无线传感器网络弱栅栏覆盖问题是针对无线传感器网络中节点覆盖密度较低或尽可能延长网络生命周期的情况下，实现对监测区域中移动目标有效追踪的一种监控策略。有向无线传感器网络弱栅栏覆盖既降低了网络能耗又避免了因网络中节点部署不均而造成强栅栏构建受限的缺陷，是一种灵活高效的覆盖策略。本文提出的基于有向无线传感器节点投影的弱栅栏构建算法，旨在依靠投影的连通性构建有向无线传感器网络弱栅栏，进而实现对监测区域中移动目标的有效追踪。

2 有向无线传感器网络弱栅栏覆盖算法

2.1 算法的设计思想

要在有向无线传感器网络中实现弱栅栏覆盖，首先应该获得每个有向无线传感器的覆盖范围在直角坐标系中的投影，再根据有向无线传感器投影间的重合关系建立弱栅栏，弱栅栏覆盖不要求节点的覆盖区域相互重叠，只需弱栅栏集合中所有节点覆盖区域的投影相互重叠即可。有向无线传感器的投影因其起始角度的不同而变化，可将其分为如下4种情况，如图3所示。

用p表示有向无线传感器投影的长度。情况1，如图3（a）所示，投影为式（1）。

情况2，如图3（b）所示，投影为式（2）。

图3 有向无线传感器节点投影示意图

情况3，如图3（c）所示，投影为式（3）。

1）在梨小食心虫越冬前，树干绑诱虫带，诱集幼虫越冬，冬末解除集中烧毁。春季越冬幼虫化蛹羽化前，刮除树干老翘皮，消灭根颈周围土壤中的越冬代幼虫。

情况4，如图3（d）所示，投影为式（4）。

2.2 弱栅栏构建算法

本算法以有向无线传感器节点在直角坐标系中的投影为依据，利用Floyd算法计算监测区域左右边界节点间的最短弱栅栏，算法描述如下：

步骤1遍历监测区域中的节点，将监测区域左右边界节点分别放入LeftNode和RightNode集合中。

步骤2遍历监测区域中的节点，计算节点的投影长度和起始位置。

步骤3遍历监测区域中的节点，依据节点投影间的垂直重合关系，建立网络的邻接矩阵。

步骤4若LeftNode和RightNode集合均不为空，且其中存在未遍历节点，执行步骤5，否则执行步骤7。

步骤5从监测区域左右边界节点集LeftNode和RightNode中分别取一个未遍历的节点作为起始和结束节点，利用Floyd算法在网络的可用节点中计算最短路径，若得到最短路径，执行步骤6，否则执行步骤4。

步骤7输出最短路径集ShortestPath中的所有路径，算法结束。

3 实验与分析

3.1 实验平台的搭建

仿真实验平台使用Eclipse开发工具进行搭建，实验环境为一个800 m×200 m的矩形区域，内部部署若干个夹角60°、半径为50 m的有向传感器节点，节点的传感方向和位置均随机分布，如图4所示。

图4 仿真实验平台效果图

3.2 算法实现

在监测区域的矩形范围内，随机部署若干节点，根据部署节点个数的不同，构建出不同数量的弱栅栏覆盖，算法实验的结果如图5-7所示（说明：黑色扇形代表当前已经构建好的弱栅栏，加粗黑色直线表示构建好的弱栅栏中相应节点的投影）。

图5 部署90个无线节点的弱栅栏覆盖构建效果图

图6 部署120个无线节点的弱栅栏覆盖构建效果图

图7 部署150个无线节点的弱栅栏覆盖构建效果图

3.3 实验数据分析

根据实验数据显示，当部署节点为90时，构建的弱栅栏有1条，栅栏节点数目为21个；当部署节点为120时，构建的弱栅栏有2条，栅栏节点数目分别为20个和19个；当部署节点为150时，构建的弱栅栏有3条，栅栏节点数目分别为19、20和20。由此可知，节点数密集时，会增加构建的弱栅栏数，但是构成栅栏节点的数目没有明显变化。

从实验结果可以看出，有向无线传感器节点部署的密度越大，构建的弱栅栏数量就越多，形成弱栅栏的节点平均数目也相对减少。

4 结语

随着传感器技术的不断发展，有向传感器网络已经逐渐走进人们的生活，如城市中的摄像头，通过有向感知实现环境监测。本文针对有向无线传感器网络的弱栅栏覆盖问题，提出了一种基于有向无线传感器投影的弱栅栏构建算法。实验结果显示，随着网络中部署节点的增多，形成的弱栅栏数量也会随之增加。该算法能够实现监控区域的弱栅栏覆盖，进而实现对监测区域入侵对象的有效追踪，但是在节点性能优化方面还需要进一步研究。