一种基于相关性感知的多目标服务组合方法

摘要

本发明涉及一种基于相关性的多目标服务组合方法，包括：将候选服务集合C

说明书

技术领域

本发明涉及云计算管理与控制技术领域，尤其涉及一种基于相关 性感知的多目标服务组合方法。

背景技术

随着SOA(Service-OrientedArchitecture，面向服务的体系结构) 技术和web服务技术的出现，互联网上出现了越来越多的具有封装 接口的服务应用。随着互联网上应用个数的急剧增多，出现了很多 的服务工业标准，例如：WSDL(WebServicesDescriptionLanguage， 网络服务描述语言)和UDDI(UniversalDescriptionDiscoveryand Integration，通用描述、发现与集成服务)等。商业过程通常需要一 系列的子服务进行协作，以完成需要的功能，这个过程叫做服务组 合。服务组合使得开发者可以根据预先定义好的需求将子服务组合 成为一个工作流。

不同供应商提供功能相同或者相近悬念具有不同非功能特征的 候选服务。非功能特征主要以服务质量来体现，当一个服务请求到 达时，由于服务质量具有多维的属性，例如包括有响应时间、吞吐 率和可用性等，是一个多目标优化的问题，因此如何选择合适的子 服务以实现最优的端到端服务质量成为研究热点。

为了处理不同服务质量属性之间的权衡和折中，现有技术中将 多目标优化的问题转化为单目标优化的问题，主要分为线性加权和 将目标转换为约束条件两类。其中，线性加权将不同目标归一化， 然后设置相应的权重再相加。一方面，在归一化过程中需要知道目 标的最大值、最小值或者平均值，然而实际应用中不容易获取这些 值；另一方面，设置权重还需要知道不同目标的优先级，实际应用 中优先级数据也不容易知道，且如何设置约束条件也未解决。

并且，现有技术中很多已有的服务组合解决方案没有考虑服务 之间的服务质量相关性，实际应用时一个子服务的服务质量值可能 会依赖其他的子服务。例如：选择将两个或者多个某公司的子服务 放置在同一个工作流中，该两个或者多个某公司的子服务的服务质 量可以打折。又如，航空预定公司在收费过程中，若用户使用信用 卡支付，可能会收多余的费用；若用户使用借记卡支付，则无需多 余费用。再如，选择将两个子服务放置在同一台服务器上，两者之 间传输时间将极大减小，组合服务的响应时间也相应减小。若不考 虑服务质量的相关性则会影响得到服务组合的服务解；但将服务质 量相关性考虑进服务组合，还会使得服务组合问题变得非常复杂。 因此，如何提高求解效率，是亟需解决的技术问题。

发明内容

本发明的目的之一在于提供一种基于相关性的多目标服务组合 方法，以提供一种求解效率高、考虑相关性的多目标服务组合方法。

为实现上述目的，本发明提出了一种基于相关性的多目标服务组 合方法，包括：

候选服务集合C_i中每个候选服务包含多个属性，若任选一个候选 服务与剩余候选服务中至少一个候选服务相对应的属性具有相关性， 则所对应的候选服务具有服务质量相关性；若一个候选服务与所有其 他候选服务的相对应的属性都没有相关性，则该候选服务没有服务质 量相关性，并将该没有服务质量相关性的候选服务存入相匹配的第一 候选服务集合

对所述第一候选服务集合中的候选服务进行两两比较以获取 优胜候选服务与非优胜候选服务，将所获取的优胜候选服务存入优胜 候选服务集合并从所述第一候选服务集合删除非优胜候选 服务；

从所述候选服务集合C_i中删除相对应的非优胜候选服务以获取 相匹配的子服务集合C′_i；

将所有子服务集合C′_i组合以形成新的服务组合解空间S′；从所述 服务组合解空间S′中随机选取多个服务组合解形成代表解集合计 算所述代表解集合中每个服务组合解S_p的粗略服务质量值并进行 分层；

穷举所选择的前s层中全部服务组合解的相关性信息，以获取全 部该服务组合解的实际服务质量值；

根据实际服务质量值对所对应的服务组合解进行排序，选择前K 个服务组合解以获取次优服务组合解集合。

可选地，所述候选服务集合C_i中每个候选服务包含多个属性，若 任选一个候选服务与剩余候选服务中至少一个候选服务相对应的属 性具有相关性，则所对应的候选服务具有服务质量相关性；若一个候 选服务与所有其他候选服务的相对应的属性都没有相关性，则该候选 服务没有服务质量相关性，并将该没有服务质量相关性的候选服务存 入相匹配的第一候选服务集合的步骤中采用如下公式判断每个候 选服务是否具有服务质量相关性：

式中，表示用于完成子服务i的候选服务，代表候选 服务的第r个属性是否具有相关性；代表候选服务是否具有 服务质量相关性；“∨”代表求并运算。

