State-based context prediction in mobile systems

Abstract

Context-aware computing has developed from a pure research area to a widely acknowledged design principle of modern mobile systems over the last years. Mobile applications, able to automatically adapt to a user’s dynamic context and improve the ease of human-computer interactions, are commonly available today. However, with current context-aware services such as restaurant finders or mobile tour guides, it is possible to support users with respect to their present behaviour only. As the next stage in context-aware computing more intelligent proactive applications are envisioned which can not only respond to the current, but also the future context of humans: Smart homes capable of controlling the ambient environment in expectation of the inhabitants’ prospective actions; Social network applications which alert users about places where their friends might be going to; Personalized mobile recommender system to promote events and offers at venues which are relevant to the daily schedules of humans.

The development of suitable context prediction methodologies to turn such applications into a reality is however a challenge. The reason is that future context information, hidden in the raw context traces left by users in the real world, is not immediately accessible to applications. Therefore, sophisticated context prediction approaches are required that are able to discover and mine patterns of a user’s behaviour from observed context histories. However, approaches which make accurate and expressive context predictions available and exploit this knowledge to optimize context-aware systems are missing in current research. As a consequence, the full potential of context-aware technologies has not been completely realised yet. In order to address this issue, we contribute in this work new context prediction algorithms and models for state-based context data, suitable for a range of different context types, such as a user’s locations or activities. To this end, this thesis makes the following contributions.

In the first part of this thesis, we develop a novel context prediction system which applies statistical modeling concepts to automatically learn a machine-processable model of a user’s behaviour and infer context predictions. With our context prediction system, we identify and address two shortcomings of existing approaches, prediction accuracy and prediction expressiveness, and propose suitable techniques and algorithms to improve them. For increasing the prediction accuracy over current systems, we develop a new context predictor that is able to exploit the conditional dependency of context changes on a user’s activities to anticipate forthcoming context states. Further, in order to overcome the limited expressiveness of prevailing prediction approaches, we explore the application of model checking algorithms for enabling expressive time-dependent forecasts in context prediction systems. Based on the algorithms and models developed in the first part of this thesis, we are able to significantly increase the amount and accuracy of the knowledge provided to proactive applications for the prediction of future context information.

In the second part of this thesis, we shift our attention towards tailored context prediction approaches to optimize the performance of mobile sensing applications. These applications represent a new class of mobile systems in the focus of current research, designed to forward streams of sensed context updates to interested parties over wireless communication channels. As mobile data communication induces a substantial energy overhead on mobile devices, we develop novel prediction-based protocols for improving the energy efficiency of mobile sensing applications. First, we present update protocols which are able to exploit context predictions for reducing the number of transmitted context update messages and trading off context accuracy vs. energy consumption. Then, we extend our approach and show how knowledge about a user’s future behaviour can be used to find the optimal update schedule for both sensing and communicating context data given hard bounds on the energy consumption on a mobile device.

We have implemented and validated our context prediction models in detailed experimental evaluations using synthetic and real-world context data. The results of our experiments demonstrate the effectiveness of our concepts for enhancing the accuracy and expressive power of predictions, as well as for increasing the energy efficiency of context-aware mobile systems.

In den letzten Jahren haben sich kontextbezogene Systeme von einer reinen Forschungsdisziplin hin zu einem allgemein anerkannten Prinzip für die Entwicklung moderner mobiler Systeme entwickelt. Mobile Anwendungen, die sich automatisch an den dynamischen Kontext eines Benutzers anpassen und so die Einfachheit der Interaktion von Mensch und Maschine verbessern können, sind heutzutage weit verbreitet. Mit gegenwärtigen kontextbezogenen Anwendungen wie bspw. Restaurant-Finder oder mobilen Touristenführer ist es jedoch nur möglich Nutzer hinsichtlich Ihrem gegenwärtigen Verhalten zu unterstützen. Als nächste Stufe im Forschungsbereich kontextbezogener Systeme wird dagegen an proaktiven Anwendungen gearbeitet, die nicht nur auf den gegenwärtigen, sondern auch den zukünftigen Kontext von Benutzern intelligent reagieren können: Intelligente Häuser, deren Steuerung an die voraussichtlichen Handlungen Ihrer Bewohner angepasst wird; Anwendungen im Bereich Sozialer Netzwerke, die Nutzer über Orte benachrichtigen, welche von Ihren Freunden als nächste besucht werden; Personalisierte mobile Empfehlungssysteme, die über ortsabhängige Ereignisse und Angebote informieren, welche hinsichtlich der Tagesabläufe Ihrer Nutzer relevant sind.

