Reliable Web Services Selection Based on Finite State Machine Model

INTRODUCTION

---

A WS is a software system identified by a Uniform Resource Locator (URL), whose public interfaces and bindings are defined and described using XML-based specifications (or standards). Its definition can be discovered by other software systems. These systems may then interact with the WSs in a manner prescribed by its definition, using XML-based messages conveyed by Internet protocols (Booth et al., 2004). In order to create the actual application, developers may compose some existing simple services provided by the system to resolve complex user problems. In the process of WSC, suitable candidates must be discovered and from them the most suitable ones must be selected (Shen et al., 2010).

Generally, the Web service composition can be viewed as a three-step process: (1) composite Web service specification, (2) selection of the component Web services and (3) execution of the CWS.

At the first step, the user submits the goal he/she wants the composite service achieves, along with some constraints and preferences that need to be satisfied (Ding et al., 2005, 2007). Most works regard a WS as the basic unit for composition. However, a WS may comprise multiple operations such that their invocation sequence is constrained. During the second step, component WSs fulfilling the user’s goal are selected among a set of available services (Haddad et al., 2010). With more and more WSs with similar or identical functionality become available, the Quality of Service (QoS) attributes (e.g., availability, response time and throughput) are subsumed as non-functional attributes. But when more and more WSs become available, WSs selection problem is a complex NP-hard optimization problem. At the third step, execute all selected component Web services.

In order to define the possible orders of calling WSs at design time, many composition methods also have been proposed. Current service composition approaches include practical languages, such as BPEL, WSCL and OWL-S and commercial service platforms or products, such as the Sun ONE framework based on J2EE, Microsoft.NET, the Oracle BPEL Process Manager, the HP WSs Management Platform and the IBM WebSphere Application Server. At the same time, several formal process models have also been proposed, including FSM, Petri net, UML, activity diagram and process algebra. They are compared among each other with respect to some key requirements, including composition correctness, automatic composition and scalability (Ding et al., 2008). In fact, most works regard a Web service as the basic unit and selection with end-to-end for composition, however, a WS may comprise multiple operations that are invoked in sequence (Hwang et al., 2008). By the comparison, FSM is a promising model and suitable to address most of the aforementioned requirements issues. Moreover, a FSM is a formalism that is suitable to describe reactive behaviors and has the notion of states which is useful for monitoring service executions (Yu et al., 2007). So, some works model Web services as finite state machine.

Hu and Wang (2004) first model WSs as FSMs and then in order to avoid some problems as deadlock, they deliver the process of composition into three parts according to the merging process: constraints before composition, constraints in composition and constraints after composition. Hwang et al. (2008) model WSs and CWS as FSMs, then propose a metric, called aggregated reliability, to measure the probability that a given state in a composite WS will lead to successful execution in an error-prone environment. Although they propose a powerful method to compute the aggregated reliabilities, when the number of atomic WSs becomes huge, calculating the all aggregated reliability is impractical, because it may take too much time. Berardi et al. (2003) model WSs as Finite State Automations (FSA). In order to take time constraints into account, then they add a time into the tuple of the FSA. At last, a new XML-based language, namely WSTL (Web Service Transaction Language) that integrates well with standard languages in order to completely specify Wss is presented. Considering automatic Web services composition is the ultimate goal of most composition efforts, so, based on their previous work, Berardi et al. (2004) present a framework that describes a Web service’s behavior as an execution tree and then translates it into a FSM. They propose an algorithm that checks a composition’s existence and returns one if it exists. In the process, the composition is proved correct and the algorithm’s computational complexity characterization is given, ensuring that the automatic composition will finish in the finite number of steps. But, the authors cannot further research the WSC selection problem based on the model.

Although these articles have modeled Web services as FSMs, only Hwang et al. (2008) introduced a selection method to WSC based on a criterion of QoS, reliability. However, they ignore that the number of atomic WSs is huge or the WSs may comprise multiple operations will induce WSC selection become inefficient. In other words, when we model a WS as multiple operations that are invoked in sequence, we still need to consider how to select a feasible CWS to execute within reasonable time. At present, some articles focus on the selection optimization problem of WSC.

