Abstract: To reduce the difficulty of binding a web service and improve the self-adaptability of service response, the concept of service cluster is proposed. A service cluster consists of a group of the services with similar functions and interfaces, by enlarging the grain of service requested, it can efficiently reduce the search space and improve the function compatibility. The algorithm to bind an appropriate web service in service clusters is presented. Logic service net constructed based on logic Petri net is put forward to describe the service flow based on service clusters. A judging theorem to test the soundness of a logic service net is also proposed in this study.
INTRODUCTION
With the development and maturity of service computing technology, the number of available web services is surging dramatically and the difficulty to search and bind a service is increased greatly. It needs to find another available service to substitute the current working service once the user request is slightly changed or the current working service is unavailable. To search and bind another available service is complicated since there are too many similar services on internet. For reducing the cost to bind a web service, some researchers propose a group of services as object of service request and response and they want to enlarge the grain of service requested to reduce the difficulty of searching an appropriate web service.
Some concepts are proposed to describe a group of services, such as service group (Maguire et al., 2006), service pool (Du et al., 2009a), service community (Budanitsky and Hirst, 2001) and service container (Benatallah et al., 2003). These concepts provide a group of services with the same functions and interfaces. However, they can not flexibly satisfy the service request with diversity and small differences.
A service cluster is proposed to define a group of web services with similar functions and interfaces in this study. The service clusters are different form the concepts mentioned above, web services included in a service cluster may have small differences in functions and interfaces and they can meet the diversity and difference of user’s requests to some extent. The service clusters can provide with good compatibility and self-adaptability.
The logic service net is put forward based on service clusters and logic Petri net. It can be used to describe the complicated service flows based on service clusters. Soundness is an essential property for a web service. A web service is sound means that it starts properly, provides service properly without interactive deadlock and stops properly. Thus whether a service flow is sound or not is directly related to whether the service flow can normally work. Test of soundness on the service flows are converted to judge the soundness on the logic service nets in this study.
SERVICE CLUSTER
Definition of service cluster: A service cluster is composed of a group of web services with similar functions and interfaces, web services in a service cluster may have different interfaces and quality parameters in expression.
Definition 1 (service cluster): A service cluster is a 8-tuple:
SC = (Id, F, f, I, O, SL, δ, Q)
where, Id is an identification of the service cluster, F is a description of its functions, f is an interface function, I and O are the sets of input and output parameters, SL is a set of services included in the service cluster, δ is a correlation function which makes a mapping between the interfaces of web services in SL and the service cluster and Q is a set of quality parameters.
Service quality parameters are key factors for binding a service in a service cluster and it may be formally defined as follows:
Definition 2 (service quality parameter): The service quality parameter q is a 5-tuple:
q = (N, CO, V, U, T)
where, N is a name of the parameter, CO is a comparison operator, V is a value of the parameter, U is a quality unit of the parameter, T is the type of service quality parameter. The value of T may be M or M' which represents the quality parameter is mandatory satisfied or not, respectively.
Service binding: Service binding is the process to search and bind an appropriate web service for the service request in a service cluster.
Service request is defined as 6-tuple:
Sr = (Id, F, f, I, O, Q)
where, each parameter in the 6-tuple has the same meaning with the definition of service cluster. The user should set parameter values of a service request before submitting it and a web service will be bound for the service request by computing similarity of the service request Sr and the web services included in the service cluster. Some definitions that will be used in the process of service binding are introduced as follows:
Definition 3 (included parameter): Let Pa and Pb be two different groups of parameters, Pa is called the included parameter of Pb if the follows hold:
| • | Num(Pa) = Num(Pb), where, Num(P) represents the number of parameters in P |
| • | ∀mi∈Pa, ∃nj∈Pb, such that
Type(mi) |
| If Pa is the included parameter of Pb, it is marked as Pa∠Pb. |
Definition 4 (isomorphic parameter): Let Pa and Pb be two different groups of parameters, Pa is called the isomorphic parameter of Pb if the follows hold:
| • | Num(Pa)=Num(Pb), where the meaning of Num() is the same as definition 3 |
| • | ∀mi∈Pa, ∃nj∈Pb, such that
Type(mi) |
| If Pa is the isomorphic parameter of Pb, it is marked as Pa⇔Pb. |
Definition 5 (satiable parameter): Let Pa and Pb be two different groups of parameters, Pb is called the satiable parameter of Pa if the follows hold:
| • | Pa∠Pb |
| • | ∀mi∈Pa, ∃nj∈Pb, such that Val(mi) ⊆Val(nj), where Val(m) represents the range of parameter value of m |
| If Pb is the satiable parameter of Pa, it is marked as Pa~Pb. |
Definition 6 (similarity of ontology concept): The semantic similar degree between the concept C1 and C2 is defined as:
where, Dist(C1,C2) represents the distance of C1 and C2, i.e., the number of edges in shortest path connected with C1 and C2 in the domain ontology tree, Distmax is the maximum distance of all concepts in the domain ontology tree and Distmin is the minimum distance of all concepts in the domain ontology tree (Sun and Jiang, 2008).
Quality of web services is a key factor for selecting an optimal service. Some quality parameters of web services are positive, such as capacity, reliability and cost; others are negative, such as response time and delay time. A larger value in positive parameters or smaller value in negative parameters denotes high quality of a web service. A method based on Simple Additive Weighting (SAW) (Yu, 1985) technique to estimate the quality of services is presented in the study and it is introduced to compute the quality score of a web service in this study.
Definition 7 (quality score): Let S = {s1, s2,…sm} be a group of web services. Assume each web service in S has N quality parameters and [qi1, qi2,…,qin] is the quality vector of web service si. The quality score of si is defined as follows:
| (1) |
| (2) |
| (3) |
There are two phases in applying such method, scaling phase and weighting phase. Equation 2 and 3 are used in scaling phase, where Eq. 2 is for negative parameters and Eq. 3 is for positive parameters. Equation 1 is used to compute the quality score of a web service in the second phase, where wj∈[0,1] and wj is the weight of qj set by the users.
A binding Algorithm 1 is presented to obtain an optimal service in a service cluster for the service request. It works as follows: First, it eliminates some web services whose interfaces are not consistent with service request by interface matching. Second, some web services are eliminated if their mandatory quality parameters are not the satiable parameters of service request by quality parameters matching. Thirdly, the similarity of ontology concept about F, I, O and similarity of quality parameters are computed and output the optimal web service in the service cluster for the service request.
| Algorithm 1: | The binding algorithm of service clusters |
An example to book tickets in e-commerce is presented in Fig. 1. Three service clusters are defined, namely book_tickets, pay_tickets and delivery_tickets. The web service Ti in book_tickets denotes a service w hich can book a train ticket, the service Pi denotes a service which can book a flight ticket. There are several services provided by different banks in the cluster of pay_tickets and the users can choose different bank to pay for their tickets. It includes a lot of web services provided by different express companies in the cluster of delivery_tickets, users can select an appropriate one to delivery their tickets according to the price or speed of these services.
| Fig. 1: | Service flow to book tickets oriented service clusters |
The user 1 may want to book a train ticket by the service flow of T2->B2->EC2 while the user2 want to book a flight ticket by the service flow of P2->B4->EC3. Once the service EC2 is unavailable, the system may conveniently and quickly find an alternative web service in the bund service cluster for user1 according his service request, the substitute service may be EC1 or other service. If user 1 want to book a flight ticket too, it only need find an appropriate service in the service cluster from the service group Pi.
LOGIC SERVICE NET
Service net unit: A Logic Petri Net (Du et al., 2007) is generated by appending the logical expression on transitions of traditional Petri Net. Logic Petri Net can be used to model and simulate system behaviors. Logic Petri Nets have been successfully applied to model and analyze the real-time cooperative systems (Du et al., 2007), e-commerce workflows (Liu et al., 2009a) and inter-organizational workflow systems (Liu et al., 2009b). It can also better exemplify the temporal properties, batch processing function and passing value indeterminacy (Du et al., 2008; Du et al., 2009b).
Definition 8 (service net unit): Service net unit is the graphic representation of a service cluster based on logic Petri net, it is composed of a service cluster transition, logic input transition, input place set, logic output transition and output place set.
The Fig. 2 is a service net unit. The black transition denotes a service cluster transition, the white transition labeled with I is a logic input transition, the logic input expression is fI = (p1Δp3)∧(p2Δp4), the symbol Δ denotes ∧ or ∨, p1Δp3 equals combination of p1∨p3 and p1∧p3. The white transition labeled with O is a logic output transition, the logic output expression is fo = p5∧(p6Δp7), p1, p2, p3 and p4 are input places, p5, p6 and p7 are output places. The service net unit represents a service cluster which can accept the input parameters {(p1, p2), (p1, p4), (p3, p2), (p3, p4), (p1, p3, p2), (p1, p3, p4), (p1, p2, p4), (p3, p2, p4), (p1, p2, p3, p4)}, the output parameters it can provide are {(p5, p6), (p5, p7), (p5, p6, p7)}.
Logic service net: The logic service net is a service flow net which uses service net unit to represent a service cluster and logic Petri net to represent the service process model. The formal definition of logic service net is introduced as follows:
Definition 9 (logic service net): LSN = (P, T, F, δST, I, O, M, SC) is a logic service net if the follows hold:
| • | SC is a set of service clusters to construct the process model of the service flow |
| • | P = Pc∪Pd is a finite nonempty set of places, where: |
| • | Pd is the data place, Pd is used to describe the data dependency between services | |
| • | Pc is control place, Pc is used to describe the flow dependency between services, two special control places are defined, the initial place i and the terminal place o, let •i = o• = ø |
| • | T = TS∪TI∪TO, T is a set of transitions, where Ts denotes a set of service net unit, TI denotes a set of logic input transitions; TO denotes a set of logic output transitions |
| • | δST is a mapping function, it establishes the mapping between Ts and SC, i.e. ∀t∈TS: δST (t) = s, s∈SC |
| Fig. 2: | An example of service unit |
The definitions of other parameters of logic service net and firing rules of transitions are the same as logic Petri net. The service clusters are firstly mapped into service units and these service units are connected by the logic transitions and formed as a logic service net.
The dotted line box in Fig. 3 shows a logic service net modeled for the service flow in Fig. 1, the logic service net is composed of three service net units which are ticket booking, ticket paying and ticket delivery. The left side and right side in Fig. 3 are the instantiate logic service nets of users, they interact with the logic service nets of ticket booking service and the service net unit has been replaced by concrete service transitions.
SOUNDNESS OF LOGIC SERVICE NET
The test on soundness of the service flow based on service clusters is converted into testing the soundness of its corresponding logic service net in this study.
Definition 10 (soundness of logic service net): Let LSN be a service net and assume all the exterior data requests can be satisfied and, the initial mark of LSN be M0 with M0(i) = 1. LSN is sound if and only if:
| • | ∀M∈R(M0), there exists a firing sequence α, such that <M,α>|=o |
| • | ∀p∈P-{o}, if M(o)=1 then M(p)=0 |
| • | ∀t∈T, ∃M∈R(M0), such that M[t > |
Definition 11 (service process net): Let LSN be a service net. Add a transition t* into LSN, such that •t*={o} and t*•={i}, let SPN = (P', T', F', δST, I, O, M',SC), where P' = Pc, T'=T∪{t*}, F'=F∪{oxt*∪t*xi}-{PdxT∪TxPd}, M' = M, SPN is called the service process net of LSN.
| Fig. 3: | A logic service net for booking tickets in e-commerce |
Let SN = (P', T', F', I, O) and SPN = (SN, M') denotes SPN introduced in the above definition.
Theorem 1: Let LSN be a service net and SPN be its service process net. LSN is sound if and only if SPN = (SN, M0') is live and safe.
Proof: First, the proof of sufficient condition is given as follows.
Since SPN = (SN, M0') is live, the condition (1) and (3) in definition 11 are correct by definition of live property in Petri net (Murata, 1989).
Given the hypothesis that condition (2) in Definition 10 is not correct and SPN = (SN, M0') is live and safe, i.e., ∃ p∈P'-{o}, such that M'(p)≠0 when M'(o)=1 and let M'(p)=1.
When M'(o) = 1, t* is enabled, let M'[t*>M'' , so M''(i) = 1. Since (SN, M0') is live, the token number in p must be added 1 with the running of SPN and then the token number in p will be 2, it will be conflict with the premise of (SN, M0') is safe, so the hypothesis is not feasible, i.e., condition 2 in Definition 10 is correct.
Since condition (1), (2) and (3) are all correct, LSN is sound by Definition 10.
Second, the necessary condition is proved as follows:
To prove (SN, M0') is live, it only need prove that ∀t∈T and ∀ M0∈R(M0'), ∃ M'∈ R(M'), such that M'[t>.
By condition (3) in Definition 10, ∀t∈T, ∃ M'∈R(M0'), such that M''[t>, it only need to prove ∀ M'∈R(M0'), ∃ M''∈R(M'). By condition (2) in Definition 10, for ∀ M', there exists a firing sequence α, it can reach the terminal place o first and then the initial place i by transition t*, so R(M0')⊂R(M'), with ∃ M''∈R(M0'), we can get the conclusion that M''∈R(M'). So LSN = (SN, M0') is live.
Given the hypothesis that (SN, M0') is not safe, i.e. ∃p∈ P'-{0,i}, such that M'(p)>1. By condition (1) in Definition 10, there is a firing sequence α, such that < M'(p),α>|=∈o and M'(p)>0. By condition (2) in Definition 10, there must be M'(p) = 0 when M'(o) = 1, this is conflict with M'(p)>0. So, the hypothesis is not correct and LSN = (SN, M0') is safe.
CONCLUSION
The concept of service cluster is put forward to respond the service request. It can make up for the lack in compatibility and self-adaptability of traditional single service response. To describe the complicate service flow based on service clusters, logic service net which is constructed based on service cluster and logic Petri net is proposed. From the logic Petri net, the service cluster is modeled as service net unit. Since logic expressions are appended on the input and output transitions, the service net unit can easily to represent a service cluster with diversified interfaces. The test of soundness of service flow is converted into to test the soundness of logic service net. From the judging theorem on soundness of the logic service net, it is easily to judge whether a service flow based on service clusters is sound.
ACKNOWLEDGMENTS
This study is supported by the National Basic Research Program of China under grant 2010CB328101; the National Natural Science Foundation of China under grants 61170078 and 61173042; the Doctoral Program of Higher Education of the Specialized Research Fund of China under grant 20113718110004; the Scientific and Technological Developing Program of Shandong Province of China under grants 2011GGX10114 and 2012G0020120; the Project of Shandong Province Higher EducationalScience and Technology Program under Grant number J12LN11; and the SDUST Research Fund of China under grant 2011KYTD102.