A branch and price algorithm for the minimum power multicasting problem in wireless sensor networks |
| |
Authors: | R Montemanni V Leggieri |
| |
Institution: | 1.Istituto Dalle Molle di Studi sull’Intelligenza Artificiale (IDSIA),Manno,Switzerland;2.Faculty of Computer Science,Free University of Bozen-Bolzano,Bolzano,Italy;3.Dipartimento di Matematica,Università del Salento,Lecce,Italy |
| |
Abstract: | The Minimum Power Multicast Problem arises in wireless sensor networks and consists in assigning a transmission power to each
node of a network in such a way that the total power consumption over the network is minimized, while a source node is connected
to a set of destination nodes, toward which a message has to be sent periodically. A new mixed integer programming model for
the problem, based on paths, is presented. A practical exact algorithm based on column generation and branch and price is
derived from this model. A comparison with state-of-the-art exact methods is presented, and it is shown that the new approach
compares favorably to other algorithms when the number of destination nodes is moderate. Under this condition, the proposed
method is able to solve previously unmanageable instances. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|