QoS約束下的語義web服務組合評估及優(yōu)化

王向輝，馮志勇

(1. 天津大學計算機科學與技術學院，天津 300072；2. 山東建筑大學計算機學院，濟南 250101)

QoS約束下的語義web服務組合評估及優(yōu)化

王向輝1,2，馮志勇1

(1. 天津大學計算機科學與技術學院，天津 300072；2. 山東建筑大學計算機學院，濟南 250101)

針對 QoS約束下的語義 web服務組合的多個組合方案，提出組合質量概念，并改進組合算法以便快速獲得高質量組合方案．針對組合質量的不同指標，引入質量平衡系數(shù)，構造可調節(jié)的啟發(fā)函數(shù)，并增加到兩步組合算法的后向搜索中，從而使用戶通過調節(jié)質量平衡系數(shù)，獲得預期質量的組合方案．為了提高組合速度，在高效數(shù)據(jù)存儲結構的基礎上，采用逐步變窄的前向搜索策略．基于前述改進的算法實現(xiàn)一個組合規(guī)劃器．實驗表明該規(guī)劃器能夠快速給出滿足QoS約束的組合方案，且通過質量平衡系數(shù)的設置，能夠給出滿足預期質量的組合方案．

web服務組合；組合質量；兩步搜索；QoS；質量平衡系數(shù)

Web服務在跨語言、跨平臺的數(shù)據(jù)交換和集成方面有著突出優(yōu)勢，成為實現(xiàn)SOA系統(tǒng)的首選[1]．隨著 web技術的發(fā)展，互聯(lián)網(wǎng)上出現(xiàn)了數(shù)量龐大的web服務，如何從中發(fā)現(xiàn)符合用戶需求的服務(服務發(fā)現(xiàn))是一項挑戰(zhàn)性的工作，并受到服務計算領域研究者的廣泛關注．在服務發(fā)現(xiàn)過程中，如果單個 web服務可能無法滿足用戶需求，就需要 web服務組合技術[2]，即從龐大的web服務集合中查找一組可組合的web服務，并形成滿足用戶需求的組合方案．語義web技術[3]的出現(xiàn)，解決了來自不同服務供應商、涉及不同領域的 web服務間的概念語義匹配問題，為實現(xiàn)web服務的自動組合奠定了基礎．

QoS感知的 web服務組合問題，是近些年來的一個研究熱點．它在組合過程中不僅考慮 web服務的功能屬性，還要考慮與功能無關而與 web服務質量相關的 QoS屬性，如響應時間、吞吐量、價格等，最終獲得QoS最優(yōu)的組合方案．關于這個問題，當前采取的解決方法有 3種：一是基于 web服務的功能屬性找到若干組合方案，然后按照 QoS值進行排序[4-6]；二是利用任一時間算法首先找到一個組合方案，然后隨著時間的推移將會遍歷到所有組合方案，所以最終能得到 QoS值最優(yōu)的方案[6-7]；三是改進兩步搜索算法，直接找到QoS最優(yōu)的組合方案[8-11]．

雖然前兩種方法最終能夠找到 QoS最優(yōu)的方案，但它們的執(zhí)行效率不高，而最后一種方法可以快速地獲得QoS最優(yōu)的組合方案．但針對一個QoS屬性(如最短響應時間或最大吞吐量)，有的只是給出一個最優(yōu)組合方案[8-10]，有的則能夠給出全部的最優(yōu)方案[11]．然而，對于語義 web服務組合來說，在獲得某個 QoS屬性值的多個最優(yōu)解后，用戶將面臨新的選擇，即如何從中選擇一個最好的方案，這對組合方法的使用來說是迫切需要解決的問題．為此，本文提出一個組合方法，該方法能夠快速找到滿足 QoS約束的組合方案，且能夠按照用戶的偏好給出一個較好的組合方案．本文有3個創(chuàng)新點．

(1) 提出組合質量概念，將組合方案的語義質量、服務數(shù)和路徑等都作為組合質量的組成元素，使用戶可從這幾個方面對 QoS相同的組合方案進行評價和比較．由于當前沒有統(tǒng)一的組合語義評價模型，本文提出一個語義質量模型，它利用參數(shù)概念間的匹配關系和路徑長度來確定組合方案的語義質量．

(2) 將 web服務按照輸入?yún)?shù)概念聚類并存儲，然后在組合算法中采用逐步變窄的前向搜索策略，使得前向搜索不再成為兩步組合算法的瓶頸，從而保證了組合算法的高效性．

(3) 針對組合質量的不同指標，引入質量平衡系數(shù)，構造可調節(jié)的啟發(fā)函數(shù)，并增加到兩步組合算法的后向搜索中，從而使用戶通過調節(jié)質量平衡系數(shù)，獲得預期質量的組合方案．

1 問題定義

語義web服務組合問題包含問題域、語義本體、用戶請求和組合方案4個要素．為了對本文討論的組合問題有一個清楚的認識，這里先描述這4個要素．

一個問題域是所有可用的 web服務組成的集合．為了解決QoS約束下的組合問題，這里除了描述web服務的功能屬性外，還需要描述QoS屬性，如響應時間、吞吐量、價格等．

定義1 帶QoS的web服務．web服務是一個四元組＜ws，Is，Os，QoSs＞，其中 ws為服務名，Is為輸入?yún)?shù)集合，Os為輸出參數(shù)集合，QoSs為服務提供的質量集合．這里QoSs中的每個質量使用三元組描述＜QoSn，QoSv，QoSr＞，即 QoSn名稱，如＜Responsetime，300,ms，MAX＞表示QoS的最長響應時間為300,ms．

定義2 帶QoS的問題域．帶QoS的問題域是一個集合，其中的每個元素為帶QoS的web服務．

在問題域中，web服務間是否能夠組合，主要取決于一個服務的輸入?yún)?shù)集與另一個服務的輸出參數(shù)集概念間是否能夠匹配．在同一本體內，概念間的匹配關系體現(xiàn)在本體中的語義匹配關系．而概念集間是否匹配表現(xiàn)為它們間滿足的關系，具體定義如下.

定義 3 語義匹配關系．令 C為概念集合，x、y∈C，MR為語義匹配函數(shù)，若y＝MR(x)，則說明在函數(shù)MR的作用下，概念y可用概念x代替，即x在語義上匹配y，或y在語義上被 x匹配，表示為序偶＜x，y＞ MR∈ ．

在后面的描述中，通常將 MR看作語義匹配關系的集合．顯然，語義匹配關系具有自反性和傳遞性.

