一种实现多个性能指标要求同时满足的服务组合方法

摘要

一种实现多个性能指标要求同时满足的服务组合方法，包括下列操作步骤：（1）根据用户服务组合的功能性要求，构建服务组合实例序列集合；（2）按照设定的方法对服务组合实例序列进行拓扑转换；（3）对服务组合实例序列的性能参数进行计算；（4）按照设定的方法从服务组合实例序列集合中，筛选出同时满足用户服务组合的所有性能指标要求的一个优化的服务组合实例序列。本发明方法能高效地找到优化的服务组合实例序列，保证同时满足用户对组合服务在价格、可靠性、延时等服务性能指标的要求，提高了复杂服务的服务质量。

说明书

技术领域

本发明涉及一种实现多个性能指标要求同时满足的服务组合方法，属于信息技术领域， 特别是属于基于因特网的多媒体通信技术领域。

背景技术

随着信息技术的发展，尤其是因特网技术和电信技术的发展，越来越多的具有多媒体特 征的智能型业务涌现出来，这些智能型业务往往比单纯的语音通信业务或者短信业务要复杂 的多，所以又被称为复杂服务或组合服务。比如：一个用户使用手机中的导游软件游览城市， 当看到一处感兴趣的景点时将其拍下，并将自己感兴趣的问题录成录音与照片一并输入导游 软件。导游软件将图片和声音上传到服务器，服务器将照片和声音同时提取出关键词并查询 数据库相关内容，最后服务器根据用户的语言类别将景点相关说明转为相应的中文或英文声 音发送回用户的手机。组合服务一般由一些基本的服务组合而成，这些基本的服务被称为原 子服务。一个组合服务可以看成是一条由原子服务实例构成的服务链，在本发明中被统称为 “服务组合路径”或“服务组合实例序列”。在市场竞争的条件下，同一种原子服务实例可以 由不同的服务提供商提供，部署在不同的网络节点服务器上，具有不同的价格、可靠性、服 务延时等多个服务质量参数QoS性能指标。对于用户提出某一个的组合服务，实现这个具体 的组合服务的服务组合路径就有很多条，当组合服务变得复杂、原子服务实例可选择的范围 变大时，服务组合路径的条数会急剧膨胀。

考虑QoS的服务实例选择主要侧重于在同时满足用户的多个QoS性能指标要求的同时， 为用户的组合服务选择合适的原子服务实例。现有考虑QoS的服务实例选择机制又可以分为 针对多约束单指标满足的服务选择方案和针对多指标满足的服务选择方案。现有针对多指标 满足的服务选择方案一般将多个指标满足问题转化为多约束的单指标满足问题进行求解，这 个转化过程中，存在解空间转化的保真性太难，服务实例选取需要对解空间有先验知识等问 题，严重情况下会无法求出真实的优化解。如果将多指标满足的服务选择问题直接进行求解， 则计算复杂性和时间复杂性都很高，实际实施中很难实现。

在同时满足用户对组合服务的价格、可靠性以及服务延时等性能指标的要求下，如何从 数量巨大的服务组合路径中，高效率地选择出一条优化的“服务组合路径”或“服务组合实 例序列”，成为目前多媒体通信技术领域业务发展急需解决的一个技术难题。

发明内容

有鉴于此，本发明的目的是发明一种方法，实现在同时满足用户对组合服务的价格、可 靠性以及服务延时等性能指标的要求下，能够高效快速地找到优化的服务组合实例序列。

为了达到上述目的，本发明提出了一种实现多个性能指标要求同时满足的服务组合方法， 所述方法包括下列操作步骤：

（1）根据用户服务组合的功能性要求，从原子服务目录中选择满足用户服务组合功能 性要求的原子服务，构成实现所述用户服务组合功能性要求的原子服务集合；然后再从原子 服务目录中选择相应的原子服务实例，构建服务组合实例序列集合；

（2）按照设定的方法把所述的服务组合实例序列中含有的串行结构、并行结构、选择 结构和循环结构分别进行拓扑转换；

（3）对完成所述的拓扑转换的服务组合实例序列，进行服务组合实例序列性能参数的 计算，服务组合实例序列的性能参数包括价格参数、时延参数和可靠性参数；

（4）根据用户服务组合的性能指标要求，按照设定的方法从服务组合实例序列集合中， 筛选出同时满足用户服务组合的所有性能指标要求的一个优化的服务组合实例序列。

所述步骤2中把服务组合实例序列中含有的串行结构进行拓扑转换的具体内容是：把该 串行结构转换为具有等价性能参数QoS的一个聚合服务实例，其中所述的等价性能参数QoS 包括等价价格参数、等价时延参数和等价可靠性参数；

等价价格参数的计算方法是该值等于构成所述串行结构的原子服务实例的价格之和，具 体如下式：该计算式中表示所述的服务组合实例序列集合中第 d个服务组合实例序列中某个串行结构的等价价格参数，表示构成所述串行结构的第i 个原子服务的第ki个原子服务实例的价格，M表示所述串行结构由M个原子服务构成，其中 d、i、ki和M都是自然数；

