基于协同过滤的组合服务备选服务集生成系统及方法

摘要

基于协同过滤的组合服务备选服务集生成系统及方法，属于计算机领域，系统包含使用信息整理及模式单元和备选集及初始实例生成单元；方法为A判断，B查找，C形成模式，D计算QoS信息，E输入调用参数，F建立内存结，G得到输入数据量和调用时刻，H填入内存结构中；I匹配，QoS信息存在且连续则返回转P，J不完全属于已存在模式，K查找信息，不存在转N，LQoS为-1，M没有则预测，N没有执行信息则预测QoS；0计算相似度，P进行降序排序，Q计算可靠性，R选择备选服务集，S形成运行实例。本发明使得预测的结果更有针对性，更准确。

说明书

技术领域

本发明属于计算机领域，具体设计服务计算技术领域，特别涉及一种基于协同过滤的组合服务备选服务集生成系统及方法。

背景技术

Web服务采用一系列基于XML的标准和协议，很好地解决了跨组织、异构平台上应用的相互连接和集成问题。随着对Web服务应用要求的不断提高，能够提供增值功能的Web服务已经得到广泛的重视。组合Web服务由广泛分布在Internet环境中各个主机节点上的Web服务组合而成，由于缺乏对服务的统一管理和控制，使得组合Web服务整体的功能和质量难以保证，并且一旦发布且开始执行后，组合Web服务无法停止，包括调试、优化和升级等一系列维护活动必须在线完成，如果能够在组合Web服务运行前产生一个性能相对较好的初始实例并提供备选实例，则在很大程度上减少了运行时出现问题的可能，并且能够降低自适应调整的代价。

针对上述问题，本发明重点研究基于协作过滤的组合服务备选服务集推荐方法，即预测不仅基于同一个Web服务的历史执行信息，同时考虑面向相同或类似的其他服务的执行信息。基于这些历史执行信息，为组合服务产生一个较好的运行实例，并且为组合服务中的每个部分生成备选实例，以便在运行时发生错误后及时替换调整。

当前的组合Web服务初始实例的生成方法存在以下几个问题：

(1)通常对用户的功能需求考虑较多，对满足组合服务中某个任务功能需求的Web服务与相关任务绑定，作为执行实例，而对非功能需求往往只关注整个组合服务的QoS。

(2)即使考虑非功能需求，通常根据服务提供者发布的QoS信息进行服务选取，由于用户需求不同、所处网络环境、服务器状态等因素的影响，不同用户在不同的调用时刻对同一服务质量的感受可能会有很大的差别，因此服务提供者发布的QoS并不能准确的描述服务的实际运行质量。

(3)对于一次调用对每个任务只产生一个实例，当某个服务调用失效时，替换服务不够方便。

目前对于服务QoS的预测部分通常采用的是对历史信息求平均值的方式，这种方式没有考虑用户的个性化差异，有些基于协同过滤的方法在一定程度上考虑了用户差异，现有的协同过滤方式中的用户为具体用户，但是即使是同一用户在不同的时刻调用服务感受到的QoS也是不同的，如果用户多次使用某服务，则在协同过滤方法中该用户使用该服务的QoS值很难确定，如果采用平均值的方式仍然不够准确。真正影响服务质量的因素并不是不同的用户，而是用户调用服务时输入数据特征、网络情况及服务所在主机的性能决定了服务执行的QoS，也就是由一组输入、网络状态和服务器状态确定下来的一个相对固定的模式，在该模式下各服务的执行质量保持相对稳定的范围内。因此，本发明在基于协同过滤做服务QoS预测时，用户的概念为一个常用的使用模式，具有相似使用模式的调用感受到的服务质量比较接近。

发明内容

针对现有技术存在的不足，本发明提供了一种基于协同过滤算法的组合服务备选集生成系统及方法。该方法通过分析服务的历史执行信息和服务的监测信息，在考虑了环境因素、用户输入因素的影响下，进行协同过滤计算，为用户提供个性化的服务QoS预测，为组合服务提供备选服务集，从而产生组合服务的运行实例。

相关定义如下：

定义1服务使用信息：服务一次调用后相关的执行信息及监测信息值。格式如：

<服务ID，所在组合服务ID，所在组合服务实例ID，所在服务器的IP，调用时刻，输入数据量，输出数据量，主机接口吞吐量，服务器CPU利用率，服务器内存利用率，服务执行时间>。这些信息是为后续的模式提取模块准备相关数据。

定义2服务执行特征模式：对于一类服务，用户的输入、服务所处的环境等特征往往会集中在一个或者几个范围内，而这些特征值较为接近的实例通常执行QoS也较为接近，因此把这些相对集中的执行特征范围称作服务的使用模式。本发明主要考虑的是用户输入数据量、主机接口吞吐量、服务器CPU利用率及内存利用率。模式的格式为：

<DataSize_low～DataSize_high，CPU_low～CPU_high，Menmory_low～Menmory_high，Throughput_low～Throughput_high>，即为<输入数据量范围，调用时刻CPU利用率范围，调用时刻内存利用率范围，调用时刻主机接口吞吐量范围>。

定义3服务执行特征模式库：由多个服务执行特征模式组成的数据库称为服务执行特征模式库。

定义4模式-使用信息关系：对于每一次调用的特征值都属于一个或者多个调用模式，则将这种关联关系称作模式-使用信息关系，并将此关系保存于数据表中。

定义5模式-服务QoS关系：有一些服务的执行QoS在具体调用模式下保持稳定或者和模式存在一定的关系，这种关系可以通过矩阵MS表示：

$\left(\begin{array}{cc}& \left(\begin{array}{cccc}{s}_1& s_2& \Lambda & s_k\end{array}\right)\\ \left(\begin{array}{c}{m}_1\\ m_2\\ M\\ m_n\end{array}\right)& \left(\begin{array}{cccc}{q}_{\mathrm{1,1}}& q_{\mathrm{1,2}}& \Lambda & q_{1,k}\\ q_{\mathrm{2,1}}& q_{\mathrm{2,2}}& \Lambda & q_{2,k}\\ M& M& \Lambda & M\\ q_{n,1}& q_{n,2}& \Lambda & q_{n,k}\end{array}\right)\end{array}\right)$

该矩阵表示有n个模式，k个服务的模式-服务QoS关系，其中m_i表示第i类调用模式；而q_i，j为在模式m_i下，服务s_j的执行QoS相关信息，我们主要考虑服务的执行时间。其中：

假设某模式的格式如＜20M-30M，0.5-0.8，0.2-0.4，30M-40M>，该模式表示用户调用的输入数据量为20-30M，CPU利用率为0.5-0.6，内存利用率为0.2-0.4，主机接口吞吐量为30-40M，在该模式下，计算每个服务的表现。如果服务在该模式下有调用信息，且调用信息中的QoS值也稳定在一个范围内，则将该范围归纳出来；如果在该模式下有调用信息，但是调用的QoS值不连续，则说明该服务在此调用模式下并不完全受模式信息的影响，还会受到调用时刻等因素的影响，在具体使用时还需进一步计算，因此将与此模式下该服务的每条使用信息关联到模式中；若该服务没有此模式下的调用信息，则此处保存空值。

该系统包含两个单元，分别为使用信息整理及模式单元和基于指定业务流程和SLA的备选集及初始实例生成单元；使用信息整理及模式单元负责离线的进行使用信息整理并提取使用模式，当用户要进行组合服务调用时，由第二部分根据用户的需求和服务的历史使用信息进行计算生成服务的备选集及初始实例；其中使用信息整理及模式单元包括两个模块，分别为使用信息整理模块和模式提取模块；基于指定业务流程和SLA的备选集及初始实例生成单元包括三个模块，分别为内存结构生成及业务提取模块、协同过滤模块和备选服务集及初始实例生成模块；

