1. Fault-tolerant routing: -inconnected many-to-one routing in wireless networks
- Author
-
Li, Deying, Wang, Yuexuan, Zhu, Qinghua, and Yang, Huiqiang
- Subjects
- *
FAULT-tolerant computing , *ROUTING (Computer network management) , *WIRELESS communications , *COMPUTER networks , *APPROXIMATION algorithms , *COMPUTER programming , *COMPUTER simulation - Abstract
Abstract: This paper addresses the problem of fault-tolerant many-to-one routing in static wireless networks with asymmetric links, which is important in both theoretical and practical aspects. The problem is to find a minimum energy subgraph for a given subset and a destination node such that there are node-disjoint paths from each node in the subset to the destination node in the subgraph. Firstly, we prove that the problem is NP-hard, and then propose two approximation algorithms: the minimum weight node-disjoint paths based (MWkNDPB) algorithm and the minimum energy node-disjoint paths based (MEkNDPB) algorithm. Extensive simulations have been conducted to show that proposed algorithms are efficient. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF