基于蜂窝网格的确定性节点部署算法

赵小敏，蒋双双

(浙江工业大学 计算机科学与技术学院， 浙江 杭州 310023)



基于蜂窝网格的确定性节点部署算法

赵小敏，蒋双双

(浙江工业大学 计算机科学与技术学院， 浙江 杭州 310023)

摘要：如何有效的部署节点是传感器网络应用系统设计中首要考虑的问题，它直接关系到系统的成本和服务质量.针对含有透明障碍物环境中无线传感器网络的节点部署问题，提出一种基于蜂窝网格的确定性节点部署算法CG-deployment，通过计算几何法确定并修复由于透明障碍物的存在而造成的覆盖空洞.仿真结果表明：在对目标监测区域实现全覆盖的情况下，CG-deployment算法所需要的节点数目比DT-Score算法和随机部署方法更少，有效的节约了网络的部署成本.

关键词：蜂窝网格；无线传感器网络；节点部署；障碍物

无线传感器网络(Wireless sensor networks, WSN)是由部署在监测区域内大量的微型无线传感器节点组成，已在工业监控、环境监测、智能家居等领域有着广泛的应用[1-2].WSN节点如何部署，关系到是否可以有效感知所关心的区域、部署成本高低和如何避免覆盖盲区等重要问题，它直接影响着无线传感器网络的服务质量，是建立无线传感器网络实际应用系统必须要解决的关键问题之一.目前大多数的节点部署研究都是考虑理想环境的情况，然而在真实的环境中，例如树、墙、建筑物等障碍物都会影响节点之间的网络连通性，从而造成覆盖空洞.目前对有障碍物遮挡环境中传感器节点的部署研究较少.DT-Score[3]是一种节点部署的启发式贪婪算法，用来最大化障碍物环境下的覆盖率.DT-Score算法分为两阶段，第一阶段沿边界和障碍物等高线部署节点，以避免死角无法覆盖，第二阶段根据Delaunay三角剖分在未覆盖区域添加传感器节点，直到满足覆盖率或达到限定的节点覆盖的最大数目.TAN等[4]提出基于计算几何的确定性完全覆盖部署方法，适用于规则或不规则的障碍物和区域.文献[5-6]提出在存在透明和不透明的障碍物环境下，利用计算几何中平面扫描算法(Sweep line algorithm)和双向链接边表(DCEL)，评估目标区域的覆盖情况并提出冗余节点的检测和消除方法.DVFA(Distributed virtual forces algorithm)算法[7]提出在存在障碍物的情况下，将障碍物视为排斥力，来重新部署传感器节点.KHOUFI等[8]提出一种简单的基于二维投影的方法来最小化覆盖区域所需的无线传感器节点的数目.

针对含有障碍物遮挡环境下的WSN节点部署问题，将网络的覆盖问题抽象成圆覆盖问题，提出一种基于六边形蜂窝网格的确定性节点部署算法，并利用计算几何的方法确定并修复覆盖空洞.算法假设已知障碍物的具体位置，首先用正六边形对平面进行无缝拼接，正六边形外接圆的圆心为节点部署的位置，由于透明障碍物的存在，落入透明障碍物内部的节点无法与其他节点进行通信，从而产生覆盖空洞.对被屏蔽节点的内接正六边形与障碍物进行布尔差运算，得到近似空洞的多边形，找到其对应最小覆盖圆，再确定新增节点的位置，最终实现目标区域的完全覆盖.

1部署问题分析描述

1.1　感知模型

假定监测区域A为二维平面，所有节点同构且不可移动.各节点感知半径为rs，通信半径为rc，为了保证网络的连通性rc≥2rs，即保证网络在充分覆盖时是连通的.

节点感知模型为二元感知模型，该模型是一个以传感节点为圆心，节点监测半径rs为模型半径的一个概率圆.即以Si节点为感知区域圆心，以节点的监测半径rs作为圆形感知区域半径.若事件P(x，y)发生在圆形感知区域内，则被监测的概率Cp(Si)为1，否则概率为0.d(P，Si)为节点Si到P(x，y)的欧式距离.其公式为

(1)

1.2　部署问题描述

