无线传感器网络中的若干计算几何问题研究

项目名称： 无线传感器网络中的若干计算几何问题研究

项目编号： No.61202147

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 计算机科学学科

项目作者： 吕琳

作者单位： 山东大学

项目金额： 23万元

中文摘要： 无线传感器网络是当今国内外备受关注的、由多学科高度交叉的新兴前沿研究领域。传感器的部署及覆盖是其中的一个关键问题，即通过一定的算法放置或移动节点，优化节点分布，合理分配网络的空间资源，以期网络在应用中利用率最大化或单个任务能量消耗最小化，从而更好的完成环境感知、信息获取等任务，并提高网络生存能力。 本项目主要研究无线传感器网络部署及最优覆盖中的几何问题，具体包括：已知多边形区域中的无线传感器最优覆盖问题、未知多边形区域中的无线传感器动态部署问题和无线传感器的多重覆盖问题。针对不同的应用环境对这些问题建立形式化描述，分析其几何特性，分别基于几类广义Voronoi图建立其几何优化模型，然后利用计算几何算法进行优化求解，并基于上述理论成果研发系统原型，为无线传感器网络的研究与应用提供有力的几何工具，丰富计算几何特别是Voronoi图的应用研究领域和内容。

中文关键词： 无线传感器网络；优化覆盖；动态部署；Voronoi图；圆排列

英文摘要： Wireless sensor networks (WSNs) are attracting an increasing degree of research interest, with a growing number of industrial applications starting to emerge. Dynamic deployment for optimal coverage is one of the fundamental issues that directly affects the performance of WSNs, which aims to optimize the layout of the sensors to fulfill environment detection and information retrieval with minimal expense or maximal utility. In this project, we will focus on some key geometric problems in deployment and optimal coverage in WSNs: the optimal deployment pattern for full coverage in WSNs in a given polygon region, the optimal dynamic deployment pattern for full coverage in WSNs in an unknown polygon region, and optimal dynamic deployment pattern for multiple coverage in WSNs in a given polygon region. We will first formulate the specific problem and analyze the inside geometric characteristics for different applications, and then set up the geometric optimization models based on several types of generalized Voronoi diagrams and propose the optimizing solutions using elegant computational geometry algorithms. Also, a software system prototype will be developed based on the algorithms presented in this project. This project provides powerful geometric tools for researches and applications in WSNs, and thus the core of

英文关键词： Wireless sensor networks；area coverage；dynamic deployment；Voronoi diagram；disk packing