工业云环境下服务的搜索与匹配*

赵 柱，宋士琳，孟 璐，马沁怡，周茂军

(大连工业大学机械工程与自动化学院，辽宁 大连 116034)

0 引言

云制造(Cloud Manufacturing,CMfg)拥有大量制造资源，而根据需求从大量的资源中找到最合适的就显得尤为重要。

文献[1]提出了供需分类匹配 (SDCM)的实现框架，提出了一种基于基本、IOPE、QoS、综合信息匹配四阶段算法。文献[2]考虑了资源提供者和服务需求者双方的利益，设计了一种匹配机制，分析了三种不同场景下的服务匹配，并构建了基于效用理论的匹配算法，根据场景的不同调用相应的匹配机制。文献[3-4]从CMfg系统的动态性出发，提出了制造服务供需匹配仿真器(SDMSim)，并设计了一种具有7个功能子系统的基于超网络的SDMSim，构建了T-Net、S-Net和匹配网络的数学模型，为实现MR&C(制造资源和能力)的优化配置提供了支持。

但上述文献只强调对服务质量(Quality of Service，QoS)的基本信息匹配，且匹配过程中权重系数只考虑用户单方面，使结果具有较强主观性。

本文在假设单一服务需求只需要调用单一的云制造服务(Cloud Manufacturing Services，CMS)的前提下，通过本文所提到的资源匹配方法，能够快速且准确地找到合适资源，并且其结果既体现了用户的主观偏好，又具有科学性。

1 云服务的标准化描述

云服务的标准化描述是云服务搜索与匹配(S-SM)的准备工作，恰当的描述能够对服务的匹配起到良好的帮助作用。本文采用XML[5]语言进行服务描述。

定义1：为了完整概括服务和需求，采用以下定义：

S=

Basic_S=

Func_S=

QoS_S=

以上涉及参数及说明如表1所示。

表1 云制造服务的描述与参数及说明

基本属性：服务的名称，所属类别包括加工服务、软件服务、检修服务等，服务的提供者即拥有者，服务所在地点，服务状态包括“休息”、“空闲”、“未满负荷”、“满负荷”和“超负荷”等。

功能属性：功能所属类别，输入形式，输出形式，工作条件，服务效率等。

质量属性：服务时间，价格，服务收到的质量评价。

定义2：服务需求的描述大致与CMS类似，基本描述形式如下：

R=

Basic_R=

Func_R=

QoS_R=

以上涉及的参数及其说明与表1相似，需要说明的是其中信息的主体为需求者，例如Time,Cost为需求者提出的时间和成本要求。

2 云服务搜索与匹配算法

S-SM框架主要由4个核心组成：本体库为服务需求和资源描述提供领域知识，对描述中的各个概念及参数进行规范化的标注；信息解析器对需求库和本体库中的文档进行有效分解；算法库为服务的匹配提供算法基础；服务匹配器是在匹配过程中，调用所需算法来实现服务与需求间的匹配。

具体流程如图1所示，首先提出服务需求，云制造平台对资源进行规范化描述，并将其分解为基本信息，IOPE信息和QoS信息。需求也被同样分解和标注；然后遍历平台中所有的制造资源集合CS，根据预设的算法，依次对其基本信息、IOPE信息进行匹配，对不满足条件的资源从候选资源集合中删除，得到候选资源集CS2；其次根据时间窗口和成本等约束条件，对不满足条件的CS2进行过滤得到CS3；然后对QoS信息进行匹配，并利用主观赋权和客观赋权相结合的方法对QoS指标设置权重，得到CS4；最后计算综合匹配度得到最优质的候选集CS5。

图1 云服务的搜索与匹配流程

2.1 基本信息匹配

首先，针对类别和状态信息进行匹配即Class和Status，将不满足Status条件的服务(Status为“超负荷”)和Class相差较大的服务筛选掉，在这部分中引入本体树(Ontology Tree，OT)，在计算服务和需求对应节点的相似度时，计算过程如下所示：

步骤1：计算OT中连接两节点的边的权重系数:

(1)

步骤2：计算两节点间的语义距离:

(2)

步骤3：计算两节点间的匹配度:

(3)

步骤4：计算基本信息的匹配度:

(4)

