服务网络的启发式定制方法

王忠杰，王少鹏，徐 飞

（哈尔滨工业大学 计算机科学与技术学院，黑龙江 哈尔滨 150001）

0 引言

服务组合［1－2］是利用小粒度Web服务组合形成大粒度服务，以满足客户个性化需求的有效手段，也是近年来服务计算领域的研究热点之一。虽然目前研究成果非常丰富，但多侧重于为单一需求构建组合方案，在应对大规模客户需求时存在成本有效性方面的不足。具体来说，当多请求抵达时，需要针对每个需求分别构造组合方案，忽略了需求间的相似性和由此导致的方案间可能存在的共享，需求满足的成本较高。

服务网络（Service Network，SN）［3］是应对该挑战的有效方法。SN采用类穷举机制将分散在互联网上的开放网络服务（Web service）和应用程序接口（Application Programming Interface，API）连接形成网络，彼此之间通过标准化互操作协议进行交互。与传统的服务组合方法相比，它不是根据特定需求构造的组合方案，而是根据可用服务之间的相关性／相似性以及历史需求体现出的共性特征，提前将可用服务组织在一起，构造出具有满足大规模需求能力的持久性基础设施。当新需求抵达时，只需对服务网络进行定制即可得到一个满足需求的子网络。该方式的优势为：用一套基础设施为同一领域内相似需求的客户提供持续服务，达到成本有效性，较好地支持服务的大规模个性化定制。

服务网络可以是自然形成的，也可由特定组织根据领域需求自行构建，在使用过程中不断进行扩展和调整，使其符合客户需求特征的变化趋势。本文关注的是服务网络的定制阶段：根据客户的个性化需求找到服务网络的最优定制方案。随着服务网络规模和复杂度的增加，定制的难度也会越来越大。一个服务网络可能存在多种定制方案均可满足客户需求，如何找出最优的定制方案，是一种挑战。另一方面，服务网络的能力是有限的，可能无法完全满足客户在功能上或性能上的期望。因此，在对服务网络进行定制时，需要能够识别出它相对于需求所缺失的能力，以便在后续的生长阶段对其进行能力增强。

本文首先给出服务网络的数学描述，建立服务网络优化定制问题的数学模型，对其能力缺陷进行分类。进而研究优化定制算法，分为预处理、输入参数补充、服务网络定制三个阶段。由于搜索空间很大，采用启发式算法求解输入参数补充的问题，采用人工蜂群算法求解服务网络定制的问题。通过仿真实验对算法性能进行测试，并分析相关参数对算法求解结果的影响。

相比已有工作，本文的贡献是：①与传统的服务组合方法针对单一需求从零开始构造组合方案的方式不同，本文针对一个已存在的服务网络进行定制，该途径能够以成本有效的方式实现面向多客户需求的服务大规模定制；②与传统的服务大规模个性化定制研究不同，本文中服务网络的可定制特征并非预先设计出来的，而是由各服务节点在功能和服务质量（Quality of Service，QoS）方面表现出的差异以及服务之间连接关系的多样性构成的，从而提升了客户个性化需求被满足的程度。

1 相关研究

大规模定制［4］起源于生产制造领域，其基本思想是：基于产品族零部件和产品结构的相似性和通用性，利用标准化模块化的方法降低产品的内部多样性，通过产品和过程重组将产品定制生产转化为零部件的批量生产，向客户提供低成本、高质量的定制产品。该思想在软件工程领域也得到应用［5］，例如动态软件产品线、面向复用的软件工程等方法强调利用标准化的、可复用的小粒度构件来快速组装领域内的相似应用，为领域内的特定需求展开定制（架构的裁剪与扩展、构件选择与组装），以提升开发效率、降低开发成本。

在面向服务的架构（Service Oriented Architecture，SOA）和服务计算领域，研究者提出了面向大规模定制的服务系统的设计和定制方法［6－7］。利用服务族、语义本体、规则等方式［8－9］刻画服务可配置点和彼此间的依存关系［10－11］，在运行阶段则以动态工作流等技术加以支持。软件即服务（Software as a Service，SaaS）是实现服务大规模个性化定制的另一种实践，其基本思想是使用元数据模型、策略（policy）等方式设定可变点来支持个性化配置［12］，用一个服务系统运行实例满足多租户的个性化需求。

但这些支持大规模个性化定制的服务系统本质上都是“封闭”的，通常由服务提供者遵循特定的模型驱动过程构建，其中包含的可定制点也是由建模者根据经验与领域知识识别出来的。这与服务的“开放”特性相违背，较难充分利用互联网上持续增长的可用服务，限制了服务系统的可定制能力。

