一種基于云模型的組合服務(wù)選擇方法

謝曉燕, 錢(qián) 宇, 王 麗

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710121)

?

一種基于云模型的組合服務(wù)選擇方法

謝曉燕, 錢(qián) 宇, 王 麗

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710121)

針對(duì)Web服務(wù)選擇問(wèn)題，提出一種以云模型為基礎(chǔ)的代表性Skyline服務(wù)選擇方法。該方法利用云模型進(jìn)行服務(wù)不確定性的篩選，從中選取代表性Skyline服務(wù)，建立代表性服務(wù)樹(shù)作為整數(shù)規(guī)劃選擇模型的輸入，最后通過(guò)整數(shù)規(guī)劃模型求解出滿(mǎn)足需求的最優(yōu)服務(wù)。對(duì)比結(jié)果表明，該方法能夠快速、準(zhǔn)確地選擇出滿(mǎn)足用戶(hù)需求的服務(wù)，在保證成功率的基礎(chǔ)上使得時(shí)間花費(fèi)有所提升。

云模型；不確定性；代表性Skyline；服務(wù)選擇

Web服務(wù)[1]作為一種開(kāi)放的業(yè)務(wù)提供方式，是Web集成技術(shù)中最具有活力的應(yīng)用技術(shù)之一，已廣泛應(yīng)用在銀行、金融服務(wù)機(jī)構(gòu)和電子商務(wù)等方面[2]。

Web服務(wù)選擇的方法主要有以下4種。(1)采用全局最優(yōu)化的策略，運(yùn)用整數(shù)規(guī)劃的方法從QoS(Quality of Service)屬性方面實(shí)現(xiàn)服務(wù)選擇[1]。(2)基于服務(wù)多維QoS信息，從局部最優(yōu)進(jìn)行服務(wù)選擇[2]。(3)運(yùn)用Agent理論技術(shù), 在面向服務(wù)計(jì)算領(lǐng)域,實(shí)現(xiàn)Web服務(wù)的自動(dòng)發(fā)現(xiàn)、交互以及自動(dòng)組合[3]。(4)基于多屬性群決策理論的混合QoS感知web服務(wù)組合群決策算法，支持多決策者和具有混合QoS信息(實(shí)數(shù)、區(qū)間數(shù)、三角模糊數(shù)、直覺(jué)模糊數(shù))的服務(wù)組合[4]。

隨著研究的深入，將Skyline計(jì)算[5]應(yīng)用到服務(wù)選擇中，通過(guò)對(duì)服務(wù)實(shí)現(xiàn)功能或者QoS層次的Skyline建模，從而根據(jù)服務(wù)間的支配關(guān)系選擇出符合要求的性能較優(yōu)的服務(wù)。該方法通過(guò)Skyline篩選，可以縮小服務(wù)選擇的范圍，提高服務(wù)選擇的效率。利用MapReduce思想進(jìn)行并行Skyline服務(wù)選擇的方法，通過(guò)優(yōu)勢(shì)度提高了服務(wù)選擇效率，但隨著屬性的增多，Skyline服務(wù)數(shù)目的增大，選擇效率變低[6]；基于云模型的Skyline服務(wù)選擇方法(Skyline service selection based on cloud model，SSSCM)通過(guò)云模型計(jì)算QoS的不確定性,采用Skyline計(jì)算提取Web服務(wù)中的Skyline服務(wù)，剔除冗余服務(wù)，最后利用混合整數(shù)規(guī)劃在Skyline服務(wù)中進(jìn)行服務(wù)選擇，但該方法的自適應(yīng)性不足，當(dāng)服務(wù)的數(shù)目很大時(shí)，很難有效處理，導(dǎo)致服務(wù)選擇效率不高[7]。本文擬提出一種改進(jìn)的服務(wù)選擇方法，采用云模型進(jìn)行候選服務(wù)預(yù)處理，利用層次聚類(lèi)算法對(duì)Skyline服務(wù)進(jìn)行聚類(lèi)，確定代表性服務(wù)樹(shù)，最后通過(guò)混合整數(shù)規(guī)劃進(jìn)行服務(wù)選擇的求解。

1 云模型與Skyline計(jì)算

1.1 云模型

云模型[7]是在概率論和模糊數(shù)學(xué)理論兩者交互的基礎(chǔ)上，通過(guò)特定的結(jié)構(gòu)算法所形成的定性概念與其定量表示之間的轉(zhuǎn)換模型[8]。在服務(wù)選擇中，如果對(duì)服務(wù)的多個(gè)QoS屬性進(jìn)行定量到定性的轉(zhuǎn)換，并根據(jù)設(shè)置的門(mén)限值來(lái)進(jìn)行服務(wù)不確定性的度量，就可以把服務(wù)屬性的定量數(shù)字轉(zhuǎn)換為不確定性的定性概念。定性概念到定量的轉(zhuǎn)換過(guò)程稱(chēng)為正向云發(fā)生器；定量到定性概念的轉(zhuǎn)換過(guò)程稱(chēng)為逆向云發(fā)生器[9]。逆向云發(fā)生器通過(guò)已知云滴[7]，得到描述定性概念的3個(gè)數(shù)字特征期望Ex、熵En和超熵He[10]，轉(zhuǎn)換過(guò)程如圖1所示。

圖1 逆向云發(fā)生器過(guò)程

1.2 Skyline計(jì)算

服務(wù)選擇的過(guò)程即是從服務(wù)發(fā)布者發(fā)布的海量服務(wù)中選擇出最能夠符合用戶(hù)需求的服務(wù)。Skyline計(jì)算是從一個(gè)數(shù)據(jù)庫(kù)中抽取不被其他任何數(shù)據(jù)對(duì)象支配的數(shù)據(jù)對(duì)象集合，將不被其他服務(wù)支配的服務(wù)作為候選服務(wù)，可降低服務(wù)選擇的搜索空間，提高服務(wù)選擇效率。

2 基于云模型的代表性Skyline服務(wù)選擇

2.1 云模型計(jì)算

假設(shè)兩個(gè)相同功能的服務(wù)S1和S2的屬性值分別為S1(x11,…,x1m)和S2(x11,…,x1n)，通過(guò)逆向云發(fā)生器計(jì)算其各自的數(shù)字特征，即期望Ex、熵En和超熵He，用以表示各服務(wù)的不確定度。比較服務(wù)S1和S2的熵En和超熵He,可得服務(wù)S1和S2不確定性的大小，從而能確定出哪個(gè)服務(wù)的的QoS較為穩(wěn)定。設(shè)置云模型中En和He參數(shù)的門(mén)限值，可以剔除不確定性較大的服務(wù)，從而保留較為穩(wěn)定的服務(wù)作為候選服務(wù)。

2.2 代表性Skyline服務(wù)計(jì)算

Skyline算法可將一部分被支配的服務(wù)剔除，降低服務(wù)的搜索空間，從而降低服務(wù)選擇的時(shí)間花費(fèi)，但是，當(dāng)某一服務(wù)類(lèi)S的Skyline服務(wù)數(shù)目K太大，從而不能有效處理時(shí)，引入代表性Skyline計(jì)算，通過(guò)從中選擇具有代表性的服務(wù)作為整數(shù)規(guī)劃優(yōu)化選擇模型的輸入，可以減少算法計(jì)算復(fù)雜度空間，并能夠快速準(zhǔn)確地選擇出符合要求的服務(wù)。

每一個(gè)服務(wù)都有響應(yīng)時(shí)間和可用性?xún)蓚€(gè)QoS屬性， Skyline服務(wù)示例如圖2所示。

圖2 Skyline服務(wù)示例

由圖2可以看出，服務(wù)S1不被任何其他服務(wù)支配，即沒(méi)有任何其他服務(wù)的響應(yīng)時(shí)間低于S1，并且可用性高于S1，因此S1為Skyline服務(wù)，同理，S2，S3，S4也是Skyline服務(wù)。

將Skyiline服務(wù)SL聚類(lèi)為m個(gè)簇(cluster)，m=2,4,6,8,16…, |SL| ，從各簇中選擇具有最高效用的服務(wù)作為代表性服務(wù)，建立代表性服務(wù)的樹(shù)結(jié)構(gòu)，如圖3所示。

(a) 1簇

(b) 2簇

(c) 4簇

(d) 候選服務(wù)S3

