Data transmission and base-station placement for optimizing the lifetime of wireless sensor networks

In this paper, we study the fundamental optimization problem in wireless sensor networks of base-station positioning such that data from the sensors may be transmitted to it in an energy-efficient manner. We primarily consider the setting where a sensor transmits all of its data directly to the base-station or relays it via one other node. This setting provides two benefits: low duty-cycling due to limited synchronization requirements between nodes and low end-to-end delay due to the limited number of hops in the routes. Given the battery limitations of the sensor nodes, our objective is to maximize the network lifetime. First, we present efficient algorithms for computing a transmission scheme for the sensors given a fixed base-station and show how to implement these in a distributed fashion with only a constant number of messages per sensor. Next, we show that the optimization problem for the setting where sensors may transmit data through more than 2 hops is NP-Hard. Finally, we present efficient algorithms for the problem of locating the base-station and simultaneously finding a transmission scheme. We compare our algorithms with linear-programming based algorithms for more general settings through extensive simulations and outline the benefits of the different approaches. (C) 2011 Elsevier B.V. All rights reserved.