在开放环境下利用“穷举”的方式构造服务网络，是近年来服务计算领域出现的一种流行策略［13－14］。该策略针对各类开放 Web服务和 API，分析它们之间的功能／语义相关性／相似性，或者基于对历史需求特征和服务使用特征的挖掘，将它们逐渐融合起来形成支持后续需求的服务网络。研究者使用了诸如服务生态系统［15］、组合服务网络［16］、Web 2.0服务网络［17］、全球社会化服务网络［18］等不同名称，来描述此类依赖于“自然生长”机制所形成的服务间连接关系，逐渐发展成为可满足各类客户需求的社会化持久基础设施。典型工作包括：服务网络的构建机制（如“滚雪球”方法［13］、服务链方法［19］、服务社交化方法［18，20］等）和服务网络的演化与生长机理（利用复杂网络和图论的相关方法来分析服务之间的静态关联与动态连接性质［15］，满足尺度无关和小世界网络特性［16－17，21］，代表了海量客户在使用服务过程中所形成的群体智能）。这些研究为服务网络作为支持服务大规模个性化定制的重要工具奠定了理论基础。

2 服务网络及定制

2.1 服务网络

上述给出的服务网络结构中隐含着两种关系：两个服务节点若相互连接，则意味着它们之间存在“关联性”（related-to），它们通过接口进行数据传递，以实现更大粒度的服务功能；包含在同一服务节点内的各原子服务之间具有功能上的等价性或相似性（similar-as），意即它们具有相似的输入输出接口和功能语义，可以相互替换，在实际定制时仅需选择一个原子服务即可。

2.2 服务网络的可定制性

服务网络的定制是指给定一个具有特定功能和QoS约束的需求，从服务网络中找到一个子网络，能够以最小的代价满足需求中的各类约束。针对不同的客户需求，可定制出不同的个性化方案。服务网络的可定制性体现在功能的可定制性和QoS的可定制性两方面。

OR关系的存在意味着SN有多种方式来生成特定数据，从而以不同方式满足需求，这是SN在功能上的定制能力。在针对具体需求的定制方案中，所有OR关系都将被消除，只保留其中唯一的一条边和相应的服务节点并提供给客户使用。将SN中满足｜Φ（sj，pk）｜＞1或｜Θ（pk）｜＞1的参数pk称为“多源参数”。

（2）QoS的可定制性 在定制时从每个服务sj的原子服务集Aj中选择一个特定的原子服务，由此影响最终定制方案的QoS水平。将满足｜Aj｜＞1的服务sj称为复合服务节点，在图1中使用双线圆形表示，以区别于｜Aj｜＝1的非复合服务节点。

归纳起来，SN的可定制机制包含两方面：①参数生成方式的多样性，体现为服务连接中的OR关系，即多源参数；②服务节点QoS的多样性，体现为复合节点。前者支持SN以不同方式满足同样的功能需求，后者使定制方案具有不同的QoS水平。这与传统的服务组合研究思路类似：基于人工智能规划的服务组合方法擅长构造服务之间连接关系的多样性（对应于SN的多源参数），而QoS感知的服务组合方法则擅长从每个服务任务的候选服务集（对应于SN的复合服务节点）中进行选择，以构造不同QoS水平的组合方案。SN则将二者有机结合，以更好地支持客户个性化需求的实现。

2.3 个性化需求

服务网络面向特定的客户需求进行定制，包含功能需求和质量需求，抽象定义为r＝（I，O，Q）。其中：I和O分别表示客户所提供的输入参数集合和期望获得的输出参数集合，共同作为功能需求；Q表示质量需求，其中的元素表示为二元组（QParami，QConsi），表示客户期望的服务组合方案的各质量参数QParami（如执行时间、可靠性、价格）需满足的最低期望为QConsi。

2.4 能力缺陷分类

根据需求r对SN进行定制，相当于对SN的两类可定制点（多源参数、复合服务节点）具体化，去掉与之无关的节点和边后形成一个子网络CN。该子网络在使用不超过I（r）中提供的参数的情况下生成O（r）中的全部输出参数，且该子网络的全局QoS指标满足质量期望Q（r）。

若找不到这样的子网络，则意味着SN相对于r来说是“能力缺陷”的，分为以下三类情况：

