基于QoS的Web服务选择研究

基于QoS的Web服务选择研究摘要：提出了WSDL扩展模型，增加了有关服务质量QoS的描述的信息，并提出了基于该模型的服务匹配算法与基于非线性整数规划模型的QoS服务选择算法服务选择算法，可得到满足用户复杂任务要求的Web服务计划序列。Abstract:theWSDLexpan关键词：Web服务，服务质量，WSDL1引言在一般情况下，Web服务描述语言精确地、无二义地定义Web服务的功能和行为，服务发现系统通过对服务描述的精确匹配或可替代匹配，过滤出满足服务功能和流程行为的服务集合，但需要进一步按非功能属性排序服务，并为用户选择服务提供积极的参考。服务质量是非功能属性的一个重要部分，可以作为进一步区分服务的重要尺度。基于服务质量的Web服务选择是一个研究热点问题，由于没有统一的服务质量定义，导致每一选择模型作用有限。过分强调单个服务质量属性作用，而忽视服务的整体质量；过分强调主观需求而无视服务质量的客观信息，往往带有很大的随意性;过分强调整个组合服务的服务质量，不考虑组件服务是否局部最优因而不利于激励服务提供者等。针对上述不足，本章通过对Web服务描述语言WSDL加入QoS服务质量描述进行扩展，建立用户需求服务抽象模型和Web注册服务抽象模型，实现服务匹配。针对用户复杂任务的要求，提出两种QoS服务选择算法，并对算法进行数学模型的建立和求解。2基于QoS的Web服务选择2．1WSDL扩展模型WSDL是一种用于描述Web服务的语言，提供对服务辅助信息的说明能力，包括Web服务可识别的数据类型、消息模式、交互方式、服务的位置、错误信息和标头信息等，具有可扩展性。而Web服务的性能是服务量度的一个重要方面。为了更加完整地描述Web服务，更方便在运行时刻实现Web服务的动态选择，对WSDL进行了扩展，增加了有关服务质量QoS的描述的信息，扩展后的WSDL描述模型如下图所示：图1WSDL扩展模型基于扩展后的WSDL模型，考察的服务质量QoS的参数属性，则可以把一个服务S的质量可表为：Q(S)={Rprice(S)，Rtime(S)，Rreliability(S)，Rusability(S)，Rbandwidth(S)}由于WSDL具有可扩展性，因此在如WSDL中加入这些质量描述，无需再在一个更高层上加以说明，使用WSDL的服务接口即可实现。将扩展后的WSDL注册于Web服务的UDDI中，从而可以将UDDI中的已注册的Web服务抽象为包含QoS服务质量描述的一个三元组RS(RegisteredService)，方便服务的查询和匹配[37]。注册服务的抽象模型形式化定义为：RS={SN，SD，QoS}RS由3个元素组成：Web服务名称SN(ServiceName)，Web服务描述SD(ServiceDescription)和QoS度量。2．2需求服务抽象模型当用户根据任务需求查询Web服务时，将需求信息发送给UDDI进行查询。UDDI上注册的Web服务，是扩展WSDL加入QoS服务描述的Web服务，为了实现Web服务查询，这里把用户的需求服务也进行抽象，创建用户需求服务抽象模型US(UserService)。用户需求服务抽象模型由用户的需求所决定，简要说明了用户所需要的Web服务的特征，其形式化的定义为一个三元组：US={SN，SD，QoS}服务实现定义服务接口定义服务质量QoSWSDLServiceBindingMessagePortTypeportType服务费用响应时间服务可靠性服务可用性网络带宽……US由3个元素组成：SN表示要用户需要查找的Web服务的名称，SD和QoS分别表示用户需要查找的Web服务的文本描述和QoS度量。US由用户根据任务的功能要求和操作要求给定。需要说明的是SN在语法上具有灵活性，不一定要与需要的Web服务的名字完全匹配。为了实现RS和US的匹配，SD和QoS必须与RS定义中的各个元素具有相同的含义。3服务匹配算法根据UDDI规范可知，UDDI只提供根据服务名称和服务文本描述关键字查询Web服务的功能。如果用户对所需Web服务的关键字选择不准确，或者UDDI注册机只提供关键字精确匹配查询，不提供模糊匹配查询的功能，那么当关键字与服务名称或者服务描述中的内容有些细微差别时，用户都将得不到满意的结果。因此，单纯的从服务名称和服务文本描述查询方面考虑，UDDI提供的服务查询方式不够理想。为了解决这个问题，根据用户需求服务抽象模型US和Web注册服务抽象模型RS，提出了一种服务匹配的算法。算法的基本思想是比较US和RS中的参数值SN和SD，以一定的方法计算出二者的语法符合度。得到的RS可能不唯一，则根据符合度将RS排序，用户可以选择符合度较高的RS作为所需的Web服务。这里讨论的算法只考虑服务名称和服务描述中的语法信息，不考虑语义问题。语法符合度的计算采用简单的计算两个字符串共有的Q-grams[82]的数目的方法，符合度函数Sim(US，RS)用来计算US和RS的语法符合度。这个函数主要基于另外两个函数SimSN(US，RS)和SimSD(US，RS)以及权值1、2。SimSN(US，RS)和SimSD(US，RS)分别是计算两个服务名称和服务描述的语法符合度的二元函数，返回0到1之间的实数值，表明语法符合的程度。Sim(US，RS)=1SimSN(US，RS)+2SimSD(US，RS)权值1，2∈[0，1]，且1+2=1。经过服务匹配算法的处理后，得到满足用户需求的Web服务信息列表，表中的Web服务信息按照语法符合度排序。如果用户对Web服务的质量比如响应时间、带宽等还有要求，则对RS中的QoS参数值进行计算，结合符合度最终选择满足用户需求的Web服务。4服务选择算法以上只是解决了用户简单任务需求的情况，下面将解决用户复杂任务需求的情况，并给出QoS服务选择算法。对于用户的复杂任务需求，可以根据可用Web服务的QoS参数，选择出满足每个子任务的Web服务，得到优化选择的Web服务计划序列。在实现QoS服务选择时，不同应用对QoS的要求有所不同，对所有QoS参数进行优化不太可能，因为有些参数相互之间是矛盾的。比如对带宽和可靠性而言，占用带宽越小越好，而带宽越小可靠性则会降低。另外，对不同的应用而言，侧重的QoS参数有所不同。例如，对于网络流媒体服务，对时延和带宽有较高要求。因此在综合考虑QoS服务选择时，应该优先考虑该应用所侧重的QoS参数。另一方面，QoS服务选择中的算法复杂度关系到该算法的可实现性，而QoS参数的选择直接关系到算法复杂度，支持的度量参数越多，越能有效保证提供的服务质量，但算法复杂度增大，性能下降，选择到完全满足要求的服务的概率随之减小。因此合理解决多参数问题，在设计低复杂度的QoS服务选择算法中占有重要地位。本节借鉴QoS路由算法的思想，提出两种QoS服务选择算法，分别是基于非线性整数规划模型的QoS服务选择算法和基于改进的蚁群算法的QoS服务选择算法。4．1服务选择问题描述假设用户任务T有m个子任务，T={1t，2t，…，mt}。经过UDDI查询匹配后，一个子任务可能对应多个可选的Web服务以完成此任务，其中iS={1is，2is，…，nis}，1,2,...im，为任务it的匹配服务集合，元素之间的区别仅在于QoS服务质量的优劣。服务匹配结果为：R={11,tS，22,tS，...，,mmtS}。则QoS服务选择的结果为：r={111,jtS，222,jtS，...，,mmmjtS}，为满足用户复杂任务需求的Web服务计划序列。4．2基于非线性整数规划模型的QoS服务选择算法本小节讨论的QoS服务选择算法只选取服务响应时间和服务可用性作为QoS参数，并假设它们相互独立。若要考虑两个以上的QoS参数，其解决方法与此处对两个参数的解决方法相类似，只须在处理时再加入约束条件即可。受两个或多个独立的可加或可乘性参数的任意组合条件约束的选择算法都是NP－完全的[83]。本小节建立了一个非线性整数规划模型，并根据模型的特点，提出了用线性整数规划逐次迭代逼近求解的启发式算法。4．2．1问题模型借鉴QoS路由算法的思想，将路由中的每条通信路径上的质量属性值看成每个Web服务的质量属性，从而每一条服务路径都对应着一个Web服务计划序列，根据全局约束，找到一条满足约束条件的顺序型的服务路径。对于下图所示的服务路径，给定一首任务1t和终任务mt，两者之间有2m个服务节点，每个任务节点kt存在kn个可选服务，1,2,...km。图2服务路径图对于用户要求的m个子任务，图5-2中存在1mkkn＝条服务路径。任务节点kt第i个可选服务响应时间kir，服务可用性为kif，1,2,...km，1,2,...kin，从服务路径图中找出一条以1t为起点、mt为终点的服务路径，对应QoS服务选择的一个结果，要求服务可用性最大且响应时间不大于给定的响应时间0r。服务路径最大平均响应时间为121max{,,...}nkmkkkkrrr＝，最小平均响应时间为121min{,,...}nkmkkkkrrr＝。引入决策变量ikx，当选择任务kt的第i个可选服务执行时，ikx=1，否则ikx=0。ikx满足1kinkix=1，1,2,...km。这样所选择的服务路径的响应时间为11kmnkikikirrx，服务可用性为111(1)kmnkikiikffx。设0r是用户任务要求的服务执行的最大平均响应时间，则满足0r的最大服务可用性…………………………………………1n……2n……mn……1t……2t……mt……的服务路径可以归结于下面的非线性整数规划问题(NLIP)：目标函数为：11max1(1)kmnkikiikffx约束条件为：011kmnkikikirrxr；1kinkix=1，1,2,...km；{0,1}kix(1,2,...km，1,2,...kin)在对非线性整数规划问题求解之前，引入如下两条定义：定义1：若{kix，1,2,...km，1,2,...kin}满足NLIP的约束条件，则称{kix，1,2,...km，1,2,...kin}是上述NLIP的可行解。定义2：若{'kix，1,2,...km，1,2,...kin}满足NLIP的约束条件，且对任意满足约束条件的{kix，1,2,...km，1,2,...kin}，都有11111(1')1(1)kkmmnnkikikikiiikkfxfx，则称{'kix，1,2,...km，1,2,...kin}是NLIP的最优解。根据上述的定义，可知非线性整数规划问题的最优解确定了满足服务选择对响应时间的要求且具有最大服务可用性的服务路径。4．2．2模型求解本节对模型进行求解，在对非线性整数规划问题(NLIP)进行求解之前，先求解下面的含0-1变量的几何规划问题(GIP)：11min(1)kmnkikiikpfxGIP的约束条件NLIP相同，显然GIP与NLIP具有相同的最优解。GIP目前尚无有效的求其精确解的算法，比较实用的求解算法是近似解法[84,85]。下面通过目标函数的一阶泰勒展开式近似代替目标函数，将几何规划转化为线性整数规划，然后逐次迭代逼近来求出GIP的近似最优解。具体的算法步骤如下[86]：令1112(,,...,,)mTmnxxxx1．令1'min{|1,2,...,}mkikkrrin。如果0'rr，则NLIP无解，停止计算；否则取GIP的任一初始可行解0x。令0k，并选定求解终止精度为(0)。2．在点kx处，将目标函数近似地取为线性函数：()()()()kkTkkPxpxpxxx，其中表示函数的梯度。3．求解服务路径问题(kR)：min()()()()kkTkkPxpxpxxx约束条件是：011kmnkikikirrxr