式中，CRj为服务需求基本信息中第j个概念；CSij为第i个候选服务基本信息中第j个概念(1≤j≤n)；h为两概念节点间的深度；length为两概念节点间的路径长度；α为区分两相交概念间的距离，取值范围为1≤α≤2，本文α=1.4。

步骤5：设定匹配阈值ξ1:

设定ξ1=0.8，则只有当Basic(Si,R)≥0.8时，才可作为候选资源集中的一员。对所有的服务重复步骤1～5，得到候选服务集，得到基本信息匹配阶段的候选集CS1，并将其作为功能信息匹配阶段的输入服务集。

2.2 功能信息匹配

此部分主要进行IOPE匹配，将服务的输入和输出用原子动作的形式表示出来，如a(v1,v2,…,vn)=(P,E),其中P是动作输入条件集合，E是输出条件合集，构建服务需求和上一步得到的候选资源集CS1的原子动作，运用推理机进行判定，满足条件的进入候选资源集CS2进入下一阶段匹配。

2.3 QoS匹配

这一匹配分为两个阶段：第一阶段限制时间和成本；第二个阶段对剩余的资源进行QoS匹配，对权重进行主观和客观融合的方法进行计算，得到最终集合。

2.3.1 候选资源集过滤

步骤1：时间窗口过滤

首先时间窗口和候选资源时间窗口要有交集，其次任务开始时间应该选取需求和服务的最大值，最后需求所要求的时间与运输时间之和应该小于需求和服务结束时间的最小值：

(5)

步骤2：成本过滤

总成本即加工成本与运输成本之和应该小于需求者所限制的成本：

Costi+ci≤CostLimit

(6)

通过如上步骤，满足条件的服务进入候选资源集合CS3进入下一阶段的匹配。

2.3.2 计算QoS匹配度

步骤1：令QoS_S为候选资源集合中的QoS指标，则将其表示为矩阵形式，由于其各指标的量化方式不同，因此须将矩阵QoS_S标准化、归一化处理，可得到矩阵QoS_S′，如式(7)、式(8)所示：

(7)

(8)

(9)

步骤2：在步骤1的基础上，分别求得QoS_S′中每列向量(即每个QoS指标)的最优解，组成最优解向量Ra=(a1,a2,…,an)。由于QoS属性指标既有正向指标I+(即越大越优型指标，如可靠性、信誉度等)，又有负向指标I-(如时间、成本等)，因此选取最优解时需满足以下条件：

(10)

步骤3：计算候选资源Si与最优解向量间的匹配度：

(11)

在实际匹配过程中，对QoS权重的分配不同可能会得到完全不同的结果集合[6]，所以对于权重的合理分配十分重要，本文采用主观赋权法和客观赋权法相结合的方式，既满足用户需求，又具有科学性。

(1)主观赋权法-AHP

主观赋权法是利用当前主流的主观赋权法-AHP来进行判断矩阵的构建，计算各属性指标的权重系数。过程如下：

步骤1：建立各层次的判断矩阵X=(xij)n×n：xij表示属性i相对于属性j的重要性比例标度且xji=1/xij，(i=1，2，...，m；j=1，2，...，n)，由用户根据所期望属性的重要程度结合表2给出[7]。

表2 判定矩阵标度

步骤2：一致性检验：计算随机一致性比例(Consistency ratio，CR)[8-9]：

CR=CI/RI

(12)

表3 RI的取值

步骤3：计算主观权重系数:

(13)

将得到的βj进行归一化处理:

(14)

(2)客观赋权法-熵值法

作为客观赋权的有效工具，熵值法(EW)主要根据决策矩阵判断其属性指标的离散程度，从而计算其客观权重[10]。具体分为如下4个步骤：

步骤1：归一化：对候选服务资源的QoS所构成的矩阵采用max-min法进行归一化：

(15)

步骤2：计算第j个QoS属性下第i个候选资源的贡献度，即每个指标占据该指标总和的大小：

(16)

步骤3：计算QoS属性aj的熵值：

(17)

式中，K=1/ln(m)，0≤Ej≤1。

步骤4：计算客观权重系数xij:

(18)

式中，Uj=1-Ej，为第j个QoS属性下各候选资源的一致性程度。

由式(17)可得：当某一QoS属性下各候选资源的贡献度趋于一致时，Ej的取值越接近1；当完全相同时，说明该属性对服务匹配的影响程度是相同的，可以不考虑此属性的权重，即αj=0。

因此,服务中第j个QoS属性所对应的权重为：