（1）输出参数缺失SN无法生成客户期望的某些输出参数，即O（r）＼O（SN）≠Ø，这意味着不管对SN做何种定制，需求一定无法完全满足。

（2）输入参数不足SN的任何定制方案CN都无法仅使用客户提供的输入参数I（r）就可以完全生成O（r）中的所有输出参数。这种情况下，可以要求客户补充某些输入参数以生成期望的全部输出。需补充的输入参数越多，意味着初始需求被满足的程度就越低。

（3）QoS水平不足 在输入／输出参数均足够的情况下，SN的任何定制方案都无法满足Q（r）中的某些QoS约束。在这种情况下，需要找到离QoS期望最近的定制方案，距离越近，需求被满足的程度就越大。

假设存在r1，r2和r3三个需求，I（r1）＝I（r3）＝｛p1，p2，p3，p6｝，I（r2）＝｛p4，p5，p10｝，O（r1）＝｛p9，p11，p15｝，O（r2）＝｛p7，p8，p12，p13｝，O（r3）＝｛p9，p11，p14｝，则图1的SN对r1而言存在输出参数缺失，因为O（r1）＼O（SN）＝｛p15｝≠Ø；对r2而言，在给定I（r2）的情况下无法生成p8，输入参数不足，可以通过补充输入参数p1来生成所需的p8，图2给出了补充p1之后的一个配置方案；对r3而言，给定I（r3）可以生成O（r3），图3是它的一种可能定制方案，但仍需计算该方案整体的QoS水平以判断可否满足期望。

3 问题数学模型

服务网络定制问题可定义为：给定一个服务网络SN和一个特定的客户需求r，找出最优的定制方案CN，它满足r中的功能与QoS需求。该问题的输出包含CN，EI和LO三部分，具体含义如下：

（1）CN是SN的一个 子网络，CN的 输 入 是SN输入参数的子集，也是客户提供的输入参数的子集，即I（CN）⊆I（SN），I（CN）⊆I（r）；CN的输出是SN输出参数的子集，并完全等于客户要求的输出，即O（CN）⊆O（SN），O（CN）＝O（r）；CN中不存在任何复合服务节点和多源参数，这意味着对SN中可定制特征的完全消除，CN是一个无冗余的组合服务。

（2）EI是待补充的输入参数，满足EI∩I（r）＝Ø，EI∩O（r）＝Ø，即要求补充的输入参数不包含在客户提供的输入参数集中，也不能要求客户补充他自己期望得到的输出参数；EI⊆I（SN），即只能在SN的输入参数集内补充，否则就超出了SN的能力范畴。

（3）LO是R中无法被当前SN生成的输出参数，即LO⊆O（r），LO∩O（SN）＝Ø。若LO≠Ø，则必然有CN＝Ø，EI＝Ø，这意味着：若SN中不包含客户期望的某些输出参数，则不再寻找定制方案，也无需补充任何输入参数，问题无解；若LO＝Ø，则必然至少存在一个CN可以完全或部分满足客户需求，CN≠Ø。

该问题的优化目标是使SN最大程度地满足R的期望，体现在DF和DQ两个方面，追求二者的最小化：

4 算法求解

4.1 求解策略分析

第3章给出的两个优化目标DF和DQ不是并列的，只有在SN能够满足功能需求的情况下，判定QoS的可满足性才有意义。首先，应分析当前SN是否有足够的能力满足功能需求，若无法满足，则以最小代价进行需求的输入参数补充，追求DF的最小化；进而对SN加以定制，找到与期望的QoS水平最接近的定制方案，追求DQ的最小化。故将问题求解分为三个阶段：

（1）预处理 判断初始服务网络SN（I）是否有能力生成全部的输出，若不能，则得到LO，算法结束；否则，对SN（I）进行剪枝，将客户不需要的输出参数和无法提供的输入参数完全剪掉。若无法满足全部期望的输出，则进入第（2）阶段，否则进入第（3）阶段。

（2）输入参数补充 采用启发式策略寻求代价最低的输入参数补充方案EI，进入第（3）阶段。

（3）定制方案生成 补足输入参数后，定制得到与客户QoS期望距离最近的定制方案CN。

4.2 阶段1：预处理

预处理阶段的目标是：①发现LO；②对初始服务网络进行剪枝，去掉与需求无关的部分，为后续两个阶段做好准备。具体算法如下：

算法1 预处理。输入：SN（I），r；

输出：LO，SN（P），SN（M）。

