An adaptive heuristic approach for distributed QoS-based service composition

QoS-based service selection becomes a commonly accepted procedure to support rapid and dynamic web service composition. In this paper, we study the problem of QoS-based service selection in distributed QoS management environments where QoS values of alternative services are maintained by distributed QoS registries. A distributed heuristic approach is proposed to solve the problem efficiently with a high approximation ratio, and enable adaptability in distributed cross-organization environments with data privacy protection and a low cost of communication. The proposed approach consists of four stages in which variable elimination is used to reduce the size of the problem; constraint decomposition allows performing service selection independently on each QoS registry; supplementary service selection and concentrated optimization improve the approximation ratio. Performance analyses and simulation experiments show that the proposed approach performs efficiently with close-to-optimal results and fits well to distributed QoS management environments.