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

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.

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

该项目围绕无线传感器网络中一些具有重要应用背景及理论价值的NP-困难组合优化问题的近似算法设计展开研究，得到了一系列较深入的研究成果，较好地完成了各项预定目标。项目取得的主要研究成果如下：① 设计出了无线传感器网络中高容错性虚拟骨干构造的多个常数倍近似算法，先后给出了3-连通m-控制集，4-连通m-控制集，以及一般的k-连通m-控制集在单位圆盘图上的常数倍近似算法；② 对于偏连通控制集问题，在单位圆盘图上给出了第一个常数倍近似算法; ③对于不相交连通控制集问题，我们证明了该问题即使限制在树上也是NP-困难的，并给出了渐进的1.5-近似算法；④对无线传感器网络中一类障碍覆盖（barrier coverage）问题，给出了首个常数倍近似算法；⑤ 对无线传感器网络中一类带成本约束的覆盖问题,得到了常数倍近似算法；⑥对连通点覆盖问题，给出了k-正则图上渐进的2k/(k+2)-近似算法。这些近似算法设计一方面在理论上帮助我们更进一步理解这些组合优化问题的内在结构，另一方面也可望在实际中得到一定应用。通过对这些问题的近似算法研究，我们提炼出了一些新的近似算法设计方法，今后将进一步应用到更多的组合优化问题中。上述研究成果在国际著名刊物IEEE/ACM Transactions On Networking,IEEE Transactions On Mobile Computing, IEEE Transactions on Vehicular Technology, Journal of Combinatorial Optimization等发表研究论文20篇。