等价时延参数的计算方法是该值等于构成所述串行结构的原子服务实例的时延之和，具 体如下式：该计算式中表示所述的服务组合实例序列集合中第 d个服务组合实例序列中某个串行结构的等价时延参数，表示构成所述串行结构的第i 个原子服务的第ki个原子服务实例的时延，M表示所述串行结构由M个原子服务构成，其中 d、i、ki和M都是自然数；

等价可靠性参数的计算方法是该值等于构成所述串行结构的原子服务实例的可靠性之 积，具体如下式：该计算式中表示所述的服务组合实例序列集 合中第d个服务组合实例序列中某个串行结构的等价可靠性参数，表示构成所述串行 结构的第i个原子服务的第ki个原子服务实例的可靠性，M表示所述串行结构由M个原子服 务构成，其中d、i、ki和M都是自然数。

所述步骤2中把服务组合实例序列中含有的并行结构进行拓扑转换的具体内容是：把该 并行结构转换为具有等价性能参数QoS的一个聚合服务实例，其中所述的等价性能参数QoS 包括等价价格参数、等价时延参数和等价可靠性参数；

等价价格参数的计算方法是该值等于构成所述并行结构的原子服务实例的价格之和，具 体如下式：该计算式中表示所述的服务组合实例序列集合中第 d个服务组合实例序列中某个并行结构的等价价格参数，表示构成所述并行结构的第i 个原子服务的第ki个原子服务实例的价格，M表示所述并行结构由M个原子服务构成，其中 d、i、ki和M都是自然数；

等价时延参数的计算方法是该值等于构成所述并行结构的原子服务实例中的那个最大 的时延，具体如下式：$D\left({\mathrm{SCP}}_d^{\mathrm{Par}}\right)=\max (D\left(S_1{I_k}_1\right),...,D\left(S_i{I_k}_i\right),...,D\left(S_M{I_k}_M\right)),$该计算式中表示 所述的服务组合实例序列集合中第d个服务组合实例序列中某个并行结构的等价时延参数， 表示构成所述并行结构的第i个原子服务的第ki个原子服务实例的时延，M表示所述 并行结构由M个原子服务构成，其中d、i、ki和M都是自然数，max()表示求最大值；

等价可靠性参数的计算方法是该值等于构成所述并行结构的原子服务实例的可靠性之 积，具体如下式：该计算式中表示所述的服务组合实例序列集 合中第d个服务组合实例序列中某个并行结构的等价可靠性参数，表示构成所述并行 结构的第i个原子服务的第ki个原子服务实例的可靠性，M表示所述并行结构由M个原子服 务构成，其中d、i、ki和M都是自然数。

所述步骤2中把服务组合实例序列中含有的选择结构进行拓扑转换的具体内容是：把该 选择结构转换为具有等价性能参数QoS的一个聚合服务实例，其中所述的等价性能参数QoS 包括等价价格参数、等价时延参数和等价可靠性参数；

等价价格参数的计算方法是该值等于构成所述选择结构的每个原子服务实例的价格与 该种原子服务被选中的概率之积的总和，具体如下式：该计算式 中表示所述的服务组合实例序列集合中第d个服务组合实例序列中某个选择结构的 等价价格参数，表示构成所述选择结构的第i个原子服务的第ki个原子服务实例的价 格，表示第i个原子服务被选中的概率，M表示所述选择结构由M个原子服务构成，其中 d、i、ki和M都是自然数；

等价时延参数的计算方法是该值等于构成所述选择结构的每个原子服务实例的时延与 该种原子服务被选中的概率之积的总和，具体如下式：该计算式 中表示所述的服务组合实例序列集合中第d个服务组合实例序列中某个选择结构的 等价时延参数，表示构成所述选择结构的第i个原子服务的第ki个原子服务实例的时 延，表示第i个原子服务被选中的概率，M表示所述选择结构由M个原子服务构成，其中 d、i、ki和M都是自然数；

等价可靠性参数的计算方法是该值等于构成所述选择结构的每个原子服务实例的可靠 性与该种原子服务被选中的概率之积的总和，具体如下式：该计 算式中表示所述的服务组合实例序列集合中第d个服务组合实例序列中某个选择结 构的等价可靠性参数，表示构成所述选择结构的第i个原子服务的第ki个原子服务实 例的可靠性，表示第i个原子服务被选中的概率，M表示所述选择结构由M个原子服务构 成，其中d、i、ki和M都是自然数。

所述步骤2中把服务组合实例序列中含有的循环结构进行拓扑转换的具体内容是：把该 循环结构转换为具有等价性能参数QoS的一个聚合服务实例，其中所述的等价性能参数QoS 包括等价价格参数、等价时延参数和等价可靠性参数；

