无线视频传感网络k-栅栏实时覆盖算法*

樊　婷，白光伟，沈　航，马　丁

（南京工业大学计算机科学与技术系，南京211816）

无线视频传感网络k-栅栏实时覆盖算法*

樊婷，白光伟*，沈航，马丁

（南京工业大学计算机科学与技术系，南京211816）

在多目标入侵的场景下，由于入侵时间的不确定性，传统栅栏覆盖方法中有些传感节点并未覆盖目标却一直保持工作状态，造成额外能量损耗的同时降低了覆盖效果。针对该问题，提出了实时旋转传感节点实现k栅栏覆盖的算法（VSRA:Visual Sensors Rotating Algorithm），将整个监测区域划分为不同分区，在有入侵的分区，实时将传感节点向权值较大的感知方向旋转从而在满足一定k栅栏覆盖要求的同时达到提高节点利用率的目的。仿真结果表明，VSRA能提高覆盖性能，延长网络生存周期。

无线视频传感网；k栅栏覆盖；区域监测；权值比较；实时旋转

EEACC:7230doi:10.3969/j.issn.1004-1699.2015.09.022

无线视频传感网（WVSNs）中k栅栏覆盖是指在狭长的带状区域内部署一系列传感节点使得试图穿越的入侵者都能被k个不同的传感节点覆盖到，其中k值的选取是根据区域不同等级的警戒度人为设定的，它不仅是无线传感网络中的重要应用也是军事和国防安全应用中的关键技术，可以用来监测试图要穿越区域且未经授权的入侵者［4］。

无线视频传感器比起标量传感器有了视频捕捉的能力并加强了对入侵目标的监测力度。近年来研究人员针对如何在固定区域内构建栅栏覆盖提出了多种方案。王超提出了用最少的节点构建分区强k-栅栏覆盖的PMNSB［5］算法。Chang C Y提出了将监测区域划分为均匀网格后构建k-栅栏覆盖的算法。通过网格的覆盖程度来选择最优的传感器覆盖集合并保留候选集合，提高了覆盖可靠性［6］。但该算法没有考虑节点能耗的问题。Cheng C F提出了一种关于k-栅栏覆盖的分布式算法［7］，传感器间通过广播寻找剩余能量最大的节点作为初始节点，并由其纵向寻找能形成k栅栏覆盖的k-1个起始节点，从第k个初始节点开始依次向左右拓展唤醒节点，多次回溯迭代后形成栅栏。这种由回溯法形成的栅栏耗时长，计算量大又太过依赖于初始节点，会影响捕捉目标的成功率。

通常监测区域内布置的传感节点是由电池供应能量，生命时间有限，在满足覆盖要求的情况下尽可能减少传感节点能耗的问题有很大的研究意义。借鉴上述文献中由网格划分构建1栅栏的策略［6］，本文主要研究如何在k-栅栏覆盖的基础上实时旋转相关节点方向达到提高节点利用率以延长整个网络生命周期的目的。主要工作包括:①用（BA:Basic Approach For Construct Barrier Coverage）算法［6］构建1-栅栏覆盖后将监测区域分块并在入侵边界布置标量传感节点，根据目标入侵位置更新网格优先级。②依据网格优先级将候选节点覆盖网格的情况比例化，由VSRA得出节点各个感知方向的权值，实时调动相应分区内的候选节点旋转达到对入侵目标的k覆盖要求的同时减少节点能耗。

本文余下章节安排如下:第1节描述网络模型和问题描述；第2节以构建2栅栏覆盖为例，详细描述了VSRA的实现过程；第3节通过仿真实验对VSRA进行性能分析；最后第4节总结全文。

1　问题的提出

1.1模型和假设

本文考虑包含一定数量的视频传感器节点和标量传感器节点以及若干入侵目标的WVSNs的网络环境。监测区域B的面积为L×H，其中Lp、Ld、Lf、Lg，分别表示区域B的上下左右边界。

入侵目标在WVSNs中的有效穿越路径是指目标从区域的下方边界Ld连续移动到上方边界Lp的移动轨道。区域被k-栅栏覆盖是指试图以任意有效路径穿越区域B的目标都能被k个视频节点同时监测到［6］，其中BCk表示栅栏防御度为k。