算法的（1）～（3）步检查初始网络SN（I）是否可满足需求期望的全部输出参数，若不能满足，则直接退出，SN存在输出参数缺失的能力缺陷。否则，在第（5）步中对SN（I）进行剪枝，将客户不需要的输出参数和无法提供的输入参数完全剪掉，进而将由于上述剪枝导致的某些输入参数不足的服务节点也剪掉，最终形成剪枝网络SN（P）。设I（r）＝｛p1，p2，p3，p6｝，O（r）＝｛p9，p11，p14｝，针对r对图1的SN进行剪枝，得到的SN（P）如图4所示，针对输入参数的剪枝过程是从SN的输入参数逐层向后进行，针对输出参数的剪枝过程则是从SN的输出参数逐层向前进行。

步骤（6）用于在SN（P）的基础上发现满足需求的骨架网络SN（M），它包含了满足该需求的所有必需的节点和边。采用逐个服务节点处理的方式：针对SN（P）中的每个服务节点s，将它以及所有与它相关的边剪掉，检查剩余网络中是否仍可生成客户期望的全部输出参数；若是，则s不是必需的，不包含在SN（M）中，在第（7）～（8）步中将s标识为可选节点（optional）；否则即表示s一定要出现在最终的定制方案中。例如，处理图4中的s1和s2，可发现剪掉s1之后仍然可以生成｛p9，p11，p14｝，而剪掉s2之后无法生成｛p14｝，故s1是可选节点、s2是必需节点。图5给出了最终得到的骨架子网络SN（M），图4中的黑色节点是经过标识的可选节点。

在第（9）～（12）步中，若SN（P）无法满足需求中全部期望的输出，则进入阶段2进行输入参数的补充，否则进入阶段3进行定制。通过剪枝和发现骨架网络，可极大地降低阶段2和阶段3的搜索空间。

4.3 阶段2：输入参数补充算法

若发现SN（P）无法生成全部的期望输出，则进行输入参数补充，找出客户在当前所提供的输入参数I（r）的基础上需要最少补充的其他输入参数集EI，这是对第3章中目标DF的优化。该阶段的输入是：

（1）LO＝O（r）＼O（SN（P）），表示剪枝网络SN（P）无法生成的某些需求输出参数，来自阶段1；

该阶段的输出为EI，满足EI⊆I（SN（I）），EI∩I（r）＝Ø，EI∩O（r）＝Ø。

优化目标为 min（DF）；在O（r）⊆O（SN（I））的情况下，一定存在一种输入参数补充方案可生成全部期望输出，最差的情况是令EI＝I（SN（I））＼（I（r）∪O（r）），即希望客户将初始SN的全部输入参数均补充齐全。但这样的代价太高（DF＝1），是最差的可行解。因此，算法需要从I（SN（I））＼（I（r）∪O（r））中选择一个最小子集使DF最小化。搜索算法的本质是从SN（I）中选择某些不包含在SN（P）中的服务节点和边加入SN（P）中，确保所有期望的输出参数O（r）都可被生成，且引入的服务节点数目和为支持这些服务节点所必需补充的SN（I）输入参数数目应尽可能小。这里采用启发式策略进行搜索，启发式规则如下：

规则1 补充输入参数的数目越少越好。

规则2 为补充输入参数而向SN（P）引入的服务节点数目越少越好。

规则1与DF直接相关，规则2是对阶段3定制时的考虑，所引入的必需服务节点越多，有很大概率会导致最终定制方案中包含的服务节点数目越多，从而对最终QoS的影响程度越大。

为采用启发式策略求解，作如下状态定义：E＝〈LI，AS，CS，AO〉表示在搜索过程中所产生的各个状态，其中：LI为当前状态下需要补充的输入参数集；AS为搜索过程中选中并加入到SN（P）的服务节点集合；CS为不包含在SN（P）中但可生成LI中1或多个参数的服务节点集合；AO为当前状态下SN（P）可提供的全部输出参数集合。

（1）初始状态E0

1）LI＝LO，表示剪枝网络无法生成的输出参数集；

2）AS＝Ø，表示尚未向SN（P）加入任何服务节点；

3）CS，表示SN（I）中最靠近输出且能直接生成LO中1个或多个参数的服务节点集，它们一定不包含在SN（P）中；

4）AO＝AI，表示当前SN（P）可提供的全部输出参数。

（2）目标状态EG

1）LI≠Ø，LI∩LO＝Ø，表示找到了所需补充的某些输入参数；

2）AS≠Ø，表示已向SN（P）加入某些服务节点；

3）CS＝Ø，表示不存在可向SN（P）补充的服务节点；

