基于Voronoi算法的无线多媒体传感器网络覆盖控制研究

霍海平，曾建潮，赵 静

(太原科技大学电子信息工程学院，太原 030024)



基于Voronoi算法的无线多媒体传感器网络覆盖控制研究

霍海平，曾建潮，赵 静

(太原科技大学电子信息工程学院，太原 030024)

无线多媒体传感器网络(Wireless Multimedia Senor Networks，WMSNs)的覆盖控制技术是传感器网络研究的关键问题，只有合理的部署传感器节点，才能达到对目标区域的全面监测。Voronoi图具有良好的区域划分性质，可以将监测区域划分成多个小的区域。所以，提出一种基于Voronoi算法的无线多媒体传感器网络的覆盖策略。通过Voronoi图形寻找新增传感器节点的坐标，计算出节点的质心点坐标，调整节点的方向。实现用比较少的节点，获得较高的覆盖率。

无线多媒体传感器网络；Voronoi算法；质心；覆盖率

伴随着信息技术、微型计算机控制技术和新型传感器技术的不断发展，生产出来了能够进行环境感知、数据处理和信息通信的智能化传感器。而由这些传感器节点可以组成一个智能化的传感器网络，在该网络所覆盖的区域中，每个节点可以感知、收集和处理各类数据信息，并将这些信息发布给需要这些信息的用户[1]。而多媒体传感器网络(Wireless Multimedia Senor Networks，WMSNs)一方面继承了无线传感器网络(WSNs)的原有特点，同时又具备了上述所说的各项功能。因此，WMSNs也日益成为了一个新兴的研究领域。

网络覆盖是设计传感器网络的关键环节，对于WSNs而言，节点的感知模型为圆形感知模型，网络覆盖算法也非常成熟[2]。但是，对于无线多媒体传感器网络而言，节点的模型不在是圆形感知模型，而是有向的扇形模型。因此，针对多媒体传感器网络节点的特点，提出新的网络覆盖控制算法。文献[3]还讨论了通过网络的合理部署来讨论延长网络寿命等问题。文献[4]讨论了在随机部署和网格部署下，节点的能耗与部署方式的关系。所以，网络覆盖是研究WMSNs的基本问题。

针对节点的模型是扇形感知模型的特点，提出了几种不同的网络覆盖策略。文献[5]戴宁等提出了在目标区域中，采用重叠质心和节点的质心来调整传感器节点，在虚拟势场力的作用下调整节点方向，以此提高了网络覆盖率。文献[6]彭玉旭等人提出了“质心Voronoi图”的概念，调整整个传感器网络中节点的方向。文献[7]提出了有关最大覆盖面积(MDAC)的问题，定义了要调整方向的节点与其邻居节点所对应的圆形覆盖下的交点或切点为候选点，之后再根据节点间的位置关系来调整方向。文献[8]采用虚拟势场的方式，对于有向传感器节点通过虚拟势场力来调整节点方向。另外有些研究通过采用传统的贪心算法或改进的贪心算法，进行网络的局部优化，通过多次迭代来完成节点的调整和部署[9-11]。利用Voronoi图形可以将监测区域分成多个小的监测区域，之后再放置节点。所以，根据Voronoi图的特点，寻找合理的位置放置传感器节点，完成部署任务[12-13]。在监测区域中，首先部署大量节点之后，得到相应的Voronoi图，利用凸耳消元法消去任意点[14]。在区域监控过程中，由于障碍物的存在，网络中可能存在漏洞点，可以利用Voronoi图和delaunay三角剖分，来对网络进行优化[15]。这些研究多数是针对随机部署，之后再调整节点和优化网络结构，这也只能提高局部位置上的覆盖率。有些采用贪心算法进行迭代部署，这样有可能会使得算法过于复杂。这些研究也很少涉及到确定性部署的问题，同时也未必能够使用比较少的节点，获得较高的覆盖率。

本文采用基于Voronoi图的原理，结合不可转动的有向扇形模型，来完成节点的部署任务。在目标区域中，首先放置少量节点，之后得到相应的Voronoi图形。分析图形特点，寻找合适位置准备下一轮的部署。由于节点是有向感知模型，所以，采用“质心”来确定节点的感知方向，最终实现使用比较少的节点，获得较高的覆盖率。

1 基于Voronoi算法的WMSNs覆盖研究

1.1 概念及节点模型

1)Voronoi图是指：由在平面上的任意相邻的多个点(a1,a2,…an)，其垂直平分线所组成的不规则多边形的集合[16]。如图1所示，在目标区域中，将少量传感器节点放置到个别关键位置上，得到对应的Voronoi图形。

图1 初始化节点位置

Fig.1 Initial nodes location

2)在图1中所示，A、B、C点称之为Voronoi图边上的顶点。

3)质心的概念

针对有向的扇形模型，其质心点的位置距节点的位置的长度为：L=2Rsinα/3α，且位于方向轴上。其中：α表示扇形模型的感知范围、R表示感知半径。为了调整有向传感器节点的方向，假设扇形节点的质心绕节点可以旋转[7]。

