System design issues in sensor databases

ABSTRACT

In-network sensor query processing systems (ISQPs), or sensor databases, have been developed to acquire, process and aggregate data from wireless sensor networks (WSNs). Because WSNs are resource-limited and involve multiple layers of embedded software, the system design issues have a significant impact on the performance of sensor databases. Therefore, we propose this tutorial to study the state of the art on these issues with a focus on their interaction with query processing techniques. Our goal is to present the challenges and efforts in developing holistic, efficient ISQPs. Specifically, we will cover architectural design, scheduling, data-centric routing, and wireless medium access control. This tutorial is intended for database researchers who are interested in sensor networks.

REFERENCES

• 1: Kemal Akkaya and Mohamed Younis, "A Survey on Routing Protocols for Wireless Sensor Networks", Ad Hoc Networks, vol. 3, no. 3, pp. 325--349, May 2005.
• 2: Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci, "A Survey on Sensor Networks," IEEE Communications Magazine, vol. 40, no. 8, pp. 102--114, August 2002.
• 3: Jamal N. Al-Karaki and Ahmed E. Kamal, "Routing Techniques in Wireless Sensor Networks: A Survey," IEEE Wireless Communication, vol. 11, no.6, pp. 6--28, December 2004.
• 4: Shah Bhatti , James Carlson , Hui Dai , Jing Deng , Jeff Rose , Anmol Sheth , Brian Shucker , Charles Gruenwald , Adam Torgerson , Richard Han, MANTIS OS: an embedded multithreaded operating system for wireless micro sensor platforms, Mobile Networks and Applications, v.10 n.4, p.563-579, August 2005 [doi>10.1145/1160162.1160178]
• 5: Jeffrey Considine, Feifei Li, George Kollios, and John Byers. Approximate Aggregation Techniques for Sensor Databases. ICDE, 2006.
• 6: David Chu, Lucian Popa, Arsalan Tavakoli, Joseph M. Hellerstein, Philip Levis, Scott Shenker, Ion Stoica. The Design and Implementation of A Declarative Sensor Network System. Submitted for publication, Oct 2006.
• 7: Tijs van Dam and Koen Langendoen, "An adaptive energy-efficient MAC protocol for wireless sensor networks", SenSys 2003.
• 8: Amol Deshpande, Carlos Guestrin, Wei Hong, Samuel Madden, "Exploiting Correlated Attributes in Acquisitional Query Processing", ICDE 2005.
• 9: Adam Dunkels, Björn Grönvall, Thiemo Voigt, "Contiki-A Lightweight and Flexible Operating System for Tiny Networked Sensors. The 29th Annual IEEE Conference on Local Computer Networks, 2004.
• 10: Cédric Florens and Robert McEliece, "Packet Distribution Algorithms for Sensor Networks," INFOCOM, 2003.
• 11: Lin Gu, John A. Stankovic, "t-kernel: Providing Reliable OS Support for Wireless Sensor Networks," SenSys, 2006.
• 12: Chih-Chieh Han, Ram Kumar, Roy Shea, Eddie Kohler and Mani Srivastava, "A Dynamic Operating System for Sensor Nodes," International Conference on Mobile Systems, Applications, and Services, 2005.
• 13: Barbara Hohlt, Lance Doherty, and Eric Brewer, "Flexible Power Scheduling for Sensor Networks," IPSN, 2004.
• 14: Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin, "Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks," MobiCom, 2000.
• 15: Brad Karp and H. T. Kung, "Greedy Perimeter Stateless Routing for Wireless Networks," MobiCom 2000.
• 16: Yannis Kotidis, Snapshot Queries: Towards Data-Centric Sensor Networks, ICDE 2005.
• 17: Philip Levis and David Culler. "Maté: A Tiny Virtual Machine for Sensor Networks." In ASPLOS, 2002.
• 18: Huan Li , Prashant Shenoy , Krithi Ramamritham, Scheduling Messages with Deadlines in Multi-Hop Real-Time Sensor Networks, Proceedings of the 11th IEEE Real Time on Embedded Technology and Applications Symposium, p.415-425, March 07-10, 2005 [doi>10.1109/RTAS.2005.48]
• 19: Huan Li, Prashant J. Shenoy, Krithi Ramamritham, "Scheduling Communication in Real-Time Sensor Applications", IEEE Real-Time and Embedded Technology and Applications Symposium 2004: 10--18.
• 20: Qinglan Li, Jonathan Beaver, Ahmed Amer, Panos K. Chrysanthis, Alexandros Labrinidis, Ganesh Santhanakrishnan, Multi-Criteria Routing in Wireless Sensor-Based Pervasive Environments, Journal of Pervasive Computing and Communications (JPCC), 1(4): 313--326, December 2005.
• 21: Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong, "TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks," OSDI, 2002.
• 22: Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong, "The Design of an Acquisitional Query Processor for Sensor Networks," SIGMOD, 2003.
• 23: Amit Manjhi, Suman Nath, Phillip B. Gibbons, Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams, SIGMOD, 2005.
• 24: René Müller, Gustavo Alonso: Efficient Sharing of Sensor Networks. IEEE International Conference on Mobile Ad-hoc and Sensor Systems, Vancouver, Canada, October 9--12, 2006.
• 25: Rene Muller, Gustavo Alonso, and Donald Kossman, "SwissQM: Next Generation Data Processing in Sensor Networks", CIDR 2007.
• 26: C. Perkins, E. Belding-Royer, and S. Das, "Ad hoc On-demand Distance Vector (AODV) Routing," RFC 3561, July 2003.
• 27: Curt Schurgers, Vlasios Tsiatsis, Saurabh Ganeriwal, and Mani Srivastava, "Connecting the physical world with pervasive networks", IEEE Transactions on Mobile Computing, vol. 1, no. 1, January 2002.
• 28: Mihail L. Sichitiu, "Cross-Layer Scheduling for Power Efficiency in Wireless Sensor Networks," INFOCOM, 2004.
• 29: A. Sharaf , Jonathan Beaver , Alexandros Labrinidis , K. Chrysanthis, Balancing energy efficiency and quality of aggregate data in sensor networks, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.384-403, December 2004 [doi>10.1007/s00778-004-0138-0]
• 30: Adam Silberstein, Kamesh Munagala, Jun Yang, "Energy-efficient monitoring of extreme values in sensor networks", SIGMOD, 2006.
• 31: Adam Silberstein, Rebecca Braynard, Jun Yang, "Constraint chaining: on energy-efficient continuous monitoring in sensor networks", SIGMOD, 2006.
• 32: Adam Silberstein and Jun Yang. "Multiple Aggregation for In-Network Control of Sensors." ICDE, April 2007.
• 33: Ping Su, "Delay Measurement Time Synchronization for Wireless Sensor Networks", IRB-TR-03-013, Intel Research Berkeley Lab, 2003.
• 34: Sun SPOT Project, http://www.sunspotworld.com/.
• 35: TinyAODV. http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/tinyos/tinyos--1.x/contrib/hsn
• 36: TinyDB, http://telegraph.cs.berkeley.edu/tinydb/.
• 37: TinyOS, http://www.tinyos.net/.
• 38: Niki Trigoni, Yong Yao, Alan Demers, Johannes Gehrke, and Rajmohan Rajaraman. "WaveScheduling: Energy-Efficient Data Dissemination for Sensor Networks". The First International Workshop on Data Management for Sensor Networks (DMSN), August 2004.
• 39: Alec Woo and David Culler, "A Transmission Control Scheme for Media Access in Sensor Networks", MobiCom, 2001.
• 40: Alec Woo, Ternence Tony, and David Culler, "Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks," SenSys, 2003.
• 41: Hejun Wu, Qiong Luo, and Wenwei Xue, "Distributed Cross-Layer Scheduling for In-Network Sensor Query Processing," PerCom, 2006.
• 42: Wenwei Xue, Qiong Luo, Lei Chen, and Yunhao Liu, "Contour Map Matching for Event Detection in Sensor Networks", SIGMOD, 2006.
• 43: Yong Yao and Johannes Gehrke, "Query Processing for Sensor Networks," CIDR, 2003.
• 44: Yong Yao, S. M. Nazrul Alam, Johannes Gehrke, and Sergio D. Servetto. "Network Scheduling for Data Archiving Applications in Sensor Networks". DMSN, 2006.
• 45: Wei Ye, John Heidemann, and Deborah Estrin, "An Energy-Efficient MAC Protocol for Wireless Sensor Networks", INFOCOM, 2002.
• 46: Le Zou, Mi Lu, and Zixiang Xiong, "PAGER-M: A Novel Location-based Routing Protocol for Mobile Sensor Networks," First International Workshop on Broadband Wireless Services and Applications (BroadWISE), 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing; Distributed databases

General Terms:
Algorithms, Design, Experimentation, Management, Performance

Keywords:
data-centric routing, in-network query processing, scheduling, sensor networks, wireless medium access control