Fault-tolerant routing: <i>k</i>-inconnected many-to-one routing in wireless networks

作     者：Li, Deying Wang, Yuexuan Zhu, Qinghua Yang, Huiqiang 

作者机构：Renmin Univ China Key Lab Data Engn & Knowledge Engn MOE Beijing Peoples R China Renmin Univ China Sch Informat Beijing Peoples R China Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2011年第412卷第3期

页      面：209-216页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Wireless networks Fault-tolerant k-inconnected many-to-one routing Approximation algorithm 

摘      要：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 k 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 k node-disjoint paths based (MWkNDPB) algorithm and the minimum energy k node-disjoint paths based (MEkNDPB) algorithm. Extensive simulations have been conducted to show that proposed algorithms are efficient. (C) 2009 Elsevier B.V. All rights reserved.