服务质量感知的并行柔性Skyline服务发现方法

摘要

本发明涉及一种服务质量感知的并行柔性Skyline服务发现方法，包括：由每个并行节点均执行锦标赛选择算法而对其内部的候选服务进行修剪；再使得每个并行节点均执行区块支配算法而对其内部的候选服务进行筛选而获得局部Skyline服务；将所有的局部Skyline服务集合构成第一集合，再用区块支配算法对第一集合进行筛选而获得全局Skyline服务；判断全局Skyline服务是否存在第一约束，若判断为是，则利用柔性Skyline服务修正算法进行处理得到柔性Skyline服务集合后输出,否则，直接输出全局Skyline服务。本发明降低了计算复杂度、提升了服务选择精度，利于准确、高效地过滤出优质服务。

说明书

技术领域

本发明涉及网络服务技术领域，尤其是指一种服务质量感知的并行柔性Skyline服务发现方法。

背景技术

在云计算按需付费商业模式的推动下，众多服务提供商基于云平台提供了大量的服务。随着服务的快速增长，服务搜索空间急剧增加。因此，通过删除质量不好的服务来降低选择难度变得至关重要。由于每个服务均具有时间、费用、有效性等属性，根据服务质量(QoS)筛选出非支配服务从而降低服务选择复杂度，该问题被定义为服务质量感知的Skyline服务(又称非支配服务)发现问题。也即，Skyline查询是指从给定的一个D维数据对象集合S中选择一个子集，该子集中的任意一个数据对象都不能被S中的任意一个其他数据对象所支配。所谓支配关系是指在D维空间的数据集合S中，如果数据对象p至少在某一幅度上优于另一个数据对象q，而且数据对象p在其他维度上都不比数据对象q差(p优于或者等于q)，那么数据对象p能够支配数据对象q。

Skyline查询问题是通过对多维数据查询处理，返回在所有维度上不比其他数据差，并且至少在一个维度上比其他数据好的数据集合。该问题中，每个服务都由一组服务质量(QoS)属性值表示，目的是根据服务质量筛选出非支配服务，从而降低服务选择的难度。目前，常用的Skyline服务发现方法包括：SFS(基于排序过滤的非支配性服务发现)、BBS(基于树结构的非支配服务发现)、改进后的BNL方法(基于区块嵌套循环的非支配服务发现)等。但是这些方法都是串行执行的，需要对任意服务进行两两比较以获取两者的支配关系，且各维度的服务质量属性均需参与比较，其计算复杂度很高。

考虑到爆炸式增长的服务数量导致搜索空间急剧增加，并行化是提高Skyline服务发现效率的有效途径。目前研究逐步提出了并行Skyline服务发现方法，但其计算效率仍有待进一步提高。

另外，由于业务需求和客户偏好等原因，服务间往往存在各种服务质量(QoS)约束(如期限和成本约束)、服务间依赖和冲突约束，但是现有的Skyline服务发现方法所输出的均为硬Skyline服务，均无法支持上述服务质量、服务依赖等约束，从而易出现多删或少删部分较好服务的现象，最终降低了服务选择的精度，从而无法准确地过滤出潜在的优质服务。例如，即使有些服务不是Skyline服务，但当他们一起被选择时，可获得QoS折扣而变得具有竞争力。

综上所述，现有Skyline服务发现方法存在计算复杂度高、服务选择精度低的缺陷，从而无法准确、高效地过滤出潜在的优质服务。

发明内容

为此，本发明所要解决的技术问题在于克服现有技术中Skyline服务发现方法的计算复杂度高、服务选择精度低的缺陷。

为解决上述技术问题，本发明提供了一种服务质量感知的并行柔性Skyline服务发现方法，包括以下步骤：

S1)将每个任务的所有候选服务随机分配到多个并行节点，每个并行节点并行执行锦标赛选择算法而对并行节点内部的候选服务进行过滤修剪；

S2)获取过滤修剪后的所述候选服务的服务属性的边界值，并使得每个并行节点均根据获取的所述服务属性的边界值进行区块划分；

将过滤修剪后的所述候选服务重新分配到多个所述并行节点中，并将每个并行节点中所分配的候选服务归属到相应的区块；

S3)每个并行节点均执行区块支配算法而对并行节点内部的候选服务进行筛选而获得局部Skyline服务；

S4)将所有的局部Skyline服务集合在一起构成第一集合，再利用区块支配算法对第一集合进行筛选处理而获得全局Skyline服务；

S5)判断全局Skyline服务是否存在第一约束，若判断为是，则执行步骤S6),否则，直接输出所述全局Skyline服务；

