基于WSDG的Web服務組合可靠性預測

謝春麗 李必信 蘇志勇

(1東南大學計算機科學與工程學院，南京 211189)(2江蘇師范大學計算機科學與技術學院，徐州 221116)

基于WSDG的Web服務組合可靠性預測

謝春麗1，2李必信1蘇志勇1

(1東南大學計算機科學與工程學院，南京 211189)(2江蘇師范大學計算機科學與技術學院，徐州 221116)

為了更好地對基于SOA的Web服務組合進行可靠性預測，提出了基于服務依賴圖的可靠性模型.首先介紹了Web服務組合的描述語言WS－BPEL，以及用來描述服務業(yè)務流程的原子活動和結構化活動;其次在傳統(tǒng)的控制流圖的基礎上提出了Web服務依賴圖的概念，Web服務依賴圖用來描述Web服務組合的執(zhí)行行為和結構信息，包括服務名、服務類型和服務的可靠性，以及服務之間的轉移概率、轉移可靠性等信息;然后分析BPEL的原子活動和結構化活動的控制依賴關系，并在此基礎上構造相應的Web服務依賴圖.最后基于服務依賴圖的遍歷，應用可靠性預測算法計算Web服務組合的可靠性.實例分析結果表明，基于依賴圖的可靠性預測方法具有簡便性和易處理性.

Web服務;可靠性;Web服務依賴圖;BPEL

Web服務是自包含的、模塊化的應用程序，它可以在網(wǎng)絡中被描述、發(fā)布、查找以及調(diào)用，具有良好的封裝性、耦合松散及高度可集成等一些特征.在商業(yè)應用中，為了滿足用戶的功能需求需要將多個Web服務組合起來，同時服務組合還需要滿足用戶對可靠性、安全性和性能等服務質(zhì)量(QoS)的要求.由于這些Web服務由不同的服務提供者提供，具有物理上分布分散、運行于不同的平臺等一些特征，并且滿足某個功能需求的可供選擇的服務越來越多，使得Web服務組合的服務質(zhì)量控制更加復雜.同時Web服務組合的復雜性及執(zhí)行失效的高昂代價也使得Web服務組合的可靠性建模和預測變得更加重要和復雜.

軟件可靠性研究的基本問題是如何將系統(tǒng)結構更好地表現(xiàn)出來，其中使用最多的是控制流圖(CFG)［1－3］.用 CFG 表示軟件系統(tǒng)的結構，通常假設系統(tǒng)各組件之間的轉移關系滿足Markov性，結合組件的失效行為(可以用可靠性或者失效率來表示)，構建基于狀態(tài)的模型，軟件系統(tǒng)的可靠性描述為從初始狀態(tài)轉移到最終成功狀態(tài)的概率.但是對于松耦合的Web服務來說，消息交換是各服務之間進行交互的主要機制［4］，CFG只能表示服務之間簡單的控制流關系(順序、選擇、循環(huán)等)，但實際上對Web服務來說，由于服務之間的松耦合性，用傳統(tǒng)的構建控制流的方法很難將服務之間的關系完整地表達出來，尤其是消息傳遞時，例如，雖然活動A和B之間沒有顯式控制關系，但是活動A發(fā)送消息到活動B，其中隱含了活動A和B之間的控制關系［5］.本文將對已有的CFG進行擴展，構成服務依賴圖(WSDG)，用于描述服務之間的控制流、消息流，并增加服務的可靠性、服務的轉移概率、服務的轉移可靠性等一些有關可靠性的屬性信息.

