239 Pages
English

The contextual map [Elektronische Ressource] : detecting and exploiting affinity between contextual information in context-aware mobile environments / Robert Schmohl

Gain access to the library to view online
Learn more

Informations

Published by
Published 01 January 2010
Reads 24
Language English
Document size 3 MB

TECHNISCHE UNIVERSITAT MUNCHEN
Fakult at fur Informatik
Lehrstuhl fur Betriebssysteme und Systemarchitektur
The Contextual Map
Detecting and exploiting A nity between contextual
Information in context-aware mobile Environments
Robert Schmohl
Vollst andiger Abdruck der von der Fakult at fur Informatik
der Technischen Universit at Munc hen
zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr. rer. nat.)
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. B. Brugge, Ph.D.
Prufer der Dissertation: 1. Univ.-Prof. Dr. U. Baumgarten
2. Dr. J. Schlichter
Die Dissertation wurde am 01.07.2010 bei der Technischen Universit at Munc hen eingereicht
und durch die Fakult at fur Informatik am 21.10.2010 angenommen.Abstract
Context-aware computing generally focuses on abstracting the situation of individual en-
tities, such as persons, places and objects, making this information available for further
computational exploitation. Those resulting entities’ contexts allow a wide spectrum of
application cases in various domains, foremost in mobile computing and internet appli-
cations. With contexts from multiple entities available, the degree of alikeness of those
contexts poses an interesting piece of information. For this purpose, we propose a con-
text model capable of easily identifying a nities among contexts. This multi-dimensional
context model is inspired by geographical map models, which are generally applicable for
geographical proximity management. We have discovered that geographical proximity can
be leveraged to contextual proximity depicting the alikeness of di erent contexts. Hence,
our goal is to apply proximity detection methods from the location-aware computing
domain on context-aware computing. The context model has been named the contextual
map, representing an entity’s context by a set of multiple contextual attributes in a multi-
dimensional vector. The representation of entities’ contexts as multi-dimensional points
in Euclidean space allows the application of location-based proximity detection in order
to identify a nities between contexts that encompass far more contextual information
than just location. This work presents the concept of the contextual map and discusses
its prototypic application in identifying large clusters of similar contexts that aim to facil-
itate the adaptation mechanisms of context-aware systems. We especially emphasize the
utilization of proximity and separation detection on general non-location contexts, hence
enabling to dynamically monitor their a nity to each other.Contents
1 Introduction 9
1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Approach in brief . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Problem Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Structural Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Background and Research Domains 17
2.1 Overview on related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.1 Context-Awareness . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.2 Location-Aw and Proximity Detection . . . . . . . . . . . . 18
2.1.3 Related Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Context: De nition and Properties . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Context De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Properties of Context . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 Context Classi cation . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Context Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.1 Conceptual Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.2 Context Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.3 Further Aspects of Context Modeling . . . . . . . . . . . . . . . . . 31
2.4 Context-aware Computing Systems . . . . . . . . . . . . . . . . . . . . . . 33
2.4.1 Relevant Aspects and Requirements . . . . . . . . . . . . . . . . . . 33
2.4.2 Architectural Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4.3 Aspects of computational Distribution . . . . . . . . . . . . . . . . 42
2.4.4 Heterogeneity Aspects . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.5 Application Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.5 Location-aware Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.5.1 Location and location-based Services . . . . . . . . . . . . . . . . . 45
2.5.2 Lo Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.5.3 Location Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.5.4 Lo Management . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.5.5 Service Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.5.6 Application Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.6 Proximity and Separation Detection . . . . . . . . . . . . . . . . . . . . . . 55
2.6.1 Proximity Detection based on circular Zones . . . . . . . . . . . . . 56
1CONTENTS CONTENTS
2.6.2 Strip-based Proximity Detection . . . . . . . . . . . . . . . . . . . . 57
2.7 The Heterogeneity Issue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.7.1y Abstraction . . . . . . . . . . . . . . . . . . . . . . . 59
2.7.2y Handling . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.7.3 Architectural Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.7.4 Application Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.7.5 Summarizing Heterogeneity-Awareness . . . . . . . . . . . . . . . . 72
2.8 Summary and Relevance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3 The Contextual Map Model 75
3.1 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.2 Context Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.3 Data Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.3.1 Indexing Structures in multi-dimensional Space . . . . . . . . . . . 85
3.3.2 Optimization Principles . . . . . . . . . . . . . . . . . . . . . . . . 87
3.3.3 Contextual Map Indexing . . . . . . . . . . . . . . . . . . . . . . . 88
3.3.4 Space-partitioning Grids . . . . . . . . . . . . . . . . . . . . . . . . 89
4 Application of the Contextual Map 91
4.1 Contextual A nities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.1.1 Context Boundaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.1.2 Detecting A nity among Contexts . . . . . . . . . . . . . . . . . . 95
4.2 Update Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.2.1 Hyperspheres (extended 2-dimensional Circles Method) . . . . . . . 99
4.2.2 Hyperplanes Strips Method) . . . . . . . . 100
4.2.3 Application of Update Semantics . . . . . . . . . . . . . . . . . . . 103
4.3 Update Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.4 E cient Update Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.4.1 Updating the Contextual Map . . . . . . . . . . . . . . . . . . . . . 105
4.4.2 Context Vicinity De nition . . . . . . . . . . . . . . . . . . . . . . 107
4.4.3 Boundary Check . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.5 Monitoring the Contextual Map . . . . . . . . . . . . . . . . . . . . . . . . 122
4.5.1 Contextual Range Monitoring . . . . . . . . . . . . . . . . . . . . . 123
4.5.2 Monitoring multiple Range Vicinities . . . . . . . . . . . . . . . . . 127
4.6 Contextual Boundary Management . . . . . . . . . . . . . . . . . . . . . . 129
4.7 Overall Work ow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5 Exploiting contextual Similarity 135
5.1 Contextual Similarity Queries . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.1.1 Boundary-de ned Similarity Query . . . . . . . . . . . . . . . . . . 136
5.1.2 Custom-parameter-de ned Similarity Query . . . . . . . . . . . . . 137
5.2 Clustering Contexts in the Contextual Map . . . . . . . . . . . . . . . . . 138
5.2.1 Clustering Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2.2 Contexts and Range Contexts . . . . . . . . . . . . . . . . . . . . . 142
2CONTENTS CONTENTS
5.2.3 Dynamic Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
5.2.4 High-dimensional Data Clustering . . . . . . . . . . . . . . . . . . . 154
5.3 Context Clusters and Contextual Realms . . . . . . . . . . . . . . . . . . . 157
5.3.1 Contexts, Situations and Contextual Realms . . . . . . . . . . . . . 158
5.3.2 Cluster-de ned Contextual Realms . . . . . . . . . . . . . . . . . . 159
5.3.3 Arbitrarily de ned Contextual Realms . . . . . . . . . . . . . . . . 162
5.3.4 Operations on Contextual Realms . . . . . . . . . . . . . . . . . . . 164
5.3.5 Contextual Realm Monitoring . . . . . . . . . . . . . . . . . . . . . 166
6 System-speci c Aspects 167
6.1 Distribution and Mobility . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
6.1.1 Context Model Distribution . . . . . . . . . . . . . . . . . . . . . . 167
6.1.2 Employable Architectures . . . . . . . . . . . . . . . . . . . . . . . 169
6.1.3 Distributed Updates of Context . . . . . . . . . . . . . . . . . . . . 175
6.1.4 Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
6.2 The Impact of Heterogeneity . . . . . . . . . . . . . . . . . . . . . . . . . . 179
6.2.1 Heterogeneous Environment . . . . . . . . . . . . . . . . . . . . . . 180
6.2.2 Heterogeneity of Context Information . . . . . . . . . . . . . . . . . 182
6.2.3 Application Heterogeneity . . . . . . . . . . . . . . . . . . . . . . . 183
7 Prototypic System Design 185
7.1 Requirement Speci cation and Scope . . . . . . . . . . . . . . . . . . . . . 185
7.1.1 Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.1.2 Scope of Prototype . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
7.2 System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
7.2.1 Component Speci cation . . . . . . . . . . . . . . . . . . . . . . . . 187
7.2.2 Model Speci cation . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
7.3 Work ow Speci cations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
7.3.1 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
7.3.2 Contextual Update . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
7.3.3 Con Proximity Detection . . . . . . . . . . . . . . . . . . . . 195
8 Realization and Validation 199
8.1 Implementation Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
8.1.1 The Core Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
8.1.2 Index Structure Selection . . . . . . . . . . . . . . . . . . . . . . . . 199
8.1.3 Application of Context Cluster Detection . . . . . . . . . . . . . . . 202
8.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
8.2.1 Test Scenario Setting . . . . . . . . . . . . . . . . . . . . . . . . . . 204
8.2.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
9 Conclusion and Outlook 213
9.1 Summarizing the Contextual Map Concept . . . . . . . . . . . . . . . . . . 213
9.2 Applicability of the Contextual Map . . . . . . . . . . . . . . . . . . . . . 216
39.2.1 Context Model Augmentation . . . . . . . . . . . . . . . . . . . . . 216
9.2.2 Contextual Proximity Management in distributed Systems . . . . . 217
9.3 Possible Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
4List of Figures
1.1 Contexts in the Contextual Map . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Applicability of the Contextual Map . . . . . . . . . . . . . . . . . . . . . 14
2.1 Context Classi cation Aspects . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Hierarchical activity-centric Context-modeling [81] . . . . . . . . . . . . . . 27
2.3 Conceptual Context Modeling Example . . . . . . . . . . . . . . . . . . . . 28
2.4 General Context Management Work ow . . . . . . . . . . . . . . . . . . . 40
2.5 Architecture for context-aware Systems . . . . . . . . . . . . . . . 41
2.6 Location Model Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.7 Multi-tier hierarchical Location Management System . . . . . . . . . . . . 49
2.8 Work ow of a location-based Service Execution . . . . . . . . . . . . . . . 52
2.9 Layered location-aware Middleware Concept . . . . . . . . . . . . . . . . . 53
2.10 Proximity and Separation Detection . . . . . . . . . . . . . . . . . . . . . . 57
2.11 Strip-based Update Semantics with 4 Neighbors . . . . . . . . . . . . . . . 58
2.12 Heterogeneity-aware Middleware Design . . . . . . . . . . . . . . . . . . . 60
2.13 Intermediary Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.14 Common Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.15 Individual Adaptation to Communication Partner . . . . . . . . . . . . . . 66
2.16 General Architecture for heterogeneity-aware Middleware . . . . . . . . . . 73
3.1 Context Mapping Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.2 Context Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . 80
23.3 R-tree Representation of Points inR . . . . . . . . . . . . . . . . . . . . . 86
23.4 kd-tree of Points inR . . . . . . . . . . . . . . . . . . . . 87
3.5 Contextual Range Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.1 Global and local Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.2 Contextual Proximity Detection Work ow . . . . . . . . . . . . . . . . . . 93
4.3 Crossing Context Boundary Example . . . . . . . . . . . . . . . . . . . . . 94
4.4 Update Strip De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
24.5 Bounding Hypersphere and Hypercube inR . . . . . . . . . . . . . . . . . 110
24.6 Hyperspheric Range Query on R-tree (R ) . . . . . . . . . . . . . . . . . . 112
24.7 SPY-TEC Space Partitioning and Querying inR . . . . . . . . . . . . . . 113
4.8 Hypercubical Range Vicinity in a spatial Grid . . . . . . . . . . . . . . . . 116
5LIST OF FIGURES LIST OF FIGURES
24.9 Boundary Thresholds in Range Vicinity (R ) . . . . . . . . . . . . . . . . . 118
24.10 Range Crossings inR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.11 Context Prediction based on Trajectory between Times t and t . . . . . . 1241 4
4.12 Context Fluctuating in Timeframe between t and t . . . . . . . . . . . . 1251 5
4.13 Range Vicinity V (C;R) in grid-based Contextual Range R . . . . . . . 130range
4.14 Work ow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.1 Hierarchical Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
5.2 Minimum Spanning Tree Representations . . . . . . . . . . . . . . . . . . . 142
5.3um Tree Clustering with d = 8 . . . . . . . . . . . . . . . 143
5.4 Example of an irregular Context Cluster . . . . . . . . . . . . . . . . . . . 146
5.5 Splitting an Context Clusters - Step 1 . . . . . . . . . . . . . . . 148
5.6 an irregular Context - Step 2 ( nal) . . . . . . . . . . . . 149
5.7 Example Context Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
5.8 Cluster-de ned contextual Realm Shapes . . . . . . . . . . . . . . . . . . . 159
5.9 Range-global cluster-derived contextual Realm . . . . . . . . . . . . . . . . 161
5.10 Example Realm on R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164loc
6.1 Distribution of the Contextual Map . . . . . . . . . . . . . . . . . . . . . . 168
6.2 Distributed Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
6.3 Dependencies among Distribution Metrics . . . . . . . . . . . . . . . . . . 174
6.4 Updates in P2P Networks . . . . . . . . . . . . . . . . . . . . . 176
6.5 Update Vector passing in P2P Architectures. . . . . . . . . . . . . . . . . . 177
6.6 Environmental Heterogeneity Handling. . . . . . . . . . . . . . . . . . . . . 181
7.1 Components of the Contextual Map Prototype . . . . . . . . . . . . . . . . 189
7.2 Static Prototype Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 191
7.3 Observer Pattern for contextual Update Management . . . . . . . . . . . . 192
7.4 Mapping Rule during Update . . . . . . . . . . . . . . . . . . . . . . . . . 193
7.5 Work ows of Prototype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
8.1 Comparison of Index Structures . . . . . . . . . . . . . . . . . . . . . . . . 200
8.2 Index Construction Benchmark . . . . . . . . . . . . . . . . . . . . . . . . 202
8.3 Insertion into Index Benc . . . . . . . . . . . . . . . . . . . . . . . . 203
8.4 k-NN Query on Index Benchmark . . . . . . . . . . . . . . . . . . . . . . . 204
8.5 Range on Index Benc . . . . . . . . . . . . . . . . . . . . . . 205
8.6 Scenario Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
8.7 Simulation Architecture . . . . . . . . . . . . . . . . . . . . . . . 209
9.1 Hybrid Context Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
6