Zeina Azmeh
email: azmeh@lirmm.fr

Maha Driss
email: mdriss@irisa.fr

Fady Hamoui
email: hamoui@lirmm.fr

Marianne Huchard
email: huchard@lirmm.fr

Naouel Moha
email: moha.naouel@uqam.ca

Chouki Tibermacine
email: tibermacin@lirmm.fr

Selection of Composable Web Services Driven by User Requirements

Keywords: Web service selection, Web service composition, Formal Concept Analysis (FCA), Relational Concept Analysis (RCA), User requirements, QoS

Building a composite application based on Web services has become a real challenge regarding the large and diverse service space nowadays. Especially when considering the various functional and non-functional capabilities that Web services may afford and users may require.

In this paper, we propose an approach for facilitating Web service selection according to user requirements. These requirements specify the needed functionality and expected QoS, as well as the composability between each pair of services. The originality of our approach is embodied in the use of Relational Concept Analysis (RCA), an extension of Formal Concept Analysis (FCA). Using RCA, we classify services by their calculated QoS levels and composability modes. We use a real case study of 901 services to show how to accomplish an efficient selection of services satisfying a specified set of functional and non-functional requirements.

I. INTRODUCTION

Service-Oriented Computing (SOC) is an emerging paradigm for developing low-cost, flexible, and scalable distributed applications based on services [START_REF] Huhns | Service-oriented computing: Key concepts and principles[END_REF]. Web services represent a realization of SOC. They are autonomous, reusable, and independent software units that can be accessed through the internet. SOC is becoming broadly adopted and in particular by organizations, which are more and more willing to open their information systems to their clients and partners over the Internet. The reason comes from the fact that SOC offers the ability to build efficiently and effectively addedvalue service-based applications by composing ready-made services. Web service composition addresses the situation when the functionality required by users (developers) cannot be satisfied by any available Web service, but by assembling suitably existing services [START_REF] Rao | A Survey of Automated Web Service Composition Methods[END_REF]. When building Web servicebased applications, we have to face several issues such as:

-Web service retrieval from the large number of existing services, and the lack of efficient indexing mechanisms. Current solutions are embodied in search engines, like: Seekda [3] and Service-Finder [START_REF]Service-Finder[END_REF]; a service's ability to meet the user's functional and non-functional requirements;

a service's composability, or the degree to which a service can be composed with another, considering the needed adaptations; the last issue is how can we achieve a compromise for service selection in the light of the previous issues. Discovering and selecting services that closely fit users' functional and non-functional requirements is an important issue highly studied in the literature as in [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF], [START_REF] Aggarwal | Constraint driven web service composition in meteor-s[END_REF], [START_REF] Yu | Efficient algorithms for web services selection with end-to-end qos constraints[END_REF]. Functional requirements define functionalities provided by Web services and non-functional requirements define Quality of Service (QoS) criteria such as availability, response time, and throughput [START_REF] Menascé | Qos issues in web services[END_REF]. However, discovering and selecting relevant composable services is another important issue that still need to be investigated, since few approaches focused on service composability problem [START_REF] Medjahed | A multilevel composability model for semantic web services[END_REF], [START_REF] Ernst | Detection of web service substitutability and composability[END_REF], [START_REF] Lécue | Semantic and syntactic data flow in web service composition[END_REF]. Relevant composable services represent services that minimize the amount of adaptation among them while best fitting requirements.

In this paper, we propose an approach for the identification of services that best fit QoS and composition requirements. This approach is based on Relational Concept Analysis (RCA) [START_REF] Huchard | Relational concept discovery in structured datasets[END_REF], a variant of Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF], [START_REF] Wille | Restructuring lattice theory: an approach based on hierarchies of concepts[END_REF]. FCA has been successfully used as a formal framework for service substitution [START_REF] Peng | Management and retrieval of web services based on formal concept analysis[END_REF], [START_REF] Aversano | Using concept lattices to support service selection[END_REF], [START_REF] Azmeh | Wspab: A tool for automatic classification and selection of web services using formal concept analysis[END_REF], [START_REF] Azmeh | Using concept lattices to support web service compositions with backup services[END_REF], [START_REF] Chollet | Heterogeneous service selection based on formal concept analysis[END_REF]. The approach also integrates a query mechanism that allows users to specify their required QoS and composability levels. Thereafter, the generated lattices help in identifying the services that match the specified queries.

The paper is organized as follows: Section II gives an overview of the FCA and RCA classification techniques. Section III describes our approach. Section IV describes the experiments performed on a real case study for validating our approach. The paper ends with the related work in Section V and the conclusion in Section VI.

II. BACKGROUND

In this section, we give the basic definitions of FCA and RCA, along with a simple example of exploiting them.

A. Formal Concept Analysis (FCA)

We base our approach on FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF], [START_REF] Wille | Restructuring lattice theory: an approach based on hierarchies of concepts[END_REF] which is a classification method that permits the identification of groups of objects having common attributes. It takes a data set represented as an n×m table (formal context) with objects as rows and attributes as columns. A cross "×" in this table means that the corresponding object has the corresponding attribute. An example of a formal context is shown in Table I, for a set of objects O={1,2,3,4,5,6,7,8,9,10} and a set of attributes A={odd,even,prime,composite,square}.

odd even prime composite square 1 × × 2 × × 3 × × 4 × × × 5 × × 6 × × 7 × × 8 × × 9 × × × 10 × ×
From a formal context, FCA extracts the set of all the formal concepts. A formal concept is a maximal set of objects (called extent) sharing a maximal set of attributes (called intent). For example, in Table I, a=({4,6,8,10},{even, composite}) is a formal concept because the objects 4, 6, 8, and 10 share exactly the attributes even and composite (and vice-versa). On the other hand, ({6},{even, composite}) is not a formal concept because the extent {6} is not maximal: other objects share the same set of attributes.

FCA reveals the inheritance relations (super-concept and sub-concept) between the extracted concepts and organizes them into a partially ordered structure known as Galois lattice or concept lattice. The resulting concept lattice is illustrated in Figure 1(L). This lattice reveals phenomena that may not be recognized intuitively. For example, in Figure 1(R) appears the concept b=({4},{composite,even,square}) as a sub-concept of the concept a. It inherits a's attributes composite and even, and extends it by the square.

B. Relational Concept Analysis (RCA)

RCA [START_REF] Huchard | Relational concept discovery in structured datasets[END_REF] is an extension of FCA that takes into consideration the relations between the objects. Thus, it takes as input two types of contexts: (non-relational) ones that are previously used with FCA to classify objects by attributes, and inter-context (relational) ones that represent the relations between the objects. RCA generates lattices similar to the ones generated by FCA, but enriched with the information about the relation between the objects. We take as an example two sets of numbers, {1,2,3,4,5} and {11, 12,13,14,15,16,17,18,19,20}. We build two non-relational contexts similar to the one in Table I. We consider a relation called Divides between the first and second sets of numbers, and we build the relational context in Table II. RCA takes the two non-relational contexts

