基于遗传算法的Web服务发现优化模型研究

杜经纬

(运城学院 计算机科学与技术系, 山西 运城 044000)

0 引言

要实现服务共享和以服务结构为中心的系统复用，关键是探寻满足客户需求的Web服务.因此，无论学术界或行业领域均对Web服务的发现予以密切关注.Web服务发现的主要过程是服务匹配.传统的Web服务匹配是通过搜索关键词对UDDI方面的服务名称、身份、特点和其他注册信息来实现的，以致查全率太低而使得所调用服务的质量和自动服务组合均无保障[1,2].

实际上，在一些重大行业的应用方面，已经对具体领域的抽象服务的功能单元的具体特点进行过介绍.在实现组合时，符合上述特点的具体服务有多种.所谓抽象服务，即在功能上与其对应的具体服务相等的服务.因此，要实现对具体服务方面的合适Web服务的发现，主要是通过非功能特点(即服务质量)来实现.例如，用户可以选择最低廉又最快捷的服务，或两者有其一的服务来实现.

为了优化基础架构的QoS意识的Web服务选择，本文为Web服务的发现提出了一种优化的服务模型.

1 QoS参数的定义

鉴于不同Web服务的多项服务执行方案可解决相同的查询问题，有必要对所有可能的执行方案制定恰当的最优Web服务的选择标准.常见并已确定的QoS标准有：执行时间、服务费、可用性和可靠性.但具体应用过程中，要根据实际需要对QoS标准重新界定.本文采取可扩展本体技术确定了专用QoS标准.每个Web服务包含一系列运算，其中的最小调用单元Operation.Web服务(WS)的QoS运算定义如下：

QoS(ws,op)=〈T(ws,op),C(ws,op),

A(sw,op),U(ws,op)〉

(1)

这里，T(ws,op)是执行时间，C(ws,op)是费用，R(ws,op)是可靠性，A(ws,op)是可用性，U(ws,op)是QoS标准，定义为(U1(ws,op),U2(ws,op),…,Un(ws,op))，即，由n个用户界定的带有多个特点的向量.为便于创建并求解QoS模型，WS的调用运算表示为Task t，上述QoS模型可简化成下列一个5-元集合：

QoS(t)=〈T(t),C(t),R(t),A(t),U(t)〉

(2)

每个质量标准存在对应的计算、评价方法.每个QoS模型也存在一个整体评价方法.优化操作过程的目的在于使以下各个QoS参数最大或最小.

(1) 响应时间(T)：即服务操作调用后所需的平均复原时间，包括服务计算时间(Tcom)、中间处理时间(Tmid)和往来通信时间(Tnet).

总响应时间：

T(t)=Tcom(t)+Tmid(t)+Tnet(t)

(3)

(2) 服务费(C)：即Web服务用户必须支付的调用每项服务所需的费用.

(3) 可靠性(R)：即可使用服务操作的概率，定义为

R(t)=MTTF(t)/(MTTF(t)+MTTR(t))

(4)

其中，MTTF(t)是平均无故障时间；MTTR(t)是平均修复时间.

(4) 可用性(A)：即Web服务正常运行的概率，概率越大，可用性越高.因Web服务是根据次数来调用的，故可采用离散时间模型来表示可用性

(5)

其中

(5) 用户定义(U)：即服务用户界定的QoS标准，如声誉、安全性和互操作性.优化目标是使负参数(如响应时间和费用)最小，使正参数(如可用性和可靠性)最大.本文的目的之一是运用遗传算法，尽快研究出针对抽象服务的具体服务，从而建立起组合服务的流程.这就需要满足以下条件：

(a)满足基于服务水平协议(SLA)的QoS限制条件：如，服务用户的预算可能有限，以致服务费可能受限或响应时间不得超出具体约定.有时，局部受限如预算有限，以及全局受限如总响应时间这两个条件需要同时满足.

(b)实现一些特殊QoS参数的具体功能的优化：如用户可能会在维持最低费用的同时寻求最短的响应时间.这时，应关注带有N项抽象服务(运算)的组合服务S={ws1,ws2,…,wsN}，其结构取决于多个工作流.每个单元wsi与M项具体服务csi1、…、csiM有关，它们功能相当.

在探讨如何通过遗传算法找出最优解之前，必须先介绍如何计算一项组合服务的QoS，首先从元服务的QoS特点的计算探讨[3].

2 组合服务的QoS计算及评级

组合服务的QoS的计算方法与文献[4]的方法一样，工作流程的描写语言仅限于BPEL4WS.对于工作流里的一个Switch结构，每个Case陈述记录为一个可能选项.

