工業(yè)云環(huán)境下服務(wù)的搜索與匹配*

趙 柱，宋士琳，孟 璐，馬沁怡，周茂軍

(大連工業(yè)大學(xué)機(jī)械工程與自動(dòng)化學(xué)院，遼寧 大連 116034)

0 引言

云制造(Cloud Manufacturing,CMfg)擁有大量制造資源，而根據(jù)需求從大量的資源中找到最合適的就顯得尤為重要。

文獻(xiàn)[1]提出了供需分類匹配 (SDCM)的實(shí)現(xiàn)框架，提出了一種基于基本、IOPE、QoS、綜合信息匹配四階段算法。文獻(xiàn)[2]考慮了資源提供者和服務(wù)需求者雙方的利益，設(shè)計(jì)了一種匹配機(jī)制，分析了三種不同場(chǎng)景下的服務(wù)匹配，并構(gòu)建了基于效用理論的匹配算法，根據(jù)場(chǎng)景的不同調(diào)用相應(yīng)的匹配機(jī)制。文獻(xiàn)[3-4]從CMfg系統(tǒng)的動(dòng)態(tài)性出發(fā)，提出了制造服務(wù)供需匹配仿真器(SDMSim)，并設(shè)計(jì)了一種具有7個(gè)功能子系統(tǒng)的基于超網(wǎng)絡(luò)的SDMSim，構(gòu)建了T-Net、S-Net和匹配網(wǎng)絡(luò)的數(shù)學(xué)模型，為實(shí)現(xiàn)MR&C(制造資源和能力)的優(yōu)化配置提供了支持。

但上述文獻(xiàn)只強(qiáng)調(diào)對(duì)服務(wù)質(zhì)量(Quality of Service，QoS)的基本信息匹配，且匹配過程中權(quán)重系數(shù)只考慮用戶單方面，使結(jié)果具有較強(qiáng)主觀性。

本文在假設(shè)單一服務(wù)需求只需要調(diào)用單一的云制造服務(wù)(Cloud Manufacturing Services，CMS)的前提下，通過本文所提到的資源匹配方法，能夠快速且準(zhǔn)確地找到合適資源，并且其結(jié)果既體現(xiàn)了用戶的主觀偏好，又具有科學(xué)性。

1 云服務(wù)的標(biāo)準(zhǔn)化描述

云服務(wù)的標(biāo)準(zhǔn)化描述是云服務(wù)搜索與匹配(S-SM)的準(zhǔn)備工作，恰當(dāng)?shù)拿枋瞿軌驅(qū)Ψ?wù)的匹配起到良好的幫助作用。本文采用XML[5]語(yǔ)言進(jìn)行服務(wù)描述。

定義1：為了完整概括服務(wù)和需求，采用以下定義：

S=

Basic_S=

Func_S=

QoS_S=

以上涉及參數(shù)及說明如表1所示。

表1 云制造服務(wù)的描述與參數(shù)及說明

基本屬性：服務(wù)的名稱，所屬類別包括加工服務(wù)、軟件服務(wù)、檢修服務(wù)等，服務(wù)的提供者即擁有者，服務(wù)所在地點(diǎn)，服務(wù)狀態(tài)包括“休息”、“空閑”、“未滿負(fù)荷”、“滿負(fù)荷”和“超負(fù)荷”等。

功能屬性：功能所屬類別，輸入形式，輸出形式，工作條件，服務(wù)效率等。

質(zhì)量屬性：服務(wù)時(shí)間，價(jià)格，服務(wù)收到的質(zhì)量評(píng)價(jià)。

定義2：服務(wù)需求的描述大致與CMS類似，基本描述形式如下：

R=

Basic_R=

Func_R=

QoS_R=

以上涉及的參數(shù)及其說明與表1相似，需要說明的是其中信息的主體為需求者，例如Time,Cost為需求者提出的時(shí)間和成本要求。

2 云服務(wù)搜索與匹配算法

S-SM框架主要由4個(gè)核心組成：本體庫(kù)為服務(wù)需求和資源描述提供領(lǐng)域知識(shí)，對(duì)描述中的各個(gè)概念及參數(shù)進(jìn)行規(guī)范化的標(biāo)注；信息解析器對(duì)需求庫(kù)和本體庫(kù)中的文檔進(jìn)行有效分解；算法庫(kù)為服務(wù)的匹配提供算法基礎(chǔ)；服務(wù)匹配器是在匹配過程中，調(diào)用所需算法來實(shí)現(xiàn)服務(wù)與需求間的匹配。

