文章导读
总览 评价 李业芳 * ， 艾文宝 ， 帅天平 （ 北京邮电大学理学院； ） 摘要： 在本论文中，我们提出并研究双向圆盘图中的最小连通k全控制集问题，该问题在无线网络的虚拟骨干网的构造中有着很重要的意义。以前这方面的工作大多数是在单位圆盘中分析，然而，
李业芳*， 艾文宝， 帅天平
（
北京邮电大学理学院； ）
摘要：
在本论文中，我们提出并研究双向圆盘图中的最小连通k全控制集问题，该问题在无线网络的虚拟骨干网的构造中有着很重要的意义。以前这方面的工作大多数是在单位圆盘中分析，然而，在WSN中，每个传感器节点的传输半径并一定相同。在本论文中，我们给出了一个集中式近似算法来构造最小连通k全控制集(totally connected k-dominating set)，简记为k-MTCDS，通过理论分析，我们给出有较好的近似比的近似算法。
关键词：
最小连通k-全控制集；极大独立集；双向圆盘图；无线传感器网络
Li Yefang*， Ai Wenbao， Shuai Tianping
（
Department of Science, Beijing University of posts and telecommunications； ）
Abstract：
Minimum connected k-tuple totally dominating set (k-MCTDS) has been proposed in this paper which as the virtual backbone makes sense to alleviate the broadcasting storm in wireless sensor network (WSN). Most recent research has extensively focused on the construction of Connected Dominating Set in unit disk graph,in which each node has the same transmission range. However, the transmission ranges of all nodes in fault tolerant CDS in the WSN are not necessary equal. In this paper, we study a general fault tolerant CDS problem, called k-MCTDS, in disk graph and give a centralized approximation algorithm which has a constant approximation ratio.
Tag：
点此返回栏目查看更多>>>参考论文
