基于Voronoi盲区的三维无线传感器网络覆盖优化算法

方 伟，梅希薇

(江南大学 物联网工程学院，江苏 无锡214122)

基于Voronoi盲区的三维无线传感器网络覆盖优化算法

方 伟，梅希薇

(江南大学 物联网工程学院，江苏 无锡214122)

针对三维空间内无线传感器网络(wireless sensor network, WSN)的覆盖优化问题，提出了一种基于Voronoi盲区的三维无线传感器网络覆盖优化算法(blind-zone centroid-based scheme in three dimensional wireless sensor network area, BCBS-3D). BCBS-3D算法对随机部署的无线传感器进行Voronoi图划分，依据传感器对应的三维Voronoi多面体的覆盖情况构造盲区图，将三维Voronoi盲区重心为候选优化位置，最大化覆盖监测区域.仿真结果表明，在基于Voronoi图的情况下， BCBS-3D算法在覆盖率和平均移动距离方面具有优势.

无线传感网;三维空间;覆盖优化;理论节点个数

0 引言

随着无线传感器网络(WSN)[1]在更多领域的推广，仅仅研究其在二维平面中的应用已经不能满足人们对生产生活的需求.覆盖优化作为WSN发展的关键技术之一，将其二维平面中的研究结果应用到三维空间成为当前研究的一个趋势[2].在二维平面中，常用基于计算几何的Voronoi图划分来设计覆盖优化算法[3].在三维空间中，可以采用多胞形四面体剖分方式来设计覆盖优化算法.四面体网格是Voronoi图的几何对偶图，它有严格的数学定义和完备的理论基础.

与二维平面的感知模型相比，三维均匀区域的覆盖问题可以看成三维球覆盖问题[4].Chen 等[5]研究了三维Voronoi单元的数据结构，依据拓扑信息提出了三维网格剖分方法.Zou等[6]提出了虚拟力(virtual forces algorithm,VFA)的概念，设计了在节点初始随机放置后利用虚拟力完成自动部署的算法.在Li等[7]提出的VFA-3D算法中，除传统虚拟力外，还加入了中央万有引力和平衡力以便获得更好的传感器分布.魏宁等[8]提出的TD-VFA盲区的无线传感器网络覆盖控制部署策略，提高了传感器初始随机部署后的覆盖率.

笔者基于前期研究的Voronoi图法[9]，在二维平面中寻找覆盖盲区的优势以及三维球覆盖模型与多胞形四面体的剖分方式，提出了基于Voronoi盲区的三维无线传感器网络覆盖优化算法(BCBS-3D).

1 三维空间WSN覆盖优化模型

1.1 问题描述

