劉衛(wèi)寧 馬 剛 劉 波

重慶大學信息物理社會可信服務計算教育部重點實驗室，重慶，400044

0 引言

云制造是一種面向多用戶需求的不確定性制造［1-2］。用戶需求的多樣性和不確定性導致用戶對云制造任務的執(zhí)行要求不同，即不同用戶對云制造任務執(zhí)行各環(huán)節(jié)的關注度不盡相同。如何精確調控云制造資源和制造能力，找到一條組合云服務執(zhí)行路徑，使其整體服務質量(quality of service，QoS)最優(yōu)并滿足各子路徑中不同用戶多樣化的QoS需求，即是本文研究的云服務組合(manufacturing cloud services composition，MCSC)路徑優(yōu)選問題［3-5］。

云制造服務組合研究受啟發(fā)于服務計算(service－oriented computing，SOC)理論的相關研究成果［2，6-8］，主要包括:①任務分解技術，如基于層次任務網(hierarchical task network，HTN)規(guī)劃的方法［9-11］等;②服務發(fā)現與匹配，如基于關鍵字的Web服務發(fā)現與匹配、基于語義的Web服務發(fā)現與匹配;③服務形式化表達與驗證，如基于Petri網的Web服務組合驗證、基于自動機理論的Web服務組合驗證、基于進程代數的Web服務組合驗證等;④服務組合方法，如基于人工智能和規(guī)劃的服務組合、基于圖搜索的服務組合、基于QoS的服務組合等。但是，鑒于制造資源的多樣性、復雜性、規(guī)模性等特點，上述服務組合方法不能直接應用到制造領域的服務組合中。近年來，服務計算領域中基于QoS的服務組合方法同制造網格等面向服務的網絡化制造模式不斷融合，逐漸形成了基于QoS的制造服務組合及優(yōu)選方法體系［3-5，12-16］。但制造網格系統(tǒng)中的服務組合重在體現“分散資源集中使用”的思想，側重于實現資源協(xié)同的整體優(yōu)化目標。而云制造致力于為制造活動中的各利益主體構造可充分溝通的制造環(huán)境，體現出“分散資源集中使用”與“集中資源分散服務”的融合，其服務組合的優(yōu)化目標不僅表現在整體需求的實現，還滲透在制造全生命周期的每個環(huán)節(jié)［2］。無論是面向計算領域還是制造領域，現有的服務組合研究都集中于追求服務組合路徑的整體QoS最優(yōu)，很少關注服務組合路徑結構上的層次化特性及各層次上子路徑的不同QoS需求。

從以上分析可以看出，現有的服務組合研究存在以下問題:①一味追求服務組合整體的服務質量最優(yōu)，忽略了各層次組合過程中的局部服務質量約束，導致服務組合路徑存在服務質量瓶頸，從而影響全局的服務質量;②在QoS計算過程中，服務組合路徑的整體服務質量直接取決于基本云服務的服務質量及其整體路徑的結構特性，忽略了中間各層次的結構特性，而根據服務組合的基本原理可知，不同結構服務組合路徑的QoS值計算方法不同［8，17］，從而導致計算結果可能存在偏差。

上述問題使得既有的制造服務組合模型及組合過程與其追求全局服務質量最優(yōu)的初衷背道而馳。因此，本文在力求云服務組合全局服務質量最優(yōu)的情況下，重點考慮云服務層次性組合過程的局部服務質量保障，提出了基于層次化的云制造服務組合(hierarchicalmanufacturing cloud services composition，H－MCSC)優(yōu)選建模方法，并對模型進行了算法求解和驗證。

1 問題提出

現階段，大多數網絡化制造的研究將云服務組合分為任務分解、候選云服務推薦、云服務組合與優(yōu)選三個階段［2-5，16］。網絡化制造過程將云制造任務分解為多個原子任務，分別選取功能相匹配的服務，形成全局QoS最優(yōu)的服務組合，將制造過程和服務組合為一個順序化的任務流程。