可选地，所述候选服务集合C_i中每个候选服务包含多个属性，若 任选一个候选服务与剩余候选服务中至少一个候选服务相对应的属 性具有相关性，则所对应的候选服务具有服务质量相关性；若一个候 选服务与所有其他候选服务的相对应的属性都没有相关性，则该候选 服务没有服务质量相关性，并将该没有服务质量相关性的候选服务存 入相匹配的第一候选服务集合的步骤之后，还包括：

计算每个候选服务集合中各个候选服务的Grade值，根据Grade 值对所述候选服务集合中全部候选服务进行升序排序。

可选地，所述从所述候选服务集合C_i中删除相对应的非优胜候选 服务以获取相匹配的子服务集合C′_i的步骤中根据如下公式得到子服 务集合C′_i：

$C_i^{\prime }=C_i-({\tilde{C}}_i-{\tilde{C}}_i-opt)$

式中，C′_i为子服务集合，C_i为候选服务集合，为优胜候选 服务集合，为候选服务集合。

可选地，所述将全部子服务集合C′_i组合以形成新的服务组合解空 间S′的步骤中采用如下公式获取服务组合解空间S′：

S′＝C′₁×C′₂×…×C′_m

式中，C′_i代表子服务集合，i＝1、2、3、……、m，符号“×”代 表笛卡尔乘积。

可选地，所述从所述服务组合解空间S′中随机选取多个服务组合 解形成代表解集合计算所述代表解集合中每个服务组合解S_p的 粗略服务质量值并进行分层的步骤包括：

选取所述服务组合解空间S′中任意两个服务组合解S_pi和S_pj进行 两两比较，若服务组合解S_pi优胜服务组合解S_pj，将服务组合解S_pj加 入到所述服务组合解S_pi的队列中，且将服务组合解S_pi加入所述服 务组合解S_pj的队列中；

定义利用L_i代表第i层的服务组合解集合；从第 一层i＝1开始，初始化当时，找到所有的服务组合解S_pj，并且将该S_pj加入L_i中，然后找到队列中所有的 服务组合解从每一个队列中删除服务组合解S_pj，再将服务 组合解从RemainingSet中删除；

重复上述过程，直至从而获取服务组合解空间 S′共有q层服务组合解；

其中，队列是所有可以优胜服务组合解S_p的服务组合解的集 合，是所有S_p优胜的解的集合。

本发明实施例通过计算服务组合解的粗略服务质量进行分层，并 计算所选择对应层中候选服务的相关性信息，以获取实际服务质量 值，从而能够处理实际系统带有相关性的服务组合情况，能够快速得 到实际系统的次优解，从而提高求解效率。

附图说明

通过参考附图会更加清楚的理解本发明的特征和优点，附图是示 意性的而不应理解为对本发明进行任何限制，在附图中：

图1是本发明实施例提供的一种基于相关性的多目标服务组合方 法框图；

图2是本发明一实施例中对候选服务优胜比较流程示意图；

图3是本发明一实施例中求解服务组合解流程示意图。

具体实施方式

下面结合附图和实施例，对本发明的具体实施方式作进一步详细 描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

本发明实施例提供了基于相关性的多目标服务组合方法，如图1 所示，包括：

S100、候选服务集合C_i中每个候选服务包含多个属性，若任选一 个候选服务与剩余候选服务中至少一个候选服务相对应的属性具有 相关性，则所对应的候选服务具有服务质量相关性；若一个候选服务 与所有其他候选服务的相对应的属性都没有相关性，则该候选服务没 有服务质量相关性，并将该没有服务质量相关性的候选服务存入相匹 配的第一候选服务集合

S200、对第一候选服务集合中的候选服务进行两两比较以获取 优胜候选服务与非优胜候选服务，将所获取的优胜候选服务存入优胜 候选服务集合并从第一候选服务集合删除非优胜候选服 务；

S300、从候选服务集合C_i中删除相对应的非优胜候选服务以获取 相匹配的子服务集合C′_i；

S400、将所有子服务集合C′_i组合以形成新的服务组合解空间S′； 从服务组合解空间S′中随机选取多个服务组合解形成代表解集合计算代表解集合中每个服务组合解S_p的粗略服务质量值并进行分 层；

S500、穷举所选择的前s层中全部服务组合解的相关性信息，以 获取全部该服务组合解的实际服务质量值；

S600、根据实际服务质量值对所对应的服务组合解进行排序，选 择前K个服务组合解以获取次优服务组合解集合。

下面结合附图及其实施例对本发明实施例所提供方法的步骤展 开说明。

