基于需求/服务模式的大规模个性化网络服务定制方法

陈春荣，何 霆+，廖永新，李海波，黄双喜

(1.华侨大学 计算机科学与技术学院，福建 厦门 361021；2.清华大学 国家CIMS工程技术研究中心，北京 100084)

1 问题的提出

服务互联网环境[1]下，服务组合优化技术是实现服务体系正常运营的方法，它将分散的、相互独立的、由不同提供者提供的多项服务通过某种合适的方式整合在一起，形成新的大粒度的服务业务并向外提供。对计算机而言，其执行该类任务的过程一般是通过基于智能规划理论的服务组合优化算法来实现。算法处理步骤一般是先对服务和用户需求进行预处理和形式化转化；然后，从已有服务出发挖掘其隐含的逻辑或业务关系，为服务发现和复杂的服务组合准备更大粒度的素材，降低服务组合的复杂度；最后，逐步将用户需求分解为服务可执行的功能单位，进而从互联网上找到相应的服务，并对其进行编排形成服务业务系统，从而满足用户需求[2]。现有服务组合优化算法主要从服务功能和服务质量两方面来进行[3-6]。功能方面的服务组合优化算法主要运用自动发现和流程规划等技术手段来匹配用户的功能需求[7]。这些方法大多采用智能演化算法来编排可用服务，算法的主要优化目标是提高需求与服务在功能上的匹配度；在服务质量方面，主要是进行基于服务质量(Quality of Service，QoS)感知的服务选择[8-9]。这些方法在一定条件下可以选出最佳的组合服务，但大都从用户需求一侧出发，没有考虑服务提供者的成本问题，甚至可能造成成本无效[10]。成本无效在本文中是指服务提供者获得的收入小于其提供组合服务所付出的成本。在正常的服务系统中，只有兼顾用户和服务提供商的利益才能维护服务体系的正常运行，否则这种状态注定无法持续。

如今也有一些研究者开始关注服务收益问题，文献[11-12]借鉴交易市场中的商品定价机制，通过对服务解决方案中成员服务的按需定价，保证在服务组合过程中最大化服务提供者的收益。文献[13-14]分别在在动态定价和静态定价环境下，提出了一种划分选择的服务选择方法。这些方法在面对单一用户需求时收益效果较好，但不适用于大规模用户需求环境。典型的大规模整合型服务应用面向特定领域汇集海量的服务资源和用户需求，使得相同或者相似的用户需求得以在短时间内大量、持续地出现，从而表现出大规模、个性化的特征。

为了实现大规模用户需求环境下的成本有效性，一个服务解决方案不应该只针对一个用户需求。实现服务解决方案以及单个原子服务的复用可能给服务提供者带来更大的收益。文献[15]在大规模用户需求的环境下，从服务收益出发采用一种渐进迭加的策略来优化服务提供者的利益。文献[16-17]采用服务网络的方法来实现大规模服务定制，这些方法都是单纯从服务功能或者服务质量出发，不能完全体现用户需求的个性化主张，同时算法在海量用户需求环境下的服务定制效率有待提高。特别是平台整合型应用(如美团、携程)的兴起，使得服务解决方案定制效率问题进一步突显。为了提高服务定制的效率，基于文献[18]中需求模式和服务模式的概念，本文使用需求模式来代替多个子需求，缩减问题规模；使用服务模式整合多个原子服务，构建大粒度的服务流程，减小服务搜索空间。

在服务解决方案构造过程中，用户支付费用一定的情况下，超过用户需求服务质量约束的解决方案不会给提供者带来额外收益。服务的服务质量越高，价格越高。如图1所示为服务解决方案质量与服务成本以及收益的关系。图1中实线代表服务解决方案成本与服务质量的变化，虚线代表服务提供者获得的收入与服务质量的变化。由图1可以看出，追求服务解决方案服务质量最优不能给服务提供者带来最大收益。因此，在服务组合过程中，一方面在用户需求约束下保障用户价值的实现，一方面优化服务提供者的利益是保证服务系统能够正常运行的关键。

