QoS約束的代表性Skyline Web服務選擇*

黃迎春 ，左甜甜

（1.沈陽理工大學信息科學與工程學院，沈陽 110159；2.東北大學計算機科學與工程學院，沈陽 110169）

0 引言

在新一代軍事指揮控制系統中，面向服務的體系結構（SOA，service-Oriented Architecture）應用趨勢明顯增長，Web service已經成為構建的SOA指控系統的重要技術。Web服務搜索引擎Seekda［1］公開發表的統計信息表明，近年來，Web service在數量上以指數性指標增長。指控用戶面對大量功能相似但QoS不同的服務信息，如何按需選擇匹配服務成為亟待解決的問題。特別地，當前許多服務匹配、選擇算法在按照QoS指標選取服務時，將顯著增加服務選擇的計算復雜度，所以實現快速的服務選擇就變得非常緊迫。

QoS約束的Web服務選擇包括兩種策略：局部選擇策略和全局選擇策略，常用的Web服務局部選擇方法，主要基于多屬性決策理論［2］，包含服務需求定義、服務QoS參數預處理、服務QoS指標賦權以及候選服務排序等服務選擇過程。全局選擇策略即組合服務選擇策略，常用的方法是0-1整數規劃、基于全局QoS約束分解的分布式組合服務選擇方法，分支界限法、啟發式算法（如遺傳算法、蟻群算法和粒子群優化算法等）。

由于傳統的基于全局選擇策略和局部選擇策略均以全部服務庫作為候選服務集合，隨著候選服務集服務數量的增長，上述策略的服務選擇時間顯著增長。為了去除冗余服務，吳鍵等［3］引入數據庫查詢中Skyline方法，利用Skyline中的支配關系，縮小了候選服務空間。王尚廣等人［4］首先通過云模型計算QoS的不確定性，然后采用整數規劃在Skyline服務中進行服務選擇。吳建等［5］提出一種利用MapReduce思想進行并行Skyline服務選擇的方法，并探討了一種稱為紙帶模型的動態Skyline服務更新方法。

當某一服務類的Skyline服務數目太大，從而不能有效處理時，提出在多個QoS屬性之間進行權衡，并選擇一系列具有代表性的Skyline服務作為服務選擇模型的輸入服務集，使得這些服務最可能成為優化選擇中的服務，滿足用戶的QoS約束并使得效用最大化。

1 Skyline服務選擇

1.1 Skyline服務

給定一系列N維空間的點，Skyline查詢選擇那些沒有被其他任何點支配的點。若某點Pi在所有N個維度均不劣于另外某個點Pj，而且至少在某個維度上優于Pj，則稱點Pi支配點Pj。借鑒Skyline的思想，可以基于服務QoS屬性值定義服務之間的優勢關系，并將其用于某一類服務中被其他服務支配的服務，進行服務選擇時可以忽略這些被支配的服務，從而降低服務選擇時需要考慮的服務數量。

定義1服務支配：設某個服務候選集存在某種服務類別S，S中的兩個服務x，y∈S，每個服務包含一組QoS屬性。x支配y，記為，當且僅當x的所有QoS值不劣于y，且x至少有一個QoS屬性值嚴格優于y，即

定義2 Skyline服務集：候選服務集的某類服務子集，記作SLs，其集合元素是服務類別S中不被其余服務支配的全部服務集合，即。SLs中的服務被稱作服務類別S中的Skyline服務。

圖1 Skyline服務示例圖

圖1為一個服務類別中的Skyline服務示例圖。其中，任何一個服務由響應時間和費用兩個QoS屬性組成［11］。所以，可以用平面上的一個點表示一個服務，點的坐標對應服務的QoS屬性的值。從圖1中可以看出：，原因是不存在其他任何服務支配服務a，即不存在有其他服務的服務費用高于a，且響應時間低于a，所以a屬于Skyline服務集；同樣可以得出b、c、d以及e也是Skyline服務。反之，服務f不是一個Skyline服務，因為f被服務b、c和d支配。

