蘇佰川，張國義，許胤龍

（中國科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，安徽 合肥230026）

隨著面向服務(wù)計(jì)算技術(shù)的深入發(fā)展，通過組合Web服務(wù)建立分布式應(yīng)用系統(tǒng)逐漸成為基于Web應(yīng)用開發(fā)的主流技術(shù)。在眾多可獲得的Web服務(wù)資源中，如何選擇合適的服務(wù)實(shí)例進(jìn)行組合，使之既能滿足應(yīng)用的功能需求，又能滿足用戶提出的QoS需求，是一個(gè)備受關(guān)注的問題，并已得到了廣泛的研究。

QoS約束的Web服務(wù)選擇與組合是一類組合優(yōu)化問題。到目前為止，求解該問題比較典型的方法有線性規(guī)劃算法[1-2]和遺傳算法[3-6]。線性規(guī)劃算法在候選服務(wù)集規(guī)模較小時(shí)是非常有效的，但是隨著規(guī)模的加大，計(jì)算耗時(shí)增長速度明顯加快，可擴(kuò)展性變差。遺傳算法被用于QoS的全局組合優(yōu)化已有許多成功的案例，但是，由于在諸多的研究中一般采用隨機(jī)交叉和變異操作，沒有考慮候選服務(wù)實(shí)例之間實(shí)際存在的連接偏好，組合服務(wù)的可靠性難以得到有效的保證。連接頻率反映了服務(wù)之間的連接偏好，頻率越高，下一次連接的可能性就越大，在一定程度上可增強(qiáng)組合服務(wù)的可靠性。如何利用候選服務(wù)實(shí)例之間的連接偏好優(yōu)化服務(wù)的隨機(jī)選擇，提高服務(wù)組合的效率與成功率是本文主要關(guān)注的問題。

根據(jù)軟件工程的一般常識可知，一個(gè)復(fù)雜的組合服務(wù)包含平行、分支、選擇、循環(huán)等結(jié)構(gòu)，可以利用數(shù)據(jù)流聚合方法形成顆粒較大的結(jié)構(gòu)塊。而對于一個(gè)大規(guī)模的候選服務(wù)集合，應(yīng)用社會網(wǎng)絡(luò)社區(qū)形成機(jī)制[7]，也可以形成與服務(wù)流程聚合塊功能相一致的服務(wù)子集，即所謂的服務(wù)社區(qū)。這樣，服務(wù)選擇就演化成社區(qū)選擇問題，運(yùn)用遺傳算法能較好地保證結(jié)構(gòu)性選擇，且依據(jù)連接權(quán)重形成的服務(wù)社區(qū)能充分體現(xiàn)服務(wù)之間的連接偏好。根據(jù)這一思想，本文提出了一個(gè)基于社區(qū)形成機(jī)制和遺傳算法的服務(wù)選擇方法，與傳統(tǒng)遺傳算法不同的是，設(shè)計(jì)了一個(gè)依據(jù)連接偏好的效用函數(shù)估算隨機(jī)選擇概率。初步的實(shí)驗(yàn)結(jié)果證明，該方法行之有效，且具有較高的計(jì)算效率。

1 問題描述

對于用戶提出的服務(wù)需求首先建立組合服務(wù)流程，圖 1所示為一個(gè)有 8個(gè)原子服務(wù) S1，S2，…，S8的服務(wù)流程。

如圖1所示，一般一個(gè)組合Web服務(wù)流程由多個(gè)Web原子服務(wù)組成，每個(gè)Web原子服務(wù)又對應(yīng)有多個(gè)候選服務(wù)。這些候選服務(wù)可能由不同的服務(wù)提供者提供，具有相同的功能和不同的QoS度量值。

