Hierarchical Situation Modeling and Reasoning for Pervasive Computing

Hierarchical Situation Modeling and Reasoning for Pervasive Computing


Stephen S. Yau and Junwei Liu
Arizona State University
Tempe, AZ 85287-8809, USA
{yau, junwei.liu}@asu.edu


Abstract
environment, system, or users, such as location,

available bandwidth and a user’s schedule [1, 2]. A
Situation awareness is one of the most fundamental
pervasive computing environment involves a set of
features of entities in pervasive computing cooperative entities, each of which has related context
environments to dynamically adapt their behavior to
data. In order to support situation-aware adaptation of
situation changes to satisfy user requirements,
the entities in pervasive computing environments, it is
including security and privacy. In order to support
necessary to model and specify context and situation in
situation-aware adaptation, it is necessary to model
a way such that multiple entities can easily exchange,
and specify context and situation in a way such that
share and reuse their knowledge on context and
multiple entities can easily exchange, share and reuse
situation.
their knowledge on context and situation. In this paper,
With recent development of Semantic Web [3],
an OWL-based situation ontology to model situation
ontology has been widely used to facilitate knowledge
hierarchically to facilitate sharing and reusing of
sharing and reusing. For pervasive computing
situation knowledge and logic inferences is presented.
environments, using ontology to model context and
The conversion of OWL situation ontology situation enables multiple entities to have common
specifications to the First-Order Logic (FOL)
understanding of the context and situation during
representations, and the performance of FOL rule-
collaboration. Web Ontology Language (OWL) [4] is a
based reasoning in terms of problem size and time are
W3C standard for representing machine interpretable
discussed.
knowledge in Semantic Web. OWL provides three

increasingly expressive sublanguages: OWL Lite, OWL
Keywords: Situation awareness, situation modeling,
DL and OWL Full. OWL DL has the maximum
situation reasoning, pervasive computing, Semantic
expressiveness, and is computationally complete and
Web, ontology and OWL.
decidable. In addition, it supports formal logic

reasoning [4]. It is called OWL DL due to its

correspondence with Description Logics (DL).
1. Introduction
In this paper, an OWL-based situation ontology will

be presented for context and situation knowledge
In pervasive computing environments, various
modeling. The situation ontology uses OWL DL to
entities are expected to integrate and cooperate
model context and situation in a hierarchical way such
seamlessly to achieve user objectives in an anywhere-
that the specifications for context and situation can be
and-anytime fashion. Situation awareness (SAW) is
easily shared and reused among multiple entities.
the capability of the entities in pervasive computing
Furthermore, the use of OWL DL supports formal
environments to be aware of situation changes and
logical reasoning over the situation ontology for
automatically adapt themselves to such changes to
consistency checking, subsumption reasoning, implicit
satisfy user requirements, including security and
knowledge inference. We will also discuss the
privacy. SAW is one of the most fundamental features
conversion of OWL situation ontology specifications
to support dynamic adaptation of entities in pervasive
to the First-Order Logic (FOL) representations and the
computing environments. A situation is a set of
performance of FOL rule-based reasoning in terms of
contexts in the application over a period of time that
problem size and time.
affects future system behavior. A context is any

instantaneous, detectable, and relevant property of the

---

2. Current State of the Art
various devices across heterogeneous networks.

Hence, it must be machine-interpretable.
Context modeling for pervasive computing has been
Semantic-based: The modeled situation
well studied in recent years. Composite Capabilities /
knowledge must have well-defined semantics so
Preferences Profile (CC/PP) [5] created by the W3C,
that multiple entities in different environments can
and User Agent Profile (UAProf) created by the WAP
understand and interoperate with each other
Forum [6] and their extensions [7, 8], are Resource
correctly.
Description Framework (RDF) based approaches that
Reusable: The modeled situation knowledge
describe the context information related to the mobile
should be reusable to reduce the information
devices. The Context Broker Architecture (CoBrA)
needed to be transferred and processed.
system [9] has a set of context entities modeled using
Extensible: Different pervasive computing systems
OWL, and uses broker-centric agent architecture to
will have different domain specific knowledge. The
acquire, share, reason and protect context information.
modeling approach must support extension of such
The Aspect-Scale-Context (ASC) model and Context
domain specific knowledge.
Ontology Language (CoOL) are introduced for context
Logic inference: The modeled situation knowledge
modeling and can be used in DAML-S model to
should support formal logic inference for
represent the context information of services in [10].
verification and reasoning.
The Context Ontology (CONON) context modeling

