Bi-Criteria Approximation Algorithms for Power-Efficient and Low-Interference Topology Control in Unreliable Ad Hoc Networks

Topology control in ad hoc networks is a multi-criteria optimization problem involving (contradictory) objectives of connectivity, interference, and power minimization. Additionally, nodes can be unreliable, which adds another dimension to an already challenging problem. In this paper, we study topology control problems in ad hoc networks under node failures for arbitrary node distributions. We consider a simple and natural stochastic failure model, in which each node can fail independently with a given probability. The topology control problem under stochastic failures is to choose a power level for each node and a subset of edges such that the residual graph (i.e., the graph formed by the nodes which have not failed) is connected and can be scheduled efficiently, with high probability. We develop provably efficient bi-criteria approximation algorithms for this problem that simultaneously minimize power, reduce interference, and ensure that the surviving graph is connected with high probability. Our algorithms can be implemented efficiently in a distributed manner.