Abstract: To solve the problem of automatic Web services composition with multiple inputs/outputs，an approach based on directed level graph was proposed．It provided an optimal composition sequence through these steps as follows：1) Built a directed level graph by inputs/outputs of user request；2) Built a complete reduction graph of the directed level graph；3) Searched all reachable paths for every node of complete reduction graph；4) Converted the optimal path for user request into services composition sequence．This approach can generate all composition sequences with least steps and an optimal composition sequence according to the quality of services．Compared with traditional graphbased approach，it reduces search space and avoids cycle searching and can be applied in a large scale of Web services repository．

Key words: Web services composition, Directed Level Graph (DLG), complete reduction graph, Quality of Service （QoS）, composition sequence

摘要： 为解决多输入/输出的Web服务自动组合问题，提出了基于有向层次图的Web服务自动组合方法，主要步骤如下：1）根据用户请求的输入/输出参数集生成有向层次图；2）在有向层次图中构造完全规约图；3）在完全规约图中计算每一顶点的所有可达路径；4）为用户请求选择最优路径，并转化为Web服务组合序列。该方法能够求得最短步数内的所有Web服务组合序列，根据Web服务的服务质量(QoS)获得最优的组合序列，从而满足多输入/输出的用户请求。与基于图的Web服务组合方法相比，减少了搜索空间，适用于大规模的Web服务库。

关键词: Web服务组合, 有向层次图, 完全规约图, 服务质量, 组合序列