close

Вход

Забыли?

вход по аккаунту

?

ijwgs.2016.080135

код для вставкиСкачать
388
Int. J. Web and Grid Services, Vol. 12, No. 4, 2016
Optimal algorithm for Internet-of-Things service
composition based on response time
Wonhong Nam
Center for Eco-Informatics,
Department of Internet and Multimedia Engineering,
Konkuk University,
Seoul 143-701, South Korea
Email: wnam@konkuk.ac.kr
Reeseo Cha
Department of Computer Science and Engineering,
Korea University,
Seoul 136-701, South Korea
Email: reeseo@formal.korea.ac.kr
Hyunyoung Kil*
Software Policy & Research Institute,
Seongnam, Gyeonggi, 13488, South Korea
Email: hkil@spri.kr
*Corresponding author
Abstract: In the near future, the Internet-of-Things (IoT) technology will
improve dramatically our daily life as a new pervasive computing paradigm.
For the IoT computing, various devices and wireless networks are the hardware
infrastructure, and Service-Oriented Architecture (SOA) is a valuable software
system that allows heterogeneous devices to interoperate each other. Even
though IoT researchers have tackled a number of challenges for service
composition, the orchestration techniques on IoT are rarely studied yet.
Moreover, it is hard to automatically compose IoT services with an optimal
aggregate response time since we have to compare all the combinations of
parallel/serial structures in a composite IoT service. In the SOA literature,
many researches on QoS-aware composition consider parallel work-flows, but
they employ service selection models that require users to manually or semiautomatically predefine a top-level work process. Accordingly, they cannot
guarantee the optimal solution. In this paper, we hence propose a novel IoT
service composition algorithm which automatically produces a composite IoT
service with a minimal response time.
Keywords: IoT; Internet-of-Things; service composition; response time
optimisation.
Reference to this paper should be made as follows: Nam, W., Cha, R. and
Kil, H. (2016) ‘Optimal algorithm for Internet-of-Things service composition
based on response time’, Int. J. Web and Grid Services, Vol. 12, No. 4,
pp.388–406.
Copyright © 2016 Inderscience Enterprises Ltd.
Optimal algorithm for IoT service composition based on response time
389
Biographical notes: Wonhong Nam received the BS and MSc degrees from
Korea University, Seoul, Korea, in 1998 and in 2001, respectively, and the PhD
degree from the University of Pennsylvania, Philadelphia, PA, USA in 2007.
From 2007 to 2009, he was a Postdoctoral Researcher with the College
of Information Sciences and Technology, Pennsylvania State University,
University Park, PA, USA. He is currently an Associate Professor of the
Department of Internet & Multimedia Engineering, Konkuk University, Seoul,
Korea. His research interests include formal methods, formal verification,
model checking, automated planning, and web services composition.
Reeseo Cha received the BS and MSc degrees from Korea University, Seoul,
Korea, in 2001 and in 2006, respectively. He is currently a PhD candidate at
the Department of Computer Science and Engineering, Korea University,
Seoul, Korea. His research interests include formal methods, formal verification,
theorem proving, type systems and functional programming.
Hyunyoung Kil received the BS and MSc degrees from Korea University,
Seoul, Korea, in 1998 and 2001, respectively. She received the MSE degree
from the University of Pennsylvania, Philadelphia, PA, USA in 2003, and the
PhD degree from the Pennsylvania State University, State College, PA, USA in
2010. She is currently a senior researcher of Software Policy & Research
Institute, Seongnam, Korea. Her research interests include automated planning,
web services composition, SOA and web sciences.
1
Introduction
Nowadays, billions of people use the internet – the global information and communication
infrastructure – and more people will be expected to access it for their daily life and
business. The growth of the internet stimulates appearance of a new pervasive paradigm
in computing and communications, named the Internet-of-Things (IoT). The basic
idea of IoT is to interconnect the pervasive presence around our daily life such as
computers, smart phones, household appliances, and commodities which are identifiable,
addressable, and controllable via the internet (Atzori et al., 2010). These smart things on
the network can interact with each other and even cooperate for common goals.
Unquestionably, the IoT technology will have a high impact on our daily life by
integrating the physical world entities into virtual world things (Xu, 2011).
The impetuses behind IoT are the technological development in hardware devices and
wireless networks, and Service-Oriented Architecture (SOA). As devices are becoming
smaller, cheaper, and more powerful, we expect that in the near future most of devices
have enough communication and computation capabilities in themselves. In addition, the
explosive growth of wireless network can strongly support network environment where
these devices can be connected. While these devices and wireless networks are the
hardware infrastructure for IoT, Service-Oriented Architecture (SOA) is a fertile ground
for a new real-world software breed on IoT.
SOA is a software design principle based on a service. A service is a self-contained
unit of application functionality showing the following characteristics; autonomous,
encapsulated, well-defined, discoverable, platform-independent, reusable, and interoperable. Due to these features, the advantages of the SOA approach are recognised in
most studies on IoT middleware as recent internet-based applications acquire the same
benefits from SOA.
390
W. Nam, R. Cha and H. Kil
Figure 1 illustrates the SOA-based IoT architecture which can be represented as a set
of software layers interposed between things and users, i.e., from bottom to top, the thing
abstraction layer, the service management layer, the service composition layer, and the
application layer. The thing abstraction layer provides a web interface discoverable on
networks in a standard web service so that heterogeneous objects can access each other in
common languages and expose themselves as services to other layers. The service
management layer performs various work for these service entities, such as service
discovery, service status monitoring, and QoS management. Based on the service
management layer, the service composition layer can produce a composite service for a
given specific user request by combining given services, and the application layer
provides users all functionalities of the systems.
Figure 1
SOA-based IoT architecture (see online version for colours)
Based on the SOA-based middleware architecture, we expect that in the future, a number
of real-world things will be able to offer their own functionality as a service which is
described in web services standard description languages (WS*), enabling other
components to interact with them. In this environment, how to automatically produce a
composite IoT service for a given request is a significant research issue, which has
received a lot of attention in the service computing literature. However, although the IoT
raises additional challenges for service composition, especially with respect to handling a
large number of heterogeneous real-world objects, the orchestration techniques on IoT
are rarely studied yet. In addition, we also notice that in an IoT scenario, the proportion
of ordinary users in service clients will get more increased since IoT techniques aim to
handle various real-world objects. For these users, response time is one of the most
sensitive factors in selecting a service and this tendency will grow stronger as IT
technology goes further (Nah, 2004). Based on the recent study on relation between
users’ behaviour and response time, 1 second is a certain threshold in which the users
could feel the added delay with very high likelihood (Arapakis et al., 2014). Therefore,
service developers and providers make every effort to efficiently provide a service with
the shorter response time to users. Above all, in emergency cases, such as a heart attack
and car accidents where people’s lives can be at stake, a faster execution of a service is
Optimal algorithm for IoT service composition based on response time
391
desirable. However, it is not trivial to automatically construct a composite service with an
optimal aggregate response time since we should consider all the combinations of
parallel/serial structures in a composite service for the minimum aggregated response
time. Most of studies (Li et al., 2012; Lia et al., 2014) on QoS-aware composition
allowing a parallel work-flow are based on service selection models where users should
manually or semi-automatically predefine a top-level work process with sub-tasks.
Due to the manual process, they cannot guarantee the optimal solution and they
impose a burden on common users. Therefore, in this paper, we propose an IoT service
composition algorithm which automatically generates a composite IoT service with an
optimal response time. To the best of our knowledge, there is no work to automatically
compose an IoT service with the optimal response time.
The rest of this paper is organised as follows. In Section 2, we discuss related work
with our research. In Section 3, we illustrate a motivate example and lay out the notions
and the problem we study in this paper. Next, in Section 4, we propose our algorithm to
produce a composite IoT service with an optimal aggregate response time. In Section 5,
we present the experimental result to validate our algorithm proposed in this paper.
Finally, we give conclusions in Section 6.
2
Related work
As recently Internet-of-Things (IoT) has emerged as a new initiative for a global
information infrastructure, many literatures introduce IoT including its related
technologies and research issues (Atzori et al., 2010; Gubbi et al., 2013; Nah 2004;
Bandyopadhyay and Sen 2011). Although there are open discussions due to manifold
definitions of IoT and different visions of research communities, most work agrees that
the Service-Oriented Architecture (SOA) is a preferable approach in IoT software
systems to ensure inter-operability across all systems. Since SOA- based technologies
can abstract specific device functionalities and expose them as services to higher
software arrays or other IoT entities, various projects to integrate SOA with IoT have
been conducted.
The SIRENA project (James and Smit, 2005) employs the SOA paradigm to develop
a service infrastructure for embedded network-based applications and proposes an early
version of Devices Profile for Web Services (DPWS) (Microsoft Corporation, 2006).
To aim for heterogeneous device integration, DPWS defines a minimal set of
implementation constraints and enables web service operations on embedded devices.
Following the SIRENA project, SODA (Service Oriented Device and Delivery
Architecture) (Deugd et al., 2006), SOCRADES (Souza et al., 2008), the IMC-AESOP
(2006), and Web Services for Devices (WS4D) project (Web Services for Devices, 2006)
propose SOA-based solutions, especially using web services technology, for various
applications in real-world domains complying with the DPWS.
There are two ways in implementing web services, i.e., REST and WS-* standards.
The RESTful web services have the advantage in their universal service interface, which
can help people to easily learn IoT application programming (Guinard et al., 2011;
Russell and Norvig, 2003). The work (Spiess et al., 2009; Guinard et al., 2009) propose
a lightweight mash-up approach to integrate enterprise services and IoT services
for wireless sensor networks and implement an architecture where sensor nodes are
392
W. Nam, R. Cha and H. Kil
accessible according to the REST principles. Guinard et al. (2010) deal with finding IoT
services on embedded devices on networks. While RESTful technologies address only
basic distributed interaction and coordination, WS-* technologies allow more expressive
descriptions than REST (Guinard et al., 2011; Pautasso et al., 2008). Therefore, web
service standard-based work makes various attempts in dealing with service behaviour,
semantics, and quality of services. The researches (Cubo et al., 2012; Mayer et al., 2012)
use WS-* specifications to specify service interfaces of things by adding a set of
constraints to the guidelines exposed by DPWS which can represent the behaviour of
single and composite things. Sommer et al. (2009) propose a development platform for
embedded networks, named eSOA which supports a seamless semantic interaction
between services. For QoS specification, there have been many standardisation efforts
such as WS-Policy (2006), Web Service Level Agreement (WSLA) language (WSLA,
2004) and WS-Agreement (2007) in web service research field. The IoT community also
follows these standards on QoS description of IoT services. However, there is few work
about QoS-aware IoT service management up to our knowledge. Lia et al. (2014)
formulate the QoS-oriented service composition problem as a multi-criteria goal
programming model. For a large scalability, they develop a multi-population genetic
algorithm which automatically assigns high quality web services for a composite service
and finds non-inferior composite services by relaxing QoS constraints to satisfy users’
QoS requirements. Li et al. (2012) propose a probabilistic approach to formally describe
for the service composition in IoT but consider only the reliability and cost-related
properties of services. However, since both of them are based on a service selection
model, they require users to manually or semi-automatically predefine a top-level work
process with sub-tasks. They can neither automatically generate an optimal structure for
response time nor guarantee the optimal answer. Li et al. (2014) has proposed a threelayer QoS scheduling model for service-oriented IoT, but their method do not
automatically produce the optimal composite IoT service. Recently, Kil et al. (2016)
propose a novel QoS-aware WSC method based on the real service transaction history of
web services, which employs the anytime algorithm technique.
3
Internet-of-Things service composition based on response time
In this section, we present a motivate example and then formalise the notion of Internetof-Things (IoT) services and their compositions based on response time, which we
consider in this paper.
3.1 Emergency response system
Consider an emergency response system for chronic patients. When the heartbeat and the
blood pressure measured are abnormal (e.g., when a heart attack occurs), the system can
notice to the emergency department in an available hospital near to the patient, call to
emergency contact persons, and send patient’s medical history to the emergency
department. Moreover, since the system handles emergent situations, the response time
of the system is the most significant factor. Assume that we want to build the emergency
response system by composing out of a number of IoT services with different response
times.
Optimal algorithm for IoT service composition based on response time
393
Figure 2 describes the example. Initially, the system has the following information:
user’s ID and password, the phone numbers of emergency contact persons. When
receiving the correct ID and password, the Sensor sends the current heartbeat and blood
pressure of the owner. The Smartphone receives the ID and password, and provides
owner’s location. Given a heartbeat, a blood pressure and a location, the FHS (Find
Hospital Service) finds an available hospital around the location and sends the name and
the address of the hospital. The ECS (Emergency Call Service) calls emergency contact
persons to inform them of the name and the address of the hospital. When the MHS
(Medical History Service) gets client’s ID and password and a hospital name, it sends
client’s medical history to the emergency department of the hospital. The response times
for each thing and service are as follows: RSensor = 1000 msec, RSmartphone = 500 msec,
RFHS = 200 msec, RECS = 100 msec, and RMHS = 200 msec, respectively. In this example,
we have to consider various combinations of IoT services and various solution structures
of them, since there are a huge number of IoT services other than the above. For instance,
the serial composition (Sensor ◦ Smartphone ◦ FHS ◦ ECS ◦ MHS) in Figure 2(a)
accomplishes our goal with the aggregate response time 2000 msec. However, the
optimal solution is (Sensor || Smartphone) ◦ FHS ◦ (ECS || MHS) where || represents a
parallel composition, as its aggregate response time is 1400 msec (see Figure 2(b)).
Figure 2
Emergency response system
(a) Serial composition
(b) Parallel composition
394
W. Nam, R. Cha and H. Kil
3.2 Internet-of-Things service composition problem
3.2.1 Internet-of-Things service and composition
Definition 1 (parameter): A parameter is a placeholder standing for the meaning of its
expected values. Every parameter p has its type denoted by  ( p ).
Example 1 (parameter): Parameters lender and borrower are placeholders for the
values of Name type, such as “John Doe”, “Jane Roe”, etc.
Definition 2 (subtype relation): Given two types t1 and t2, t1 is a subtype of t2 (denoted by
t1 <: t2) iff every value of t1 type is also a value of t2 type.
In this case, t2 is a supertype of t1. This relation is reflexive (i.e., t <: t for any type t) and
transitive (i.e., if t1 <: t2 and t2 <: t3 then t1 <: t3).
Definition 3 (informativeness relation over parameters): Given two parameters p1 and p2,
p1 is more or equally informative than p2 (denoted by p1  p2 ) iff  ( p1 ) :  ( p2 ).
Definition 4 (IoT service): An IoT service s is a pair I , O where:

