基于QoS的制造云服務(wù)組合優(yōu)選問題研究*

唐　雨，汪永超，王　宇

(四川大學(xué) 制造科學(xué)與工程學(xué)院，成都　610065)

?

基于QoS的制造云服務(wù)組合優(yōu)選問題研究*

唐雨，汪永超，王宇

(四川大學(xué) 制造科學(xué)與工程學(xué)院，成都610065)

摘要：基于云制造的QoS(Quality of Service)屬性分析了制造云服務(wù)的組合優(yōu)選問題，建立了該問題的以時(shí)間、費(fèi)用、信譽(yù)和可靠性為目標(biāo)的云服務(wù)組合數(shù)學(xué)模型。提出了結(jié)合層次分析法和改進(jìn)的粒子群算法對(duì)該模型進(jìn)行求解的優(yōu)化方法。為了分析用戶需求，細(xì)化了每個(gè)QoS屬性，形成了云服務(wù)屬性層次，采用層次分析法確定各屬性的權(quán)重。改進(jìn)的粒子群算法則可以快速有效地收斂到最優(yōu)解。這種優(yōu)化方法既彌補(bǔ)了以往單一優(yōu)化方法的不足，同時(shí)又能深入分析用戶對(duì)云服務(wù)的需求，找到滿足用戶需求動(dòng)態(tài)變化的云服務(wù)組合方案。

關(guān)鍵詞：云制造；云服務(wù)組合；粒子群算法；層次分析法

0引言

在我國制造業(yè)面臨瓶頸的背景下,為了加快我國制造業(yè)實(shí)現(xiàn)“敏捷制造”、“服務(wù)型制造”、“綠色制造”的新型制造模式，李伯虎院士與其團(tuán)隊(duì)于2009年提出了“云制造”的理念。“云制造”是一種面向服務(wù)的、高效低耗和基于知識(shí)的網(wǎng)絡(luò)化敏捷制造新模式，是現(xiàn)有云計(jì)算和現(xiàn)有制造業(yè)信息化中的網(wǎng)絡(luò)化制造、ASp 平臺(tái)、制造網(wǎng)格等概念和技術(shù)的延伸和拓展[1]。隨后于2012年李伯虎院士又提出了云制造的關(guān)鍵技術(shù)，簡(jiǎn)述了云制造的技術(shù)難點(diǎn)和技術(shù)途徑，包括物聯(lián)化技術(shù)、虛擬化技術(shù)、服務(wù)化技術(shù)、協(xié)同化技術(shù)及智能化技術(shù)[2]。在這些關(guān)鍵技術(shù)中，服務(wù)化技術(shù)被討論的很多，其需要解決的難點(diǎn)主要包括資源/能力服務(wù)的描述、發(fā)現(xiàn)、匹配、組合、調(diào)度等。從制造云的基本構(gòu)造制造云服務(wù)(簡(jiǎn)稱云服務(wù))來看，大量的云服務(wù)按一定的規(guī)則聚合在一起所形成的動(dòng)態(tài)云服務(wù)中心，是云制造系統(tǒng)構(gòu)架的核心，能透明地為用戶提供可靠的、廉價(jià)的、按需使用的產(chǎn)品全生命周期應(yīng)用服務(wù)[3]。所以制造云服務(wù)的組合優(yōu)選對(duì)云制造服務(wù)的質(zhì)量有決定性的影響，于是出現(xiàn)了很多針對(duì)制造服務(wù)云選擇和組合優(yōu)化的方法。

目前制造云服務(wù)的組合優(yōu)選大多采用單一的非線性的進(jìn)化方法，如遺傳算法[4]，粒子群算法[5]，蟻群算法[6]，人工神經(jīng)網(wǎng)絡(luò)[7]等。雖然這些方法都得到了優(yōu)化結(jié)果但是可能存在編碼誤差大，易陷入局部最優(yōu)、早熟收斂的問題而不能保證解的優(yōu)越性。本文提出將層次分析法和改進(jìn)的粒子群算法結(jié)合的方式求解該組合優(yōu)選問題，即基于制造云的QoS屬性，同時(shí)建立云服務(wù)QoS層次分析結(jié)構(gòu)，讓用戶基于需求對(duì)QoS屬性進(jìn)行打分，結(jié)合層次分析法(Analytic Hierarchy process，AHp)得到各指標(biāo)的權(quán)重，然后構(gòu)造云服務(wù)組合與優(yōu)選問題模型，采用改進(jìn)的粒子群算法收斂到滿足用戶需求的最優(yōu)制造云服務(wù)組合。

