Bounded-hops power assignment in ad-hoc wireless networks

Motivated by topology control in ad-hoc wireless networks, power assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity). These problems have been studied in the past. In this paper we consider delay bounds as an additional constraint to provide quality of service. Delay is measured by the number of hops on a path between two nodes. We present an algorithm for minimum power bounded hops broadcast with guaranteed bicriteria ratio of (O(log n), O(log n)) for general graphs. That is, in the solution produced by our algorithm, the number of hops between the root and any other node is at most O(log n) times the given bound and the power is at most O(log n) times the power of optimal solution. Our bicriteria results extend to min-power bounded-hops strong connectivity (the solution must have a path of at most d edges in between any two nodes) and min-power bounded-hops symmetric connectivity (the undirected graph having an edge uv iff the solution has both uv and vu is required to have diameter at most d). Previous work for min-power bounded-hops strong connectivity consists only of constant or better approximation for special cases of the Euclidean case. We also provide better guarantees for the Euclidean cases by post processing solutions of the main algorithm.