Latency Constrained Aggregation in Sensor Networks

Summary form only given. A sensor network is a network of sensor nodes which may exchange data through wireless communication. A particular feature of sensor networks is that they are highly energy constrained due to their use of batteries. We investigate data aggregation as a possible way to save energy consumption: nodes may delay data in order to aggregate them into a single packet before forwarding them towards some central node (or nodes). Latency constraints restrict the delay allowed for data arriving at the central node. These two ingredients, data aggregation and latency constraints, give rise to a large variety of optimization problems depending on how transmission energy and time are related to size of packets sent and transmission distance, how transmission paths are chosen, if latency is data or node dependent or not, if we work off- or on-line, in a centralized setting or in a distributed setting, etc. In this paper we investigate a first, basic data aggregation problem in which transmission energy and -time depend only on the pair of nodes involved in the transmission, and not on packet size. We assume unique transmission paths that form a tree rooted into the central node. The objective we have chosen is to minimize the maximum energy consumption over all nodes. Already this simple model gives rise to interesting and challenging algorithmic problems. We prove that the off-line version of the sensor problem is strongly NP-hard and we design a 2-approximation algorithm. Almost all real life sensor networks are managed in an on-line fashion by simple distributed algorithms in the nodes. We consider distributed on-line models both if the nodes are synchronized and non-synchronized and we apply competitive analysis into the quality of algorithms for them