TU Darmstadt / ULB / TUprints

Fault-Tolerant Spatio-Temporal Compression Scheme for Wireless Sensor Networks

Ali, Azad :
Fault-Tolerant Spatio-Temporal Compression Scheme for Wireless Sensor Networks.
Technische Universität Darmstadt, Darmstadt
[Ph.D. Thesis], (2017)

This is the latest version of this item.

[img]
Preview
Text
Azad-Final-Gray.pdf
Available under CC-BY 4.0 International - Creative Commons Attribution 4.0.

Download (6MB) | Preview
Item Type: Ph.D. Thesis
Title: Fault-Tolerant Spatio-Temporal Compression Scheme for Wireless Sensor Networks
Language: English
Abstract:

Wireless sensor networks are often deployed for environmental sampling and data gathering. A typical wireless sensor network consists, from hundreds to thousands, of battery powered sensor nodes fitted with various sensors to sample the environmental attributes, and one or more base stations, called the sink. Sensor nodes have limited computing power, memory and battery. Sensor nodes are wirelessly interconnected and transmit the sampled data in a multihop fashion to the sink. The sheer number of sensor nodes and the amount of sampled data can generate enormous amount of data to be transmitted to the sink, which subsequently can transform into network congestion problem resulting into data losses and rapid battery drain. Hence, one of the main challenges is to reduce the number of transmissions both to accommodate to the network bandwidth and to reduce the energy consumption. One possibility of reducing the data volume would be to reduce the sampling rates and shutdown sensor nodes. However, it can affect the spatial and temporal data resolution. Hence, we propose a compression scheme to minimize the transmissions instead of reducing the sampling.

The sensor nodes are vulnerable to external/environmental effects and, being relatively cheap, are susceptible to various hardware faults, e.g., sensor saturation, memory corruption. These factors can cause the sensor nodes to malfunction or sample erroneous data. Hence, the second biggest challenge in data gathering is to be able to tolerate such faults.

In this thesis we develop a spatio-temporal compression scheme that detects data redundancies both in space and time and applies data modeling techniques to compress the data to address the large data volume problem. The proposed scheme not only reduces the data volume but also the number of transmissions needed to transport the data to the sink, reducing the overall energy consumption. The proposed spatio-temporal compression scheme has the following major components:

Temporal Data Modeling: Models are constructed from the sampled data of the sensor nodes, which are then transmitted to the sink instead of the raw samples. Low computing power, limited memory and battery force us to avoid computationally expensive operations and use simple models, which offer limited data compressibility (fewer samples are approximated). However, we are able to extend the compressibility in time through our model caching scheme while maintaining simple models.

Hierarchical Clustering: The data sampled by the sensor nodes is often not only temporally correlated but also spatially correlated. Hence, the sensor nodes are initially grouped into 1-hop clusters based on sampled data. Only a single model is constructed for one cluster, essentially reducing the sampled data of all the sensor nodes to a single data model. However, we also observed through experiments that the data correlations often extend beyond 1-hop clusters. Hence, we devised a hierarchical clustering scheme, which uses the model of one 1-hop cluster to also approximate the sampled data in the neighboring clusters. All the 1-hop clusters approximated by a given model are grouped into a larger cluster. The devised scheme determines the clusters that can construct the data models, the dissimilation of the model to the neighboring clusters and finally the transmission of the data model to the sink. The accuracy of data to the single sensor node level is maintained through outliers for each sensor node, which are maintained by the cluster heads of the respective 1-hop clusters and cumulatively transmitted to the sink.

The proposed spatio-temporal compression scheme reduces the total data volume, is computationally inexpensive, reduces the total network traffic and hence minimizes the overall energy consumption while maintaining the data accuracy as per the user requirements.

This thesis also addresses the second problem related to data gathering in sensor networks caused by the faults that results into data errors. We have developed a fault-tolerance scheme that can detect the anomalies in the sampled data and classify them as errors and can often correct the resulting data errors. The proposed scheme can detect data errors that may arise from a range of fault classes including sporadic and permanent faults. It is also able to distinguish the data patterns that may occur due to both the data errors and a physical event. The proposed scheme is quite light weight as it exploits the underlying mechanisms already implemented by spatio-temporal compression scheme. The proposed fault-tolerance scheme uses the data models constructed by the compression scheme to additionally detect data errors and subsequently correct the erroneous samples.

