基于Voronoi图的无线传感器网络栅栏覆盖算法设计
2020-04-09郭新明张瑾陈伟李康
郭新明 张瑾 陈伟 李康
摘 要：针对无线传感器网络中栅栏构建的问题，提出了一种基于监测区域Voronoi图划分的无线节点栅栏构建算法。仿真结果显示，网络中无线节点部署地越多，栅栏形成的可能性和组建栅栏的节点平均数量也会随之增加。该算法能够在无线传感器网络节点覆盖密度较低且不均，已经形成了少量栅栏空洞的情况下快速实现监测区域的栅栏覆盖，但空洞修复还需要进一步研究。
关键词：无线传感器网络;栅栏覆盖;Voronoi图
中图分类号：TP393 文献标识码：A
Design of Wireless Sensor Network Barrier Covering
Algorithm Based on Voronoi Diagram
GUO Xin-ming？覮，ZHANG Jin，CHEN Wei，LI Kang
（School of Computer，Xianyang Normal University，Xianyang，Shaanxi 712000，China）
Abstract：Aiming at the problem of barrier construction in wireless sensor network，a wireless sensor network barrier construction algorithm based on Voronoi graph division of monitoring area is proposed. Simulation results show that the more wireless nodes deployed in the network，the possibility of barrier formation and the average number of barrier nodes will increase. The algorithm can quickly realize the barrier coverage of the monitoring area when the wireless sensor network node coverage is low and uneven，and a few barrier holes have been formed，but the cavity repair needs further research.
Key words：wireless sensor networks（WSN）;barrier coverage;Voronoi diagram
隨着微电子技术、传感技术、网络技术的不断进步，无线传感器网络技术及应用迅速成为当下WSN的热点研究问题，栅栏覆盖是WSN目标检测中一个重要的研究方向，主要研究如何能有效监测移动目标穿越WSN覆盖区域的问题[1]。栅栏覆盖技术如今已经被广泛地应用到军事监测、工业和农业控制、安全防御等范畴[2]。栅栏覆盖的概念是由Gage在机器人领域首次提出的[3]，Kumar等首次将栅栏覆盖分为强栅栏和弱栅栏两种覆盖方式[4]。栅栏覆盖研究中强栅栏覆盖[5-9]和弱栅栏覆盖[10-11]均取得了一些研究成果。文献[12]中基于监测区域的 Voronoi图划分，可快速查找出WSN中的覆盖漏洞，在只关注邻近传感器节点影响的宽松覆盖条件下，论证出利用该图生成的最小暴露进攻轨迹逼近于理想情况。文献[13]运用监测区域的Voronoi 图划分整个部署区域，提出了基于 Voronoi 图的无线传感器网络栅栏覆盖策略，并监测部署区域是否存在栅栏覆盖空洞，以决定节点是否通过有限移动重新部署空洞区域，实现了对栅栏部署区域的有效覆盖。
针对WSN的栅栏覆盖问题，提出了一种基于Voronoi图的栅栏覆盖构建算法，该算法能够在WSN中节点覆盖密度较低且不均，已经出现少量栅栏空洞的情况下快速实现监测区域的栅栏覆盖，从而有效追踪监测区域移动目标的移动轨迹。
1 模型构建及问题概述
1.1 网络模型
仿真平台是一个长L宽W的矩形监测区域，在该监测区域中随机部署n个无线传感器节点，所有无线节点同构，且部署后位置不再变化。
无线传感器节点的感知模型可用一个二元组
图1 传感器节点感知模型
定义1 起点集合和终点集合
起点集合：在覆盖区域中，如果某个Voronoi多边形的一条边和覆盖区域的左边界重合，那么这个Voronoi多边形中的传感器节点属于起点集合，该节点称为起始无线节点，该Voronoi多边形也称为起始Voronoi多边形。
终点集合：在覆盖区域中，如果某个Voronoi多边形的一条边和覆盖区域的右边界重合，那么这个Voronoi多边形中的传感器节点属于终点集合，该节点称为终止无线节点，该Voronoi多边形也称为终止Voronoi多边形。
定义2 穿越路径
在矩形覆蓋区域中，任意经过该区域上下边界的曲线段称一个穿越路径。
定义3 邻居节点
在覆盖区域中，由部署在该区域中的节点生成的Voronoi图中，如果任意两个Voronoi多边形有一条公共边，那么这两个多边形中的传感器节点互为邻居节点。
定义4 Voronoi栅栏
以任一起始Voronoi多边形开始和任一终止Voronoi多边形结束的，由若干相邻Voronoi多边形彼此依次连接形成的栅栏称为一条Voronoi栅栏。
1.2 Voronoi栅栏覆盖问题
基于Voronoi图的WSN栅栏覆盖问题是针对WSN中节点覆盖密度偏低且不均，已经形成了少量栅栏空洞的情况下通过修复空洞来实现覆盖栅栏重构的一种策略。本文提出的基于Voronoi图的无线传感器网络栅栏覆盖算法，只涉及Voronoi栅栏覆盖的构建，Voronoi栅栏覆盖构建后的空洞修复问题将是下一步的研究内容。
2 基于Voronoi图的WSN栅栏构建算法
设计
2.1 算法设计思想
在监测区域内随机部署n个无线传感器节点，利用Voronoi图的几何原理为每个节点生成一个Voronoi多边形，这样就可以将监测区域划分成n个子区域。即每一个子区域内有且只有一个无线传感器节点。再根据这n个Voronoi多边形的邻接关系，运用弗洛伊德算法[14]寻找起始Voronoi多边形和终止Voronoi多边形间的最短路径，并将此路径作为Voronoi栅栏。
2.2 基于Voronoi图的无线传感器网络栅栏覆盖
算法
本课题中有关监测区域的Voronoi图划分，主要采用文献[15]中的算法进行，算法的具体步骤如下：
步骤1 遍历监测区域中的所有无线节点，对监测区域进行Voronoi图划分，按照定义3建立所有节点的邻接矩阵，相邻节点的权值均为1。
步骤2 根据定义1建立起点集合与终点集合。
步骤3 分别遍历起点集合与终点集合，采用弗洛伊德算法查找每对起始无线节点和终止无线节点间的最短路径，如果最短路径存在，则执行步骤4，否则执行步骤5。
步骤4 将步骤3中求得的最短路径存入Voronoi栅栏集，执行步骤5。
步骤5 若起点集合与终点集合遍历结束执行步骤6，否则执行步骤3。
步骤6 清理Voronoi栅栏集，若多条Voronoi栅栏存在共同的Voronoi多边形，则保存其中Voronoi多边形数量最少的一条，其余的Voronoi栅栏删除。
步骤7 返回清理后的Voronoi栅栏集。
3 仿真实验与数据分析
3.1 实验平台构建
仿真平台使用Eclipse进行构建，实验环境为一个1366×768m的矩形监测区域，该区域内部署若干无线传感器节点。如图2所示，仿真平台为监测区域的一个Voronoi划分图。
图2 仿真实验平台效果图
3.2 算法实现
仿真实验发现，传感器节点的网络覆盖率随着节点数目的增加发生着变化。如图3至图6所示，分别为部署了50、100、150、200个传感器节点的Voronoi栅栏覆盖实验效果图。
图3 部署50个传感器节点的栅栏覆盖图
图4 部署100个传感器节点的栅栏覆盖图
图5 部署150个传感器节点的栅栏覆盖图
图6 部署200个传感器节点的栅栏覆盖图
3.3 实验数据分析
根据仿真实验结果可知，随着监测区域中部署节点数量的增加，构成栅栏覆盖的Voronoi多边形数量也会随之增多。图7是监测区域部署的传感器节点数与栅栏覆盖的Voronoi多边形平均数之间的变化关系，图8反映了监测区域部署的传感器节点数与构造的Voronoi栅栏数间的变化关系。
图7 部署节点数与构成栅栏的Voronoi
多边形平均数关系图
图8 部署节点数与Voronoi栅栏数目关系图
从实验结果可以看出，构成栅栏覆盖的Voronoi多边形数目随着部署传感器节点数量的增加呈递增趋势，当部署传感器节点的数量增多时，栅栏的数目也随之增加。
4 结 论
针对WSN的栅栏覆盖问题，提出了一种基于Voronoi图的WSN栅栏构建算法。从实验数据分析可知，构成栅栏的Voronoi多边形数目随着部署传感器节点数量的增加而增加，当部署传感器节点的密度升高，构建的栅栏数目也呈递增趋势。该算法能够在无线传感器网络节点覆盖密度较低且不均，已经形成了少量栅栏空洞的情况下快速实现监测区域的栅栏覆盖，为下一步开展空洞修复研究奠定基础。
参考文献
[1] PARK D J，KIM K，LEE P J.Public key encryption withconjunctive field keyword search[M]//Information Security Applications. Berlin/Heidelberg：Springer，2004：73—86.
[2] HOU J C，YAU D K Y，MA C Y T，et al.Coverage in wireless sensor networks[J]. Guide to Wirdless Sensor Networks，2009，3（5）：47—79.
[3] GAGE D W.Command control for many-robot systems[J].Unmanned Systems，1992，10（4）：28—34.
[4] KUMAR S，LAI T H，ARORA A.Barrier coverage with wireless sensors[C]//MobiCom 2005：Proceedings of the 11th Annual International Conference on Mobile Computing and Networking.NewYork：ACM，2005：284—298.
[5] 郭新明.高效无线传感器网络强k-栅栏覆盖节能算法[J].计算机应用，2013，33（8）：2014—2017.
[6] 韩睿松.无线多媒体传感器网络覆盖增强与拓扑控制技术研究[D].北京：北京交通大学，2018.
[7] 范兴刚，王超，杨静静，等.一种基于选择框的有向K-栅栏构建算法[J].计算机学报，2016，39（5）：946—960.
[8] 郭新明，王宇，魏浩，等.视角受限的无线传感器网络强栅栏覆盖算法设计[J].咸阳师范学院学报，2016，31（6）：58—61.
[9] 邓绯.无线传感器网络栅栏覆盖的研究与仿真[J].西南师范大学学报：自然科学版，2015，40（5）：94—100.
[10] 吴菊英，冯秀芳.有向传感器网络中弱栅栏覆盖构建算法[J].计算机工程与设计，2016，37（10）：2685—2689.
[11] 郭新明，李康，陈伟，等.有向无线传感器网络弱栅栏覆盖构建算法设计[J].咸阳师范学院学报，2018，33（6）：53—56.
[12] 秦宁宁，盖祎，张林，等. Voronoi图在无线传感器网络栅栏覆盖中的应用研究[J]. 计算机应用研究，2008，25（3）：863—865.
[13] 黨小超，马如仓，郝占军.基于Voronoi的无线传感器网络栅栏覆盖策略[J].计算机工程与应用，2018，54（2）：91—96.
[14] 严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2007：190—192.
[15] 周培德.计算几何——算法设计、分析与应用[M].第5版.北京：清华大学出版社，2016：146—147.