所述第一约束包括QoS约束、属性依赖约束、服务依赖约束或服务冲突；

S6)利用柔性Skyline服务修正算法对所述第一约束所涉及的任务进行处理而得到柔性Skyline服务集合后输出。

在本发明的一个实施例中，所述步骤S1)中，每个并行节点执行锦标赛选择算法而对并行节点内部的候选服务进行过滤修剪的方法包括：在并行节点内部的候选服务中根据锦标赛选择规则选取多个候选服务作为标记服务，并将剩余的候选服务均与多个所述标记服务进行比较，然后剔除比至少一个标记服务差的候选服务。

在本发明的一个实施例中，不同的所述区块中的候选服务的服务属性的区隔值不完全相同，服务属性的区隔值越大表示该服务属性越好，则所述步骤S3)中，每个并行节点执行区块支配算法而对并行节点内部的候选服务进行筛选而获得局部Skyline服务的方法包括：

依次进行多次筛选，筛选次数等于区块划分数量，最终经多次筛选得到的候选服务为所述局部Skyline服务；

每次筛选均先选定一个区块作为代表区块，每次筛选所选定的代表区块不同；每次筛选的过程为：先筛选出代表区块中的Skyline服务，再将区块编号小于所述代表区块的其他区块中的候选服务分别与代表区块中的Skyline服务进行比较以获取支配关系，然后删除区块编号小于所述代表区块的其他区块中被代表区块中的Skyline服务所支配的候选服务；

在每次筛选的过程中，若其他区块中的候选服务的一个服务属性的区隔值小于代表区块中的Skyline服务的相应服务属性的区隔值，则该服务属性不再参与比较。

在本发明的一个实施例中，若不同任务之间存在QoS约束，则步骤S6)中利用柔性Skyline服务修正算法对QoS约束所涉及任务进行处理的方法包括：将要利用柔性Skyline服务修正算法进行处理的任务定义为待判任务，将与所述待判任务存在QoS约束的其他任务均定义为关联任务，获得每个所述关联任务中全局Skyline服务的QoS值的极限值，并对所有关联任务的QoS值的极限值进行聚合计算得到关联值，将待判任务中每个全局Skyline服务的QoS值均与所述关联值进行聚合计算得到判断值，对于判断值不能满足QoS约束的待判任务中的相应全局Skyline服务进行删除。

在本发明的一个实施例中，若全局Skyline服务存在属性依赖约束，则步骤S6)中利用柔性Skyline服务修正算法对属性依赖约束所涉及的任务进行处理的方法包括：定义与所述全局Skyline服务存在属性依赖约束的非Skyline服务为待处理服务，判断待处理服务在执行属性依赖约束后是否能够在所属任务中成为非支配服务，若判断为是，则在待处理服务所属任务中添加所述待处理服务，否则，不作处理。

在本发明的一个实施例中，若全局Skyline服务存在服务依赖约束，则步骤S6)中利用柔性Skyline服务修正算法对服务依赖约束所涉及的任务进行处理的方法包括：将要利用柔性Skyline服务修正算法进行处理的任务定义为待判任务，将与待判任务中的全局Skyline服务满足服务依赖约束的候选服务均定义为前件依赖服务；

若待判任务中的全局Skyline服务唯一，则判断前件依赖服务是否都存在于待判任务以外的其他任务的全局Skyline服务中，若判断为是，则不作处理，若判断为否，则在前件依赖服务所属任务中添加所述前件依赖服务，并在待判任务中添加第一次优服务，所述第一次优服务与所述前件依赖服务之间不存在服务依赖约束，且在待判任务中不考虑所述全局Skyline服务时能成为非支配服务；

若待判任务中的全局Skyline服务不唯一，则不作处理。

在本发明的一个实施例中，若全局Skyline服务存在服务冲突约束，则步骤S6)中利用柔性Skyline服务修正算法对服务冲突约束所涉及的任务进行处理的方法包括：将要利用柔性Skyline服务修正算法进行处理的任务定义为待判任务，将与待判任务中的全局Skyline服务满足服务冲突约束的候选服务均定义为前件冲突服务，若待判任务中的全局Skyline服务唯一，则判断前件冲突服务是否存在于待判任务以外的其他任务的全局Skyline服务中且前件冲突服务在所属任务中为唯一的全局Skyline服务，若判断为是，则在待判任务中增加第二次优服务且在前件冲突服务所属任务中添加第三次优服务，判断为否，则不作处理；

所述第二次优服务与所述前件冲突服务之间不存在服务冲突约束，且在待判任务中不考虑其所述全局Skyline服务时能成为非支配服务；

