liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Dual Decomposition for Computational Optimization of Minimum-Power Shared Broadcast Tree in Wireless Networks
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology.
University of Bergen, Norway .
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
Abstract [en]

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.
Keyword [en]
Shared broadcast tree, wireless networks, discrete optimization, dual decomposition
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-85844DOI: 10.1109/TMC.2011.231ISI: 000310390400005OAI: 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|

Available from: 2012-11-30 Created: 2012-11-30 Last updated: 2012-12-21

Open Access in DiVA

bilaga(115 kB)49 downloads
File information
File name ATTACHMENT01.pdfFile size 115 kBChecksum SHA-512
Type attachmentMimetype application/pdf
fulltext(279 kB)253 downloads
File information
File name FULLTEXT01.pdfFile size 279 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Yuan, Di
By organisation
Communications and Transport SystemsThe Institute of Technology
In the same journal
IEEE Transactions on Mobile Computing
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 253 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 78 hits
ReferencesLink to record
Permanent link

Direct link