表1给出了单个流程结构的QoS特征的聚合函数.对组合服务进行介绍是组合服务的具体应用事例，其中的每个抽象服务与对应的具体服务有关.总QoS可以根据表1中的法则计算得出.尽管已明确界定了一些标准的QoS特征的聚合函数[5]，但其他特征取决于具体应用的那些特征，可能需要根据抽象运算的本体库由用户来自定义.用户也需对单个工作流的聚合函数进行设定(如表1最后一行)，然后像标准的QoS特征那样发布到服务注册中心的WS-QoS库.

表1 单个流程结构的QoS特征计算的聚合函数

一个Web服务在其服务周期内会不断变化，因此，无法完全对SLA规定的QoS参数进行界定.通常情况下，多数用户会接受QoS参数的实际值与界定值之间的细微偏差，但是，若偏差过大，则说明Web服务功能的性能下降.因此，系统需要对所调用的Web服务的QoS参数进行监控.实际上，对QoS参数的变化进行监测有助于对Web服务进行评价，这对优化运算也起着重要作用[6].

当用户挑选并调用一项Web服务运算时，系统会检测预期QoS与实际发布的QoS之间的距离，由此，QoS的距离便等于所有QoS参数偏差(或倒数)的加权和.假设pQi和dQi分别是QoS的第i个参数的预期值和实际发布值，pos和neg分别是最大、最小值下的QoS参数序列数集，ωi是向整合者(或用户)提供服务的具体QoS特性方面的重要性，那么QoS距离即DQoS可以由以下公式计算得出：

根据以下公式计算得Web服务的评级

Ranting(op)=

在公式(7)中，负阀值θ-和正阀值θ+分别又称为置信下限和置信上限；q是QoS距离波动的调整因子，其值通常为1.根据公式，若一项Web服务的QoS距离位于SLA规定的QoS参数波动区间(θ-,θ+)，那么，结果就是正常评级；若QoS距离小于负阀值θ-，则评级下降；反之，则上升.通过给每个参数分配评级结果，可以逐一对每项服务的QoS进行计算.然后，根据每个参数的评级结果，将加权分配给目标函数里对应的QoS或对所有评级进行求和，最后得出整个优化公式.

迄今为止，Web领域已有多种评级体系，主要是通过用户反馈来实现，包括用户产品、服务评价以及供应商的个人经验这几方面.本文选取专门机构对Web服务运算的调用进行监控，从而可定期更新和提取服务评级.

3 目标函数及优化限制条件

一项Web服务能否顺利发挥其功能主要取决于QoS.因此，优化的目标在于挑选并应用QoS参数最优的Web服务.此外，参数评级和匹配度(MD)可对服务功能的成功发挥了进一步定义.因此，3个衡量标准即预期QoS参数、评级和匹配度可用来描写查询操作所涉及的任意Web服务操作.下文会做详细探讨.

目前，据QoS参数来计算一项操作的综合质量的方法多种多样.简单的加权法，广泛应用于决策过程，与一些较复杂的计算法相比[7]，其生成的结果十分接近排序结果.该法包括3个步骤，操作质量是各个值求和，在最后一步得出：

(1) 规范L个不同的QoS参数以使得相互可比较；

(2) 将用户自定义的加权ùi应用到查询操作的每个QoS参数，设wi>0；

(8)

(3) 对每个参数的加权、规范的QoS参数进行求和.

为了便于分析某个查询过程的每个抽象运算opj(与相匹配的具体服务阵列的项目指数相对应)，最大目标函数fj(opj)可表示为：

fj(opj)=rating(opj)×mod(opj)×

其中：

Ni(opj)=

Pi(opj)=

(12)

若αj是opj的加权，满足条件αj>0，

(13)

当ci(g)是相关查询的限制性条件时，ci(g)可从查询(等式条件)或由抽象运算(不等式条件)界定的范围直接计算得出，那么，查询过程的可行性解向量g=(op1,op2,…,opN)也就是下列多目标优化问题的解：

(14)

4 基于遗传算法的检索策略

遗传算法实际上是群组迭代进行不断优化的一个过程.与线性整数规划不同的是，GA不对目标函数和限制性条件的线性化加以限制，故优化模型可采用各种可能的QoS特征(甚至是个性化特征).为了通过GA进行求解，首先，需要找出合适的遗传集对问题进行编码.本文的遗传集表示为一个整数阵列，其中的项目数等于相关抽象服务的个数，每个元包含一个与抽象服务相匹配的具体服务阵列的项目指数.

