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

Direct link
Cite
Citation style
  • apa
  • 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
Minimum-Energy Broadcast and Multicast in Wireless Networks: An Integer Programming Approach and Improved Heuristic Algorithms
Linköping University, The Institute of Technology. Linköping University, Department of Science and Technology, Communications and Transport Systems.
University of Bergen, Bergen, Norway.
University of Bergen, Bergen, Norway.
2008 (English)In: Ad hoc networks, ISSN 1570-8705, E-ISSN 1570-8713, Vol. 6, no 5, p. 696-717Article in journal (Refereed) Published
Abstract [en]

Both integer programming models and heuristic algorithms have been proposed for finding minimum-energy broadcast and multicast trees in wireless ad hoc networks. Among heuristic algorithms, the broadcast/multicast incremental power (BIP/MIP) algorithm is most known. The theoretical performance of BIP/MIP has been quantified in several studies. To assess the empirical performance of BIP/MIP and other heuristic algorithms, it is necessary to compute an optimal tree or a very good lower bound of the optimum. In this paper, we present an integer programming approach as well as improved heuristic algorithms. Our integer programming approach comprises a novel integer model and a relaxation scheme. Unlike previously proposed models, the continuous relaxation of our model leads to a very sharp lower bound of the optimum. Our relaxation scheme allows for performance evaluation of heuristics without having to compute optimal trees. Our contributions to heuristic algorithms consist of the power-improving algorithm successive power adjustment (SPA), and improved time complexity of some previously suggested algorithms. We report extensive numerical experiments. Algorithm SPA finds better solutions in comparison to a host of other algorithms. Moreover, the integer programming approach shows that trees found by algorithm SPA are optimal or near-optimal.

Place, publisher, year, edition, pages
Institutionen för teknik och naturvetenskap , 2008. Vol. 6, no 5, p. 696-717
Keywords [en]
Algorithm, Broadcast, Integer programming, Lagrangean relaxation, Minimum-energy, Multicast, Performance evaluation, Wireless networks
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-11903DOI: 10.1016/j.adhoc.2007.06.006OAI: oai:DiVA.org:liu-11903DiVA, id: diva2:18295
Note
Original publication: Di Yuan, Joanna Bauer and Dag Haugland, Minimum-Energy Broadcast and Multicast in Wireless Networks: An Integer Programming Approach and Improved Heuristic Algorithms, 2008, Ad Hoc Networks, (6), 5, 696-717. http://dx.doi.org/10.1016/j.adhoc.2007.06.006. Copyright: Elsevier B.V., http://www.elsevier.com/Available from: 2008-05-23 Created: 2008-05-23 Last updated: 2017-12-13

Open Access in DiVA

fulltext(269 kB)621 downloads
File information
File name FULLTEXT01.pdfFile size 269 kBChecksum SHA-1
d891c7449e216ff6ea2bf8742572730213cc2bec9d8d5c9614a9e22fb67951c42477af72
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records

Yuan, Di

Search in DiVA

By author/editor
Yuan, Di
By organisation
The Institute of TechnologyCommunications and Transport Systems
In the same journal
Ad hoc networks
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 621 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: 308 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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