Minimum power assignment in wireless ad hoc networks with spanner property

Power assignment for wireless networks is to assign a power for each wireless node such that the induced communication graph has some required properties. 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. A polynomial time algorithm is given to minimize the maximum assigned power. Then we propose a new polynomial time approximation method to minimize the total transmission radius of all nodes. We also give two heuristics 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.