与文献[13-19]类似，本文仅考虑工作流已知的服务组合问题，且工作流中每个活动的候选服务已知。工作流由常见的4种组合模式即顺序(SEQ)、选择(XOR)、并发(AND)及循环(LOOP)进行有限次迭代而成。为方便表述，引入虚拟活动的概念来描述工作流。

定义1  虚拟活动(VA)：一个VA可由一个三元组(CP，AL，K)描述。其中CP表示工作流模式，分别为SEQ、XOR、AND或LOOP；AL= < a₁, a₂, …, a_n > 表示一个有序列表，其中a_i(i = 1, 2, …, n)表示一个活动或者VA；K仅当CP为LOOP时有效(无效时K=-1)，表示AL中元素的循环次数。

对于文献[13]给出的工作流(图 1)，可以由内到外构成如下VA序列，用以描述该工作流，其中VA₅代表整个工作流。

图  1  一个工作流例子

VA₁(SEQ, < A₂, A₃, A₄ > , -1)

VA₂(XOR, < A₆, A₇, A₈ > , -1)

VA₃(SEQ, < A₅, VA₂, A₉ > , -1)

VA₄(AND, < VA₁, VA₃ > , -1)

VA₅(SEQ, < A₁, VA₄, A₁₀ > , -1)

不难验证，对于一个包含n个活动的工作流，可由不超过n个VA组成的序列描述。

时序约束可分为3类：施加于整个工作流全局的时序约束、施加于由多个活动构成的某种组合模式的时序约束和施加于单个活动的本地时序约束。对于前两类，可以用针对VA的时序约束描述；对于第三类，可以用针对活动的时序约束描述。以图 1所示工作流为例，可用tc(VA₅)≤12表示整个工作流的完成时间不超过12个单位，tc(VA₁)≤4表示完成由活动A₂、A₃、A₄构成的顺序模式的时间不超过4个单位，tc(A₃)表示应在1个时间单元内完成活动A₃。

一个包含n个活动(记为：A₁, A₂, …, A_n)的工作流，活动A_i拥有m_i个候选服务(第j个候选服务记为s_ij，对应的完成时间记为s_ij.pt，1≤j≤m_i)，用于描述该工作流的VA序列有u个(记为VA₁, VA₂, …, VA_u，u≤n)。用户对于该工作流的时序约束，可以施加到某些VA或者某些活动之上。时序服务组合问题可定义为：当满足用户时序约束时，使得其某些QoS最优化(例如：执行价格最低)。

用户时序约束分解的目标是寻找每个活动应该满足的时序上限，记为ULT(A_i)，i = 1, 2, …, n。当每个活动应该满足的时序上限确定时，任何一个VA应该满足的时序上限可由算法UtterLimit(VA)计算所得。为便于描述，活动A_i被看作一个VA(NONE, < A_i > , -1)。该算法在最坏情况下，需要递归遍历每个VA和活动，其时间复杂度为O(n)。

算法UtterLimit(VA)

输入：虚拟任务VA

输出：VA应满足的时序上限

If (VA.CP == NONE) {

  获取VA.AL中的元素A_i;

  Return   ULT(A_i); }

Else if (VA.CP== SEQ) {

  Set value = 0; //初始化VA的时序上限

  For each element in VA.AL

    value += UtterLimit (element);

  Return value; }

Else if (VA.CP == XOR) {

  Set value = +∞;

  For each element in VA.AL {

    temp = UtterLimit (element);

    If (temp < value)

      value = temp; }

  Return value; }

Else if (VA.CP == AND) {

  Set value = 0;

  For each element in VA.AL {

    temp = UtterLimit (element);

    If (temp > value)

      value = temp; }

  Return value; }

Else if (VA.CP == LOOP) {

  Set value = 0;

  For each element in VA.AL

    value += UtterLimit (element);

  Return value * VA.K; }

