<figure><img src="image_1.png" /></figure>

HAL
open science

# A QoS-Aware Hyper-graph Based Method of Semantic Service Composition

Cui Lizhen, Xu Meng

► To cite this version:

Cui Lizhen, Xu Meng. A QoS-Aware Hyper-graph Based Method of Semantic Service Composition. 4th International Working Conference on Enterprise Interoperability (IWEI), Sep 2012, Harbin, China. pp.81-91, 10.1007/978-3-642-33068-1_9. hal-01515737

HAL Id: hal-01515737

https://inria.hal.science/hal-01515737

Submitted on 28 Apr 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A QoS-Aware Hyper-Graph Based Method of Semantic Service Composition

Cui Lizhen, Xu Meng

School of Computer Science and Technology, Shandong University, Jinan, China
Shandong Provincial Key Laboratory of Software Engineering
clz@sdu.edu.cn

**Abstract**—Semantic service composition is an important issue in web service based systems. It is about how to build a new, reusable and value-added service by combining existing semantic web services. In this paper we propose a new hyper-graph based method supporting semantic service composition, which model the service composition problem as a hyper-graph. Then the hyper-graph based service composition algorithm has been implemented and evaluated. The evaluation results have shown that the method can effectively reduce the composition time and has good robustness, especially in the case of large number of web services and concepts.

**Index Terms**—QoS-aware, Hyper-graph, Service Composition

## 1 Introduction

Service-oriented computing (SOC) has been widely accepted as the next generation programming paradigm. The web services are loosely coupled, reusable and self-describing software components that encapsulate discrete functionality and are distributed and programmatically accessible over standard internet protocols [1]. It is an alternative and promising approach to development web-based application or system rapidly to combine the existing Web Services. But with the number of Web Service on the internet over the last few years increasing sharply, it is difficult and time consuming to combine web services manually [2]. Therefore, semantic web is introduced into Web Service technologies to support dynamic and automated tasks such as discovery, composition and execution. In recent years, how to composite services automatically have drawn lots of research attentions [3-9].

In this paper we proposed a QoS(Quality of Service)-aware hyper-graph based method for semantic Web Service Composition. We model the service composition problem as two hyper-graphs. And by pruning the vertexes and the link between two hyper-graphs, the composite service is built effectively.

The main contributions of this paper are as follows:

(1) Show how the problem of service composition can be modeled as a hyper-graph transversal problem.
(2)Tackle the problem of automatic service composition and QoS-aware service selection problem together with an algorithm that both efficient and 100% precise.

The rest of the paper is organized as follows: Section 2 reviews related work and motivates this work. Section 3 shows how to model the service composition problem as a hyper-graph transversal problem. Section 4 discusses the detail of the approach. Section 5 evaluates the performance of the proposed QoS-aware hyper-graph based method of semantic service composition in this paper, and finally Section 6 concludes.

## 2 Related Work

Since it is very difficult and time consuming to find composite service manually from huge amount of services, automatic service composition is proposed to enable automatic building composition for a given request. Some approaches, such as [5, 6], tackle Web service composition problem via AI planning. On the other hand, some other researches [4, 10] regards it as a graph search problem and solves it by shortest path, A*, etc. algorithms.

To guarantee local or global QoS requirements of service composition, the QoS-aware service composition has attracted a lot of attention in recent years. Different from automatic service composition, it assumes that a work plan is predefined and has a set of “abstract” tasks and the objective is to select service for each task from its candidate services to meet local or global QoS constraints. Zeng [12] uses two service selection approaches based on Multiple Criteria Decision Making. In [13], the authors model the problem as a multi-choice 0-1 knapsack problem or a multi-constraint optimal path problem, and then compute optimal result according to the objective function. In addition, a genetic algorithm is proposed to address the problem in [3]. Although it is more inefficient than Integer Programming, it can deal with non-linear constraints.

