Adaptive Broadcast Consumption (ABC), a new heuristic and new bounds for the Minimum Energy Broadcast Routing Problem
- Resource Type
- Authors
- Stéphane Pérennes; Alfredo Navarra; Ralf Klasing; Aris Papadopoulos
- Source
- Adaptive Broadcast Consumption (ABC), a new heuristic and new bounds for the Minimum Energy Broadcast Routing Problem
Proc. 3rd FIP-TC6 Networking Conference (Networking 2004)
Proc. 3rd FIP-TC6 Networking Conference (Networking 2004), 2004, Greece. pp.866--877
Lecture Notes in Computer Science ISBN: 9783540219590
NETWORKING
Scopus-Elsevier
- Subject
- Consumption (economics)
[INFO.INFO-OH] Computer Science [cs]/Other [cs.OH]
Computer science
Heuristic
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH]
Routing (electronic design automation)
Heuristics
Algorithm
Energy (signal processing)
ComputingMilieux_MISCELLANEOUS
- Language
- English
In this paper we present a new heuristic called Adaptive Broadcast Consumption (ABC for short) for the Minimum-Energy Broadcast Routing (MEBR) problem. We first investigate the problem trying to understand which are the main properties not taken into account by the classic and well-studied MST and BIP heuristics, then we propose a new algorithm proving that it computes the MEBR with an approximation ratio less than or equal to MST, for which we prove an approximation ratio of at most 12.15 instead of the well-known 12 [10]. Finally we present experimental results supporting our intuitive ideas, comparing ABC with other heuristics presented in the literature and showing its good performance on random instances even compared to the optimum.