IoT Service Clustering for Dynamic Service Matchmaking

Abstract

As the adoption of service-oriented paradigms in the IoT (Internet of Things) environment, real-world devices will open their capabilities through service interfaces, which enable other functional entities to interact with them. In an IoT application, it is indispensable to find suitable services for satisfying users’ requirements or replacing the unavailable services. However, from the perspective of performance, it is inappropriate to find desired services from the service repository online directly. Instead, clustering services offline according to their similarity and matchmaking or discovering service online in limited clusters is necessary. This paper proposes a multidimensional model-based approach to measure the similarity between IoT services. Then, density-peaks-based clustering is employed to gather similar services together according to the result of similarity measurement. Based on the service clustering, the algorithms of dynamic service matchmaking, discovery, and replacement will be performed efficiently. Evaluating experiments are conducted to validate the performance of proposed approaches, and the results are promising.

1. Introduction

1.1. Background

The Internet of things (IoT) integrates user requirement, cyberspace and physical space, which enables the seamless cooperation of human-machine-thing. SOC (Service-Oriented Computing) proposes techniques for provision, selection, discovery, and composition of Web services, and integrates heterogeneous and complicated software entities together organically [1,2]. As the adoption of service-oriented paradigms in the IoT environment [3], real-world devices will open their capabilities through service interfaces, which enable other functional entities to interact with them. In an IoT application, it is indispensable to find suitable services for satisfying users’ requirements or replacing the unavailable services.

With the rapidly growing number of IoT services, discovery and selection for numerous services under the dynamic and large-scale environment of IoT is becoming a crucial task. Several middleware solutions have been proposed for the integration of the physical world with the Web, such as OpenIoT [4], GSN (Global Sensor Networks) [5], and Xively [6]. These solutions act as service platforms that manage millions of services around the world, which enable people to share and monitor environmental data from objects that are connected to the Web. However, most leading middleware solutions provide only limited service discovery and selection functions. It is effective to discover services through service matchmaking techniques [7,8]. However, from the perspective of performance, it is unreasonable to discover services from online repositories directly in the context of the IoT-scale environment [9,10]. Instead, if services are classified offline or clustered according to their similarity, and then the online examining of services will be controlled within several limited clusters. Then, the performance of finding desired services online will be optimistic [11,12]. Besides, because of the dynamic of IoT, the selected services may become unavailable or unfit for the current context, so re-selection and replacing services by similar services from the same cluster is necessary. Therefore, techniques that cluster services offline according to their similarity are critical for dynamic service matchmaking, discovery, and replacement [13].

1.2. Motivation

As the research [14] discusses, nearly 12,000 Web services are active on the Web. Even in such conditions, the similarity measurement and clustering of Web service has become a challenging problem. The same issue of IoT service will become a much more complex challenge due to the scale and complexity of IoT. As the IoT service acts on ternary space (i.e., user, cyber, and physical space) rather than Web service that only exists in cyber space, the context of IoT service is more complex than Web service. IoT services imply multidimensional semantic, for instance, the physical quantity observed by the service, the observation capabilities of service, the observation area of the service, and so on. When clustering or measuring similarity between services, these information should be taken into consideration.

A bundle of approaches about measuring similarity between Web services has been proposed in recent years. Basically, it can be divided into: information content-based approaches [15,16] and semantic-network-structure-based approaches [17,18]. However, it is inappropriate that directly using existing approaches on IoT services. Existing similarity measurements focus on the hierarchy and inheritance relations between services in the semantic model. They ignore the relation types, relation contexts, and relation restrictions that imply meaningful semantic information for distinguishing service. Besides, service nodes in a semantic model are defined with data-type and object-type properties. The properties should also not be ignored when computing the similarity between services.

Moreover, existing service models mix multiple feature dimensions of IoT service to construct complicated models. The dimension-mixed model cannot obtain a well-defined taxonomy structure. Thus, using semantic structure-based algorithms to measure the dimension-mixed model will not achieve a satisfactory accuracy. Besides, the property and restriction descriptions of multiple dimensions interfere with each other when measuring similarity based on service description. Therefore, using the existing algorithms to measure IoT services will not conform to the equivalence soundness and disjointedness incompatibility principles of similarity measurement, and the measurement results cannot reflect the real similarity between services [19]. Without accurate similarity measurement, it is impossible to obtain satisfactory clustering results, which will influences the effect of follow-up matchmaking and discovery of services.

