版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.