1.2 Skyline服務集的選擇命題

文獻［4］給出并證明了Skyline服務集的選擇命題1，即最優服務必須來自Skyline服務集。

命題2基于Skyline服務集的服務選擇能夠提高服務選擇的效率。

證明：因為用戶需求對QoS屬性的約束條件與確定Skyline服務不相關，因此，不需要在進行優化選擇時實時在線實時進行Skyline服務選擇。所以可以在進行服務匹配、選擇、組合時不再考慮那些不在Skyline中的服務，從而提高優化選擇的效率。

基于上述分析，服務代理可以為在服務注冊中心維護一個Skyline服務列表。該列表在每一次有服務加入、離開、或者已注冊服務QoS信息有變化時進行更新。當服務代理收到一個服務請求時，就直接向服務請求者返回匹配的服務類別中的Skyline服務。

2 代表性Skyline服務選擇

在現實環境中，Skyline集合中對象的數量會隨著維度的增加呈指數增長。因此，在高維空間，盡管Skyline方法已經裁剪了大部分的對象，但是仍然會向用戶呈現大量的Skyline對象，因此，使用Skyline方法只是第一步，本節對Skyline服務集進行篩選，得到最具代表性的Skyline服務達到縮小Skyline服務集的目的。

定義3代表性服務：代表性服務是在服務集合中能夠反應同一類事物共同特征，并能夠代替該服務集合中服務的部分服務，是整個服務集服務主成分的體現。

同理，代表性Skyline服務即為在Skyline集合中的部分體現服務主成分的服務。

2.1 服務選擇中的效用函數

QoS約束的局部服務選擇或全局服務選擇均為在滿足QoS約束條件下選擇使QoS效用函數值最大的服務。服務選擇中的效用函數可采用兩個步驟計算：首先規范化服務QoS屬性值，即將不同量綱與值域的QoS屬性進行屬性值尺度上的規范并統一。其次基于不同指控用戶對QoS屬性的偏好進行量化并賦權，通過加權計算服務效用函數值［6-8］。QoS約束的局部服務可采用多屬性決策理論的加權和法計算服務效用函數值。然而對于QoS約束的全局服務選擇，可用抽象組合服務流程對應的一個具體組合服務的第k個QoS屬性的最大、最小聚合值計算過程可以形式化描述為

式（1）、式（2）中，

而組合服務CS的效用函數為

式（7）中，ωk∈R+表示用戶對組合服務 QoS 屬性 q′k的重視程度（即權重）。

2）整體效用U′（CS）最大化。

2.2 順序結構組合服務選擇模型

完全順序結構的服務組合問題是一個0-1整數規劃問題，可以采用文獻［6，9-10］提到的方法進行求解。在基于0-1整數規劃的QoS約束服務選擇問題時，服務sji是否被選擇可表示為0，1二元決策變量xji，若xji=1，則表示在服務集合中包含候選服務sji，若xji=0，則表示在服務集合中不包含候選服務sji。根據以上分析，基于0-1整數規劃的QoS約束服務選擇問題可被轉換成為組合服務整體效用值的最大值求解問題，0-1整數規劃的目標函數可定義為

為保證被選取的指控服務聚合值滿足全局QoS約束條件，必須將其他的約束條件引入整數規劃模型。具體包括：

1）將以下約束加入模型

式（9）表示聚合的QoS屬性采用累加方式，如響應時間、價格、信譽度等QoS屬性。

2）若QoS屬性之間采用乘法運算，例如：可用性、可靠性、可能性等指標，約束條件可表示為

為計算方便，也可對式（10）取自然對數，將乘法運算轉換成加法運算，如式（11）所示。

3）將如下約束條件加入模型

式（12）表示基于最小化函數的QoS屬性約束，如容量等。

2.3 基于代表性Skyline服務集的選擇分析

