第33卷第5期2019年10月南华大学学报(自然科学版)
Journal of University of South China(Science and Technology)
Vol.33No.5Oct.2019
收稿日期:2019-06-08
基金项目：国家自然科学基金面上项目(61971215)；湖南省教育厅优秀青年项目(18B287)；南华大学核燃料循环技
术与装备湖南省协同创新中心开放基金项目(2019KFZ12)
作者简介：王明华(1980-)，男，讲师，博士，主要从事无线传感网络覆盖控制与优化方面的研究㊂E-mail:wmh1013@ 126
DOI :10.19431/jki.1673-0062.2019.05.008
无线传感网络可信信息覆盖泰森多边形区域划分算法研究
王明华1,2，欧㊀然1
(1.南华大学电气工程学院，湖南衡阳421001;2.南华大学核燃料循环技术与
装备湖南省协同创新中心，湖南衡阳421001)
摘㊀要：针对无线传感网络区域划分问题，基于可信信息覆盖模型，设计了一种新的面向可信信息覆盖的泰森多边形区域划分算法㊂首先，该算法利用节点间的协作感知，通过节点聚类形成节点协作感知盘；然后基于可信信息覆盖模型计算各重建点的权值；最后利用权重泰森多边形图理论设计基于该模型的泰森多边形区域划分算法㊂仿真实验结果表明，该算法与传统圆盘模型下的泰森多边形法相比较，在相同数量节点下划分的泰森多边形区域数量更少，并且有着更高的覆盖率㊂关键词：无线传感网；可信信息覆盖；泰森多边形；区域划分中图分类号:TN915 文献标志码:B
文章编号:1673-0062(2019)05-0046-08
Research of Voronoi Region Partitioning for Confident Information
Coverage in Wireless Sensor Network
WANG Minghua 1,2,OU Ran 1
(1.School of Electrical Engineering,University of South China,Hengyang,Hunan 421001,China;
2.Cooperative Innovation Center for Nuclear,Fuel Cycle Technology and Equipment,
University of South China,Hengyang,Hunan 421001,China)
Abstract :Aiming at the problem of region partitioning in wireless sensor network,this paper devises a new region partitioning algorithm based on the Confident Information Cov-erage Model and Voronoi.Firstly,a node cooperative sensing disk is formed through node
clustering by utilizing the cooperative sensing between nodes.Then weight values of each reconstruction point are calculated based on Confident Information Coverage model.Finally,a novel region partitioning algorithm is devised by using the theoretical method of
the weighted voronoi polygon graph based on the Confident Information Coverage model.
第33卷第5期王明华等：无线传感网络可信信息覆盖泰森多边形区域划分算法研究Simulation results show that the proposed algorithm outperforms the traditional disc coverage model in terms of the number of voronoi regions and the coverage performance.电流变换器
key words:wireless sensor network;confident information coverage;voronoi;region parti-
tioning
0㊀引㊀言
无线传感器网络(wireless sensor network, WSN)是由许多具有感知㊁计算和无线网络通信能力的微型传感器节点组成，通过无线通信的方式构成的无线网络，主要目的是感知㊁采集和处理网络覆盖区域中被感知对象的信息㊂在无线传感器网络的研究中，覆盖控制是无线传感网应用的一个基本问题，它是在保证一定的服务质量条件下，如何达到网络覆盖范围最大化㊂在覆盖控制问题中，覆盖模型的选择是一个重要问题[1]㊂传统的布尔圆盘覆盖模型[2]是使用最多的节点覆盖模型，该模型覆盖区域为以其自身为圆心㊁以其感测距离为半径的一个圆盘㊂衰减圆盘覆盖模型㊁概率覆盖模型[3]等都是一种在布尔覆盖模型的基础上进行的扩展延伸，其特点是节点对目标的感知能力呈现出概率特征，目的是为了契合实际环境下节点感知的不确定性㊂针对泰森多边形(voronoi)图在无线传感网中的研究,G. Wang[4]等人提出了基于voronoi图的三种部署算法,VEC(基于矢量的算法)㊁VOR(基于voronoi的算法)和Minimax来检测覆盖漏洞㊂H.Lee[5]等人通过使用voronoi图和质心来提出质心和双质心方案以最大化传感覆盖，在最新的一些关于voronoi图的研究中，在文献[6]中，研究了一种安全的基于voronoi的部署算法，可以到节点最短移动路径来修补漏洞,W.Fang[7]等提出了考虑节点邻居位置的盲区质心
算法，在文献[8-9]中采用加权voronoi图来划分感测场㊂H.Mahboubi[10]等使用此分区来发现覆盖漏洞并相应地重新放置传感器以最小化它们，同时考虑到现场中不同点的覆盖优先级，提出三种算法，最大加权顶点，最大加权点和最大距离权重用来迭代地移动每个传感器，使得其加权覆盖率增加㊂文献[11]提出了一套分布式部署算法，用于有效的现场覆盖㊂但是上述各种覆盖模型的选取，以及覆盖算法的研究都是基于传统的圆盘模型，在利用泰森多边形的区域划分的算法中虽然考虑到异构情况，很少考虑到其邻居传感器以及传感器间的协同感测能力，没有体现出节点间的空间相关性㊂
针对以上不足，本文选用可信信息覆盖模型(confident information coverage,CIC)作为节点的覆盖模型[12-14]，它在信息重建的理论基础上充分考虑节点间的空间相关性，挖掘了节点间的协同工作能力，大大提升了网络覆盖能力㊂并在此基础上结合泰森多边形，设计了一种新的区域划分算法，名为CIC-Voronoi算法，以期适用于可信信息覆盖模型，并为以后的传感器移动算法的设计以及覆盖问题的研究提供理论基础㊂
1㊀模型介绍
1.1㊀泰森多边形在无线传感网中的应用
泰森多边形是一种空间平面的剖分工具，它是由连接两相邻节点线段的垂直平分线组成的连续多边形，具有空间上的等分特性，目前在许多领域中有着较为广泛的用处㊂
空间等分性是指，在每个泰森多边形中，只包含一个离散数据点，在每个泰森多边形内的任意一点到相应的离散点的距离最近，并且在位于泰森多边形边上的点到其两边的离散点的距离相等㊂泰森多边形在无线传感网中运用正是利用了这个特性，它可以将整个传感区域分为N个小区域(N为传感器节点的数目)，同时分别去研究每个小区域的覆盖情况㊂这样的好处是只需要考虑泰森多边形的区域的性质就可以确定相应节点的性质，如：判断一个离散点与其它哪些离散点相邻时，可根据泰森多边形直接得出；若泰森多边形是n边形，则就与n个节点相邻等等㊂这样可以大大节省研究无线传感网覆盖时的工作量，省时省力㊂
在无线传感网的应用中，只需要考虑每个节点自身所在多边形的覆盖关系，如果传感器覆盖半径不完全大于离散点到最远泰森多边形顶点的距离，如图1(a)所示,abcd为S1节点所在的闭合泰森多边形区域，顶点d到S1的距离大于圆盘半径，即顶点d未被覆盖，因此该泰森多边形区域未被完全覆盖，存在覆盖漏洞㊂反之如图1(b)所示,efgh为节点S2节点所在的闭合泰森多边形区域,S2节点半径大于多边形所有顶点到S2的距离，因此该泰森多边形区域不存在覆盖漏洞㊂
74
㊀㊀㊀南华大学学报(自然科学版)
2019年10
月
图1㊀节点覆盖泰森多边形Fig.1㊀Node covers vorovoi
1.2㊀可信信息覆盖模型
可信信息覆盖模型是一种从信息重建角度出
发的一种节点协同感测模型，它充分挖掘变量之间的空间相关特性，通过传感器节点与空间点之间的几何位置关系刻画并提高了传感器节点的感测能力与感测质量㊂
在整个传感区域，用p =(p 1,p 2, ,p n )来表
示采样空间点集合，针对t 时刻时用z =(z 1(t ),z 2(t ), ,z n (t ))来表示采样空间点的环境信息㊂由于环境变量所蕴含的时空相关性，用^Z
x (t )来表示未被采用空间点的估计值㊂本文使用均方根误差(root mean square error,RMSE)来度量和评估每个未被采样空间点位置环境变量值的重建和估计质量，即:
Φ(x )=
1N ðN
n =1
(Z n (x )-^Z n (x ))2(1)
㊀㊀Φ(x )取决于未被采样空间位置x 与其最近的传感器节点之间的几何距离，通常距离越大Φ(x )数值越大㊂对于可信信息覆盖模型的定义如下:
可信信息覆盖模型：在一个随机场中，给定一个重建函数f ，如果该场中一个空间位置点x 上的重建信息的Φ(x )在时域上的均方根误差均值小于等于实际应用中网络用户所提出的阈值ε，即Φ(x )ɤε，则称该空间位置点x 被可信信息覆盖㊂
利用式(1)计算出的Φ(x )与事先预RMSE 值相比较，即可判断该位置未被采样点是否被可信信息覆盖㊂图2为当采用最近距离插值方法作为重建函数时，四个节点的可信信息覆盖模型的
覆盖范围用，阴影部分表示㊂图2中可以看出存在S 1㊁S 2㊁S 3㊁S 4四个传感器节点，三角形点为重建点位置，点P 为圆盘外一点，未被四个节点中任意节点覆盖，通过可信信息覆盖模型计算
，点Φ(P )小于预设RMSE，因此点P 被可信信息覆盖㊂
图2㊀可信信息覆盖模型节点协同感测示意图Fig.2㊀Schematic diagram of cooperative sensing of
confident information coverage model nodes
2㊀CIC-Voronoi 算法
本节将泰森多边形与CIC 模型结合，提出了
一种适应CIC 模型的异构网络区域划分算法㊂在本设计中，将节点协同的CIC 模型作为一个新的模拟传感器，中心点作为模型重建点㊂因此在整
8
4
第33卷第5期王明华等：无线传感网络可信信息覆盖泰森多边形区域划分算法研究
个二维传感区域R 2中会出现不同数量节点汇聚的CIC 协同感测盘㊂将每个CIC 协同感测盘看做一个模拟节点，由于每个协同感测盘的半径不同，因此整个网络实际上成为由多个不同感测半径的CIC 协同感测盘组成的异构网络㊂在本文设计中，所有传感器节点都是同种节点，并以节点所在位置为圆心，定长为半径的圆形区域，且通信半径r c 的为感测半径r s 的两倍㊂通过计算CIC 协同感测盘覆盖范围的最大内接圆，以该内接圆半径R s 为模拟传感器感测半径㊂
黄金龟甲虫2.1㊀CIC-Voronoi 算法流程CIC-Voronoi 算法的实现流程如图3所示，具
泉州移动网上营业厅
马布里扣篮体步骤流程如下，算法运行停止后形成基于CIC 模型的加权voronoi
网络区域划分结果
图3㊀基于可信信息覆模型的泰森多边形生成流程图Fig.3㊀Vorovoi generation flow chart based on
confident information overlay model
第1步，在整个特定的传感区域，随机部署传感器节点㊂
第2步，获取所有传感器节点的位置，计算所有传感器节点间的距离，将随机部署的传感器节点通过层次聚类的方式进行重聚类㊂
第3步，每个类通过CIC 模型的定义，形成新的CIC 协同感测盘㊂
第4步，通过考虑重建点的位置与权重，绘制乘性加权CIC-Voronoi 图㊂
在本章之后的小节中，针对算法每一步骤做了详细说明㊂
2.2㊀节点聚类
在节点聚类的过程中，本文采用经典的凝聚
型层次聚类的方法，通过设置凝聚条件以及迭代终止条件，从而达到对所有随机部署的传感器节点重聚类㊂在层次聚类过程中，本文使用欧几里得距离来计算各个节点间的距离，考虑传感器节点再实际
应用中存在的感测半径r s 与通信半径r c ㊂
聚类算法初始化首先将每一个传感器节点归
为一个类，计算每两个类之间的距离㊂之后寻各类之间距离最近的两个类，凝聚条件为该最近距离小于传感器节点通信半径r c ，满足条件的两个类归为一个新类㊂
上述步骤完成之后，算法再次重新计算新生成的类与各个旧类之间的距离，重复上述步骤，直至算法终止㊂由于CIC 模型的特殊性，该聚类算法的终止条件为凝聚的新类中最多包含6个传感器节点，以及每一个类之间的欧式距离大于r c ㊂
这里特别强调一点，由于5个节点的CIC 模型计算相对复杂，以及2节点的CIC 模型不适于该算法，本文在此不做考虑㊂2.3㊀CIC 协同感测盘
在2.2介绍的CIC 模型原理中，对确定的空间点即传感器节点的位置，通过计算任意位置点的均方根误差Φ(x )与预设可信信息覆盖阈值ε相比较，满足小于ε的点，即为可信信息覆盖㊂
针对CIC 协同感测盘的形成，本文在整个传感场区域内，将整个区域分割成若干个极小的区域，算法依次针对每一个极小区域计算均方根误
差Φ，若满足小于ε，那么该区域为可信信息覆盖区域㊂算法结束后满足可信信息覆盖的区域本文定义为CIC 协同感测盘㊂图4为ε等于0.6，节点数量分别为3㊁4㊁6时形成的CIC 协同感测盘㊂2.4㊀基于CIC 模型的乘性加权泰森多边形设计
泰森多边形是分析和设计传感器部署技术的
基本工具，但正如上章所介绍的，只有在所有传感器都具有相同属性的情况下，该工具才适用㊂因此采用一种乘性加权泰森多边形(multiplicative weighting voronoi,MWV)的划分算法来适应于CIC 模型，期望将整个平面划分为n 个区域㊂定义1㊀CIC 协同感测盘覆盖范围的最大内接圆半径R s 为该模拟传感器的权重w ㊂定义2㊀任意位置点q 到模拟节点(S i ,w i )的
加权距离为:
9
4
㊀㊀㊀南华大学学报(自然科学版)
2019年10
月
图4㊀节点数量分别为3㊁4㊁6时的CIC 协同感测盘Fig.4㊀CIC cooperative sensor disks with 3,4and 6nodes
d w (q ,S i )=胡太后
d (q ,S i )w i
(2)
d (q ,S i )为q 到模拟节点S i 的欧氏距离㊂
用(S ,w )来表示每个不同CIC 协同感测盘,
在整个二维传感场R 2中，存在n 个不同加权值的模拟传感器节点，即S ={(S 1,w 1),(S 2,w 2), ,(S n ,w n )}㊂值得注意的是，与普通乘性加权泰森多边形不同的，每个区域中包含一个模拟节点而不是一个实际的传感器节点，加权距离也应为任意点q 到重建点的加权距离㊂
性质1㊀每个区域中包含一个模拟节点(重建点)，且该节点是它所在区域的任意位置点到它的加权距离最近的点㊂数学公式可表示为:
ᵑi
={Q ɪR 2|w i d (Q ,S i )ɤ
㊀w j d (Q ,S j ),∀j ɪn -{i }}(3)
㊀㊀定义3㊀区域内任意一点q 到两相邻节点S 1,S 2的距离之比
杨赤忠
d (q ,S 1)
d (q ,S 2)
=k 为常数的轨迹称为
圆(Apollonius circle)，如图
5㊂
图5㊀圆Fig.5㊀Apollonius circle
性质2㊀圆上任意一点q 到该圆所在节点的加权距离相同㊂即
d w (q ,S 1)=d w (q ,S 2)
(4)
㊀㊀如图6所示为当只存在一个节点与四个节点协同，一个节点与六个节点协同，以及四个节点协同与六个节点协同时所产生的MWV 边的对比图，由图6所示可知
d (q 1,S 1)/d (q 1,S 2)=w 1/w 2,d (q 2,S 3)/d (q 2,S 4)=w 3/w 4,d (q 3,S 5)/d (q 3,S 6)=w 5/w 6
㊂
图6㊀节点与协同节点间所产生MWV 边对比
Fig.6㊀Comparison of MWV edges between nodes
and cooperative nodes
5
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议