樹(shù)中各葉子節(jié)點(diǎn)對(duì)應(yīng)1個(gè)SL中的Skyline服務(wù)，根節(jié)點(diǎn)和中間節(jié)點(diǎn)則對(duì)應(yīng)在相應(yīng)簇中選擇的代表性服務(wù)。綜合服務(wù)運(yùn)行時(shí)，一旦接受到用戶(hù)給組合服務(wù)的請(qǐng)求時(shí)，就從樹(shù)的根節(jié)點(diǎn)開(kāi)始啟動(dòng)搜索，也就是只考慮每個(gè)服務(wù)類(lèi)中的頂層代表性服務(wù)，如圖3(d)所示。

利用K-means算法[11]，建立代表服務(wù)樹(shù)算法。輸入為服務(wù)類(lèi)S的Skyline服務(wù)Si,輸出為1個(gè)代表性服務(wù)的二叉樹(shù)。確定SL中效用值最大的服務(wù)根節(jié)點(diǎn)S，將S聚類(lèi)為2個(gè)子簇，并分別將這2個(gè)簇中效用值最大的服務(wù)作為S的子節(jié)點(diǎn)。對(duì)每個(gè)子簇不斷重復(fù)這個(gè)過(guò)程，直到不能再生成新的簇。

2.3 服務(wù)選擇

給定的抽象流程組合服務(wù)集合SA={S1,S2,…,Sj,…,Sn}和全局約束向量C=[c1,c2,…,ck,…,cm]。SA服務(wù)類(lèi)別Sj有l(wèi)個(gè)功能屬性相同但QoS值不同的候選服務(wù)，即Sj={sj1,…,sji,…,sjl}，并且每個(gè)服務(wù)受約束向量C的限制。通過(guò)為每個(gè)Sj綁定1個(gè)sjl∈Sj，將SA={S1,S2,…,Sn}進(jìn)行實(shí)例化，使得

(2)U(SA)是組合服務(wù)集合的QoS效用函數(shù)。

通過(guò)該效用函數(shù)值表示服務(wù)類(lèi)Sj中所有候選服務(wù)中第k個(gè)屬性值。讓SA中的每個(gè)組合服務(wù)滿(mǎn)足U最大化，即整體效用U(SA)最大化。

對(duì)于本文的順序結(jié)構(gòu)的服務(wù)組合，其優(yōu)化問(wèn)題可以用整數(shù)規(guī)劃方法來(lái)解決。利用0-1二元決策變量xji表示是否選擇服務(wù)sji,sji表示服務(wù)類(lèi)Sj中的候選服務(wù)。如果xji設(shè)置為1，則候選服務(wù)被包含在優(yōu)化組合中，而在同一個(gè)服務(wù)類(lèi)Sj中的其他候選服務(wù)則會(huì)被忽略。將決策變量xji引入效用函數(shù)，則服務(wù)選擇問(wèn)題就可以被形式化為最大組合服務(wù)效用的問(wèn)題，其目標(biāo)函數(shù)f(x)可以表示為

(1)

為確保選擇的組件服務(wù)滿(mǎn)足全局的QoS約束，則需加入約束條件

同時(shí)決策變量xji需滿(mǎn)足xji∈[0,1]，還需滿(mǎn)足分配約束，以確保為每一個(gè)服務(wù)類(lèi)別Sj只綁定一個(gè)組件服務(wù)，即

(2)

其中n為服務(wù)中類(lèi)的個(gè)數(shù)，l為每個(gè)服務(wù)類(lèi)中的候選服務(wù)數(shù)量，r為候選服務(wù)的QoS屬性個(gè)數(shù)，Ck為QoS的約束值。

采用云模型進(jìn)行候選服務(wù)預(yù)處理，利用層次聚類(lèi)算法對(duì)Skyline服務(wù)進(jìn)行聚類(lèi)，確定代表性服務(wù)樹(shù)，屏蔽了 QoS 不確定性較大的服務(wù),且通過(guò)Skyline計(jì)算剔除了冗余服務(wù),從而在保證獲得可靠服務(wù)的同時(shí),降低了服務(wù)選擇的搜索空間。在所選擇的組合服務(wù)和全局約束向量下，通過(guò)約束條件可以快速、有效的選擇出滿(mǎn)足用戶(hù)需求的全局QoS約束最優(yōu)的組合服務(wù)。

3 仿真與驗(yàn)證

實(shí)驗(yàn)基于Pentium Dual 2.4 GHz,2.0 GB RAM，Windows 7,Microsoft Visual C++6.0軟硬件環(huán)境進(jìn)行，采用2 500個(gè)網(wǎng)絡(luò)上收集到的真實(shí)數(shù)據(jù)集QWS (Quality of Web Service)[12]，將該方法與文獻(xiàn)[7]的成功率進(jìn)行對(duì)比，并在保證成功率的基礎(chǔ)上對(duì)運(yùn)行時(shí)間進(jìn)行分析評(píng)價(jià)。

