Exact Algorithms for Maximum Lifetime Data-Gathering Tree in Wireless Sensor Networks

Marco Casazza () and Alberto Ceselli ()
Additional contact information
Marco Casazza: Dipartimento di Informatica, Università degli Studi di Milano, 20133 Milano, Italy
Alberto Ceselli: Dipartimento di Informatica, Università degli Studi di Milano, 20133 Milano, Italy

INFORMS Journal on Computing, 2022, vol. 34, issue 4, 1987-2002

Abstract: We tackle an optimization problem arising in the design of sensor networks: given a set of sensors, only one being connected to a backbone, to establish connection routes from each of them to the sink. Under a shortest path routing protocol, the set of connections form a spanning tree. Energy is required to transmit and receive data, and sensors have limited battery capacity: as soon as one sensor runs out of battery, a portion of the network is disconnected. We, therefore, search for the spanning tree maximizing the time elapsed before such a disconnection occurs, and therefore, maintenance is required. We propose new mathematical formulations for the problem, proving and exploiting theoretical results on its combinatorial structure. On that basis, we design algorithms offering a priori guarantees of global optimality. We undertake an extensive experimental campaign, showing our algorithms to outperform previous ones from the literature by orders of magnitude. We also identify which instance features have higher impact on network lifetime.

Keywords: sensor networks; energy conservation; data aggregation; spanning tree; exact algorithms (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1175 (application/pdf)

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:inm:orijoc:v:34:y:2022:i:4:p:1987-2002

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().