使用信息整理模块实现对服务执行日志及监测日志中的值进行整理，得到后续模块需要的信息存放在使用信息数据库中；所需要的信息为多元组数据，包括服务ID，所在组合服务ID，所在组合服务实例ID，所在服务器的IP，调用时刻，输入数据量，输出数据量，主机接口吞吐量，服务器CPU利用率，服务器内存利用率和服务执行时间；

模式提取模块实现从使用信息整理模块得到的信息进行服务调用的常用模式提取；

首先将使用信息分组，对具有相似业务特征的执行信息作为一组，将这些业务特征提取出来作为一个模式。对于具有相似业务特征服务调用，将其执行QoS的范围归纳，建立模式和QoS之间的关系。

内存结构生成及业务提取模块实现处理用户的输入，由用户选择组合服务及SLA，对用户输入进行分析，得到用户输入的数据量大小、调用时刻和对整个服务的QoS约束；并根据用户输入的数据量大小、调用时刻和对整个服务的QoS约束信息及服务的历史执行信息，为组合服务中的每个任务及任务对应的服务获取其业务特征；将用户选择的业务流程及流程中各个任务的业务特征生成易于后续程序执行的内存结构，发送给协同过滤模块。

协同过滤模块负责模式匹配及基于协同过滤的QoS预测过程。在为某个服务预测其QoS信息时，首先将该服务的业务特征与模式库中的模式进行匹配，找到最为相近的模式或模式集合后，查找该模式下目标服务的执行信息，如果服务的QoS值可以由模式特征确定，则可以直接将已经保存的信息返回；否则如果该模式下没有目标服务的执行信息，需要根据其他相似服务的执行信息来为目标用户预测。如果在该模式下有目标服务的相关历史日志信息，但是这些历史信息并不能够得到一个稳定的值，则需要进行历史调用实例与目标服务的业务特征进行相似性计算，并由此预测目标服务的QoS信息。

备选服务集及初始实例生成模块实现针对本次用户需求生成组合服务各任务的备选服务集及初始实例。根据协同过滤模块预测出的QoS信息及服务的可靠性信息加权为服务进行排序，在备选服务集推荐的过程中，不仅仅要考虑预测的QoS信息，还要考虑服务的可靠性，如果可靠性过低的服务即使其预测QoS性能良好仍然不能够被推荐。查找执行日志中目标服务的多次调用信息，计算服务执行的可靠性，备选服务集生成模块根据协同过滤模块得到的服务的QoS信息对满足条件的服务进行排序，根据排序选择可靠性在0.5以上的服务作为备选服务集。如果运行时服务出现异常，则根据备选集中的服务顺序产生新的替换服务。

使用信息整理及模式提取单元的逻辑。当服务执行信息增量积累到一定程度后，触发使用信息整理模块，经过使用信息整理模块对执行日志中服务的历史使用信息和监测信息进行整理，整理后的使用信息保存在使用信息数据库中。模式提取模块负责从使用信息数据库中对增量的使用信息进行模式提取，并将提取出的模式保存在模式信息库中。

基于指定业务流程和SLA的备选集及初始实例生成单元的逻辑。当用户需求到达后，内存结构生成及业务特征提取模块根据用户选择的组合服务及业务性能需求(SLA)，为此次调用提取出组合服务中每个任务以及其对应的具体服务的业务特征，并生成内存结构发送给协同过滤模块。协同过滤模块将内存结构中的业务特征与模式信息中的模式进行模式匹配，根据匹配情况得到进行协同过滤计算，预测组合服务中每个任务对应服务的QoS信息。最后由备选集及初始实例生成模块根据协同过滤模块计算的服务QoS信息及可靠性计算产生组合服务的备选集以及初始实例。

采用基于协同过滤的组合服务备选服务集生成系统的进行备选服务集生成方法，按如下步骤进行：

1、使用信息整理及模式单元；

1.1使用信息整理模块

步骤A、判断服务执行信息增量是否到达阈值δ，其中δ指使用信息增加的百分比；如果到达，则触发使用信息整理，将已有的日志信息进行整理，从服务执行日志及环境监测日志中抽取出服务使用信息，生成多元组数据包括服务ID，所在组合服务ID，所在组合服务实例ID，所在服务器的IP，调用时刻，输入数据量，输出数据量，主机接口吞吐量，服务器CPU利用率，服务器内存利用率和服务执行时间；否则结束；

1.2模式提取模块

步骤B、针对步骤A中得到的使用信息增量查找具有相似调用方式的调用；

步骤C、抽取出步骤B中得到的相似调用方式中相关特征作为一个模式，相关特征是指用户输入数据量、服务所在主机接口吞吐量、主机CPU利用率及内存利用率，时间规律需要从挖掘日志中抽取；

步骤D、对于每个模式按执行特征模式提取算法，计算此模式下每个服务的QoS信息，得到的数据信息如下面的矩阵所示：

$\left(\begin{array}{cc}& \left(\begin{array}{cccc}{s}_1& s_2& \Lambda & s_k\end{array}\right)\\ \left(\begin{array}{c}{m}_1\\ m_2\\ M\\ m_n\end{array}\right)& \left(\begin{array}{cccc}{q}_{\mathrm{1,1}}& q_{\mathrm{1,2}}& \Lambda & q_{1,k}\\ q_{\mathrm{2,1}}& q_{\mathrm{2,2}}& \Lambda & q_{2,k}\\ M& M& \Lambda & M\\ q_{n,1}& q_{n,2}& \Lambda & q_{n,k}\end{array}\right)\end{array}\right)$

其中m_i(1≤i≤n)表示第i类调用模式，其格式为：<DataSize_low～DataSize_high，CPU_low～CPU_high，(改成宋体比较清楚)Memory_low～Memory_high，Throughput_low～Throughput_high>，即为<输入数据量范围，调用时刻CPU利用率范围，调用时刻内存利用率范围，调用时刻主机接口吞吐量范围>，s_j(1≤j≤k)表示第j个服务，而q_i，j为在模式m_i下，服务s_j的执行QoS信息，主要记录了服务的执行时间信息；

其中执行特征模式提取算法，按如下步骤进行：

输入：服务使用信息包括执行日志和监测日志；

输出：模式及模式与服务，模式与使用信息的关系；

步骤1)、在服务使用信息库中随机找到一条没有所属模式的使用信息，设为信息P，其中信息格式为<输入数据量，服务器CPU利用率，服务器内存利用率，主机接口吞吐量，执行时间>，将以其为种子产生一个新的模式，为其赋一个模式编号；

步骤2)、设定该信息为服务s在执行时的特征信息，其对应上述向量的值为＜DataSize_s，CPU_s，Memory_s，Throughput_s，t_s>；

步骤3)、在服务使用信息库中查找与执行信息P的执行特征相近的使用信息集合，即将执行特征中除时间外其他特征值与s的使用信息相差在±ε以内的信息；

步骤4)、将步骤3)中得到的使用信息集合记为L(l₁，l₂，…l_n)，称作一个簇，在模式-使用信息中将这些信息编号与该模式编号组合作为一条新的记录，如果L中个数n＞minP，其中minP为一个簇里最少执行信息条数。

步骤5)、则在这n条执行信息里找到不同服务的使用信息，并且跳到步骤2)，但是特征向量包括执行时间继续在服务使用信息库中查找相似的使用信息集合，直到服务的相邻信息个数小于minP时，说明到此时相似信息的密度已经变小，此时停止继续循环；

步骤6)、对加到簇里的信息进行整理，统计各个特征的取值范围，将模式表中对应的模式特征填写完整，并对属于该模式的使用信息进行整理，将每个服务对应到该模式下的QoS信息记录到模式-服务表中；