Zeng et al. (2004) proposed a method to compute an optimal set of WSs for each possible execution path in the process based on a weighted combination of QoS measures, including: price, duration, reputation, availability and successful rate. Although integer programming is utilized to accelerate the computation, with the number of possible execution paths become huge, the selection process may become impractical.

Yu et al. (2007) model the WSC selection in two ways: combinatorial model and graph model. The combinatorial model defines the problem as a Multidimension Multichoice 0-1 Knapsack Problem (MMKP). The graph model defines the problem as a Multiconstraint Optimal Path (MCOP) problem. Efficient heuristic algorithms for service processes of different composition structures are presented in this article. At last, this study proposed a broker-based architecture to select the QoS-based services.

Different articles have different methods for addressing the selection problem. Jaeger et al. (2005) draw a conclusion to some selection algorithms, including: Greedy Selection, Discarding Subsets, Bottom-Up Approximation and Pattern-wise Selection. But because of the different WSC model, these algorithms are not suitable to the problem above-mentioned.

This study extends our previous work presented by Shen et al. (2010), where firstly an algorithm is proposed to create the WSCT. Then, a heuristic algorithm is presented to complete the selection of WSs based on the given WSCT. According to WSCT features, an effective heuristic function is designed. Moreover, an approximate solution is generated to get an execution path of WS composition within a reasonable period of time and the reliability of the execution path is feasible to user.

In this study, with the number of available WSs becomes huge, constructing the WSCT will spend much time. So, in order to further decrease the time of selecting the execution path, a backtracking algorithm is proposed to select a feasible execution path. According to the CWS and the WS community, a feasible execution path can be selected without constructing the whole WSCT to satisfy the requirement of users in reasonable time. And some improvements are made in the heuristic algorithm in the previous work.

PROBLEM DESCRIPTION

The selection problem about WSC has become a focus in the filed. Generally, most works regard a WS as the basic unit and compose CWS end to end, then, according to various QoS measures, such as response time, cost and reliability, users can select the suitable WSs (Zeng et al., 2004; Yu et al., 2007).

Fig. 1:	A composition problem: buy a PC service

Fig. 2:	Composite WS and WS community

However, a WS may comprise multiple operations in practice that are invoked in sequence. So, the WS can be modeled as a FSM with tuples including state, operations and others (Hwang et al., 2008).

The state of a service (atomic service or CWS) describes the changes of its behavior and the state can transfer by the invocation of the operation. Depending on specific research topics, the state can be (a) the actual internal execution state, (b) only a part of the state of relevance to the parties connected with the WSs or (c) the state of the “external world”. Furthermore, different models rely on different kinds of “operation” to change state, these might be (i) messages, (ii) activities and (iii) events (Gerede et al., 2004).

Here, two definitions are articulated for technical discussions which include a FSM approach to model a WS and the definitions of WSC. The definitions come from Hwang et al. (2008) which are not repeated here.

This study consider a CWS W₀, a WS community C consists of the atomic Wss and the WS community C = {W₁, W₂, …, W_n}.

Suppose we intend to buy a Personal Computer (PC) in a commercial web site, we would like to develop a shopping service such that users apply to buy a PC and then pay for it, at last, the PC will be delivered to the users and we would like to be flexible on the payment. So, users can pay either by money order or by credit card, then users can deliver the PC by land, the example is shown in Fig. 1.

Here, a WS Community C = {W₁, W₂, W₃, W₄, W₅} is given as shown in Fig. 2. W₀ is the buying a PC service in the Fig. 1. Consider the composition W₀ shown in Fig. 2, to select the delegation to invoke for the operation o₁, there are three choices: W₁.o₁, W₂.o₁ and W₅.o₁. Here, WSs consist of a sequence operations that is say, in the W₁, after the o₁, o₂ and o₃ are invoked successfully, the o₄ can be used and after all operations are invoked, the WS can be invoked.

In the Fig. 2, according to the WS composite W₀ and the atomic WS community C, we can get the composite WSs set to meet the user requirements, for example, the set {W₁} can meet the composite WS W₀, at the same time, the set{W₂, W₃} also meet the composite WS W₀. So, one suitable set need to be selected for user in the acceptable time according to the reliability criteria.

