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

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 computational geometry especially Voronoi diagrams can be enriched by new problem domains.

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

无线传感器网络（WSN）是当今国内外备受关注的、由多学科高度交叉的新兴前沿研究领域。传感器的部署及覆盖是其中的一个关键问题，即通过一定的算法放置或移动节点，优化节点分布，合理分配网络的空间资源，以期网络在应用中利用率最大化或单个任务能量消耗最小化，从而更好的完成环境感知、信息获取等任务，并提高网络生存能力。.在本项目的资助下，我们首先研究了WSN在已知区域的优化覆盖问题，基于已有的基于均匀区域的覆盖算法，提出了非均匀区域内的优化覆盖算法，研发了WSN交互部署仿真平台软件。对于未知区域的动态部署问题，我们重点研究了其中可见性计算的加速算法，包括多边形中点的可见性计算与NURBS曲线路径的弱可见区域计算。进一步的，我们研究了重心Voronoi图的扩展与应用，提出了包括基于流线重心 Voronoi 图的流场布局算法，基于能量图的圆排列优化算法，并应用于图像拼贴与层次数据可视化布局等问题中，基于扩展 Voronoi 图的泊松分布优化算法。另外，面向3D 打印这一近年来蓬勃发展的领域，我们基于 Voronoi 图的相关理论，针对其中三维物体的结构优化与形状处理等问题进行了一系列的探索。所取得的成果为无线传感器网络中覆盖与部署问题的研究与应用提供了有力的几何工具，丰富了计算几何特别是 Voronoi 图的应用研究领域和内容。.在项目执行期内，在图形学顶级期刊ACM Transactions on Graphics (TOG)上发表论文2篇，其它SCI期刊论文2篇，EI论文5篇，出版学术专著1部，申请专利9项，已授权3项，软件著作权1项，培养硕士生 4 名、博士生 1 名。