Definition and configuration of reliable event detection for application in wireless sensor networks [Elektronische Ressource] / Steffen Ortmann

Sujets

• Informatik

Informations

• Publié par: brandenburgische_technische_universitat_cottbus
• Publié le: 01 janvier 2010
• Nombre de lectures: 26
• Langue: English
• Poids de l'ouvrage: 52 Mo

Extrait

De nition and Con guration of Reliable
Event Detection for Application in
Wireless Sensor Networks
Von der Fakult at fur Mathematik, Naturwissenschaften und Informatik
der Brandenburgischen Technischen Universit at Cottbus
zur Erlangung des akademischen Grades
Doktor der Ingenieurwissenschaften
(Dr.-Ing.)
genehmigte Dissertation
vorgelegt von
Diplom-Informatiker
Ste en Ortmann
Geboren am 30.10.1980 in Eisenhutte nstadt
Gutachter: Prof. Dr. rer. nat. Peter Langend orfer
Gutachter: Prof. Dr.-Ing. J org Nolte
Gutachter: Prof. Dr. Torsten Braun
Tag der mundlic hen Prufung: 06. Juli 2010To my familyContents
Contents 1
Extended Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Kurzfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1 Introduction 9
2 Related Work 13
2.1 Design criteria for reliable event-based applications . . . . . . . . . 13
2.2 High abstraction for sensor network con guration . . . . . . . . . . 15
2.3 Fault tolerant voting mechanisms . . . . . . . . . . . . . . . . . . . 16
2.4 Collaborative event detection . . . . . . . . . . . . . . . . . . . . . 19
2.5 Assessment of related work . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Introduction to Quality of Information . . . . . . . . . . . . . . . . 23
3 Complex Fault Tolerant Event De nition 25
3.1 Architectural overview . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Specifying complex event detection . . . . . . . . . . . . . . . . . . 27
3.2.1 Structure of an event speci cation . . . . . . . . . . . . . . 27
3.2.2 De nition of complex phenomena . . . . . . . . . . . . . . . 29
3.2.3 Addition of execution constraints and associated handlers . 32
3.2.4 Determining the region of event . . . . . . . . . . . . . . . . 33
3.2.5 Customising voting preconditions . . . . . . . . . . . . . . . 35
3.3 Reactive Majority Voting (RMV) . . . . . . . . . . . . . . . . . . . 36
3.4 Fire detection scenario - An illustrative example . . . . . . . . . . 39
3.5 Generation of deployable event descriptions . . . . . . . . . . . . . 41
3.5.1 Adaptation to target sensor platform . . . . . . . . . . . . . 43
3.5.2 Creation of event descriptions . . . . . . . . . . . . . . . . . 43
4 Deployment on Sensor Nodes as Event Decision Tree (EDT) 47
4.1 Architecture of the EDT-engine . . . . . . . . . . . . . . . . . . . . 47
12 CONTENTS
4.2 Establishing Event Decision Tree . . . . . . . . . . . . . . . . . . . 48
4.2.1 Evaluation of the EDT . . . . . . . . . . . . . . . . . . . . . 50
4.3 Local adaptation of EDTs by pruning . . . . . . . . . . . . . . . . 51
4.4 Collaborative exchange of event information . . . . . . . . . . . . . 54
4.4.1 Publish/subscribe scheme . . . . . . . . . . . . . . . . . . . 55
4.4.2 Lease procedure . . . . . . . . . . . . . . . . . . . . . . . . 57
4.5 Side e ects of voting and collaboration . . . . . . . . . . . . . . . . 65
4.6 Performance evaluation . . . . . . . . . . . . . . . . . . . . . . . . 67
4.6.1 Evaluation methodology . . . . . . . . . . . . . . . . . . . . 68
4.6.2 Simulation parameters and deployment patterns . . . . . . 69
4.6.3 Deviations in sensor readings . . . . . . . . . . . . . . . . . 72
4.6.4 Failing sensing capabilities . . . . . . . . . . . . . . . . . . . 86
4.6.5 Transiently failing sensing capabilities . . . . . . . . . . . . 95
4.6.6 Simultaneous occurrence of deviations and transient failures 99
4.6.7 Lessons learnt from simulations . . . . . . . . . . . . . . . . 104
5 Indicating the Signi cance of Data Readings 107
5.1 Mathematical background . . . . . . . . . . . . . . . . . . . . . . . 108
5.2 Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.3 Short summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6 Conclusions 117
6.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Bibliography 123
A Event Speci cation Language (ESL) 133
A.1 eXtensible Markup (XML) schema of the ESL . . . . . . 133
A.2 Class diagram of the ESL-parser implementation . . . . . . . . . . 138
A.3 State transition table of the EDT-generator. . . . . . . . . . . . . . 139
B Diagrams of simulation results 141
B.1 Simulation results for positive deviating sensor
readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
B.2 Simulation results for negative deviating sensor
readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
B.3 Simulation results for general deviating sensor
readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
B.4 Simulation results for permanently failing sensing capabilities . . . 163
B.5 Sim for transiently failing sensing . . . . 168
B.6 Simulation results for simultaneous occurrence of deviations and
transient failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173CONTENTS 3
List of Symbols and Abbreviations 179
List of Figures 181
List of Tables 193
Listings 196EXTENDED ABSTRACT 5
Extended Abstract
Ubiquitous systems based on wireless sensor networks will amazingly increase
our quality of life. These systems are to be deployed in large areas with high
density where hundreds or thousands of nodes are used. Certainly that demands
to use low cost devices with limited resources, which in turn are prone to faulty
behaviour. This work introduces a novel concept for wireless sensor network
con guration considering fault tolerance, energy e ciency and convenience as
primary goals while being tailored to user needs. It allows to ignore low-level
details like node resources, network structures, node availability etc. and en-
ables the programmer to work on a high abstraction level, namely the event itself
including event related constraints. The de nition of events characterising real
world phenomena is of prominent use in sensor networks. The presented con-
cept autonomously con gures and monitors events, even if it requires to organise
collaboration between nodes to deliver the results.
The contribution of this work is threefold. An intuitive XML-based Event
Speci cation Language (ESL) simpli es event con guration to a level that is
even suitable for non-professionals. It features hardware independent descrip-
tion elements to de ne complex phenomena and enhances these by tailor-made
voting schemes and application constraints. Based on that, a novel, fully de-
centralised mechanism to autonomously set up distributed event detection called
Event Decision Tree (EDT) and a cost e cient means to maintain such EDT,
are presented. EDTs can be e ciently constructed on every device by using a
tiny generating nite state machine requiring eight states only. It enables every
node to self-divide event queries according to its own resources and self-adapt to
the tasks assigned. Simultaneously, the EDT provides the interface for e cient
collaboration using a lease-based publish/subscribe approach. The simulations
clearly show that this concept works well and the applied collaboration scheme
outperforms even idealised acknowledgement-based approaches.
On top of the EDT, a means is developed that enhances the reliability of
detection beyond the scope of Boolean event decision. It examines behavioural
trends in sensor readings to indicate the signi cance of actual measurements in
relation to the con gured event. Measured data is investigated in detail to nally
attach a signi cance indicator i to each event. This automatically generatedS
indicator shall support users or overlaying systems in decision-making. In the
example scenario based on data of real test cases, the i indicates a aming reS
88 seconds and a smouldering re 48 seconds before the threshold-based method
triggers the alarm.6 CONTENTS
Kurzfassung
Drahtlose Sensornetze stellen eine Informationstechnologie dar, deren ubiquit are
Verwendung unsere zukunftige Lebensweise entscheidend beein ussen und ver-
bessern kann. Der massenhafte Einsatz solcher Systeme bedingt strengste Ein-
schr ankungen in Kosten und Ressourcen und fuhrt damit zu einer verringerten
Zuverl assigkeit der einzelnen Sensorknoten und des gesamten Sensornetzes. Diese
Arbeit fuhrt ein neuartiges Konzept zur Kon guration von drahtlosen Sensor-
netzen ein. Die Schwerpunkte liegen dabei auf Fehlertoleranz und Energieef-
zienz unter besonderer Beruc k-sichtigung von Verbraucherfreundlichkeit und
Komplexit at. Es erlaubt dem Nutzer auf einem hohen Abstraktionsniveau zu ar-
beiten, ohne niedrigstu ge Details wie Sensor-Ressourcen, Netzwerkstrukturen,
Verfugbar keit der Knoten usw. beachten zu mussen. Die Beschreibung physikalis-
cher Ph anomene als Events ndet breite Anwendung bei der Programmierung
von Sensornetzen. Das vorgestellte Konzept kon guriert und beobachtet einma-
lig de nierte Events vollautomatisch, auch wenn dazu kooperative Beziehungen
zwischen verschiedenen Sensorknoten notwendig sind.
Die Arbeit besteht aus 3 Hauptteilen. Eine intuitive auf XML basierende
Sprache zur De nition von Events vereinfacht die Kon guration der Sensornetze
auf ein Niveau, das auch fur konventionelle Nutzer angemessen ist. Es be-
sitzt hardware-unabh angige Elemente zur De nition von komplexen Phanomenen
(Events) und erweitert diese durc