全局QoS约束分解策略是研究QoS感知的Web服务组合的重要方法。现有QoS约束分解模型^{[13, 20-26]}可分为3类：依据经验公式或规则建立的分解模型^[20-21]，其优点是易于实现，但它不能保障全局QoS约束，也不能保证不丢失可行组合方案；以保障全局QoS约束建立的分解模型^{[13, 22-25]}，它在用户约束强度较强时，容易丢失可行组合方案；保障以不丢失可行组合方案建立的分解模型^[26]，其目的是过滤不可行的候选服务，在用户约束强度较弱时过滤效果较差，也不能保障全局约束。由此可见，用户约束强度会影响QoS约束分解的效果。

用RA(VA)描述VA涉及到的活动的集合：

若为RA(VA)中的每个活动选择一个候选服务，其执行时间为对应的活动的所有候选服务的平均执行时间，由这些服务组合成的执行方案的平均执行时间称为VA的平均执行时间，记为APT(VA)。设用户对VA的时序约束为${\rm{tc}}({\rm{VA}}) \leqslant \tau ({\rm{VA}})$，用CI(VA)表示用户对VA的时序约束强度：

构建CIA-TCD模型的基本思想是在TCD模型的基础上引入松弛因子。当约束强度较弱时，取松弛因子为0以保障全局约束；当约束强度较强时，松弛因子取一个大于0的合适值，以保留一定数量的组合方案和降低丢失可行组合方案的概率。

CIA-TCD模型可描述如下：

目标：

约束条件：

式中，#{}表示集合中元素的个数；$\tau $(A_u)、$\tau $(VA_v)(1≤u≤n，1≤v≤n)分别为用户对各个活动、VA的时序约束(若无约束，设为$ + \infty $)；min(A_u.pt)、max(A_u.pt) (1≤u≤n)分别表示A_u的候选服务的执行时间的最小值与最大值；${\lambda _v}$(1≤v≤n)表示VA_v的时序约束所需引入的松弛因子；ULT(A_u)(1≤u≤n)为模型变量，表示A_u的时序约束上限。式(3)表明CIA-TCD模型的优化目标为最大化剩余组合方案的个数。

若能确定CIA-TCD模型中${\lambda _v}$(1≤v≤k)的值，该模型可以采用文献[13]中给出的贪心算法求解。${\lambda _v}$的取值主要与RA(VA_v)中活动个数(记为|RA(VA_v)|)和CI(VA_v)相关，可采用模糊推理规则来实现${\lambda _v}$的自适应调节。图 2a、图 2b、图 2c分别描述了|RA(VA_v)|、CI(VA_v)和${\lambda _v}$的隶属函数。采用表 1所示的推理规则，可得${\lambda _v}$的投影曲面如图 3所示。

图  2  隶属度函数

图  3  模糊规则的曲面投影

其中|RA(VA_v)|和CI(VA_v)的模糊子集均为{S, M, L}；${\lambda _v}$则划分为6个等级，从小到大依次记为S₁, S₂, …, S₆。

本文采用CIA-TCD模型和文献[13]中的TCD模型找到可行组合方案的概率和剩余组合方案个数进行对比，以及仅在CIA-TCD模型下找到可行组合方案的概率随约束个数变化的仿真实验。实验与文献[13]类似，考虑了3种规模的服务组合问题：G1(活动个数100，每个活动拥有的候选服务个数100)，G2(活动个数100，每个活动拥有的候选服务个数200)，G3(活动个数200，每个活动拥有的候选服务个数100)。工作流根据活动个数而随机生成，其中AND、XOR及SEQ模式的比例为1:1:2。以QWS数据集^[27-28]中的响应时间模拟服务的执行时间。在求解模型所采用的贪心算法中，参数步长StepNumber取为50，参数测试次数TestTimes取值100，时序约束个数为活动个数的0.3倍。实验代码用java 7编写，运行环境是Intel(R)Core(TM) i5-2430M、2.50 GHz Intel Xeon双核处理器，4.0 GB内存及win7操作系统。

