Model-driven optimizations for public sensing systems

Abstract

The proliferation of modern smartphones such as the Apple iPhone or Google Android Phones has given rise to Public Sensing, a new paradigm for sensor data acquisition using spare resources of commodity smartphones. As smartphones are already deployed wherever there are people present, data collection is enabled at an urban scale. Having access to such a wealth of data facilitates the creation of applications depending on real-world information in a way that may have a lasting impact on our everyday life. However, creating large-scale Public Sensing systems is not without its challenges. On the data requesting side, an interface is required that allows to specify arbitrary sensing tasks independent of the mobility of participants and thus facilitates user acceptance of Public Sensing. On the data gathering side, as many people as possible must participate in the system and thus provide a sufficient amount of data. To this end, the system must conserve the resources shared by participants as much as possible, with the main concern being energy. Participants will withdraw from the system, when participating significantly impacts the battery life of their smartphone. We address the aforementioned issues in the context of two applications: Indoor map generation and large-scale environmental data acquisition. In the area of indoor map generation, we first address the problem of building an indoor map directly from odometry traces. In contrast to existing approaches, our focus is to extract the maximum amount of information from trace data without relying on additional features such as WiFi fingerprints. Furthermore, we present an approach to improve indoor maps derived from traces using a formal grammar encoding structural information about similar indoor areas. Using this grammar allows us to extend an incomplete trace-based map to a plausible layout for the entire floor while simultaneously improving the accuracy of floor plan objects observed by odometry traces. Our evaluations show that the accuracy of grammar-based maps in the worst-case is similar to the accuracy of trace-based maps in the best-case, thus proving the benefit of the grammar-based approach. To improve the energy efficiency of the mapping process, we furthermore present a generic quality model for trace-based indoor maps. This quality metric is used by a scheduling algorithm, instructing a participating device to disable its energyintensive sensors while it travels in an area that has been mapped with high quality already, enabling energy savings of up to 15%. In the area of large-scale environmental data acquisition, we first present the concept of virtual sensors as a mobility-independent abstraction layer. Applications configure virtual sensors to report a set of readings at a given sampling rate at a fixed position. The Public Sensing system then selects smartphones near the position of a virtual sensor to provide the actual data readings. Furthermore, we present several optimization approaches geared towards improving the energy efficiency of Public Sensing. In a local optimization, smartphones near each individual virtual sensor coordinate to determine which device should take a reading and thus avoid oversampling the virtual sensor. The local optimization can achieve a 99% increase in efficiency with the most efficient approaches and exhibits only about 10% decrease in result quality under worst conditions. Furthermore, we present a global optimization, where a data-driven model is used to identify the subset of most interesting virtual sensors. Data is obtained from this subset only, while readings for other virtual sensors are inferred from the model. To this end, we present a set of online learning and control algorithms that can create a model in just hours or even minutes and that continuously validate its accuracy. Evaluations show that the global optimization can save up to 80% of energy while providing inferred temperature readings matching an error-bound of 1°C up to 100% of the time.

