An efficient indexing and query mechanism for ubiquitous IoT services 247
according to their functional description, and their spatial and
temporal constraints. A query mechanism is developed for
facilitating the query of IoT-WSs with as less computation
effort as possible. In a nutshell, IoT-WSs are firstly clustered
according to their functionality description. Spatial indexing
method is applied for organising IoT-WSs according to their
spatial property. As to the temporal aspect, we assign IoT-WSs
into some time slots based on their temporal specification. The
main contributions of this paper include the following three
aspects:
• IoT-WS multi-indexes. Indexes are built for organising
IoT-WSs according to their functionality descriptions,
spatial and temporal specifications.
• Management of IoT-WS clusters and indexes.
Mechanisms are proposed for managing IoT-WS
clusters and indexes when IoT-WSs joins or leaves the
network.
• IoT-WS query mechanism. Query mechanism is
proposed for searching IoT-WSs leveraging the indexes
we have built. Our technique requires less computation
effort compared with directly searching IoT services
according to their functionality similarity.
Preliminary result of this paper has been reported in our
previous work (Du et al., 2013a). The current paper gives
a new and more comprehensive presentation and discussion
about IoT-WSs indexing and query mechanisms, including
details of definitions, tractable algorithms, and evaluation of
the algorithms.
The rest of this paper is organised as follows. In Section 2
we present the definition of IoT-WS. In Section 3 we review
related techniques. In Section 4 we propose the multi-
index method to group IoT-WSs into functionality cluster,
spatial and temporal indexes, and provide some operations
for managing the cluster and indexes. In Section 5 we
propose a query algorithm for searching IoT-WS leveraging
our multi-index method. In Section 6 we present the prototype
implementation and the evaluation of our technique. Finally,
we conclude this paper in Section 7.
2 IoT-WS: preliminary
Below we give a formal definition of IoT-WS, where spatial
and temporal attributes are considered as the first-class
citizens:
Definition 1 (IoT-WS): An IoT-WS is a tuple
S = (ID, Des, Ip, Op, AveF D, Loc, T em)
where ID is the id of this IoT-WS, Des is its functionality
description, Ip is a set of input variables, Op is a set
of output variables, AveFD is the average distance of the
functionality specification with respect to other IoT-WSs
within a functionality cluster, Loc is a set of the service’s
spatial properties describing its location and spatial range,
Tem is a set of the service’s temporal properties describing its
temporal constraints.
Generally, Des, Ip and Op are used to calculate functionality
similarity degree between IoT-WSs. This process is similar
to other services functionality similarity clustering methods.
AveFD represents the average functionality distance of
a certain IoT-WS with respect to other IoT-WSs in the
functionality cluster. The IoT-WS having the smallest AveFD
is chosen as the representative of the functionality cluster, for
representing the main functionality of this cluster. Loc and Tem
are applied for organising IoT-WSs considering their spatial
and temporal constraints.
In Figure 1, we present some sample IoT-WSs in smart city,
which are used for the illustration purpose of our technique in
the following sections. Intuitively, the (real-time) information
observed by the objects in a city helps people make the right
decision, and thus keep the whole city running properly and
response to the emergency events quickly. For example when
a fire is breaking out in the downtown, the fireman needs to
figure out the situation around the fire location through using
sensing devices to collect live data, such as collecting the
components in the air to determine whether the gas coming out
of the fire is above the threshold allowed, and getting known
the wind direction in order to make a reasonable residents
evacuation plan when necessary. Mostly, all these functions
rely on the high-quality services built upon sensor networks
(Wu and Hsieh, 2012). The traffic situation is also required
to be monitored for finding the appropriate rescue route. The
spatial distribution of these sample IoT-WSs used in this
scenario is shown in Figure 1 and their description is presented
in Table 1.
Figure 1 Sample IoT-WSs in smart city
Before presenting our multi-index method for organising IoT-
WSs properly in order to facilitating the query on certain
regions with spatial and temporal restrictions, we review and
compare related techniques in the next section.
3 Related work and comparison
The clustering and discovery of IoT services with spatial and
temporal constraints is a hot research topic in recent years. In
the following, we classify and discuss the related techniques