Exact Algorithms for Maximum Lifetime Data-Gathering Tree in Wireless Sensor Networks
研究无线传感器网络中如何构建一棵生成树，使得在最短路径路由协议下，网络在第一个传感器电池耗尽前运行时间最长，并提出了具有全局最优性保证的精确算法，实验表明算法性能远超已有方法。
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.