具體流程如圖1所示，首先提出服務(wù)需求，云制造平臺(tái)對(duì)資源進(jìn)行規(guī)范化描述，并將其分解為基本信息，IOPE信息和QoS信息。需求也被同樣分解和標(biāo)注；然后遍歷平臺(tái)中所有的制造資源集合CS，根據(jù)預(yù)設(shè)的算法，依次對(duì)其基本信息、IOPE信息進(jìn)行匹配，對(duì)不滿足條件的資源從候選資源集合中刪除，得到候選資源集CS2；其次根據(jù)時(shí)間窗口和成本等約束條件，對(duì)不滿足條件的CS2進(jìn)行過濾得到CS3；然后對(duì)QoS信息進(jìn)行匹配，并利用主觀賦權(quán)和客觀賦權(quán)相結(jié)合的方法對(duì)QoS指標(biāo)設(shè)置權(quán)重，得到CS4；最后計(jì)算綜合匹配度得到最優(yōu)質(zhì)的候選集CS5。

圖1 云服務(wù)的搜索與匹配流程

2.1 基本信息匹配

首先，針對(duì)類別和狀態(tài)信息進(jìn)行匹配即Class和Status，將不滿足Status條件的服務(wù)(Status為“超負(fù)荷”)和Class相差較大的服務(wù)篩選掉，在這部分中引入本體樹(Ontology Tree，OT)，在計(jì)算服務(wù)和需求對(duì)應(yīng)節(jié)點(diǎn)的相似度時(shí)，計(jì)算過程如下所示：

步驟1：計(jì)算OT中連接兩節(jié)點(diǎn)的邊的權(quán)重系數(shù):

(1)

步驟2：計(jì)算兩節(jié)點(diǎn)間的語(yǔ)義距離:

(2)

步驟3：計(jì)算兩節(jié)點(diǎn)間的匹配度:

(3)

步驟4：計(jì)算基本信息的匹配度:

(4)

式中，CRj為服務(wù)需求基本信息中第j個(gè)概念；CSij為第i個(gè)候選服務(wù)基本信息中第j個(gè)概念(1≤j≤n)；h為兩概念節(jié)點(diǎn)間的深度；length為兩概念節(jié)點(diǎn)間的路徑長(zhǎng)度；α為區(qū)分兩相交概念間的距離，取值范圍為1≤α≤2，本文α=1.4。

步驟5：設(shè)定匹配閾值ξ1:

設(shè)定ξ1=0.8，則只有當(dāng)Basic(Si,R)≥0.8時(shí)，才可作為候選資源集中的一員。對(duì)所有的服務(wù)重復(fù)步驟1～5，得到候選服務(wù)集，得到基本信息匹配階段的候選集CS1，并將其作為功能信息匹配階段的輸入服務(wù)集。

2.2 功能信息匹配

此部分主要進(jìn)行IOPE匹配，將服務(wù)的輸入和輸出用原子動(dòng)作的形式表示出來，如a(v1,v2,…,vn)=(P,E),其中P是動(dòng)作輸入條件集合，E是輸出條件合集，構(gòu)建服務(wù)需求和上一步得到的候選資源集CS1的原子動(dòng)作，運(yùn)用推理機(jī)進(jìn)行判定，滿足條件的進(jìn)入候選資源集CS2進(jìn)入下一階段匹配。

2.3 QoS匹配

這一匹配分為兩個(gè)階段：第一階段限制時(shí)間和成本；第二個(gè)階段對(duì)剩余的資源進(jìn)行QoS匹配，對(duì)權(quán)重進(jìn)行主觀和客觀融合的方法進(jìn)行計(jì)算，得到最終集合。

2.3.1 候選資源集過濾

步驟1：時(shí)間窗口過濾

首先時(shí)間窗口和候選資源時(shí)間窗口要有交集，其次任務(wù)開始時(shí)間應(yīng)該選取需求和服務(wù)的最大值，最后需求所要求的時(shí)間與運(yùn)輸時(shí)間之和應(yīng)該小于需求和服務(wù)結(jié)束時(shí)間的最小值：

