A branch-and-cut algorithm for the strong minimum energy topology in wireless sensor networks

Y.P. Aneja, R. Chandrasekaran, Xiangyong Li and K.P.K. Nair

European Journal of Operational Research, 2010, vol. 204, issue 3, 604-612

Abstract: This paper studies the strong minimum energy topology design problem in wireless sensor networks. The objective is to assign transmission power to each sensor node in a directed wireless sensor network such that the induced directed graph topology is strongly connected and the total energy consumption is minimized. A topology is defined to be strongly connected if there exists a communication path between each ordered pair of sensor nodes. This topology design problem with sensor nodes defined on a plane is an NP-Complete problem. We first establish a lower bound on the optimal power consumption. We then provide three formulations for a more general problem defined on a general directed graph. All these formulations involve an exponential number of constraints. Second formulation is stronger than the first one. Further, using the second formulation, we lift the connectivity constraints to generate stronger set of constraints that yield the third formulation. These lifted cuts turn out to be extremely helpful in developing an effective branch-and-cut algorithm. A series of experiments are carried out to investigate the performance of the proposed branch-and-cut algorithm. These computational results over 580 instances demonstrate the effectiveness of our approach.

Keywords: OR; in; energy; Wireless; sensor; network; Minimum; energy; topology; Branch; and; bound; Cutting (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00824-8
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:204:y:2010:i:3:p:604-612

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().