定義 4 語義滿足關系?MR．令 C為概念集合，MR為C中概念間的語義匹配關系集合，R和S是C的子集，則R?MRS＝(?x)(x∈R→(?y)y∈S∧＜x，y＞ MR∈ ．

定義 5 帶 QoS的用戶請求．該用戶請求是一個三元組＜RIs，ROs，RQoS＞，其中RIs表示請求的輸入?yún)?shù)集合，ROs表示期望的輸出參數(shù)集合，RQoS表示對組合方案的 QoS期望．如＜Responsetime，3,000,ms，MAX＞表示用戶期望的響應時間不超過3,000,ms．

定義 6 帶 QoS的組合方案．該組合方案是一個四元組＜CIs，，COs，CQoS，CG＞，其中，CIs為其接受的輸入?yún)?shù)集合，COs為其產(chǎn)生的輸出參數(shù)集合，CQoS為其提供的QoS，CG為組合方案對應的帶標記的有向無環(huán)圖．這里，CG中的節(jié)點表示web服務，有向邊表示服務參數(shù)概念間的語義匹配關系，其上的標記記錄從始端節(jié)點的輸出參數(shù)到終端的輸入?yún)?shù)間的所有語義匹配關系．已知概念語義匹配關系集合MR，WS為CG中的web服務集合，則CG需滿足下列條件：

(1) 對于任一入度為 0的 web服務 ws，滿足ws.Is?MRCIs；

(2) 對于任一入度為k(k≠0)的web服務ws，假設mri表示指向ws的第i條有向邊上的語義匹配關系集合，則滿足?in.(in ∈w s.Is→?out.＜out，in＞∈∪1≤i≤kmri)，且

(4) 給定QoS計算函數(shù)fQoS，則符合上述3個條件的有向圖CG，滿足fQoS(CG)＝CQoS；

(5) 如果去掉CG中的任意一個節(jié)點，形成一個新的有向圖 CG’，則 CG’不能同時滿足上述的 4個條件．

這里使用帶標記的有向無環(huán)圖來表示組合方案，它能更加直觀地展現(xiàn)組合方案中的控制流和數(shù)據(jù)流結構，方便向標準的工作流執(zhí)行語言轉換，如 WSBPEL[12]．同時，定義 6中的(1)～(3)條限定了組合方案需滿足用戶的功能請求；第(4)條要求組合方案滿足用戶的非功能請求，這兩方面是保證組合方案正確性的必要條件；而第(5)條要求組合方案不存在冗余的web服務，這在組合方案執(zhí)行時，可減少重復執(zhí)行，提高執(zhí)行效率．

需要注意的是，有向無環(huán)圖表示的組合方案能夠轉換成帶并行和順序結構的工作流描述，見定理1．

定理 1 定義 6中描述的組合方案中的有向圖CG能夠轉換成帶并行和順序結構的工作流W．

證 明 wsout0表示組合方案 CG中出度為 0的web服務集合，可以按照下面的步驟生成W：

(1) 對于 wsout0中入度為 0的任一 web服務ws，其對應的工作流Wws＝invoke(ws)；

(2) 對于 wsout0中入度大于 0的任一 web服務ws，進行下面的處理：①在 CG中查找使 ws得以滿足的最小子圖Gws；②wsout0’為Gws中指向ws的web服務集合，ws’為wsout0’中任一web服務，令wsout0＝wsout0’，則重復步驟(1)、(2)，可得到 ws’對應的工作流 Wws’；③生成一個并行結構 flow(Wws’)，即將wsout0’中的每個 web服務對應的工作流作為其中的一個分支；然后再生成一個順序結構 sequence (flow(Wws’)，invoke(ws))，即執(zhí)行flow結構，再執(zhí)行invoke結構，這時Wws＝sequence(flow(Wws’)，invoke (ws))．

(3) 在W中創(chuàng)建并行結構flow(Wws)，即將每個Wws作為 flow的一個分支．這時，整個組合方案 CG的工作流轉換完成．證畢．

定義 7 ,QoS約束下的語義 web服務組合問題．給定帶QoS的問題域WS，帶QoS約束的服務請求 R，概念語義匹配關系集合 MR，服務組合問題即為確定是否存在一個帶 QoS的組合方案 CR，滿足CR.CIs＝R.RIs，CR.COs＝R.ROs，且 CR.CQoS符合R.RQoS．

由于在解答一個 QoS約束下的組合問題時，會獲得多個不同的組合方案，它們都滿足給定的 QoS約束條件．因此，其他質量因素成了這些組合方案相互比較的依據(jù)，如參數(shù)間的語義匹配度、web服務的個數(shù)、服務路徑的長度等．為了同 QoS質量相互區(qū)別，本文將這些質量因素稱為組合方案的組合質量．這樣，具有優(yōu)良組合質量的組合方案可以稱為一個好的組合方案，而對于QoS約束下的web服務組合來說，找到一個好的組合方案是一件有意義的事情，也是本文研究的重點．下面首先介紹帶QoS的組合方案(定義6)的QoS質量和組合質量的計算方法，然后再介紹具體的組合方法．

2 質量模型及評估

為了簡化處理，在本文的組合問題中，將響應時間作為組合問題的 QoS約束條件，同時在組合方案選取時考慮語義匹配度和服務個數(shù)這兩個組合質量屬性．這里將分別描述組合方案在每種質量指標下的計算模型．

2.1 ,QoS質量

在文獻[13]中給出了帶有并行和順序結構的BPEL組合方案的QoS計算方法，而對于組合方案來說，基于有向圖的表達形式更具有普遍性，因此，這里基于定義6描述的有向圖給出一個等價的QoS計算模型MinRQM．

假定G為一個組合方案的有向圖，這里將G中重復出現(xiàn)的web服務看作是不同的web服務．對于G中每個 web服務 ws，使用 frts(ws)獲得其本身執(zhí)行的最大響應時間，ind(ws)表示 ws節(jié)點的入度，wsin表示指向ws的web服務集合．則在G中ws得以執(zhí)行的最短響應時間的計算函數(shù)如下：

即對于入度為0的web服務，根據(jù)定義6中的第(1)條，它們的輸入?yún)?shù)均由用戶請求直接提供，所以其在組合方案中的響應時間即為自身的響應時間．而對于入度非 0的 web服務，它們的執(zhí)行時間是在所有提供其輸入?yún)?shù)的 web服務執(zhí)行完畢后，所以根據(jù)定義6中的第(2)條，wsin中的web服務均執(zhí)行完畢后才可執(zhí)行ws．同時，為了節(jié)約時間，對wsin中每個web服務的不同執(zhí)行路徑，采用并行方式執(zhí)行，因此，這些執(zhí)行路徑最短響應時間的最大值才是 ws開始執(zhí)行的時間，再加上ws本身的響應時間，即為ws在整個組合方案G中的最短響應時間．同時，考慮組合方案G的有向無環(huán)性，frt函數(shù)能夠保證求得G中每個ws的最短響應時間．

使用wsout0表示組合方案G中出度為0的web服務集合，則根據(jù)每個web服務的最短響應時間，組合方案G的最短響應時間的計算函數(shù)如下：

