一种基于虚拟力的分布式Voronoi控制策略

针对无线移动传感器网络在目标区域的覆盖问题,提出了一种基于移动距离的局部分布式算法,利用Voronoi多边形的特征对目标区域进行有效的分割,运用力学的矢量概念,根据Voronoi图的边和顶点确定虚拟力的方向和大小即节点的移动方向和距离,提出了基于移动距离的分布式Voronoi控制算法,以确定节点移动状态。仿真实验表明,所提算法不仅使得节点在目标区域实现了高覆盖率,同时在时间上也较早地达到了收敛,优化了网络的覆盖控制。     

基于Voronoi图的三维移动传感器网络自主部署算法

针对给定目标区域的节点自主部署问题,传统的虚拟力方法容易产生覆盖重叠和覆盖空洞,并且计算所需要的参数具有不确定性.文中提出了两种基于 Voronoi 图的三维移动传感器网络的自主部署算法 TDADA-Ⅰ和 TDADA-Ⅱ(Autonomous Deployment Algorithm of Three-dimensional Mobile Sensor Network Based on Voronoi Diagram).Voronoi图具有良好的邻近性、邻接性和快速划分区域的特性.该算法计算每个Voronoi区域的重心,使节点向Voronoi区域的重心移动,经过多次迭代构造Voronoi图使得节点移动到最佳位置,从而提高被监测区域的网络覆盖率.仿真实验结果表明,TDADA-Ⅰ和TDADA-Ⅱ有效的提高了被监测区域的网络覆盖率,TDADA-Ⅰ从85.27%提高到了96.04%,TDADA-Ⅱ从85.27%提高到了92.07%.实验结果证明了算法的有效性和正确性.     

平面上可相交凸多边形的Voronoi图

传统的多边形的Voronoi图存在不能相交的问题,以至于无法将其应用于计算机视觉、生态学等领域中的多边形相交情况.为了解决多边形相交情况下的最邻近空间划分问题,提出了可相交凸多边形的Voronoi图.首先定义可相交凸多边形的Voronoi图;然后阐述相交多边形特有的Voronoi边的区域化现象,证明了其发生的充要条件,进一步揭示了相交多边形与不相交多边形之间的关系;最后提出Voronoi图的生成算法,并用代码实现.实验结果表明,该算法能够有效地解决多边形相交的问题,突破了不能相交的限制,为计算机视觉、生态学等领域的实际应用提供了理论基础.     

Voronoi 优化的蜂群算法在WSN覆盖中的应用

包含移动节点的混合网络成为无线传感器网络发展的主流。为了优化混合无线传感器网络的部署质量,提高部署效率,本文提出一种与Voronoi多边形相结合的改进蜂群算法来指导移动节点的部署。通过Voronoi多边形迅速找到固定节点部署的覆盖漏洞,指导引领蜂的生成,利于迅速定位全区域覆盖漏洞;通过评价漏洞大小代替轮盘赌选择方式来实现跟随蜂的开采过程,利于局部优化。仿真结果表明,该算法简便易实现,能够迅速收敛,提高网络覆盖率,达到混合网络的最优覆盖效果。     

多边形中的点可见性快速算法

针对点的可见性计算这一计算几何中的基础问题,提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法.以与Voronoi骨架路径对应的Voronoi通道概念,以及相应的局部最短路径概念为基础,按照深度优先策略对Voronoi图进行遍历,在计算Voronoi骨架路径的同时计算局部最短路径,并基于局部最短路径计算所遍历的多边形边的可见部分.该算法可以处理“带洞”多边形,而且只对多边形进行局部访问;对于“带洞”多边形,由于该算法的数据结构比较简单、剖分空间合理且易于实现,因此仅需O(n)空间和O(nlgn)预处理时间.最后给出了在三维室内虚拟场景设计与漫游系统中的应用实例,结果表明文中算法是实际可行,且运行时间与点的可见多边形的边数和多边形的边数均呈线性关系.     

基于粒子滤波预测的WSN分布式动态目标跟踪设计

为了保证在具有较高跟踪精度的条件下,实现WSN监测区域移动目标的动态跟踪,并尽可能地降低节点能耗和延长网络的生命周期,提出了一种基于改进粒子滤波算法的分布式移动目标跟踪算法;首先,对网络假设和目标移动模型均进行了描述,然后设计了实现对移动目标进行跟踪的节点组织策略,对网络进行动态分簇,在初始时刻簇头收集簇成员的目标估值并进行信息融合以获得目标的初始位置,然后在簇头处运行改进的粒子滤波算法并周期收集各簇成员的观测值进行目标跟踪;采用Matlab仿真工具进行仿真,结果表明文中方法能精确地实现WSN监测区域的移动目标跟踪,且与其它方法比较,具有较高的跟踪精度、较小的误差及较大的优越性。     

