Web服務組合中的去冗余方法研究

◆崔曉柳 范國棟 李靜

Web服務組合中的去冗余方法研究

◆崔曉柳 范國棟 李靜通訊作者

（山東理工大學 山東 255049）

Web服務組合結合了網絡上不同功能的服務，以完成更復雜的功能，滿足用戶的需求。然而，傳統方法得到的解決方案往往包含不必要的冗余服務，效果重復的服務會導致額外的響應時間和成本。為了去除冗余服務，本文提出了一種Web服務組合的去冗余方法（CRR，composition redundancy removal）。該方法對規劃圖算法進行改進，在規劃圖算法中加入去冗余過程。首先對服務存儲庫進行搜索，找出滿足用戶需求的候選服務；然后，以用戶請求的目標輸出為起點進行逆向搜索，同時刪除冗余服務，得到無冗余的Web服務組合結果。使用數據集進行實驗分析與驗證，結果表明，與改進前的規劃圖方法比較，CRR過程去除了大量冗余服務，可以獲得服務質量QoS（Quality of Service）更優的解。

Web服務組合；QoS；規劃圖；去冗余

近年來，Web 服務作為可以滿足用戶需求的互聯網資源，使用得越來越廣泛。然而，單一的Web服務可實現的功能有限，有時網絡上的單個服務不能滿足用戶提出的復雜需求。Web服務組合根據需要選擇多個功能不同的Web服務并進行組合，可以實現用戶更加復雜的需求。例如，網絡上已存在將中文翻譯為英語的服務1與將英語翻譯為德語的服務2，如果我們想將中文翻譯成德語，但沒有單個服務可實現此功能，可以將1的輸出結果作為2的輸入，完成從中文翻譯為德語的過程。

隨著Web服務的日益成熟，網絡上提供的功能相同的服務日益增多。如何從海量服務中搜索合適的服務并得到滿足特定輸入與輸出的組合是當前急需解決的問題。服務組合方案應在滿足功能性需求，即保證目標輸出的前提下，選擇Web服務質量QoS更優的服務。

Web服務組合問題作為計算機應用的一個研究熱點，吸引了眾多學者對其展開研究，并提出了一些算法。例如skyline算法[1，2]，規劃圖算法[3，4]。skyline算法可以使用更少的存儲空間和更快的速度解決大的組合問題，規劃圖算法是Web服務自動組合的方法。

然而，在使用Web Service Challenge（WSC）的文獻[6，7，8]中，幾乎所有的算法都不能避免組合中出現冗余服務。為了解決這個問題并作為研究[5，9]的繼續，本文提出了一種結合去冗余過程的Web服務組合方法CRR。該方法分為兩個階段：向前擴展階段、向后搜索階段。向前擴展階段對服務存儲庫進行搜索，找出滿足用戶需求的候選服務；向后搜索階段以用戶請求的目標輸出為起點進行逆向搜索，同時刪除冗余服務，得到無冗余的Web服務組合方法。

1 背景知識

1.1 QoS標準

Web服務組合可以實現單一服務無法滿足的復雜功能。在能夠實現功能性需求的前提下，優先考慮非功能屬性QoS，可以選擇QoS更優的Web服務組合。

服務質量QoS是一個綜合指標，用來體現服務能力，如響應時間、吞吐量、花費、可信度等。QoS屬性可以分為兩類：積極的屬性和消極的屬性。對于積極的屬性，QoS值越高，代表服務的質量越好（如吞吐量和可信度）。而消極的屬性，QoS值越低，代表服務質量越好（如響應時間與花費）。

Web服務可以按照順序的方式連接，也可以按照流的方式連接。順序連接的Web服務形式如（1;2;…;），按流連接的Web服務形式表示為（1||2||…||）。常用的Web服務質量的屬性與其計算方式如下：

響應時間（）：收到查詢消息與回復響應消息的時間間隔（單位：毫秒）。

吞吐量（）：單位時間內經由通信通道成功傳遞信息的數量。（單位：請求/分鐘）

花費（）：用戶為使用Web服務資源所付出的代價（單位：元）。

關于QoS更多分類可以參考文獻[10]。

1.2 規劃圖方法