即G中出度為0的web服務將在組合方案的最后執(zhí)行，它們中最短響應時間中的最大值才能保證所有的ws都執(zhí)行完畢，因此取最大值作為整個組合方案的最短響應時間．這里，函數(shù)公式(1)、(2)構成了最短響應時間計算模型MinRQM．根據(jù)定理1中的步驟，容易證明用 MinRQM模型計算的 G最短響應時間和與其對應的工作流 W的最短響應時間相同，其中W的計算方式與文獻[13]中的描述方式相同．這里通過實例來說明轉換過程和最短響應時間，見圖1．

圖1 組合方案及其工作流結構Fig.1 A solution and its workflow structure

圖 1(a)表示用有向圖形式描述的一個組合方案，其中每個橢圓里面分別標注了服務名和響應時間．根據(jù) MinRQM模型，frt(ws5)＝max{frt(ws3)，frt(ws4)}＋100，而 frt(ws3)＝frt(ws1)＋50＝250， frt(ws4)＝max{frt(ws1)，frt(ws2)}＋100＝300，所以frt(ws5)＝max{250，300}＋100＝400；又 frt(ws6)＝frt(ws4)＋200＝500，且ws5和ws6都是出度為0的節(jié)點，因此，圖 1(a)描述的組合方案的最短響應時間為max{frt(ws5)，frt(ws6)}＝500．

圖 1(b)是對應圖 1(a)的工作流描述，它使用Flow前綴描述了并行結構；使用 Seq描述了順序結構，并且在該圖中默認左邊的分支先于右邊的分支執(zhí)行；使用Inv前綴表示對具體web服務的調用．在最短響應時間的計算方法[14]中，規(guī)定并行結構取分支的最大響應時間作為該結構的最短響應時間，順序結構則取所有分支響應時間的總和作為順序結構最短響應時間．根據(jù)這個規(guī)定，可以計算得到圖中 Seq1的最短響應時間為 400，Seq2的最短響應時間為500，因此 Flow1的最短響應時間為 max{Seq1，Seq2}＝500．這與圖1(a)使用MinRQM模型計算的結果相同．

2.2 組合質量

對一個組合方案來說，服務數(shù)和路徑長度都有統(tǒng)一的計算方法，而對于體現(xiàn)其參數(shù)間語義匹配程度的語義質量來說，并沒有統(tǒng)一的計算方法，這里提出一個簡捷合理的組合方案語義質量模型WSCSQM．

在描述組合方案的語義質量之前，首選需要確定每對匹配的參數(shù)概念間的相似度．這里假定所有的概念使用本體描述，概念之間的關系由它們在本體層次上的匹配類型和距離確定．匹配類型采用 Exact、Plugin和Subsume 3種類型[15]，同時借鑒匹配質量計算方法[14]，取 Exact匹配類型的概念間相似度為 1，Plugin為3/4，Subsume為1/2．已知參數(shù)a1、a2，其類型分別為t1、t2，若a1匹配a2，則t1與t2的匹配關系為Exact、Plugin、Subsume中的一種，其計算函數(shù)如下：

定義6描述的組合方案的有向圖中，雖然通過邊上的標記描述了參與組合的web服務間的參數(shù)匹配信息，但未展示用戶請求中的參數(shù)與web服務具體參數(shù)間的匹配信息．而這些信息在整個組合方案語義質量計算中不可缺少，因此，本文通過引入初始請求服務和目標請求服務來擴展前面的組合方案定義．

定義 8 初始請求服務．初始請求服務是一個web服務，它沒有輸入?yún)?shù)，只有輸出參數(shù)，且輸出參數(shù)為用戶請求的初始參數(shù)集合．

定義9 目標請求服務．目標請求服務也是一個web服務，它只有輸入?yún)?shù)，沒有輸出參數(shù)，且輸入?yún)?shù)為用戶請求的目標參數(shù)集合．

給定用戶請求 R，其提供的輸入?yún)?shù)為{1#，2#，3#，4#}，輸出參數(shù)為{18#，19#}，引入初始和目標請求兩個擴展服務，并在邊上加入標記后，圖 1(a)的組合方案轉變成擴展的帶標記組合方案，見圖 2．在圖2中，帶#后綴的數(shù)字表示參數(shù)名．若邊上只標注一個參數(shù)名，表明兩端web服務通過同名參數(shù)匹配；若使用尖括號標記，則表示兩端 web服務通過不同的參數(shù)名匹配，其中，第1個參數(shù)名為始端web服務的參數(shù)，第2個為終端的參數(shù)，如ws1和ws3間的＜7#，9#＞，表示ws1的參數(shù)7#與ws3的參數(shù)9#在語義上匹配；若使用花括號標記，則表示兩端web服務間有不止1對參數(shù)能夠匹配，如ws4與ws6間的{＜15#，15#＞，＜20#，21#＞}，表示ws4的參數(shù)15#匹配ws6的15#，ws4的20#匹配ws6的21#．

圖2 擴展的帶標記組合方案Fig.2 An extended solution with labels

直觀地，組合方案中的每個執(zhí)行路徑的語義質量，是由路徑上的每個 web服務的語義質量決定的．因此，這里給出每個web服務ws在執(zhí)行路徑上的語義質量，即執(zhí)行到該web服務時，參數(shù)的語義匹配質量，其計算函數(shù)如下：

式中：wsin為有向圖中指向 ws的 web服務集合；label(wsi，ws)為有向邊(wsi，ws)上的標記集合．

式(4)表示 web服務在執(zhí)行路徑上的語義質量等于其所有輸入?yún)?shù)的語義質量的平均值，而每個輸入?yún)?shù)的語義質量則等于與之匹配的輸出參數(shù)的匹配度，與產(chǎn)生這個輸出參數(shù)的 web服務語義質量的乘積．若指定 ws為目標請求服務，則該公式計算的結果即為整個組合方案的語義質量．

從式(4)可以看出，fsd函數(shù)的計算是通過遞歸的方式完成的，并且其取值區(qū)間是(0，1]．在執(zhí)行路徑前面的參數(shù)匹配情況會通過路徑上的 web服務傳遞下去，這是與實際情況相符的．例如，若某個非初始請求服務 ws執(zhí)行路徑上的所有參數(shù)的匹配度都為1，則這個路徑上所有的web服務的語義質量也為1，最終根據(jù)式(4)，ws的語義質量也為 1．若執(zhí)行路徑上存在參數(shù)匹配度小于1的匹配，則整個組合方案的語義質量將小于 1．如果這種近似匹配經(jīng)過的路徑越長，則其匹配度越低，從而說明了匹配過程中的語義損耗．