无线传感网中能量高效的目标跟踪算法研究

针对无线传感网现有跟踪算法精度低、能耗高等问题,研究一种能量高效的目标跟踪算法.该算法提出基于Voronoi图的节点休眠调度机制,在节约能量的同时保证监测区域的网络覆盖质量.然后分析节点间的位置拓扑关系对定位精度的影响,并通过合理选择信标节点实现目标的定位跟踪.仿真结果表明,该算法在能量效率、跟踪精度与稳定性方面表现出较好的性能.     

一种基于点集自适应分组构建Voronoi 图的并行算法

论文提出一种基于点集自适应分组构建Voronoi 图的并行算法,其基本思 路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成 Voronoi 图,称为Voronoi 子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi 图,称为边界点Voronoi 图;最后,针对每个边界点,提取其位于Voronoi 子图和边界点Voronoi 图内所对应的两个多边形,进行Voronoi 多边形的合并,最终实现子网的合并。考虑到算法 耗时主要在分组点集的Voronoi 图生成,而各分组的算法实现不受其他分组影响,采用并行 计算技术加速分组点集的Voronoi 图生成。理论分析和测试表明,该算法是一个效率较高的 Voronoi 图生成并行算法。     

异构无线传感器网络对移动目标的连续跟踪

针对固定节点组成的传统无线传感器网络在进行目标跟踪时存在的能耗过高和覆盖空洞问题,提出在传统传感器网络中引入少量移动性节点组成异构传感器网络进行目标跟踪的方案.基于较传统0/1监测模型更为实际的概率监测模型,提出一种协同调度移动节点和固定节点工作的算法来对移动目标进行跟踪.移动节点对目标实施近距离的移动式跟踪,减少了处于活跃状态的固定节点数量,节约了能耗.此外,移动节点可以移动进入空洞监测目标,解决了传统网络不能监测覆盖空洞中的目标的问题.基于NS2的实验结果表明所提出的跟踪方法可以大幅度减少固定节点的能耗并提高跟踪质量,证明了其有效性.     

基于可变形状参数Gamma混合模型的区域化模糊聚类SAR图像分割

为了解决传统模糊聚类算法无法准确刻画SAR图像强度分布特征以及抗噪性差等问题,提出一种基于可变形状参数Gamma混合模型(GaMM)的区域化模糊聚类SAR图像分割方法.首先,利用Voronoi划分技术将SAR图像完备地划分为若干个Voronoi多边形;然后,假设SAR图像强度服从可变形状参数的GaMM,以GaMM的负对数函数刻画多边形与聚类间的非相似性关系,并结合具有邻域多边形空间约束作用的规则化项定义区域化模糊聚类目标函数;在模型参数求解的过程中,对于无法直接通过导数求解的形状参数及生成点集,设计以目标函数最小化为准则的移动更新操作以逐步逼近最优解.通过对真实及模拟SAR图像分割结果进行定性定量分析,有效地验证了所提出算法对SAR图像强度分布拟合的准确性及分割的抗噪性.     

An augmented Voronoi roadmap for 3D translational motion planning for a convex polyhedron moving amidst convex polyhedral obstacles

This paper concerns the development of a piecewise linear Voronoi roadmap for translating a convex polyhedron in a three-dimensional (3-D) polyhedral world. In general the Voronoi roadmap is incomplete for motion planning, i.e., it can have several disjoint components in one connected component of free space. An analysis of the roadmap shows that incompleteness is caused by the occurrence of the following simple geometric structure: a polygon in the Voronoi surface containing one or more polygons inside it. We formally bring out the details of this geometric structure and give an efficient augmentation of the roadmap that makes it complete. We show that the roadmap has size e = O(n²Q²l²), where n is the total number of faces on the obstacles, Q is the total number of obstacles and l is the number of faces on the moving object. We also present an algorithm to construct the roadmap in O((n + Ql)e + Q²log Q) time.     

Voronoi算法模型及其程序实现

在自然科学和社会科学的诸多研究领域的问题中，Voronoi（沃洛诺依）多边形网络常常被用来做为计算机仿真模型。由于按照定义形成Voronoi多边形网络较难用程序实现，人们多采用Delauney（狄洛尼）三角形的方法完成模型的构建。该文首先介绍Voronoi多边形和Delauney三角形的定义和形成模型的方法，然后就Voronoi多边形的计算机程序实现进行讨论，模型中使用少量的多边形和周期边界条件可以忽略系统边界效应的影响，最后给出了用Turbo C和C＋＋所写程序的基本框架。     