本发明实施例中，用集合I＝{1,2,…,m}表示m个子服务，对于每 个一个子服务i有n_i个候选服务可以完成。该n_i个候选服务用候选服 务集合来表示；服务组合解表示某一 个具体的服务组合解，其中表示用于完成子服务i的候选服务； S＝C₁×C₂×…×C_m表示解空间。a_r表示第r个服务质量的属性，所有的 服务质量属性用向量A＝(a₁,a₂,…,a_l)来表示。从子服务的服务质量值 到组合服务的服务质量值的聚集函数用表示，聚 集函数有相加、相乘、最大化、最小化、并和交等。

本发明实施例中用Dep_r＝{<S_sp,v_sp>}表示第r个服务质量相关性集 合，其中S_sp代表具有相关性的子服务组合，v_sp代表该子组合的服务 质量值。二元变量代表候选服务的第r个属性是否具有相关 性；代表候选服务是否具有服务质量相关性；“∨”代表并运 算；代表候选服务第r个属性的默认值。

V(S_p)＝(v₁(S_p),…,v_r(S_p),…,v_l(S_p))用于表示组合服务S_p的服务质量 值。对于任意两个组合服务，S_p和S′_p，若下式成立，则称为S_p＞S′_p， 即S_p优胜S′_p。

$\forall r\in \{1,2,\mathrm{...},l\},v_r\left(S_p\right)\ge v_r\left(S_p^{\prime }\right);$

$\exists k\in \{1,2,\mathrm{...},l\},v_k\left(S_p\right)>v_k\left(S_p^{\prime }\right),$

其中，≥表示优于或相等，＞表示严格优于。最优的服务组合解 是解空间S中所有不被其他解优胜的解集，即最优解集合 对于目标值为最大化的服务 质量属性，将其服务质量值取反。

首先，介绍步骤S100、候选服务集合C_i中每个候选服务包含多个 属性，若任选一个候选服务与剩余候选服务中至少一个候选服务相对 应的属性具有相关性，则所对应的候选服务具有服务质量相关性；若 一个候选服务与所有其他候选服务的相对应的属性都没有相关性，则 该候选服务没有服务质量相关性，并将该没有服务质量相关性的候选 服务存入相匹配的第一候选服务集合的步骤。

候选服务集合C_i中包含多个候选服务，每个候选服务包含多个属 性。若对于其中一个候选服务，如果该候选服务的其中一个属性与该 候选服务集合C_i中其他至少一个候选服务的相对应的属性有相关性， 则判断该候选服务具有服务质量相关性。若对于其中一个候选服务， 如果该候选服务与剩余候选服务中的所有候选服务都没有相关性，则 判断该候选服务没有相关性。

本发明实施例中，利用公式(1)来判断一个候选服务是否具有 服务质量相关性

其中，二元变量表示候选服务是否具有服务质量相关性。

针对每个候选服务集合C_i，找出其中所有的候选服务， 并将满足条件的候选服务放入候选服务集合该第一候选服务集合 采用下式表示：

其次，介绍S200、对第一候选服务集合中的候选服务进行两两 比较以获取优胜候选服务与非优胜候选服务，将所获取的优胜候选服 务存入优胜候选服务集合并从第一候选服务集合删除非优 胜候选服务的步骤。

根据每个候选服务的相对应的属性的默认值，利用下式计算第一 候选服务集合中每个候选服务的Grade值：

$g\left(c_{j_i}^i\right)=\underset{r=1}{\overset{r=l}{\Sigma }}{d}_r\left(c_{j_i}^i\right).---\left(2\right)$

并根据Grade值对第一候选服务集合中的候选服务进行排序， 本发明实施例中采用升序排序。选择Grade值最小的候选服务置于 第一候选服务集合的第一个，其他候选服务依次放入至相应的位 置。

然后从第一候选服务集合中获取优胜候选服务与非优胜候选 服务。

本发明实施例中，定义优胜候选服务集合表示第一候选服 务集合中最优的候选服务集合。变量c_k代表第一候选服务集合中 第k个候选服务，二元变量IsDominated(k)＝1表示候选服务c_k已经被优 胜了。

如图2所示，初始化优胜候选服务集合针对所有的候 选服务c_k，初始化二元变量IsDominated(k)＝0。从候选服务c₁开始比较， 直至最后一个候选服务c_k。针对候选服务c_k的比较称为第k轮比较， 过程如下：如果候选服务c_k优胜候选服务c_j，那么标记 IsDominated(j)＝1，再继续将候选服务c_k和后面的候选服务 比较；不然，依次将候选服务c_k和之后的候 选服务c_j(j>k,IsDominated(j)＝0)比较。如果候选服务c_j优胜候选服务c_k， 标记IsDominated(k)＝1，并且直接跳到第k+1轮比较；否则，如果候选 服务c_k和候选服务c_j互相不优胜，则将候选服务c_k与和后面的候选服 务比较。该比较过程一直继续，直到进行到 第一候选服务集合中最后一轮候选服务的比较。