1云制造服務(wù)相關(guān)概念

1.1制造云服務(wù)、制造云及云服務(wù)執(zhí)行路徑的關(guān)系

(1)制造云服務(wù)(Cloud Service，CS)是通過采用物聯(lián)網(wǎng)、云化技術(shù)，將分散的制造資源和和能力進(jìn)行封裝的產(chǎn)物，是云制造的基本功能構(gòu)成(云滴)。CS的Qos屬性就是對(duì)云服務(wù)質(zhì)量描述

(2)制造云(Manufacturing Cloud，MC)則是由一組功能屬性相同但非功能屬性QoS不同的CS聚合形成的CS集合。

(3)云服務(wù)執(zhí)行路徑(Cloud Service Executing path，CSEp)，由于制造任務(wù)一般被分解為多個(gè)子任務(wù)。每個(gè)子任務(wù)與一個(gè)制造云(從中選取一個(gè)合適的云服務(wù))相對(duì)應(yīng)，所以多個(gè)云服務(wù)按一定順序執(zhí)行就構(gòu)成了一條CSEp，對(duì)應(yīng)一個(gè)制造任務(wù)，可以描述為CSEp=[8]。制造云服務(wù)、制造云及云服務(wù)執(zhí)行路徑之間的關(guān)系見圖1。

圖1　制造云服務(wù)、制造云及云服務(wù)執(zhí)行路徑關(guān)系圖

1.2制造云服務(wù)的QoS

制造云服務(wù)的服務(wù)質(zhì)量QoS屬性包括云服務(wù)運(yùn)行時(shí)間T，費(fèi)用C，信譽(yù)等級(jí)Rep，可靠性R，其形象化描述為：

QoSCS=

每個(gè)云服務(wù)有QoS屬性，那么有云服務(wù)組合而成的云服務(wù)執(zhí)行路徑pi的QoS屬性可以描述為：

QoS(pi)=

2云服務(wù)QoS屬性量化

在滿足云服務(wù)功能匹配的基礎(chǔ)上，云服務(wù)的選擇和組合優(yōu)化過程實(shí)際就是對(duì)云服務(wù)執(zhí)行路徑QoS屬性的優(yōu)化即對(duì)QoS(pi)的優(yōu)化。云服務(wù)執(zhí)行路徑分為4種基本模型(順序結(jié)構(gòu)、并行結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu))，設(shè)每種模型中包含n個(gè)云服務(wù){(diào)CS1,CS2,…CSn} ，①順序結(jié)構(gòu)中n個(gè)CS串行執(zhí)行；②并行結(jié)構(gòu)中n個(gè)CS同時(shí)執(zhí)行；③選擇結(jié)構(gòu)中n個(gè)CS，組合服務(wù)只選擇其中m(m

表1　四種模型對(duì)應(yīng)的QoS(pi)計(jì)算方法

3AHp確定云服務(wù)QoS權(quán)向量

基于云服務(wù)的QoS屬性，本文選取時(shí)間T、費(fèi)用C、信譽(yù)等級(jí)Rep及可靠性R四個(gè)屬性，每一屬性又分別包含更為詳細(xì)的子屬性，從而對(duì)云服務(wù)進(jìn)行綜合分析評(píng)價(jià)。制造云服務(wù)QoS屬性層次如圖2所示，一級(jí)指標(biāo)由時(shí)間A1、費(fèi)用A2、信譽(yù)等級(jí)A3及可靠性A4組成，二級(jí)指標(biāo)由響應(yīng)時(shí)間B1、執(zhí)行時(shí)間B2、運(yùn)輸時(shí)間B3等12項(xiàng)指標(biāo)組成。

圖2　制造云服務(wù)QoS屬性層次

依據(jù)AHp法的標(biāo)度及含義(如表2所示)，基于客戶對(duì)云服務(wù)的具體需求對(duì)各屬性及其子屬性的權(quán)重進(jìn)行兩兩比較，可得到屬性層和子屬性層兩級(jí)指標(biāo)的判斷矩陣，借助層次分析軟件最終得到基于客戶需求的云服務(wù)QoS各屬性的權(quán)向量[9]：

α=(α1,α2,α3,α4)

4建模與求解方法

4.1云服務(wù)組合優(yōu)選問題建模

從本文已經(jīng)建立的QoS模型中的四個(gè)屬性考慮，云服務(wù)的組合優(yōu)選結(jié)果應(yīng)該滿足運(yùn)行時(shí)間盡可能短、費(fèi)用盡可能低、信譽(yù)盡可能好、可靠性盡可能高，所以可以建立云服務(wù)組合優(yōu)選問題模型，其表達(dá)式如下：

minZ(pi)=α1T(pi)+α2C(pi)+

α3/Rep(pi)+α4/R(pi)

(1)

式(1)中的α1、α2、α3、α4分別是通過層次分析法確定的QoS各屬性的權(quán)重。因?yàn)楣讲捎玫氖乔竽繕?biāo)函數(shù)最小值的方法，而信譽(yù)和可靠性越大越好，所以這里取其倒數(shù)。因此使得目標(biāo)函數(shù)Z(pi)值最小的云服務(wù)組合執(zhí)行路徑pi就是該云服務(wù)組合優(yōu)化問題的最優(yōu)解。下面將采用改進(jìn)的粒子群算法進(jìn)行求解。

4.2模型求解方法

4.2.1改進(jìn)的粒子群算法說明

(1)粒子群算法(pSO)是在1995年提出的一種進(jìn)化計(jì)算算法，對(duì)pSO算法的研究已經(jīng)有很多了，這里不再贅述，只是使用其標(biāo)志性的迭代更新公式：

(2)

(3)

(2)改進(jìn)的粒子群算法則旨在避免原算法過早陷入局部最優(yōu)，引入遺傳算法算法中的交叉算子，同時(shí)對(duì)pSO算法中的參數(shù)作動(dòng)態(tài)調(diào)整。采用如下公式對(duì)r1、r2進(jìn)行優(yōu)化：

(4)

慣性因子ω是一個(gè)控制參數(shù)，一般希望在搜索前期ω足夠大，使算法有很好的全局搜索能力，而在后期ω可以自動(dòng)減小增強(qiáng)局部搜索能力，加快收斂速度，提高搜索精度，所以對(duì)ω進(jìn)行動(dòng)態(tài)改進(jìn)，經(jīng)大量實(shí)驗(yàn)取其初值為0.91，動(dòng)態(tài)變化公式如下：

(5)

式中：t為當(dāng)前進(jìn)化代數(shù)；T為最大進(jìn)化代數(shù)。

(6)

4.2.2算法求解過程

上文中已經(jīng)闡述了改進(jìn)的粒子群算法的主要公式，該算法的求解步驟如下：

①粒子群初始化，由一個(gè)制造任務(wù)分解成的n個(gè)子任務(wù)構(gòu)成一條云服務(wù)執(zhí)行路徑pi，與pSO算法中的粒子概念相對(duì)應(yīng)。在初始化時(shí)，隨機(jī)組合云服務(wù)生成規(guī)模稍大的初始種群Cp以便擴(kuò)大搜索范圍，給定種群規(guī)模p，然后依次遍歷整個(gè)初始粒子群，找出相似性小的前p個(gè)粒子，作為初始粒子群pS。輸出初始粒子群pS，初始全局最優(yōu)位置gBest0，初始個(gè)體最優(yōu)位置pBest0。

②參數(shù)設(shè)置，按照公式(4)、(5)為r1、r2和ω設(shè)定初值和確定動(dòng)態(tài)變化規(guī)律。

③適應(yīng)度計(jì)算，評(píng)價(jià)粒子群中每個(gè)粒子的適應(yīng)度，將最優(yōu)粒子的位置作為pBesti和gBesti輸出，適應(yīng)度按公式(7)計(jì)算，公式中的Z(pi)見公式(1)，fitness(pi)的值越大，粒子的適應(yīng)度越高，pi的質(zhì)量也就越好。

(7)

④粒子群更新，是pSO算法的核心內(nèi)容，是優(yōu)化粒子群尋找理想解的關(guān)鍵。本文粒子群中的每個(gè)粒子的速度和位置按公式(2)和(3)更新。輸出更新后每個(gè)粒子的位置并以此計(jì)算pBesti+1和gBesti+1。

經(jīng)過多次進(jìn)化更新，粒子群將逐步靠近最優(yōu)解，最終獲得gBest為最優(yōu)的云服務(wù)組合執(zhí)行路徑。

5結(jié)束語