等价价格参数的计算方法是该值等于构成所述循环结构的一个完整循环的原子服务实 例的价格之和与该循环结构循环次数的乘积，具体如下式：该计 算式中表示所述的服务组合实例序列集合中第d个服务组合实例序列中某个循环结 构的等价价格参数，表示构成所述循环结构的一个完整循环的第i个原子服务的第ki 个原子服务实例的价格，N_loop表示该循环结构的循环次数，M表示所述循环结构由M个原子 服务构成，其中d、i、ki和M都是自然数；

等价时延参数的计算方法是该值等于构成所述循环结构的一个完整循环的原子服务实 例的时延之和与该循环结构循环次数的乘积，具体如下式：该计 算式中表示所述的服务组合实例序列集合中第d个服务组合实例序列中循环串行结 构的等价时延参数，表示构成所述循环结构的一个完整循环的第i个原子服务的第ki 个原子服务实例的时延，N_loop表示该循环结构的循环次数，M表示所述循环结构由M个原子 服务构成，其中d、i、ki和M都是自然数；

等价可靠性参数的计算方法是该值等于构成所述循环结构的一个完整循环的原子服务 实例的可靠性之积，具体如下式：该计算式中表示所述的服 务组合实例序列集合中第d个服务组合实例序列中某个循环结构的等价可靠性参数，表示构成所述循环结构的一个完整循环的第i个原子服务的第ki个原子服务实例的可靠性， M表示所述循环结构由M个原子服务构成，其中d、i、ki和M都是自然数。

所述步骤4的具体内容是：使用优化方法从所述的服务组合实例序列集合中找到一个优 化的服务组合实例序列，使得该服务组合实例序列的性能参数同时满足用户服务组合的所有 性能指标要求，并且该服务组合实例序列的每个性能参数是所述的服务组合实例序列集合中 性能参数最优或次最优的；所述的服务组合实例序列的性能参数包括价格参数、时延参数和 可靠性参数。

所述步骤4具体包括如下操作步骤：

（400）对每个原子服务的原子服务实例从1开始用自然数进行编号，所有可能的服务组 合实例序列就构成一个解空间，该解空间的维数就是构成所述的实现用户服务组合功能性要 求的原子服务集合的大小，该解空间的每一个坐标轴代表一个原子服务，每一个坐标轴上的 坐标即原子服务实例的编号；

（401）起始阶段，选定一定数量的算子，随机初始化每个算子对应的服务组合实例序列；

（402）将每个算子起始阶段的局部最优解设为该算子当前的服务组合实例序列；

（403）从所有算子中，选取合适数量的局部最优解存入优化解候选集合，并要求在该优 化解候选集合中，不存在一个解支配另一个解；

（404）随机从所述的优化解候选集合中选取一个解作为所有算子的全局最优解；

（405）迭代阶段，按照设定的方法对每个算子的局部最优解进行更新，获得该算子当前 服务组合实例序列；

（406）对每一个算子，判断当前服务组合实例序列是否支配局部最优解，如果支配则更 新该算子的局部最优解为当前服务组合实例序列，否则随机选择一个作为该算子的局部最优 解；

（407）从所有算子的局部最优解和优化解候选集合中选出一定数量的解作为新的优化 解候选集合，并要求在该新的优化解候选集合中，不存在一个解支配另一个解，并且要求这 些解在解空间中分布尽量稀疏；

（408）从所述新的优化解候选集合中随机选出一个解做为全局最优解；

（409）如果迭代次数未超过最大设定迭代次数，则跳到步骤（405）重新开始迭代；否 则，把当前的全局最优解选定为最终优化的服务组合实例序列，操作结束；

所述的解A支配解B的意思是指解A的所有性能参数均优于解B；

所述步骤405的具体内容是：

在第t+1次迭代时，按照如下计算式更新第b个算子的当前服务组合实例序列的第i个 原子服务实例的编号：

即：依照概率选择依照概率p₂=1-p₁，选择 上式中表示在第t+1次迭代时第b个算子的当前服务组合实例序列的第i 个原子服务实例的编号；表示在第t次迭代时第b个算子的当前服务组合实例序列的第i 个原子服务实例的编号；表示在第t+1次迭代时第b个算子的当前服务组合实例序列的第 i个原子服务实例编号的改变量；运算符表示对该运算符内的数值进行上取整运算；运算 符表示对该运算符内的数值进行下取整运算；b是自然数；

其中，在第t+1次迭代时，按照下式计算第b个算子的当前服务组合实例序列的第i个 原子服务实例编号的改变量

$v_{\mathrm{bi}}^{t+1}={\omega }^t{v}_{\mathrm{bi}}^t+c_1^t{\xi }^t(p_{\mathrm{bi}}^t-x_{\mathrm{bi}}^t)+c_2^t{\eta }^t(p_{\mathrm{gi}}^t-x_{\mathrm{bi}}^t)$