所述第三次优服务与所述待判任务中的全局Skyline服务之间不存在服务冲突约束，且在前件冲突服务所属任务中不考虑所述前件冲突服务时能成为非支配服务。

本发明的上述技术方案相比现有技术具有以下优点：

本发明所述的服务质量感知的并行柔性Skyline服务发现方法，通过锦标赛选择算法、区块支配算法和柔性Skyline服务修正算法来对候选服务进行多次筛选，大大降低了计算复杂度，并能够适应QoS约束、属性依赖约束、服务依赖约束或服务冲突等约束，从而避免了多删或少删部分较好服务的现象，提高了服务选择的精度，从而能够更加准确地过滤出潜在的优质服务。

附图说明

为了使本发明的内容更容易被清楚的理解，下面根据本发明的具体实施例并结合附图，对本发明作进一步详细的说明，其中，

图1是本发明的服务质量感知的并行柔性Skyline服务发现方法的流程框图；

图2是一算例的服务流程图；

图3是不考虑第一约束的情况下，第一组实验中在不同抽象任务数量下的Skyline服务发现方法的计算时间对比图；

图4是不考虑第一约束的情况下，第一组实验中在不同抽象任务数量下的Skyline服务发现方法的求解结果对比图；

图5是不考虑第一约束的情况下，第二组实验中在不同候选服务数量下的Skyline服务发现方法的计算时间对比图；

图6是不考虑第一约束的情况下，第二组实验中在不同候选服务数量下的Skyline服务发现方法的求解结果对比图；

图7是考虑第一约束的情况下，第一组实验中在不同抽象任务数量下的Skyline服务发现方法的计算时间对比图；

图8是考虑第一约束的情况下，第一组实验中在不同抽象任务数量下的Skyline服务发现方法的求解结果对比图；

图9是考虑第一约束的情况下，第二组实验中在不同候选服务数量下的Skyline服务发现方法的计算时间对比图；

图10是考虑第一约束的情况下，第二组实验中在不同候选服务数量下的Skyline服务发现方法的求解结果对比图；

具体实施方式

下面结合附图和具体实施例对本发明作进一步说明，以使本领域的技术人员可以更好地理解本发明并能予以实施，但所举实施例不作为对本发明的限定。

为便于理解，先对以下专业名词进行说明：“Skyline服务”是指非支配服务，是指该服务不能被所属任务中的其他服务所支配；所谓“支配”是指在D维空间的数据集合S中，如果数据对象p至少在某一幅度上优于另一个数据对象q，而且数据对象p在其他维度上都不比数据对象q差(p优于或者等于q)，那么数据对象p能够支配数据对象q，例如，服务具有时间和声誉这两个服务属性，若第一个服务的时间少于(优于)第二个服务的时间，且若第一个服务的声誉不低于第二个服务的声誉，则第一服务支配第二服务。

参照图1，本发明公开了一种服务质量感知的并行柔性Skyline服务发现方法，包括以下步骤：

S1)将每个任务的所有候选服务随机分配到多个并行节点，每个并行节点并行执行锦标赛选择算法而对并行节点内部的候选服务进行过滤修剪；

S2)获取过滤修剪后的所述候选服务的服务属性的边界值，并使得每个并行节点均根据获取的所述服务属性的边界值进行区块划分；

将过滤修剪后的候选服务重新分配到多个并行节点中，并将每个并行节点中所分配的候选服务归属到相应的区块；

例如，服务属性包括{时间，费用，声誉，成功率，有效性}这五个质量属性，各属性的取值范围分别为[6,12]，[5,8]，[0.95,0.99]，[0.91,0.96]和[0.94,0.99]，其中，6、12、5、8等均为服务属性的边界值，若将每个属性的取值范围分为两个区隔，如将时间的取值范围分为[6,9]和(9,12]这两个区隔，依此类推将其他属性也均划分为两个区隔，则一个并行节点中可以划分出2

S3)每个并行节点均执行区块支配算法而对本并行节点内部的候选服务进行筛选而获得局部Skyline服务；也即，并行节点内部最终筛选结束后剩下的候选服务均称为局部Skyline服务；

S4)将所有的局部Skyline服务集合在一起构成第一集合，再利用区块支配算法对第一集合进行筛选处理而获得全局Skyline服务；也即，对所有的局部Skyline服务筛选后最终剩下的局部Skyline服务均称为全局Skyline服务；

S5)判断全局Skyline服务是否存在第一约束，若判断为是，则执行步骤S6),否则，直接输出所述全局Skyline服务；