然而，制造過程管理的相關研究表明，制造過程是層次化執(zhí)行的［9，17］。文獻［17］提出了基于層次鏈的產品裝配過程建模方法，將制造任務描述為一系列子任務按一定層次結構的聚合;文獻［9］使用基于HTN的規(guī)劃方法，建立了產品裝配序列生成的任務分解策略?；贖TN的任務規(guī)劃是當前服務組合中任務分解的重要方法［10-11］，該方法在制造任務分解中的廣泛應用正是制造過程層次化特性的有力證明。而云服務組合過程可以看成是任務分解的逆過程，所以層次化特性在云制造服務組合中也具有一般性。

本文結合云制造中服務組合的相關研究，將制造任務的層次化特性引入到云制造的服務組合過程中，提出基于 H－MCSC的模型，如圖1所示。

在圖1所描述的基于層次化的制造云服務組合過程中，首先對云制造任務進行層次化分解，每個非原子任務都可以分解為一系列的子任務(圖1a→圖1b)。找到各原子任務與功能匹配的一組服務候選集，選取服務候選集中的某個云服務并構造一個云服務組合來執(zhí)行其上層任務(圖1b→圖1c)，該上層任務又可以由這一系列組合服務的組合來執(zhí)行，最終形成一個層次化的組合服務集群(圖1d)，共同完成用戶提交的云制造任務。具體的層次化服務組合過程描述如圖2所示。

2 問題建模

2.1 問題描述

云制造的層次化服務組合是一個遞歸的迭代過程，其制造任務可按任務層次和性質分為頂級任務、原子任務和中間子任務，頂級任務即為用戶提交的云制造請求，中間子任務則是由一系列的原子任務或其他的中間子任務組合而成的非頂級任務。只有原子任務可以被單個的云服務獨立執(zhí)行，其他任務需要根據任務層次由多個云服務逐層組合執(zhí)行。顯而易見，各層次間的服務組合具有相同的迭代性質，本文特別針對3層的云服務組合問題進行研究。

圖1 基于層次化的制造云服務組合模型

基于層次化的服務組合問題形式化描述如下:

圖2 基于層次化的服務組合流程

組合優(yōu)選過程要遵循以下原則:

原則1 云服務組合路徑中的各制造云服務必須滿足云平臺最低的服務質量約束。

原則2 必須使層次化服務組合路徑中各中間層服務組合子路徑的服務質量滿足用戶對相應子任務的服務質量要求。

原則3 要盡可能使層次化云服務組合形成的最終復合云服務組合執(zhí)行路徑的整體服務質量最優(yōu)。

2.2 QoS 評估模型

受啟發(fā)于服務計算領域中基于QoS的服務組合研究，網絡化制造領域中的許多研究也采用了QoS來評價制造服務的優(yōu)劣。文獻［18］研究了制造網格中的QoS建模和評價方法，但只給出了一系列QoS屬性的概念性定義;文獻［4］針對時間、成本、可用性等QoS屬性給出了相應的量化計算方法。本文選取時間、成本、可靠度、信譽度4個具有代表性的QoS屬性為云制造服務質量的評價指標，并給出了各QoS屬性的具體定義及其量化計算方法，詳見表1。

表1 QoS屬性定義及量化方法

對于每個制造云服務RS，系統(tǒng)給出其各QoS屬性值，即可計算各服務組合路徑的QoS。文獻［7］將云計算中的服務組合路徑描述為4種類型(順序結構、并行結構、選擇結構、循環(huán)結構)，給出了其相應的QoS計算方法。文獻［6，8］直接將這4種結構引入到制造領域的服務組合QoS的計算中。本文將云制造任務分解為一系列的制造子任務序列，很顯然任務執(zhí)行路徑已經確定?？紤]到制造云服務獨占、成本高、執(zhí)行周期長等特性，云制造服務組合路徑一般不會出現選擇結構和循環(huán)結構，故本文只考慮服務組合中的順序結構和并行結構兩種情況，并據此給出了服務組合中QoS值的計算方法，詳見表2。