遍历所有候选服务的IsDominated(k)，如果IsDominated(k)＝0，则将 候选服务c_k加入优胜候选服务集合即优胜候选服务集合 中保存了第一候选服务集合中最优的候选服务。

再次，介绍S300、从候选服务集合C_i中删除相对应的非优胜候选 服务以获取相匹配的子服务集合C′_i的步骤。

如果IsDominated(k)＝1，则候选服务c_k为非优选候选服务。根据如 下公式求解子服务集合C′_i：

$C_i^{\prime }=C_i-({\tilde{C}}_i-{\tilde{C}}_i-opt)---\left(3\right)$

第四，介绍将多个子服务集合C′_i组合以形成新的服务组合解空间 S′；从所述服务组合解空间S′中随机选取多个服务组合解形成代表解 集合计算所述代表解集合中每个服务组合解S_p的粗略服务质量 值并进行分层的步骤。

采用如下公式(4)将多个子服务集合C′_i组合以获取服务组合解 空间S′。

S′＝C′₁×C′₂×…×C′_m(4)

从获取服务组合解空间S′中随机选取多个服务组合解形成代表 解集合本发明一实施例中随机选择多个代表解，例如一实施例 中选择10000个代表解，针对这10000个代表解，先不考虑相关性 信息，直接通过聚集函数计算每个服务组合解S_p的粗略服务质量值 V_c(S_p)。

聚集函数下式(5)所示：

$f:(c_{j_1}^1,c_{j_2}^2,\mathrm{...},c_{j_m}^m)\to S_p---\left(5\right)$

粗略服务质量值V_c(S_p)如式(6)所示：

V_c(S_p)＝(v_1c(S_p),…,v_rc(S_p),…,v_lc(S_p))(6)

例如，对于聚集函数为相加的属性，组合服务解的服务质量值等 于每个子服务的服务质量值之和；对于聚集函数为相乘的属性，组合 服务解的服务质量值等于每个子服务的服务质量的乘积。

根据粗略服务质量值V_c(S_p)对所选择的10000个代表解进行分层 和排序，根据代表解的分层以获取该10000个代表解的好坏信息。

第五，介绍S500、穷举所选择的前s层中全部服务组合解的相关 性信息，以获取全部该服务组合解的实际服务质量值的步骤。

根据上述步骤中每个服务组合解S_p的粗略服务质量值和一共的 层数，确定所需要选择的服务组合解的层数s，例如需要前三层的服 务组合解，则穷举该前三层服务组合解的所有的相关性信息，从而 可以得到这些服务组合解的实际服务质量值，从而获取服务组合解 空间共有q层服务组合解。

对所选择的前s层服务组合解进行分层过程如下：如图3所示，针 对每一个服务组合解S_p，设置两个队列和其中，队列代表 所有可以优胜服务组合解S_p的服务组合解的集合，队列代表所有 服务组合解S_p优胜的服务组合解的集合。

对于代表解集合中所有的服务组合解S_pi，初始化其中，服务组合解S_pi表示代表解集合中第i个服务组合解。

从代表解集合中所有的服务组合解中任选两个服务组合解进 行两两比较，若服务组合解优胜服务组合解S_pj，则将服务组合解S_pi加入服务组合解S_pj的队列中，将服务组合解S_pj加入服务组合解的队列中；若服务组合解S_pj优胜服务组合解S_pi，则将服务组合解 S_pi加入服务组合解S_pj队列中，服务组合解S_pj加入服务组合解S_pi的队列中。

定义用L_i代表第i层的服务组合解的集合。从第 一层(i＝1)开始，初始化当时，找到所有的服务组合解S_pj，并且将该S_pj加入L_i中，然后找到队列中所有的 服务组合解从每一个队列中删除服务组合解S_pj，再将服务组 合解从RemainingSet中删除。重复上述过程，直至为 止，此时可以得到代表解集合一共有q层解。

最后，介绍S600、根据实际服务质量值对所对应的服务组合解进 行排序，选择前K个服务组合解作为次优服务组合解集合的步骤。

根据上步骤中实际服务质量值，对所选择的前s层中全部服务组 合解进行排序，并选择前K个服务组合解作为次优服务解集合。

与现有技术中考虑服务质量相关性时计算复杂等问题相比，本 发明实施例提供的方法能够解决多目标的服务组合问题，可以有效 地处理不同服务质量目标之间的权衡及折中；此外，本发明实施例 通过计算服务组合解的粗略服务质量进行分层，并计算所选择对应 层中候选服务的相关性信息，以获取实际服务质量值，从而能够处 理实际系统带有相关性的服务组合情况，能够快速得到实际系统的 次优解，从而提高求解效率。

虽然结合附图描述了本发明的实施方式，但是本领域技术人员可 以在不脱离本发明的精神和范围的情况下做出各种修改和变型，这样 的修改和变型均落入由所附权利要求所限定的范围之内。