假设视频传感节点是随机抛洒的，每个视频传感器节点都有①唯一的ID标识并且能通过GPS单元或者其他定位机制获取自身的位置信息；②可以与邻节点交换信息获得通信范围内传感节点ID和其覆盖目标的信息；③相同的初始能量，并且消耗后不能补充；④相同的感知距离和通信距离；⑤相同的感知角度和旋转模式（与文献［8］类似，如图1（a）和图1（b）所示）。

本文中使用到的符号如表1所示。

图1　视频传感节点模型

表1　本文中使用的符号

1.2问题的提出

k-栅栏覆盖是指任意穿越检测区域的目标am能够被k个不同的传感器同时覆盖到［9］。如图2所示若要将连续的网格2覆盖则需要part1与part2内的传感器同时唤醒形成覆盖路径。一方面在无目标入侵的part2区域也需要保持2-栅栏覆盖的传感器唤醒，会造成此区域传感器节点能量的损耗，等下一次入侵目标从part2区域穿越时，能量已被消耗无法实现本次栅栏覆盖的要求。另一方面节点抛洒后的位置和感知方向是随机的，随着k值的提高，栅栏覆盖的成功率也得不到相应的保证。

图2　监测区域的2-栅栏覆盖

针对以上现象，可以将监测区域划分为不同的区域，在有入侵的分区实现k-栅栏覆盖，而未入侵的分区保持1-栅栏覆盖的节点工作，这样不仅可以减少传感节点的能耗还能提高k-栅栏覆盖的成功率。

为了便于描述，给出如下定义:

定义1网络生存周期，即系统监测时长当第z次入侵时存在任意入侵目标am∈A无法达到k覆盖要求时，意味着当前k-栅栏覆盖生命结束。

定义2k覆盖路径［8］已知入侵目标集合A和节点感知方向集合D，路径节点集合C是D的子集，使得A中任意目标都被C中元素覆盖且符合相应k覆盖要求。该集合C则可为A的一组k覆盖路径。

定义3网格全覆盖已知网格集合G和节点感知方向集合D，若节点感知方向集合中存在D的子集将网格各个顶点都包含在内，则此网格被全覆盖了。

1.3k覆盖问题及旋转示例描述

由上所述可知，对监测区域的k栅栏覆盖可简化为传感集合Df（si，j）对区域从左至右边界相邻网格的连续k覆盖。

将目标与网格被k覆盖的问题表示如下:

A=｛am|m=1…M｝，S=｛si|i=1…N｝

K=｛km|m=1…M｝

每个网格的顶点坐标为:

若视频传感节点方向di，j覆盖到网格gm，n则可表示为:

若网格gmn被k覆盖，有

如图2所示，当区域内的一轮入侵中只有目标a1时为了构建2栅栏覆盖，需要s1～s12共12个频传感节点一起工作。而在节点感知方向［10］可旋转的情况下，如图3所示，达到上述要求只需要旋转s3（图中加粗部分为s3旋转后的方向）并让｛s1，s4，s6，s8，s10｝共6节点工作即可，这样可以节省传感节点的使用数量，从而延长网络的生存周期。

图3　旋转后实现对目标的2覆盖

2　算法描述

BA算法可以从边界左边到右边形成一条1栅栏覆盖的工作传感节点方向集合Df（si，j）与候选工作传感节点方向集合Df*（si，j）。在此基础上，我们设计VSRA以实现对监测区域的k栅栏覆盖具体算法如下。

2.1目标入侵时网格优先级的确定

首先在目标入侵的区域边界布置一系列标量传感器，这些传感器总能感知到入侵的目标并能及时发送其所在的网格位置信息给所属分区内的视频传感节点。再以每个分区目标am入侵所在的网格位置为对称中心，分别向左右拓展得到网格集合:

然后，覆盖到这些网格集合的传感节点将这些网格的优先级PRm，n均加上1并标记为Ginvadef。在前面形成1栅栏覆盖的算法中，被工作视频传感节点集合连续覆盖的网格集合G（si，j）的优先级均为1且表示为BG1（si，j∈Df（si，j）），那么BG1与刚刚优先级加1的拓展网格Ginvadef的交集形成了优先级为2的矩形网格区域，其网格集合表示为:

BG2=Ginvadef⋂G（si，j），f=1，2...F，Si，j∈Df（Si，j）（6）

把BG2作为视频传感节点实时旋转的最优区域，BG1网格集合为视频传感节点旋转的次优区域，统称为关键区域。在多目标入侵的情况下，会有网格优先级发生冲突，解决方法如下:若分块内出现关键区域BG1与BG2重合的情况，则高优先级默认覆盖低优先级即重叠区域优先级为BG2，各个感知方向上的权值计算方法不变。

