Minimum Power Broadcast: Fast Variants of Greedy Approximations

摘要

We study the problem of assigning transmission power to the nodes of ad hoc wireless networks to minimize power consumption while ensuring that the given source reaches all the nodes in the network (unidirectional links allowed for broadcast). In the most general cost model, the best published approximation ratio is achieved by the "greedy spider" algorithm (Calinescu et al., ESA 2003). We present a variant of this algorithm with running time big-Oh of n to power 3 (n is the number of nodes), and the same approximation ratio. In the restricted "Euclidean" two-dimensional cost model, where the power requirement to transmit from node u to node v is the Euclidean distance between the location of u and the location v, raised to a fixed power that dependends on the wireless environment, the best known approximation ratio is achieved by the "relative greedy" algorithm (Caragiannis et al., ICALP 2007). We present a variant of this algorithm with running time big-Oh of n times m (m is the number of edges in the input graph), and the same approximation ratio. The new variants make use of advanced data structures and/or simple amortized analysis, improving naive variants by a factor of n. This improvement allows us to apply these algorithms to large instances (1000-2000 nodes). Our experimental results show that the best output achievable within 100 seconds improves the solution based on minimum spanning tree by an average of up to 15%, and comes within 25% of optimum, in average, on the instances where we can compute the optimum (based on an integer program). The improvement is circa 50% larger compared to what one would get applying existing fast heuristics.