• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Workshop on Experimental and Efficient Algorithms(WEA 2005); 20050510-13; Santorini Island(GR) >The 'Real' Approximation Factor of the MST Heuristic for the Minimum Energy Broadcasting
【24h】

The 'Real' Approximation Factor of the MST Heuristic for the Minimum Energy Broadcasting

机译：MST启发式用于最小能量广播的“真实”近似因子

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

摘要

The paper deals with one of the most studied problems during the last years in the field of wireless communications in Ad-Hoc networks. The problem consists in reducing the total energy consumption of wireless radio stations randomly spread on a given area of interest to perform the basic pattern of communication given by the Broadcast. Recently an almost tight 6.33-approximation of the Minimum Spanning Tree heuristic has been proved. While such a bound is theoretically close to optimum compared to the known lower bound of 6 , there is an evident gap with practical experimental results. By extensive experiments, proposing a new technique to generate input instances and supported by theoretical results, we show how the approximation ratio can be actually considered close to 4 for a "real world" set of instances, that is, instances with a number of nodes more representative of practical purposes.
机译：本文讨论了近年来Ad-Hoc网络中无线通信领域中研究最多的问题之一。问题在于减少随机分布在给定感兴趣区域上以执行广播给出的基本通信模式的无线电台的总能耗。最近，已经证明最小生成树启发式算法几乎接近6.33逼近。尽管与已知的下限6相比，理论上该上限接近最佳值，但与实际实验结果之间存在明显差距。通过广泛的实验，提出了一种生成输入实例的新技术并得到了理论结果的支持，我们展示了如何将“真实世界”实例集（即具有多个节点的实例）的逼近率实际视为接近4更具实际意义。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号