命題3如果某個服務si屬于服務類S，并且服務si支配了另一個服務sj，則服務si的效用函數值必然優于服務sj的效用函數值。

命題4通過優化Skyline服務的匹配過程，QoS約縮短了服務匹配選擇時間。

證明：通過QoS聚類操作后，代表性Skyline服務選出了效用函數值最優的Skyline服務，進而實現了指控服務的最優匹配，所以通過提高服務匹配成功率，縮小了服務搜索范圍，縮短了服務選擇時間。

3 代表性Skyline選擇算法

代表性Skyline服務選擇算法的基本原理是：首先采取層次聚類操作，將Skyline服務SL聚類為k個簇，k≤|SL|，并且k為偶數；其次選取服務效用函數值最大的服務作為代表性Skyline服務。為實現代表性Skyline服務選擇算法，采用樹形結構表示代表性Skyline服務的層次關系數據結構，如圖2（d）所示。圖2（d）中，樹結點對應SL中的一個Skyline服務，除葉子外，其余結點表示在相應簇中選擇的代表性服務。

具體的服務搜索策略如下：指控服務選擇服務器首先接收用戶服務請求，從圖2（d）所示的服務樹的根結點開始搜索，由于根結點代表服務集中的頂層服務（圖2（d）中的頂層服務為候選服務s3），因此，首先搜索頂層服務。如果位于該層次的服務不能滿足用戶的QoS約束的屬性值，則繼續向樹的下層進行搜索，不斷重復該過程，進行從根向葉子的路徑搜索，搜索過程終止于樹的分支結點和葉子結點。如果搜索到葉子結點，說明問題無解，否則，如果問題有解，根據命題1，搜索過程將終止于分支結點，因此，必然會通過遍歷二叉樹求解出最佳的服務選擇結果。

對于組合服務來說，候選服務則作為組合方案選擇模型的輸入進行求解。如果使用給定的代表服務沒有得到滿足用戶的QoS約束條件，則繼續處理下一個級別的代表服務，不斷重復該過程，直到找到一個解或者已經到達樹的最底層，即已經嘗試了所有的Skyline服務。如果問題有解，根據命題1，則遍歷完該二叉樹一定會找到優化選擇結果。

圖2 利用層次聚類確定代表性服務

建立代表服務樹的過程本文利用k-means聚類算法完成。利用k-means算法對服務類S的Skyline服務SL進行聚類，將SL劃分為k個簇SL={sl1，sl2，…，slk}，其中，使得每個簇之間的距離平方和最小，即

式（13）中，μi表示簇i中服務的質心，也稱為均值。在多維QoS屬性情況下，服務質心的坐標定義為各QoS維度的平均值。

代表性Skyline服務選擇算法主要分為算法1：基于k-means的Skyline服務聚類算法（如下頁圖3所示）以及算法2：生成代表服務樹算法（如圖4所示）。

圖3 基于k-means的Skyline服務聚類算法

圖4 生成代表性服務樹

以算法1的k-means算法為基礎，進一步設計算法2，用來生成代表性Skyline服務樹。算法2的基本原理如下：步驟1，計算SL中效用函數值最大的結點s，然后再以s作為的根結點子簇上進行搜索；步驟2，通過k-means算法輸入SL，生成兩個子簇 CLs［1］和 CLs［2］的聚類集合，分別計算 CLs［1］和CLs［2］子簇中效用函數值最大的兩個結點，并將它們分別作為根s的左右孩子結點構造一顆新的二叉樹；步驟3，不斷對每個子簇重復執行步驟2，使二叉樹不斷生長，直至最終子簇中的服務數量小于2為止，至此，通過輸入Skyline服務集合SL，最終輸出以s為根結點的代表性服務二叉樹。

4 試驗分析