目前關于構件和Web服務的可靠性預測的研究有許多成果［6－11］. 文獻［7］介紹了基于場景的構件系統(tǒng)可靠性分析方法.使用構件依賴圖(CDG)來表示基于構件的軟件的執(zhí)行場景，屬于基于路徑的方法.本文的Web服務依賴圖的思想來源于構件依賴圖，但是本文從BPEL文檔出發(fā)，建立服務組合系統(tǒng)的依賴圖，基于BPEL的可靠性模型比基于場景的更具有確定性和可應用性.文獻［1］將基于構件系統(tǒng)的可靠性預測方法分為2類:基于狀態(tài)的方法和基于路徑的方法.文獻［10－11］應用Markov模型對軟件系統(tǒng)的可靠性進行建模，主要是對模塊或構件之間的結構和它們之間的轉移信息進行建模，屬于基于狀態(tài)的方法.但是轉移矩陣通常都是稀疏矩陣，應用效率不高.本文則將轉移可靠性、轉移概率和服務可靠性相結合，將服務之間的結構關系轉換為圖的形式，借助于圖的遍歷過程計算組合服務的可靠性，提高了計算效率.

1 WS－BPEL

Web服務作為SOA的應用實例，其體系結構是基于3種角色(服務提供者、服務注冊中心和服務請求者)之間的交互.基于現(xiàn)有的SOA，服務提供者在服務注冊中心發(fā)布各自的Web服務，服務請求者通過UDDI注冊中心查詢所需服務時，注冊中心返回該服務的描述文件(包括WSDL文檔、服務質(zhì)量信息等)，服務請求者可以從描述文件中獲取服務質(zhì)量或綁定信息，根據(jù)服務質(zhì)量標準選定服務并綁定到所需服務的接口上.服務請求者通常請求調(diào)用多個Web服務，并使用WS－BPEL(簡稱BPEL)來描述多個Web服務的調(diào)用和交互.Web服務使用WSDL將其描述為服務端口的集合，然后BPEL以業(yè)務流程活動的形式集成多個Web服務，構成復雜的Web服務組合.BPEL描述的業(yè)務流程的每一步稱為一個活動，主要分為原子活動和結構化活動.下面將簡要介紹這些活動.

1)原子活動

原子活動描述業(yè)務流程行為的基本步驟，是流程定義中所使用的活動原語，與服務進行交互，操作傳輸數(shù)據(jù)或處理異常.BPEL包含8種類型的原子活動:〈receive〉、〈reply〉、〈invoke〉、〈assign〉、〈throw〉、〈exit〉、〈wait〉和〈empty〉.原子活動中與外界進行交互的活動是:〈invoke〉、〈reply〉和〈receive〉.流程的伙伴之間通過使用這3種活動發(fā)生交互，通過指定端口類型、操作以及伙伴，這些活動中的每一種活動被標識出它所屬于的Web服務調(diào)用.

2)結構化活動

結構化活動描述了一系列活動的執(zhí)行次序.通過BPEL所提供的結構化活動，可以將各種活動進行組合，形成活動有序執(zhí)行的流程.這些結構化活動，類似于傳統(tǒng)編程語言中的控制結構，表達業(yè)務協(xié)議中所涉及的控制模式、數(shù)據(jù)流、故障和外部事件的處理以及在流程實例之間進行消息交換的協(xié)調(diào).BPEL包含8種類型的結構化活動:順序活動〈sequence〉，選擇活動〈if〉，循環(huán)活動〈while〉、〈repeatUntil〉、〈forEach〉，并行活動〈flow〉，事件選擇活動〈pick〉，BPEL語句塊〈scope〉.

下面將從Web服務的角度出發(fā)，集中關注與Web服務的調(diào)用、消息交互相關的活動，它們?yōu)閃eb服務描述了輸入消息、輸出消息以及Web服務組合的執(zhí)行行為和結構信息等.

2 Web服務依賴圖

依賴圖起源于CFG，CFG是程序代碼中用來描述程序流程、分支結構等的典型方法.Yacoub等［6］將CFG引用到基于構件的應用程序中，用來表示構件間的結構關系以及可能的執(zhí)行路徑，稱之為CDG.本文將傳統(tǒng)的構件依賴圖的原理應用到Web服務中，對Web服務及消息傳遞路徑進行描述，稱之為Web服務依賴圖(WSDG)，其定義如下:

