一种视频传感器网络的栅栏覆盖方法

尤炳棋，徐向华，王 然

(杭州电子科技大学 计算机学院，浙江 杭州 310018)

在实际应用中，根据检测对象的性质，可将覆盖问题大致分为3类，目标覆盖[1-3]、区域覆盖[4-6]、栅栏覆盖[7-9]。覆盖模型有全向覆盖和定向覆盖[10]。本文重点研究视频传感器网络的栅栏覆盖问题。

视频传感器与普通定向传感器有较大不同，监测有效性取决于目标正面朝向与视频传感器方向的可视角度[11]。因此，文献[12]提出了视频传感器网络的全视域覆盖的概念并给出了全视域覆盖的判定。全视域覆盖是指被监测的目标，无论朝向任何方向都能被至少一个视频传感器有效覆盖。有效覆盖是指目标的朝向与目标和视频传感器连线矢量的夹角小于给定角度。全视域覆盖区域是指区域中每个点都是全视域覆盖的。基于全视域覆盖，文献[13]提出了视频栅栏的概念。视频栅栏是指栅栏上的区域都是全视域覆盖的。文献[13～14]研究了普通定向视频传感器的视频栅栏覆盖问题。而在一些场景中，传感器有多个可能的工作方向，同一时刻只能开启一个方向工作[15]。

本文研究了多工作方向视频传感器网络的视频栅栏覆盖问题。假设每个视频传感器都有3个可能的工作方向，但同一时刻只能有一个方向在工作。对于给定的区域，区域里随机抛洒了很多这样的视频传感器。研究如何挑选尽可能少的视频传感器并同时确定工作方向来构成视频栅栏。

1 问题描述

对于视频传感器网络来说覆盖时要考虑目标的朝向。

1.1 全视域覆盖

图1 全视域覆盖模型

图2 点的全视域覆盖判定

图3 安全区域和非安全区域

图4 网格单元的全视域覆盖示例

图5 最小覆盖集合示例

最小覆盖集合定义：如果传感器工作方向集合di能全视域覆盖网格单元bi，且di的任何真子集都不能全视域覆盖网格单元bi，则di就是网格单元bi的一个最小覆盖集合。图5中网格单元被10个视频传感器覆盖，画出传感器间的非安全区域可得3个最小覆盖集合分别为{S1,S2,S3,S4,S5,S6,S8,S10}，{S1,S2,S3,S4,S5,S6,S7,S9,S10}，{S1,S2,S3,S4,S5,S7,S8,S10}。

网格单元的I集合：网格单元bi的I集合就是网格单元bi的所有最小覆盖集合所组成的集合。

1.2 问题定义

约束条件：

di∈Ii,1≤i≤m

(1)

∀So,p∈di，1

若p≠t, 则0≠r

(2)

条件(1)保证所选的最小覆盖集合为路径上网格单元的最小覆盖集合。条件(2)保证同一时刻一个视频传感器只能有一个方向在工作。

2 问题分析

本文的难点在于视频传感器有3个可能的工作方向，选择不同的工作方向会形成不同的全视域覆盖区域，而文献[13～14]中为普通定向视频传感器，部署后全视域覆盖的区域也已确定。因此，本文采用离散的方法将区域划分成网格单元，判断每个网格单元是否可能被全视域覆盖，如果可能被全视域覆盖，添加标记并求出所有满足该网格单元全视域覆盖的传感器工作方向的集合，即所有最小覆盖集合。求解最小覆盖集合的算法参见文献[14]，其中的算法是对不规格区域求最小覆盖集合，该算法同样适用于求解网格单元的最小覆盖集合。根据标记情况，如果两个标记网格单元相邻，则彼此之间存在一条边，边的权值设置为1，再添加起始点S和结束点T分别代表区域的左右边界。调用迪杰斯特拉算法，求出最短路径，判断该最短路径是否有冲突，若无冲突则该路径就是一条视频栅栏。

图6 调用迪杰斯特拉算法求最短路径

变形后可得挑选问题与最大交集问题是等价的，而最大交集问题在文献[16]中已被证明是一个NP问题，因此本文的问题也是NP问题。

3 算法设计

挑选问题在上文中已被证明是NP问题，所以设计 “不冲突选择算法”来近似解决。算法步骤为：

步骤1 输入最短路径上网格单元的I集合{I1,I2,…,Im}，初始化参数MinBarrer=Φ,j=1,MinNum=∞；