WEB SERVICES COMPOSITION AND SELECTION

WSCT: In fact, the Web service composition can be viewed as a three steps process, the first step is composite Web service specification. In this study, the composite Web service specification is to create the service composition tree and the general process of constructing the service composition tree by iterating following operations is: 1) search WSs whose inputs contain the given input, 2) attain outputs of the selected WSs, 3) search input matched to the selected output as the given input in the operation. At last, search the composition result from service composition tree (Chen et al., 2006).

According to the definition mentioned above, the general process of combination of services actually is to produce a tree and then select a suitable path to execute in order to meet the requirement. So, this study introduce the process of building the WSCT according to service requester’s composite WS W₀ and candidate atomic WSs in the WS community. Different from the enumeration method by Chen et al. (2006), in this study, an algorithm is proposed to build a WSCT from back of WSs operation sequence. Due to operation set is a sequence in an atomic WS, only previous operations are selected to invoke, can the subsequent operations be selected which can avoid the exhaustion to all operations of WSs. So this study builds WSCT from back which can reduce search space slightly. For example, in Fig. 2, before operation o₄ in the W₁ is invoked by the application, operation o₂ or o₃ in the W₁ must be selected.

The main idea of algorithm 1 is as follows, search all possible nodes contain the given requirement from back of the Wss sequence and define a previous operations set for each candidate node. By the previous set of each candidate node algorithm 1 know whether the candidate node is a feasible node. When creating a WSCT, the node of WSCT includes one or more operations.

Here we give some signs introduction in the algorithm 1, S_CBI is a set to store nodes which can be invoked that is to say, their previous node have been invoked and you only can invoke the needful node from the S_CBI as the S_C. S_C is the candidate node set which include the nodes can be selected as part of the CWS. S_C is a subset of S_CBI. A node has previous nodes set S_P. When operations in the node will be invoked, the S_P of the node must be invoked firstly and the S_P can be used to judge whether the execution path is feasible at current state. If the S_P of the node can not be selected at next step, the S_P of the node must be added into the S_P of children of the node. S_OS [i] is the operation node set of the ith state in a WS. W_i. S_OS [i] is a node set of ith state in the W_i, for example, in W₁ operations set of the second state is W₁.S_OS [2] = {W₁.o₂, W₁.o₃}. Pop is the functions that gets a node from set or queue or stack and delete the node. GetPreviousOp is the function that gets the previous operation node. And root is the root node of the WSCT.

The description of algorithm 1 is as follows.

Initialization: Firstly, create a null node root as the root node of WSCT and push the root node of WSCT into the queue Queue; put all the last state operations of atomic WSs in the WS community into the S_CBI, set the S_P of root node of WSCT as null, i is state of CWS.

Step 1: Get a node from Queue as the parent node (line 2) and get all candidates as S_C (line 4 to 13), the process is: if the S_P of parent node is null, we do not need to consider the nodes in S_P, so, the S_C is the intersection of S_CBI and W₀. S_OS [i] (line 4 to 5), else we get the candidate nodes from S_P, so, S_C is intersection of S_P and W₀. S_OS [i] (line 6) and if the S_P have nodes but have no suitable candidate nodes (line 7), in other word, S_P of parent node will be used later, we still need to find the candidate nodes from S_CBI, so S_C is the intersection of the set of S_CBI and the set of W₀. S_OS [i] (line 8), meanwhile, the nodes in S_P of parent node must be added into the previous node set of candidate node (in fact, they are also children nodes of parent node) in order to be used later (line 9) and remove the unfeasible candidate nodes according to the previous set (line 10 to 11).

Step 2: Set all nodes in the S_C as the children node of parent node and push the children nodes into the Queue (line 18) and go the next state (line 23 to 25). Iterate the step 1 and 2 till the whole WSCT is returned.

Algorithm 1:	CWSCT: Create the WSCT