式(3)、式(4)構成了組合方案的語義質量模型WSCSQM．下面通過計算圖 2中組合方案的語義質量來說明WSCSQM模型的使用．這里，假設出現(xiàn)在邊上不同參數(shù)名間的匹配對(即尖括號中參數(shù)名不同的標記)匹配度為0.75，同名參數(shù)的匹配度為1，則整個組合方案的語義質量為 fsd(目標請求)．根據(jù)式(4)若要計算fsd(目標請求)，則需從頭計算每個執(zhí)行路徑上的web服務的語義質量，計算過程如下：

同樣的算法，可以得到 fsd(ws5)＝0.615,234，fsd(ws6)＝0.669,922，最終 fsd(目標請求)＝0.481,933．

組合方案的服務數(shù)也是衡量組合方案質量的一個重要指標．這里將組合方案最終執(zhí)行的 web服務的個數(shù)作為其服務數(shù)，并不是不同的 web服務個數(shù)．如圖 1表示的組合方案，其服務數(shù)為 10，即圖1(b)中展示的 Invoke個數(shù)，而不是圖 1(a)中的服務個數(shù)6．因為在實際執(zhí)行中，ws1、ws2和ws4將被重復執(zhí)行．

3 組合方法

前面已給出了QoS約束下的語義web服務組合問題的定義和組合方案的質量模型及評估方法，本節(jié)給出一個高效的問題解決方案，它保證得到的組合方案能夠滿足給定的 QoS約束，且具有較高的組合質量．

3.1 系統(tǒng)框架

WS-Challenge2010[13]給出了一個 web服務組合框架，但該框架是針對競賽的，不具有一般性．這里結合前面的定義，給出一個更加通用的系統(tǒng)框架．通過該框架不僅能夠解決文獻[13]中的問題，而且還能處理本文提出的新問題．由于 web服務組合問題本質上是AI規(guī)劃問題[16]，所以這里將web服務組合系統(tǒng)稱為 web服務組合規(guī)劃器．由于該規(guī)劃器主要解決 QoS約束下的組合問題，因此這里簡稱為QoSWSCPlaner，其系統(tǒng)框架如圖3所示．

圖3 QoSWSCPlaner系統(tǒng)框架Fig.3 Framework of QoSWSCPlaner

從圖中可以看出 QoSWSCPlaner主要由問題預處理和組合引擎兩部分組成，前者對問題相關描述進行解析，包括問題的檢索空間即帶QoS的問題域、用戶的檢索請求即帶 QoS的用戶請求，以及描述兩者中參數(shù)概念間的語義關系的域本體，并對這些描述進行預處理生成便于組合引擎使用的數(shù)據(jù)結構．組合引擎是QoSWSCPlaner的核心，它改進了傳統(tǒng)圖規(guī)劃算法，在高效的數(shù)據(jù)結構的基礎上，采用逐步變窄的前向搜索和 QoS約束的后向啟發(fā)搜索重新設計了兩步搜索算法；同時，增加組合質量調節(jié)功能，使得用戶可以根據(jù)自己的偏好控制啟發(fā)函數(shù)，從而獲得期望質量的組合方案．此外，QoSWSCPlaner還可以利用生成工作流程功能將有向圖組合方案轉換成標準的工作流執(zhí)行文件．

3.2 問題預處理

作為QoSWSCPlaner輸入的問題域、域本體和用戶請求，通常使用各種現(xiàn)有的 XML文件存放，如使用WSDL或OWL-S等存放問題域中的每個web服務和用戶請求，使用 OWL來存放域本體描述．這就需要在解決組合問題之前首先對這些文件進行解析，并使用合理的存儲結構和存取方式進行組織和存儲，以便供后續(xù)的組合引擎使用．

在這一階段形成了兩個重要的數(shù)據(jù)存儲結構：一個用來存取 web服務的 wsSetByInput，另一個用來存取概念語義匹配關系的 matchRelations．前者使用哈希存儲結構，其中出現(xiàn)在問題域中的所有輸入?yún)?shù)以及能夠匹配這些參數(shù)的所有概念作為其索引鍵，能夠接受鍵值的 web服務集合作為其存儲值，而每個元素記錄 web服務及其被鍵值匹配的輸入?yún)?shù)．后者采用兩級哈希結構，記錄所有概念間兩兩匹配關系，一級鍵為被匹配的參數(shù)，二級鍵為匹配的參數(shù)，值為(0，1]范圍的數(shù)值，表示兩級鍵之間的匹配情況，其值按照式(3)計算得到．在規(guī)劃器運行時，所有的 web服務和語義數(shù)據(jù)都按照這兩種存儲結構直接加載到內存中，這樣可減少對外存的訪問，從而加快整個規(guī)劃器的執(zhí)行速度．

3.3 組合引擎

基于圖規(guī)劃的兩步搜索算法經(jīng)常被用于進行web服務組合[4,11,16]．其核心思想是首先在問題域中的所有 web服務中，查找用戶請求輸入?yún)?shù)能夠滿足的所有 web服務，形成一個展現(xiàn) web服務執(zhí)行關系的有向分層圖，稱為前向搜索過程；接著在前向搜索得到的有向分層圖上，從后往前以深度優(yōu)先的方式查找能夠提供用戶期望輸出參數(shù)的 web服務執(zhí)行路徑，過濾掉那些與請求輸出參數(shù)無關的服務；最終，這些執(zhí)行路徑形成了web服務的組合方案．在QoS約束下的服務組合中，QoS約束主要體現(xiàn)在第2步的后向搜索中，即需要查找那些提供用戶期望輸出參數(shù)且滿足QoS約束條件的web服務執(zhí)行路徑，稱這個過程為QoS約束的后向搜索．

前向搜索關鍵的操作是在每一層都需要遍歷所有的 web服務以檢查其輸入?yún)?shù)是否被滿足，這個過程耗時巨大，直接影響著組合的效率．因此，為減少前向搜索的時間，研究者采取了各種措施[9,11,17].本文采用逐步變窄的前向搜索策略，并本著將重復檢查降到最低的原則，重新設計了一個快速的前向搜索算法．同時，為了方便QoS約束的后向搜索，算法在進行有向分層圖構建的同時，記錄并計算了每個web服務執(zhí)行路徑的最優(yōu) QoS值．QoSWSCPlaner組合引擎的執(zhí)行過程如圖4(算法1)所示．算法1 WebServiceComposition(matchRelations，wsSetByInput，QWr)

圖4 算法1Fig.4 Algorithm 1

圖中，outputInfos是 1個集合，記錄了每個參數(shù)和web服務的詳細信息，包括其最短響應時間、提供該參數(shù)的web服務集合等；QWr為帶QoS的用戶請求(定義 5)；compResult為帶有并行和順序結構的組合方案(行5～6)．

3.3.1 逐步變窄的前向搜索