In one words, all the methods above for automatic service composition or QoS-aware service composition only consider one aspect of QoS-aware automatic service composition, which is to search work plans for a given request or to guarantee global QoS requirements. Furthermore, Some researchers have proposed approaches to address the QoS-aware automatic service composition problem, such as [14-16]. Peter [11] proposes a fast approach by some index tables stored in database to fit the competition CEC'09[11]. But it cannot provide 100% precision and its efficiency are not good enough when the scale of services is big.

In [17], Zhu modeled the problem of computing cost constrained collections of Web services as a constrained hyper-graph transversal problem. But it only can compute a set of services to fulfill some functions. Our method can find a composite service which can satisfy a user request.
### 3 Definition and Problem Model

We now provide the necessary definition about hyper-graphs and the semantic service composition. Then a formal description of the problem will be given.

**Definition 1** A hyper-graph H is a pair $H = \langle E, V \rangle$ where V is a finite set of vertices $V = \{ v_1, v_2, ..., v_m \}$ and E is a family of (hyper) edges, $E = \{ e_1, e_2, ..., e_t \}$ where each $e_i$ is a subset of V, $1 \le i \le t$. We assume $V = \{ \cup e_i | e_i \in E, 1 \le i \le t \}$.

**Definition 2** The candidate service is a service which can be used in the service composition process. The candidate service set is a finite set of services $S=\{s_i|s_i$ is a candidate service$}$. And $s_i=<p(s_i)_{in}, p(s_i)_{out}, QoS>$, where $p(s_i)_{in}$ is the input parameters set of $s_i$, $p(s_i)_{out}$ is the output parameters set of $s_i$, QoS is the QoS property of $s_i$.

In this paper, we only consider the response time as the QoS property of web service. And the computing method can be find in [18].

**Definition 3** The composition request is a request of user which can be represent as $R=\{P_{in}, P_{out}\}$, $P_{in}$ is the set of input parameters and $P_{out}$ is the set of output parameters.

We now describe the reduction of the semantic service composition problem to the problem involving hyper-graphs. We will model the problem to two hyper-graphs. One is called output parameters hyper-graph, which is represented by $H_o$. And the other is called input parameters hyper-graph, which is represented by $H_i$. Each Web Service in S is modeled as a vertex both of $H_o$ and $H_i$. Furthermore, a virtual service (vertex) is added in $H_o$ and $H_i$ respectively. The virtual service which is added in $H_o$ is called input_service $I_s=\{\phi, R, P_{in}, 0\}$ whilst the virtual service which is added in $H_i$ is called output_service $O_s=\{R, P_{out}, \phi, 0\}$. Then we will add edges in $H_o$ and $H_i$. Each edge in $H_o(H_i)$ corresponds to a set of vertices (web services) which have a particular output(input) parameter. The transversals of the two hyper-graphs now correspond to two sets of services that cover all the services requested by the user.

**Example 1** Let us consider a example. $S=\{s_1, s_2, s_3, s_4, s_5, s_6\}$. The input and output parameters of all services are listed in Table 1. The request of user is $R=\{a,b,e\}, \{f,g\}$.

<table><caption>TABLE 1. CANDIDATE SERVICES</caption><thead><tr><td>Service Name</td><td>input</td><td>output</td><td>QoS</td></tr></thead><tbody><tr><td>s1</td><td>a, b</td><td>c, d</td><td>10</td></tr><tr><td>s2</td><td>c</td><td>g</td><td>20</td></tr><tr><td>s3</td><td>d, e</td><td>f</td><td>15</td></tr><tr><td>s4</td><td>c</td><td>g</td><td>25</td></tr><tr><td>s5</td><td>c, d</td><td>f, g</td><td>30</td></tr><tr><td>s6</td><td>f, g</td><td>h</td><td>20</td></tr><tr><td>s7</td><td>h, i</td><td>j</td><td>15</td></tr></tbody></table>

The request of user is $R=\{a,b,e\}, \{f,g\}$.

According to the R, we add two virtual services $I_s=\{\phi, \{a,b,e\}\}$ and $O_s=\{\{f,g\}, \phi\}$. Then the $H_o$ and $H_i$ are drawn in Fig. 1.
<figure><img src="image_3.png" /><figcaption>Fig. 1. Hi and Ho</figcaption></figure>

