Lecture Notes in Computer Science, 2009, Volume 5573/2009, 483-493, DOI: 10.1007/978-3-642-02026-1_46

Fault-Tolerant Routing: k-Inconnected Many-to-One Routing in Wireless Networks

Deying Li, Qinghua Zhu and Huiqiang Yang

View Related Documents

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 k node-disjoint paths from each node in the subset to the destination node in the subgraph. We prove that the problem is NP-hard, and propose two efficient heuristic approaches, namely, the minimum weight k node-disjoint paths based (MWkNDPB) approach and the minimum energy k node-disjoint paths based (MEkNDPB) approach. Extensive simulations have been conducted to show that proposed algorithms are efficient.

Keywords  wireless networks - fault-tolerant -  k-inconnected many-to-one routing - heuristics

Fulltext Preview

Image of the first page of the fulltext document