In Fig. 2, we create the WSCT from back, firstly there are nodes {W₁.o₄} and {W₂.o₄} as the candidate nodes and their previous set is {W₁.o₂ or W₁.o₃} and {W₂.o₁} each other, at the same time, we set {W₁.o₄} and {W₂.o₄} as the children nodes, then go the next step, we get W₁.o₄ or W₂.o₄ as the parent node each other, if firstly we get {W₂.o₄} as the parent node, the candidate nodes is {W₃.o₂ or W₃.o₃, W₄.o₃ and W₅.o₃}, their previous set is Ø, Ø and {W₅.o₁}, since the previous set {W₁.o₄} of {W₂.o₄} can not be selected as candidate node, so the previous set {W₁.o₄} of {W₂.o₄} must be added into previous set of its children nodes, so the previous set of {W₃.o₂ or W₃.o₃}, {W₄.o₃} and {W₅.o₃} is {W₂.o₁}, {W₂.o₁} and {W₅.o₁, W₂.o₁} each other, here, because there are two o₁ coming from different WSs in the previous set of {W₅.o₃}, so the {W₅.o₃} will be delete from the candidate node set. At last, iterate the process till returning the whole WSCT.

Figure 3 shows the WSCT based on algorithm 1 according to W₀ and the atomic WSs in Fig. 2. Dotted line frame is the wrong path that is removed by the algorithm 1. According to composite WS W₀, we can use some atomic WSs from the WS community to get some execution paths that meet the composite WS W₀, when the number of atomic WSs becomes large, calculating all the reliability of all WSC execution paths may take too much time and thereby we give a heuristic algorithm to select the WSs for composite WS.

Fig. 3:	The WSCT of Fig. 2 created by the algorithm 1

In Table 1 we can see that each path from root to leaf node can meet the requirement of CWS. So we must select a path to execute the CWS according to the QoS. Here, we consider a QoS property, reliability. The reliability of a service is the probability that a request is correctly responded within the maximum expected time frame (Zeng et al., 2004). Moreover, Hwang et al. (2008) proposed a service metric called aggregated reliability, to measure the probability that a given state in a composite WS will lead to successful execution in an error-prone environment. Although proposed powerful method to compute the aggregated reliabilities, if the number of atomic WSs becomes huge, calculating the all aggregated reliability is impractical, because it may take too much time. So we propose a heuristic algorithm to select the WSC based on WSCT above mentioned and difference from Hwang et al. (2008), in this study, the reliability of a whole execution path of composite WS is a product of reliability of all operations.

Definition 3 (Reliability): Given a composite WS W₀ and a WS community C = {W₁, W₂, …, W_n }, the Reliability of W₀ using C is R (W₀) = Π R (W_i.o_j), 1≤i, j≤n, where:

•	R (W0) is the Reliability of CWS W0
•	R (Wi.oj) is the Reliability of operation oj in the service Wi

Using Heuristic Algorithm (HA) to Select the WSC Based on WSCT: Generally, the heuristic evaluation function will be used to evaluate and find the suitable path from the current node to the goal node. Heuristic evaluation function consist of two parts, one part is viewed as G (x), standing for known information, another one is H (x), standing for the unknown information. Our proposed solution to select the suitable composition is utilizing a Heuristic Evaluation Function (HEF) to evaluate the reliability of the path from current node to the goal node current node and then select the suitable path according to heuristic evaluation function.

Designing appropriate heuristic evaluation function is very important to the heuristic algorithm. In order to design better heuristic evaluation function, we must try our best to gain known information. So, we analyze the execution tree of the WSC selection. In this study, we define heuristic evaluation function as the function that evaluates the reliability of the path from the current node to the goal node. The evaluation of path from current node to the goal node is divided into four parts. The definition of HEF as follows.

Definition 4 (HEF): Let HEF be a function F(x) = G₁ (x)xG₂ (x)xH₁ (x)xH₂ (x), where:

•	G1 (x) is the current node information
•	G2 (x) stand for nodes information that must be selected into WSC according to current node
•	H1 (x) is the next step node information and it is also the children node information of current node
•	H2 (x) is these nodes information that can not be considered in G1 (x), G2 (x) and H1 (x) but these nodes belong to the CWS