Die Entwicklung von geeigneten Technologien zur Kontextvorhersage um solche Anwendungen Wirklichkeit werden zu lassen stellt jedoch eine große Herausforderung dar. Ein Grund hierfür ist, dass zukünftige Kontextinformationen in den rohen Kontextdaten versteckt sind, die Menschen in der realen Welt zurücklassen und somit nicht einfach zugreifbar sind. Daher werden Verfahren zur Kontextvorhersage gebraucht, die in der Lage sind charakteristische Verhaltensmuster aus erfassten Kontexthistorien zu erkennen. In der gegenwärtigen Forschung fehlen jedoch Ansätze, die genaue und ausdrucksstarke Vorhersagen möglich machen und dieses Wissen ausnutzen können um kontextbezogene Systeme zu verbessern. Um dieses Problem zu beheben, steuern wir in dieser Arbeit neue Algorithmen und Modelle bei zur Vorhersage von beliebigem zustandsbasiertem Kontext mobiler Nutzer. In dieser Hinsicht leistet diese Arbeit die folgenden Beiträge.

Im ersten Teil dieser Arbeit stellen wir ein neues Kontextvorhersagesystem vor, welches auf Grundlage von statistischer Modellierungskonzepte ein für Computer verarbeitbares Modell des Nutzerverhaltens automatisch lernen und Kontextvorhersagen ableiten kann. Mit unserem Kontextvorhersagesystem adressieren wir Schwachstellen hinsichtlich Genauigkeit und Ausdruckstärke der Vorhersage, die wir bei gegenwärtigen Ansätzen ausgemacht haben. Um die Vorhersagegenauigkeit gegenüber bestehenden Verfahren zu verbessern, wird ein neuer Kontextprädiktor entwickelt, der die Beziehung zwischen Kontextänderungen und vom Nutzer ausgeführten Aktivitäten lernt um bedingte Abhängigkeiten für die Vorhersage ausnutzen zu können. Darüberhinaus erforscht diese Arbeit den Einsatz von Algorithmen aus dem Bereich Model Checking um ausdrucksstarke zeitabhängige Vorhersagen berechnen zu können und so die limitierte Ausdrucksstärke existierender Ansätze zu verbessern. Mit Hilfe der Algorithmen und Modelle, die im ersten Teil dieser Arbeit entwickelt werden, erhöhen wir so die Menge und Genauigkeit an Information, die proaktive Anwendungen für die Vorhersage von zukünftigem Kontext zur Verfügung gestellt wird.

Im zweiten Teil dieser Arbeit wird das Augenmerk auf neue Ansätze zur Kontextvorhersage gerichtet um die Performanz mobiler sensorgetriebener Anwendungen zu optimieren. Diese Anwendungen stellen eine neue Klasse mobiler Systeme dar, welche im Fokus gegenwärtiger Forschungsarbeiten stehen um kontinuierlich Kontext auf einem mobilen Gerät zu erfassen und über drahtlose Kommunikationskanäle an interessierte Konsumenten weiterzuleiten. Da mobile Datenkommunikation für mobile Geräte einen beträchtlichen Energiemehraufwand bedeutet, entwickeln wir in dieser Arbeit neue vorhersagebasierte Updateprotokolle um die Energieeffizienz dieser Anwendungen zu verbessern. Als Erstes stellen wir Updateprotokolle vor, die Kontextvorhersagen ausnutzen um die Anzahl der übertragenen Kontextupdates zu reduzieren und den anfallenden Energieverbrauch gegenüber der erzielten Kontextgenauigkeit abwägen zu können. Zusätzlich wird ein erweiterter Ansatz entwickelt, der Kontextvorhersagen ausnutzt um eine optimale Entscheidung zu finden, wann Kontext erfasst und verschickt werden soll, wenn feste Schranken hinsichtlich des Energieverbrauchs auf mobilen Geräten gegeben sind.

Die in dieser Arbeit beschriebenen Kontextvorhersageansätze wurden implementiert und in ausführlichen Experimenten mittels simulierten und echten Datensätzen bewertet. Die Ergebnisse der Experimente belegen die Wirksamkeit der Ansätze um die Genauigkeit und Ausdrucksstärke von Vorhersagen verbessern und die Energieeffizienz kontextbezogener mobiler System erhöhen zu können.