基于虚拟力和泰森多边形的分布式覆盖算法  

Distributed coverage algorithm based on virtual force and Voronoi

作　　者：祁春阳 戴欢 赵晓燕 李克清[3,4] 

机构地区：[1]中国矿业大学计算机科学与技术学院,江苏徐州221116 [2]苏州科技大学电子与信息工程学院,江苏苏州215009 [3]常熟理工学院计算机科学与工程学院,江苏常熟215500 [4]苏州市职业大学计算机科学与工程学院,江苏苏州215002

出　　处：《计算机工程与设计》2018年第3期606-611,共6页Computer Engineering and Design

基　　金：国家自然科学基金项目(61300186); 教育部赛尔网络下一代互联网技术创新基金项目(NGII20160322); 苏州市科技计划基金项目(SYG201603); 苏州市物联网工程应用重点实验室基金项目(SZS201407)

摘　　要：基于虚拟力的无线传感器网络覆盖算法易陷入局部最优,导致覆盖率低、收敛速度慢。针对上述问题,提出一种基于虚拟力和泰森多边形划分的分布式覆盖(virtual force Voronoi partition,VFVP)优化算法。通过虚拟力方案尽可能分散节点,提高监测区域的覆盖率,采用集合划分泰森多边形方案和Minmax算法减少虚拟力末端中覆盖率下降的情况,使用质心算法提高虚拟力算法的收敛速度。相比基于虚拟力的网络覆盖算法,VFVP算法提高了5%左右的覆盖率。Wireless sensor network coverage algorithm based on virtual force is easy to fall into local optimum,which leads to low coverage and slow convergence speed.Aiming at the above problems,a distributed coverage algorithm based on virtual force and Voronoi partition optimization algorithm（virtual force Voronoi partition,VFVP）was proposed.Nodes were dispersed as much as possible through the virtual force scheme to improve the coverage ratio of the monitored area.The coverage reduction in the virtual force end was reduced using the partitioned Voronoi scheme and the Minmax algorithm.The centroid algorithm was used to improve the convergence speed of the virtual force algorithm.Compared with the network coverage algorithm based on virtual force,the VFVP algorithm improves the coverage rate by 5%.

关 键 词：VORONOI划分 虚拟力 覆盖优化 Minmax算法 质心算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]