特别的，笔者曾提出一种基于模式的个性化服务定制方法来解决服务定制的效率问题[18]。但该方法仅面向单用户需求，不适用于大规模用户需求环境，同时也没有考虑服务成本问题。有鉴于此，本文在此基础上提出一种基于需求/服务模式的大规模个性化网络服务定制方法，该方法不但使用具有先验知识、经过历史数据验证的需求模式和服务模式、以及可以复用的服务网络来提升服务定制的效率，而且还可以从服务提供者和用户双方的角度来实现用户服务价值—供应商服务成本的均衡优化。

2 问题定义

2.1 服务网络

服务网络(service network)是将分散在互联网和现实中的各类服务(e-Service、人工服务、信息、资源等)按特定方式连接形成的网络，彼此之间通过特定的协同与互操作协议进行交互[16]。服务网络不是针对单个用户需求的，而是面向大规模用户需求的。图2显示了一个服务网络的示例，在服务网络中主要包含4个部分：输入参数、输出参数、具体的服务以及它们之间的有向边。

在服务网络中，对于给定的用户需求，可以对用户需求定制个性化的服务解决方案。在满足用户需求功能约束和服务质量约束下，服务网络中一个服务子网代表了一种服务解决方案。对于一个用户需求，服务网络中可能存在不同的服务子网都满足当前需求。例如在图2中对于服务节点s6,存在着3条有向边均传递参数p4到服务s6，在最终的服务解决方案定制中只需要选择一条有向边。

2.2 问题定义

下面对本文提出的候选服务，服务模式，用户需求以及需求模式做出形式化定义，并提出本文算法的优化目标。

(1)候选服务与服务模式

定义服务网络中一个具体服务si为si={Ii,Oi,Qi,Pi,NCi}。其中：Ii,Oi分别代表服务的输入参数和输出参数。Qi代表服务的服务质量集，Qi={Ai,Ei,Ti,}。Ai代表服务可用性即服务请求成功的数量/所有请求数量，Ei代表服务可靠性即服务正常运行时间/总运行时间[5]。Ti为服务响应时间，Pi代表服务价格，NCi是用户与服务提供商关于服务的协商成本。

服务网络中一个服务模式被定义为sp=(spin,spout,spq,spp,spnc)。服务模式代表从一定规模的历史服务记录中抽取出来的频繁出现的完整/部分服务组合[18]。例如在旅游团中，旅行社会为用户提供一个完整的旅行服务套餐，服务套餐中的这些服务在历史服务方案中经常以一定的顺序频繁出现。本文对这些高频使用的服务流程进行分析和挖掘，从而形成服务模式。spin，spout分别代表服务模式的功能输入和输出；spq代表服务模式的各项性能参数，spq=(spA,spE,spT)，spA,spE,spT分别代表服务模式的可用性，可靠性以及响应时间；spp代表服务模式价格；spnc代表服务模式的协商成本。spq,spp,spnc三者性能指标可由工作流聚合函数根据服务流程计算得出。

(2)用户需求与需求模式

需求模式rp定义为rp=(rpin,rpout,rpq,rpp)。需求模式rp代表在多个历史需求中抽取出来的频繁连续的需求片段[18]。例如在用户旅行需求中，用户在预定机票的同时，通常需要预定酒店，本文将这种经常一起出现的连续需求片段刻画为需求模式。其中：rpin表示需求模式期望输入参数，rpout表示需求模式输出参数，rpq表示需求模式的服务质量约束水平，rpp表示需求模式被满足时支付的费用。

(3)优化目标

在处理大规模用户需求中，服务提供者所获得的收入为满足用户需求时用户所支付的费用。服务提供者付出的成本主要是服务提供者提供组合服务方案所付出的构建成本。服务构建成本由服务资源提供成本以及协商成本决定。因此，服务提供者获得的利益为收入与构建成本的差值，计算公式如下：

(1)

(2)

式中：CC表示服务的总构建成本；Pi表示服务资源提供成本，当服务被用来满足多个用户需求时，Pi应该计算多次；|SRi|表示服务si参与满足用户需求的次数；NC代表服务构建成本中的总服务协商成本，

(3)

式中：NC表示服务的协商成本，服务协商成本是服务提供者之间就服务使用方式以及使用时间达成一致所需付出的成本；u代表服务网中单位节点的维护成本；|SN|代表服务网络中总的服务节点数。

