Noha Ibrahim
email: noha.ibrahim@imag.fr

Stéphane Frénot
email: stephane.frenot@insa-lyon.fr

Frédéric Le Mouël
email: frederic.le-mouel@insa-lyon.fr

User-Excentric Service Composition in Pervasive Environments

Keywords: SOA, social network of services, user-excentric composition, semantic matching

In pervasive environments, services are fastly developing and are being deployed everywhere. In this article, we introduce a Servicebook, a new social network of services, where services create and join group of service profile providing to users better access to all the services in their vicinity. We propose a novel technique to realize this Servicebook, the userexcentric service composition. This user-excentric composition relies on two service relations: the compatible relation and the composition relation. We developed and evaluated an OSGiprototype as a proof-of-concept.

I. INTRODUCTION

The development of service-based computing technologies and communication networks opened the way for new trends, where services are the main actors of their environments. We borrow the human social behavior and define a service social behavior as everything that concerns a service in a society composed of services. A society of service is defined by the service profiles evolving in an organised group. We define the organisation of a society around interface compatibilities. One of this idea challenges is in defining the service profile upon which groups of services are formed and the criteria for services to join groups of their interest. The natural idea is to use the interface description profile. Services with the same profile, come together to form a group. A group is formed by all the services having the same interface profile but different capabilities (implementations, non functional properties, etc).

To create this service society named Servicebook, where services gather according to their interface profiles, we propose a user-excentric composition. The composition is excentric because not requested by users, but yet it provides composed services with new capabilities but already existing interfaces. All the service composition technologies ( [START_REF] Ben | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF], [START_REF] Fujii | Semantics-based dynamic service composition[END_REF], [START_REF] Kalasapur | Dynamic Service Composition in Pervasive Computing[END_REF], [START_REF] Chakraborty | Service Composition for Mobile Environments. Journal on Mobile Networking and Applications[END_REF], [START_REF] Shankar | SWORD: A developer toolkit for web service composition[END_REF]) are user-centric as they await a user request to compose services. The composition we are after consists of (1) composing services of the environment without prior user request to extend the Servicebook with new capabilities and for that [START_REF] Chakraborty | Service Composition for Mobile Environments. Journal on Mobile Networking and Applications[END_REF] this user-excentric composition needs to provide services with new capabilities (implementations, non functional properties, etc) but with the same interface profile as the services already existing in the Servicebook.

Based on the above, the contributions of this article are threefold. First, the article defines a new social network of services, the ServiceBook. Second, it describes using a formal language two kinds of relations between services: the compatible relation and the composition relation. Finally, it explains the user-excentric service composition based on these relations. What is new with our approach is that we are the first one to propose a user-excentric service composition approach in opposition to the user-centric one. We propose a novel application for this user-excentric composition, the Servicebook social network. We also define and formalize service compatible and composition relations which have not been done before.

To better appreciate the approach, we consider a running example, consisting of services and operations providing different capabilities to users. Upon this running example we illustrate our compatible and composition service relations, followed by our user-excentric service composition. The remaining of this paper is organised as follows. Section 2 is a state of the art for the service composition in pervasive environments. Section 3 defines the Servicebook as a social network of services. Section 4 introduces the service model and the semantic matching tools. Section 5 explains the service compatible and composition relations. Section 6 depicts the user-excentric service composition. Section 7 details the developed proof-of-concept prototype and its results. Section 8 concludes this work.

II. STATE OF THE ART

Service composition allows the combination of multiple services into a single composite service, which may be achieved at design-time (static) or at run-time (dynamic). In current middleware and systems, dynamic service composition is very often associated with the realization, on the fly, of user tasks. Indeed, service composition can be a major key for the user-centrism paradigm by enabling the user to be at the heart of the realization of his daily tasks through the combination of relevant services available in the vicinity. The three composition middleware depicted in this section (PERSE [START_REF] Ben | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF], SeGSeC [START_REF] Fujii | Semantics-based dynamic service composition[END_REF], and Broker [START_REF] Chakraborty | Service Composition for Mobile Environments. Journal on Mobile Networking and Applications[END_REF]) are, as all other major current service composition middleware (SeSCo [START_REF] Kalasapur | Dynamic Service Composition in Pervasive Computing[END_REF], WebDG [START_REF] Medjahed | Composing Web services on the Semantic Web[END_REF], eFlow [START_REF] Casati | Adaptive and dynamic service composition in eflow[END_REF], SWORD [START_REF] Shankar | SWORD: A developer toolkit for web service composition[END_REF], and Contract-Based composition [START_REF] Milanovic | Contract-based Web Service Composition[END_REF]), user-centric as they dynamically compose services in response to a user task.