基于開放的QWS數據集進行實驗以驗證算法的有效性。QWS數據集包含了2 442個Web服務及其參數，這些服務分別來自于服務門戶網站、UDDI服務注冊中心、互聯網搜索引擎等渠道，由Eyhab Al-Masri博士采用 WSCE（Web Service Crawler Engine）工具構建。QWS數據集中包括了服務吞吐率、服務響應時間等8個QoS屬性參數值。實驗環境基于Windows 7操作系統，CPU來自Inter公司，主頻3.3 GHz，內存為4 GB；使用Java、R語言編寫了相關軟件。為了驗證算法性能，設計了如下兩組實驗。

實驗1：比較3種QoS約束下Web服務選擇算法執行時間。

1）多屬性決策服務選擇方法：不采用Skyline服務，僅使用局部選擇算法。

2）Skyline服務選擇方法：在多屬性決策方法基礎上，采用Skyline服務。

3）代表性Skyline服務選擇方法：由本文算法1和算法2構造的基于代表性Skyline服務選擇方法。

對于3種服務選擇方法，當服務數量在100～1 000之間取值時，固定QoS維度及其參數值，測試服務選擇的執行時間，實驗結果如圖5所示。固定候選服務數量，當QoS屬性維度及其參數值在2～8之間變化時，測試服務選擇的執行時間，實驗結果如圖6所示。

圖5 對比不同候選服務數量上的執行時間

圖6 對比不同QoS屬性維度上的執行時間

從圖5和圖6中可以看出：1）多屬性決策方法由于搜索空間較大，導致對QoS參數值的評價數據量較大，因此，排序時間較長，所以多屬性決策方法的服務選擇執行時間最長。2）Skyline方法通過篩選方法過濾掉不必要的候選服務，縮小了服務選擇的目標集合，因此，在多屬性決策方法基礎上，縮短了服務選擇的執行時間。然而，有些情況下其候選服務集依舊較大時，其性能處于3種方法的中間水平。3）在Skyline方法的基礎上，由于引入了代表性Skyline算法，當服務數量和QoS屬性維度增加時，依然能夠取得3種方法中最短的服務選擇實行時間。

實驗2：比較整數線性規劃和代表性Skyline方法的服務選擇執行時間和QoS約束的服務效用值。

實驗參數包括：1）輸入由10個服務組成的Web服務組合組件；2）每個組件的服務數量為100個～1 000個。

實驗中的整數線性規劃求解基于Skyline服務選擇方法，采用文獻［4］給出的啟發式算法。代表性Skyline方法同樣采用求解整數線性規劃方法，不同的是在服務選擇組件中選擇代表性Skyline服務。實驗2的測試結果如圖7和圖8所示。

圖7 對比不同候選服務數量上服務組合執行時間

從圖7中可以看出：當候選服務數量在100～1 000范圍內變化時，代表性Skyline服務選擇算法明顯優于僅結合Skyline服務的整數規劃算法，其服務選擇執行之間至少縮短了25%，且當服務數量大于800時，二者的服務選擇執行時間差距顯著增加。

圖8 對比不同候選服務數量服務組合效用值

從圖8中也可以得出代表性Skyline服務選擇算法在效用值指標上也明顯優于僅結合Skyline服務的整數規劃算法，其服務選擇平均效用值約提升10%。

5 結論

在存在QoS約束的服務選擇中，不僅需關注服務組合的功能，還需考慮服務選擇的性能優選服務。通過在傳統的多屬性決策變量的方法基礎上，提出了代表性Skyline服務選擇算法，該方法基于k-means的Skyline服務聚類算法，通過生成具有多維QoS屬性的代表性Skyline服務二叉樹，在縮小服務候選集合的基礎上，通過樹形結構查找高效的特點提升了服務選擇性能指標。通過在QWS數據集應用代表性Skyline服務選擇算法進行了數據實驗，結果表明所提出的方法在服務選擇執行時間和服務效用值兩個指標上均優于傳統算法。對于QoS約束的Web服務選擇的后續工作，需進一步對組合服務Skyline計算以及對Web服務的QoS預測方面進行研究。