Entwurf und Evaluation eines Ansatzes zur approximativen Ereignisverarbeitung auf Sensordatenströmen

BearbeiterIn:Christoffer Löffler
Titel:Entwurf und Evaluation eines Ansatzes zur approximativen Ereignisverarbeitung auf Sensordatenströmen
Typ:masters thesis
Betreuer:Mutschler, C.; Philippsen, M.
Status:abgeschlossen am 1. Dezember 2014
Vorausetzungen:

Programmierkenntnisse in C/C++
Ereignisbasierte Systeme/Programmierung

Thema:

Thema

Die Gruppe „Sensorfusion und Ereignisverarbeitung" am Fraunhofer Institut für Integrierte Schaltungen in Nürnberg arbeitet an der Generierung und Verarbeitung von Positionsdatenströmen in Echtzeit. Basierend auf diesen Positionsdaten können zur Laufzeit Ereignisse detektiert werden. Aufgrund der hohen Datenrate von Lokalisierungssystemen sowie der hohen Anzahl an parallelen Datenströmen entstehen hohe Anforderungen an die Effizienz und Skalierbarkeit von Systemen zur Ereignisverarbeitung. Zur Verarbeitung dieser Daten wurde in Kooperation mit dem Lehrstuhl für Programmiersysteme ein verteiltes System entwickelt, um Ereignisse und Abläufe zur Laufzeit detektieren zu können.
Die Effizienz des Systems liegt teilweise in dem Determinismus der Berechnung von Ereignissen begründet. Derartige Systeme können wegen der Eindeutigkeit der Ergebnisse oft nicht mit unsicheren Entscheidungen umgehen, da diese dem Determinismus widersprechen. Eine unsichere Datengrundlage auf Grund von Messunsicherheit der verwendeten Sensoren, oder auch uneindeutige Situationen auf Anwendungsebene können Ursachen falscher Ereignisberechnungen sein.
Zur Veranschaulichung soll ein Beispiel dienen. Es sei ein Fußballspieler im Ballbesitz, der für seine Dribbling-Künste bekannt ist. Er wird von einem Gegenspieler angegriffen. Bei dem folgenden Zweikampf tunnelt der Spieler den Angreifenden und passt so zu einem Mannschaftsmitglied. Das deterministische System erkennt einen Fehlpass, denn dem Verteidiger wird kurzzeitig, während des Passes durch dessen Beine, der Ballbesitz zugesprochen. Das deterministische System würde zur Konsistenzwahrung bei der Erkennung der Ereignisse nur eine Möglichkeit erkennen und alle anderen somit verwerfen.
Ein probabilistisches System aber würde eine Menge an möglichen Wirklichkeiten beobachten und basierend auf Sensorgenauigkeit und Regeln Wahrscheinlichkeiten zuordnen. Jede Wirklichkeit kann einfachen Ereignissen oder auch komplexen Hierarchien von aufeinander aufbauenden Ereignissen entsprechen. So ist bspw. ein „Doppelpass" eine Komposition aus zwei „Pass"-Ereignissen.
Die Zuverlässigkeit der Ereigniserkennung lässt sich durch die Berücksichtigung von Unsicherheitsfaktoren ver-bessern. Durch die Beachtung von vordefinierten Regeln lässt sich die Anwendungsentwicklung für den Domänenexperten vereinfachen und die Konsistenz des Systems wahren. Ziel der Arbeit ist es, sich in das vorhandene System zur Ereignisverarbeitung einzuarbeiten und veröffentlichte Verfahren zum Umgang mit Unsicherheit in der komplexen Ereignisverarbeitung zu sichten. Auf dieser Basis soll das bestehende System um skalierbare bzw. ressourcenbewusste, korrekte Ereignisverarbeitung erweitert werden, sodass Fehler auf Grund unsicherer Daten minimiert werden.
Eine Komponente zur Darstellung von Unsicherheiten und zur Definition von Erkennungsregeln soll erarbeitet werden. Diese soll die Integration von Unsicherheiten in die Ereignisberechnung für Anwendungsentwickler erlauben, und ihnen die Möglichkeit geben, alternative Berechnungspfade zu definieren um auch alternative Wirklichkeiten probabilistisch zu erfassen. Denkbare Ansätze sind der probabilistische Event Calculus nach Skarlatidis et. al. oder die von Wasserkrug et. al. vorgestellten Formalismen für regelbasierte Systeme. Die nötigen Mechanismen zur Konfliktauflösung zwischen inkonsistenten Berechnungspfaden sollen ebenfalls bereitgestellt werden. Das vorhandene System soll auf Basis dieser Komponente um die Fähigkeit der Darstellung, Berechnung und abschließenden Auswahl von alternativen, isolierten Berechnungspfaden ergänzt werden. Die von Anwendungsentwicklern oder Domänenexperten definierten Regeln sollen hierbei als Argumentationsgrundlage der probabilistischen Erweiterung dienen, und die Unsicherheiten der Sensordaten und Ereignisberechnungen quantifizieren. Als technische Beispiele verwandter Arbeiten zur Modellierung und Bewertung möglicher Wirklichkeiten dienen die von Skarlatidis et al. angewandten Markov Logic Networks und der Einsatz von bayesschen Netzen und Monte-Carlo Sampling durch Wasserkrug et. al.
Weiterführende technische Beispiele probabilistischer Ereignisberechnung sind der Einsatz von kontinuierlichen Zufallsvariablen durch Tran et. al. zur weiteren Optimierung solcher Systeme und auch die von Cao. et. al. verwendete Evidenztheorie von Dempster und Shafer zur Vereinigung vieler unsicherer Datenströme.