Alternative Abstract:
Alternative AbstractLanguage
Für die Erfassung von Umweltdaten kommen häufig Sensornetzwerke zum Einsatz. Derartige Netzwerke bestehen typischerweise aus einigen hundert bis zu mehreren tausend batteriebetriebenen Sensorknoten (Quellen), welche die nötige Sensorik zur Erfassung der Umwelteigenschaften enthalten, sowie einer oder mehreren Basisstationen (Senken). Die Sensorknoten verfügen über eine begrenzte Rechenleistung, wenig Speicher und kleine Batterien. Sie sind untereinander drahtlos vernetzt und übertragen die gesammelten Daten über mehrere Sensorknoten, die als Zwischenstationen fungieren, zur Basisstation. Durch die enorme Zahl von Sensorknoten können riesige Datenmengen entstehen. In Folge kommt es zu Datenstaus oder gar zum Verlust von Messwerten und zu einer verkürzten Laufzeit der Sensorknoten durch erhöhten Stromverbrauch für die Übertragung. Eine zentrale Herausforderung bei Sensornetzwerken stellt somit die Optimierung der Datenübertragung hinsichtlich Bandbreite und Energieverbrauch dar. Eine einfache Methode, das Datenaufkommen zu reduzieren, bestünde in der Verringerung der Abtastrate und dem zeitweisen Abschalten von Sensorknoten. Allerdings würde dies die zeitliche und räumliche Auflösung der Ergebnisse beeinträchtigen. Wir schlagen daher stattdessen eine Komprimierung der aufgenommenen Daten vor. Aufgrund ihres kostenoptimierten Aufbaus sind die Sensorknoten störanfällig gegenüber externen Umwelteinflüssen. Auch interne Defekte wie zum Beispiel Sensorsättigung oder Speicherfehler können auftreten. Diese Faktoren führen zu verfälschten Messergebnissen und im schlimmsten Fall zum Ausfall von Sensorknoten. Eine weitere Herausforderung ist somit die Fehlertoleranz des Netzwerkes gegenüber derartigen Fehlern. In dieser Arbeit entwickeln wir ein Komprimierungsverfahren basierend auf der Erkennung von räumlichen und zeitlichen Redundanzen. Durch Anwendung von Datenmodellierungsverfahren reduziert sich die Datenmenge, die Anzahl der nötigen Übertragungen wird verringert und der Gesamtenergiebedarf gesenkt. Diese räumlich-zeitliche Komprimierung gliedert sich in 2 Bereiche: • Zeitliche Datenmodellierung: Die aufgenommenen Sensordaten werden vor dem Versenden in Modelle überführt und anstatt der Rohwerte zu den Basisstation übertragen. In Anbetracht der begrenzten Ressourcen auf den Sensorknoten verbietet sich die Nutzung komplexer Berechnungen. Zum Einsatz kommen daher einfache Modelle mit etwas geringerem Komprimierungspotential, deren Optimierung auf Basis einer geringeren Anzahl von Messwerten erfolgt. Es gelingt uns allerdings, die zeitliche Komprimierung durch effiziente Zwischenspeicherung der Modelle zu erhöhen. • Hierarchische Gruppierung: Die gewonnenen Sensordaten sind häufig nicht nur zeitlich, sondern auch räumlich korreliert. Dadurch bietet sich eine räumliche Gruppierung an. Unter Verwendung der aufgenommenen Daten werden die Sensorknoten initial in sogenannte ‚1-hop‘ Cluster zusammengefasst. Pro Cluster wird auf Basis der Rohwerte aller enthaltenen Sensorknoten jeweils nur ein einziges Datenmodell generiert. Experimente zeigten darüber hinaus oft auch übergeordnete Abhängigkeiten zwischen Messwerten außerhalb dieser ersten Ebene. Wir setzen daher auf eine hierarchische Gruppierung, welche die Daten benachbarter Cluster analog der Vorgehensweise der ersten Ebene kombiniert und somit Cluster höherer Ordnung bildet. Das beschriebene Verfahren beinhaltet die Ermittlung gruppierbarer Cluster, die Ausweitung des Datenmodells auf passende Nachbarn sowie die finale Übermittlung der komprimierten Daten an die Basisstationen. Um Fehler durch die Prozessierung zu vermeiden, wird die Güte der finalen Daten unter Einbeziehung von Ausreißern auf Einzelsensorebene gewährleistet. Die Hauptknoten der ‘1-hop’ Cluster sammeln entsprechende Daten und senden diese kumuliert an die Basisstationen. Das vorgeschlagene räumlich-zeitliche Komprimierungsverfahren reduziert die Gesamtdatenmenge, benötigt wenig Rechenleistung, minimiert die Anzahl der Übertragungen und damit auch den Energieverbrauch des Netzwerkes. Dabei lässt sich die Genauigkeit der gewonnenen Daten flexibel an die Bedürfnisse des Nutzers anpassen. Neben der Komprimierung beschreiben wir in dieser Arbeit auch Methoden zur Erhöhung der Fehlertoleranz gegenüber internen und externen Einflüssen. Unregelmäßigkeiten in den Messwerten werden erkannt, als Fehler klassifiziert und können in vielen Fällen korrigiert werden. Das vorgeschlagene Verfahren deckt eine breite Palette möglicher Fehlerfälle ab und verarbeitet sowohl sporadische als auch permanente Abweichungen. Dabei ist es in der Lage, Fehler von realen, durch plötzliche Änderung der zu messenden physikalischen Größen hervorgerufenen, Abweichungen zu unterscheiden. Der verwendete Ansatz ist sehr effizient, da er sich der Methoden der räumlich-zeitlichen Komprimierung bedient und bereits existierende Datenmodelle zur Erkennung und Korrektur fehlerhafter Daten nutzt.German
Place of Publication: Darmstadt
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: 20 Department of Computer Science > Embedded Systems and Applications
20 Department of Computer Science > Embedded Sensing Systems
Date Deposited: 06 Mar 2017 11:46
Last Modified: 06 Mar 2017 11:46
URN: urn:nbn:de:tuda-tuprints-59240
Referees: Suri, Prof. Dr. Neeraj and Becker, Prof. Dr. Christian and Katzenbeisser, Prof. Dr. Stefan and Schürr, Prof. Dr. Andy and Fischlin, Prof. Dr. Marc
Refereed: 4 November 2016
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/5924
Export:

Available Versions of this Item

  • Fault-Tolerant Spatio-Temporal Compression Scheme for Wireless Sensor Networks. (deposited 06 Mar 2017 11:46) [Currently Displayed]
Actions (login required)
View Item View Item

Downloads

Downloads per month over past year