节点部署方法一般有确定性部署和自组织部署.前者是指手工部署节点，一般适合规模较小、环境状况良好、人工可以到达的区域，其特点是环境已知、网络相对固定，预先配置节点位置，并根据目标区域的具体情况确定网络拓扑、传感器节点密度和预定探测概率情况下的节点数目.已知含有障碍物的目标监测区域范围确定且规模较小，决定采用确定性部署.障碍物分为透明障碍物(Transparentobstacles)和不透明障碍物(Opaqueobstacles)[5].如图1所示，透明障碍物只阻碍节点间的通信，但不影响节点对目标区域的感知；不透明障碍物则阻碍节点间的通信，从而使节点丧失感知能力.下文只考虑透明障碍物的情形，所指的障碍物都是指透明障碍物，其位置和大小信息可从初始化配置文件中获取.

假设目标监测区域为二维确定性区域，用A表示，含有透明障碍物n个，透明障碍物i所占的区域为Obsi，O=∪i=[1,n]Obsi表示障碍物的集合.需要节点监测的区域为A-O.提出一种基于蜂窝网格的部署算法(CG-depolyment，deploymentbasedoncellulargrid)，使得存在障碍物的目标监测区域内实现全覆盖所需要的节点数目最少.

图1　不同障碍物对传感器节点感知的影响Fig.1　The influence of the sensors in a region containing transparent and opaque obstacles

2部署算法

2.1　基于蜂窝网格的初始化部署

图2　基于蜂窝网格的初始化部署Fig.2　Initial deployment based on cellular grid

图3　边界最佳部署Fig.3　Optimal deployment along a border

图4　6个交点构成蜂窝Fig.4　Cellular grid made of 6 points of intersection

2.2　修复覆盖空洞

假设空洞边缘节点1~7互为感知邻居，这些节点互相连接围成空洞，a~g为空洞边缘交叉点，如图5所示.由空洞边缘交叉点所围成的多边形，近似于空洞，包含多边形最小圆的圆心坐标就是修复空洞的节点部署的最佳位置.

图5　覆盖空洞的界定Fig.5　Definition of coverage holes

这里的覆盖空洞有两种，一是节点放置在目标检测区域的外部而造成的空洞，二是节点放置在障碍物内部造成的空洞.由于环境中含有透明障碍物，第二种空洞边缘交叉点是由空洞边缘节点和障碍物共同围成.初始化部署时假设障碍物不存在，基于蜂窝网格划分，节点分布均匀.如图6所示，深灰色区域为近似于空洞的多边形，近似于覆盖空洞大小的多边形PL可以看成Nobs对应的Hobs与障碍物Obsi之间的布尔差运算所得到的结果，深灰色区域就是PL的顶点坐标所围成的多边形，PL.

图6　由障碍物造成的覆盖空洞Fig.6　The coverage holes caused by transparent obstacles

对于第一种空洞情况，如图7(a)所示，AB为边界，节点C位于目标检测区域的外部，做节点位置C到边界AB的正交投影，投影点为C′，此时C′为节点重新部署的位置.如图7(b)所示，当节点C正交投影点落在目标监测区域外部时(这种情况发生在右上角最后一个节点的部署上)，以C为圆心的圆与上边界交于A点，B为边界的顶点，此时线段AB的中点C′作为节点重新部署的位置.对于第二种空洞，首先确定近似覆盖空洞大小的多边形PL，再确定包含PL的最小圆圆心O的坐标(x，y)及半径r0.由于PL是其对应的Hobs的一部分，所以r0肯定小于等于感知半径.如图8所示，若圆心O位于障碍物ABCD的内部(不包括边界)，则分别做圆心O到障碍物边(到圆心O的距离小于感知半径的边)的正交投影点O′，O′为新增节点部署的位置.反之，若圆心O在障碍物外部，此时圆心O为新增节点部署的位置.

图7　投影的两种情况Fig.7　Two cases of projection

判断交点的凹凸性是关键，根据不同的相交情况分为四种情况，如图9所示.

图8　圆心在障碍物内部的情况Fig.8　Center of the circle inside the transparent obstacle

图9　交点的凹凸性Fig.9　Definition of concave & convex point of intersection

算法1确定近似空洞的多边形.

1) 对于A多边形的每条边e1和B多边形的每条边e2，如果e1和e2存在交点，则将交点顺序插入两个多边形顶点的集合中，使得A多边形顶点的集合及其交点成逆时针排列，B多边形顶点集合及其交点成顺时针排列.