規劃圖是一種有向分層圖，表示為文字和操作符交替的序列：（0;1;1;2;2;3;3; …;A;P; …;A;P）。在規劃圖中，層包含服務的參數，層包含可被喚醒的服務。初始參數層0表示規劃問題的初始狀態，A層的每個節點都有P層的輸入弧與P層的輸出弧，即P層的參數可以滿足A層的輸入，A層的輸出被加到P層。層中的多個操作意味著它們可能被并行執行。

規劃圖方法包含兩個階段：向前擴展和向后搜索。

向前擴展階段從初始狀態構建規劃圖。首先，根據用戶輸入，構建初始參數層0層；然后執行循環：遍歷Web服務存儲庫，對于存儲庫中的每一個服務，如果規劃圖中沒有，且參數層P含當前服務所有輸入參數，則服務可被喚醒。將加入A層，將的輸出參數加入P層。重復循環的過程，當服務存儲庫遍歷結束，且規劃圖的服務層A中不再添加任何服務，整個過程結束。如果規劃圖的參數層P存在要找的目標，就可以找到解決方案。

向后搜索階段，是從最后一層到第一層的反向搜索循環，根據要找的目標，向前搜索路徑，檢索解決方案。執行循環：當P層存在用戶要找的目標，在A層中尋找一組輸出參數滿足目標的服務，這一組服務的輸入參數又是前一層P的目標。直到達到初始參數層，循環結束，得到一組從初始狀態到目標狀態的服務組合路徑（w，w，…，w）。

2 去冗余過程

大部分Web服務有多個輸入參數和輸出參數。規劃圖方法得到的服務組合結果中，并不是每一個服務都必須用到。

冗余服務是在規劃圖的前向階段被加進候選組合的大量后續用不到或產生與已有服務相同效果的Web服務。

冗余的Web服務會增加不必要的副作用。如果在組合中包含了冗余的Web服務，將導致組合的QoS變得更差，如響應時間變長、吞吐量減少，并且系統的總體執行時間和花費將會增大。

從用戶的角度考慮冗余的Web服務組合，如果有兩個付款的服務同時包含在Web服務組合中，就有可能為同一個訂單付款兩次。因此，我們需要找到無冗余的解決方案來避免這些問題。

圖1為一個Web服務組合的實例。在這個組合中，3服務只有一個輸出，而3的前一層，服務1已經輸出參數。移除服務3后，服務組合依舊能夠得到結果。所以，3是冗余服務。去除冗余服務后的結果如圖2所示。

圖1 服務組合

圖2 冗余的服務組合

重復的輸出造成了冗余。而在傳統規劃圖的過程中，無法判別冗余服務的產生。將冗余服務移除，往往可以保持組合移除后的功能目標與QoS值不變，甚至QoS數值更優，得到性能更好的組合結果。

本文提出的去冗余方法為：在向后搜索的同時刪除冗余服務。向后搜索過程中的每一層搜索結束后，向前遍歷一遍，將遍歷過程中的所有非冗余服務的輸出參數放進集合。若集合包含前面層某服務的全部輸出，則這個服務是冗余服務。該方法可將規劃圖前面層對組合結果無用的Web服務刪除。具體過程見3.2的算法。

3 組合過程、算法與實例

3.1 組合過程

本文所提方法的流程如圖3所示。

圖3 總體流程圖

用戶發送請求到服務存儲庫，通過改進的規劃圖方法，得到服務組合結果。

實驗所用的服務存儲庫由WSC數據集解析得到。該數據集包含WSDL文件、OWL文件、WSLA文件。WSDL文件用于描述 Web服務的名稱、輸入、輸出、如何進行訪問等，OWL文件用來描述服務本體論的結構關系，WSLA文件描述服務的QoS屬性值。

改進規劃圖方法分為兩個階段：第一階段在服務存儲庫中尋找滿足用戶需求的候選Web服務組合，向前擴展構成規劃圖；第二階段以用戶請求為起點，向后搜索的同時刪除冗余服務。向后搜索階段結束后，得到滿足目標輸出的無冗余服務組合結果。

3.2 算法

整個過程的算法分為向前擴展階段和向后搜索階段。

