Data transmission and base-station placement for optimizing network lifetime

We study the problem of transmitting data from a set of sensors to a base-station where the data is to be gathered. Each sensor continuously generates data and has to transmit it through the network (via other sensor nodes) to the base-station. Considering the battery limitations of the sensors, our goal is to find an optimum location of the base-station and a corresponding data transmission scheme for routing the data from the sensors, such that the network is operating for the longest possible time. We focus mainly on tree networks for 2-level trees, with at most 2 hops from sensor to the base-station. For such networks we give efficient algorithms for forwarding data from sensors to the base-station and for locating the base-station optimally for maximizing network lifetime. Further, we show that determining a transmission protocol for trees with 3 or more levels is NP-hard. We demonstrate the effectiveness of our methods with experimental results on simulated data, comparing our 2-level tree algorithm with methods based on linear programming.