基于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%.实验结果证明了算法的有效性和正确性.     

移动传感器网络覆盖算法研究

随着MEMS技术的发展,移动传感器网络近年来受到较多的关注,其中覆盖算法是其研究的重要问题之一。现有的移动覆盖算法主要分为虚拟力法、Voronoi图法和Delaunay三角剖分法三类。本文分析了这三类方法的不足,给出了一种新的移动覆盖算法,能够针对大规模移动传感器网络,真正实现分布式的实时响应网络的拓扑变化。仿真表明,该
算法具有良好的覆盖效果。     

A provably complete exploration strategy by constructing Voronoi diagrams

We present novel exploration algorithms that enable the construction of Voronoi diagrams over unknown areas using a vehicle equipped with range sensors. The underlying control law uses range measurements to make the vehicle track Voronoi edges between obstacles. The exploration algorithms make decisions at vertices in the Voronoi diagram to expand the explored area until a complete Voronoi diagram is constructed in finite time. Our exploration algorithms are provably complete, and the convergence of the control law is guaranteed. Simulations and experimental results are provided to demonstrate the effectiveness of both the control law and the exploration algorithms.     

一种基于模糊连接度和维诺图的混合分割方法

介绍一种可用于医学图像处理的、集成了模糊连接度和维诺图分类算法的混合分割方法。首先采用模糊连接度算法对指定图像区域进行过滤处理形成组织样本数据,这些输出数据将作为维诺图分类算法的输入数据和分类标准,然后通过维诺图分类算法对其进行迭代处理直至形成近似的图像区域边界。最终的输出值为一组分割后的三维图像数据,可以采用体绘制方法形成三维图像分割结果,也可用于进一步的图像处理。和其他医学图像分割方法相比,这种混合分割方法集成了基于区域和基于边界两种不同的分割方法,兼具两者的优点,通过两种分割方法的协同工作,提高了图像分割的精度,适用于复杂图像的分割处理。在医学图像计算机辅助诊断系统中集成了这一方法并取得了良好的实际应用效果。     

Linear time Euclidean distance transform algorithms

Two linear time (and hence asymptotically optimal) algorithms for computing the Euclidean distance transform of a two-dimensional binary image are presented. The algorithms are based on the construction and regular sampling of the Voronoi diagram whose sites consist of the unit (feature) pixels in the image. The first algorithm, which is of primarily theoretical interest, constructs the complete Voronoi diagram. The second, more practical, algorithm constructs the Voronoi diagram where it intersects the horizontal lines passing through the image pixel centers. Extensions to higher dimensional images and to other distance functions are also discussed     

Dynamic distributed clustering in wireless sensor networks via Voronoi tessellation control

This paper presents two dynamic and distributed clustering algorithms for Wireless Sensor Networks (WSNs). Clustering approaches are used in WSNs to improve the network lifetime and scalability by balancing the workload among the clusters. Each cluster is managed by a cluster head (CH) node. The first algorithm requires the CH nodes to be mobile: by dynamically varying the CH node positions, the algorithm is proved to converge to a specific partition of the mission area, the generalised Voronoi tessellation, in which the loads of the CH nodes are balanced. Conversely, if the CH nodes are fixed, a weighted Voronoi clustering approach is proposed with the same load-balancing objective: a reinforcement learning approach is used to dynamically vary the mission space partition by controlling the weights of the Voronoi regions. Numerical simulations are provided to validate the approaches.     

三维点集Voronoi图的算法实现

对现有三维点集Voronoi图的生成算法进行深入研究,提出并实现由Delaunay三角剖分构建Voronoi图的算法．首先采用随机增量局部转换计算Delaunay三角剖分,然后再根据对偶特性构建Voronoi图．该算法健壮性很高,适用于处理各种非完全共面三维点集．     

关于一般图形Voronoi图的离散构造法的研究

生成元为任意图形的一般图形Vomnoi图，由于其生成元的任意性，使得构造一般图形Voronoi图的算法均比较复杂。本文给出了在生成元边界上选取母点，利用点为生成元的Voronoi图的离散画法进行构造，从而得到一般图形Voronoi图的离散构造法。与其它算法相比，该算法的实现与生成元的形状无关，无需复杂计算，无需考虑误差控制，因而更加实用，效率也更高。实验结果表明，该算法简单，具有较高的理论价值和应用价值。     