向前擴展階段以服務存儲集、初始輸入、目標參數作為輸入、輸出規劃圖向前擴展的結果。該算法以初始輸入為起點參數集，對服務存儲庫進行層次劃分，過濾輸入參數無法喚醒的服務。如果存儲庫中服務的所有輸入參數被當前參數集包含，表示該服務能被喚醒，將該服務加入規劃圖，并添加服務的輸出到參數集。服務存儲庫遍歷結束，規劃圖當前層添加完畢。再次對服務存儲庫進行層次劃分，將當前參數集能夠喚醒的服務加入規劃圖下一層。直到不再加進新服務，獲得前向規劃圖。如果前向規劃圖中有目標請求，繼續執行向后搜索階段。

向后搜索階段以用戶請求的輸出參數為起點進行逆向搜索，同時刪除冗余服務，得到無冗余服務的Web服務組合方法。該算法以前向規劃圖、初始輸入、目標參數作為輸入，輸出為當前層得到的路徑結果。以用戶請求，即最后一層的輸出目標為起點反向遍歷，如果規劃圖下一層的服務輸出與目標參數相同，將這個服務加入集合，使用RemoveRedundant（）方法刪除路徑結果中的冗余服務，并將加入路徑結果。此時起點目標參數更新為未能滿足的目標和新加入服務的輸入。規劃圖的每一層均循環上述過程，當目標中所有目標都可由用戶請求滿足時，循環結束，最后一層的為無冗余的Web服務組合路徑結果。

算法 RemoveRedundant（）

輸入：cover，initial，solution

輸出：redundant

2. for each srv in cover do

4. end for

5. for each level in solution do

6. for each srv in level do

7. if outset contains all srvout

9. delete redundant

10. else

12. end for

13. end for

在向后搜索階段，規劃圖路徑每新加入一層，都執行一遍去冗余算法。該算法以向后階段準備加入下一層的服務集合、初始輸入、向后搜索階段中已得到的路徑作為輸入，最終效果為刪除冗余服務。結果集合中存儲初始輸入參數中每個服務的輸出參數和每層已判定為非冗余服務的輸出參數。

將初始輸入與集合的輸出參數加入集合，將中每一個的服務的輸出與集比較，若中存在此服務全部的輸出，則該服務為冗余服務，將其刪除；若沒有存在此服務全部的輸出，則該服務為非冗余服務，將它的輸出也加入集合。

3.3 實例

在本節中，我們通過一個具體的例子來解釋所提出的算法。在本例中，服務的信息表如表1所示，其中包括輸入、輸出的概念、響應時間、吞吐量。假設用戶給定輸入，與目標輸出，求一組Web服務組合。

表1 Web服務信息表

3.3.1 Graphplan方法向前擴展

在向前擴展階段，規劃圖方法以層的參數作為輸入，從服務集合中選擇滿足功能性需求的服務，加入層，并將層的輸出加入層，直到不再加入新的服務。如圖4所示。

圖4 規劃圖

3.3.2向后搜索并去冗余階段

此階段以用戶請求為起點向后擴展，過程如下。

最后一層3中的目標結果可由服務4輸出，于是規劃圖路徑為{4}，結果集合記錄為初始輸入與4的輸出{，}。

4需要的輸入為和，在2層，由2輸出，由3輸出，規劃圖路徑下一層將加入{2，3}，結果集合記錄為初始輸入與2、3的輸出{，，}，此時路徑中4的輸出不存在于結果集合，因此當前沒有冗余服務，結果集合為{，，}。此時規劃圖路徑為{（2||3）;4}。

2與3需要的輸入為，在1層，由1輸出，規劃圖將加入{1}，此時結果集合為{，，}，遍歷規劃圖路徑中的服務：

2的輸出不包含于結果集合，因此2不是冗余服務，將其輸出加入結果集合，結果集合更新為{，，，}；3的輸出包含于結果集合，因此3是冗余服務，將其刪除；4的輸出不存在于結果集合，不是冗余服務，將其輸出加入結果集合，結果集合為{，，}。此時1的輸入可由初始輸入滿足，向后搜索過程結束。

最終得到的服務組合路徑為（1;2;4）。響應時間R和吞吐量T分別為：

R=R（1）+R（2）+R（4）=700

T=min（T（1），T（2），T（4））=1000

如果沒有進行去冗余階段，服務組合為{1;（2||3）;4}，得到的QoS結果為：