The value of G₁ (x), G₂ (x), H₁ (x) and H₂ (x) is the reliability of the part of path in the corresponding function. According to the WSCT we know that in atomic WSs, execution of some operations will induce the inevitable occurrence of a number of previous operations in the same atomic WS. For example, in Fig. 2, assumption that the operation W₂.o₄ be selected which will induce the inevitable occurrence of previous operation W₂.o₁ that is to say, W₂.o₁ must be selected into CWS W₀. Therefore, we consider that the information of selecting W₂.o₁ will be part of the heuristic evaluation function. Here the heuristic evaluation function includes two parts, one part is viewed as G (x), standing for known information and G (x) is divided into two parts, G₁ (x) and G₂ (x) (definition 3). Another part of the heuristic function is H (x) which also is divided into two parts, H₁ (x) and H₂ (x) (see definition 3). For example, in Fig. 3, we consider selecting the W₁.o₄ or W₂.o₄, if the W₁.o₄ is selected, the information of W₁.o₄ is the G₁ (x) and according to compare with W₀, W₁.o₂, W₁.o₃ and W₁.o₁ must be selected, so the information of W₁.o₂, W₁.o₃ and W₁.o₁ is the G₂ (x), according to WSCT, W₁.o₂ and W₁.o₃ also belong to the H₁ (x). Because there are the same operations o₂ and o₃ in G₂ (x) and H₁ (x), the operations are considered once. H₂ (x) does not have any operations here, so the reliability of H₂ (x) is 1. If the W₂.o₄ is selected, the information of W₂.o₄ is the G₁ (x) and according to comparison with W₀, W₂.o₁ must be selected, so the information of W₂.o₁ is the G₂ (x), according to WSCT, W₃.o₂ and W₃.o₃ is the H₂ (x) and H₁ (x) is empty, so, the reliability of H₁ (x) is 1.

After designing the heuristic evaluation function, the process of algorithm can be designed naturally.

Here we give some signs introduction in the algorithm 2 and 3. WSCT is the root node of WSCT. W_EP is a stack that is used to store the selected nodes. P_R is the reliability of the execution path in W_EP. S_CL is a set that store the children node of a parent node and node is a node. F_HEF is the value of function HEF.

The idea of algorithm 2 is as follows: firstly, calculating the reliability of each branch of according to current nodes, then by comparing them selecting the maximal branch and remove the other branch, at last, finish all selection of the nodes and get the WSC execution path and the reliability of the path.

The description of algorithm 2 is as follows.

Initialization: Set W_EP as null and set P_R is 1:

•	Step 1: If WSCT is not null, we get all children as the children set SCL (line 1 to 2)
•	Step 2: Calculate the HEF of all nodes in SCL (Algorithm 3), then push the suitable node into the WEP (line 3 to 5)
•	Step 3: WSCT point to the root of sub tree of WSCT and the root node of sub tree is node (line 6). And repeatedly the Step1 and 2 till the WSCT has no child and return the selected path WEP and the reliability PR of the path

Algorithm 2:	HS: Heuristic Select

The idea of algorithm 3 is as follows. Firstly, get the F_HEF of all nodes in S_CL according to definition of G₁(x), G₂(x), H₁(x) and H₂(x) and get the children node with maximal F_HEF, then return the node and the reliability P_R.

Algorithm 3:	CF: Calculate FHEF

The steps are as follows:

•	Step 1: Get a node as node from SCL (line 2) and get the value of G1(x), G2(x), H1(x) and H2(x)
•	Step 2: Get FHEF of all nodes in SCL according to G1 (x), G2 (x), H1(x) and get the children node with maximal FHEF in SCL.
•	Step 3: return node and PR of the node

Consider the composite WS W₀ and the WS community C = {W₁, W₂, W₃, W₄, W₅} shown in Fig. 2. For simplicity, like article Hwang et al. (2008), assume that each operation in node has the same chance to be selected, the children nodes have the same chance to be selected and has the same reliability 0.8, except for operations W₃.o₂, W₃.o₃ and W₄.o₃, whose reliabilities are all 0.75.

