Concepts and algorithms for efficient distributed processing of data streams

Abstract

During the last years, the proliferation of modern devices capable of capturing context information through various sensors has triggered the blossom of context-aware systems, which automatically adapt their behaviour based on the detected context. For many emerging context-aware applications, context may include a huge amount of entities possibly dispersed geographically over a wide area. In such large-scale scenarios, the efficient processing of context information becomes a challenging task. In this dissertation, we are going to focus on the problem of the efficient processing of context information. In particular, we will consider the problem of deriving high-level context information, also referred to as situation in the literature, from sensor data streams captured by a large set of geographically distributed sensors. First, we present the architecture of a distributed system that uses reasoning algorithms to detect situations in an overlay network of data stream processing operators. Then we are going to introduce our strategies for the optimal distribution of data processing between processing nodes in order to save network resources, by optimizing for bandwidth-delay product, and fulfill given QoS requirements, such as end-to-end latency constraints. To this end, we formulate three (constrained) optimization problems, which search for an optimal placement of operators onto physical hosts with respect to different application constraints. The proposed algorithms are executed in a distributed way, by using local knowledge of the system. Our evaluation shows that our algorithms achieve good approximations of the optimal solutions, while inducing limited communication overhead.

Während der letzten Jahre hat die Anzahl an vernetzten Sensoren und mit Sensoren ausgestatteten Geräten wie Smartphones stark zugenommen. Diese weitreichende Verfügbarkeit von Sensorinformationen hat zu einer Vielzahl so genannter kontextbezogener Anwendungen z.B. in der Logistik, der intelligenten Verkehrssteuerung, der Produktion („Smart Factory“) oder der Energiewirtschaft („Smart Grid“) geführt, welche in der Lage sind, ihr Verhalten automatisch an ihren Kontext anzupassen. Viele Anwendungsszenarien basieren dabei auf einer großen Anzahl von Sensoren (Datenquellen), Kontextdatenprozessoren, welche aus Sensordaten höherwertige Kontextinformationen (Situationen) ableiten und Anwendungen (Datensenken), welche geographisch weit verteilt und über Weitverkehrsnetze bzw. das Internet miteinander vernetzt sind. Die Quellen produzieren dabei u.U. großvolumige Datenströme (z.B. kontinuierliche Videoaufzeichnungen) bzw. eine Vielzahl von Datenströmen (z.B. aus großen Netzen von Temperatursensoren, Kontaktschleifen entlang von Straßen, Verbrauchsdaten von „Smart-Meters“, usw.). Insbesondere in solch großen Szenarien stellt die effiziente Kommunikation und Verarbeitung von Sensordatenströmen eine große Herausforderung dar, der sich diese Dissertation widmet. Das übergeordnete Ziel dieser Arbeit ist dabei der Entwurf von Konzepten und Mechanismen zur effizienten verteilten Verarbeitung von Sensordatenströmen in einem Netz aus Kontextdatenprozessoren zur Ableitung von höherwertigen Situationen zur Unterstützung kontextbezogener Anwendungen. Hierzu leistet diese Arbeit die folgenden Beiträge. Zunächst wird eine Architektur zur verteilten Verarbeitung von Sensordaten in einem dem physischen Netz überlagerten Overlay-Netz aus Datenprozessoren - so genannten Operatoren - entworfen sowie das Konzept der Operatorgraphen zur Modellierung der verteilten Verarbeitung formal eingeführt. Dieses Konzept ermöglicht insbesondere die verteilte Ausführung von Situationserkennungsoperatoren, z.B. basierend auf Bayes'schen Netzen. Des Weiteren werden verschiedene Algorithmen zur optimalen Verteilung der Operatoren eines Operatorgraphen auf physischen Rechnern (Hosts) im Overlay-Netz vorgeschlagen (Operatorplatzierung). Ziel der Optimierung ist dabei die Steigerung der Skalierbarkeit durch die Entlastung des physischen Kommunikationsnetzes. Hierbei wird im Detail die Minimierung des Bandbreiten-Verzögerungsprodukts der Datenströme eines Operatorgraphen betrachtet. Ferner wird dieses zunächst reine Optimierungsproblem durch Randbedingungen in Form anwendungsspezifischer Dienstgüteeigenschaften (Quality of Service) erweitert. Betrachtet wird hierbei vor allem die Ende-zu-Ende-Verzögerung von den Datenquellen zur -senke als wichtige Randbedingung zeitkritischer Anwendungen und Prozesse. Neben der Betrachtung der Kommunikationsverzögerung werden dabei auch verarbeitungsintensive Anwendungen durch die Einbeziehung der Verarbeitungszeit auf den Rechenknoten berücksichtigt. Ein wesentlicher Beitrag dieser Arbeit ist ein verteilter Algorithmus zur näherungsweisen Lösung des Optimierungsproblems durch dezentrale Platzierungsentscheidungen der Operatoren basierend auf lokalem Wissen. Dieser Algorithmus wird in weiteren Schritten so erweitert, dass eine gegebene Ende-zu-Ende-Verzögerung eingehalten wird. Die im Rahmen dieser Dissertation durchgeführten Evaluierungen zeigen, dass diese Verfahren zu sehr guten Annäherungen der optimalen Lösung mit nur geringem Kommunikationsaufwand zur Ausführung des verteilten Algorithmus führen.