Medians and beyond: new aggregation techniques for sensor networks

By Nisheeth Shrivastava, Chiranjeeb Buragohain, D. Agrawal, Subhash Suri. ACM International Conference on Embedded Networked Sensor Systems, 2004

580 citations recorded by the source corpus.

Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensors, however, have significant power constraint (battery life), making communication very expensive. Another important issue in the context of sensor-based information systems is that individual sensor readings are inherently unreliable. In order to address these two aspects, sensor database systems like TinyDB and Cougar enable in-network data aggregation to reduce the communication cost and improve reliability. The existing data aggregation techniques, however, are limited to relatively simple types of queries such as SUM, COUNT, AVG, and MIN/MAX. In this paper we propose a data aggregation scheme that significantly extends the class of queries that can be answered using sensor networks. These queries include (approximate) quantiles, such as the median, the most frequent data values, such as the <i>consensus</i> value, a histogram of the data distribution, as well as range queries. In our scheme, each sensor aggregates the data it has received from other sensors into a fixed (user specified) size message. We provide strict theoretical guarantees on the approximation quality of the queries in terms of the message size. We evaluate the performance of our aggregation scheme by simulation and demonstrate its accuracy, scalability and low resource utilization for highly variable input data sets.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Water Science and Technology

View Paper: https://www.semanticscholar.org/paper/8730bab60ed824e6fc547e055fcf81970b02d47a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Water Science and Technology

Citations in the corpus

Online outlier detection in sensor data using non-parametric models (2006, background): “Another recent study [41] addresses the problem of approximating the data distribution for computing order statistics, as well as range queries.”
Computing Extremely Accurate Quantiles Using t-Digests (2019, methodology): “To force the digests to be equal in size compression parameter values of δ q = 20 for Q-digest and δ t = 200 for t -digest were chosen.”
Wireless Sensor Network Security: A Survey (2006, background): “However, they prove strict guarantees on the approximation quality of the queries [70].”
Wireless sensor network survey (2008, background): “The confidence factor ensures that error in any query is bounded, else it is discarded. q-Digest supports a variety of queries such as average query, median query, and histogram query.”
Security in Wireless Sensor Networks (2008, unknown): “Snekkenes (2001) presents advanced concepts for policy specification on cell phone networks.”
Continual Learning in Practice (2019, methodology): “The t-digest construction algorithm uses a variant of 1-dimensional k-means clustering to produce a data structure that is related to the Q-digest [21], except that the t-digest can handle ﬂoating point values while the Q-digest is limited to integers.”
Driver Behavior Profiling Using Smartphones: A Low-Cost Platform for Driver Monitoring (2015, methodology): “To do this, Q-Digest [26] would be used to compute a fast quantile approximation.”
A Fast Algorithm for Approximate Quantiles in High Speed Data Streams (2007, background): “In Section 4, we demonstrate our implementation results.”
Data streams: algorithms and applications (2005, background): “Take any point in the stream as the center and draw sectors centered on that point of appropriate angular width.”
Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams (2009, background): “Quantile estimation is perhaps the most extensively studied problem in the data-stream model [3,4,9,10,15,19,20,23].”
Funneling-MAC: a localized, sink-oriented MAC for boosting fidelity in sensor networks (2006, background): “Researchers have proposed distributed congestion control algorithms [15], tiered network design [7], and data aggregation techniques [16] [17] to respond to increased load and congestion in sensor networks.”
Swarm intelligence based routing protocol for wireless sensor networks: Survey and future directions (2011, background): “It addresses the study of the collective behaviors of systems made by many components that coordinate using decentralized controls and self-organization.”
A Survey on Wireless Sensor Network Security (2009, background): “A number of secure and efficient routing protocols [28, 50, 49, 69], secure data aggregation protocols [21, 30, 52, 77, 64, 83] etc.”