4)有向的扇形模型

在有向的节点模型中，其模型假设为：2α=900，α=450为感知范围；R=80 m为感知半径；V表示节点的方向；(xi,yi)表示节点坐标。

如图2所示，根据上述的节点模型，在初始化阶段，放置了13个传感器节点，每个节点的模型为有向的扇形模型。

图2 初始化13个扇形感知模型

Fig.2 Initial 13 sector perceptual models

1.2 算法描述

1.2.1 寻找合理的新增节点的位置

如图3所示，两个节点的连线与Voronoi图形的边相垂直，垂足为C点。同时，节点与Voronoi图形的边距离最小的点也是C点，也是覆盖最强的地方。从C出发点沿着Voronoi的边到达顶点处(A、B点)，监测的范围与节点的距离拉大，因此，节点的监控覆盖逐渐减弱。所以，A点或B点成为覆盖监测过程中比较薄弱的位置[12]。

同理，针对扇形感知模型覆盖时，Voronoi图形边上的顶点同样也是覆盖最薄弱的环境，所以，任然可以考虑将顶点坐标作为新增节点的坐标位置。

1.2.2 明确扇形节点的感知方向

针对扇形节点的特点，即：节点是有向的感知模型。如何放置节点就成为了提高网络覆盖率的一个关键环节。第一步，根据上述方法，找到放置节点的坐标位置。第二步，要确定扇形节点的感知方向。这时，引用质心的概念来明确节点的方向，使用比较少的节点，获得较高的覆盖率。

图3 根据Voronoi图的特点寻找新增节点的位置

Fig.3 the location of the new nodes to be found according to the features of Voronoi diagram

在监测区域中，不同的节点之间可能会彼此相互影响。当两节点之间的距离小于节点的通信半径时，才可能会出现覆盖重叠的情况。所以，当出现上述情况时，可以认为两节点间会彼此影响，同时存在相互作用力[18]。当满足上述条件的节点，就称之为邻居节点。

在两个相邻节点之间，其质心之间的作用力大小，定义如下：

(1)

如果质心点Ci与质心点Cj的距离不小于2倍感知半径时，对应的节点间的作用力为0.反之，则存在作用力。同理，当质心点Ci受到周围多个质心点的作用力时，当节点受力平衡时，节点就会固定在一个确定的位置。

如图4中所示，由节点S1、S2、S3、S4的坐标值，能够计算出S1与S2的距离L12、S1与S2的距离L13和S1与S4的距离L14，可以判断出L12和L13小于节点的通信半径、L14大于节点的通信半径。所以，S1同时会受到S2、S3的影响，而不会受到S4的影响。F12表示：质心点C2对C1的作用力,F13表示：质心点C3对C1的作用力。当F12和F13中沿着质心圆切线方向的分力不平衡时，质心会沿着质心圆的轨迹来调整节点的方向。通过微调节点的角度，如果沿着切线方向的受力平衡时，将节点调整到了合适的位置上。

图4 节点与其邻居节点

Fig.4 Nodes and its neighbor nodes

综上所述，在寻找节点的方向时。第一步，以节点为圆心，以节点与质心点之间的距离为半径画圆，此圆为质心圆。第二步，根据节点的坐标值，可以计算出节点间的距离，就可以判断出那些节点是邻居节点。第三步，当找到邻居节点之后，假设该节点周围有k个邻居节点，方向角是：(α1,α2…,αk).可以令：αi=(α1+α2+…+αk)/k为初始角，来放置新增节点并得到相应的质心圆。第四步，根据邻居节点的质心位置，进行受力分析，沿着质心圆来微调节点的方向。当质心点所受外力平衡时，此时就是新增的最终方向。

通过部署比较少的节点，获得较高的覆盖率。如图5所示，在初始化覆盖的基础上，继续寻找新增节点的位置，给该节点初始化一个方向，再根据上述的方法来调整其方向，之后进行迭代部署，就得到了第1次的覆盖情况。

图5 第1次覆盖

Fig.5 The first coverage

2 仿真与分析

实验是在MATLAB R2012a的环境下进行的，对所提出的算法进行仿真。在仿真实验中，令：α=450为节点感知范围，R=80 m为感知半径，在500×500 m2的目标区域中完成节点的部署。

在初始化阶段，在关键位置上放置13个节点，如图1和图2所示。之后，找到新增节点的坐标位置，给新增节点初始化一个方向角并且计算出质心坐标，调整节点方向。如图5所示，第一轮覆盖的情况，覆盖率为32.1%.如图6、7分别是第2次部署和第3次部署，覆盖率为45.71%和55.94%，使用节点数量分别是23个和29个。如图8所示，当通过10次的部署之后，使用62个节点，最终达到94.52%的覆盖率。

图6 第2次覆盖

Fig.6 The 2nd coverage

图7 第3次覆盖

Fig.7 The 3rd coverage

图8 第10次覆盖

Fig.8 The 10th coverage