步骤7)、如果所有使用信息都有所属的相关模式，则结束，否则跳到步骤1)继续执行；

其中：

步骤D1：如果服务在该模式下有调用信息，且调用信息中的QoS值也稳定在一个范围内，则将该范围归纳出来并记录在执行特征模式库中；

步骤D2：如果服务在该模式下有调用信息，但是调用的QoS值不连续，则将QoS信息记为-1，并将与此模式下该服务的每条使用信息关联到模式中，将关联关系保存；

步骤D3：若服务没有此模式下的调用信息，则此处保存空值。

2.基于指定业务流程和SLA的备选集及初始实例生成单元，步骤如下：

2.1内存结构生成及业务提取模块

步骤E、用户选择组合业务流程及SLA(Service Level Agree，服务等级协议)，输入调用参数；

步骤F、建立内存结构，内存结构为一个带有优先级队列的数组，如果组合服务有n个任务，那么数组就有n个元素，每个元素对应一个任务，每个元素中包含对任务的描述。并且对于每个数组元素对应一个优先级队列，队列中的元素为该任务的备选服务，每个元素预留本次调用的相应业务特征信息初始状态队列中元素为满足本任务功能需求的所有服务；

步骤G、根据业务流程的历史调用信息，得到流程中每个任务的输入数据量和调用时刻，并填入内存结构对应的服务中；

其中：

步骤G1：在服务使用信息中查找待执行组合服务的其它调用实例信息；

步骤G2：如果存在执行信息，则根据这些执行信息得到业务流程的输入数据量大小和组合服务中各任务的输入数据量大小的关系，为各个任务预测数据量特征信息；

步骤G3：如果在使用信息中没有该组合服务的使用信息，则对待执行组合业务中的每个任务，在使用信息中查找其它实例的执行信息，从而找出其中的输入数据和输出数据之间的关系，则得出用户的最初输入数据量input1经过第一个任务后的输出数据量，则该数据量作为第二个任务的输入数据量input2，按照关联规则依次得出，最后根据初始输入，得到每个任务的输入数据量大小；

步骤G4：调用时刻特征提取：每个任务的约束是在组合服务设计时就确定好的一个范围，则可根据每个任务的时间约束，并且根据调用时刻对其他每个任务的调用时刻进行计算，按照每个任务的时间约束与调用时刻之和进行计算。

步骤H、针对内存结构中每个任务对应的优先队列中的服务，根据服务的历史使用信息，估算出在输入数据量和调用时刻确定后的主机CPU利用率、内存利用率、接口吞吐量，并填入内存结构中；

步骤H1：每个服务的业务特征格式为<DataSize，InvokeTime，CPU，Memory，Throughput>，即<数据量，调用时刻，主机CPU利用率，主机内存利用率，主机接口吞吐量>；使用的信息可归纳如矩阵I，I_i表示对目标服务的第i次调用，t_i，d_i，c_i，m_i，tp_i分别表示第i次调用的调用时刻、调用时数据量值、CPU利用率、内存利用率、吞吐量的值，对于服务s的本次调用，调用时刻的CPU利用率、内存利用率、吞吐量的值都为未知，所以相应的位置为空值；

首先要基于调用时刻和输入数据量大小进行其它调用与本次调用的相似度计算，对两个特征分别进行规范化，由于调用时刻的相似性不能够通过时间值直接进行计算，所以先将输入数据量的值进行规范化，方法采用：

步骤H2：计算调用时刻的相似度，调用时刻的相似度主要是通过调用时刻对服务其它特征影响情况来计算的，调用时刻的相似度计算方法如下：在计算主机接口吞吐量时，查找挖掘日志，通过挖掘日志中该时刻的吞吐量情况来进行计算，把时间分成24个时间段，分别为0时、1时……23时。这些时间段的半径分别是左右各半个小时。从23点半到0点半都是属于0时，从0点半到1点半都是属于1时，依次类推下去，当一个服务请求是0点38发出的，我们就认为它应该在1时这个时间段内，挖掘日志中记录了时间段与其他特征之间的关系情况，

  服务接口吞吐量  时间段  20-30M  0时  25-50M  1时

步骤H3：设定要为服务s估算这三个特征值，调用为第n次调用，s的输入数据量为dn，s的被调用时刻为tn，通过步骤H2计算各个实例与实例I_n的相似度，然后根据两实例的相似度来估算各特征量的值，估算方法为：估算的特征为c，c有三种取值：主机接口吞吐量、主机CPU利用率、主机内存利用率。估算的公式如下：

$C_n=\bar{c}+\frac{{\Sigma }_{I_i\in \mathrm{Ins}}{\mathrm{sim}}_{\mathrm{Inst}}(I_n,I_i)\times (c_i-\bar{c})}{{\Sigma }_{I_i\in \mathrm{Ins}}\left(\right|{\mathrm{sim}}_{\mathrm{Inst}}(I_n,I_i)\left|\right)}$

由此得到的为调用时刻的主机接口吞吐量、主机CPU利用率和主机内存利用率的规范化值，在进行和原始数据的对比转换出具体的值。

2.2.协同过滤模块

步骤I、将目标服务的业务特征与执行特征模式库中的执行模式进行匹配；如果该模式下目标服务的QoS信息存在且在一个连续范围内，则直接将该信息返回，转步骤P；

步骤J、如果本次调用不完全属于任何已存在模式，则转步骤M；

步骤K、若用户业务特征属于某个执行特征模式，则查找该模式下目标服务的信息，如果不存在执行信息则转步骤N；

步骤L、如果服务在此模式下的QoS为-1，表示在模式条件限制下该服务有执行信息，但是其执行QoS并不稳定在一个范围内，则转步骤0；

步骤M、如果没有完全匹配的模式，则根据挖掘日志中的关联规则进行目标服务的QoS值预测；

其中：

步骤M1：在挖掘日志中查找与目标服务相关的关联规则，通过关联规则得到对于目标服务来说哪个特征对QoS的影响是最大的；

步骤M2：则先进行该特征的匹配，按次序匹配其它业务特征，得到相近的模式集合；

步骤M3：分别在这些模式下预测目标服务的QoS信息

步骤M4：将这些预测值加权求和。

步骤N、如果目标服务在匹配的模式下没有执行信息，则根据模式-服务信息中的其他使用过目标服务的模式信息，基于协同过滤为目标服务预测QoS；

其中：

步骤N1：计算其他服务与目标服务的相似度，找到与目标服务相似的服务集合；

其他服务与目标服务的相似度计算方法如下：

设定有m个模式，k个服务，其使用信息表示为矩阵：

$\left(\begin{array}{cc}& \left(\begin{array}{cccc}{s}_1& s_2& \Lambda & s_k\end{array}\right)\\ \left(\begin{array}{c}{m}_1\\ m_2\\ M\\ m_n\end{array}\right)& \left(\begin{array}{cccc}{q}_{\mathrm{1,1}}& q_{\mathrm{1,2}}& \Lambda & q_{1,k}\\ q_{\mathrm{2,1}}& q_{\mathrm{2,2}}& \Lambda & q_{2,k}\\ M& M& \Lambda & M\\ q_{n,1}& q_{n,2}& \Lambda & q_{n,k}\end{array}\right)\end{array}\right)$

其中m_i表示第i类调用模式；而q_i，j为在模式mi下，服务s_j的执行QoS信息，主要考虑服务的执行时间。

现在要为服务s_j预测其执行QoS信息，经过步骤I中的模式匹配，得到本次调用属于模式m_i，也就是要计算q_i，j的值；

(1)服务s_v和s_j相似度计算为：