approach [11] models an upper ontology for context
4 OWL-based Situation Ontology
and uses OWL DL language to represent and reason

over CONON. These approaches all focus on modeling
Due to the complexity of pervasive computing
context, which is not sufficient for situation modeling.
environments, it is impossible to enumerate all possible
Among the approaches for modeling situation, the
contexts and situations in a single ontology. Our
following are four major ones: In Context Toolkit [12],
situation ontology only models the upper ontology for
situation is modeled on a system level as the
context and situation by defining a set of core classes
aggregation of context, but there is no language level
and relations using OWL DL. For each pervasive
situation modeling. Situation calculus and its
computing application, specific domain-related
extensions [13, 14] model situation based on the
knowledge can be easily extended. Consider a smart
effects of actions and events, and consider situation as
conference environment scenario: “If the user is in the
a complete state of the world. Hence, situation is not
conference room and the light is on, then the user is
fully described. This causes the well-known frame
ready for a meeting”. Complicated situation
problem and ramification problem [13]. A core SAW
(ReadyForMeeting) is derived from the basic contexts
ontology [15] models situation as a collection of Goals,
(location and light). Based on the conceptual model
SituationObjects and Relations using UML, and can be
presented in [16, 17], the contexts in our OWL-based
converted to OWL representation. How to model
situation ontology are aggregated as situations and
context, derive situation based on context and reuse
complicate situations are composed of simple
simple situation definition to compose complicated
situations in a hierarchical structure to facilitate the
situation are not considered. A conceptual model for
sharing and reusing of context and situation knowledge
context and situation for service-based systems and a
since the semantics of context/situation specification
situation specification example based on the can be clearly understood by all entities in the system.
conceptual model using F-logic are presented in [16,
The hierarchical structure of situation ontology can be
17].
roughly divided to two layers: context layer and

situation layer. By separating context layer and
3 Requirements of Situation Modeling
situation layer, we separate the context acquisition and

processing from the situation evaluation, which gives a
Pervasive computing environments usually involve
clearer view of SAW and facilitates SAW development
entities with different platforms connected through
[12].
heterogeneous wired and wireless networks. These
Context layer: Context layer models context
entities need to interoperate with each other to achieve
definition, contextual data of entities and various
user objectives. To make these entities situation aware
context value domains in an upper ontology with the
in such dynamic environments, the situation modeling
following ontology classes and relations:
approach must satisfy the following requirements:
Context class: The context class is the super class
Machine interpretable: The modeled situation
for all the contexts in pervasive computing
knowledge must be easily exchanged among
environments. Any instance of the context class

---

Figure 1. The situation ontology
represents a conceptual context, such as
context corresponding to different context value
availableBandwidthContext or locationContext.
scales. For example, the available-MemoryContext
Different contexts can be indexed hierarchically
may have two context value domains
based on class hierarchy, such as deviceContext,
corresponding to scales of MB and Bytes.
environmentContext and userContext in Figure 1.
dataContextOperation / booleanContextOperator
contextData class: An instance of contextData will
class: The context value interpretation between
represent a certain context, and have associated
different domains is modeled as dataContext-
host ID, timestamp and context value. All the
Operation. The booleanContextOperor is a special
contextData instances, which represent the same
type of context value interpretation which returns a
context and have the same host ID, define a
Boolean value and is used to compose atomic
specific context instance in the system within a
situation definition in the situation layer. Each
certain time period. Any Entity in pervasive
booleanContextOperor instance may associate with
computing system can specify related contextual
a rdf:Property by the URI of the property, such as
data using property relatedContextData.
owl:sameAs or location:sameFloor,
contextValue class: The actual value of the context
Situation layer: The situation layer is built on top
is modeled by contextValue class. The context
of the context layer to aggregate context into situations
value in pervasive computing environments can be
and to compose complicated situations of simple
simple, such as the float number temperature value,
situations via logical composition and temporal
or complicated data structures, like a location
composition. Whether an entity in a pervasive
involving address number, street name, city, state
computing environment satisfies a certain situation or
and zip code. To support such variation, the
not is specified via satisfies and notSatisfy properties.
contextValue class can have multiple subclasses to
Situation class: The Situation class is the super
deal with different types of values. User can define
class for all the situations in pervasive computing
a complex ontology class streetLocation class as a
environments. Different situations form a hierarchy
subclass of contextValue class. Simple data types
based on their derivation and can be divided to two
like float or Boolean can be wrapped into
major categories: atomicSituation and
floatValue or booleanValue classes.
compositeSituation.
contextValueDomain class: For each context, the
atomicSituation class: The atomicSituation class
valid domain of its value is defined by
represents all the basic situations whose value is
contextValueDomain class with hasDomain
directly derived from the value of a single
property. Each contextValue instance also belongs
contextual data with respect to certain operator and
to a certain context value domain via inDomain
argument. The situation layer links to the context
property. Multiple context value domains of a
layer with three properties: atomicSituation:

