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

Direct link
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, 57-68 p.Article 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, 57-68 p.
Keyword [en]
Ad hoc networks, Broadcasting, Integer programming, Multicasting
National Category
Natural Sciences
URN: urn:nbn:se:liu:diva-50431DOI: 10.1002/net.20222OAI: diva2:271327
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2012-06-25

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
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: 23 hits
ReferencesLink to record
Permanent link

Direct link