A genetic algorithm for spanning tree optimization in sensor networks

In a time-driven sensor network, monitored data are periodically reported to the base station via a data-gathering tree. Unfortunately, the problem of finding the spanning tree with maximum lifetime is known to be NP-complete. In this work-in-progress paper, we propose a genetic algorithm to solve this problem. We test it for small-sized networks, for which the optimal solution can be evaluated, and we obtain encouraging preliminary results in terms of correctness and computational complexity.