I is a finite set of input parameters required to invoke s, and

O is a finite set of output parameters returned by s.
Example 2 (IoT service): An IoT service
{PostAddr}. {ZipCode, Magnitude, Longitude}
takes a postal address and returns the zip-code, magnitude and longitude for the given
postal address.
Definition 5 (state): A state is a finite set of already-acquired parameters at a certain time.
Definition 6 (invocability of an IoT service): Given a state P and an IoT service
s  I , O , s is invocable at P iff for every input parameter i  I , there exists an alreadyacquired parameter p  P such that p is more or equally informative than i. Formally,
s  I , O is invocable at P  i  I , p  P, p  i.
Also, given a state P and an IoT service s  I , O which is invocable at P, the resulting
state P after running of s is a set P  O.
Definition 7 (null IoT service): A null IoT service is an IoT service  ,  , denoted by
the symbol .
This special IoT service is regarded as available at any situation, is invocable at any state,
and never changes the state after running alone.
Definition 8 (informativeness relations over IoT services): Given two IoT services
s1  I1 , O1 and s2  I 2 , O2 , si is more or equally input-informative than s2 (denoted
by s1 I s2 ) iff si requires more or equally informative inputs than s2; i.e., s2 is invocable
Optimal algorithm for IoT service composition based on response time
395
at every state where si is invocable. Inversely, s2 is more or equally output-informative
than si (denoted by s1 O s2 ) iff s2 provides more or equally informative output than s1;
i.e., any IoT service invocable at O1 is also invocable at O2.
Definition 9 (IoT service discovery problem): Given a set S of available IoT services and
a requested IoT service sr, an IoT service discovery problem is to find an IoT service
s  S such that sr  I s and sr O s.
However, it might happen that there is no single IoT service satisfying the requirement.
In that case, we want to find a composition of IoT services such that we can invoke one
or more IoT services in each step and achieve the desired requirement eventually. For
this purpose, we define the notion of a composite IoT service. From now on, for
distinction, we will call IoT services defined in the definition 4 and 7 as atomic IoT
services.
Definition 10 (composite IoT service): A composite IoT service (or shortly, a
composition) is an IoT service which is constructed using any of the following three
cases, inductively:

base case: Any atomic IoT service s itself is a composite thing, denoted by s (as is).

step case 1 (serial composition): Given two or more composite IoT services
s1  I1 , O1 s2  I 2 , O2 , , sn  I n , On (where n  2), an IoT service I , O is a
composite thing, denoted by ( s1 o s2 o o sn ), where:
 I  I1  ( I 2 \ O1 )  ( I 3 \ (O1  O2 ))    ( I n \ (O1    On 1 ))
  ni 1 I i \   nj11 O j 
O  O1  O2    On   ni 1 Oi

step case 2 (parallel composition): Given two or more composite IoT services
s1  I1 , O1 , s2  I 2 , O2 , , sn  I n , On
(where n ≥ 2), an IoT service
 ni 1 I i ,  ni 1 Oi
is a composite IoT service, denoted by ( s1 || s2 ||  || sn ).
Intuitively, the serial composition ( s1  s2  sn ) means that each IoT service in the
given composition is invoked one by one in that order, and the parallel composition
( s1  s2  sn ) means that all the IoT services in the given composition are invoked
simultaneously.
We can abuse the relations I and O over composite IoT services, since a
composite thing itself is also a thing. Now, we extend the IoT service discovery problem
to the IoT service composition problem as follows.
Definition 11 (IoT service composition problem): Given a set S of available IoT services
and a requested IoT service sr, an IoT service composition problem is to find a composite
IoT service s such that sr I s and sr O s.
396
W. Nam, R. Cha and H. Kil
3.2.2 Internet-of-Things service composition problem
based on response time
We extend the notion of IoT services defined by Definition 4 to the notion of IoT
services with response time as follows.
Definition 12 (IoT service with response time): An IoT service with response time s is a
triple I , O, R , where I and O are as described in Definition 4 and R is a number
indicating the response time of s.
Definition 13 (null IoT service with response time): A null IoT service with response
time is an IoT service  ,  , 0 , denoted by the symbol .
Example 3 (IoT service with response time): An IoT service with response time
{PostAddr},{ZipCode, Magnitude, Longitude}, 351
takes a postal address and returns the corresponding zip-code, magnitude and longitude
in 351 milliseconds.
In order to extend the IoT service composition problem to a problem based on
response time, we need to extend the notion of compositions in the Definition 10 as
follows.
Definition 14 (composite IoT service with response time): A composite IoT service with
response time is an IoT service with response time which is constructed using any of the
following three cases, inductively:

base case: Any atomic IoT service with response time s itself is a composite IoT
service with response time, denoted by s (as is).

step case 1 (serial composition): Given composite IoT services with response time
s1  I1 , O1 , R1 , s2  I 2 , O2 , R2 , , sn  I n , On , Rn , an IoT service with response
time
 ni 1 I i \   nj11 O j  ,  ni 11 Oi ,  i 1 Ri
n
is a composite IoT service, denoted by
( s1  s2  sn ).

step case 2 (parallel composition): Given two or more composite IoT services with
response time s1  I1 , O1 , R1 , s2  I 2 , O2 , R2 , , sn  I n , On , Rn (where n  2),
an IoT service with response time
 ni 1 I i ,  ni 1 Oi , max( R1 , R2 , , Rn ))
is a
composite IoT service with response time, denoted by ( s1 || s2 ||  || sn ).
Definition 15 (response time-based IoT service composition problem): Given a set S of
available IoT services with response time and a requested IoT service sr, a response timebased IoT service composition problem is to find a composite IoT service s such that
sr I s and sr O s, and its response time is minimal.
Optimal algorithm for IoT service composition based on response time
4
397
Optimal algorithm for Internet-of-Things service
composition based on response time
In this section, we propose an optimal algorithm for the Internet-of-Things (IoT) service
composition problem based on response time. Given a set of IoT services and a user
request, our algorithm automatically composes an IoT service out of the service set,
which satisfies the given user request and has the minimal aggregate response time. To
guarantee the minimal response time, for each data item the algorithm identifies the way
with optimal response time which produces the data item. The algorithm continues this
process until we find the ways for all data items in the given user request. First we
explain our algorithm and then present the proof for the correctness of our algorithm.
Our algorithm includes two phases – the first phase presented in Algorithm 1 finds
the earliest way to generate each data item in a user request, and the second phase
illustrated in Algorithm 2 picks up only the necessary IoT services and produces a
composite IoT service to satisfy the user request. If the IoT service composition problem
allows only serial compositions as a solution, we may employ the uniform cost search
algorithm (Russell and Norvig, 2003) which is a breath-first search version on weighted
graphs. The search continues by visiting the next node that has the least total cost from
the root until a goal node is reached, where the total cost is computed as a summation of
each edge’s weight. However, the IoT service composition problem we study in this
paper allows parallel compositions as well as serial compositions in a solution. Remark
that the response time of a parallel composition s1 || s2 ||  || sn is max( R1 , R2 , , Rn )
where Ri is the response time of si. That is, if s1 and s2 are both invocable and the
response time of s1 is longer than one of s2, the response times of s1 and s1 || s2 are same.
Accordingly, our algorithm exploits the maximum parallelism; that is, it executes IoT
services in parallel whenever services are invocable. Then, our algorithm can compute
the earliest time to acquire each data item. Since the search may contain unnecessary
parallel compositions which are no help to accomplish the user request, we finally collect
the necessary IoT services only.
Algorithm 1 is given a set of IoT services and a user requirement as inputs. At the
beginning, it computes a universal set of all the data items included in the given problem
instance (line 1). The algorithm maintains the current simulation time, time, and a set
ItemsAcquired of data items acquired until now, and initially sets them as 0.0 and Input,
respectively (lines 2-3). We compute a time AcquiredTime[item] for each data item,
and initially assign 0.0 for the items in Input since the data items are already given
by Input (lines 4-7). In addition, our algorithm constructs a table Table[item] for each
data item that represents which service can produce the item first. As the simulation time
goes by, the algorithm repeats as follows: (1) it finds currently invocable IoT services
and enqueues them into a priority queue which is sorted by services’ response time
(lines 9-15), (2) the algorithm removes the earliest finishing service from the queue
and modifies the current simulation time as the completion time of the IoT service
(lines 16-20), and (3) the algorithm finally collects the output data items of the service,
and sets the AcquiredTime[item] and Table[item] for items in the outputs as the current
time and the current service, respectively (lines 21-26). We repeat the loop until finding
all data items in the user request. After the loop, the algorithm constructs a solution from
Table[] by calling constructSolution() in Algorithm 2.
398
W. Nam, R. Cha and H. Kil
Algorithm 2 illustrates procedures to inductively construct the optimal composition from
Table which is produced in Algorithm 1. The procedure constructSolution()
constructs the top level of a solution which is a parallel composition of composite IoT
services, s1 || s2 ||  || sn , where each composite service si produces one of data items in a
given user request (line 3-7). Since the response time of a parallel composition
s1 || s2 ||  || sn is max( R1 , R2 , , Rn ) where Ri is the response time of Si, the aggregate
response time depends only on one of composite services which has the maximum
response time. Note that for each data item in the user requirement, Table[item]
represents which service can produce it first. However, to invoke the service represented
by Table[item], we need all inputs of the service, i.e., the precondition of the service
should hold. Accordingly, the composite service si above should be a serial composition
of the precondition for the service represented by Table[item] and the service. Given a
IoT service s and Table, the procedure constructSub() first constructs the
precondition for s (lines 10–15) and then returns a serial composition of the precondition
Optimal algorithm for IoT service composition based on response time
399
and the given service s (line 16). The precondition is again a parallel composition of
composite services, t1 || t2 ||  || tn , where each composite service tj produces one of
inputs for s (line 11–15). To construct each tj , we again call constructSub() until
all the inputs are included in Input provided by the given user request. We also have two
auxiliary procedures, parallel() and serial() which are the parallel composition
and the serial composition, respectively, for given two IoT services (lines 17–27).
Now, we prove the correctness of our algorithm by Lemma 1 (which claims that our
algorithm computes the earliest acquired time for each data item) and Theorem 1 (which
claims that our algorithm constructs a composite IoT service with the optimal aggregate
response time).
Lemma 1 Suppose that our IoT service composition algorithm is given a set S of IoT
services and a requested IoT service sr. Upon termination, the algorithm computes
acquireTime[item] =  (item) for all item  ItemsAcquired where (item) is the earliest
time to acquire item.
(by contradiction): Assume that when the IoT service composition algorithm terminates,
there are some data items p for which AcquiredTime[p] is greater than its earliest time to
acquire p (i.e., AcquiredTime > (p)). Let pmin be the data item with minimum (p)
among data items with incorrect AcquiredTime[p]. Let s be the IoT service which
400
W. Nam, R. Cha and H. Kil
produces pmin in the optimal composite service, so that  ( pmin )   ( s )  s.responseTime
where (s) is the earliest time when we can invoke s. Since the IoT service s produces
pmin on the optimal composite service, all the input parameters in of s have been acquired
before pmin. Since pmin is the data item with minimum (p) among data items with
incorrect AcquiredTime [p], we have AcquiredTime [in] = (in). Therefore, s .invokeTime
= 5(s) since the algorithm invokes any IoT service whenever the service is invocable.
Since s.invokeTime + s.responseTime = s.completeTime, we have
AcquireTime[ pmin ]   ( s)  s.responseTime
 s.completeTime