上式中，表示在第t次迭代时第b个算子的局部最优解的第i个原子服务实例的编号，表 示在第t次迭代时全局最优解的第i个原子服务实例的编号，表示在第t次迭代时第b个算 子的当前服务组合实例序列的第i个原子服务实例编号的改变量；ω^t表示在第t次迭代时系统 的时变迭代权重；ξ^t表示第t次迭代时在0和1之间均匀分布的一个随机值；η^t表示第t次迭 代时在0和1之间均匀分布的一个随机值；表示在第t次迭代时系统的时变学习因子，表 示在第t次迭代时系统的时变学习因子；

其中，在第t次迭代时，按照下式计算系统的时变迭代权重ω^t：

ω^t=ω_max-(ω_max-ω_min)×t/T_max

上式中，ω_max表示系统的最大迭代权重，ω_min表示系统的最小迭代权重，T_max表示系统的最大 迭代次数，t表示系统的当前迭代次数；

其中，在第t次迭代时，按照下式计算系统的时变学习因子

$c_1^t=(c_{1f}-c_{1i})\times t/T_{\max }+c_{1i}$

上式中，c_1i和c_1f分别表示系统的时变学习因子的初始值和终止值；

其中，在第t次迭代时，按照下式计算系统的时变学习因子

$c_2^t=(c_{2f}-c_{2i})\times t/T_{\max }+c_{2i}$

上式中，c_2i和c_2f分别表示系统的时变学习因子的初始值和终止值。

所述的算子是指具有计算能力和存贮能力的计算单元，该计算单元能够按照设定的计算 方法对计算对象即服务组合实例序列进行计算。

所述步骤（407）中要求被选入优化解候选集合的解在解空间中分布尽量稀疏的计算方法 是：作为一个解的服务组合实例序列在解空间中的稀疏性是通过计算该服务组合实例序列的 性能参数向量与其他所有服务组合实例序列的性能参数向量之间的拥挤程度，也即曼哈顿距 离之和来进行计算的，曼哈顿距离之和越小，则拥挤程度越小，对应稀疏性越大。

本发明的有益效果在于能高效地找到优化的服务组合实例序列，保证同时满足用户对组 合服务在价格、可靠性、延时等服务性能指标的要求，提高复杂服务的服务质量。

附图说明

图1是本发明提出的一种实现多个性能指标要求同时满足的服务组合方法的流程图。

图2是本发明的实施例中服务组合实例序列中的串行结构进行拓扑转换的示意图。

图3是本发明的实施例中服务组合实例序列中的并行结构进行拓扑转换的示意图。

图4是本发明的实施例中服务组合实例序列中的选择结构进行拓扑转换的示意图。

图5是本发明的实施例中服务组合实例序列中的循环结构进行拓扑转换的示意图。

图6是本发明的实施例中手机导游组合服务例子的示意图。

图7是本发明的实施例中手机导游组合服务例子中并行结构拓扑转换示意图。

图8是本发明的实施例中手机导游组合服务例子中选择结构拓扑转换示意图。

图9是本发明的实施例中手机导游组合服务例子中服务组合实例序列筛选示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面结合附图对本发明作进一步的详细 描述。

参见图1，介绍本发明提出的一种实现多个性能指标要求同时满足的服务组合方法，所 述方法包括下列操作步骤：

（1）根据用户服务组合的功能性要求，从原子服务目录中选择满足用户服务组合功能 性要求的原子服务，构成实现所述用户服务组合功能性要求的原子服务集合；然后再从原子 服务目录中选择相应的原子服务实例，构建服务组合实例序列集合；

（2）按照设定的方法把所述的服务组合实例序列中含有的串行结构、并行结构、选择 结构和循环结构分别进行拓扑转换；

（3）对完成所述的拓扑转换的服务组合实例序列，进行服务组合实例序列性能参数的 计算，服务组合实例序列的性能参数包括价格参数、时延参数和可靠性参数；

（4）根据用户服务组合的性能指标要求，按照设定的方法从服务组合实例序列集合中， 筛选出同时满足用户服务组合的所有性能指标要求的一个优化的服务组合实例序列。

参见图2，所述步骤2中把服务组合实例序列中含有的串行结构进行拓扑转换的具体内 容是：把该串行结构转换为具有等价性能参数QoS的一个聚合服务实例ASS_Seq，其中所述的 等价性能参数QoS包括等价价格参数、等价时延参数和等价可靠性参数；

等价价格参数的计算方法是该值等于构成所述串行结构的原子服务实例的价格之和，具 体如下式：该计算式中表示所述的服务组合实例序列集合中第 d个服务组合实例序列中某个串行结构的等价价格参数，表示构成所述串行结构的第i 个原子服务的第ki个原子服务实例的价格，M表示所述串行结构由M个原子服务构成，其中 d、i、ki和M都是自然数；

等价时延参数的计算方法是该值等于构成所述串行结构的原子服务实例的时延之和，具 体如下式：该计算式中表示所述的服务组合实例序列集合中第 d个服务组合实例序列中某个串行结构的等价时延参数，表示构成所述串行结构的第i 个原子服务的第ki个原子服务实例的时延，M表示所述串行结构由M个原子服务构成，其中 d、i、ki和M都是自然数；

