Approximating the Minimum Number of Maximum Power Users in Ad hoc Networks

Topology control is the problem of assigning transmission power values to the nodes of an ad hoc network so that the induced graph satisfies some specified property. The most fundamental such property is that the network/graph be connected. For connectivity, prior work on topology control gave a polynomial time algorithm for minimizing the maximum power assigned to any node (such that the induced graph is connected). In this paper we study the problem of minimizing the number of maximum power nodes. After establishing that this minimization problem is NP-complete, we focus on approximation algorithms for graphs with symmetric power thresholds. We first show that the problem is reducible in an approximation preserving manner to the problem of assigning power values so that the sum of the powers is minimized. Using known results for that problem, this provides a family of approximation algorithms for the problem of minimizing the number of maximum power nodes with approximation ratios of 5/3 + ε for every ε > 0. Unfortunately, these algorithms, based on solving large linear programming problems, are not practical. The main results of this paper are practical algorithms with approximation ratios of 7/4 and 5/3 (exactly). In addition, we present experimental results, both on randomly generated networks, and on two networks derived from proximity data associated with the TRANSIMS project of Los Alamos National Labs. Finally, based on the reduction to the problem of minimizing the total power, we describe some additional results for minimizing the number of maximum power users, both for graph properties other than connectivity and for graphs with asymmetric power thresholds. A preliminary version of this paper was presented at the ADHOC-NOW’04 conference in Vancouver, Canada, July 2004. Prepared through collaborative participation in the Communications and Networks Consortium sponsored by the U.S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes not withstanding any copyright notation thereon. Errol L. Lloyd is a Professor of Computer and Information Sciences at the University of Delaware. Previously he served as a faculty member at the University of Pittsburgh and as Program Director for Computer and Computation Theory at the National Science Foundation. From 1994 to 1999 he was Chair of the Department of Computer and Information Sciences at the University of Delaware. Concurrently, from 1997 to 1999 he was Interim Director of the University of Delaware Center for Applied Science and Engineering in Rehabilitation. Professor Lloyd received undergraduate degrees in both Computer Science and Mathematics from Penn State University, and a Ph.D. in Computer Science from the Massachusetts Institute of Technology. His research expertise is in the design and analysis of algorithms, with a particular concentration on approximation algorithms. In 1989 Professor Lloyd received an NSF Outstanding Performance Award, and in 1994 he received the University of Delaware Faculty Excellence in Teaching Award. Rui Liu received the B.S. degree in mathematics from Peking University, Beijing, China, in 1998, and the Ph.D. degree in Computer and Information Sciences from the University of Delaware in 2004. Since that time, he has been a Senior Associate Staff Scientist with Oracle|Retek. His research interests include design and analysis of algorithms for combinatorial optimization problems, and mobile computing. S.S. Ravi received his Ph.D. in Computer Science from the University of Pittsburgh in 1984. Since that time, he has been on the computer science faculty at the University at Albany – State University of New York, where he is currently a Professor. His areas of interest include design and analysis of algorithms, mobile computing, data mining and fault-tolerant computing.