(5)

步驟2：成本過濾

總成本即加工成本與運(yùn)輸成本之和應(yīng)該小于需求者所限制的成本：

Costi+ci≤CostLimit

(6)

通過如上步驟，滿足條件的服務(wù)進(jìn)入候選資源集合CS3進(jìn)入下一階段的匹配。

2.3.2 計(jì)算QoS匹配度

步驟1：令QoS_S為候選資源集合中的QoS指標(biāo)，則將其表示為矩陣形式，由于其各指標(biāo)的量化方式不同，因此須將矩陣QoS_S標(biāo)準(zhǔn)化、歸一化處理，可得到矩陣QoS_S′，如式(7)、式(8)所示：

(7)

(8)

(9)

步驟2：在步驟1的基礎(chǔ)上，分別求得QoS_S′中每列向量(即每個(gè)QoS指標(biāo))的最優(yōu)解，組成最優(yōu)解向量Ra=(a1,a2,…,an)。由于QoS屬性指標(biāo)既有正向指標(biāo)I+(即越大越優(yōu)型指標(biāo)，如可靠性、信譽(yù)度等)，又有負(fù)向指標(biāo)I-(如時(shí)間、成本等)，因此選取最優(yōu)解時(shí)需滿足以下條件：

(10)

步驟3：計(jì)算候選資源Si與最優(yōu)解向量間的匹配度：

(11)

在實(shí)際匹配過程中，對(duì)QoS權(quán)重的分配不同可能會(huì)得到完全不同的結(jié)果集合[6]，所以對(duì)于權(quán)重的合理分配十分重要，本文采用主觀賦權(quán)法和客觀賦權(quán)法相結(jié)合的方式，既滿足用戶需求，又具有科學(xué)性。

(1)主觀賦權(quán)法-AHP

主觀賦權(quán)法是利用當(dāng)前主流的主觀賦權(quán)法-AHP來進(jìn)行判斷矩陣的構(gòu)建，計(jì)算各屬性指標(biāo)的權(quán)重系數(shù)。過程如下：

步驟1：建立各層次的判斷矩陣X=(xij)n×n：xij表示屬性i相對(duì)于屬性j的重要性比例標(biāo)度且xji=1/xij，(i=1，2，...，m；j=1，2，...，n)，由用戶根據(jù)所期望屬性的重要程度結(jié)合表2給出[7]。

表2 判定矩陣標(biāo)度

步驟2：一致性檢驗(yàn)：計(jì)算隨機(jī)一致性比例(Consistency ratio，CR)[8-9]：

CR=CI/RI

(12)

表3 RI的取值

步驟3：計(jì)算主觀權(quán)重系數(shù):

(13)

將得到的βj進(jìn)行歸一化處理:

(14)

(2)客觀賦權(quán)法-熵值法

作為客觀賦權(quán)的有效工具，熵值法(EW)主要根據(jù)決策矩陣判斷其屬性指標(biāo)的離散程度，從而計(jì)算其客觀權(quán)重[10]。具體分為如下4個(gè)步驟：

步驟1：歸一化：對(duì)候選服務(wù)資源的QoS所構(gòu)成的矩陣采用max-min法進(jìn)行歸一化：

(15)

步驟2：計(jì)算第j個(gè)QoS屬性下第i個(gè)候選資源的貢獻(xiàn)度，即每個(gè)指標(biāo)占據(jù)該指標(biāo)總和的大?。?/p>

(16)

步驟3：計(jì)算QoS屬性aj的熵值：

(17)

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

步驟4：計(jì)算客觀權(quán)重系數(shù)xij:

(18)

式中，Uj=1-Ej，為第j個(gè)QoS屬性下各候選資源的一致性程度。

由式(17)可得：當(dāng)某一QoS屬性下各候選資源的貢獻(xiàn)度趨于一致時(shí)，Ej的取值越接近1；當(dāng)完全相同時(shí)，說明該屬性對(duì)服務(wù)匹配的影響程度是相同的，可以不考慮此屬性的權(quán)重，即αj=0。

因此,服務(wù)中第j個(gè)QoS屬性所對(duì)應(yīng)的權(quán)重為：

(19)

代入到式(11)，來計(jì)算各候選服務(wù)的QoS匹配度，得到新的候選服務(wù)集CS4。

2.4 綜合匹配