Die wachsende Verbreitung moderner Smartphones wie des Apple iPhone oder den Android-Geräten von Google hat die Idee des Public Sensing inspiriert. Public Sensing ist ein neues Paradigma der Datenerfassung unter Verwendung ungenutzter Ressourcen von Smartphones. Da Smartphones überall dort verfügbar sind, wo sich Menschen aufhalten, ermöglicht Public Sensing eine Datenerfassung auf urbanem Maßstab. Die Verfügbarkeit dieser Datenmenge ermöglicht die Entwicklung neuer, Realwelt-bezogener Anwendungen, die unser alltägliches Leben nachhaltigen verändern können. Die Entwicklung von Public-Sensing-Systemen in großem Maßstab birgt jedoch einige Herausforderungen. Systeme müssen die Anfrage von unterschiedlichsten Daten unabhängig von der Mobilität der Menschen ermöglichen, um die Verwendung und Akzeptanz von Public Sensing zu fördern. Weiterhin müssen so viele Personen wie möglich am System teilnehmen, damit die notwendigen Daten erfasst werden können. Dazu muss das Public-Sensing-System die Ressourcen der Teilnehmer, insbesondere den Energievorrat der Smartphones, so weit wie möglich schonen. Teilnehmer werden sich aus dem System zurückziehen, wenn die Teilnahme die Akkulaufzeit ihres Smartphones signifikant beeinträchtigt. In dieser Arbeit betrachten wir die zuvor genannten Herausforderungen im Kontext zweier Anwendungen: Der Erfassung von Innenraumkarten und der Erfassung von Umweltdaten in großem Maßstab. Im Bereich der Erfassung von Innenraumkarten präsentieren wir zunächst ein System zur Ableitung von Innenraumkarten aus Bewegungsspuren der Teilnehmer. Im Gegensatz zu bestehenden Ansätzen konzentrieren wir uns darauf, ohne Verwendung zusätzlicher Informationen, wie z.B. WLAN-Fingerabdrücken, ein Maximum an Informationen aus den Bewegungsspuren zu extrahieren. Weiterhin präsentieren wir einen Ansatz zur Verbesserung von Innenraumkarten aus Bewegungsspuren mit Hilfe einer formalen Grammatik. Die Grammatik codiert dabei strukturelle Informationen über ähnliche Innenraumbereiche anderer Gebäude. Die Verwendung der Grammatik erlaubt das plausible Vervollständigen einer unvollständigen Innenraumkarte, wobei zusätzlich die Genauigkeit fehlerbehafteter Beobachtungen verbessert wird. Diese Verbesserung wird von unseren Experimenten belegt, die zeigen, dass die Genauigkeit der besten Innenraumkarten aus Bewegungsspuren gerade der Genauigkeit der schlechtesten grammatikgenerierten Karten entspricht. Um die Energieeffizienz des Kartierungsprozesses zu verbessern präsentieren wir weiterhin ein generisches Qualitätsmodell für Innenraumkarten. Dieses Qualitätsmodell wird von einem Planungsalgorithmus verwendet, der die energieintensive Erfassungssensorik eines Smartphones deaktiviert, während es sich in einem Bereich aufhält, der bereits mit hoher Qualität erfasst wurde. Dadurch kann bis zu 15% der Energie für die Datenerfassung eingespart werden. Im Bereich der Umweltdatenerfassung in großem Maßstab stellen wir zunächst das Konzept des virtuellen Sensors als mobilitätsunabhängige Abstraktion vor. Anwendungen konfigurieren virtuelle Sensoren, um Informationen an einer festen Position mit einer vorgegebenen Datenrate aufzunehmen. Das Public-SensingSystem wählt dann Smartphones in der Nähe jedes virtuellen Sensors aus, um die tatsächliche Datenerfassung auszuführen. Weiterhin präsentieren wir mehrere Optimierungsanätze um die Energieeffizienz von Public Sensing zu verbessern. Bei der lokalen Optimierung koordinieren die Smartphones in der Nähe jedes einzelnen virtuellen Sensors selbstständig, welches Gerät Daten erfassen soll. Somit wird vermieden, Daten mehrfach zu erfassen. Die lokale Optimierung kann die Effizienz der Datenerfassung um bis zu 99% verbessern, während die Datenqualität im schlechtesten Fall um höchstens etwa 10% sinkt. Weiterhin präsentieren wir eine globale Optimierung, die ein datengetriebenes Modell nutzt, um eine Untermenge der wichtigsten virtuellen Sensoren zu bestimmen. Daten werden nur für diese Untermenge erfasst, während die Messwerte für alle anderen virtuellen Sensoren aus dem Modell abgeleitet werden. Dazu stellen wir eine Reihe von Online-Lern- und Kontrollalgorithmen vor, die die Erstellung eines Modells in Stunden oder sogar nur Minuten ermöglichen, und die kontinuierlich die Gültigkeit des Modells überprüfen. Unsere Untersuchungen zeigen, dass die globale Optimierung bis zu 80% Energieeinsparung bietet. Dabei bleibt der Fehler in abgeleiteten Temperaturmesswerten bis zu 100% der Zeit unter einer Fehlerschranke von 1°C.