“Web服务”已经成为网络环境下对资源进行封装、抽象和虚拟化的主要手段之一,它是一种自描述、自包含、平台无关的自治计算单元。面向服务的计算SOC(ServiceOrientedComputing)以服务为基本单位,通过复用相关的服务来构造功能更加强大的组合服务及应用。随着SOC这种蕴含“复用服务”思想的计算方式业成为主流,服务组合应用的逐步展开,服务数量增长速度不断加快,在这样一个海量的服务集合中,手工比对、选择可互操作的服务候选者,并构造服务组合流程的方法往往是行不通的。为此,自动服务组合技术应运而生,并日渐引起了学术界和工业界的重视。但是现有的自动服务组合研究存在若干缺陷,主要表现为:(1)相关方法的准确性不足,效率仍有很大的提高空间;(2)相关方法基于静态服务的假设,忽略了服务动态特性,无法保证服务组合结果的一致性和有效性;(3)相关方法缺乏处理Top-k查询的能力,无法满足用户的个性化需求,极易导致负载不均。为克服上述问题,本文围绕质量敏感的自动服务组合问题,研究如下内容并开发了相关系统,主要工作和贡献包括:　　 1.为了给自动服务组合研究工作奠定坚实的基础,本文首先对网络上真实Web服务的现状进行了调研和分析。相比现有工作,我们不仅分析基于SOAP的Web服务,还分析了基于WADL和文本描述的RESTful服务;我们监控服务规模最大(超过2万个不同类型服务)、而且持续了将近一年的周期,为现有Web服务调研工作之最;此外,我们不但考虑了诸多静态的服务信息,如服务类别、URL、描述文档大小,而且考虑其动态信息,如接口变化、响应时间、吞吐量变化等。依托Amazon平台,我们在全世界五个国家设置了五台服务器对Web服务进行了监测,以分析不同地域调用服务的差异性。所有调研获取的Web服务数据集已在网络上公开与共享。　　 2.为应对海量服务环境下的自动服务组合及全局QoS求优问题,本文提出了基于图搜索的两阶段质量敏感的自动服务组合算法,该算法的优势为:首先,在数以万计的服务规模下,它能够在毫秒级别内返回最优的服务组合结果。其次,它能处理多种不同类型的服务质量(QoS)和不同的组合模式,100%保证所返回的服务组合结果的最优性。我们设计的两套算法—Worklist算法和Sim-Diikstra算法,分别获得IEEECEC举办的世界Web Service Challenge2009和2010性能冠军。实验表明:这两个算法能在毫秒级别时间内响应查询请求、且具有100%准确性。　　 3.为适应真实的动态服务环境,本文首次将持续查询机制引入质量敏感的自动服务组合中,通过事件驱动方式即时地处理动态服务并按需更新受影响的服务组合结果。据此思想,本文实现了自动服务组合的持续查询算法。该算法的优势为:首先,它不但可以处理新加入的服务,失效的服务,而且可以处理QoS发生变化的服务、接口发生变化的服务。其次,它不但可以支持无效服务的1-1替换,而且支持n-m替换和逻辑结构的变换。实验证明:持续查询的效率比重新查询方法(基于Web Service Challenge性能冠军的算法)的效果平均提高了11倍以上。　　 4.为满足用户的个性化需求,同时避免过热的服务和组合服务,实现负载均衡,本文提出了支持Top-k查询的质量敏感的自动服务组合问题,并设计了基于关键路径的松弛算法。依据它们,我们设计了中国首届服务竞赛的题目和测试集,并将关键路径松弛算法的结果作为基准来评测其它参赛系统,在中国云计算大会上被授予特别贡献奖。实验表明:该算法仅为相关研究中的算法所消耗时间的3%-35%,且准确性提高出了近1倍。　　 5.通过对质量敏感自动服务组合问题进行图论抽象,我们定义了与经典图不同的标记图。论文详细讨论了标记图中结点的可达性、最优DAG问题、Top-kDAGs问题,以及它们与最短路径问题和前k条最短路径问题的区别和联系。此外,论文还对新图论问题及算法的潜在应用,如API推荐和供应链,进行了讨论。实验表明:与API推荐中的相关工作相比,我们的算法不仅在解决查询的能力方面最强,而且准确性更高。