黃迎春 ，左甜甜

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

0 引言

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

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

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

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

1 Skyline服務(wù)選擇

1.1 Skyline服務(wù)

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

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

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

圖1 Skyline服務(wù)示例圖

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

1.2 Skyline服務(wù)集的選擇命題

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

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

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

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

2 代表性Skyline服務(wù)選擇

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

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

同理，代表性Skyline服務(wù)即為在Skyline集合中的部分體現(xiàn)服務(wù)主成分的服務(wù)。

2.1 服務(wù)選擇中的效用函數(shù)

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

式（1）、式（2）中，

而組合服務(wù)CS的效用函數(shù)為

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

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

2.2 順序結(jié)構(gòu)組合服務(wù)選擇模型

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

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

1）將以下約束加入模型

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

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

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

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

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

2.3 基于代表性Skyline服務(wù)集的選擇分析

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

命題4通過優(yōu)化Skyline服務(wù)的匹配過程，QoS約縮短了服務(wù)匹配選擇時間。

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

3 代表性Skyline選擇算法

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

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

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

圖2 利用層次聚類確定代表性服務(wù)

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

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

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

圖3 基于k-means的Skyline服務(wù)聚類算法

圖4 生成代表性服務(wù)樹

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

4 試驗分析

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

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

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

2）Skyline服務(wù)選擇方法：在多屬性決策方法基礎(chǔ)上，采用Skyline服務(wù)。

3）代表性Skyline服務(wù)選擇方法：由本文算法1和算法2構(gòu)造的基于代表性Skyline服務(wù)選擇方法。

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

圖5 對比不同候選服務(wù)數(shù)量上的執(zhí)行時間

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

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

實驗2：比較整數(shù)線性規(guī)劃和代表性Skyline方法的服務(wù)選擇執(zhí)行時間和QoS約束的服務(wù)效用值。

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

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

圖7 對比不同候選服務(wù)數(shù)量上服務(wù)組合執(zhí)行時間

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

圖8 對比不同候選服務(wù)數(shù)量服務(wù)組合效用值

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

5 結(jié)論

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