Fault Tolerant Topology Control for All-to-One and One-to-All Communication in Wireless Networks

Abstract

This paper introduces the problem of fault tolerant topology control for all-to-one and one-to-all communication in static wireless networks with asymmetric wireless links. This problem is important in both theoretical and practical aspects. We investigate two approaches, namely minimum weight based approach and nearest neighbor augmentation approach,to address this problem. Specifically, for each approach, we propose three algorithms for three interpretations of the problem: 1) construct k-node disjoint paths from every node to a specific root node, 2) construct k-node disjoint paths from the root node to every other node, 3) construct k-node disjoint paths from the root node to every other node and also from every node to the root node.

Furthermore, we give theoretical analysis for all six algorithms. Among other results, we show that the minimum weight based approach has a k-approximation algorithm for all-to-one fault tolerant topology control where k is the number of disjoint paths. When k=1, this approach solves the minimum power all-to-one 1-connected topology control problem. Through extensive simulations, we demonstrate that minimum weight based approach performs better for the first two interpretations and the augmentation based approach performs better for the third interpretation. To the best of our knowledge, this paper is the first to study the fault tolerant topology control for all-to-one and one-to-all communication in asymmetric static wireless networks, and also is the first to demonstrate that the minimum power all-to-one 1-connected topology control problem has an optimal solution.