定義1(服務依賴圖)WSDG定義為四元組〈N，E，s，t〉，其中〈N，E〉為有向圖，s為開始節(jié)點，t為終止節(jié)點.N為節(jié)點的集合E為有向邊的集合

定義2(節(jié)點n)n∈N用來表示W(wǎng)eb服務，ni表示 Web 服務Wi，ni=〈Wi〉，其中Wi是第i個Web服務，且

定義3(服務Wi)Web服務由三元組〈Ni，Ti，Ri〉定義，其中Ni為服務名，Ti為服務類型，Ti指明當前服務所屬的類型，可以是基本服務，也可以是包含結構化活動的服務，Ti={s，t，basic，structure，while，scope}.其中，s表示起始節(jié)點，t表示終止節(jié)點，basic活動包含了〈invoke〉、〈reply〉和〈receive〉，而結構化活動〈sequence〉、〈if〉、〈flow〉、〈pick〉和〈forEach〉最終可以進一步拆分為若干個basic活動的組合.〈while/repeatUntil〉，〈scope〉等結構化活動也可以進一步拆分為一個活動的多次循環(huán)調(diào)用.Ri為服務的可靠性，指服務在被調(diào)用時能夠正確執(zhí)行的概率R且 0≤Ri≤1.

定義4(有向邊e) 有向邊e表示從一個服務轉移到另外一個服務的控制流，由三元組表示，其中Tij表示從節(jié)點ni到nj的轉移路徑名，RT

ij表示從節(jié)點ni轉移到節(jié)點nj的可靠性，Pij表示從節(jié)點ni到轉移到節(jié)點nj的轉移概率

3 基于WSDG的可靠性模型

3.1 BPEL活動分析

BPEL中包含了原子活動和結構化活動，活動之間存在依賴關系［12］.本文所關注的是活動之間的控制依賴關系.BPEL中影響活動之間的控制依賴的因素主要有3個:

1)如果活動之間有消息傳遞，即活動A發(fā)送消息到活動B，那么稱活動B控制依賴于A［5］.如BPEL程序中實現(xiàn)服務消息交換機制的語句調(diào)用，同步服務機制的receive－reply語句，說明了原子活動receive和reply活動之間的控制依賴關系.

2)結構化活動定義了其所包含的原子活動或結構化活動的控制依賴關系.BPEL的結構化活動主要有〈sequence〉、〈if〉、〈pick〉、〈flow〉、〈for Each〉、〈while〉/〈repeatUntil〉和〈scope〉.

·sequence包含一組順序執(zhí)行的活動1，2，…，n.

·if根據(jù)條件表達式的結果進行不同活動的選擇.

·pick結構包含n個互斥的消息事件，當任意一個消息到達時，相應的活動被觸發(fā).

·flow結構中的n個活動并發(fā)執(zhí)行.

· forEach，while，repeatUntil都是循環(huán)結構，反復執(zhí)行活動.

3)BPEL中的變量(variable)和鏈接(link).變量不僅可以用于〈if〉、〈while〉/〈repeatUntil〉活動的條件表達式中，也可以用于〈flow〉活動中source元素的條件中［8］，而鏈接是〈flow〉活動中的布爾變量，用來在〈flow〉活動中定義更多的控制結構.如下面的BPEL程序片段中定義了結構化活動flow中，活動X和活動Y之間的控制依賴關系，這種控制依賴關系通過source和target元素獲取.

3.2 Web服務依賴圖的構造