4）AO⊇LO，表示可生成所有缺失的输出参数。

根据规则1和规则2，从E0达到当前状态E的代价g＝｜LI∩LO｜＋｜AS｜，前者为当前状态需要引入的新输入参数的数目，后者表示当前状态需引入的新服务节点的数目。从当前状态E到目标状态EG的距离h＝｜LO＼AO｜，表示当前状态尚无法生成的缺失输出参数的数目，在h＞0时需要继续迭代搜索。利用f＝g＋h作为启发式规则进行迭代搜索，算法如下。

算法2 寻找需求中待补充的最少输入参数集。

输入：LO，AI；

输出：EI。

算法的第（3）～（11）步代表一次迭代，由状态生成规则可知，每次迭代可补充至少1个缺失的输出参数，故最多只需迭代｜LO｜次，可确保达到目标状态。而LO最大取值为需求r中期望的输出参数个数，故最差的迭代次数为M＝｜O（r）｜。每次迭代分为两部分：（4）～（8）步从当前最优状态EC的候选服务集中取出每个服务节点，产生｜CS（EC）｜个新状态。CS（EC）中最多包含的服务节点数量N＝｜S（SN（I））＼S（SN（P））｜，极端情况下N＝｜S（SN）｜。第（9）～（10）步从新状态中选择最优的一个状态，替换当前的EC，最差情况下的时间复杂度也是N。第（12）～（15）步从所有已达目标状态中的生成状态中选择代价最小的一个，将其补充的输入参数集合LI作为算法输出，并更新SN（P）。归纳起来，算法2的时间复杂度为O（M×N）。

4.4 阶段3：服务网络定制算法

该阶段的输入是经过阶段1剪枝和阶段2补充输入参数之后形成的子网络SN（P）。此时的SN（P）一定可以生成客户期望的全部输出参数，本阶段的目标是找到与客户QoS期望距离最近的定制方案，即min（DQ）。定制过程相当于对SN（P）中存在的每一个多源参数和复合节点进行定制，即：为多源参数选择一条具体的“源边”、为复合节点选择一个具体的原子服务。这两方面选择的结果都会对最终定制结果的全局QoS产生影响。

ABC算法借助于一群蜜蜂合作寻找蜜源的过程，将局部搜索和全局搜索相结合，逐步逼近最优解。局部搜索是指：针对SN个食物源，按照特定标准对每个食物源进行邻域探索，适应度越高的食物源得到的被探索机会就越大，探索后的新食物源若优于原有食物源，则替换之；若探索达到Limit次之后仍无改进，则跳出局部搜索，寻找一个新食物源代替它，即全局搜索。若连续迭代MCN次仍无法继续改善全局最优解，则算法结束，当前搜索得到的最优解为最终输出结果。SN、Limit和MCN是ABC算法的三个基本控制参数。之所以选择ABC求解，是因为它具有强大的并行化局部搜索的能力、跳出局部搜索进行全局搜索的能力，以及根据优化效果动态停止迭代的能力，且已在服务组合等类似问题上得到应用，并被证实具有良好效果［23］。

以下对ABC求解SN定制问题中的若干关键要素进行说明：

（1）食物源（解）的表示f＝（p1，p2，…，pm；s1，s2，…，sn），∀i∈［1，m］，pi＝eiu表示第i个多源参数的第u条源边被选中；∀j∈［1，n］，sj＝ajv表示复合节点sj中的第v个服务ajv被选中。

（2）食物源的适应度（fitness） 用DQ加以度量，根据食物源所代表的定制方案的流程结构和被选中的各个服务节点的具体QoS值，计算定制方案的全局QoS，再计算相应的DQ。

（3）解的邻域有两种形式 ①对某个多源参数pi，若在当前解中其值为eiu，则为其选择其他源边，其他所有与pi不同的参数以及复合服务的选择方案均不变，即构成了当前解的邻域；②复合节点sj，若在当前解中的值为ajv，则为其选择其他原子服务，其他所有多源参数和与sj不同的复合节点的选择方案均不变，也构成了当前解的邻域。

（4）邻域搜索策略 ①完全随机策略，在食物源处随机选择1个参数或1个复合节点，随机在它的其他源边或其他原子服务中选择1个，替换形成新解；②启发式策略，为了提高收敛速度，针对复合节点的邻域使用如下启发式规则：根据DQ对每个原子服务进行估值，其DQ值越小，被选中的概率就越大，即那些具有更优QoS的原子服务会被优先探索。