## 4 Hyper-Graph Based Service Composition Algorithm

In this section, we will describe the hyper-graph based service composition algorithm. We will use the example shown in Fig. 1. Response time of every service is shown using superscripts. Fig. 2 illustrates the basic outline of the algorithm.

First, the two hyper-graphs are generated according to the request and candidate service set. During the process of generating hyper-graphs, the complete time is calculated for every service. Then a pruning strategy is applied to delete the useless service and edge. At last, a solution generation algorithm is used to create the composite service.

Input: User Request R, Candidate Service Set S

Output: Composite Service CS

1. $H_o = \emptyset, H_i = \emptyset$

2. HG_Generate(R, S, $H_o$, $H_i$)

3. Prune($H_o$, $H_i$)

4. CS=Solution_Generate($H_o$, $H_i$)

5. Return CS

<caption>Fig. 2. Hyper-Graph Based Service Composition Algorithm</caption>

### 4.1 Generating the Hyper-Graphs

Fig. 3 shows how to generate the hyper-graphs. First, two virtual services, $I_s$ and $O_s$, is created. The output of $I_s$ is the input of request $R.P_{in}$ and the input of $O_s$ is the output of request $R.P_{out}$, while the input of $I_s$ and the output of $O_s$ is $\emptyset$ (line 0). After the creation of the virtual services, the $I_s$ is added into $H_o$ and its complete time is computed. And an edge is added into $H_o$ for every output parameter of $I_s$. Moreover, all parameters of $I_s$.output is put into a queue Q (line 2-6). If the queue Q is not null, it suggests that there are parameters which are not processed. So we get the parameter and find the services whose input parameters include it. Then the service is added into $H_i$ and its complete time is calculated. At that time, it is decided whether the edge
need to be added into $H_i$ (line 9-17). If all of the input parameters of the service is in $H_o$, the service is added into $H_o$. Repeat that until the queue is null. After doing all this, we get two hyper-graph $H_i$ and $H_o$. Fig. 1 shows the $H_i$ and $H_o$ which is generated by the algorithm.

<table><caption>Fig. 3. Hyper-Graph Generating Algorithm</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>HG_Generate</td><td></td></tr><tr><td>Input: User Request R, Candidate Service Set S</td><td></td></tr><tr><td>Output: Hyper-Graphs H<sub>o</sub>, H<sub>i</sub></td><td></td></tr><tr><td>1. create virtual service I<sub>s</sub>={φ,R.P<sub>in</sub>, 0}, O<sub>s</sub>={R.P<sub>out</sub>, φ, 0}</td><td></td></tr><tr><td>2. set I<sub>s</sub>.complete_time=0</td><td></td></tr><tr><td>3. for each p ∈ I<sub>s</sub>.output do</td><td></td></tr><tr><td>4. add e<sub>p</sub> to H<sub>o</sub></td><td></td></tr><tr><td>5. add I<sub>s</sub> to H<sub>o</sub>.e<sub>p</sub></td><td></td></tr><tr><td>6. EnQueue(Q,p)</td><td></td></tr><tr><td>7. end for</td><td></td></tr><tr><td>8. while Q!=NULL</td><td></td></tr><tr><td>9. p= DeQueue(Q)</td><td></td></tr><tr><td>10. while ∃ service s which input includes p</td><td></td></tr><tr><td>11. if s complete_time&lt;s.response_time+min(H<sub>o</sub>.e<sub>p</sub>.s complete_time)</td><td></td></tr><tr><td>12. s complete_time=s.response_time+min(H<sub>o</sub>.e<sub>p</sub>.s complete_time)</td><td></td></tr><tr><td>13. end if</td><td></td></tr><tr><td>14. if e<sub>p</sub> not in H<sub>i</sub></td><td></td></tr><tr><td>15. add e<sub>p</sub> to H<sub>i</sub></td><td></td></tr><tr><td>16. end if</td><td></td></tr><tr><td>17. add s to H<sub>i</sub>.e<sub>p</sub></td><td></td></tr><tr><td>18. if all p ∈ s.input exist e<sub>p</sub> in H<sub>o</sub></td><td></td></tr><tr><td>19. for each p ∈ s.output do</td><td></td></tr><tr><td>20. add e<sub>p</sub> to H<sub>o</sub></td><td></td></tr><tr><td>21. add s to H<sub>o</sub>.e<sub>p</sub></td><td></td></tr><tr><td>22. EnQueue(Q,p)</td><td></td></tr><tr><td>23. end for</td><td></td></tr><tr><td>24. end if</td><td></td></tr><tr><td>25. end while</td><td></td></tr><tr><td>26. end while</td><td></td></tr></tbody></table>

