无线网络中一些图论与组合优化问题

无线传感器网络作为一个新兴的应用领域，必然会带来许多新的研究问题，其中主要包括拓扑控制、数据融合、路由协议、覆盖问题等等。由于传感器节点通常携带能量有限的电池，网络中优化问题的首要设计目标是能源的高效使用。本项目着重探讨两类基本问题：（1）能量高效与最短时间的数据融合，（2）最小能量或最小干扰的拓扑控制。我们拟对无线网络的数据融合、最小能量（连通）控制集以及最小干扰数等方面提出的一系列新型的网络优化问题进行算法研究，特别设计这些问题的具有良好性能保证的近似算法。

传感器网络作为一个新兴的应用领域，带来许多新的研究问题，其中主要包括拓扑控制，数据融合，路由协议，覆盖问题等。我们主要研究了网络中能量高效与最短时间的数据融合问题、最小控制集问题的计算复杂性和近似算法； 图论中二维带宽问题、匹配可扩问题；工件排序问题等。受本项目资助共发表学术论文12篇；还有3篇接收待发表。其中代表性成果如下：（1）对于最短时间的数据融合问题设计了具有常数近似比的算法；（2）对单位圆盘图中Roman控制集问题给出了NP-困难性证明和近似算法；（3）对具有容量限制的最小控制集与连通控制集问题给出了这两个问题近似比分别为6和9的近似算法；（4）对于二维带宽问题研究了基本性质，上下界以及精确结果。