无线网络中连通控制集问题及其变形的近似算法的研究

Connected dominating set (CDS) can be used as the virtual backbone in wireless networks. With the help of CDS, message burden can be reduced, routing becomes much easier and the efficiency and stability of communication can be improved. Thus, finding a fine CDS is a significant work in wireless networks. In this project, we study the CDS problem and its variants in wireless networks. This project has a practical background, and concerns many scientific fields, such as combinatorial optimization, graph theory, computational complexity and approximation algorithm...In detail, this project will study the d-hop CDS problem and fault-tolerant d-hop CDS problem in unit disk graphs, in order to present new approximation algorithms and improve the approximation ratio. We will thorough research the open problems on node-weighted CDS in unit disk graphs and design better and more implementary approximation algorithms. Then, this project will discuss the unsolved situation in the connected dominating set problem under routing cost constraint, to find approximation algorithms and determine whether it has polynomial-time approximation scheme (PTAS). Furthermore, we will study the structure and properties of more general wireless networks-disk graphs with bidirectional links and disk graphs and discuss the relationship between unit disk graphs and them, to present better approximation algorithms for CDS problem and its variants in these two graphs. Finally, we will probe other variants and preliminary study the CDS problem and its variants in unit ball graphs.

连通控制集在无线网络中起着虚拟中枢链路的作用，可以降低信息负荷，简化路由，提高通信效率和稳定性。因此，寻找一个好的连通控制集是十分有意义的。本项目研究无线网络的连通控制集及其变形问题，研究内容具有实际背景，研究方法涉及组合最优化，图论，计算复杂性及近似算法等领域。具体地，本项目研究单位圆盘图的多跳连通控制集问题和容错多跳连通控制集问题，提出新的近似算法并改进近似比；对单位圆盘图上点赋权连通控制集方面尚未解决的公开问题进行深入研究，设计更好更具有操作性的近似算法；讨论有路由限制的连通控制集问题，对尚未解决的情形，探索近似算法，并判断其是否具有多项式时间近似方案；研究更一般的无线网络- - 双向圆盘图和圆盘图的结构和性质，讨论这两类图与单位圆盘图的关系，给出这两类图上求解连通控制集及其变形问题的更好的近似算法；最后，探讨其它几类连通控制集的变形，并对单位球图上连通控制集问题及其变形做初步研究。

连通控制集在无线网络中起着虚拟中枢链路的作用，可以降低信息负荷，简化路由，提高通信效率和稳定性。因此，寻找一个好的连通控制集是十分有意义的。本项目主要研究了一般图上的多跳连通控制集，单位圆盘图上的容错连通控制集，点赋权连通控制集，双向圆盘图上和圆盘图上的连通控制集变形问题的近似算法。此外，我们还对网络中常用的拓扑结构--超立方的变形进行了研究，考察了这些图类上一些参量的性质及计算复杂性。在多跳连通控制集方面，我们提出一个贪心策略的连接算法，证明了该算法优于已有的支撑树的连接方法，并通过仿真模拟表明对于一般图，新算法的计算结果明显优于已有算法；在单位圆盘图的容错连通控制集方面，我们首先对已有的3-连通控制集近似算法进行了改进，较低了其复杂性并简化了证明方法，然后我们还提出了4-连通控制集的常数近似比的近似算法，并尝试将算法推广到一般的连通度上，这是目前为止首个高连通控制集的近似算法；关于点赋权连通控制集问题，我们认为该问题不具有PTAS并且正在尝试给予严谨的理论证明；对于双向圆盘图与圆盘图，我们考虑了多跳连通控制集与容错连通控制集问题，提出了这些问题的近似算法并证明其近似比为关于最大半径与最小半径之比的函数；关于超立方的变形，我们考虑了平衡超立方的容错哈密尔顿二部连通性，证明了任意去掉至多2n-2条边后，新的图依旧是哈密尔顿二部连通的，同时我们得到该图的超2-连通度与超3-连通度都为4n–4，且超2-边连通度为与6n-4；关于增广超立方，我们证明了其存在两条点不交的同样长度的路将它的所有顶点覆盖；我们还考虑了网络健壮度的另一个重要参数--匹配排除集，研究了它的一般形式--反凯库勒结构与推广形式--s-限制匹配排除集，并证明了二部图上的这两个问题都是NP-完备的。