工業云環境下服務的搜索與匹配*

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

(大連工業大學機械工程與自動化學院，遼寧 大連 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匹配過程中融合主觀賦權法和客觀賦權法。通過與其他算法進行比較，證明了該方法可以明顯提高匹配準確度。