• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Minimum Connected Dominating Set Using a Collaborative Cover Heuristic for Ad Hoc Sensor Networks
【24h】

Minimum Connected Dominating Set Using a Collaborative Cover Heuristic for Ad Hoc Sensor Networks

机译：Ad Hoc传感器网络使用协作覆盖启发式的最小连通支配集

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

摘要

A minimum connected dominating set (MCDS) is used as virtual backbone for efficient routing and broadcasting in ad hoc sensor networks. The minimum CDS problem is NP-complete even in unit disk graphs. Many heuristics-based distributed approximation algorithms for MCDS problems are reported and the best known performance ratio has (4.8+ln 5). We propose a new heuristic called collaborative cover using two principles: 1) domatic number of a connected graph is at least two and 2) optimal substructure defined as subset of independent dominator preferably with a common connector. We obtain a partial Steiner tree during the construction of the independent set (dominators). A final postprocessing step identifies the Steiner nodes in the formation of Steiner tree for the independent set of G. We show that our collaborative cover heuristics are better than degree-based heuristics in identifying independent set and Steiner tree. While our distributed approximation CDS algorithm achieves the performance ratio of (4.8+ln 5){rm opt} + 1.2, where {rm opt} is the size of any optimal CDS, we also show that the collaborative cover heuristic is able to give a marginally better bound when the distribution of sensor nodes is uniform permitting identification of the optimal substructures. We show that the message complexity of our algorithm is O(nDelta^{2} ), Delta being the maximum degree of a node in graph and the time complexity is O(n).
机译：最小连接支配集（MCDS）用作虚拟骨干网，以在ad hoc传感器网络中进行有效的路由和广播。即使在单位磁盘图中，最小的CDS问题也是NP完全的。报告了许多基于启发式的MCDS问题的分布式逼近算法，最著名的性能比为（4.8 + ln 5）。我们提出了一种新的启发式方法，称为协作覆盖，它使用两个原则：1）连通图的球面数至少为2，以及2）最佳子结构定义为独立主宰子集，最好具有公共连接器。在构造独立集（支配者）的过程中，我们获得了部分Steiner树。最后的后处理步骤为G的独立集识别Steiner树形成中的Steiner节点。我们证明，在识别独立集和Steiner树时，我们的协作覆盖启发式算法优于基于度的启发式算法。尽管我们的分布式近似CDS算法实现了（4.8 + ln 5）{rm opt} + 1.2的性能比，其中{rm opt}是任何最佳CDS的大小，但我们也证明了协作覆盖启发式算法能够给出当传感器节点的分布是均匀的时，边界会更好，从而可以确定最佳的子结构。我们证明了我们算法的消息复杂度为O（nDelta ^ {2}），Delta是图中节点的最大程度，时间复杂度为O（n）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号