(1)
Now, consider the time when the algorithm dequeues s in line 21. At this time, pmin is
either in ItemsAcquired already or not. We shall show that in both cases, we derive a
contradiction to (1). If pmin is not in ItemsAcquired, AcquireTime[pmin] = s:completeTime
by lines 25, contradicting to (1). If pmin is already in ItemsAcquired, then there is another
IoT service s which produces pmin and s was dequeued before s from the queue. Since
the queue is a priority queue on the completion time of services, s.completeTime 
s:completeTime. Hence, AcquireTime[pmin] = s.completeTime  s:completeTime, once
again contradicting to (1). Finally, we conclude acquireTime[item] =  (item) for all item
 InfoAcquired.
Theorem 1 Given a set S of IoT services and a requested IoT service sr, the IoT service
composition algorithm constructs an IoT composite service s with the optimal response
time, which satisfies the user request sr  I , O .
T: o satisfy the user request, s should produce every o  O. By the lemma 1, the
algorithm computes the earliest time for every data items item  InfoAcquired (including
o  O), and Table[item] represents the service which produces item first. For
o1 , o2 , , on  O, the algorithm constructs a solution s1 || s2 ||  || sn where each si is the
composite service that produces oi. Since the algorithm computes the optimal way for
every item  ItemsAcquired not only o  O, it constructs each composite service si with
the optimal response time.
5
Experiment
We have implemented an automatic tool for the algorithm in Section 4, i.e., an IoT
service composition tool based on response time. Given a WSDL file for a set of IoT
services, an OWL file for the type information, a WSLA file for the response time for
each IoT service, and a WSDL file for a requirement IoT service, our tool automatically
constructs the optimal composite service out of the given IoT service set. Finally, our
tool translates the optimal composite service into a BPEL file.
To demonstrate that our tool efficiently identifies an optimal solution, we have
experimented on a number of problem instances generated by the TestSetGenerator
which the Web Service Challenge 2009 competition (Kona et al., 2009) provides. All
experiments have been performed on a PC using a 2.93GHz i7 processor, 4GB memory
and a Linux operating system.
Optimal algorithm for IoT service composition based on response time
401
The first set of experiments illustrated in Table 1 shows how strongly execution time
and memory usage depend on the number of IoT services. With the fixed number of data
items (i.e., 10,000, 50,000, and 100,000, respectively), we have measured the execution
time and memory usage of our tool as increasing the number of IoT services from 1,000
to 10,000. In the case of 10,000 data items, our tool has produced, for the problem
instance including 1,000 IoT services, the optimal composite IoT service in 0.39 sec and
consumed 37,936 KB memory. Also, it has solved the problem instance including 2,000
IoT services in 1.05 sec with 56,080 KB memory. Finally, it has identified the optimal
solution in 35.91 sec with 187,632 KB memory for the problem instance including
10,000 IoT services. In the cases of 50,000 data items and 100,000 data items, our
tool has shown the similar results, respectively. The experiment results with 10,000,
50,000, and 100,000 data items are represented also in Figure 3 (a) to (c), respectively.
The plots show that the execution time and memory usage increase linearly. This
consequence is consistent with the fact that the dominant part of our main algorithm is
FindInvocableServices() which has linear complexity on the number of IoT services.
Table 1
IoT
services
1,000
2,000
3,000
4,000
5,000
6,000
7,000
8,000
9,000
10,000
Figure 3
Experiment results as increasing the number of IoT services
Data items = 10,000
Time (sec)
Mem (KB)
0.39
37,936
1.05
1.99
4.88
8.33
11.88
18.17
24.41
33.00
35.91
56,080
71,840
92,736
109,008
128,672
147,424
163,296
181,680
187,632
Data items = 50,000
Time
Mem
0.38
40,704
Data items = 100,000
Time
Mem
0.41
41,248
1.21
2.79
5.88
9.62
16.32
26.82
37.34
49.45
57.89
1.42
3.32
6.84
12.48
19.50
25.03
38.17
51.11
58.19
58,720
80,032
101,520
117,712
143,136
163,296
184,656
203,488
222,048
Plot as increasing the number of IoT services
(a) Data items = 10,000
63,312
83,280
113,200
132,912
154,016
167,440
191,344
211,936
223,328
402
Figure 3
W. Nam, R. Cha and H. Kil
Plot as increasing the number of IoT services (continued)
(b) Data items = 50,000
(c) Data items = 100,000
On the other hand, the second set of experiments illustrated in Table 2 shows whether
execution time and memory usage depend on the number of data items. With the fixed
number of IoT services (i.e., 1,000, 5,000, and 10,000, respectively), we have measured
the execution time and memory usage of our tool as increasing the number of data items
from 10,000 to 100,000. In the case of 1,000 IoT services, our tool has solved the
problem including 10,000 data items in 0.39 sec and consumed 37,824 KB memory.
Also, it has solved the problem instance including 20,000 IoT services in 0.40 sec with
38,000 KB memory. Finally, it has identified the optimal solution in 0.41 sec with 40,784
KB memory for the problem instance including 100,000 data items. In the case of 5,000
(10,000) IoT services, our tool has solved problems in around 10 (60) seconds and
Optimal algorithm for IoT service composition based on response time
403
consumed about 100,000 (200,000) KB memory, respectively. The experiment results
with 1,000, 5,000, and 10,000 IoT services are also represented in Figure 4 (a) to (c),
respectively. The plots show that the execution time and memory usage rarely depend on
the number of IoT services. This result is based on the fact that the dominant part of the
main loop of our algorithm depends on not the number of data items but the number of
IoT services.
Table 2
Data
items
Experiment results as increasing the number of data items
IoT services = 1,000
IoT services = 5,000
IoT services = 10,000
Time (sec)
Mem (KB)
Time
Mem
Time
Mem
10,000
0.39
37,824
10.61
109,376
58.31
201,568
20,000
0.40
38,000
10.44
111,632
59.20
207,696
30,000
0.37
40,256
10.11
119,664
60.19
221,824
40,000
0.47
40,688
10.54
117,840
60.21
220,864
50,000
0.44
41,088
10.60
120,592
59.96
224,208
60,000
0.42
41,296
11.09
122,848
59.49
226,512
70,000
0.42
41,296
12.38
126,192
62.05
223,472
80,000
0.40
40,640
11.99
125,648
61.68
228,672
90,000
0.38
39,488
12.62
133,872
65.08
232,432
100,000
0.41
40,784
11.41
124,032
64.85
235,024
Figure 4
Plots as increasing the number of data items
(a) IoT services = 1,000
404
W. Nam, R. Cha and H. Kil
Figure 4
Plots as increasing the number of data items (continued)
(b) IoT services = 5,000
(c) IoT services = 10,000
6
Conclusion
In this paper, we have proposed an IoT service composition based on response time.
Given a set of IoT services and a user request, our algorithm automatically composes an
IoT service out of the service set, which satisfies the given user request and has the
minimal aggregate response time. Moreover, our preliminary experiment has shown
promising results.
Optimal algorithm for IoT service composition based on response time
405
There are several issues that are interesting for future study. First, while we have
proposed an optimal algorithm to deal with response time, there are various criteria for
Quality of Services (QoS). Consequently, we want to study efficient way to handle
various QoS criteria. Second, it is worth comparing our automatic optimal algorithm
from several heuristic solutions (Li et al., 2012; Lia et al., 2014) for QoS-aware
web service composition problem. Finally, we plan to research into different problem
settings on IoT service composition, e.g., IoT service composition based on behavioral
description and uncertain QoS-based composition.
Acknowledgements
This paper was supported by Konkuk University in 2016.
References
Arapakis, I., Bai, X. and Cambazoglu, B.B. (2014) ‘Impact of response latency on user behavior in
web search’, 37th International ACM SIGIR Conference on Research and Development in
Information Retrieval, pp.103–112.
Atzori, L., Iera, A. and Morabito, G. (2010) ‘The internet of things: a survey’, Computer Networks,
Vol. 54, No. 15, pp.2787–2805.
Bandyopadhyay, D. and Sen, J. (2011) ‘Internet of things: applications and challenges
in technology and standardization’, Wireless Personal Communications, Vol. 58, No. 1,
pp.49–69.
Cubo, J., Brogi, A. and Pimentel, E. (2012) ‘Behaviour-aware compositions of things’, IEEE
International Conference on Green Computing and Communications, pp.1–8.
De Deugd, S., Carroll, R., Kelly, K., Millett, B. and Ricker, J. (2006) ‘SODA: service oriented
device architecture’, IEEE Pervasive Computing, Vol. 5, No. 3, pp.94–96.
De Souza, L., Spiess, P., Guinard, D., Khler, M., Karnouskos, S. and Savio, D. (2008) ‘Socrades: a
web service based shop floor integration infrastructure’, International Conference on the
Internet of Things, pp.50–67.
Gubbi, J., Buyya, R., Marusic, S. and Palaniswami, M. (2013) ‘Internet of things (IoT): a vision,
architectural elements, and future directions’, Future Generation Computer Systems, Vol. 29,
No. 7, pp.1645–1660.
Guinard, D., Ion, I. and Mayer, S. (2011) ‘In search of an internet of things service architecture:
REST or WS-*? A developers’ perspective’, International Conference on Mobile and
Ubiquitous Systems: Computing, Networking and Services, pp.326–337.
Guinard, D., Trifa, V., Karnouskos, S., Spiess, P. and Savio, D. (2010) ‘Interacting with the SOAbased internet of things: discovery, query, selection, and on-demand provisioning of web
services’, IEEE Transactions on Services Computing, Vol. 3, No. 3, pp.223–235.
Guinard, D., Trifa, V., Spiess, P., Dober, B. and Karnouskos, S. (2009) ‘Discovery and on-demand
provisioning of real-world web services’, IEEE International Conference on Web Services,
pp.583–590.
IMC-AESOP Project (2006) Available online at: http://www.imc-aesop.eu/
Jammes, F. and Smit, H. (2005) ‘Service-oriented paradigms in industrial automation’, IEEE
Transactions on Industrial Informatics, Vol. 1, pp.62–70.
Kil, H., Cha, R. and Nam, W. (2016) ‘Transaction history-based web service composition for
uncertain QoS’, International Journal of Web and Grid Services, Vol. 12, No. 1, pp.42–62.
406
W. Nam, R. Cha and H. Kil
Kona, S., Bansal, A., Blake, M.B., Bleul, S. and Weise, T. (2009) ‘WSC-2009: a quality of serviceoriented web services challenge’, IEEE Conference on Commerce and Enterprise Computing,
pp.487–490.
Li, L., Jin, Z., Li, G., Zheng, L. and Wei, Q. (2012) ‘Modeling and analyzing the reliability and
cost of service composition in the IoT: a probabilistic approach’, 2012 IEEE 19th
International Conference on Web Services, pp.584–591.
Li, L., Li, S. and Zhao, S. (2014) ‘QoS-aware scheduling of services-oriented internet of things’,
IEEE Transaction on Industrial Informatics, Vol. 10, No. 2, pp.1497–1505.
Lia, Q., Doua, R., Chena, F. and Nana, G. (2014) ‘A QoS-oriented web service composition
approach based on multi-population genetic algorithm for internet of things’, International
Journal of Computational Intelligence Systems, Vol. 7, No. 2, pp.26–34.
Mayer, S., Guinard, D. and Wilde, E. (Eds) (2012) Third International Workshop on the Web of
Things.
Microsoft Corporation (2006) Devices profile for web services. Available online at:
http://specs.xmlsoap.org/ws/2006/02/devprof/devicesprofile.pdf
Miorandi, D., Sicari, S., Pellegrini, F.D. and Chlamtac, I. (2012) ‘Internet of things: vision,
applications and research challenges’, Ad Hoc Networks, Vol. 10, No. 7, pp.1497–1516.
Nah, F.F. (2004) ‘A study on tolerable waiting time: how long are web users willing to wait?’
Behavior and Information Technology, Vol. 23, No. 3, pp.153–163.
Web services agreement specification (WS-Agreement) (2007) Available online at:
http://www.ogf.org/ documents/ GFD.107.pdf
Pautasso, C., Zimmermann, O. and Leymann, F. (2008) ‘RESTful web services vs. “big” web
services: making the right architectural decision’, Proceedings of the 17th International
Conference on World Wide Web, pp.805–814.
Russell, S. and Norvig, P. (2003) Artificial Intelligence: A Modern Approach, 2nd ed., PrenticeHall.
Sommer, S., Scholz, A., Buckl, C., Knoll, A., Kemper, A., Heuer, J. and Schmitt, A. (2009)
‘Towards the internet of things: integration of web services and field level devices’,
International Workshop on the Future Internet of Things and Services - Embedded Web
Services for Pervasive Devices (at FITS 2009).
Spiess, P., Karnouskos, S., Guinard, D., Savio, D., Baecker, O., de Souza, L.M.S. and Trifa, V.
(2009) ‘SOA-based integration of the internet of things in enterprise services’, IEEE
International Conference on Web Services, pp.968–975.
Web services policy (WS-Policy) (2006) Web services policy version 1.2. Available online at:
http://www.w3.org/Submission/WS-Policy.
Web services for devices (2006) Available online at: http://ws4d.e-technik.uni-rostock.de/
WSLA (Web Service Level Agreements) project (2004) Available online at: http://www.
research.ibm.com/wsla/documents.html
Xu, L.D. (2011) ‘Enterprise systems: state-of-the-art and future trends’, IEEE Transactions on
Industrial Informatics, Vol. 7, No. 4, pp.630–640.
Документ
Категория
Без категории
Просмотров
4
Размер файла
717 Кб
Теги
080135, ijwgs, 2016
1/--страниц
Пожаловаться на содержимое документа