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

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

项目编号： No.11201208

项目类型： 青年科学基金项目

立项/批准年度： 2013

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

项目作者： 李宪越

作者单位： 兰州大学

项目金额： 23万元

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

中文关键词： 单位圆盘图；连通控制集；近似算法；无线网络；超立方图

英文摘要： 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 betwee

英文关键词： unit disk graphs；connected dominating set；approximation algorithm；wireless networks；hypercube