Cluster Comput DOI 10.1007/s10586-015-0469-1
Hybrid service matchmaking in ambient assisted living environments based on context-aware service modeling Aitor Urbieta1 · Alejandra González-Beltrán2 · Sonia Ben Mokhtar3 · Jorge Parra1 · Licia Capra5 · M. Anwar Hossain4 · Abdulhameed Alelaiwi4 · Juan Ignacio Vázquez6
Received: 15 September 2014 / Revised: 26 June 2015 / Accepted: 4 July 2015 © Springer Science+Business Media New York 2015
Abstract Ambient assisted living (AAL) environments are augmented with sensing and communication technologies to support elderly people with personalized, adaptive and anticipatory requirements. A plethora of heterogeneous devices and services appear and disappear, which expose different behavior with the changing contexts in these environments. Therefore, a service matchmaking mechanism that attempts to identify relevant services in order to fulfill the user needs, has to deal with the heterogeneity of devices and services along with their dynamic behavior. Existing service specifications, such as semantic web services, are often used to abstract the environment’s functionalities and the user tasks without incorporating context-aware properties, which makes them unsuitable for service matchmaking in pervasive and ambient environment. To deal with these issues, we introduce a contExt Aware web Service dEscription Language
B
Aitor Urbieta
[email protected] Alejandra González-Beltrán
[email protected] Sonia Ben Mokhtar
[email protected]
(wEASEL) that is an abstract service model to represent services and user tasks in AAL environments. Also, we present a set of wEASEL-based service matching algorithms and evaluate them for their suitability. The proposed service matchmaking mechanism can incorporate services that are available in local AAL environment as well as in the cloud computing marketplace. Keywords Ambient assisted living · Pervasive computing · Service matchmaking · Semantic web services · Knowledge modeling · Context-awareness
1 Introduction Ambient and pervasive computing environments [39], for example AAL environments [41], are populated by heterogeneous network connected devices and sensors to support elderly people with their daily needs and activities. The devices facilitate user interaction and access to resources and data anywhere and anytime. However, in order to achieve a seamless integration of applications and data, techniques sup-
Jorge Parra
[email protected]
2
Licia Capra
[email protected]
Oxford e-Research Centre, University of Oxford, 7 Keble Road, Oxford OX1 3QG, UK
3
M. Anwar Hossain
[email protected]
DRIM Research Group, LIRIS, INSA de Lyon, 20 Avenue Albert Einstein, 69621 Villeurbanne, France
4
Software Engineering Department, College of Computer and Information Sciences, King Saud University, Riyadh 11543, Saudi Arabia
Juan Ignacio Vázquez
[email protected]
5
Department of Computer Science, University College London, Gower Street, London WC1E 6BT, UK
IK4-IKERLAN, Paseo J.M. Arizmendiarrieta, 20500 Arrasate, Gipuzkoa, Spain
6
Intelligent Environments - DeustoTech, University of Deusto, Av. de las Universidades, 24, 48007 Bilbao, Bizkaia, Spain
Abdulhameed Alelaiwi
[email protected]
1
123
Cluster Comput
porting the automation of service discovery and matching, dynamic service composition and execution must be provided. The seamless integration of distributed and heterogeneous devices and services in AAL environment require an open deployment and execution model. Web Service (WS) [11] is such a model that is designed to support interoperable communication among different platforms and operating systems. However, WS operate at a purely syntactic level, without considering any kind of machine-understandable semantics. Therefore, dynamic service discovery and composition become difficult tasks and human intervention is often required. On the other hand, Semantic WSs (SWSs) [36] aim at minimizing end-users’ intervention, automating WSs matchmaking (which is one of the important steps of service compositions) and discovery. SWSs also provide better integration and interoperability support wherever possible. SWSs combine WSs with the Semantic Web [8] by describing or annotating the services with machine-processable information using concepts represented on ontologies, which are artifacts that provide a conceptualization of a domain.The ontology-based annotations describe the activities performed by the services, making possible the automation of discovery and other high-level tasks in a dynamic fashion [36]. As with the pervasive computing environment, an AAL environment has the requirement to adapt to a dynamic context [10]. They must be aware of the changes in the environment including the location and state of users and devices. Based on the dynamic surrounding context, different services can be provided to the elderly people in AAL, for example, context-aware entertainment services for the elderly people [20], context-aware reminding system [13], and healthcare media services [22,23]. The services offered to the elderly people must be modeled taking into account the contextual information, describing the different effects produced by the correct execution of the services. The effects produced by the services would be different depending on what post-conditions are fulfilled at a particular moment. Using a context model, the post-conditions can be obtained from the user and the environment [49]. However, current approaches for service modeling and matching have a number of limitations:
1. While signature and conversation matching models have been thoroughly investigated in the literature (e.g., OWLS1 , WSMO2 ), existing behavioural specification models
mostly rely on generic rule languages (e.g., SWRL3 , RuleML4 ) and do not allow for the definition of expressive context-aware pre-conditions, post-conditions and effects as required by pervasive systems. 2. Service matching algorithms mostly focus on service signature matching, while specification matching is implemented using costly rule inference engines. In this paper, we introduce wEASEL and wEASELbased framework including a set of matching algorithms that deal with the limitations enumerated above. wEASEL is an abstract service model meeting the requirements of pervasive software systems, like the one that is required in AAL. It can be translated to existing service description languages and thus, it allows to deal with the increasing number of emergent service description proposals. wEASEL supports the definition of services in terms of their semantic signature, context-aware behavioral specification and conversation. As part of our framework, we developed a set of signatureand context-aware specification-based matching algorithms to match a required service description against a set of provided services available in the local environment or deployed in the cloud environment. In this paper, we proposed a framework that deals with the definition and matching of context-aware services, producing the following contributions: – a classification framework within which to read and interpret the related work – the novel wEASEL language for context-aware semantic services description in AAL environments, in terms of their semantic signature, conversation and expressive context-aware behavioural specification with pre- and post-conditions and effects – a wEASEL-based service matching framework that deals simultaneously with signature and specification matching and supports several concept matching techniques – a thorough evaluation of the proposed service matching algorithms, considering both the performance and the quality of the results. The remainder of this paper is structured as follows. Section 2 presents the key requirements for service modeling in AAL environments through a motivating scenario. Section 3 categorises related research efforts for models and matching algorithms. Then, we introduce our abstract service model (Sect. 4) and its related matching algorithms (Sects. 5,6), which allow to deal with the scenario of Sect. 2. Section 7
1
Semantic Markup for Web Services (OWL-S): http://www.w3.org/ Submission/OWL-S/
2
Web Service Modeling Ontology (WSMO): http://www.w3.org/ Submission/WSMO/
123
3
Semantic Web Rule Language (SWRL): http://www.w3.org/ Submission/SWRL/
4
Rule Markup Language (RuleML): http://ruleml.org/
Cluster Comput
evaluates the matching algorithms. Finally, our concluding remarks and future work appear in Sect. 8.
2 Scenario We consider the following scenario motivating the key requirements for modeling the environment’s services and associated matching algorithms. Carla is an elderly person who lives in an Ambient Assisted Living residence. The residence is equipped with the latest technologies, such as the wEASEL system that is able to integrate heterogeneous devices and services (cloud-based as well as local ones) in order to facilitate the entertainment of the elderly people living there. For this purpose the residents carry a wEASEL-Compatible device, which is a tiny smart phone that helps them everyday with different requests. Today, Carla arrives early to the residence from a holiday trip. When she enters the living room, she observes that nobody is there. Hence, she decides to continue watching the film she was watching on the bus to the residence, while waiting for the dinner to be served. The wEASEL-Compatible device discovers and browses the content of available video and multimedia services (that are in the vicinity or in the cloud), and to select the most appropriate display devices in Carla’s reach (e.g., the one having the largest display or the one that is closed to her location). Furthermore, the device adapts the surrounding environment to Carla’s preferences (e.g., room lighting, film sound level, room temperature). Hence, it starts displaying the film selected by Carla on the large LED display of the living room while email and phone notifications are redirected to the display in a smooth way. Half an hour later, wEASEL-Compatible device informs Carla that dinner is ready and is already at her room. Therefore, she decides to go there. After she has entered the room she is asked by wEASEL-Compatible device whether she would like to continue watching the film on the personal LED panel of her room. Later, while she is watching the film again, she receives a phone call from her relatives. Thus, the wEASEL-Compatible device pauses the film so she can talk (through the multimedia system of her room) with her relatives and it continues after she has finished the call.
bilities. In OWL-S, a service description is composed of three parts: the Service Profile, the Process Model and the Service Grounding. The Service Profile gives a high-level description of a service and its provider, and it is generally used for service publication and discovery. The Process Model describes the service conversation as a process, while the Service Grounding specifies the information necessary for service invocation. The Web Service Modeling Ontology (WSMO) [40] consists of four elements: Ontologies, Goals, Web Services and Mediators. Ontologies are defined using the Web Service Modeling Language (WSML) and specify the semantics underlying service descriptions. Goals describe the objectives of a service requester, fulfilled through the execution of Web Services. A Web Service is a computational entity able to achieve users Goals, and described with provided capability, interface and non-functional properties. Finally, Mediators are used to resolve mismatches between the other three elements (i.e., Ontologies, Goals and Web Services). The Semantic Web Services Framework (SWSF)5 [2] is composed of two parts: a language for ontology specification (Semantic Web Services Language, SWSL) and the Semantic Web Service Ontology (SWSO) to describe services. There are two versions of SWSO: the First-Order Logic Ontology for Web Services (FLOWS) and the Rules Ontology for Web Services (ROWS). Similarly to OWL-S, FLOWS and ROWS are composed of three ontologies: the Service Descriptors, the Process Model and the Grounding ontology. The Semantic Annotation for WSDL and XML Schema (SAWSDL)6 [33] is a W3C published technical recommendation that defines how to add semantic annotations to various parts of a WSDL document and its associated XML schema files. These annotations are defined by means of three attributes: the modelReference used to link WSDL elements (e.g., operation names, input, output messages) or XML Schema elements representing data types, with concepts in existing ontologies while the liftingSchemaMapping and loweringSchemaMapping attributes specify mappings between semantic data and XML structures. Discussion. Considering the above descriptions and the semantic service ontologies overview presented in [49], we extract the following conclusions:
3 Related work
– While each approach uses different terminology for naming IOPEs, all of them have the same foundation. – None of them specify how to describe the Pre-conditions and Effects (PEs), leaving to the developer the choice of
Next, we discuss the merits and shortcomings of current approaches for service specification languages and matchmaking mechanisms, motivating our model and algorithms. 3.1 Semantic service description languages The Semantic Markup for Web Services (OWL-S) [35] is an ontology defined using OWL to describe Web Services capa-
5
Semantic Web Services Framework (SWSF): http://www.w3.org/ Submission/SWSF/
6
Semantic Annotation for WSDL and XML Schema (SAWSDL): http://www.w3.org/2002/ws/sawsdl/
123
Cluster Comput
representing the relation between services and the environment (context information). – The approaches only mention the possible languages to represent this relation, being SWRL, WSML and SWSL the most cited ones. However, these approaches do not define the types of contextual changes, as defined in [48], that can occur in AAL environments. Hence, they do not offer mechanisms to develop context-aware semantic services. There are several approaches that deal with the contextual representation in services, such as Fujii and Suda [15], Guinard et al. [16], Hasswa and Hassanein [19], and Hossain et al. [21], however these approaches offer simple servicecontext description models [15] or does not use ontological representations [16] (using other methods to augment service descriptions at matching phase). On the contrary, there are other approaches that tried to tackle the previous drawbacks by defining ontologies to represent contextual changes and their relationships with services. The Effect Ontology by Young-hee et al. [17,18,42] represents service effects only, described using three factors: the contextual information affected by the effect (e.g. , Brightness), the contextual value (e.g. , High) and the affected target (e.g. , Eye). The second approach is the Situation-Awareness Ontology by Yau it et al. [53,54], which proposes to use an ontological model for post-condition (referring to effects) and pre-condition representation, using the Situation-Awareness (SAW) paradigm as a basis. The approach combines OWL-S with SAW into a new ontology representing pre-conditions and post-conditions. Even if these approaches intended to advance the services contextual definition, they neither distinguish different types of contextual changes nor offer enough expressivity to represent them [48]. Thus, an ontological model, offering a higher-level of abstraction and expressivity, is needed for the representation of the basic set of primitives to represent services effects and pre-conditions and their integration with contextual information. This ontology must facilitate the development of matchmaking and composition algorithms that will enable us to provide better services for the elderly people in AAL. Thereby, in Sect. 4 we introduce wEASEL that tackles the described drawbacks. 3.2 Matching semantic service capabilities Paolucci et al. [37,46] propose a base algorithm for service signature matching (subsumption relationship identification between the concepts describing Inputs and Outputs (IOs) of capabilities [55]) that matches a required capability, described as a set of provided inputs and required outputs, with a number of provided capabilities, each described as a set of required inputs and provided outputs. IOs are semantically annotated with ontology concepts using the all-
123
values-from annotation type, indicating that all the IOs are members of the class described by the concept. Other solutions extending the previous signature matching of SWS have been proposed in the literature: [14,30,34,47]. However, all these algorithms neither consider the matching of service’s non-functional properties (such as contextual information or quality of service information), nor the computational cost associated with their matching functions. On the contrary, there are other approaches such as Efficient semAntic Service discoverY (EASY) [6] and Pervasive Semantic Syntactic (PerSeSyn) [7], both proposed by Ben Mokhtar et al., that try to improve the matching efficiency by using numerical codifications to represent the ontological concepts. Besides, Klusch et al. [25] propose to use non-logic and hybrid techniques to improve not only the performance but also the quality of the results. Another kind of service matching, called specification matching has also been investigated in the literature: [9, 43,45,56]. This matching type deals with pre- and postconditions that describe the functional semantics of services. For instance, in Zaremsky et al. [56], specification matching is performed using theorem proving, i.e., inferring general subsumption relations between logical expressions that specify pre- and post-conditions of services. A more practical way to perform specification matching is to use query containment [43,45]. This is done by modeling both service advertisements and service requests as queries with a set of constraints (e.g., required IOs are modelled as restrictions on their types). The approach called Preconditions and Effects Exact Matching (PCEM) [9] proposes to use PEs based on the Planning Domain Definition Language (PDDL) with a Prolog-based reasoner for specification matching. Other approaches combine both signature and specification matching. The DIANE Service Descriptions-MatchMaker (DSD-MM) [32] uses graph-based matching where the PEs are described by means of states with related variables. Kumar et al. [31] propose to use the Munkres polynomial time assignment algorithm to match boolean expressions of unary and binary predicates. Bellur et al. [3,4] improve Kumar et al. approach by using a three-phase matching process (parameter compatibility, condition equivalence and condition evaluation). The system proposed by Stollberg et al. [44], based on Keller et al. [24] work, defines PEs using First-Order-Logic (FOL) expressions combined with the theorem prover Vampire. Bener et al. [5] use SWRL to describe the PE using a WordNet-based matchmaking. Wang et al. [52] use satisfiability checking of DL reasoners to match PEs. None of the described specification matching algorithms nor the combined approaches are for AAL environments. Moreover, they do not offer mechanisms to describe contextual changes. However, Rasch et al. [38], Young-hee et al.
Cluster Comput
[17,18,42] and Yau et al. [53,54] present AAL-oriented solutions. Rasch et al. propose an specification-based matching (using an attribute-value type context representation style) approach that can continuously present the most relevant services to the user in response to context changes, using numeric coding methods to improve the algorithms’ performance. Young-hee et al. use subsumes relations to calculate the distance between services, but there is no detail about the evaluation nor the implementation of the mechanism. Yau et al. combine Paolucci et al. approach for signature matching and Zaremsky et al. approach for specification matching. In these three approaches the evaluation is based on services developed by them, rather than on existing test collections. Discussion. Considering the above classification and the thorough semantic service matching overview presented by Klush et al. in [26], we conclude that existing service matchmaking algorithms do not support dynamic reasoning on user task and service behaviors to face the heterogeneity of AAL domains: – Most matchmaking approaches are signature-based, and there are few specification-based approaches or the combination of both. – The approaches either are not targeted for AAL environments (not representing contextual changes) or allow for simple contextual types of changes and do not offer a complete validation. – Some approaches combine both logic and non-logic techniques to create hybrid ones, which offer better results [25]. Thus, the quest is still open to develop a contex-aware semantic service matchmaker that supports both signatureand specification-based services. Besides, the matchmaker must take into account the dynamic nature of AAL environments offering flexible mechanisms (not only logic-based ones but also non-logic or hybrid ones [25]). This flexibility will deal with the trade-off between performance and quality of results, taking into account resource-constraint services. In Sects. 5 and 6 we describe our matchmaking mechanism, dealing with the aforementioned issues.
4 Abstract service model In this section, we present wEASEL, extending the approach proposed in [50,51] adding service conversation support as well as extending the service specification model. wEASEL is a markup language for services that supports context descriptions. wEASEL is the basis for our abstract model for user tasks and the environment’s pervasive services. We
describe wEASEL elements independently of any representation language and implement it using OWL (we have developed a set of 10 OWL ontologies that can be found at http://tinyurl.com/wEASELsite). The UML diagram of Fig. 1 shows the main elements of the abstract model. Both a UserTask and a PervasiveService are modelled as a Service, which is a unit of functionality. A service has a name and is associated with a non-empty set of capabilities (of type Capability), which are set of functionalities provided by a service (or required for a user task). In turn, capabilities have a name and can be visible or non-visible by setting the visibility field to true or false, respectively. A visible capability represents a capability that can be invoked directly and that provides a meaningful functionality to the end user. Instead, non-visible capabilities are those that are invoked as part of other (composite) capabilities and cannot be invoked out of that specific context. The functionality offered/requested by a capability is described with three optional elements: a Signature, an Specification and a Conversation. Each signature involves a set of inputs and outputs, each of which have a name, a type and can be associated with a SemanticElement that is a reference to an element in an existing domain ontology. The capability’s specification supports the description of associated context-aware PreConditions (describing what must happen, or be true, before the capability can be executed), PostConditions (describing under what specific conditions, the effects that will be generated after the execution of a capability) and Effects. Pre-conditions, post-condition and effects are represented as ContextExpressions. These, in turn, can be SimpleExpressions or CompositeExpressions. A simple expression can be: (1) an EntityExpression used to express the appearance or disappearance of entities in/from the environment; (2) a RelationalExpression used for expressing the appearance or disappearance of a relation between two entities in/from the environment and (3) DataExpression used for expressing numeric conditions. Data expressions have NumericOperators, and the ones supported by wEASEL are: <, >, ≤, ≥, = and =. A composite expression is a set of context expressions combined with logic operators. The ones supported in wEASEL are conjunction, disjunction and negation. A capability in wEASEL can be either simple or composite, and the latter is associated with a Conversation, whose aim is to determine the order in which the capabilities are executed. A conversation is an aggregation of other (simple or composite) capabilities expressed as an Automaton element, representing a finite state automaton (FSA). In addition to the standard definition of a FSA that includes sets of states, symbols, finalStates, an initialState and a transitionFunction, wEASEL supports the specification of DataFlowConstraints and ContextFlowConstraints. Data-flow constraints express the data dependency between two capabilities where an out-
123
Cluster Comput
Fig. 1 wEASEL service model
Fig. 2 An ontology of resources of the scenario
put produced by a capability is used as one of the inputs consumed by another capability. Similarly, context-flow constraints express the context expression dependency between two capabilities where one of the effects produced by the execution of a capability validates one of the pre-conditions or post-conditions necessary to execute another capability. To exemplify the model elements, we show the services from the Scenario (Sect. 2) and their semantic annotations using a domain ontology about resources (see Fig. 2). In the ontology, a Resource can be a Digital Resource, a Display Resource or a Computing Resource. In turn, a LED Display is a Display Resource and thus, it is also a Resource.
123
Figure 3 shows the devices and associated set of services available in the residence’s waiting room (including Carla’s room) and their visible capabilities of the Scenario described in Sect. 2. The Video Server service offers capabilities to search (Search Video Resource) and get video resources (Get Video Resource). As an example of annotations, the output of the Get Video Resource capability is semantically annotated with the concept Video Resource. The capability Display MM Resource offered by the LED Display service has a pre-condition expressed as a composite context expression. Specifically, it is a conjunction between a composite data expression, an entity expression and a simple data expression. The composite data
Cluster Comput
Fig. 4 Pervasive services’ conversations
Fig. 3 Devices and associated pervasive services of the scenario
expression (i.e., T ime < 9am ∨ T ime > 9 pm) indicates that the screen is available to mobile users only before 9am and after 9pm, while in between it is under the control of the residence administration (e.g., for displaying the residence announcements, advertisements). The entity expression < E xists, Room > specifies that the display has to be (physically) present in a context environment where there is a room. Finally, the data expression N br Per sons < 5 indicates that there must be less than five persons in the room for the capability to be executed, above which the screen would display news to avoid overwhelming people with other people’s content. A relational expression is used to describe the effect generated by the Display MM Resource capability of the LED Display service: < E xists, Displays Fr om Ser ver, V ideoSer ver L E D >. This effect describes the appearance of a new relation between the video server and the LED display in the environment when the display shows a stream coming from the server. Figure 4 shows the composite capabilities offered by the services of Fig. 3. The service Smart Environment Controller is composed of two capabilities: Display MM Resource capability of the LED Display service and Light Controller capability of the Smart Environment Controller service. The Display MM Resource capability is non-visible for Smart Environment Controller, which indicates that this capability cannot be invoked alone for that service. In contrast, this capability can only be invoked alone with the LED Display service and it is the pre-condition for the Light Controller capability. The services Carla Music Server and Video Server have a data constraint between two of their simple capabilities. Specifically, (part of) the output generated by the Search
Audio Resource and Search Video Resource capabilities is used as an input of Get Audio Resource and Get Video Resource, respectively. Furthermore, and as it has been mentioned previously, the Smart Environment Controller service offers a composite capability that combines the Display MM Resource capability of the LED Display service and the Light Controller capability of the Smart Environment Controller service itself. Those two capabilities have a context-flow constraint between them: the effect generated by the Display MM Resource capability, which describes the appearance of a relationship between the Video Server and the LED Display in the environment, triggers the pre-condition required for changing the light level of the room (not as for the Light Controller capability of the Lamp service, which it does not require any pre-condition to invoke it).
5 Matching: preliminary definitions First, we present the definitions required for the comprehension of the matchmaking mechanism. We describe the basic unit of service matching, i.e., the matching of a pair of concepts. For each of the three proposed matching techniques we describe how the distance between a pair of concepts (the required concept Req and the provided concept Pr ov) is calculated. Req is the concept specified within the user required service, and Pr ov exists in the specification of one of the registered pervasive services. There are several levels of concept matching [28] (following the next level order E xact < Plugin < Subsumes < Logical Fail < N ear est − N eighbour < Fail), namely: – E xact: The concept Pr ov matches the concept Req exactly ⇐⇒ Pr ov ≡ Req, i.e., the concepts are equivalent.
123
Cluster Comput
– Plugin: The concept Pr ov plugs into the concept Req ⇐⇒ Req subsumes Pr ov. In symbols, Pr ov Req. The plugin match is also called subsumed by match. – Subsumes match: The concept Pr ov subsumes the concept Req ⇐⇒ Req Pr ov. – Logical Fail: If concept Req does not match concept Pr ov in any of the situations above, then it is considered that the logical-based matching has failed and both concepts are incompatible. – N ear est-N eighbour : The concept Pr ov has a nearestneighbour relation with the concept Req if and only if their text similarity (using an Information Retrieval (IR) distance) is greater than a threshold α. In symbols, S I M I R (Req, Pr ov) ≥ α. – Fail: A concept Pr ov does not match with requested concept Req according to any of the above described levels. 5.1 Logic distance To compute the logic distance between two concepts, we use a technique based on concept similarity. We reinforce the definition by Ben Mokhtar et al. [7], which in turn is based on the relationships proposed by Paolucci et al. [37,46]. Ben Mokhtar et al. [7] define the distance between two ontological concepts Req and Pr ov, as the number of separation levels between them in the hierarchy defined by the classified ontology. Here, we extend Ben Mokhtar et al. [7] definitions to consider the role the concepts play in the service annotation. In other words, the logic distance function (d L ) is different for inputs and conditions (pre-conditions and post-conditions) and for outputs and effects, as follows: d L (Req, Pr ov) = 0 d L (Req, Pr ov) > 0 d L (Req, Pr ov) = N ull d L (Req, Pr ov) > 0 d L (Req, Pr ov) = N ull d L (Req, Pr ov) = N ull (a) (b) (c) (d) (e) (f)
(a) (b) (c) (d) (e) (f)
E xact, for any role the concept is playing Subsumed By and concepts are inputs or conditions Subsumed By and concepts are outputs or effects Subsumes and concepts are outputs or effects Subsumes and concepts are inputs or conditions Fail
For inputs and conditions: d L (Computing Rsc, Computing Rsc) = 0
d L (Rsc, AudioRsc) = N ull (b) d L (V ideoRsc, Digital Rsc) = 2
7
The word Resour ce has been shortened to Rsc in order to save space
123
(c)
d L (Digital Rsc, Display Rsc) = N ull (d) For outputs or effects: d L (Computing Rsc, Computing Rsc) = 0
(a)
d L (Rsc, AudioRsc) = 3
(b)
d L (V ideoRsc, Digital Rsc) = N ull (c) d L (Digital Rsc, Display Rsc) = N ull (d) (a) (b) (c) (d)
E xact Subsumes Subsumed By Fail
In order to eliminate false positives in the logic distance, which occurs when the matching is positive for concepts that are far away in the hierarchy defined by the ontology, we defined a logic threshold (T h L ) representing the maximum number of levels for which the logic distance is valid. Thus, for T h L = 7, d L (Req, Pr ov) ≤ 7 and false positives are eliminated. However, false negatives (related with the Nearest-Neighbour level of concept matching) cannot be eliminated due to inherent subsumption type of reasoning used by logic techniques. We note that the threshold value has been used by Klusch et al. in [28] only for non-logic distances and we have also included it for logic-based distances. 5.2 Non-logic distance The non-logic method uses IR techniques to compute the distance between two concepts. Thus, it is computed in a purely syntactic way. In particular, four similarity metrics are used: cosine, extended Jacquard, loss of information and Jensen Shannon, as used for OWLS-MX [28]. Let Sim N L be one of these similarity metrics, then the non-logic distance d N L is defined as:
d N L (Req, Pr ov) =
⎧ ⎨
0
1 ⎩ Sim N L (Req,Pr ov)
N ull
Some examples of the logic-based distance for concepts from the ontology of resources (Fig. 2) are7 :
(a)
(a) Sim N L (Req, Pr ov) = 1 (b) Sim N L (Req, Pr ov) ≥ (T h N L )−1 (c) Sim N L (Req, Pr ov) < (T h N L )−1
(a) (b) (c)
(1)
Cluster Comput
where the non-logic Threshold value (T h N L ) is defined to establish the maximum valid non-logic distance, helping to reduce the false positives. Klusch et al. in [28] provide a similar definition but only used it for the hybrid matching method. The numeric value for T h N L is defined such that (T h N L )−1 = 0.815. This method also gives false positives because it matches the concepts in an absolute way, i.e., it does not make any distinction between Subsumes or SubsumedBy levels. Also there is other type of false positives due to the fact that the system ignores the logical operands of the concept definitions (such as and and or connectives) in the preprocessing of concept unfolding.
able depending on the power of the mobile device where the service matching mechanism is applied.
5.3 Hybrid distance
The degree of matching between two Inputs is computed as follows (where the distance d method can be any of the techniques described in Sect. 5 applied to the corresponding role of the concepts — this notation applies in the rest of the paper for any equation including distance d):
The hybrid matching distance method (d H ) combines logicand non-logic base methods [28]. Combining each of the four non-logic techniques with the logic one, we obtain four hybrid variants. Firstly, the logic-based method is applied. If the logic distance is equal to zero or it is bigger than zero and the non-logic distance is not equal to N ull, the hybrid method returns the logic distance. Otherwise, if the logic distance is N ull but the non-logic one is not N ull, the nonlogic distance is applied. Finally, if both distances are N ull the hybrid method returns N ull. ⎧ ⎪ ⎪ ⎨
0 d L (Req, Pr ov) d H (Req, Pr ov) = (Req, Pr ov) × TThhNLL d ⎪ N L ⎪ ⎩ N ull (a) (b) (c) (d)
(a) (b) (c) (d)
6.1 Signature matching of service capabilities Each service is characterised by its signature, i.e. the set of Inputs and Outputs, in turn associated with SemanticElements. In order to calculate the matching degree of the service signature, it is necessary to explain how the matching degree of Inputs and Outputs is calculated. 6.1.1 Inputs matching
I nput DoM(in 1 , in 2 ) =
1 1+d(in 1 ,in 2 )
0
(a) (b)
(3)
(a) E xact ∨ Subsumed By (b) other wise 6.1.2 Outputs matching
(2)
d L (Req, Pr ov) = 0 d L (Req, Pr ov) > 0 ∧ d N L (Req, Pr ov) = N ull d L (Req, Pr ov) = N ull ∧ d N L (Req, Pr ov) = N ull d L (Req, Pr ov) = N ull ∧ d N L (Req, Pr ov) = N ull
Thus, the hybrid method combines the advantages of logic and non-logic ones, eliminating the false negatives that can be retrieved by the logic-distance (as it does not support Nearest-Neighbour relation), and eliminating false positives from non-logic and logic thanks to the Threshold parameter.
6 Context-aware service matching This section describes the different levels of the matching process: first detailing the signature-based matching mechanism (Sect. 6.1), secondly describing the specification-based mechanism (Sect. 6.2) and finally presenting the mechanism to combine both matchmaking techniques (Sect. 6.3). These different matching levels vary on computational cost and the quality of the results. Thus, they will be more or less suit-
The matching degree between two Outputs is computed as follows: Out put DoM(out1 , out2 ) =
1 1+d(out1 ,out2 )
0
(a) (b)
(4)
(a) E xact ∨ Subsumes (b) other wise 6.1.3 Signature matching Consider the services S1 and S2 (with one capability per service) having the signatures Sig1 =< I n 1 , Out1 > and Sig2 = < I n 2 , Out2 > respectively, where I n i , Outi are the set of inputs and outputs of Si . The signature matching between S1 and S2 holds when all the inputs required by S1 are matched with inputs provided by S2 and all the outputs required by S2 are matched with outputs provided by S1 . In that case S1 is said to match S2 as it consumes at most the inputs that S2 consumes and produces at least the outputs that S2 produces. This can be determined by the expression SigMatch(Sig1 , Sig2 ): ∀in 1 ∈ I n 1 , ∃in 2 ∈ I n 2 : d(in 1 , in 2 ) = N ull∧ ∀out2 ∈ Out2 , ∃out1 ∈ Out1 : d(out1 , out2 ) = N ull
(5)
123
Cluster Comput
The maximum degree of match of each provided input M AX in (in 2 ) is obtained with: max(I nput DoM(in 1 , in 2 )) : in 1 ∈ I n 1
(6)
Cont E x pMatch(Pr e1 , Pr e2 ) = N ull ∧ Cont E x pMatch(Post1 , Post2 ) = N ull ∧ Cont E x pMatch(E f f 1 , E f f 2 ) = N ull
(9)
Finally, the degree of signature matching SigDoM(Sig1 , Sig2 ) is obtained from:
ContExpMatch(Cont E x p1 , Cont E x p2 ) is a function able to match contextual expressions (defined in Sect. 6.2.4). This function is used to match two context expressions that can be either simple or composite (see Sect. 6.2.4). Matching simple context expressions depends on their type: for an entity expression see Sect. 6.2.1, for a relational expression see Sect. 6.2.2 and for a data expression see Sect. 6.2.3. Thus, the equation that calculates de degree of matching between a couple of specification expressions is SpeDoM(Spe1 , Spe2 ):
j=J i=I M AX in (in i ) M AX out (out j ) + 2I 2J
1/3 (Cont E x p DoM(Pr e1 , Pr e2 )+ Cont E x p DoM(Post1 , Post2 )+ Cont E x p DoM(E f f 1 , E f f 2 ))
And the maximum degree of match of each required output M AX out (out1 ) is obtained with: max(Out put DoM(out1 , out2 )) : out2 ∈ Out2
i=1
(7)
(8)
j=1
where I represents the number of provided Inputs (I n 2 ), J represents the number of required Outputs (Out1 ), ∀in i ∈ I n 2 M AX in (in i ) > 0 and ∀out j ∈ Out1 M AX out (out j ) > 0. Thus, considering the next two signature-based capabilities: – Capab1 : Sig1 =< in 1 =< Resour ceN ame >, out1 =< M M Resour ce >> that represents the Get MM Resource capability required by Carla in the Scenario described in Sect. 2. – Capab2 : Sig2 =< in 2 =< Resour ceN ame >, out2 =< V ideoResour ce >> that represents the Get Video Resource capability from the Video Server pervasive service in Fig. 3. We determine that as both capabilities input concepts are the same (d(in 1 , in 2 ) = 0) then the I nput DoM(in 1 , in 2 ) = 1 1+0 = 1; and as the distance between output concepts is one (d(out2 , out2 ) = 1) then the Out put DoM(out1 , out2 ) = 1 1 1+1 = 2 . Thus, we conclude that Sig DoM(Sig1 , Sig2 ) = 1/2 1 3 2×1 + 2×1 = 4 . 6.2 Specification matching of service capabilities Specification matching refers to matching service pre-conditions, post-conditions and effects. Consider Spe1 =< Pr e1 , Post1 , E f f 1 > and Spe2 =< Pr e2 , Post2 , E f f 2 > as two services specifications associated with the services S1 and S2 , respectively. Similarly to signature matching, specification matching between S1 and S2 holds when the pre-conditions and post-conditions of S1 are satisfied by the pre-conditions and post-conditions of S2 , and when the effects of S2 are satisfied by the effects of S1 as described in the expression SpeMatch(Spe1 , Spe2 ):
123
(10)
where the Cont E x p DoM(Pr e1 , Pr e2 ) × Cont E x p DoM (Post1 , Post2 ) × Cont E x p DoM( E f f 1 , E f f 2 ) > 0 condition must be satisfied and the expression ContExpDoM (Cont E x p1 , Cont E x p2 ) is a function that calculates the degree of match between a couple of contextual expression definitions (see Sect. 6.2.4). In order to describe how the specification-based matching is achieved in detail, first we will describe how the three types of simple contextual expressions are matched (Sect. 6.2.1, 6.2.2, 6.2.3) and then how the composite contextual expressions (Sect. 6.2.4) are matched. 6.2.1 Matching entity expressions Consider two entity expressions E E 1 = < E xist1 , Ent1 > and E E 2 = < E xist2 , Ent2 >, where E xisti is a boolean representing the appearance or the disappearance from the environment of the entity Enti , respectively (Ent elements are represented by a SemanticElement). The matching between E E 1 and E E 2 is defined with the equation EExpMatch(E E 1 , E E 2 ) as: (E xist1 = E xist2 ) ∧ (d(Ent1 , Ent2 ) = N ull)
(11)
where the degree of matching between two entity expressions is determined by: ⎧ 1 (a) ⎪ ⎪ ⎨ 1 (b) d(Ent1 ,Ent2 )+1 E E x p DoM(E E 1 , E E 2 ) = (12) 1 ⎪ (c) ⎪ ⎩ 2×(d(Ent1 ,Ent2 )+1) 0 (d) (a) (b) (c) (d)
E xact Subsumed By ∧ E xist) ∨ (Subsumes ∧ E xist Subsumed By ∧ E xist) ∨ (Subsumes ∧ E xist) Fail
Cluster Comput
where E xist represents that both elements E xist1 and E xist2 are tr ue, and E xist represents that both are f alse. Thus, if we consider the next two effects (defined in the Scenario of Sect. 2 and the pervasive service in Fig. 3) that are represented by the following entity expressions: E E 1 = < E xists, Resour ce > and E E 2 = < E xists, LC D Display >. We conclude that as both existence values are equal, the type of relation is Subsumes and the logic distance between both concepts is two, the distance of match between the expressions is: E E x p DoM(E E 1 , 1 = 16 . E E 2 ) = 2×(2+1) 6.2.2 Matching relational expressions Consider two relational expressions R E 1 =< E xist1 , Sr c Ent1 , Relation 1 , T rg Ent1 > and R E 2 =< E xist2 , Sr c Ent2 , Relation 2 , T rg Ent2 >, where E xisti is a boolean representing the appearance or the disappearance from the environment of the relation Relation i between a pairs of semantic elements < Sr cEnti , T rg Enti > (source and target entities). Relation elements are represented by a SemanticElement. Thus, the matching RExpMatch(R E 1 , R E 2 ) between R E 1 and R E 2 is defined as follows: (E xist1 = E xist2 )∧ (d(Relation 1 , Relation 2 ) = N ull)∧ (d(Sr cEnt1 , Sr cEnt2 ) = N ull)∧ (d(T rg Ent1 , T rg Ent2 ) = N ull)
(13)
where the degree of matching between two relational expressions, RExpDoM(R E 1 , R E 2 ), is given by: 1/3 (E E x p DoM(Sr cEnt1 , Sr cEnt2 )+ E E x p DoM(T rg Ent1 , T rg Ent2 )+ E E x p DoM(Relation 1 , Relation 2 ))
(14)
and the E E x p DoM(Sr cEnt1 , Sr cEnt2 )×E E x p DoM(T rg Ent1 , T rg Ent2 )× E E x p DoM( Relation 1 , Relation 2 ) > 0 expression has to be fulfilled. Thus, if we consider the next two pre-conditions (defined in the Scenario of Sect. 2 and the pervasive service in Fig. 3) that are represented by the following relational expressions: R E 1 =< E xists, L E D Display, ConnectedT o, Smar t phone > and =< E xists, Display Resour ce, expression R E 2 ConnectedT o, Smar t phone >. We conclude that as both existence values are equal, the logic distance between the source entities is one (with Subsumed By relation), the logic distance between the target entities is zero (with E xact relation) and the two relation entities are equal (distance is one), the distance of match between the expressions is: 1 + 1 + 1) = 56 . R E x p DoM(R E 1 , R E 2 ) = 13 ( 1+1
6.2.3 Matching data expressions Consider two data expressions described as D E 1 =< O pr nd1, O pr t1 , V al1 > and D E 2 =< O pr nd2, O pr t2 , V al2 > (O pr nd represents the operand, O pr t the operator and V al the value), where an O pr nd element is represented by means of a SemanticElement. The matching between D E 1 and D E 2 , DExpMatch(D E 1 , D E 2 ), is defined as follows (where btwn represents between): d(O pr nd1, O pr nd2) = N ull∧ ∃ inter val o f common values btwn D E 1 ∧ D E 2
(15)
where the matching degree DExpDoM(D E 1 , D E 2 ) between two data expressions is given by: 1/2 (O perand DoM(O pr nd1, O pr nd2)+ O perator DoM(O pr t1 , V al1 , O pr t2 , V al2 ))
(16)
and the O perand DoM(O pr nd1, O pr nd2)× O perator DoM( O pr t1 , V al1 , O pr t2 , V al2 > 0 expression must be satisfied. Besides, the equation OperandDoM(O pr nd1, O pr nd2) is represented as follows: ⎧ ⎪ ⎪ ⎪ ⎨
1
1 d(O pr nd1,O pr nd2)+1 1 ⎪ ⎪ ⎪ 2×(d(O pr nd1,O pr nd2)+1)
⎩
0
E xact Subsumed By Subsumes Fail
(17)
and the matching degree value between a pair of < O pr t, V al > expressions (OperatorDoM(O pr t1 , V al1 , O pr t2 , V al2 )) has to take into account the type of operators that are being compared as it is described in Table 1. The table (where rows represent the values for O pr t1 and columns for O pr t2 ) describes which is the type of matching supported for each operator combination. The role of the compared elements also has to be taken into account, because depending on whether it is a condition or an effect the supported relations are different (see Table 1). Therefore, the OperatorDoM(O pr t1 , V al1 , O pr t2 , V al2 ) equation, that calculates the degree of match between a couple of < O pr t, V al > expressions is defined as follows: ⎧ ⎨
1
O p1 ∩O p2 ⎩ O p1 ∪O p2
0
E xact Subsumes ∨ Subsumed By other wise
(18)
where expression O p = {op | op f ollows (O pr t, V al)∧ V al ∈ ∧ V almin ≤ V al ≤ V almax } has to be fulfilled. Besides, V almin and V almax represent the range of supported values for V al. Thus, if we consider the next two post-conditions (defined in the Scenario of Sect. 2 and the
123
Cluster Comput Table 1 Relation types matching according to O pr t1 and O pr t2 values (a) Part I equalTo
lessThan
lessThanEqualTo
equalTo
E xact a ∨ Fail bc
Subsumed By b ∨ Fail ac
Subsumed By ab ∨ Fail c
lessThan
Subsumes c ∨ Fail ab
Subsumed By b ∨ Subsumes c ∨ E xact a
Subsumed By ab ∨ Subsumes c
lessThanEqualTo
Subsumes ac ∨ Fail b
Subsumed By b ∨ Subsumes ac
Subsumed By b ∨ Subsumes c ∨ E xact a
greaterThan
Subsumes b ∨ Fail ac
Fail abc
Fail abc
greaterThanEqualTo
Subsumes ab ∨ Fail c
Fail abc
Fail abc
notEqualTo
Subsumes bc ∨ Fail a
Subsumes ac ∨ Fail b
Subsumes c ∨ Fail ab
(a) Part II greaterThan
greaterThanEqualTo
notEqualTo
equalTo
Subsumed By c ∨ Fail ab
Subsumed By ac ∨ Fail b
Subsumed By bc ∨ Fail a
lessThan
Fail abc
Fail abc
Subsumed By ab ∨ Fail c
lessThanEqualTo
Fail abc
Fail abc
Subsumed By b ∨ Fail ac
greaterThan
Subsumed By c ∨ Subsumes b ∨ E xact a
Subsumed By c ∨ Subsumes ab
Subsumed By ac ∨ Fail b
greaterThanEqualTo
Subsumed By c ∨ Subsumes ab
Subsumed By c ∨ Subsumes b ∨ E xact a
Subsumed By c ∨ Fail ab
notEqualTo
Subsumes ab ∨ Fail c
Subsumes b ∨ Fail ac
E xact a ∨ Fail bc
a b c
V al1 = V al2 V al1 < V al2 V al1 > V al2
pervasive service in Fig. 3) represented by the following data expressions: D E 1 =< Light Level, gr eater T han, 145lx > and D E 2 =< Ligth Level, gr eater T han, 165lx >. We conclude that as both operands are equal, both operators are equal and V almax = 200, then the distance of match between the expressions is D E x p DoM(R E 1 , 1 7 9 R E 2 ) = 21 (1 + 200−165 200−145 ) = 2 (1 + 11 ) = 11 . 6.2.4 Matching composite expressions Composite expressions are logic expressions including conjunctions and/or disjunctions between context expressions (i.e., entity, relational or data expressions). In order to match composite expressions we first normalize them into the standard Disjunctive Normal Form (DNF), i.e., a disjunction of conjunctive clauses. Consider two composite expressions C E 1 = ex p1 ∨ . . . ∨ ex p K and C E 2 = ex p1 ∨ . . . ∨ ex p L where ex pk,k=1...K , and ex pl,l=1...L , are conjunctive clauses (i.e., composite context expressions with conjunctions only). Therefore, a matching between C E 1 and C E 2 , represented as CompExpMatch(C E 1 , C E 2 ) holds if the next expression is achieved: ∃ex pk ∈ {ex p1 , . . . , ex p K }∧ ∃ex pl ∈ {ex p1 , . . . , ex p L } : Con j E x pMatch(ex pk , ex pl )
(19)
where ConjExpMatch(ex p1 , ex p2 ) is a function used to match conjunctive context expressions as follows: consider two conjunctive context expressions: ex p1 = e1 ∧
123
. . . ∧ e M and ex p2 = e1 ∧ . . . ∧ eN , where em,m=1..M , , are simple context expressions (i.e., entity and en,n=1..N expressions, relational expressions and data expressions). A matching holds between ex p1 and ex p2 in the expression ConjExpMatch(ex p1 , ex p2 ) if: (∀em ∈ ex p1 , ∃en ∈ ex p2 : S E x pMatch(em , en ))∧ (20) (∀en ∈ ex p2 , ∃em ∈ ex p1 : S E x pMatch(em , en )) This means that all the simple expressions of ex p2 need to be matched with at least one context expression in ex p1 and all the simple expressions of ex p1 need to match at least one simple expression of ex p2 , where SExpMatch(em , en ) represents the equation to calculate if there exists a match between two simple expressions, based on their tipology (see Sects. 6.2.1, 6.2.2, 6.2.3). Therefore, the degree of match between a pair of conjunctive expressions is calculated in two steps, first calculating the maximum degree of match of em respecting to each element of ex p2 , represented by the M AX 1 (em ) expression: max(S E x p DoM(em , en )) : en ∈ {e1 , . . . , eN }
(21)
and viceversa (calculating the maximum degree of match of en respecting to each element of ex p1 ), which is represented by the expression M AX 2 (en ): max(S E x p DoM(em , en )) : em ∈ {e1 , . . . , e M }
(22)
Cluster Comput
and second, calculating the average degree of match ConjExpDoM(ex p1 , ex p2 ) of the previous formulas for each element of ex p1 and ex p2 : m=M m=1
M AX 1 (em ) + 2M
n=N n=1
M AX 2 (en ) 2N
(23)
where ∀em ∈ ex p1 M AX 1 (em ) > 0 and ∀en ∈ ex p2 M AX 2 (en ) > 0. SExpDoM(em , en ) represents the degree of match of any of the simple expression types described previously. Thus, the degree of match CompExpDoM(C E 1 , C E 2 ) between a pair of composite expressions is represented as the maximum degree of match of the conjuctive context expressions calculated before: max(Con j E x p DoM(ex pk , ex pl ))
(24)
where the expression ex pk ∈ {ex p1 , . . . , ex p K }, ex pl ∈ {ex p1 , . . . , ex p L } and at least there is a conjunctive expression with Con j E x p DoM(ex pk , ex pl ) > 0. Finally, as the function CompExpMatch(C E 1 , C E 2 ) can be used for simple as well as composite expressions. As it is determined that ContExpMatch(Cont E x p1 , Cont E x p2 ) = CompExpMatch(Cont E x p1 , Cont E x p2 ), thus we can infer that ContExpDoM(Cont E x p1 , Cont E x p2 ) = CompExpDoM(Cont E x p1 , Cont E x p2 ). Thus, considering the next two specification-based capabilities: – Capab1 : Spe1 = < Post1 =< Ligth Level, gr eater T han, 165lx >, E f f 1 =< Decr ease, Light Level >> that represents the Light Controller capability required by Carla in the Scenario described in Sect. 2. – Capab2 : Spe2 = < Post2 =< Ligth Level, gr eater T han, 145lx >, E f f 2 =< Decr ease, Light Level >> that represents the Ligt Controller capability from the Lamp pervasive service in Fig. 3. Referring to the Eq. 10, we can determine that as there are not pre-conditions, then Cont E x p DoM (Pr e1 , Pr e2 ) = 9 (extracted from the 1, Cont E x p DoM(Post1 , Post2 ) = 11 example described in Sect. 6.2.3) and as both effects are equal Cont E x p DoM (E f f 1 , E f f 2 ) = 1. Thus, we conclude that 1 31 SpeDoM (Spe1 , Spe2 ) = 13 + 9/11 3 + 3 = 33 .
where SigDoM(Sig1 , Sig2 ) (described in Sect. 6.1) and SpeDoM(Spe1 , Spe2 ) (described in Sect. 6.2) are computed using the selected distance functions, dReq, Prov, according to whether the two entities are matched in a logic (Sect. 5.1), non-logic (Sect. 5.2) or hybrid (Sect. 5.3) way. In order to consider a valid degree o match, the expression Sig DoM(Sig1 , Sig2 ) × SpeDoM(Spe1 , Spe2 ) > 0 has to be satisfied.
7 Assessment In order to evaluate the service matchmaker , the first step was to generate the set of simple-capability wEASEL services for the test collection. To do that, we considered the OWL-S service retrieval test collection version 4 (OWLSTC48 ). OWLS-TC4 is a test collection built to support the evaluation of OWL-S service matchmaking mechanisms. The OWLS-TC4 services are written in OWL-S 1.1 and are divided into nine different domains: communication, economy, education, food, geography, medical, simulation, travel and weapon. The collection is composed of 1.083 services and 42 queries. The queries are associated with relevance sets to allow for performance and correction evaluation experiments. To evaluate the service matchmaking engine, we used a Intel Pentium 4 PC with Windows XP with a Core 2 Duo processor of 2.4GHz and 4GB of RAM memory. 7.1 Simulation setup: generation of simple wEASEL services Using as a starting point the OWL-S services from the previously mentioned OWLS-TC4 test collection, we converted them to wEASEL services in an automatic way (both services and queries)9 . The automation is achieved by defining a mapping between OWL-S 1.1 services and wEASEL services. Additionally, we added pre-conditions and effects to the wEASEL services and queries generated as part of the automatic transformation, by creating a CompositeExpression (representing a PreCondition) that is constructed by the conjunction of all the inputs (representing SimpleExpressions) of each service and another CompositeExpression (that represents a PostCondition) that represents the conjunction of all outputs (represented by SimpleExpresssions) of each service.
6.3 Matching of Service Capabilities 7.2 Metrics CapabilityDoM(Capab1 , Capab2 ) is the function that returns In order to evaluate the AAL-related heterogeneity and the degree of match between two service capabilities Capab1 dynamism characteristics, we evaluated two aspects of the and Capab2 as follows: Sig DoM(Sig1 , Sig2 ) + SpeDoM(Spe1 , Spe2 ) 2
(25)
8
http://projects.semwebcentral.org/projects/owls-tc/
9
Available at http://tinyurl.com/wEASEL-site
123
Cluster Comput
service matchmaking mechanism: its performance and correctness. The performance metric is related to evaluating the capacity of the matchmaker to respond to the appearance of new services in the environment and thus to calculate if those services are compatible with the required ones, while the correctness metric is related to evaluating the capacity of the matchmaker to deal with heterogeneously described services. For our evaluation, we used the Service Matchmaker Evaluation Environment (SME2)10 system developed by Klusch et al. using also the same simulation scenario domains (dataset) as well as the same evaluation process like ours (for more detail of the whole evaluation process see [26]). This SME2 system allows the integration of wEASEL matchmaker mechanism as a plugin of SME2 and evaluate it using standard metrics for information retrieval (IR) performance evaluation. More concretely, we used the precision/recall11 metrics over each of the distance techniques (logic, four non-logic and four hybrid) described in Sect. 5, for each matching type (defined in Sect. 6): signature matching (input/output matching or IO), specification matching (precondition/effect matching or PE) and the combination of both (IOPE). For matchmaking and composition of Semantic Web Services, precision may be more important to the user than recall, since the set of relevant services is subject to continuous change in practice [25], specially in AAL environments where mobility is very high. In order to give full IOPE support for all the queries and services in the test collection and to evaluate the precision/recall of the matchmaker, we extended the graded relevance set of OWLS-TC4 (adapting and converting it to support wEASEL-based service descriptions). The graded relevance set is given as an XML file built using the SWS Relevance Assessment Tool (SWSRAT) and uses a 4-graded scale: highly relevant, relevant, potentially relevant and nonrelevant [29]. In this way, thanks to the transformed services and to the extended graded relevance set, we obtained the necessary input for the SME2. 7.3 Results We evaluated the precision/recall degree of each distance metric (logic, four non-logic and four hybrid) for each matching type (IO, PE and IOPE) over the transformed and extended wEASEL services created from OWLS-TC4. In order to do that, we matched each query against all the services belonging to the same domain of the query. The eval10
http://projects.semwebcentral.org/projects/sme2/
Fig. 5 Precision/recall evaluation
uation was done using the macro-averaged12 precision/recall technique described in [27], obtaining the following results (see Fig. 5): – The Hybrid techniques are the ones that offer a better average precision/recall degree than the rest of the distance metrics (logic and non-logic). This is because they provide higher precision values for different recall levels
11
In IR, precision is defined the proportion of retrieved material that is actually relevant. On the other hand, the recall of the system is the proportion of relevant material actually retrieved in answer to a search request [12].
123
12
Precision macro-averaging refers to the mean precision values for answer sets retrieved by the matchmaker for all queries in the test collection at specific recall values.
Cluster Comput
service component in the cloud server as well as put a service registry there so that the services can be published from both local and cloud-based AAL environment. Publishing the matchmaking service in the cloud means that it would be possible to leverage cloud capability for allocating dynamic computing resources (elastic) when needed, supporting the variability of service appearance and disappearances. The cloud-based deployment will also help us access the services ubiquitously in a more accessible fashion.
8 Conclusion Fig. 6 Average time (ms) to match a set of services for each HybridCosine variant
and due to the benefits obtained from the combination of both logic and non-logic techniques. – Among the set of Hybrid techniques, the Hybrid-Cosine technique stands out as it produces the best results in the three matching types. Thus, we confirmed the claim by Klusch et al. in [25,26,28] that the Hybrid-Cosine technique offers better correction degree than the rest. In the case of the wEASEL matchmaker, this is satisfied for all the matching types. After concluding that the best distance technique was the one based on Hybrid-Cosine, the next step was to determine which of the matching types offered the best precision/recall degree. We compared the average precision of each of the Hybrid-Cosine variants: for IO it is 0.663, for PE it is 0.348 and for IOPE it is 0.731; and we also compared the average time to match sets of services for each of the Hybrid-Cosine variants (see Fig. 6). Therefore, we concluded that the IOPEbased Hybrid-Cosine variant is the best technique, because it offers the highest balance between precision/recall degree and performance (it is able to match 300 IOPE services in less than 1 s). 7.4 Perspectives of service matchmaking on cloud environment Going beyond the traditional service setup, the proposed service matchmaking mechanism can also benefit from the capability cloud computing offers in terms of storage, processing and scalability [1]. When considering a largescale AAL setup, there will be a plethora of different types of services and different situations (different contexts such as: residence, home, etc.) to be handled. This demand for a robust service matchmaking mechanism, which should allow efficient service selection and enable the combination of local and cloud-based services to fulfill high level user requirements. So in a real setup, we can deploy the matchmaking
In the midst of heterogeneous devices and services available in AAL environment, the ability to discover and match the functionalities offered by software and hardware resources in the vicinity of mobile users is still an unresolved challenge. To achieve this, this paper proposed a novel service matchmaking mechanism along with a wEASEL language for context-aware semantic services description in AAL environments. The service descriptions are based on their semantic signature, conversation and expressive context-aware behavioural specification with pre- and post-conditions and effects. We also conducted a thorough evaluation of the proposed service matchmaking algorithms by considering both the performance and the quality of the result. In light of the results and analysis, we propose the following as part of future work: – to extend the evaluation of the system by using different semantic reasoners, as the algorithms depend heavily on the efficiency of the reasoners, – to develop a wEASEL-based service composition mechanism in the cloud environment based on the model and matchmaking framework described in this paper. Acknowledgments The authors extend their appreciation to the Deanship of Scientific Research at King Saud University for funding this work through the research group Project No. RGP-VPP-049.
References 1. Armbrust, M., Fox, A., Griffith, R., Joseph, A.D., Katz, R., Konwinski, A., Lee, G., Patterson, D., Rabkin, A., Stoica, I., et al.: A view of cloud computing. Commun. ACM 53(4), 50–58 (2010) 2. Battle, S., Bernstein, A., Boley, H., Grosof, B., Gruninger, M., Hull, R., Kifer, M., Martin, D., McIlraith, S., McGuinness, D.: Semantic web services framework (swsf). Tech. Rep. W3C Member Submission - 9 (2005) 3. Bellur, U., Kulkarni, R.: Improved matchmaking algorithm for semantic web services based on bipartite graph matching. In: IEEE International Conference on Web Services (ICWS), pp. 86–93. (2007)
123
Cluster Comput 4. Bellur, U., Vadodaria, H.: On extending semantic matchmaking to include preconditions and effects. In: IEEE International Conference on Web Services (ICWS), pp. 120–128. (2008) 5. Bener, A.B., Ozadali, V., Ilhan, E.S.: Semantic matchmaker withprecondition and effect matching using swrl. Expert Syst. Appl. 36(5), 9371–9377 (2009). doi:10.1016/j.eswa.2009.01.010 6. Ben Mokhtar, S., Preuveneers, D., Georgantas, N., Issarny, V., Berbers, Y.: Easy: efficient semantic service discovery in pervasive computing environments with qos and context support. J. Syst. Softw. 81(5), 785–808 (2008) 7. Ben Mokhtar, S., Raverdy, P.G., Urbieta, A., Cardoso, R.: Interoperable semantic and syntactic service discovery for ambient computing environments. Innovative Applications of Ambient Intelligence: Advances in Smart Systems (2012) 8. Berners-Lee, T., Hendler, J.: The semantic web. Sci. Am. 284(5), 28–37 (2001) 9. Botelho, L., Fernandez, A., Fries, B., Klusch, M., Pereira, L., Santos, T., Pais, P., Vasirani, M.: Service Discovery, Chap. 10. CASCOM—Intelligent Service Coordination in the SemanticWeb. Springer, New York (2008) 10. Bottaro, A., Bourcier, J., Escoffier, C., Lalanda, P.: Autonomic context-aware service composition. In: 2nd IEEE International Conference on Pervasive Services (ICPS’07). Istanbul, Turkey (2007) 11. Champion, M., Ferris, C., Newcomer, E., Orchard, D.: Web services architecture. W3C Tehnical Report (2002) 12. Cleverdon, C., Mills, J., Keen, M.: Aslib Cranfield research projectFactors determining the performance of indexing systems; Volume 2, Test results. Cranfield (1966) 13. Du, K., Zhang, D., Zhou, X., Hariz, M.: Handling conflicts of context-aware reminding system in sensorised home. Cluster Computing 14(1), 81–89 (2011). doi:10.1007/s10586-009-0091-1 14. Filho, J.G.P., van Sinderen, M.: Web service architectures— semantics and context-awareness issues in web services platforms. Tech. rep, Telematica Instituut (2003) 15. Fujii, K., Suda, T.: Semantics-based context-aware dynamic service composition. ACM Trans. Auton. Adapt. Syst. 4(2), 12 (2009) 16. Guinard, D., Trifa, V., Karnouskos, S., Spiess, P., Savio, D.: Interacting with the soa-based internet of things: Discovery, query, selection, and on-demand provisioning of web services. IEEE Trans. Serv. Comput. 3(3), 223–235 (2010) 17. Gwang-hun, K., Do-hyun, K., XuanTung, H., Younghee, L.: Group-aware service discovery using effect ontology for conflict resolution in ubiquitous environment. In: 10th International Conference on Advanced Communication Technology (ICACT) (2008) 18. Gwang-hun, K., Do-hyun, K., XuanTung, H., Younghee, L., Gabsoo, L.: Semantic service discovery using effect ontology for appliance service in ubiquitous environment. In: International Conference on Ubiquitous Information Technologies and Applications (ICUT) (2008) 19. Hasswa, A., Hassanein, H.: A smart spaces architecture based on heterogeneous contexts, particularly social contexts. Clust. Comput. 15(4), 373–390 (2012). doi:10.1007/s10586-011-0157-8 20. Hossain, M.A., Alamri, A., Almogren, A.S., Hossain, S., Parra, J.: A framework for a context-aware elderly entertainment support system. Sensors 14(6), 10538–10561 (2014) 21. Hossain, M.A., Parra, J., Atrey, P.K., El Saddik, A.: A framework for human-centered provisioning of ambient media services. Multimed. Tools Appl. 44(3), 407–431 (2009) 22. Hossain, M.S.: Adaptive media service framework for health monitoring. In: Proceedings of the Third International Conference on Internet Multimedia Computing and Service, pp. 70–73. ACM (2011) 23. Hossain, M.S., Muhammad, G.: Cloud-based collaborative media service framework for healthcare. International Journal of Distributed Sensor Networks (2014)
123
24. Keller, U., Lara, R., Lausen, H., Polleres, A., Fensel, D.: Automatic location of services. In: Proceedings of the 2nd European Semantic Web Conference (ESWC 2005), pp. 38–49. Springer (2005) 25. Klusch, M., Fries, B., Sycara, K.: Automated semantic web service discovery with owls-mx. In: AAMAS ’06: Proceedings of the 5th int. joint conf. on Autonomous agents and multiagent systems, pp. 915–922. ACM, New York (2006). doi:10.1145/1160633. 1160796 26. Klusch, M., Fries, B., Sycara, K.: OWLS-MX: a hybrid Semantic Web service matchmaker for OWL-S services. Web Semant. 7(2), 121–133 (2009) 27. Klusch, M., Kapahnke, P.: Owls-mx3: An adaptive hybrid semantic service matchmaker for owl-s. In: Proceedings of 3rd International Workshop on Service Matchmaking and Resource Retrieval in the Semantic Web. CEUR-WS.org (2009) 28. Klusch, M., Kapahnke, P., Fries, B.: Hybrid semantic web service retrieval: A case study with OWLS-MX. In: IEEE Second International Conference on Semantic Computing (ICSC’08) (2008) 29. Klusch, M., Khalid, M., Kapahnke, P., Fries, B., Vasileski, M.: Owls-tc owl-s service retrieval test collection—version 4.0—user manual (2010) 30. Kourtesis, D., Paraskakis, I.: Combining sawsdl, owl-dl and uddi for semantically enhanced web service discovery. In: 5th European Semantic Web Conference (ESWC 2008), vol. 5021, pp. 614–628. Springer (2008) 31. Kumar, A., Neogi, A., Pragallapati, S., Ram, D.J.: Raising programming abstraction from objects to services. In: International Conference on Web Services (ICWS) (2007) 32. Kuster, U., Konig-Ries, B., Stern, M., Klein, M.: Diane: an integrated approach to automated service discovery, matchmaking and composition. In: Proceedings of the 16th International Conference on World Wide Web, pp. 1033–1042 (2007) 33. Lausen, H., Innsbruck, D.: Semantic annotations for WSDL and XML schema (sawsdl) (2006) 34. Majithia, S., Walker, D.W., Gray, W.A.: A framework for automated service composition in service-oriented architecture. In: 1st European Semantic Web Symposium (2004) 35. Martin, D., Burstein, M., Hobbs, J., Lassila, O., McDermott, D., McIlraith, S., Narayanan, S., Paolucci, M., Parsia, B., Payne, T.: Owl-s: Semantic markup for web services. W3C Memb. Submiss. 22 (2004) 36. McIlraith, S.A., Zeng, T.C., Zeng, H.: Semantic web services. IEEE Intell. Syst. Appl. 16(2), 46–53 (2001) 37. Paolucci, M., Kawamura, T., Payne, T.R., Sycara, K.: Semantic matching of Web services capabilities. Lecture Notes in Computer Science 2342, 333–347 (2002). http://link.springer-ny.com/ link/service/series/0558/bibs/2342/23420333.htm; http://link.spr inger-ny.com/link/service/series/0558/papers/2342/23420333.pdf 38. Rasch, K., Li, F., Sehic, S., Ayani, R., Dustdar, S.: Context-driven personalized service discovery in pervasive environments. World Wide Web 14(4), 295–319 (2011). URL http://www.springerlink. com/index/10.1007/s11280-011-0112-x 39. Remagnino, P., Foresti, G.L.: Ambient intelligence: a new multidisciplinary paradigm. IEEE Trans. Syst. Man Cybern. Part A 35(1), 1–6 (2005) 40. Roman, D., Lausen, H., Keller, U.: Web service modeling ontology standard (wsmo-standard) (2004) 41. Ruyter, B.d., Pelgrim, E.: Ambient assisted-living research in carelab. interactions, Interactions 14(4), 30–33 (2007) 42. Saehoon, K., Woohyun, K., Dongman, L., Younghee, L.: Group context-aware service discovery for supporting continuous service availability. In: Proceedings of the First Internaltional Workshop on Personalized Context Modeling and Management for UbiComp Applications (ubiPCMM 2005) (2005)
Cluster Comput 43. Sirin, E., Parsia, B., Hendler, J.: Template-based composition of semantic web services. In: AAAI Fall Symposium on Agents and the Semantic Web (2005) 44. Stollberg, M., Keller, U., Lausen, H., Heymans, S.: Two-phase web service discovery based on rich functional descriptions. In: 4th European Semantic Web Conference, ESWC 2007, vol. 4519, pp. 99–113. Springer (2007) 45. Sycara, K., Lu, J., Klusch, M., Widoff, S.: Matchmaking among heterogeneous agents on the internet. In: Proceedings of the 1999 AAAI Spring Symposium on Intelligent Agents in Cyberspace (1999) 46. Sycara, K., Paolucci, M., Ankolekar, A., Srinivasan, N.: Automated discovery, interaction and composition of semantic web services. Web Semant. 1(1), 27–46 (2003) 47. Trastour, D., Bartolini, C., Gonzalez-Castillo, J.: A semantic web approach to service description for matchmaking of services. In: Proceedings of the International Semantic Web Working Symposium (SWWS) (2001). http://citeseer.ist.psu.edu/ trastour01semantic.html 48. Urbieta, A.: An integrated approach for context-aware modelling, matchmaking and composition of semantic services, based on preconditions and effects, oriented to intelligent environments. Ph.D. Thesis, Mondragon Unibertsitatea (MU) (2010) 49. Urbieta, A., Azketa, E., Gomez, I., Parra, J., Arana, N.: Analysis of effects- and preconditions-based service representation in ubiquitous computing environments. In: IEEE Second International Conference on Semantic Computing (ICSC’08) (2008) 50. Urbieta, A., Azketa, E., Gomez, I., Parra, J., Arana, N.: Bridging the gap between services and context in ubiquitous computing environments using an effects- and conditions-based model. In: 3th International Symposium on Ubiquitous Computing and Ambient Intelligence (UCAm I), Advances in Soft Computing Series. Springer (2008) 51. Urbieta, A., Azketa, E., Gomez, I., Parra, J., Arana, N.: Towards effects-based service description and integration in pervasive environments. In: ACM Service Integration in Pervasive Environments (SIPE’08) Workshop on International Conference on Pervasive Services (ICPS’08) (2008) 52. Wang, H., Li, Z., Fan, L.: Capability matchmaking of semantic web services with preconditions and effects. In: The Third Chinese Semantic Web Symposium (CSWS) (2009) 53. Yau, S.S., Liu, J.: Hierarchical situation modeling and reasoning for pervasive computing. In: SEUS-WCCIA ’06: Proceedings of the The Fourth IEEE Workshop on Software Technologies for Future Embedded and Ubiquitous Systems, and the Second International Workshop on Collaborative Computing, Integration, and Assurance (SEUS- CCIA’06), pp. 5–10 (2006). doi:10.1109/ SEUS-WCCIA.2006.25 54. Yau, S.S., Liu, J.: Incorporating situation awareness in service specifications. In: ISORC ’06: Proceedings of the Ninth IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing, pp. 287–294. (2006). doi:10. 1109/ISORC.2006.39 55. Zaremski, A.M., Wing, J.M.: Signature matching: a tool for using software libraries. ACM Trans. Softw. Eng. Methodol. 4(2), 146– 170 (1995). http://citeseer.ist.psu.edu/zaremski95signature.html 56. Zaremski, A.M., Wing, J.M.: Specification matching of software components. ACM Trans. Softw. Eng. Methodol. 6(4), 333–369 (1997)
Aitor Urbieta is a research fellow at the Software Technologies Department of IK4-IKERLAN since November 2007. Aitor got his Ph.D. degree in Computer Science in 2010 from Mondragon University. Aitor’s current research interests include Semantic Web, Semantic Web Services, Service Discovery and Matchmaking, Service Composition, Ubiquitous Computing, Context-awareness, Semantic Devices, Semantic Sensor Networks, Internet of Things (IoT), Machine to Machine (M2M), IEC61850, Service Oriented Architectures, SOAP Services, RESTful services. He is author or co-author of several papers and articles in the field of Service Oriented Architectures and Internet of Things. During the last five years he has been working on the validation of a safety critical system for railways and on the definition and development of several components for vertical transportation and energy efficient systems. Alejandra González-Beltrán is a Research Lecturer at the University of Oxford e-Research Centre, UK. Her research focuses on developing methodologies and software tools for data science, including knowledge management and data analysis. Before joining the University of Oxford, Alejandra was involved with the Computational and Systems Medicine project and the Department of Computer Science at University College London. Before that, she completed a Ph.D. in Computer Science at Queen’s University Belfast and a Licentiateship in Computer Science at Universidad Nacional de Rosario, Argentina. Sonia Ben Mokhtar is a CNRS researcher at the LIRIS laboratory (Lyon, France) since October 2009. Before working for the CNRS, Sonia got her Ph.D. degree from Université Pierre et Marie Curie, Paris (France) while carrying out her research at the INRIA Rocquencourt research center (France) in the “ARchitectures Logicielles Et Systèmes distributes” (ARLES) research group. She then worked as a research associate at University College London (UK) taking part of the Mobile Systems Special Interest Group for two years. Sonia’s research topics include middleware for distributed and/or mobile systems in general with a special interest in fault-tolerance and privacy issues.
123
Cluster Comput Jorge Parra is a researcher at IK4-IKERLAN since 1999, within the Software Technologies department. His main activity is the design and development of embedded safety-critical systems, focusing on distributed software aspects. In the last 5 years he has been actively involved in the design and development of railway systems such as ERTMS/ETCS (SIL4) and power loading for tramways (SIL2). Holding an M.Sc. in Industrial Engineering from University of Basque Country, he has been a visiting researcher at University of Ottawa (Canada) and INRIA (France). He is a certified TÜV Functional Safety Engineer for the design of hardware and software based on the IEC-61508 standard (Fs/Eng.5280/12) since 2009.
Abdulhameed Alelaiwi is an Assistant Professor of Software Engineering department, at the College of Computer and Information Sciences, King Saud University. Riyadh, Saudi Arabia. He is currently the Vice Dean for Deanship of Scientific Research at King Saud University. He received his Ph.D. degree in Software Engineering from the College of Engineering, Florida Institute of TechnologyMelbourne, USA in 2002. He has authored and co-authored many publications including refereed IEEE/ACM/Springer journals, conference papers, books, and book chapters. His research interest includes software testing analysis and design, cloud computing, and multimedia.
Licia Capra is a Reader in pervasive computing in the Department of Computer Science at University College London. Licia conducts research in the area of computer-supported cooperative work. She has tackled specific topics within this broad research field, including crowdsourcing, coordination, context-awareness, trust management, and personalisation. She has published more than 70 papers on these topics, in top venues including SIGSOFT FSE, IEEE TSE, ACM CSCW, SIGIR, SIGKDD, and RecSys.
Juan Ignacio Vázquez is CEO at EasiBeacon (Easi Technologies), creating proximity-based experiences for retail, tourism and other markets based on iBeacon technology, and providing consulting and development services for Internet of Things projects. He is lecturer on Smart Objects and Mobile App Development at the University of Deusto (Bilbao, Spain) and occasionally also about Business Model Canvas, especially on mixed product+service business models (Internet of Things). Previously, he was Research Leader of the Intelligent Environments Research Group at the University of Deusto (Spain). He has taken part in cross-European FP7 projects related to mobile computing, and he has also managed cooperative projects involving smart context-aware objects, wearable devices, and mobile computing systems.
M. Anwar Hossain is an Associate Professor in the Department of Software Engineering, College of Computer and Information Sciences at King Saud University (KSU), Riyadh, KSA, since 2010. He obtained his master degree in Computer Science from the University of Ottawa, Canada, in 2005 and Ph.D. degree in Electrical and Computer Engineering from the same University in 2010. In the same university, he was a research assistant at the Multimedia Communications Research Laboratory (MCRLab). He completed his bachelor degree in Computer Science and Engineering Discipline from Khulna University, Bangladesh. Dr. Hossain received IBM faculty award in 2011. His current research interests include multimedia surveillance and privacy, ambient intelligence, smart cities and cloud computing. He has authored/co-authored over 85 research articles in reputed conferences and journals. Dr. Hossain has co-organized several IEEE/ACM workshops including IEEE ICME AAMS-PS 2011-13, IEEE ICME AMUSE 2014, ACM MM EMASC-2014, and is involved as TPC in several other conferences. He served as guest editor of Springer Multimedia Tools and Applications journal. He is a member of IEEE and ACM.
123