基于 Voronoi 网格传感网络近似最少连通覆盖值算法.pdf

《基于 Voronoi 网格传感网络近似最少连通覆盖值算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第39卷第5期西南师范大学学报(自然科学版)2Ol4年5月Vo1．39No．5JournalofSouthwestChinaNormalUniversity(NaturalScienceEdition)May．2014文章编号：1000—5471(2014)5—0011—07基于Voronoi网格传感网络近似最少连通覆盖值算法①邹赛。，汪文勇1．厦门大学信g科学与技术学院，厦门361005；2．电子科技大学计算机科学与工程学院，成都611731；3．重庆电子工程职业学院软件学院，重庆401331摘要：基于并行处理理念使用Voronoi网格可将平面区域划分为几何体集合的性质，提出了

2、传感器网络正六边形剖分的近似连通最少覆盖算法(ACA—RH)．Sink节点将信息收集区域进行正六边形网格剖分，然后让传感器节点与各个正六边形网格的位置进行比较来决定自己是工作还是睡眠，从而构造近似连通最少覆盖集．经过理论分析与仿真实验表明，ACA—RH算法时间复杂度和所需要节点的数量少于SCR—CADS算法、so8LYe算法．关键词：正六边形剖分；传感器网；连通；覆盖中图分类号：TP393文献标志码：A在无线传感器网络中，构建虚拟骨干网是优化网络性能的重要手段之一[】]．构建虚拟骨干网实际上就是求解最少覆盖连通支配集]．这样将使大部分节点进入睡眠状态，只有少部分节点工作，有利于优

3、化路由，而且极大地节约能量，延长了整个网络的寿命．在任意图中求解最小连通集是一个NP难问题，对它的求解一般采用启发式算法，主要有集中式口和分布式[】¨两种方法．基于Voronoi网格可将平面区域划分为简单几何体集合的性质，很多学者把它广泛应用于传感器网络中的覆盖问题研究，如So&Ye提出了一种二维空间中k一覆盖问题求解算法，其时间复杂度为O(nlogn)，在时间复杂度上达到最优值口，但求解前需要知道整个图的全局信息，在拓扑结构动态变化的无线传感器网络中并不适用．典型的分布式算法有sCR—cADs(SurfaceCoverageRelayConnect—edAreaDominati

4、ngSet)l1j，节点仅通过获取其邻节点的位置信息来决定自己是工作还是睡眠，具备良好的可扩展性，适合于大规模的传感器网络，但它的最少连通覆盖值不是最小．本文结合文献[12]集中式算法与文献[14]分布式算法各自的优点，基于Voronoi网格特性，提出一种正六边形剖分的传感器网络近似连通最少覆盖值算法(ACA—RH)．首先Sink节点将信息收集区域进行正六边形网格剖分，然后让传感器节点与各正六边形网格的位置进行比较来决定自己是工作还是睡眠，从而构造近似最少连通覆盖集．经过理论分析与仿真实验证明，ACA—RH算法能有效降低网络的计算复杂度及对信息收集区域所需要节点的数量．针对具有个

5、节点的传感器网络，与so&Ye提出的算法相比，ACA—RH的时间复杂度为()(3+t)；与SCR—CADS算法相比，所需要节点数量为其2／3．①收稿日期：2013—11—06基金项目：国家发改委CNGI二期项目(CNGI-09—01—07)；863项目(2008AA01A303)；973项目(2009CB320505)；2014年重庆市教委科学技术研究项目；重庆市“十二五”教育规划课题(2013一ZJ一077)．作者简介：邹赛(1981一)，男，湖南祁东人，博士生，高级实验师，主要从事计算机网络，软件工程方面的研究．12西南师范大学学报(自然科学版)http：／／xbbjb．SW

6、U．cn第39卷l符号说明为方便阅读，本文所用到的专有名字如表1所示，且传感器网的拓扑结构可定义为一个二维的无向图G(V，E)，其中，E分别表示节点及能量的集合．对于任意节点iEV，当前节点能量记作E()，节点i的当前覆盖半径记作r，通信半径R，节点的查询能量(监听能量)记作e()．表1符号表专有名字定义覆盖，假定S一{S，Sz，⋯，}为任意给定的部署于二维空间R中的个传感器节点集合，对Cover信息收集区域G中的任意位置点i，至少存在1个传感器节点ES，iED，则称s覆盖信息收集区域G．CoverDisk覆盖圆盘，对G中的任意位置点o，存在传感器节点s，s的覆盖范围称为s的覆盖

7、圆盘CoverSet覆盖集，在信息收集区域G中的任何位置都能够被S中的1个或者多个节点覆盖，则称S覆盖G．ConnectedCoverSet连通覆盖集，在满足CoverSet的情况下了，s中所有节点能够实现通信，则称S为G的连通覆盖集．MinimalConnected最少连通覆盖集，在满足ConnectedCoverSet的情况下了，如s{S，5，⋯，S)中所有节点COVerSet数量最少，则称s为G的最少连通覆盖集．节点编号，当基站节点对信息收集区域G进行正六边形网格剖分后，把