定義(服務(wù)流程，SP)1：對于任意一個(gè)組合Web服務(wù)流程 SP可表示為 SP=(S，≤s)，其中其中 Si表示第 i個(gè)原子服務(wù)，≤s表示各個(gè)服務(wù) Si、Sj之間的內(nèi)部關(guān)系，可表示為：≤s=(Pre，Suc，R)，其中 Pre 和Suc分別表示當(dāng)前服務(wù)在服務(wù)流程中的前驅(qū)和后繼。同時(shí)如果某個(gè)Si.Pre=∧，則此結(jié)點(diǎn)為開始結(jié)點(diǎn)，如果某個(gè)Si.Suc=∧，則此結(jié)點(diǎn)為結(jié)束結(jié)點(diǎn)。R(0＜R≤1)表示當(dāng)前原子服務(wù)在服務(wù)流程中的結(jié)構(gòu)關(guān)系，R=1表示此服務(wù)在服務(wù)流程中是串行、并行或者循環(huán)結(jié)構(gòu)，0＜R＜1則表示此服務(wù)屬于服務(wù)流程選擇結(jié)構(gòu)的一個(gè)分支。

假定每個(gè)原子服務(wù)Si包含m個(gè)候選服務(wù)，即：

對于每個(gè)候選服務(wù)Sji都有不同的服務(wù)質(zhì)量(QoS)[3，8]，如響應(yīng)時(shí)間(Response time)、代價(jià)(Cost)、可靠性(Reliability)、信譽(yù)度(Reputation)等，假定每個(gè)候選服務(wù)的服務(wù)質(zhì)量(QoS)維度為 k，即：

其中T、C、R為某一服務(wù)選擇實(shí)例(WS)完成組合服務(wù)要經(jīng)歷的總的響應(yīng)時(shí)間、總代價(jià)及可靠性。而TQoS、CQoS及RQoS為用戶提出的約束條件。組合Web服務(wù)流程[3]的4種基本結(jié)構(gòu)——串行、并行、選擇和循環(huán)中QoS度量值(T，C，R)計(jì)算公式在文中已給出，此處不再敘述[8]。

2 算法描述

2.1 服務(wù)社會網(wǎng)絡(luò)

要應(yīng)用社會網(wǎng)絡(luò)[9-10]，首先要將候選服務(wù)結(jié)點(diǎn)集合轉(zhuǎn)換為以網(wǎng)絡(luò)為主的服務(wù)社會網(wǎng)絡(luò)，因此要在結(jié)點(diǎn)之間加入邊及其邊的權(quán)值的確定。

定義(服務(wù)結(jié)點(diǎn)，Node)3：對于組合Web服務(wù)選擇問題中的每個(gè)候選服務(wù)，都稱之為一個(gè)候選服務(wù)結(jié)點(diǎn)(Node)，每個(gè) Node除了候選服務(wù)本身的 QoS之外，另外加入邊的權(quán)值 (Weight)屬性，具體數(shù)據(jù)結(jié)構(gòu)表示為Node(Name，Type，Weight，QoS)。 為描述方便，將 Node.Name 由之前的轉(zhuǎn)化為 Nk(k=1，2，…，n×m)，每個(gè)服務(wù)結(jié)點(diǎn) Ni的服務(wù)類型 Ni.Type=Sj(j=1，2，…，n)，同時(shí) Ni.Weight是一個(gè)三元組，表示為(Name，Type，w)。

設(shè) Edge(Si，Sj)為如果在服務(wù)流程 S中 Si到 Sj存在邊相連，則 Edge(Si，Sj)為 1，否則為 0。

定義(服務(wù)社會網(wǎng)絡(luò)，SSN)4：對于特定的服務(wù)流程S，用戶每提出一個(gè)QoS需求，都會對應(yīng)一個(gè) WS滿足用戶的功能需求及QoS需求，對每個(gè)滿足需求的WS作如下判斷：

通過以上的定義，將之前的服務(wù)結(jié)點(diǎn)之間加入邊及權(quán)值，形成服務(wù)社會網(wǎng)絡(luò)，如圖2所示。

2.2 服務(wù)社會網(wǎng)絡(luò)選擇算法

Web服務(wù)的部分QoS是負(fù)相關(guān)的，即取值越小越好(如響應(yīng)時(shí)間、代價(jià))，而同時(shí)部分 QoS則是正相關(guān)的，即取值越大越好(如可靠性等)。因此對于負(fù)相關(guān)的QoS屬性和服務(wù)結(jié)點(diǎn)之間的權(quán)值歸一化：