---

hasContext, hasBOperator and hasArgument. The
needed to be specified can be greatly reduced
evaluation of the atomicSituation has the semantic
without losing any knowledge.
of “The atomic situation is satisfied by an entity iff

the entity has a related contextual data
6. FOL Rule-based Reasoning
representing the context and the Boolean context

operator over the contextual data value and the
Our OWL-based situation ontology also supports
argument returns true.”
reasoning about whether an entity satisfies a certain
compositeSituation class: The compositeSituation
situation or not by FOL rule-based reasoning. To
class represents complicated situations: either the
achieve this, the situation ontology specifications are
logical composition over other situations first converted to FOL representations and then FOL
(conjunctionSituation, disjunctionSituation and rule-based reasoning is performed using FOL provers.
negationSituation), or the temporalSituation whose

value is derived from the value history of another
6.1 Converting OWL Situation Specifications
situation. All these four subclasses of to FOL Representations
compositeSituation are disjoint with each other.

Although supporting all the three types of logical
The basic idea of converting OWL specifications to
composition is redundant, it is more convenient for
FOL representations is to translate class references to
situation specification. A temporalSituation
unary predicates, properties to binary predicates, and
instance must have associated temporalOperator,
OWL axioms (such as owl:sameAs) to FOL rules [20].
such as alwaysTrue or onceTrue, and timePeriod.
In [11], FOL reasoning over OWL ontology was also
Using the situation ontology, the above-mentioned
discussed.
smart conference scenario can be specified as
To evaluation if there is any entity u satisfying a
“situation ReadyForMeeting is the conjunction of two
situation s, we can decompose the situation based on
atomic situations InConferenceRoom and LightOn”,
the situation hierarchy and generate FOL rules from
where InConferenceRoom situation is “the location-
the OWL situation specifications according to Table 1.
Context value is same as crLocation” and LightOn
By recursively performing these transformation rules,
situation is “the lightContext value is true”.
the composition tree of the situation and a set of FOL

rules can be generated. For example, the composition
5. OWL Ontology Reasoning
tree and rules of ReadyForMeeting situation defined in

Section 4 are shown in Figure 2.
Various OWL ontology inferences over our

situation ontology can be performed by DL reasoners,
Table 1. Transformation rules from OWL
such as RACER [18] and Pellet [19]. The following
situation specifications to FOL rules
inferences are commonly used:
atomicSituation:
p = the associated property of o
Consistency checking: Check whether a situation
hasContext: c
(?u
hasContextData ?cd )

specification is consistent by reasoning if there is
hasBOperator: o
∧(?cd
present c)
any inconsistent ontology class or inconsistent
hasArgument: a
ontology instance in the specification.
∧(?cd
hasValue ?v) ∧ (?v
p
a)
Subsumption reasoning: Check whether an
⇒ (?u satisfies s)
ontology class subsumes another. This is useful to
conjunctionSituation: (?u
satisfies s ) ∧ (?u
satisfies
s )
1
2
identify implicit subsume relations in situation
composedBy:
∧...∧ (?u
satisfies s )
n
specifications.
s , s ,...s
⇒ (?u satisfies s)
1
2
n
Implicit knowledge reasoning: Reason about the
disjunctionSituation:
(?u
satisfies s ) ⇒ (?u
satisfies s)
implicit knowledge conveyed by situation
1
composedBy:
(?u
satisfies s ) ⇒ (?u
satisfies s)
specifications. For example, we can reason implicit
2
knowledge “room401 sameFloor room415” from
s , s ,...s
...
1
2
n
explicitly specified knowledge “room401
(?u
satisfies s ) ⇒ (?u
satisfies
s)
n
sameFloor room402” and “room402 sameFloor
negationSituation:
(?u
notSatisfy s ) ⇒ (?u
satisfies
s)
room415” if the sameFloor is a transitive property.
composedBy: s

For pervasive computing applications, it is

impossible for designers and users to explicitly
With user-defined properties and the extension of
specify all the knowledge. With implicit knowledge
SWRL [21], more complicated operators can be
reasoning capability supported by OWL, the facts
supported. For example: OnSameFloorAsConference-

---

