基于社會網絡的Web服務選擇算法的研究

蘇佰川，張國義，許胤龍

（中國科學技術大學 計算機科學學院，安徽 合肥230026）

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

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

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

1 問題描述

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

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

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

假定每個原子服務Si包含m個候選服務，即：

對于每個候選服務Sji都有不同的服務質量(QoS)[3，8]，如響應時間(Response time)、代價(Cost)、可靠性(Reliability)、信譽度(Reputation)等，假定每個候選服務的服務質量(QoS)維度為 k，即：

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

2 算法描述

2.1 服務社會網絡

要應用社會網絡[9-10]，首先要將候選服務結點集合轉換為以網絡為主的服務社會網絡，因此要在結點之間加入邊及其邊的權值的確定。

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

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

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

通過以上的定義，將之前的服務結點之間加入邊及權值，形成服務社會網絡，如圖2所示。

2.2 服務社會網絡選擇算法

Web服務的部分QoS是負相關的，即取值越小越好(如響應時間、代價)，而同時部分 QoS則是正相關的，即取值越大越好(如可靠性等)。因此對于負相關的QoS屬性和服務結點之間的權值歸一化：

定義(歸一化，Normalized)5：

結點的效用函數Fi的定義由QoS參數組成，其中的QoS參數是與用戶提出的目標函數中的QoS參數相對應的，由式(4)可知目標函數使整個組合Web服務的執行時間最小，故效用函數的定義如定義6所示。

定義(效用函數，Fi)6：Fi=T′i

服務結點之間的權值歸一化后，結點 Ni與 Nj之間的歸一化權值w′ij與 w′ji值不相同，因此結點間的選擇概率定義如下：

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

Pij越大，表明結點 Ni與 Nj被選擇在一起用于解決問題的概率越大。

給出Pij之后，同時結合Web服務選擇問題和遺傳算法，提出了如下的服務社會網絡算法(SSN Algorithm)：

某一結點Ni在某一服務實例WS中關于前驅后繼的平均選擇概率P的計算公式如下(前驅后繼可能不止一個，Num函數用于計算某一原子服務Si在某一服務流程中前驅與后繼的個數)：

3 實驗分析

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

(1)服務結點規模不同時對選擇算法執行時間的影響。

表1 各組原子服務類型規模及候選服務規模

選擇算法中的外層循環設置為1 000次，內層循環條件為當TBest有連續50次不發生變化或者循環滿3 000次時結束。算法在4個group下的執行時間如圖3所示，由圖可知，當整個社會網絡中總結點個數為3 000時，所用的時間剛剛1 s，而且隨著網絡規模的增加，執行時間的增長速率要緩慢得多。因此說網絡規模越大，SSN算法的執行效率越高。

(2)隨著社會網絡權值的不同找到最優解的概率

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

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

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

[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，FAUST K.Introduction to social network analysis[M].Cambridge Cambridge Univ.Press，1994.