Date Added: Apr 2011
This paper studies the problem of energy efficient routing in a sensor network with multiple gateways. Due to the complexity of this problem, the authors divide it into two sub-problems: the problem of constructing efficient routing trees and the problem of wake-up frequency assignment in a network with multiple routing trees. For the first problem they present an optimal algorithm and an approximation algorithm that achieves very close performance but can be more easily implemented. They prove that the second problem is NP-hard and propose a polynomial time approximation algorithm.