表2 服務組合QoS計算方法

綜上所述，定義各制造云服務RS的QoS為Q(RS)=〈T(RS)，C(RS)，Rel(RS)，Rep(RS)〉;相應的對于每個裝配任務的執(zhí)行路徑Pj，定義其QoS 為Q(Pj)=〈T(Pj)，C(Pj)，Rel(Pj)，Rep(Pj)〉;對于整個云制造任務執(zhí)行的服務組合路徑P，定義其QoS為Q(P)=〈T(P)，C(P)，Rel(P)，Rep(P)〉。

為計算服務組合路徑P的服務質量Q(P)，假設路徑P中的順序結構、并行結構的比例分別為f1(P)和f2(P)，f1(P)+f2(P)=1。

為避免路徑P的整體結構失衡造成服務質量計算偏差，將其結構特性分散到各子路徑中Pj中，分別以f1(Pj)、f2(Pj)表示服務組合路徑Pj中的順序結構與并行結構的比例，且對于任意的Pj，有f1(Pj)+f2(Pj)=1。則服務組合路徑P及其各子路徑Pj的QoS計算方法如下。

順序結構下Pj的服務質量Qseq(Pj):

并行結構下Pj的服務質量Qprl(Pj):

服務組合子路徑Pj的服務質量Q(Pj)為

順序結構下P的服務質量Qseq(P):

并行結構下P的服務質量Qprl(P):

則服務組合路徑P的服務質量Q(P)為

鑒于制造過程中各環(huán)節(jié)具有不同的重要性，用戶不僅需要追求全局最優(yōu)的服務質量，還需要使各子任務的服務組合路徑Pj的服務質量得到保障。定義用戶對各子任務Pj的最低可靠性和最低信譽度約束:

其中，Relu(Pj)、Repu(Pj)分別為用戶針對Pj對應子任務的重要性給出的最低的可靠性和信譽度保障。

綜上所述，我們將基于層次化的服務組合優(yōu)化問題表達如下:

基于層次化的服務組合優(yōu)化問題本質上是一個多目標多約束規(guī)劃問題，利用權重系數α和β，將其轉化成為了單目標規(guī)劃，其中，α和β分別為QoS中時間與價格的權重系數，滿足α+β=1;Relsys、Repsys分別為系統(tǒng)預設的云服務最低的可靠性和信譽度需求，Rel0、Rep0分別為用戶給定的全局服務組合路徑最低的可靠性和信譽度。

3 問題求解

本文提出的基于層次化的云制造服務組合模型是一個典型NP組合優(yōu)化問題，其層次性決定了其解空間為一個多維的復合型解空間，較一般的服務組合問題求解更為復雜。模擬退火算法被證明是能夠以概率1收斂到全局最優(yōu)解的智能優(yōu)化算法。考慮模型求解過程中的運算量隨服務組合層次增加而顯著增加，本文采用較為簡單的模擬退火算法進行求解，以保證模型層次化可擴展性和算法的實用性。同時，為了保證算法性能，提高算法效率，本文設計了提前剪枝的策略。

基于層次化的云制造服務組合問題的模擬退火算法求解過程如下:

(1)解空間。層次化服務組合路徑P包含一系列的子路徑P={P1，P2，…，PJ}，Pj中的節(jié)點Pjk對應候選云服務集RSSjk中的某個候選云服務RSjkh，用xjk表示云服務RSjkh在RSSjk中的序號h(為方便，以Xjk表示RSjkh)，則層次化的云服務組合問題的解空間S可表示為

①對二維解空間S，取其中的一維S［j］;