步骤2 从{I1,I2,…,Im}中依次取出元素Ij，对取出的集合Ij中的每个最小覆盖集Sm依次进行判断，如果|Sm∪MinBarrer|

步骤3 令MinBarrer=Sk∪MinBarrer；

步骤4 输出MinBarrer集合，该集合即使区域满足全视域的视频栅栏覆盖的工作方向集合。

4 实验模拟

实验设定区域为10 m×20 m，网格单元大小为1 m×1 m，视频传感器的感应半径为3 m，有效角度为π/3,传感器的数量从500个依次增加到3 500个。每次设置传感器数量后运行100次，记录构成视频栅栏的次数以及每次构成视频栅栏所花费的传感器的平均数量。

图7 传感器数量变化对构成视频栅栏概率的影响

由图7可知，当随机部署的视频传感器数量很少时不能构成视频栅栏。随着部署的视频传感器数量的增多，构成视频栅栏的概率增大。图7中普通视频传感器的曲线是文献[14]的实验结果，本文的方法比文献[14]采用普通视频传感器的方法构成视频栅栏的概率更高，尤其是随机部署的传感器数量较少时，优势更明显。

图8 传感器数量对构成视频栅栏所需传感器数量的影响

由图8可知，当设定的有效角度越小时，形成全视域覆盖的难度越大，构成视频栅栏所需传感器数量也越多。随着部署视频传感器数量的增加，构成视频栅栏所花费的传感器数量也不断增加。这是因为随着部署视频传感器数量的增加，单个网格单元满足全视域覆盖的视频传感器数量也增加了。

5 结束语

实验结果表明，本文的方法可以应用于多工作方向视频传感器网络，实现选择尽可能少的视频传感器并确定工作方向来构成视频栅栏的目标。本文方法比普通视频传感器网络构成视频栅栏拥有更好的性能，尤其当网络中随机部署的视频传感器数量较少时效果更佳。

[1] 魏鹏,路赞赞.无线传感器网络分布式多传感器目标检测[J].电子科技,2014,27(3):143-146.

[2] Mohamadi H,Salleh S,Ismail A S.A learning automata-based solution to the priority-based target coverage problem in directional sensor networks[J].Wireless Personal Communications,2014,79(3):2323-2338.

[3] Cai Y,Lou W,Li M.Cover set problem in directional sensor networks[J].Future Generation Communication & Networking, 2007(1):274-278.

[4] 宋苏鸣,张燕,陈源.多蜜源蜂群算法在无线传感器网络覆盖的优化[J].电子科技,2013, 26(11):17-21.

[5] Tao D,Ma H,Liu L.Coverage-enhancing algorithm for directional sensor networks[M].Berlin Heidelberg:Springer,2006.

[6] Aghdasi H S,Abbaspour M.Energy efficient area coverage by evolutionary camera node scheduling algorithms in visual sensor networks[J].Soft Computing,2016, 20(3):1191-1202.

[7] Tao D,Wu T Y.A survey on barrier coverage problem in directional sensor networks[J]. Sensors Journal IEEE,2015,15(2):876-885.

[8] Zhang Y,Sun X,Wang B.Efficient algorithm for k-barrier coverage based on integer linear programming[J].China Communications,2016, 13(7):16-23.

[9] Eftekhari E,Mohsen A,Kranakis R,et al. Distributed algorithms for barrier coverage using relocatable sensors[J].Distributed Computing,2016,29(5):361-376.

[10] Wang B.Coverage problems in sensor networks:a survey[J].ACM Computing Surveys,2011,43(4):32-38.

[11] Chang C C,Aghajan H.Collaborative face orientation detection in wireless image sensor networks[C].Macro:Proceedings of ACM SenSys Workshop on Distributed Smart Cameras,2006.

[12] Wang Y,Cao G.On full-view coverage in camera sensor networks[C].Shanghai:IEEE International Conference on Computer Communications,2011.

[13] Wang Y,Cao G.Barrier coverage in camera sensor networks[C].Paris:ACM International Symposium on Mobile Ad Hoc Networking and Computing,2011.

[14] Ma H,Yang M,Li D,et al.Minimum camera barrier coverage in wireless camera sensor networks[C].Xi’an:IEEE International Conference on Computer Communications,2012.

[15] 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.

[16] Clifford R,Popa A.Maximum subset intersection[J].Information Processing Letters,2011,111 (7):323-325.