综上所述，本文的优化目标函数为最大化Rev-CC。

3 服务网络构建方法

3.1 服务网络构建

本文采用一种迭代增强的策略来构建服务网络，对于每个用户需求，可以通过定制服务网络中的具体服务子网来生成满足用户需求的服务解决方案。方法中首先对大规模用户需求进行排序，然后依次处理各用户需求。在处理当前用户需求时首先利用ORSC(requirement oriented service composition)算法寻找基于服务模式构建的服务解决方案，同时检查当前服务网络中是否存在一个服务子网满足当前需求。若服务网络中不存在服务子网满足当前需求，则采用ORSC算法中利用服务模式构建的服务解决方案，并将其融入服务网络中；若服务网络存在服务子网满足当前用户需求，比较两种方案的成本，采用具有较低成本的服务解决方案。

算法1服务网络构建算法SN_CT。

输入:CS, R；

输出:SN, SR,{CNi}。

1.R←Sort(R)

2.if n=1

3.SN(n)←ORSC(r,CS),CNn=SN(n)

4.Else

5.SN(n-1)=SN_CT(R/rn,CS)

8.soln←ORSC(r,CS)

12.Else

13.SN(n-1)←soln

14.SN(n)←merge(SN(n), SN(n-1))

15.return

3.2 基于服务水平协议的用户需求排序

在大规模的用户需求中，存在着大量功能相似但性能不同的需求。用户需求处理顺序的不同会给服务提供者带来不同的收益。根据用户需求的服务质量约束对应的服务水平协议对用户需求进行排序，可以得到按照降序排列的用户需求集R。从而在处理用户需求时可以尽可能实现原子服务的复用，达到优化服务提供者利益的目的。

服务水平协议集[19]SetSLA={SLA1,SLA2,..SLAn}，对于每一个服务水平协议，Qsetn为服务水平协议对应的服务质量标准集合，Qsetn={qn1,qn2,..,qnk}。本文选取的服务指标有服务可用性、可靠性和响应时间，故k=3。确定用户需求所属的服务水平协议后，定义各服务水平协议之间的质量优劣关系，构造一个服务质量关系图，这是一个有向无环图，如图3所示。

在图3中对于任意一条边相邻的两个顶点，出度节点代表的服务质量约束优于入度节点。同一层中不直接相邻的两个顶点代表的服务质量约束关系是一种不等关系。例如在图3中，对于SLA1和SLA2两个顶点，SLA1代表的服务质量标准集Qset1优于SLA2代表的服务质量标准集Qset2。同时Qset1与Qset2存在以下关系:

(4)

式中：>表示优于符号，对于正向Qos属性指标，表示q1i大于q2i，对于负向的Qos属性指标表示q1i小于q2i。

对于同一层中的SLA2和SLA3两个节点，所代表的服务质量标准集是一种不等关系，如式(5)所示：

(5)

通过构造一个服务质量关系图，可以得到各用户需求服务质量的相对优劣关系。通过服务质量关系图广度优先遍历节点时，可以得到按照降序排列的用户需求集R。

3.3 面向个性化需求的服务定制算法

本节将介绍SN_CT算法中所使用的面向个性化需求的服务定制算法ORSC算法[18]。算法中首先利用频繁模式挖掘算法FP-growth[20]，基于一定规模的历史数据集，构建面向领域/跨领域的需求模式库和服务模式库，并建立双边模式映射匹配概率。然后，对于用户的个性化需求，利用遗传算法在需求模式库中找到最佳的需求模式集来代替当前用户需求。如果需求模式集为空，则代表没有任何的先验知识可用于当前需求，传统的扩展多目标演化算法(Extended Multi-Objective Evolutionary Algorithm, EDMOEA)[5]将被调用，以此生成服务解决方案。最后,对于代替当前用户需求的需求模式集，利用建立的需求模式和服务模式之间的匹配概率来寻找最佳的服务模式集，并以此生成满足当前需求的服务解决方案。当服务模式生成的服务解决方案不能完全满足用户需求时，对于缺失的服务节点，从成本出发选择最佳的候选服务与原有服务模式相结合来生成完整的服务解决方案。算法2详细阐述了ORSC算法的步骤。

