Data aggregation in sensor networks: Balancing communication and delay costs

In a sensor network the sensors, or nodes, obtain data and have to communicate these data to a central node. Because sensors are battery powered they are highly energy constrained. Data aggregation can be used to combine data of several sensors into a single message, thus reducing sensor Communication costs at the expense of message delays. Thus, the main problem of data aggregation is to balance the communication and delay costs. In this paper we study the data aggregation problem as a bicriteria optimization problem; the objectives we consider are to minimize maximum energy consumption of a sensor and a function of the maximum latency costs of a message. We consider distributed algorithms under a synchronous time model, under an asynchronous time model, and under an almost synchronous time model, where sensor clocks are synchronized up to a small drift. We use competitive analysis to assess the quality of the algorithms. (C) 2008 Elsevier B.V. All rights reserved.