第一约束包括QoS约束、属性依赖约束、服务依赖约束或服务冲突；

其中，QoS约束通常存在于不同任务之间，而属性依赖约束、服务依赖约束或服务冲突约束存在于不同服务之间；

S6)利用柔性Skyline服务修正算法对所述第一约束所涉及的任务进行处理后输出，也即对第一约束所涉及的任务中的服务进行增加或删减处理后输出，处理后输出的服务称之为柔性Skyline服务，各柔性Skyline服务集合在一起形成柔性Skyline服务的集合。

上述服务质量感知的并行柔性Skyline服务发现方法，通过锦标赛选择算法、区块支配算法和柔性Skyline服务修正算法来对候选服务进行多次筛选修剪，大大降低了计算复杂度，提升了服务选择精度，锦标赛选择算法能够通过部分标记服务能够对明显较差的服务进行删减，避免了大量支配服务之间的成对比较，相较于传统Skyline服务发现方法中任意服务必须参与两两比较来说，有效降低了计算搜索复杂度，区块支配算法则在锦标赛选择算法删减过后再对候选服务进行精确过滤，其通过对剩余服务进行分区块，可精确定义服务区块间的支配关系，并通过区块支配快速实现Skyline服务发现，以进一步降低Skyline服务发现问题的计算复杂度；而柔性Skyline服务修正算法则对Skyline服务进行了修正，以适应QoS约束、属性依赖约束、服务依赖约束或服务冲突，从而避免了多删或少删部分较好服务的现象，从而提高了服务选择的精度，能够更加准确地过滤出潜在的优质服务。

另外，将锦标赛选择算法和区块支配算法分成独立的作业。这样做的原因是：在标赛选择算法之后每个并行节点的服务数量可能会不同，因此重新进行区块划分可以平衡每个并行节点的计算；并且使得各区块根据统一的服务属性的边界值进行划分，利于简化计算。

在其中一个实施方式中：步骤S1)中，每个并行节点执行锦标赛选择算法而对该并行节点内部的候选服务进行过滤修剪的方法包括：在并行节点内部的候选服务中根据锦标赛选择规则选取多个候选服务作为标记服务，可以理解的，标记服务通常为较优的候选服务，并将剩余的候选服务均与多个标记服务进行比较，然后剔除比至少一个标记服务差的候选服务，也即只要候选服务比其中一个标记服务差，则就剔除该候选服务。

该锦标赛选择算法的性能高度依赖于标记服务的好坏，由于每个服务只需要与标记进行比较，因此避免了大量支配服务之间的成对比较，通过部分标记服务对明显较差的服务进行删减，从而大大降低了计算复杂度。

在其中一个实施方式中：不同区块中的候选服务的服务属性的区隔值不完全相同，也即不同区块至少在一种服务属性上的区隔值不同，服务属性的区隔值越大表示该服务属性越好，例如，第29号区块的区隔值集合为sg＝{1,0,1,1,1}，第30号区块的区隔值集合为sg＝{0,1,1,1,1}，每个区隔值集合sg中的元素分别代表一种不同服务属性的区隔值，sg中五个元素从左至右分别代表第一、第二、第三、第四和第五种服务属性的区隔值，第29号区块和第30块在第一个和第二种服务属性上的区隔值不同，在第一种服务属性上，第29号区块的区隔值“1”大于第30号区块，因此，在第一种服务属性上，第29号区块上的所有服务优于第30号区块服务，同样的，在第二种服务属性上，第29号区块的服务差于第30号区块的服务。

则在则步骤S3)中，每个并行节点执行区块支配算法而对并行节点内部的候选服务进行筛选而获得局部Skyline服务的方法包括：

依次进行N次筛选，筛选次数N等于区块划分数量，最终经N次筛选得到的候选服务为局部Skyline服务；例如，若每个并行节点内部的区块划分数量为31，则需进行31次筛选，下一次筛选在前一次筛选结束后进行；

每次筛选均先选定一个区块作为代表区块，每次筛选所选定的代表区块不同；

每次筛选的过程为：先筛选出代表区块中的Skyline服务，再将将区块编号小于代表区块的其他区块中的候选服务分别与代表区块中的Skyline服务进行比较以获取两者之间的支配关系，然后删除区块编号小于代表区块的其他区块中被代表区块中的Skyline服务所支配的候选服务；

其中，每个区块均对应一个区块编号，每次筛选时，只需将区块编号小于代表区块的区块和代表区块中的Skyline服务进行比较即可，可有效提升计算效率。