2) 从A多边形的某一交点I出发，根据A多边形中以该交点为终点的矢量与B多边形中以该交点为起点的矢量判定该点的凹凸性.若为凸点，则沿B多边形遍历，若为凹点，则继续沿着A多边形遍历.每遇到一个凸点，转向另一个多边形，否则继续遍历当前多边形，在遍历的过程中，A多边形的遍历方向始终保持逆时针，B多边形的遍历方向始终保持顺时针.直到再次遇到交点I，结束本次遍历.从I开始至I结束的多边形即为差集的一部分.重复上述过程，直到遍历完所有交点，每次循环都是A与B的差值的结果.

3) 上一步骤所得到的差集∂C即为空洞边缘交叉点所围成的多边形的集合，包含多边形最小圆的圆心为空洞的填补点.

算法2确定包含多边形的最小圆.

1) 确定多边形中两两顶点之间距离最远的线段为长轴L.

2) 计算多边形各顶点到长轴的距离，最远点与长轴构成三角形ABC，外接圆为O，半径为r.

3) 计算多边形各顶点到外接圆圆心的距离，若距离的最大值小于r，则该外接圆为包含多边形的最小圆.反之，则转至步骤4).

4) 取步骤3)距离最大值的点p，计算点p到三角形ABC各顶点的距离，p点取代距离最近的点作新的三角形，计算最小外接圆，返回第2)步继续迭代.

5) 获得最小圆的半径r0和圆心O坐标(x0，y0)后，判断圆心与离它最近的障碍物Obsi之间的位置关系，若圆心在在障碍物外部(包括边界上)，则算法结束，圆心的位置即为新增节点部署位置，反之，转至下一步.

6) 若圆心O位于障碍物内部，则做圆心到距圆心距离小于感知半径的障碍物边的正交投影，投影点为O′，此时O′的位置为新增节点部署的位置.

3仿真实验与结果分析

为了验证算法的有效性，假设在100 m×100 m的监测区域内，使用matlab对无障碍物和含有障碍物的情况分别进行节点部署仿真实验，将CG-depolyment算法与DT-Score算法[3]以及随机部署Random算法做比较，实验结果都为50次仿真实验的平均值.

在无障碍物的情况下，随着感知半径的变化，达到指定的覆盖率所需的节点数目如图10所示.在同一覆盖率要求下，随机部署算法需要的节点数目最多，由于节点部署的随机性，很难达到100%的覆盖率要求.即使在100%覆盖率要求的情况下，CG-depolyment算法和DT-Score算法所需的节点数也比覆盖率要求只为90%的随机部署算法所需的节点数目少.在覆盖率要达到100%的要求下，CG-depolyment算法比DT-Score算法所需的节点数目少.图11为感知半径为3 m，覆盖率为100%时CG-depolyment算法和DT-Score算法的部署结果.DT-Score算法实现完全覆盖所需的节点数目为531个，而CG-depolyment算法仅需460个节点就可达到完全覆盖，减少了13.4%.在无障碍物的情况下，CG-depolyment算法实质上是基于蜂窝网格的传感器节点部署算法，充分利用了每个传感器节点的覆盖圆盘，即节点之间的重叠面积最小，使得目标区域内节点最少.

图10　无障碍物时感知半径不同所需节点数目变化情况Fig.10　The number of sensor nodes change with sensing radius when there is no obstacle

图11　无障碍物时的节点部署结果Fig.11　The result of sensors deployment configured without obstacles

假设监测区域内含有10个障碍物，其位置信息可以从初始化的配置文件读取.当传感器节点的感知半径为3 m，覆盖率为100%要求下，CG-depolyment算法和DT-Score算法的部署结果如图12所示.在有障碍物的环境中，DT-Score算法实现完全覆盖需要472个节点，而CG-depolyment算法只需448个节点即可实现完全覆盖，节点数减少了5.1%.当传感器感知半径不同时，实现指定的覆盖率所需节点数目的变化情况如图13所示.CG-depolyment算法达到完全覆盖所需要的节点数目少于DT-Score算法，也远小于随机算法达到90%覆盖率所需节点数.在CG-depolyment算法中，当传感器节点在平面内呈正三角形覆盖，节点之间构成正六边形蜂窝网格，有效覆盖率达到最高.采用计算几何的方法能快速求出Nobs对应的Hobs与障碍物Obsi之间的布尔差，得到近似空洞的多边形，再求出覆盖近似空洞的多边形的最小圆，圆心即为新增节点部署的位置.CG-depolyment算法与DT-Score算法相比,算法简单，易于实现，而DT-Score算法在初始边界线部署完成后，每次选取候选节点都需要进行Delaunay三角剖分，时间复杂度较高.CG-depolyment算法使得节点在目标监测区域内分布均匀，在使用较少的节点数时就可以达到最优的覆盖率，大大降低了部署成本.

