• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks
【24h】

Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks

机译：在无线网络中构造带界的最小连通控制集

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Connected Dominating Sets (CDSs) can serve as virtual backbones for wireless networks. A smaller virtual backbone incurs less maintenance overhead. Unfortunately, computing a minimum size CDS is NP-hard, and thus most researchers in this area concentrate on how to construct smaller CDSs. However, people neglected other important metrics of network, such as diameter and average hop distances between two communication parties. In this paper, we investigate the problem of constructing quality CDS in terms of size, diameter, and Average Backbone Path Length (ABPL). We present two centralized algorithms having constant performance ratios for its size and diameter of the constructed CDS. Especially, the size of CDS computed by the second algorithm is no more than 6.906 times of its optimal solution. Furthermore, we give its distributed version, which not only can be implemented in real situation easily but also considers energy to extend network lifetime. In our simulation, we show that in average the distributed algorithm not only generates a CDS with smaller diameter and ABPL than related work but also suppresses its size well. We also show that it is more energy efficient than others in prolonging network lifetime.
机译：连接支配集（CDS）可以用作无线网络的虚拟主干。较小的虚拟主干网将导致较少的维护开销。不幸的是，计算最小尺寸的CDS是NP难的，因此该领域的大多数研究人员都专注于如何构建较小的CDS。但是，人们忽略了网络的其他重要指标，例如两个通信方之间的直径和平均跳距。在本文中，我们从大小，直径和平均骨干路径长度（ABPL）的角度研究了构建高质量CDS的问题。我们提出了两种集中式算法，它们的大小和所构建CDS的直径具有恒定的性能比。特别是，第二种算法计算出的CDS的大小不超过其最优解的6.906倍。此外，我们给出了它的分布式版本，它不仅可以轻松地在实际情况下实现，而且还考虑了延长网络寿命的精力。在我们的仿真中，我们表明，平均而言，分布式算法不仅会生成比相关工作更小的直径和ABPL的CDS，而且还能很好地抑制其大小。我们还表明，在延长网络寿命方面，它比其他能源效率更高。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号