一次入侵后，待越区目标被视频传感节点k覆盖后，拓展网格Ginvadef的优先级会被清零，等待下一次的入侵重新确定拓展网格。

2.2视频节点感知方向选择

由上节可知当目标入侵partf时布置在边界的标量传感器

可感知目标的信息，并且视频传感节点能通过相邻节点知晓优先级高的网格信息。

如图1（b）所示随机抛洒的视频节点有4个感知方向且每个方向视域为90°。候选工作传感节点方向集合Df*（si，j）需要判断如何旋转方向以实现对关键区域的覆盖最大化。

我们考虑两种算法。第一种是基于网格覆盖率下的贪心（GREEDY）算法，视频传感节点优先选择对关键区域网格面积覆盖率大的感知方向。第二种是VSRA，节点根据其4个感知方向对关键区域整体覆盖的情况设定不同的权值，通过比较权值大小来选择最优旋转方向最终得到覆盖路径集合。本节从传感节点对关键区域的覆盖成功率方面将GREEDY算法和VSRA作比较。

2.2.1GREEDY算法

该算法随机确定k覆盖要求，候选工作集合Df*（si，j）中的视频传感节点将其不同方向对关键区域的覆盖面积比率量化为相应数值，每轮通过比较各个感知方向量化数值的大小，确定传感节点方向的优先级。具体步骤如下:

视频节点si的第j个方向di，j在partf对优先级为e的区域的格覆盖率为:

其中BGe，i，j表示传感节点si第j个方向对优先级为e网格的覆盖面积，BGe表示优先级为e网格的面积。

依据dij对关键区域的覆盖率，设定不同传感方向上的比例值Oi，j，具体方式如下:

候选节点集合Df*（si，j）在目标入侵partf后被唤醒，并向具有最大比例值Oij的方向旋转。如果不同传感节点的不同传感方向都有最大的比例值，则比较它们各个方向比例总值，优先选择总值大的方向旋转。每轮去掉已覆盖网格区域后重新计算比例值，如此迭代选出旋转工作集合Df（si，j）。迭代的终止条件是指partf区域中入侵目标被k覆盖了。

2.2.2VSRA

该算法在GREEDY的基础上做出改进，先得出候选工作集合Df*（si，j）不同方向的比例值Oij后，再根据不同传感节点各个传感方向总体的比例值，参考文献［11］权值的计算方法得到每个传感方向的权值。传感节点方向选择的计算方法如下:

感知方向调节算法（VSRA）

当有目标am入侵partf时，根据VSRA依次唤醒候选集合Df*（si，j）中传感节点工作，得到partf中可实现k栅栏覆盖的传感节点集合Df（si，j）。

如图4所示，矩形监测域内画出的窄长关键区域的中间部分网格代表最优区域BG2，其左右两端部分网格则代表次优区域。传感节点s1～s4按照如上算法实时旋转传感节点的方向，实现对入侵目标的k覆盖要求。图表中只列出2个传感方向，但目标数和权值计算是结合4个传感方向得来的，具体步骤见表2与表3。

图4　传感节点旋转方向选择的例子

表2　GREEDY选取旋转工作集合步骤

表3　VSRA选取旋转工作集合步骤

结合上述例子，通过对比GREEDY与VSRA可知若采用前者会出现关键区域漏覆盖与传感节点s4被闲置的情况，而采用本文提出的VSRA后，可以最大化关键区域覆盖，满足任意入侵目标被k覆盖要求的同时提高节点利用率。

3　仿真实验与结果分析

3.1实验环境和参数设置

本文在MATLAB平台上实现了在多目标入侵的场景下对监测区域的k-栅栏覆盖，并设计了一系列仿真实验。区域内随机抛洒300～600个视频传感节点，各个节点位置固定不变，初始能量相同并随机部署多目标沿有效路径穿越监测区域。

视频节点所消耗的能量主要来自数据处理过程、感知过程和传输过程。根据文献［12］，节点的能量消耗根据工作模式的不同而变化。我们假设当路径序列中的节点工作时，处理和感知过程为活动模式，传输过程为空闲模式。假设每个视频节点的初始能量为200 J，期望工作时间为3 120 s。仿真过程基本参数设置详见表4。

