Sonia Ben Mokhtar
email: sonia.benmokhtar@inria.fr

Nikolaos Georgantas
email: nikolaos.georgantas@inria.fr

Valérie Issarny
email: valerie.issarny@inria.fr

Ad Hoc Composition of User Tasks in Pervasive Computing Environments

Due to the large success of wireless networks and portable devices, the pervasive computing paradigm is becoming a reality. One of the most challenging objectives to be achieved in pervasive computing environments is to allow a user to perform a task by composing on the fly the environment's service and resource components. However, existing approaches commonly assume that networked components have been developed to integrate in terms of interfaces and conversations, which restricts the user's ability to fully exploit the diversity of the pervasive computing components. In order to overcome this constraint, we propose a solution for ad hoc composition of pervasive computing components, based on the Web services and Semantic Web paradigms. The main feature of our solution is the ability to integrate on the fly a number of Web services' conversation fragments to reconstruct a conversation enabling the target user task.

Introduction

The paradigm of pervasive computing has opened new perspectives to the enactment of human everyday activities related to accessing information and computation. Pervasive computing enables user-centric retrieval and consumption of information, compared to the conventional computer-centric approach. Systemically, this is realized as a synergistic combination of intelligent human-machine interfaces and ubiquitous computing and networking. The ubiquitous property implies a useful, pleasant and unobtrusive presence of the system everywhere around us.

A pervasive computing environment is populated with networked, both computing and input/output devices providing the environment's components. Within this environment, users perform tasks which integrate the functionalities offered by the environment's components. A pervasive computing environment is characterized by a number of features, such as: (i) the highly dynamic character of the computing and networking environment due to the intense use of the wireless medium and the mobility of users; (ii) the resource constraints of mobile devices, in terms of CPU, memory, storage, display capabilities, battery power and bandwidth; and (iii) the high heterogeneity of integrated technologies in terms of networks, devices and software infrastructures. In such an environment, satisfying the functional requirements of user tasks becomes extremely hard. Specifically, the integration of the environment's components to support a user task shall: (i) be dynamic, according to available components at the specific time and place;

(ii) satisfy the functional requirements in an effective way within the bounds posed by the resource constraints of mobile devices; and (iii) accommodate the heterogeneity of technologies. However, existing approaches assume that pervasive computing components have been developed to integrate. This means that components being integrated shall perfectly match with the task specification in terms of supported interfaces and conversations.

Our aim is to allow a user who carries an abstract task description on his/her device, i.e., a description without any reference to existing component instances, to perform this task by integrating on the fly the environment's components that are available around him/her, without any preliminary knowledge about these components. This is what we call "ad hoc composition of user tasks". This requires building upon an architectural style that deals with the heterogeneity of pervasive computing components.

Service Oriented Architecture (SOA) is an architectural style that offers solutions to the interoperability problem among distributed applications. In the SOA approach, software resources that are available on the network are abstracted as services. These services are described in a declarative manner that is independent from their implementation; they are loosely coupled, and communicate using standard protocols. This architectural style is most convenient to the pervasive computing environment, as it enables homogeneous use of the heterogeneous software components that populate the pervasive computing environments.

Web services is one of the realizations of the SOA architectural style. Web services introduces loosely coupled services that communicate using the standard technologies that made the success of the Web. More precisely, a Web service is a software component that is developed using any programmation language and deployed on any platform, and that is accessible via the Web. It exposes an XML interface that describes its public operations and its access details; this interface is specified using the Web Services Description Language (WSDL) 1 . A Web service communicates using the Simple Object Access Protocol (SOAP)2 on top of Internet protocols (HTTP, SMTP). Furthermore, Web services have already been used in pervasive computing environments [START_REF] Issarny | Developing ambient intelligence systems: A solution based on web services[END_REF] and have proved to be efficient when deployed on mobile, resource-constrained devices. All these features make Web services an excellent candidate to support application-level interoperability in pervasive computing environments. Thus, by representing each pervasive computing component as a Web service, the problem of dynamic integration of components can be treated as a problem of dynamic composition of Web services.

Dynamic composition of Web services involves automating the discovery and selection of services, ensuring semantic and data-type compatibility [START_REF] Majithia | A framework for automated service composition in service-oriented architecture[END_REF], but also automating service invocation. The automation of service discovery and selection can be achieved only if service descriptions are machine-interpretable. A key issue is that the two main standards for describing and publishing Web services (WSDL and UDDI 3 ) are mainly syntactic. Thus, to discover and select services a strong matching (i.e. a syntactic comparison) have to be made between the required functionalities and the ad-vertised ones. The semantic representation of service descriptions' content will allow machines to understand and process this content, and to support dynamic discovery and integration. Thus, a number of research efforts have been made to apply to Web services the solutions that have been proposed by the Semantic Web community for semantically annotating Web pages. This leads the emergence of semantic Web services. In this area, Ontology Web Language for Services (OWL-S) 4 is one of the most promising languages for describing semantic Web services.

On the other hand, the automation of service invocation involves the use of conversation languages (e.g., WSCI [START_REF] Wsci | Web Service Choreography Interface (WSCI) 1.0. BEA Systems, Intalio[END_REF], WS-CDL [START_REF] Ws-Cdl | Web Services Choreography Description Language Version 1.0. W3C[END_REF], WSCL [START_REF] Wscl | Web Services Conversation Language (WSCL)[END_REF]) to describe the external behavior of the service rather than describing only the service operations as supported by WSDL. This conversation description prescribes how to interact with the service so that it behaves in a specific desired manner.

Our work presented in this paper is a part of the effort of the IST Amigo project 5 that investigates solutions to realize the full potential of home networking to improve people's lives. In this paper, we present a solution to the ad hoc composition of user tasks from available pervasive computing components. Both the user task and the environment's components are represented as semantic Web services described using OWL-S. The main feature of OWL-S that we exploit, is the ability to describe semantic conversations. More precisely, OWL-S allows the description of the external behavior of a Web service by using a semantic model, in which each operation involved is described semantically in terms of inputs/outputs. The difference between the user task description and the environments' services descriptions, is that the task description is abstract and does not contain any concrete reference to existing Web services.

Our solution introduces a matching algorithm that attempts to reconstruct the abstract task process description by integrating fragments from the environments' services process descriptions. The result obtained is a concrete task description that contains references to available environments' services and that is executable by invoking those services.

The remainder of the paper is structured as follows. First, we present the general context of our work (Section 2). We then present our approach to the ad hoc composition of Web services (Section 3). Further, we review related research efforts in the area of matching algorithms (Section 4). Finally, we conclude with a summary of our contribution and discuss our future work (Section 5).

Background

Service Description

Web services can be described using three description levels that are : (i) the interfacelevel; (ii) the process-level; and (iii) the binding-level. The interface-level description contains the signatures of the service operations. The process-level description is the specification of the external behavior of the service, which is also called the service's conversation. Finally, the binding-level description contains the low level information necessary to communicate with the service, including protocols, addressing and message formats.

WSDL describes services using the interface-level description and the binding-level description. While these two levels are sufficient when the service has a simple behavior (i.e., invocation of a single operation), it remains insufficient when the service has a complex behavior. In this case, the key issue is that we do not have any indication about when and which service operations have to be invoked in order to lead the service to behave as we want. Moreover, for dynamic service invocation, this has to be automated. Thus, by having a conversation description, a requester dynamically can derive the sequence of information to exchange with the service, which in turn correspond to the interaction protocol of the service [START_REF] Sycara | Automated discovery, interaction and composition of semantic web services[END_REF]. This is what makes the process-level description an important requirement to achieve dynamic service composition.

Semantic Web Services

Semantic Web services is a research area at the intersection of two important research domains that concern Web technologies : the Semantic Web and Web services. The Semantic Web aims at describing the static information provided by Web pages in a nonambiguous manner, in order to allow machines to understand and process their content [START_REF] Berners-Lee | The semantic web[END_REF]. Web services standards, such as WSDL and UDDI, use XML structures to describe Web services functionalities and their exchanged data. However, these structures are syntactic which makes it impossible for a machine to automatically understand Web services descriptions. A semantic Web service is then a Web service described using a well defined semantic language, which provides the service with a non-ambiguous interface, facilitating the automation of certain tasks, such as discovery, invocation and composition.

There are two main approaches to semantically describe Web services. The first approach adds semantics on top of WSDL. The second approach uses ontologies 6 that have been developed specifically to describe Web services.

A number of research efforts have been undertaken in order to bring semantics to WSDL [START_REF] Aggarwaland | Dynamic web service composition in meteor-s[END_REF][START_REF] Eberhart | Ad-hoc of invocation semantic web services[END_REF][START_REF] Heß | Machine learning for annotating semantic web services[END_REF][START_REF] Sivashanmugam | Adding semantics to web services standards[END_REF]1]. These introduce different models to semantically annotate WSDL descriptions, and some of them propose solutions for mapping XSD structures to ontologies and/or classify services into categories. However, as they are build upon WSDL, these models lack in describing Web services' conversation, which is an important requirement to achieve dynamic service composition.

OWL-S

OWL-S (previously DAML-S), is a Web service ontology based on the Ontology Web Language (OWL) 7 , used to describe Web services properties and capabilities. Using OWL-S a service description is composed of three parts : the service profile, the process model and the service grounding.

The benefit of using OWL-S rather than another approach to semantically describe Web services is that OWL-S offers a generic model to describe Web services. This model is easily extensible and allows the different levels of service description that we have identified earlier. Furthermore, OWL-S brings semantics to the conversation description, and thus allows flexible conversation matching.

OWL-S Service Profile. The service profile gives a high level description of a service and its provider. It is generally used for service publication and discovery. The service profile is composed of three parts: (i) an informal description of the service oriented to a human user; (ii) a description of the service's capabilities, in terms of Inputs, Outputs, Pre-conditions and Effects (IOPE); and (iii) a set of attributes describing complementary information about the service.

OWL-S Process Model.

The process model is a representation of the external behavior of the service as a process. This description contains a specification of a set of sub-processes that are coordinated by a set of control constructs (e.g., Sequence or Parallel constructs); these sub-processes are atomic or composite. The atomic processes correspond to WSDL operations. The composite processes are decomposable into other atomic or composite processes by using a control construct.

OWL-S Service Grounding.

The service grounding specifies the information that is necessary for the service invocation, such as the protocol, message formats, serialization, transport and addressing information. It is a mapping between the abstract description of the service and the concrete information necessary to interact with the service. The OWL-S service grounding is based on WSDL.

Ad Hoc Composition of Semantic Web Services

Ad hoc composition of Web services translates into the integration on the fly of a set of services to perform a user task. Our objective is to allow a user entering into a pervasive computing environment, in which services and resources publish an OWL-S description, to perform a task. A description of this task is available on the user's device as an abstract OWL-S conversation. In order to select the set of services that are suitable to be integrated to perform the user's task, and to integrate this set of services, a matching algorithm is needed. In our approach, we propose a matching algorithm that enables reconstructing the task's conversation using fragments from the conversations of the environment's services. Towards this goal, we first introduce formal modeling of the conversations of both the environment's services and the task as finite state processes (FSP). Other approaches for formalizing Web services conversation and composition have been proposed in the literature, generally based on process algebras (e.g. π-calculus, CCS) [START_REF] Issarny | Specifying web services recovery support with conversations[END_REF][START_REF] Koshkina | Verification of business processes for web services[END_REF][START_REF] Brogi | Formalizing web services choreographies[END_REF], or Petri nets [START_REF] Van Der Aalst | Yawl: Yet another workflow language[END_REF][START_REF] Rachid | A petri net-based model for web service composition[END_REF][START_REF] Narayanan | Simulation, verification and automated composition of web services[END_REF]. FSP is generally used as a textual notation for concisely describing and reasoning about concurrent programs, such as workflows of Web service compositions [START_REF] Foster | Model-based verification of web service compositions[END_REF]. These processes can be represented graphically using finite state automata.

In the following, we describe our dynamic composition approach. First, we present the notion of abstract task (Section 3.1). Then, we present our model to map OWL-S conversations to finite state automata (Section 3.2). Finally, we describe our matching algorithm (Section 3.3).

Abstract Task Description

While Web services of the pervasive computing environment are described as OWL-S processes with a WSDL grounding, the user task is described as an abstract OWL-S process without any reference to existing services. An abstract OWL-S process involves abstract atomic and composite processes.

An abstract atomic process is defined as an elementary entity that has a set of inputs/outputs. Those inputs/outputs are specified with logical names. They carry semantic definitions, and have to be matched to inputs/outputs of a concrete OWL-S atomic process contained in the description of an environment's service. An abstract composite process is composed of a set of abstract, either composite or atomic, processes, and uses a control construct from those offered by the OWL-S process model. These control constructs are: Sequence, Split, Split + Join, Choice, Unordered, If-Then-Else, Repeat-While, and Repeat-Until.

In addition to the description of the task's conversation, we allow the definition of a set of atomic conversations, that are fragments of the task conversation that must be executed by a single Web service.

Modeling OWL-S Processes as Finite State Automata

Formally, an automaton is represented by the 5-tuple < Q, , δ, S 0 , F > [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF], where:

-Q is a finite set of states.

is a finite set of symbols that define the alphabet of the language the automaton accepts. is the empty symbol.

δ is the transition function, that is δ : Q × → Q -S 0 is the start state, that is, the state in which the automaton is when no input has been processed yet (Obviously, S 0 ∈ Q). -F a subset of Q (i.e. F ⊂ Q), called final states.

In our modeling approach, the symbols correspond to the atomic processes involved in the conversation. The initial state corresponds to the root composite process, and a transition between two states is performed when an atomic process is executed.

Each process, either atomic or composite, that is involved in the OWL-S conversation, is mapped to an automaton and linked together with the other ones in order to build the conversation automaton. This is achieved following the OWL-S process description and the mapping rules shown in Figure 1. In this Figure we can see that an atomic process ap is modeled as an automaton < Q, , δ, S 0 , F >, where :

-Q = {S 0 , S 1 } ; - = {ap} ; -δ(S 0 , ap) = S 1 ; -S 0 is the start state ; -F = {S 1 }.
A composite process C that involves a set of processes P 1 , P 2 , ..., P n ,represented by the automata < Q1, 1 , δ1, S0,1, F1 >, < Q2, 2 , δ2, S0,2, F2 >, ..., < Qn, n , δn, S0,n, Fn >, respectively, is represented by the automaton < Q, , δ, S 0 , F > according to the control construct it uses, as follows.

-If C=Repeat-While(P 1 )8

• Q = Q 1 ; • = 1 ; • δ : Q 1 × 1 → Q 1 (x, y) → δ(x, y) = δ 1 (x, y)when(x, y) ∈ Q 1 × 1 and δ(x, y) = S 0 when x ∈ F 1 and y = ; • S 0 = S 0,1 ; • F = F 1 ∪ {S 0 }.
-If C=Choice(P 1 , P 2 , ..., P n ), then:

• Q = ( Q i ) ∪ S Init (S Init is a new start state); • = i ; • δ : (Q i × i ) → Q i (x, y) → δ(x, y) = δ i (x, y)when(x, y) ∈ Q i × i and δ(x, y) = S 0,i when x = S Init and y = ; • S 0 = S Init ; • F = F i . -If C=Sequence(P 1 , P 2 , ..., P n ) then: • Q = Q i ; • = i ; • δ : (Q i × i ) → Q i (x, y) → δ(x, y) = δ i (x, y)when(x, y) ∈ Q i × i and δ(x, y) = S 0,i+1 when x ∈ F i (i = n)and y = ; • S 0 = S 0,1 ; • F = F n .
-If C= Split(P 1 , P 2 ) then C is treated as Choice(Sequence(P 1 , P 2 ), Sequence (P 2 , P 1 )), as we process parallelism as non determinism. The Split+Join and the Unordered constructs are treated as the Split construct. -If C=If-Then-Else(P 1 , P 2 ) then C is treated as Choice(P 1 , P 2 ).

The conditions involved in the constructs Repeat-While, Repeat-Until and If-Then-Else are not visible in our automata model. However, these conditions will be taken into consideration during the matching process. The OWL class Condition that defines those conditions, is actually a placeholder for further work, and will be defined as a class of logical expressions. Thus, we consider that during our matching algorithm a comparison between those logical expression will be made. More information about this comparison will be given in future work.

Matching Algorithm

One of the most important features of a dynamic service composition approach is the matching algorithm being used. Following the definition given by Trastour et al. in [START_REF] Trastour | A semantic web approach to service description for matchmaking of services[END_REF], the matching is the process by which parties that are interested in having exchange of economic value are put in contact with potential counterparts. The matching process is carried out by matching together features that are required by one party and provided by another. Thus, the matching allows the selection of the most suitable services to respond to the users' requirements. In our approach, matching depends on two important features : (i) the services' advertisements; and (ii) the task's description. A service advertisement is composed of the information published by the service provider. This description could be quite simple, for example, a set of keywords describing the service, or more complex, describing for example the service's operations, conversation, functional and non-functional capabilities. This description could further be syntactic (by using XML-based standards for Web services' description) or semantic (by using semantic Web languages). In our approach, services are advertised by means of their provided behavior, i.e., conversation, while the user task is described by the behavior it requires from services.

The matching algorithm we propose aims at reconstructing the task's behavior by using fragments of the services behaviors. This algorithm is performed in two steps: (i) semantic operation matching, and (ii) conversation matching, which are detailed bellow. Semantic operation matching aims at selecting a set of services that may be integrated to compose the target task. Our selection criterion is the provision by the service of at least one semantically equivalent operation from those that are involved in the task. Conversation matching then compares the structure of the task's conversation with those of selected services and attempts to compose fragments from the services' conversations to reconstruct the task's conversation.

Semantic Operation Matching. The objective of the semantic matching step is to compare semantically described operations involved in the task's conversation with those involved in the services' conversations. This kind of matching is more powerful and more flexible than syntactic matching, as it allows the use of inference rules enabled by ontologies to compare elements, rather than comparing syntactically their names.

To perform semantic operation matching, we build upon the matching algorithm proposed by Paolucci et al. in [START_REF] Paolucci | Semantic matching of Web services capabilities[END_REF][START_REF] Sycara | Automated discovery, interaction and composition of semantic web services[END_REF]. This algorithm is used to match a requested service with a set of advertised ones. The requested service has a set of provided inputs in Req , and a set of expected outputs out Req , whereas each advertised service has a set of expected inputs in Ad and a set of provided outputs out Ad . In our case, we propose to use this matching algorithm to compare atomic processes, i.e., operations, rather that high-level Web services' capabilities. This matching algorithm defines four levels of matching.

-Exact : if out Req = out Ad or out Req is a direct subclass of out Ad -Plug in : if out Ad subsumes 9 out Req , in other words, out Ad could be used in the place of out Req -Subsumes : if out Req subsumes out Ad , in this case, the service does not completely fulfill the request. Thus, another service may be needed to satisfy the rest of the expected data. -Fail : failure occurs when no subsumption relation between advertisement and request is identified.

This matching algorithm also applies between the inputs of the request and the inputs of the advertisement. A match between an advertisement and a request is recognized when all outputs of the request are matched against all outputs of the advertisement; and all the inputs of the advertisement are matched against all the inputs of the request. Furthermore, we propose to use the two first levels of matching : Exact and Plug in matches, as we consider that a subsumes match cannot guarantee that the required functionality will be provided by the advertised service [START_REF] Majithia | A framework for automated service composition in service-oriented architecture[END_REF]. Furthermore, as we match operations we don't want to split them between two or more services.

The matching process we are building upon is a complex mechanism that may lead to costly computations. However, the algorithm uses a set of strategies that rapidly prune advertisements that are guaranteed not to match the request [START_REF] Paolucci | Semantic matching of Web services capabilities[END_REF]. For example, if one of the out Req cannot be matched by any of the out Ad the match directly fails. Furthermore, the fact that we use only the first two levels of matching considerably reduces the cost of the matching.

The main logic of our semantic operation matching algorithm is that Process model descriptions of services are parsed, and once all inputs/outputs of a task's operation are matched against all inputs/outputs of a service's operation the service is recorded. More precisely, all the operations of this service that are semantically equivalent to task's operations are recorded. This allows the selection of a set of services that offer semantically equivalent operations with those of the user's task. The conversations offered by those selected services are then used to reconstruct the task's conversation.

Conversation Matching. The objective of the conversation matching is to compare the structure of the task's process with the structure of the selected services processes, in terms of control constructs involved. In this algorithm, we use the automaton model describing each service that has been selected and the one describing the user task. The first step is to connect the selected services' automata to form a global automaton. This is achieved by adding a new initial state and an -transition from this state to each of the initial states of the selected services. Other -transitions are also added to link each final state of the selected services with the new initial state.

Fig. 2. Main logic of the conversation matching algorithm

The next step of our conversation matching algorithm is to parse each state of the task's automaton by starting with the initial state and following the automaton transitions. Simultaneously, a parsing of the global automaton is done in order to find at each step of the parsing process, an equivalent state to the current one in the task. An equivalence is detected between a task's automaton state and a global automaton state, when for each input symbol of the former there is at least a semantically equivalent input symbol10 of the latter. Each state of the task's automaton is parsed just once. We have implemented this algorithm in a recursive form. This algorithm checks whether we can find a sub-automaton in the global automaton that behaves like the task's automaton. The main logic of this algorithm is described in Figure 2.This algorithm gives a list of sub-automata of the global automaton that behave like the task automaton. Figure 3 shows an example of the conversation matching algorithm. In this figure the abstract task automaton (on the left higher corner) that involves the operations op1, op2, op3 and op4 is going to be matched against the global automaton (on the right) which connects together the automata of the services S1, S2, S3, S4 and S5. The operations involved in the task have already been matched semantically against the services' operations during the semantic operation matching step. Thus, in the global automaton we have just represented a selected set of operations that are semantically equivalent to the task's operations. After browsing simultaneously the two automata as specified in the algorithm, the sub-automaton of the global automaton represented in the left lower corner of the figure is found. This automaton behaves exactly as the task's automaton. Once the list of sub-automata that behave like the task automaton is produced, a last step consist in checking whether the atomic conversation constraints, have been respected in each sub-automaton. As the global automaton is modeled as a union of the selected services automata, it is easy to check whether an atomic conversation fragment, that is, a set of transitions, is provided by a single service. Indeed, it is sufficient to verify that for each transition set that corresponds to an atomic conversation there is no -transition going to the initial state before this conversation is finished. -transitions that connect final states to the initial state of the global automaton mark the end of a service conversation and the passing to a new one. After rejecting those sub-automata that don't verify the atomic conversation constraints, we select arbitrarily one of the remainders, as they all behave as the user task. Using the sub automaton that has been selected, an executable description of the user task that includes references to existing environment's services is generated, and sent to an execution engine that executes this description by invoking the appropriate service operations.

An example: a video application In this section we show a simple example of how our matching algorithm could be used to match conversations. This example is inspired from one of the Amigo's scenarios.

"...Robert, (Maria's and Jerry's son) is waiting for his best friend to play video games. Robert's friend arrives bringing his new portable DVD player. He proposes to watch a film rather than playing games, and asks Robert if he has any new films in his home databases. In order to use his friend's DVD player, Robert has asked the system to consider this device as a guest device and to authorize it to use the home's services. This player is quite complex as it takes into consideration some user's contextual and access rights information. The former is used to display the video streams according to the user's physical environment and preferences (for example by adapting the luminosity and the sound volume), while the latter is used to check whether the user is authorized to visualize a specific stream (for example some violent films may be unsuitable for children)..."

This DVD player contains a video application that uses Web ontologies to describe its offered and required capabilities. The conversation that is published by this application is depicted in figure 4 (left higher corner). This conversation is described as an OWL-S process that contains concrete offered operations (uncolored) and abstract required operations (in gray) that have to be bound to environment's operations. On the other hand Robert's home environment contains a number of services among which a Digital Resource Database service and a Context manager service; both publish OWL-S conversations as shown in the same figure (on the right and left lower corner respectively).

At execution time this device will discover the missing abstract conversation fragment involved in its description. The semantic operation matching step will allow the selection of the two previous services as they contain operations that match the operations of the video application. For example, using the ontology fragment described in figure 5 the operation GetFilm of the video application will be matched against the operation GetDigitalResource of the Digital Resource Database service. More precisely, an exact match is recognized between the output of both operations as they are both instances of the concept Stream. On the other hand, a Plug In match is recognized between the inputs of both operations as the concept DigitalResource subsumes the concept VideoResource. The second step of the matching algorithm is the conversation matching. In this step our algorithm attempts to reconstruct the abstract conversation of the video application by using the conversations of the selected services. The selected fragments after matching are shown in figure 4.

Related Work on Matching Algorithms

We can classify the related work on service matching algorithms in two categories: interface-level matching algorithms and process-level matching algorithms. In the first category of matching algorithms, services are generally advertised as a set of provided outputs and required inputs. These inputs/outputs constitute the service's interface. On the other hand, the request is specified as a set of required outputs and provided inputs. A match between an advertisement and a request consists in matching all outputs of the request against all outputs of the advertisement and all inputs of the advertisement against all inputs of the request. An approach for matching semantic Web services at the interface level has been proposed by Paolucci et al. in [START_REF] Paolucci | Semantic matching of Web services capabilities[END_REF][START_REF] Sycara | Automated discovery, interaction and composition of semantic web services[END_REF]. We have employed this algorithm to semantically match operations as described in Section 3.3. This algorithm is one of the most used approaches in the literature. Because of its simplicity and efficiency, a number of research efforts such as [START_REF] Pereira Filho | Web service architectures -semantics and contextawareness issues in web services platforms[END_REF][START_REF] Majithia | A framework for automated service composition in service-oriented architecture[END_REF][START_REF] Trastour | A semantic web approach to service description for matchmaking of services[END_REF][START_REF] Javier | Description logics for matchmaking of services[END_REF][START_REF] Guizzardi | Using ontologies for modeling context-aware service platforms[END_REF], have elaborated matching algorithms that are mainly based on this algorithm. In the second category of matching a process, there is no process integration effort. Thus, the authors implicitly assume that the user's request is quite simple and can be performed by a single process. On the contrary, in our approach a composition effort is made to reconstruct a complex task process by integrating the services' processes.

Aggarwal et al. in [START_REF] Aggarwaland | Dynamic web service composition in meteor-s[END_REF] propose to describe a task as a BPEL4WS [START_REF]BPEL4WS. Business Process Execution Language for Web Services (BPEL4WS) 1[END_REF] process. This description may contain both references to known services (static links) and abstract descriptions of services to be integrated (service templates). At execution time, services that correspond to the service templates are discovered and the task is carried out by invoking the services following the process workflow. This approach proposes a composition scheme by integrating a set of services to reconstruct a task's process. However, the services being integrated are rather simple. Indeed, each service is described using a semantic model defined by the authors, which specifies the high-level functional and non-functional capabilities of the service, without describing its external behavior (conversation). On the contrary, we consider services as entities that can behave in a complex manner, and we try to compose these services to realize the user task.

Another process-level matching algorithm is proposed by Majithia et al. in [START_REF] Majithia | A framework for automated service composition in service-oriented architecture[END_REF]. In this approach, the user's request is specified in a high-level manner and automatically mapped to an abstract workflow. Then, service instances that matches the ones described in the abstract workflow, in terms on inputs outputs pre-conditions and effects, are discovered in the network, and a concrete workflow description is constituted. As we have noticed in the previous approach, the service composition scheme that is proposed in this approach does not involve any process integration, as the Web services are only described at the interface level.

Conclusion

In the pervasive computing vision the user has a central position. This vision involves that everywhere around us, the environment is populated with networked, both computing and input/output devices that provide the environment's components. Our objective has been to allow a user entering to a pervasive computing environment to perform a task, abstractly described on his/her device, by integrating on the fly the environment's components. A key feature of pervasive computing components is their heterogeneity. Most existing solutions poorly deal with heterogeneity since they assume that components being integrated have been developed to conform syntactically in terms of interfaces and conversations.

Our solution building on semantic Web services offers much more flexibility by enabling semantic matching of interfaces and ad hoc reconstruction of the user task's conversation from service's conversations. Our solution is achieved in two steps. In the first step, we perform a semantic matching of interfaces that leads to the selection of the set of services that may be useful during the integration. In the second step, we perform a conversation matching starting from the set of previously selected services, thus obtaining a conversation composition that behaves as the task's conversation. Our matching is based on a mapping of OWL-S conversations to finite state automata. This mapping facilitates the conversation integration process, as it transform this problem to an automaton equivalence issue.

The main feature of our solution is the ability to compose Web services that expose complex behaviors to realize a user's task that itself has a complex behavior. Existing approaches in process-level matching generally consider either that the services or the task have a simple behavior, thus leading to simple integration solutions. In our case, we assume complex behaviors for both services and task and we propose a matching algorithm that attempts to reconstruct the task's behavior using fragments of the services behaviors. In order to deal with such a high level of dynamicity our solution uses some costly mechanisms such as semantic reasoning. Thus, we intend to implement our approach and to evaluate it in terms of efficiency and performance. We have already implemented the conversation matching algorithm based on automata analysis; the next step is to augment this algorithm with the semantic matching.

Fig. 1 .

 1 Fig. 1. Modeling OWL-S processes as finite state automata

Fig. 3 .

 3 Fig. 3. An example of the conversation matching

Check(TaskState, EnvState){ if(TaskState is a final state and EnvState is a final state) success; else{ if(EnvState.followingSymbols don't include TaskState.followingSymbols ) fail; else{ forall Symbol in TaskState.followingSymbols, state1 in EnvState.nextState(Symbol), state2 in TaskState.nextState(Symbol){ Check(state1,state2); }}}}

T. Gschwind, U. Aßmann, and O. Nierstrasz (Eds.): SC 2005, LNCS 3628, pp. 31-46, 2005. c Springer-Verlag Berlin Heidelberg 2005

WSDL: Web Services Description Language. http://www.w3c.org/TR/wsdl

SOAP: Simple Object Access Protocol. http://www.w3c.org/TR/SOAP

UDDI: Universal Description, Discovery, and Integration of Business for the Web. http://www.uddi.org

OWL-S: Semantic Markup for Web Service. http://www.daml.org/services/owl-s

Amigo: ambient intelligence for the networked home environment. http://www.extra.research.philips.com/euprojects/amigo/

Ontologies describe structured vocabularies, containing useful concepts for a community who wants to organize and exchange information in a non-ambiguous manner.

OWL: Web Ontology Language. http://www.w3.org/TR/owl-ref/

If C=Repeat-Until(P1) then it is treated as the Repeat-While(P1) but with removing the initial state from the set of final states. The only difference between the Repeat-While construct and the Repeat-Until construct is that the process being repeated is executed at least once in the case of the Repeat-Until construct.

Subsumption means the fact to incorporate something under a more general category.

We remind that equivalence relationship between symbols is a semantic equivalence that have already been checked during the semantic matching step.

Check

Fig. 5. A fragment of a Home Networking Ontology algorithms, authors argue that the conversation description is richer than the interface description, as it provides more information about the service's behavior, thus, leading to a more precise matching [START_REF] Bansal | Matchmaking of web services based on the daml-s service model[END_REF]. Furthermore, we argue that to obtain valid results when dynamically executing a service that publishes a conversation, it is important to follow the sequence of operations to invoke, as specified in the conversation description, until the latter finishes. Consequently, when composing Web services that expose complex behaviors, it is important to have solutions for dynamically integrating conversations. A number of research efforts have been conducted in the area of process-level matching [START_REF] Klein | Towards high-precision service retrieval[END_REF][START_REF] Aggarwaland | Dynamic web service composition in meteor-s[END_REF][START_REF] Majithia | A framework for automated service composition in service-oriented architecture[END_REF]. For example, Klein et al. in [START_REF] Klein | Towards high-precision service retrieval[END_REF] propose to describe services as processes, and define a request language named PQL (Process Query Language). This language allows to find in a process database those processes that contain a fragment that responds to the request. While this approach proposes a new process query language to search for


Nikolaos Georgantas

Sonia Ben Mokhtar

Yérom-David Bromberg

Valérie Issarny

Jarmo Kalaoja

Julia Kantarovitch

Anne Gérodolle
email: canne.gerodolle@francetelecom.com

Ron Mevissen

The Amigo Service Architecture for the Open Networked Home Environment

The Amigo project aims to develop a networked home system enabling the ambient intelligence / pervasive computing vision by effectively integrating devices and their hosted services in today's home. The Amigo system architecture poses limited technology-specific restrictions, supporting interoperability among heterogeneous services.

Introduction

The open networked home environment shall allow the seamless integration of the various devices and applications coming from today's, mostly disjoint, four home application domains: personal computing (PC), based on the home computers and Internet connection; mobile computing, manifested by the increasing use of home Wi-Fi and Bluetooth networks connecting laptops, PDAs and tiny personal devices; consumer electronics (CE), targeting multimedia in the home; and home automation, adding intelligence to household appliances. Service-orientation [START_REF]Serviceoriented computing[END_REF] appears as the appropriate architectural paradigm for the networked home system. Therein, networked devices and hosted applications are abstracted as services, which may dynamically be retrieved and composed, thanks to service discovery and coordination protocols.

This paper outlines the Amigo service-oriented system architecture for the open networked home, which has been designed as part of the Amigo 1 European project on the development of a networked home system enabling the ambient intelligence / pervasive computing vision. Key property that we are targeting within Amigo is interoperability, since the networked home integrates devices coming from different manufacturers that use different communication standards and different hardware and software platforms. The novelty of the Amigo approach lies in imposing no specific middleware technology, as most existing service architectures do: it allows heterogeneous technologies to be integrated, establishing interoperability at a higher, semantic, level. Further properties provided by the Amigo system are context-awareness, quality of service (QoS) 1 http://www.hitech-projects.com/euprojects/amigo/ and security & privacy, as these decisively affect user's experience of the networked home. In the next section, we introduce the overall Amigo reference service architecture; we conclude in Section 3.

Amigo Reference Service Architecture

In the elaboration of the Amigo system architecture, we do not intend to develop yet another service infrastructure imposing a homogeneous middleware layer on all home devices. We elaborate an abstract reference service architecture for the Amigo system, which can represent and integrate existing individual service infrastructures (e.g., Web Services2 , UPnP3 , etc.) relevant to the four home application domains by abstracting their fundamental features. To specify the Amigo reference architecture, we use as basis a typical service-oriented architecture [START_REF]Serviceoriented computing[END_REF]. The required properties discussed in Section 1 lead us to introduce additional building blocks into the typical architecture. Principally, we assume that all three layers (application-middleware-platform) of the architecture may be heterogeneous and based on diverse technologies; therefore, we incorporate appropriate interoperability mechanisms. The resulting Amigo reference architecture is depicted in Figure 1, where the advanced added elements are printed in boldface [START_REF]Deliverable D2.1: Specification of the Amigo Abstract Middleware Architecture[END_REF].

The interoperability mechanisms are based on semantics. Semantics of an entity encapsulate the meaning of this entity by reference to an established vocabulary of terms (ontology) representing a specific area of knowledge. In this way, semantics of entities become machine-interpretable, enabling machine reasoning on them. Such concepts come from the knowledge representation field and have been applied and further evolved in the Semantic Web4 domain. We have employed semantic concepts to model Amigo services. Our semantic service modeling builds upon the software architecture notions of components and connectors [START_REF] Georgantas | Semantics-Aware Services for the Mobile Computing Environment[END_REF]. Figure 2 depicts the mapping of the Amigo service modeling on the Amigo reference architecture. Typically, components are mapped on the application layer, and connectors are mapped on the middleware layer, to which we may attach the platform layer in order to address the complete interaction mechanism offered to applications. What distinguishes our mapping from the typical case is the semantic modeling and the resulting interoperability feature. Based on this modeling, we have introduced generic conformance relations at both component/application and connector/middleware levels, which enable reasoning on service composability. We have further devised associated interoperability methods at both component/application and connector/middleware levels, which allow composing partially conforming services. Conformance relations together with interoperability methods establish semantics-based service interoperability [START_REF] Georgantas | Semantics-Aware Services for the Mobile Computing Environment[END_REF].

Figure 1. Amigo reference service architecture

Based on the Amigo reference service architecture and the encompassed semantics-based interoperability, we further define a device capable of being integrated into the Amigo system as any device that: (i) implements (a subset of) the reference architecture employing specific technologies; and (ii) may implement some interoperability methods. This definition is very generic and allows very diverse technologies to be integrated into the Amigo system. The incorporation of interoperability methods by a device within Amigo will depend on a number of factors, such as the feasibility to enhance legacy platforms, the computational resources of the device, and certainly the necessity of such methods. Two devices capable of being integrated into the Amigo system will be interoperable if: (i) they conform semantically in terms of functional and non-functional properties; and (ii) they implement complementary interoperability methods. The degree to which the first condition is true, determines the degree to which the second condition is needed. Moreover, the complementarity of interoperability methods allows deploying such methods on one or both peer devices, for example depending on their resource capacity, or even on a third, intermediate, node (gateway).

Conclusion

We have outlined the Amigo reference architecture integrating heterogeneous devices and hosted services in the networked home environment by establishing interoperability at semantic level. Our next objectives in the Amigo project concern the detailed specification and prototype implementation of the Amigo system architecture. In this direction, specific application-layer and middleware-layer interoperability methods are being developed, as presented in [START_REF] Ben Mokhtar | QoSaware Dynamic Service Composition in Ambient Intelligence Environments[END_REF][START_REF] Bromberg | INDISS: Interoperable Discovery System for Networked Services[END_REF][START_REF]Deliverable D3.1: Detailed Design of the Amigo Middleware Core[END_REF].

Figure 2 .

 2 Figure 2. Amigo service modelingApplying the above fundamental principles, the Amigo reference architecture supports a number of features[START_REF]Deliverable D2.1: Specification of the Amigo Abstract Middleware Architecture[END_REF], such as: (i) (in the application layer) enriched service description specifying both functional and non-functional (context & QoS) properties of services; (ii) (in the middleware layer) service communication, enhanced service discovery reflecting the enriched service description, service composition, QoS & context support, security & privacy; (iii) (in the platform layer) QoS support, device resource-& capability-awareness.

http://www.w3.org/2002/ws/

http://www.upnp.org

http://www.w3.org/2001/sw/ Proceedings of the

5th Working IEEE/IFIP Conference on Software Architecture (WICSA'05)

Proceedings of the 5th Working IEEE/IFIP Conference on Software Architecture (WICSA'05)


Pierre-Guillaume Raverdy
email: pierre-guillaume.raverdy@inria.fr

Valerie Issarny
email: valerie.issarny@inria.fr

Context-Aware Service Discovery in Heterogeneous Networks

Pervasive environments bring new challenges for service management, as clients have to handle large collections of services offered by concurrent networks at their location, as well as services on networks in known remote locations. To enable service discovery in such service-rich environments, we introduce the Multi-protocol Service Discovery (MSD) platform that interacts with existing SD protocols and extend their service descriptions with context information. Service information and discovery requests are then disseminated between interconnected networks based on service and network profiles.

Introduction

The ubiquitous computing vision can now be realized, thanks to latest consumer-oriented mobile devices that are powerful enough to host services, and the deployment of wirelessly accessible services embedded into the environment to support mobile users in their daily life. The widespread integration of wireless technologies such as Bluetooth or WiFi has enabled complex heterogeneous networks to emerge, with a mix of infrastructure-based and/or infrastructure-less networks available to users at a location. Such environments bring new challenges to service management, and service discovery in particular.

Over the years, many academic and industrysupported service discovery (SD) protocols have been proposed for specific networks (e.g., Jini [START_REF]Jini[END_REF] for intranets, UPnP/SSDP [START_REF]Simple Service Discovery Protocol -Internet Draft[END_REF] for home networks). While efficient for the targeted environment, existing SD protocols prove to be inefficient or not applicable in different network settings. It is in fact unlikely for a single efficient SD protocol to emerge, due to diverse environment constraints and the de-facto standard status of some of the existing protocols. A service discovery solution for pervasive environments must thus address the issues of: (i) interoperability among existing SD protocols, and (ii) propagation of SD information across loosely coupled heterogeneous networks. Context-awareness and semantic knowledge, which have been seldom investigated in current SD protocols, also prove fundamental for the effective execution of mobile applications in such service-rich environments [START_REF] Bellavista | Context-aware Middleware for Resource Management in the Wireless Internet[END_REF]. To address the above issues, we propose the Multi-Protocol Service Discovery (MSD) platform, which is a comprehensive SD solution for heterogeneous networks.

In Section 2 of this paper, we describe the different components of the MSD platform and its common service description format. In Section 3 we elaborate how service discovery is performed in the MSD platform and in Section 4 we details remote service access. We finally conclude in Section 5.

The MSD Platform

We define an Elementary Network (EN) to be a set of devices that belong to the same administrative domain (e.g., IP subnet) and share the same IP-level set of communication functionalities (e.g., IP multicast). Examples of EN include hotspots, simple home networks, or MANETs. Several SD protocols may be in use in the same EN. We then define a Global Network (GN) to be a set of Elementary Networks, with some devices being connected to multiple ENs at the same time. Devices in the same GN, but in different ENs may or may not be able to communicate (e.g., no global IP routing, security restrictions).

Architectural Overview

The MSD platform is composed of the following components: (i) MSD Managers that provide contextaware SD to client applications, (ii) SD Plugins that interact with specific SD protocols on behalf of an MSD Manager; and (iii) MSD Bridges that disseminate service information in the GN.

The MSD Manager is the central component of the MSD platform. Each EN dynamically elects an MSD Manager that activates the relevant SD plugins, based on SD protocols activity detected in the EN. The MSD Manager interacts with its SD plugins to collect service descriptions and perform discovery requests. It also interacts with MSD Bridges in the EN to disseminate service descriptions and discovery requests in the GN. Each MSD Manager maintains a repository for the local and remote service descriptions that it receives.

Each SD Plugin interacts with a specific SD protocol (e.g., Jini, SSDP) on behalf of it's MSD Manager. Depending on the SD protocol, a SD plugin either registers for service announcements or performs discovery requests. In the MSD platform, a common format is used for describing services: the MSD service description ( §2.2). This description format not only contains service information derived from the original service description, but also contains context information added by the SD plugin and its MSD Manager. Different MSD Managers may support different sets of SD plugins.

Within the MSD platform, devices simultaneously connected to different ENs may be selected by the MSD Manager to act as MSD Bridges. MSD Bridges propagate service descriptions and discovery requests between the ENs on their different network interfaces according to specific propagation rules (i.e., to avoid message duplication and network flooding). Different MSD Bridges within an EN may not propagate the same service descriptions and discovery requests (e.g., if the target ENs do not have the same bandwidth or the same privacy policies). MSD Bridges also enable remote service access between clients and services in different ENs when direct connectivity is not possible by providing application-level routing. We argue that such federation of centralized managers supporting different SD protocols is the best approach to provide accurate and responsive service discovery while limiting processing and communication overhead.

MSD Service Description

MSD service descriptions generated by SD plugins contain: (i) creation information, (ii) service information, (iii) context information, (iv) propagation information, and (v) remote access information. The creation information is used by MSD Managers (local and remote) to learn about the MSD components that generated the MSD description (i.e., MSD Manager and SD plugin). The service information is used by client applications to learn on the basic features of the service (e.g., its methods or attributes) and on the SD protocol it was advertised with. The context information is primarily used to describe the environment where the service is hosted and aggregates the semantic and context information added by the MSD Manager and the SD plugin. The propagation information is primarily used by MSD Bridges to evaluate if they should forward the MSD service description. This information is composed of a set of propagation rules, and a list of propagation hops that represent the different MSD Bridges and networks the MSD service description already crossed during its dissemination. Finally, the remote access part contains information related to the remote access of the service. It indicates which methods of the service support remote access along with their requirements (e.g., bandwidth), and how to set up the communication channel to be used for remote service access.

Service Discovery in the MSD platform

A discovery request or MSD request is created by an MSD Manager on behalf of a client application and is composed of three parts: (i) a service description part where the client specifies the attributes of the service it is looking for; (ii) a request propagation part, which is similar to the propagation information in the MSD service description; and (iii) a request processing part that defines how MSD Managers, both local and remote, should return the results of the MSD request.

A client application interacts with the MSD Manager in its EN to issue an MSD request, that specify the characteristics of the requested service as well as the characteristics of its context (i.e., execution environment). The client also selects between different methods for collecting the request results: local and remote results may be returned independently, or together after a given timeout. The initial (local) MSD Manager reviews the SD protocols it supports and, depending on whether the protocol is push-based or pull-based, it either checks for potential services in its repository, or transmits the request to the relevant SD plugins. Each SD plugin then performs the relevant SD-specific discovery request, and returns the corresponding MSD service descriptions.

The MSD Manager also forwards the request to local MSD Bridges (if any) that evaluate if they should propagate it based on network profiles and status, and the propagation rules of the request. For each request it propagates, the MSD Bridge maintains a pendingrequest entry in order to return the results. Once expired, the entry is deleted, and the MSD Bridge does not return results for this request anymore. An MSD Manager receiving a remote MSD request evaluates it and returns the results. The MSD Manager also forwards the MSD request to the other MSD Bridges in its EN that evaluate if the request should be further propagated in the GN.

Remote Service Access

Discovering services hosted on nearby networks is only relevant if they can be accessed by client applications. The MSD platform enables such remote access. However, our objective is not to provide complete and transparent access: some methods of a service may not be accessible due, for example, to unmet requirements (e.g., bandwidth). The MSD platform relies on adaptors provided by service developers to translate calls between the generic service interface exposed in the MSD description and the native service interface, and to define the service requirements. We assume that clients explicitly use the MSD generic interface to access these remote services.

As each EN is managed independently, IP connectivity between the client and the remote service cannot be guaranteed. Prior to instantiating the service adaptor, and based on the propagation list from the MSD service descriptions, the relevant MSD Bridges are contacted to create a communication channel to provide application-level routing. Carefully selecting devices for acting as MSD Bridges is thus critical. In particular, the MSD platform targets consumeroriented pervasive environments, and we assume that most ENs in the environment are not highly mobile, and that in most cases a few stable devices will be available.

Related Work and Conclusion

We presented the MSD platform that addresses context-awareness and interoperability issues for SD protocols in pervasive environments. Some projects have also investigated the use of a common representation of service information to address SD protocols interoperability [START_REF] Friday | Supporting Service Discovery, Querying and Interaction in Ubiquitous Computing Environments[END_REF] [START_REF] Koponen | Service Discovery: A Service Broker Approach[END_REF]. Some middleware platforms [START_REF] Allard | Jini Meets UPnP: An Architecture for Jini/UPnP Interoperability[END_REF][5] have also investigated the full interoperability between clients and services (i.e., both service discovery and access). These projects however only consider SD protocol interoperability within the same network. On the other hand, some projects [START_REF] Castro | Locating Application Data Across Service Discovery Domains[END_REF] have investigated overlay networks and applicationlevel routing to enable service discovery in heterogeneous networks, but often assume global IP routing or limited service discovery in specific networks selected by the user.

The MSD platform combines the two approaches, and further investigate how application data (i.e., service descriptions) must be propagated depending on the underlying networks. We argue that a fully transparent approach for service discovery and access, while feasible for some discovery protocols and in specific network configurations, is not feasible in UBISEC GNs due to networking and security constraints, and may not even be desirable as client applications may not be able to distinguish local and remote services (i.e., location-based services). We are confident that our solution is well suited for mobile and pervasive environments, as the mass marketing of powerful CE devices (e.g., portable gaming devices and multimedia players) with multiple network interfaces and P2P-oriented services will create a network-rich and service-rich environment. The project also aims at defining the different profile types that can be collected from pervasive environments, and how they should be processed to provide effective context information.

Proceedings of the Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks (WoWMoM'05) 0-7695-2342-0/05 $20.00 © 2005 IEEE

Acknowledgements

This work has been done within the UBISEC project [9] running under the 6 th framework program performed by Information Society Technologies (IST) under the contract n o 506926.


Daniel Augot
email: daniel.augot@inria.fr

Valérie Issarny Raghav Bhaskar
email: raghav.bhaskar@inria.fr

Daniele Sacchetti
email: daniele.sacchetti@inria.fr

An Efficient Group Key Agreement Protocol for Ad hoc Networks

A Group Key Agreement (GKA) protocol is a mechanism to establish a cryptographic key for a group of participants, based on each one's contribution, over a public network. The key, thus derived, can be used to establish a secure channel between the participants. When the group composition changes (or otherwise), one can employ supplementary GKA protocols to derive a new key. Thus, they are well-suited to the key establishment needs of dynamic peer-to-peer networks as in ad hoc networks. While many of the proposed GKA protocols are too expensive to be employed by the constrained devices often present in ad hoc networks, others lack a formal security analysis. In this paper, we present a simple, secure and efficient GKA protocol well suited to dynamic ad hoc networks. We also present results of our implementation of the protocol in a prototype application.

Introduction

Ad hoc networks are networks composed of constrained devices communicating over wireless channels in the (partial) absence of any fixed infrastructure. Moreover, network composition is highly dynamic with devices leaving/joining the network quite frequently. Securing such networks becomes a more difficult task with additional challenges in the form of: lack of trusted third parties, expensive communication, ease of interception of messages and limited computational capabilities of the devices. Key establishment is a vital step in securing in any network. In ad hoc networks, key distribution techniques are not useful as there is not enough trust in the network so as to agree on a key decided by one member or some central authority. Group Key Agreement (GKA) [START_REF] Menezes | Hand-Book of Applied Cryptography[END_REF] protocols, which enable the participants to agree on a common secret value, based on each participant's public contribution, seem to provide a good solution. They don't require the presence of a central author-ity. Also, when the group composition changes (as in case of merger or partition of groups), one can employ supplementary key agreement protocols to get a new group key. Thus a transient secure channel can be constructed during the lifetime of one session of a group.

Related Work

Many GKA protocols [START_REF] Burmester | A secure and efficient conference key distribution system[END_REF][START_REF] Steiner | Key agreement in dynamic peer groups[END_REF][START_REF] Kim | Simple and fault-tolerant key agreement for dynamic collaborative groups[END_REF][START_REF] Bresson | Dynamic group Diffie Hellman key exchange under standard assumptions[END_REF][START_REF] Katz | Scalable protocols for authenticated key exchange -full version[END_REF][START_REF] Boyd | Round-optimal contributory conference key agreement[END_REF] have been proposed in literature, most being derived from the two-party Diffie-Hellman (DH) key agreement protocol. While some are secure against passive adversaries only, others do not have a rigorous security proof. A security proof typically involves showing that an attack on a protocol can be used to solve a well-known hard problem under some standard assumptions. Provably secure protocols in a well-defined model of security were first provided by Bresson et al. [START_REF] Bresson | Dynamic group Diffie Hellman key exchange under standard assumptions[END_REF]. Their security model extended the earlier work of Bellare et al. [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF]. The number of rounds in these protocols is linear in the number of participants, thus making them unsuitable for large ad hoc networks.

Yung et al. [START_REF] Katz | Scalable protocols for authenticated key exchange -full version[END_REF] proposed the first provably-secure constant round GKA protocol inspired from the works of Burmester et al. [START_REF] Burmester | A secure and efficient conference key distribution system[END_REF]. In the same work, they also proposed a scalable "compiler" to transform a GKA protocol, secure against a passive adversary, into one which is secure against an active adversary. But one round in their protocol consists of 1 broadcast and n -1 simultaneous receives by each user. Achieving this is not possible in most networks. Also it lacks procedures to handle group dynamism. Boyd et al. [START_REF] Boyd | Round-optimal contributory conference key agreement[END_REF] proposed an efficient constant round protocol where the bulk of the computation is done by one participant, thus making it efficient for heterogeneous ad hoc networks. It is provably secure in the Random Oracle model [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF] but lacks perfect forward secrecy (i.e., compromise of long-term key compromises all past session 1 keys). We propose a provably secure and efficient protocol which Protocol Expo per U i Rounds PS (Max Expo) (Messages) [START_REF] Steiner | Key agreement in dynamic peer groups[END_REF] 3 achieves perfect forward secrecy as well. Subsequent to our work, Won et al. [START_REF] Nam | DDH based group key agreement for mobile computing[END_REF] also solve this problem but their proposition turns out to be expensive computationally. In table 1, the number of exponentiations per member for our protocol are compared with some well-known protocols (including maximum number of exponentiations by any member for asymmetric protocols). Also the number of rounds (multiple independent messages can be sent in a round) and total number of messages are provided.

(m) m + 1 (2m -3) No [7] log 2 m + 1 log 2 m (m) No [4] i + 1 m (m) Yes [6] 3 2 (2m) Yes [9] 2 (

Outline

The paper is organized as follows: In Section 2, we present a new key agreement protocol for ad hoc environments. It is efficient both in communication and computation terms. Also, most of the exchanged messages are independent of each other, thus making it possible to collect them before the group is defined. In Section 3 we present a security analysis of the same and convert it into an authenticated key agreement protocol. In Section 4, we present our implementation results. Finally, we conclude in Section 5.

A New Group Key Agreement Protocol

We propose a new GKA protocol in this section. This protocol is unauthenticated and secure against passive adversaries only. We first introduce the notations used, illustrate the basic principle of key exchange, followed by detailed explanation of how it is employed to derive Initial Key Agreement (IKA), Join/Merge and Delete/Partition procedures for ad hoc groups.

Notation

G: A subgroup (of prime order q with generator g) of some mathematical group.

M i : i th participant in the current session. M l : The group leader: A member that is elected to coordinate group-level computation such as group-membership and group key management. Can be chosen randomly or by some application specific criteria. r i : A random number (from [1, q -1]) generated by member M i for each session. Also called the secret for M i . g ri : The blinded secret for M i , which is a public quantity. M: The set of indices of the participants in the current session (the session being considered). J : The set of indices of the joining participants (joining the current session). D: The set of indices of the leaving participants (leaving the current session).

x ← y: x is assigned y. x r ← S: x is randomly drawn from the uniform distribution S.

M i -→ M j : {M }: M i sends message M to participant M j . M i B -→ M : {M }: M i broadcasts message M to all par- ticipants indexed by M.

A Two Round Protocol

Protocol Steps: Round 1: Each M i responds to the initial request, IN IT , with its blinded secret g ri to the initiator. Round 2: The group composition is calculated and the group leader M l is elected and passed all the received data2 . M l raises each joining member's blinded secret to its secret (r l ) and broadcasts them along with the original contributions to the group, i.e., it sends {g ri , g rir l } for all i ∈ M \ {l}. Key Calculation: Each M i checks if its contribution is included correctly and then removes its secret r i from g rir l to get g r l . The group key is

Key = g r l * Π i∈M\{l} g rir l = g r l (1+ i∈M\{l} ri) .

Note:

1) The original contributions g ri are included in the last message as they are required for key calculation in case of group modifications (see below).

2) Even though Π i∈M\{l} g rir l is publicly known, it is included in key computation, to derive a key composed of everyone's contribution. The protocol is formally defined in table 2. We now see how this protocol can be used to derive IKA, Join/Merge and Delete/Partition procedures for ad hoc networks.

IKA: Secure ad hoc group formation procedures typically involve peer discovery and connectivity checks before a

Round 0 ∃j ∈ M, M j B -→ M : {IN IT } Round 1 ∀i ∈ M \ {j}, r i r ← [1, q -1], M i -→ M j : {g ri } Round 2 l r ← M, r l r ← [1, q -1] M l B -→ M : {g ri , g rir l } i∈M\{l} Key = g r l (1+ i∈M\{l} ri) Table 2. IKA
group key is derived. Thus, a discovery request is issued by a member (possibly multiple members) and all interested peers respond. The responses are collected and connectivity checks are carried out to ensure that all members can listen/broadcast to the group (see for instance [START_REF] Boulkenafed | Using group management to tame mobile ad hoc networks[END_REF][START_REF] Roman | Consistent group membership in ad hoc networks[END_REF]). After the group membership is defined, GKA procedures are implemented to derive a group key. Such an approach is quite a drain on the limited resources of ad hoc network devices. Thus an approach which integrates the two separate procedures of group formation and group key agreement is required. The above protocol fits well with this approach. Round 0 and Round 1 of the above protocol can take place in the discovery stage as the exchanged messages are independent of each other. In this way, blinded secrets, g ri 's, of all potential members, M i 's, are collected before the group composition is defined. When the fully connected ad hoc group is defined, a single message (Round 2 in table 2) from the group leader, M l , (using contributions of only the joining members) helps every member to compute the group key. Note that if in the group management protocol, the initiator and the leader are different entities, the leader will be passed on all the blinded secrets (along with other management data) during the group management stage. An example is provided below.

Suppose M 1 initiates the group discovery and initially 5 members express interest and send g r2 , g r3 , g r4 , g r5 and g r6 respectively. Finally only 3 join because of connectivity constraints. Suppose the members who finally join are M 2 , M 4 and M 5 . Then the group leader, say M 1 , broadcasts the following message:{g r 2 , g r 4 , g r 5 , (g r 2 ) r 1 , (g r 4 ) r 1 , (g r 5 ) r 1 } On receiving this message, each member can derive g r1 using his respective secret. Thus the key g r1(1+r2+r4+r5) can be computed.

Join/Merge: Join is quite similar to IKA. Each joining member, M i (i ∈ J ), sends a JOIN request along with its blinded secret, g ri to the existing group. The group leader (M l ) chooses a new random secret, r l , and sends all the blinded secrets to the new group leader 3 , M l . The new 3 For each session, one may want to elect a new leader.

Round 0 ∀i ∈ J , r i r ← [1, q -1], M i B -→ M : {JOIN, g ri } Round 1 r l r ← [1, q -1], M = M ∪ J , l r ← M M l -→ M l : {g ri } i∈M\{l } Round 2 l ← l , r l r ← [1, q -1] M l B -→ M : {g ri , g rir l } i∈M\{l} Key = g r l (1+ i∈M\{l} ri)
Table 3. Join/Merge group leader broadcasts a message similar to the round 2 message in IKA, i.e., all the blinded secrets and the blinded secrets raised to his (new) secret. It is worth noting that when a member, whose blinded secret is public, is chosen as the group leader, he chooses a new pair of secret and blinded secret. See table 3 for formal specification and below for an example.

Suppose new members, M 9 and M 10 join the group of M 1 , M 2 , M 4 and M 5 with their contributions g r9 and g r10 respectively. Then the previous group leader (M 1 ) changes its secret to r * 1 and sends g r * 1 , g r2 , g r4 , g r5 , g r9 to M 10 (say the new group leader). M 10 generates a new secret r * 10 and broadcasts the following message to the group: {g r * 1 , g r2 , g r4 , g r5 , g r9 , g r * 10 r * 1 , g r * 10 r2 , g r * 10 r4 , g r * 10 r5 , g r * 10 r9 }. And the new key is g r * 10 (1+r * 1 +r2+r4+r5+r9) .

Delete/Partition: Delete is quite similar to Join. When members leave the group, a new group leader is randomly chosen from the remaining members and he changes his secret contribution and sends an IKA Round 2 like message to the group, omitting the leaving members' contributions.

We omit the details.

Security Result

The protocol presented in the earlier section is provably secure against passive adversaries in the model of [START_REF] Bresson | Dynamic group Diffie Hellman key exchange under standard assumptions[END_REF], from where the notations and definitions are taken.

Theorem 1: Let P be the protocol as defined above. Let A be a passive adversary making q ex = (q ika +q join +q delete ) Execute queries to the parties and running in time t. Then Protocol P is a secure GKA protocol. Namely:

Adv A P (t, q ex ) ≤ 2q ex * Succ DDH (t )
where t ≤ t + q ex |P|t exp , t exp is the time to perform an exponentiation in G and |P| being the maximum number of participants in the protocol.

Authenticated protocol

Thus applying the above compiler to our protocol yields a 3-round authenticated GKA protocol, P with the following security reduction:

Theorem 3: Adv A P (t, q ex , q s ) ≤ (q s + 2q ex ) * Succ DDH (t ) + |P| * Succ Σ (t ) + q 2 s +qexqs 2 k

Implementation

To test the performance of this new GKA protocol, we incorporated it in the group management protocol of [START_REF] Boulkenafed | Using group management to tame mobile ad hoc networks[END_REF]. The group management of [START_REF] Boulkenafed | Using group management to tame mobile ad hoc networks[END_REF] consists of three communication rounds: DISC, JOIN and GROU P . The DISC stage initiates the group formation by calling for interested participants. Each interested participant responds with a JOIN message. The group membership is defined and announced by the group leader (chosen randomly) by the GROU P message. The design of the new GKA protocol allowed us to piggy-back GKA data on group management messages, thus member contributions towards the group key are collected during JOIN messages while the GROU P message carries the message from the group leader which enables everyone to compute the group key. Thus no additional communication round is required to derive a group key, irrespective of the group size. It is worth mentioning that it would not have been possible with most of the protocols presented in table 1, as the messages sent by group members are dependent on messages sent by other members. A comparison of the computation times on a device in the absence and presence of GKA procedures is plotted in table 4. The data shown is for an experimental setup consisting of laptops (Compaq 500 Mhz running Linux) and palmtops (Compaq ipaq 400MHz running Linux familiar 0.7). All random contributions for the group key were cho- sen from a Diffie-Hellman group of prime order of 1024 bits. The code was written in Java except the exponentiation function which was implemented in native code with the GMP library5 . The graphs in table 4 plot computation time (in milliseconds on Y axis) against group-size with and without GKA. There are separate plots for the cases when the device was a leader/non-leader. Leader for group management was randomly chosen. As expected, the time for non-leader members increases (when employing GKA protocol) by an almost constant factor (order of time to perform two 1024 bit exponentiations) , while for a leader it increases linearly as the group size increases. As most ad hoc networks are expected to be composed of devices of unequal computing power, more powerful devices (like laptops) can assume the role of a leader more often.

Conclusion

We have proposed a new group key agreement protocol, particularly well suited to ad hoc networks, and secure against a passive adversary. It is efficient in the number of rounds (only two rounds, the first round may be executed along with group management procedures), and also efficient in computational terms. It can be, using Yung et al. compiler, transformed into a three round protocol secure against an active adversary. This adds to the cost of the protocol, by adding one round of broadcasts. The protocol is simple and we have provided a security proof in the framework of [START_REF] Bresson | Dynamic group Diffie Hellman key exchange under standard assumptions[END_REF], using the standard model and the Decisional Diffie-Hellman assumption in any group. Experimental results show that our protocol results in a reasonable computational overhead during group formation with hardly any communication burden. Further reductions in terms of computation overhead can be made by using Elliptic curve groups.

  and non-leader

Table 1 . Efficiency Comparison of GKA proto- cols (PS: Provably Secure)

 1

		2m )	2 (m)	Yes
	Ours	2 (m)	2 (m)	Yes
	m: Number of participants
	: 3 rounds for authenticated GKA : m inverse calculations or O(m 2 ) multiplications apart from m exponentia-
	tions

Table 4 . Computation time per device with and without GKA for laptop and palmtop

 4

A session refers to one instance of GKA protocol execution in some group.Proceedings of the Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks (WoWMoM'05) 0-7695-2342-0/05 $20.00 ©

IEEE

Note this is part of the group management protocol. Proceedings of the Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks (WoWMoM'05) 0-7695-2342-0/05 $20.00 © 2005 IEEE

Proceedings of the Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks (WoWMoM'05)

Proceedings of the Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks (WoWMoM'05) 0-7695-2342-0/05 $20.00 © 2005 IEEE

http://www.swox.com/gmp/

Proof: Due to lack of space, we only give a sketch of the proof. The complete proof will appear in the full version 4 . We show that an adversary who achieves an advantage in calculating the session key, can be used to build an attacker ∆ which gains an advantage in solving an instance of the Decisional Diffie-Hellman (DDH) Problem. The Send and Corrupt queries are not applicable as we are dealing with a passive adversary and there are no long-term secrets. Thus the only relevant queries are the Execute, Reveal and Test queries. Assume the adversary A distinguishes the session key with a probability non-negligibly greater than 0.5. We construct from A a DDH attacker ∆ that receives as input an instance D = {g, g 1 , g 2 , g 3 } and predicts if it is an instance from (g, g ra , g r b , g rar b ) or (g, g ra , g r b , g rc ) with a non-negligible advantage.

The Attacker ∆ feeds A with elements derived from the instance D in the reply to the Execute query of the session for which A will make the Test query. So ∆ picks at random c test from [1, q ex ] which is its guess for the number of the Execute query, corresponding to the session, for which A makes the Test query. For all other sessions, ∆ responds to Execute queries with randomly generated data.

∆ replies to the Test query with a session key, sk, constructed using data from the instance D. sk is a valid session key only if the instance D is a DH tuple. Thus, if the adversary A correctly identifies sk as the session key, the tuple (g, g 1 , g 2 , g 3 ) is indeed a DH tuple otherwise it is a random tuple. The success probability of ∆ is the probability that it correctly guesses the session for which A makes the Test query (1/q ex ), multiplied by the success probability of A. Thus if we denote by p the probability of adversary A distinguishing the session key, the probability of success of ∆ is: Succ DDH (t ) ≥ p/q ex . The running time of ∆ is bounded by the running time of A and the time to perform at most |P| exponentiations during q ex queries.

An authentication compiler

In [START_REF] Katz | Scalable protocols for authenticated key exchange -full version[END_REF], Yung et al. introduced a scalable compiler which transforms any GKA protocol P , secure against passive adversary, to an authenticated GKA protocol P , secure against an active adversary. It achieves this by enhancing the protocol to include a (pre-)round where everyone broadcasts its identity and a random nonce. Thereafter each message is accompanied by a signature on the message, identities of the participants and their nonces (see [START_REF] Katz | Scalable protocols for authenticated key exchange -full version[END_REF] for details). Then if P is a secure GKA protocol, then the protocol P is a secure Authenticated GKA protocol. Namely, Theorem 2: Adv A P (t, q ex , q s ) ≤ qs 2 * Adv A P (t , 1) + Adv A P (t , q ex ) + |P| * Succ Σ (t ) + q 2 s +qexqs 2 k

4 http://www.inria.fr/rrrt/index.en.html

where: q ex and q s are the number of Execute and Send queries respectively. t = t + (|P|q ex + q s ).t P , t P is the time to execute P . Adv A P (t, q ex , q s ): Advantage of an active adversary (A ) against the authenticated protocol P , making q ex Execute queries and q s Send queries in time t. Adv A P (t , 1): Advantage of a passive adversary (A) against the protocol P , making 1 Execute query in time t . Adv A P (t, q ex ): Advantage of a passive adversary (A) against the protocol P , making q ex Execute queries in time t . Succ DDH (t ): Success probability of an adversary against an instance of the DDH problem in time t . Succ Σ (t ): Success probability of an adversary against the signature scheme Σ in time t . and k is the security parameter.