(19)

代入到式(11)，来计算各候选服务的QoS匹配度，得到新的候选服务集CS4。

2.4 综合匹配

综合匹配度计算公式为：

Match(Si，R)=μBasic(Si，R)+γQoS(Si，Ra)

(20)

式中，μ、γ分别为基本信息匹配和QoS匹配的权重，且μ+γ=1。将结果从大到小进行排列，并组成候选服务集合CS5，反馈给用户。

3 实例验证

本文基于某CMP中CMSD提交的某一服务需求为例，对以上理论加以分析和验证。其具体信息同CMP中所提供的CMS信息如表4所示。

表4 需求和服务的描述文档 Cost单位：千元

步骤1：基本信息匹配

制造加工服务的部分本体树及其各边的权重系数如图2所示。

图2 部分制造加工服务本体树

根据图2、式(1)～式(4)及设定的阈值ξ1=0.8，得到各候选服务与需求之间基本信息匹配度为：Basic(Si,R)=(0.851 1，1，0.851 1，1，0.851 1，0.8，0.851 1),由于Basic(S6,R)≤0.8，S3的Status=“超负荷”，二者均不满足条件，所以CS1=(S1，S2，S4，S5，S7)。

步骤2：IOPE匹配

将R和CS1表示为原子动作，则R的原子动作可表示为：αR(v)=(Pr,Er),其中Pr=(Input(40Cr的合金钢；锻件；数量；精度)，(大连))，Er=(Output(零件)，合格率(100%))；CS1的原子动作可表示为：S(α1，α2，α4，α5，α7)=(P(α1，α2，α4，α5，α7),E(α1，α2，α4，α5，α7))。则利用推理机根据可满足性，得到IOPE的匹配结果为CS2=(S1，S2，S5，S7)。

步骤3：候选资源集过滤

由于需求方的位置为大连，候选集CS2中涉及的地理位置为大连和沈阳，依据经验给定运输时间ti(沈阳-大连)=1d，运输成本ci(沈阳-大连)=0.3，而大连-大连的ti和ci可忽略不计。因此，根据式(5)、式(6)可得：S5不满足条件，将其过滤，可得CS3=(S1，S2，S7)。

步骤4：QoS匹配

(1)求归一化矩阵及最优解

QoS_S={Quality，Reliability，Cost，Avaliability，Credit}，根据CS3及式(7)～式(10)，构建QoS_S矩阵，并利用MATLAB求归一化矩阵QoS_S′矩阵及最优解向量：

Ra=(0.344 9,0.341 6,0.317 3,0.346 7,0.348 9)。

(2)计算主观权重βj

根据用户所描述的各指标的相对重要性及表2，构建判断矩阵X：

(3)计算客观权重

根据式(15)～式(18)利用MATLAB计算可得：Ej=(0.605 0，0.466 8，0.620 4，0.565 3，0.601 7)，αj=(0.184 5,0.249 1,0.177 3,0.203 0,0.186 1)。

(4)计算QoS匹配度

根据式(19)计算组合权重，然后根据式(11)计算候选服务Si与Ra的匹配度，ωj=(0.499，0.122 1，0.135 9，0.072 2，0.239 9)，QoS(S，Ra)=(0.983 62，0.983 65，0.969 9)。因此，可得CS4=(S1，S2，S7)。

步骤5：综合匹配

令μ=0.4、γ=0.6，根据式(20)，可以计算得到，Match(S1,R)=0.930 6,Match(S2,R)=0.990 19,Match(S7,R)=0.922 38。

按照从大到小排序：CS5=(S2，S1，S7)。

通常查全率Recall和查准率Precision来衡量匹配算法的优劣性。其中Recall是指符合要求的候选服务集与返回的服务集的交集占前者的比例，Precision是指符合要求的候选服务集与返回的服务集的交集占后者的比例。如表5所示，将本文的匹配结果与文献[1]的匹配结果相比较，可知本文匹配算法的查准率有明显提高。

表5 不同算法的匹配结果比较

4 总结

针对云制造环境下的资源匹配问题，本文提出了一种服务资源描述方法，在此基础上，设计了基于基本信息、功能信息、QoS的云服务匹配算法，并且在QoS匹配过程中融合主观赋权法和客观赋权法。通过与其他算法进行比较，证明了该方法可以明显提高匹配准确度。