在每次筛选的过程中，若其他区块中的候选服务的一个服务属性的区隔值小于代表区块中的Skyline服务的相应服务属性的区隔值，则该服务属性不再参与比较，此时只需对其他服务属性的QoS值进行比较即可；下面举例说明上述区块支配算法的筛选过程:若候选服务具有5种服务质量评价标准，也即具有5种服务属性，分别为时间、费用、声誉、成功率和有效性，首先通过区块划分方法划分出2

上述区块支配算法，通过服务属性区隔值来划分区块，通过服务属性区隔值的比较可快速确定来自不同区块的服务属性的优劣，从而免除处于劣势服务属性的比较，保证区隔值高的服务不会被区隔值低的服务支配，相较于现有方法中“确定服务支配关系时，必须考虑所有的服务属性”的计算方式，大大简化了来自不同区块的候选服务的支配关系的计算，可以避免候选服务间大量不必要的计算，降低了计算复杂度，从而提高了整体候选服务支配关系的计算速度，提高了计算效率。

在其中一个实施方式中：若不同任务之间存在QoS约束，则步骤S6)中利用柔性Skyline服务修正算法对QoS约束对QoS约束所涉及任务进行处理的方法包括：将要利用柔性Skyline服务修正算法进行处理的任务定义为待判任务，将与待判任务存在QoS约束的其他任务均定义为关联任务，获得每个所述关联任务中全局Skyline服务的QoS值的极限值，并对所有关联任务的QoS值的极限值进行聚合计算得到关联值，将待判任务中每个全局Skyline服务的QoS值均与所述关联值进行聚合计算得到判断值，对于判断值不能满足QoS约束的待判任务中的相应全局Skyline服务进行删除。

例如：存在任务序列t23→t24→t25，一个QoS约束描述如下：在任务t23开始执行之后，抽象任务t25要在12h时间内执行完。假设任务t23和任务t24的所有Skyline服务的最短时间分别为3小时和4小时；为了满足QoS约束，针对任务t25中执行时间大于5h的Skyline服务则不可能组成可行的执行计划，则可删除任务t25中执行时间大于5h的Skyline服务。具体的，将任务t25定义为待判任务，任务t23和任务t24均为关联任务，任务t23的QoS值的极限值为3，任务t24的QoS值的极限值为4，求和得到关联值为3+4＝7,然后将能够执行任务t25的所有全局Skyline服务的QoS值分别与关联值“7”进行求和得到判断值，比如，一个将能够执行任务t25的全局Skyline服务为A,服务A的QoS值为6，则判断值为6+7＝13,，该判断值13＞12，也即判断值大于QoS约束的“12小时”，因此，服务A不可能组成可行的执行计划,则将服务A从能够执行任务t25的服务中删除。

当不同任务之间存在QoS约束时，通过上述柔性Skyline服务修正算法可对QoS约束中任一任务的所述全局Skyline服务进行进一步裁剪，以裁减掉不可能组成最佳的执行计划一些服务。

在其中一个实施方式中：若全局Skyline服务存在属性依赖约束，则步骤S6)中利用柔性Skyline服务修正算法对属性依赖约束所涉及的任务进行处理的方法包括：定义与全局Skyline服务存在属性依赖约束的非Skyline服务为待处理服务，判断待处理服务在执行属性依赖约束后是否能够在所属任务中成为非支配服务，若判断为是，则在待处理服务所属任务中重新添加待处理服务，否则，不作处理。

例如：服务s22_1和s24_3之间存在属性依赖约束，属性依赖约束描述如下：如果同时选择服务s22_1和s24_3，则可获得$2的折扣。假设s22_1是一个成本为$7的非Skyline服务。根据上述约束，如果它和s24_3均被选中，则费用降低为$5。若s22_1执行属性依赖约束后，也即得到了折扣变为费用为$5时，也即QoS值更新为“5”后，s22_1不能在其所属任务t22中成为Skyline服务(非支配服务)，则它不可能出现在最佳执行计划中，否则，则表明当服务s22_1属性优化后将成为skyline服务，即可能出现在最佳执行计划中，因此，我们需将服务s22_1添加到其所属任务t22中，并最终作为柔性Skyline服务输出。

在其中一个实施方式中：若全局Skyline服务存在服务依赖约束，则步骤S7)中利用柔性Skyline服务修正算法对服务依赖约束所涉及的任务进行处理的方法包括：将要利用柔性Skyline服务修正算法进行处理的任务定义为待判任务，将与待判任务中的全局Skyline服务满足服务依赖约束的候选服务均定义为前件依赖服务；