PERSE [START_REF] Ben | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF] introduces the architecture of a semantic service registry for pervasive computing. This registry allows heterogeneous service capabilities to be registered and retrieved by translating their corresponding descriptions to a predefined service model. Service discovery protocol interoperability requires the translation of service advertisements into a common service description language for enabling service matching and composition to be performed independently from the specific underlying languages. Once the translation done, the services can be published, stored, compared or composed depending on what is needed in the environment.

SeGSeC [START_REF] Fujii | Semantics-based dynamic service composition[END_REF] proposes an architecture that obtains the semantics of the requested service in an intuitive form (e.g. using a natural language), and dynamically composes the requested service based on its semantics. To compose a service based on its semantics, the proposed architecture supports semantic representation of services -through a component model named Component Service Model with Semantics (CoSMoS) -discovers services required for composition -through a middleware named Component Runtime Environment (CoRE) -and composes the requested service based on its semantics and the semantics of the discovered services -through a service composition mechanism named Semantic Graph-Based Service Composition (SeGSeC)

Broker [START_REF] Chakraborty | Service Composition for Mobile Environments. Journal on Mobile Networking and Applications[END_REF] presents a distributed architecture and associated protocols for service composition in mobile environments that take into consideration mobility, dynamic changing service topology, and device resources. The composition protocols are based on distributed brokerage mechanisms and utilize a distributed service discovery process over ad-hoc network connectivity. The proposed architecture is based on a composition manager, a device that manages the discovery, integration, and execution of a composite request. Two broker selection-based protocols -dynamic one and distributed one -are proposed in order to distribute the integration requests to the composition managers available in the environment.

These service composition middleware are clearly usercentric as they fulfill the user requests. To our knowledge, User-excentric service composition, that composes services without the user request but still providing new functionalities to the environment, is not considered.

III. SE R V I C E B O O K : A SOCIAL NETWORK OF SERVICES

Social networking has encouraged new ways to communicate and share information. A social network focuses on building online communities of people who share interests and/or activities, or who are interested in exploring the interests and activities of others. In a human social network, people get together because of certain compatibilities they define in advance, and get to create groups of interest where they can exchange. In general, social networks allow users to create a profile for themselves and groups that share common interests.

We define a social network of services, the Servicebook, inspired from the human social networks. Servicebook gets services together by grouping them according to their interfaces. Services publish their profiles which are (i) interface semantic signature, (ii) functional properties describing the service implementation and (iii) non functional properties describing the service context. Services providing the same interface semantic signature (i) come together to form a group of interest. Each service bring its functional properties (ii) and non functional properties (iii) as a specificity to the group. All the services of a same group publish the same interface (i). Groups of services are created where each group publishes a same interface but provides multiple implementations and/or non functional properties(cf. Figure 1). Each group will see it community grows or shrinks depending on what services are available in the environment. The Servicebook provides extended capabilities to the users. A service user searching for a specific interface will seek for the interface specific group and will have a large choice of implementations (ii) and non functional properties (iii) within this group (cf. Figure1).

The Servicebook gains to be web based and can provide a variety of ways for services to interact via standards such as SOAP. Services can also be hosted on ambient devices carried by users and come to meet as users encounter. This creates an ambient social network of services where users can benefit from the new capabilities of their services. In this article, important issues such as security and trust are not considered. In social networks of services these issues are essential as service may condition its participation to a particular group depending on these criteria. Now that we defined what is a Servicebook, how to create a group and how to join it. We define in next sections the user-excentric composition as an efficient tool to update the Servicebook with new services. Indeed, finding services that offer the same interface but different capabilities is not always easy and we argue that the user-excentric composition is an efficient way to do this. We first begin by formalizing the service model and the service relations followed by the user-excentric composition definition.