(?u
hasContextData ?li) ∧ (?li
present
Light)
The size of the FOL problem in
(?u
satisfies InConferenceRoom)
∧(?li
hasValue ? v) ∧ (?v
owl : sameAs
TrueValue)
terms of the number of functions
∧(?u
satisfies LigthOn)
⇒ (?u
satisfies LightOn)
and formula increases when the
⇒ (?u
satisfies Re adyForMeeting)
size of the OWL specification
increases. It is noted that in our
experiments, all the situation
specifications are defined using
(?u
hasContextData ?lo) ∧ (?lo
present
Location)
the same ontology, and hence the
∧(?lo
hasValue ?v) ∧ (?v
owl : sameAs
crLocation)
number of predicates does not
⇒ (?u
satisfies InConferenceR
)
oom
change.

The time needed to convert an
Figure 2. A composition tree example
OWL specification to FOL
Room situation can be defined based on the sameFloor
problem is negligible. Even for a large OWL
property of location class, and the rule is
specification including 2000 RDF triples, the
(?u
hasContextData ?lo) ∧ (?lo
present
Location)
conversion only takes about 160 microseconds.
∧(?lo
hasValue
? v) ∧ (? v )
sameFloor crLocation
The time needed for FOL rule-based reasoning
⇒ (? u satisfies OnSameFloorAsConferenceRoom)
increases dramatically when the size of the OWL
Furthermore, SWRL build-ins can also be used to
specification increases, especially when the OWL
reason whether a booleanContextOperator returns true
specification size is over 1000 RDF triples.
value. For example, SWRL building-in
These observations indicate that FOL rule-based
swrlb:greatThanOrEqualTo can be used to reason the
reasoning is feasible for situation reasoning for non-
situation HasBroadBandConnection.
time-critical applications, especially when the size of
(?u
hasContextData ? nb)
the situation specification is small. For large situation
∧(?nb
present NetworkBandwidth) ∧ (? nb
hasValue
?v)
specifications, each single situation reasoning task
∧(?v
greatThanOrEqualTo "256KB")
usually only requires a small part of the specification
⇒ (?u satisfies HasBroadBandConnection)
(?v
inDomain ?d ) ∧ ("256KB"
inDomain ?d )
1
2
∧(?d
sameAs
?d ) ∧ (?v
hasFloatValue
? f )
1
2
1
∧("256KB"
hasFloatValue
? f )
2
∧(? f
swrlb : greatThanOrEqualTo f )
1
2
⇒ (?v greatThanOrEqualTo "256KB")

6.2. Experimental Results of FOL Rule-based
Reasoning

In this section, the performance of FOL rule-based
reasoning in terms of problem size and time will be
discussed.
In our experiments, the Jena2 toolkit [22] was used

to generate and parse OWL specifications and convert
OWL specifications to DFG problems supported by
SPASS FOL theorem prover [23]. The RDF triple size
of the situation specifications used in our experiments
varied from 56 to 1980. We compared the size of FOL
problems in terms of the number of functions,
predicates and formula. We also compared the average
time needed for the conversion from OWL
specifications to FOL problems and the average time
for the execution of FOL reasoning. The hardware used
in our experiments is Dell OPTIPLEX GX820 Desktop
with 3GHZ CPU and 1GB memory. The results are
shown in Figure 3.
From these experimental results, we have the

Figure 3. Experimental results of FOL Rule-
following observations:
based Reasoning

---

rather than the entire specification. Therefore, when
[5] W3C. Composite Capabilities / Preferences Profile
OWL specification is converted to FOL problem; only
(CC/PP), Available at: http://www.w3.org/Mobile/CCPP/
the related portion of the specification needs to be
[6] WAPFORUM. User Agent Profile (UAProf). Available
converted so that the reasoning time is reduced. As for
at: http://www.wapforum.org.
time-critical applications, FOL rule-based situation
[7] Albert Held, Sven Buchholz and Alexander Schill,
“Modeling of context information for pervasive computing
reasoning is not applicable, and specially designed and
applications”, Proc. 6th World Multiconference on Systemics,
time-efficient processes need to be used.
Cybernetics and Informatics (SCI2002), 2002.

[8] Indulska, J., Robinson, R., Rakotonirainy, A., and
7. Conclusions and Future Work
Henricksen, K. “Experiences in Using CC/PP in Context-