图12　存在透明障碍物时节点部署结果Fig.12　The result of sensors deployment configured with transparent obstacles

图13　存在障碍物时感知半径不同所需节点数目变化情况Fig.13　The number of sensor nodes change with sensing radius when configured with obstacles

4结论

针对含有障碍物环境中的节点部署问题，提出

了一种基于蜂窝网格的确定性部署算法CG-deployment，修复了由于透明障碍物的存在而造成的覆盖空洞问题，并且确定近似空洞的多边形的最小覆盖圆的圆心，通过部署新增的传感器节点，使得节点对目标监测区域达到100%完全覆盖.下一步的研究工作主要考虑网络动态运行中的空洞修复以及如何进一步延长网络生命周期等问题.

参考文献：

[1]周晓，李杰，边裕挺.基于无线传感器网络的环境温度监测系统设计[J]．浙江工业大学学报，2013，41(4)：440-443．

[2]周晓，边裕挺，李杰．基于Android智能终端的WSN监控系统[J]．浙江工业大学学报，2013，41(5)：558-5610．

[3]WU C H, LEE K C, CHUNG Y C. A delaunay triangulation based method for wireless sensor network deployment[J]. Computer communications，2007，30(14)：2744-2752．

[4]TAN H, WANG Y, HAO X, et al. Arbitrary obstacles constrained full coverage in wireless sensor networks[M]. Halifax: Springer Berlin Heidelberg，2010：1-10．

[5]FOTOUHI A, RAZZAZI M. Redundancy and coverage detection in wireless sensor networks in the presence of obstacles[C]//Proceedings of the 34th International Convention on MIPRO. Opatija: IEEE，2011：541-546．

[6]RAZZAZI M, FOTOUHI A. Coverage of wireless sensor networks in the presence of transparent obstacles[C]//Proceedings of International Conference on Software, Telecommunications and Computer Networks (SoftCOM). Split: IEEE，2010：209-213．

[7]MAHFOUDH S, KHOUFI I, MINET P, et al. Relocation of mobile wireless sensors in the presence of obstacles[C]//Proceedings of 20th International Conference on Telecommunications (ICT). Casablanca: IEEE，2013：1-5．

[8]KHOUFI I, MINET P, LAOUITI A, et al. A simple method for the deployment of wireless sensors to ensure full coverage of an irregular area with obstacles[C]//Proceedings of the 17th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems. New York: ACM，2014：203-210．

[9]ROY S B, DAS G, DAS S. Computing best coverage path in the presence of obstacles in a sensor field[M]. Halifax: Springer Berlin Heidelberg，2007：577-588．

(责任编辑：刘岩)

Deterministic node deployment algorithm based on cellular grid

ZHAO Xiaomin, JIANG Shuangshuang

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:How to effectively deploy sensor nodes is a primary consideration in wireless sensor network application system, which influences the cost and quality of service. For wireless sensor network node deployment problem in a region containing transparent obstacles, the paper proposed a node deployment method, named as CG-deployment, based on cellular grid. The algorithm uses computational geometry techniques to identify and fix coverage hole caused by transparent obstacles. The simulation results show that, in the case of the target to achieve full coverage of the monitoring area, the proposed algorithm requires fewer nodes than DT-Score and random deployment methods. It can effectively save the cost of network deployment.

Keywords:cellular grid; wireless sensor network; node deployment; obstacles

中图分类号：TP391

文献标志码：A

文章编号：1006-4303(2016)01-0039-06

作者简介：赵小敏(1976—)，男，浙江文成人，副教授，博士，研究方向为无线传感器网络和信息安全，E-mail：zxm@zjut.edu.cn．

收稿日期：2015-09-04