In Fig. 3, if W₁.o₄ is selected into the composite WS W₀, by comparison between the W₀ and W₁, we know that W₁.o₁, W₁.o₂ and W₁.o₃ must be selected into the execution path of WSC, so, we can calculate the G₂ (x) = R (W₁.o₁)x1/2x(R (W₁.o₂)+R (W₁.o₃)) = 0.64 W₁.o₄ is the current operation, so, G₁ (x) = R (W₁.o₄) = 0.8, here, because the next step selection operations also belong to the G₂ (x), so, H₁ (x) = 1 and there are no operations between W₀ and W₁. We define H₂ (x) = 1. So, F_HEF = 0.8x0.64x1x1= 0.512.

As discussion above, if W₂.o₄ is selected, we have G₂ (x) = R (W₂.o₁) = 0.8, G₁ (x) = R (W₂.o₄) = 0.8, we know that the next step selection operations are W₃.o₂, W₃.o₃ and W₄.o₃ according to WSCT as shown in Fig. 3. W₃.o₂ and W₃.o₃ have an equal chance to be selected, H₂ (x) =1/2x(1/2x(R (W₃.o₂)+R (W₃.o₃)) +1/2x(R (W₄.o₃)) = 0.75. and the different operations set is null, so H₁(x) = 1, then F_HEF = 0.8x0.8x1x0.75 = 0.48.

So, we select W₁.o₄ as the next step, we can continue till all steps are finished. At last, we can gain a feasible execution path {W₁.o₄, W₁.o₃ or W₁.o₂, W₁.o₁}.

Using backtracking algorithm (BA) to select the WSC: Although the heuristic algorithm can resolve the problem that select the suitable the execution path, the time that spend in the process of creating the WSCT still is too much. So we consider selecting a feasible execution path without creating the WSCT that is say, according to the merit of model, we can select a path to accomplish the requirement of users instead of firstly spending larger of time in creating WSCT and then selecting an optimal or approximately optimal path.

According to the analysis above, we still execute the WSC process from back. The process of select a feasible path by backtracking algorithm is: firstly, we get all possible candidate nodes and then according to the merits of WSs model we can attain each Selection Function (SF) of all candidate nodes, SF is used to evaluate the path including the current node. At last, we sort the candidate nodes according to the SF and select the best candidate node into WSC according to the value of the SF of candidates nodes, if the selected candidate node is failed in the future process, we will backtrack and select the second-best candidate node and iterate the process till we get a feasible execution.

In Fig. 2, for example, we consider selecting o₄. Firstly we get all possible candidate nodes, the set is {W₁o₄, W₂.o₄} and then we calculate the SF of each node in the set. Suppose we select the W₂.o₄ as the part of WSC according to the value of SF and if W₂.o₄ is failed in the future process, we will backtrack that is say, we will select W₁.o₄ to replace the W₂.o₄ and remove the WSs including W₂.o₄ in WS Community then iterate the above process till we get a whole feasible path.

Now we introduce how to calculate the selection function SF(x).

Definition 5 (SF): Let SF be a function SF (x) = G₁ (x)xG₂ (x)xH (x), where:

•	G1 (x) is the current consideration node information
•	G2 (x) stand for nodes that must be selected into WSC according to current node information
•	H (x) is these operations information that can not be considered in G1 (x), G2 (x)

Different from Definition 4, since we do not create the WSCT, we can not know the next step node information, then we can not divide the H (x) into two parts. When we consider selecting o₄, we can get all possible candidate operations set which is {W₁.o₄, W₂.o₄}. Assumption that the operation W₂.o₄ be selected into the WSC which will lead to the inevitable occurrence of operation W₂.o₁ that is to say, W₂.o₁ must be selected into WSC. So, the information of W₁.o₄ belong to G₁(x) and the information of W₂.o₁ belong to G₂(x). Since we do not know the next step node information, we do not know where the o₂ or o₃ come from, so the next step nodes of W₂.o₄ is all possible nodes in the set {W₃.o₂ or W₃.o₃, W₄.o₃, W₅.o₃}, we denote the average value of them as the information of H (x). At the same time, if the W₁.o₄ is selected, information of W₁.o₄ belong to G₁ (x) and according to the W₀ and W₁, the information of set {W₁.o₁, W₁.o₂, W₁.o₃} belong to G₂ (x) and H (x) is empty, so the reliability is 1.

Here we give some signs introduction in algorithm 4 to 6: Q_OQ [i] is an ordered queue that stores the backtracking candidate nodes in the ith state, SF is the value of function SF (x).

The general idea of algorithm 4 is as follows: we still select the suitable nodes of each state from back, by calculating SF (x) of each candidate node in the same state, we can sort order to them, then, we select the candidate node that has the maximal SF (x), if we need backtrack, we select second maximal one, repeatedly till there are no any candidate node in the same state, then we backtrack to the previous state, repeatedly steps mentioned above. At last, we can get a feasible WSC execution path.

The description of algorithm 4 is as follows.

Initialization: push the root into the W_EP, we put all the last state operation nodes of atomic Wss in the WS Community into the S_CBI, set S_P of root as null. For example, at first, in Fig. 2, S_CBI = {W₁.o₄, W₂.o₄, W₃.o₂ or W₃.o₃, W₄.o₃ and W₅.o₃}:

•	Step 1: Get a node as node from WEP (line 1) and get candidate nodes set SCS of next state (line 4 to 11)
•	Step 2: If need backtrack, see algorithm 6, or get the candidate node have maximal SF (x), (algorithm 5), then repeat the process till we get a feasible execution path WEP and PR of the WEP

Algorithm 4:	BTS: Backtracking select

The description of algorithm 5 is as follows:

•	Step 1: Get all SF of candidates in SC, (line 2 to) and push all SF into QOQ [i]
•	Step 2: Sort order to all SF by descending and return the QOQ [i]

Algorithm 5:	SF: Selection function

The description of algorithm 6 is as follows.

The algorithm 6 is the backtracking process, when the first maximal SF (x) need to be backtracked, because the Q_OQ [i] is a sort order sequence, we can invocate the second-best SF(x) in the same state, if there is not any other node in the Q_OQ [i] of ith state, we must backtrack to previous state (line 5 to 6) and repeatedly till we can get a substitute node and push node into W_EP as the replacement of node:

•	Step 1: If the QOQ [i] is not null, get a node as node from QOQ [i], (line 1 to 2)
•	Step 2: If the QOQ [i] is null, we go back the last state (line 6), WEP need to delete a node (we need to select the node again) and repeat Step 1

Algorithm 6:	BT: Backtracking

Similarly, we consider the composite WS W₀ and the WS community C = {W₁, W₂, W₃, W₄, W₅} shown in Fig. 2. As mentioned above, assume that each operation has an equal chance to be selected and has the same reliability 0.8, except for operations W₃.o₂, W₃.o₃ and W₄.o₃, whose reliabilities are all 0.75 and W₅.o₁ and W₅.o₃, whose reliabilities are all 0.95. We denote the R (W₁.o₂) as the reliability of the operation W₁.o₂.

In Fig. 2, at first, we have two choices about o₄, they are W₁.o₄ and W₂.o₄. Consider the W₁.o₄, G₁ (x) = R (W₁.o₄) = 0.8, selected into the composite WS W₀ and W₁.o₁, W₁.o₂ and W₁.o₃ must be selected into WSC, so G₂ (x) = R (W₁.o₂)x1/2x(R (W₁.o₂)+R (W₁.o₃)) = 0.64. By comparison between the W₀ and W₁, we know that there is not operation in H(x), so, H(x) = 1 and SF = G₁ (x)xG₂ (x)xH (x) = 0.512. On the other hand, W₂.o₄ is the current operation, so, G₁ (x) = R (W₂.o₄) = 0.8 and G₂ (x) = R (W₁.o₂) = 0.8, here, because the next step possible selection operations are {W₃.o₂, W₃.o₃, W₄.o₃, W₅.o₃} according to WSCT as shown in Fig. 3, so, H (x) = 1/3x(1/2x (R (W₃.o₂)+R (W₃.o₃))+1/3x(R (W₄.o₃)+1/3x(R (W₅.o₃)) = 0.82, then SF = G₁ (x)xG₂ (x)xH (x) = 0.523.

So, we select W₂.o₄ as the next step operation and then we continue to select the next step operation. The next operation set is {W₃.o₂ or W₃.o₃, W₄.o₃, W₅.o₃}. Similarly, the SF is {0.656, 0.656, 0.901}, we select W₅.o₃ but, in next step, because we have two optional operations W₅.o₁ and W₂.o₁, we need backtrack and we select W₄.o₃ or W₃.o₂ or W₃.o₃ to substitute W₅.o₃, then continue till all steps are finished. At last, we can gain a feasible execution path {W₂.o₄, W₄.o₃, W₂.o₁}.

EXPERIMENTS AND EVALUATION

In order to evaluate our proposed Heuristic Algorithm (HA) and Backtracking Algorithm (BA), two algorithms are compared with each other and with Exhaustion Method (EM). Exhaustion method traverses all the operations in the WSCT and then gets the execution path with best reliability. In our previous study, the heuristic algorithm have been compared with exhaustion method And then, we compared the three methods. The experiments are run on a PC configure with Intel Petium (R) IV 3.00 GHz CPU, 1G RAM.

Here we mainly evaluated the total reliability of the selected path and the selection time among exhaustion method, our proposed heuristic algorithm and backtracking algorithm.

In the first scenario, we firstly generated a composite WS with six states and twelve atomic WSs into the WS community. Then, we select a suitable CWS according to twelve atomic WSs and we carried out the experiment for ten groups in HA and EM and each group the operations reliability is generated by random from 0.8 to 1.0. Here, we do not consider the time of constructing WSCT and only compare the time of the selection of EM and HA. The experimental results are shown in Table 1. The x-axis stands for that we carry out the experiment for ten groups and the y axis stands for the WSC reliability of the total execution path and the data is shown in Table 1. Then on basis of the Table 1 we generated a composite WS with six states and seven WS communities with different number of atomic WSs from 10 to 22. We carried out the experiment according to different WS community for ten groups and got the average time of selecting an execution path. The experimental results are shown in Table 2 the x-axis stands for the number of atomic WSs and the y axis stand for the average time of the execution path is selected for ten groups by corresponding method, the data is shown in Table 2 and the unit of time is millisecond. Table 1 shows that the average reliability of the path selected by HA is about 95% reliability of the best execution path selected by EM and from the Table 2, when the number of atomic WSs is twelve, the average time of selection by HA is about one fourth of selection time by EM. In other word, we spend one fourth selection time by EM but we get about 95% precision. So, the execution path selected by our HA can meet the requirement of users and Table 1 shows that with the increasing of the atomic WSs, the selection time by HA is relatively stable and the selection time by EM increase obviously .

In the second scenario, we evaluate the three selection methods, we firstly still generate a composite WS with six states and twelve atomic WSs into the WS community and then, we applied three methods to select a CWS and considered the time of creating WSCT. Meanwhile, we carried out experiment for ten groups and each group the operations reliability is generated by random from 0.8 to 1.0. The experimental results Table 3.

Then, a composite WS with six states and seven WS communities with different number of atomic WSs from 10 to 22 are generated. Experiments are carried out to each WS community for ten groups and got the average time of selecting an execution path. The experimental results shown in Table 4.

Table 3 shows that the reliability of the path selected by EM, HA and BA for ten groups with different operations reliability. Results of experiments show that the reliability of execution path selected by BA is about 84% reliability of execution path selected by HA and about 81% reliability of execution path selected by EM. Although reliability of the execution path selected by our BA may be lower reliability than the best execution path selected by EM or the path selected by HA, the feasible path can be got in shorter time shown in Table 4.

Table 1:	The WSC reliability of the execution path for ten groups experiment

Table 2:	The time of selected by different number of atomic WSs
EM: Exhaustion method, HA: Heuristic algorithm

Table 3:	The WSC reliability of the execution path for ten groups experiment
BA: Backtracking algorithm

Table 4:	The time of selected by different number of atomic WSs

In the community with twelve atomic WSs, Table 2 shows that the time of selecting path is 16 ms but Table 4 shows that the time of including WSCT is 78 ms, so the time of creating WSCT is about 80% of whole time, in fact, when we get about 95% reliability of EM, we spend half selection time by EM, however, we spend one fifth selection time of EM in BA, then we can get about 81% reliability of EM. From Table 4 we can also see that time of selection by BA is relatively stable and much shorter than EM and HA. So, BA can find a feasible path with less time.