算法1中的FastForeSearchToFixPoint函數(shù)實現(xiàn)了加速的前向搜索功能，其執(zhí)行過程如圖 5(算法 2)所示．該算法將用戶請求的輸入?yún)?shù)作為開始的當前狀態(tài) currentstates(行 1)；然后在 wsSetByInput中查找與 currentstates中輸入?yún)?shù)相關的 web服務集合(行 8～17)，這樣就在問題域中過濾掉大量不相關的web服務；接著在這些相關web服務中，查找其輸入?yún)?shù)都能夠被currentstates滿足的web服務，并將這些 web服務的輸出參數(shù)加入到 currentstates(行18～30)，這些web服務構成了有向分層圖的第1個層次；最后基于新的currentstates進行第2個層次的查找，依次類推，直到到達不動點整個前向查詢過程終止(行6)．

為了提高前向搜索的執(zhí)行速度，在算法2中采取了3項加速措施：

(1) 在查找相關 web服務過程中，為每個 web服務增加是否訪問標記isVisited(行12～15)，減少對已訪問web服務的重復添加；

(2) 在篩選滿足的 web服務過程，每個已滿足web服務在下一層次的篩選中也是滿足的，所以為其增加是否滿足標記 isSatisfied(行 20～23)，減少重復判斷；

(3) 判斷每個 web服務的所有輸入?yún)?shù)是否被當前狀態(tài)滿足，需要逐個判斷其匹配性，是相當耗時的．但注意到，WSsetByInput中其實保存了每個輸入?yún)?shù)與所對應的web服務的信息，因此，在查找相關web服務的過程中使用inputSetSatisfied順便記錄了當前狀態(tài)能夠提供的 web服務的那個輸入?yún)?shù)(行 11)．這樣，在滿足性判斷中，就不需對當前狀態(tài)和服務的輸入?yún)?shù)進行逐一語義匹配判斷，只需查看輸入?yún)?shù)集是否包含在inputSetSatisfied中(行24)．

此外，算法 2在建立有向分層圖的過程中，維護和更新了outputInfos(行3、21、27)，這些信息是后面計算 QoS約束組合方案的基礎．InitRespTime-

圖5 算法2Fig.5 Algorithm 2

算法2 FastForeSearchToFixPoint(wsSetByInput，matchRelations，QWr)OfReqparam函數(shù)用來將用戶請求的輸入?yún)?shù)能夠匹配的所有的參數(shù)的響應時間置 0，ComputeOptResp-Byws函數(shù)用來循環(huán)更新每個輸出參數(shù)的最短響應時間和能夠提供該參數(shù)的 web服務，以及 web服務在執(zhí)行路徑上的最短響應時間等信息．

3.3.2 QoS約束的后向啟發(fā)搜索

算法1中的BackSearchWithQoS函數(shù)實現(xiàn)了后向搜索，其過程如圖6(算法3)所示．