sim(s_v，s_j)＝α·sim_sum(s_v，s_j)+β·sim_data(s_v，s_j)

式中sim_sum(s_v，s_j)为两服务s_v，s_j的共同使用模式的相似性，两个服务的共同使用模式的个数越多，说明两服务越相似。sim_data(s_v，s_j)使用服务s_v，s_j的模式的使用信息相似性，同样，两服务的模式使用信息越相似，两服务越相似；α，β为设定的可调节的同类项目相似性平衡参数；

(2)根据使用s_j和s_v的相同调用模式数量计算相似性，对于两个服务s_j和s_v，用P(s_j/s_v)表示服务s_j和s_v的使用共同调用模式的条件概率，用这个概率即可衡量s_j和s_v的相似性sim_sum(s_v，s_j)，计算方式如下：

${\mathrm{sim}}_{\mathrm{sum}}(s_v,s_j)=\frac{\mathrm{num}\left(s_v{s}_j\right)}{\mathrm{num}\left(s_j\right)}$

式中num(s_v，s_j)表示使用两个服务的相同模式数量，num(s_j)表示使用过服务s_j的模式数量，从公式(1)可以看出，sim_sum(s_v，s_j)的值在0到1之间，两个服务的共同使用模式越多，值越大；

(3)通过共同使用模式上服务s_v和s_j的使用数据计算两服务的相似性，计算方式采用改进的余弦值计算方法.设定s_v与s_j的共同使用模式的集合为M_oq_u，v表示模式m_u下服务s_v的QoS值，表示服务s_v在所有模式下使用数据的平均值。同理可知q_u，j和

${\mathrm{sim}}_{\mathrm{data}}(s_v,s_j)=\frac{{\Sigma }_{m_u\in M}(q_{u,v}-\overline{q_v})(q_{u,j}-\overline{q_j})}{\sqrt{{\Sigma }_{m_u\in M}{(q_{u,v}-\overline{q_v})}^2}\sqrt{{\Sigma }_{m_u\in M}{(q_{u,j}-\overline{q_j})}^2}}$

找到与目标服务相似的服务后，选出目标服务的最近k1个相似服务，设这些相似服务的集合为S′＝{s′₁，s′₂，Λ，s′_k1}；

步骤N2：基于此服务集合的QoS信息计算其他模式与目标模式的相似度，得到相似的模式集合；

其他模式与目标模式的相似度计算方法如下：

先将所有模式对于服务集合S′中服务的使用信息进行预测补充，对于模式m_i使用服务s_j的使用信息预测公式为：

其中s_p为服务集合S’中的一个服务。

由此，所有的模式对于服务集合S′中就都有了使用信息，计算模式的相似度，计算公式如下：

$\mathrm{sim}(m_i,m_u)=\frac{{\Sigma }_{v\in S^{\prime }}(q_{i,v}-\overline{q_i})(q_{u,v}-\overline{q_u})}{\sqrt{{\Sigma }_{v\in S^{\prime }}{(q_{i,v}-\overline{q_i})}^2}\sqrt{{\Sigma }_{v\in S^{\prime }}{(q_{u,v}-\overline{q_u})}^2}}$

其中q_i，v和q_u，v分别表示模式m_i和模式m_u使用服务s_v的历史QoS信息。表示模式m_i在所有服务上的使用数据的平均值。同理可知

根据模式的相似度计算公式，可以得到服务集合S′中服务的调用模式与目标模式之间的相似度，选择其中的最近k2个相似的模式集合M′＝{m′₁，m′₂，Λm′_k2}；

步骤N3：根据相似的模式在相似服务下的使用信息预测服务在此模式下执行的QoS值；

找到与目标服务相似的服务以及与目标模式相似的模式集合，则可根据相似模式下相似服务的使用信息来进行QoS的预测，按下式进行预测

其中q_v，j表示模式集合M’中的模式m_v使用服务q_v的历史QoS信息。

步骤0、如果所匹配模式下目标服务的执行状态并不稳定，则根据挖掘日志中使用信息与时间的关联规则对其他实例与本次调用的进一步计算相似度；这里的相似度计算不仅包括用户输入数据量、服务所在主机接口吞吐量、主机CPU利用率及内存利用率特征，还加入了调用时刻的相似度计算。时间相似度的计算依靠使用信息与时间的关联规则。其中的使用信息与时间关联规则中挖掘出了在某段时间内，服务的QoS保持稳定，则时间在此范围内的相似度较高；

其中：

步骤01：在数据挖掘中的关联规则查找使用信息与时间的关联规则；

步骤02：根据使用信息与时间关联规则进行时间特征相似度计算

使用信息与时间关联规则进行时间特征相似度的计算方法如下：

将不同小时之间的相似度定义如下表，

单位小时间的相似度

设D_ui表示第u个使用第i个服务的时间与对目标服务使用服务i时间的时间间隔，定义基于时间权重的函数，它是一个和D_ui相关的函数值，信息u属于近期访问的重要性，函数设计成关于D_ui的递减函数，即对于D_ui＞D_ki会存在如下关系：y(D_ui)＜y(D_ki)，将基于时间的权重函数作如下定义：

$y\left(D_{\mathrm{ui}}\right)=\frac{1}{b\times a^{D_{\mathrm{ui}}}},$其中α、b＞0

其中，D_ui代表时间(这是一个相对的时间，从u代表的服务调用时间到目标组合业务该服务预测的调用之间的时间差)，a、b是大于零的参数，a、b的取值是一个大于1的正数，公式中的b是用来调整函数走势的参数。保证求得的基于时间的权重函数值位于[0，1]之间；

步骤03：对模式特征做进一步匹配，匹配的方法如下：

协作过滤使用的信息可归纳如矩阵I，I_i表示对目标服务的第i次调用d_i，c_i，m_i，t_i分别表示第i次调用时数据量值，CPU利用率，内存利用率，吞吐量的值。在进行相似性计算前，首先对这些特征值进行规范化，设定得到的矩阵I’，

$I=\left(\begin{array}{cc}\left(\begin{array}{c}{I}_1\\ I_2\\ M\\ I_n\end{array}\right)& \left(\begin{array}{cccc}{d}_1& c_1& m_1& t_1\\ d_2& c_2& m_2& t_2\\ M& M& M& M\\ d_n& c_n& m_n& t_n\end{array}\right)\end{array}\right),$$I^{\prime }=\left(\begin{array}{cc}\left(\begin{array}{c}{I}_1\\ I_2\\ M\\ I_n\end{array}\right)& \left(\begin{array}{cccc}{d}_1^{\prime }& c_1^{\prime }& m_1^{\prime }& t_1^{\prime }\\ d_2^{\prime }& c_2^{\prime }& m_2^{\prime }& t_2^{\prime }\\ M& M& M& M\\ d_n^{\prime }& c_n^{\prime }& m_n^{\prime }& t_n^{\prime }\end{array}\right)\end{array}\right)$

相似度计算可使用如下公式：

${\mathrm{sim}}_{\mathrm{Inst}}(I_v,I_j)=$

$\frac{(d_v^{\prime }-\overline{I_v^{\prime }})(d_j^{\prime }-\overline{I_j^{\prime }})+(c_v^{\prime }-\overline{I_v^{\prime }})(c_j^{\prime }-\overline{I_j^{\prime }})+(m_v^{\prime }-\overline{I_v^{\prime }})(m_j^{\prime }-\overline{I_j^{\prime }})+(t_v^{\prime }-\overline{I_v^{\prime }})(t_j^{\prime }-\overline{I_j^{\prime }})}{\sqrt{{(d_v^{\prime }-\overline{I_v^{\prime }})}^2+{(c_v^{\prime }-\overline{I_v^{\prime }})}^2+{(m_v^{\prime }-\overline{I_v^{\prime }})}^2+{(t_v^{\prime }-\overline{I_v^{\prime }})}^2}\sqrt{{(d_j^{\prime }-\overline{I_j^{\prime }})}^2+{(c_j^{\prime }-\overline{I_j^{\prime }})}^2+{(m_j^{\prime }-\overline{I_j^{\prime }})}^2+{(t_j^{\prime }-\overline{I_j^{\prime }})}^2}}$

