Teilprojekt C3
From GRK-Wiki
zum übergeordneten Forschungsbereich
Contents |
Datenbankzugriff für Sensornetze
Der Zugriff auf Messwerte in einem Szenario vieler, unzuverlässiger und räumlich verteilter Sensoren ist ein wichtiges Thema aktueller Forschung. Anfragen an ein Sensornetz betreffen beispielsweise die durchschnittliche Temperatur in einer bestimmten Region oder die Verteilung seismologischer Erschütterungen entlang einer bestimmten Bruchlinie. Die einfachste Möglichkeit, solche Anfragen zu beantworten, besteht in einer zentralistischen Anfrageausführung, d.h., ein zentraler Rechner lokalisiert alle relevanten Sensoren im Netz, schickt eine entsprechende Anfrage an diese Sensoren, sammelt die Daten ein, und berechnet die gewünschten Ergebnisse zentral aufgrund dieser Daten. Eine wesentlich komfortablere und elegantere Möglichkeit besteht darin, deklarative, SQL-artige Anfragen auf Sensornetzen zu ermöglichen. Dazu muss jeder Sensor mit einer Anfrageschnittstelle (logisch oberhalb der Netzschicht) ausgestattet werden. Eine Anfrage kann dann von einem beliebigen Knoten im Sensornetz aus formuliert werden; die Berechnung der Ergebnisse erfolgt aber dezentral im Netz selber. Dadurch wird Sensorlokalisierung mit Anfrageausführung verknüpft und man kann Zwischenberechnungen, beispielsweise Teilaggregationen, im Netz ausführen und dadurch Bandbreite sparen. Ein besonders aussichtsreicher Ansatz zur Optimierung von derartigen Anfragen ist der Einsatz von intelligenten Caching-Strategien.
Stand des Wissens
Deklarative Anfragesprachen für Sensornetze werden in unterschiedlichen Ansätzen in der Forschung bearbeitet. Ein Vorschlag für eine solche Sprache wird in [1] beschrieben. Kern der Sprache ist eine SQL-artige Syntax und ein Ausführungsmodell, das adaptiv auf Verzögerungen im Netz und ausfallende Knoten reagiert. Zusätzlich sind langlebige (Aggregation von realzeitlichen Sensordaten über Stunden oder Tage) und periodisch ausführbare Anfragen spezifizierbar. Der Vorschlag basiert auf dem reaktiven Routing-Protokoll AODV [2]. Den Umgang mit fehlenden oder verrauschten Daten im Netz untersucht [3], basierend auf Verfahren des Machine Learnings [4]. Hier werden Vorhersagen zur approximativen und damit Ressourcen sparenden Anfragebearbeitung eingesetzt, durch die das Netz entscheiden kann, wie viele Knoten zur Laufzeit noch besucht werden müssen, um die vom Benutzer gewünschte Genauigkeit im Ergebnis zu erreichen. Grundlagen zum semantischen Caching durch Techniken der Multiple Query Optimization werden zum Beispiel in [5], [6] beschrieben. Wesentlich für die Arbeiten dieses Vorhabens werden strombasierte Ansätze der Anfragebearbeitung sein. Hier wurden in [7] und [8] Ansätze zur Verarbeitung von Strömen aufgezeigt, die für das Verarbeiten von Sensordaten in der Anwendung einen idealen Startpunkt darstellen. Des Weiteren werden auch Ansätze des Publish/Subscribe (d. h. welche Daten werden von wem benötigt/gewünscht) Eingang in die Forschungsarbeiten finden.
Vorarbeiten der beteiligten Wissenschaftler
U. Leser forscht seit vielen Jahren im Bereich der Anfrageübersetzung und –optimierung in verteilten Informationssystemen [9], [10]. Schwerpunkt sind dabei Algorithmen, die auf der Erkennung und nur einmaligen Auswertung gleicher Anfrageteile durch Anfrage-Homomorphismen beruhen [11]. Derartige Algorithmen bilden die Grundlage sämtlicher semantischer Caching-Verfahren. J.- C. Freytags relevate Arbeiten für dieses Vorhaben sind zum einen in verschiedenen Bereichen der Anfragebearbeitung/–optimierung [12] und der aktiven Datenbanksysteme [13] sowie im P2P-Bereich [14] angesiedelt. Arbeiten zu Publish/Subscribe-Systemen in Kooperation mit der IBM werden ebenfalls in diesem Vorhaben zur Anwendung kommen (industrial co-operation, unpublished).
Geplante Arbeiten
Das Vorhaben untersucht Methoden, Anfragen in Sensornetzen durch den Einsatz von intelligenten Caching-Strategien sowohl schneller als auch fehlertoleranter zu machen. Anfragen können durch Caching ohne Traversierung des gesamten Netzes beantwortet werden. Besonders effektiv verspricht dieses Verfahren für die in Sensornetzen wichtigen Aggregationsanfragen zu sein, bei denen durch geschicktes Caching unter Umständen ganze Subnetze nicht mehr betreten werden müssen. Darüber hinaus ist Caching geeignet, ausfallende oder temporär nicht oder nur verzögert erreichbare Knoten eine Zeit lang durch approximierte Informationen zu ersetzen. Auch die Verfahren zur Bearbeitung von Strömen werden die Grundlage der Weiterentwicklung im beschriebenen Anwendungsszenario sein.
Referenzen
[1] Y. Yao, J. Gehrke: Query Processing for Sensor Networks. Conf. on Innovative Data Systems (CIDR03), Asilomar, California, 2003.
[2] C. Perkins: Ad hoc on demand distance vector (aodv) routing. Internet Draft, 1999.
[3] A. Deshpande, C. Guestrin, S. Madden, J. Hellerstein, W. Hong: Model-Driven Data Acquisition in Sensor Networks. Conf. on Very Large Databases (VLDB04), Toronto, Canada, 2004.
[4] T. Mitchell: Machine Learning, McGraw Hill, 1997.
[5] A. Chen, A. Dunham: Common Subexpression Processing in Multiple-Query Processing. IEEE Transactions on Knowledge and Data Engineering 10(3), pp. 493-499, 1998.
[6] M. Kang, H. Dietz, B. Bhargava: Multiple-Query Optimization at Algorithm-Level. Data and Knowledge Engineering 14(1), pp. 57-75, 1994.
[7] A. Arasu, B. Babcock, S. Babu, M. Datar, K. Ito, I. Nishizawa, J. Rosenstein, J. Widom: STREAM- The Stanford Stream Data Manager. SIGMOD Conference 2003, p. 665, 2003.
[8] R. Motwani, J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. Singh Manku, C. Olston, J. Rosenstein, R. Varma: Query Processing, Approximation, and Resource Management in a Data Stream Management System. CIDR, 2003.
[9] U. Leser: Combining Heterogeneous Data Sources through Query Correspondence Assertions. Workshop on Web Information and Data Management, in conjunction with CIKM'98, Washington, D. C. pp. 29-32, 1998.
[10] U. Leser: Maintenance and Mediation in Federated Databases. In: Proc. of 8th Workshop on Information Technology and Systems, Helsinki, Finland, TR-19, University of Jyvaeskylae. pp. 187 - 196, 1998.
[11] U. Leser: Query Planning in Mediator Based Information Systems. Technical University Berlin, 2000.
[12] J.- C. Freytag, D. Maier, G. Vossen: Query Processing for Advanced Database Systems. In: Selected Contributions from a Workshop on Query Processing in Object-Oriented, Complex-Object and Nested Relation Databases, Internationales Begegnungs- und Forschungszentrum für Informatik, Schloss Dagstuhl, June 1991 Morgan Kaufmann, 1994.
[13] U. Jaeger, J. C. Freytag: An Annotated Bibliography on Active Databases. SIGMOD Records Vol.24, No.1, March 1995.
[14] R. Heese, S. Herschel, F. Naumann, A. Roth: Self-Extending Peer Data Management, BTW 2005, Karlsruhe, 2005.