算法2面向个性化需求的服务定制算法ORSC。

输入：ri,HR, HS；

输出：solni。

1.PR, SP←FP-growth(HR,HS)

2.map←match(RP,SP)

3.RPi←cover(ri,RP)

4.if RPi=∅

5. solni=EDMOEA(ri,CS)

6.else

7. RPi←GA(RPi)

8.SPi←FindSP(map,RPi,SP)

9.solni←combine(SPi)

10.return

算法的输入为需求ri，历史需求集HR以及历史服务解决方案记录集HS，算法输出为根据用户需求约束定制的个性化服务解决方案solni。算法中第1行利用频繁模式挖掘算法FP-growth构建需求/服务模式库。第2行利用match函数建立了需求模式与服务模式的匹配关系。第3行从需求模式库中找到能够覆盖用户需求的需求模式集RPi。如果需求模式集RPi为空，代表当前用户需求没有任何历史先验知识可用，算法将调用传统的服务组合方法EDMOEA生成服务解决方案。最后算法利用FindSP函数找到需求模式集对应的最佳服务模式集来生成个性化服务解决方案。

3.3.1 需求模式/服务模式映射

如图4所示，利用模式挖掘算法可以从一定规模的历史需求和对应的服务解决方案中挖掘出需求模式和服务模式，之后建立双边模式之间的匹配概率。需求模式和服务模式间的匹配概率主要考虑以下两个因素：

(1)先验知识 先验知识体现了在历史服务请求及其服务解决方案中，服务模式spj满足需求模式rpi的概率，这个概率是从一定规模的历史数据中抽象出的经验知识。可以使用朴素贝叶斯定理来进行表示，如式(6)所示：

(6)

式中:p(spj)=sp+/n，n表示历史数据集中服务解决方案总个数；sp+表示服务模式spj在历史服务解决方案中出现的总次数；p(rpi)=rp+/n,rp+表示需求模式rpi在历史服务请求中出现的总次数；p(spj/rpi)=c+/rp+,c+表示需求模式rpi与服务模式spj在历史服务请求响应记录中共同出现的次数。

(2)需求模式与服务模式的相似性 需求模式与服务模式的相似性包含了服务质量和服务功能两方面，如式(7)所示。式(7)中I表示服务性能指示函数，当指示函数I中表达式为真时，值为1，否则为0；⊕表示服务性能比较符号，当服务模式spj的服务性能满足需求模式rpi的服务性能约束时，指示函数I的值为1，否则为0。当服务模式的输出参数与需求模式的期望输出参数重叠的比例越高时，aij概率值也就越高，从而表示服务模式spj更容易满足需求模式rpi。

(7)

由pij和aij两者指标可以得出需求模式rpi和服务模式spj之间的匹配概率，如式(8)所示，w1和w2分别表示两个指标的权重，w1与w2的和为1。

s(rpi,spj)=w1pij+w2aij。

(8)

本文中需求模式的先验分数定义为需求模式与相映射的服务模式的匹配分数之和，如式(9)所示，需求模式的先验分数越高，越容易被服务服务模式所满足。

(9)

3.3.2 需求模式集选择

建立需求模式和服务模式匹配概率后，对于用户个性化需求ri，在需求模式库中利用遗传算法找到一个最佳的需求模式集RPi来代替用户需求。遗传算法的适应度函数主要考虑以下3个指标：

(1)考虑服务收益，互联网上存在大量功能相似但服务性能不同的服务，通常情况下性能越高的服务，价格也越高。当一个用户需求被需求模式集所覆盖时，需求模式集的服务质量约束和用户需求的服务质量约束越接近越好，从而在需求模式—服务模式匹配时，不用寻找服务性能过高的服务模式，因此式(10)中c1(X)应该被最小化。

c1(X)=|riq-q(RPi)|，

(10)

式中q是计算服务性能指标的聚合函数。

(2)考虑需求模式集RPi和用户需求ri的期望功能输出参数的重叠度，重叠度越大，用户需求被覆盖的程度越大，因此式(11)中c2(X)应该最大化。

(11)