（5）解的重复性检查 按照解的结构对SN（P）进行删减，剪掉那些对其他节点或输出参数无贡献的节点，若形成的定制方案与之前已经探索过的解相同，则将其抛弃，重新随机生成或探索新的邻域。

（6）算法的停止条件 当最优解的质量连续MCN次迭代均没有改进时，算法停止，将当前最优解输出。

5 实验与分析

5.1 数据准备

编程环境：Visual Studio 2010C＋＋；运行环境：Intel Core i3双核3.10GHz，2.93G内存，Windows 7操作系统。实验数据采用仿真生成方式，生成100个客户需求，输入参数数目和输出参数数目在［1，100］范围内，期望 QoS指标 Time，Reliability，Price的取值范围分别为［20，100］，［0.5，1］，［25，500］。生成20个服务网络，表1给出了其中10个网络的基本信息，它们的规模、复杂度、可定制点数目均保持逐渐增加的趋势。

表1 实验所用服务网络的基本信息

续表1

5.2 实验1：需求特征对定制结果的影响

本实验用来验证需求特征对定制质量的影响。选择1个特定的SN和多个需求，分别利用算法求解，以分析需求处于不同苛刻程度下解的质量的变化情况。这里“需求苛刻程度”分为三方面：①所提供的输入参数数量；②所期望的输出参数数量；③所期望的QoS水平。“解的质量”分为三方面：①为补充输入参数所付出的代价；②所得定制方案的适应度（QoS水平）；③二者的综合。需求提供的输入越少、期望输出越多、期望QoS水平越高，则表明该需求越“苛刻”，直观可知SN满足该需求的能力就越低、所付出的代价也就越高。

图6给出了对具有不同输入参数数目的多个需求进行服务网络定制的解质量变化情况。这些需求除了输入参数数目不同，所期望的输出参数和QoS水平均相同。由图6a可以看出，针对输入参数较多的需求，无需补充很多输入参数，为此所需付出的成本（AddedCost）较低；随着输入参数的逐渐减少，需要补充越来越多的输入参数，故AddedCost呈阶梯跳跃上升的状态。之所以出现这种现象，是因为当某个需求缺少了某个关键输入参数后，很多原本可以参与定制的服务节点不再可用，不得不集中补充若干输入参数，故成本出现跳跃上升。

对解的适应度（fitness）来说，则呈现出一种“平稳—上升—下降”的趋势。这仍然是由补充输入参数造成的：随着输入参数的减少，网络中出现了一部分失效服务节点，而由于新补充了某些输入参数，最终形成的定制方案中无需包含那些失效的服务节点，而是选择其他更有效用的服务节点，故定制方案中包含的服务节点较原来变少，解的质量上升；而当可提供的输入参数更少时，越来越多的服务节点都需要补充输入参数，算法会再次倾向于生成包含较多服务节点的定制方案，解的质量下降。

图6b是将Fitness和AddedCost综合在一起之后形成的综合性能曲线。由此可以看出，随着需求提供的输入参数数量的下降，整体性能呈现一种阶梯下降的趋势。

图7给出了针对具有不同输出参数数目的多个需求的解质量的变化情况。这些需求除了输出参数的数目不同，其所提供的输入参数和QoS水平均相同。该结果表明：需求的输出参数越多，需要补充的输入参数就越多，所需成本上升，解的质量下降。

图8展示了解的质量受需求的QoS严格程度影响的曲线，随着横轴所表示的QoS需求越来越严格，SN满足它的能力变得越来越弱，算法求解得到的最优定制方案的质量逐渐下降。

综合上述实验结果可知，个性化需求的苛刻程度对定制结果的质量有较大影响。

5.3 实验2：服务网络特征对定制结果的影响

本实验用来验证SN特征对定制结果质量的影响。选择1个特定的需求和多个SN，分别利用算法求解，以分析具有不同结构特征的SN满足同一需求的定制方案质量变化情况。这里“SN的结构特征”分为三方面：①包含多源参数的数量；②包含服务节点的数量；③包含复合服务节点的数量。解的质量也分为三方面：①为补充输入参数所付出的代价；②所得定制方案的适应度；③二者的综合。SN包含的多源边越多、服务节点越多、复合服务节点越多，意味着SN的可定制能力越强，满足需求的能力就越高，但定制时的搜索空间也越大。