为了提高实验结果的参考价值，每组实验结果都是进行了多次随机试验后求得的平均值。

表4　实验参数设置

3.2实验结果分析

本节主要从k-栅栏覆盖成功率和节点剩余能量百分比这些方面考察算法的性能。通过改变目标入侵次数、目标入侵数量以及区域分块个数得到不同的网络场景来考察BA与VSRA的性能。

VSRA、GREEDY算法与BA算法在目标入侵速度不同的情况下实现k-栅栏覆盖的成功率如图5所示。实验取2-栅栏与3-栅栏覆盖为例，由于节点入侵的速度是随机不同的，在穿越距离固定的情况下，各个目标入侵的完成时间与其穿越速度是成反比的，那么可以通过观察横轴的入侵完成时间来体现多目标整体穿越的速度。BA在目标入侵前开启了要实现k-栅栏覆盖所需的传感器集合并一直工作等待入侵。VSRA是根据目标入侵的位置，计算出关键区域，并调动入侵分区的候选传感节点实时旋转以达到覆盖要求。实际情况下目标的入侵完成时间总是大于3 s，从图5可以看出在3栅栏覆盖要求下，横轴时间点在接近3 s时，VSRA的成功率超过传统BA算法并稳定增长直至高于其18.91%左右。同理在2栅栏覆盖要求下成功率可以比于原BA算法大于7.1%～16.88%左右。

图5　入侵速度对栅栏覆盖成功率的影响

由BC3与BC2的情况对比可知随着栅栏覆盖k值越高，VSRA与GREEDY需要配置的时间越长，待花费时间到达一定上限的时候VSRA的成功率会趋于平稳。虽然GREEDY算法也是实时旋转的，但是其会在节点方向选择的时候出现漏覆盖的情况，所以成功率相对VSRA较低，并且随着k覆盖要求的提高，漏覆盖情况会更加严重。

图6显示出VSRA和BA算法在固定的时间段内，多目标同时对监测区域入侵时，观察改变目标数量对节点剩余能量的影响，以此反应节点能耗情况。如图6所示相比较BA而言VSRA受目标数目影响较大。在区域分块数目固定的情况下，当入侵目标较少时，只有较少的分区需要唤醒候选节点，其余分区均保持形成1栅栏的节点工作而BA算法每个分区一直都要保持形成2栅栏的节点工作，因此其节点的平均剩余能量在开始时要低于VSRA 9.7%左右，但随着入侵目标的不断增加，涉及的分区不断增加，分区内的候选节点相继工作，节点的平均能耗也逐渐增加。当多目标遍及整个区域时，节点的平均剩余能量逐渐接近于BA算法。

图6　入侵目标数对节点剩余能量的影响

图7是表示在区域分块可变的情况下，一次入侵3～10个目标考察形成2栅栏覆盖后节点剩余能量百分数的变化。由实验可知节点的剩余能量在BA算法下基本不受区域分块的影响而在VSRA下是随着区域的分块数量而变化的。一方面监测区域的分块数目越多，节点的处理能耗越高，另一方面固定区域的分块数目越少，目标穿越时唤醒的传感节点越多，节点的传感能耗越高，节点剩余能量越少。分块数为8时可以看出节点的能耗较低，此时节点剩余能量的达到一定的峰值点，比传统BA算法的节点剩余能量高出7%左右。

图7　区域分块数对节点能耗的影响

从表5可以看出在一次入侵1～3个目标且入侵次数变化的情况下，BA与VSRA节点平均能耗和能耗方差的对比。VSRA在1栅栏覆盖的基础上待一次入侵后，实时关闭旋转的候选节点等待下一次入侵，节省了节点的能耗，延长了网络的生命时间。但从表5可以看出随着多目标入侵次数的增加，两种算法的方差都在不断变大，这是由于一直开启的节点能量在持续损耗，特别是VSRA中实时旋转的节点与保持1-栅栏一直工作的节点会出现能耗不均衡现象。

表5　入侵次数改变时节点平均剩余能量和剩余能量方差比较

4　总结

本文提出了WVSNs中k-栅栏实时覆盖算法VSRA。通过将整个监测区域合理分块后，在1-栅栏覆盖的基础上，提出根据目标入侵的位置，用VSRA得到候选节点各个感知方向的权值，实时触发其向目标最有可能出现的网格区域旋转，提高了节点利用率。最后通过一系列仿真实验，对其性能进行分析和评价，仿真结果表明:VSRA能提高覆盖性能，节省传感节点的能耗，延长了网络生存周期。

