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

Marco Casazza

doi:10.1287/ijoc.2022.1175

2022-07-01

PRE

Marco Casazza *

Alberto Ceselli

DOI：10.1287/ijoc.2022.1175

原文链接

原文求助

摘要

En 中文

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.

Keyword:

sensor networks

energy conservation

data aggregation

spanning tree

exact algorithms