图9给出了解的质量（fitness）和算法执行时间（execution time）随多源参数数目变化的趋势。随着SN中包含的多源参数越来越多，在进行ABC搜索时的解空间越来越大，需要迭代的次数就越多，故执行时间呈上升趋势。同时，多源参数的增多为定制提供了更多可能，故SN满足需求的能力也在提升，fitness上升。

图10a展示了解的质量（fitness，AddedCost）随SN服务节点数目增加的变化趋势。可以看出，随着节点数目的增加，为满足需求所需补充的输入参数会逐渐下降，从而降低额外成本。但从fitness的变化看，定制方案满足需求的水平呈先上升后下降的趋势，这是因为：在SN规模较小时，为满足需求需要补充更多的输入参数，并且随着SN规模的增大，补充输入参数后找到的定制方案的质量也越来越好；当SN的规模越来越大时，代表着SN满足需求的能力逐渐提高，需要客户在需求中补充的输入参数逐渐减少，算法逐步倾向于使用SN本身所提供的越来越丰富的服务节点来满足需求。根据算法的设计思路可知，通过补充输入参数来满足需求时，算法倾向于寻求增加那些以最简单的方式满足需求的输入参数，故定制方案的复杂度可保持较低，使用更少的服务节点即可满足需求，解的QoS质量较高；而若使用SN本身的服务来满足需求，则算法不得不在SN自身结构的限定下进行搜索，所形成的定制方案结构可能会相对复杂，从而影响解的全局QoS，其质量变得稍差。但从图上可以看出，解质量的降低程度并不十分明显，并且在SN的服务节点数目达到一定程度后即保持稳定。

图10b是解的综合性能（global performance）和算法执行时间（execution time）的变化趋势。综合性能呈现逐渐上升的趋势，意味着SN中服务节点的数目对定制结果具有一定的正相关性，服务节点越多，SN的定制能力也越高。从算法执行时间看，整体上也处于上升的趋势，这表明服务节点数目增大了搜索空间，从而降低了算法效率。

图11给出了定制方案质量和算法执行时间随SN中复合服务节点数目增加的变化趋势。从该图可以看出，二者整体上均呈现非常缓慢的上升趋势。这意味着复合服务节点并未显著地增加服务网络的定制能力，也没有使算法搜索空间得到较大扩展，故执行时间不会有太大恶化。由此可得结论：在SN的各项结构指标中，服务节点数目和多源参数数目更影响SN的定制能力，而复合节点数目对SN定制能力的影响则相对较低。

分析原因在于：复合服务节点属于一种局部可配置点，它只能改变定制方案某个局部的QoS，却无法影响定制方案整体的结构。而服务节点和多源参数则是从全局角度对定制方案的结构起到了很大的作用。这也意味着为了提升SN的定制能力，首先应丰富其服务节点和节点之间的边，其次考虑为每个服务节点增加其他候选服务。

6 结束语

针对客户的个性化需求，如何从包含多个可定制点的服务网络中派生出与客户需求距离最近的定制方案，是本文解决的核心问题。问题求解分为三个阶段，分别采用启发式方法和ABC方法进行优化求解，在有限时间内寻求近似最优解。实验分析得到的结论是：①需求的苛刻程度对服务网络定制的性能有较大影响：需求越苛刻，对服务网络进行定制的代价就越大、所获得的定制结果质量越低；②服务网络的结构特性对其定制性能有不同的影响：多源参数越多、服务节点越多、服务网络的满足需求的可定制能力就越强，而复合服务节点的数量对其定制能力的影响则不明显。该结论可对现实中服务组织规划和提供自己的服务网络具有参考价值，倾向于将有限的成本用于增加服务网络可定制能力。

本文的研究具有实际应用价值。由于客户的需求越来越倾向于大粒度和跨领域性，为满足需求所构造的服务方案也必然需要集成多个跨领域的服务以形成服务网络，需要在其上进行快速准确的个性化定制。典型实例是智能交通领域的交通应急救援服务网络，涉及城市交通监控、交警、消防、医院救护、环卫和特种物品处置等多个服务领域，在面对突发交通意外时，如何快速对其进行定制，选择最优服务投入运作，是现实交通服务中真实面临的挑战。在制造服务、物流服务等其他生产服务领域，这种问题场景普遍存在。

［1］ HATZI O，VRAKAS D，BASSILIADES N，et al.The PORSCE II framework：using AI planning for automated semantic Web service composition［J］.The Knowledge Engineering Review，2013，28（2）：137-156.

［2］ ALRIFAI M，RISSE T，NEJDL W.A hybrid approach for efficient Web service composition with end-to-end QoS constraints［J］.ACM Transactions on the Web，2012，6（2）：1-31.

