基于Voronoi图的SDSN覆盖优化算法研究

发布时间：2018-10-20 16:32

【摘要】：本学位论文的研究课题来源于国家自然科学基金"软件定义传感网的网络重配置若干算法研究"(基金号:61471164)。主要工作是对软件定义传感器网络(SDSN,Software-DefinedSensorNetworks)的覆盖优化问题进行研究,提出了基于Voronoi图的覆盖优化算法和基于节点剩余能量的覆盖优化算法。对于基于Voronoi图的覆盖优化算法,首先设计了极小化极大半径算法(MRA,MinimaxRadiusAlgorithm),在保证目标区域全覆盖的基础上,尽可能地缩小节点的感知半径。其次设计了休眠算法(SLA,SLeeping-based Algorithm),在不产生新的覆盖空洞的前提下,设置尽可能多的节点的工作模式为休眠。然后结合了 MRA与SLA两者的特点,设计了极小化极大半径和休眠算法(MSA,Minimax radius and Sleeping-based Algorithm)和基于休眠和极小化极大半径算法(SMA,Sleeping-based and Minimax radius Algorithm),采用缩小节点感知半径和使节点休眠的方法尽可能地增加网络的工作效率。对于基于节点剩余能量的覆盖优化算法,根据Delaunay三角剖分,设计了一种基于节点剩余能量的半径优化分配方法,在保证目标区域全覆盖的前提下,均衡网络能量分布。最后,分别运用仿真工具对所提的两种覆盖优化算法进行了分析,仿真结果表明两种算法均能减少网络的能量消耗,随着目标区域内节点数量的增加,两种算法减少的网络能量消耗比例也增加。本论文共分为五章,主要包含以下内容。第一章介绍了课题研究背景以及国内外的发展现状,阐明研究课题的意义和用途,同时简要介绍主要研究工作及具体章节安排。第二章首先介绍了无线传感器网络(WSN,Wireless Sensor Networks)的概念和特点,引出软件定义网络(SDN,Software-Defined Networks)的概念并简要介绍了 SDN体系结构和SDN控制器,阐述了 OpenFlow的工作原理。然后结合WSN与SDN引出SDSN的概念。最后简要介绍了 SDN其它相关应用。第三章以SDSN为应用场景,根据几何里面Voronoi图的概念设计了 MRA、SLA、MSA和SMA,在保持目标区域全覆盖的前提下,尽可能减少网络的能量消耗并运用仿真工具验证了算法的有效性。第四章根据不同节点具有不同的剩余能量,将Delaunay三角剖分的概念引入SDSN覆盖优化算法之中,计算节点的最优感知半径分配方法并通过仿真工具分析该方法的有效性。第五章对学位论文的主要工作进行了总结,对下一步研究工作进行了展望。
[Abstract]:The research of this dissertation comes from the National Natural Science Foundation of China, "Research on several algorithms for Network reconfiguration of Software Definitions Sensor Networks" (Fund No.: 61471164). The main work of this paper is to study the coverage optimization of software defined sensor networks (SDSN,Software-DefinedSensorNetworks). A coverage optimization algorithm based on Voronoi graph and a coverage optimization algorithm based on residual energy of nodes are proposed. For the coverage optimization algorithm based on Voronoi graph, the minimum maximum radius algorithm (MRA,MinimaxRadiusAlgorithm) is first designed to minimize the perceived radius of nodes on the basis of ensuring the full coverage of the target area. Secondly, we design a sleep algorithm (SLA,SLeeping-based Algorithm), which sets as many nodes as possible to sleep without generating new overlay holes. Then combined with the characteristics of MRA and SLA, The minimum radius and sleep algorithm (MSA,Minimax radius and Sleeping-based Algorithm) and the algorithm based on sleep and minimization maximum radius (SMA,Sleeping-based and Minimax radius Algorithm),) are designed to increase the efficiency of the network as much as possible by reducing the perceived radius of the nodes and enabling the nodes to sleep. For the coverage optimization algorithm based on the residual energy of nodes, according to the Delaunay triangulation, a radius optimal allocation method based on the residual energy of the nodes is designed, which can balance the energy distribution of the network on the premise of ensuring the full coverage of the target area. Finally, the simulation tools are used to analyze the proposed two coverage optimization algorithms. The simulation results show that the two algorithms can reduce the energy consumption of the network, with the increase of the number of nodes in the target area. The ratio of network energy consumption reduced by the two algorithms is also increased. This paper is divided into five chapters, mainly including the following content. The first chapter introduces the background of the research and the development situation at home and abroad, clarifies the significance and use of the research, and briefly introduces the main research work and specific chapter arrangement. The second chapter introduces the concept and characteristics of Wireless Sensor Network (WSN,Wireless Sensor Networks), introduces the concept of Software definition Network (SDN,Software-Defined Networks), briefly introduces the SDN architecture and SDN controller, and expounds the working principle of OpenFlow. Then the concept of SDSN is introduced by combining WSN with SDN. Finally, other related applications of SDN are briefly introduced. In chapter 3, using SDSN as the application scene, according to the concept of Voronoi graph in geometry, we design MRA,SLA,MSA and SMA, to reduce the energy consumption of the network while keeping the full coverage of the target area, and use simulation tools to verify the effectiveness of the algorithm. In chapter 4, according to the different residual energy of different nodes, the concept of Delaunay triangulation is introduced into the SDSN coverage optimization algorithm, and the optimal perceptual radius allocation method of nodes is calculated, and the effectiveness of the method is analyzed by simulation tools. The fifth chapter summarizes the main work of the dissertation and looks forward to the next research work.
【学位授予单位】：东南大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN929.5;TP212.9

【相似文献】