Asymmetric topology control: Exact solutions and fast approximations

We study the problem of assigning transmission power to the nodes of ad hoc wireless networks to minimize power consumption while ensuring strong network connectivity (unidirectional links allowed). We give (1) an exact algorithm based on new integer linear program formulations, solving instances with up to 30 nodes in one minute, (2) a fast variant of a recent greedy approximation algorithm, finishing within 85 seconds on instances with up to 2000 nodes, (3) a comprehensive experimental study comparing new and previously proposed heuristics with the above exact and approximation algorithms, showing tradeoffs between the running time and the quality of the output. Thus we deal with the original power assignment problem introduced by Chen and Huang in 1989, who proved that a minimum spanning tree (MST) based approximation algorithm has ratio of 2. Our experimental results show that the recent 1.98-approximation algorithm improves the MST solution by an average of up to 15%, and comes within 4-16% of optimum, in average, on the instances where we can compute the optimum.