等价可靠性参数的计算方法是该值等于构成所述串行结构的原子服务实例的可靠性之 积，具体如下式：该计算式中表示所述的服务组合实例序列集 合中第d个服务组合实例序列中某个串行结构的等价可靠性参数，表示构成所述串行 结构的第i个原子服务的第ki个原子服务实例的可靠性，M表示所述串行结构由M个原子服 务构成，其中d、i、ki和M都是自然数。

参见图3，所述步骤2中把服务组合实例序列中含有的并行结构进行拓扑转换的具体内 容是：把该并行结构转换为具有等价性能参数QoS的一个聚合服务实例ASS_Par，其中所述的 等价性能参数QoS包括等价价格参数、等价时延参数和等价可靠性参数；

等价价格参数的计算方法是该值等于构成所述并行结构的原子服务实例的价格之和，具 体如下式：该计算式中表示所述的服务组合实例序列集合中第 d个服务组合实例序列中某个并行结构的等价价格参数，表示构成所述并行结构的第i 个原子服务的第ki个原子服务实例的价格，M表示所述并行结构由M个原子服务构成，其中 d、i、ki和M都是自然数；

等价时延参数的计算方法是该值等于构成所述并行结构的原子服务实例中的那个最大 的时延，具体如下式：$D\left({\mathrm{SCP}}_d^{\mathrm{Par}}\right)=\max (D\left(S_1{I_k}_1\right),...,D\left(S_i{I_k}_i\right),...,D\left(S_M{I_k}_M\right)),$该计算式中表示 所述的服务组合实例序列集合中第d个服务组合实例序列中某个并行结构的等价时延参数， 表示构成所述并行结构的第i个原子服务的第ki个原子服务实例的时延，M表示所述 并行结构由M个原子服务构成，其中d、i、ki和M都是自然数，max()表示求最大值；

等价可靠性参数的计算方法是该值等于构成所述并行结构的原子服务实例的可靠性之 积，具体如下式：该计算式中表示所述的服务组合实例序列集 合中第d个服务组合实例序列中某个并行结构的等价可靠性参数，表示构成所述并行 结构的第i个原子服务的第ki个原子服务实例的可靠性，M表示所述并行结构由M个原子服 务构成，其中d、i、ki和M都是自然数。

参见图4，所述步骤2中把服务组合实例序列中含有的选择结构进行拓扑转换的具体内 容是：把该选择结构转换为具有等价性能参数QoS的一个聚合服务实例ASS_Sel，其中所述的等 价性能参数QoS包括等价价格参数、等价时延参数和等价可靠性参数；

等价价格参数的计算方法是该值等于构成所述选择结构的每个原子服务实例的价格与 该种原子服务被选中的概率之积的总和，具体如下式：该计算式 中表示所述的服务组合实例序列集合中第d个服务组合实例序列中某个选择结构的 等价价格参数，表示构成所述选择结构的第i个原子服务的第ki个原子服务实例的价 格，表示第i个原子服务被选中的概率，M表示所述选择结构由M个原子服务构成，其中 d、i、ki和M都是自然数；

等价时延参数的计算方法是该值等于构成所述选择结构的每个原子服务实例的时延与 该种原子服务被选中的概率之积的总和，具体如下式：该计算式 中表示所述的服务组合实例序列集合中第d个服务组合实例序列中某个选择结构的 等价时延参数，表示构成所述选择结构的第i个原子服务的第ki个原子服务实例的时 延，表示第i个原子服务被选中的概率，M表示所述选择结构由M个原子服务构成，其中 d、i、ki和M都是自然数；

等价可靠性参数的计算方法是该值等于构成所述选择结构的每个原子服务实例的可靠 性与该种原子服务被选中的概率之积的总和，具体如下式：该计 算式中表示所述的服务组合实例序列集合中第d个服务组合实例序列中某个选择结 构的等价可靠性参数，表示构成所述选择结构的第i个原子服务的第ki个原子服务实 例的可靠性，表示第i个原子服务被选中的概率，M表示所述选择结构由M个原子服务构 成，其中d、i、ki和M都是自然数。

参见图5，所述步骤2中把服务组合实例序列中含有的循环结构进行拓扑转换的具体内 容是：把该循环结构转换为具有等价性能参数QoS的一个聚合服务实例ASS_Loop，其中所述的 等价性能参数QoS包括等价价格参数、等价时延参数和等价可靠性参数；

等价价格参数的计算方法是该值等于构成所述循环结构的一个完整循环的原子服务实 例的价格之和与该循环结构循环次数的乘积，具体如下式：该计 算式中表示所述的服务组合实例序列集合中第d个服务组合实例序列中某个循环结 构的等价价格参数，表示构成所述循环结构的一个完整循环的第i个原子服务的第ki 个原子服务实例的价格，N_loop表示该循环结构的循环次数，M表示所述循环结构由M个原子 服务构成，其中d、i、ki和M都是自然数；

