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 u u in a directed spanning subgraph H H is given by p H ( u ) = max uv ? E ( H ) c ( uv ) , and corresponds to the energy consumption required for node u u to transmit to all nodes v v with uv?E(H) uv ? E ( H ) . The power  of H H is given by p ( H ) = ? u ? V p H ( u ) . Power Assignment seeks to minimize p(H) p ( H ) while H 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 d and a r?V r ? V . The output H H must be a r r -rooted outgoing arborescence of depth at most d d . We give an (O(logn),O(logn)) ( O ( log n ) , O ( log n ) ) bicriteria approximation algorithm for Min-Power Bounded-Hops Broadcast: that is, our output has depth at most O(dlogn) O ( d log n ) and power at most O(logn) O ( log n ) 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 ( ( log n ) ? ) 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 H H must have a path of at most d 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.
ad hoc wireless networks topology control bicriteria approximation approximation algorithms