定義(歸一化，Normalized)5：

結(jié)點(diǎn)的效用函數(shù)Fi的定義由QoS參數(shù)組成，其中的QoS參數(shù)是與用戶提出的目標(biāo)函數(shù)中的QoS參數(shù)相對應(yīng)的，由式(4)可知目標(biāo)函數(shù)使整個(gè)組合Web服務(wù)的執(zhí)行時(shí)間最小，故效用函數(shù)的定義如定義6所示。

定義(效用函數(shù)，F(xiàn)i)6：Fi=T′i

服務(wù)結(jié)點(diǎn)之間的權(quán)值歸一化后，結(jié)點(diǎn) Ni與 Nj之間的歸一化權(quán)值w′ij與 w′ji值不相同，因此結(jié)點(diǎn)間的選擇概率定義如下：

定義(選擇概率，Pij)7：

Pij越大，表明結(jié)點(diǎn) Ni與 Nj被選擇在一起用于解決問題的概率越大。

給出Pij之后，同時(shí)結(jié)合Web服務(wù)選擇問題和遺傳算法，提出了如下的服務(wù)社會網(wǎng)絡(luò)算法(SSN Algorithm)：

某一結(jié)點(diǎn)Ni在某一服務(wù)實(shí)例WS中關(guān)于前驅(qū)后繼的平均選擇概率P的計(jì)算公式如下(前驅(qū)后繼可能不止一個(gè)，Num函數(shù)用于計(jì)算某一原子服務(wù)Si在某一服務(wù)流程中前驅(qū)與后繼的個(gè)數(shù))：

3 實(shí)驗(yàn)分析

實(shí)驗(yàn)環(huán)境為100 Mb/s的局域網(wǎng)，微機(jī)的配置為Intel Pentium Dual 2.0 GHz CPU，2 GB內(nèi)存，操作系統(tǒng)為Windows XP，算法編譯環(huán)境為VC++6.0。實(shí)驗(yàn)分為 4組，每組的服務(wù)類型個(gè)數(shù)及候選服務(wù)個(gè)數(shù)如表1(其中n表示原子服務(wù)個(gè)數(shù)，m表示每種原子服務(wù)對應(yīng)的候選服務(wù)個(gè)數(shù))所示，分別從以下幾個(gè)方面進(jìn)行實(shí)驗(yàn)。

(1)服務(wù)結(jié)點(diǎn)規(guī)模不同時(shí)對選擇算法執(zhí)行時(shí)間的影響。

表1 各組原子服務(wù)類型規(guī)模及候選服務(wù)規(guī)模

選擇算法中的外層循環(huán)設(shè)置為1 000次，內(nèi)層循環(huán)條件為當(dāng)TBest有連續(xù)50次不發(fā)生變化或者循環(huán)滿3 000次時(shí)結(jié)束。算法在4個(gè)group下的執(zhí)行時(shí)間如圖3所示，由圖可知，當(dāng)整個(gè)社會網(wǎng)絡(luò)中總結(jié)點(diǎn)個(gè)數(shù)為3 000時(shí)，所用的時(shí)間剛剛1 s，而且隨著網(wǎng)絡(luò)規(guī)模的增加，執(zhí)行時(shí)間的增長速率要緩慢得多。因此說網(wǎng)絡(luò)規(guī)模越大，SSN算法的執(zhí)行效率越高。

(2)隨著社會網(wǎng)絡(luò)權(quán)值的不同找到最優(yōu)解的概率