在初始化部署阶段，其P0=26.13%.不断部署节点，覆盖率逐渐增加。当通过10次的部署之后，使用了62个节点，可以达到P10=94.52%.所以，通过Voronoi图形进行确定性部署，先来判断那些位置上可能是最大的覆盖漏洞点，之后选择合适的位置作为新增节点的坐标，利用质心来调整节点的方向，降低覆盖重叠度，能够合理的部署节点。最终达到使用比较少的节点，获得较高的覆盖率。

3 结束语

本文提出一种基于Voronoi图的WMSNs的覆盖控制策略，研究对象主要是不可转动的节点模型，采用确定性部署方案，通过迭代来完成网络覆盖任务，研究了如何能够获得较高的覆盖率。确定节点的坐标，计算节点的质心坐标，调整每个节点的方向，使得节点转到一个较为合理的方向上，降低重叠度，最后通过仿真实验来验证算法的合理性。接下来要讨论的是针对节点可以转动的情况下，如何完成节点的部署任务；以及有关网络的连通性与网络覆盖的关系。

[1] MA HUA-DONG,TAO DAN.Multimedia Sensor Network and Its Research Progresses[J]. Journal of Software,2006,17(9):2013-2028.

[2] 张璐.无线多媒体传感器网络覆盖技术研究[M].西安:西安电子科技大学,2014.

[3] ZHU CHUAN.A Survey on Coverage and Connectivity Issues in Wireless Sensor Networks[J].Journal of Network and Computer Applications,2012(35):619-632.

[4] MONICA. Comparative Study of Energy Consumption for Wireless Sensor Network Based on Random and Gird Deployment Strategies[J]. International Journal of Computer Applications, 2010,1(6):28-35.

[5] 戴宁，毛剑琳.基于虚拟势场的有向传感器网络覆盖优化算法[J].计算机应用研究,2014,31(3):905-907.

[6] 彭玉旭.有向传感器网络覆盖增强研究[J].计算机工程,2011,37(2):100-104.

[7] TSAI CHIH-HUNG.Coverage Enhancing Algorithms in Directional Sensor Networks with Rotatable Sensors[J].Asia-Pacific Service Computing Conference,2011,15(12):377-383.

[8] Jing Z. A Virtual Potential Field Based Coverage Algorithm for Directional Networks[J]. Control and Decision Conference.Chinese，2009(6):4590-4595.

[9] Jing LI,WAND RU-CHUANG. Voronoi-Based Coverage Optimization for Directional Sensor Networks[J].Wireless Sensor Network,2009(1):417-424.

[10] 陆克中,冯禹洪.有向传感器网络覆盖增强问题的贪婪迭代算法[J].电子学报,2012,40(4):687-694.

[11] 温俊,蒋杰.公平的有向传感器网络方向优化和节点调度算法[J].软件学报,2009,20(3):644-659.

[12] 杨海雳,赵静. 基于Voronoi图的无线传感器网络覆盖算法研究[J].信息通信, 2015(7):28-31.

[13] 秦泽峰.基于Voronoi图的无线传感器网络覆盖算法研究[J].太原科技大学学报,2013,34(3):185-190.

[14] 秦志霞,沈炜. 二维Voronoi图删除任意生成点算法研究[J].浙江理工大学学报，2010:27(3):421-425.

[15] MEYSAM ARGANY.Voronoi-Based Approaches for Geosensor Networks Coverage Determination and Optimisation:A Survey[J].International Symposium on Voronoi Diagrams in Science and Engineering(ISVD),2010(6):115-123.

[16] 邓俊辉.计算几何-算法与应用[M].北京:清华大学出版社,2006.

[17] 阴成军.无线多媒体传感器网络覆盖增强算法研究[D].太原:太原理工大学,2008.

[18] 张贤凤.有向传感器网络覆盖算法研究[D].长沙:长沙理工大学,2011.

[19] 赵静,曾建潮.无线多媒体传感器网络感知模型与数量估计[J].软件学报,2012,23(8):2104-2114.

Research on Coverage in Wireless Multimedia Senor Networks Based on Voronoi Algorithm

HUO Hai-ping, ZENG Jian-chao, ZHAO Jing

(School of Electronic and Information Engineering, Taiyuan University of Science and Technology, Taiyuan 030024, China)

Coverage technology of Wireless Multimedia Senor Networks(WMSNs) is the key problem of sensor network research. Only the rational deployment of sensor nodes can achieve full detection of the target areas. Voronoi diagram has good characteristics of regional division, and monitoring areas can be divided into some smaller areas. This paper presents a method based on Voronoi diagram coverage strategy in wireless multimedia sensor networks, the coordinates of the new nodes by Voronoi graph can be found. Then, the centroid coordinates of its node can be calculated and the direction of nodes can be adjusted, and maximum coverage rate can be achieved by using a few nodes as possible.

wireless multimedia senor networks, voronoi algorithm, centroid point, coverage rate

1673-2057(2016)06-0438-05

2016-01-08

山西省自然科学基金(2014011019-2)；校博士后科研启动基金( 20142023).

霍海平(1988-)，男，硕士研究生，主要研究方向为无线传感器网络。

TP393

A

10.3969/j.issn.1673-2057.2016.06.004