②對S［j］中的xjk，分別取Xjk所有可能的取值中可靠性和信譽度最大的元素，計算S［j］對應路徑的最大可靠性Relmax和信譽度Repmax;

③分別取Xjk所有可能的取值中可靠性和信譽度最小的元素，計算S［j］對應路徑的最小可靠性Relmin和信譽度Repmin;

④ 取(RelmaxRelmin)1/2、(Repmax+Repmin)/2 為S［j］對應子路徑的Pj的QoS約束(Relu和Repu);

⑤ 對空間S［j］所有可能出現的解S0［j］，根據式(1)、式(2)計算對應的可靠性Rel和信譽度Rep;

(3)目標函數。本文以時間T和成本C為服務質量的評價指標，在式(9)定義了基于權重系數的目標函數:

(4)約束條件。式(11)、式(12)分別定義了子路徑Pj和路徑P的QoS約束，解空間S對應的服務組合路徑必須滿足這兩個約束。

(5)新解的產生。對當前解S0取任意的xjk，根據可選的云服務，替換為x'jk，得到S0的鄰域S'，結合式(13)推導得

(6)代價函數。設新的解S'對應的服務組合路徑為P'，其代價函數Δf表示如下:

(7)接受準則。對新的解空間S'，按以下概率進行接受:

只有在新路徑滿足約束條件的情況下，才允許接受新路徑。如果Δf＜0，則接受新路徑;否則，以概率exp(－Δf/T)接受新的路徑。

(8)降溫。利用選定的降溫系數λ(0＜λ＜1)進行降溫得到新的溫度，即T←λT。λ可根據算法要求進行調整，降溫越慢，算法找到全局最優(yōu)解的可能性越大，但執(zhí)行的時間也越久。

(9)結束條件。用選定的終止溫度e，判斷退火過程是否結束。若T＜e，則算法結束，得到最終的解。

4 實驗仿真

為驗證本文中模型和算法的有效性，本文假設云制造任務MT包含4個中間子任務，每個中間子任務由4個原子任務構成，每個原子任務有4個云服務可供選擇，并在MATLAB7.1的環(huán)境中對算法進行了仿真實驗。其中，各云服務的QoS屬性值均隨機生成，各子路徑的QoS約束根據數據中組合所有可能出現的情況綜合設置(取均值等)。MT對應的服務組合路徑P有16個路徑節(jié)點，有232種組合方案。

4.1 模型的有效性驗證

(1)對隨機生成了20組數據，分別根據式(12)對不滿足子路徑約束的服務組合進行剪枝，得到其解空間大小和無約束條件下解空間大小的比，見表3。

表3 剪枝前后解空間大小的比 ‰

可以看出，根據子路徑約束提前對服務組合路徑進行剪枝，能夠使解空間大小減小到原來的1‰ ～1%，從而提高了算法的搜索效率。本文主要研究3層的服務組合，對于更多層的服務組合，效果將更為明顯。

圖3 未分層結構的QoS評價值與分層結構的比例因子

從圖3可以看出，雖然比值比較接近，但并不線性相關。從式(2)、式(5)可以看出，在不分層的情況下，并行結構的計算很容易受路徑結構影響。本文通過分層對服務進行組合，將路徑結構對QoS的影響分散到各層次的組合服務中，避免因單一考慮整體的結構特性造成QoS計算偏差。

(3)對其中某一組數據，分別計算了文中帶有子路徑約束的分層服務組合情況下的dest的值(實線)和不分層的服務組合下dest值(虛線)的概率分布，如圖4所示。

圖4 QoS評價值的區(qū)間概率曲線

從圖4可以看出，在所有的服務組合路徑中，滿足用戶對各子路徑約束的服務組合只是其中的一小部分，而且一部分全局QoS較優(yōu)的服務組合并不滿足局部QoS約束。所以，一味追求服務組合的全局最優(yōu)QoS，可能導致因為局部服務質量偏低，使得云制造任務的服務質量難以保證。