3. 1 成功率對(duì)比

成功率 (success ratio，SR)[6]指在某個(gè)組合服務(wù)運(yùn)行t次,QoS總效用函數(shù)(overall utility,OU)與其實(shí)際運(yùn)行監(jiān)測(cè)結(jié)果(monitoring result,MR)的比值不小于設(shè)定門(mén)限值h,組合服務(wù)集合SA中抽取的所有服務(wù)都是相同屬性下QoS值最高的，由于QoS聚合函數(shù)的單調(diào)性，即越大的QoS屬性值產(chǎn)生越大的QoS聚合值U(SA)。且該用戶(hù)的全局QoS約束向量C的屬性值ci與監(jiān)測(cè)到的該屬性的聚合值U(SA)之間的比值w也不小于設(shè)定門(mén)限值h的次數(shù)與t的百分比,即

(4)

其中SR越大，表示成功率越高。本文方法與文獻(xiàn)[7]方法的成功率對(duì)比結(jié)果如圖4所示。

圖4 本文方法與文獻(xiàn)[7]方法成功率對(duì)比

圖4中可以看出，當(dāng)候選服務(wù)數(shù)目在1～1 000之間時(shí)，兩種方法的成功率相差不是很大，但是當(dāng)候選服務(wù)數(shù)目增大到1 000～2 000時(shí)，本文方法的成功率整體略?xún)?yōu)于文獻(xiàn)[7]方法的成功率，但當(dāng)服務(wù)數(shù)目增加到2 000～2 500時(shí)，本文方法的成功率明顯優(yōu)于文獻(xiàn)[7]方法。本文方法采用云模型對(duì)服務(wù)進(jìn)行不確定性計(jì)算，剔除了不確定性較高的服務(wù)，通過(guò)聚類(lèi)選擇出代表性Skyline服務(wù)，保證了候選服務(wù)QoS的穩(wěn)定性和可用性，提高了服務(wù)選擇的可靠性。

3.2 運(yùn)行時(shí)間對(duì)比

圖5為本文方法和文獻(xiàn)[7]方法在相同的QoS數(shù)據(jù)類(lèi)型上時(shí)間花費(fèi)的對(duì)比結(jié)果。

圖5 本文方法與文獻(xiàn)[7]方法運(yùn)行時(shí)間對(duì)比

從圖5中可以看出，不論候選服務(wù)的數(shù)目為多少，本文方法的運(yùn)行時(shí)間都比文獻(xiàn)[7]方法少，尤其在數(shù)據(jù)量在1 000～2 500之間，本文的運(yùn)行時(shí)間平均在50 ms左右，較為平穩(wěn)，而文獻(xiàn)[7]中的方法隨著數(shù)據(jù)量的增大在不斷增加。本文方法在每個(gè)候選服務(wù)類(lèi)的Skyline服務(wù)中選取了最高效用的代表性Skyline服務(wù)作為組合服務(wù)選擇模型的輸入，很大程度的降低了算法的時(shí)間復(fù)雜度，從而提高了服務(wù)選擇的效率。

4 結(jié)語(yǔ)

通過(guò)云模型的逆向發(fā)生器進(jìn)行不確定服務(wù)篩選，提高服務(wù)選擇的可靠性，選取代表性Skyline服務(wù)并建立代表性服務(wù)樹(shù)作為整數(shù)規(guī)劃模型的輸入。與文獻(xiàn)[7]方法對(duì)比結(jié)果表明，該方法在保證成功率的基礎(chǔ)上使得運(yùn)行時(shí)間有所提升，減小了服務(wù)選擇的搜索空間，降低了服務(wù)選擇所需的時(shí)間花費(fèi)。

[1] ZENG L H, BENATALLAH B, DUMAS M, et al. Quality driven Web services composition[C/OL]//Proceedings of the 12th International Conference on World Wide Web. Budapest: Hungary, 2003: 411-421[2015-09-08]. https://www.mysciencework.com/publication/show/8b420d8c6dd914be9f42d2d43b5e86e5.

