基于QoS线性化和最短路径思想的Web服务组合选择体系.docVIP

 基于 QoS 线性化和最短路径思想的 Web 服 务组合选择体系 胡启平 （清华大学计算机科学与技术系，北京 100084） 摘要：针对从大量符合用户功能性需求的 Web 服务组合中选择服务质量（QoS）最高的一 组服务的问题，分析了目前 Web 服务选择方法和 QoS 计算模型的不足，在已有标准和方法 的基础上提出了线性化的 QoS 计算模型，解决了局部和全局一致性的问题，并给出了一套 基于最短路径思想的选择方法。该方法拥有很低的时间复杂度，能够支持服务间的 QoS 关 联，多路径选择，并可以针对候选流程图的不同复杂程度使用尽量高效的方法。最后通过实 例对该系统进行了说明和分析。 关键词：Web 服务；服务组合选择；服务质量；线性化；最短路径 中图分类号：TP393 文献标识码：A Composite web service selection system based on QoS linearization and shortest path Hu Qiping (Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China) Abstract: Aiming at the problem of selecting composite web services with the highest quality of service (QoS) from large number of candidates which meet the functional needs of the user, we analyze the weakness of current web service selection method and QoS calculation model, and provide a linear QoS calculation model based on existing standards and methods to make the parts and the overall consistent. We also provide a selection method based on ideas of shortest path, which has low time complexity and supports multi-path selection and QoS correlation between services. The method can adaptively use different algorithms for different levels of complexity of the flowchart to get higher efficiency. Finally, we illustrate and analyze the system through an example. Key words: web services; composite service selection; quality of service; linearization; shortest path 0 引言 随着 Web 服务技术的高速发展，网络上出现了大量 Web 服务，部分 Web 服务之间虽然 提供的业务功能基本相同，但却具有不同的非功能属性，如价格、可靠性、响应时间等。这 些非功能属性统称为服务质量（QoS，quality of service）。 面对不同用户各种复杂的需求，如何在满足用户功能性需求的前提下，从海量 Web 服 务中快速而准确地选择一套高质量的服务组合方案，使用户更满意，是 Web 服务发展中的 一个重要问题，也是目前的一个研究热点[1-2]。 基于 QoS 的 Web 服务选择问题是一个 NP 难问题[1,3]。假设用户的需求需要 n 个服务通 过组合共同完成，每个服务中有 m 个相同功能、不同 QoS 的服务可供选择。传统的穷举算 法通过枚举所有 mn 种可能的组合，能够保证找到全局最优解，但是对于大规模数据，其效 率是无法令人接受的。而另一种传统的贪心算法可以在 O(nm)的复杂度内找到每个服务中 QoS 最高的局部最优解，然后选择这些服务进行组合，虽然非常高效，但无法保证整个全局 组合后的服务质量是最优的[1]。 贪心算法无法适用于全局的根本原因在于现有 QoS 计算模型中每个 QoS 指标归一化变 换、每个服务以及整个组合服务的总体 QoS 均采用线性化的方法计算[4]，但是各 QoS 指标 作者简介： 胡