A Parallel Approach for Service Composition with Complex Structures in Pervasive Environments

The composition of multiple services that are deployed on smart devices generally incurs significant communication overheads, especially when an optimized composition is pursued. A parallel approach for service composition is proposed for obtaining the optimal solution with minimum executing time efficiently. In this approach, the request for a composite service is represented by a function graph which is decomposed into multiple path-structured sub graphs firstly. Then messages are sent among the service nodes to search for the corresponding sub-solutions. Finally, a Branch-and-Bound strategy is applied to generate the optimal solution over these sub-solutions. The experiments show our optimization strategies can reduce the time and communication cost considerably under different experimental settings.