Minimum Cost Composition Algorithm for Web Service Based on CSP

Traditional formal method has been solved the problems of functional modeling and verification of Web service composition, but it could not effectively analyze and calculate the costs of the service composition. A minimum cost composition algorithm based on process algebra CSP is proposed. The algorithm first translates the XML format Web service composition description to CSP format formal description. According to the trace model of the CSP, the executive paths for the proper composition schemes can be found. Finally, the total cost of the composition schemes can be solved out according to the cost of the single event in the web services' interfaces. A case study is presented that shows the algorithm can effectively calculate the total costs of the composition schemes, and the optimal scheme can be pick out refer to the results.