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). The input consists of a directed complete weighted digraph G=(V,c)G=(V,c) (that is, c:V×V→R+). The power   of a vertex uu in a directed spanning subgraph HH is given by pH(u)=maxuv∈E(H)c(uv), and corresponds to the energy consumption required for node uu to transmit to all nodes vv with uv∈E(H)uv∈E(H). The power   of HH is given by p(H)=∑u∈VpH(u). Power Assignment seeks to minimize p(H)p(H) while HH satisfies the given connectivity constraint.Min-Power Bounded-Hops Broadcast is a power assignment problem which has as additional input a positive integer dd and a r∈Vr∈V. The output HH must be a rr-rooted outgoing arborescence of depth at most dd. We give an (O(logn),O(logn))(O(logn),O(logn)) bicriteria approximation algorithm for Min-Power Bounded-Hops Broadcast: that is, our output has depth at most O(dlogn)O(dlogn) and power at most O(logn)O(logn) times the optimum solution.For the Euclidean case, when c(u,v)=c(v,u)=∥u,v∥κc(u,v)=c(v,u)=∥u,v∥κ (here ∥u,v∥∥u,v∥ is the Euclidean distance and κκ is a constant between 2 and 5), the output of our algorithm can be modified to give a O((logn)κ)O((logn)κ) 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∥κc(u,v)=c(v,u)=∥u,v∥κ.Our bicriteria results extend to Min-Power Bounded-Hops Strong Connectivity, where HH must have a path of at most dd 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.