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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:liu:diva-85844DOI: 10.1109/TMC.2011.231ISI: 000310390400005OAI: oai:DiVA.org:liu-85844DiVA: diva2:573292
Note

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: 2017-12-07

Open Access in DiVA

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

Other links

Publisher's full text

Authority records BETA

Yuan, Di

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: 289 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 102 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf