无线传感网络中基于Delaunay和Voronoi的区域覆盖研究

发布时间：2018-04-02 03:02

本文选题：无线传感网络　切入点：Voronoi　出处：《东华大学》2017年硕士论文

【摘要】：当前随着科学技术的飞速发展人类信息获取高度智能化,无线传感网络得到高度的重视和研究。无线传感网络在我们的生活中扮演着越来越重要的角色,特别是在地震、森林火灾等自然灾害对灾情信息的获取给我们带来巨大便利。无线传感网络作为一种以数据为中心的网络,覆盖是衡量传感网络服务质量的重要标准之一,因此对覆盖问题的研究具有重要的意义。本文以传感节点随机分布在监测区域内为研究场景,研究了传统的全向传感网络覆盖问题和定向传感网络覆盖问题,充分利用Delaunay和Voronoi来设计覆盖提高算法。全向传感网络中研究由静态节点和移动节点组成的混合网络的覆盖问题。节点的随机分布导致覆盖空洞的产生,由静态节点估算覆盖空洞并计算出辅助点具体位置,然后命令移动节点去修复漏洞。本文做了以下工作:a)引入Delaunay几何图形,由静态节点构成三角网在每个三角形内估算覆盖空洞,根据覆盖空洞计算辅助点个数,并设计了一套节点部署策略;b)设计覆盖空洞修复算法。定向传感网络中我们利用节点移动和旋转特性设计覆盖提高算法,定向传感网络的覆盖不同于全向传感网络覆盖,其覆盖受到节点坐标、传感半径、传感器工作方向以及视角的影响。把随机分布的节点按照Voronoi原理划分成多个网格,把整个区域的覆盖问题转化成每个网格内的覆盖优化问题。本文引入传感节点的两个虚拟辅助点,节点根据判断两个辅助节点是否在网格内做出移动或则旋转的决定。定向传感网络覆盖中设计了三种覆盖优化算法:a)基于Voronoi顶点的网格内节点移动覆盖优化算法。该算法主要利用节点的移动特性,根据判断辅助点是否在当前网格内(即传感节点在当前网格内是否得到完整覆盖)做出移动的决定,节点移动轨迹始终限定在当前网格,网络拓扑结构变化较小;b)基于Voronoi顶点的网格内旋转工作方向提高算法。该算法利用节点旋转特性有效控制节点的工作方向,以旋转最小的角度达到在当前网格内取得最大化覆盖的目的;c)基于边界的旋转算法,该算法提高了边界节点有效覆盖率和传感节点的利用率。本文着重研究了全向传感网络和定向传感网络的区域覆盖问题,通过引入Delaunay和Voronoi两种经典几何图形来进行算法的设计,并使用Matlab进行仿真试验,且与其他已存在的相关算法进行比较。最后论文做出了总结展望,并指出了本文有待解决和完善的问题及进一步需要开展的工作
[Abstract]:With the rapid development of science and technology, wireless sensor network (WSN) has been paid more and more attention and research. Wireless sensor network (WSN) plays a more and more important role in our life, especially in earthquake. Natural disasters such as forest fires bring us great convenience to obtain disaster information. As a data-centric network, wireless sensor network (WSN) is one of the important standards to measure the quality of service of WSN. Therefore, it is of great significance to study the coverage problem. In this paper, the traditional omnidirectional sensor network coverage problem and the directional sensor network coverage problem are studied based on the random distribution of sensor nodes in the monitoring area. In omnidirectional sensor networks, the coverage problem of hybrid networks composed of static nodes and mobile nodes is studied. The random distribution of nodes leads to the generation of coverage voids. The overlay holes are estimated by the static nodes and the specific position of the auxiliary points is calculated, and then the mobile nodes are ordered to fix the holes. In this paper, the following work is done: a) the Delaunay geometry is introduced. A triangulation network composed of static nodes is used to estimate the coverage holes in each triangle, and the number of auxiliary points is calculated according to the coverage holes. We design an algorithm for repairing coverage holes in directional sensor networks using the characteristics of node movement and rotation. The coverage of directional sensor networks is different from that of omnidirectional sensor networks. The coverage is affected by the coordinate of the node, the radius of the sensor, the working direction of the sensor and the angle of view. The randomly distributed nodes are divided into several meshes according to the Voronoi principle. The coverage problem of the whole region is transformed into the coverage optimization problem in each grid. In this paper, two virtual auxiliary points of sensor nodes are introduced. Nodes decide whether to move or rotate in the grid according to the decision of the two auxiliary nodes. Three coverage optimization algorithms: a Voronoi vertex based mobile coverage algorithm for nodes in the grid is designed in the coverage of directed sensor networks. The algorithm mainly utilizes the mobility characteristics of nodes, Based on the decision to determine whether the auxiliary point is moving within the current grid (that is, whether the sensor node is completely covered in the current grid), the node trajectory is always limited to the current grid. Based on the Voronoi vertex, the algorithm of improving the working direction of the grid rotation is proposed. The algorithm effectively controls the working direction of the nodes by using the rotation characteristics of the nodes. A boundary based rotation algorithm is used to maximize coverage in the current grid at a minimum rotation angle. This algorithm improves the effective coverage of boundary nodes and the utilization of sensor nodes. In this paper, the region coverage problem of omnidirectional sensor networks and directional sensor networks is studied, and the algorithm is designed by introducing two classical geometric figures, Delaunay and Voronoi. Finally, the paper makes a summary and prospects, and points out the problems to be solved and improved in this paper and the further work to be done.
【学位授予单位】：东华大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP212.9;TN929.5

【相似文献】