...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>ACM transactions on sensor networks >Near-Optimal Deterministic Steiner Tree Maintenance in Sensor Networks
【24h】

Near-Optimal Deterministic Steiner Tree Maintenance in Sensor Networks

机译：传感器网络中的近最佳确定性Steiner树维护

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

摘要

We consider the group-communication maintenance problem between a set of k mobile agents that are tracked by a static sensor network. We develop a scalable deterministic distributed algorithm for maintaining a Steiner tree of the agents so that group communication between them can be provided with the minimum total cost possible. The main idea is that our algorithm maintains a virtual tree of mobile agents that can be immediately converted to an actual Steiner tree at all times. Our algorithm achieves the Steiner tree with total length at most O(log k) times the length of the optimal Steiner tree in the constant-doubling graph model. The total communication cost (the number of messages) to maintain the Steiner tree is only O(min{log n, log D}) times the optimal communication cost, where n and D, respectively, are the number of nodes and the diameter of the constant-doubling network. We also develop improved algorithms for the mobile k-center, sparse-aggregation, and distributed-matching problems. Experimental evaluation results show the benefits of our algorithms compared to previous algorithms. These four problems are NP-hard and, to the best of our knowledge, our algorithms are the first near-optimal deterministic algorithms for maintaining approximate solutions to these important network problems with low maintenance costs in a distributed setting.
机译：我们考虑由静态传感器网络跟踪的一组k个移动代理之间的组通信维护问题。我们开发了一种可伸缩的确定性分布式算法，用于维护代理的Steiner树，以便可以以最小的总成本提供它们之间的组通信。主要思想是我们的算法维护移动代理的虚拟树，可以随时将其立即转换为实际的Steiner树。在恒定倍数图模型中，我们的算法获得的Steiner树的总长度最多为O（log k）乘以最佳Steiner树的长度。维护Steiner树的总通信成本（消息数）仅为O（min {log n，log D}）乘以最佳通信成本，其中n和D分别是节点数和直径不断增加的网络。我们还针对移动k中心，稀疏聚合和分布式匹配问题开发了改进的算法。实验评估结果显示了与以前的算法相比，我们的算法的优势。这四个问题都是NP难题，据我们所知，我们的算法是第一个接近最优的确定性算法，用于在分布式环境中以低维护成本维护这些重要网络问题的近似解决方案。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号