A substrate for in-network sensor data integration

ABSTRACT

With the ultimate goal of extending the data integration paradigm and query processing capabilities to ad hoc wireless networks, sensors, and stream systems, we consider how to support communication between sets of nodes performing distributed joins in sensor networks. We develop a communication model that enables in-network join at a variety of locations, and which facilitates coordination among nodes in order to make optimization decisions. While we defer a discussion of the optimizer to future work, we experimentally compare a variety of strategies, including at-base and in-network joins. Results show significant performance gains versus prior work, as well as opportunities for optimization.

REFERENCES

• 1: Daniel J. Abadi , Samuel Madden , Wolfgang Lindner, REED: robust, efficient filtering and event detection in sensor networks, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 2: Paul M. Aoki, Generalizing "Search'' in Generalized Search Trees (Extended Abstract), Proceedings of the Fourteenth International Conference on Data Engineering, p.380-389, February 23-27, 1998
• 3: Arvind Arasu , Shivnath Babu , Jennifer Widom, The CQL continuous query language: semantic foundations and query execution, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.121-142, June 2006 [doi>10.1007/s00778-004-0147-z]
• 4: B. Bonfils and P. Bonnet. Adaptive and decentralized operator placement for in-network query processing. In IPSN, 2003.
• 5: Miguel Castro , Peter Druschel , Anne-Marie Kermarrec , Animesh Nandi , Antony Rowstron , Atul Singh, SplitStream: high-bandwidth multicast in cooperative environments, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 6: V. Chowdhary and H. Gupta. Communication-efficient implementation of join in sensor networks. In DASFAA, 2005.
• 7: Alan Demers , Johannes Gehrke , Rajmohan Rajaraman , Niki Trigoni , Yong Yao, The Cougar Project: a work-in-progress report, ACM SIGMOD Record, v.32 n.4, December 2003 [doi>10.1145/959060.959070]
• 8: T. M. Gil and S. Madden. Scoop: An adaptive indexing scheme for stored data in sensor networks. In ICDE, pages 1345--1349, 2007.
• 9: Moustafa A. Hammad , Walid G. Aref , Ahmed K. Elmagarmid, Stream window join: tracking moving objects in sensor-network databases, Proceedings of the 15th international conference on Scientific and statistical database management, p.75-84, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214967]
• 10: Philip Levis , Nelson Lee , Matt Welsh , David Culler, TOSSIM: accurate and scalable simulation of entire TinyOS applications, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958506]
• 11: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 12: Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031525]
• 13: Sylvia Ratnasamy , Brad Karp , Scott Shenker , Deborah Estrin , Ramesh Govindan , Li Yin , Fang Yu, Data-centric storage in sensornets with GHT, a geographic hash table, Mobile Networks and Applications, v.8 n.4, p.427-442, August 2003 [doi>10.1023/A:1024591915518]
• 14: Xiaoyan Yang , Hock Beng Lim , Tamer M. Özsu , Kian Lee Tan, In-network execution of monitoring queries in sensor networks, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247538]
• 15: Hai Yu , Ee-Peng Lim , Jun Zhang, On In-network Synopsis Join Processing for Sensor Networks, Proceedings of the 7th International Conference on Mobile Data Management, p.32, May 10-12, 2006 [doi>10.1109/MDM.2006.113]
• 16: D. Zeinalipour-Yazti , Z. Vagena , D. Gunopulos , V. Kalogeraki , V. Tsotras , M. Vlachos , N. Koudas , D. Srivastava, The threshold join algorithm for top-k queries in distributed sensor networks, Proceedings of the 2nd international workshop on Data management for sensor networks, August 30-30, 2005, Trondheim, Norway [doi>10.1145/1080885.1080896]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Keywords:
joins, routing, sensor networks