Synopsis Diffusion addresses the problem of robustly computing aggregates (e.g., the average temperature reported by the sensors) in a wireless sensor network. Traditional approaches for computing aggregates use in-network aggregation over a spanning tree rooted at the base station. However, a tree, being fragile against node- and communication-failures, gives inaccurate answers in practice. For example, under a message loss rate (20-30%) typical in real sensor deployments, the inaccuracy can be as high as 75%. One way to make the routing robust is to employ redundancy, by using multi-path routing for example. However, using such redundancy with traditional in-network aggregation approaches would introduce double-counting because sensor readings and partial results would be sent along multiple paths. This concern with double-counting led the researchers to stick with the tree topology despite its inaccuracies. In other words, in traditional in-network aggregation approaches, routing is dictated by the requirements of the in-network aggregation techniques.

Synopsis Diffusion decouples aggregation and routing so that these can be optimized independently. Synopsis Diffusion achieves topology-independence through the use of order- and duplicate-insensitive (ODI) synopses. ODI synopses,  a special class of synopses used in traditional data-streams research, eliminate double-counting and summarize the intermediate results during in-network aggregation. This enables the use of a robust aggregation topology. I have shown that Synopsis Diffusion can make the aggregation process significantly more robust against typical node- and communication-failures than traditional approaches, without additional energy overheads. For example, under a typical message loss rate, Synopsis Diffusion can improve the accuracy of aggregation by around 85%.

Apart from this basic framework, we have also provided i) novel synopsis diffusion algorithms for (approximately) computing a number of useful aggregates, (ii) surprisingly simple methods to check the correctness and the approximation errors of any Synopsis Diffusion algorithm., and iii) techniques to exploit a unique property of Synopsis Diffusion as an  implicit acknowledgement of message delivery.

As an extension to this work, we have proposed, formalized, and provided algorithms to construct the Tributary-Delta aggregation scheme, a novel approach that combines the advantages of Synopsis Diffusion and traditional tree-based approaches by running them simultaneously in different parts of the network.

Publications:

• Synopsis Diffusion for Robust Aggregation in Sensor Networks [ps][pdf]
  Suman Nath, Phillip B. Gibbons, Srinivasan Seshan, and Zachary Anderson
  ACM SenSys 2004.
• Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams. [ps][pdf]
  Amit Manjhi, Suman Nath, and Phillip B. Gibbons
  ACM SIGMOD 2005.