IV. SERVICE FORMALIZATION

In this section, we define our service model and the semantic matching tools for comparing different concepts belonging to a same ontology.

A. Service Model

A service has functional properties corresponding to the operations it computes and non functional properties describing the operation behaviour. Non functional properties correspond to all the properties that characterize the operation context excluding the operation implementation itself.

Consider finite sets of grammatical alphabet Σ, ontologies O, concepts N belongings to these ontologies O, functional properties P, non functional properties Np, quantitative and qualitative non-functional properties Np QN , Np QL . Consider the following operators:

• * (repetition zero or more times) Where:

• In is the set of the operation op inputs. In = in 1 . . . in |In| . ∀ in ∈ In, in is defined as a tuple: < name, semantic >, where name is the chosen input syntactic name and semantic the input semantic description.

• out is the operation op output. out is defined as a tuple < semantic > where semantic its the semantic description.

• P the functional property of a service describing its implementation. This property also indicates whether the service is atomic or composed. We define non functional properties of an operation op as follow: DEFINITION where: N p is the set of non functional properties characterizing the operation. N p can be qualitative or quantitative.

• np QL ∈ N p QL is the qualitative non functional properties defined as a tuple (name, semantic), where name is the syntactic name through which the property is specified and semantic is its semantic description. • np QN ∈ N p QN is the quantitative non functional properties defined as a tuple, where value ∈ R and operator ∈ {>, <, =}. Operator specifies the value range the service can offer. For '>' the value is the smallest value the service can offer during its runtime execution. For '<' the value is the biggest value the service can offer during its service runtime execution. For '=' the value is the only value the service can offer during its service runtime execution. • The qualitative property access describes the overall operation. It indicates how to connect to the printer device. The concepts belong to the same ontology (cf.

Figure 3).

The functional properties describe the operation implementation and indicates that the three services are atomic.

We define two operations opi and opj to be comparable if they have the same number of inputs and the same number of outputs and if it exists a bijection f over their inputs allowing to compare the inputs parameters two by two:

∃ f : In opi → In opj , ∀ in l ∈ In opj , ∃! in k ∈ In opi , f (in k ) = in l
We define two services to be comparable if they have the same number of operations and if it exists a bijection f over their operations allowing to compare them two by two.

It may also be interesting to compare services together even if they do not have the same number of operations but at least two comparable operations. All the following definitions can be applied to this special case where two or more services are comparable over a sub-set of their operations but not all of their operations.

B. Semantic Matching Tools

The matching of two concepts belonging to the same ontology has been widely studied. We define M Cpt our matching relation between concepts that belong to the same ontology.

A concept n belonging to an ontology o, can provide all its immediate sub-concepts n 1 and n 2 (Paolucci [START_REF] Paolucci | Semantic matching of web services capabilities[END_REF]) or one of its sub-concepts n 1 or n 2 . We fall into the first category, stipulating that a super-concept offers what its sub-concepts offer, and hence can replace them.

Defining n and m, two concepts belonging to the same ontology o. We define the four values of concept matching M Cpt inspired from Paolucci as follows:

M Cpt (n, m) values are:

• Exact If n and m are equivalent concept

• P lugIn If n is a super-concept of m • Subsume If n is a sub-concept of m • F ail
If n and m do not verify the above conditions Following Paolucci matching, we choose not to consider the siblings in our semantic matching and by that we stipulate that two concepts are not compatible even if they have the same parents.

EXAMPLE 2: Using our ontology Figure 3, we give an example of M Cpt matching.

M Cpt ( ′′ W ireless ′′ , ′′ Bluetooth ′′ ) = P lugIn The two values of of Exact and F ail are the best and worst case. For the P lugIn and Subsume values, we consider the P lugIn to be better than the Subsume as a concept can provide all its immediate sub-concepts but not necessary the other way round (Paolucci definition).