交叉算子是标准的两点交叉，而变异算子随机挑选抽象服务(即在遗传集挑选位置)，并随机使用其它可行的具体服务来取代对应的具体服务.显然，仅存在一项可用具体服务的抽象服务可以通过GA演变来获取.要选择什么样的算子可通过传统的轮盘赌法来实现，这里，我们假设个体i存在适应度Fitness(i)，那么，i被选中的概率Pi是：

(15)

在子代个体生成后，遗传算法也可采纳最佳个体保存法，即，如果子代里适应度最高的个体的适应度比父代里最佳个体的适应度要低，那么，父代里的那个最佳个体将转移并保存到子代里.随后的问题是设计一个适应度函数，最大限度地提高某些QoS属性(如可靠性)，同时降低其他属性(如成本).采取用户自定义的QoS特征时，将由流程设计人员来制定适应度函数的要求.此外，适应度函数必须对无法满足限制性条件的个体进行惩罚以推动演变.假设原始群组(假定大小为m)满足公式(15)里的限制性条件，结合问题方面的编码和遗传算子，显然可以满足限制性条件g≥0.因此，得出罚函数：

(16)

这里因子yi指代：

(17)

那么，附带罚函数的遗传集g的适应度可表示为：

Fit(g)=F(g)+rH(g) (18)

在公式(18)中，r是罚函数的惩罚因子，且r>0.

最后，根据下线表现，必须对GA的优化法则进行界定：

(19)

这里，T是当前计算出现的代数，f(*,t)=max{f(1,t),f(2,t),…,f(m,t)}，即第t代最佳个体的适应度.该函数反映了经平稳调整后的群组里的最优个体的适应度变化情况，展现了个体的演变能力和GA的搜索能力，接近收敛值，因此PF(T+1)-PF(T)<ε可被视为循环终止的条件之一.为研究方便，设ε=1.0×10-5，为了防止因群组过大而致搜索时间过长但要获取到精确度好的搜索结果，设最大代数为循环终止的另一个条件.

5 研究实验与结论

通过模拟实验对优化模型的表现进行了鉴定，设酒店预订服务为目标，用户根据需要搜索所需服务内容.实验假设基于本体的所有推论已经完成，登记处已存在酒店服务的对应记录，输入Oracle数据库进行模拟.查全率和查准率的对比结果如图1所示.

图1 下线性能的演变

图1利用公式(19)里的下线表现来反映经调整后的群组里的最佳个体的适应度变化情况，以及个体的演变能力和GA的搜索能力.由图可见，所有3个不同的适应度函数均可确保GA找到满足限制性条件的解，同时，又能为全局QoS参数提供全面优化.

服务发现的主要过程是服务匹配.匹配算法的目标是实现所提供服务与所需服务之间的语义匹配，即根据信息的语义描述的分析结果来判定匹配度和相似度，从而找出用户需求的最佳服务.通常而言，用户所需的服务会不同，对如何界定一项服务，用户与提供商之间未事先达成一致，如果匹配标准制定得过于严格，就不利于体现匹配的共性.实验证明，本文所采用的GA效果良好，可在规定的时限内求得最优解.同时，实验还证实了所选用的适应度函数拉伸法的合理性和恰当性.

[1] Jia Yu, Rajkumar Buyya. A Novel architecture for realizing grid workflow using tup leSpaces[C]. Fifth IEEE /ACM International Workshop on Grid Computing, 2004,(8):119-128.

[2] Hong Fen, Lu Wang, Hui Yang. Grid workflow technology and its application in teacher professional development[J].Audio-Visual Education Research, 2007,(4):124-129.

[3] Yuan Ying-Chun, Li Xiao-Ping, Wan Qian, et al.Bottom level based heuristic for workflow scheduling in grids[J]. Computers, February, 2008,(2):68-74.

[4] M. Srinivas, L. M. Patnaik. Genetic algorithms:asurvey[C]. IEEE Comput,1994,(27):17-26.

[5] Wang Xiao-ping, Cao Li-ming. Genetic algorithm[M]. Xi′an: Xi′an Jiaotong University Press, 2002.

[6] Wu Xiong-qi ，Zeng Wen-hua. Grid resource scheduling algorithm based on improved genetic algorithm[J].Microelectronics and Computer，2006，23(9)：26-29.

[7] Anthony Sulistio, Chen Shin Yeo,Rajkumar Buyya.Visual model for grid modeling and simulation (gridsim) toolkit[C]. ICCS 2003, LNCS 2659 :1123-1132. 2003.