［1］ Halawani S，Khan A W.Sensors Lifetime Enhancement Techniques in Wireless Sensor Networks-A Survey［J］.Journal of Computing，2010，2（5）:34-47.

［2］ Lee I，Shaw W，Park J H.On Prolonging the Lifetime for Wireless Video Sensor Networks［J］.Mobile Networks and Applications，2010，15（4）:575-588.

［3］ 孙超，赵路路，张影，等.无线传感器网络分簇拓扑的覆盖区域节点调度优化算法研究［J］.传感技术学报，2010，23（1）:116-121.

［4］ Ssu K F，Wang W T，Wu F K，et al.K-Barrier Coverage with a Directional Sensing Model［J］.International Journal on Smart Sensing and Intelligent Systems，2009，2（1）:75-93.

［5］ 王超，范兴刚，王恒，等.一种高效强K-栅栏覆盖构建算法［J］.传感技术学报，2015（2）:227-233.

［6］ Chang C Y，Hsiao C Y.The K-Barrier Coverage Mechanism in Wireless Visual Sensor Networks［C］//Proceedings of IEEE Wireless Communications and Networking Conference（WCNC）.Pairs: WCNC，2012:2318-2322.

［7］ Cheng C F，Tsai K T.Distributed Barrier Coverage in Wireless Visual Sensor Networks with β-QoM［J］.IEEE Sensors Journal，2012，12（6）:1726-1735.

［8］ Cai Y，Lou W，Li M，et al.Energy Efficient Target-Oriented Scheduling in Directional Sensor Networks［J］.IEEE Transactions on Computers，2009，58（9）:1259-1274.

［9］ Saipulla A，Liu B，Xing G，et al.Barrier Coverage with Sensors of Limited Mobility［C］//Proceedings of the Eleventh ACM International Symposium on Mobile ad hoc Networking and Computing. Chicago:MobiHoc，2010:201-210.

［10］Costa D G，Guedes L A.The Coverage Problem in Video-Based Wireless Sensor Networks:A Survey［J］.Sensors，2010，10（9）: 8215-8247.

［11］Munishwar V P，Abu-Ghazaleh N B.Coverage Algorithms for Visual Sensor Networks［J］.ACM Transactions on Sensor Networks （TOSN），2013，9（4）:293-314.

［12］Wang B.Coverage Problems in Sensor Networks:A Survey［J］. ACM Computing，2011，43（4）:87-88.

樊婷（1991-），女，硕士研究生，主要研究方向为无线多媒体传感器网络，传感网络栅栏覆盖技术，648364417@qq.com；

白光伟（1961-），男，博士，教授，博士生导师，CCF高级会员（E200012029S），主要研究方向为无线传感器网络，移动互联网，网络体系结构和协议，网络系统性能分析和评价，多媒体网络服务质量等，bai@njtech.edu.cn。

The Real Time Algorithm on K-Barrier Coverage in Wireless Visual Sensor Networks*

FAN Ting，BAI Guangwei*，SHEN Hang，MA Ding
（Department of Computer Science and Technology，Nanjing Tech University，Nanjing 211816，China）

In the case of uncertain intruding time in a multi-target invasion scenario，some sensors maintain actuated state though cannot cover the targets，which leads to the reduction of coverage impact and consuming sensors extra energy.To address this problem，this paper proposes a Visual Sensors Rotating Algorithm（VSRA）to improve the utilization of sensors，which can also satisfy real-time k-barrier coverage requirement.It divides the surveillance area into several regions and Sensors rotate to directions with higher weight in invaded regions.Our simulation results show that the proposed VSRA can improve the energy efficiency of sensors and prolong the network lifetime.

wireless visual sensor networks；k-barrier coverage；area monitoring；weight comparison；real-time rotation scheme

TP393

A

1004-1699（2015）09-1395-07

项目来源:国家自然科学基金项目（60673185，61073197）；江苏省自然科学基金项目（BK2010548）；江苏省科技支撑计划（工业）项目（BE2011186）；江苏省未来网络前瞻性研究项目（BY2013095-4-09）；南京邮电大学宽带无线通信与传感网技术教育部重点实验室开放研究基金课题项目（NYKL201304）；江苏省六大高峰人才基金（第八批）课题项目

2015-04-10修改日期:2015-06-18