Suman Nath
Phillip B. Gibbons
Zachary R. Anderson
ABSTRACT
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.
- N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. J. of Computer and System Sciences, 58:137--147, 1999. Google Scholar
Digital Library
- Atmel AVR Microcontroller Datasheet. http://www.atmel.com/dyn/resources/prod documents/2467s.pdf.Google Scholar
- B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. In ACM PODS, 2002. Google ScholarDigital Library
- Z. Bar-Yossef, R. Kumar, and D. Sivakumar. Sampling algorithms: lower bounds and applications. In ACM STOC, 2001. Google ScholarDigital Library
- M. Bawa, A. Gionis, H. Garcia-Molina, and R. Motwani. The price of validity in dynamic networks. In ACM SIGMOD, 2004. Google ScholarDigital Library
- J. Considine, F. Li, G. Kollios, and J. Byers. Approximate aggregation techniques for sensor databases. In IEEE ICDE, 2004. Google ScholarDigital Library
- B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge University Press, 2002.Google ScholarCross Ref
- P. Flajolet and G. N. Martin. Probabilistic counting algorithms for database applications. Journal of Computer and System Sciences, 31:182--209, 1985. Google ScholarDigital Library
- D. Ganesan, R. Govindan, S. Shenker, and D. Estrin. Highly-resilient, energy-e.cient multipath routing in wireless sensor networks. Mobile Computing and Communications Review (M2CR), 1(2), 2002. Google ScholarDigital Library
- P. B. Gibbons and Y. Matias. Synopsis data structures for massive data sets. DIMACS: Series in Discrete Math. and Theoretical Computer Science: Special Issue on External Memory Algorithms and Visualization, 1999. Google ScholarDigital Library
- P. B. Gibbons and S. Tirthapura. Estimating simple functions on the union of data streams. In ACM SPAA, 2001. Google ScholarDigital Library
- P. B. Gibbons and S. Tirthapura. Distributed streams algorithms for sliding windows. In ACM SPAA, 2002. Google ScholarDigital Library
- J. Gray, A. Bosworth, A. Layman, and H. Pirahesh. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals. In IEEE ICDE, 1996. Google ScholarDigital Library
- I. Gupta, R. van Renesse, and K. Birman. Scalable fault-tolerant aggregation in large process groups. In IEEE Dependable Systems and Networks, 2001. Google ScholarDigital Library
- C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In ACM MobiCom, 2000. Google ScholarDigital Library
- D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.Google ScholarCross Ref
- D. Kostic, A. Rodriguez, J. R. Albrecht, A. Bhirud, and A. Vahdat. Using random subsets to build scalable network services. In USITS. USENIX, 2003. Google ScholarDigital Library
- P. Levis, N. Lee, M. Welsh, and D. Culler. TOSSIM: Accurate and scalable simulation of entire TinyOS applications. In ACM SenSys, 2003. Google ScholarDigital Library
- S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. Tag: A tiny aggregation service for ad hoc sensor networks. In USENIX OSDI, 2002. Google ScholarDigital Library
- S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. The design of an acquisitional query processor for sensor networks. In ACM SIGMOD, 2003. Google ScholarDigital Library
- S. Madden, R. Szewczyk, M. J. Franklin, and D. Culler. Supporting aggregate queries over ad-hoc wireless sensor networks. In IEEE WMCSA, 2002. Google ScholarDigital Library
- S. Muthukrishnan. Data streams: Algorithms and applications. Technical report, Rutgers University, Piscataway, NJ, 2003.Google Scholar
- S. Nath, P. B. Gibbons, S. Seshan, and Z. Anderson. Synopsis di.usion for robust aggregation in sensor networks. Technical Report IRP-TR-04-13, Intel Research Pittsburgh, PA, April 2004.Google Scholar
- C. R. Palmer, P. B. Gibbons, and C. Faloutsos. ANF: A fast and scalable tool for data mining in massive graphs. In ACM KDD, 2002. Google ScholarDigital Library
- B. Przydatek, D. Song, and A. Perrig. SIA: Secure information aggregation in sensor networks. In ACM SenSys, 2003. Google ScholarDigital Library
- Y. Tao, G. Kollios, J. Considine, F. Li, and D. Papadias. Spatio-temporal aggegration using sketches. In IEEE ICDE, 2004. Google ScholarDigital Library
- Y. Yao and J. Gehrke. Query processing in sensor networks. In CIDR, 2003.Google Scholar
- J. Zhao and R. Govindan. Understanding packet delivery performance in dense wireless sensor networks. In ACM SenSys, 2003. Google ScholarDigital Library
Index Terms
- Synopsis diffusion for robust aggregation in sensor networks
Recommendations
Synopsis diffusion for robust aggregation in sensor networks
Previous approaches for computing duplicate-sensitive aggregates in wireless sensor networks 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 ...
Attack-resilient hierarchical data aggregation in sensor networks
SASN '06: Proceedings of the fourth ACM workshop on Security of ad hoc and sensor networksIn a large sensor network, in-network data aggregation, i.e., combining partial results at intermediate nodes during message routing, significantly reduces the amount of communication and hence the energy consumed. Recently several researchers have ...
SIA: Secure information aggregation in sensor networks
Special Issue on Security of Ad-hoc and Sensor NetworksIn sensor networks, data aggregation is a vital primitive enabling efficient data queries. An on-site aggregator device collects data from sensor nodes and produces a condensed summary which is forwarded to the off-site querier, thus reducing the ...
Comments