根據(jù)3.1節(jié)給出的3個因素來分析BPEL文檔，獲得活動之間的控制依賴關系，進而構造服務組合的Web服務依賴圖.圖1中給出了BPEL到對應的WSDG的轉換.對于原子活動中與Web服務交互的〈invoke〉、〈receive〉和〈reply〉活動而言，它們調(diào)用了Web服務的操作，是執(zhí)行的實體，所以將其看作是依賴圖中的節(jié)點，節(jié)點類型Ti=basic，如圖1中的服務依賴圖(1)所示.〈assign〉，〈empty〉，〈wait〉，〈throw〉和〈exit〉這5個原子活動不需要調(diào)用具體的服務，因此不予考慮.對于結構化活動而言，它們將各種基本活動或者其他結構化活動進行組合，形成活動有序執(zhí)行的流程.本文僅討論有多個基本活動組成的結構化活動，根據(jù)3.1節(jié)將BPEL的結構化活動轉化為相應的依賴圖.〈sequence〉、〈if〉、〈pick〉、〈flow〉和〈forEach〉活動由多個活動組成，其中每個活動既可以是基本活動也可以是結構化活動，因此在依賴圖的定義中，這幾個結構化活動可進一步分解成多個節(jié)點和邊的表示形式，如圖1中服務依賴圖(2)～(4)所示.如果結構化活動〈sequence〉、〈if〉、〈pick〉、〈flow〉和〈forEach〉中包含其他結構化活動，可以按照上述方法進一步遞歸分解，最終可以分解為若干個基本活動的組合.循環(huán)結構〈while〉/〈repeatUntil〉是自身包含的活動反復執(zhí)行，為了便于表示依賴圖，將〈while〉/〈repeatUntil〉和〈scope〉活動也用節(jié)點來表示，并分別定義節(jié)點類型Ti為while和scope，表明Wi包含Web服務依賴圖Wi－WSDG，如圖1中服務依賴圖(5)和(6)所示.

圖1BPEL到WSDG的轉換

3.3 可靠性預測算法

對于給定的BPEL文檔，首先根據(jù)3.1節(jié)的3種因素，構造出包含基本活動和各種結構化活動的WSDG，除了scope和while結構活動之外其余的所有結構化活動根據(jù)圖1逐步分解為基本服務的組合，最終得到的WSDG中有基本服務、scope結構和while結構.WSDG中Web服務之間的依賴關系已經(jīng)給出，但是WSDG中節(jié)點和邊的信息參數(shù)并不完整，需要對這些參數(shù)進行預測.下面討論WSDG中的參數(shù)問題.

1)Web服務的可靠性RiWeb服務可靠性的來源有很多，如:服務提供者可以提供可靠性值作為參考;服務請求者可以對該服務進行可靠性測試獲得可靠性值;根據(jù)Web服務器所記錄的歷史數(shù)據(jù)計算可靠性.本文假設basic類型的Web服務的可靠性已知.對于服務類型為while/repeatUntil和scope的Web服務，則基于其所包含的Web服務依賴圖來計算.Scope類型的Web服務可靠性用它所包含的Web服務的可靠性R1來表示，即

假設while類型的Web服務包含的循環(huán)服務為W1，P為while結構中繼續(xù)循環(huán)的概率，R1為W1的可靠性，則while類型的Web服務的可靠性計算公式為

2)轉移的可靠性RTijWeb服務的分布性使得服務之間的轉移失效率在可靠性預測中起著關鍵作用，因此必須考慮Web服務之間的轉移失效率.關于參數(shù)RTij的分析，在文獻［9］中已經(jīng)有所討論，本文不再進行討論，均假設轉移可靠性已知.

3)轉移概率PijPij表示從Web服務Wi轉移到Wj的概率.通過對依賴圖的分析，發(fā)現(xiàn)并不需要考慮各個服務之間的轉移情況，而是根據(jù)依賴圖得出可靠性預測所需要的轉移概率參數(shù).這里通過轉移次數(shù)來計算轉移概率.

給定WSDG以及所需要的參數(shù)后，就可以預測Web服務組合的可靠性.下面給出Web服務組合的可靠性預測算法.

