Advertisement
Published in:
2007 | OriginalPaper | Chapter
An Exponential Improvement on the MST Heuristic for Minimum Energy Broadcasting in Ad Hoc Wireless Networks
Authors : Ioannis Caragiannis, Michele Flammini, Luca Moscardelli
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we present a new approximation algorithm for the
Minimum Energy Broadcast Routing
(MEBR) problem in ad hoc wireless networks that has exponentially better approximation factor than the well-known Minimum Spanning Tree (MST) heuristic. Namely, for any instance where a minimum spanning tree of the set of stations is guaranteed to cost at most
ρ
times the cost of an optimal solution for MEBR, we prove that our algorithm achieves an approximation ratio bounded by 2ln
ρ
− 2 ln 2 + 2. This result is particularly relevant for its consequences on Euclidean instances where we significantly improve previous results.