[2] 胡建強(qiáng)，李涓子，廖桂平.一種基于多維服務(wù)質(zhì)量的局部最優(yōu)服務(wù)選擇模型[J].計(jì)算機(jī)學(xué)報(bào),2010,33(3)：526-534. DOI: 10.3724/ SP.J.1016 .2010.00526.

[3] 葉榮華,金枝,王璞巍,等.一種需求驅(qū)動(dòng)的自主Web服務(wù)聚類(lèi)方法[J].軟件學(xué)報(bào),2010,6(21):1181-1195. DOI:10.3724/SP.J.1001.2010.03666.

[4] 張龍昌. 混合QoS感知的服務(wù)組合群決策[J].北京郵電大學(xué)學(xué)報(bào),2013,36(1):27-30.

[5] BORZSONYI S,KOSSMANN D,STOCKER K.The Skyline Operator[C/OL]//International Conference on Data Engineering.Germany:Heidelberg,2001:421-430 [2015-09-08].https://www.computer.org/csdl/proceedings/icde/2001/1001/00/10010421-abs.html .DOI:10.1109/ICDE.2001.914855.

[6] WU J, CHEN L, YU Q, et al. Selecting skyline services for QOS-aware composition by upgrading MapReduce paradigm[J/OL].Cluster Computing ,2013, 16(4):1-14[2016-05-10]. https://www.researchgate.net/publication/257548717_Selecting_skyline_services_for_QoS-aware_composition_by_upgrading_MapReduce_paradigm

[7] 王尚廣,孫其博,張光衛(wèi),等.基于云模型的不確定性QoS感知的Skyline服務(wù)選擇[J].軟件學(xué)報(bào),2012,23(6): 1397-1412.DOI:10.3724/SP.J.1001.2012.04084.

[8] 李德毅,孟海軍,史雪梅.隸屬云和隸屬云發(fā)生器[J].計(jì)算機(jī)研究和發(fā)展,1995,32(6):16-21.

[9] 李德毅,李常昱，杜鹢,等.不確定性人工智能[J/OL].軟件學(xué)報(bào)，2004,15(11):1583-1594[2015-09-08].http://www.jos.org.cn/1000-9825/15/1583.htm.DOI :10.13328/j.cnki.jos.2004.11.001

[10] 陳思,王曙燕,孫家澤.基于云模型的可信軟件可靠性度量模型[J].計(jì)算機(jī)應(yīng)用研究, 2014,31(9): 2729-2731.DOI:10.3969/j.issn.1001-3695.2014.09.039.

[11] 吳夙彗，成穎，鄭彥寧，等.K-means研究算法綜述[J/OL].現(xiàn)代圖書(shū)情報(bào)技術(shù), 2011,205(5):28-34[2016-05-10]. http://www.cnki.com.cn/Article/CJFDTotal-XDTQ201105007.htm.

[12] Al-MASARI E, MAHMOUD Q H. Discovering the best Web service[C/OL]// WWW ’07 Proceedings of the 16th international conference on World Wide Web, New York: ACM, 2007: 1257-1258[2016-05-10]. http://dl.acm.org/citation.cfm?id=1242572.1242795. DOI:10.1145/1242572.1242795.

[責(zé)任編輯：祝劍]

Research on representative Skyline service selection approach based on cloud model

XIE Xiaoyan, QIAN Yu, WANG Li

(School of Computer Science and Technology, Xi’an University of Posts and Telecommunications，Xi’an 710121, China)

A representative Skyline service selection approach based on cloud model is proposed in this paper for the efficiency, accuracy and reliability of the Web service selection. In this approach cloud model is used to filter the uncertainty of services and to select representative Skyline services, and to establish a representative service tree which is also the input of integer programming. Integer programming is then employed to select the best service to meet the need. Experimental results from the testing on the real datasets show that the proposed approach can meet users’ needs reliably and quickly, and improve 10 times of time spending in the premise of selecting the best service.

cloud model, uncertainty, representative Skyline, service selection

10.13682/j.issn.2095-6533.2016.06.022

2015-10-08

陜西省自然科學(xué)基金資助項(xiàng)目(2013JC2-32)

謝曉燕(1972-)，女，碩士，副教授，從事服務(wù)計(jì)算研究。E-mail：xxy@xupt.edu.cn 錢(qián)宇(1991-)，男，碩士研究生，研究方向?yàn)榉?wù)計(jì)算。E-mail：z69365656@163.com

TP311

A

2095-6533(2016)06-0114-04