算法 3 DoBackSearchWithQoS(currentGoalStates，maxResponse，

圖6 算法3Fig.6 Algorithm 3

該算法遞歸地查找實現(xiàn)每個當前子目標的 web服務執(zhí)行路徑，且要求每條執(zhí)行路徑的響應時間在QoS范圍內，并將這些路徑組成一個并行結構的工作流程．在算法遞歸調用過程中，按照式(3)、式(4)遞歸計算了組合方案的語義質量(行7、19～21、24)．

對于一個 QoS約束下的組合方案來說，滿足QoS約束是其正確性的必要條件，但正確并不意味著質量高．一個高質量的組合方案應該具有響應時間短、語義質量高、服務數(shù)少、路徑短的特點．但實際中，約束下的多準則優(yōu)化問題是 NP-hard問題[18]，所以，目前沒有辦法找到滿足這些特點的最優(yōu)組合方案，只能通過近似算法找到其近似最優(yōu)解．這里的后向搜索算法，在選擇每個提供參數(shù)的web服務時，采用了綜合響應時間、語義質量和服務數(shù)特點的局部啟發(fā)策略(算法 3)，該策略保證每次都選擇綜合質量最高的web服務，其主要思路如下：

(1) 在前向搜索過程中，記錄每個 web服務的最短響應時間，優(yōu)先選擇這個時間短的web服務；

(2) 每個候選 web服務都記錄了與給定目標參數(shù)匹配的輸出參數(shù)以及它們之間的語義匹配度，優(yōu)先選擇這個匹配度高的web服務；

(3) web服務的入度數(shù)越少，意味著執(zhí)行該服務所需的web服務數(shù)可能越少，因此，優(yōu)先選擇入度數(shù)少的web服務；

(4) 所選 web服務的響應時間越長，有可能組合路徑越長，根據(jù)前面的語義質量模型 WSCSQM，從而可能使整個方案的語義質量降低；同時，路徑越長，也可能意味著組合方案的服務數(shù)越多．可以看出，這3個維度對組合方案的質量是相互影響的．因此，在實際選擇中，需要綜合考慮這 3個影響質量的因素，提供靈活、有效的web服務質量評估方法．

在GetWSwithOptimal函數(shù)中采用的啟發(fā)函數(shù)表達式為

式中：md為給定目標參數(shù)與所提供參數(shù)的匹配度；ind為候選web服務的入度；rt為候選web服務的最短響應時間；mind為問題域中所有 web服務的最大入度；mrt為給定目標參數(shù)的最大響應時間約束；cr為組合質量的平衡系數(shù)，其范圍為[0，1]；cl為組合質量和QoS平衡系數(shù)，其范圍也為[0，1]．若cr為0，則表示只選擇入度最小的服務；若cr為1，表示只選擇語義匹配度最高的服務；若 cr為(0，1)范圍內的值，則需要選擇組合質量綜合值最高的服務．cl為0表示選擇最短響應時間最小的服務；cl為1表示只考慮組合質量因素；(0，1)范圍內的cl值表示兩方面因素都考慮．

4 實驗結果與分析

WS-Challenge2010[13]提供了專門的 web服務組合測試集生成工具 TestsetGenerator和檢驗工具ChallengeChecker，使用 TestsetGenerator可以生成不同規(guī)模的虛擬測試集，每個測試集包括 web服務的描述文件、服務質量描述文件、本體描述文件和用戶請求描述文件．為了方便結果的比較，本文使用競賽第1名[9]的5個測試集，其基本特征描述見表1．

表1 測試集基本特征Tab.1 Basic features of test sets

本文 QoSWSCPlaner使用Java語言實現(xiàn)，本次實驗的硬件環(huán)境為ThinkPad E300筆記本(2.4,GHz× 2，4,GRAM，Win7)．在實驗中，QoS因素只考慮響應時間．下面分別對 QoSWSCPlaner前向搜索的高效性、后向搜索中質量調節(jié)的靈活性和有效性、以及整個規(guī)劃器的執(zhí)行效率和正確性進行相關的實驗．需要說明的是，為了減少實驗中的不穩(wěn)定因素，所有執(zhí)行時間相關的實驗數(shù)據(jù)是在多次執(zhí)行的基礎上取其中多次出現(xiàn)的一個值．

4.1 前向搜索的結果與分析

在 QoSWSCPlaner中采用逐步變窄的前向搜索策略，即在前向搜索的每次迭代中，在查找當前狀態(tài)滿足的web服務之前，先對問題域中的 web服務進行一遍過濾，得到與當前狀態(tài)相關的web服務集合，然后在該 web服務集上進行當前狀態(tài)滿足性的檢查，得到有效的web服務集合．

從圖7可以看出逐步變窄策略對web服務的過濾效果明顯，尤其在后3個大規(guī)模測試集中，第1次分別過濾出30%、51%、31%的相關web服務．這樣，在滿足性檢查時，僅檢查這些相關的web服務即可，從而大大縮短了前向搜索的時間．同時，在滿足性檢查時，通過充分利用過濾相關服務時記錄的已滿足參數(shù)信息，進一步減少了搜索時間．文獻[11]也提出了一種快速的組合算法，基于本文同樣的測試集給出了前向搜索的時間，本文提出的前向搜索時間明顯高于文獻[11]，如圖8所示．

圖7 逐步變窄前向策略的過濾效果Fig.7 Effects of gradually narrowing forward search

圖8 本文前向搜索時間與文獻[11]的比較Fig.8 Comparison of forward search time between this paper and Ref.[11]

4.2 后向搜索的結果與分析

QoSWSCPlanner的后向搜索保證得到的是滿足QoS約束的組合方案，同時它允許用戶通過質量平衡系數(shù)調節(jié)組合方案的組合質量．在 Testset5上，假定QoS約束為最短響應時間4,070,ms，驗證質量平衡系數(shù) cl和 cr(見式(5))對組合方案的語義質量和服務數(shù)的影響．實驗中對 cl的取值為 0、0.2、0.5、0.8和1.0，然后對每一個cl值對cr取值0、0.2、0.5、0.8和1.0．其對組合方案的調節(jié)效果如圖9所示(橫坐標第1行表示cr的不同取值)．

當 cl＝0時，根據(jù)式(5)，cr的調節(jié)作用失效，實驗得到一個組合方案，其語義質量為 0.114,3，服務數(shù)為32個．其他情況下，cr的調節(jié)具有明顯的作用．通過分析，得出3點結論．

(1) 候選 web服務的最短響應時間對組合質量的影響很大．

當cl＝0即只考慮最短響應時間時，得到組合方案的服務數(shù)為 32，是所有實驗中的最小服務數(shù)．當cl＝1.0(見圖9(d))即在選擇web服務時完全不考慮最短響應時間，得到的服務數(shù)都比 cl小于 1的情況大，同樣組合方案的語義質量也不高．在cl＝0.2時(見圖9(a))，cr系數(shù)調節(jié)作用比較明顯，語義質量和服務數(shù)均與平衡系數(shù)cr呈線性遞增關系．即cr越大在構建組合方案的過程中考慮的語義因素越多，則整個方案的語義質量越高；同時cr越大，在選取web服務時考慮的服務數(shù)因素越少，則整個方案的服務數(shù)越多．

(2) 后向搜索的啟發(fā)策略是局部的，因此找到的是近似最優(yōu)解．從圖 9(b)和圖 9(c)可以看出，隨著cr的增加，其考慮的服務數(shù)因素減少時，整個組合方案的服務數(shù)反而下降．

(3) 在選擇 web服務時，如果考慮語義質量和服務數(shù)因素(cl≠0)，則組合方案的組合質量變化明顯．這意味著用戶可以根據(jù)自己的偏好，在多個不同質量組合方案中做出自己的選擇，充分說明了QoSWSCPlanner中質量調節(jié)的有效性．

圖9 質量平衡系數(shù)對組合質量的影響Fig.9 Effects of quality equilibrium coefficient on composition quality

4.3 執(zhí)行效率及正確性的結果與分析

QSynth系統(tǒng)[10]是基于 WS-Challenge2009第 1名的算法[9]實現(xiàn)的組合系統(tǒng)，它將查找最短響應時間組合方案與查找最大吞吐量組合方案并行執(zhí)行，在300,ms(不包含預處理時間)的時間內找到全部 5個測試集的最優(yōu)組合方案．由于采用并行算法，可以認為其單獨查找最短響應時間組合方案的時間與查找兩個組合方案的時間相當．本文提出的QoSWSCPlaner在組合時間上體現(xiàn)出了與QSynth相當?shù)膱?zhí)行速度，而且找到了每個測試集的最短響應時間，如表2所示．這里，在運行QoSWSCPlaner時，設置每個測試集的 QoS約束為其最短響應時間(見表1)，并取cl＝0．

表2 QSynth與本文的QoSWSCPlaner比較Tab.2 Comparison between QSynth and QoSWSCPlaner

QoSWSCPlaner得到的所有組合方案均使用ChallengeChecker工具進行了正確性測試，并得到了組合方案的路徑長度和服務數(shù)信息(見表 2)．從實驗數(shù)據(jù)中可以看出：QoSWSCPlanner能夠在300,ms內找到最優(yōu)解，且最優(yōu)解的路徑長度和服務數(shù)與QSynth相當；在 Testset4中找到的最優(yōu)解的服務數(shù)為 40個，遠少于 QSynth的 93個，進一步說明了QoSWSCPlanner后向搜索中減少web服務的措施是有效的．

5 相關工作

目前，考慮QoS屬性的web服務組合方法主要有兩大類：一類是排序法，即首先根據(jù)web服務的功能屬性查找若干組合方案，然后按照QoS進行排序，并將QoS最優(yōu)的方案提供給用戶[4-5]；另一類是QoS感知的方法，即在組合過程中，既考慮服務的功能屬性又考慮其QoS屬性，直接得到一個組合方案．由于排序法在組合時并不考慮 QoS因素，所以其第一階段的組合結果將有很多，而基于多個組合結果的排序也是一個耗時的過程．所以，從效率上來講，排序法遠低于 QoS感知的方法．因此，本文主要采用 QoS感知的方法進行組合，下面主要介紹 QoS感知組合的相關工作．

一些研究者[6-7]采用任一時間算法來進行QoS感知的組合，這種算法可以很快得到一個組合方案，并且時間越長，結果越好．Kil[6]基于近似搜素算法beam stack和啟發(fā)策略，設計了任一時間QoS感知的WSC算法，并驗證了其可以更快地找到質量較高的組合方案．Yan等[7]根據(jù) QoS值擴展規(guī)劃圖，將其值標記成邊的權重，然后在該圖基礎上運用迪杰斯特拉(Dijkstra)算法查找最優(yōu)方案，由于迪杰斯克拉算法會遍歷到圖中的每個頂點，因此隨著時間的推移，它總能找到無冗余的QoS最優(yōu)方案[9]．文中將I/O參數(shù)的語義匹配關系進行了扁平化處理，不用每次在匹配時都運行 OWL推理機，這樣節(jié)省了組合時間．任一時間算法雖然效率很高，但得到的組合方案并不一定是QoS最優(yōu)的，而QoSWSCPlanner可以快速得到一個QoS最優(yōu)的方案，實驗表明它在大規(guī)模的web服務集中效率也很高．