如图1所示，在大小为L×W×H(长宽高)的三维平面监测区域T内，随机部署N个传感器节点S={s1,s2,…,si,…,sN}(i∈[1,n]),si的感知范围是以该节点为圆心,感知半径为Rs、通信半径Rc=2Rs的球形区域，用位置坐标si(xi,yi,zi){si={p∈L×W×H|ds(p,si)≤Rs}表示，ds(p,si)为点p与si的欧氏距离，传感器节点为同构节点(感知半径相同).当前节点si与邻居节点[9]zi组成的节点集表示为Di={si,z1,z2,…,ze}.网格点位置记为tj=(xj,yj,zj)j,j∈[1,t]，网格密度影响覆盖率CR的精确度.

图1 三维传感器部署Fig.1 WSN deployment in 3D area

1.2 基本概念

空间离散化[10]：求解覆盖率问题时，首先在监测区域内构造离散网格单元，如图2(a)将三维感知模型映射到二维平面，可看到离散的网格单元边界和实际边界.若离散的网格单元边界上某点与实际给定的边界点重合，则实际边界条件为离散的网格单元边界条件，但实际情况下大部分边界点不是实际边给定的边界，需要计算当前传感器节点si与网格点tj距离d(si,tj)，若dsi≤Rs，则网格点tj被覆盖，记为gtj=1，否则gtj=0.

图2 离散网格单元Fig.2 Discrete grid cell

覆盖率CR:定义覆盖率为当前传感器覆盖体积与当前网格覆盖情况下的最大覆盖体积的比值，是网格区域覆盖质量的一个量度，节点覆盖的总体积取集合概念中的并集.网格密度不同，传感器的覆盖体积不同.

(1)

式中：Ai为第i个节点的覆盖体积；N为节点的数目；A为整个目标区域的最大覆盖体积，本文中A的体积用网格点数t表示.

移动距离ds：表明传感器节点在运行过程中总共移动的距离.

(2)

式中：u表示运行次数；M表示迭代次数；N表示网络传感器节点总个数；(x1i,y1i,z1i)和(x2i,y2i,z2i)分别表示每个传感器节点迭代完成后的位置以及迭代前的初始位置.

2 BCBS-3D算法

2.1 三维空间Voronoi图划分

对三维空间传感器节点集S的Voronoi图划分是指将空间内任一传感器节点si与最近节点按特定方式划分空间，使得每个空间内有且仅有一个传感器节点，这个多面体空间就是Voronoi区域，Delaunay三角剖分是Voronoi图的对偶直线[11].Voronoi图划分给每个节点对应的结构单元划分了最佳形状.如图3所示三维Voronoi图：s1、s2、s3、s4、s5、s6、s7分别为凸胞体的7个顶点，ts1s2s3s4、ts1s2s4s5、ts2s3s4s6分别表示四面体V(s1)、V(s2)、V(s3)，f1、f2、f3分别是Voronoi单元V(s1)和V(s2)、V(s2)和V(s3)、V(s2)和V(s3)的公共面，实线e1、e2、e3为公共面的共享边(如e3所在的面有f1、f2、f3)，实线和虚线的交点v1、v2、v3、v4表示外接球球心，也是Voronoi顶点.按照四面体的访问顺序访问各四面体未访问过的相邻四面体，构造对应的Voronoi图，直到所有的四面体都被访问过为止，这样便得到给定点集的三维Voronoi图.

图3 三维Voronoi模型Fig.3 3D Voronoi model

2.2 三维Voronoi重心

(3)

(4)

(5)

三维Voronoi重心算法是对三维序列重心[11]算法进行的改进：将三维空间的多面体分为边、面、体3部分.边区域重心为其中点；面区域重心将多面体区域的节点按z坐标由小到大非递增排序，求出各区域重心后取平均值，面区域重心由式(3)和(4)得到；体区域取其最远两点的中点.

2.3 三维泰森盲区多面体

三维泰森盲区多边形是指在部署过程中移除当前传感器节点后，根据邻居节点和边界对该节点感知圆盘的覆盖情况，对未被覆盖部分构造与之相似的多边形. BCBS算法对此进行改进：泰森多边形顶点全覆盖时，盲区顶点为邻居节点与当前感知圆盘[9]交点，如图4所示.虚线表示新的传感器与邻居节点感知圆盘的交点(1、2、3、4)围成的多边形，图中正中央的实心三角形为盲区多边形形心，通过比较在不同形心位置的覆盖率来选择最佳部署节点位置；泰森多边形顶点部分覆盖时，如图5所示.盲区顶点为已覆盖顶点的邻居节点与当前感知圆盘交点(3、4、5)，以及未覆盖的顶点(1、2)围成的多边形；泰森多边形顶点都没被覆盖时，盲区为当前传感器所在泰森多边形的顶点.继而通过对盲区形心和伪形心位置的选取，来提高监测区域的覆盖率.

图4 Voronoi多边形顶点全部覆盖Fig.4 Full coverage of Voronoi polygon vertices

三维空间的BCBS-3D算法对感知盲区的处理方式为构造泰森盲区多面体，并依据其顶点覆盖情况讨论盲区的形状.泰森盲区多面体顶点全部覆盖时，盲区顶点为邻居节点与当前感知球域交点；部分覆盖时，盲区顶点为已覆盖顶点的邻居节点与当前感知球域交点以及未覆盖的顶点；都未被覆盖时，盲区顶点为当前传感器所在泰森多面体的顶点.继而通过对盲区重心和原多面体重心位置的选取来提高监测区域的覆盖率.BCBS-3D算法方式的优势为通过Delaunay三角网将三维Voronoi单胞划分成若干不重叠且充满Voronoi单胞的四面体, 从而可简单地通过对四面体体积(格点)的计算得到Voronoi 单胞的体积.

图5 Voronoi多边形顶点部分覆盖Fig.5 Partial coverage of Voronoi polygon vertices

如图6～8所示，传感器节点形成的感知球域之间存在重合、相交、相切，相离(外离和内含)的关系.对三维监测区域划分后，每个传感器节点都有与之对应的三维泰森多面体[12]，传感器节点在监测区域内自由移动，划分后的泰森多面体与边界存在约束关系，可通过检查当前泰森多面体是否超出边界来决定是否对顶点进行修改.

关系1：如图6(a)，当前节点所在凸胞全部被覆盖，且存在泰森盲区.如图6(b)，盲区多面体由交面1、2、3、4构成，叉表示泰森盲区多面体重心位置，实心三角形表示泰森盲区多面体的重心位置，优化后节点分布的均匀性得到提高.

图6 全部被覆盖 Fig.6 Full coverage graph

关系2：当前节点所在凸胞全都未被覆盖，则泰森盲区多面体与原泰森多面体相同.注：泰森盲区多面体不限于凸多面体, 有时也会产生凹多面体, 所以会出现三维Voronoi重心位于多面体之外的情况.当泰森盲区多面体重心位于泰森多面体以外时, 取原泰森多面体重心.

关系3：如图7(a)，当前节点所在凸胞部分被覆盖，且与邻居节点感知球域的交面在边界内，则存在感知盲区.如图8(b)，盲区多面体为交面1、2、3、4以及未覆盖面1、2构成，优化后节点能更快地向盲区移动, 覆盖节点自身对应的泰森多面体, 提高覆盖效率.

图7 部分被覆盖且交面在边界内Fig.7 Partial coverage and intersect surface in the boundary

关系4：如图8(a)，当前节点所在凸胞部分被覆盖，且与邻居节点感知球域的交面在边界外，则存在感知盲区.如图8(b)，盲区多面体为交面1、2、3、4以及未被覆盖的当前凸胞(未覆盖面1、2)，其余为边界区域.

图8 部分被覆盖且交面在边界外Fig.8 Partial coverage and intersect surface outside of the boundary

2.4 BCBS-3D算法描述

根据2.3节三维泰森盲区多面体的4种情况, 提出基于Voronoi盲区的三维无线传感器网络覆盖优化覆盖(BCBS-3D)算法：

步骤1 三维空间内随机部署N个传感器结点，得到传感器节点集S.

步骤2 计算每个节点si在当前位置(xi、yi、zi)对应的初始局部覆盖率qi.

步骤3 构造初始三维空间Voronoi图.

步骤4 判断当前凸胞内是否存在盲区.

步骤5 当前节点与邻居节点的节点集Di，对应三维空间内的Voronoi集合为Vk.

步骤6 若为2.3节关系1，则顶点全覆盖，转步骤9；若为关系2，则盲区多面体与原泰森多面体相同；若为关系3，则盲区多面体由交面fi和未被覆盖的当前凸胞构成；若为关系4，则盲区多面体由交面fi及未被覆盖的当前凸胞和边界构成，进入下一步骤.

步骤7 由三维Voronoi重心公式得到di在盲区V(si)处的重心vi，计算覆盖率ti，再计算在当前位置的覆盖率qi.

步骤8 如果qi≥ti，则保留当前位置，转步骤10；否则用vi替换di，继续步骤9.

步骤9 暂时删去vi，得到邻居节点V'e={v'z1,...,v'ze},对应Voronoi多面体V(e)集合Z'e={z1,...,ze}， 如果V(e)内存在盲区，则根据关系2、3、4中的情况构造盲区，转步骤7；否则用V(e)重心vi替换di位置.

步骤10 重复步骤4～9，直至每个节点都判断一遍是否存在盲区.

步骤11 重复步骤3～10，直至迭代结束.

3 实验仿真与分析

笔者从CR和ds两方面研究BCBS-3D算法的性能.用Matlab平台进行实验仿真, 监测区域T设置为20 m×20 m×20 m. 传感器节点的Rs为3.3 m，计算可得最多能不重合部署27个传感器节点，对应的理想情况下网格点数占总网格点数比率：在网格点密度为0.5 m情况下是47.46%，1.0 m情况下是43.53%.

图9表示网格点密度grid分别为0.5 m和1.0 m的条件下, BCBS-3D与TD-VFA算法[6]使用27个传感器节点随机部署30次的结果.从图9中覆盖率曲线的变化情况可看出,在相同网格密度下部署实验, BCBS-3D算法的覆盖率总是优于TD-VFA网格点. 在网格点密度0.5 m时，TD-VFA算法最终覆盖率为89.65%,而BCBS-3D算法是94.42%，高出TD-VFA算法4.77%. 在网格点密度为1.0 m时，TD-VFA算法最终覆盖率为94.03%,而BCBS-3D算法是96.39%，高出TD-VFA算法2.36%. 由此可见，网格点密度越高，BCBS-3D算法的覆盖率优势越明显，因为BCBS-3D算法就是通过从不规则Voronoi多面体中所有网格求重心提高覆盖率的.图10表明BCBS-3D算法平均移动距离小于TD-VFA算法，这可以减少传感器的移动能耗.

图9 覆盖率曲线Fig.9 Coverage rate curve

图10 平均移动距离Fig.10 Average distace

4 结论

覆盖优化一直以来都是无线传感器网络中的研究热点，笔者提出的BCBS-3D算法将圆覆盖平面问题引申至球体覆盖三维空间，将复杂的体积覆盖转为空间网格点覆盖问题，并对盲区多面体的不同覆盖方式给出了对应的解决措施，再根据三维Voronoi重心引出对三维盲区多面体重心的计算，方便了对泰森盲区多面体重心的优化.

[1] 阎新芳, 严晶晶, 冯岩，等.WSN中基于梯度和粒子群优化算法的分级簇算法[J].郑州大学学报(工学版), 2016, 37(2):33-36.

[2] ZHSANG L, MA P, JIN M, et al. Research on a firefly localization algorithm based on RSSI ranging for 3D wireless sensor networks[J].Chinese high technology letters, 2016，26(1):1-7.

[3] 贾程, 陈卉卉. 一种单位分解三角形单元及其在动力响应分析中的应用[J]. 郑州大学学报(工学版), 2012, 33(6):125-128.

[4] 张磊. 面向无线传感器网络的三维覆盖策略研究[D]. 南京邮电大学计算机学院, 2013.

[5] CHEN S, CHENG L, LI M. Autonomic visiting in digital 3D scenes[J]. Earth science informatics, 2016,9(3)：1-18.

[6] ZOU Y, CHAKRABARTY K.Sensor deployment and target localization based on virtual forces[C]//Joint conference of the IEEE computer and communications. San Francisco, CA, USA: IEEE societies, 2003: 1293-1303.

[7] LI X,LI C,YANG M,et al. Deploying three-dimensional mobile sensor networks based on virtual forces algorithm advancesin wireless sensor networks[J].Commuications in computer and in formation science,2013, 334(7):204-216.

[8] 魏宁. 无线传感器网络的三维空间覆盖与目标定位问题研究[D]. 西安电子科技大学通信工程学院, 2009.

[9] 方伟,宋鑫宏. 基于Voronoi图盲区的无线传感器网络覆盖控制部署策略[J]. 物理学报, 2014,63(22): 128-137.

[10]陈斌. 客车车身周围流场数值模拟的空间离散化研究[D]. 长安大学公路学院, 2000.

[11]陈嘉兴, 刘志华. 三维无线传感器网络节点的序列重心定位算法[J]. 计算机工程与应用, 2011, 47(2):81-83.

[12]林海峰, 刘晓红. 对海洋污染状况预测方法的研究[J]. 天津航海, 2013(1):60-62.

Blind-Zone Centroid-Based Scheme in Three Dimensional Wireless Sensor Network Area

FANG Wei,MEI Xiwei

(School of Internet of things Engineering, Jiangnan University, Jiangsu Wuxi 214122,China)

For the problem of coverage optimization in Wireless Sensor Network(WSN), a blind-zone centroid-based scheme in three dimensional area(BCBS-3D) was proposed. In the three-dimensional monitoring region, BCBS-3D partitioned random sensors by Voronoi diagram. According to the coverage of three dimensional Voronoi polyhedron, blind-zone diagram could be constructed clearly. BCBS-3D also regarded the centroid of blind-zone area as the optimal position, so as to maximize the monitoring area. Simulation results showed that BCBS-3D hadobvious advantages in coverage rate and distance compared with other algorithms that based on Voronoi diagram.

wireless sensor networks; three dimension area; coverage optimization; theoretical number of sensors

2016-11-10；

2016-12-10

国家自然科学基金资助项目(61105128,61170119,61373055);江苏省自然科学基金资助项目(BK20131106，BK20130161);江南大学自主科研计划重点项目资助项目(JUSRP51410B);中国博士后基金资助项目(2014M560390)

方伟(1980— )，男，江苏扬州人，江南大学副教授，博士，主要从事群体智能研究，E-mail:wxfangwei@hotmail.com.

1671-6833(2017)04-0073-05

TP393

A

10.13705/j.issn.1671-6833.2017.01.019