若待判任务中的全局Skyline服务唯一，则判断前件依赖服务是否都存在于其他任务(待判任务以外的任务)的全局Skyline服务中，若判断为是，则表明前件依赖服务均为非支配服务，可以被选中，此时不需要作处理，若判断为否，则表明前件依赖服务不全是非支配服务，不能同时选中，则需要在在前件依赖服务所属任务中添加上述前件依赖服务，并在待判任务中添加第一次优服务，以便于服务依赖约束的所有全局Skyline服务能够同时选中组成可执行计划；

若待判任务中的全局Skyline服务不唯一，则不作处理。

其中，第一次优服务与前件依赖服务之间不存在服务依赖约束，且在待判任务中不考虑其内部之前存在的唯一的全局Skyline服务时能成为非支配服务。

例如：一个服务依赖约束描述如下：只有当服务s14_3和s15_5都被选择时，服务s18_2才能被选择。这里定义服务s18_2所属任务t18为待判任务，服务s14_3和s15_5均为前件依赖服务。假设服务s18_2是待判任务t18中唯一的非支配服务(Skyline服务)，服务s14_3和s15_5不全是非支配服务(Skyline服务)，那么服务s14_3和s15_5不能被同时选中，此时s18_2、s14_3和s15_5就不能同时选择，不可能产生可行的执行计划。为了制定出可行的执行计划，首先，在待判任务t18中添加次优服务，所谓次优服务为那些与前件依赖服务不存在服务依赖约束且在待判任务t18中不考虑服务s18_2时能成为非支配服务(Skyline服务)的服务，此处称之为“第一次优服务”，这样“第一次优服务”就可以与任务t14和t15中现有的Skyline服务相结合，制定可行的执行计划；其次，将前件依赖服务s14_3和s15_5分别添加到其所属任务t14和t15中，这样它们就可以与服务s18_2相结合，制定一个可行的执行计划。

在其中一个实施方式中：若全局Skyline服务存在服务冲突约束，则步骤S6)中利用柔性Skyline服务修正算法对服务冲突约束所涉及的任务进行处理的方法包括：将要利用柔性Skyline服务修正算法进行处理的任务定义为待判任务，将与待判任务中的全局Skyline服务满足服务冲突约束的候选服务均定义为前件冲突服务，若待判任务中的全局Skyline服务唯一，则判断前件冲突服务是否“存在于待判任务以外的其他任务的全局Skyline服务中且前件冲突服务在所属任务中为唯一的全局Skyline服务”，若判断为是，表明前件冲突服务为所属于任务的唯一非支配服务，由于组成执行计划时只能选中该前件冲突服务，但此时与前件冲突服务存在服务冲突约束的待判任务中的相应服务就无法选中，则此时需要在待判任务中增加第二次优服务且在前件冲突服务所属任务中添加第三次优服务，以便于组成可执行计划，判断为否，表明前件冲突服务不是非支配服务或不是唯一非支配服务，因此在组成执行计划时可不选中该前件冲突服务，那么此时与前件冲突服务存在服务冲突约束的待判任务中的相应服务就可以选中，此时就不需要作处理；

其中，第二次优服务与前件冲突服务之间不存在服务冲突约束，且在待判任务中不考虑其内部之前存在的唯一的全局Skyline服务时能成为非支配服务；

第三次优服务与待判任务中的全局Skyline服务之间不存在服务冲突约束，且在前件冲突服务所属任务中不考虑该前件冲突服务时能成为非支配服务。

例如：一个服务冲突约束描述如下：由于技术不兼容，服务s23_5和s24_8不能被同时选择。定义服务s24_8所属任务t24为待判任务，服务s23_5为前件冲突服务。现假设前件冲突服务s23_5是任务t23唯一的非支配任务(Skyline服务)，服务s24_8是任务t24唯一的非支配任务(Skyline服务)，可以看出服务s23_5和s24_8是唯一的候选服务，但是他们由于技术不兼容不能组合在一起，所以不可能得到可行的执行计划。为了制定出可行的执行计划，可采用以下方式：在待判任务t24中添加第二次优服务且在前件冲突服务所属任务t23中添加第三次优服务，所谓第二次优服务为那些与前件冲突服务s23_5不存在服务冲突约束且在待判任务t24中不考虑服务s24_8时能成为非支配服务，也即，第二次优服务为次优于服务s24_8的服务；第三次优服务与待判任务t24中的服务s24_8之间不存在服务冲突约束，且在前件冲突服务所属任务t23中不考虑服务s23_5时能成为非支配服务，也即，第三次优服务为次优于服务s23_5的服务。这样“第二次优服务”就可以与服务s23_5相结合而制定出可行的执行计划；“第三次优服务”也可以与服务s24_8相结合而制定出可行的执行计划。

