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). The input consists of a directed complete weighted digraph G = (V, c) (that is, c: V × V → R+). The power of a vertex u in a directed spanning subgraph H is given by pH (u) = maxuv∈E(H)c(uv), and corresponds to the energy consumption required for node u to transmit to all nodes v with uv ∈ E(H). The power of H is given by p(H) = Σu∈V pH u). Power Assignment seeks to minimize p(H) while H satisfies the given connectivity constraint.Min-Power Bounded-Hops Broadcast is a power assignment problem which has as additional input a positive integer d and a r ∈ V. The output H must be a r-rooted outgoing arborescence of depth at most d. We give an (O(log n), O(log n)) bicriteria approximation algorithm for Min-Power Bounded-Hops Broadcast: that is, our output has depth at most O(d logn) and power at most O(log n) times the optimum solution.For the Euclidean case, when c(u, v) = c(v, u) = ||u, v||k (here ||u, v|| is the Euclidean distance and K is a constant between 2 and 5), the output of our algorithm can be modified to give a O((log n)K) approximation ratio. Previous results for Min-Power Bounded-Hops Broadcast are only exact algorithms based on dynamic programming for the case when the nodes lie on the line and c(u, v) = c(v, u) = ||u, v||K.Our bicriteria results extend to Min-Power Bounded-Hops Strong Connectivity, where H must have a path of at most d edges in between any two nodes. Previous work for Min-Power Bounded-Hops Strong Connectivity consists only of constant or better approximation for special cases of the Euclidean case.
['Gruia Calinescu', 'Sanjiv Kapoor', 'Mohammad Sarwat']
Bounded-hops power assignment in ad hoc wireless networks