等价时延参数的计算方法是该值等于构成所述循环结构的一个完整循环的原子服务实 例的时延之和与该循环结构循环次数的乘积，具体如下式：该计 算式中表示所述的服务组合实例序列集合中第d个服务组合实例序列中循环串行结 构的等价时延参数，表示构成所述循环结构的一个完整循环的第i个原子服务的第ki 个原子服务实例的时延，N_loop表示该循环结构的循环次数，M表示所述循环结构由M个原子 服务构成，其中d、i、ki和M都是自然数；

等价可靠性参数的计算方法是该值等于构成所述循环结构的一个完整循环的原子服务 实例的可靠性之积，具体如下式：该计算式中表示所述的服 务组合实例序列集合中第d个服务组合实例序列中某个循环结构的等价可靠性参数，表示构成所述循环结构的一个完整循环的第i个原子服务的第ki个原子服务实例的可靠性， M表示所述循环结构由M个原子服务构成，其中d、i、ki和M都是自然数。

参见图6，一个手机导游组合服务的例子，首先根据用户服务组合的功能性要求，从原 子服务目录中选择图片提取S1、声音提取S2、内容检索S3、文本转中文语音S5、文本转英 文语音S4五个原子服务。每个原子服务都有一到多个具有相同功能不同QoS属性的原子服 务实例，如图片提取原子服务S1有S₁I₁和S₁I₂两个原子服务实例。随后，将服务组合实例序 列中含有的各种结构进行拓扑转换并进行性能参数计算，原子服务实例的QoS参数如表1所 示。

表1

服务实例 代价 时延 可靠性 S₁I₁1 5 0.95 S₁I₂2 6 0.99 S₂I₁3 3 0.98 S₃I₁2 4 0.97 S₃I₂3 6 0.96 S₃I₃1 4 0.95 S₄I₁1 5 0.99 S₄I₂1 5 0.98 S₄I₃3 6 0.97 S₅I₁2 2 0.99 S₅I₂2 4 0.98

原子服务S1和S2是并行结构，拓扑转换为聚合服务S12，如图7所示。实例S₁I₁、S₂I₁合成聚合服务实例S₁₂I₁，该服务实例的代价计算如：时延计算 如：$D_{S_{12}{I}_1}=D_{S_1{I}_1}+D_{S_2{I}_1}=5+3=8,$可靠性计算如：$R_{S_{12}{I}_1}=R_{S_1{I}_1}\times R_{S_2{I}_1}=0.95\times 0.98=0.93.$实例 S₁I₂、S₂I₁合成聚合服务实例S₁₂I₂，该服务实例的代价计算如：时延计算如下：可靠性计算如： $R_{S_{12}{I}_2}=R_{S_1{I}_2}\times R_{S_2{I}_1}=0.99\times 0.98=0.97.$

原子服务S4和S5是选择结构，拓扑转换为聚合服务S45，如图8所示。聚合服务的服 务实例集合为原有两原子服务的所有服务实例的集合，S₄₅I₁、S₄₅I₂、S₄₅I₃的QoS参数与S₄I₁、 S₄I₂、S₄I₃相同，S₄₅I₄、S₄₅I₅的QoS参数与S₅I₁、S₅I₂相同。这样，服务组合实例序列就被转 换为聚合的串行结构。

所述步骤4的具体内容是：使用优化方法从所述的服务组合实例序列集合中找到一个优 化的服务组合实例序列，使得该服务组合实例序列的性能参数同时满足用户服务组合的所有 性能指标要求，并且该服务组合实例序列的每个性能参数是所述的服务组合实例序列集合中 性能参数最优或次最优的；所述的服务组合实例序列的性能参数包括价格参数、时延参数和 可靠性参数。

所述步骤4具体包括如下操作步骤：

（400）对每个原子服务的原子服务实例从1开始用自然数进行编号，所有可能的服务组 合实例序列就构成一个解空间，该解空间的维数就是构成所述的实现用户服务组合功能性要 求的原子服务集合的大小，该解空间的每一个坐标轴代表一个原子服务，每一个坐标轴上的 坐标即原子服务实例的编号；

（401）起始阶段，选定一定数量的算子，随机初始化每个算子对应的服务组合实例序列；

（402）将每个算子起始阶段的局部最优解设为该算子当前的服务组合实例序列；

（403）从所有算子中，选取合适数量的局部最优解存入优化解候选集合，并要求在该优 化解候选集合中，不存在一个解支配另一个解；

（404）随机从所述的优化解候选集合中选取一个解作为所有算子的全局最优解；

（405）迭代阶段，按照设定的方法对每个算子对应的服务组合实例序列进行更新，获得 该算子当前服务组合实例序列；

（406）对每一个算子，判断当前服务组合实例序列是否支配局部最优解，如果支配则更 新该算子的局部最优解为当前服务组合实例序列，否则随机选择一个作为该算子的局部最优 解；