This paper proposes the multidimensional semantic model for describing IoT services. Each dimension constructs a semantic model including well-defined service classification, service properties, and property constraints. Based on this multidimensional service model, we propose an MDM (Multiple Dimensional Measuring) algorithm to calculate the similarity between services on each dimension by taking both model structure and model description into consideration. The similarity between services on each dimension is measured concurrently. If the context of service changes, MDM just needs to re-measure the similarity of changed dimensions, rather than existing approaches which require re-measuring the whole similarity. Thus, compared with dimension-mixed approaches, MDM is more accurate and efficient. After that, based on the result of similarity measurement, we employs density-peaks-based clustering [20] to divide services into clusters according to the distribution of their similarity. The similar service clusters are generated automatically without the artificial estimating of parameter (e.g., cluster size or number of cluster). Different services have personalized cluster sizes, which take the heterogeneity of service context into consideration. After clustering, the agile service matchmaking and discovery are possible. In particular, this paper has the following contributions:

• This paper proposes the MDM algorithm for measuring the similarity between IoT services based on multidimensional service model. The accuracy and efficiency of MDM outperform the dimension-mixed approaches.
• MDM algorithm employs a density-peaks-based clustering approach to gather similar services together according to the actual distribution of services. It avoids the complicated process of estimating or optimizing parameters.
• To evaluate the applicability of proposed approaches, we use a combined data set including real and synthetic data. The experiment results indicate that the performance of proposed approaches are applicable to real-life scenarios.

2. Preliminaries: Multidimensional Service Model and Model Vectorization

A series of works have been proposed to formally describe IoT services in ontology models, such as references [21,22,23,24,25,26,27,28]. However, existing models mix multiple feature dimensions of IoT service to construct complicated models. Therefore, in a model hierarchy multiple classifying criterions are referenced. The dimension-mixed model cannot obtain a well-defined taxonomy structure, and the distance and positional relationships between nodes are meaningless to reflect the similarity between services. Therefore, using semantic structure-based algorithms to measure the similarity between services will not achieve a satisfactory accuracy. Besides, the restrictions and property descriptions of different dimensions interfere with each other when measuring similarity based on service descriptions.

Based on the multidimensional service model proposed in our previous work [29], the service classification, service properties, and property constraints of each dimension are well defined. Then, the MDM algorithm discussed in Section 3 can calculate the similarity between services on each feature dimension accurately and concurrently. To reflect the similarity meeting the perspectives of different users, the whole similarity values are aggregated by users’ personalized weight values. In this section, four representative dimensions are described to demonstrate the idea of multidimensional model, shown in Figure 1. The other parts of service model and the detailed discussion about the problem of existing model are presented in [29].

Figure 1a shows the dimension of observation principle, which is based on the standard definition of observation physical principle described in [30]. As a sensor is a converter of transforming nonelectrical effects into electrical signals, several steps are needed before outputting the electric signal. For example, the measurement principle of capacitive water-level sensor is dielectric-constant. This sensor is fabricated in a form of a coaxial capacitor where the surface of each conductor is coated with an isolating layer. If the water level increases, water occupies more and more space between the coaxial conductors, then transforming the capacitance. The model of this dimension is helpful to discover suitable services according to users’ application scenarios. For instance, magnetic sensors are unfit for the environment with magnetic interference.

Figure 1b depicts the dimension of observation quantity type. It defines the physical quantities that be measured by the IoT services. The quantity type model is a key criterion for service matchmaking; it avoids the ambiguous representation of physical quantity. For instance, the services of body temperature and environment temperature have the similar type of output. Without an exact definition of quantity type, a body temperature service may be offered to user when he requires observing the ambient temperature. The model is constructed based on the Climate and Forecast standard of W3C CF (Climate and Forecast)-feature ontology [31], which makes a standard definitions for common observed physical quantity. For instance, it has more than 50 quantity types to express temperature, such as surface air temperature, canopy temperature, and dry-bulb temperature, etc.

Figure 1c indicates the dimension of application domain deriving from reference [30]. This dimension will help users to choose the services that are fit for their application domain. For instance, if we select a service to measure the gas concentration in coalmine domain, the service must be coalmine dedicated and “intrinsically-safe”.

