The QoS-aware Web service composition problem : a new approach for the selection step

In the last ten years, through the growth of Web services utilisation, the Web has transformed from a structure with manual interactions to one with automated interactions. This is originating huge chances for the creation of online business-to-business cooperations. The development of value-added Web services by the composition of simple Web services is receiving a growing attention from researchers in the field. Due to the fact that a large number of Web services provide comparable or identical functionalities, the selection and the composition becomes a decision problem based on non-functional properties of Web services. The industrial areas in which Web services are becoming important are the ones of finances and multimedia applications. The goal of the present work is to address the second step of the QoS-aware Web service composition problem, which is the selection step. To do this, we provide a deep analysis of some of the most important papers in the field, starting from one that is considered as a milestone arriving to a recent hybrid approach. We examined papers that implemented exact methods (especially, IP) as well as articles that proposed heuristic methods to solve the problem. The hybrid approach is a technique which combine the two existing method families. Then, we present a new algorithm we developed, basing on two papers we analysed. For our approach, we started from a known structure to model Web services and we modified it by applying an "aggregation transformation" with the aim of applying an IP solver, in order to get a faster optimal solution to the Web service selection problem. We implemented our IP model in the optimisation software package CPLEX and we recorded the execution time of our algorithm by varying the dimension of the instance of the model. We charted the results and showed them in several figures. We concluded our work by making some considerations on what we did and indicating some possible directions for future improvements to the state of the art.

Negli ultimi dieci anni, il progredire da un Web costituito di interazioni manuali verso un Web di interazioni automatizzate mediante il crescente impiego dei Web service sta creando grandi occasioni per la cooperazione online di tipo business-to-business. Lo sviluppo dei Web service a valore aggiunto sta ricevendo un'attenzione sempre maggiore da parte dei ricercatori. Data l'esistenza di numerosi Web service che forniscono funzioni paragonabili o identiche, la selezione e la composizione di questi viene considerato come un problema di decisione basato sulle proprietà non funzionali dei Web service. I settori dell'industria in cui i Web service stanno acquisendo importanza sono quelli della finanza, contabilità e delle applicazioni multimediali. L'obiettivo di questo documento consiste nell'affrontare la seconda fase del QoS-aware Web service composition problem, ovvero la fase di selezione. Per fare questo, per prima cosa ci occupiamo di analizzare alcuni dei lavori più importanti nel settore, a partire da quello che è considerato come una pietra miliare fino ad arrivare ad approcci di tipo "ibrido". Abbiamo quindi esaminato documenti che implementano metodi esatti (in particolare, PI), così come lavori che propongono metodi euristici per risolvere il problema. L'approccio ibrido è una tecnica che combina le due famiglie di metodi. Abbiamo quindi sviluppato un nuovo algoritmo, sulla base di due degli articoli analizzati. Siamo partiti da una struttura nota per modellare i Web service, modificandola mediante l'applicazione di una "trasformazione" con l'obiettivo di applicare un risolutore PI, al fine di ottenere una soluzione ottima al problema di selezione più velocemente. Abbiamo implementato il nostro modello nel software di ottimizzazione CPLEX e abbiamo registrato il tempo di esecuzione dell'algoritmo al variare della dimensione dell'istanza del modello. Abbiamo disegnato dei grafici per mostrare i risultati ottenuti. Abbiamo concluso il nostro lavoro con alcune considerazioni su quanto fatto e indicando alcune possibili direzioni per lo sviluppo futuro dello stato dell'arte.