（407）从所有算子的局部最优解和优化解候选集合中选出一定数量的解作为新的优化 解候选集合，并要求在该新的优化解候选集合中，不存在一个解支配另一个解，并且要求这 些解在解空间中分布尽量稀疏；

（408）从所述新的优化解候选集合中随机选出一个解做为全局最优解；

（409）如果迭代次数未超过最大设定迭代次数，则跳到步骤（405）重新开始迭代；否 则，把当前的全局最优解选定为最终优化的服务组合实例序列，操作结束；

所述的解A支配解B的意思是指解A的所有性能参数均优于解B；

所述步骤405的具体内容是：

在第t+1次迭代时，按照如下计算式更新第b个算子的当前服务组合实例序列的第i个 原子服务实例的编号：

即：依照概率选择依照概率p₂=1-p₁，选择 上式中表示在第t+1次迭代时第b个算子的当前服务组合实例序列的第i 个原子服务实例的编号；表示在第t次迭代时第b个算子的当前服务组合实例序列的第i 个原子服务实例的编号；表示在第t+1次迭代时第b个算子的当前服务组合实例序列的第 i个原子服务实例编号的改变量；运算符表示对该运算符内的数值进行上取整运算，如 运算符表示对该运算符内的数值进行下取整运算，如b是自然数；

其中，在第t+1次迭代时，按照下式计算第b个算子的当前服务组合实例序列的第i个 原子服务实例编号的改变量

$v_{\mathrm{bi}}^{t+1}={\omega }^t{v}_{\mathrm{bi}}^t+c_1^t{\xi }^t(p_{\mathrm{bi}}^t-x_{\mathrm{bi}}^t)+c_2^t{\eta }^t(p_{\mathrm{gi}}^t-x_{\mathrm{bi}}^t)$

上式中，表示在第t次迭代时第b个算子的局部最优解的第i个原子服务实例的编号，表 示在第t次迭代时全局最优解的第i个原子服务实例的编号，表示在第t次迭代时第b个算 子的当前服务组合实例序列的第i个原子服务实例编号的改变量；ω^t表示在第t次迭代时系统 的时变迭代权重；ξ^t表示第t次迭代时在0和1之间均匀分布的一个随机值；η^t表示第t次迭 代时在0和1之间均匀分布的一个随机值；表示在第t次迭代时系统的时变学习因子，表 示在第t次迭代时系统的时变学习因子；

其中，在第t次迭代时，按照下式计算系统的时变迭代权重ω^t：

ω^t=ω_max-(ω_max-ω_min)×t/T_max

上式中，ω_max表示系统的最大迭代权重，ω_min表示系统的最小迭代权重，T_max表示系统的最大 迭代次数，t表示系统的当前迭代次数；

其中，在第t次迭代时，按照下式计算系统的时变学习因子：

$c_1^t=(c_{1f}-c_{1i})\times t/T_{\max }+c_{1i}$

上式中，c_1i和c_1f分别表示系统的时变学习因子的初始值和终止值；

其中，在第t次迭代时，按照下式计算系统的时变学习因子

$c_2^t=(c_{2f}-c_{2i})\times t/T_{\max }+c_{2i}$

上式中，c_2i和c_2f分别表示系统的时变学习因子的初始值和终止值。

所述的算子是指具有计算能力和存贮能力的计算单元，该计算单元能够按照设定的计算 方法对计算对象即服务组合实例序列进行计算。

所述步骤（407）中要求被选入优化解候选集合的解在解空间中分布尽量稀疏的计算方法 是：作为一个解的服务组合实例序列在解空间中的稀疏性是通过计算该服务组合实例序列的 性能参数向量与其他所有服务组合实例序列的性能参数向量之间的拥挤程度，也即曼哈顿距 离之和来进行计算的，曼哈顿距离之和越小，则拥挤程度越小，对应稀疏性越大。

参见图9，对于手机导游组合服务的例子，假设使用3个算子P1、P2、P3来搜索最优解， 每个算子有三个维数，分别对应服务S12、S3、S45。算法起始阶段随机初始化每个算子的服 务实例序列，如P1对应的服务组合实例序列是：S₁₂I₁、S₃I₃、S₄₅I₂，该服务组合实例序列的 性能参数向量为：

$\left(\begin{array}{c}O\left(P1\right)=(C_{P1},D_{P1},R_{P1})\\ =(C_{S_{12}{I}_1}+C_{S_3{I}_3}+C_{S_{45}{I}_2},D_{S_{12}{I}_1}+D_{S_3{I}_3}+D_{S_{45}{I}_2},R_{S_{12}{I}_1}\times R_{S_3{I}_3}\times R_{S_{45}{I}_2})\\ =(4+1+\mathrm{1,8}+4+\mathrm{5,0.93}\times 0.95\times 0.98)\\ =\left(\mathrm{6,17,0.87}\right)\end{array}\right)$

同理，P2对应的服务组合实例序列是：S₁₂I₂、S₃I₂、S₄₅I₄，该服务组合实例序列的性能参 数向量为：