Aware Systems”, Proc. 4th Int’l Conf. on Mobile Data
In this paper, a hierarchical OWL-based situation
Management, 2003, pp. 247-261.
ontology, which satisfies all the requirements in
[9] H. Chen, T. Finin, A. Joshi, “Using OWL in a Pervasive
Computing Broker”, Proc. Workshop on Ontologies in Open
Section 3, is presented. The situation ontology models
Agent Systems, 2003, pp. 9-16.
the core upper ontology for contexts and situations in
[10] T. Strang, C. Linnhoff-Popien, and K. Frank, “CoOL: A
pervasive computing environments using machine-
Context Ontology Language to enable Contextual
interpretable semantic-based OWL DL. The Interoperability”, Proc. 4th IFIP Int’l Conf. on Distributed
hierarchical situation ontology facilitates sharing and
Applications and Interoperable Systems, 2003, pp. 236-247.
reusing of situation information, and can be easily
[11] X. Wang, D. Zhang, T. Gu and H. Pung, “Ontology-
extended with domain specific knowledge. The logic
Based Context Modeling and Reasoning using OWL”, Proc.
inferences supported by the situation ontology,
2nd IEEE Ann. Conf’ on Pervasive Computing and
including the conversion of OWL situation ontology
Communications Workshops, 2004, pp. 18-22.
[12] Anind K. Dey, “Providing Architectural Support for
specifications to FOL representations and the
Building Context-Aware Applications”, PhD thesis, College
performance of FOL rule-based reasoning in terms of
of Computing, Georgia Institute of Technology, 2000.
problem size and time, are also discussed. We have
[13] J. A. Pinto, Temporal Reasoning in the Situation
shown that the situation can be effectively modeled
Calculus, PhD Thesis, University of Toronto, 1994.
using our OWL-based situation ontology, and that
[14] J. McCarthy., “Situation Calculus with Concurrent
logic reasoning can be performed on the situation
Events and Narrative”, http://wwwformal.stanford.edu/jmc/
ontology specifications.
narrative/ narrative.html, 2000.
Future research in this area includes improving
[15] C. J. Matheus, M. M. Kokar, and K. Baclawski, “A Core
situation ontology with temporal logic to reason the
Ontology for Situation Awareness”, Proc. 6th Int’l Conf. on
Information Fusion, 2003, pp. 545 –552.
values of temporalSituations, and developing [16] S. S. Yau, D. Huang, H. Gong and H. Davulcu,
algorithms to minimize the FOL problem size
“Situation-Awareness for Adaptable Service Coordination in
converted from situation ontology specifications.
Service-based Systems”, Proc. 29th Ann. Int'l Computer

Software and Application Conference, 2005, pp. 107-112.
Acknowledgment
[17] S. S. Yau, D. Huang, H. Gong, and Y. Yao, "Support for
The work reported here is supported by the National
Situation-Awareness in Trustworthy Ubiquitous Computing
Science Foundation under the grant number ITR-
Application Software", Jour. of Software Practice and
Engineering, to appear.
CYBERTRUST 0430565. The authors would like to
[18] V. Haarslev and R. Möller. “Racer: A Core Inference
thank Dazhi Huang of Arizona State University for
Engine for the Semantic Web”, Proc.2nd Int’l Workshop on
many valuable discussions.
Evaluation of Ontology-based Tools, 2003, pp. 27-36.

[19] Pellet. Pellet - OWL DL Reasoner, 2003.
References
http://www.mindswap.org/2003/pellet.
[1] S. S. Yau, Y. Wang, and F. Karim, "Development of
[20] Using a First Order Logic Prover with OWL. Available
Situation-Aware Application Software for Ubiquitous
at: http://wonderweb.man.ac.uk/owl/first-order.shtml
Computing Environments", Proc. 26th Ann. Int'l Computer
[21] SWRL: A Semantic Web Rule Language Combining
Software and Applications Conf., 2002, pp. 233-238.
OWL and RuleML. Available at:
[2] S. S. Yau, F. Karim, Y. Wang, B. Wang, and S.Gupta,
http://www.w3.org/Submission/SWRL/.
"Reconfigurable Context-Sensitive Middleware for Pervasive
[22] Jena2 Semantic Web Toolkit. Available at:
Computing," IEEE Pervasive Computing, 1(3), July-
http://www.hpl.hp.com/semweb/jena2.htm.
September 2002, pp.33-40.
[23] C. Weidenbach, U. Brahm, T. Hillenbrand, E. Keen, C.
[3] T. Berners-Lee, J. Hendler, and O. Lassila, “The
Theobalt, and D. Topic, SPASS version 2.0. Automated
Semantic Web”, Scientific American, May 2001, pp. 34-43.
Deduction – CADE-18, LNCS 2392, 2002, pp. 275–279.
[4] OWL Web Ontology Language, Available at:
http://www.w3.org/TR/owl-ref/.

---