也有一些研究通過QoS感知的方法得到了QoS最優(yōu)的方案[8-10]．Xu等[8]采用前向廣度優(yōu)先搜索和后向深度優(yōu)先搜索相結合的方法找到了 QoS最優(yōu)的組合方案．在前向搜索中，記錄了每個web服務和數(shù)據(jù)類型的最優(yōu) QoS值，并通過前向搜索的逐步迭代過程更新這些最優(yōu)值；然后在后向搜索中按照目標輸出參數(shù)類型，遞歸查找每個提供該類型的 QoS最優(yōu)的web服務，最終形成一個QoS最優(yōu)的組合方案．Jiang等[9-10]采用 3個階段完成組合，首先采用前向過濾找到有效的 web服務，然后采用動態(tài)編程方法找到每個概念的最優(yōu) QoS值，并在查找的過程中記錄提供最優(yōu)值的 web服務，形成組合子圖；最后，利用多線程技術在組合子圖上并行查找滿足最大吞吐量和最短響應時間的組合方案．在 WS-Challenge2009中，姜偉團隊的方法在最快的時間內找了所有測試集的最優(yōu)QoS方案，獲得了第1名；而許斌團隊則在第5個大規(guī)模測試集上的執(zhí)行時間多于前者，取得了第 2名．這些方法對每個QoS值獲得了一個最優(yōu)方案，鄧水光等[11]提出了 QoS最優(yōu)的全解構造方法，也是采用3個階段完成，首先進行前向搜索獲得去掉無用服務的分層規(guī)劃圖，然后基于該圖進行 QoS最優(yōu)值的計算，最后以QoS最優(yōu)值為約束條件，以用戶請求的輸出參數(shù)為起點后向搜索所有的 QoS最優(yōu)解．該方法能夠獲得多個 QoS最優(yōu)的組合方案，但其獲得單個最優(yōu)解的效率不如文獻[9]中的方法．

Bartalos等[17]提出了高效的 QoS感知的組合方法，它在組合前的預處理階段設計了高效的數(shù)據(jù)結構和算法，為后面的快速組合提供了基礎．通過web服務間的兼容性檢驗將 web服務連接成一個有向無環(huán)圖，圖中記錄了 web服務間的前驅-后繼關系．然后將 web服務分成兩種：一種是其輸入?yún)?shù)可由其他服務提供；另一種是其有一個或多個輸入?yún)?shù)不能由其他服務提供，后者稱為用戶相關服務．對于用戶相關服務來說，如果用戶請求的輸入?yún)?shù)不能滿足，則該服務為無效服務．基于前面的預處理，組合算法取得了很好的速度，但其組合算法并不能求得 QoS最優(yōu)的方案．

本文提出的 QoSWSCPlanner能夠快速地得到QoS最優(yōu)的方案，它借鑒了文獻[8]中的組合思路，但在預處理階段使用輸入?yún)?shù)聚類相關 web服務，并利用逐步變窄的思想修改了前向搜索算法，大大提高了前向搜索速度，同時也使其整體組合速度與文獻[9]相當．此外，QoSWSCPlanner并不局限于僅得到一個 QoS最優(yōu)的方案[8-9]，也不局限于求所有最優(yōu)方案[11]，而是建立了語義質量模型，在后向搜索中通過靈活的質量啟發(fā)函數(shù)來優(yōu)化 QoS約束下的組合方案質量，為通過放寬 QoS約束條件的方式來獲得優(yōu)良的組合方案提供了可行的思路．

在 web服務組合中利用質量啟發(fā)來改進組合方案質量的研究也有一些．Arpinar等[19]在組合過程的web服務選擇中，對候選web服務的QoS值和語義相似度進行綜合權衡，優(yōu)先選擇綜合質量高的 web服務．Freddy用公共描述度與匹配度計算參數(shù)間的相似度，并提出語義鏈的質量的計算方法，同時將其與 QoS整合在一起建立組合方案質量模型[14]. Hatzi等[20]給出了通過參數(shù)語義距離計算組合方案語義距離的方法．本文將組合方案質量分成 QoS質量和組合質量兩部分，并在 QoS約束下評估組合方案的組合質量．因此，要求組合方案首先滿足 QoS約束，然后再計算其組合質量，包括語義質量和服務數(shù)．在語義質量計算時不僅考慮語義相似度，而且還考慮路徑長度對語義質量的影響．本文工作與相關文獻的比較如表3所示．

表3 本文工作與相關文獻的比較Tab.3 Comparison among this paper and others

6 結 語

在解決QoS約束下的web服務組合問題時，可能會得到多個滿足 QoS約束的組合方案．本文提出了包含語義質量和服務數(shù)的組合質量概念，用來對多個組合方案進行評估和比較．其中，基于帶標記的有向圖，設計了合理的語義質量模型，為多個組合方案的語義評估提供了依據(jù)．同時，改進了圖規(guī)劃的兩步搜索算法，并基于該算法設計了一個組合規(guī)劃器QoSWSCPlanner，它能夠快速找到滿足 QoS約束且具有高組合質量的方案．它在組合開始前使用以輸入?yún)?shù)為鍵的哈希結構組織 web服務，在此基礎上設計了逐步變窄的高效前向搜索算法，實驗表明這樣的改進大大縮短了前向搜索的時間．它也修改了后向搜索算法，在其中引入了組合質量啟發(fā)函數(shù)．該函數(shù)通過質量平衡系數(shù)能夠對候選 web服務的語義匹配度、入度數(shù)以及執(zhí)行路徑上的最短響應時間進行控制，從而達到對最終方案的組合質量特性進行干預的目的．最后的實驗驗證了這種調節(jié)是有效性的．

通過質量平衡系數(shù)的不同設置，QoSWSCPlanner能夠得到多個 QoS相同但組合質量不同的組合方案，為用戶按需選擇組合方案提供了基礎．此外，實驗展示了QoSWSCPlanner在大規(guī)模測試集上也能夠在毫秒級上快速給出組合方案，這為面向互聯(lián)網(wǎng)構建大規(guī)模的面向服務系統(tǒng)提供了一個有效的方法．