4.2 算法的有效性驗證

圖4中的虛線為利用窮舉法計算得到的層次降化服務組合下的所有QoS評價值dest的概率曲線，其全局最優(yōu)解為4.3334，本文中，降溫系數λ取0.90、0.95、0.99，對該數據分別各執(zhí)行10次，求得的最優(yōu)解如表4所示。

表4 模擬退火算法求得的最優(yōu)目標dest值

其中，當降溫系數取0.90和0.95時，找到全局最優(yōu)解(表4中帶下劃線的數值，即4.3334)的概率分別為40%和70%，當降溫系數增大到0.99或更大時，基本上能以接近1的概率找到全局最優(yōu)解。在文中給出的問題規(guī)模下，計算過程都能在以秒為單位的時間內完成。在不對解空間預先剪枝的情況下，當降溫系數小于0.999時，很難收斂到全局最優(yōu)解。

5 結論

(1)本文在分析了制造任務執(zhí)行過程層次化特性的基礎上，對云制造及其相關領域的服務組合進行了研究，提出了基于層次化的云制造服務組合模型。

(2)通過各層服務組合的QoS屬性約束，提前剔除服務組合路徑中不滿足局部QoS約束的子路徑，提高了服務組合路徑搜索的效率，避免了一味追求全局QoS最優(yōu)而忽略局部組合服務QoS過低的問題。同時，也滿足了各服務組合子路徑不同 QoS約束限制，保證了關重節(jié)點的服務質量。

(3)本文提出了層次化的云服務組合方法，分層計算組合服務的QoS值，將服務組合的結構特性均勻分布到服務組合路徑的各個層次中，避免因單一考慮整體的結構特性造成在QoS計算時產生偏差。

(4)本文對提出的層次化云制造服務組合模型進行了求解，分析了該模型對算法效率的影響，及服務組合結構均衡性對QoS的影響。

［1］李伯虎，張霖，王時龍，等.云制造——面向服務的網絡化制造新模式［J］.計算機集成制造系統(tǒng)，2010，16(1):1-7.

Li Bohu，Zhang Lin，Wang Shilong，et al.Cloud Manufacturing:a New Service－oriented Networked Manufacturing Model［J］.Computer Integrated Manufacturing Systems，2010，16(1):1-7.

［2］陶飛，張霖，郭華，等.云制造特征及云服務組合關鍵問題研究［J］.計算機集成制造系統(tǒng)，2011，17(3):477-486.

Tao Fei，Zhang Lin，Guo Hua，et al.Typical Characteristics of Cloud Manufacturing and Several Key Issues of Cloud Service Composition［J］.Computer Integrated Manufacturing Systems，2011，17(3):477-486.

［3］劉衛(wèi)寧，劉波，孫棣華.面向多任務的制造云服務組合研究［J/OL］.計算機集成制造系統(tǒng)，2012［2012-03-16］.http://www.cnki.net/kcms/detail/11.3619.TP.20120201.1556.003.htm l.

［4］Tao Fei，Zhao Dongming，Hu Yefa，et al.Resource Service Composition and Its Optimal Selection Based on ParticlesWarm Optimization in Manufacturing Grid System［J］.IEEE Transactions on Industrial Informatics，2008，4(4):315-327.

［5］Zhang L，Guo H，Tao F，et al.Flexible Management of Resource Service Composition in Cloud Manufacturing［C］//2010 IEEE International Conference on Industrial Engineering＆ Engineering Management(IE＆EM 2010).Macao，2010:2278-2282.

［6］鄧水光，黃龍濤，尹建偉，等.Web服務組合技術框架及其研究進展［J］.計算機集成制造系統(tǒng)，2011，17(2):404-412.

Deng Shuiguang，Huang Longtao，Yin Jianwei，et al.Technical Framework for Web Services Composition and Its Progress［J］.Computer Integrated Manufacturing Systems，2011，17(2):404-412.

