Online Data Gathering for MaximizingNetwork Lifetime in Sensor NetworksWeifa Liang, Senior Member, IEEE, and Yuzhen LiuAbstract—Energy-constrained sensor networks have been deployed widely for monitoring and surveillance purposes. Data gatheringin such networks is often a prevalent operation. Since sensors have significant power constraints (battery life), energy efficientmethods must be employed for data gathering to prolong network lifetime. We consider an online data gathering problem in sensornetworks, which is stated as follows: Assume that there is a sequence of data gathering queries, which arrive one by one. To respondto each query as it arrives, the system builds a routing tree for it. Within the tree, the volume of the data transmitted by each internalnode depends on not only the volume of sensed data by the node itself, but also the volume of data received from its children. Theobjective is to maximize the network lifetime without any knowledge of future query arrivals and generation rates. In other words, theobjective is to maximize the number of data gathering queries answered until the first node in the network fails. For the problem ofconcern, in this paper, we first present a generic cost model of energy consumption for data gathering queries if a routing tree is usedfor the query evaluation. We then show the problem to be NP-complete and propose several heuristic algorithms for it. We finallyconduct experiments by simulation to evaluate the performance of the proposed algorithms in terms of network lifetime delivered. Theexperimental results show that, among the proposed algorithms, one algorithm that takes into account both the residual energy and thevolume of data at each sensor node significantly outperforms the others.Index Terms—Sensor network, data gathering, energy consumption optimization, network lifetime, sensor database, sensornet queryoptimization.Ç1INTRODUCTIONRECENT advances in microelectronic technology havemade it possible to construct compact and inexpensivewireless sensors. Networks formed by such sensors, termedwireless sensor networks, have been receiving significantattention due to their potential applications in environ-mental surveillance, military operations, and other domains[22]. In such networks, each sensor not only serves as a hostto generate sensed data and to process the collected data,but also as a router to transmit messages to and receivemessages from other sensors within its transmission range.The main constraint of sensor nodes, however, is their lowfinite battery energies, which limit the network lifetime andimpact on the quality of the network. Therefore, energyefficiency in the design of routing protocols for sensornetworks is of paramount importance.To prolong the network lifetime, many different energyoptimization metrics have been proposed [24]. One typicaloptimization objective in the design of routing protocols isto minimize the total energy consumption, while in manypractical applications, the performance measure of actualinterest is not only to optimize the overall energy con-sumption but also to maximize the lifetime of each node inthe network because a node failure in a network can causethe network partitioned and any further service will beinterrupted. To avoid the extinction of nodes due to theexhaustion of their batteries, energy efficient routingalgorithms should evenly distribute transmission energyload among the nodes, thereby prolonging the networklifetime. Thus, the network lifetime of a wireless sensornetwork is defined as the time of the first node failure in thenetwork [3].A sensor network can usually be treated as a database [8].In such a database, each sensor produces one or moretuples. The node that generates tuples is termed the source.A collection of similarly-typed tuples from a group ofsensors forms a ‘‘snapshot.’’ This snapshot constitutes arelational table which is horizontally partitioned across thesensors in the group. For example, the tuples generated by acollection of temperature sensors form a temperature table.A sensor network database allows any user to issue a datagathering query to the network and obtain a response to thequery as if it is a database system. There are two typicalforms of data gathering queries. One is the periodiccollection of information from the sensor nodes, where thequery result is updated periodically for a specified interval.Another is event-driven [19], [26], in which the occurrenceof an event (a specific data gathering query arrives) triggersa data gathering query. In this paper, we will focus onevent-driven data gathering queries.When a user poses a query at a base station (the sinknode) to the sensor network, the query is disseminatedacross the network. In response to the query, the systembuilds a routing tree rooted at the sink for it, each nodegenerates tuples that match the query, and the matchedtuples are transmitted toward the origin (the sink) of thequery. As the tuples are routed using the routing treeconsisting of all nodes, relay nodes in the tree might applyone or more database operators (e.g., aggregation opera-tors). We refer to this kind of query processing in sensor2 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 6, NO. 1, JANUARY 2007. The authors are with the Department of Computer Science, AustralianNational University, Canberra, ACT 0200, Australia.E-mail: {wliang, yliu}@cs.anu.edu.au.Manuscript received 10 Feb. 2005; revised 22 Nov. 2005; accepted 14 Mar.2006; published online 15 Nov. 2006.For information on obtaining reprints of this article, please send e-mail to:[email protected], and reference IEEECS Log Number TMC-0028-0205.1536-1233/07/$20.00 ß 2007 IEEE Published by the IEEE CS, CASS, ComSoc, IES, & SPSnetworks as the in-network processing. It has shown that in-network processing is fundamental to achieve energyefficiency in energy-constrained sensor networks [18],[20], [29].1.1 MotivationsIn the following, we use two examples to illustrate ourmotivations in this paper. The first one is a simple datagathering query. Consider the following SQL query on atemperature table consisting of temperature tuples stored ineach sensor during a certain time period:SELECT nodeidFROM sensorsWHERE 18  temperature  25DURATION 30sAssume that there are many nodes in the sensor networkwhose temperatures are within 18C to 25C. If a routing treeis built to evaluate the above data gathering query, then thevolume of the data transmitted by a