步骤04：计算实例总的相似度

经过以上步骤02和步骤03的计算，综合可以得到两个实例之间的相似度为：

sim(I_v，I_j)＝α·sim_time(I_v，I_j)+(1-α)·y(D_vj)·sim_Inst(I_v，I_j)

其中D_vj表示第v个使用第j个服务的时间与对目标服务使用服务j时间的时间间隔，y(D_vj)为基于时间的权重函数。

其中sim(I_v，I_j)为第v次调用与第j次调用业务相关特征之间的总相似性权重，α值在[0.1]区间内，α和1-α分别代表业务特征相似度与时间权重在总权重中所占比例，通过设置α可以调整两种权重在预测中的比例，适当的α会进一步提高推荐的准确率；

步骤05：基于服务历史实例QoS信息及协同过滤的服务QoS预测算法

经过步骤04中实例总的相似度，可以得到与目标实例最为接近的k3个实例组成的实例集合Ins＝{I′₁，I′₂，ΛI′_k3}。根据这个实例集合中的实例之间相似度进行目标服务的QoS预测，预测的方法采用如下公式：

其中q_n，j为实例I_n使用服务s_j的历史QoS信息，表示服务s_i在所有调用中的平均使用QoS值。同理。

2.3备选服务集及初始实例生成模块

步骤P、根据协同过滤模块得到的服务的QoS信息对满足条件的服务进行降序排序；

步骤Q、按照服务调用成功的次数与总调用次数的比值计算服务的可靠性；

步骤R、根据排序选择可靠性在0.5以上的服务作为备选服务集；

步骤S、在备选服务集最前面的服务即为运行实例。

本发明的优点：

本发明设计了一种组合服务备选服务集及运行实例的生成方法，该方法基于协作过滤方法进行算法设计。该方法考虑了用户的差异，可以为用户生成具有针对性的组合服务运行实例，并为组合服务的执行推荐高效可靠的选服务集，以方便在服务运行过程中失效时及时替换。组合服务备选集及运行实例生成过程中，需要对服务进行QoS预测，本方法采用的基于协作过滤方法不仅考虑了单个服务的QoS信息，还根据组合服务执行的历史信息，对某个服务在组合服务中的可能QoS进行了分析。本文引入了执行特征模式的概念及基于服务历史执行信息的执行特征模式提取的方法，模式的特征值包括服务的调用时刻、调用时的输入数据量、调用时刻服务所在主机的CPU利用率、内存利用率、接口吞吐量因素，当用户需求到达后，如果用户的业务特征与模式库中的模式匹配则可以在常数时间内为用户进行服务QoS预测，效率较高。当没有完全匹配的模式或者匹配模式下的QoS值不确定，采用基于协作过滤的方法进行个性化的服务QoS预测，考虑了用户在调用服务时调用时刻、用户输入、网络环境及服务所在主机的状态的差异，使得预测的结果更有针对性，更准确。

附图说明

图1本发明系统模块图；

图2本发明使用信息整理及模式提取单元的逻辑示意图；

图3本发明基于指定业务流程和SLA的备选集及初始实例生成单元的逻辑示意图；

图4本发明使用信息整理及模式提取单元的方法流程图；

图5本发明执行特征模式提取算法流程图；

图6本发明基于指定业务流程和SLA的备选集及初始实例生成单元的方法流程图；

图7本发明内存结构流程图；

图8本发明任务数据量特征生成方法流程图；

图9本发明基于协同过滤的服务QoS预测方法流程图；

图10本发明k＝5时的平均误差率比较示意图；

图11本发明k＝10的平均误差率比较示意图。

具体实施方式

本发明结合具体实施实例和说明书附图进行说明。

为了验证本发明提出的方法和系统的性能，进行了一系列的实验。实验环境由分布于不同位置的50个PC机构成，有处于校园网的，也有在外网不同区域的。在每台计算机上安装了监控软件，用来监测其上的服务执行时主机的CPU利用率，内存利用率以及接口吞吐量。产生的日志信息保存在数据库中，

如图1所示，该系统包含两个单元，分别为使用信息整理及模式单元和基于指定业务流程和SLA的备选集及初始实例生成单元；使用信息整理及模式单元负责离线的进行使用信息整理并提取使用模式，当用户要进行组合服务调用时，由第二部分根据用户的需求和服务的历史使用信息进行计算生成服务的备选集及初始实例；其中使用信息整理及模式单元包括两个模块，分别为使用信息整理模块和模式提取模块；基于指定业务流程和SLA的备选集及初始实例生成单元包括三个模块，分别为内存结构生成及业务提取模块、协同过滤模块和备选服务集及初始实例生成模块；

使用信息整理模块实现对服务执行日志及监测日志中的值进行整理，得到后续模块需要的信息存放在使用信息数据库中；所需要的信息为多元组数据，包括服务ID，所在组合服务ID，所在组合服务实例ID，所在服务器的IP，调用时刻，输入数据量，输出数据量，主机接口吞吐量，服务器CPU利用率，服务器内存利用率和服务执行时间；

模式提取模块实现从使用信息整理模块得到的信息进行服务调用的常用模式提取；

首先将使用信息分组，对具有相似业务特征的执行信息作为一组，将这些业务特征提取出来作为一个模式。对于具有相似业务特征服务调用，将其执行QoS的范围归纳，建立模式和QoS之间的关系。

内存结构生成及业务提取模块实现处理用户的输入，由用户选择组合服务及SLA，对用户输入进行分析，得到用户输入的数据量大小、调用时刻和对整个服务的QoS约束；并根据用户输入的数据量大小、调用时刻和对整个服务的QoS约束信息及服务的历史执行信息，为组合服务中的每个任务及任务对应的服务获取其业务特征；将用户选择的业务流程及流程中各个任务的业务特征生成易于后续程序执行的内存结构，发送给协同过滤模块。

协同过滤模块负责模式匹配及基于协同过滤的QoS预测过程。在为某个服务预测其QoS信息时，首先将该服务的业务特征与模式库中的模式进行匹配，找到最为相近的模式或模式集合后，查找该模式下目标服务的执行信息，如果服务的QoS值可以由模式特征确定，则可以直接将已经保存的信息返回；否则如果该模式下没有目标服务的执行信息，需要根据其他相似服务的执行信息来为目标用户预测。如果在该模式下有目标服务的相关历史日志信息，但是这些历史信息并不能够得到一个稳定的值，则需要进行历史调用实例与目标服务的业务特征进行相似性计算，并由此预测目标服务的QoS信息。

备选服务集及初始实例生成模块实现针对本次用户需求生成组合服务各任务的备选服务集及初始实例。根据协同过滤模块预测出的QoS信息及服务的可靠性信息加权为服务进行排序，在备选服务集推荐的过程中，不仅仅要考虑预测的QoS信息，还要考虑服务的可靠性，如果可靠性过低的服务即使其预测QoS性能良好仍然不能够被推荐。查找执行日志中目标服务的多次调用信息，计算服务执行的可靠性，备选服务集生成模块根据协同过滤模块得到的服务的QoS信息对满足条件的服务进行排序，根据排序选择可靠性在0.5以上的服务作为备选服务集。如果运行时服务出现异常，则根据备选集中的服务顺序产生新的替换服务。