本文在分析云服務(wù)組合優(yōu)選這一云制造關(guān)鍵問題后，基于目前云服務(wù)QoS屬性，并細(xì)化成子屬性建立了QoS屬性層次體系，以方便用戶基于需求對(duì)云服務(wù)的各個(gè)屬性進(jìn)行賦權(quán)，同時(shí)建立云服務(wù)組合優(yōu)化問題模型，為避免pSO算法易陷入局部最優(yōu)以及早熟收斂的問題，而采用引入遺傳算法交叉算子的改進(jìn)的粒子群算法對(duì)模型求解。這種層次分析法和改進(jìn)的粒子群算法相結(jié)合的方式既彌補(bǔ)了以往單一優(yōu)化方法的不足，同時(shí)又能深入分析用戶對(duì)云服務(wù)的需求，找到滿足用戶需求動(dòng)態(tài)變化的云服務(wù)組合方案。

[參考文獻(xiàn)]

[1] 李伯虎,張霖,王時(shí)龍,等. 云制造——面向服務(wù)的網(wǎng)絡(luò)化制造新模式[J].計(jì)算機(jī)集成制造系統(tǒng),2010,16(1):1-7,16.

[2] 李伯虎,張霖,任磊,等. 云制造典型特征、關(guān)鍵技術(shù)與應(yīng)用[J].計(jì)算機(jī)集成制造系統(tǒng),2012,18(7):1345-1356.

[3] 張霖,羅永亮,陶飛,等.制造云構(gòu)建關(guān)鍵技術(shù)研究[J].計(jì)算機(jī)集成制造系統(tǒng)2010,16(11):2510-2520.

[4] Zhang Liangjie,Li Bing.Requirements Driven Dynamic Services Composition for Web Services and Grid Solutions[J].Journal of Grid Computing,2004,2(2):121.

[5] 范小芹,蔣昌俊,方賢文,等. 基于離散微粒群算法的動(dòng)態(tài)Web服務(wù)選擇[J]. 計(jì)算機(jī)研究與發(fā)展,2010,47(1):147-156.

[6] 倪志偉,王會(huì)穎,吳昊. 基于MapReduce和多目標(biāo)蟻群算法的制造云服務(wù)動(dòng)態(tài)選擇算法[J]. 中國機(jī)械工程,2014,25(20):2751-2760.

[7] 楊輝,謝慶生. 基于人工神經(jīng)網(wǎng)絡(luò)的動(dòng)態(tài)聯(lián)盟制造資源評(píng)估方法[J]. 貴州工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2005,34(4):54-58.

[8] 張以文,張鈴,錢付蘭,等.云制造模式下云服務(wù)選擇算法研究[J].小型微型計(jì)算機(jī)系統(tǒng),2014,35(11):2390-2395.

[9] 陳浩,袁逸萍,李曉娟,等. 基于QoS的云制造制造資源組合評(píng)價(jià)方法[J]. 組合機(jī)床與自動(dòng)化加工技術(shù),2013(12):25-28,32.

[10] 李一鳴. 基于交叉變異粒子群算法的復(fù)雜多任務(wù)制造云服務(wù)組合研究[D].重慶:重慶大學(xué),2013.

(編輯李秀敏)

Study on Optimization of Manufacturing Cloud Services Composition Based on QoS

TANG Yu，WANG Yong-chao，WANG Yu

(School of Manufacturing Science and Engineering, Sichuan University, Chengdu 610065, China)

Abstract：The optimization problem of manufacturing cloud services composition was analysed based on QoS of cloud manufacturing. A mathematical model with time, cost, reputation and reliability goals of this problem was set up. To solve the mathematical model, an optimization method which combined the Analytic Hierarchy process (AHp) with the improved particle swarm algorithm was proposed. In order to analyze user’s needs, each QoS attributes were refined to form a cloud service attribute level, and AHp was used to determine the weight of each attribute. The improved particle swarm algorithm can converge to the optimal solution quickly and efficiently. This optimization method is able to make up for the shortages of the previous method and also find cloud services composition solution meeting user’s dynamic demands.

Key words：cloud manufacturing; cloud services composition; particle swarm algorithm; AHp

中圖分類號(hào)：TH166;TG506

文獻(xiàn)標(biāo)識(shí)碼：A

作者簡(jiǎn)介：唐雨(1991—)，男，四川綿陽人，四川大學(xué)碩士研究生，研究方向?yàn)闄C(jī)械制造及其自動(dòng)化，企業(yè)信息化，(E-mail)12345tangyu@163.com。

*基金項(xiàng)目：國家“十一五”科技支撐計(jì)劃項(xiàng)目(2006BAC02A02)

收稿日期：2015-02-08