Meilensteine:

  • Recherche zum Thema Ereignisverarbeitung und probabilistische Systeme.
  • Einarbeitung in die bestehenden Systeme am Fraunhofer IIS
  • Implementierung der benötigten Komponenten zur Abbildung der Unsicherheiten
  • Implementierung der Erweiterung für probabilistische Ereignisberechnung
  • Evaluation des Verfahrens mit Hilfe des realen Systems
  • Ausarbeitung der Ergebnisse

Literatur

  • Etzion, O; Niblett, P; Event Processing in Action. Manning. 2010.
  • Wasserkrug, S; Gal, A; Etzion, O; Turchin, Y. Complex Event Processing over Uncertain Data. Proceedings of the 2nd International Conference on Distributed Event-Based Systems (Rome, Italy). 2008, pp. 253-264.
  • Wasserkrug, S; Gal, A; Etzion, O; A Model for Reasoning with Uncertain Rules in Event Composition Systems. Proceedings of the 21st Annual Conference on Uncertainty in Artificial Intelligence (Edinburgh, Scotland, UK), 2005, pp. 599-606.
  • Skarlatidis, A; Paliouras, G; Vouros, G. A; Artikis, A; Probabilistic Event Calculus based on Markov Logic Networks. RuleML America (Ft. Lauderdale, FL, Florida), 2011, pp. 155-170.
  • Tran, T T L; Peng, L; Li, B; Diao, Y; Liu, A. PODS: A new model and processing algorithms for uncertain data streams. ACM SIGMOD International Conference on Management of Data (Indianapolis, Indiana), 2010, pp. 159-170.
  • Ge, T; Liu, F; Accuracy-Aware Uncertain Stream Databases. Proceedings of the 8th International Conference on Data Engineering (Washington, DC), 2012, 174-185.
  • Olteanu, D; Huang, J; Koch, C; Approximate Confidence Computation in Probabilistic Databases, Proceedings of the 26th International Conference on Data Engineering (Long Beach, California,), 2010, 145-156.
  • Li, R-H; Yu, J X; Mao, R; and Jin, T; Efficient and Accurate Query Evaluation on Uncertain Graphs via Recursive Stratified Sampling, Technical Report
  • Cao, B; and Li, J; An Intelligent Complex Event Processing with D-S Evidence Theory in IT Centralized Monitoring. Proceedings of the 6th International Conference on Internet and Distributed Computing Systems (Hangzhou, China), 2013, pp. 373-384.
  • Meiser, T; Dylla, M; Theobald, M; Interactive reasoning in uncertain RDF knowledge bases. Proceedings of the 20th International Conference on Information and Knowledge Management (Glasgow, Scotland, UK), 2011, pp. 2557-2560.
  • Sadri, F.; On the Foundations of Probabilistic Information Integration. Proceedings of the 21st ACM International Conference on Information and Knowledge Management (Maui, Hawaii), 2012, pp. 882-891.
watermark seal