Synopsis diffusion for robust aggregation in sensor networks

By Suman Nath, Phillip B. Gibbons, Srinivasan Seshan, Zachary R. Anderson. 2004

707 citations recorded by the source corpus.

Previous approaches for computing duplicate-sensitive aggregates in sensor networks (<i>e.g.</i>, in TAG) have used a tree topology, in order to conserve energy and to avoid double-counting sensor readings. However, a tree topology is not robust against node and communication failures, which are common in sensor networks. In this paper, we present <i>synopsis diffusion</i>, a general framework for achieving signi.cantly more accurate and reliable answers by combining energy-efficient multi-path routing schemes with techniques that avoid double-counting. Synopsis diffusion avoids double-counting through the use of <i>order- and duplicate-insensitive (ODI) synopses</i> that compactly summarize intermediate results during in-network aggregation. We provide a surprisingly simple test that makes it easy to check the correctness of an ODI synopsis. We show that the properties of ODI synopses and synopsis di.usion create <i>implicit</i> acknowledgments of packet delivery. We show that this property can, in turn, enable the system to adapt message routing to dynamic message loss conditions, even in the presence of asymmetric links. Finally, we illustrate, using extensive simulations, the significant robustness, accuracy, and energy-efficiency improvements of synopsis diffusion over previous approaches.

Subfields: Computer Networks and Communications

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

1. Samuel Madden
2. David E. Culler
3. Scott Shenker
4. Ion Stoica
5. Sencun Zhu
6. Adrian Perrig
7. W. Hong
8. P. Levis

Citations in the corpus

• Over-the-air Function Computation in Sensor Networks (2016, background): “(a) Aggregated Wireless Sensor Networks : Most data aggregation work can be classified as: tree-based [17, 26, 16, 13], cluster-based [12, 27, 30, 18] or multipath [20, 19, 7].”
• Secure hierarchical in-network aggregation in sensor networks (2006, background): “The energy savings of performing in-network aggregation have been shown to be signi.cant and are crucial for energy-constrained sensor net­works [9, 11, 20].”
• A unifying link abstraction for wireless sensor networks (2005, background): “It has been suggested [3] that, in prin­ ciple, wireless sensor networks would bene.t from a unifying ab­straction (or narrow waist in architectural terms), and that this abstraction should be closer to the link level than the network level.”
• Wireless sensor network survey (2008, background): “Synopsis diffusion: Synopsis diffusion [80] provides a framework for in-network aggregation and best-effort multi-path routing.”
• SDAP: a secure hop-by-Hop data aggregation protocol for sensor networks (2006, methodology): “[2006] augmented the normal data aggregation framework such as synopsis diffusion [Nath et al. 2004] with a set of countermeasures against values falsified by compromised nodes.”
• Opportunistic Flooding in Low-Duty-Cycle Wireless Sensor Networks with Unreliable Links (2009, background): “Yet this type of solution has been shown [16, 29] to be very fragile, since the failure of a parent”
• Approximate Data Collection in Sensor Networks using Probabilistic Models (2006, background): “One way to significantly reduce communication cost in sensor networks is to perform in-network aggregation (e.g., AVG and MIN) [19] [11] or data reduction via wavelets or distributed regression [22] [12].”
• Resource Management in Fog/Edge Computing (2018, methodology): “However, Synopsis Diffusion (SD) is a technique proposed for decoupling routing from aggregation so they can be individually optimized to improve accuracy [128].”
• Approximate aggregation techniques for sensor databases (2004, methodology): “In parallel with our work, the sketches of [1] were adapted to summations in [17], but their methods involve both logarithms and exponentiation, making them unsuitable for sensor networks.”
• Model-based approximate querying in sensor networks (2005, background): “[44] have shown that sketch-based approximation techniques can be applied in sensor networks.”