Dual Decomposition for Computational Optimization of Minimum-Power Shared Broadcast Tree in Wireless Networks
2012 (English)In: IEEE Transactions on Mobile Computing, ISSN 1536-1233, E-ISSN 1558-0660, Vol. 11, no 12, 2008-2019 p.Article in journal (Refereed) Published
We consider the problem of constructing a shared broadcast tree (SBT) in wireless networks, such that the total power required for supporting broadcast initiated by all source nodes is minimal. In the well-studied minimum-energy broadcast (MEB) problem, the optimal tree varies by source. In contrast, SBT is source-independent, thus substantially reducing the overhead for information storage and processing. The SBT problem also differs from the range assignment problem (RAP), because the power for message forwarding in SBT, although being source-independent, depends on from which tree neighbor the message is received. We approach SBT from a computational optimization standpoint, and present a dual decomposition method applied to an optimization model that embeds multiple directed trees into a shared tree. For the dual decomposition method, some of the constraints in the model are preferably formulated implicitly. The dual decomposition scheme is coupled with a fast local search algorithm. We report computational results demonstrating the effectiveness of the proposed approach. In average, the performance gap to global optimality is less than three percent.
Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE) , 2012. Vol. 11, no 12, 2008-2019 p.
Shared broadcast tree, wireless networks, discrete optimization, dual decomposition
National CategoryEngineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-85844DOI: 10.1109/TMC.2011.231ISI: 000310390400005OAI: oai:DiVA.org:liu-85844DiVA: diva2:573292
Funding Agencies|Swedish Research Council||CENIIT center of Linkoping University, Sweden||ELLITT center of Linkoping University, Sweden||Research Council of Norway|201434/S10|2012-11-302012-11-302012-12-21