A Localized Algorithm Based on Minimum Cost Arborescences for the MECBS Problem with Asymmetric Edge Costs

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

L

ocal

M

inimum

C

ost

A

rborescences). Given a directed weighted graph

G

 = (

V

,

E

) with edge weight function

w

and a source node

s

, the MECBS problem consists of finding a range assignment to

V

such that the induced graph contains a spanning directed tree rooted at

s

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.