A Survey of Context Modelling and Reasoning Techniques

* Manuscript
A Survey of Context Modelling and
Reasoning Techniques
Claudio Bettini a,∗ Oliver Brdiczka b Karen Henricksen c
Jadwiga Indulska d,c Daniela Nicklas e Anand Ranganathan f
Daniele Riboni a
aDICo, Universit`a di Milano, Italy
bTelecooperation Group, TU Darmstadt, Germany
cNICTA, Australia
dSchool of Information Technology and Electrical Engineering,
The University of Queensland, Australia
eDepartment f¨ur Informatik, Carl von Ossietzky Universit¨at Oldenburg, Germany
f IBM TJ Watson Research Center, Hawthorne, NY
Abstract
Development of context-aware applications is inherently complex. These applica-
tions adapt to changing context information: physical context, computational con-
text, and user context/tasks. Context information is gathered from a variety of
sources that differ in the quality of information they produce and that are of-
ten failure prone. The pervasive computing community increasingly understands
that developing context-aware applications should be supported by adequate con-
text information modelling and reasoning techniques. These techniques reduce the
complexity of context-aware applications and improve their maintainability and
evolvability. In this paper we discuss the requirements that context modelling and
reasoning techniques should meet, including the modelling of a variety of context
information types and their relationships, of situations as abstractions of context
information facts, of histories of context information, and of uncertainty of context
information. This discussion is followed by a description and comparison of current
context modelling and reasoning techniques.
Key words: context modelling, context reasoning, context management, quality of
context, situation modelling
∗ corresponding author
Email address: bettini@dico.unimi.it (Claudio Bettini).
Preprint submitted to Elsevier
27 March 2008

---

1
Introduction
There is a growing body of research on the use of context-awareness as a tech-
nique for developing pervasive computing applications that are flexible, adapt-
able, and capable of acting autonomously on behalf of users. A large part of
this research investigates approaches to modelling context information used by
context-aware applications and reasoning techniques for context information.
The pervasive computing community increasingly understands benefits of for-
mal context information modelling. First of all, due to the inherent complexity
of context-aware applications, the development should be supported by ade-
quate software engineering methods. The overall goal is to develop evolvable
context-aware applications. Therefore the design of the general functions of
such applications should not be intertwined with the definition and evalua-
tion of context information, which is often subject to change. A good context
information modelling formalism reduces the complexity of context-aware ap-
plications and improves their maintainability and evolvability. In addition,
since gathering, evaluating and maintaining context information is expensive,
re-use and sharing of context information between context-aware applications
should be considered from the beginning. The existence of well-designed con-
text information models eases the development and deployment of future ap-
plications. Moreover, a formal representation of context data within a model
is necessary for consistency checking, as well as to ensure that sound reasoning
is performed on context data.
Several requirements have to be taken into account when modelling context
information:
Heterogeneity and mobility: Context information models have to deal with
a large variety of context information sources that differ in their update rate
and their semantic level. Sensors can observe certain states of the physical
world and provide fast and near realtime access, while providing rather raw
data (like a GPS position or a camera stream) that has to be interpreted
before being usable by applications. Information provided by the user—like
profiles or preferences—is updated more rarely and in general does not need
additional interpretation. Finally, context data obtained from databases or
digital libraries—like geographic map data—is often static. Typically, these
shared content spaces contain data at a medium level of semantics. It is in-
terpreted in some way (e.g., the geographic features are enriched with names,
tags, and relationships), but the interpretation is specific for a certain appli-
cation domain. Many context-aware applications are also mobile (i.e., running
on a mobile device) or depend on mobile context information sources (e.g.,
mobile sensors). This adds to the problem of heterogeneity as the context in-
formation provisioning must be adaptable to the changing environment. Also,
location and spatial layout of the context information play important roles
2

---

due to this requirement.
Relationships and dependencies: There exist various relationships be-
tween types of context information that have to be captured to ensure correct
behaviour of the applications. One such relationship is dependency whereby
context information entities/facts may depend on other context information
entities: for example, a change to the value of one property (e.g., network
bandwidth) may impact the values of other properties (e.g., remaining bat-
tery power).
Timeliness: Context-aware applications may need access to past states and
future states (prognosis). Therefore, timeliness (context histories) is another
feature of context information that needs to be captured by context models.
The management of context histories is difficult if the number of updates is
very high. It may not be feasible to store every value for future access, and
therefore summarisation techniques (e.g., the aggregation of position updates
to a movement function using interpolation techniques, or the use of historical
synopses of data) need to be applied.
Imperfection: Due to its dynamic and heterogeneous nature, context infor-
mation may be of variable quality. In fact, it may even be incorrect. Most
sensors feature an inherent inaccuracy (e.g., a few metres for GPS positions),
and the sensed values age if the physical world changes, so that this inaccu-
racy increases over time. Also, the context information may be incomplete: a
sensor that detects the number of people in a room may miss somebody. Thus,
a good context modelling approach must take these problems into account to
enable proper reasoning about context information changes to achieve appro-
priate adaptations for the application, and thus provide an experience for the
user that is consistent with the physical world.
Reasoning: Context-aware applications use context information to evaluate
whether there is a change to the user and/or to the environment situation;
taking a decision whether any adaptation to that change is necessary often
requires reasoning capabilities. Reasoning techniques can also be adopted to
derive higher level context information. Therefore, it is important that the
context modelling techniques are able to support both consistency verification,
and reasoning about complex situations.
Usability of modelling formalisms: Context information models are cre-
ated by designers of context-aware applications and are also used by the appli-
cations to manipulate context information. Therefore the important features
of modelling formalisms are the ease with which designers can translate real
world concepts to the modelling constructs and the ease with which the ap-
plications can at runtime use and manipulate context information.
Efficient context provisioning: Efficient access to context information is
3

---

needed which can be a difficult requirement to meet in the presence of large
models and numerous data objects. To select the relevant objects, attributes
for suitable access paths have to be represented in the context modelling. These
access paths represent dimensions along which applications often select con-
text information, typically supported by indexes. These dimensions are often
referred to as primary context, in contrast to secondary context which is ac-
cessed using the primary context. Commonly used primary context attributes
are the identity of context objects, location, object type, time, or activity of
user. Since the choice of primary context attributes is application-dependent,
given an application domain, a certain set of primary context attributes is
used to build up efficient access paths (e.g., spatial indexes if location is a
primary context).
Existing approaches to context information modelling —or context modelling
as they are often referred to—differ in the ease with which real world concepts
can be captured by software engineers, in the expressive power of the con-
text information models, in the support they can provide for reasoning about
context information, and in the computational performance of the reasoning.
Early approaches to context modelling include key-value models and markup
scheme models. Key-value models use simple key-value pairs to define the list
of attributes and their values to describe context information used by context-
aware applications. Markup based context information models use a variety
of markup languages including XML. The introduction of the W3C standard
for description of mobile devices, Composite Capabilities / Preference Pro-
file (CC/PP) [40], saw the first context modelling approaches to use RDF
and included elementary constraints and relationships between context types.
Simple kinds of reasoning over these elementary constraints and relationships
were performed with special purpose reasoners. Mark-up and RDF based con-
text information models have limitations shown in [39,65] that do not make
them very good candidates for generic context information models. Newer
approaches to context modelling use more sophisticated information systems
(database) modelling techniques or knowledge management techniques. They
also employ general purpose reasoning techniques that match their modelling
technique, e.g., first-order logic and description logic. These newer approaches
to context modelling and reasoning address many of the requirements listed
above; however none of them fulfills all the requirements for a generic context
information modelling and reasoning approach.
The goal of this paper is to show the state-of-the-art in context modelling and
reasoning in pervasive computing. We discuss the current approaches and show
the lessons learned in the process. The paper structure is as follows. Sections 2
– 4 describe the three most prominent approaches to context modelling and
reasoning. Section 5 discusses high level abstractions, often called situations,
for combining low level context information into a form more appropriate for
use by context-aware applications. Section 6 addresses the issue of context
4

---

information uncertainty, and shows its impact on context modelling and rea-
soning. Section 7 presents the research on hybrid context models as a lesson
learned from the application of previously presented approaches. Section 8
concludes the paper.
2
Object-role based models of context information
Fact-based context modelling approaches, including the object-role modelling
approach described in this section, originated from attempts to create suffi-
ciently formal models of context to support query processing and reasoning, as
well as to provide modelling constructs suitable for use in software engineering
tasks such as analysis and design. Early context modelling approaches, such as
attribute-value pairs, could not satisfy these requirements, particularly as the
types of context information used by applications grew more sophisticated.
This section is concerned with context modelling approaches that have their
early roots in database modelling techniques. In particular, it focuses on the
Context Modelling Language (CML), which was described in a preliminary
form by Henricksen et al. in 2002 [34] and refined in later publications [32,33].
2.1 CML overview
CML is based on Object-Role Modeling (ORM) [30], which was developed
for conceptual modelling of databases. CML provides a graphical notation
designed to support the software engineer in analysing and formally specifying
the context requirements of a context-aware application. It extends ORM with
modelling constructs for:
• capturing the different classes and sources of context facts discussed in sec-
tion 1: specifically, static, sensed, derived, and user-supplied (“profiled”)
information;
• capturing imperfect information using quality metadata and the concept of
“alternatives” for capturing conflicting assertions (such as conflicting loca-
tion reports from multiple sensors) [32];
• capturing dependencies between context fact types; and
• capturing histories for certain fact types and constraints on those histories.
The formality of ORM and the CML extensions makes it possible to support a
straightforward mapping from a CML-based context model to a runtime con-
text management system that can be populated with context facts and queried
by context-aware applications. Halpin [29] describes the Rmap procedure for
5

---

has mode
synchronous
Communication
s
Communication
s
Channel (id)
Mode (name)
requires device
has channel
permitted to use
Probability
(nr)+
Person
Device
located near
(identity)
(id)
Certainty
engaged in
*
located at
a
located at
[ ]
Key
a
Sensed fact type
Activity
Location
s
Static fact type
(name)
(name)
Profiled fact type
Derived fact type
*
[ ] Temporal fact type
located near(p,d) iff located at(p, l1)
*
a Ambiguous/alternative fact type
and located at (d, l2)
Key/uniqueness constraint

and l1 = l2
Snapshot uniqueness constraint
Alternative uniqueness constraint
engaged in(p1,a) dependsOn located at(p2,l)
Dependency
iff p1 = p2
Quality annotation
Fig. 1. An example CML model.
transforming a conceptual schema to a relational schema, and Henricksen [31]
has developed an extension of Rmap that can be used to map a CML-based
context model to a relational database. However, the formal semantics of ORM
and CML can be leveraged to provide integration with other implementations
such as fact-based reasoners (though it should be noted that some features of
CML—particularly the constructs related to imperfect information—may not
be supported).
Figure 1 illustrates the graphical notation using an example context model.
This example model is designed for use by context-aware communication ap-
plications such as the one described in [33]. The model captures user activities
in the form of a temporal fact type that covers past, present and future activ-
ities; associations between users, communication channels, and devices; and
locations of users and devices (both absolute and relative, where the latter is
represented as a derived fact type).
Each ellipsis in the figure depicts an object type—with the value in parentheses
describing the representation scheme used for the object type—while each box
denotes a role played by an object type within a fact type. The key summarises
the remainder of the notation used in the figure. A detailed discussion of both
6

---

Table 1
Table 2
Example instantiation of the “located
Example instantiation of the “located
at” fact type without alternatives.
at” fact type with alternatives.
Person
Location
Person
Location
Fitzwilliam Darcy Kitchen
Fitzwilliam Darcy Kitchen
Elizabeth Bennet
Study
Fitzwilliam Darcy Dining
Elizabeth Bennet
Study
the model and the software engineering process used in conjunction with CML
can be found in [33].
2.2 Support for reasoning
CML leverages the formality of ORM to support the evaluation of simple
assertions as well as SQL-like queries. One of the novel features of CML is
its ability to support querying over uncertain information (specifically, am-
biguous information represented using the “alternatives” construct) using a
three-valued logic. This can be illustrated using the “located at” fact type
from the model in Figure 1 as an example. Two possible instantiations of this
fact type are shown in Tables 1 and 2. Using the three-valued logic, the asser-
tion “Fitzwilliam Darcy located at Kitchen” evaluates to true with respect
to the first instantiation and possibly true with respect to the second.
To evaluate more complex conditions than can be captured by assertions,
Henricksen et al. define a grammar for formulating situations. Situations are
expressed using a novel form of predicate logic that balances efficient evalua-
tion against expressive power. They are defined as named logical expressions
of the form S(v1, ..., vn) : ϕ, where S is the name of the situation, v1 to vn are
variables, and ϕ is a logical expression in which the free variables correspond
to the set {v1,...,vn}. The logical expression combines any number of basic
expressions using the logical connectives, and, or and not, and special forms
of the universal and existential quantifiers. The permitted basic expressions
are either equalities/inequalities or assertions. Situations can be incrementally
combined to form more complex logical expressions. Examples and further in-
formation can be found in [33].
2.3 Evaluation
One of the main strengths of CML is its support for various stages of the
software engineering process. Its graphical notation supports analysis and de-
7

---

sign of the context requirements of a context-aware application; the relational
representation and situation grammar support run-time representation and
querying. CML also provides more comprehensive support for capturing and
evaluating imperfect and historical information than many of the other context
modelling approaches that are currently in use.
However, CML has several weaknesses. It has a “flat” information model, in
that all context types are uniformly represented as atomic facts. If a hierar-
chical structure is needed, or one particular dimension of context is dominant
from the perspective of querying (as in spatial models, which place greater
importance on location than on other types of information), then other repre-
sentations may be more appropriate. CML also emphasises the development
of context models for particular applications or application domains, and does
not provide the support for interoperability that is found in models such as
Strang et al.’s ontology-based Aspect-Scale-Context model [66]. An attempt
to create a hybrid model that combines the respective advantages of CML and
ontology-based approaches (including support for hierarchical structures and
interoperability) is described by Henricksen et al. in [35]. The development of
hybrid models is also discussed further in Section 7.
3
Spatial models of context information
Space is an important context in many context-aware applications. Most con-
text definitions mention space as a vital factor: e.g., Schilit, Adams and Want
define three important aspects of context as “Where you are, who you are with
and what resources are nearby” [61]. Also, in the most frequently used context
definition by Dey et al. [19] space can be seen as a central aspect of context
entities: “An entity is a person, place or object that is considered relevant
to the interaction between a user and an application, including the user and
applications themselve”—places are spatial entities, and interaction typically
requires some vicinity. Thus, some context modelling approaches give space
and location a preferential treatment. As we will see, it is well suited to organ-
ise and efficiently access context information. Spatial existence also serves well
as an intuitive metaphor for non-physical context information (e.g., virtual in-
formation towers [42] for context-tagged web pages or Pascoe’s Stick-E-Notes
[51]). How people associate certain situations with location can be also seen
in the most common question they ask on a mobile phone: “Where are you?”
What they typically are interested in is not the exact location but the general
situation of the person they are talking to.
8

---

3.1 Context information model
Most spatial context models are fact-based models (see section 2) that organise
their context information by physical location. This could be the location of
the real-world entities which is described in the context information (e.g., the
boundaries of a room), the location of the sensor that measures the context
information, or, for non-physical context information, an associated location
as metaphor (e.g., Stick-E-Notes or virtual information towers).
This location information is either pre-defined (if the entities are static), or it
is obtained by positioning systems which track mobile objects and report their
position to a location management system. In general, two kinds of coordinate
systems are supported by positioning systems:
Geometric coordinates: Represent points or areas in a metric space, such as
the WGS 84 coordinates of GPS which represent the latitude, longitude, and
elevation above sea level of some point on the earth’s surface. Using geometric
functions such as the Euclidian distance allows distance calculation and allows
for nearest neighbour queries. Overlaps of geometric figures can be used to
specify ranges by their geometric extension and determine whether ranges are
included in each other which allows for range queries.
Symbolic coordinates: Symbolic coordinates are represented by an iden-
tifier, such as a room number or the ID of a cell or access point in wireless
telephone or local area networks. In contrast to geometric coordinates there is
no spatial relation offered by symbolic coordinates. In order to allow spatial
reasoning about inclusion (for ranges) and distances (for nearest neighbours)
explicit information about the spatial relations between pairs of symbolic co-
ordinates has to be provided. Note that this location model also is applicable
if there is no explicit modelling of space but only relations between objects
(as in [52]).
Spatial context models can be described along the tiers of spatial ontologies
proposed by A. Frank [24]:
• Tier 0 is the ontology of the physical reality. It is based on the assumption
that there is exactly one real world; hence, for every property in the world
and for a given point in time-space there is a single value.
• Tier 1 includes observations of reality and is the first tier that can be ac-
cessed in context models. Here, a value can be derived at a location with a
given observation type. The type determines the measurement scale of the
value (e.g., nominal or rational) and the measurement unit (e.g., metres or
seconds). For spatial values, a coordinate system must be given. Values nor-
mally have a limited accuracy due to observation errors. Fact-based context
models are typically situated on that tier.
9

---

• In tier 2, single observations are grouped with individual objects that are
defined by uniform properties. Now, the value of an observation is the state
of a whole object, given by an identifier. Frank only considers physical ob-
jects in this tier, i.e., “things which exist in the physical world and can
be observed by observation methods”. They have a geometric boundary in
the world, but it can change over time (e.g., dunes or fluids). Up to tier
2, the ontology tiers cover data that can be seen as objective reality—you
can send out a team of geographers or students to model physical objects
and they will come to an agreement about their observations. Thus, this
kind of information can be easily shared between different context-aware
applications.
• In tier 3, the socially constructed reality is represented. Social reality in-
cludes all objects and relations that are created by social interactions. Such
properties are classified and named within the context of administrative,
legal or institutional rules. Object names belong to this tier since they are
assigned by culture; for many important things (but not all) there are func-
tions to determine the name and to find the object by name in a certain
environment.
• Finally, in tier 4 the rules are modelled that are used by cognitive agents
(both human and software) for deduction. This tier is normally built into
database query languages, applications or reasoning engines of knowledge
based systems. Ontology based models of context information (see Section 4)
typically cover all tiers up to this level.
Although the tiered model of Frank is just an abstract conceptualization of
different (spatial) representations of the world, it is useful to distinguish be-
tween various implementations of spatial context models (as can be seen in
[7]). For example, fact-based models like the Context Modelling Language of
Henricksen et al. (Section 2 and [33]) cover tier 1–3, and the grammar used
to define situations is located at tier 4.
The spatial context model developed in the Nexus project (called Augmented
World Model [50]) is an object-based class hierarchy of context information
that supports multi-inheritance (a camera can be both a MobileObject and
a Sensor), multi-attributes (a MobileObject can have multiple instances
of its position attribute that differ in their meta data, e.g., the measurement
time), and both a geometric coordinate system (that supports multiple spatial
reference systems) and a simple symbolic location system (based on spatial re-
lationships). Most object classes inherit from the class SpatialObject, which
makes the Augmented World model inherently spatial: almost all objects (real
and virtual) are modelled with a location, either by their physical location or
by a meaningful association metaphor (like the location of a virtual infor-
mation tower for web sites). Because the Nexus context model was designed
to be sharable between different context-aware applications in a potentially
global scope and thus to be scalable to a high amount of context data [27]. In
10

---