基于Voronoi和空间自相关的离群点检测

为了提高空间数据挖掘的效率和准确度,在分析传统的离群点检测算法优、缺点的基础上,提出一种空间离群点检测算法。用Voronoi来确定空间对象间的邻近关系,在空间邻域内利用空间自相关性来计算局部Moran指数,并将其作为离群因子进而判断离群点。实验结果表明,该算法能够高效、准确地检测出空间离群点,具有对用户依赖性少和可伸缩性强等优点。     

基链分治算法与Voronoi区的面积计算定理研究

基于一般曲线多边形Voronoi图的面向对象数据结构,提出了一种改进的Voronoi图生成算法——基链分治算法.该算法与经典的分治法相比更容易被实现.同时,在欧氏米制中,由于Voronoi区的边界包含抛物线或双曲线,因而Voronoi区的面积很难被计算.为此提出了Voronoi区的面积计算定理,并给出了定理证明和算例,从而为某些工程应用中的面积计算提供了一种方法.     

A higher-order removal method

A major attraction of functional languages is their support for higher-order functions. This facility increases the expressive power of functional languages by allowing concise and reusable programs to be written. However, higher-order functions are more expensive to execute and to analyse for optimisations. To reduce the performance penalties of using higher-order functions, this paper proposes two transformation algorithms which could automatically removemost higher-order functions from functional programs. The first algorithm uses aneta-expansion technique to eliminate expressions which return function-type results. The second algorithm uses afunction specialisation technique to eliminate expressions with function-type arguments. Together, they remove higher-order functions by transforming each higher-order program to an equivalent first-order (or lower-order) program. We shall prove that the two algorithms areterminating (when applied to well-typed programs) and alsototally-correct (preserving non-strict semantics).     

粗糙域Voronoi图离散生成算法研究

Voronoi图是计算几何的一个重要分支,粗糙域Voronoi图是Voronoi图概念在复杂生成面上的扩展。提出了粗糙域Voronoi图的概念并利用A‘算法计算生成面上点与各母点的最短路径对其进行离散生成。为了降低粗糙域Voronoi图离散生成算法的复杂度,对粗糙域下A’算法估价函数权值与粗糙域粗糙特性的关系进行了深入探索。实验结果表明,A’算法估价函数权值与粗糙域粗糙特性正相关,并以此获得r算法估价函数的最优权,大大降低了粗糙域Voronoi图离散生成算法的复杂度。     

Voronoi-based localisation algorithm for mobile sensor networks

Localisation is an essential and important part in wireless sensor networks (WSNs). Many applications require location information. So far, there are less researchers studying on mobile sensor networks (MSNs) than static sensor networks (SSNs). However, MSNs are required in more and more areas such that the number of anchor nodes can be reduced and the location accuracy can be improved. In this paper, we firstly propose a range-free Voronoi-based Monte Carlo localisation algorithm (VMCL) for MSNs. We improve the localisation accuracy by making better use of the information that a sensor node gathers. Then, we propose an optimal region selection strategy of Voronoi diagram based on VMCL, called ORSS-VMCL, to increase the efficiency and accuracy for VMCL by adapting the size of Voronoi area during the filtering process. Simulation results show that the accuracy of these two algorithms, especially ORSS-VMCL, outperforms traditional MCL.     

Incremental Labelling of Voronoi Vertices for Shape Reconstruction

We present an incremental Voronoi vertex labelling algorithm for approximating contours, medial axes and dominant points (high curvature points) from 2D point sets. Though there exist many number of algorithms for reconstructing curves, medial axes or dominant points, a unified framework capable of approximating all the three in one place from points is missing in the literature. Our algorithm estimates the normals at each sample point through poles (farthest Voronoi vertices of a sample point) and uses the estimated normals and the corresponding tangents to determine the spatial locations (inner or outer) of the Voronoi vertices with respect to the original curve. The vertex classification helps to construct a piece‐wise linear approximation to the object boundary. We provide a theoretical analysis of the algorithm for points non‐uniformly (ε‐sampling) sampled from simple, closed, concave and smooth curves. The proposed framework has been thoroughly evaluated for its usefulness using various test data. Results indicate that even sparsely and non‐uniformly sampled curves with outliers or collection of curves are faithfully reconstructed by the proposed algorithm.     