當然，本文的方法還有一些需要優(yōu)化的地方. 如后向啟發(fā)函數(shù)還可以進一步優(yōu)化，可以增加影響組合質量的其他因素，使得規(guī)劃器對組合質量的調節(jié)更加靈敏和有效，從而為用戶提供更有意義的參考．再有，本文的規(guī)劃器在組合時默認環(huán)境是靜態(tài)的，并沒有考慮服務環(huán)境的動態(tài)性，如服務的增加、刪除和QoS質量變化情況等，動態(tài)環(huán)境下的 QoS約束組合將更具有實際意義．最后，組合方案的正確性還需驗證技術的支持[21]．

［1］ High Rob Jr，Kinder Stephen，Graham Steve. IBM's SOA Foundation-An Architectural Introduction and Overview[M]. IBM，2005.

［2］ Rao Jinghai，Su Xiaomeng. A survey of automated web service composition methods[C]// Semantic Web Services and Web Process Composition 2004. Washington：Springer-Verlag Berlin Heidelberg，2005：43-54.

［3］ Antoniou Grigoris，van Harmelen Frank. A Semantic Web Primer [M]. 2nd ed. Massachusetts，London：The MIT Press，2008.

［4］ Bansal S K，Bansal A，Gupta G. Semantics-based web service composition engine[G]// Blake M B，ed. Semantic Web Services. Washington：Springer-Verlag Berlin Heidelberg，2012：329-343.

［5］ Shiaa M M，F(xiàn)ladmark J O，Thiell B. An incremental graph-based approach to automatic service composition [C]// IEEE International Conference on Services Computing. Honolulu，USA，2008：397-404.

［6］ Kil Hyunyoung. Efficient Web Service Composition：From Signature-Level to Behavioral Description-Level[D]. Pennsylvania，USA：Department of Computer Science and Engineering，The Pennsylvania State University，2011.

［7］ Yan Yuhong，Chen Min，Yang Yubin. Anytime QoS optimization over the PlanGraph for web service composition[C]//Proceedings of the 27th Annual ACM Symposium on Applied Computing. New York，USA，2012：1968-1975.

［8］ Xu Bin，Luo Sen，Yan Yixin，et al. Towards efficiency of QoS-driven semantic web service composition for large-scale service-oriented systems[J]. Service Oriented Computing and Applications，2012，6(1)：1-13.

［9］ Huang Zhenqiu，Jiang Wei，Hu Songlin，et al. Effective pruning algorithm for QoS-aware service composition[C]// IEEE Conference on Commerce and Enterprise Computing. Vienna，Austria，2009：519-522.

［10］ Jiang Wei，Zhang Charles，Huang Zhenqiu，et al. QSynth：A tool for QoS-aware automatic service composition[C]// Proceedings of the IEEE International Conference on Web Services(ICWS). Miami，USA，2010：42-49.

［11］ 鄧水光，黃龍濤，吳 斌，等. 一種QoS最優(yōu)的語義Web服務自動組合方案[J]. 計算機學報，2013，36(5)：1015-1029. Deng Shuiguang，Huang Longtao，Wu Bin，et al. QoS optimal automatic composition of semantic Web services [J]. Chinese Journal of Computers，2013，36(5)：1015-1029(in Chinese).

［12］ OASIS. Web Services Business Process Execution Language Version 2.0[EB/OL]. https：//www.oasis-open. org/committees/download.php/21575/wsbpel-specification_ public_review_draft_2_diff.pdf，2006-11-20/2013-10-27.

［13］ CEC’2010. Web Services Challenge 2010[EB/OL]. http：//ws-challenge. georgetown. edu/wsc10/，2013-04-06.

［14］ Lécué F. Optimizing QoS-aware semantic web service composition[C]// Proceedings of the Eighth International Semantic Web Conference(ISWC). Washington：Springer-Verlag Berlin Heidelberg，2009：375-391.

［15］ Paolucci M，Kawamura T，Payne T R，et al. Semantic matching of web services capabilities[C]// ISWC 2002. Washington：Springer Berlin Heidelberg，2002：333-347.

［16］ Oh S-C，Lee D，Kumara S R. Effective web service composition in diverse and large-scale service networks [J]. IEEE Transactions on Services Computing，2008，1(1)：15-32.

［17］ Bartalos P，Bieliková M. Effective QoS aware service composition based on forward chaining with service space restriction[G]// Blake M B，ed. Semantic Web Services. Washington：Springer-Verlag Berlin Heidelberg，2012：313-328.

［18］ Papadimtriou C H，Steiglitz K. Combinatorial Optimization：Algorithms and Complexity [M]. London：Prentice-Hall，1982.

［19］ Arpinar I B， Zhang Ruoyan， Aleman-Meza Boanerges，et al. Ontology-driven Web services composition platform[J]. Information Systems and e-Business Management，2005，3(2)：175-199.

［20］ Hatzi O，Vrakas D，Bassiliades N，et al. The PORSCE II framework：Using AI planning for automated semantic Web service composition[J]. The Knowledge Engineering Review，2013，28(2)：137-156.

［21］ 胡 靜，饒國政，馮志勇. 基于多元 Pi-演算的 Web服務組合描述與驗證[J]. 天津大學學報：自然科學與工程技術版，2013，46(6)：520-525. Hu Jing，Rao Guozheng，F(xiàn)eng Zhiyong. Polyadic Picalculus based description and verification for Web service[J]. Journal of Tianjin University：Science and Technology，2013，46(6)：520-525(in Chinese).

（責任編輯：趙艷靜）

Evaluating and Optimizing Semantic Web Service Composition Under QoS Constraints

Wang Xianghui1,2，F(xiàn)eng Zhiyong1
(1. School of Computer Science and Technology，Tianjin University，Tianjin 300072，China；2. School of Computer Science and Technology，Shandong Jianzhu University，Jinan 250101，China)

Regarding many solutions in semantic web service composition under a given QoS constraint，a composition quality concept was proposed，and an improved composition algorithm was designed to quickly generate a solution with high composition quality. Concerning different criteria of composition quality，quality equilibrium coefficient was introduced. And it was used to construct an adjustable heuristic function，which was applied to backward search of traditional two-step search algorithms. Thus，users can obtain a solution with desirable composition quality by adjusting the equilibrium coefficient. To improve efficiency，the composition algorithm adopted the gradual narrowing forward search strategy，which was based on an efficient data storage structure. On the basis of this improved algorithm，a composition planner was achieved. A series of experiments indicate that the planner can generate solutions satisfying given QoS constraint values. Meanwhile，by setting different values to the quality equilibrium coefficient，the planner can produce a desirable composition quality solution.

web service composition；composition quality；two-step search；QoS；quality equilibrium coefficient

TP301

A

0493-2137(2015)02-0126-13

10.11784/tdxbz201310075

2013-10-31；

2013-11-27.

國家自然科學基金資助項目(61173155，61070202).

王向輝（1979— ），女，博士研究生，講師.

王向輝，wxh_225@163.com.

時間：2014-01-06. 網(wǎng)絡出版地址：http：//www.cnki.net/kcms/detail/12.1127.N.20140106.1530.002.html.