× × × × × × × × × × 2 × × × × × 3 × × × 4 × × × 5 × ×
(numbers×attributes), and the relational context Divides, then generates the two lattices in Figure 2. These lattices are similar to FCA lattices, but one of them is enriched with the relation Divides. For example: by regarding the concept a=({2},{prime,even, Divides:c7,Divides:c3}) in lattice (L), we notice that numbers of its extent can divide numbers of the extents of the concepts 7 and 3 in lattice (R). In the general case, where relations form directed cycles between objects, RCA applies iteratively. During this iteration, several scaling operators can be used. Here we use the existential one (see [START_REF] Huchard | Relational concept discovery in structured datasets[END_REF] for more details). III. APPROACH Using our approach, a user can specify an abstract process described as a set of functional and non-functional requirements. The functional requirements describe the needed tasks, while the non-functional requirements describe the expected QoS and mode of composition for these tasks. The approach retrieves sets of Web services, filters and analyzes their data according to the user requirements. Then, it classifies them in concept lattices based on RCA classification technique (II-B). This latter enables a simplified selection of Web services that best match the specified requirements and thus, allows the realization of a desired process with less time and effort.

We explain our approach in view of Figure 3, which illustrates the different components and their course of action that lead to service selection. We describe these components respectively along with an example of an abstract process of three tasks {Task1,Task2,Task3}, as follows:

A. User Requirements Analyzer:

The approach starts by analyzing the requirements specified by the user via a description file (see Figure 4), which is composed of the following elements:

1) Functional requirements: this part is described by a set of tasks. Each task is described by its input and output parameters via their names and types.

For each parameter, a user specifies a set of relevant keywords for its name, and another set for its type. For example, Task1 has one input parameter, which is defined by {InParamNameKeys1, InParamTypeKeys1}. We enabled the user of providing more than one keyword, in order to retrieve more relevant services. For example: if a user needs a "date" parameter, he/she may specify the possible keywords for its name as {date} and types (primitive or complex) as {string, date}. 2) Non-functional requirements: this part is composed of two other parts.

-QoS specification, which specifies the requested QoS level for each task according to the supported QoS attributes (qos x ,qos y ,etc.). -Composition specification, which specifies the mode of composition (links) between each two consecutive tasks, for example: Task1 → Task2. The mode of composition describes whether Task1 (source) covers all the input of Task2 (target) or not. This notion is better described below. The analyzer extracts the information related to these functional and non-functional requirements, which is used by the remaining components as described below.

B. Web Service Retriever:

The requirements analyzer sends to this component the keywords provided for the parameter names input/output for each task {InParamNameKeys, OutParam-NameKeys}. In our example, the retriever searches and retrieves a set of services: WS1.i, WS2.j, and WS3.k, corresponding respectively to each of the three tasks. It also gathers the QoS values (the supported attributes) for each retrieved service (qos x .i,qos y .i,etc.).

C. WSDL Parser:

Each set of the retrieved services is passed to this component 1 , in order to extract for each service its operations with their input/output parameters.

Using the information extracted from the parsed services, we can check a service's compatibility.

D. Compatibility Checker:

This component checks whether a service provides an operation that can satisfy the corresponding task. An operation satisfies a task when it contains the requested input/output parameters names. We verified this by using the Jaro-Winkler string distance measure [START_REF] Cohen | A comparison of string distance metrics for name-matching tasks[END_REF]. By doing so, we discovered three possible cases:

compatible, there exists one operation at least that satisfies the corresponding task and has the same parameters types; or it may become: adaptable compatible, meaning that none of the satisfying operations has the same parameter types (either for input, or output, or both), thus type adaptations need to be done; otherwise: incompatible, the service does not satisfy the corresponding task. The compatibility checker reduces the number of the retrieved services, by omitting the incompatibles ones (WS1.i becomes WS1.i'). Thus, it keeps a detailed list of the compatible services together with their satisfying operations.

Once we identified the compatible services, we can measure the mode of composition and the QoS levels using the two following components.

E. Composability Evaluator:

Composing two Web services is finding two operations (one of each) that can be linked. Two operations can be linked when the output parameters of the first (source) can cover the input parameters of the second (target). We can define two composition modes according to the coverage of the input parameters of a target operation, in addition to two other modes according to the needed adaptations that are discovered by the compatibility checker. They are: -Fully-Composable (FC), when a source operation covers by its outputs all of the expected inputs of a target operation; -Partially-Composable (PC), when one or more input parameters of a target operation are not covered; -Adaptable-Fully-Composable (AFC), when the source and target operations have an FC mode, but need some type adaptations either for the output of the source or the input of the target, or both of them; and -Adaptable-Partially-Composable (APC), similar to AFC but when having a PC mode.

Thus, having the composition Task1 → Task2, the composability evaluator determines the mode of composition for all the services in WS1.i' with all the services in WS2.j'.

Then, it generates four relational contexts (Section II-B) between WS1.i' and WS2.j' according to the four previously defined modes of composition. These contexts are exploited by the RCA classifier to clarify which services can be composed and following which mode. This is illustrated in the experiments section IV.

F. QoS Levels Calculator:

This component takes into consideration the QoS values for all the sets of compatible services (qos x .i',qos x .j',qos x .k',etc.). It extracts these values from the ones returned by the service retriever, according to the list returned by the compatibility checker. Web services have many QoS attributes and different ranges of numerical values for each one of these attributes. In order to have a better overview of these values, we apply a statistical technique called BoxPlot++ [START_REF] Azmeh | BoxPlot++[END_REF] to cluster the convergent values together. The BoxPlot++ is an extension of the original boxplot [START_REF] Mcgill | Variations of Box Plots[END_REF] technique. It takes as input a given set of numerical values, and produces one to seven corresponding levels of values: L = {BadOutlier,VeryBad,Bad,Medium,Good, VeryGood,GoodOutlier}2 . The technique is applied on each QoS attribute. Then, it generates for each set of services a non-relational context (Section II-A) having all of its QoS attributes levels. These contexts are exploited afterwards by RCA classifier, in order to classify the services according to these different QoS levels.

G. RCA Classifier:

This component takes into consideration the relational contexts of composition modes and the non-relational contexts of QoS levels. It also uses the non-functional requirements provided in the user requirements file. These requirements are considered as queries that are added to the two types of contexts as follows:

The QoS specifications for each task are integrated to the corresponding non-relational context as a new row. The composition specifications are also integrated to the corresponding relational context in the same way.

Finally, the RCA classifier [START_REF] Galicia | Galois lattice interactive constructor[END_REF] generates all the corresponding service lattices and passes them to the final component. This component is further detailed in [START_REF] Azmeh | QoS-Driven Selection of Composable Web Services[END_REF].

H. Lattice Interpreter:

By integrating the non-functional queries into the contexts, they appear inside the concepts of the corresponding lattices. This enables this component of locating the services that satisfy the queries and to navigate between the different solutions. These services are present at the sub-concepts of the queries concepts. This is better illustrated in section IV.

IV. EXPERIMENTS

We applied our approach on an abstract process, which is supposed to provide the weather information for a given ip address. It is described by a user requirements file (Section III) using three tasks: Task1, Task2, and Task3. Task1 takes as input an ip address and provides Task2 with the corresponding city name. Task2 takes the city name and returns to Task3 the corresponding zipcode. Finally, Task3 returns the corresponding weather information. From this file, the experiments are conducted on four steps as follows:

1. Collecting Services: We use the set of keywords describing each task to search and retrieve sets of corresponding Web services. We make use of the Service-Finder Web service search engine [START_REF]Service-Finder[END_REF] to collect a set of corresponding endpoints (WSDL addresses). This engine also provides us with values of two QoS attributes: availability (A) and response time (RT). We download the corresponding WSDL files after omitting repeated and invalid endpoints. We show in Table III each task with its keywords as well as the number of obtained endpoints, the number of retrieved WSDL files, and the sets identifiers. In this step, we make use of the requirements analyzer components (III-A) and the service retriever (III-B). 2. Filtering the Services: In this step, we parse the WSDL files using the WSDL parser (III-C) and remove the invalid ones (Filter1). Then we calculate the compatible ones (Filter2) using the Compatibility checker (III-D). In Table IV, we can see the resulting number of filtered services for each set. 3. Composability and QoS: In this step, we calculate the composition modes for the compatible sets of services (Table V) as well as their QoS levels. We use the Composability evaluator (III-E) and the QoS level calculator (III-F).

The resulting composition modes and QoS levels are organized into non-relational and relational contexts (see [START_REF]RCA contexts[END_REF]), and are used to classify the services in the next step.

4. RCA-Based Classification: During this step, the RCA classifier (III-G) takes the contexts formed in the previous step and integrates the QoS queries. The queries that we choose in this case study are specified to be Good A and Good RT levels for each task in the process. We also require an FC composition mode for both (Task1,Task2) and (Task2,Task3). The generated lattices are illustrated in Figure 5. These lattices are finally interpreted by the lattice interpreter (III-H), considering two rules:

in each lattice, the services satisfying the corresponding query (QoS and composition) appear in the subconcepts of the concept where the query appears. Example: the services in c0 (WS1.i) satisfy Query1; the services located closer to the bottom of a lattice offer better QoS levels than the farther ones, for example: in the lattice (WS2.j), the service WS2.8 is better than service WS2.198 because it has a VeryGood A (an inherited attribute). On the other hand, the services located in a same concept have convergent QoS levels. Following the precedent rules, the lattice interpreter extracts the following services to be the best choice regarding the specified requirements: {WS1.59,WS1.5,WS1.3} for Task1 because they all appear in the same concept (c0); {WS2.8} for Task2 because it is better than {WS2.198}; and {WS3.23} for Task3 because it is better than {WS3.1}. If we verify the actual services, we get the information in Table VI. facilitates services selection according to user requirements. In each lattice, services are classified by their QoS levels as well as their composition modes with services in a following lattice. A lattice reveals two relations between the services regarding QoS: hasSimilarQoS when services are located in a same concept and hasBetterQoS when a service is a descendant of another service(s). Services having a hasSimilarQoS or hasBetterQoS relations with a selected service, are considered to be its alternatives. User requirements (queries) can be expressed as new services to be classified in the corresponding lattices. This locates the part of the lattice that meets the user requirements and thus represent an efficient lattice navigation mechanism. In the case where no services could be found for the specified requirements, the query mechanism enables the user to identify the next best service selection. This service will have lesser QoS than the requested and it represents the direct ascendant of the query concept. For example: in the third lattice of Figure 5, we could take WS3.2 or WS3.3 in concept c3 to be the next best selection. They have a Medium RT and a Good A.

In this experiment, we had several functional and nonfunctional requirements needed to build a simple process of three tasks as described previously. The Service-Finder enabled us to find a total of 901 (Table III) Web service addresses, among which we have to identify and retrieve the services meeting our requirements. Using our approach, we efficiently identified out of 901 endpoints a set of five services that best match our requirements (VI). The total time required to extract these services is equal to 103 sec3 , starting from the WSDL Parser (component C) till the end.

V. RELATED WORK

We list the related work according to three categories:

Web Service Composability: The Web service Composability problem have been addressed by many works [START_REF] Ernst | Detection of web service substitutability and composability[END_REF], [START_REF] Sycara | Automated discovery, interaction and composition of semantic web services[END_REF], [START_REF] Medjahed | Composing web services on the semantic web[END_REF], [START_REF] Medjahed | A multilevel composability model for semantic web services[END_REF], [START_REF] Lécue | Semantic and syntactic data flow in web service composition[END_REF]. Ernst et al. [START_REF] Ernst | Detection of web service substitutability and composability[END_REF] present an approach based on syntactic descriptions of Web services. This approach detects the matching between Web service's operations by analyzing the results obtained after multiple invocations of these services. The input and output parameter values are compared syntactically and matchings are deduced. Contrarily to our approach, which focuses on the syntactic, semantic, and QoS descriptions of Web services, this work is based on the experimental usage of Web services, and is perfectly complementary to ours. In this research area, much work has been done also on semantic Web services [START_REF] Sycara | Automated discovery, interaction and composition of semantic web services[END_REF], [START_REF] Medjahed | Composing web services on the semantic web[END_REF], [START_REF] Medjahed | A multilevel composability model for semantic web services[END_REF], [START_REF] Lécue | Semantic and syntactic data flow in web service composition[END_REF]. In [START_REF] Sycara | Automated discovery, interaction and composition of semantic web services[END_REF], Sycara et al. present DAML-S, an ontology for semantic Web service description. They show the use of this ontology for service discovery, interaction, and composition. Two implementations are proposed: the DAML-S/UDDI Matchmaker that provides semantic capability matching and the DAML-S Virtual Machine that manages the interaction with Web services. Contrarily to our approach, this work do not deal with QoS properties to compose Web services. In [START_REF] Medjahed | Composing web services on the semantic web[END_REF] and [START_REF] Medjahed | A multilevel composability model for semantic web services[END_REF], Medjahed et al. present a model for checking the composability of semantic Web services at different levels: syntactic, semantic, and QoS. Two kinds of composability are defined: horizontal (normal composability) and vertical (substitutability). This work deals with three QoS properties: fees, security, and privacy. In our approach, we may consider any QoS property. We used availability and response time provided by Service-Finder. In [START_REF] Lécue | Semantic and syntactic data flow in web service composition[END_REF], Lécue et al. present a method which combines semantic and static analysis of messages in semantic Web services. Data types (XML schemas) and semantic description (domain ontologies and SA-WSDL specifications) of parameters are used to deduce mappings. These mappings are then transformed into adapters (XSL documents). In this work, the focus is on the generation of adapters of Web service data flows. This enhances greatly the composability of Web services which are not directly composable. In our work, we concentrated on the selection of services that best fit the user's QoS and composability requirements. The two approaches are complementary.

QoS-Based Web Service Selection: Many approaches like [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF], [START_REF] Aggarwal | Constraint driven web service composition in meteor-s[END_REF], [START_REF] Yu | Efficient algorithms for web services selection with end-to-end qos constraints[END_REF] have been proposed to solve the problem of QoS-based Web service selection. In [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF], Zeng et al. present a middle ware platform that enables the quality-driven composition of Web services. In this platform, the QoS is evaluated by means of an extensible multidimensional model, and the selection of Web services is performed in such a way as to optimize the composite service's QoS. Aggarwal et al. [START_REF] Aggarwal | Constraint driven web service composition in meteor-s[END_REF] present a constraint driven Web services composition tool that enables the selection and the composition of Web services considering QoS constraints. Like Zeng et al. [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF], a linear integer programming approach is proposed for solving the optimization problem. In [START_REF] Yu | Efficient algorithms for web services selection with end-to-end qos constraints[END_REF], Yu et al. propose heuristic algorithms to find a near-to-optimal solution more efficiently than exact solutions. They model the QoS-based service selection and composition problem in two different ways: a combinatorial model and a graph model. A heuristic algorithm is introduced for each model. The QoS-based service selection problem is viewed by all the works detailed above [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF], [START_REF] Aggarwal | Constraint driven web service composition in meteor-s[END_REF], [START_REF] Yu | Efficient algorithms for web services selection with end-to-end qos constraints[END_REF] as an optimization problem that aims to find the service that best fit QoS requirements from the set of candidate services. The advantage of our approach compared to these works is that FCA provides equivalence classes of services (the extents formal concepts provide classes of services that share the same characteristics). If a service in an application fails, one of the other services in the class can replace it. This provides considerable enhancement for the dynamic composition since it reduces the reaction time.

Web Service Classification Using Concept Lattices:

Many works in the literature like [START_REF] Peng | Management and retrieval of web services based on formal concept analysis[END_REF], [START_REF] Aversano | Using concept lattices to support service selection[END_REF], [START_REF] Azmeh | Wspab: A tool for automatic classification and selection of web services using formal concept analysis[END_REF], [START_REF] Azmeh | Using concept lattices to support web service compositions with backup services[END_REF], [START_REF] Fenza | Friendly web services selection exploiting fuzzy formal concept analysis[END_REF], [START_REF] Chollet | Heterogeneous service selection based on formal concept analysis[END_REF], [START_REF] Driss | A requirement-centric approach to web service modeling, discovery, and selection[END_REF] have addressed the classification of Web services using concept lattices. Peng et al. [START_REF] Peng | Management and retrieval of web services based on formal concept analysis[END_REF] present an approach to classify and select services. They build lattices upon contexts where individuals are Web services and properties represent the operations of these services. The approach allows similar services clustering by applying similarity search techniques that compare operation descriptions and input/output messages data type. Aversano et al. [START_REF] Peng | Management and retrieval of web services based on formal concept analysis[END_REF] use FCA, to understand relationships between services, as well as between operations of a complex service, by analyzing service interfaces and documentation. Concept lattices are built upon a context obtained from keywords extracted from service descriptions or operation parameters. They cluster similar services, highlight hierarchical relationships, commonalities, and differences between services. Azmeh et al. [START_REF] Azmeh | Wspab: A tool for automatic classification and selection of web services using formal concept analysis[END_REF] present a similar approach to classify and select services using the FCA. They propose WSPAB tool that permits the discovery, the automatic classification, and the selection of Web services. Classification is accomplished by defining a binary relation between services and operation signatures. In [START_REF] Azmeh | Using concept lattices to support web service compositions with backup services[END_REF], Azmeh et al. uses FCA to classify Web services by keywords extracted from their WSDL description files, to identify relevant services and their substitutes. Fenza and Senatore [START_REF] Fenza | Friendly web services selection exploiting fuzzy formal concept analysis[END_REF] describes a system for supporting the user in the discovery of semantic Web services that best fit personal requirements and preferences. Through a conceptbased navigation mechanism, the user discovers conceptual terminology associated to the Web services and uses it to generate an appropriate service request which syntactical matches the names of input/output specifications. The approach exploits the fuzzy FCA for modelling concepts and relative relationships elicited from Web services. After the request formulation and submission, the system returns the list of semantic Web services that match the user query. Contrarily to our approach, these works [START_REF] Peng | Management and retrieval of web services based on formal concept analysis[END_REF], [START_REF] Aversano | Using concept lattices to support service selection[END_REF], [START_REF] Azmeh | Wspab: A tool for automatic classification and selection of web services using formal concept analysis[END_REF], [START_REF] Azmeh | Using concept lattices to support web service compositions with backup services[END_REF], [START_REF] Fenza | Friendly web services selection exploiting fuzzy formal concept analysis[END_REF] do not deal with QoS properties to classify Web services. In [START_REF] Chollet | Heterogeneous service selection based on formal concept analysis[END_REF], Chollet et al. propose an approach based on FCA to organize the services registry at runtime and to allow the best service selection among heterogeneous and secured services. The services registry is viewed as a formal context where the services are the individuals and the services types, functional, and non-functional characteristics (security characteristics) are properties. In [START_REF] Driss | A requirement-centric approach to web service modeling, discovery, and selection[END_REF], Driss et al. propose a requirement-centric approach to Web services, modelling, discovery, and selection. They consider formal contexts with services as individuals and QoS characteristics as properties. The obtained lattices are used to check out relevant (that best fit functional requirements) and high QoS Web services. All the works detailed above [START_REF] Peng | Management and retrieval of web services based on formal concept analysis[END_REF], [START_REF] Aversano | Using concept lattices to support service selection[END_REF], [START_REF] Azmeh | Wspab: A tool for automatic classification and selection of web services using formal concept analysis[END_REF], [START_REF] Azmeh | Using concept lattices to support web service compositions with backup services[END_REF], [START_REF] Fenza | Friendly web services selection exploiting fuzzy formal concept analysis[END_REF], [START_REF] Chollet | Heterogeneous service selection based on formal concept analysis[END_REF], [START_REF] Driss | A requirement-centric approach to web service modeling, discovery, and selection[END_REF] are based on FCA, and not on RCA. In addition, they do not deal with service composition since they propose to classify and select only individual services.

VI. CONCLUSION

In this paper, we presented an approach for facilitating Web service selection according to user functional and nonfunctional requirements. This approach is based on four principal steps; service collecting, validity and compatibility filtration, QoS levels calculating, and RCA classification. The resulting lattices group services that have common QoS and composition levels. User requirements are expressed as new services and are classified in the corresponding lattices. This locates the part of the lattice that meets the user requirements. We validated our approach on a set of 901 real-world Web services obtained by querying Service-Finder. Experimental results show that our approach allows an efficient selection of services satisfying the specified functional and non-functional requirements.

Future work includes: (i) enhancing the composability evaluator component by considering advanced semantic and syntactic similarity techniques; (ii) proposing keywords to the user to help her/him in specifying the needed tasks more efficiently; and (iii) performing experiments on more complex compositions.

Figure 1 :

 1 Figure 1: Formal concept lattice for the context in Table I (L); focus on the concept b (R). Lattices are built with Concept Explorer (ConExp) tool [20].

Figure 2 :

 2 Figure 2: The enriched lattices generated by RCA.

Figure 4 :

 4 Figure 4: An excerpt of the user's requirements file.

Figure 3 :

 3 Figure 3: An overview of the approach's components in their course of action.

Figure 5 :

 5 Figure 5: The concept lattices for the compatible sets of services with Good A, Good RT queries, and FC mode.

Table I :

 I A formal context for objects O and attributes A.

Table II :

 II The relational context Divides.

	Divides 11	12	13	14	15	16	17	18	19	20
	1

Table III :

 III Summary of the retrieved services.

	Task Keywords	#Endpoints	#Services	SetID
	1	{ip,ipAddress},	94	94	WS1.i
		{city,cityName}
	2	{city,cityName},	768	760	WS2.j
		{zip,zipcode,postal,postalcode}
	3	{zip,zipcode,postal,postalcode},	39	37	WS3.k
		{weather,weatherInfo,forecast,
		weatherForecast,weatherReport}

Table IV :

 IV The number of filtered services for each set.

		WS1.i	WS2.j	WS3.k
	Filter1 (Valid)	94	748	37
	Filter2 (Compatible)	17	96	21

Table V :

 V Number of services per composition mode.

		WS1.i'	WS2.j'	WS3.k'
	# FC services	12	3	12
	# PC services	4	89	4
	# AFC services	2	1	11
	# APC services	0	3	2

Table VI :

 VI Information about the services satisfying the queries with the selected ones (highlighted).

	WS	Name	Operation	A(%) RT(ms)
	1.59	Ip2LocationWebService	IP2Location	100	257
			(in) IP:string
			(out) CITY:string,..
	1.5	GeoCoder	IPAddressLookup	100	328
			(in) ipAddress:string
			(out) City:string,..
	1.3	IP2Geo	ResolveIP	100	798
			(in) ipAddress:string
			(out) City:string,..
	2.198	MediCareSupplier	GetSupplierByCity	85	304
			(in) City:string
			(out) Zip:string,..
	2.8	ZipcodeLookupService	CityToLatLong	100	439
			(in) city:string
			(out) Zip:string,..
	3.1	USWeather	GetWeatherReport	85	384
			(in) ZipCode:string
			(out) WeatherReport:string
	3.23	Weather	GetCityForecastByZIP	100	237
			(in) ZIP:string
			(out) ForecastReturn:complex
	These service lattices offer a browsing mechanism that

Available online: http://www.lirmm.fr/ ∼ azmeh/tools/WsdlParser.html

Available online: http://www.lirmm.fr/ ∼ azmeh/tools/BoxPlot.html

Calculated by NetBeans (6.9.1) using Intel Core 2 Duo (1.80GHz) and a RAM of (2.00 GB).


Christine Louberry
email: christine.louberry@mines-nantes.fr

Philippe Roose
email: philippe.roose@iutbayonne.univ-pau.fr

Marc Dalmau
email: marc.dalmau@iutbayonne.univ-pau.fr

Kalimucho: Contextual Deployment for QoS Management

Keywords: QoS management, context-awareness, contextual deployment, dynamic adaptation, software component

Recently, the increasing use of mobile technologies leads to face with new challenges in order to satisfy users. New systems deal with three main characteristics: context changes, mobility and limited resources of such devices. In this article we try to address such requirements using QoS-driven dynamic adaptations of application deployment. We are particularly interested in distributed applications QoS management facing with hardware limitations and mobility of devices, user requirements and usage constraints. We propose a service-based reconfiguration platform named Kalimucho. It implements a contextual-deployment heuristic to find a configuration matching context and QoS requirements. Kalimucho was tested with the Osagaia/Korrontea component model and several devices; the results confirm that Kalimucho provides a satisfying execution time to adapt applications.

Introduction

The increasing use of mobile technologies leads to face with new challenges in order to satisfy people using mobile devices. As they can now take their devices anywhere, people wish to use their favorite applications as well as at home. Moreover, they wish that applications could be automatically customized according to their location, light, weather or other environmental oriented context. However, we have to deal with three main characteristics of such systems: context changes, mobility and limited resources.

The aim of this article is to answer to user needs and changes of the environment using QoS-driven dynamic adaptations of application deployment. We are particularly interested in QoS management of distributed applications facing with hardware limitations and mobility of devices, user requirements and usage constraints.

In this article, we illustrate our work with the sample use case of a tourismcentered application: the visit of a museum. Three visitors use the application running on a mobile device (a smart phone for example). The museum provides a server hosting a video information service (fig. 1). We consider that the best QoS is to broadcast a color video. The visitor #3 moves in the museum. The platform is advised of this change and consequently estimates the quality of the video service provided to the user #3. First, the bandwidth is low but the device still reach the server. To ensure the continuity of the service, one solution is to reduce the number of transmitted data. The server transforms the color video in a black and white one. Secondly, the device cannot reach the server. The platform has to look for a new route to reach the device #3 and ensure the continuity of the service. For example, the visitor #2 device, which also uses the video service, can be a relay for the device #3. Discovering a new route to broadcast information is a classic problem, many protocols as AODV [START_REF] Chakeres | AODV Routing Protocol Implementation Design[END_REF] can be implemented. Nevertheless, such protocol just manages physical routing constraints. To propose more interesting solutions not only based on technical criteria of feasibility, we use a supervision platform distributed on each device enabling to have a complete and global knowledge of the application. Hence, because the color video is already broadcasted to the users #1 and #2, it is possible to use one of these two users as a relay for the user #3, which cannot reach the video service anymore. However if the relay device does not have enough energy available, the broadcast of a color video is not possible. We can thus propose to install a black and white conversion component on the relay device in order to transmit the adapted video more suitable to the energy available on the device. The energy consumption depending on the quantity of data, the conversion into black and white allows to reduce the quantity of data to transmit to the device #3 and thus to preserve its energy. Furthermore distributing services allows network load balancing. Obviously such a solution requires a good knowledge of the whole application in terms of services in order to choose the best deployment. Our approach using dynamic reconfiguration and redeployment allows proposing reliable solutions from both points of view of the infrastructure and the QoS.

In the remainder of this paper, we first discuss related work (Section 2). Section 3 presents the definition of context and QoS we use in this paper. In Section 4, we present our QoS model, which addresses the utility of an application and its durability. Then, in Section 5, we describe Kalimucho, our reconfiguration platform that provide contextual-deployment of applications in order to meet QoS requirements. Finally, Section 6 presents an experimentation of Kalimucho with the Sunspot platform and we conclude and discuss directions for future work (Section 7).

Related work

Routing protocol is the most common solution when dealing with QoS in distributed or mobile environment [START_REF] Chen | Qos routing performance in multihop, multimedia, wireless networks[END_REF] [START_REF] Lin | Qos routing in ad hoc wireless networks[END_REF]. Routing protocols allow discovering reliable routes, ensuring the continuity of service and the best bandwidth. However, such protocols are not sufficient to face with heterogeneity and context changing as well as highlevel routing decision. Following this report, several works proposed software architecture to manage QoS in mobile and limited systems. Such approaches address the global problem of context-awareness to manage QoS and adapt applications.

Music [START_REF] Rouvoy | Music : Middleware support for self-adaptation in ubiquitous and service-oriented environments[END_REF] project propose a context-aware middleware to adapt application in mobile systems. "Planning-based adaptation refers to the capability of adapting an application to changing operating conditions by exploiting knowledge about its composition and Quality of Service (QoS) meta-data associated to the application components" [START_REF] Floch | Using architecture models for runtime adaptability[END_REF]. Music considers that applications are developed with a QoS model such as utility functions. Applications are described in several variations where components are associated to QoS meta-data. The planning process chooses variations in order to maximize utility. Music is a device-oriented approach. For each adaptation, an adaptation domain is defined around the device requesting adaptation where the adaptation planner can act. Moreover, distribution plans are associated to each variation that limits the range of solutions. QuAMobile [START_REF] Sten Lundesgaard Amundsen | Qosaware mobile middleware for video streaming[END_REF] is a generic QoSaware software architecture for multimedia distributed applications. It is based on two concepts: QoS-oriented components monitoring QoS and a service planner. As Music, this service planner allows composing dynamically a configuration according to QoS requirements. This approach shows how it is important to model QoS and describe components and devices in order to provide a suitable configuration. However none of these works tackle the problem of distributed deployment. Some works such as Carisma and AxSeL [START_REF] Hamida | A graph-based approach for contextual service loading in pervasive environments[END_REF] provide contextual deployment solutions. As well as optimize resources consumption, they allow driving deployment according to physical and/or logical dependencies. Nevertheless no one includes network communication cost in adapting applications.

Context and QoS

A unique definition of what the context is does not exist. The context is application domain dependant. This article addresses QoS management through context adaptation in mobile applications. Hence, context has to include particularities of such applications: mobility, limited devices, customization according location, environment. We refer to the definition of Schilit and Teimer [START_REF] Schilit | Disseminating active map information to mobile hosts[END_REF] and one of David and Ledoux [START_REF] David | Wildcat: a generic framework for context-aware applications[END_REF]. Such definitions point out that the context and the QoS are linked: context changes can be seen as a QoS evolution. However, all context changes do not have the same consequence. Thus, we define three categories of context (fig. 2): user, usage and execution. The user context refers to user preferences, what service user wants to use. The usage context refers to application constraints. There are functional specifications, which define what the application must do and must not do. The execution context refers to hardware (CPU, memory, energy) and networks capabilities. These entities are traditionally monitored in context-aware systems. The context is a measure of the QoS of applications. Usually used in networks to measure the performance of transmissions according to quantitative criteria such as delay, gigue or rate of error, QoS cannot only be based on a network and hardware criterion [START_REF] Franken | Quality of service management using generic modelling and monitoring techniques[END_REF]. The consideration of the users' point of view is necessary but not enough for the QoS evaluation when dealing with constraint devices. Indeed, using limited mobile devices implies to optimize the energy consumption and the way to provide applications so that the offered service fits within environment constraints and can be used for a long time.

To achieve this goal, we wish to act at the three levels (fig. 2). At the infrastructure level, we have to guarantee the continuity of service, whatever the evolutions of the infrastructure are and despite hardware or network failure. At the application level, we have to guarantee the durability of the application. Indeed, the use of limited devices raises the problem of their lifetime. Finally, at the user level, we have to guarantee the respect of user needs to provide a useful application (utility).

Fig. 2. QoS and context interactions

Continuity of service.

Considering application QoS, the main objective is to guarantee the continuity of service despite the hardware, software and network failures. Furthermore we have to face with the heterogeneity due to the use of several types of devices, as well as hardware fails like the battery level of mobile devices. Application durability. We wish to guarantee the continuity of service of applications running on limited devices. One solution consists in maximizing the lifetime of the application. A device without energy causes the disconnection of all the services running on it and consequently may compromise the continuity of service. [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF] points out that network exchanges consume more energy than computation. Therefore, solutions based on service mobility can minimize transmissions and maximize lifetime.

Application utility. We defined the usage constraints as the functional specifications of the application that the system has to respect. For example, in the application of visiting a museum, the designer can express constraints as follows:

-When the visitor comes into a room where the conference is, avoid providing the information service with sound to not disturb the visitor.

-

When it is close time, activate the guide service to drive visitors to the exit door.

A two dimensional QoS model

In order to make the decision to reconfigure, we have to measure the application QoS. We aim at providing useful application running as long as possible. In mobile systems we have to meet the user needs and to maximize the lifetime of devices. To minimize energy consumption, most of approaches try to choose the most suitable components according to their CPU and energy consumption. Actually, network communications on mobile devices consume 90% more energy than data processing [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF]. Energy consumption is closely linked with network distribution. Our approach does not limit lifetime management with optimizing resources consumption. We also try to optimize network balancing. We propose a two dimensional QoS model allowing optimizing utility and durability of an application.

Utility

Utility is represented as a classification of configurations. Each configuration has a mark first determined by the designer. This classification changes according to the context. Usage constraints correspond to rules, which change the utility of a set of configurations. For example, when sound is higher than 70dB, we avoid providing the sound features so that the user does not support noise disturbance. This kind of constraint is translated as an Event-Condition-Action rule:

If (sound > 70) throws beginConference

Event: [ beginConference, sound, « -», 0.2 ]
We associate an event to a feature (sound, video, etc.), an operator to increase or decrease the utility mark and a coefficient. In our example, we decrease the utility of a configuration providing sound when beginConference event occurs. Such a rule can change the classification placing concerned configuration in a bottom position.

Durability

As utility functions minimize impact of several factors in systems [START_REF] Alia | A utility-based adaptivity model for mobile applications[END_REF], we use two functions to evaluate durability of an application. The first one aims at minimizing the impact of the resources consumption when deploying components on devices. Then, the second one aims at minimizing the network balancing of a deployment.

Durability depending on the resources consumption. Each component and device is represented with a 3-uple: consumption/availability of CPU (C), memory (M) and energy. Each value is expressed in percentage between 0 and 1. A component consumes no energy (CPU or memory), 0, or 100% energy of a device, 1. When a configuration is deployed, we calculate the influence of each component supported by a device (component C on device H (1)).

(C on H) = (C H -C C ,M H -M C ,E H -E C ) .
(1)

However, we have to distinguish components that seem equivalent. For example, A(0.5, 0.2, 0.2), B(0.2, 0.5, 0.2) and C(0.2, 0.1, 0.6). If we calculate the average of the three values, we obtain 0.3 for all these components. If we deploy A on a device P, A will consume much energy and P will be rapidly out of order. B consumes much memory and P will not be able to support other component anymore. C consumes much CPU, which can slow computation. To resume, the discriminatory factor relates to the deployment impact of a component on a device and we use the min of the three values as the durability of deploying C. We name this equation QoS_RC:

.

(

) 2
If we deploy several components on a device, we add all the values of components and we finally calculate the durability of a configuration: .

(

) 3
This method to calculate QoS is not optimal because we choose a configuration that consumes little energy on two devices instead of choosing a configuration that consumes much energy on one device. This method exhausts devices little by little instead of completely exhausts devices one by one. Nevertheless, our goal is to maximize the lifetime of devices, so we want to avoid breaking up a device.

Durability depending on the network consumption. We calculate the durability depending on network consumption (QoS_NC) with a similar method than QoS_RC. For a particular deployment, we know each device supporting each component and we know all network links between components.

In a previous work, we propose a design method describing each component and device in an ID card [START_REF] Louberry | QoS Based Design Process for Pervasive Computing Applications[END_REF]. In these ID cards, a device knows the theoretical bandwidth (BWTh) of every networks it can reach (Wi-Fi, Bluetooth, Zigbee, etc.). In our applications, software components and data flows are encapsulated into containers (called Osagaia for software components and Korrontea for data flow containers). They are composed of three entities, Input Unit, Output Unit and Control Unit, which are the main information source for the platform. When a unit detects an evolution of its context, it raises an event informing the platform and the platform can query information from containers (section 5). According to the Korrontea container, we can monitor the bandwidth of connectors during execution and calculate the average bandwidth of a connection between two devices. Then we can calculate the available bandwidth between two devices, H1 ad H2:

. ( 4
)
Finally, ID cards of components indicate the output bandwidth that a component produces. So, we can apply a simple method to know the output bandwidth of a device is to sum the output bandwidth of every component it supports: .

(5)

QoS evaluation

We can represent applications as configuration graphs [START_REF] Laplace | Kalinahia: Considering quality of service to design and execute distributed multimedia applications[END_REF] where one application can be realized by one or several configurations with different QoS. For each application, configurations are classified according their decreasing utility. The Utility QoS is first determined by the designer depending on the application domain. Then the usage context defines some rules modifying the configurations QoS. For example, when sound level is higher than 70dB, we propose to avoid configuration providing sound. Hence, we apply a coefficient, which reduces QoS of such configuration, consequently, classification is modified. This classification is the base for QoS evaluation. We represent the QoS of a configuration (and its deployments) in a two dimensional diagram where X-axis represents the Utility and Y-axis represents the Durability. We place Utility and Durability thresholds, which define a set of reliable configurations (fig. 3). Such thresholds can be modified during execution in order to enlarge this set and achieve a deployment. We study each configuration of the classification from top to bottom and calculate durability of their deployments. While the QoS of a deployment is outside the boundaries, we test another deployment or configuration until a deployment meets QoS requirements. If there are two reliable deployments as in figure 2, we take the one with the best QoS.

The following paragraph presents Kalimucho, a reconfiguration platform that implements this QoS model through a heuristic for contextual deployment.

In this article, we choose to address QoS management in mobile and constraint systems by dynamic reconfiguration of applications. Hence, we use component-based applications, which provide flexibility and modularity. They are based on a component model, Osagaia and a connector model, Korrontea [START_REF] Bouix | The korrontea data modeling[END_REF]. These models encapsulate each component and connector in a suitable container, which allows to monitor context (activity, QoS, delay, etc.) and to control component/connector life cycle (start, stop, connection, disconnection, migration). These containers can be controlled through a control unit that is an interface with the platform. So, we can act directly on components and connectors to reconfigure applications.

To provide such quality in mobile applications, we propose a distributed QoSaware platform: Kalimucho (https://kalimucho.dev.java.net/). Kalimucho consists in five collaborating services, distributed to all devices supporting the application in order to have a global knowledge of the system. This platform is able to trigger the context changes and to modify the structure and the deployment of the application using five basic actions: add, remove, connect, disconnect and migrate component/connector. This set of five services allows Kalimucho ensuring the four following objectives: (1) it must first be able to capture the context. Events can come from the application or the platform itself. It must have mechanisms to capture these events, interpret them and take the appropriate decision to adapt the application. These mechanisms correspond to the application monitoring and are provided by the Supervisor service. (2) When the reconfiguration decision is taken, the platform must be able to propose a reliable deployment. So it must know all the software components and devices available and test whether a deployment meets the QoS requirements. It is carried by the Reconfiguration Builder service. (3) The reconfiguration involves moving, adding and removing components. To maintain an effective application, we must ensure the reliability of the network connections between devices supporting the application. Kalimucho therefore needs a service to maintain the network topology of the application. This is the Routing service. (4) Finally, our applications can be used with any device. All devices do not have the same hardware and software resources. We must manage this heterogeneity between devices. Components must be able to run on any device. We use a component model where each component/connector is encapsulated in a container suited to the device, which free it of all non-functional properties. Lifetime of containers is limited to the use of the component. They are created when the component is installed and destroyed when the component is removed. The container must then be adapted to the device. The platform needs a service able to create specific containers depending on the component and the device. This is the Container Factory and the Connector Factory.

Depending on events, Kalimucho provides two reconfiguration processes. First, it can migrate a service: it tries to differently deploy the components of the current service. Secondly, it can deploy a new configuration of a service: it evaluates a set of configurations respecting utility and tries to find a deployment respecting durability. To find such a deployment, it implements a heuristic for contextual deployment.

Heuristic for contextual deployment

This heuristic aims at finding a configuration and its deployment meeting the context constraints and the QoS criteria: Utility and Durability. This heuristic is composed of two parts. The first one evaluates the utility criterion whereas the second one searches for a deployment optimizing durability. It plays the following scenario: For each configuration where the utility is between 1 and the utility threshold, our heuristic searches for a deployment. This deployment has to ensure durability between 1 and the durability threshold.

To limit the energy consumption, we propose to minimize the number of network links. Since there are location dependencies for some components, we try to group them on imposed devices. When they cannot support component anymore, we try to place component on a device located on paths between imposed devices (Fig. 5). This solution is based on a device ranking (table 1), which is itself based on two concepts: component weight and device weight. We can represent configuration as an oriented graph (fig. 4(a)). Then we define paths between components that are fixed with particular devices (location dependence). We define the weight of a component as its minimal rank in such path. It is the minimal distance from the component to a fixed-component. Fixed-components are always set to rank 0. We apply the same definition to define the weight of a device but network is represented as a nonoriented graph (bidirectional paths).

From this ranking, we try to deploy each configuration until one meets QoS requirements. In order to find rapidly a deployment, we improve the initial ranking of devices with other criteria: type of a component, energy, CPU and memory: -Type of component: This ranking aims at using a maximum of non-limited devices. So, we distinguish 3 types of devices: Fixed, CDC1 and CLDC, according to Sun Microsystems's J2ME standard classification. CLDC devices are the most limited such as mobile phones and wireless sensors.

-Energy: Energy available on devices is an important criterion because it directly addresses the durability of devices and consequently the durability of the application. It may imply more reconfigurations than CPU or memory-use changes.

-CPU: CPU workload is a less important criterion than energy. However, a high workload can slow the computing of components.

-Memory: Memory availability has no impact on the durability of the application at this moment. It will impact when we would add component on a device. According to this ranking, the heuristic uses a recursive approach to calculate a deployment for each component: 1.

We rank components, in a list CL, according their impact.

2.

We select the first component where impact == 1 a. If it does not exist, it means that all components have been placed.

3.

We rank devices, in a list DL, according the criteria of table 1. 4.

We calculate the impact of placing this component on the first device of DL. a. If (QoS_RC >= QoS_RC threshold) then we place the component on this device and we invoke the recursive heuristic since step 1. If the placement refers to the last component of CL, we can calculate the QoS_NC of the deployment. b. If (QoS_RC < QoS_RC threshold) then we go back to step 4 with the next device in DL if there is one. Else, this recursive call fails and implies a new calculus to place again the previous component. In case of failure, we can update the QoS threshold in order to select new configurations, which can provide a deployment meeting QoS requirements. If the QoS threshold update cannot provide such a deployment and the heuristic has tested all the configurations, it means that the application cannot be adapted.

As an example, we try to deploy the "Text" configuration represented in figure 4(a) on the network represented in figure 4(b). The "Text" configuration is composed of 8 components, C1 to C8. Location dependences have been defined: C1 is placed on H1, C5 and C6 are placed on H2 and C8 is placed on H3. The result of the heuristic in figure 5 confirms that the components are grouped on the devices already used in order to limit the number of networks links and the energy consumption.

Experimentations

We developed a prototype of Kalimucho running on a netbook, a PDA and two SunSPOT platforms. This implementation of Kalimucho can deploy and reconfigure components-based applications using batch files. It can also capture contextual elements necessary for decision-making. The Supervisor service relates, as an alarm, the context changes and the user requests to adapt the application. To do so, the Supervisor service is able to monitor the state of a device (memory, CPU, battery), to monitor the state of a component or a connector (QoS, activity, connections, etc.) and to relay statements to other distributed platforms. The Reconfiguration Builder service is able to create or remove components/connectors, migrate components, connect or disconnect a component input and delete or duplicate component output and send commands to other platforms.

Kalimucho is distributed on all devices supporting the application. We implement specific versions according to the type of device. Thus we find in our prototype: -Kalimucho for fixed devices such as PCs and laptops (about 260Ko); -CDC Kalimucho for devices such as smart phone (about 356Ko); -Kalimucho for CLDC devices such as sensors Sun Spot (about 169Ko). We also implemented an Android version. Finally, the devices do not use the same network, so we have to provide tools to relay information through the several networks. In our prototype, the PC and the Android phone use Wi-Fi although SunSpots use Zigbee. To enable the Sunspots to communicate with others devices, a base-station plugged into the PC runs as a gateway. We propose a scenario that where we can use the five actions providing by the platform and measure execution time of these actions. This is an application displaying the angle captured by a SunSpot. This application is initially composed of 3 components: capture, processing and display (Figure 6). The Supervisor service of Kalimucho captures the activity of components and connectors, the QoS and the resources of devices (CPU, energy, memory). First, we replace the processing component to reverse display [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF]. Then, we add a new component on the PC to choose color display [START_REF] Alia | A utility-based adaptivity model for mobile applications[END_REF]. We migrate the color component on the smart phone (3). We have to care about the network links. Hence, the smart phone has to share information with a SunSpot through the PC (gateway). Finally, we reconfigure the application to display on the smart phone too. We duplicate the output from color component to send information to the display components on the SunSpot and the smart phone (4). Table 2 resumes the execution time of all the command we used in this scenario. We can notice that the most execution times are in the order of millisecond, which is acceptable for such limited devices.

Conclusion and future work

Pervasive computing is becoming a reality. Nowadays, people want to use application anywhere with its mobile device. Due to the mobility, people want applications to be adapted according to context changes. This brings new challenges to traditional applications. As said in [START_REF] Zheng | Deployment of Context-Aware Component-Based Applications Based on Middleware[END_REF], applications should be context aware because of limited resources of the devices and the variability of the execution context. Most approaches deal with energy consumption providing planning-based adaptation or contextual deployment. However, these approaches only consider CPU and energy consumption, no one considers network communication cost. So we propose a QoS model allowing to guaranty the utility of an application and to maximize its lifetime. The durability is a fundamental notion with mobile devices because a high quality application is useless if it just runs for a few time. Utility measures the adequacy of the provided application to user needs and application specifications. Durability measures the lifetime of the application according to resources and network consumption. Then we propose Kalimucho, a contextual deployment platform. It implements the QoS model through a recursive heuristic. We test Kalimucho on several platforms such as SunSpot and Android. Execution times of Kalimucho commands, in the order of millisecond show that response time is acceptable for limited devices.

However, it still exist an obvious limit to our approach. Although QoS can be adapted dynamically, it is based on static measure of resources consumption from components. Then, the heuristic to select a deployment only computes the QoS of the service where the reconfiguration event occurred, and not the whole application. When reconfiguring, we offer the possibility to get the best QoS for one service. The reconfiguration of one service does not imply the reconfiguration of another one. But, the modification of the application (its deployment) has consequences on the execution context because it modifies the charge of devices and the network traffic. So, a reconfiguration of one service may induce the raise of events that will trigger new reconfigurations.

Future works focus on the design and test of this configuration choice heuristic. We must specifically work on: -Does the platform have to manage priorities on events in order to manage quicker reaction for some of them? -When an event is managed, do we have to manage those waiting or ignore them? Doing a reconfiguration modify the context and consequently some events produced before this configuration may be obsolete.

-

The QoS model manages utility QoS and durability. The importance between these to criteria depends on the application. For example, a video surveillance application needs to give priority to durability whereas the one presented for museums visits gives priority to utility QoS in order to produce good quality information corresponding to users' demands.

Fig. 1 .

 1 Fig. 1. Visit of a museum application

Fig. 3 .

 3 Fig. 3. QoS evaluation

Fig. 4 .

 4 Fig. 4. (a) Graph of the "Text" configuration. (b) Network Graph

Fig. 5 .

 5 Fig. 5. Result of deploying the "Text" configuration

Fig. 6 .

 6 Fig. 6. Display application

Table 1 .

 1 Ranking of devices.

	Device	H1	H2	H3	A	C	B	D	F	E
	Impact	0	0	0	1	1	1	1	1	2
	Type	Fixed CDC CDC Fixed Fixed CDC CLDC CLDC CLDC
	Energy			0.8				0.2	0.3
	CPU				0.9	0.75
	Memory

Table 2 .

 2 Execution of Kalimucho commands on a SunSpot sensor and a Nexus One mobile phone.

	Command	Execution time in ms
		SunSpot	Android
	Create a component	70 to 170 ms	450 to 750 ms (upload of a
			2kB byte code)
	Delete a component	20 ms minimum	15 ms. Depends on
		Depends on time to end the	component activity
		component
	Create a connector	Internal: 70 to 110 ms	Internal: 3 to 15 ms
		Distributed: 100 to 190 ms on	Distributed: 10 to 100 ms
		device receiving the
		command, 30 to 120 ms on
		the other
	Delete a connector	Internal: 60 to 80 ms	Internal: 3 to 15 ms
		Distributed: 100 to 260 ms on	Distributed: 3 to 25 ms
		device receiving the
		command, 30 to 120 ms on
		the other
	Disconnection or	20 to 60 ms	2 to 7 ms
	reconnection of an input
	Duplication of an output 20 to 80 ms	2 to 7 ms
	Read QoS of a container 80 ms
	Read state of a container 70 to 80 ms
	Read state of a device	70 to 90 ms
	Migrate a component	90 to 230 ms	650 to 750 ms (upload of a
			2kB byte code)

According to Sun Microsystem devices type description