( ′′ W ireless ′′ , ′′ W if i ′′ ) = P lugIn ( ′′ W ireless ′′ , ′′ Access ′′ ) = Subsume ( ′′ W ireless ′′ , ′′ W ired ′′ ) = F ail ( ′′ W ireless ′′ , ′′ 802.11a ′′ ) = P lugIn

V. SERVICE RELATION FORMALIZATION

In this section, based on the above tools, we define our service relations. These latter are the cornerstone of our userexcentric service composition.

A. Service Compatible Relation

Based on the concept matching, we define the semantic matching between two comparable operations. The operation op i is:

• Exact semantic matching to op j if all the matching values between their respective comparable inputs and their respective output are Exact. We define operation op i to be semantically compatible ≡ sem with operation op j , if the semantic matching of op i with op j is Exact or P lugIn semantic matching.

DEFINITION 3 -(≡ sem (op i , op j ) = T rue) if M Cpt (op i , op j ) ∈ {Exact ∨ P lugIn}
The compatible relation implies that op i can easily replace op j as it has a semantic compatible signature. Each user of the op j operation can be satisfied with the op i operation. He can not easily distinguish the difference as the semantic matching we adopted assures a complete compatibility.

As we did for the operations, we define the semantic matching between two comparable services S i and S j :

• Services S i is Exact semantic match to S j if all the comparable operations of S i are Exact matching with the respective comparable operations of S j . • Services S i is P lugIn semantic match to S j if all their comparable operations of S i are Exact and P lugIn matching with the respective comparable operations of S j . At least one P lugIn matching must be found. • Services S i is Subsume semantic match to S j if they are not Exact nor P lugIn semantic match and no F ail matching is found between any comparable operations of the two services. • Services S i is F ail semantic match to S j if at least one operation of S i is F ail semantic match to a comparable operation of S j . We define operation S i to be semantically compatible ≡ sem to S j if S i is Exact or P lugIn semantic matching to S j . DEFINITION 4 -(≡ sem (S i , S j ) = T rue) if M Cpt (S i , S j ) ∈ {Exact ∨ P lugIn} As for the operations, the compatible relation implies that S i can easily replace S j as it has a semantic compatible interface. Each user of S j can be satisfied with S i . He can not easily distinguish the difference as the semantic matching we adopted assures a complete compatibility.

S i and S j can also be not semantically compatible but have semantically compatible operations. We can then say that S i is semantically compatible to S j over a subset of their operations. This can be very useful as it is difficult to always find comparable services having all their operations compatible.

We need to specify that we will only consider the functional properties of services for the compatible relation. We defined in [START_REF] Ibrahim | MySIM: a Spontaneous Service Integration Middleware for Pervasive Environments[END_REF] a function that computes the compatibility between service non functional properties. But one of the goals of our user-excentric service composition is to provide different non functional properties as we will see in section V and for that reason, no compatibility over non functional properties is required.

B. Service Composition Relation

After the service compatible relation definitions, we define the service composition relations. A service is considered to be composable with another service, if the functionality it produces can be consumed by the other service, and if the non-functional properties are compatible. Combining two services together means combining their functional interfaces, and by that at least one of their operations. The output produced by the operation of one service is used as an input for the operation of the other service. To be able to compose services, non-functional properties need to be taken into account, indeed if incompatibilities exist no composition can take place.

Two services S i and S j are semantically compatible for composition (O sem ) if they have at least two semantic composable operations. Two operations are semantic composable if the semantic description of the output of one operation is Exact or P lugin matching to the semantic description of one input of the other operation (cf. Figure 4).

But even if two operations are functionally composable, they can present incompatible non-functional properties that prevent from establishing a valid composition relation between the concerned operations. The non-functional properties we are concerned with, are those that describe and specify the output and the input that are combined together. Indeed, the composition relation is built upon the condition that the output of one operation is consumed as an input for the other operation. The non-functional properties dealing with these parameters need to be compatible. The non functional property compatibilities depend on the properties type. For qualitative properties, considering np QL = (name, semantic) a common property for both op i and op j . The semantic of np QL of out opi must be Exact or P lugIn semantic match with the semantic of np QL of in opj . By that way the out opi satisfies the functional and non functional requirement of in opj . If the semantic of np QL of out opi is Subsume semantic match with the semantic of np QL of in opj there is no guarantee that the composition works as the subsume concept is not capable of providing all the required concept of its superconcept.

