Research Article
A Localized Algorithm Based on Minimum Cost Arborescences for the MECBS Problem with Asymmetric Edge Costs
@INPROCEEDINGS{10.1007/978-3-642-29096-1_16, author={Frederico Barboza and Fl\^{a}vio Assis}, title={A Localized Algorithm Based on Minimum Cost Arborescences for the MECBS Problem with Asymmetric Edge Costs}, proceedings={Ad Hoc Networks. Third International ICST Conference, ADHOCNETS 2011, Paris, France, September 21-23, 2011, Revised Selected Papers}, proceedings_a={ADHOCNETS}, year={2012}, month={5}, keywords={MECBS asymmetric edge costs minimum cost arborescence localized algorithm wireless sensor networks}, doi={10.1007/978-3-642-29096-1_16} }- Frederico Barboza
Flávio Assis
Year: 2012
A Localized Algorithm Based on Minimum Cost Arborescences for the MECBS Problem with Asymmetric Edge Costs
ADHOCNETS
Springer
DOI: 10.1007/978-3-642-29096-1_16
Abstract
In this paper we describe a (distributed) localized approximation algorithm for the MECBS (Minimum Energy Consumption Broadcast Subgraph) problem with asymmetric edge costs, called LMCA (Localized algorithm for energy-efficient broadcast based on ocal inimum ost rborescences). Given a directed weighted graph = (, ) with edge weight function and a source node , the MECBS problem consists of finding a range assignment to such that the induced graph contains a spanning directed tree rooted at with minimized cost. This problem can be efficiently solved for some specific cases, but it is NP-hard in the general case. To the best of our knowledge, LMCA is the first localized algorithm to the MECBS problem with asymmetric edge costs (without restricting the way how edge costs might be asymmetric). We compared LMCA with blind flooding and with two alternative solutions we designed for the problem, LMCP and LBIPAsym (a variation of LBIP for the case of asymmetric edge costs). In our experiments, LMCA outperformed these algorithms. We additionally present and evaluate two slight variations of LMCA, called LMCAc and LMCAfl.