(3)考虑需求模式的先验知识,需求模式的先验分数越高，在需求模式/服务模式的匹配过程中更容易被服务模式所满足，因此式(12)中c3(X)应该最大化。

(12)

综上所述，遗传算法的适应度函数如式(13)所示，w1，w2，w3分别代表3个指标的权重，权重值相加为1。

f(X)=w1c1(X)+w2c2(X)+w3c3(X)。

(13)

3.3.3 服务模式集选择

在需求模式/服务模式的双边映射匹配中，SPi为需求模式集RPi相映射的服务模式集。为了找到最佳的服务模式集来满足需求模式集RPi，首先利用式(14)找出与需求模式集RPi中每一个需求模式匹配分数最高的服务模式spi，并将服务模式spi加入到SPi。

spi=∀spj∈SPimaxs(rpi,spj)。

(14)

现实情境中，一个服务模式往往不能百分之百的满足一个需求模式，因此大多数情况下算法需要寻找额外的服务模式来满足需求模式集。通过式(15)可以计算出SPi中的每个服务模式与需求模式集RPi的相关度，相关度的大小代表了服务模式对需求模式集的作用程度，相关度越大，服务模式对当前需求模式集越有用。

(15)

在计算相关度时，当前服务模式与SPi中已选择服务模式的重叠度对服务模式的选择会产生影响，因此算法实际运行过程中会设置一个阈值，将大于指定阈值的服务模式从SPi中去除掉。算法在每次迭代过程中选择与需求模式集RPi相关度最大的服务模式加入到SPi中，同时设置阈值a，将相关度小于阈值a的服务模式从服务模式集SPi中过滤掉，算法迭代，直到SPi为空。

4 实验

4.1 数据准备

实验候选服务数据集采用QWS[1]，WS-DREAM[7]两个公开的服务数据集。这两个数据集包含了大约6 000个公开的Web服务，这些服务来源于搜索引擎门户网站等。数据集中包含了服务的QoS属性信息,如服务价格，可靠性，响应时间等。同时可从服务的 Web服务描述语言(Web Services Description Language，WSDL)[21]文件中提取服务的输入以及输出参数。实验中服务提供者所获得的收入为用户需求被满足时所支付的费用，服务的构建成本由服务资源提供成本与服务协商成本决定。服务协商成本为NC，服务提供商之间每协商一次都需要付出协商成本，具体的服务协商价格由服务提供者根据具体服务使用场景来确定。

对于大规模用户请求集，由于没有公开的服务请求集，本文模拟生成3 000个用户服务请求。用户需求通过以下规则产生。

(1)从公开的服务集中提取出1 000个输入输出参数，分成20组。从前10组任意选取5～10个参数作为需求输入参数，从后10组参数中选取10～15个参数作为需求输出参数。输入参数与输出参数最多来自3个组。

(2)需求的QoS约束水平即服务可靠性、可用性以及相应时间取值范围分别是[0.8,1.0],[0.9,1.0],[1,10]。

(3)用户支付的费用价格范围为[100,1 000],用户支付费用与用户的服务质量约束水平一致，即需求的QoS属性越高，用户愿意支付的费用越大。同时需求输出参数越多，用户支付费用也会变大。

4.2 实验结果与分析

基于上述数据，总共进行如下3个方面的实验来验证文中所提方法的有效性。

实验1在第一项实验中比较了服务网络构建算法(SN_CT)，EDMOEA[5]，以及智能演化算法(Intellignet Evolutionary Algorithm，IEA)[16]三种算法在处理不同用户规模的用户需求时的收益以及服务定制效率。实验中采用了2 000个用户需求，需求变化个数从0～2 000。实验中单个服务协商成本设置在[40,1 000]之间。实验结果如图5和图6所示。

从图5可以看到，本文提出的SN_CT算法在处理不同用户需求规模时，收益相比传统的服务组合算法EDMOEA有很大的优势，同时相比IEA算法，本文算法在处理不同的用户需求时，在收益方面同样稍具优势。这是由于SN_CT算法在处理过程中，每次都从成本出发，在实现服务复用的同时每次选择成本最低的解决方案满足用户需求。从图6可以看出，在执行效率方面，本文所提算法相对于IEA以及EDMOEA都有较大的优势，用户需求的规模越大，在执行效率上本文所提算法的优势越大。这可能是由于SN_CT算法利用了大粒度的服务模式而不是从原子服务出发来构造服务解决方案，从而极大加快了服务定制效率。

