The pervasiveness of smart objects in people daily life is increasing, as the capabilities of objects are becoming more and more sophisticated. Objects participate to the Internet of Thing (IoT) with changing contexts and scopes, thus resulting in the rise of multiple networks linked to each other to form a new paradigm, called Multi-IoTs (MIoT). Of course, cooperation strategies among objects must follow this innovative trend as classical strategies based on the concept of coexistence appear no more adequate. In this scenario, this paper proposes a contribution by introducing a complex model for devices and contexts that follows a knowledge representation approach. It adopts dimension hierarchies in the multidimensional perspective typical of OLAP systems to represent roll-up relationships between admissible members of the considered dimensions, enabling the retrieval of relevant objects through a supervised algorithm.
Nowadays devices and sensors are smart enough to have connection capabilities
forming a network also known as Internet of Things (IoT). Furthermore, the
variety of types of objects, contexts, and scopes for which devices participate to
the IoT push towards the definition of multiple networks linked to each other
to form the notion of Multi-IoTs (MIoT). In these scenarios it is of crucial
importance the development of techniques for the retrieval of relevant devices and
data conveyed by them. As a matter of fact, some contexts, e.g. outdoor
applications like intelligent transportation, have largely casual, non pre-determined
goals. Moreover, objects move and meet other ones, so that cooperation
strategies must be dynamically defined. Some approaches in the literature define some
simple criteria to decide about the creation of the network [
In this paper we propose an approach to identify and query relevant devices inside a MIoT, that is based on the notion of device’s “context”, describing its semantics in terms of its customary usage, the interest and behavior (in terms of activities done with the object itself) of the owner, and so forth. Interactions among objects can be then driven by the degree of similarity among their respective contexts. As usually done in the framework of IoT research, a context is defined as a set of couples (p, v), where p is some property, and v represents an admissible value of the property. Differing from other approaches, we adopt a richer model based on a hierarchy of admissible values for each property, in the spirit of the multi-dimensional model typical of OLAP systems. This allows us to introduce different types of relationships among contexts, namely identity, inclusion (similar to the notion of roll-up among members of each context dimension) and a fuzzier relationship of compatibility. On the basis of this model, this paper presents an algorithm to determine the subset of devices that are more likely able to provide relevant answers to a user’s query.
Knowledge representation approaches to context modeling have been
extensively investigated in the literature [
The above literature focuses on “how” context information can be
represented. Another issue is related to “which” information should be included in
context. As already noted, this greatly varies from application to application.
Authors in [
The object’s network(s) created in this way can be compared to a person’s list
of contacts in a social network. This view is strongly supported by the research
community and, indeed, a number of works have tried to adopt the paradigm
of social network in the IoT realm and to combine these worlds improving their
usability and the offered services [
Differing from a social network, where peers are not classified according to their profile, or only very na¨ıve manual classification in a predefined set of categories can be done, the proposed model allows a very rich and flexible definition of contexts, and a graded association of profiles to contexts. Furthermore, interaction mechanisms in social networks are typically limited to information sharing by broadcasting (posting information that reaches all node’s contacts) or to one-to-one messaging (directly contacting a node via its name/address). In the present paper we also present an algorithm to determine the best set of nodes that can be queried according to given information needs or preferences and contexts, hence producing a projection, or view, of the original overall network, that can be actually exploited for the goal at hand.
This paper is structured as follows: Section 2 presents the model for device contexts in a Multi-IoT scenario, on the top of which a supervised algorithm for device retrieval is presented in Section 3. Experiments to assess the effectiveness of our approach are reported in Section 4, whereas Section 5 ends this paper.
A model for devices in a multi-IoT network This section is devoted to introduce the model used to represent devices and their relations in the context of a multi-IoT network. We define a device Δi as a set of sensors Δi = {S1, . . . , Sn}. We refer to the term context as a scenario in which the devices operated in the past, are currently operating or may operate in the future. A set Pi of properties are associated with a device, each of which represented as a pair (p, v) where p is a property (e.g., owner, brand, model, cost, reference measure) and v is the corresponding value. We discuss in more detail contexts and properties in the following. 2.1
In order to specify a context, we refer to a set of dimensions D = {D1, . . . , Dm}, which are to be intended as the dimensions in the multidimensional model (e.g., or instance time, space, goal). Therefore, from a data perspective, a context may be compared to a fact in a multidimensional model. In this work, we do not assume that all contexts for all devices are defined by the same set of dimensions. According to the information provided by its sensors, each device will specify a context according to available information.
Analogously to the multidimensional model, given a dimension Dj ∈ D, it is possible to define a hierarchy of levels Lj = {lj1 , . . . , ljm } such that lj1 → lj2 → · · · → ljm . The notation ljp → ljq implies that a functional dependency exists from ljp to ljq . To make an example, given the dimension space, the following relation holds: street → district → city → · · · → country. Given a level lji of a dimension Dj , its members {ιj1 , . . . , ιji } are named instances, e.g. level city can include instances Rome, Venice, Milan.
The schema of a context C for a device is a set of dimensions D. A context instance c ∈ C is a tuple c = (ι1, ι2, · · · , ιm). To make an example, considering a dimensional schema including { space, time, goal }, a possible instance can take the following values: ιspace= Grosseto, ιtime= June 16th 2019, 11:00-12:00, ιgoal = Running.
Given a dimension Dj ∈ D, let ιjp , ιjq ∈ Dj be two instances of Dj . The following relations are defined between ιjp and ιjq : – id(ιjp , ιjq ): it means that ιjp and ιjq are identical instances, e.g. id(Montecitorio square, Montecitorio Sq.). – inc(ιjp , ιjq ): it means that ιjp is included in ιjq , e.g. inc(Montecitorio square, Rome). In order for this property to hold, it must be that square → city and Montecitorio square is in Rome. Moreover, given that square → city and, in turn, city → nation, it also holds that inc(Montecitorio square, Italy). In the following we refer to dist(ιjp , ιjq ) as the distance between ιjp and ιjq , that is the number of steps in the dimensional hierarchy necessary to move from the former to the latter. – cpt(ιjp , ιjq ): it means that inc(ιjp , ιjr ), inc(ιjq , ιjr ), where ljp → ljr , ljq → ljr and ljp (resp., ljq , ljr ) represents the level of ιjp (resp., ιjq , ιjr ). This means that ιjp and ιjp are siblings, e.g. cpt(Rome,Milan), cpt(Italy, France), whereas it does not hold that cpt(Rome, Paris).
Let c = (ι1, ι2, · · · , ιm) and c′ = (ι′1, ι′2, · · · , ι′m) be two contexts. The following relations are defined among them: – idC (c, c′), if id(ιi, ι′i), 1 ≤ i ≤ m; for instance c=(Montecitorio square, [10:0011:00], Running) c′=(Montecitorio sq., [10:00-11:00], Running). – incC (c, c′), if id(ιi, ι′i) or if inc(ιi, ι′i), 1 ≤ i ≤ m and idC (c, c′) does not hold; for instance c=(Montecitorio square, [10:00-11:00], Running), c′=(Montecitorio sq., Morning, Running). We define dist(c, c′) as a measure of distance between c and c′, measured as Pim=1 dist(ιi, ι′i), where dist(ιi, ι′i) = 0 if id(ιi, ι′i). – cptC (c, c′), if either id(ιi, ι′i) or inc(ιi, ι′i) or cpt(ιi, ι′i), 1 ≤ i ≤ m and neither idC (c, c′) nor incC (c, c′) holds; for instance, c=(Montecitorio square, [09:0010:00], Running) c=(Montecitorio square, [10:00-11:00], Running) In the following, we define an operator match(c), which returns the set of devices that are matching with the context c. In order for a device Δi to match with c, the context provided by Δi must be a superset of c, i.e it must provide at least the same dimensions included in c, with the same members. Definition 1. (Match operator) Given a net N = {Δ1, . . . , Δn} including a set of n devices, each with a corresponding context ci, and given a context c = (i1D1 , . . . , iDmm ), match(c)={Δi ∈ N : c ⊆ ci}. 2.2
Let (pi, vi) and (pj , vj ) be two property-value pairs. We define the following relations between them: – idP (pi, pj ), if pi = pj and vi = vj ; – cptP (pi, pj ), if pi = pj and cptV (vi, vj ); – cptV (vi, vj ), to state an explicit compatibility relation among them. For instance, a device measuring temperature in Farenheit is compatible with another device referring to Celsius.
Let us define P (d) as the set of properties for a device d, i.e. P = {(p1, v1),
(p2, v2), · · · , (pn, vn)}. We introduce a Jaccard modified operator J ∗(P, P ′) which
works on two sets of properties P and P ′ and returns a float between 0 ed 1
representing the ratio of P that are identical or compatible with P ′. It is computed
through the following steps:
– the set I = {(p, p′)|p ∈ P, p′ ∈ P ′, idP (p, p′)} is computed, which includes all
properties that are identical;
– the set C = {(p, p′)|p ∈ P, p′ ∈ P ′, cptP (p, p′)} is computed, including those
properties that are compatible each other;
– finally, the result of J ∗(P, P ′) is computed as J ∗(P, P ′) = |I|+α·|C| , where
|P |
α ∈ [
Retrieval of devices in a multi-IoT network Given a user and its network, this section presents a supervised algorithm aimed to retrieve the subset of devices satisfying some requirements, that are expressed through a query.
A query q is represented as q = hc, Zi, where c is the context of interest and Z = {(p1, v1), (p2, v2), · · · , (pn, vn)} represents the properties that the devices must satisfy, expressed as a set of pairs (p, v) indicating the required value v for each property p. The pseudocode is reported in Algorithm 1.
To provide an answer to a query q, the supervised algorithm first executes a SEARCH function, computing all contexts that are respectively identical, included or compatible with c, checking whether there are devices that belong to such contexts. In case there is no answer, the algorithm rewrites the query by finding one or more contexts that include c, i.e. that are more general than c (formally the set {c′ ∈ C : incC(c, c′)), and then the SEARCH is performed again. The whole procedure iterates until to: (1) a solution is found, (2) the number of rewritings is above a defined threshold (using the function dist discussed in Section 2.1), (3) there are no more general contexts. The pseudocode for the SEARCH function is reported in Algorithm 1, and operates as follows: 1. The Algorithm searches for devices that have contexts identical to or included in c by calling the corresponding function. If there are such devices (line 4) then their properties P (s) are matched against the vector Z to verify if, and to what extent, they satisfy the user query in terms of property values (line 6). Finally, each retrieved device, ranked according to the Jaccard function J ∗ (discussed in Section 2.2), is added to the output list SO (line 7). 2. In case no device is found in the previous step, then the algorithm searches for devices having a context compatible with c, through the corresponding function. Similarly to the previous case, for each retrieved device a rank r is computed and the pair hdevice, ranki is added to the output list SO (line 14). To take into account that such devices have contexts that are compatible, but neither identical to, nor included in, c, the rank is weighted by a parameter αcpt < 1.
Finally, the list SO is returned as output (line 18). 4
The supervised algorithm discussed in the previous section has been evaluated. In particular, hereafter, we compare our approach with two baseline algorithms: – Baseline1 (no contexts): this approach does not consider contexts. Therefore, the query is expressed only as q = h∅, Zi. – Baseline2 (only identical): this approach considers contexts but it does not include a knowledge base. Therefore, the supervised approach can only match identical contexts but no reasoning on inclusion or compatibility can be done. Algorithm 1 Pseudocode for the SEARCH function Input:
The set S of devices in the user net.
A query q=hc, Zi over S, where c ∈ C is a context and Z = {(p1, v1), (p2, v2), · · · , (pn, vn)} is a set of pairs (property value) Output:
a ranked set of devices SO = {hs1, r1i, . . . , hsn, rni}, where si ∈ S and ri ∈ [
S 20: function Find Devices ID(c, S) 2221:: SC′′ ←← {IsC∈(′cS)∪|sI∈NmCa−t(cch)(c=′){,cc′′ ∈∈ CC|′i}dC(c, c′) ∨ incC(c′, c)} 23: return S 24: end function 25: function Find Devices CPT(c, S) 2276:: SC′′ ←← {CsP∈′TS(c|s) =∈ m{ca′ t∈chC(c|′c)p,tcC′ (∈c,Cc′′)}∨ incC (c′, c)} 28: return S 29: end function
Firstly, the dataset, the knowledge base and the experimental settings are introduced. Then, we present results aimed to evaluate three different measures: (1) the probability to obtain a response from a query, (2) how the query rewriting approach discussed in Section 3 affects retrieval and (3) how it affects precision of the supervised algorithm. Hereby, we refer to the precision as the ratio rreetlreiveavnetdccoonntteexxttss , where retrieved contexts stands for the contexts belonging to the retrieved sensors, while relevant contexts refer to those contexts that are relevant to the query.
Dataset and model In this set of experiments we refer to a dataset that includes 5000 devices, each with a single sensor. Each device belongs to one or more IoT networks, the largest of which includes 500 devices. These are described in terms of their properties, although, in these tests, we consider a single property, namely the “measure” retrieved by the device (e.g., temperature, humidity or pressure), for the sake of simplicity.
The model taken into consideration for these tests includes 3 dimensions, 3 hierarchical levels for each dimension and a branching factor of the dimensional tree equal to 3. In particular, the dimensional tree will include 1 root element at level 1, 3 elements at level 2 and 9 elements at level 3 (i.e. 13 elements in total). The overall number of possible contexts is, therefore, given by all the possible combinations of elements for each dimension, e.g. |C| = 133 = 2197 in this case. Specific compatibility relationships among members are defined for each dimension. In our experimental setting, each member is defined to be compatible with 5% of the other members in the same level (e.g., given the level “street” of dimension space, each specific member will have 5% of chances to be defined as compatible with any other street).
Experimental settings The initialization includes the following steps: – Device initialization: a device is picked from the dataset, and the set S of all the devices belonging to its net are extracted. In our test, the following procedure is repeated with 5 devices belonging to nets with sizes S1, . . . , S5 from |S1| =100 to |S5|=500. – For each device s ∈ Si: a context c is randomly assigned to s. The assignment is done according to a strategy following a power law: we randomly assign a context from a small subset of C (i.e., 20% its size) to the large majority of devices (i.e., 80% in our tests), which hereafter we name Cs. We aim to model in such a way as the probable context similarity of devices belonging to the same network. The procedure assigns a random context from the remaining set C − Cs (i.e., in this case corresponding to the remaining 80% of C) to the rest (i.e., the remaining 20% of devices). – A query q = hc, Zi is defined by assigning a context c from Cs and a property value from the list of possible property values seen in the database. – The query q is launched on the network.
The procedure has been repeated for a number of queries equal to |C|, in order to perform a comprehensive evaluation. Results are, then, averaged. Results Results are summarized in Figure 1. Figure 1(a) shows the performances of the supervised algorithm with increasing net sizes, in terms of percentage of queries with an answer. On the other hand, Figure 1(b) shows how the number of rewritings affects precision (as defined above) and how it affects recall in terms of the increase in the percentage of queries answered when one or more rewritings occur (see Section 3).
The most relevant insights are summarized as follows: the increase in the number of devices in a net has a positive impact, on average, on results. In particular, the larger the size, the greater the ratio of queries with an answer. By rewriting a query c as a query c′ (which includes the former), the likelihood of obtaining an answer increases. Indeed, the number of contexts included or compatible in c′ is obviously larger than in the former case. A single rewriting is enough to significantly increase the chance to find at least one solution to the query. However, this is achieved at the price of a relaxation of the original query specification and, as a consequence, of a decrease of the precision of results.
A direct comparison with Baseline1 is straightforward, as the number of retrieved devices is purely based on property information. Therefore, with Baseline1 the result set is always larger, but the whole set of sensors in the network must be analysed and matched against the properties, with no guarantee on the correctness of the results. In other terms, recall is not higher whereas precision is much lower. On the other hand, by comparing these results with the Baseline2 approach, it is possible to conclude that our approach allows the retrieval of a much larger number of relevant results. In this respect, Baseline2 is basically equivalent to the evaluation of only identical contexts. Therefore, precision is high, whereas recall is typically much lower. On the other hand, by exploiting the knowledge base, and specifically inclusion relations among contexts, more contexts can be obtained. Moreover, contexts that are compatible are added to the result with a lower rank, meaning that their relevance is lower than the others but can be still useful, depending on the specific application case. Finally, by exploiting inclusion relationships and the notion of rewriting, our approach can optionally lower precision in order to increase the probability to answer a query. ],1 0.4 0 [ d e v e i r t rsee 0.2 c i v e D % 0 id inccpt total ],10 0.8 [ d ieev 0.6 r t e rsce 0.4 i v eD 0.2 % 1 0
Precision Recall (100) Recall (300) Recall (500) 100 200 400
500 300 Net size 0 1
2 3 # Query rewriting 4 5 (a) (b) This paper has discussed an approach to querying a Multi-IoT network of devices, which relies on a multi-dimensional model for device’s contexts that takes also into account its customary usage, user interest and behavior. On top of that, we proposed a supervised algorithm to determine the best set of nodes that can be queried according to given information needs or preferences and contexts, experimentally evaluating its effectiveness. Future works include: (1) the extension of the model with more expressive relations between dimensions members, (2) an unsupervised algorithm that starts with no initial specification of desiderata and automatically generates a query on the basis of its current context and device’s properties, and (3) a more comprehensive experimentation.
This work was partially funded by the Department of Information Engineering at the Polytechnic University of Marche under the projects “A network-based approach to uniformly extract knowledge and support decision making in heterogeneous application contexts” and “Novel and Optimal Solutions for Metering and Enforcing Security and Privacy in Cloud Systems” (RSA-B 2018).