多连通多边形的内部Voronoi图的顶点和边数的上界

多边形的Voronoi图在路径规划、碰撞检测等方面有着广泛的应用,其顶点和边数在这些应用算法的复杂度分析方面起着重要作用.Held证明了一个简单多边形的内部Voronoi图最多有n+k-2个顶点和2(n+k)-3条边,其中n和k分别是多边形的顶点和内尖点数.但其结论不能适用于多连通多边形.对多连通多边形进行研究,通过将其Voronoi图转化为有根树,并利用有根树的性质,给出了其内部Voronoi图的顶点和边数上界的估计,并对Voronoi区域的边界所包含顶点和边数的平均值进行了讨论."SDU数字博物馆"系统所采用的基于Voronoi图的可见性算法的复杂度分析,就利用了所得出的结论.     

增删点后的Voronoi 图生成算法

Voronoi 图可广泛应用于模式识别、计算机图形学、计算机辅助设计、地 理信息系统等领域。利用Voronoi 图及其对偶图Delaunay 三角网构建的不规则三角网TIN 能充分地反映地形地貌特征,对TIN 的统一管理和动态调用可较好地应用到数字高程模型 的建立中。通过联机增量和减量算法来来实现增删点后的Voronoi 图的生成,具有能够动态 修改点集、速度快、效率高等优势。     

A Computational Method for Optimizing the Shape and Location of a Polygon on a Plane

This study applies the concept of the Voronoi diagram to a simultaneous search for the optimal shape and location of a polygon. Suppose that an area-like facility is contained in a finite two-dimensional uniform region. The objective of our study is to optimize the shape and location of the facility (polygon) in terms of the mini-sum distance from all the surrounding points. When the mini-sum distance is minimized, the polygon forms a star-shaped polygon at the center, and when maximized, it verges alongside the edge of the region. The results are represented by an approximate value of local optima obtained by replacing the boundary of the polygon with points. We justify the results by examining the difference between the value obtained from a line Voronoi diagram and that generated from points.     

Generating and updating multiplicatively weighted Voronoi diagrams for point,line and polygon features in GIS

A Voronoi diagram is an interdisciplinary concept that has been applied to many fields. In geographic information systems (GIS), existing capabilities for generating Voronoi diagrams normally focus on ordinary (not weighted) point (not linear or area) features. For better integration of Voronoi diagram models and GIS, a raster-based approach is developed, and implemented seamlessly as an ArcGIS extension using ArcObjects. In this paper, the methodology and implementation of the extension are described, and examples are provided for ordinary or weighted point, line, and polygon features. Advantages and limitations of the extensions are also discussed. The extension has the following features: (1) it works for point, line, and polygon vector features; (2) it can generate both ordinary and multiplicatively weighted Voronoi diagrams in vector format; (3) it can assign non-spatial attributes of input features to Voronoi cells through spatial joining; and (4) it can produce an ordinary or a weighted Euclidean distance raster dataset for spatial modeling applications. The results can be conveniently combined with other GIS datasets to support both vector-based spatial analysis and raster-based spatial modeling.     

基于mean-shift的快速跟踪算法设计与实现

介绍了一种基于mean-shift跟踪算法，分析了mean-shift中各参数对实时性能的影响。并利用DM642EVM作为视频信号处理器，设计了一套运动目标全物理仿真实验系统。     

简化三维地形中爬行路径的设计

首先对问题进行了简化，重点把地形中地物的形状简化成包围其边界的凸多边形包围盒，并且提出了简化问题的基于局部贪心的规划方法，实验结果证明，该方法命中最优路径的可能性较高，具有一定的应用价值。     

各向异性传感环境下的移动对象反监控算法

研究异构传感环境下移动对象的反监控问题,提出一种暴露模型,该模型可用于近似估算移动对象穿越各向异性传感器网络时的风险.并在此基础上,结合各向异性Voronoi图提出了一种路径判定算法,该算法能够保障移动对象选择一条具有近似最小风险的路径穿越各向异性传感器网络区域.理论分析和实验结果表明,算法具有良好的反监控性能.另外,算法只需知道移动对象侦测半径之内的局部信息,因此也具有分布式和实用性等良好特性.     

移动对象最近邻查询实时更新算法

在移动对象最近邻查询实时更新算法中,安全区一般是难以求解的不规则凸多边形。针对该问题,将安全区设计为圆形,在此基础上提出一种效率更高的移动对象最近邻查询更新算法。将算法分别运行于基站上的最近邻管理系统和移动对象上的Client管理系统,实验结果表明,该算法可以降低系统的存储代价,提高其数据处理性能。