Exact algorithms for the minimum power symmetric connectivity problem in wireless networks

In this paper we consider the problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized. Two mixed integer programming formulations are presented together with some ne...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2005-11, Vol.32 (11), p.2891-2904
Main Authors: Montemanni, R., Gambardella, L.M.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Exact sciences and technology
Integer programming
Mathematical programming
Operational research and scientific management
Operational research. Management science
Operations research
Studies
Telecommunications
Telecommunications and information theory
Teleprocessing networks. Isdn
Valuation and optimization of characteristics. Simulation
Wireless networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we consider the problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized. Two mixed integer programming formulations are presented together with some new valid inequalities for the polytopes associated. A preprocessing technique and two exact algorithms based on the formulations previously introduced are also proposed. Comprehensive computational results, which show the effectiveness of the new valid inequalities and of the preprocessing technique are presented. The experiments also show that the exact approaches we propose outperform more complex methods recently appeared in the literature.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2004.04.017