For the quantitative property, considering np QN = (name, value, operator) a common property for both op i and op j . To be able to compose the two operations, the intersection of their respective values must not be equal to zero, otherwise, no composition can take place.

All these relations are illustrated via our running example in the next section.

VI. USER-EXCENTRIC SERVICE COMPOSITION

We first begin by defining the user-excentric service composition and illustrating this composition via our running example. Then, we return to our Servicebook and show how the user-excentric composition is used for building and updating such a service network.

A. Definitions and Techniques

Using the previous definition on service relations, we define in this section our user-excentric service composition. This composition is not requested by users and hence need to be as transparent as possible. To define the composition over services we begin by defining the composition over operations. Considering three operations op i , op j and op k . we define a user-excentric composition as follows:

DEFINITION 5 -User-excentric operation composition O sem (op i , op j ) = T rue and ∃l ∈ {i, j, k} , ≡ sem (op comp(opi,opj ) , op l ) = T rue

The new resulting composed operation op comp(opi,opj ) is compatible with one of the three operations (op i , op j , op k ) which means that it is invisible to the users (it has the same signature as already existing operations) but hence propose new functionalities (which correspond to the combination of the two operations op i and op j ).

EXAMPLE 3: Considering our running example, two user-excentric service composition are possible as shown in Figure 6. Concerning the non functional property compatibility, the store composition is always possible as the qualitative property of the reSize output is Exact semantic matching with the store input qualitative property, and the intersection of their quantitative property exists. For the getSnapshot the composition is not possible all the time due to the Subsume semantic match between the respective qualitative property.

Based on DEFINITION 5 we define the user-excentric service composition as follows: DEFINITION 6 -User-excentric service composition O sem (S i , S j ) = T rue and ∃l ∈ {i, j, k} , ≡ sem (S comp(Si,Sj ) , S l ) = T rue

The new resulting service is compatible to an already existing service as it publishes the same interface. EXAMPLE 4: Figure 7 describes the functional and non functional properties of the two services T ake photo and Storage. The functional properties reflect the service composition and the non functional properties are the intersection between those of the composed services. These new composite services extend the environment with new implementations (functional property) and new non functional properties. This result reflects our choice to restrict the semantic compatibility between services and operations only to their interface signature. By this way we extend the environment not only with new implementations but also new non functional properties.

B. Servicebook Application

Coming back to the Servicebook application, we argue that the user-excentric composition is an efficient tool for updating this social network with all the capabilities the environment can offer. When a service appears in the Servicebook environment, it first checks whether a group of its interface description already exists. If so, the new service joins this group and brings with it its functional implementation and non functional properties. If no group already exists, it creates a new group publishing this new interface.

We suppose that three atomic different services are available in the environment S i , S j and S k . For each service, a group is created hosting the interface of the service and the corresponding implementation (cf. Figure 8). Supposing that:

O sem (S i , S j ) = T rue and ∃l ∈ {i, j, k} , ≡ sem (S comp(Si,Sj ) , S l ) = T rue

The new composed service S comp(Si,Sj ) is added to the S l group ∀ l ∈ {i, j, k}. Each group is extended with new user-excentric composite service appearing (in Figure 8 the S k group is extended as we suppose l = k).

VII. EVALUATION AND RESULTS

We implemented, as a proof of concept, all the major functionalities of the user-excentric service composition under an OSGi service platform implementation, the Apache Felix. For the evaluations we developed a simulation use case composed of 100 OSGi services in a small environment deployed on three laptops. We evaluated the time and memory consumption of the semantic tools, service relation computing and the user-exentric service composition.