使用信息整理及模式提取单元的逻辑如图2所示。当服务执行信息增量积累到一定程度后，触发使用信息整理模块，经过使用信息整理模块对执行日志中服务的历史使用信息和监测信息进行整理，整理后的使用信息保存在使用信息数据库中。模式提取模块负责从使用信息数据库中对增量的使用信息进行模式提取，并将提取出的模式保存在模式信息库中。

基于指定业务流程和SLA的备选集及初始实例生成单元的逻辑如图3所示。当用户需求到达后，内存结构生成及业务特征提取模块根据用户选择的组合服务及业务性能需求(SLA)，为此次调用提取出组合服务中每个任务以及其对应的具体服务的业务特征，并生成内存结构发送给协同过滤模块。协同过滤模块将内存结构中的业务特征与模式信息中的模式进行模式匹配，根据匹配情况得到进行协同过滤计算，预测组合服务中每个任务对应服务的QoS信息。最后由备选集及初始实例生成模块根据协同过滤模块计算的服务QoS信息及可靠性计算产生组合服务的备选集以及初始实例。

采用基于协同过滤的组合服务备选服务集生成系统的进行备选服务集生成方法，按如下步骤进行：

1、使用信息整理及模式单元；

1.1使用信息整理模块的流程图如图4所示

步骤A、判断服务执行信息增量是否到达阈值δ，δ＝10％，其中δ指使用信息增加的百分比；如果到达，则触发使用信息整理，将已有的日志信息进行整理，从服务执行日志及环境监测日志中抽取出服务使用信息，生成多元组数据包括服务ID，所在组合服务ID，所在组合服务实例ID，所在服务器的IP，调用时刻，输入数据量，输出数据量，主机接口吞吐量，服务器CPU利用率，服务器内存利用率和服务执行时间；否则结束；

1.2模式提取模块

步骤B、针对步骤A中得到的使用信息增量查找具有相似调用方式的调用；

步骤C、抽取出步骤B中得到的相似调用方式中相关特征作为一个模式，相关特征是指用户输入数据量、服务所在主机接口吞吐量、主机CPU利用率及内存利用率，时间规律需要从挖掘日志中抽取；

步骤D、对于每个模式按执行特征模式提取算法，计算此模式下每个服务的QoS信息，得到的数据信息如下面的矩阵所示：

$\left(\begin{array}{cc}& \left(\begin{array}{cccc}{s}_1& s_2& \Lambda & s_k\end{array}\right)\\ \left(\begin{array}{c}{m}_1\\ m_2\\ M\\ m_n\end{array}\right)& \left(\begin{array}{cccc}{q}_{\mathrm{1,1}}& q_{\mathrm{1,2}}& \Lambda & q_{1,k}\\ q_{\mathrm{2,1}}& q_{\mathrm{2,2}}& \Lambda & q_{2,k}\\ M& M& \Lambda & M\\ q_{n,1}& q_{n,2}& \Lambda & q_{n,k}\end{array}\right)\end{array}\right)$

其中m_i(1≤i≤n)表示第i类调用模式，其格式为：<DataSize_low～DataSize_high，CPU_low～CPU_high，(改成宋体比较清楚)Memory_low～Memory_high，Throughput_low～Throughput_high>，即为<输入数据量范围，调用时刻CPU利用率范围，调用时刻内存利用率范围，调用时刻主机接口吞吐量范围>，s_j(1≤j≤k)表示第j个服务，而q_i，j为在模式m_i下，服务s_j的执行QoS信息，主要记录了服务的执行时间信息；

其中执行特征模式提取算法，如图5所示，按如下步骤进行：

输入：服务使用信息包括执行日志和监测日志；

输出：模式及模式与服务，模式与使用信息的关系；

步骤1)、在服务使用信息库中随机找到一条没有所属模式的使用信息，设为信息P，其中信息格式为<输入数据量，服务器CPU利用率，服务器内存利用率，主机接口吞吐量，执行时间>；

步骤2)、设定该信息为服务s在执行时的特征信息，其对应上述向量的值为<DataSize_s，CPU_s，Memory_s，Throughput_s，t_s>，将以其为种子产生一个新的模式，为其赋一个模式编号；

步骤3)、在服务使用信息库中查找与执行信息P的执行特征相近的使用信息集合，即将执行特征中除时间外其他特征值与s的使用信息相差在ε，ε设为±10％以内的信息；

步骤4)、将步骤3)中得到的使用信息集合记为L(l₁，l₂，…l_n)，称作一个簇，在模式-使用信息中将这些信息编号与该模式编号组合作为一条新的记录，如果L中个数n＞minP，其中minP为一个簇里最少执行信息条数。

步骤5)、则在这n条执行信息里找到不同服务的使用信息，针对不同服务的使用信息的特征向量包括执行时间继续在服务使用信息库中查找相似的使用信息集合，并且跳到步骤2)循环查找，直到服务的相邻信息个数小于minP时，说明到此时相似信息的密度已经变小，此时停止继续循环；

步骤4)、对加到簇里的信息进行整理，统计各个特征的取值范围，将模式表中对应的模式特征填写完整，并对属于该模式的使用信息进行整理，将每个服务对应到该模式下的QoS信息记录到模式-服务表中；

步骤5)、如果所有使用信息都有所属的相关模式，则结束，否则跳到步骤1)继续执行；

其中：

步骤D1：如果服务在该模式下有调用信息，且调用信息中的QoS值也稳定在一个范围内，则将该范围归纳出来并记录在执行特征模式库中；

步骤D2：如果服务在该模式下有调用信息，但是调用的QoS值不连续，则将QoS信息记为-1，并将与此模式下该服务的每条使用信息关联到模式中，将关联关系保存；

步骤D3：若服务没有此模式下的调用信息，则此处保存空值。

2.基于指定业务流程和SLA的备选集及初始实例生成单元，步骤流程图如图6所示，步骤如下

2.1内存结构生成及业务提取模块

步骤E、用户选择组合业务流程及SLA(Service Level Agree，服务等级协议)，输入调用参数；

步骤F、建立内存结构，内存结构如图7所示。内存结构为一个带有优先级队列的数组，如果组合服务有n个任务，那么数组就有n个元素，每个元素对应一个任务，每个元素中包含对任务的描述。并且对于每个数组元素对应一个优先级队列，队列中的元素为该任务的备选服务，每个元素预留本次调用的相应业务特征信息初始状态队列中元素为满足本任务功能需求的所有服务；

步骤G、根据业务流程的历史调用信息，得到流程中每个任务的输入数据量和调用时刻，并填入内存结构对应的服务中；输入数据量特征的生成方法如图8所示。

其中：

步骤G1：在服务使用信息中查找待执行组合服务的其它调用实例信息；

步骤G2：如果存在执行信息，则根据这些执行信息得到业务流程的输入数据量大小和组合服务中各任务的输入数据量大小的关系，为各个任务预测数据量特征信息；

步骤G3：如果在使用信息中没有该组合服务的使用信息，则对待执行组合业务中的每个任务，在使用信息中查找其它实例的执行信息，从而找出其中的输入数据和输出数据之间的关系，则得出用户的最初输入数据量input1经过第一个任务后的输出数据量，则该数据量作为第二个任务的输入数据量input2，按照关联规则依次得出，最后根据初始输入，得到每个任务的输入数据量大小；

步骤G4：调用时刻特征提取：每个任务的约束是在组合服务设计时就确定好的一个范围，则可根据每个任务的时间约束，并且根据调用时刻对其他每个任务的调用时刻进行计算，按照每个任务的时间约束与调用时刻之和进行计算。

步骤H、针对内存结构中每个任务对应的优先队列中的服务，根据服务的历史使用信息，估算出在输入数据量和调用时刻确定后的主机CPU利用率、内存利用率、接口吞吐量，并填入内存结构中；

