4.5 Article

An Exponential Improvement on the MST Heuristic for Minimum Energy Broadcasting in Ad Hoc Wireless Networks

Journal

IEEE-ACM TRANSACTIONS ON NETWORKING
Volume 21, Issue 4, Pages 1322-1331

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2012.2223483

Keywords

Approximation algorithms; broadcasting; energy consumption; wireless networks

Funding

  1. European Union [STREP FP7-258307 EULER]
  2. PRIN 2008 research project COGENT (COmputational and GamE-theoretic aspects of uncoordinated NeTworks)
  3. Italian Ministry of University and Research

Ask authors/readers for more resources

We present a new approximation algorithm for the Minimum Energy Broadcast Routing (MEBR) problem in ad hoc wireless networks that achieves an exponentially better approximation factor compared to 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 rho >= 2 times the cost of an optimal solution for MEBR, we prove that our algorithm achieves an approximation ratio bounded by 2ln rho - 2ln 2 + 2. This result is particularly relevant for its consequences on Euclidean instances where we significantly improve previous results. In this respect, our experimental analysis confirms the better performance of the algorithm also in practice.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.5
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available