首页> 外文期刊>IEEE/ACM Transactions on Networking >Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-hop Networks
【24h】

Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-hop Networks

机译:无线多跳网络的容错拓扑控制算法中的功率优化

获取原文
获取原文并翻译 | 示例

摘要

In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power while maintaining $k$-fault tolerance. Specifically, we require all links established by this power setting be symmetric and form a $k$-vertex connected subgraph of the network graph. This problem is known to be NP-hard. We show current heuristic approaches can use arbitrarily more power than the optimal solution. Hence, we seek approximation algorithms for this problem. We present three approximation algorithms. The first algorithm gives an $O(kalpha )$ -approximation where $alpha $ is the best approximation factor for the related problem in wired networks (the best $alpha $ so far is $O(log k)$ .) With a more careful analysis, we show our second (slightly more complicated) algorithm is an $O(k)$ -approximation. Our third algorithm assumes that the edge lengths of the network graph form a metric. In this case, we present simple and practical distributed algorithms for the cases of 2- and 3-connectivity with constant approximation factors. We generalize this algorithm to obtain an $O(k^{2c+2})$-approximation for general $k$-connectivity ($2leq cleq 4$ is the power attenuation exponent). Finally, we show that these approximation algorithms compare favorably with existing heuristics. We note that all algorithms presented in this paper can be used to minimize power -while maintaining $k$-edge connectivity with guaranteed approximation factors. Recently, different set of authors used the notion of $k$-connectivity and the results of this paper to deal with the fault-tolerance issues for static wireless network settings.
机译:在ad hoc无线网络中,至关重要的是在保持关键网络属性的同时将功耗降至最低。这项工作研究了无线设备的功率分配,这些功率分配可在保持$ k $-故障容限的同时最大程度地降低功率。具体来说,我们要求通过此幂设置建立的所有链接都对称,并形成网络图的$ k $-顶点连接子图。已知此问题是NP难题。我们显示,当前的启发式方法可以比最佳解决方案任意使用更多的功能。因此,我们寻求该问题的近似算法。我们提出了三种近似算法。第一种算法给出了$ O(kalpha)$近似值,其中$ alpha $是有线网络中相关问题的最佳近似因子(到目前为止,最好的$ alpha $是$ O(log k)$)。仔细分析,我们显示第二种算法(稍微复杂一些)是一个$ O(k)$近似值。我们的第三个算法假设网络图的边长形成一个度量。在这种情况下,我们针对具有恒定逼近因子的2和3连通性情况提供了简单实用的分布式算法。我们对该算法进行一般化,以获得与一般$ k $连通性的$ O(k ^ {2c + 2})$逼近($ 2leq cleq 4 $是功率衰减指数)。最后,我们证明了这些近似算法与现有的启发式算法相比具有优势。我们注意到,本文中介绍的所有算法都可用于最大程度地降低功耗,同时在保证近似因子的情况下保持$ k $边缘连接。最近,不同的作者使用$ k $ -connectivity概念和本文的结果来处理静态无线网络设置的容错问题。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号