This paper addresses the problem of discovering Web of Things (WoT) agents, also known as servients, that can interact in a mediated or peer-to-peer fashion to form compound systems. We develop a framework that relies on the W3C Thing Description (TD) and Semantic Sensor Network (SSN) ontologies, which provide semantics for the physical world entities WoT servients are associated with. We formulate the problem of WoT discovery as an abductive reasoning problem over knowledge bases expressed in terms of TD and SSN concepts, where new semantic relationships between existing systems lead to the creation of other, larger systems. We then address the specific case of EL++ knowledge bases, a fragment of Description Logic, for which we leverage the mathematical framework of Abductive Logic Programming to provide a concrete algorithm for abduction that terminates in polynomial time. We illustrate the feasability of our approach on an experimental industrial workstation, equipped with micro-controllers capable of storing and exchanging RDF data in binary format ( RDF store with EXI4JSON serialization).
One of the promises of the Web of Things (WoT) is to bring more autonomy in
automation systems by the automatic mash-up of Web agents [
These semantically described WoT systems may be seen as intelligent
systems, as autonomy is regarded as an important characteristic of intelligence [
The problem we address in this paper is that of automatically discovering WoT agents (servients) for which a potential interaction in a MAS exists. That is, we aim at building a ‘graph of interactions’ between servients, potentially at Web scale. For instance, in a mediated scenario, a WoT client could execute the following procedure to empty a water tank by opening a valve when the tank is full: 1. send GET coap://{IP1}/watertank/overflow 2. if returned value is true,
(a) then send PUT coap://{IP2}/valve/status ‘true’ 3. sleep for 1s and go to step 1.
Here, semantic discovery consists in finding the pair of servients (IP1, IP2)— an edge in the graph of interactions—, such that one exposes a boolean value representing the detection of overflow in a water tank and the other exposes a writable boolean value to control a valve in a water circulation circuit.
In this paper, we address the problem of WoT discovery by relying on Semantic Web technologies. More precisely, we express possible servient interactions in terms of the relations between the physical world entities they are associated with. In the remainder of the paper, we speak of ‘semantic discovery’. The paper is organized as follows: we first introduce the semantic models one can use to associate servients with physical world entities, most importantly the Semantic Sensor Network (SSN) ontology; then, we formulate the problem of semantic discovery as an abductive reasoning task on the SSN class of System; we then present an algorithm for E L++ ontologies by leveraging the mathematical framework of Abductive Logic Programming; we finally present experimentations on an prototype workstation equipped with micro-controllers, and conclude on the provided results. 2
Several discovery mechanisms can coexist in the Web of Things [
hypermedia catalogue, on which plain Web resources can be registered and annotated with RDF-like statements. Annotations can either be used to connect resources with each others or to connect them with semantic resources from an external knwoledge base, e.g. an RDF store. The IETF Resource Directory provides similar functionalities but it relies on the IETF CoRE Link format for resource annotations, which targets constrained environments by providing concise serializations5. Both proposals provide simple query functionalities (key/value filtering).
The Eclipse Thingweb project, that implements W3C standards for the Web
of Things, includes an implementation of a ‘Thing Directory’6, inspired by the
IETF specification but allowing arbitrary RDF annotations, like Hypercat. WoT
servients can register so-called ‘Thing Descriptions’ (TDs) on a Thing Directory.
A TD is an RDF document that links physical world entities (instances of the
concept of Thing) to Web resources [
This problem of identity of physical world entities is well-known in the Semantic Web community and best practices have emerged to distinguish semantic resources from other Web resources: one should exclusively use hash URIs or HTTP 303 redirection to identify them7. However, in the context of WoT, uniquely identifying all physical world entities involved in a system is a challenge. Even in very simple cases, there is no obvious way to identify inanimate objects (like the water tank in our introductory example). A convention for manufactured products could be to use their serial number. Another convention could be to use arbitrary identifiers encoded in RFID tags. However, even if one assumes there exists a widely agreed upon addressing mechanism to unambiguously give an IRI to any physical world entity, this kind of approach requires the deployment of a vast and heterogeneous network to combine near-field communication (to expose a product serial number) with wired local connectivity and other wireless technologies. This high human integration effort hinders, to some extent, the vision of WoT as a network of autonomous systems.
An alternative to this approach is to leverage the model theoretical semantics of the TD model and Semantic Web technologies. By means of reasoning, the existence of certain physical world entities can be inferred from statements contained in TD documents. Indeed, TDs can contain arbitrary statements about Things, along with the links between these Things and Web resources, by using
any RDF vocabulary. Numerous already existent vocabularies can be used, all
of them being grounded in Descirfpation Logic (DL). The most important one is
the SSN ontology [
WoT servients exposing TDs annotated with SSN, SEAS and SAREF form a promising basis for semantic discovery. A typical TD would expose a Thing as an SSN System or a SOSA FeatureOfInterest, whose Properties are exposed via Web resources. Interacting with the servient corresponds to either a SOSA Observation or a SOSA Actuation. SAREF defines more specific concepts like TemperatureSensor and Temperature (specializations of System and Property, respectively). Semantic discovery would then consist in performing automated reasoning on the statements from various TDs registered on a Thing Directory.
DL concepts for industrial equipment would be required for fine-grain discovery in cyber-physical systems. In our introductory example, concepts for water tanks and valves can be found in the industrial standard eCl@ss9: 27309210 (reservoir/tank for hydraulics), 27292200 (pneumatic valve), 27292300 (proportional valve). It is also possible to combine SSN with ontologies for physical quantities and units like QUDT10 or OM11.
In the following, we formalize the problem of semantic discovery in the Web of Things in terms of DL reasoning. 3
Every WoT servient i exposes in the form of a TD a set of logical assertions Ai (called an ABox) with respect to a shared set of axioms C (called a CBox). We denote A the ABox Si Ai and KB the knowledge base defined as A [ C.
We denote NI the set of individuals (i.e. Web resources) in A. As argued in
A Sec. 2, we do not assume that there exists a global adressing mechanism to give an IRI to any physical world entity. As a consequence, a 2 NIAi and b 2 NIAj (i 6= j) may designate the same entity, i.e. the unique name assumption does not generally apply to WoT knowledge bases. But it also means that entities potentially useful for discovery may not be represented in the knowledge base at all. In this context, deductive reasoning would not be sound if potential servient interactions involve entities whose existence can neither be asserted nor inferred. However, in many cases, their existence can reasonably be simply assumed, so that deduction leads to the expected conclusions. We formalize the problem of
semantic discovery in the Web of Things as an abduction problem, to compute such assumptions.
Definition 1. [
In our case, we aim at discovering new possible systems by making various WoT servients interact. Semantic discovery can therefore be formulated as the abduction of role assertions between individuals of two or more distinct ABoxes and possibly fresh individuals, such that new instances of System are created in the overall knowledge base.
Definition 2. WoT semantic discovery on a knowledge base KB = Si Ai [ C is the abductive reasoning task where = System(a) and KB0 is a set of role assertions for which there exists i; j, such that NIKB0 \NIAi 6= ; and NIKB0 \NIAj 6= ;.
We do not consider class assertions in KB0 to avoid trivial solutions like KB0 = fSystem(a)g, where a is a fresh individual. In practice, one can exploit the mereologic relation hasSubSystem to create a new system as the combination of two or more sub-systems.
Example 1. Let us define a knowledge base for our introductory example, as would be available on a Thing Directory:
A1 = f27292200(valve); A2 = f27273201(sensor); href(valve; coap://192.168.0.1/valve/status)g href(sensor; coap://192.168.0.1/tank/overflow); 27273201(tank); isHostedBy(sensor; tank)g C = fValveControlSystem v System;
Here, 27292200, 27273201 and 27273201 are the eCl@ss concepts for pneumatic valve, level sensor, and water tank (respectively). We define here the role href as a direct link from a Thing instance to a Web resource, which is a simplification of the original TD model.
The following axioms are a solution to semantic discovery on the above knowledge base:
KB0 = fhasSubSystem(a; valve); hasSubSystem(a; sensor)g
In the case where interaction between servients is mediated, the mediator can simply access the Thing Directory’s knowledge base after it is added KB0. However, in a peer-to-peer setup, local ABoxes (i.e. TDs stored on the servient themselves) must be updated with the results of semantic discovery, in order for all servients involved in a new system to have sufficient knowledge about it. This relates to the notion of explanation.
Definition 3. [
KB
Any servient involved in a newly discovered system should be updated with a set of statements that would allow it to infer from its ABox alone the class assertion axiom used for discovery.
A0i = E n Ai.
Definition 4. Let E be an explanation over KB [ KB0 for an axiom of the form System(a). The update ABox of a WoT semantic discovery in a peer-to-peer system is the ABox A0 = Si A0i, such that for all Ai where NIAi \ NIE 6= ;,
Given Definition 4, it then holds that (Ai [ A0i) [ C j= System(a). One can further note that update ABoxes can be computed incrementally. That is, if Ai 0 is the update ABox resulting from a first discovery on servient with ABox Ai, when discovery is performed a second time, the new update ABox A0i0 can be computed against Ai [A0i, such that Ai \A0i0 = ;. It is indeed likely that servients 0 enter the network at different times over the lifecycle of an industrial system. Example 2. The update ABox for Example 1 is the following:
A01 = fhasSubSystem(a; sensorg
A02 = fhasSubSystem(a; valveg
One can note in Example 2 that the performed update is of little value as long as the valve has no knowledge of the Web resource to access the level sensor value (or as long as the sensor has no knowledge of the valve status update Web resource). To include them in their respective update ABox, one can modify C by adding restrictions on href to sub-concepts of System. In general, the value of semantic discovery depends on the axioms present in C. We give more examples of axioms used for discovery in Sec. 5 (Example 3). 4
In this paper, we focus on semantic discovery with E L++ knowledge bases, the
only tractable fragment of DL. There exists other works addressing ABox
abduction on other DL fragments [
Classification of E L++ knowledge bases can be computed in polynomial time,
as first introduced by Baader et al [
EL++ Classification For an extensive documentation of the original classification algorithm and the semantics of E L++, we refer to Baader et al.’s technical report. oDfetfihneiftoiormn 5f. g[2(]aL2et NBIC)Canbed tRhe set of concept names and nominal concepts a C C be the set of role names in C. Let C1; C2 2 BCC [ f>g, D 2 BCC [ f>; ?g and r; s; r1; r2 2 RC.
C is an E L++ normal form if any axiom in C is one of:
C1 v D C1 u C2 v D
C1 v 9r:C2 9r:C1 v C2
r v s r1 r2 v s
Any E L++ knowledge base can be emulated by a CBox C in normal form. Class assertions C(a) are rewritten fag v C and role assertions r(a; b) are rewritten fag v 9r:fbg. In the following, we assume all knowledge bases are in normal form.
Baader et al.’s algorithm consists in applying eleven completion rules to a normalized knowledge base C, to construct a mapping S, such that for C 2 BCC, S(C) BCC [f>; ?g and a mapping R, such that for r 2 RC, R(r) BCC BCC. Deciding whether C entails a given class inclusion can then be decided by a single look-up of S or R. Briefly: – if D 2 S(C), it implies that C j= C v D – if (C; D) 2 R(r), it implies that C j= C v 9r:D
In the present paper, we reformulate Baader et al.’s algorithm in terms of logic
programming [
from DL constructs to FOL formulas is defined (C); (r); (a) map to variables
(D 2 S(C)) = s( (C); (D)) ((C; D) 2 R(r)) = r( (r); (C); (D)) (C v D 2 C) = subClassOf( (C); (D)))
(fag) = objectOneOf( (a)) (C u D) = objectIntersectionOf( (C); (D))
(9r:D) = objectSomeValuesFrom( (r); (D)) (r v s 2 C) = subObjectPropertyOf( (r); (s))
(r1 r2) = objectPropertyChain( (r1); (r2))
One may note that our definition of associates DL axioms to plain formulas.
This differs from classical logic programming embeddings of DL, which turn
axioms into rules (e.g. with Datalog [
Definition 7. The logic program P for E L++ classification is defined as follows: true (D 2 S(C)) (D 2 S(C)) ((C; D) 2 R(r)) (E 2 S(C)) (? 2 S(C)) (S(D)
S(C)) ((C; D) 2 R(s)) (C 2 S(C)) (C0 2 S(C)) ^ (C0 v D 2 C) (C1 2 S(C)) ^ (C2 2 S(C)) ^ (C1 u C2 v D 2 C) (C0 2 S(C)) ^ (C0 v 9r:D 2 C) ((C; D) 2 R(r)) ^ (D0 2 S(D)) ^ (9r:D0 v E 2 C) ((C; D) 2 R(r)) ^ (? 2 S(D)) (fag 2 S(C) \ S(D)) ^ (C ; D) ((C; D) 2 R(r)) ^ (r v s 2 C) (CR1) (CR2) (CR3) (CR4) (CR5) (CR6) (CR10) 12 In the present work, we discard rules 7-9, as they relate to the out-of-scope notion of concrete domains. Moreover, rule 6 includes the ; notation which, although it is also embeddable in FOL, we do not develop here. ((C; E) 2 R(r3)) (CR11) ((C; D) 2 R(r1)) ^ ((D; E) 2 R(r2)) ^ (r1 r2 v r3 2 C)
Deciding whether D 2 S(C) can then be reduced to derivation on the
predicate s. That is, given a set of clauses P 0 stating class and role inclusions, it is
equivalent to proving P [ P 0 ` s( (C); (D)), for which standard resolution can
be applied (forward or backward chaining).
On this basis, it is possible to define abduction on E L++ knowledge bases as
an Abductive Logic Programming (ALP) problem. ALP extends standard logic
program resolution with hypothesis generation from abducible predicates and
integrity constraint checking [
(fag v C 2 C) (fag v 9r:fbg 2 C) classAssertion( (C); (a)) objectPropertyAssertion( (r); (a); (b)) – A = fclassAssertion; objectPropertyAssertiong and – C includes the following constraints: f alse classAssertion( (C); (a)) ^ (IC1) fresh( (a))
true (a) = (c) (b) = (d) objectPropertyAssertion( (r); (a); (b)) ^ objectPropertyAssertion( (r); (a0); (b0)) ^ ((:fresh( (a)) ^ :fresh( (b0))) _ (:fresh( (a)) ^ :fresh( (a0)) ^ (b) 6= (b0)) _ (:fresh( (b)) ^ :fresh( (b0)) ^ (a) 6= (a0))) objectPropertyAssertion( (r); (a); (b)) ^ objectPropertyAssertion( (r); (a0); (b)) ^ fresh( (a)) ^ :bound( (a0)) objectPropertyAssertion( (r); (a); (b)) ^ objectPropertyAssertion( (r); (a); (b0)) ^ fresh( (b)) ^ :bound( (b0)) (IC2) (IC3) (IC4)
Hypotheses generated during abduction are either class and role assertions
from C (ground formulas) or formulas whose unbound variables are substituted
with randomly generated terms. We assume the existence of a unary built-in
predicate we denote fresh, whose term unifies with randomly generated UUID
URIs [
Definition 2 includes two restrictions compared to the general problem of abduction. First, hypotheses should be of the form of role assertions. In Proposition 1, this restriction translates into the integrity constraint IC1. Second, at least two individuals in the resulting role assertions should not be fresh individuals, which we expressed as IC2.
Constraints IC3 and IC4 guarantee that abduction terminates, by limiting the number of fresh individuals that can be introduced. The number of possible role assertions that meet these constraints is polynomial with respect to the size of the original ABox. It follows that the overall discovery terminates in polynomial time, given that E L++ classification also terminates in polynomial time.
It is straightforward to prove that any solution produced by the ALP program of Proposition 1 is also a solution to the problem of WoT semantic discovery (up to the renaming of fresh individuals). However, to prove the converse, one should first observe that for any two CBoxes C; C0, such that individuals of C0 can be substituted to obtain C, it holds that if C0 6j= , then C 6j= . We do not develop a formal proof in this paper, left as future work. 5 5.1
Experimental Setup
We applied the discovery framework presented in this paper on an experimental
industrial workstation. This workstation includes water tanks and circulation
pipes, equipped with various automation devices like valves, water level sensors,
a flow meter, a temperature sensor, a pump, and a heater; it had initally been
designed as a water management plant model for educational purposes. The
original model has been added six micro-controllers, wired to the automation
devices and acting as WoT servients with IP connectivity (over Wi-Fi). An
overview of the workstation is provided in Fig. 1.
These micro-controllers are ESP8266 (64kB RAM, 80 MHz), they all
embed a lightweight RDF store designed for constrained devices ( RDF store [
We implemented the ALP program of Definition 1 in Prolog, using the
HYPROLOG framework [
Discovery Task Our experiment consists in building a graph of interaction for the six TDs exposed on the workstation. These TDs are defined against SOSA, SSN, TD and eCl@ss. The CBox we perform reasoning on includes the axioms of these four ontologies, as well as the definition of five systems that can be discovered by combining servient capabilities. These systems, whose definitions we manually provide, are the following: Valve Control An open/close or proportional valve is coupled to a water level sensor to avoid overflow. When water level in a tank goes above a certain threshold, the valve opens.
Pump Control A water pump is coupled to a water level sensor to refill a tank when necessary. When water level in a tank goes below a certain threshold, the pump starts.
Heater Control A temperature sensor is coupled to a heater to maintain water at a stable temperature by turning on and off heating (thermostat). Circuit Anomaly Detection A flow meter and a valve are synchronously monitored to detect potential anomaly in a circuit, e.g. when the measured flow is not null but the valve is closed.
Water Circulation A pump and a valve are synchronously activated to keep water flowing in a closed loop, e.g. for cleaning purposes.
All these systems are rather simple and were designed to study the feasibility of our approach only. We do not address performance and scalability issues. Each system is meant to be the combination of two sub-systems, hosted by one or more servients. One can note that these systems themselves can be combined to perform more elaborate (and more realistic) tasks. Our semantic discovery approach would still cover these cases. As mentioned at the end of Sec. 3, the result of semantic discovery depends on the axioms we define. For our experiments, we defined axioms on systems such that all systems that can be discovered are associated to Web resources, as in the following example. 13 http://blabel.github.io/ Example 3. In our experiments, the full axiom defining ValveControlSystem is as follows (note the use of the existential construct 9href:WebResource):
9isHostedBy:27273201 u v ValveControlSystem
After applying our Prolog program on the six TDs (ABox) and the CBox described above, we obtain height edges in the graph of interactions (computation time below 1s). All five compound systems can be instantiated and ‘Water Circulation’ has two solutions, while ‘Valve Control’ has three solutions. The whole graph of interaction is showed in Fig. 2. In practice, this graph can be used for various purposes, such as the identification of critical points in the network (nodes with a high degree). Here, one of the nodes has a degree of seven, for a maximum degree of sixteen. If the servient is decommissioned and removed from the network, half of the discovered systems would stop functioning.
In addition, we looked at the exchange that takes place between the Thing Directory and servients. In a mediated scenario, the only exchange required for discovery is the registration of each TD on the directory. Registration can either happen by POST requests sent by individual servients to the Thing Directory or by a GET request broadcast by the Thing Directory to all RDF store instances on the network. In the former case, TDs are put in the request payload while in (a) Thing Descriptions (b) Results Fig. 3: Size of knowledge bases exchanged between servients and Thing Directory, encoded in EXI4JSON (servients are identified by their IP address) the latter case, they are in the response payload. In Fig. 3a, we show the size of the payload each servient sends.
In a peer-to-peer scenario, in addition to gathering servients’ TDs, the Thing Directory must update them, as per Definition 4. Updates are performed as PUT requests sent by the Thing Directory to each RDF store, with statements to add in the request payload. Payload sizes for updates are shown in Fig. 3b. One can note that in most cases, the update size is comparable to the size of the original TD. Both TDs and updates, except one, fit in a single CoAP block (of max. size 1024 bytes), which represents no technical challenge for micro-controllers like the ESP8266.
All RDF files and results shown in this paper are available online14. 6
The problem we addressed in this paper is that of semantic discovery in WoT. We formalized it as an abductive reasoning problem over knowledge bases that use standard ontologies, among others the SOSA/SSN and TD ontologies. The former provides semantics for systems and features of interest, which are, in a generic fashion, referred to as ‘things’ in WoT.
Our logic programming approach and its implementation over a water management workstation with six servients show that constrained devices like microcontrollers can carry enough knowledge in the form of TD documents, such that meaningful reasoning can be performed to make spontaneous systems form in an autonomous fashion. Moreover, even though discovery is centralized, having 14 https://github.com/vcharpenay/urdf-store-exp peer-to-peer systems, robust to changes, is still possible if the knowledge base carried by individual servients can be updated with the results of discovery.
In other words, the framework we present in this paper supports the vision of WoT as a large scale multi-agent system as presented in introduction, where devices can be quickly deployed and autonomously perform various tasks. To fully realize it, large scale experiments addressing performance, scalability and practicability issues are yet to be made. One condition to be fulfilled before large scale tests are even possible is to make extensive expert-reviewed system descriptions available on the Semantic Web. As we modeled them, sytem descriptions can be shared with existing Semantic Web technologies as regular Web ontologies. However, scaling up the engineering of such ontologies remains a challenge.