下面以一小规模算例来验证上述服务发现方法的有效性：

基于Docker和Spark构建了一个集群环境，该环境包括一个主节点和四个工作节点，每个工作节点运行一个执行器(并行节点)。硬件环境为配置8vCPUs和64GB内存的华为柔性云服务器。本方法的参数如下:锦标赛选择算法的规模k＝5，标记服务规模ps＝5％。所有算法基于Python编程实现。

如图2所示，本算例包含了两个服务流程，例如，Process1由9个抽象任务组成，分别标记为t11到t19。其中，除了t13和t17外，每个抽象任务都必须选择一个服务来具体执行。另一方面，云上存在着大量服务，它们能够以不同的服务质量完成特定抽象任务。例如，服务s11_1需要7h和$7来实现t11，而服务s11_2需要6h和$9。特别是由于业务偏好和技术的不兼容性，服务间存在各种约束关系，如：“由于技术不兼容，服务s23_5和s24_8不能被同时选择。”

目前各任务的候选服务个数依次为：668,762,376,421,542,679,823,334,256,623,678,456,579。即有668个候选服务可执行任务t11，762个候选服务可执行任务t12等。

每个候选服务的服务属性包括“时间，费用，声誉，成功率，有效性”这五种质量属性；

将每个任务的服务划分为四个部分，以构建RDD(弹性分布式数据集)，便于将划分后的每个部分置于一个执行器中进行并行执行。例如，由于任务t11存在668个服务，它们被分成四个部分，每个部分包含167个服务。由每个执行器均通过定义锦标赛选择算法的map函数对RDD进行处理，并行实现锦标赛选择算法的支配服务修剪。以其中一个执行器为例：每次随机抽取5个服务，并根据锦标赛选择规则选取多个较优服务作为标记服务；选取接近5％×167服务作为标记服务后，所有剩余的候选服务都与这8个标记服务进行比较，删除比标记服务差的候选服务，也即只要候选服务比任一个标记服务差，就将其删减掉，从而删减了52个服务；然后，汇集各执行器的结果，从而计算剩余的各候选服务的QoS值，并根据剩余的候选服务QoS取值计算各服务属性的边界值。例如，可执行任务t11的一个服务的{时间、成本、信誉、成功率和可用性}的QoS值为[9.5,6,0.95,0.95,0.95]，遍历各服务从而获得候选服务的服务属性的边界值，使得各执行器均根据获取的所述服务属性的边界值进行区块划分；

在每个执行器中运行区块支配算法，从而并行实现基于区块支配算法的Skyline服务发现。以其中一个执行器为例：由于服务采用5种服务质量属性评价标准，则将一个执行器中划分出2

然后，考虑到部分服务不能满足所提出的QoS约束、属性依赖约束、服务依赖约束或服务冲突等约束，从而进一步执行柔性Skyline服务修正算法，结果显示，执行柔性Skyline服务修正算法后，候选服务的数量从原来的57个全局Skyline服务减少为成48个柔性Skyline服务，其调整率为18.75％。所有任务对应的柔性Skyline服务的计算结果如表1所示。

表1柔性Skyline服务的计算结果

由表1可知，本实施例的服务发现方法中服务的删减数量普遍在80％以上，表明本实施例的服务质量感知的并行柔性Skyline服务发现方法能有效降低服务选择的难度。在这基础上，执行柔性Skyline服务修正算法后，柔性Skyline服务的调整率在0～30％之间，表明本专利提出的柔性Skyline服务修正算法能根据当前约束设置情况，更合理地筛选出潜在的优质服务。

下面以一大规模算例来验证上述服务发现方法的有效性：

将本实施例的服务质量感知的并行柔性Skyline服务发现方法记为PRSkyline方法，选择现有的并行BNL方法(PBNL)及并行区块删除法(PBE)这两种并行Skyline求解方法与本实施例的PRSkyline方法进行对比。

本实施例的PRSkyline方法参数设置如下:锦标赛选择算法的规模k＝5，标记服务规模ps＝5％。其他算法的参数按相关研究的建议进行了设置。考虑到计算时间具有随机性，我们运行20次，并基于求解结果及求解时间评估其效果。

(1)在不考虑QoS约束、属性依赖约束、服务依赖约束或服务冲突的情况下，将本实施例的PRSkyline方法与PBNL方法、PBE这两种Skyline服务发现方法进行比较：