• The prototype matches all the inputs and outputs of these services together in order to find all the compatible services from these 100 services. We suppose that each service has one operation. Table I gives the time and memory consumption values for matching two operations and 100 operations. We notice that semantic matching is much slower and consume more than simple quantitative computing. Indeed, accessing an ontology to find the needed concept can be tedious depending on the ontology length and depth. • Table III gives the time and memory values to compose two services together and 100 services two by two. The composition technique we adopted is in creating for each newly composed service a new unit of deployment independent from the services taking part in the composition. We can notice that the more the number of composed service is, the slower and heavier is the composition process. This is due to our composition technique that creates for each newly composed service a new unit of deployment. Another technique would be to only redirect the call to the services involved in the composition allowing by that our user-excentric service composition to scale to large environments.

VIII. CONCLUSION

In this article, we proposed a new way to compose services in a user-excentric way. This novel composition is ensured by simply combining two very well known service relations: the compatible relation and the composition one. We formalized the service compatible and composition relations and proposed an easy combination of them in order to propose this new way of composing services. This user-excentric service composition extends the environment with new capabilities even if not required at that moment by users with a highly appreciable condition, keeping the service and operation signatures unchanged. We proposed, the Servicebook as an application use case for the user-excentric composition. This new type of service social network provides to users all the capabilities an environment can offer in terms of services. We implemented a prototype under Java OSGi framework as a proof of concept and evaluated the efficiency of our proposal. The next step would be to test our prototype in large and highly dynamic environments, such as university campus, were thousands of services may meet and where a real end user experience could be tested to evaluate the interest, efficiency and scalability of our user-excentric service composition approach in these highly dynamic environments. Later on, we aim to develop the Servicebook on the web to evaluate the utility and attractiveness of such networks for Web applications.

Figure 1 .

 1 Figure 1. Servicebook: a social network of services

• 0 .

 0 .1 (zero or one time) • |A| (the cardinality if applied to a set A) We define functional properties of an operation as follows: DEFINITION 1 -Functional property definition op : (In * , Out 0..1 , P, N p * ) in : (name, semantic), name ∈ Σ * out : (semantic) p : (semantic, type) type ∈ {atomic, composed} semantic = (o, n), o ∈ O, n ∈ N

EXAMPLE 1 :

 1 Three service examples are given in Figure2. For conciseness and clarity we suppose that each service has one operation.

Figure 2 .

 2 Figure 2. Running example services

Figure 3 .

 3 Figure 3. access ontology

M

  Cpt (In opi , In opj ) = Exact and M Cpt (Out opi , Out opj ) = Exact • P lugIn semantic matching to op j if they are not Exact matching and all the matching between their respective comparable inputs and their respective output values are Exact or P lugIn. M Cpt (In opi , In opj ) ∈ {Exact ∨ P lugIn} and M Cpt (Out opi , Out opj ) ∈ {Exact ∨ P lugIn} • Subsume semantic matching to op j if they are no Exact or P lugIn matching and at least one matching value between their respective comparable inputs or their respective output is Subsume M Cpt (In opi , In opj ) = Subsume or M Cpt (Out opi , Out opj ) = Subsume and no F ail matching value is found between outputs, and the corresponding comparable inputs. M Cpt (In opi , In opj ) = F ail and M Cpt (Out opi , Out opj ) = F ail • They are F ail semantic matching to op j if at least one semantic matching value between their respective comparable inputs or their respective outputs is F ail. M Cpt (In opi , In opj ) = F ail or M Cpt (Out opi , Out opj ) = F ail

Figure 4 .

 4 Figure 4. Operation op i composable with operation op j

Figure 5 .

 5 Figure 5. Non functional property compatibility

Figure 6 .

 6 Figure 6. User-excentric operation compositionAs shown Figure6, the new composed getSnapshot operation has the same signature as the atomic getSnapshot but with extended functionalities. It can resize the picture image it produces. The new composed store operation has the same signature as the atomic store with extended implementation allowing to resize images before storing them.Concerning the non functional property compatibility, the store composition is always possible as the qualitative property of the reSize output is Exact semantic matching with the store input qualitative property, and the intersection of their quantitative property exists. For the getSnapshot the composition is not possible all the time due to the Subsume semantic match between the respective qualitative property.Based on DEFINITION 5 we define the user-excentric service composition as follows:

Figure 7 .

 7 Figure 7. New composed service descriptions

Figure 8 .

 8 Figure 8. User-excentric composition in Servicebook