綜合匹配度計(jì)算公式為：

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

(20)

式中，μ、γ分別為基本信息匹配和QoS匹配的權(quán)重，且μ+γ=1。將結(jié)果從大到小進(jìn)行排列，并組成候選服務(wù)集合CS5，反饋給用戶。

3 實(shí)例驗(yàn)證

本文基于某CMP中CMSD提交的某一服務(wù)需求為例，對(duì)以上理論加以分析和驗(yàn)證。其具體信息同CMP中所提供的CMS信息如表4所示。

表4 需求和服務(wù)的描述文檔 Cost單位：千元

步驟1：基本信息匹配

制造加工服務(wù)的部分本體樹及其各邊的權(quán)重系數(shù)如圖2所示。

圖2 部分制造加工服務(wù)本體樹

根據(jù)圖2、式(1)～式(4)及設(shè)定的閾值ξ1=0.8，得到各候選服務(wù)與需求之間基本信息匹配度為：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=“超負(fù)荷”，二者均不滿足條件，所以CS1=(S1，S2，S4，S5，S7)。

步驟2：IOPE匹配

將R和CS1表示為原子動(dòng)作，則R的原子動(dòng)作可表示為：αR(v)=(Pr,Er),其中Pr=(Input(40Cr的合金鋼；鍛件；數(shù)量；精度)，(大連))，Er=(Output(零件)，合格率(100%))；CS1的原子動(dòng)作可表示為：S(α1，α2，α4，α5，α7)=(P(α1，α2，α4，α5，α7),E(α1，α2，α4，α5，α7))。則利用推理機(jī)根據(jù)可滿足性，得到IOPE的匹配結(jié)果為CS2=(S1，S2，S5，S7)。

步驟3：候選資源集過濾

由于需求方的位置為大連，候選集CS2中涉及的地理位置為大連和沈陽(yáng)，依據(jù)經(jīng)驗(yàn)給定運(yùn)輸時(shí)間ti(沈陽(yáng)-大連)=1d，運(yùn)輸成本ci(沈陽(yáng)-大連)=0.3，而大連-大連的ti和ci可忽略不計(jì)。因此，根據(jù)式(5)、式(6)可得：S5不滿足條件，將其過濾，可得CS3=(S1，S2，S7)。

步驟4：QoS匹配

(1)求歸一化矩陣及最優(yōu)解

QoS_S={Quality，Reliability，Cost，Avaliability，Credit}，根據(jù)CS3及式(7)～式(10)，構(gòu)建QoS_S矩陣，并利用MATLAB求歸一化矩陣QoS_S′矩陣及最優(yōu)解向量：

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

(2)計(jì)算主觀權(quán)重βj

根據(jù)用戶所描述的各指標(biāo)的相對(duì)重要性及表2，構(gòu)建判斷矩陣X：

(3)計(jì)算客觀權(quán)重

根據(jù)式(15)～式(18)利用MATLAB計(jì)算可得：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)計(jì)算QoS匹配度

根據(jù)式(19)計(jì)算組合權(quán)重，然后根據(jù)式(11)計(jì)算候選服務(wù)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，根據(jù)式(20)，可以計(jì)算得到，Match(S1,R)=0.930 6,Match(S2,R)=0.990 19,Match(S7,R)=0.922 38。

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

通常查全率Recall和查準(zhǔn)率Precision來衡量匹配算法的優(yōu)劣性。其中Recall是指符合要求的候選服務(wù)集與返回的服務(wù)集的交集占前者的比例，Precision是指符合要求的候選服務(wù)集與返回的服務(wù)集的交集占后者的比例。如表5所示，將本文的匹配結(jié)果與文獻(xiàn)[1]的匹配結(jié)果相比較，可知本文匹配算法的查準(zhǔn)率有明顯提高。

表5 不同算法的匹配結(jié)果比較

4 總結(jié)

針對(duì)云制造環(huán)境下的資源匹配問題，本文提出了一種服務(wù)資源描述方法，在此基礎(chǔ)上，設(shè)計(jì)了基于基本信息、功能信息、QoS的云服務(wù)匹配算法，并且在QoS匹配過程中融合主觀賦權(quán)法和客觀賦權(quán)法。通過與其他算法進(jìn)行比較，證明了該方法可以明顯提高匹配準(zhǔn)確度。