算法1 Web服務組合可靠性預測算法

該可靠性預測算法將服務組合的Web服務依賴圖作為輸入，從起始節(jié)點開始并使用堆棧存貯節(jié)點，通過節(jié)點的依賴關系，找出當前節(jié)點的所有后續(xù)節(jié)點，來進行圖的深度優(yōu)先遍歷.在對圖中每個節(jié)點進行遍歷的同時計算服務的可靠性.假設每個服務在同一層次只能出現(xiàn)在一個結構化活動中，那么組合服務的依賴圖其實就是一個圖的最小生成樹，有n－1條邊，根據(jù)深度優(yōu)先遍歷的算法，可知該算法的復雜度為O(n).

如果當前活動Wi的后續(xù)節(jié)點是由基本服務w1，w2，…，wn組成的 sequence 結構或者串行的for－Each結構，則根據(jù)上述算法，其結構化活動的可靠性可用下式計算:

其中，Pj(j+1)=1，j=1，2，…，n.如果當前活動Wi執(zhí)行后，接下來執(zhí)行的活動是由基本服務w1，w2，…，wn組成的forEach，flow，if，pick結構，則結構化活動的可靠性可按下式計算:

如果是并行的forEach或者flow結構，式(4)中的Pij=1，若是if或pick結構，則

4 應用實例分析

本文以文獻［13］的申請貸款服務這一Web服務組合為例，分析該應用的BPEL文檔，生成依賴圖，最后預測該應用的可靠性.申請貸款的場景描述如下:用戶需要申請貸款，將個人信息和貸款信息提交給申請貸款服務.應用接收到用戶請求后，將執(zhí)行一個評估驗證流程，以決定批準或拒絕貸款.評估驗證流程根據(jù)用戶申請貸款額度和用戶信用信息，分為2種情況:首先進行評估，貸款額度低(小于10 000美元)且信用好的用戶將自動批準;對高額度貸款或者貸款額度低但信用差的用戶將進行進一步驗證，決定是否批準貸款.最終應用將是否批準貸款的結果以消息的形式通知用戶.該Web服務組合的依賴圖如圖2所示.

通過對依賴圖的分析，需要進行預測的參數(shù)主要有:每個服務的可靠性、每個轉移的可靠性、轉移概率.使用軟件Matlab對這些參數(shù)進行模擬，如表1和表2所示.最后采用可靠性預測算法，得到申請貸款應用的可靠性為Rcomp=0.807 1.

圖2 申請貸款服務的WSDG

表1 申請貸款服務的可靠性參數(shù)

表2 服務轉移參數(shù)

5 結語

本文介紹了Web服務組合的一種可靠性預測方法.首先將BPEL轉化為Web服務依賴圖，然后根據(jù)依賴圖得到需要預測的參數(shù)，最后基于WSDG和參數(shù)估計值計算Web服務組合的可靠性.本文主要貢獻是基于Web服務組合語言BPEL構造用于可靠性預測的Web服務依賴圖;依賴圖中處理了選擇、并發(fā)、循環(huán)和scope結構.本文所提出的Web服務依賴圖也可以應用于Web服務組合執(zhí)行時間、價格等的計算.接下來將進一步研究Web服務的可靠性參數(shù)的多種預測方式和依賴圖的精確建立.

［1］ Gokhale S S.Architecture－based software reliability analysis:overview and limitations［J］.IEEE Transactions on Dependable and Secure Computing，2007，4(1):32－40.

［2］ Hansen K M，Br?nsted J.RH－02－2010 Modeling service composition reliability in pervasive computing［R］.Reykjavik，Iceland:Science Institute，University of Iceland，2010.

［3］ Cheung R C.A user－oriented software reliability model［J］.IEEE Transactions on Software Engineering，1980，6(2):118－125.

［4］ Object Management Group，Inc.Business process modeling notation，V1.1 ［EB/OL］.(2008－01)［2011－10－31］.http://www.omg.org/spec/BPMN/1.1/.