实验2实验2中观察了SN_CT算法在迭代处理不同用户需求时服务网络成本的变化以及原子服务复用度的变化。服务复用度是指一个原子服务参与满足服务解决方案的次数。实验2中同样采用了2 000个用户需求来进行实验，同时实验中单个服务协商成本设置在[40,1 000]之间。实验结果如图7和图8所示。

从图7可以看出，在需求数量比较少时，服务成本上升较快，曲线斜率较大。但当需求越来越大时，斜率逐渐变小。这表明当需求规模越来越大时，SN_CT算法在满足每个用户需求时的平均成本在逐渐减少。这也从侧面证明了本文算法在处理大规模用户需求时有较大的优势。从图8中可以看到，服务的平均复用度呈现上升趋势，这表面文本算法在尽可能地实现服务复用，以提高服务提供者的利益。同时从图8中可以发现曲线在某一时刻服务复用度的增大趋势减缓，这有可能是因为服务网络中导入了大量新服务。

实验3在此项实验中观察了需求的Qos约束水平不同对SN_CT算法的影响。现实服务场景中可能存在一些极端情况，即一些用户希望在较少费用情况下确期望得到的服务解决方案具有更高的服务性能水平或者较高费用情况下期望的服务性能水平却较低。实验选取了3组用户需求，每组包含200个用户需求。每组用户需求的期望输出的功能和支付的费用是固定不变的，但每组需求期望的服务QoS水平是不同的，第一组用户需求期望QoS水平较低,图中标志为Relaxed，第二组用户需求期望的QoS水平和费用一致,的图中标志为Aligned，第3组用户需求期望的QoS水平较高,图中标志为Strict。同时,实验中设置单个服务的协商成本为100。实验中总共进行了下面2个小实验来观察需求QoS水平的不同对SN_CT算法的影响。第一个实验观察了SN_CT算法在处理三组不同Qos水平的需求时，对服务收益和成本的影响；第二个实验观察了SN_CT算法在处理三组不同Qos水平的需求时，对服务网络复杂度的影响，图9和图10分别显示了实验结果。

从图9中可以看到当,用户需求期望的QoS水平为Relaxed时，收益是最高的，成本是最低的。当用户需求期望的QoS水平为Strict时正好相反。这是由于当需求期望的服务QoS水平很高时，服务网络需要寻找性能更好,价格更高的服务解决方案来满足用户需求，但是由于用户愿意支付的价格是不变的，故而造成服务解决方案定制成本的上升而服务提供者的服务收益下降。

观察图10中SN_CT算法在处理3组需求时服务网络复杂度的变化。计算了在处理3组需求时，服务网络中所包含的具体服务以及边的个数。从实验结果可以看到，随着需求期望的QoS水平升高，服务网络中包含的原子服务以及边的数量都变化不大，说明用户需求期望的QoS水平差异对服务网络的复杂度影响比较有限。

5 结束语

本文针对大规模用户需求环境下，如何实现成本有效的个性化服务定制问题，提出了一种基于需求/服务模式的大规模个性化网络服务定制方法。在本文所提出的方法中首先根据用户需求的服务质量约束对用户需求进行排序，然后采用迭代增强的策略来构建服务网络。通过定制服务网络中具体的服务子网可以生成满足用户需求的服务解决方案，从而可以最大可能地复用服务网络中的原子服务，达到优化服务提供者利益的目的。同时，在服务网络构建过程中，算法使用了经过大量实践验证的需求/服务模式，从而极大地加快了服务解决方案的定制速率。最后，在实验阶段，通过将本文提出的算法与IEA，EDMOEA算法进行对比，验证了所提方法的有效性。未来可以进一步提高服务网络在面对并发需求时的服务定制效率，通过挖掘用户需求之间的功能相似性关系，减少算法的调用次数，进一步提高服务定制算法的效率；增加对并发需求的冲突处理。