Abstract: With the development of information technology, the quantity of web services in internet has increased rapidly. The time complexity of service composition becomes higher. To solve this problem, a new method of service composition is proposed based on Enhanced Logic Petri nets (ELPNs) in this study. The main innovation is the construction of a composition library. The experiment in this study shows the time complexity of service composition is decreased. Firstly, web services and service compostion are modeled by ELPNs. Then, the reachability of ELPNs is analyzed. All cases of service composition are obtained based on the ELPNs model of service composition. A composition library is constructed. The method of service composition is proposed based on the composition library. Moreover, some theorems are given, such as enabled conditions of transitions, marking computing. Some algorithms are introduced, such as reachable markings, service composition and so on. Finally, the validity and advantages of proposed methods are illustrated by experiments and comparative analysis.
INTRODUCTION
With the development of information technology, the web service based on XML (Extensible Markup Language) has developed rapidly (D’Mello and Ananthanarayana, 2010). Web service is the computer program which is marked by the URL (Uniform Resource Locator). Web service can be used distributely on the cross-platform system. Because of the above advantages of web service, the quantity of services has increased rapidly (Liu et al., 2007). Meanwhile, the demands for web services are also increased. Moreover, there are many demands which can not be satisfied by a single web service. Thus, there is the problem that how to compose single web service to satisfy the user requirement. To solve this problem, the researches on service composition (Wang, 2011) were studied by scholars.
There have been already a lot of achievements on service composition. In order to minimize the duration of service compositon, the concepts of service clusters (Sheng et al., 2009) has been introduced. The services which are similar on inputs and outputs should be grouped when service composition (Deng and Du, 2012). In order to unify the rules of service composition, the concept of semantic was introduced into web service composition (Tao, 2012). The information representation can be unified base on the semantic vocabulary tree (Lei and Duan, 2009). Moreover, the types of service composition were given, such as simple service composition, labeled composition, parallel composition and hybrid composition (Deng and Du, 2013).
From the above researches, the main method for service composition is service discovery. When the demand is given by the user, the system would discover the web services from service clusters and compose them to the user (Xie, 2011). Howere, the quantity of services has increased rapidly. Web service providers have given a large number of services in the internet. Although, clustering services can minimize the cardinal number for service discovery, the total time complexity is high for service composition.
To solve the above problem, a new method of service composition is proposed based on Enhanced Logic Petri Nets (ELPNs) in this study. The innovation of this study has three aspects. Firstly, the composition library is constructed. All cases of service composition can be found from composition library. When the demand is given by the user, the system can found the case of service composition which can satisfy the user’s demand from composition library and not have to find web services from service clusters. The experiment in this study virified the time complexity of service composition is decreased. Secondly, the web services and service composition are modeled by ELPNs. Logic Petri Nets (LPNs) are the mathematical tool and suitable to describe batch processing function and passing value indeterminacy in cooperative systems (Du and Jiang, 2002; Du et al., 2011). The inputs, outputs and other aspects of web service have the characteristics of batch processing function and passing value indeterminacy. So, the web service can be modeled properly by LPNs (Du et al., 2008, 2009). Howere, it’s difficult to use LPNs to decscribe the case that the output and input places of a transition are all restricted by a logic expression at the same time. Thus, the ELPNs is introduced and defined in this study. The web services and service composition are modeled by ELPNs conveniently. Thirdly, the reachability of ELPNs is analyzed. Then, all cases of service composition are obtained from the ELPNs model of service composition. Moreover, the definitions of web serive and user’ demand are given. Some theorems are proposed, such as enabled conditions of transitions, marking computing. Some algorithms are introduced, such as reachable markings, service composition and so on. The validity and advantages of proposed methods are illustrated by some experiments and their comparative analysis.
ELPNs MODEL OF WEB SERVICE
The definitions of web service and ELPNs are showed in this section. The ELPNs model of web service is also introduced. A brief introduction of Petri Nets (PNs) (Hu et al., 2010a, b) is given as follows:
Definition 1: N = (P, T, F) is a net, where:
| • | P is a finite set of places |
| • | T is a finite set of transitions with P∪T ≠ Ø and P∩T = Ø |
| • | F⊆(PxT)∪(TxP) is a set of arcs |
| • | dom(F)∪cod(F) = P∪T, where: |
dom(F) = {xεP∪T|∃yεP∪T: (x, y)εF}
cod(F) = {xεP∪T|∃yεP∪T: (y, x)εF}
Definition 2: xεP∪T is a node in N = (P, T, F). •x = {y|(y, x)εF} denotes a pre-set of x and x• = {y|(x, y)εF} denotes a post-set of x. If X⊆P∪T, the pre-set and post-set of X are represented by •X = ∪xεX•x and X• = ∪xεXx•, respectively.
Definition 3: PN = (P, T, F, M0) is a marked PN, where:
| • | N = (P, T, F) is a net | |
| • | M: P→Z is a marking function, where M0 is the initial marking. Z = {0, 1, 2,…} is a natural number set | |
| • | Transition firing rules: | |
| • | t is enabled at M if ∀pε•t: M(p)≥1, represented by M[t> | |
| • | If t is enabled, it can fire and a new marking M’ is generated from M, represented by M[t>M’, where: | |
In order to model web service conveniently, the definition of ELPNs is introduced as follows:
Definition 4: Let LN = (P, T, F, L). ELPN = (LN, M) be an enchanced logic Petri nets, where:
| • | P is a finite set of places |
| • | T is a finite set of transitions, T∪P ≠ Ø, P∩T = Ø, ∀tεT: •t∩t• = Ø. ∀tεT, the input places of t are restricted by a logic input expression fI(t) and the output places of t are restricted by a logic output expression fO(t) |
| • | F⊆(PxT)∪(TxP) is a finite set of directed arcs |
| • | L is a mapping set from the transitions to the logic input and output expressions, i.e., ∀tεT, L(t) = <fI(t), fO(t)> |
| • | M: P→{0, 1} is a marking function, where ∀pεP, M(p) is the number of tokens in p |
| • | The logic operator of logic expressions in ELPN is only “∧” |
| • | Transition firing rules: ∀tεT, fI(t)|M = •T•, where •T• denotes the logic value ‘true’. •F• denotes the logic value ‘false’. If M[t>M’, then ∀pε•t: M’(p) = 0; ∀pεt• must satisfy fO(t)|M’ = •T• and ∀p∉•t∪t•: M’(p) = M(p) |
Form definition 4, the differences between ELPN and LPN is that the transitions in ELPN are restricted by the logic input expressions and output expressions at the same time. The other aspect is that the logic operator of logic expressions in ELPN is only “Λ”. The definition of web service is proposed as follows:
Definition 5: Let webservice = (Identity, Inputs, Outputs, Relations) be a web service, where:
| • | Identity denotes the unique mark number of the web service |
| • | Inputs = {Input1, Input2,…, Inputj} is a finite set which contains the input parameter of the web service |
| • | Outputs = {Output1, Output2,…, Outputk} is a finite set which contains the output parameter of the web service |
| • | Relations = {Relation1, Relation2,…, Relationi} is a finite set which contains the logic relations between inputs and outputs of the web service |
| • | The format of the item of relations is <input logic expression, output logic expression> = <(Inputw∧ Inputr∧…∧Inputt), (Outputh∧Outputq∧…∧Outputp)>. It means that if the inputs of webservice are Inputw, Inputr, … and Inputt, the outputs of webservice are Outputh, Outputq, … and Outputp |
The algorithm for modeling web service by ELPNs is introduced as follows:
| Algorithm 1: | Modeling web service by ELPNs |
Algorithom 1 presents a method for modeling web services by ELPNs. An example is given as follows:
Example 1: Let webservice1 = (Identity1, Inputs1, Outputs1, Relations1) to be a web service, where Identity1 = 1, Inputs1 = {a, b, c, d}, Outputs1 = {e, f, g, h}, Relations1 = {<(a), (e)>, <(b), (f)>, <(c∧d), (g∧h)>}. According to algorithm 1, the ELPNs model of webservice1 is showed in Fig. 1.
From Fig. 1, the web service webservice1 is represented by ELPNs all-sidedly. The service composition will be modeled based on ELPNs in the next sections.
| Fig. 1: | ELPNs model of webservice1 |
ELPNs MODEL OF SERVICE COMPOSITION
The ELPNs model of service composition is given in this section. Firstly, the definition and operational rules of operator “≡” is given as follows:
Definition 6: Let ELPNj = (P, T, F, L, M0) is an ELPN. p1 and p2 are the labels of two places in P. Then, the rules of operator “≡” is shown as follows:
Example 2: ELPNj = (P, T, F, L, M0) is showed in Fig. 2. From Fig. 2, the Name and Grade are labels of two places in P. From definition 6, Name ≡ Grade = 0.
The algorithm for searching the label of a place in ELPNs from the input or output logic expressions of transitions is given as follows:
| Algorithm 2: | Searching the label from logic expression |
The algorithm for modeling service composition by ELPNs is introduced as follows:
| Algorithm 3: | Modeling service composition by ELPNs |
| Fig. 2: | An ELPNs ELPNj |
Algorithom 2 presents a method for modeling services composition by ELPNs. An example is given as follows:
Example 3: There are the web service set Q = {webservice1, webservice2}, where webservice1 is the same as the web service in example 1. Webservice2 = (Identity2, Inputs2, Outputs2, Relations2), where Identity2 = 2, Inputs2 = {a, j, d}, Outputs2 = {e, i, h}, Relations1 = {<(a), (e)>, <(j∧d), (i∧h)>}. According to algorithm 3, the ELPNs model of service composition with webservice1 and webservice2 is showed in Fig. 3.
The ELPNs model after the 3rd step of algorithm 3 is showed in Fig. 3.
The ELPNs model after the 5th step of algorithm 3 is showed in Fig. 4.
From Fig. 4, the service composition between webservice1 and webservice2 is modeled by ELPNs.
REACHABILITY ANALYSIS OF ELPNs
Enabled transition: The enabled conditions of transitions are given here.
From definition 4, the transition of an ELPN is restricted by the logic input and output expressions. For ∀tεT, if fI(t)|M = •T•, then M[t>. The definition of enabling label set is defined below:
Definition 7: For ELPN = (P, T, F, L, M0) and tiεT. fI(ti) = (a1∧a2∧…∧ aj) is the logic input expression of ti. Vi = (a1, a2,…, aj)T denotes the enabling label set of ti. And V = {Vi| tiεT, iε{1,2, …, |T|}} denotes the enabing label set of T.
The definition and operational rules of operator Θ is given as follows:
Definition 8: Let ELPNm = (P, T, F, L, M0) be an ELPN and MεR(M0). V is the enabing label set of T. tiεT and Vi = (a1, a2, …, aj)T. The rules of operator “Θ” is shown as follows:
| Fig. 3: | ELPNs model after the 3rd step of algorithm 3 |
The enabled conditions of transitions are obtained from theorem 1.
Theorem 1: For ELPN = (P, T, F, L, M0) and MεR(M0). V is the enabing label set of T. ∀tiεT, ti is enabled at M if and only if MΘVi = 1.
Proof: [Necessity] For ∀tiεT, since V is the enabing label set of T and Vi is the enabing label set of ti. Suppose Vi = (a1, a2, …, aj)T. Thus, the input expression of ti is fI(ti) = (a1∧a2∧…∧ aj). Suppose ti is enabled at M, i.e., M[ti>. From definition 4, since M[ti>, thus, the logic value of the logic input expression of ti is •T• at the Marking M. i.e. fI(ti)|M = •T•. So, M(a1) = M(a2) = … = M(aj) = 1. i.e., MΘVi.
| Fig. 4: | ELPNs model after the 5th step of algorithm 3 |
[Sufficiency] For ∀tiεT, since Vi is the enabing label set of ti. Suppose Vi = (a1, a2,…, aj)T. Thus, the input expression of ti is fI(ti) = (a1∧a2∧…∧ aj). Since, MΘVi = 1, thus, M(a1) = M(a2) = … = M(aj) = 1. So, the logic value of the logic input expression of ti is •T• at the Marking M. i.e., fI(ti)|M = •T•. From definition 4, since M[ti>.
From theorem 1, the enabled conditions of transitions are given and the enabled transitions at the current marking can be obtained. The theorem for computing marking after an enabled transition fired is introduced in the next section.
Marking computing: The method for computing marking after an enabled transition fired is given in this section. The definition of output label set is defined below.
Definition 9: For ELPN = (P, T, F, L, M0) and tiεT. fO(ti) = (b1∧b2∧…∧ bj) is the logic output expression of ti. Bi = (b1, b2, …, bj)T denotes the output label set of ti. And B = {Bi| tiεT, iε{1,2, …, |T|}} denotes the output label set of T.
The marking computing theorem is introduced as follows:
Theorem 2: For ELPN = (P, T, F, L, M0), where P = {p1, p2,…, pm} and MεR(M0). V is the enabing label set of T. B is the output label set of T. ∀tiεT, If M[ti>M’, then M’ = (M’(p1), M’(p2),…, M’(pm))T, where for jε{1, 2,…, m}:
| (1) |
Proof: For ∀tiεT, since, V is the enabing label set of T and Vi is the enabing label set of ti. From definition 7, the item in •ti is the same as the item in Vi. Since, M[ti>M’. From definition 4, ∀pε•ti: M’(p) = 0. Thus, ∀pεVi: M’(p) = 0. For ∀tiεT, Since, B is the output label set of T and Bi is the output label set of ti. From definition 9, the item in ti• is the same as the item in Bi. Since, M[ti>M’. From definition 4, ∀pεt• must satisfy fO(t)|M’ = •T•. Since, the logic operator of logic expressions in ELPN is only “∧”. Thus, ∀pεBi: M’(p) = 1. Since, M[ti>M’. From Definition 4, ∀p∉•ti∪ ti•: M’(p) = M(p), thus, ∀p∉Vi∪Bi: M’(p) = M(p).
Theorem 2 presents a method for computing marking when a enabled transition fired. All reachable markings can be obtained in the next section.
Reachability analysis: The method for obtaining all reachable markings is introduced in this section. The algorithm for computing reachable markings of an ELPN is showed as follows:
| Algorithm 4: | Computing reachable markings |
Algorithm 4 presents a method for obtaining all reachable markings of an ELPN. From algorithm 4, the three-dimensional array A[n][i] contains all reachability information of an ELPN.
Example 4: Suppose the current marking M of ELPN set Σ in Fig. 4 is {M(a) = M(f) = M(c) = M(d) = M(j) = 1, M(e) = M(b) = M(g) = M(h) = M(i) = 0}. From theorem 1, the transitions t1+1, t2+2 are enabled at M. From theorem 2, when the transition t1+1 is fired, the marking M of ELPN set Σ in Fig. 4 is {M(e) = M(b) = M(c) = M(h) = M(i) = 1, M(a) = M(f) = M(g) = M(d) = M(j) = 0}. From algorithm 4, A[0][0] = {M(a) = M(f) = M(c) = M(d) = M(j) = 1, M(e) = M(b) = M(g) = M(h) = M(i) = 0}, A[0][1] = {M(e) = M(f) = M(c) = M(d) = M(j) = 1, M(a) = M(b) = M(g) = M(h) = M(i) = 0}, A[0][2] = t1+1.
CONSTRUCTION OF COMPOSITION LIBRARY
The method for constructing composition library is introduced in this section. The definition of composition library is given as follows:
Definition 10: Scomlry = (C_ELPNs, C_Relations) is a composition library, where:
| • | C_ELPNs is the ELPNs model of servcie composition |
| • | C_Relations = {Relation1, Relation2,…, Relationi} is a finite set which contains the mapping relations of inputs, outputs, transitions in C_ELPNs |
| • | The format of the item of C_Relations is <inputs of C_ELPNs, outputs of C_ELPNs, transitions of C_ELPNs> = <(Inputa, Inputb,…, Inputc), (Outputd, Outpute,…, Outputf), (tg, th,…, ti)>. It means that if there are the inputs of service composition are Inputa, Inputb, … and Inputc, the outputs of service composition would be Outputd, Outpute, … and Outputf, after the transitions tg, th,…, ti fired successively |
The definition and operational rules of operator “⊗” is given as follows:
Definition 11: Let ELPNm = (P, T, F, L, M0) be the ELPNs model of service composition, where P = {p1, p2, …, pm} and MεR(M0). Q is the label set of the places in ELPNm.P. The rules of operator “⊗” is shown as follows:
M⊗Q = M, where, For jε{1, 2, …, m}
The function for combination is given as follows:
| Function 1: | COMB(s, n, m, top, W, queue, array) |
The algorithm for constructing initial marking set is given as follows:
| Algorithm 5: | Construction initial marking set |
The algorithm for constructing composition library is introduced as follows:
| Algorithm 6: | Construction composition library |
Algorithm 6 presents a method for constructing composition library.
Example 5: The ELPNs model of service composition ELPNi = (P, T, F, L, M0) is the same as the ElPN in Fig. 4. From algorithm 5, the label set is {{a}, {b}, {c}, {d}, {j}, {a, b}, {a, c}, {a, d}, {a, j}, {b, c}, {b, d}, {b, j}, {c, d}, {c, j}, {d, j}, {a, b, c}, {a, b, d}, {a, b, j}, {a, c, d}, {a, c, j}, {a, d, j}, {b, c, d}, {b, c, j}, {b, d, j}, {c, d, j}, {a, b, c, d}, {a, b, c, j}, {a, b, d, j}, {a, c, d, j}, {b, c, d, j}, {a, b, c, d, j}}. From algorithm 6, the composition library can be constructed as Scomlry = (C_ELPNs, C_Relations), where C_ELPNs = ELPNi and C_Relations = {<{a}, {e}, t1+1>, <{b}, {f}, t1+2>, <{c,d}, {g,h}, t1+3>, <{j,d}, {i,h}, t2+1>}.
SERVICE COMPOSITION ORIENTED TO USER’S DEMANDS
The method for service composition oriented to user’s demands is introduced in this section. The definition of user’s demand is given as follows:
Definition 12: Udemand = (Id, Uinputs, Uoutputs) is an user’s demand, where:
| • | Id denotes the unique mark number of the user’s demand |
| • | Uinputs = {Input1, Input2,…, Inputj} is a finite set which contains the input parameters of the user’s demand |
| • | Uinputs = {Output1, Output2, …, Outputk} is a finite set which contains the output parameters of the user’s demand |
| • | The user’s demand can be satisfied, if the outputs can be given by the service composition system based on the user’s inputs |
| • | The output and input parameters of user’s demand is consistent with the input and output parameters of web services |
The theorem for service composition oriented to user’s demands is introduced as follows:
Theorem 3: Udemandi = (Id, Uinputs, Uoutputs) is an user’s demand. ELPNj = (P, T, F, L, M0) is the ELPNs model of service composition and MaεR(M0). The user’s demand can be satisfied if and only if (Ma⊗Uinputs)εR(M0⊗Uoutputs).
Proof: [Necessity] From algorithm 1 and 3, the Udemandi. Uinputs and Udemandi.Uoutputs are the label sets of the places in ELPNj.P. Thus, from definition 11, Ma⊗Uinputs denotes the marking of ELPNj which is consistent with the user’s input parameters. M0⊗Uoutputs denotes the marking of ELPNj which is consistent with the user’s output parameters. Since, the user’s demand can be satisfied. From definition 12, the outputs can be given by the service composition system based on the user’s inputs. Thus, the marking Ma⊗Uinputs of ELPNj can be reached from the marking M0⊗Uoutputs of ELPNj i.e., (Ma⊗Uinputs)εR(M0⊗Uoutputs).
[Sufficiency] Since, (Ma⊗Uinputs)εR(M0⊗Uoutputs), thus, the marking Ma⊗Uinputs of ELPNj can be reached from the marking M0⊗Uoutputs of ELPNj. From definition 11, Ma⊗Uinputs denotes the marking of ELPNj which is consistent with the user’s input parameters. M0⊗U outputs denotes the marking of ELPNj which is consistent with the user’s output parameters. Thus, the outputs of the user’s demand can be given by the service composition system based on the user’s inputs. From definition 12, the user’s demand can be satisfied.
Definition 13: Rtable = (Records) is the composition result for user’s demand, where:
| • | Records = {record1, record2,…, recordk} is a finite set | |
| • | The format of the item of Records is <Rid, Rinputs, Routputs, Sid>, where: | |
| • | Rid denotes the unique mark number of the item and created in ascending order successively | |
| • | Rinputs denotes the input parameters | |
| • | Routputs denotes the output parameters | |
| • | Sid denotes the unique mark number of web service | |
Example 6: There is a composition result for user’s demand Rtablei = (Recordsi). Suppose Recordsi = {record1, record2}, where record1≤1, {a}, {b}, 3> and record2≤2, {b}, {c}, 5>. It means that the user’s demand is input a and output c. The demand can be satisfied by the work flow that user inputs a and b can be obtained using the web service which Identity = 3. Then, the user inputs b and c can be obtained using the web service which Identity = 5.
The algorithm for service composition oriented to user’s demands is introduced as follows:
| Algorithm 7: | Service composition oriented to user’s demands |
EXPERIMENT AND COMPARISON
In order to verify the validity and advantages of proposed methods in this study, the experiment and comparison are given in this section. Because of no standard software and test data, one hundred services are defined according to definition 5. Although, the services defined in this study is not real, there are no effect on the result of the experiment.
Construction of web services: From definition 5, one hundred services are defined. For simplicity, the inputs and outputs of web services are defined as letters. The first six items of service set are showed in Table 1.
| Table 1: | First six web services |
| Fig. 5: | First four ELPNs model of services |
Model web services by ELPNs: From algorithm 1, the web services defined in this section can be model by ELPNs. The first four ELPNs models of services is showed in Fig. 5.
Model service composition by ELPNs: From algorithm 3, the services composition oriented to the services defined in this section can be model by ELPNs. The part of ELPNs model of service composition is showed in Fig. 6.
Construction of composition library: From algorithm 6, the composition library based on ELPNs model of service composition can be constructed as Scomlry = (C_ELPNs, C_Relations). C_ELPNs is equal to the ELPNs model of service composition and the first six items of C_Relations are shown below:
| Fig. 6: | Part of ELPNs model of service composition |
| Table 2: | First three items of user’s demands |
Construction of user’s demands: From definition 12, fifty user’s demands are defined. The outputs and inputs of user’s demand are consistent with which in web services. The first three items of user’s demands are showed in Table 2.
Service composition oriented to user’s demands: From algorithm 7, all composition result can be obtained. The first six composition results binded to user are showed in Table 3.
Comparison: There are a lot of achievements on service composition. The innovation and superiority of this study have three aspects. Firstly, the composition library is constructed before service discovery. Secondly, the ELPNs is introduced and defined for the first time.
| Table 3: | First six composition results |
The methods for analyzing reachability of ELPNs are given. At last, the service composition is modeled by ELPNs. The comparison analysis is showed as follows:
| • | The comparison analysis with the time complexity for service composition oriented to user’s demand is shown as follows: | |
| • | Service composition oriented to user’s demand from the proposed method in this study | |
Suppose the service composition library is constructed and named as Scomlryj = (C_ELPNs, C_Relations). Suppose | C_Relations| = n. From algorithm 7, if the item in C_Relations satisfied to user’s demand is not found, the time complexity for service composition is O(n). Else, if the item in C_Relations satisfied to user’s demand can be found and named as Rk = <inputsk, outputsk, transitionsk>. Suppose |transitionsk| = m, thus, the time complexity for service composition is O(n+m):
| • | Service composition oriented to user’s demand from web service set Q (Sheng et al., 2009; Nayak and Lee, 2007) |
Suppose |Q| = n, If the user’s demand is segmented to m atomic demands completely. Obviously, the time complexity for service composition is O(n×m).
From above analysis the time complexity of service combination using the method proposed in this study is decreased:
| • | The comparison analysis with the optimality of service composition oriented to user’s demand is showed as follows: | |
| • | The result of service composition generated by the propose method in this study | |
From algorithm 5 and 6, all reachable markings of ELPNs model of service composition can be obtained. In order to construct the optimal composition library, the adjacent matrix is constructed. Every path from the inputs to outputs of user’s demand is obtained through the classic shortest path first algorithm. For example, from Table 3, for the second user’s demand, the service composition is that user inputs cxa, hej, io and crw, ki can be obtained using the web service which Identity = 3. Then, the user inputs crw, ki and pts, tts can be obtained using the web service which Identity = 58:
| • | The result of service composition generated without the pretreatment for the shortest path (Lian and Zheng, 2011; Liu et al., 2010) |
For the user’s demand, if the demand is not satisfied by a single web service, the demand should be segmented to several sub-demands. Obviously, it is hard to segment user’s demand optimally without the pretreatment of the shortest path computation. For example, from Table 3, the second user’s demand is Udemand2 = (2, {cxa, hej, io}, {pts, tts}). From the service composition oriented to Udemand2 in Table 3, the optimal segment of Udemand2 is Udemand2-1 = (2-1, {cxa, hej, io}, {crw, ki}), Udemand2-2 = (2-2, {crw, ki}, {pts, tts}). Howere, the segment of Udemand2 would be not the same as the above case.
So, the method proposed in this study is superior on the optimality of service composition:
| • | The comparison analysis between ELPNs and LPNs with modeling web service is shown as follows: |
Model web service by ELPNs: From definition 5, the web service has three aspects inputs, outputs and the relations between input and output parameters. From definition 4, the transitions in ELPNs are restricted by logic input and output expressions at the same time. Thus, From algorithm 1, the web service can be model by ELPNs conveniently. For example, Let webservicek = (Identityk, Inputsk, Outputsk, Relationsk) to be a web service, where Identityk = k, Inputsk = {a, b, c, d}, Outputsk = {e, f, g, h}, Relationsk = {<(c∧d), (g∧h)>}. According to algorithm 1, the ELPNs model of webservicek is showed in Fig. 7.
Model web service by LPNs: From the definition of LPNs, there are three kinds of transitions in LPNs. TD denotes the traditional transitions. TI denotes the transitions restricted by the logic input expressions (Du and Guo, 2009). TO denotes the transitions restricted by the logic output expressions. The LPNs model of webservicek is showed in Fig. 8.
| Fig. 7: | ELPNs model of webservicek |
| Fig. 8: | LPNs model of webservicek |
From Fig. 7 and 8, obviously, the transition and place in Fig. 8 is more than that in Fig. 7. Thus, it is easier for modeling web service by ELPNs than by LPNs.
From the above analysis, the validity, superiority and effectiveness of the proposed method are illustrated.
CONCLUSION
A new method for service composition is introduced in this study. In order to model web service conveniently, an Enhanced Logic Petric nets is defined in this study firstly. The comparison has already verified that ELPNs is the abstract and extension of LPNs and high-level PNs. The enabled conditions of transitions and marking computation theorem of ELPNs are given. The reachability of ELPNs is analyzed. The ELPNs models of web service and service composition are given. All reachable markings of ELPNs model of service composition are obtained. The service composition library is constructed based on ELPNs model of service composition. Every path in composition library from the inputs to outputs of user’s demand is obtained through the classic shortest path first algorithm. The method for service composition oriented to user’s demand is introduced. From the simulation experiments and comparisons, the time complexity of service composition oriented to user’s demand is decreased and the result binding to user is optimal.
Further study will be the properties analysis of ELPNs, including fairness, reversibility and the construction of reachable marking gragh. Moreover, service discovery, service binding and service substitution will be studied.
ACKNOWLEDGMENTS
This study is supported by the National Basic Research Program of China under Grant No. 2010CB328101; the National Natural Science Foundation of China under Grant No. 61170078 and 61173042; the Doctoral Program of Higher Education of the Specialized Research Fund of China under Grant No. 20113718110004; Basic Research Program of Qingdao City of China under Grant No. 13-1-4-116-jch and the SDUST Research Fund of China under Grant No. 2011KYTD102.