［5］ Pautasso C，Alonso G.Visual composition of Web services［C］//Proc of Human Centric Computing Languages and Environments.Auckland，New Zealand，2003:92－99.

［6］ Yacoub S，Cukic B，Ammar H H.A scenario－based reliability analysis approach for component－based software［J］.IEEE Transactions on Reliability，2004，53(4):465－480.

［7］蘇志勇，周穎，李必信.面向用戶的Web服務可靠性計算模型［J］.東南大學學報:自然科學版，2008，28(4):605－610.

Su Zhiyong，Zhou Ying，Li Bixin.User－oriented Web services reliability computing model［J］.Journal of Southeast University:Natural Science Edition，2008，28(4):605－610.(in Chinese)

［8］ Hsu C J，Huang C Y.An adaptive reliability analysis using path testing for complex component－based software systems［J］.IEEE Transactions on Reliability，2011，60(1):158－170.

［9］ Huang C Y，Lin C T.Analysis of software reliability modeling considering testing compression factor and failure－to－fault relationship［J］.IEEE Transactions on Computers，2010，59(2):283－288.

［10］ Wang Lijun，Bai Xiaoying，Zhou Lizhu，et al.A hierarchical reliability model of service－based software system［C］//Proc of33rd Annual International Computer Software and Applications Conference.Seattle，USA，2009:199－208.

［11］ Wang W L，Pan D，Chen M H.Architecture－based software reliability modeling ［J］.The Journal of Systems and Software，2006，79(1):132－146.

［12］ Zheng Y Y，Krause P.Automata semantics and analysis of BPEL［C］//Proc of the2007Inaugural IEEE International Conference on Digital EcoSystems and Technologies.Carins，Australia，2007:147－152.

［13］ OASIS.Web services business process execution language，Version 2.0［EB/OL］.(2007－04－01)［2012－04－19］.https://www.oasis－open.org/committees/download.php/23964/wsbpel－v2.0－primer.htm.

WSDG-based reliability prediction approach for Web service composition

Xie Chunli1，2Li Bixin1Su Zhiyong1

(1School of Computer Science and Engineering，Southeast University，Nanjing 211189，China)
(2School of Computer Science and Technology，Jiangsu Normal University，Xuzhou 221116，China)

In order to estimate the reliability for Web service compositions based on service－oriented architecture(SOA)，a Web services dependency graph(WSDG)－based reliability prediction model is proposed.First the description language for web service composition WS－BPEL is introduced，and the atomic activity and structural activity which describe business process for web services are presented.Then the concept of WSDG is proposed based on the traditional control flow graph(CFG).WSDG is used to describe the execution behavior and the structural information for web services composition，such as service name，service type，service reliability，transition probability of service and reliability of transition.Moreover，control dependencies of basic activities and structured activities of business process execution language(BPEL)are analyzed and the WSDG of compositions are constructed.Finally，an algorithm for predicting the reliability of Web service compositions is presented based on the WSDG traversal.An example shows that the approach is simple and tractable.

Web services;reliability;Web services dependency graph(WSDG);business process execution language(BPEL)

TP311

A

1001－0505(2012)06－1074－06

10.3969/j.issn.1001－0505.2012.06.010

2012－05－17.

謝春麗(1979—)，女，博士生;李必信(聯(lián)系人)，男，博士，教授，博士生導師，bx.li@seu.edu.cn.

國家自然科學基金資助項目(60973149)、教育部博士點基金資助項目(20100092110022)、江蘇省高?？蒲谐晒a(chǎn)業(yè)化推進項目(JHB2011－3).

謝春麗，李必信，蘇志勇.基于WSDG的Web服務組合可靠性預測［J］.東南大學學報:自然科學版，2012，42(6):1074－1079.［doi:10.3969/j.issn.1001 －0505.2012.06.010］