无线传感器网络中带几何约束的几类组合优化问题的近似算法研究

项目名称： 无线传感器网络中带几何约束的几类组合优化问题的近似算法研究

项目编号： No.11471005

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 王卫

作者单位： 西安交通大学

项目金额： 63万元

中文摘要： 不同于传统的有线网络，无线传感器网络没有固定的基础设施，如何使大量传感器组成一个自组织、动态、可靠的网络是一个极具挑战性的研究课题。研究表明基于连通控制集的虚拟骨干是解决这一问题的关键之一。受这一实际问题的驱动，本项目拟研究无线传感器网络中虚拟骨干构造中提出的若干关键、核心NP-难解组合优化问题（譬如满足一定容错性、一定传输延时限制的虚拟骨干构造等）。我们拟采用图论、几何优化、概率分析等工具发展这些问题的在理论上有性能保证的近似算法设计，一方面深入挖掘无线传感器网络模型的内在几何特性，给出这些问题在单位圆盘图中的快速、高效的常数倍多项式时间近似算法甚至多项式时间近似方案（PTAS）；另一方面在有向圆盘图的近似算法研究上力求取得理论上的突破。上述研究不仅有着重要的理论价值，同时我们任何有意义的进展都有望在无线传感网络中得到进一步的应用。我们前期的工作为该项目的开展奠定了坚实的基础。

中文关键词： 近似算法；组合优化；算法设计与分析；网络优化；计算复杂性

英文摘要： Unlike the traditional wired networks, the wireless sensor networks have no fixed infrastructure. It is an extremely challenging problem as how to organize the numerous sensors into a self-organized, dynamic and reliable network. It was shown by many researches that the connected dominating set based virtual backbone is one of the key solutions to the above problem. Driven by this pratical problem, this project aims at studying some important NP-hard combinatorial problems arising from the virtual backbone construction in wireless sensor networks (such as the construction of a virtual backbone with a certain degree of fault-tolerance, and with a certain degree of latency). By using various tools from graph theory, geometric optimization, and probabilistic analysis, we will focus our attentions on designing approximation algorithms for these problems with theoretical performance guarantee. Fast, efficient, constant approximation algorithms as well as polynomial time approximation schemes (PTASs) will be presented for these problems, by deeply employing the geometric nature of unit disk graphs which are often used to model the wireless sensor networks. Moreover, considerable efforts will be made to seek a breakthrough for designing approximation algorithms for these problems under the more general directed disk graph model. The above investigations have deep theoretical significance, moreover, any progress in this project will find further applications in wireless sensor networks. Our previous research has laid the foundations for the development of this project.

英文关键词： Approximation Algorithm;Combinatorial Optimization;Algorithm Design and Analysis;Network Optimization;Computational Complexity