步骤H1：每个服务的业务特征格式为<DataSize，InvokeTime，CPU，Memory，Throughput>，即<数据量，调用时刻，主机CPU利用率，主机内存利用率，主机接口吞吐量>；使用的信息可归纳如矩阵I，I_i表示对目标服务的第i次调用，t_i，d_i，c_i，m_i，tp_i分别表示第i次调用的调用时刻、调用时数据量值、CPU利用率、内存利用率、吞吐量的值，对于服务s的本次调用，调用时刻的CPU利用率、内存利用率、吞吐量的值都为未知，所以相应的位置为空值；

首先要基于调用时刻和输入数据量大小进行其它调用与本次调用的相似度计算，对两个特征分别进行规范化，由于调用时刻的相似性不能够通过时间值直接进行计算，所以先将输入数据量的值进行规范化，方法采用：

步骤H2：计算调用时刻的相似度，调用时刻的相似度主要是通过调用时刻对服务其它特征影响情况来计算的，调用时刻的相似度计算方法如下：在计算主机接口吞吐量时，查找挖掘日志，通过挖掘日志中该时刻的吞吐量情况来进行计算，把时间分成24个时间段，分别为0时、1时……23时。这些时间段的半径分别是左右各半个小时。从23点半到0点半都是属于0时，从0点半到1点半都是属于1时，依次类推下去，当一个服务请求是0点38发出的，我们就认为它应该在1时这个时间段内，挖掘日志中记录了时间段与其他特征之间的关系情况，

  服务接口吞吐量  时间段  20-30M  0时  25-50M  1时

步骤H3：设定要为服务s估算这三个特征值，调用为第n次调用，s的输入数据量为dn，s的被调用时刻为tn，通过步骤H2计算各个实例与实例I_n的相似度，然后根据两实例的相似度来估算各特征量的值，估算方法为：估算的特征为c，c有三种取值：主机接口吞吐量、主机CPU利用率、主机内存利用率。估算的公式如下：

$C_n=\bar{c}+\frac{{\Sigma }_{I_i\in \mathrm{Ins}}{\mathrm{sim}}_{\mathrm{Inst}}(I_n,I_i)\times (c_i-\bar{c})}{{\Sigma }_{I_i\in \mathrm{Ins}}\left(\right|{\mathrm{sim}}_{\mathrm{Inst}}(I_n,I_i)\left|\right)}$

由此得到的为调用时刻的主机接口吞吐量、主机CPU利用率和主机内存利用率的规范化值，在进行和原始数据的对比转换出具体的值。

2.2.协同过滤模块，如图9所示；

步骤I、将目标服务的业务特征与执行特征模式库中的执行模式进行匹配；如果该模式下目标服务的QoS信息存在且在一个连续范围内，则直接将该信息返回，转步骤P；

步骤J、如果本次调用不完全属于任何已存在模式，则转步骤M；

步骤K、若用户业务特征属于某个执行特征模式，则查找该模式下目标服务的信息，如果不存在执行信息则转步骤N；

步骤L、如果服务在此模式下的QoS为-1，表示在模式条件限制下该服务有执行信息，但是其执行QoS并不稳定在一个范围内，则转步骤0；

步骤M、如果没有完全匹配的模式，则根据挖掘日志中的关联规则进行目标服务的QoS值预测；

其中：

步骤M1：在挖掘日志中查找与目标服务相关的关联规则，通过关联规则得到对于目标服务来说哪个特征对QoS的影响是最大的；

步骤M2：则先进行该特征的匹配，按次序匹配其它业务特征，得到相近的模式集合；

步骤M3：分别在这些模式下预测目标服务的QoS信息

步骤M4：将这些预测值加权求和。

步骤N、如果目标服务在匹配的模式下没有执行信息，则根据模式-服务信息中的其他使用过目标服务的模式信息，基于协同过滤为目标服务预测QoS；

其中：

步骤N1：计算其他服务与目标服务的相似度，找到与目标服务相似的服务集合；

其他服务与目标服务的相似度计算方法如下：

设定有m个模式，k个服务，其使用信息表示为矩阵：

$\left(\begin{array}{cc}& \left(\begin{array}{cccc}{s}_1& s_2& \Lambda & s_k\end{array}\right)\\ \left(\begin{array}{c}{m}_1\\ m_2\\ M\\ m_n\end{array}\right)& \left(\begin{array}{cccc}{q}_{\mathrm{1,1}}& q_{\mathrm{1,2}}& \Lambda & q_{1,k}\\ q_{\mathrm{2,1}}& q_{\mathrm{2,2}}& \Lambda & q_{2,k}\\ M& M& \Lambda & M\\ q_{n,1}& q_{n,2}& \Lambda & q_{n,k}\end{array}\right)\end{array}\right)$

其中m_i表示第i类调用模式；而q_i，j为在模式m_i下，服务s_j的执行QoS信息，主要考虑服务的执行时间。

现在要为服务s_j预测其执行QoS信息，经过步骤I中的模式匹配，得到本次调用属于模式m_i，也就是要计算q_i，j的值；

(1)服务s_v和s_j相似度计算为：

sim(s_v，s_j)＝α·sim_sum(s_v，s_j)+β·sim_data(s_v，s_j)

式中sim_sum(s_v，s_j)为两服务s_v，s_j的共同使用模式的相似性，两个服务的共同使用模式的个数越多，说明两服务越相似。sim_data(s_v，s_j)使用服务s_v，s_j的模式的使用信息相似性，同样，两服务的模式使用信息越相似，两服务越相似；α，β为设定的可调节的同类项目相似性平衡参数；

(2)根据使用s_j和s_v的相同调用模式数量计算相似性，对于两个服务s_j和s_v，用P(s_j/s_v)表示服务s_j和s_v的使用共同调用模式的条件概率，用这个概率即可衡量s_j和s_v的相似性sim_sum(s_v，s_j)，计算方式如下：

${\mathrm{sim}}_{\mathrm{sum}}(s_v,s_j)=\frac{\mathrm{num}\left(s_v{s}_j\right)}{\mathrm{num}\left(s_j\right)}$

式中num(s_v，s_j)表示使用两个服务的相同模式数量，num(s_j)表示使用过服务s_j的模式数量，从公式(1)可以看出，sim_sum(s_v，s_j)的值在0到1之间，两个服务的共同使用模式越多，值越大；

(3)通过共同使用模式上服务s_v和s_j的使用数据计算两服务的相似性，计算方式采用改进的余弦值计算方法.设定s_v与s_j的共同使用模式的集合为M_oq_u，v表示模式m_u下服务s_v的QoS值，表示服务s_v在所有模式下使用数据的平均值。同理可知q_u，j和

${\mathrm{sim}}_{\mathrm{data}}(s_v,s_j)=\frac{{\Sigma }_{m_u\in M}(q_{u,v}-\overline{q_v})(q_{u,j}-\overline{q_j})}{\sqrt{{\Sigma }_{m_u\in M}{(q_{u,v}-\overline{q_v})}^2}\sqrt{{\Sigma }_{m_u\in M}{(q_{u,j}-\overline{q_j})}^2}}$

找到与目标服务相似的服务后，选出目标服务的最近k1个相似服务，设这些相似服务的集合为S′＝{s′₁，s′₂，Λ，s′_k1}；

步骤N2：基于此服务集合的QoS信息计算其他模式与目标模式的相似度，得到相似的模式集合；

其他模式与目标模式的相似度计算方法如下：

先将所有模式对于服务集合S′中服务的使用信息进行预测补充，对于模式m_i使用服务s_j的使用信息预测公式为：

其中s_p为服务集合S’中的一个服务。