Figure 1d shows the measurement capability dimension. This model is derived from the capability model of W3C SSN (Semantic Sensor Network) ontology [32]. Due to the performance of IoT service may be influenced by operation environment, this model expresses the measurement capabilities of services under certain conditions, consisting the concepts of sensitivity, frequency, drift, and accuracy, etc. It can be used to check whether the service has been properly used or to determine how a service will perform in a particular environment. It is also an important criterion for service matchmaking. For instance, the capability of a temperature observation service is: with temperature −200 to 500 °C the accuracy is ±1.0 °C, while from 500 to 800 °C it is ±0.5%.

Based on the formally multidimensional model, the semantic similarity between IoT services can be measured. Before measuring, the model of services should be vectorized, that is, transforming the model description of a service to a tuple of terms. The model conversion approach of [33] is adopted. After vectorization, the semantic concept $C$ will be denoted as a tuple, as Equation (1) defines:

$$tuple=\left\{C,\left[{\delta }_i,{\gamma }_{{\delta }_i}\right],\left[o_j,{\gamma }_{o_j}\right],\left[o_j,C_{o_j}^x\right],C_{o_j}^x,{\lambda }_{o_j}^y\right\}$$

(1)

where in OWL-annotated semantic documents, $C$ is the name (or URI) of the concept $C$, each $[]$ is a property term including a property and its restriction, ${\delta }_i$ ($i=1\dots n$) is a datatype property of the concept $C,{\gamma }_{{\delta }_i}$ is a restriction for the datatype property ${\delta }_i$, $o_j$($j=1\dots m$) is an object property of the concept $C$, ${\gamma }_{o_j}$ is a restriction for the object property $o_j$, $C_{o_j}^x$($x=1\dots k$) is a concept related by the object property $o_j$, and ${\lambda }_{o_j}^y$ is a Boolean operation between concepts $C_{o_j}^x$.

After the model vectorization, the semantic description of an IoT service $i$ can be represented as a tuple:

$$tupl{e}_i=\left\{ter{m}_1,ter{m}_2,\dots ,ter{m}_i,\dots ,ter{m}_n\right\}$$

Example 1.

We use a simplified model structure (shown in Figure 2) to demonstrate the process of model vectorization. In this model, $C1$ to $C5$ are classes that form the inheritance structure, $s1$ to $s4$ are service instances (i.e., objects that belong to different classes). $P1$ and $P2$ are object properties that denote the relationships between service instances. Assuming that we want to measure the similarity between $s1$, $s2$, and $s3$. Before similarity measurement, we should vectorize the model of services into tuples as following according to above discussion:

$$tupl{e}_{s1}=\left\{s1,s3,C4,P2,typeOf,\left[typeOf,C4\right],\left[P2,s3\right]\right\};$$

$$tupl{e}_{s2}=\left\{s2,s3,C3,P2,typeOf,\left[typeOf,C3\right],\left[P2,s3\right]\right\};$$

$$tupl{e}_{s3}=\left\{s2,s3,C4,P1,typeOf,\left[typeOf,C4\right],\left[P1,s2\right]\right\};$$

3. MDM Similarity Measurement

Before clustering IoT services, the similarities (or distances) between services should be measured based on MDM. MDM matches both the structure information of the model hierarchy and the description of service properties, relations and restrictions. It employs Li’s approach [34] as the similarity computing method of structure information, which proposed a hybrid semantic similarity model by adopting a nonlinear model. For measuring the similarity of service description, based on the model vectorization algorithm discussed in Section 2, it adapts the TF-IDF (Term Frequency and Inverse Document Frequency) [35] and Cosine Similarity to calculate the similarity of service tuples. By combining the similarity of structure and description, MDM can measure the similarity of every dimension accurately and concurrently. Then, the overall similarity will be generated by aggregating the similarity of multiple dimensions according to users’ preferences, for instance, allocating different weights for different dimensions.

3.1. Structure Similarity