考虑到Skyline服务发现方法的规模取决于抽象任务及候选服务数量。因此，构建了两组具有不同问题规模的实验来评估方法的性能。在第一组实验中，每个服务流程中抽象任务的数量依次从15到150，每个抽象任务的服务数量为5000。在第二组实验中，抽象任务的数量固定为100，每个抽象任务对应的候选服务的数量依次从1000到10000。第一组实验在不同抽象任务数量下的Skyline服务发现方法的计算时间和求解结果对比情况参阅图3-图4，第二组实验在不同候选服务数量下的Skyline服务发现方法的计算时间和求解结果对比情况参阅图5-图6；

由图3-图4可知，随着抽象任务数量的增加，Skyline服务发现方法的计算时间在增加。在每个实验中，本实施例的PRSkyline算法的计算时间最短。此外，针对每个实验，三种方法均能找到相同数量的Skyline服务，表明上述算法的计算都是正确的。

由图5-图6可知，候选服务数量越大，Skyline服务发现方法的计算时间越长。本实施例的PRSkyline算法用时最短。同样，在每个实验中，三种方法均能找到全部Skyline服务，表明上述算法的计算都是正确的。

综上可知，在不同问题规模下，上述三种算法均能找到全部Skyline服务。其中，本实施例的PRSkyline算法用时最短，在效率方面提高了24.49％到79.52％，其中，效率提高＝(对比算法的计算时间-我们算法的计算时间)/对比算法的计算时间。

(1)在考虑QoS约束、属性依赖约束、服务依赖约束或服务冲突的情况下，将本实施例的PRSkyline方法与PBNL方法、PBE这两种Skyline服务发现方法进行比较：

在第一组实验中，每个服务流程中抽象任务的数量依次从15到150，每个抽象任务的服务数量为5000。在第二组实验中，抽象任务的数量固定为100，每个抽象任务对应的候选服务的数量依次从1000到10000。其中，在各组实验中，QoS约束、属性依赖、服务依赖、服务冲突四种约束的个数为100。第一组实验中在不同抽象任务数量下的Skyline服务发现方法的计算时间和求解结果对比情况参阅图7-图8，第二组实验中在不同候选服务数量下的Skyline服务发现方法的计算时间和求解结果对比情况参阅图9-图10；

PRSkyline的计算时间由两部分组成：一部分是Skyline服务发现方法中锦标赛选择算法和区块支配算法的计算总时间，在图7和图9中用PRSkyline_S表示；另一部分是柔性Skyline服务修正算法的计算时间，在图7和图9中用PRSkyline_SS表示。

如图7-图8所示，随着抽象任务数量的增加，Skyline服务发现方法的求解时间增加。在每个实验中，本实施例的PRSkyline方法的计算时间最短。此外，可以看出，在包含约束的情况下，柔性Skyline服务的数量与Skyline服务数量是不一样的，这表明相较于PBNL和PBE方法，采用我们的PRSkyline算法能够精确筛选出合适的候选服务，而采用PBNL和PBE方法将存在多删优质服务的问题。

如图9-图10所示，随着候选服务数量的增加，Skyline服务发现问题的计算时间增加，本实施例的PRSkyline算法用时最短。同样，在包含约束的情况下，本实施例的PRSkyline算法能够更好地筛选出合适的候选服务。

综上可知，在上述包含约束的实验中，本实施例的PRSkyline算法用时最短，在效率方面提高了20.36％到79.56％。且能够更加精确地筛选出合适的候选服务，相对于现有的Skyline服务发现方法相比，柔性Skyline服务的调整率为2.59％到21.43％。

综上，本实施例的服务质量感知的并行柔性Skyline服务发现方法，通过锦标赛选择算法来进行一次筛选修剪，可避免大量非支配服务间的成对比较，提高了计算求解效率，再通过区块支配算法来进行二次筛选修剪，可根据区块支配关系删减被支配区块及简化来自不同区块间的服务之间的两两比较，进一步提高了求解效率；再次，针对服务间可能存在QoS约束、属性依赖约束、服务依赖约束或服务冲突的情况，提出柔性Skyline服务修正算法，避免了多删或少删部分较好服务的现象，提高了服务选择的精度，利于准确、高效地过滤出优质候选服务；本实施例的服务质量感知的并行柔性Skyline服务发现方法对于存于或不存在第一约束的服务筛选均适用，适用范围较广。

本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

显然，上述实施例仅仅是为清楚地说明所作的举例，并非对实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式变化或变动。这里无需也无法对所有的实施方式予以穷举。而由此所引申出的显而易见的变化或变动仍处于本发明创造的保护范围之中。