基于服务簇的服务组合与替换方法
基于服务簇的服务组合与替换方法
【技术领域】
[0001] 本发明设及一种基于服务簇的服务组合与替换方法。
【背景技术】
[0002] 在全球信息化大潮的推动下，Web服务技术得到迅猛的发展，Web服务的应用尤为 常见。随着网络资源的丰富，服务的数量大量增加，该使服务发现与替换面临着巨大的压 力。服务簇的提出大大缩小了服务发现的查找范围，使服务发现效率有效提高。而在服务 簇中，各个服务具有参数不确定性，需要一种统一的形式化描述方法。在Web服务的形式化 描述中，不仅要给出服务自身的特征，还要能够方便在服务簇的描述中给出服务之间的交 互特点，该样方便服务的发现与组合，因此，需要给出服务及服务簇的合理规范的形式化描 述。由于服务的动态性，在响应用户请求的过程中，可能存在一些服务失效。在传统的服务 组合模式中，服务的失效会造成服务流程的中断。在实际应用中，流程的中断可能会造成巨 大的损失。
[0003] 目前，国内外对于服务形式化模型的研究主要基于Petri网、进程代数和有限状 态自动机、语义网等几类工具，并且都取得了一定的成果，然而服务替换的研究还处在初级 阶段。现有的大多数研究都是围绕解决现有的Web服务替换机制中存在的查准率不高的问 题，而很少有在聚类得到的服务集合（即服务簇，Servicecluster)层面上建模并进行服 务替换的研究，而且对服务的组合替换缺乏考虑。随着Web服务数量的迅速增加，采用传统 的服务查找和替换方法，必然会浪费大量时间来处理毫不相关的服务，从而使得效率低下 甚至造成服务组合流程的中断，造成巨大损失。
【发明内容】
[0004] 针对现有技术中存在的上述技术问题，本发明提出了一种基于服务簇的服务组合 与替换方法，其采用如下技术方案：
[0005] 基于服务簇的服务组合与替换方法，包括如下步骤：
[0006]a、构建Web服务和服务簇的形式化模型
[0007]定义N是一个自然数集合，即N={0, 1，2,…}，而设定N尸{0,1，2,…，片.，N+=N\W， 且N/=m\{〇};
[0008] 定义化tri网；
[0009] 一个化tri网表示为一个四元组PN= (S，T;F，M0)，其中，
[0010] (1)S是一个有限库所集；
[00川（2)T是一个有限变迁集，且心於0，、片幼
[001引做巧;('s'x7>j(;rxs)是一个弧集；
[001引（4)dom(巧Ucod(巧=S U T，其中，
[0014] dom(F)= {.，ve5ur|3yeSuT:(,v,.v)gF1 , cod(F)= {ve5ur|3xeSuT:(,v,y)eF\；
[001引妨M: 为网PN的一个标识，其中，
[0016]VseS，M(s)表示标识M下库所s中的托肯数，M。是初始标识；
[0017] 定义输入/输出集：
[001引设PN= (S,T;F，M。）为一个化tri网，XGSUT为网N的一个元素，记；
[001引'X={yIyG S U T八（y，X)G巧称为X的输入集；
[0020] X' ={y|yG S U T八（X,y)G巧称为X的输出集；
[0021] 'XUX'称为元素X的外延；
[0022] 在化tri网中，采用一个圆圈表示一个库所，用一个矩形表示一个变迁；若 (X，y)GF，则X到y的一条有向边表示它们的流关系；
[0023] 定义引发规则：
[0024] 设PN= (S，T;F，M。）为一个化tri网，则其具有如下的变迁发生规则；
[002引1)对于变迁t G T，如果V.s'E,S': .s'eV一M(单1，则变迁t在标识M有发生权，记为M[t >；
[002引。如果M[t>，则在标识M下，变迁t能够发生，从标识M发生变迁t得到一个新 的标识M'，记为M[仪V/'，V.s'eS，
[0027]
[0028] 根据上述化tri网的定义，构建Web服务的形式化模型如下：
[002引定义Web服务；
[0030] -个Web服务描述为一个四元组WS=(SF，I，0)，其中；
[0031] (1)SF表示服务的功能语义描述；
[003引似I、0表示服务的输入、输出参数集，并且V戶e/u化戶=(戶題歴，片C饼ice的，其 中，
[0033] ①P. name是输入、输出参数名；
[0034] ②P.concept是一个输入、输出参数的本体概念，用W表示参数的语义；
[00对定义服务请求：
[0036] -个服务请求表示为R=(SFr，I"Or)，其中：
[0037] (1)SFr表示服务请求的功能语义描述；
[0038] (2) If代表服务请求者可提供的输入参数集；
[0039] (3)Or代表服务请求者需要输出的参数集；
[0040] 定义服务网元：
[00川服务WS= (SF，I，0)的服务网元定义为SNU=扣1。0。尸。1)，其中；
[0042] (1)t是一个能够完成服务功能的变迁；
[0043](2)It='t={su,Si2, Su,…，sj是变迁t的输入集，代表服务的输入参数集合； 〇t二t= {s。。3。2, 3。3,…，S。。}代表服务的输出参数集合；
[0044]做Ft= (ItXt)U(tX〇t)是有向弧集合，表示服务的输入、输出参数的流关系；[004引（4)M是服务网兀的标识，M;ItU0t- ;
[0046] (5)变迁t在M下的发生规则为：
[0047] ①Vpe/:M(/))= 1，则变迁t在M下有发生权，记为M[t>;
[0048] ②若M[t〉，则t在标识M下能够发生并得到一个新的标识，记作M[t〉M'，对于 Vjf?eIfKJ0tf
[0049]
[0050] 定义服务簇：
[0051]对于n个服务；wSi,WS2, . ..，sc= {wSi,WS2, . . .，WS。}是一个服务簇，其中：
[00閲 ！化N/，丽,,=口Fy，/,,，0,,，旅M,,)，且Vリ，化N,,+，SFu和SFv满足语义相似；
[005引定义服务簇网元：
[0054]一个有n个服务的服务簇；SC = {wsi, WS2, . . .，WS。}，Ae N"+，SNUk= (tk，Itk，〇tk，Ftk，Mk)，服务簇网元表示为SCNU = (SU，tc，Ic，〇c，Fc，Me)，其中：
[005引（1)SU= {SNUi，SNUs，SNUs，…，SNU。}是服务网元的集合；
[005引（2)te是服务簇网元的变迁，且能够完成服务簇中各服务的功能；
[0057] 做I。〇c分别表示服务的输入、输出参数集，并且V尸e /(. U()(.，/，=(/>(.顶聊庐 /"片知），其中；
[0058] ①P.concept是服务簇中服务输入参数对应的语义概念；
[005引②P. 1油le是一个nX1的矩阵，其中，n是服务簇中服务的个数，并且P. 1油le是 服务簇中的服务相应P.cone巧t的值；
[0060] (4化=(IctXtc)U(teXOa)表示服务簇输入、输出参数的流关系；
[006。巧)Me是服务簇网元的标识；
[0062] 根据服务簇网元的定义，将一个服务的输入参数值作为服务簇输入矩阵的一行； 将该服务的输出参数值作为服务簇输出参数矩阵的对应行；
[0063] b、基于服务簇的服务发现、组合与替换
[0064] 设服务簇k的服务总数为m个，输入参数的总数为n;个，输出参数总数为n。个； lek、〇a、if、Of分别代表服务簇的输入矩阵、服务簇的输出矩阵、服务请求的输入矩阵、W及 服务请求的输出矩阵；其中，Ick是一个mXrii矩阵，〇ck是一个mXn。矩阵，if是一个IXrii 矩阵，〇r是一个1Xn。矩阵；IaP(q)代表输入矩阵的第P行第q列的值；
[006引输入一个服务簇网元模型SCNUk=(SUk，tck，Ick，0ck，Fck，Mck)和一个服务请求网元Sf=(sft，if,Of}，基于服务簇的服务匹配输出Cl和C。，其中，Cl表示输入匹配矩阵，是一个 mXn先阵；C康示输出匹配矩阵，是一个mXn。矩阵；
[0066] 基于服务簇的服务匹配的过程如下：
[0067] SI:Wlek的首行开始，依次匹配该行的每个值；
[0068]S2:若该行中元素的值小于或者等于if对应的值，则标记Cl对应位置的值为1;
[0069]S3:否则，标记为0;
[0070] S4:W〇ck的首行开始，依次匹配该行的每个值；
[0071] S5:若该行中元素的值大于或者等于if对应的值，则标记Cl对应位置的值为1 ;
[007引 S6:否则，标记为0;
[0073]S7:输出矩阵。和矩阵C。；
[0074] 其中，服务匹配过程的时间复杂度是mXni2+mXn。2;
[00巧]通过上述服务匹配过程，服务簇输入/输出匹配矩阵将服务簇中的服务按照当前 服务请求统一表示服务匹配结果；
[0076] 通过上述服务匹配过程明确区分各服务输入输出参数是否满足服务请求，提高服 务查找效率；
[0077] 输入一个输入匹配矩阵。和一个输出匹配矩阵C。，基于上述服务匹配过程提出服 务发现的过程，进而得到一个服务集合S;
[0078] 服务发现的具体过程如下：
[0079] Sl:p=1,S=0;
[0080]S2:WCl的第p行开始，依次匹配该行的每个值；
[0081] S3:若该行中所有的值都为1，则跳到S5 ;
[008引 S4:否则P=P+1，循环该一匹配过程；
[0083]S5:依次匹配C。第P行的各值；
[0084]S6:若该行中所有的值都为1，则将该服务合并入集合S中，即S=SU{wsp};
[00财 S7:否则P=P+1，跳到S2;
[008引 S8输出服务集合S;
[0087] 通过服务发现过程发现服务簇中满足服务请求的服务；服务发现过程输出的服务 集合S中，所有服务的输入输出匹配矩阵同为'即服务集合S中的每个服务都满足 服务请求；服务发现过程的时间复杂度为；mXni+mXn;
[008引定义*3冷WSj表示服务WSi和服务WSj的并行组合；定义WSi|wSj表示服务WSi和 服务WSj.的串行组合；
[008引设曰=比。b2,…，bj是一个IXk矩阵，其中，biG{0,U，/eNa+，且,kN+，对 于Vz'eN-/，如果bi= 1，a表示为E，即E= [1,…，1];
[0090]对于V/eN/，若bi=0，a表示为 0,即 0=[0, 0,…，0];
[00川 其中，a表示F>etri网中的一个标识；并且aa2表示V/eN/，b2i;
[0092] 定义基元素：
[009引设a1=比。，b。，…，bj且a2=比21As,…Ak]是两个IXk矩阵，其中neN+,&GN"+，V6i,.e{0，l}，andbgiE{〇, 1}，/eN/;若a2,则称 是a1的一个 基元素；
[0094] 定义基集合；
[009引设C是一个IXk矩阵的集合；3C'cC，如果V%eC，otpeC'或者30CgeC'，a。是曰P 的一个基元素，且VC"，|C"I> |C'I，则称C'是C的一个基集合；
[0096] 定义服务组合标志；
[0097] 用于标记当前服务请求下的服务组合的服务基集合，其初始标志为0;
[009引根据服务匹配过程提出服务匹配的运算方法如下：
[0099] 定义匹配运算：
[0100] SNUa=(t。，Ita，〇ta，Fta，M。）是一个服务网元，R= (SFr，If,Or)是一个服务请求；
[0101] 匹配运算被定义为：
[0106] 定义服务簇匹配矩阵：
[0107] WSreq=(SFre。，Ireg，〇reg)是一个服务请求；
[010引SCNUa=佛。，tc。，Ict。，0ct。，Fct。，M。）是一个服务簇网元；
[0109] 服务簇的输入/输出匹配矩阵被定义为：
[0110]
[0113] Ci和C。代表了服务簇中的服务匹配服务请求的标识；
[0114] 输入服务簇网元SCNU= (SU，tc，Ic，〇c，Fc，Mc)和服务簇匹配矩阵Ci，C。;其中，V戶e /('U()('，/^=(C )，服务输入、输出参数的个数分别为k，1 ;输出服务集合 B；
[0115] 则服务串行组合的过程如下：
[0116] S1:依次匹配服务的输入、输出参数的参数语义；
[0117] S2:若存在la.concept= 〇cj.concept,依次匹配Cl(i);
[om]S3:若c/a) = 0,WCl的首行开始，依次匹配该行的每个值；
[011引 S4:若c/= [1，1，…，1]，匹配相应的c〇g;
[0120] S5:若CCi) = 1 且CUC〇P= [1，1，…，1]，则B=BU{ws。}，循环该一过程；
[0121] S6:若^=0，输出"没有满足条件的串行服务组合"；
[0122] S7:输出服务集合B;
[0123] SCM表示服务的基集合，通过SCM的过程体现服务簇中服务间的共性与个性，从而 用SCM来发现单一替代服务和组合替代服务；
[0124] 输入服务簇SC= {wsi,WS2,…，wsJ和服务簇匹配矩阵Ci、C。，SCM的过程如下； [01幼S1:依次匹配叫，若m。'声[1, 1,…，]_]，贝ijSCMj标记为巫；
[012引 S2:匹配m0k，若m0k= [1, 1,…，]_]，SCMk标记为 0 ;
[0127] S3:若m〇k声[1，1，…，1]，找到所有不为巫的SCMP且若W。曲则
[012引 S4:若A=巫，则SCMk=巫；
[0129] S5:否则标记SCMk为A的基集合；
[0130] S6:若在所有的SCM中有一列全为1，在所有SCM中删掉该一列；
[013" S7:输出SCM;
[01础定义SCM1^戈表SCMk的第m个元素；S1^1是SCM,。的第1列，打，W，andA;eN,,+;
[0133] 定义组合规则；
[0134] SC= {wsi，WS2,...，wsJ是一个服务簇；其中，u'.s',.=(W, /,化SCM,.)，侣乂,+;
[0135] SCMk丄SCMp=SCMki丄SCMpi丄SCMk2丄SCMp2丄…丄SCMh丄SCMpn，
[01 3引 其中，SCMkm丄SCMpm= [S。S2,…，S。]且
[0137] 输入SC= {wSi,WS2,. . .，WS。}和失效服务WS。，输出替换服务集合A;
[013引则发现单一服务和组合服务的服务替换的过程如下：
[0139] S0:A=巫；
[0140] S1:若失效服务的SCMm= 〇 或SCMm= 0 ;
[01川S1. 1:匹配SCM，若3化端=0,则将服务wSk并入集合A中，A=AU(wsJ;
[014引SI. 2:若匹配存在SCMi，SCMk，SCMi丄SCMk= 0,则将wsi和wsk的组合并入集合A中，即A=AU{讯3冷wsJ;
[014引S2:否则，若失效服务的SCMm声巫且SCMm声0 ;
[0144] S2. 1:如果匹配SCMk=0,则将服务wSk并入集合A中，A=AU{wsJ;
[014引 S2. 2:若匹配存在SCMkj'ESCMk，SCM血GSCMm，且SCMkj'《SCMmh，则将服务wSk并入 集合A中，A=AU(wsJ;
[0146] S2. 3:如果匹配SCMi，SCMk，SCMi丄SCMk=〇,则将wsi和wSk的组合并入集合A中， A=AU{wSjOws；
[0147]S3:若A=巫；
[014引S3. 1:若SCMm中存在某一列的值为1，而其他服务的在该列的值都不为1，则将该 一列在所有的SCM中移除，转到S2 ;
[0149] S3. 2:否则，输出"没有满足条件的替换服务"；
[0150] S4:输出A，即为满足条件的替换服务集合。
[0151] 本发明具有如下优点：
[0152] (1)本发明借助已有的服务聚簇方法构建服务簇，并基于化tri网提出服务及服 务簇的形式化描述方法；将服务的输入输出参数抽象表示，通过参数矩阵来描述服务的输 入输出参数；
[0153] (2)本发明提出的服务匹配方法使服务簇中的服务间能够充分共性与个性，通过 缩小服务查找范围，从而提高服务发现与组合效率；通过对服务簇模型的改进，提出Web服 务组合替换方法；对服务簇内服务的并行组合与串行组合分别进行了描述，在服务簇内实 现快速服务组合，进而实现高效率的服务组合替换；
[0154] (3)本发明提出的服务簇的服务替换方法，不仅能够实现服务簇内单一服务替 换，而且能够实现服务簇内服务组合替换。
【附图说明】
[0155] 图1为一个简单的Petri网模型示意图；
[0156] 图2为一个火车票查询服务网元模型示意图；
[0157] 图3为火车票查询服务网元示意图；
[015引图4为一个火车票查询的服务簇网元示意图；
[0159] 图5为查询服务簇的服务簇网元模型示意图；
[0160] 图6为服务簇的输入输出匹配矩阵匹配示意图；
[0161] 图7为本发明实验中Web服务发现时间比较示意图；
[0162] 图8为本发明实验中单一服务替换的比较示意图；
[0163] 图9为本发明实验中组合服务替换的比较示意图。
【具体实施方式】
[0164] 下面结合附图W及【具体实施方式】对本发明作进一步详细说明：
[0165] 基于服务簇的服务组合与替换方法，包括如下步骤：
[0166] 1构建Web服务和服务簇的形式化模型
[0167] 1. 1相关技术描述
[0168] 定义N是一个自然数集合，即N={0, 1，2,…}，而设定N尸{0,1,2,…，如N+=N\{0}， 且沁=Na-\{0}。
[0169] 定义化tri网；
[0170] -个化tri网表示为一个四元组PN= (S,T;F，M0)，其中，
[0171] (1)S是一个有限库所集；
[017引 （2)T是一个有限变迁集，且5。片凤折片風 [017引 做化(於7>_;(rxS)是一个弧集；
[0174] (4)dom(巧Ucod(F) =SUT，其中，
[01 巧]dom(F)="!.\-e&jr|ve瓜爪（.\-，-v)E巧.，cod(F)={ve5U7l (..V，.v')E巧.；
[017引 妨M: 为网PN的一个标识，其中，
[0177]VkS，M(s)表示标识M下库所s中的托肯数，M。是初始标识。
[0178] 定义输入/输出集；
[017引设PN = (S, T ;F，M。）为一个化tri网，xGSUT为网N的一个元素，记[0180] ? X = {y I y G S U T八（y，X) G巧称为X的输入集；
[01X' ={y|yGSUT八（X,y)G巧称为X的输出集；
[0182] -XUX'称为元素X的外延。
[0183] 在化tri网中，通常用一个圆圈表示一个库所，用一个矩形表示一个变迁。若 (X，y)GF，则X到y的一条有向边表示它们的流关系。
[0184] 如图1给出了一个简单的Petri网模型。
[01财在图1中，有限库所集S= {s。S2,S3,sj;
[0186]有限变迁集T={ti，t2，t3，t4};
[0187]弧集F = { (Si, *2)，（S2, ti)，（S2, t*)，（S3, ts)，（S3, t*)，（S4, ts)，（ti, Si)，（t2, S2)，（t2 ,S3),(tg, Si),(t4, S4)}；
[018引初始标识M0= (1，0, 0, 0);
[0189] 对于库所Si，它的前集为'Si={t。tg}，后集为Si'=咕};
[0190] 对于变迁t2的前集和后集分别为't2={sJ，t2' = {S2,S3}。
[0191] 定义引发规则：
[019引设PN= (S，T;F，M。）为一个化tri网，则其具有如下的变迁发生规则：
[019引 1)对于变迁tGT，如果V化&化一M似H，则变迁t在标识M有发生权，记为M[t> ；
[0194] 2)如果M[t>，则在标识M下，变迁t能够发生，从标识M发生变迁t得到一个新 的标识M'(记为M[t>M' )，VkS，
[0195]
[0196] 本体的ntology)是一种起源于哲学领域的概念，主要研究存在本质的哲学问题， 上世纪90年代被用于计算机领域。
[0197] 1997年，W.N.Borst对Guarino的理论进行了扩充，进而把本体定义为"对共享概 念模型的形式化的明确说明"，得到广泛的认可。其中体现了四层含义：
[0198] (1)概念模型：通过抽象出客观世界中一些现象的相关概念所得的模型；
[0199] (2)明确；所使用的概念W及使用此概念的约束都有明确定义；
[0200] (3)形式化：是计算机可读的；
[0201] (4)共享；体现的是共同认可的知识，反映的是相关领域中公认的概念集合。
[0202] 领域本体是依据领域来表述特定领域的静态知识。
[0203] 领域本体通过对特定领域内的概念及概念见的关系的精确描述，成为人机之间、 机器和机器之间相互理解的语义基础。
[0204] 领域本体由对象、对象的属性、对象之间的关系及子领域本体构成，故领域实体对 象和实体间的关系都是独立的知识单元，能够把领域本体形式化表示成一个有向无循环 图，图中的结点表示概念或单个对象，有向边表示概念之间的关系或关联。现有技术文献基 于领域本体的概念，构建了一个层次语义知识库，并提出了一种服务相似度的计算方法；
[0205]
[020引式中，SF。S。代表服务WSi和WSj.的服务功能语义描述；
[0207] 1是层次语义网中S。和SFj.之间的最短路径；
[020引 h是在层次语义网中的深度；
[0209] a，P是两个参数，择优选择为；a=0. 2and|3=0. 6。
[0210] 1.2Web服务
[0211] 根据上述1. 1对于化tri网的概念，构建服务的形式化模型如下：
[0引引定义Web服务；
[021引一个Web服务描述为一个四元组WS= (SF，1，0)，其中；
[0214] (1)SF表示服务的功能语义描述；
[02巧]似I、0表示服务的输入、输出参数集，并且V尸e/u(),尸=(/'^""歷，戶(顶巧的，
[0216] 其中，P. name是输入、输出参数名；P. concept是一个输入、输出参数的本体概念， 用W表示参数的语义；
[0217] 定义服务请求：
[0引引一个服务请求表示为R= (SFf，If,Of)，其中：
[021引 （1)SFr表示服务请求的功能语义描述；
[0220] (2)I,代表服务请求者可提供的输入参数集；
[0221] (3)Or代表服务请求者需要输出的参数集。
[0222] 定义服务网元；
[022引服务WS= (SF，I，0)的服务网元定义为SNU= (t，I。0。F。M)，其中；
[0224] (1)t是一个能够完成服务功能的变迁；
[0225] (2)It='t={Sil，s。，s。，…，sJ是变迁t的输入集，代表服务的输入参数集合； 〇t=t? = {s。。3。2, 3。3,…，S。。}代表服务的输出参数集合；
[022引 做Ft= (ItXt)U(tX0t)是有向 弧集合，表示服务的输入、输出参数的流关系；
[0227] (4)M是服务网元的标识，M ;ItU〇t-U ;
[022引 （5)变迁t在M下的发生规则为：
[022引 （a)V戶/:M(/，)=l，则变迁t在M下有发生权，记为M[t> ;
[0230] (b)若M[t〉，则t在标识M下能够发生并得到一个新的标识，记作，对于
[0231]
[0232] 利用服务网元来表示服务，能够有效地将服务的输入输出参数数量化。为了方便 模型表示，本发明将服务的输入、输出参数名作为变迁的输入、输出库所名。
[0233] 例如；一个火车篇查询服务：
[0234] WS"s= (SF"s,l"s，0"s);其中，1。日={(ii，D巧arture),山，Arrival)，山，Date), (i*,ID)}，并且 0。日={(0。price), (〇2,TrainNo), (〇3,time)}。"D巧arture", "Arrival", "Date", "ID", "price","TrainNo"和"time"分别代表出发地，目的地，日期，身份信息，票 价，列车号和出发时间。
[0235] 根据服务网元的定义，该服务经过模型化后如图2所示。
[0236] 1. 3服务簇
[0237] 本发明用基于本体计算服务功能相似度来聚簇。由于本发明主要是在服务聚簇的 基础上进行，因此只对服务聚簇进行简单的介绍。
[0238] 本发明基于现有技术中服务相似度计算方法来确定语义相似，若Sim佑Y)〉= 0. 8,则认为概念X与概念Y是语义相似的。
[0239] 有了上述语义相似的理论基础，根据服务功能的语义相似度将服务聚簇，形成服 务簇，下面给出服务簇的定义。
[0240] 定义服务簇；
[024^ 对于n个服务；WS。WS2, . . .，SC={wsi,WS2, . . .，WS。}是一个服务簇，其中；
[024引！/gN"+，wsu=(SFU，1山 0山SC心，且.Vi/，veN,,%SFu和SFV满足语义相似。
[0243] 为了高效的发现和替换服务，服务簇需要模型化。根据服务网元模型的构建方式， 将服务的参数数字化，同样，将服务簇中的参数数字化。
[0244] 由于一个服务簇中的参数较多，本发明引入参数矩阵来表示服务簇的参数。
[0245] 定义服务簇网元；
[024引一个有n个服务的服务簇；SC={w化简，…，W,，}，AeN"+，SNUk= (tk，Itk，0tk，Ftk，Mk)，服务簇网元被表示为SCNU= (SU，tc，I。0c，Fc，Me)，其中：
[0247] (1)SU= {SNUi，SNUs，SNUs，…，SNU。}是服务网元的集合；
[024引 （2)te是服务簇网元的变迁，它能够完成服务簇中各服务的功能；
[0249] 做I。0康示服务的输入、输出参数集，并且V尸S/('U()(.，尸:=作。。化'(仰/"/]/(〇， 其中：
[0巧0] (a)P.concept是服务簇中服务输入参数对应的语义概念；
[0251] (b)P. 1油le是一个nX1的矩阵，其中n是服务簇中服务的个数，并且P. 1油le是 服务簇中的服务相应P.cone巧t的值；
[025引 （4化=(IctXtc)U(teXOa)表示服务簇输入、输出参数的流关系；
[0巧引 巧)Me是服务簇网元的标识；
[0巧4] 根据服务簇网元的定义，将一个服务的输入参数值，作为服务簇输入矩阵的一行； 将该服务的输出参数值，作为服务簇输出参数矩阵的对应行。
[025引例如；一个火车票查询服务簇包括四个服务；wsi-WS4,服务网元模型如图3所示。 根据服务网元和服务簇网元的定义，构建出该服务簇的服务簇网元模型如图4所示。
[0256] 在图4中，I。和0。用两个矩阵表示，在下文中分别称该两个矩阵为输入矩阵和输 出矩阵。在服务簇中，服务的输入、输出参数被编号。
[0巧7] 在输入矩阵中，表示为"1"的，是对应的服务发生时所需要的参数。
[0巧引在输出矩阵中，表示为"1"的，是对应的服务发生后能够输出的参数。
[0巧9] 在输入输出矩阵中，每一行代表一个服务的输入输出参数值，而每一列，代表服务 簇中所有服务相应于某一参数的参数值。
[0260] 2、基于服务簇的服务发现组合与替换分析
[0261] 服务簇网元模型的建立能够提高服务的查找替换效率。
[0262] 在服务发现与组合阶段能够快速地筛选与服务请求功能不匹配的服务，进而缩小 替换服务的范围，使得服务发现与组合效率大大提高。
[0263] 下面本发明将提出一种基于服务簇的服务发现与组合算法，更进一步提高效率。
[0264] 2. 1服务发现
[0265] 在服务发现之前，对服务簇中的服务进行预处理能够有效的减少服务的查找范 围，提高服务发现效率。良好的服务匹配算法可W快速排除与服务请求不匹配的服务，然后 通过服务发现算法发现服务簇中满足服务请求的服务。
[026引 2. 11服务匹配算法
[0267] 在服务发现的过程中，首先需要通过服务匹配服务请求。服务匹配方法在提高服 务发现效率方面是至关重要的。因此，本发明首先给出一个服务匹配算法。
[026引在下述算法中，服务簇k的服务总数为m个，输入参数的总数为n;个，输出参数总 数为n。个。Iek，0ek，if和0t都分别代表服务簇的输入矩阵，输出矩阵，服务请求的输入矩阵 和输出矩阵。lek是一个mXni矩阵，Ouk是一个mXn。矩阵，it是一个1Xni矩阵，0t是一个 IXn。矩阵。iGkP(q)代表输入矩阵的第P行第q列的值。
[0269] 算法1服务匹配算法：
[0270] 输入；一个服务簇网元模型SCNUk=(SUk,tck,Ick，〇ck，Fck，Mck)，一个服务请求网元 Sr=(sf"i"oj;
[0271] 输出；Cl和C。，其中，Cl是一个mXn先阵，并且C。是一个mXn。矩阵；
[027引SI:Wlek的首行开始，依次匹配该行的每个值；
[0273] S2:若该行中元素的值小于或者等于if对应的值，则标记Cl对应位置的值为1 ;
[0274] S3:否则，标记为0;
[027引 S4:W0ck的首行开始，依次匹配该行的每个值；
[0276] S5:若该行中元素的值大于或者等于if对应的值，则标记Cl对应位置的值为1 ;
[0277] S6:否则，标记为0;
[0278] S7:输出矩阵。和矩阵C。；
[027引算法1是一种基于服务簇的服务匹配算法，其时间复杂度是mXni2+mXn。2。矩阵Ci被称之为输入匹配矩阵，矩阵C。称之为输出匹配矩阵。C/i(qi) =1表示服务wspi可W 满足第个参数需求。BP2(屯）=1表示服务wsp2可W满足第Q2个参数需求。
[0280] 通过算法1的服务匹配算法，服务簇输入/输出匹配矩阵将服务簇中的服务按照 当前服务请求统一表示服务匹配结果。服务输入/输出匹配矩阵中"1"代表对应的服务输 入/输出参数可W满足当前服务请求；而服务输入/输出矩阵中"0"代表对应的服务输入 /输出参数不能满足当前服务请求。根据该一特点，可W为实现服务发现效率的提高奠定坚 实的基础。
[0281] 算法1的提出可朗尋服务簇中的服务按照当前服务请求，给出统一的标记。该可 W为服务发现算法的提出奠定坚实的基础。根据算法1，下面给出服务发现的匹配定理。
[0282] 定理 1 ;
[028引服务需求Reg=(SFre。，Ireg，0reg)，服务WSb=(SFb，Ib，0b)，服务网元SNUb= (tb，Itb，0tb，Ftb，Mb)。矩阵Cl和矩阵C。分别是服务WSb相对于服务请求R6。的输入匹配矩阵 和输出匹配矩阵。如果
I则服务WSb可W满足服务输出请求 Req。
[0284] 证明；根据服务匹配算法，C/i(qi) = 1意味着服务wsp河W满足第个参数需求。 C2(屯）=1意味着服务WSp2可W满足第Q2个参数需求。
[0285] 进一步说，
表示服务wsb可W满足服务输入请求IU。的每个参数需 求
表示服务WSb可W满足服务输出请求0t。。的每个参数需求。
[028引故，如果
则服务WSb可W满足服务输出请求R。。， 证毕。
[0287] 2. 12服务发现算法
[028引算法1通过参数矩阵的匹配实现服务簇内快速筛选，从而更一进步缩小服务查找 范围。定理1为服务发现算法提供了有力的理论依据。
[0289] 算法2服务发现算法
[0290] 输入；输入匹配矩阵输出匹配矩阵C。；
[0291] 输出；S: -个服务集合；
[029引Sl:p= 1，护0;
[029引 S2:WCi的第P行开始，依次匹配该行的每个值；
[0294] S3:若该行中所有的值都为1，则跳到S5 ;
[029引 S4:否则P=P+1，循环该一匹配过程；
[0296] S5:依次匹配C。第P行的各值；
[0297] S6:若该行中所有的值都为1，则将该服务合并入集合S中，即S=SU{wsp};
[029引 S7:否则P=P+1，跳到S2 ;
[0299] S8 输出S.
[0300] 通过算法2可W发现服务簇中满足服务请求的服务。算法2输出的服务集合S中， 所有服务的输入输出匹配矩阵同为该意味着集合S中的每个服务都可W满足服 円 务请求。服务发现算法的时间复杂度为；mXni+mXn。
[0301]例如；一个服务请求Reg= (SFreq，Ireg，〇re。)，其中Ireg= [l，0，l，0，(U]，〇reg=[0，l，0,0，l，l]，服务簇SCNUk=(SUk，tck，Ick，0ck，Fck，M证）中有两个服务WSl，WS2。WSi= (5。，1。〇1),1 = 1,2。其中11=[1,0,0,1,0,1]，〇1=[1,1,0,0,1,1]，12二[1,1,1,0,0,1]， 〇2= [0, 1，1，0, 1，1]。
[030引根据算法1得到服务簇内服务的预处理结果；Cii= [1，1，1，0, 1，U，C。= [1，1，1，1，1，1]，并且向2= [1，1，1，1，1，1]，根据算法2得出服务WS2可W满足服务请求R。。。
[0303] 2. 2服务组合
[0304] 上述算法2可W在海量服务中，完成单个服务的服务发现。
[0305] 当服务组合体系中，单个服务失效时，可W利用算法2的方法进行服务发现及替 换。而在服务簇中，单个的服务可能不能满足服务请求，需要通过多个服务的组合来满足服 务请求。
[0306]当构成服务组合体系的单个或多个服务失效时，为了提高效率，将损失降到最低， 将服务组合模式保持不变。
[0307] 在服务簇中，选择与其功能相似且参数匹配的服务或服务组合将失效服务替换。 其中，服务簇中两个服务的组合包括服务的并行组合和串行组合。
[030引 3. 21服务并行组合
[0309] 基于上述内容，本发明首先对服务并行组合的方法进行描述。
[0310] 算法1中A"(屯）=0代表服务wspi的输入参数q1不能满足服务输入请求。换句话 说，在当前的服务请求条件下，服务WSpi不能发生。在服务组合发现的过程中，服务簇中的 该些服务可W不予考虑。在下文中，表示服务WSi和服务WSj的并行组合。WSilwSj 表不服务WSf和服务WSJ的串行组合。
[0311] 本发明提出一种新的概念，用于后文中对服务组合过程的描述。
[031引设a二比。bg,…，bj是 1Xk矩阵，其中扣e{0,1}, /巨N& 且内e抓，对于 V/eNA+，如果bi= 1，a可W表示为E，即，E= [1，…，1].对于V/eNa+，若bi=0,a可W表示为0，即，0=[0, 0,…，0]。
[031引在本发明中，a表示Petri网中的一个标识。并且aa2表示Vz'eNa+, bii^b2i0
[0314 ] 定义基元素： 防3巧]设a1=比…b。，…，bj且a2=比21A2,…Ak]是两个IXk矩阵，其中N,,+,V6i,'e{0, 1}，and/>2,'巨{0, 1}，/巨Na+。若aa2,则称a2是a1的一个基元 素。
[0316] 定义基集合：
[0317] 设C是一个IXk矩阵的集合。3C'cC如果VapeC，％eC'或者3而eC'，a。是 曰P的一个基元素，且VC"，Ic" |>Ic'I，则称C'是C的一个基集合。
[031引在服务簇中，任何服务都是没有编号的，为了标记服务簇中的服务，本发明提出一 种独特的方法。
[0319]定义服务组合标志（ServiceCompositionMarking,SCM);
[0320] 用于标记当前服务请求下的服务组合的服务基集合，其初始标志为0。
[0321] 在服务簇中，通过服务与当前服务请求的匹配结果，可W发现服务间的组合关系。 根据算法1可W提出服务匹配的运算方法。
[0322] 定义匹配运算：
[032引SNUa=(ta,Ita，0ta，Fta，Ma)是一个服务网元，R=佛"I"Or)是一个服务请求。
[0324] 匹配运算被定义为：
[0325] (1) /,' 0 /化=[修"啦蝴)，w(5巧)0 "如邮),...,w(w.to)0 "如口切化其中，，円知切
[032引（引@ /H(.S'"")0 /H(.S7V,|), /H(.S77)2)，...，"!柄
，打el^,j.eN,,+ 0
[0327] 从上述定义可W看出，当单个服务满足服务请求，意味着服务输入请求可W引发 服务变迁，并且服务输出标志可W满足服务请求。由定理1可W提出一个新的定理如下： [032引 定理2 ;
[0329] Req=(SFre。，Ireg，〇reg)是一个服务请求，SNUb=(tb，1扣，〇扣，Ftb，Mb)是WSb的一个服 务网元，如果知=丘且如@如广凡则WSb满足服务请求Re。。
[0330] 证明：由于/，巧魄*=￡且化@0,'矿&根据匹配运算定义， "!(.st")>/,!(.s7，"）and,7如/，巧)> "z(.sT巧 并且〇b可W满足0U。。因此服务WSb满足服务请求RW，证毕。
[0331] 定义服务簇匹配矩阵：
[0332] WSreq=佛re。，Ire。，Ore。）是一个服务请求。SCNUa=佛。，t。。，la。，0。,。，F。,。，M。）是一 个服务簇网元。服务簇的输入/输出匹配矩阵被定义为：
[0333]
[0336]Ci和C。代表了服务簇中的服务匹配服务请求的标识。根据算法2,满足服务请求 的单个服务可W被发现。然而在服务簇中，单个服务可W不能满足服务请求，而多个服务的 组合可能会满足服务请求。因此，下面提出服务组合定理。在下文中，WSi^WSj.表示服务WSi和服务WS j的服务组合。
[0337]定理 3;
[03 測虹 …，mjT(C0=虹。i，m02，m03,…，mjT)是服务簇的输入 / 输 出匹配矩阵，其中叫二虹j(Sii)，mj(s。)，…，nij(Sik)]且m〇j=虹j(s〇i)，mj(s〇2),… ，mJ(s。k)]，n，Ae]^r，z'JeN,，+。若服务组合wSi?wSj.可W满足服务请求的充分条件是：
[033引（l)mij=E且mn=E;
[0340]
[0341] 证明；（1)对于mii= E，根据服务簇匹配矩阵定义，知與也=￡。从匹配运算定义可 W看出V/eN"+，m(srii)〉m(si。）。因此服务wsi的输入参数都可W满足服务输入请求，服务 簇中的服务WS河W发生。相似地，由于mu=E，可W得出，服务wsj.的输入参数同样都可W满足服务输入请求的所有参数，服务簇中的服务WSj.也有发生权。所W，服务组合WSWSj.， 在当前服务输入请求的条件下，满足发生条件。
[03化| 似因为巧=尼，所WVpeN&+,mj(s0p) = 1ormi(s0p) = 1.根据 服务簇匹配矩阵定义，服务请求的所有输出参数都可W由服务WSi或WSj.满足。故， Vwe物;+，3"?/00。)，所啦0。)>7?切'0。)，/€哪+，7€14+。因此，根据服务匹配算法，服务组合 WSj斯输出参数可W与服务输出请求参数相匹配。从而，服务组合WS冷WSj.可W满 足服务的输出请求。综上所述，服务组合WSj.可W满足服务的输入请求，证毕。
[034引3. 22服务串行组合
[0344] 由于本发明中的服务簇是W服务功能相似度来聚簇，所W从服务功能参数上说， 当服务簇内发生服务失效时，并行组合替换的成功率相比串行组合更大一些。在服务簇粒 度足够小的情况下，串行组合服务替换可W忽略，不予考虑。本发明中的服务簇粒度足够 小，串行组合发生率较低，所W，本发明只给出简要的算法思想。在下文中，wSpMws。表示服 务WSp和服务WS。的串行组合。
[0345]定理 4;
[034引 SCNU=(SU，tc，Ic，0c，Fc，Mc)为一个服务簇网元，其中， We把U化，戶=(戶（'疆'(抑戶沁/沁），服务输入、输出参数的个数分别为k，1。服务请求R=佛,，Ir，0r)，服务簇匹配矩阵：Ci，C。。若C/声[1，1，…，1]，且C/a) = 0时，WS。同时 满足下面两个条件：
[0347] (1)却G N/十，1口. concept = 0". concept,且C〇q(j) = 1 ;
[034引 似(：1。=[1，1，…，U;
[034引贝1JWS。IIWSp可W满足服务请求R。
[0350]证明；因为C/声[1，1，…，1]，根据定理1，服务WSp满足服务输入请求。且根据服 务网元定义，VC/(/)=l时，服务wSp才能引发。当马eN^，Ici.conc巧t= 〇cj.concept时， 则服务簇中存在输入请求与输出请求语义相同。若(V(j) = 1则服务WSp的输出请求可W满足wsp的输入请求。而C/= [1，1，…，1]，根据服务网元定义，服务WS。可W满足当前服 务请求，可W引发。故可W通过先引发WS。后引发WSP，来满足服务请求。 防351 ] 综合上述，WS。IIwSp可W满足服务请求R。
[0巧2] 定理4的提出对服务的串行组合提供了理论依据。由定理4可知要想服务簇内发 生串行组合，服务簇必须有相同的输入输出语义参数，而该可能需要服务的粒度足够大。根 据定理4,下面提出服务串行组合算法：
[0巧3] 算法3服务串行组合算法
[0354]输入；服务簇网元SCNU=柳，tc,Ic，〇c，Fc，Me)，其中，We/VU化，尸=(C聊，f心6心)，服务簇匹配矩阵：Ci，C。，服务输入、输出参数的个数分别为k，1。
[035引输出；服务集合B;
[0356]S1:依次匹配服务的输入、输出参数的参数语义； 防357] S2:若存在 1口.concept= 0。'.concept,依次匹配Ci(i);
[0巧引 S3:若C/a) = 0,W。的首行开始，依次匹配该行的每个值；
[0359]S4:若C/= [1，1，…，1]，匹配相应的C〇a;
[0360] S5:若C〇a(j) = 1 且C〇auC〇P= [1，1，…，1],则B=BU{ws。}，循环该一过程；
[0361] S6:若公=0，输出"没有满足条件的串行服务组合"；
[036引 S7:输出集合B。
[0363] 算法3是在服务簇中查找能与WS。串行组合的服务，集合B为满足条件的服务集 合。
[0364] 2. 3服务替换
[0365] 服务簇的提出可W大大缩小查找服务的范围，提高查找效率。在同一个服务簇中， 体现各个服务共性的同时，需要发现服务的个性，从而快速发现替换服务。因此，需要有一 种标记服务的方法。SCM表示了服务的基集合，用SCM来发现单一替代服务和组合替代服 务。下面给出SCM的算法。
[0366] 算法4服务组合标识算法
[0367] 输入；服务簇SC= {wsi,WS2,…，WS。}，服务簇匹配矩阵：Ci，C〇;
[036引 输出；SCM
[036引 S1:依次匹配叫，若m。'声[1, 1,…，1],贝IjSCMj标记为巫；
[0370] S2:匹配m〇k，若m〇k= [1，1，…，]_]，SCMk标记为 0 ;
[0371]S3:若m〇k声[1，1，…，1]，找到所有不为巫的SCMP且若"U货"V=E，贝IJ J气4u{m〇p}，fEN打+;
[0；37引 S4:若A=巫，贝1JSCMk=巫；
[0；37引 S5:否则标记SCMk为A的基集合；
[0374]S6:若在所有的SCM中有一列全为"1"，在所有SCM中删掉该一列；
[037引 S7:输出SCM。
[0376] 根据算法4,基于服务簇网元模型可W得到SCM的值。SCM=〇代表当前服务簇 中没有服务可W满足服务请求。SCM= 0代表单个服务可W满足服务请求。而，如果SCMk 是一个集合，SCMk中的每个元素都代表着一个或者一组服务，在该组服务中的每一个服务 都可W通过与WSk组合满足当前服务请求。
[0377] 在服务请求参数中，考虑范围内所有服务都可W满足的请求参数可W人为是可忽 略参数。在服务簇输入、输出匹配矩阵中，可忽略参数所对应的那一列，可W认为是可忽略 列。
[0378] SCM可W将服务簇中的服务分类。若SCM= 〇,在服务替换过程中，相应的服务可 W不必考虑。然而，通常情况下，SCM为一个集合。在该种情况下，不能快速发现对应的组 合服务。为了解决该个问题，在算法4中，将SCM中的可忽略列删除。从而方便通过SCM来 快速发现可替换的组合服务。
[OW引利用SCM发现组合服务时，需要提出一种组合规则。在下文中，SCMkm代表SCMk的 第m个元素。是SCMJ勺第1列，/?，化佔沪，ancU'eK/。一种组合规则被定义如下。
[0380] 定义组合规则（CompositionRule);SC= {wsi,WS2, ...，WS。}是一个服务簇；其 中，W尸口巧，么化SCM/)，z'eN/。SCMk丄SCMp=SCMki丄SCMpi丄SCMk2丄 8〔1。2丄". 丄SCMkn丄SCMpn，其中，SCM虹丄SCMpm= [S。S2,…，S。]且
[0381] 根据组合规则定义，可W通过SCM.快速发现可替换的组合服务。为了更好的证实 该一结论，下面给出两个定理。
[0382] 定理 5 ;
[038引假设服务簇SC= {wsi，WS2, . . .，WS。}中存在一个失效服务WSm，R= (SF,，I,，0,)是 服务请求。若WSk是WSm的一个替换服务，则WSk满足下面条件之一：
[0384] (l)SCMk=0;
[03财 似 3SCMa7'，SCMmi，SCMkj《SCMmi，内巨 且,《，皮eN"+。
[038引证明；（1)若SCMk= 0,根据服务组合标识算法，可知m。=E且mDk=E。根据匹 配运算定义，/,御A-=扔化@0尸扔根据定理2,可W得出WSk是WSm的一个替换服务。
[0387]似若 350旬且SCMmiESCMm，SCMw=SCMmi,根据算法 4,有一组服务与SCMb.相关，当然也与SCMm湘关。假设与SCMmi相关的服务为WSg，通过算法4可知，mim= E,mig=Eandm。"曲"。广怎。由定理3可W得出wSgOWSm可W满足服务请求R。相似地，WSg 也是与SCMkj相关的服务，同样mik=E,mig=EandWoA货"％=￡。因此，服务WSk是服务WSm 的一个替换服务。
[038引若弘CMA7'eSCA4且SCMmiESCMm，SCMy<SCMmi，根据服务组合标识算法可知，SCMk是A的一个基集合。由基元素定义可知，SCMy是SCMmi的一个基元素。假设与SCMmi相关的 一个服务是WSg，根据定理3可W得到，WSm可W满足服务请求R。通过算法4可W看 出，服务WSg同样与SCMkj相关。相似地，WSgOwSk也可W满足服务请求。因此，WSk是WSm 的一个替换服务。
[ 0389] 根据定理5可W发现替换服务，而在服务簇中，组合服务也可替换失效服务。为了 发现组合替换服务，可W提出下面定理。
[0390]定理6 ;
[03川一个服务簇SC= {wsi,WS2, . . . ,WS。}，其中，w&=(公Tfc<SFa-，，化,504)，AgN,7+。服 务簇中存在一个失效服务WSm，如果SCMp丄SCM。= 0，则WSWS。是WSm的一个替换服务 组合，化祈，且p，geNn+。
[039引证明：因为SCMp丄SCM。= 0,由组合规则定义首先可W看出，SCMP声巫and SCM。声巫。通过服务组合标识算法可知，mip=E且miq=E。根据组合规则定义，3各eNn+, Spgi= 0或3AeN"+，8也1= 0。设与Spgi相关的那一列标号为mp(s0v)，mq(s0v)。则由算法4 可知，nip(S0v)= 1或mq(S0v)= 1。根据定理3,邸货护故，WSp^WS。是服务WSm的一 个替换服务组合。
[0393] 有了上述算法与定理的支撑，提出一种可W发现单一服务和组合服务的服务替换 算法：
[0394] 算法5服务替换算法
[039引输入；SC= {wSi,WS2, . . .，WS。}，失效服务WSm;
[039引输出；一个替换服务集合A;
[0397] S0:A=巫；
[039引 S1:若失效服务的SCMm=巫或SCMm= 0
[0399] S1. 1:匹配SCM，若 3 5"CM/；. =0,则将服务wSk并入集合A中，A=AU(wsJ;
[0400]SI.2:若匹配存在SCMi，SCMk，SCMi丄SCMk= 0,则将wsi和wsk的组合并入集合A 中，即A=AU{讯3冷wsJ;
[0401]S2:否则，若失效服务的SCMm声巫且SCMm声0 ;
[040引S2. 1:如果匹配SCMk= 0,则将服务wsk并入集合A中，A=AU{wsJ;
[040引S2.2:若匹配存在SCMyESCMk，SCM血GSCMm，且SCMy《SCM血，则将服务wsk并 入集合A中，A=AU(wsJ;
[0404]S2. 3:如果匹配SCMi，SCMk，SCMi丄SCMk= 0,则将wsi和wsk的组合并入集合A中， A=AU{wSjOws；
[0405]S3:若A=巫；
[0406] S3. 1:若SCMm中存在某一列的值为"1"，而其他服务的在该列的值都不为"1"，则 将该一列在所有的SCM中移除，转到S2;
[0407]S3. 2:否则，输出"没有满足条件的替换服务"
[0408]S4:输出A，即为满足条件的替换服务集合。
[0409] 在算法5中，首先发现单个服务是否能替换失效服务，若单个服务不能替换失效 服务，考虑组合服务替换。算法5中，在最好情况下的时间复杂度，仅为n。下面通过一个实 例来进一步描述该个算法。
[0410] 3. 4火车订票服务簇实例
[0411] 现有一个火车订票系统包括3个服务簇；一个安全管理（safetydetection)服务 簇，一个查询（ticketinquiry)服务簇和一个订票化ooking)服务簇。
[0412] 它们的服务簇组合关系是；safetydetection-ticketinquiiT-booking。在 查询服务簇中，有10个服务；WSi，WS2, . . .，WSi。。查询服务簇的服务簇网元模型见图5。
[0413] 在查询服务簇中，现存在一个失效服务，为了确保服务簇组合模型的模式不变，月良 务簇必须满足一个服务请求。该服务请求为；而。。。1,,^[1 1 1 1 0] - [0 1 0 1 1 1]。
[0414] 根据匹配运算定义，可W得到服务簇的输入输出匹配矩阵，如图6所示。
[0415] 由输入输出匹配矩阵可W快速的发现不满足服务输入请求的服务，并予W排除缩 小查询范围。
[041引通过算法4可W得到服务簇inquiry中每个服务的SCM值，所得的结果显示如表 1 ：
[0417] 表1查询服务簇的服务组合标识
[0418]
[0419] 在表1中，每一行显示了服务簇中服务的SCM。 '
[0420] 服务簇i叫uiry中的10个服务可W通过SCM被清楚地分类。如果WS4为失效服 务，服务簇中有SCMi丄SCMs= 0,根据定理6,WS8是WS4的一个替换服务。如果WS2失效， 从表1可W看出SCM2i=SCMei，根据定理5,wse是WS2的一个替换服务。
[0421] 通过算法5,服务簇中各服务失效时，它们的替换服务可W统计为表2 :
[0422] 表2不同失效服务下的替换服务
[0423]
[0424] 从表2中可W看出，服务簇中，不同的服务失效，它们的替换服务也不同，而且替 换服务的数量也不相同。有的服务失效通过单一服务替换即可，而有的服务失效，单一服务 无法完成替换，需要组合服务来替换。
[0425] 在火车订票服务簇实例中，只演示了服务簇中单个服务失效时的情形。当服务簇 中多个服务失效时，仍然可W通过算法4得到SCM，而定理5和定理6仍然适用。失效服务 的替换服务扔可W通过算法5得到，在该里就不再详述。
[042引 3实验过程
[0427]本发明利用上述相关算法，并采用C#语言编写，可随机生成本体树、随机生成服 务簇，并能随机选取服务模拟失效，统计每次查找时间。
[042引设计实验平台自动生成指定数量的服务，根据本发明提出的方法模拟服务发现过 程、W及单一服务替换与组合服务替换过程，并记录其响应时间。
[0429] 在实验设计环节，首先对本发明提出的服务发现算法与传统的服务发现算法进行 比较，从而验证本发明提出的服务发现算法的有效性。然后根据本发明的实验设计思路，对 本发明提出的服务替换算法与原有的替换算法进行比较。替换算法的比较分为两个方面， 一种是考虑单个服务替换效率，一种是考虑服务组合替换效率。
[0430] 替换算法比较实验中，在服务的替换效率方面，对原有的服务替换算法与本发明 基于服务簇的服务替换算法进行了比较分析。由于本发明提出的相关方法是基于服务簇的 基础上且鉴于目前没有相关的平台和Web服务库可用，本实验结果也是在服务簇已构建的 基本情况下产生。因此，实验中将采用自上而下的方式产生模拟数据。首先，采用了已提出 的方法建立领域本体树。然后定义服务簇，标注服务簇的输入/输出参数，并根据服务簇产 生簇内的相关服务。本发明采用C#语言编程，并进行仿真模拟实验。算法比较实验设计如 下：
[0431] ①构建领域本体树，生成服务簇并标注相关参数，从而自动生成簇内相关服务和 产生服务参数。
[0432] ②在实验中随机选取服务并模拟服务失效，对所选服务的输入输出参数进行随机 指定，从而达到模拟实验的效果。
[0433] ⑨单个服务替换查找成功时，计算响应时间仅考虑单个服务的发现时间和替换时 间，如果组合服务替换查找，计算响应时间是考虑发现服务时间、组合服务时间W及替换服 务时间。
[0434] ④根据服务发现算法，在服务个数不同的情况下分别记录服务发现的响应时间。
[0435] ⑥在本发明中，响应时间是多次实验的平均值。
[0436] ⑧在实验中，服务簇中服务个数分别为100、200.....500。为了避免偶然数据，本 实验重复做100次。
[0437] 3. 1服务发现算法比较
[0438] 首先根据本发明提出的服务发现算法与传统的服务发现算法进行比较，每次随机 生成服务请求100个。与服务替换算法设计相似，分别记录服务簇中服务个数分别为100、 200、...、500时的响应时间。得到的实验结果如图7所示。
[043引图7中，横坐标为服务的数量，纵坐标为服务发现的响应时间；带有方形标记线的 为本发明中服务发现算法的响应时间，带有圆形标记线的为传统的服务发现算法的响应时 间。
[0440] 从图7中可W得出结论：
[0441] 本发明中服务发现算法的效率是明显高于传统服务发现算法的；随着服务数量的 增多两种服务发现算法的效率有所下降，而相对传统的发现算法，本发明所提出的服务发 现算法受服务数量的影响较小。
[0442] 3. 2服务替换算法比较
[0443] 本实验对服务替换响应时间的比较分析分为两个实验；
[0444] 实验一；对于服务的单一替换按照设计思路，对两种方法进行实验比较；
[0445] 实验二：对于组合服务替换按照设计思路，对两种方法进行实验数据比较。
[0446] 在本发明的实验平台中，经过多次实验，得出实验一的实验结果如图8所示。而实 验二的实验结果相关数据如图9所示。
[0447] 在图8中，横坐标为服务的数量，纵坐标为服务发现的响应时间；带有方形标记线 的为本发明中服务替换算法的响应时间，带有圆形标记线的为传统的服务替换算法的响应 时间。
[044引在图8中可W看出，两种替换方法的响应时间随着服务数量的增多而增长。然而 在响应时间的增长速率上比较，本发明中的服务替换方法的增长速率低于传统的服务替换 方法。从曲线走势上看，随着服务数量的增多，两条曲线之间的距离越来越大。从曲线整体 上来看，本发明服务替换方法的响应时间稳定低于传统的服务替换方法的响应时间。
[044引图8中，在服务簇内服务相同的基础上，本发明中的服务替换算法平均响应时间 占传统服务替换方法的68. 8%。
[0450] 在图9中，横坐标为服务的数量，纵坐标为服务发现的响应时间；带有菱形标记线 的为本发明中服务替换算法的响应时间，带有=角形形标记线的为传统的服务替换算法的 响应时间。
[045。在图9中，服务簇内服务相同的基础上，本发明提出的服务替换算法平均响应时 间占传统服务替换方法的45. 6%。
[0452] 综合图8和图9可W得到实验结论：
[0453] 第一，两种算法的响应时间都随服务数量增多而增长；
[0454] 第二，本发明服务替换算法的效率明显低于传统的服务替换算法；
[0455] 第=，两种替换方法的效率均受服务数量影响，而本发明服务替换算法的效率受 服务数量的影响较小。
[0456] 实验结果证实了本发明所提出的服务替换算法的正确性和有效性，且替换效率特 别是组合替换效率有了明显的提高。
[0457] 通过本发明与传统的服务发现算法、W及服务替换算法的实验比较，验证了本发 明所提出的服务发现算法和服务替换算法的有效性和高效性。
[0458] 本发明在服务簇已建立的基础上实现了服务的发现与替换，利用Petri网定义服 务和服务簇的形式化模型，提出了服务匹配方法和服务组合方法，并通过理论证明、实例演 示、及仿真实验验证了本发明方法的正确性、实用性及有效性。
[0459] 当然，W上说明仅仅为本发明的较佳实施例，本发明并不限于列举上述实施例，应 当说明的是，任何熟悉本领域的技术人员在本说明书的教导下，所做出的所有等同替代、明 显变形形式，均落在本说明书的实质范围之内，理应受到本发明的保护。
【主权项】
1.基于服务簇的服务组合与替换方法，其特征在于，包括如下步骤： a、构建Web服务和服务簇的形式化模型 定义N是一个自然数集合，即N={〇, 1，2,···}，而设定NitHO, 1，2,_··，幻，Ν+=Ν\{0}，且 Ν/=ΝαΛ{0}； 定义Petri网： 一个Petri网表示为一个四元组PN = (S，T ;F，MO)，其中， (I)S是一个有限库所集； ⑵T是一个有限变迀集，且化作0, 5ηΓ=0; (3) /USx7)u(rxS)是一个弧集； (4) dom(F) U cod (F) = S U T，其中， dom(F)={.\-e5oT| ByeSvjT: (λ\ VjeZ7I, Cod(F)= [ veSoTl BxeSvjT: (.v,y)eF\ ； (5) M: 为网PN的一个标识，其中， Vse5*，M(s)表示标识M下库所s中的托肯数，Mci是初始标识； 定义输入/输出集： 设PN = (S，T;F，Mci)为一个Petri网，X e S U T为网N的一个元素，记： ? X = {y I y e S U T~ (y, X) e F}称为 X 的输入集； x' = {y Iy e S u τ~ (X，y) e F}称为 X 的输出集； 'X U X'称为元素 X的外延； 在Petri网中，采用一个圆圈表示一个库所，用一个矩形表示一个变迀；若（x，y) eF， 则x到y的一条有向边表示它们的流关系； 定义引发规则： 设PN = (S，T ;F，Mtl)为一个Petri网，则其具有如下的变迀发生规则： 1) 对于变迀t e T，如果V.veS: .s'eV-Mdd，则变迀t在标识M有发生权，记为M[t > ; 2) 如果M[t >，则在标识M下，变迀t能够发生，从标识M发生变迀t得到一个新的标 识 M'，记为 M[t>M'，VseS』，根据上述Petri网的定义，构建Web服务的形式化模型如下： 定义Web服务： 一个Web服务描述为一个四元组WS = (SF，I，0)，其中： (1) SF表示服务的功能语义描述； (2) 1、0表示服务的输入、输出参数集，并且//^/^0，？=化仙1^，？.(：〇11(3印〇，其中， ① P. name是输入、输出参数名； ②P. concept是一个输入、输出参数的本体概念，用以表示参数的语义； 定义服务请求： 一个服务请求表示为R = (SI U OJ，其中： (1) S匕表示服务请求的功能语义描述； (2) 仁代表服务请求者可提供的输入参数集； (3) Or代表服务请求者需要输出的参数集； 定义服务网元： 服务WS = (SF，I，0)的服务网元定义为SNU = (t，It，0t，Ft，M)，其中： (1) t是一个能够完成服务功能的变迀； (2) It= 't = {sn, si2, si3,…，sin}是变迀t的输入集，代表服务的输入参数集合；Ot = t' = {sQl, Sq2, Sq3,…，SraJ代表服务的输出参数集合； (3) Ft= (ItXt) U (tX0t)是有向弧集合，表示服务的输入、输出参数的流关系； (4) M是服务网兀的标识，M :It U 0 t- {0, 1}; (5) 变迀t在M下的发生规则为： ① Vpe/: M(/;)=l，则变迀t在M下有发生权，记为M[t> ; ② 若M [t>，则t在标识M下能够发生并得到一个新的标识，记作M [t W，对于 J； vj〇r定义服务簇： 对于η个服务WS1, ws2, . . .，SC = (Ws1, ws2, . . .，wsJ是一个服务簇，其中： i/eN/，Wsu= (SF u，Iu，0U，SCMu)，且V?. veN/，SFu和 SF v满足语义相似； 定义服务簇网元： 一个有 η 个服务的服务簇：SC = (Ws1, ws2, ...，wsn}，々e N"+，SNUk = (tk，Itk，0tk，Ftk，Mk)，服务簇网元表示为 SCNU = (SU，tc，Ic，0C，Fc，Mc)，其中： (1) SU = (SNU1, SNU2, SNU3, ···，SNUJ 是服务网元的集合； (2) t。是服务簇网元的变迀，且能够完成服务簇中各服务的功能； (3) I。、Oc分别表示服务的输入、输出参数集，并且VPeicU Oc，P= (P. conc印t，P. lable)，其中： ① P. concept是服务簇中服务输入参数对应的语义概念； ② P. Iable是一个nX 1的矩阵，其中，η是服务簇中服务的个数，并且P. Iable是服务 簇中的服务相应Ρ. concept的值； (4) F。= (IetXte) U (I^XOet)表示服务簇输入、输出参数的流关系； (5) 1^是服务簇网元的标识； 根据服务簇网元的定义，将一个服务的输入参数值作为服务簇输入矩阵的一行；将该 服务的输出参数值作为服务簇输出参数矩阵的对应行； b、基于服务簇的服务发现、组合与替换 设服务簇k的服务总数为m个，输入参数的总数为叫个，输出参数总数为η。个；I a、Oa、 分别代表服务簇的输入矩阵、服务簇的输出矩阵、服务请求的输入矩阵、以及服务请求 的输出矩阵；其中，Ia是一个mXn i矩阵，O a是一个mXn。矩阵，i 1?是一个I Xn i矩阵，〇 ^是 一个I X η。矩阵；I ttp(q)代表输入矩阵的第p行第q列的值； 输入一个服务簇网元模型SCNUk= (SU k, ?α, Iek, Oa, Fa, Ma)和一个服务请求网元S1 = {sfr，ir，〇r}，基于服务簇的服务匹配输出(:冴口 C。，其中，C1表示输入匹配矩阵，是一个mXη 土 矩阵；Q表示输出匹配矩阵，是一个mXn。矩阵； 基于服务簇的服务匹配的过程如下： SI:以Ia的首行开始，依次匹配该行的每个值； S2:若该行中元素的值小于或者等于、对应的值，则标记(^对应位置的值为1 ; S3:否则，标记为0 ; S4:以Oa的首行开始，依次匹配该行的每个值； S5:若该行中元素的值大于或者等于、对应的值，则标记(^对应位置的值为1 ; S6:否则，标记为0 ; S7:输出矩阵C1和矩阵C ^ 其中，服务匹配的时间复杂度是mXn^+mXn。2; 输入矩阵C1和矩阵C ^，基于上述服务匹配过程提出服务发现的过程，进而得到一个服 务集合S ;服务发现的具体过程如下： SI :p = 1, 5=0； S2: WC1的第p行开始，依次匹配该行的每个值； S3:若该行中所有的值都为1，则跳到S5 ; S4:否则p = p+1，循环这一匹配过程； S5:依次匹配(^第？行的各值； S6:若该行中所有的值都为1，则将该服务合并入集合S中，即S = S U {wsp}; S7:否则p = p+1，跳到S2 ; S8输出服务集合S ; 通过服务发现过程发现服务簇中满足服务请求的服务；服务发现输出的服务集合S 中，所有服务的输入输出匹配矩阵同为即服务集合S中的每个服务都满足服务 请求；服务发现过程的时间复杂度为：mXrii+mXn ; 定义WSiO WS j表示服务WS i和服务WS j的并行组合；定义WS i I WSj表示服务ws i和服务 WSj的串行组合； 设 a = [Id1, b2,…，bk]是一个 I Xk 矩阵，其中，IDiG {〇, 1}，/e Να+，且《eN+，对于 We Nt+，如果 h= 1，α 表示为 E，即 E = [1，…，1]; 对于V/e Ν/，若h= 0, α表示为〇,即〇 = [〇, 〇,…，〇]; 其中，α表示Petri网中的一个标识；并且α ρ α 2表示V ζ·￡ ΝΛ b 2i; 定义基元素： 设 a i= [b n，b12，…，blk]且 a 2= [b 21，b22，…，b2k]是两个 IXk 矩阵，其中 neN+，kN"+，於成川，1}，and b2ie {〇，1}，z.eNA+;若 α 2,则称（12是 a i的一个 基元素； 定义基集合： 设C是一个IXk矩阵的集合；f gC，如果apec'或者％是α p的一个基元素，且V C"，I C" I > I C' I，则称C'是C的一个基集合； 定义服务组合标志： 用于标记当前服务请求下的服务组合的服务基集合，其初始标志为0; 根据服务匹配过程提出服务匹配的运算方法如下： 定义匹配运算： SNUa= (t a, Ita, Ota, Fta, Ma)是一个服务网元，R = (SFr, Ir, Or)是一个服务请求； 匹配运算被定义为：定义服务簇匹配矩阵： WSrai= (SF _ I_ Orai)是一个服务请求； SCNUa= (SE a，tCa，Icta，0cta，Fcta，M a)是一个服务簇网元； 服务簇的输入/输出匹配矩阵被定义为：其中，we N+, ne N+, Nw+，j'e N"+, mk(sI(0)j) = 0,1 ; 输入服务簇网元SCNU = (SU，t。，I。，0。，F。，M。）和服务簇的匹配矩阵Q、Q，其中，VPe IcU 0C，P = (P. cone印t，P. Iable)，服务输入、输出参数的个数分别为k，1 ;输出服务集合 B ； 则服务串行组合的过程如下： si:依次匹配服务的输入、输出参数的参数语义； S2:若存在 Ici. concept = Ocj. concept，依次匹配 C1Q); S3:若C/⑴=0, WC1的首行开始，依次匹配该行的每个值； S4:若(V1= [1，1，…，1]，匹配相应的(V; S5:若C (j) = 1 且CU C Qp= [1，1，…，1]，则B = B U IwstJ，循环这一过程； S6:若β =0，输出"没有满足条件的串行服务组合"； S7:输出服务集合B ; SCM表示服务的基集合，通过SCM的过程体现服务簇中服务间的共性与个性，从而用 SCM来发现单一替代服务和组合替代服务； 输入服务簇SC = (WS1, WS2,…，WS1J和服务簇的匹配矩阵Cp C〇, SCM过程如下： Sl:依次匹配Hilj,若Hilj乒[1，1，…，1]，贝丨」SCM标记为Φ ; S2:匹配!!^，若 mok= [1，1，…，1]，SCMk标记为 0 ; S3:若mok乒[1，1，…，1]，找到所有不为Φ的SCMp且若所〇册~=五，则A = A U ImJ， P^Nn+- S4:若 A = Φ，则 SCMk= Φ ; S5:否则标记SCMk为A的基集合； S6:若在所有的SCM中有一列全为1，在所有SCM中删掉这一列； S7:输出 SCM ; 定义SCMkm代表SCMk的第m个元素 ；s ^是SCM km的第1列，n，m，/el, and 定 义组合规则： SC = {wSuWSw.^wsJ 是一个服务簇；其中，WSi= (SFolDOoSCMih/eN,,+; SCMk 丄 SCMp= SCMklI SCMplI SCMk2I SCMp2丄…丄 SCMknI SCM pn， 其中，SCMkniI SCMpni= [s " S2，…，sj 且，《e#，女，/;eN"+ ; 输入SC = (Ws1, ws2, ...，wsn}和失效服务wsm，输出替换服务集合A ; 则发现单一服务和组合服务的服务替换的过程如下： S0:A = Φ ； SI:若失效服务的SCMm= Φ或SCM m= 0 ; SI. 1:匹配SCM，若彐<SCMa=0,则将服务WSk并入集合A中，A = A U {ws k}; 51. 2:若匹配存在SCMi, SCMk，SCMiI SCMk= 0,则将ws JP wsk的组合并入集合A中， 即 A = A U (WsiO ws k}; S2:否则，若失效服务的SCMy Φ且SCM 0 ; 52. 1:如果匹配SCMk= 0,则将服务ws k并入集合A中，A = A U {ws k}; S2. 2:若匹配存在SCMkje SCM k，SCMmhe SCMm，且SCMkj彡SCMmh，则将服务wsk并入集合 A 中，A = A U {wsk}; S2. 3:如果匹配SCMi, SCMk，SCMiI SCMk= 0,则将ws JP wsk的组合并入集合A中，A = A U (WSiO ws k}； S3:若A = Φ ; S3. I:若SCMm中存在某一列的值为1，而其他服务的在该列的值都不为1，则将这一列 在所有的SCM中移除，转到S2 ; S3. 2:否则，输出"没有满足条件的替换服务"； S4:输出A，即为满足条件的替换服务集合。
【专利摘要】本发明公开了一种基于服务簇的服务组合与替换方法。本发明借助已有的服务聚簇方法构建服务簇，并基于Petri网提出服务及服务簇的形式化描述方法；将服务的输入输出参数抽象表示，通过参数矩阵来描述服务的输入输出参数；本发明中的服务匹配方法使服务簇中的服务间能够充分共性与个性，通过缩小服务查找范围，从而提高服务发现与组合效率；通过对服务簇模型的改进，提出Web服务组合替换方法；对服务簇内服务的并行组合与串行组合分别进行了描述，在服务簇内实现快速服务组合，进而实现高效率的服务组合替换；本发明中的服务替换方法，不仅能实现服务簇内单一服务替换,而且能实现服务簇内服务组合替换。
【IPC分类】H04L29/08
【公开号】CN104902018
【申请号】CN201510259703
【发明人】杜玉越, 盖俊静, 盖俊虎, 沙静, 刘伟
【申请人】山东科技大学
【公开日】2015年9月9日
【申请日】2015年5月20日
【技术领域】
[0001] 本发明设及一种基于服务簇的服务组合与替换方法。
【背景技术】
[0002] 在全球信息化大潮的推动下，Web服务技术得到迅猛的发展，Web服务的应用尤为 常见。随着网络资源的丰富，服务的数量大量增加，该使服务发现与替换面临着巨大的压 力。服务簇的提出大大缩小了服务发现的查找范围，使服务发现效率有效提高。而在服务 簇中，各个服务具有参数不确定性，需要一种统一的形式化描述方法。在Web服务的形式化 描述中，不仅要给出服务自身的特征，还要能够方便在服务簇的描述中给出服务之间的交 互特点，该样方便服务的发现与组合，因此，需要给出服务及服务簇的合理规范的形式化描 述。由于服务的动态性，在响应用户请求的过程中，可能存在一些服务失效。在传统的服务 组合模式中，服务的失效会造成服务流程的中断。在实际应用中，流程的中断可能会造成巨 大的损失。
[0003] 目前，国内外对于服务形式化模型的研究主要基于Petri网、进程代数和有限状 态自动机、语义网等几类工具，并且都取得了一定的成果，然而服务替换的研究还处在初级 阶段。现有的大多数研究都是围绕解决现有的Web服务替换机制中存在的查准率不高的问 题，而很少有在聚类得到的服务集合（即服务簇，Servicecluster)层面上建模并进行服 务替换的研究，而且对服务的组合替换缺乏考虑。随着Web服务数量的迅速增加，采用传统 的服务查找和替换方法，必然会浪费大量时间来处理毫不相关的服务，从而使得效率低下 甚至造成服务组合流程的中断，造成巨大损失。
【发明内容】
[0004] 针对现有技术中存在的上述技术问题，本发明提出了一种基于服务簇的服务组合 与替换方法，其采用如下技术方案：
[0005] 基于服务簇的服务组合与替换方法，包括如下步骤：
[0006]a、构建Web服务和服务簇的形式化模型
[0007]定义N是一个自然数集合，即N={0, 1，2,…}，而设定N尸{0,1，2,…，片.，N+=N\W， 且N/=m\{〇};
[0008] 定义化tri网；
[0009] 一个化tri网表示为一个四元组PN= (S，T;F，M0)，其中，
[0010] (1)S是一个有限库所集；
[00川（2)T是一个有限变迁集，且心於0，、片幼
[001引做巧;('s'x7>j(;rxs)是一个弧集；
[001引（4)dom(巧Ucod(巧=S U T，其中，
[0014] dom(F)= {.，ve5ur|3yeSuT:(,v,.v)gF1 , cod(F)= {ve5ur|3xeSuT:(,v,y)eF\；
[001引妨M: 为网PN的一个标识，其中，
[0016]VseS，M(s)表示标识M下库所s中的托肯数，M。是初始标识；
[0017] 定义输入/输出集：
[001引设PN= (S,T;F，M。）为一个化tri网，XGSUT为网N的一个元素，记；
[001引'X={yIyG S U T八（y，X)G巧称为X的输入集；
[0020] X' ={y|yG S U T八（X,y)G巧称为X的输出集；
[0021] 'XUX'称为元素X的外延；
[0022] 在化tri网中，采用一个圆圈表示一个库所，用一个矩形表示一个变迁；若 (X，y)GF，则X到y的一条有向边表示它们的流关系；
[0023] 定义引发规则：
[0024] 设PN= (S，T;F，M。）为一个化tri网，则其具有如下的变迁发生规则；
[002引1)对于变迁t G T，如果V.s'E,S': .s'eV一M(单1，则变迁t在标识M有发生权，记为M[t >；
[002引。如果M[t>，则在标识M下，变迁t能够发生，从标识M发生变迁t得到一个新 的标识M'，记为M[仪V/'，V.s'eS，
[0027]
[0028] 根据上述化tri网的定义，构建Web服务的形式化模型如下：
[002引定义Web服务；
[0030] -个Web服务描述为一个四元组WS=(SF，I，0)，其中；
[0031] (1)SF表示服务的功能语义描述；
[003引似I、0表示服务的输入、输出参数集，并且V戶e/u化戶=(戶題歴，片C饼ice的，其 中，
[0033] ①P. name是输入、输出参数名；
[0034] ②P.concept是一个输入、输出参数的本体概念，用W表示参数的语义；
[00对定义服务请求：
[0036] -个服务请求表示为R=(SFr，I"Or)，其中：
[0037] (1)SFr表示服务请求的功能语义描述；
[0038] (2) If代表服务请求者可提供的输入参数集；
[0039] (3)Or代表服务请求者需要输出的参数集；
[0040] 定义服务网元：
[00川服务WS= (SF，I，0)的服务网元定义为SNU=扣1。0。尸。1)，其中；
[0042] (1)t是一个能够完成服务功能的变迁；
[0043](2)It='t={su,Si2, Su,…，sj是变迁t的输入集，代表服务的输入参数集合； 〇t二t= {s。。3。2, 3。3,…，S。。}代表服务的输出参数集合；
[0044]做Ft= (ItXt)U(tX〇t)是有向弧集合，表示服务的输入、输出参数的流关系；[004引（4)M是服务网兀的标识，M;ItU0t- ;
[0046] (5)变迁t在M下的发生规则为：
[0047] ①Vpe/:M(/))= 1，则变迁t在M下有发生权，记为M[t>;
[0048] ②若M[t〉，则t在标识M下能够发生并得到一个新的标识，记作M[t〉M'，对于 Vjf?eIfKJ0tf
[0049]
[0050] 定义服务簇：
[0051]对于n个服务；wSi,WS2, . ..，sc= {wSi,WS2, . . .，WS。}是一个服务簇，其中：
[00閲 ！化N/，丽,,=口Fy，/,,，0,,，旅M,,)，且Vリ，化N,,+，SFu和SFv满足语义相似；
[005引定义服务簇网元：
[0054]一个有n个服务的服务簇；SC = {wsi, WS2, . . .，WS。}，Ae N"+，SNUk= (tk，Itk，〇tk，Ftk，Mk)，服务簇网元表示为SCNU = (SU，tc，Ic，〇c，Fc，Me)，其中：
[005引（1)SU= {SNUi，SNUs，SNUs，…，SNU。}是服务网元的集合；
[005引（2)te是服务簇网元的变迁，且能够完成服务簇中各服务的功能；
[0057] 做I。〇c分别表示服务的输入、输出参数集，并且V尸e /(. U()(.，/，=(/>(.顶聊庐 /"片知），其中；
[0058] ①P.concept是服务簇中服务输入参数对应的语义概念；
[005引②P. 1油le是一个nX1的矩阵，其中，n是服务簇中服务的个数，并且P. 1油le是 服务簇中的服务相应P.cone巧t的值；
[0060] (4化=(IctXtc)U(teXOa)表示服务簇输入、输出参数的流关系；
[006。巧)Me是服务簇网元的标识；
[0062] 根据服务簇网元的定义，将一个服务的输入参数值作为服务簇输入矩阵的一行； 将该服务的输出参数值作为服务簇输出参数矩阵的对应行；
[0063] b、基于服务簇的服务发现、组合与替换
[0064] 设服务簇k的服务总数为m个，输入参数的总数为n;个，输出参数总数为n。个； lek、〇a、if、Of分别代表服务簇的输入矩阵、服务簇的输出矩阵、服务请求的输入矩阵、W及 服务请求的输出矩阵；其中，Ick是一个mXrii矩阵，〇ck是一个mXn。矩阵，if是一个IXrii 矩阵，〇r是一个1Xn。矩阵；IaP(q)代表输入矩阵的第P行第q列的值；
[006引输入一个服务簇网元模型SCNUk=(SUk，tck，Ick，0ck，Fck，Mck)和一个服务请求网元Sf=(sft，if,Of}，基于服务簇的服务匹配输出Cl和C。，其中，Cl表示输入匹配矩阵，是一个 mXn先阵；C康示输出匹配矩阵，是一个mXn。矩阵；
[0066] 基于服务簇的服务匹配的过程如下：
[0067] SI:Wlek的首行开始，依次匹配该行的每个值；
[0068]S2:若该行中元素的值小于或者等于if对应的值，则标记Cl对应位置的值为1;
[0069]S3:否则，标记为0;
[0070] S4:W〇ck的首行开始，依次匹配该行的每个值；
[0071] S5:若该行中元素的值大于或者等于if对应的值，则标记Cl对应位置的值为1 ;
[007引 S6:否则，标记为0;
[0073]S7:输出矩阵。和矩阵C。；
[0074] 其中，服务匹配过程的时间复杂度是mXni2+mXn。2;
[00巧]通过上述服务匹配过程，服务簇输入/输出匹配矩阵将服务簇中的服务按照当前 服务请求统一表示服务匹配结果；
[0076] 通过上述服务匹配过程明确区分各服务输入输出参数是否满足服务请求，提高服 务查找效率；
[0077] 输入一个输入匹配矩阵。和一个输出匹配矩阵C。，基于上述服务匹配过程提出服 务发现的过程，进而得到一个服务集合S;
[0078] 服务发现的具体过程如下：
[0079] Sl:p=1,S=0;
[0080]S2:WCl的第p行开始，依次匹配该行的每个值；
[0081] S3:若该行中所有的值都为1，则跳到S5 ;
[008引 S4:否则P=P+1，循环该一匹配过程；
[0083]S5:依次匹配C。第P行的各值；
[0084]S6:若该行中所有的值都为1，则将该服务合并入集合S中，即S=SU{wsp};
[00财 S7:否则P=P+1，跳到S2;
[008引 S8输出服务集合S;
[0087] 通过服务发现过程发现服务簇中满足服务请求的服务；服务发现过程输出的服务 集合S中，所有服务的输入输出匹配矩阵同为'即服务集合S中的每个服务都满足 服务请求；服务发现过程的时间复杂度为；mXni+mXn;
[008引定义*3冷WSj表示服务WSi和服务WSj的并行组合；定义WSi|wSj表示服务WSi和 服务WSj.的串行组合；
[008引设曰=比。b2,…，bj是一个IXk矩阵，其中，biG{0,U，/eNa+，且,kN+，对 于Vz'eN-/，如果bi= 1，a表示为E，即E= [1,…，1];
[0090]对于V/eN/，若bi=0，a表示为 0,即 0=[0, 0,…，0];
[00川 其中，a表示F>etri网中的一个标识；并且aa2表示V/eN/，b2i;
[0092] 定义基元素：
[009引设a1=比。，b。，…，bj且a2=比21As,…Ak]是两个IXk矩阵，其中neN+,&GN"+，V6i,.e{0，l}，andbgiE{〇, 1}，/eN/;若a2,则称 是a1的一个 基元素；
[0094] 定义基集合；
[009引设C是一个IXk矩阵的集合；3C'cC，如果V%eC，otpeC'或者30CgeC'，a。是曰P 的一个基元素，且VC"，|C"I> |C'I，则称C'是C的一个基集合；
[0096] 定义服务组合标志；
[0097] 用于标记当前服务请求下的服务组合的服务基集合，其初始标志为0;
[009引根据服务匹配过程提出服务匹配的运算方法如下：
[0099] 定义匹配运算：
[0100] SNUa=(t。，Ita，〇ta，Fta，M。）是一个服务网元，R= (SFr，If,Or)是一个服务请求；
[0101] 匹配运算被定义为：
[0106] 定义服务簇匹配矩阵：
[0107] WSreq=(SFre。，Ireg，〇reg)是一个服务请求；
[010引SCNUa=佛。，tc。，Ict。，0ct。，Fct。，M。）是一个服务簇网元；
[0109] 服务簇的输入/输出匹配矩阵被定义为：
[0110]
[0113] Ci和C。代表了服务簇中的服务匹配服务请求的标识；
[0114] 输入服务簇网元SCNU= (SU，tc，Ic，〇c，Fc，Mc)和服务簇匹配矩阵Ci，C。;其中，V戶e /('U()('，/^=(C )，服务输入、输出参数的个数分别为k，1 ;输出服务集合 B；
[0115] 则服务串行组合的过程如下：
[0116] S1:依次匹配服务的输入、输出参数的参数语义；
[0117] S2:若存在la.concept= 〇cj.concept,依次匹配Cl(i);
[om]S3:若c/a) = 0,WCl的首行开始，依次匹配该行的每个值；
[011引 S4:若c/= [1，1，…，1]，匹配相应的c〇g;
[0120] S5:若CCi) = 1 且CUC〇P= [1，1，…，1]，则B=BU{ws。}，循环该一过程；
[0121] S6:若^=0，输出"没有满足条件的串行服务组合"；
[0122] S7:输出服务集合B;
[0123] SCM表示服务的基集合，通过SCM的过程体现服务簇中服务间的共性与个性，从而 用SCM来发现单一替代服务和组合替代服务；
[0124] 输入服务簇SC= {wsi,WS2,…，wsJ和服务簇匹配矩阵Ci、C。，SCM的过程如下； [01幼S1:依次匹配叫，若m。'声[1, 1,…，]_]，贝ijSCMj标记为巫；
[012引 S2:匹配m0k，若m0k= [1, 1,…，]_]，SCMk标记为 0 ;
[0127] S3:若m〇k声[1，1，…，1]，找到所有不为巫的SCMP且若W。曲则
[012引 S4:若A=巫，则SCMk=巫；
[0129] S5:否则标记SCMk为A的基集合；
[0130] S6:若在所有的SCM中有一列全为1，在所有SCM中删掉该一列；
[013" S7:输出SCM;
[01础定义SCM1^戈表SCMk的第m个元素；S1^1是SCM,。的第1列，打，W，andA;eN,,+;
[0133] 定义组合规则；
[0134] SC= {wsi，WS2,...，wsJ是一个服务簇；其中，u'.s',.=(W, /,化SCM,.)，侣乂,+;
[0135] SCMk丄SCMp=SCMki丄SCMpi丄SCMk2丄SCMp2丄…丄SCMh丄SCMpn，
[01 3引 其中，SCMkm丄SCMpm= [S。S2,…，S。]且
[0137] 输入SC= {wSi,WS2,. . .，WS。}和失效服务WS。，输出替换服务集合A;
[013引则发现单一服务和组合服务的服务替换的过程如下：
[0139] S0:A=巫；
[0140] S1:若失效服务的SCMm= 〇 或SCMm= 0 ;
[01川S1. 1:匹配SCM，若3化端=0,则将服务wSk并入集合A中，A=AU(wsJ;
[014引SI. 2:若匹配存在SCMi，SCMk，SCMi丄SCMk= 0,则将wsi和wsk的组合并入集合A中，即A=AU{讯3冷wsJ;
[014引S2:否则，若失效服务的SCMm声巫且SCMm声0 ;
[0144] S2. 1:如果匹配SCMk=0,则将服务wSk并入集合A中，A=AU{wsJ;
[014引 S2. 2:若匹配存在SCMkj'ESCMk，SCM血GSCMm，且SCMkj'《SCMmh，则将服务wSk并入 集合A中，A=AU(wsJ;
[0146] S2. 3:如果匹配SCMi，SCMk，SCMi丄SCMk=〇,则将wsi和wSk的组合并入集合A中， A=AU{wSjOws；
[0147]S3:若A=巫；
[014引S3. 1:若SCMm中存在某一列的值为1，而其他服务的在该列的值都不为1，则将该 一列在所有的SCM中移除，转到S2 ;
[0149] S3. 2:否则，输出"没有满足条件的替换服务"；
[0150] S4:输出A，即为满足条件的替换服务集合。
[0151] 本发明具有如下优点：
[0152] (1)本发明借助已有的服务聚簇方法构建服务簇，并基于化tri网提出服务及服 务簇的形式化描述方法；将服务的输入输出参数抽象表示，通过参数矩阵来描述服务的输 入输出参数；
[0153] (2)本发明提出的服务匹配方法使服务簇中的服务间能够充分共性与个性，通过 缩小服务查找范围，从而提高服务发现与组合效率；通过对服务簇模型的改进，提出Web服 务组合替换方法；对服务簇内服务的并行组合与串行组合分别进行了描述，在服务簇内实 现快速服务组合，进而实现高效率的服务组合替换；
[0154] (3)本发明提出的服务簇的服务替换方法，不仅能够实现服务簇内单一服务替 换，而且能够实现服务簇内服务组合替换。
【附图说明】
[0155] 图1为一个简单的Petri网模型示意图；
[0156] 图2为一个火车票查询服务网元模型示意图；
[0157] 图3为火车票查询服务网元示意图；
[015引图4为一个火车票查询的服务簇网元示意图；
[0159] 图5为查询服务簇的服务簇网元模型示意图；
[0160] 图6为服务簇的输入输出匹配矩阵匹配示意图；
[0161] 图7为本发明实验中Web服务发现时间比较示意图；
[0162] 图8为本发明实验中单一服务替换的比较示意图；
[0163] 图9为本发明实验中组合服务替换的比较示意图。
【具体实施方式】
[0164] 下面结合附图W及【具体实施方式】对本发明作进一步详细说明：
[0165] 基于服务簇的服务组合与替换方法，包括如下步骤：
[0166] 1构建Web服务和服务簇的形式化模型
[0167] 1. 1相关技术描述
[0168] 定义N是一个自然数集合，即N={0, 1，2,…}，而设定N尸{0,1,2,…，如N+=N\{0}， 且沁=Na-\{0}。
[0169] 定义化tri网；
[0170] -个化tri网表示为一个四元组PN= (S,T;F，M0)，其中，
[0171] (1)S是一个有限库所集；
[017引 （2)T是一个有限变迁集，且5。片凤折片風 [017引 做化(於7>_;(rxS)是一个弧集；
[0174] (4)dom(巧Ucod(F) =SUT，其中，
[01 巧]dom(F)="!.\-e&jr|ve瓜爪（.\-，-v)E巧.，cod(F)={ve5U7l (..V，.v')E巧.；
[017引 妨M: 为网PN的一个标识，其中，
[0177]VkS，M(s)表示标识M下库所s中的托肯数，M。是初始标识。
[0178] 定义输入/输出集；
[017引设PN = (S, T ;F，M。）为一个化tri网，xGSUT为网N的一个元素，记[0180] ? X = {y I y G S U T八（y，X) G巧称为X的输入集；
[01X' ={y|yGSUT八（X,y)G巧称为X的输出集；
[0182] -XUX'称为元素X的外延。
[0183] 在化tri网中，通常用一个圆圈表示一个库所，用一个矩形表示一个变迁。若 (X，y)GF，则X到y的一条有向边表示它们的流关系。
[0184] 如图1给出了一个简单的Petri网模型。
[01财在图1中，有限库所集S= {s。S2,S3,sj;
[0186]有限变迁集T={ti，t2，t3，t4};
[0187]弧集F = { (Si, *2)，（S2, ti)，（S2, t*)，（S3, ts)，（S3, t*)，（S4, ts)，（ti, Si)，（t2, S2)，（t2 ,S3),(tg, Si),(t4, S4)}；
[018引初始标识M0= (1，0, 0, 0);
[0189] 对于库所Si，它的前集为'Si={t。tg}，后集为Si'=咕};
[0190] 对于变迁t2的前集和后集分别为't2={sJ，t2' = {S2,S3}。
[0191] 定义引发规则：
[019引设PN= (S，T;F，M。）为一个化tri网，则其具有如下的变迁发生规则：
[019引 1)对于变迁tGT，如果V化&化一M似H，则变迁t在标识M有发生权，记为M[t> ；
[0194] 2)如果M[t>，则在标识M下，变迁t能够发生，从标识M发生变迁t得到一个新 的标识M'(记为M[t>M' )，VkS，
[0195]
[0196] 本体的ntology)是一种起源于哲学领域的概念，主要研究存在本质的哲学问题， 上世纪90年代被用于计算机领域。
[0197] 1997年，W.N.Borst对Guarino的理论进行了扩充，进而把本体定义为"对共享概 念模型的形式化的明确说明"，得到广泛的认可。其中体现了四层含义：
[0198] (1)概念模型：通过抽象出客观世界中一些现象的相关概念所得的模型；
[0199] (2)明确；所使用的概念W及使用此概念的约束都有明确定义；
[0200] (3)形式化：是计算机可读的；
[0201] (4)共享；体现的是共同认可的知识，反映的是相关领域中公认的概念集合。
[0202] 领域本体是依据领域来表述特定领域的静态知识。
[0203] 领域本体通过对特定领域内的概念及概念见的关系的精确描述，成为人机之间、 机器和机器之间相互理解的语义基础。
[0204] 领域本体由对象、对象的属性、对象之间的关系及子领域本体构成，故领域实体对 象和实体间的关系都是独立的知识单元，能够把领域本体形式化表示成一个有向无循环 图，图中的结点表示概念或单个对象，有向边表示概念之间的关系或关联。现有技术文献基 于领域本体的概念，构建了一个层次语义知识库，并提出了一种服务相似度的计算方法；
[0205]
[020引式中，SF。S。代表服务WSi和WSj.的服务功能语义描述；
[0207] 1是层次语义网中S。和SFj.之间的最短路径；
[020引 h是在层次语义网中的深度；
[0209] a，P是两个参数，择优选择为；a=0. 2and|3=0. 6。
[0210] 1.2Web服务
[0211] 根据上述1. 1对于化tri网的概念，构建服务的形式化模型如下：
[0引引定义Web服务；
[021引一个Web服务描述为一个四元组WS= (SF，1，0)，其中；
[0214] (1)SF表示服务的功能语义描述；
[02巧]似I、0表示服务的输入、输出参数集，并且V尸e/u(),尸=(/'^""歷，戶(顶巧的，
[0216] 其中，P. name是输入、输出参数名；P. concept是一个输入、输出参数的本体概念， 用W表示参数的语义；
[0217] 定义服务请求：
[0引引一个服务请求表示为R= (SFf，If,Of)，其中：
[021引 （1)SFr表示服务请求的功能语义描述；
[0220] (2)I,代表服务请求者可提供的输入参数集；
[0221] (3)Or代表服务请求者需要输出的参数集。
[0222] 定义服务网元；
[022引服务WS= (SF，I，0)的服务网元定义为SNU= (t，I。0。F。M)，其中；
[0224] (1)t是一个能够完成服务功能的变迁；
[0225] (2)It='t={Sil，s。，s。，…，sJ是变迁t的输入集，代表服务的输入参数集合； 〇t=t? = {s。。3。2, 3。3,…，S。。}代表服务的输出参数集合；
[022引 做Ft= (ItXt)U(tX0t)是有向 弧集合，表示服务的输入、输出参数的流关系；
[0227] (4)M是服务网元的标识，M ;ItU〇t-U ;
[022引 （5)变迁t在M下的发生规则为：
[022引 （a)V戶/:M(/，)=l，则变迁t在M下有发生权，记为M[t> ;
[0230] (b)若M[t〉，则t在标识M下能够发生并得到一个新的标识，记作，对于
[0231]
[0232] 利用服务网元来表示服务，能够有效地将服务的输入输出参数数量化。为了方便 模型表示，本发明将服务的输入、输出参数名作为变迁的输入、输出库所名。
[0233] 例如；一个火车篇查询服务：
[0234] WS"s= (SF"s,l"s，0"s);其中，1。日={(ii，D巧arture),山，Arrival)，山，Date), (i*,ID)}，并且 0。日={(0。price), (〇2,TrainNo), (〇3,time)}。"D巧arture", "Arrival", "Date", "ID", "price","TrainNo"和"time"分别代表出发地，目的地，日期，身份信息，票 价，列车号和出发时间。
[0235] 根据服务网元的定义，该服务经过模型化后如图2所示。
[0236] 1. 3服务簇
[0237] 本发明用基于本体计算服务功能相似度来聚簇。由于本发明主要是在服务聚簇的 基础上进行，因此只对服务聚簇进行简单的介绍。
[0238] 本发明基于现有技术中服务相似度计算方法来确定语义相似，若Sim佑Y)〉= 0. 8,则认为概念X与概念Y是语义相似的。
[0239] 有了上述语义相似的理论基础，根据服务功能的语义相似度将服务聚簇，形成服 务簇，下面给出服务簇的定义。
[0240] 定义服务簇；
[024^ 对于n个服务；WS。WS2, . . .，SC={wsi,WS2, . . .，WS。}是一个服务簇，其中；
[024引！/gN"+，wsu=(SFU，1山 0山SC心，且.Vi/，veN,,%SFu和SFV满足语义相似。
[0243] 为了高效的发现和替换服务，服务簇需要模型化。根据服务网元模型的构建方式， 将服务的参数数字化，同样，将服务簇中的参数数字化。
[0244] 由于一个服务簇中的参数较多，本发明引入参数矩阵来表示服务簇的参数。
[0245] 定义服务簇网元；
[024引一个有n个服务的服务簇；SC={w化简，…，W,，}，AeN"+，SNUk= (tk，Itk，0tk，Ftk，Mk)，服务簇网元被表示为SCNU= (SU，tc，I。0c，Fc，Me)，其中：
[0247] (1)SU= {SNUi，SNUs，SNUs，…，SNU。}是服务网元的集合；
[024引 （2)te是服务簇网元的变迁，它能够完成服务簇中各服务的功能；
[0249] 做I。0康示服务的输入、输出参数集，并且V尸S/('U()(.，尸:=作。。化'(仰/"/]/(〇， 其中：
[0巧0] (a)P.concept是服务簇中服务输入参数对应的语义概念；
[0251] (b)P. 1油le是一个nX1的矩阵，其中n是服务簇中服务的个数，并且P. 1油le是 服务簇中的服务相应P.cone巧t的值；
[025引 （4化=(IctXtc)U(teXOa)表示服务簇输入、输出参数的流关系；
[0巧引 巧)Me是服务簇网元的标识；
[0巧4] 根据服务簇网元的定义，将一个服务的输入参数值，作为服务簇输入矩阵的一行； 将该服务的输出参数值，作为服务簇输出参数矩阵的对应行。
[025引例如；一个火车票查询服务簇包括四个服务；wsi-WS4,服务网元模型如图3所示。 根据服务网元和服务簇网元的定义，构建出该服务簇的服务簇网元模型如图4所示。
[0256] 在图4中，I。和0。用两个矩阵表示，在下文中分别称该两个矩阵为输入矩阵和输 出矩阵。在服务簇中，服务的输入、输出参数被编号。
[0巧7] 在输入矩阵中，表示为"1"的，是对应的服务发生时所需要的参数。
[0巧引在输出矩阵中，表示为"1"的，是对应的服务发生后能够输出的参数。
[0巧9] 在输入输出矩阵中，每一行代表一个服务的输入输出参数值，而每一列，代表服务 簇中所有服务相应于某一参数的参数值。
[0260] 2、基于服务簇的服务发现组合与替换分析
[0261] 服务簇网元模型的建立能够提高服务的查找替换效率。
[0262] 在服务发现与组合阶段能够快速地筛选与服务请求功能不匹配的服务，进而缩小 替换服务的范围，使得服务发现与组合效率大大提高。
[0263] 下面本发明将提出一种基于服务簇的服务发现与组合算法，更进一步提高效率。
[0264] 2. 1服务发现
[0265] 在服务发现之前，对服务簇中的服务进行预处理能够有效的减少服务的查找范 围，提高服务发现效率。良好的服务匹配算法可W快速排除与服务请求不匹配的服务，然后 通过服务发现算法发现服务簇中满足服务请求的服务。
[026引 2. 11服务匹配算法
[0267] 在服务发现的过程中，首先需要通过服务匹配服务请求。服务匹配方法在提高服 务发现效率方面是至关重要的。因此，本发明首先给出一个服务匹配算法。
[026引在下述算法中，服务簇k的服务总数为m个，输入参数的总数为n;个，输出参数总 数为n。个。Iek，0ek，if和0t都分别代表服务簇的输入矩阵，输出矩阵，服务请求的输入矩阵 和输出矩阵。lek是一个mXni矩阵，Ouk是一个mXn。矩阵，it是一个1Xni矩阵，0t是一个 IXn。矩阵。iGkP(q)代表输入矩阵的第P行第q列的值。
[0269] 算法1服务匹配算法：
[0270] 输入；一个服务簇网元模型SCNUk=(SUk,tck,Ick，〇ck，Fck，Mck)，一个服务请求网元 Sr=(sf"i"oj;
[0271] 输出；Cl和C。，其中，Cl是一个mXn先阵，并且C。是一个mXn。矩阵；
[027引SI:Wlek的首行开始，依次匹配该行的每个值；
[0273] S2:若该行中元素的值小于或者等于if对应的值，则标记Cl对应位置的值为1 ;
[0274] S3:否则，标记为0;
[027引 S4:W0ck的首行开始，依次匹配该行的每个值；
[0276] S5:若该行中元素的值大于或者等于if对应的值，则标记Cl对应位置的值为1 ;
[0277] S6:否则，标记为0;
[0278] S7:输出矩阵。和矩阵C。；
[027引算法1是一种基于服务簇的服务匹配算法，其时间复杂度是mXni2+mXn。2。矩阵Ci被称之为输入匹配矩阵，矩阵C。称之为输出匹配矩阵。C/i(qi) =1表示服务wspi可W 满足第个参数需求。BP2(屯）=1表示服务wsp2可W满足第Q2个参数需求。
[0280] 通过算法1的服务匹配算法，服务簇输入/输出匹配矩阵将服务簇中的服务按照 当前服务请求统一表示服务匹配结果。服务输入/输出匹配矩阵中"1"代表对应的服务输 入/输出参数可W满足当前服务请求；而服务输入/输出矩阵中"0"代表对应的服务输入 /输出参数不能满足当前服务请求。根据该一特点，可W为实现服务发现效率的提高奠定坚 实的基础。
[0281] 算法1的提出可朗尋服务簇中的服务按照当前服务请求，给出统一的标记。该可 W为服务发现算法的提出奠定坚实的基础。根据算法1，下面给出服务发现的匹配定理。
[0282] 定理 1 ;
[028引服务需求Reg=(SFre。，Ireg，0reg)，服务WSb=(SFb，Ib，0b)，服务网元SNUb= (tb，Itb，0tb，Ftb，Mb)。矩阵Cl和矩阵C。分别是服务WSb相对于服务请求R6。的输入匹配矩阵 和输出匹配矩阵。如果
I则服务WSb可W满足服务输出请求 Req。
[0284] 证明；根据服务匹配算法，C/i(qi) = 1意味着服务wsp河W满足第个参数需求。 C2(屯）=1意味着服务WSp2可W满足第Q2个参数需求。
[0285] 进一步说，
表示服务wsb可W满足服务输入请求IU。的每个参数需 求
表示服务WSb可W满足服务输出请求0t。。的每个参数需求。
[028引故，如果
则服务WSb可W满足服务输出请求R。。， 证毕。
[0287] 2. 12服务发现算法
[028引算法1通过参数矩阵的匹配实现服务簇内快速筛选，从而更一进步缩小服务查找 范围。定理1为服务发现算法提供了有力的理论依据。
[0289] 算法2服务发现算法
[0290] 输入；输入匹配矩阵输出匹配矩阵C。；
[0291] 输出；S: -个服务集合；
[029引Sl:p= 1，护0;
[029引 S2:WCi的第P行开始，依次匹配该行的每个值；
[0294] S3:若该行中所有的值都为1，则跳到S5 ;
[029引 S4:否则P=P+1，循环该一匹配过程；
[0296] S5:依次匹配C。第P行的各值；
[0297] S6:若该行中所有的值都为1，则将该服务合并入集合S中，即S=SU{wsp};
[029引 S7:否则P=P+1，跳到S2 ;
[0299] S8 输出S.
[0300] 通过算法2可W发现服务簇中满足服务请求的服务。算法2输出的服务集合S中， 所有服务的输入输出匹配矩阵同为该意味着集合S中的每个服务都可W满足服 円 务请求。服务发现算法的时间复杂度为；mXni+mXn。
[0301]例如；一个服务请求Reg= (SFreq，Ireg，〇re。)，其中Ireg= [l，0，l，0，(U]，〇reg=[0，l，0,0，l，l]，服务簇SCNUk=(SUk，tck，Ick，0ck，Fck，M证）中有两个服务WSl，WS2。WSi= (5。，1。〇1),1 = 1,2。其中11=[1,0,0,1,0,1]，〇1=[1,1,0,0,1,1]，12二[1,1,1,0,0,1]， 〇2= [0, 1，1，0, 1，1]。
[030引根据算法1得到服务簇内服务的预处理结果；Cii= [1，1，1，0, 1，U，C。= [1，1，1，1，1，1]，并且向2= [1，1，1，1，1，1]，根据算法2得出服务WS2可W满足服务请求R。。。
[0303] 2. 2服务组合
[0304] 上述算法2可W在海量服务中，完成单个服务的服务发现。
[0305] 当服务组合体系中，单个服务失效时，可W利用算法2的方法进行服务发现及替 换。而在服务簇中，单个的服务可能不能满足服务请求，需要通过多个服务的组合来满足服 务请求。
[0306]当构成服务组合体系的单个或多个服务失效时，为了提高效率，将损失降到最低， 将服务组合模式保持不变。
[0307] 在服务簇中，选择与其功能相似且参数匹配的服务或服务组合将失效服务替换。 其中，服务簇中两个服务的组合包括服务的并行组合和串行组合。
[030引 3. 21服务并行组合
[0309] 基于上述内容，本发明首先对服务并行组合的方法进行描述。
[0310] 算法1中A"(屯）=0代表服务wspi的输入参数q1不能满足服务输入请求。换句话 说，在当前的服务请求条件下，服务WSpi不能发生。在服务组合发现的过程中，服务簇中的 该些服务可W不予考虑。在下文中，表示服务WSi和服务WSj的并行组合。WSilwSj 表不服务WSf和服务WSJ的串行组合。
[0311] 本发明提出一种新的概念，用于后文中对服务组合过程的描述。
[031引设a二比。bg,…，bj是 1Xk矩阵，其中扣e{0,1}, /巨N& 且内e抓，对于 V/eNA+，如果bi= 1，a可W表示为E，即，E= [1，…，1].对于V/eNa+，若bi=0,a可W表示为0，即，0=[0, 0,…，0]。
[031引在本发明中，a表示Petri网中的一个标识。并且aa2表示Vz'eNa+, bii^b2i0
[0314 ] 定义基元素： 防3巧]设a1=比…b。，…，bj且a2=比21A2,…Ak]是两个IXk矩阵，其中N,,+,V6i,'e{0, 1}，and/>2,'巨{0, 1}，/巨Na+。若aa2,则称a2是a1的一个基元 素。
[0316] 定义基集合：
[0317] 设C是一个IXk矩阵的集合。3C'cC如果VapeC，％eC'或者3而eC'，a。是 曰P的一个基元素，且VC"，Ic" |>Ic'I，则称C'是C的一个基集合。
[031引在服务簇中，任何服务都是没有编号的，为了标记服务簇中的服务，本发明提出一 种独特的方法。
[0319]定义服务组合标志（ServiceCompositionMarking,SCM);
[0320] 用于标记当前服务请求下的服务组合的服务基集合，其初始标志为0。
[0321] 在服务簇中，通过服务与当前服务请求的匹配结果，可W发现服务间的组合关系。 根据算法1可W提出服务匹配的运算方法。
[0322] 定义匹配运算：
[032引SNUa=(ta,Ita，0ta，Fta，Ma)是一个服务网元，R=佛"I"Or)是一个服务请求。
[0324] 匹配运算被定义为：
[0325] (1) /,' 0 /化=[修"啦蝴)，w(5巧)0 "如邮),...,w(w.to)0 "如口切化其中，，円知切
[032引（引@ /H(.S'"")0 /H(.S7V,|), /H(.S77)2)，...，"!柄
，打el^,j.eN,,+ 0
[0327] 从上述定义可W看出，当单个服务满足服务请求，意味着服务输入请求可W引发 服务变迁，并且服务输出标志可W满足服务请求。由定理1可W提出一个新的定理如下： [032引 定理2 ;
[0329] Req=(SFre。，Ireg，〇reg)是一个服务请求，SNUb=(tb，1扣，〇扣，Ftb，Mb)是WSb的一个服 务网元，如果知=丘且如@如广凡则WSb满足服务请求Re。。
[0330] 证明：由于/，巧魄*=￡且化@0,'矿&根据匹配运算定义， "!(.st")>/,!(.s7，"）and,7如/，巧)> "z(.sT巧 并且〇b可W满足0U。。因此服务WSb满足服务请求RW，证毕。
[0331] 定义服务簇匹配矩阵：
[0332] WSreq=佛re。，Ire。，Ore。）是一个服务请求。SCNUa=佛。，t。。，la。，0。,。，F。,。，M。）是一 个服务簇网元。服务簇的输入/输出匹配矩阵被定义为：
[0333]
[0336]Ci和C。代表了服务簇中的服务匹配服务请求的标识。根据算法2,满足服务请求 的单个服务可W被发现。然而在服务簇中，单个服务可W不能满足服务请求，而多个服务的 组合可能会满足服务请求。因此，下面提出服务组合定理。在下文中，WSi^WSj.表示服务WSi和服务WS j的服务组合。
[0337]定理 3;
[03 測虹 …，mjT(C0=虹。i，m02，m03,…，mjT)是服务簇的输入 / 输 出匹配矩阵，其中叫二虹j(Sii)，mj(s。)，…，nij(Sik)]且m〇j=虹j(s〇i)，mj(s〇2),… ，mJ(s。k)]，n，Ae]^r，z'JeN,，+。若服务组合wSi?wSj.可W满足服务请求的充分条件是：
[033引（l)mij=E且mn=E;
[0340]
[0341] 证明；（1)对于mii= E，根据服务簇匹配矩阵定义，知與也=￡。从匹配运算定义可 W看出V/eN"+，m(srii)〉m(si。）。因此服务wsi的输入参数都可W满足服务输入请求，服务 簇中的服务WS河W发生。相似地，由于mu=E，可W得出，服务wsj.的输入参数同样都可W满足服务输入请求的所有参数，服务簇中的服务WSj.也有发生权。所W，服务组合WSWSj.， 在当前服务输入请求的条件下，满足发生条件。
[03化| 似因为巧=尼，所WVpeN&+,mj(s0p) = 1ormi(s0p) = 1.根据 服务簇匹配矩阵定义，服务请求的所有输出参数都可W由服务WSi或WSj.满足。故， Vwe物;+，3"?/00。)，所啦0。)>7?切'0。)，/€哪+，7€14+。因此，根据服务匹配算法，服务组合 WSj斯输出参数可W与服务输出请求参数相匹配。从而，服务组合WS冷WSj.可W满 足服务的输出请求。综上所述，服务组合WSj.可W满足服务的输入请求，证毕。
[034引3. 22服务串行组合
[0344] 由于本发明中的服务簇是W服务功能相似度来聚簇，所W从服务功能参数上说， 当服务簇内发生服务失效时，并行组合替换的成功率相比串行组合更大一些。在服务簇粒 度足够小的情况下，串行组合服务替换可W忽略，不予考虑。本发明中的服务簇粒度足够 小，串行组合发生率较低，所W，本发明只给出简要的算法思想。在下文中，wSpMws。表示服 务WSp和服务WS。的串行组合。
[0345]定理 4;
[034引 SCNU=(SU，tc，Ic，0c，Fc，Mc)为一个服务簇网元，其中， We把U化，戶=(戶（'疆'(抑戶沁/沁），服务输入、输出参数的个数分别为k，1。服务请求R=佛,，Ir，0r)，服务簇匹配矩阵：Ci，C。。若C/声[1，1，…，1]，且C/a) = 0时，WS。同时 满足下面两个条件：
[0347] (1)却G N/十，1口. concept = 0". concept,且C〇q(j) = 1 ;
[034引 似(：1。=[1，1，…，U;
[034引贝1JWS。IIWSp可W满足服务请求R。
[0350]证明；因为C/声[1，1，…，1]，根据定理1，服务WSp满足服务输入请求。且根据服 务网元定义，VC/(/)=l时，服务wSp才能引发。当马eN^，Ici.conc巧t= 〇cj.concept时， 则服务簇中存在输入请求与输出请求语义相同。若(V(j) = 1则服务WSp的输出请求可W满足wsp的输入请求。而C/= [1，1，…，1]，根据服务网元定义，服务WS。可W满足当前服 务请求，可W引发。故可W通过先引发WS。后引发WSP，来满足服务请求。 防351 ] 综合上述，WS。IIwSp可W满足服务请求R。
[0巧2] 定理4的提出对服务的串行组合提供了理论依据。由定理4可知要想服务簇内发 生串行组合，服务簇必须有相同的输入输出语义参数，而该可能需要服务的粒度足够大。根 据定理4,下面提出服务串行组合算法：
[0巧3] 算法3服务串行组合算法
[0354]输入；服务簇网元SCNU=柳，tc,Ic，〇c，Fc，Me)，其中，We/VU化，尸=(C聊，f心6心)，服务簇匹配矩阵：Ci，C。，服务输入、输出参数的个数分别为k，1。
[035引输出；服务集合B;
[0356]S1:依次匹配服务的输入、输出参数的参数语义； 防357] S2:若存在 1口.concept= 0。'.concept,依次匹配Ci(i);
[0巧引 S3:若C/a) = 0,W。的首行开始，依次匹配该行的每个值；
[0359]S4:若C/= [1，1，…，1]，匹配相应的C〇a;
[0360] S5:若C〇a(j) = 1 且C〇auC〇P= [1，1，…，1],则B=BU{ws。}，循环该一过程；
[0361] S6:若公=0，输出"没有满足条件的串行服务组合"；
[036引 S7:输出集合B。
[0363] 算法3是在服务簇中查找能与WS。串行组合的服务，集合B为满足条件的服务集 合。
[0364] 2. 3服务替换
[0365] 服务簇的提出可W大大缩小查找服务的范围，提高查找效率。在同一个服务簇中， 体现各个服务共性的同时，需要发现服务的个性，从而快速发现替换服务。因此，需要有一 种标记服务的方法。SCM表示了服务的基集合，用SCM来发现单一替代服务和组合替代服 务。下面给出SCM的算法。
[0366] 算法4服务组合标识算法
[0367] 输入；服务簇SC= {wsi,WS2,…，WS。}，服务簇匹配矩阵：Ci，C〇;
[036引 输出；SCM
[036引 S1:依次匹配叫，若m。'声[1, 1,…，1],贝IjSCMj标记为巫；
[0370] S2:匹配m〇k，若m〇k= [1，1，…，]_]，SCMk标记为 0 ;
[0371]S3:若m〇k声[1，1，…，1]，找到所有不为巫的SCMP且若"U货"V=E，贝IJ J气4u{m〇p}，fEN打+;
[0；37引 S4:若A=巫，贝1JSCMk=巫；
[0；37引 S5:否则标记SCMk为A的基集合；
[0374]S6:若在所有的SCM中有一列全为"1"，在所有SCM中删掉该一列；
[037引 S7:输出SCM。
[0376] 根据算法4,基于服务簇网元模型可W得到SCM的值。SCM=〇代表当前服务簇 中没有服务可W满足服务请求。SCM= 0代表单个服务可W满足服务请求。而，如果SCMk 是一个集合，SCMk中的每个元素都代表着一个或者一组服务，在该组服务中的每一个服务 都可W通过与WSk组合满足当前服务请求。
[0377] 在服务请求参数中，考虑范围内所有服务都可W满足的请求参数可W人为是可忽 略参数。在服务簇输入、输出匹配矩阵中，可忽略参数所对应的那一列，可W认为是可忽略 列。
[0378] SCM可W将服务簇中的服务分类。若SCM= 〇,在服务替换过程中，相应的服务可 W不必考虑。然而，通常情况下，SCM为一个集合。在该种情况下，不能快速发现对应的组 合服务。为了解决该个问题，在算法4中，将SCM中的可忽略列删除。从而方便通过SCM来 快速发现可替换的组合服务。
[OW引利用SCM发现组合服务时，需要提出一种组合规则。在下文中，SCMkm代表SCMk的 第m个元素。是SCMJ勺第1列，/?，化佔沪，ancU'eK/。一种组合规则被定义如下。
[0380] 定义组合规则（CompositionRule);SC= {wsi,WS2, ...，WS。}是一个服务簇；其 中，W尸口巧，么化SCM/)，z'eN/。SCMk丄SCMp=SCMki丄SCMpi丄SCMk2丄 8〔1。2丄". 丄SCMkn丄SCMpn，其中，SCM虹丄SCMpm= [S。S2,…，S。]且
[0381] 根据组合规则定义，可W通过SCM.快速发现可替换的组合服务。为了更好的证实 该一结论，下面给出两个定理。
[0382] 定理 5 ;
[038引假设服务簇SC= {wsi，WS2, . . .，WS。}中存在一个失效服务WSm，R= (SF,，I,，0,)是 服务请求。若WSk是WSm的一个替换服务，则WSk满足下面条件之一：
[0384] (l)SCMk=0;
[03财 似 3SCMa7'，SCMmi，SCMkj《SCMmi，内巨 且,《，皮eN"+。
[038引证明；（1)若SCMk= 0,根据服务组合标识算法，可知m。=E且mDk=E。根据匹 配运算定义，/,御A-=扔化@0尸扔根据定理2,可W得出WSk是WSm的一个替换服务。
[0387]似若 350旬且SCMmiESCMm，SCMw=SCMmi,根据算法 4,有一组服务与SCMb.相关，当然也与SCMm湘关。假设与SCMmi相关的服务为WSg，通过算法4可知，mim= E,mig=Eandm。"曲"。广怎。由定理3可W得出wSgOWSm可W满足服务请求R。相似地，WSg 也是与SCMkj相关的服务，同样mik=E,mig=EandWoA货"％=￡。因此，服务WSk是服务WSm 的一个替换服务。
[038引若弘CMA7'eSCA4且SCMmiESCMm，SCMy<SCMmi，根据服务组合标识算法可知，SCMk是A的一个基集合。由基元素定义可知，SCMy是SCMmi的一个基元素。假设与SCMmi相关的 一个服务是WSg，根据定理3可W得到，WSm可W满足服务请求R。通过算法4可W看 出，服务WSg同样与SCMkj相关。相似地，WSgOwSk也可W满足服务请求。因此，WSk是WSm 的一个替换服务。
[ 0389] 根据定理5可W发现替换服务，而在服务簇中，组合服务也可替换失效服务。为了 发现组合替换服务，可W提出下面定理。
[0390]定理6 ;
[03川一个服务簇SC= {wsi,WS2, . . . ,WS。}，其中，w&=(公Tfc<SFa-，，化,504)，AgN,7+。服 务簇中存在一个失效服务WSm，如果SCMp丄SCM。= 0，则WSWS。是WSm的一个替换服务 组合，化祈，且p，geNn+。
[039引证明：因为SCMp丄SCM。= 0,由组合规则定义首先可W看出，SCMP声巫and SCM。声巫。通过服务组合标识算法可知，mip=E且miq=E。根据组合规则定义，3各eNn+, Spgi= 0或3AeN"+，8也1= 0。设与Spgi相关的那一列标号为mp(s0v)，mq(s0v)。则由算法4 可知，nip(S0v)= 1或mq(S0v)= 1。根据定理3,邸货护故，WSp^WS。是服务WSm的一 个替换服务组合。
[0393] 有了上述算法与定理的支撑，提出一种可W发现单一服务和组合服务的服务替换 算法：
[0394] 算法5服务替换算法
[039引输入；SC= {wSi,WS2, . . .，WS。}，失效服务WSm;
[039引输出；一个替换服务集合A;
[0397] S0:A=巫；
[039引 S1:若失效服务的SCMm=巫或SCMm= 0
[0399] S1. 1:匹配SCM，若 3 5"CM/；. =0,则将服务wSk并入集合A中，A=AU(wsJ;
[0400]SI.2:若匹配存在SCMi，SCMk，SCMi丄SCMk= 0,则将wsi和wsk的组合并入集合A 中，即A=AU{讯3冷wsJ;
[0401]S2:否则，若失效服务的SCMm声巫且SCMm声0 ;
[040引S2. 1:如果匹配SCMk= 0,则将服务wsk并入集合A中，A=AU{wsJ;
[040引S2.2:若匹配存在SCMyESCMk，SCM血GSCMm，且SCMy《SCM血，则将服务wsk并 入集合A中，A=AU(wsJ;
[0404]S2. 3:如果匹配SCMi，SCMk，SCMi丄SCMk= 0,则将wsi和wsk的组合并入集合A中， A=AU{wSjOws；
[0405]S3:若A=巫；
[0406] S3. 1:若SCMm中存在某一列的值为"1"，而其他服务的在该列的值都不为"1"，则 将该一列在所有的SCM中移除，转到S2;
[0407]S3. 2:否则，输出"没有满足条件的替换服务"
[0408]S4:输出A，即为满足条件的替换服务集合。
[0409] 在算法5中，首先发现单个服务是否能替换失效服务，若单个服务不能替换失效 服务，考虑组合服务替换。算法5中，在最好情况下的时间复杂度，仅为n。下面通过一个实 例来进一步描述该个算法。
[0410] 3. 4火车订票服务簇实例
[0411] 现有一个火车订票系统包括3个服务簇；一个安全管理（safetydetection)服务 簇，一个查询（ticketinquiry)服务簇和一个订票化ooking)服务簇。
[0412] 它们的服务簇组合关系是；safetydetection-ticketinquiiT-booking。在 查询服务簇中，有10个服务；WSi，WS2, . . .，WSi。。查询服务簇的服务簇网元模型见图5。
[0413] 在查询服务簇中，现存在一个失效服务，为了确保服务簇组合模型的模式不变，月良 务簇必须满足一个服务请求。该服务请求为；而。。。1,,^[1 1 1 1 0] - [0 1 0 1 1 1]。
[0414] 根据匹配运算定义，可W得到服务簇的输入输出匹配矩阵，如图6所示。
[0415] 由输入输出匹配矩阵可W快速的发现不满足服务输入请求的服务，并予W排除缩 小查询范围。
[041引通过算法4可W得到服务簇inquiry中每个服务的SCM值，所得的结果显示如表 1 ：
[0417] 表1查询服务簇的服务组合标识
[0418]
[0419] 在表1中，每一行显示了服务簇中服务的SCM。 '
[0420] 服务簇i叫uiry中的10个服务可W通过SCM被清楚地分类。如果WS4为失效服 务，服务簇中有SCMi丄SCMs= 0,根据定理6,WS8是WS4的一个替换服务。如果WS2失效， 从表1可W看出SCM2i=SCMei，根据定理5,wse是WS2的一个替换服务。
[0421] 通过算法5,服务簇中各服务失效时，它们的替换服务可W统计为表2 :
[0422] 表2不同失效服务下的替换服务
[0423]
[0424] 从表2中可W看出，服务簇中，不同的服务失效，它们的替换服务也不同，而且替 换服务的数量也不相同。有的服务失效通过单一服务替换即可，而有的服务失效，单一服务 无法完成替换，需要组合服务来替换。
[0425] 在火车订票服务簇实例中，只演示了服务簇中单个服务失效时的情形。当服务簇 中多个服务失效时，仍然可W通过算法4得到SCM，而定理5和定理6仍然适用。失效服务 的替换服务扔可W通过算法5得到，在该里就不再详述。
[042引 3实验过程
[0427]本发明利用上述相关算法，并采用C#语言编写，可随机生成本体树、随机生成服 务簇，并能随机选取服务模拟失效，统计每次查找时间。
[042引设计实验平台自动生成指定数量的服务，根据本发明提出的方法模拟服务发现过 程、W及单一服务替换与组合服务替换过程，并记录其响应时间。
[0429] 在实验设计环节，首先对本发明提出的服务发现算法与传统的服务发现算法进行 比较，从而验证本发明提出的服务发现算法的有效性。然后根据本发明的实验设计思路，对 本发明提出的服务替换算法与原有的替换算法进行比较。替换算法的比较分为两个方面， 一种是考虑单个服务替换效率，一种是考虑服务组合替换效率。
[0430] 替换算法比较实验中，在服务的替换效率方面，对原有的服务替换算法与本发明 基于服务簇的服务替换算法进行了比较分析。由于本发明提出的相关方法是基于服务簇的 基础上且鉴于目前没有相关的平台和Web服务库可用，本实验结果也是在服务簇已构建的 基本情况下产生。因此，实验中将采用自上而下的方式产生模拟数据。首先，采用了已提出 的方法建立领域本体树。然后定义服务簇，标注服务簇的输入/输出参数，并根据服务簇产 生簇内的相关服务。本发明采用C#语言编程，并进行仿真模拟实验。算法比较实验设计如 下：
[0431] ①构建领域本体树，生成服务簇并标注相关参数，从而自动生成簇内相关服务和 产生服务参数。
[0432] ②在实验中随机选取服务并模拟服务失效，对所选服务的输入输出参数进行随机 指定，从而达到模拟实验的效果。
[0433] ⑨单个服务替换查找成功时，计算响应时间仅考虑单个服务的发现时间和替换时 间，如果组合服务替换查找，计算响应时间是考虑发现服务时间、组合服务时间W及替换服 务时间。
[0434] ④根据服务发现算法，在服务个数不同的情况下分别记录服务发现的响应时间。
[0435] ⑥在本发明中，响应时间是多次实验的平均值。
[0436] ⑧在实验中，服务簇中服务个数分别为100、200.....500。为了避免偶然数据，本 实验重复做100次。
[0437] 3. 1服务发现算法比较
[0438] 首先根据本发明提出的服务发现算法与传统的服务发现算法进行比较，每次随机 生成服务请求100个。与服务替换算法设计相似，分别记录服务簇中服务个数分别为100、 200、...、500时的响应时间。得到的实验结果如图7所示。
[043引图7中，横坐标为服务的数量，纵坐标为服务发现的响应时间；带有方形标记线的 为本发明中服务发现算法的响应时间，带有圆形标记线的为传统的服务发现算法的响应时 间。
[0440] 从图7中可W得出结论：
[0441] 本发明中服务发现算法的效率是明显高于传统服务发现算法的；随着服务数量的 增多两种服务发现算法的效率有所下降，而相对传统的发现算法，本发明所提出的服务发 现算法受服务数量的影响较小。
[0442] 3. 2服务替换算法比较
[0443] 本实验对服务替换响应时间的比较分析分为两个实验；
[0444] 实验一；对于服务的单一替换按照设计思路，对两种方法进行实验比较；
[0445] 实验二：对于组合服务替换按照设计思路，对两种方法进行实验数据比较。
[0446] 在本发明的实验平台中，经过多次实验，得出实验一的实验结果如图8所示。而实 验二的实验结果相关数据如图9所示。
[0447] 在图8中，横坐标为服务的数量，纵坐标为服务发现的响应时间；带有方形标记线 的为本发明中服务替换算法的响应时间，带有圆形标记线的为传统的服务替换算法的响应 时间。
[044引在图8中可W看出，两种替换方法的响应时间随着服务数量的增多而增长。然而 在响应时间的增长速率上比较，本发明中的服务替换方法的增长速率低于传统的服务替换 方法。从曲线走势上看，随着服务数量的增多，两条曲线之间的距离越来越大。从曲线整体 上来看，本发明服务替换方法的响应时间稳定低于传统的服务替换方法的响应时间。
[044引图8中，在服务簇内服务相同的基础上，本发明中的服务替换算法平均响应时间 占传统服务替换方法的68. 8%。
[0450] 在图9中，横坐标为服务的数量，纵坐标为服务发现的响应时间；带有菱形标记线 的为本发明中服务替换算法的响应时间，带有=角形形标记线的为传统的服务替换算法的 响应时间。
[045。在图9中，服务簇内服务相同的基础上，本发明提出的服务替换算法平均响应时 间占传统服务替换方法的45. 6%。
[0452] 综合图8和图9可W得到实验结论：
[0453] 第一，两种算法的响应时间都随服务数量增多而增长；
[0454] 第二，本发明服务替换算法的效率明显低于传统的服务替换算法；
[0455] 第=，两种替换方法的效率均受服务数量影响，而本发明服务替换算法的效率受 服务数量的影响较小。
[0456] 实验结果证实了本发明所提出的服务替换算法的正确性和有效性，且替换效率特 别是组合替换效率有了明显的提高。
[0457] 通过本发明与传统的服务发现算法、W及服务替换算法的实验比较，验证了本发 明所提出的服务发现算法和服务替换算法的有效性和高效性。
[0458] 本发明在服务簇已建立的基础上实现了服务的发现与替换，利用Petri网定义服 务和服务簇的形式化模型，提出了服务匹配方法和服务组合方法，并通过理论证明、实例演 示、及仿真实验验证了本发明方法的正确性、实用性及有效性。
[0459] 当然，W上说明仅仅为本发明的较佳实施例，本发明并不限于列举上述实施例，应 当说明的是，任何熟悉本领域的技术人员在本说明书的教导下，所做出的所有等同替代、明 显变形形式，均落在本说明书的实质范围之内，理应受到本发明的保护。
【主权项】
1.基于服务簇的服务组合与替换方法，其特征在于，包括如下步骤： a、构建Web服务和服务簇的形式化模型 定义N是一个自然数集合，即N={〇, 1，2,···}，而设定NitHO, 1，2,_··，幻，Ν+=Ν\{0}，且 Ν/=ΝαΛ{0}； 定义Petri网： 一个Petri网表示为一个四元组PN = (S，T ;F，MO)，其中， (I)S是一个有限库所集； ⑵T是一个有限变迀集，且化作0, 5ηΓ=0; (3) /USx7)u(rxS)是一个弧集； (4) dom(F) U cod (F) = S U T，其中， dom(F)={.\-e5oT| ByeSvjT: (λ\ VjeZ7I, Cod(F)= [ veSoTl BxeSvjT: (.v,y)eF\ ； (5) M: 为网PN的一个标识，其中， Vse5*，M(s)表示标识M下库所s中的托肯数，Mci是初始标识； 定义输入/输出集： 设PN = (S，T;F，Mci)为一个Petri网，X e S U T为网N的一个元素，记： ? X = {y I y e S U T~ (y, X) e F}称为 X 的输入集； x' = {y Iy e S u τ~ (X，y) e F}称为 X 的输出集； 'X U X'称为元素 X的外延； 在Petri网中，采用一个圆圈表示一个库所，用一个矩形表示一个变迀；若（x，y) eF， 则x到y的一条有向边表示它们的流关系； 定义引发规则： 设PN = (S，T ;F，Mtl)为一个Petri网，则其具有如下的变迀发生规则： 1) 对于变迀t e T，如果V.veS: .s'eV-Mdd，则变迀t在标识M有发生权，记为M[t > ; 2) 如果M[t >，则在标识M下，变迀t能够发生，从标识M发生变迀t得到一个新的标 识 M'，记为 M[t>M'，VseS』，根据上述Petri网的定义，构建Web服务的形式化模型如下： 定义Web服务： 一个Web服务描述为一个四元组WS = (SF，I，0)，其中： (1) SF表示服务的功能语义描述； (2) 1、0表示服务的输入、输出参数集，并且//^/^0，？=化仙1^，？.(：〇11(3印〇，其中， ① P. name是输入、输出参数名； ②P. concept是一个输入、输出参数的本体概念，用以表示参数的语义； 定义服务请求： 一个服务请求表示为R = (SI U OJ，其中： (1) S匕表示服务请求的功能语义描述； (2) 仁代表服务请求者可提供的输入参数集； (3) Or代表服务请求者需要输出的参数集； 定义服务网元： 服务WS = (SF，I，0)的服务网元定义为SNU = (t，It，0t，Ft，M)，其中： (1) t是一个能够完成服务功能的变迀； (2) It= 't = {sn, si2, si3,…，sin}是变迀t的输入集，代表服务的输入参数集合；Ot = t' = {sQl, Sq2, Sq3,…，SraJ代表服务的输出参数集合； (3) Ft= (ItXt) U (tX0t)是有向弧集合，表示服务的输入、输出参数的流关系； (4) M是服务网兀的标识，M :It U 0 t- {0, 1}; (5) 变迀t在M下的发生规则为： ① Vpe/: M(/;)=l，则变迀t在M下有发生权，记为M[t> ; ② 若M [t>，则t在标识M下能够发生并得到一个新的标识，记作M [t W，对于 J； vj〇r定义服务簇： 对于η个服务WS1, ws2, . . .，SC = (Ws1, ws2, . . .，wsJ是一个服务簇，其中： i/eN/，Wsu= (SF u，Iu，0U，SCMu)，且V?. veN/，SFu和 SF v满足语义相似； 定义服务簇网元： 一个有 η 个服务的服务簇：SC = (Ws1, ws2, ...，wsn}，々e N"+，SNUk = (tk，Itk，0tk，Ftk，Mk)，服务簇网元表示为 SCNU = (SU，tc，Ic，0C，Fc，Mc)，其中： (1) SU = (SNU1, SNU2, SNU3, ···，SNUJ 是服务网元的集合； (2) t。是服务簇网元的变迀，且能够完成服务簇中各服务的功能； (3) I。、Oc分别表示服务的输入、输出参数集，并且VPeicU Oc，P= (P. conc印t，P. lable)，其中： ① P. concept是服务簇中服务输入参数对应的语义概念； ② P. Iable是一个nX 1的矩阵，其中，η是服务簇中服务的个数，并且P. Iable是服务 簇中的服务相应Ρ. concept的值； (4) F。= (IetXte) U (I^XOet)表示服务簇输入、输出参数的流关系； (5) 1^是服务簇网元的标识； 根据服务簇网元的定义，将一个服务的输入参数值作为服务簇输入矩阵的一行；将该 服务的输出参数值作为服务簇输出参数矩阵的对应行； b、基于服务簇的服务发现、组合与替换 设服务簇k的服务总数为m个，输入参数的总数为叫个，输出参数总数为η。个；I a、Oa、 分别代表服务簇的输入矩阵、服务簇的输出矩阵、服务请求的输入矩阵、以及服务请求 的输出矩阵；其中，Ia是一个mXn i矩阵，O a是一个mXn。矩阵，i 1?是一个I Xn i矩阵，〇 ^是 一个I X η。矩阵；I ttp(q)代表输入矩阵的第p行第q列的值； 输入一个服务簇网元模型SCNUk= (SU k, ?α, Iek, Oa, Fa, Ma)和一个服务请求网元S1 = {sfr，ir，〇r}，基于服务簇的服务匹配输出(:冴口 C。，其中，C1表示输入匹配矩阵，是一个mXη 土 矩阵；Q表示输出匹配矩阵，是一个mXn。矩阵； 基于服务簇的服务匹配的过程如下： SI:以Ia的首行开始，依次匹配该行的每个值； S2:若该行中元素的值小于或者等于、对应的值，则标记(^对应位置的值为1 ; S3:否则，标记为0 ; S4:以Oa的首行开始，依次匹配该行的每个值； S5:若该行中元素的值大于或者等于、对应的值，则标记(^对应位置的值为1 ; S6:否则，标记为0 ; S7:输出矩阵C1和矩阵C ^ 其中，服务匹配的时间复杂度是mXn^+mXn。2; 输入矩阵C1和矩阵C ^，基于上述服务匹配过程提出服务发现的过程，进而得到一个服 务集合S ;服务发现的具体过程如下： SI :p = 1, 5=0； S2: WC1的第p行开始，依次匹配该行的每个值； S3:若该行中所有的值都为1，则跳到S5 ; S4:否则p = p+1，循环这一匹配过程； S5:依次匹配(^第？行的各值； S6:若该行中所有的值都为1，则将该服务合并入集合S中，即S = S U {wsp}; S7:否则p = p+1，跳到S2 ; S8输出服务集合S ; 通过服务发现过程发现服务簇中满足服务请求的服务；服务发现输出的服务集合S 中，所有服务的输入输出匹配矩阵同为即服务集合S中的每个服务都满足服务 请求；服务发现过程的时间复杂度为：mXrii+mXn ; 定义WSiO WS j表示服务WS i和服务WS j的并行组合；定义WS i I WSj表示服务ws i和服务 WSj的串行组合； 设 a = [Id1, b2,…，bk]是一个 I Xk 矩阵，其中，IDiG {〇, 1}，/e Να+，且《eN+，对于 We Nt+，如果 h= 1，α 表示为 E，即 E = [1，…，1]; 对于V/e Ν/，若h= 0, α表示为〇,即〇 = [〇, 〇,…，〇]; 其中，α表示Petri网中的一个标识；并且α ρ α 2表示V ζ·￡ ΝΛ b 2i; 定义基元素： 设 a i= [b n，b12，…，blk]且 a 2= [b 21，b22，…，b2k]是两个 IXk 矩阵，其中 neN+，kN"+，於成川，1}，and b2ie {〇，1}，z.eNA+;若 α 2,则称（12是 a i的一个 基元素； 定义基集合： 设C是一个IXk矩阵的集合；f gC，如果apec'或者％是α p的一个基元素，且V C"，I C" I > I C' I，则称C'是C的一个基集合； 定义服务组合标志： 用于标记当前服务请求下的服务组合的服务基集合，其初始标志为0; 根据服务匹配过程提出服务匹配的运算方法如下： 定义匹配运算： SNUa= (t a, Ita, Ota, Fta, Ma)是一个服务网元，R = (SFr, Ir, Or)是一个服务请求； 匹配运算被定义为：定义服务簇匹配矩阵： WSrai= (SF _ I_ Orai)是一个服务请求； SCNUa= (SE a，tCa，Icta，0cta，Fcta，M a)是一个服务簇网元； 服务簇的输入/输出匹配矩阵被定义为：其中，we N+, ne N+, Nw+，j'e N"+, mk(sI(0)j) = 0,1 ; 输入服务簇网元SCNU = (SU，t。，I。，0。，F。，M。）和服务簇的匹配矩阵Q、Q，其中，VPe IcU 0C，P = (P. cone印t，P. Iable)，服务输入、输出参数的个数分别为k，1 ;输出服务集合 B ； 则服务串行组合的过程如下： si:依次匹配服务的输入、输出参数的参数语义； S2:若存在 Ici. concept = Ocj. concept，依次匹配 C1Q); S3:若C/⑴=0, WC1的首行开始，依次匹配该行的每个值； S4:若(V1= [1，1，…，1]，匹配相应的(V; S5:若C (j) = 1 且CU C Qp= [1，1，…，1]，则B = B U IwstJ，循环这一过程； S6:若β =0，输出"没有满足条件的串行服务组合"； S7:输出服务集合B ; SCM表示服务的基集合，通过SCM的过程体现服务簇中服务间的共性与个性，从而用 SCM来发现单一替代服务和组合替代服务； 输入服务簇SC = (WS1, WS2,…，WS1J和服务簇的匹配矩阵Cp C〇, SCM过程如下： Sl:依次匹配Hilj,若Hilj乒[1，1，…，1]，贝丨」SCM标记为Φ ; S2:匹配!!^，若 mok= [1，1，…，1]，SCMk标记为 0 ; S3:若mok乒[1，1，…，1]，找到所有不为Φ的SCMp且若所〇册~=五，则A = A U ImJ， P^Nn+- S4:若 A = Φ，则 SCMk= Φ ; S5:否则标记SCMk为A的基集合； S6:若在所有的SCM中有一列全为1，在所有SCM中删掉这一列； S7:输出 SCM ; 定义SCMkm代表SCMk的第m个元素 ；s ^是SCM km的第1列，n，m，/el, and 定 义组合规则： SC = {wSuWSw.^wsJ 是一个服务簇；其中，WSi= (SFolDOoSCMih/eN,,+; SCMk 丄 SCMp= SCMklI SCMplI SCMk2I SCMp2丄…丄 SCMknI SCM pn， 其中，SCMkniI SCMpni= [s " S2，…，sj 且，《e#，女，/;eN"+ ; 输入SC = (Ws1, ws2, ...，wsn}和失效服务wsm，输出替换服务集合A ; 则发现单一服务和组合服务的服务替换的过程如下： S0:A = Φ ； SI:若失效服务的SCMm= Φ或SCM m= 0 ; SI. 1:匹配SCM，若彐<SCMa=0,则将服务WSk并入集合A中，A = A U {ws k}; 51. 2:若匹配存在SCMi, SCMk，SCMiI SCMk= 0,则将ws JP wsk的组合并入集合A中， 即 A = A U (WsiO ws k}; S2:否则，若失效服务的SCMy Φ且SCM 0 ; 52. 1:如果匹配SCMk= 0,则将服务ws k并入集合A中，A = A U {ws k}; S2. 2:若匹配存在SCMkje SCM k，SCMmhe SCMm，且SCMkj彡SCMmh，则将服务wsk并入集合 A 中，A = A U {wsk}; S2. 3:如果匹配SCMi, SCMk，SCMiI SCMk= 0,则将ws JP wsk的组合并入集合A中，A = A U (WSiO ws k}； S3:若A = Φ ; S3. I:若SCMm中存在某一列的值为1，而其他服务的在该列的值都不为1，则将这一列 在所有的SCM中移除，转到S2 ; S3. 2:否则，输出"没有满足条件的替换服务"； S4:输出A，即为满足条件的替换服务集合。
【专利摘要】本发明公开了一种基于服务簇的服务组合与替换方法。本发明借助已有的服务聚簇方法构建服务簇，并基于Petri网提出服务及服务簇的形式化描述方法；将服务的输入输出参数抽象表示，通过参数矩阵来描述服务的输入输出参数；本发明中的服务匹配方法使服务簇中的服务间能够充分共性与个性，通过缩小服务查找范围，从而提高服务发现与组合效率；通过对服务簇模型的改进，提出Web服务组合替换方法；对服务簇内服务的并行组合与串行组合分别进行了描述，在服务簇内实现快速服务组合，进而实现高效率的服务组合替换；本发明中的服务替换方法，不仅能实现服务簇内单一服务替换,而且能实现服务簇内服务组合替换。
【IPC分类】H04L29/08
【公开号】CN104902018
【申请号】CN201510259703
【发明人】杜玉越, 盖俊静, 盖俊虎, 沙静, 刘伟
【申请人】山东科技大学
【公开日】2015年9月9日
【申请日】2015年5月20日
最新回复(0)