［3］ WANG Z，XU X.Mass customization oriented and cost-effective service network［J］.Lecture Notes in Business Information Processing，2013，144：172-185.

［4］ SILVEIRAA G D，BORENSTEINB D，FOGLIATTOC F S.Mass customization：literature review and research directions［J］.International Journal of Production Economics，2001，72（1）：1-13.

［5］ HALLSTEINSEN S，HINCHEY M，PARK S，et al.Dynamic software product lines［J］.IEEE Computer，2008，41（4）：93-95.

［6］ HU B，MA Y，ZHANG LJ，et al.A CCRA based mass customization development for cloud services［C］／／Proceedings of International Confrence on Service Computing.Washington，D.C.，USA：IEEE，2013：705-712.

［7］ DAN Bin，JING Youguo，SUN Min，et al.Intelligent need acquisition approach for heterogeneous customers under online mass customization［J］.Computer Integrated Manufacturing Systems，2012，18（1）：15-24（in Chinese）.［但 斌，经有国，孙敏，等.在线大规模定制下面向异质客户的需求智能获取方法［J］.计算机集成制造系统，2012，18（1）：15-24.］

［8］ SUN C，ROSSING R，SINNEMA M，et al.Modeling and managing the variability of Web service-based systems［J］.Journal of Systems and Software，2010，83（3）：502-516.

［9］ LIANG Q，WU X，PARK EK，et al.Ontology-based business process customization for composite Web services［J］.IEEE Transactions on Systems，Man and Cybernetics，Part A：Systems and Humans，2011，41（4）：717-729.

［10］ HADAYTULLAH H，KOSKIMIES K，SYSTA T.Using model customization for variability management in service compositions［C］／／Proceedings of International Confrence on Web Service. Washington，D.C.， USA：IEEE，2009：687-694.

［11］ NGUYEN T，COLMAN A，HAN J.Modeling and managing variability in process-based service compositions.serviceoriented computing［J］.Lecture Notes in Computer Science，2011，7084：404-420.

［12］ SUN W，ZHANG X，GUO C J，et al.Software as a service：configuration and customization perspectives［C］／／Proceedings of IEEE Congress on Services PartⅡ.Washington，D.C.，USA：IEEE，2008：18-25.

［13］ LIANG Q X，CHEN S Z，FENG Z Y.Application of services relation tracing to automated Web service composition［J］.Applied Mathematics ＆Information Sciences，2013，7（S1）：243-251.

［14］ WANG Z，XU F，XU X.A cost-effective service composition method for mass customized QoS requirements［C］／／Proceedings of International Confrence on Service Computing.Washington，D.C.，USA：IEEE，2012：194-201.

［15］ HUANG K M，FAN Y S，TAN W.An empirical study of programmable web：a network analysis on a service-mashup system［C］／／Proceeding of International Confrence on Web Service.Washington，D.C.，USA：IEEE，2012：552-559.

［16］ TAO F，GUO H，ZHANG L，et al.Modelling of combinable relationship-based composition service network and the theoretical proof of its scale-free characteristics［J］.Enterprise Information Systems，2012，6（4）：373-404.

［17］ HWANG J，ALTMANN J，KIM K.The structural evolution of the Web 2.0service network［J］.Online Information Review，2009，33（6）：1040-1057.

［18］ CHEN W，PAIK I，HUANG P C K.Constructing aglobal social service network for better quality of Web service discovery［J］.IEEE Transactions on Services Computing，2015，8（2）：284-298.

［19］ JUNG J J.Service chain-based business alliance formation in service-oriented architecture［J］.Expert Systems with Applications，2011，38（3）：2206-2211.

［20］ MAAMAR Z，HACID H，HUHNS M N.Why Web services need social networks［J］.IEEE Internet Computing，2011，15（2）：90-94.

［21］ KIL H，OH S C，ELMACIOGLU E，et al.Graph theoretic topological analysis of Web service networks［J］.World Wide Web，2009，12（3）：321-343.

［22］ ZHENG H，ZHAO W，YANG J，BOUGUETTAYA A.QoS analysis for web service compositions with complex structures［J］.IEEE Transactions on Services Computing，2013，6（3）：373-386.

［23］ WANG X，WANG Z，XU X.An improved artificial bee colony approach to QoS-aware service selection［C］／／Proceedings of International Confrence on Web Service.Washington，D.C.，USA：IEEE，2013：395-402.