与TCD模型相比，本文提出的CIA-TCD模型由于引入了松弛因子，使得当时序约束较强时，仍能保留一定量的候选服务，因此在时序约束较强时，采用CIA-TCD模型应比TCD模型更可能找到可行组合方案。图 4给出G1和G2规模时，分别采用CIA-TCD及TCD模型时找到可行组合方案的概率随约束强度变化的情况(设定所有约束的约束强度相同，约束强度从-0.8以步长0.1增加到-0.1)。从图 4中可以发现：约束强度较强时(-0.7~-0.3之间)，采用CIA-TCD模型比TCD模型更可能找到可行组合方案；G2与G1相比，活动个数相同，候选服务个数增加一倍，在同等约束强度时，两种模型在G2时都比G1时更能找到可行组合方案，这在一定程度上表明松弛因子与候选服务个数关联不大。图 5对比了G1和G3规模时，两种模型找到可行组合方案的概率随约束强度变化的情况。该图同样表明：当约束强度较强时，CIA-TCD模型比TCD模型更可能找到可行组合方案。从图 5可以发现：对于G1和G3两种问题规模，两种模型找到可行方案的概率变化的约束强度区间基本一致(CIA-TCD模型为(-0.7, -0.4)，TCD模型为(-0.5, -0.1))，这表明松弛因子的选取对活动个数具有较强适应能力(G1与G3的区别在于活动个数不同)。

图  4  找到可行组合方案的概率对比(G1和G2)

图  5  找到可行组合方案的概率对比(G1和G3)

引入松弛因子的另一个目的是使得剩余组合方案(不一定是可行组合方案)个数保持在一定范围内。图 6给出了在G1、G2及G3规模时，采用CIA-TCD及TCD模型时，剩余组合方案个数随约束强度变化的情况(由于剩余组合方案个数很大，纵坐标为其采用科学计数法时的指数值)。在同样规模时，与TCD模型相比，CIA-TCD模型可以在更大约束强度区间上基本保持稳定(以G1为例，采用CIA-TCD时的稳定区间为[-0.7, -0.1]，而采用TCD时的区间为[-0.4, -0.1])。对于CIA-TCD模型，对比G1和G2时的情形可以发现，它们的变化区间一致，但由于G1时候选服务个数较少，剩余组合方案个数也较少，这表明若要更好的控制剩余组合方案个数，松弛因子的选取还应考虑候选服务个数的影响；对比G1和G3时的情况，活动个数较多时，稳定区间较窄，表明在同等约束强度时，活动个数越多(约束个数也越多，其值是活动个数的0.3倍)，越不容易找到可行组合方案。

图  6  剩余组合方案个数的指数随约束个数变化

图 7给出了在G1规模、CIA-TCD模型、约束个数从20以步长20递增到100时，找到可行方案的概率随约束强度变化的情况。可以看出：无论哪种约束个数，当约束强度小于等于-0.7时找不到可行组合方案，当约束强度大于等于-0.4时几乎总能找到可行组合方案，在区间(-0.7, -0.4)上，约束个数对可找到组合方案的概率有些影响，但影响不大，表明松弛因子的选取受约束个数的影响不大。

图  7  找到可行方案的概率随约束个数变化

应用于服务组合的时序约束分解模型对用户约束强度较为敏感，尤其是当用户约束强度较强时，保障全局约束的分解模型容易丢失本就不多的可行组合方案。通过在保障全局约束的时序约束分解模型中引入松弛因子建立的CIA-TCD模型，在约束强度较大时，仍然能够保留一定量的可行组合方案，从而明显提高找到可行组合方案的概率。在采用模糊推理自适应调节松弛因子的值时只关注了约束强度及任务个数的影响。而仿真实验结果表明候选服务个数、约束个数等对松弛因子的取值也有影响，这将是以后研究的一个方向。