［7］Cardoso J，Sheth A，Miller J，et al.Quality of Service for Workflows and Web Service Processes［J］.Journal ofWeb Semantics，2004，1(3):281-308.

［8］Zeng L，Benatallah B，Ngu A H H，et al.QoS － aware Middleware for Web Services Composition［J］.IEEE Transactions on Software Engineering，2004，30(5):311-327.

［9］宋涇舸，查建中，陸一平.基于虛擬裝配體綁定的產品層次化裝配序列生成［J］.北京交通大學學報，2011，35(1):145-149.

Song Jingge，Cha Jianzhong，Lu Yiping.Assembly Sequence Generation for Hierarchical Structure Product Based on Virtual Assembly Binding［J］.Journal of Beijing Jiaotong University，2011，35(1):145-149.

［10］何鳳英.基于用戶偏好的HTN規(guī)劃在網格服務組合中的研究［J］.福州大學學報(自然科學版)，2010，38(1):14-19.

He Fengying.The Research of HTN Planning in Grid Services Composition Based on User Preferences［J］.Journal of Fuzhou University(Natural Science Edition)，2010，38(1):14-19.

［11］蕭毅鴻，周獻中，朱亮，等.基于改進層級任務網絡規(guī)劃的Web服務自動組合［J］.江蘇大學學報(自然科學版)，2012，33(1):77-82.

Xiao Yihong，Zhou Xianzhong，Zhu Liang，et al.Automatic Web Services Composition Based on Improved HTN Planning［J］.Journal of Jiangsu University(Natural Science Edition)，2012，33(1):77-82.

［12］李惠林，殷國富，謝慶生，等.面向網絡化制造的制造資源組合評價方法研究［J］.計算機集成制造系統(tǒng)，2008，14(5):955-961.

Li Huilin，Yin Guofu，Xie Qingsheng，et al.Manufacturing Resource Combination Evaluation Method Oriented to Networked Manufacturing［J］.Computer Integrated Manufacturing Systems，2008，14(5):955-961.

［13］劉麗蘭，俞濤，施戰(zhàn)備.制造網格中服務質量管理系統(tǒng)的研究［J］.計算機集成制造系統(tǒng)－CIMS，2005，11(2):284-288.

Liu Lilan，Yu Tao，Shi Zhanbei.Quality of Service Management System in Manufacturing Grid［J］.Computer Integrated Manufacturing Systems － CIMS，2005，11(2):284-288.

［14］劉麗蘭，俞濤，施戰(zhàn)備.制造網格中基于服務質量的資源調度研究［J］.計算機集成制造系統(tǒng) －CIMS，2005，11(4):475-480.

Liu Lilan，Yu Tao，Shi Zhanbei.Research on QoS －based Resource Scheduling in Manufacturing Grid［J］.Computer Integrated Manufacturing Systems－CIMS，2005，11(4):475-480.

［15］陶飛，胡業(yè)發(fā)，張霖.制造網格資源服務優(yōu)化配置理論與方法［M］.北京:機械工業(yè)出版社，2010.

［16］Xu Xun.From Cloud Computing to Cloud Manufacturing［J］.Robotics and Computer－ Integrated Manufacturing，2011，2(1):75-86.

［17］侯偉偉，劉檢華，寧汝新，等.基于層次鏈的產品裝配過程建模方法［J］.計算機集成制造系統(tǒng)，2009，15(8):1522-1527.

Hou Weiwei，Liu Jianhua，Ning Ruxin，et al.Product Assembly Process Modeling Method Based on Hierarchy Chain Technique［J］.Computer Integrated Manufacturing Systems，2009，15(8):1522-1527.

［18］Tao Fei，Hu Yefa，Zhao Dongming，et al.Study on Manufacturing Grid Resource Service QoS Modeling and Evaluation［J］.International Journal of Advanced Manufacturing Technology，2009，41(9):1034-1042.