## 4.2 Pruning Strategy

After the hyper-graphs is generated, they should be pruned to remove the useless vertexes and edges. Fig. 4 shows the pruning strategy. By this way, the search space and the time of composition time can be reduced. Before the pruning strategy is applied, the redundant vertexes of $H_i$ should be deleted and the edge order of the $H_i$ should be adjusted first. We arrange the edges which contain the service $O_s$ at last (line 1-2). By doing this, the pruning strategy can be applied from the last to first of $H_i$. The edges of $H_i$ which contain $O_s$ should be reserved and all vertexes except $O_s$ in the edge should be deleted. On the other hand, the edges of $H_i$ which do not contain $O_s$ will only reserve the vertex which has the minimal complete time and all other
vertexes will be deleted. After the edge of $H_o$ is pruned, the edge of $H_i$ which has the same subscript will be pruned. Then we will get two pruned hyper-graphs after $H_o$ and $H_i$ are pruned. Fig. 5 shows the pruned hyper-graphs of Fig. 1.

<table><caption>Fig. 4. Pruning Algorithm</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Prune</td><td></td></tr><tr><td>Input: Hyper-Graphs $H_o$, $H_i$</td><td></td></tr><tr><td>Output: Hyper-Graphs $H_o$, $H_i$ after pruned</td><td></td></tr><tr><td>1. delete all vertexes from $H_i$ which not in $H_o$</td><td></td></tr><tr><td>2. sort the edges $H_i.e$ to make all edges $e \supseteq O_s$ have max subscript</td><td></td></tr><tr><td>3. for i=number of edges in $H_i$ to 1 do</td><td></td></tr><tr><td>4. if $H_i.e_i = \emptyset$</td><td></td></tr><tr><td>5. delete $H_i.e_i$</td><td></td></tr><tr><td>6. delete $H_o.e_i$</td><td></td></tr><tr><td>7. continue</td><td></td></tr><tr><td>8. end if</td><td></td></tr><tr><td>9. if $H_i.e_i \supseteq O_s$</td><td></td></tr><tr><td>10. $s_i = O_s$</td><td></td></tr><tr><td>11. else</td><td></td></tr><tr><td>12. $s_i = \min\_complete\_time(H_i.e_i)$</td><td></td></tr><tr><td>13. end if</td><td></td></tr><tr><td>14. delete all vertexes except $s_i$ which in $H_i.e_i$ from $H_i.e_i$</td><td></td></tr><tr><td>15. $t = s_i(complete\_time) - s_i(response\_time)$</td><td></td></tr><tr><td>16. $s_o = s$ whose complete\_time = $t$ and $s \in H_o.e_i$</td><td></td></tr><tr><td>17. delete all vertexes except $s_o$ which in $H_o.e_i$ from $H_o.e_i$</td><td></td></tr><tr><td>18. delete all vertexes except $s_o$ which in $H_o.e_i$ from $H_i.e_i$</td><td></td></tr><tr><td>19. end for</td><td></td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Fig. 5. Pruned $H_o$ and $H_i$</figcaption></figure>

## 4.3 Solution Generation

Solution Generation is used to generate the composite service of the request. After applying the pruning strategy to $H_o$ and $H_i$, we get two pruned hyper-graph. The every edge of pruned $H_o$ and $H_i$ must have and only have one vertex. Furthermore, the number of edges of $H_o$ and $H_i$ is equal. So we can get the $i^{th}$ edge of $H_o$ and the $i^{th}$ edge of $H_i$.
edge of $H_i$, and then link the vertexes of two services in the edges. This is an edge in composite service. Combining all edges which we get, the composite service is generated. Fig. 6 shows the solution generating algorithm and Fig. 7 gives the composite service of Example 1.

