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
Analysis and computational study of several integer programming formulations for minimum-energy multicasting in wireless ad hoc networks
Department of Informatics, University of Bergen, N-5020 Bergen, Norway.
Department of Informatics, University of Bergen, N-5020 Bergen, Norway.
Linköping University, The Institute of Technology. Linköping University, Department of Science and Technology, Communications and Transport Systems.
2008 (English)In: Networks, ISSN 0028-3045, E-ISSN 1097-0037, Vol. 52, no 2, p. 57-68Article in journal (Refereed) Published
Abstract [en]

A multicast session in a wireless ad hoc network concerns routing messages from a source to a set of destination devices. Transmitting messages consumes energy at the source and intermediate devices of the session. Since a battery is the only energy source in many applications of wireless ad hoc networks, energy efficiency is an important performance measure of multicasting. In this paper, we present and analyze integer programming models for the problem of minimizing the total energy required by multicasting. We start from a straightforward multicommodity flow model, which is strengthened by a more efficient representation of transmission power. Further strengthening is accomplished by lifting the capacity constraints of the model. We then present cut-based models for the problem, and prove, from a bounding standpoint, the equivalence in strength between these models and their flow-based counterparts. By expanding the underlying graph, we show that the problem can be transformed into finding a minimum Steiner arborescence. The expanded graph arises also in the separation procedure for solving one of the cut-based models. In addition to a theoretical analysis of the relation between various models, we perform extensive computational experiments to study the numerical strengths of these models and their efficiency in solving the problem. © 2008 Wiley Periodicals, Inc.

Place, publisher, year, edition, pages
2008. Vol. 52, no 2, p. 57-68
Keywords [en]
Ad hoc networks, Broadcasting, Integer programming, Multicasting
National Category
Natural Sciences
Identifiers
URN: urn:nbn:se:liu:diva-50431DOI: 10.1002/net.20222OAI: oai:DiVA.org:liu-50431DiVA, id: diva2:271327
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2017-12-12

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Yuan, D.

Search in DiVA

By author/editor
Yuan, D.
By organisation
The Institute of TechnologyCommunications and Transport Systems
In the same journal
Networks
Natural Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 123 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