由此，所有的模式对于服务集合S′中就都有了使用信息，计算模式的相似度，计算公式如下：

$\mathrm{sim}(m_i,m_u)=\frac{{\Sigma }_{v\in S^{\prime }}(q_{i,v}-\overline{q_i})(q_{u,v}-\overline{q_u})}{\sqrt{{\Sigma }_{v\in S^{\prime }}{(q_{i,v}-\overline{q_i})}^2}\sqrt{{\Sigma }_{v\in S^{\prime }}{(q_{u,v}-\overline{q_u})}^2}}$

其中q_i，v和q_u，v分别表示模式m_i和模式m_u使用服务s_v的历史QoS信息。表示模式m_i在所有服务上的使用数据的平均值。同理可知

根据模式的相似度计算公式，可以得到服务集合S′中服务的调用模式与目标模式之间的相似度，选择其中的最近k2个相似的模式集合M′＝{m′₁，m′₂，Λm′_k2}；

步骤N3：根据相似的模式在相似服务下的使用信息预测服务在此模式下执行的QoS值；

找到与目标服务相似的服务以及与目标模式相似的模式集合，则可根据相似模式下相似服务的使用信息来进行QoS的预测，按下式进行预测

其中q_v，j表示模式集合M’中的模式m_v使用服务q_v的历史QoS信息。

步骤0、如果所匹配模式下目标服务的执行状态并不稳定，则根据挖掘日志中使用信息与时间的关联规则对其他实例与本次调用的进一步计算相似度；这里的相似度计算不仅包括用户输入数据量、服务所在主机接口吞吐量、主机CPU利用率及内存利用率特征，还加入了调用时刻的相似度计算。时间相似度的计算依靠使用信息与时间的关联规则。其中的使用信息与时间关联规则中挖掘出了在某段时间内，服务的QoS保持稳定，则时间在此范围内的相似度较高；

其中：

步骤01：在数据挖掘中的关联规则查找使用信息与时间的关联规则；

步骤02：根据使用信息与时间关联规则进行时间特征相似度计算

使用信息与时间关联规则进行时间特征相似度的计算方法如下：

将不同小时之间的相似度定义如下表，

单位小时间的相似度

设D_ui表示第u个使用第i个服务的时间与对目标服务使用服务i时间的时间间隔，定义基于时间权重的函数，它是一个和D_ui相关的函数值，信息u属于近期访问的重要性，函数设计成关于D_ui的递减函数，即对于D_ui＞D_ki会存在如下关系：y(D_ui)＜y(D_ki)，将基于时间的权重函数作如下定义：

$y\left(D_{\mathrm{ui}}\right)=\frac{1}{b\times a^{D_{\mathrm{ui}}}},$其中α、b＞0

其中，D_ui代表时间(这是一个相对的时间，从u代表的服务调用时间到目标组合业务该服务预测的调用之间的时间差)，a、b是大于零的参数，a、b的取值是一个大于1的正数，公式中的b是用来调整函数走势的参数。保证求得的基于时间的权重函数值位于[0，1]之间；

步骤03：对模式特征做进一步匹配，匹配的方法如下：

协作过滤使用的信息可归纳如矩阵I，I_i表示对目标服务的第i次调用d_i，c_i，m_i，t_i分别表示第i次调用时数据量值，CPU利用率，内存利用率，吞吐量的值。在进行相似性计算前，首先对这些特征值进行规范化，设定得到的矩阵I’，

$I=\left(\begin{array}{cc}\left(\begin{array}{c}{I}_1\\ I_2\\ M\\ I_n\end{array}\right)& \left(\begin{array}{cccc}{d}_1& c_1& m_1& t_1\\ d_2& c_2& m_2& t_2\\ M& M& M& M\\ d_n& c_n& m_n& t_n\end{array}\right)\end{array}\right),$$I^{\prime }=\left(\begin{array}{cc}\left(\begin{array}{c}{I}_1\\ I_2\\ M\\ I_n\end{array}\right)& \left(\begin{array}{cccc}{d}_1^{\prime }& c_1^{\prime }& m_1^{\prime }& t_1^{\prime }\\ d_2^{\prime }& c_2^{\prime }& m_2^{\prime }& t_2^{\prime }\\ M& M& M& M\\ d_n^{\prime }& c_n^{\prime }& m_n^{\prime }& t_n^{\prime }\end{array}\right)\end{array}\right)$

相似度计算可使用如下公式：

${\mathrm{sim}}_{\mathrm{Inst}}(I_v,I_j)=$

$\frac{(d_v^{\prime }-\overline{I_v^{\prime }})(d_j^{\prime }-\overline{I_j^{\prime }})+(c_v^{\prime }-\overline{I_v^{\prime }})(c_j^{\prime }-\overline{I_j^{\prime }})+(m_v^{\prime }-\overline{I_v^{\prime }})(m_j^{\prime }-\overline{I_j^{\prime }})+(t_v^{\prime }-\overline{I_v^{\prime }})(t_j^{\prime }-\overline{I_j^{\prime }})}{\sqrt{{(d_v^{\prime }-\overline{I_v^{\prime }})}^2+{(c_v^{\prime }-\overline{I_v^{\prime }})}^2+{(m_v^{\prime }-\overline{I_v^{\prime }})}^2+{(t_v^{\prime }-\overline{I_v^{\prime }})}^2}\sqrt{{(d_j^{\prime }-\overline{I_j^{\prime }})}^2+{(c_j^{\prime }-\overline{I_j^{\prime }})}^2+{(m_j^{\prime }-\overline{I_j^{\prime }})}^2+{(t_j^{\prime }-\overline{I_j^{\prime }})}^2}}$

步骤04：计算实例总的相似度

经过以上步骤02和步骤03的计算，综合可以得到两个实例之间的相似度为：

sim(I_v，I_j)＝α·sim_time(I_v，I_j)+(1-α)·y(D_vj)·sim_Inst(I_v，I_j)

其中D_vj表示第v个使用第j个服务的时间与对目标服务使用服务j时间的时间间隔，y(D_vj)为基于时间的权重函数。

其中sim(I_v，I_j)为第v次调用与第j次调用业务相关特征之间的总相似性权重，α值在[0.1]区间内，α和1-α分别代表业务特征相似度与时间权重在总权重中所占比例，通过设置α可以调整两种权重在预测中的比例，适当的α会进一步提高推荐的准确率；

步骤05：基于服务历史实例QoS信息及协同过滤的服务QoS预测算法

经过步骤04中实例总的相似度，可以得到与目标实例最为接近的k3个实例组成的实例集合Ins＝{I′₁，I′₂，ΛI′_k3}。根据这个实例集合中的实例之间相似度进行目标服务的QoS预测，预测的方法采用如下公式：

其中q_n，j为实例I_n使用服务s_j的历史QoS信息，表示服务s_i在所有调用中的平均使用QoS值。同理。

2.3备选服务集及初始实例生成模块

步骤P、根据协同过滤模块得到的服务的QoS信息对满足条件的服务进行降序排序；

步骤Q、按照服务调用成功的次数与总调用次数的比值计算服务的可靠性；

步骤R、根据排序选择可靠性在0.5以上的服务作为备选服务集；

步骤S、在备选服务集最前面的服务即为运行实例。

实验结果如图10、图11所示，k表示在进行协作过滤预测服务QoS时取目标服务的最相似k个服务的数据进行预测。AP方法指平均值预测方法，CF指的是常用的协作过滤方法，Ourmethord指本文采用的方法。图10和图11分别选择5近邻和10近邻。当矩阵密度不断增大时，本文的方法比AP方法和常用的CF方法都更加准确。从而提高了备选服务集生成的准确度，也为组合服务的稳定执行提供了保障。