### Solution_Generate

Input: Hyper-Graphs $H_o, H_i$

Output: Composite Service CS

1. Graph $CS=\phi, temp=\phi$

2. for $i=1$ to number of edges in $H_o$ do

3. get $s_o$ from $H_o.e_i$

4. get $s_i$ from $H_i.e_i$

5. add $s_o$ to temp

6. add $s_i$ to temp

7. add edge $<s_o, s_i>$ to temp

8. $CS=combine(CS, temp)$

9. $temp=\phi$

10. end for

11. return $CS$

<figure><img src="image_5.png" /><figcaption>Fig. 7. Composite Service</figcaption></figure>

# 5 Experiments and Results

To evaluate the performance of our method, we have developed some experiments. And our evaluation consists of two parts. First, we compare SUTB [4] with our method by the precision and composition time. Then we carry out some experiments on the test sets which are generated by the WSC 2009 Testset Generator to evaluate the method furthermore. This generator has three input parameters: concept number, service number and solution depth. In order to prove the scalability and efficiency of our algorithm in different and even extreme conditions, we generate five groups of test sets which have solution depth 10, 15, 20, 25 and 30 respectively. And each group contains three subgroup of different ratio of concept number and service number. We generate service number of test sets from 4000 to 20000 to make sure that our method has good scalability. Furthermore, we conduct experiments on each test set several times to get the average values. All experiments were performed on a PC platform with a Intel® Core™2 Duo 2.33GHz CPU, Windows XP, and 2 GB RAM and all algorithms were implemented in Java.
## 5.1 Compare with SUTB

We use the 5 Testsets of WSC'09[19] to evaluate the precision and composition time of SUTB and HGSC(Hyper-Graph based Service Composition). The composition time is shown in Fig. 8. The composition time of SUTB is increased sharply from TestSet01 toTestset05. But it is not true for HGSC. The composition time of HGSC has little changed. On the other hand, from Table II, the precision of HGSC is 100% while SUTB is only 20%. So we can conclude that HGSC has a better scalability and precision.

<figure><img src="image_6.png" /><figcaption>Fig. 8. Composition Time of WSC'09 TestSet</figcaption></figure>

<table><caption>TABLE 2. PRECISION OF SUTB AND HGSC</caption><thead><tr><td>TestSets</td><td>SUTB</td><td>HGSC</td><td>Optimal QoS</td></tr></thead><tbody><tr><td>TestSets01</td><td>780</td><td>500</td><td>500</td></tr><tr><td>TestSets02</td><td>2100</td><td>1690</td><td>1690</td></tr><tr><td>TestSets03</td><td>760</td><td>760</td><td>760</td></tr><tr><td>TestSets04</td><td>2070</td><td>1470</td><td>1470</td></tr><tr><td>TestSets05</td><td>4500</td><td>4070</td><td>4070</td></tr></tbody></table>

## 5.2 Experiments with Other Testsets

We use WSC 2009 Testset Generator to generate more testsets and evaluate HGSC furthermore. Fig. 9 shows the experiment results with different service number (4000-20000), concept number (8000-200000) and solution depth (10-30). From Fig. 9, we can find that the maximum composition time of HGSC is less than 180ms. In addition, with the change of service number, concept number and solution depth, the composition time varied little. So the HGSC has good scalability and can be applied in large number of service and concept.
<figure><img src="image_7.png" /><figcaption>(a) Solution Depth=10</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(b) Solution Depth=15</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(c) Solution Depth=20</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(d) Solution Depth=25</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>(e) Solution Depth=30
Fig. 9. Composition Time of our method</figcaption></figure>

# 6 Conclusion and Future Work