R=R（1）+R（3）+R（4）=800

T=min（T（1），min（T（2），T（3）），T（4））=1000

顯然無冗余的組合方法QoS更優。

4 實驗

4.1 數據源

我們使用了五個數據集[11]進行實驗，每個數據集都有OWL文件、WSDL文件、WLSA文件，分別描述服務、本體、QoS。WLSA文件提供了每個服務響應時間和吞吐量的值。數據集均有500-15000個服務，5000-100000個參數概念。

4.2 實驗環境

實驗環境為：（1）CPU：Intel（R） Core（TM） i3-4170 CPU @ 3.70GHz 3.70GHz；（2）RAM：8.00GB；（3）操作系統：Windows 7旗艦版 Service Pack1。算法用Java實現。

4.3 實驗結果

為了說明算法的有效性，將CRR方法的結果與改進前的規劃圖方法進行比較。如表2所示。

從實驗結果可以看出，去冗余方法有顯著效果，去除了大量冗余服務。與未改進的規劃圖方法相比，CRR組合結果的服務數量明顯減少，且刪除冗余服務后，組合的響應時間更短，從而有更好的QoS。

綜上，無冗余的Web服務組合方法不僅可以完成的功能屬性，實現目標輸出，還可以優化組合的非功能屬性。實驗表明，此方法可以有效地刪除冗余服務，特別是對于海量數據而言，可以大大減少組合結果的服務數量、優化QoS結果。

表2 實驗結果

5 結語

本文提出了一種Web服務組合去冗余方法CRR，該方法可有效刪除組合結果中的冗余服務。對服務存儲庫進行搜索，找出滿足用戶需求的候選服務；之后，以用戶請求的輸出參數為起點進行逆向搜索，同時刪除冗余服務，得到無冗余的Web服務組合方法。使用數據集進行實驗分析與驗證，結果表明，與規劃圖方法比較，去冗余方法可以有效刪除大量冗余服務，得QoS更好的組合結果。

去冗余方法可以結合其他服務組合方法，優化其他方法獲得的解。用其他方法，如skyline算法篩選Web服務存儲庫后，在最后一步進行去冗余操作，剔除對組合結果無用的服務，得到更好的解決方案。

[1]J.Li，Y.Yan，D.Lemire.Scaling up web service composition with the skyline operator[C]//IEEE InternationalConference on Web Services，USA，ICWS，2016：147-154.

[2]楊莉，張文生，許國艷.基于Skyline服務的Top-k選擇方法[J].計算機應用與軟件，2016，33（11）：253-257.

[3]戴雪梅，姜浩.基于帶權圖規劃算法的語義Web服務組合[J].計算機技術與發展，2010，20（03）：67-70+75.

[4]鄒子靖.基于圖規劃的啟發式Web服務組合算法研究[D].哈爾濱工程大學，2016.

[5]范國棟，祝銘，等.基于FAHP與規劃圖融合的Web服務組合方法[J].計算機科學，2020，47（01）：270-275.

[6]G.Fan，M.Zhu，X.Cui.（2019）.Optimizing Web Service Composition with Graphplan and Fuzzy Control.Journal of Ubiquitous Systems and Pervasive Networks. 11. 15-21.10.5383/JUSPN.11.02.003.

[7]T.Yu，K.J.Lin. Service selection algorithms for Web services with end-to-end QoS constraints. Seventh IEEE International Conference on E-Commerce Technology （CEC'05），San Diego，California，2004 pp.129-136.

[8]L.Zeng，B.Benatallah，A.H.H.Ngu，et al. QoS-Aware Middleware for Web Services Composition[J]. IEEE Transactions on Software Engineering，2004，30（5）：311-327.

[9]M.Zhu，X.Cui，G.Fan.（2019）.Modeling and Verification of Response Time of QoS-aware Web Service Composition by Timed CSP.Journal of Ubiquitous Systems and Pervasive Networks.11.01-09.10.5383/JUSPN.11.01.001.

[10]S.Ran.A Model for Web Service Discovery with QoS[J].AcmSigecom Exchanges，2003.

[11]WS-Challenge.Testsetgenerator2009[OL].https://code.google.com/p/wsc-pku-tcs/downloads/list.