$O\left(P2\right)=(C_{P2},D_{P2},R_{P2})$

$=(C_{S_{12}{I}_2}+C_{S_3{I}_2}+C_{S_{45}{I}_4},D_{S_{12}{I}_2}+D_{S_3{I}_2}+D_{S_{45}{I}_4},R_{S_{12}{I}_2}\times R_{S_3{I}_2}\times R_{S_{45}{I}_4})$

$=(5+3+\mathrm{2,9}+6+\mathrm{2,0.97}\times 0.96\times 0.99)$

$=\left(\mathrm{10,17,0.92}\right)$

P3对应的服务组合实例序列是：S₁₂I₂、S₃I₁、S₄₅I₁，该服务组合实例序列的性能参数向量 为：

$\left(\begin{array}{c}O\left(P3\right)=(C_{P3},D_{P3},R_{P3})\\ =(C_{S_{12}{I}_2}+C_{S_3{I}_1}+C_{S_{45}{I}_1},D_{S_{12}{I}_2}+D_{S_3{I}_1}+D_{S_{45}{I}_1},R_{S_{12}{I}_2}\times R_{S_3{I}_1}\times R_{S_{45}{I}_1})\\ =(5+2+\mathrm{1,9}+4+\mathrm{5,0.97}\times 0.97\times 0.99)\\ =\left(\mathrm{8,18,0.93}\right)\end{array}\right)$

这时每个算子的局部最优解为当前算子的服务组合实例序列，现有服务组合实例序列的 性能参数向量有三个：（6,17,0.87）、（10,17,0.92）、（8,18,0.93），这三个性能参数向量之间无 法比出优劣，都为非支配解。假设优化解候选集合容量为二，则从这三个性能参数向量中需 要选出两个对应的服务组合实例序列存入优化解候选集合，并要求这两个服务组合实例序列 在解空间中应尽量保持稀疏。具体计算如下：

（6,17,0.87）到其他两个性能参数向量的拥挤程度按照下式来计算：

(|6-10|+|17-17|+|0.87-0.92|)+(|6-8|+|17-18|+|0.87-0.93|)=7.11

同理，

（10,17,0.92）到其他两个性能参数向量的拥挤程度计算如下：

(|10-6|+|17-17|+|0.92-0.87|)+(|10-8|+|17-18|+|0.92-0.93|)=7.06

（8,18,0.93）到其他两个性能参数向量的拥挤程度计算如下：

(|8-6|+|18-17|+|0.93-0.87|)+(|8-10|+|18-17|+|0.93-0.92|)=6.07

所以，选择（8,18,0.93）、（10,17,0.92）两个拥挤程度最小也即稀疏性最大的性能参数向 量对应的服务组合实例序列S₁₂I₂、S₃I₁、S₄₅I₁和S₁₂I₂、S₃I₂、S₄₅I₄存入优化解候选集合，并从 其中随机选择一个作为全局最优解，如S₁₂I₂、S₃I₁、S₄₅I₁。

在第一次迭代阶段中，算子P1的改变量如下计算：

$\left(\begin{array}{c}{v}_1^2={\omega }^1{v}_1^1+c_1^1{\xi }^1(p_{b1}^1-x_1^1)+c_2^1{\eta }^1(p_{g1}^1-x_1^1)\\ =0.5\times \left(\mathrm{0.9,1.1,2}\right)+0.52\times 0.3\times (\left(\mathrm{1,3,2}\right)-\left(\mathrm{1,3,2}\right))+2.48\times 0.2\times (\left(\mathrm{2,1,1}\right)-\left(\mathrm{1,3,2}\right))\\ =(0.946,-0.\mathrm{442,0.504})\end{array}\right)$

上式中，ω¹=0.5，$v_1^1=\left(\mathrm{0.9,1.1,2}\right),$$c_1^1=0.52,$ξ¹=0.3，$p_{b1}^1=\left(\mathrm{1,3,2}\right),$$x_1^1=\left(\mathrm{1,3,2}\right),$$c_2^1=2.48,$η¹=0.2，$p_{g1}^1=\left(\mathrm{2,1,1}\right).$

算子P1的服务组合实例序列计算如下：

$x_1^2=x_1^1+v_1^2=\left(\mathrm{1,3,2}\right)+(0.946,-\mathrm{0.442,0.504})=\left(\mathrm{1.946,2.558,2.504}\right)$

由于服务组合实例序列为整数，所以本次迭代所得到的服务组合序列对应的 性能参数向量为O(P1)=(9,19,0.89)，与（6,17,0.87）互为非支配解，所以随机选择（9,19,0.89） 对应的作为本次迭代P1的局部最优解。同理可以求出P2、P3在本次迭代中对应 的服务组合实例序列，进而求出P2、P3的局部最优解。然后，将优化解候选集合考虑在内进 行全局最优解的求解，方法继续迭代直到达到最大迭代次数，输出最后状态的全局最优解。