TinyDB: an acquisitional query processing system for sensor networks

Abstract

We discuss the design of an acquisitional query processor for data collection in sensor networks. Acquisitional issues are those that pertain to where, when, and how often data is physically acquired (sampled) and delivered to query processing operators. By focusing on the locations and costs of acquiring data, we are able to significantly reduce power consumption over traditional passive systems that assume the a priori existence of data. We discuss simple extensions to SQL for controlling data acquisition, and show how acquisitional issues influence query optimization, dissemination, and execution. We evaluate these issues in the context of TinyDB, a distributed query processor for smart sensor devices, and show how acquisitional techniques can provide significant reductions in power consumption on our sensor devices.

References

1. Alonso, R. and Ganguly, S. 1993. Query optimization in mobile environments. In Proceedings of the Workshop on Foundations of Models and Languages for Data and Objects. 1--17.]]
2. Alonso, R. and Korth, H. F. 1993. Database system issues in nomadic computing. In Proceedings of the ACM SIGMOD (Washington, DC).]]
3. Avnur, R. and Hellerstein, J. M. 2000. Eddies: Continuously adaptive query processing. In Proceedings of ACM SIGMOD (Dallas, TX). 261--272.]]
4. Bancilhon, F., Briggs, T., Khoshafian, S., and Valduriez, P. 1987. FAD, a powerful and simple database language. In Proceedings of VLDB.]]
5. Bonnet, P., Gehrke, J., and Seshadri, P. 2001. Towards sensor database systems. In Proceedings of the Conference on Mobile Data Management.]]
6. Brooke, T. and Burrell, J. 2003. From ethnography to design in a vineyard. In Proceedings of the Design User Experiences (DUX) Conference. Case study.]]
7. Carney, D., Centiemel, U., Cherniak, M., Convey, C., Lee, S., Seidman, G., Stonebraker, M., Tatbul, N., and Zdonik, S. 2002. Monitoring streams---a new class of data management applications. In Proceedings of VLDB.]]
8. Cerpa, A., Elson, J., D. Estrin, Girod, L., Hamilton, M., and Zhao, J. 2001. Habitat monitoring: Application driver for wireless communications technology. In Proceedings of ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean.]]
9. Chakrabarti, K., Garofalakis, M., Rastogi, R., and Shim, K. 2001. Approximate query processing using wavelets. VLDB J. 10, 2-3 (Sep.), 199--223.]]
10. Chakravarthy, S., Krishnaprasad, V., Anwar, E., and Kim, S. K. 1994. Composite events for active databases: Semantics, contexts and detection. In Proceedings of VLDB.]]
11. Chandrasekaran, S., Cooper, O., Deshpande, A., Franklin, M. J., Hellerstein, J. M., Hong, W., Krishnamurthy, S., Madden, S. R., Raman, V., Reiss, F., and Shah, M. A. 2003. TelegraphCQ: Continuous dataflow processing for an uncertain world. In Proceedings of the First Annual Conference on Innovative Database Research (CIDR).]]
12. Chen, J., DeWitt, D., Tian, F., and Wang, Y. 2000. NiagaraCQ: A scalable continuous query system for internet databases. In Proceedings of ACM SIGMOD.]]
13. Chen, Z., Gehrke, J., and Korn, F. 2001. Query optimization in compressed database systems. In Proceedings of ACM SIGMOD.]]
14. Crespo, A. and Garcia-Molina, H. 2002. Routing indices for peer-to-peer systems. In Proceedings of ICDCS.]]
15. Delin, K. A. and Jackson, S. P. 2000. Sensor web for in situ exploration of gaseous biosignatures. In Proceedings of the IEEE Aerospace Conference.]]
16. Dewitt, D. J., Ghandeharizadeh, S., Schneider, D. A., Bricker, A., Hsiao, H. I., and Rasmussen, R. 1990. The gamma database machine project. IEEE Trans. Knowl. Data Eng. 2, 1, 44--62.]]
17. Ganeriwal, S., Kumar, R., Adlakha, S., and Srivastava, M. 2003. Timing-sync protocol for sensor networks. In Proceedings of ACM SenSys.]]
18. Garofalakis, M. and Gibbons, P. 2001. Approximate query processing: Taming the terabytes! (tutorial). In Proceedings of VLDB.]]
19. Gay, D., Levis, P., von Behren, R., Welsh, M., Brewer, E., and Culler, D. 2003. The nesC language: A holistic approach to network embedded systems. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation (PLDI).]]
20. Gehrke, J., Korn, F., and Srivastava, D. 2001. On computing correlated aggregates over continual data streams. In Proceedings of ACM SIGMOD Conference on Management of Data (Santa Barbara, CA).]]
21. Hanson, E. N. 1996. The design and implementation of the ariel active database rule system. IEEE Trans. Knowl. Data Eng. 8, 1 (Feb.), 157--172.]]
22. Hellerstein, J., Hong, W., Madden, S., and Stanek, K. 2003. Beyond average: Towards sophisticated sensing with queries. In Proceedings of the First Workshop on Information Processing in Sensor Networks (IPSN).]]
23. Hellerstein, J. M. 1998. Optimization techniques for queries with expensive methods. ACM Trans. Database Syst. 23, 2, 113--157.]]
24. Hellerstein, J. M., Franklin, M. J., Chandrasekaran, S., Deshpande, A., Hildrum, K., Madden, S., Raman, V., and Shah, M. 2000. Adaptive query processing: Technology in evolution. IEEE Data Eng. Bull. 23, 2, 7--18.]]
25. Hill, J., Szewczyk, R., Woo, A., Hollar, S., and Pister, D. C. K. 2000. System architecture directions for networked sensors. In Proceedings of ASPLOS.]]
26. Ibaraki, T. and Kameda, T. 1984. On the optimal nesting order for computing n-relational joins. ACM Trans. Database Syst. 9, 3, 482--502.]]
27. Imielinski, T. and Badrinath, B. 1992. Querying in highly mobile distributed environments. In Proceedings of VLDB (Vancouver, B.C., Canada).]]
28. Intanagonwiwat, C., Govindan, R., and Estrin, D. 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of MobiCOM (Boston, MA).]]
29. Intersema. 2002. MS5534A barometer module. Tech. rep. (Oct.). Go online to http://www.intersema.com/pro/module/file/da5534.pdf.]]
30. Ives, Z. G., Florescu, D., Friedman, M., Levy, A., and Weld, D. S. 1999. An adaptive query execution system for data integration. In Proceedings of ACM SIGMOD.]]
31. Kossman, D. 2000. The state of the art in distributed query processing. ACM Comput. Surv. 32, 4 (Dec.), 422--46.]]
32. Krishnamurthy, R., Boral, H., and Zaniolo, C. 1986. Optimization of nonrecursive queries. In Proceedings of VLDB. 128--137.]]
33. Leopold, M., Dydensborg, M., and Bonnet, P. 2003. Bluetooth and sensor networks: A reality check. In Proceedings of ACM Conference on Sensor Networks (SenSys).]]
34. Lin, C., Federspiel, C., and Auslander, D. 2002. Multi-sensor single actuator control of HVAC systems. In Proceedings of the International Conference for Enhanced Building Operations (Austin, TX, Oct. 14--18).]]
35. Liu, L., Pu, C., and Tang, W. 1999. Continual queries for internet-scale event-driven information delivery. IEEE Trans. Knowl. Data Eng. (special Issue on Web technology) 11, 4 (July), 610--628.]]
36. Madden, S. 2003. The design and evaluation of a query processing architecture for sensor networks. Ph.D. dissertation. University of California, Berkeley, Berkeley, CA.]]
37. Madden, S. and Franklin, M. J. 2002. Fjording the stream: An architechture for queries over streaming sensor data. In Proceedings of ICDE.]]
38. Madden, S., Franklin, M. J., Hellerstein, J. M., and Hong, W. 2002a. TAG: A Tiny AGgregation service for ad-hoc sensor networks. In Proceedings of OSDI.]]
39. Madden, S., Hong, W., Franklin, M., and Hellerstein, J. M. 2003. TinyDB Web page. Go online to http://telegraph.cs.berkeley.edu/tinydb.]]
40. Madden, S., Shah, M. A., Hellerstein, J. M., and Raman, V. 2002b. Continously adaptive continuous queries over data streams. In Proceedings of ACM SIGMOD (Madison, WI).]]
41. Mainwaring, A., Polastre, J., Szewczyk, R., and Culler, D. 2002. Wireless sensor networks for habitat monitoring. In Proceedings of ACM Workshop on Sensor Networks and Applications.]]
42. Melexis, Inc. 2002. MLX90601 infrared thermopile module. Tech. rep. (Aug.). Go online to http://www.melexis.com/prodfiles/mlx90601.pdf.]]
43. Monma, C. L. and Sidney, J. 1979. Sequencing with series parallel precedence constraints. Math. Operat. Rese. 4, 215--224.]]
44. Motwani, R., Widom, J., Arasu, A., Babcock, B., S.Babu, Data, M., Olston, C., Rosenstein, J., and Varma, R. 2003. Query processing, approximation and resource management in a data stream management system. In Proceedings of the First Annual Conference on Innovative Database Research (CIDR).]]
45. Olston, C. and Widom, J. 2002. In best effort cache sychronization with source cooperation. In Proceedings of SIGMOD.]]
46. Pirahesh, H., Hellerstein, J. M., and Hasan, W. 1992. Extensible/rule based query rewrite optimization in starburst. In Proceedings of ACM SIGMOD. 39--48.]]
47. Pottie, G. and Kaiser, W. 2000. Wireless integrated network sensors. Commun. ACM 43, 5 (May), 51--58.]]
48. Priyantha, N. B., Chakraborty, A., and Balakrishnan, H. 2000. The cricket location-support system. In Proceedings of MOBICOM.]]
49. Raman, V., Raman, B., and Hellerstein, J. M. 2002. Online dynamic reordering. VLDB J. 9, 3.]]
50. Sensirion. 2002. SHT11/15 relative humidity sensor. Tech. rep. (June). Go online to http://www.sensirion.com/en/pdf/Datasheet_SHT1x_SHT7x_0206.pdf.]]
51. Shatdal, A. and Naughton, J. 1995. Adaptive parallel aggregation algorithms. In Proceedings of ACM SIGMOD.]]
52. Stonebraker, M. and Kemnitz, G. 1991. The POSTGRES next-generation database management system. Commun. ACM 34, 10, 78--92.]]
53. Sudarshan, S. and Ramakrishnan, R. 1991. Aggregation and relevance in deductive databases. In Proceedings of VLDB. 501--511.]]
54. TAOS, Inc. 2002. TSL2550 ambient light sensor. Tech. rep. (Sep.). Go online to http://www.taosinc.com/images/product/document/tsl2550.pdf.]]
55. UC Berkeley. 2001. Smart buildings admit their faults. Web page. Lab notes: Research from the College of Engineering, UC Berkeley. Go online to http://coe.berkeley.edu/labnotes/1101.smartbuildings.html.]]
56. Urhan, T., Franklin, M. J., and Amsaleg, L. 1998. Cost-based query scrambling for initial delays. In Proceedings of ACM SIGMOD.]]
57. Wolfson, O., Sistla, A. P., Xu, B., Zhou, J., and Chamberlain, S. 1999. DOMINO: Databases fOr MovINg Objects tracking. In Proceedings of ACM SIGMOD (Philadelphia, PA).]]
58. Woo, A. and Culler, D. 2001. A transmission control scheme for media access in sensor networks. In Proceedings of ACM Mobicom.]]
59. Yao, Y. and Gehrke, J. 2002. The cougar approach to in-network query processing in sensor networks. In SIGMOD Rec. 13, 3 (Sept.), 9--18.]]

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

    • Sensors and actuators

• Information systems

  • Data management systems

    • Database management system engines

      • Database query processing

      • Parallel and distributed DBMSs

    • Query languages

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)