Exact Algorithms for Maximizing Lifetime of WSNs Using Integer Linear Programming

摘要

In wireless sensor networks, maximizing the lifetime of a data gathering tree is known to be NP-hard, so various (exponential-time) exact algorithms are designed to find the best data gathering tree. The state-of-the-art exact algorithm recursively performs graph decomposition to reduce search space. However, it essentially enumerates all possibilities in adjacent graph decompositions, and cannot handle moderately large sensor networks. In this paper, we propose an exact algorithm using integer linear programming. The challenge is that some constraints are not linear in the optimization problem. To address this challenge, instead of the optimization problem, we formulate the decision problem, and solve each decision problem by integer linear programming. The optimal value is then found by binary search over all possible lifetimes. To reduce the running time, we preprocess the graph by decomposing it into bi- connected subnetworks, and propose various rules to reduce the number of candidate lifetimes. Numerical results on simulated networks show that, within two hours, our algorithm can solve more problem instances than previous algorithms.