分析在不同權(quán)值下各個(gè)group運(yùn)行SSN算法100次，能找到的目標(biāo)函數(shù)的較優(yōu)值與最優(yōu)解之間的比值，通過圖4可以看到隨著網(wǎng)絡(luò)中權(quán)值的增大，4個(gè)group找到的較優(yōu)解與最優(yōu)解之間的差距越來越小。當(dāng)網(wǎng)絡(luò)中結(jié)點(diǎn)的規(guī)模不是很大(group1，group2)時(shí)，即使權(quán)值不是很大，找到最優(yōu)解概率也非常高。隨著權(quán)值的增加，能找到最優(yōu)解的次數(shù)也不斷增多，當(dāng)用戶提出次數(shù)到達(dá)40次左右時(shí)，group1與group2基本每次都可以找到最優(yōu)解。當(dāng)網(wǎng)絡(luò)規(guī)模較大(group3，group4)的情況下，雖然權(quán)值很小時(shí)找到最優(yōu)解的概率不是很高，大概85%，但隨著權(quán)值的增加，能找到最優(yōu)解的概率迅速加大，當(dāng)權(quán)值為30時(shí)，概率達(dá)到了96%左右，權(quán)值為 50時(shí)，概率達(dá)到了98%，因此隨著用戶QoS需求的增加，能找到最優(yōu)解的概率能夠迅速加大，同時(shí)對于結(jié)點(diǎn)規(guī)模很大的社會網(wǎng)絡(luò)來說，效果更佳。

隨著服務(wù)計(jì)算的迅速發(fā)展，可利用的Web服務(wù)資源越來越多，候選服務(wù)結(jié)點(diǎn)的規(guī)模也越來越大。本文總結(jié)了近期相關(guān)的工作，提出了一種基于社會網(wǎng)絡(luò)社區(qū)形成機(jī)制的Web服務(wù)選擇方法。將Web服務(wù)選擇問題轉(zhuǎn)換到社會網(wǎng)絡(luò)中，利用社會網(wǎng)絡(luò)特有的性質(zhì)結(jié)點(diǎn)聯(lián)系強(qiáng)度等來解決服務(wù)選擇問題。提出了一種服務(wù)社會網(wǎng)絡(luò)概率選擇方法，此方法與遺傳算法的不同之處在于變異結(jié)點(diǎn)的選擇不是隨機(jī)的，而是根據(jù)結(jié)點(diǎn)之間的連接頻率，它反映了服務(wù)之間的連接偏好，頻率越高，下一次連接的可能性就越大。

雖然最終算法給出了很好的性能，但還有待進(jìn)一步改進(jìn)，如本文算法是基于單目標(biāo)優(yōu)化的，希望今后在多目標(biāo)優(yōu)化方面有所進(jìn)展。同時(shí)本文算法是基于歷史信息(服務(wù)實(shí)例)的，因此當(dāng)歷史信息較少或剛開始沒有歷史信息時(shí)性能方面可能會很差，希望今后在這方面也有所研究。

[1]Zeng Liangzhao，BENATALLAH B，DUMAS M，et al.Quality driven Web services composition[C].Proceedings of the 12th International Conference on World Wide，2003.

[2]ARDAGNA D，PERNICI B.Adaptive service composition in flexible processes[J].IEEE Trans.Software Eng，2007，33(6)：369-384.

[3]HWANG S Y，WANG H，TANG J，et al.A probabilistic approach to modeling and estimating the QoS of Web-Services-based Workflows[J].Information Sciences，2007，23(177)：5484-5503.

[4]KLEIN A，ISHIKAWA F，BAUER B.A probabilistic approach to service selection with conditional contracts and usage patterns[C].ICSOC-ServiceWave2009，2009：253-268.

[5]Tang Maolin，Ai Lifeng.A hybrid genetic algorithm for the optimal constrained Web service selection problem in Web Service composition[C].WCCI 2010 IEEE World Congress on Computational Intelligence，2010.

[6]Liu Shulei，Liu Yunxiang，Jing Ning，et al.A dynamic Web service selection strategy with QoS global optimization based on multi-objective genetic algorithm[C].GCC2005，2005：84-89.

[7]KUMPULA J M，ONNELA J P，SARAMAKI J，et al.Model of community emergence in weighted social networks[J].Computer Physics Communication，2009(180)：517.

[8]YU T，ZHANG Y，LIN K J.Efficient algorithms for Web services selection with end-to-end qos constraints[J].ACM Transactions on the Web，2007，1(1)：1-26.

[9]NEWMAN M E J.Analysis of weighted networks[J].Physical review，2004，70(05)：1-9.

[10]WASSERMAN S，F(xiàn)AUST K.Introduction to social network analysis[M].Cambridge Cambridge Univ.Press，1994.