A series of algorithms for measuring structure similarity have been proposed, considering the aspect of information content [15,16], depth in the hierarchy [36,37], semantic density [34,38], and shortest path length [39,40], etc. In order to achieve a good similarity measure, Li [34] investigated the effectiveness of a variety of strategies considering possible structure information. Its research results demonstrate that comparing the performance against human common sense is the only way to evaluate the quality of a method for calculating concept similarity. Therefore, the closer the result compares with human judgment, the better it will be. The work of [34] has confirmed the hypothesis that the human judgment of similarity is a nonlinear process. Its measurement algorithm, which models the length and depth of shortest path into a nonlinear function and combines them by multiplication, can obtain a dramatic improvement compared to previous methods. We employ their approach to calculate the structure similarity of services. Given the service a and b, the structure similarity on dimension $i$ between their class $C$ can be measured by Equation (2).

$$Si{m}_{C_i}\left(a,b\right)=\{\begin{array}{c}{e}^{-\alpha l}\cdot \frac{e^{\beta h}-e^{-\beta h}}{e^{\beta h}+e^{-\beta h}}if{C}_{ai}\ne C_{bi}\\ 1if{C}_{ai}=C_{bi}\end{array}$$

(2)

where $h$ denotes the depth of the subsume Class of $C_{ai}$ and $C_{bi}$, and $l$ is the shortest path length between $C_{ai}$ and $C_{bi}$. $\alpha$ and $\beta$ are the impacts of $l$ and $h$. Li [34] configures the optimal parameters that α = 0.2 and β = 0.6. Under these parameters, the correlation coefficient between this measurement and human similarity judgments is 0.8914, while correlation between different people is 0.9015. It indicates that the measurement performs nearly at a level of human replication.

3.2. Service Description Similarity

Assuming that $S$ is the candidate service set $S=\left\{s_1,s_2,\dots ,s_i,\dots ,s_m\right\}$, then according to Equation (1), $S$ can be represented as:

$$S=\left\{tupl{e}_1,tupl{e}_2,\dots ,tupl{e}_i,\dots ,tupl{e}_m\right\}$$

Then we construct the feature vector of each service using the TF-IDF. TF-IDF is the product of two statistics: term frequency (TF) and inverse document frequency (IDF). The former is the frequency of a term in a document, while the latter represents the occurrence frequency of the term across all documents. It is obtained by dividing the total number of documents by the number of documents containing the term and then taking the logarithm of that quotient. The higher TF-IDF of a term, the more important it is for a document. In our study, corpus is the service set, document and term are tuple and description term respectively. We adopt TF-IDF to calculate the frequency of terms in the service tuple. The TF of a term in a service tuple is:

$$T{F}_{term}=\frac{f}{\left|tuple\right|}$$

$\left|tuple\right|$ is the size of terms of the tuple, and $f$ is the occurrence frequency of term in this tuple. The $IDF$ of the term can be measured by:

$$ID{F}_{term}=log\frac{\left|S\right|}{\left|\left\{tuple\in S:term\in tuple\right\}\right|}$$

The cardinality of service set $S$ is denoted as $\left|S\right|$, and $\left|\left\{tuple\in S:term\in tuple\right\}\right|$ represents the amount of tuples that includes the $term$. Thus, the $TF-IDF$ can be calculated by:

$$TF-ID{F}_{term}=T{F}_{term}\cdot ID{F}_{term}$$

Then, a vector of a service by calculating the TF-IDF of terms in its tuple is obtained. For a service $s$, its tuple $tupl{e}_s=\left\{ter{m}_1,ter{m}_2,\dots ,ter{m}_i,\dots ,ter{m}_k\right\}$ and its vector is:

$$vecto{r}_s=\left\{TFID{F}_1,TFID{F}_2,\dots ,TFID{F}_i,\dots ,TFID{F}_k\right\}$$

The similarity between two vectors can be measured by the cosine-similarity. The IDF not only strengthens the effect of terms whose frequencies are very low in a tuple, but also weakens the effect frequent terms. For instance, the property subClassof: Thing occurs in most ontology concepts, then the $IDF$ of it is close to zero. Therefore, the terms with low $IDF$ value will have weak impact on the cosine similarity measurement. The description similarity on the dimension $d$ between two services $i$ and $j$ can be measured by:

$$Si{m}_{P_d}\left(i,j\right)=\frac{vecto{r}_i\cdot vecto{r}_j}{\left|\left|vecto{r}_i\left||\cdot |\right|vecto{r}_j\right|\right|}$$

(3)

3.3. Multidimensional Aggregation

The similarity in the $i$ dimension between two services $a$ and $b$ can be calculated by combining $si{m}_C$ (Equation (2)) and $si{m}_P$ (Equation (3)). $\delta$ is the impact parameter which indicates the effect of structure information on the similarity measurement.

$$Si{m}_i\left(a,b\right)=\delta \cdot si{m}_{C_i}\left(a,b\right)+\left(1-\delta \right)\cdot si{m}_{P_i}\left(a,b\right)$$

(4)

The similarity values of each dimension can be aggregated by weights according to the users’ preferences:

$$Sim\left(a,b\right)={\displaystyle \sum }_{i=1}^n{w}_i\cdot si{m}_i\left(a,b\right),{\displaystyle \sum }_{i=1}^n{w}_i=1$$

(5)

where $n$ is the dimension number of semantic service model.

4. IoT Service Clustering

This paper employs density-peaks-based clustering [20] to divide services into clusters according to the potential density distribution of similarity between services. Density-peaks-based clustering is a fast and accurate clustering approach for large-scale data. After clustering, the similar services are generated automatically without the artificial determining of parameter. The distance between two services can be calculated by Equation (6):

$$Dist\left(a,b\right)=1-Sim\left(a,\mathrm{b}\right)$$

(6)

4.1. Local Density and Distance Calculating

The density-peaks algorithm is based on the assumptions that cluster centers are surrounded by neighbors with lower local density, and they are keep a large distance from other points with higher density. Assuming that $S={\left\{s_i\right\}}_{i=1}^N$ is the service set that will be clustered, $s_i$ is a service of $S$, $I_S=\left\{1,2,\dots ,N\right\}$ is the set of index. For each service $s_i$ in $S$, two quantities are defined: its local density ${\rho }_s$ and its distance ${\theta }_s$ from services of higher density. The local density $\rho$ of service $i$ is defined as:

$${\rho }_i={\displaystyle \sum }_j\chi \left(d_{ij}-d_c\right)$$

(7)

where $d_c$ is a cutoff distance. If $x<0,\chi \left(x\right)$ equals to $1$, otherwise $\chi \left(x\right)=0$. $\theta$ is calculated by measuring the closest distance between the service $i$ and other services with higher density than $i$:

$${\theta }_i=\underset{j:{\rho }_j>{\rho }_i}{\min }{d}_{ij}$$

(8)

For the service with highest density, its density is defined as: ${\theta }_i=ma{x}_j\left(d_{ij}\right)$. Note that ${\theta }_i$ is much larger than the typical nearest neighbor distance only for services that are local or global maxima in the density. Algorithm 1 describes the procedure of calculating clustering distance. Firstly, the data density are sorted in descending order, set ${\left\{q_i\right\}}_{i=1}^N$ is the index generated from the descending order, $i$ is the index of descending order and $q_i$ is the original index. Then, the clustering distance ${\theta }_i$ of service $s_i$ is calculated by ${\theta }_i=Dist\left(i,j\right)$, $s_j$ is the service that has larger density (than $s_i$) and closest to $s_i$. In $S$, we use $n_i$ to denote the index of $s_j$, namely, $n_i=j$. ${\left\{n_i\right\}}_{i=1}^N$ is defined as:

$$n_{q_i}=\{\begin{array}{c}arg\underset{\begin{array}{c}{q}_j\\ j<i\end{array}}{\min }\left\{d_{q_i{q}_j}\right\},i\ge 2;\\ 0,i=1.\end{array}$$

(9)

The clustering distance of the point with largest density is defined as $ma{x}_j\left(d_{ij}\right)$ that is the maximum value of all data points, and the index is $n_{{\mathrm{q}}_1}=0$.

Algorithm 1. Calculating Clustering Distance
Input:	$F$: the matrix of distances between services;
	$\rho$: local density of each service;
Output:	$\theta$: the clustering distance of each service;
	$n_{{\mathrm{q}}_i}$: the index of service that has larger density and closest to $s_{{\mathrm{q}}_i}$;
Sort in descending order by density $\rho$ 1: ${\left\{{\rho }_i\right\}}_{i=1}^N$ 2: ${\mathrm{q}}_i$←descending order index of density; Distance assignment of $\theta$ 3: ${\left\{n_i\right\}}_{i=1}^N$← 0; 4: for i:=1 to N do 5: ${\theta }_{qi}$←$d_{max}$; 6:   for j:=1 to i−1 do 7:     if $dist(s_{{\mathrm{q}}_i},s_{{\mathrm{q}}_j})<{\theta }_{qi}$ then 8:       ${\theta }_{qi}=dist(s_{{\mathrm{q}}_i},s_{{\mathrm{q}}_j});$ 9:       $n_{{\mathrm{q}}_i}=q_j$; 10:     end if 11:   end for 12: end for 13: ${\theta }_{q_1}=\underset{j\ge 2}{\max }{\theta }_j;$

4.2. Cluster Center Selecting

For services ${\left\{x_i\right\}}_{i=1}^N$ in $S$, their local density and clustering distance can be calculated: ${\left\{\left({\rho }_i,{\theta }_i\right)\right\}}_{i=1}^N$. Cluster centers are the services that have both large $\rho$ and large $\theta$. In order to eliminate the difference of magnitude, the $\rho$ and $\theta$ of each service are normalized to [0,1]. Then, the values that are comprehensive consideration of $\rho$ and $\theta$ are calculated:

$${\gamma }_i={\rho }_i{\theta }_i,i\in I_S$$

(10)

Obviously, the higher value of $\gamma$, the more likely it becomes a cluster center. ${\left\{{\gamma }_i\right\}}_{i=1}^N$ are sorted in descending order. The sorted $\gamma$s are drawn on the coordinate plane, the horizontal axis is the index of $\gamma$, the vertical axis is the value of $\gamma$, as shown in Figure 3. This coordinate plane is defined as decision graph. In addition, then a number of service points are intercepted from front to back as the cluster centers. The decision graph shows that the $\gamma$ values of cluster centers are larger and discrete, while non-center services are continuous and smooth. The transition of $\gamma$ value from the cluster centers to the non-center services has a significant “jump”, this “jump” can be detected by numerical detection method [41]. Therefore, the cluster center of the dataset $S$ will be determined according to decision graph and numerical detection method.

4.3. Cluster Assignment

After the center of every cluster is assumed, the next step is to assign non-center services to clusters. Algorithm 2 describes the procedure of cluster assignment. Each service are assigned in the order of density descending, which is from the cluster center services to the cluster core services to the cluster halo services in the way of layer by layer.

Suppose that $n_c$ is the total number of cluster centers, naturally, the number of clusters is also $n_c$. ${\left\{m_j\right\}}_{j=1}^{n_c}$ is the index of corresponding service for each cluster center, i.e., service $s_{m_j}$ is the center of the $j\mathrm{th}$ cluster. ${\left\{c_i\right\}}_{i=1}^N$ is the cluster of each service belongs to, i.e., service $s_i$ belongs to cluster $c_i$. According to the definition of ${\left\{n_i\right\}}_{i=1}^N$ in Equation (9), $n_i$ is the index of service which has larger density than $i$th service ($s_i$) and closest to $s_i$.

Algorithm 2. Cluster Assignment
Input:	$q_i$: the descending order of index according to density $\rho$;
	${\left\{m_j\right\}}_{j=1}^{n_c}$: the index of cluster center of cluster j;
	$n_c$: total number of clusters (centers);
	$n_{q_i}$: the index of service which has larger density than $s_{q_i}$ and closest to $s_{q_i}$;
Output:	${\left\{c_i\right\}}_{i=1}^N$: the cluster of each service belongs to, i.e., $s_i$ belongs to $c_i$;
1: ${\left\{c_i\right\}}_{i=1}^N\leftarrow -1$; //initialization of $c_i$ 2: for j:=1 to $n_c$ do 3: $c_{m_j}$=j;     //cluster centers 4: end for Non-center services assignment 5: for i:=1 to N do //descending order of index 6:   if $c_{q_i}=-1$ then 7:     $c_{q_i}=c_{n_{{\mathrm{q}}_i}}$; 8:   end if 9: end for

If the dataset has more than one cluster, each cluster can be furthermore divided into two parts: cluster core and cluster halo. The cluster core with higher density is the core part of a cluster. The cluster halo with lower density is the edge part of a cluster. The procedure of determining cluster core and cluster halo is described in Algorithm 3. We define the border region of a cluster as: the border region of cluster $c_1$ is consisted by the services $s_i$ that belongs to $c_1$, and the distance between $s_i$ and $s_j$ (which belongs to another cluster $c_2$) is less than $d_c$. An average density bound is defined as ${\left\{{\rho }_{c_i}^b\right\}}_{i=1}^{n_c}$, ${\rho }_{c_i}^b$ is the average density bound of cluster $c_i$. If the density $\rho$ of service $s$ is larger than ${\rho }_{c_i}^b$, then service $s$ belongs to the core part of cluster $c_i$; otherwise, it belongs to the halo part of cluster $c_i$.

Algorithm 3. Determining Cluster Core and Cluster Halo
Input:	$F$: the matrix of distances between services;
	$d_c$: cut-off distance;
	${\left\{c_i\right\}}_{i=1}^{n_c}$: the cluster of each service belongs;
Output:	${\left\{h_i\right\}}_{i=1}^N$: the signal of core or halo that service $s_i$ belongs to;
Initialization 1: ${\left\{h_i\right\}}_{i=1}^N$ ← 0; 2: ${\left\{{\rho }_{c_i}^b\right\}}_{i=1}^{n_c}$ ← 0; 3: for i:=1 to N−1 do 4: for j:=I + 1 to N do 5:   if $c_i\ne c_j$ and $dist\left(s_i,s_j\right)<d_c$then 6:     ${\overline{\rho }}_{ij}=\frac{1}{2}\left({\rho }_i+{\rho }_j\right)$; 7:     if ${\overline{\rho }}_{ij}>{\rho }_{c_i}^b$ then 8:     ${\rho }_{c_i}^b={\overline{\rho }}_{ij}$; 9:   end if  10:   if ${\overline{\rho }}_{ij}>{\rho }_{c_j}^b$ then 11:     ${\rho }_{c_j}^b={\overline{\rho }}_{ij}$; 12:   end if 13: end if 14: end for 15: end for 16: for i:=1 to N 17: if ${\rho }_i<{\rho }_{c_i}^b$ then 18:     $h_i=1$;   //belongs to halo part of cluster $c_i$ 19:   end if 20: end for

After clustering, the similar service neighbors are generated automatically without the estimation of parameters. Moreover, different services have personalized neighbor sizes according to the actual density distribution, which may avoid the inaccurate matchmaking caused by constant neighbor size.

5. Experimental Evaluation

In this section, we evaluate the performance of proposed MDM measurement and service clustering. We use a combined data set including real and synthetic data, which collects service from multiple sources and adds essential service instances and descriptions. The data sources of combined service set are shown in

Table 1. Service set.

	Source	Number of Services	Number after Expansion
Outdoor	ABM	105	200
	LSM	100	200
	CCMWS	93	200
	DHCIS	76	200
Indoor	IntelLab	54	100
	MavHome	82	100
Total		510	1000

. In this paper, 510 real sensor services are collected from 6 sensor sets, including indoor and outdoor sensors. Then, the amount of service is expanded to 1000, and essential semantic service descriptions are supplemented for similarity measuring. The experimental evaluation is performed under the environment of 64-bit Windows 7 Professional, Java 7, Intel Xeon Processor E5-2650 2.3GHz processor, and 32 GB RAM. Section 5.1 discusses about the performance of MDM, and Section 5.2 discusses about the performance of service clustering.

5.1. Performance of Similarity Measurement

To evaluate the performance of similarity measurement, we employ the most widely used performance metrics from the information retrieval field. The performance metrics in this experiment are defined as follows:

Precision. Precision is used to measure the preciseness of a search system. Precision for a single service refers to the proportion of matched and logically similar services in all services matched to this service, which can be represented by the following equation:

$$Precision=\frac{\left|A{\displaystyle \cap }B\right|}{\left|B\right|}$$

where A is the number of logically similar service and B is the number of matched services calculated by MDM.

Recall. Recall is used to measure the effectiveness of a search system. Recall for a single service is the proportion of matched and logically similar services in all services that are logically similar to this service, which can be represented by the following equation:

$$Recall=\frac{\left|A{\displaystyle \cap }B\right|}{\left|A\right|}$$

F-measure. F-measure is employed as an aggregated performance scale for a search system. In this experiment, F-measure is the mean of precision and recall, which can be represented as:

$$F-measure=\frac{2\times Precision\times Recall}{Precision+Recall}$$

When the F-measure value reaches the highest level, it means that the aggregated value between precision and recall reaches the highest level at the same time.

In order to filter out the dissimilar services with lower similarity values, an optimal threshold value is needed to be estimated. In addition, the aggregative metric of F-measure is used as the primary benchmark for estimating the optimal threshold value. Besides, parameter δ is the impact of description and structure similarity for similarity measuring. To obtain the best performance, an optimal $\delta$ value should also be estimated. The initial values of two parameters are set to 0, and increasing incrementally by 0.1 until 1.0.

Figure 4 and Figure 5 demonstrate the variation of F-measure values of dimension-mixed and multidimensional model as the changing of these two parameters. When the value of F-measure reaches the highest point, it achieves the best performance, and the optimal value of threshold and $\delta$ will be determined. As Figure 4 and Figure 5 indicates, δ = 0.5 and threshold = 0.8 are the optimal values of dimension-mixed model, and the F-measure is 40 with these parameters; meanwhile δ = 0.7 and threshold = 0.7 are the optimal values of multidimensional model, and the F-measure is 63 with these parameters. Besides, the overall F-measure values of multidimensional model are higher than dimension-mixed model.

The performance comparison between multidimensional and dimension-mixed model is shown in Figure 6. As the results indicate, the performance of similarity measurement based on the multidimensional model outperforms to the dimension-mixed way. The reason is that, employing the multidimensional model, both description similarity and structure similarity can be measured accurately. For the structure similarity, each dimension has a well-defined semantic structure in which the distance and positional relationships between nodes are meaningful to reflect the similarity between services. For the description similarity, each dimension only focuses on the descriptions that are contributed to expressing the features of current dimension. Conversely, using the dimension-mixed way, which mixes the semantic structures and descriptions of all dimensions into a complicated model, the measurement can only obtain an overall similarity value.

5.2. Performance of Service Clustering

In this section, we evaluate the performance of clustering. The number of service that will be clustered is 1000 with essential semantic description and structure, as Table 1 describes. The cut-off distance $d_c$ for calculating local density of services is set to 0.03. As Figure 7 shows, although the service set is high overlap in data distribution, the proposed approach successfully detects the cluster structure. The services are clustered into 5 clusters, the borders of clusters are clear, and each cluster is dense and compact.

The size of service set and the number of feature dimensions are two important factors to evaluate the efficiency of proposed clustering approach. Figure 8 shows the time of clustering as the size of services is increased from 100 to 1000. The time of clustering 1000 services is 3.2 s. The results show that the clustering time is linear with respect to the number of IoT services to be clustered, and the clustering time of hundreds services is controlled within a few seconds. Figure 9 shows the time of clustering as the dimensions of service model increasing from 1 to 10. The number of services that will be clustered is set to 1000. The minimum clustering time is 2.8 s, when there are four feature dimensions of the model; and the maximum clustering time is 3.3 s, when the number of feature dimensions is eight. The results show that the clustering time will not increase as the increase of dimension number. It is because that MDM measures each dimension’s similarity concurrently. Thus, the whole time of measuring similarity of all dimensions is equal to the time of single dimension that takes longer time than other dimensions. Besides, the clustering is based on the measurement result of MDM (distances between services), it will not be influenced by the dimension number. Therefore, the proposed approaches improve the accuracy of similarity measurement and service clustering in the condition of not increasing the computation time.

The experimental results demonstrate that, the proposed clustering approach is able to cluster hundreds of IoT services in a reasonable amount of time. In the application domains of IoT SOC paradigm, the number of services usually does not exceed several thousands. Besides, if the scale of services is very large, the service clustering can be performed offline. Thus, the performance of proposed clustering approach is competent for applying in real application scenarios.

6. Conclusions

This paper proposes a multidimensional model-based approach to measure the similarity between IoT services. Then, density-peaks-based clustering is employed to gather similar services together according to the result of similarity measurement. A combined data set is used to evaluate the proposed approaches, which collects service from multiple sources and adds essential service instances and descriptions. The experiment results demonstrate that the performance of proposed approaches are promising and applicable to real-life scenarios.

Currently, the experiments are conducted using a centralized single dataset, and the size of test set is limited. Our future works include extending the experiments using distributed datasets and expanding the number of service set. Moreover, we plan to propose a quantitative model to diagnose the quality of service clustering, then to determine when the clustering structure becomes unacceptable and require re-clustering as the evolution of services.