Minimum power assignment in wireless ad hoc networks with spanner property

Abstract — Power assignment for wireless networks is to assign a power for each wireless node such that the induced communication graph has some required properties. In this paper, we study the power assignment such that the induced communication graph is a spanner for the original communication graph when all nodes have the maximum power. Polyno-mial time algorithm is given to minimize the maximum assigned power. Then we propose a new polynomial time approximation method to mini-mize the total transmission radius of all nodes. We also give two heuris-tics and conduct extensive simulations to study their performance when we want to minimize the total assigned power of all nodes. Our simulations validate our theoretical claims. Keywords—Power assignment, spanner, wireless ad hoc networks. I