二维约束Voronoi网格构造及其尺寸、质量控制

给出二维约束Voronoi网格的有关概念,分析了约束线段在二维Voronoi网格存在的条件,提出了一种二维约束Voronoi网格构造算法;并对二维约束Voronoi网格的尺寸和质量控制进行了研究;最后给出了实例以说明算法的有效性．该算法计算快速,适应性广,在诸多领域具有广泛的应用前景．     

The Hausdorff Voronoi Diagram of Point Clusters in the Plane

We study the Hausdorff Voronoi diagram of point clusters in the plane, a generalization ofVoronoi diagrams based on the Hausdorff distance function. We derive a tight combinatorial bound on the structural complexity of this diagram and present a plane sweep algorithm for its construction. In particular, we show that the size of the Hausdorff Voronoi diagram is (n + m), where n is the number of points on the convex hulls of the given clusters, and m is the number of crucial supporting segments between pairs of crossing clusters. The plane sweep algorithm generalizes the standard plane sweep paradigm for the construction of Voronoi diagrams with the ability to handle disconnected Hausdorff Voronoi regions. The Hausdorff Voronoi diagram finds direct application in the problem of computing the critical area of a VLSI layout, a measure reflecting the sensitivity of the VLSI design to spot defects during manufacturing.     

分区加权Voronoi图的性质及其面积计算

分区加权Voronoi图是Voronoi图和加权Voronoi图的推广,可以用来模拟移动通信中基站发射天线分扇区以不同功率向周围发射时所覆盖区域的形状。首先,给出了分区加权Voronoi图的性质、定理及相关证明;其次,分析了分区加权Voronoi图中的各种区域,并给出了一种计算相应区域面积的算法;最后,利用分区加权Voronoi图模拟石家庄市部分城区中的基站建设情况,并对模拟产生的重复覆盖、服务区和盲区面积进行了计算。     

A higher-order removal method

A major attraction of functional languages is their support for higher-order functions. This facility increases the expressive power of functional languages by allowing concise and reusable programs to be written. However, higher-order functions are more expensive to execute and to analyse for optimisations.To reduce the performance penalties of using higher-order functions, this paper proposes two transformation algorithms which could automatically removemost higher-order functions from functional programs. The first algorithm uses aneta-expansion technique to eliminate expressions which return function-type results. The second algorithm uses afunction specialisation technique to eliminate expressions with function-type arguments. Together, they remove higher-order functions by transforming each higher-order program to an equivalent first-order (or lower-order) program. We shall prove that the two algorithms areterminating (when applied to well-typed programs) and alsototally-correct (preserving non-strict semantics).A preliminary version of this paper appeared in the Proceedings of 15th Australian Computer Science Conference, Hobart, Tasmania, January 1992.     

Sorting helps for voronoi diagrams

It is well known that, using standard models of computation, Ω(n logn) time is required to build a Voronoi diagram forn point sites. This follows from the fact that a Voronoi diagram algorithm can be used to sort. However, if the sites are sorted before we start, can the Voronoi diagram be built any faster? We show that for certain interesting, although nonstandard, types of Voronoi diagrams, sorting helps. These nonstandard types of Voronoi diagrams use a convex distance function instead of the standard Euclidean distance. A convex distance function exists for any convex shape, but the distance functions based on polygons (especially triangles) lead to particularly efficient Voronoi diagram algorithms. Specifically, a Voronoi diagram using a convex distance function based on a triangle can be built inO (n log logn) time after initially sorting then sites twice. Convex distance functions based on other polygons require more initial sorting.     

基于改进Voronoi区域面积的Mark Meyer曲率估算方法

以微分几何曲率计算公式为理论基础,对常用的Mark Meyer离散点云曲率估算方法进行改进,提出基于Voronoi区域面积的改进Mark Meyer算法。针对Mark Meyer算法中Voronoi区域面积的计算进行改进,对于Voronoi区域中存在钝角的情形进行详细论述并且改进钝角三角形的计算公式,同时给出更为准确的面积计算方法。将该算法应用于球面、柱面、抛物面、马鞍面,计算结果表明该算法提高了离散点云曲率估算的精度和稳定性。