To handle QoS-aware service composition automatically and efficiently, a QoS-aware hyper-graph based method is proposed in this paper. We show how to model the service composition problem as a hyper-graph and give the algorithms of generating hyper-graph, pruning strategy and solution generating. At last, to address the scalability, precision and performance of our method, some experiments are conducted and results show that our method has good scalability, efficiency and 100% precision.

In future work, we plan to develop the method in a distributed way.

# Acknowledgment

This work has been supported by the National Natural Science Foundation of China under Grant No. 61003253; the Natural Science Foundation of Shandong Province of China under Grant No. ZR2010FM031, ZR2010FQ010.

# References

[1] Tsur S, Abiteboul S, Agrawal R, Dayal U, Klein J, Weikum G, "Are Web services the next revolution in e-commerce?" In: Proceedings of the VLDB conference, Rome, September 2001, pp 614–617

[2] Freddy L'ecu, "A Formal Model for Semantic Web Service Composition" In: ISWC 2006, 2006.

[3] G. Canfora, M. D. Penta, R. Esposito, and M. L. Villani. An approach for qos-aware service composition based on genetic algorithms. In GECCO, pages 1069–1075, 2005.

[4] S. V. Hashemian and F. Mavaddat. A graph-based framework for composition of stateless web services. In ECOWS, pages 75–86, 2006.

[5] S. McIlraith and T. Son. Adapting golog for composition of semantic web services. In KR2002, pages 482–493, Toulouse, France, April 22-25 2002.

[6] E. Sirin, B. Parsia, D. Wu, J. Hendler, and D. Nau. Htn planning for web service composition using shop2. Web Semantics: Science, Services and Agents on the World Wide Web, 1(4):377–396, October 2004.
[7] T. Yu, Y. Zhang, and K.-J. Lin. Efficient algorithms for web services selection with end-to-end qos constraints. ACM Trans. Web, 1(1):6, 2007.

[8] L. Zeng, B. Benatallah, A. Ngu, M. Dumas, J. Kalagnanam, and H. Chang. Qos-aware middleware for web services composition. IEEE Transactions on Software Engineering, 30(5):311–327, May 2004.

[9] A. Zhou, S. Huang, and X. Wang. Bits: A binary tree based web service composition system. Int. J. Web Service Res., 4(1):40–58, 2007.

[10] N. Milanovic and M. Malek. Search strategies for automatic web service composition. Int. J. Web Service Res., 3(2):1–32, 2006.

[11] P. Bartalos and M. Bielikova. Semantic web service composition framework based on parallel processing. In CEC’09, Vienna, Austria, 2009.

[12] L. Zeng, B. Benatallah, A. Ngu, M. Dumas, J. Kalagnanam, and H. Chang. Qos-aware middleware for web services composition. IEEE Transactions on Software Engineering, 30(5):311–327, May 2004.

[13] T. Yu, Y. Zhang, and K.-J. Lin. Efficient algorithms for web services selection with end-to-end qos constraints. ACM Trans. Web, 1(1):6, 2007.

[14] J. Liu, N. Gu, Y. Zong, Z. Ding, S. Zhang, and Q. Zhang. Web services automatic composition based on qos. In ICEBE ’05, pages 607–610, 2005.

[15] X. Wang, S. Huang, and A. Zhou. Qos-aware composite services retrieval. J. Comput. Sci. Technol., 21(4):547–558, 2006.

[16] M. Naseri and A. Towhidi. Qos-aware automatic composition of web services using ai planners. In ICIW ’07, page 29, 2007.

[17] Zhou Zhu, James Bailey, "Fast Discovery of Interesting Collections of Web Services," wi, pp.152-160, 2006 IEEE/WIC/ACM International Conference on Web Intelligence (WI'06), 2006.

[18] Danilo Ardagna, Barbara Pernici, "Adaptive Service Composition in Flexible Processes," IEEE Transactions on Software Engineering, vol. 33, no. 6, pp. 369-384, June 2007.

[19] Srividya Kona, Ajay Bansal, M. Brian Blake, Steffen Bleul, Thomas Weise, "WSC-2009: A Quality of Service-Oriented Web Services Challenge," cec, pp.487-490, 2009 IEEE Conference on Commerce and Enterprise Computing, 2009