動態(tài)的QoS感知Web服務選擇和組合優(yōu)化模型(

1、11動態(tài)的QoS感知Web服務選擇和組合優(yōu)化模型* 基金項目：本課題得到國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2002AA415280)、教育部博士點基金項目(20050359004)、教育部新世紀優(yōu)秀人才計劃項目(NCET-04-050562)、合肥工業(yè)大學科學研究發(fā)展基金項目(2007GDBJ012)資助.作者簡介: 蔣哲遠,男,1966年生,博士,副研究員,主要研究領(lǐng)域為面向服務軟件工程、軟件體系結(jié)構(gòu)和軟件工程環(huán)境. jzheyuan. 韓江洪,男,1954年生,教授,博士生導師,主要研究領(lǐng)域為智能控制技術(shù)和分布式系統(tǒng). 王釗,男,1958年生,副教授,主要研究領(lǐng)域為電子商務和軟件工

2、程.通信地址：安徽省合肥市屯溪路193號 合肥工業(yè)大學微機所13信箱郵政編碼：230009電 話：(0551)2902075, (0-mail: jzheyuan蔣哲遠 韓江洪 王釗(合肥工業(yè)大學計算機與信息學院 合肥 230009)摘 要 Web服務軟件工程的實用化挑戰(zhàn)之一是QoS感知的選擇、組合和稍后的綁定，表現(xiàn)為允許在運行時綁定一組領(lǐng)域Web服務構(gòu)成面向服務的系統(tǒng)。這些領(lǐng)域Web服務在提供要求的功能同時，還滿足一些非功能約束，例如總的費用或響應時間，并且使之最優(yōu)化。提出了一種把Web服務看作為首類構(gòu)件對象的關(guān)系查詢基礎(chǔ)結(jié)構(gòu)，它通過各種Web服務操作調(diào)用評估查詢。

3、由于個性化和效率在這種評估中起重要作用，提出了一個基于聚合不同Web服務的多屬性QoS參數(shù)的查詢優(yōu)化模型，該模型通過用戶設定的全局約束和偏好、一個動態(tài)的等級方案、以及多級匹配來調(diào)整QoS。等級提供了一個Web服務的行為評估，而多級匹配通過使能類似的和部分的答案對解決方案的空間進行擴展。給出了模型求解的遺傳算法，并從適應度函數(shù)的靜態(tài)懲罰、動態(tài)懲罰以及拉伸三個方面對優(yōu)化性能進行了比較。該文最后介紹了一個從高端實現(xiàn)的服務查詢引擎原型系統(tǒng), 用以展示該方法的適應性、可行性和有效性。關(guān)鍵詞 Web服務; 服務質(zhì)量; 服務選擇; 約束優(yōu)化; 遺傳算法中圖分類號：TP311 文獻標識碼：A An Optim

4、ization Model for Dynamic QoS-Aware Web Services Selection and CompositionJIANG Zhe-yuan HAN Jiang-hong WANG Zhao(School of Computer and Information, Hefei University of Technology, Hefei 230009)Abstract One of the most promising opportunities from a Web services engineering perspective is the QoSaw

5、are selection, composition and late-binding. This allows you to dynamically assemble a collection of domain-specific QoS-aware Web services providing the required features into a composition services that can meet some nonfunctional constraints, and optimize criteria such as the overall cost or resp

6、onse time. This paper presents a query infrastructure that considers Web services as first class component objects. It evaluates queries through the invocations of different Web services operations. Because personality and efficiency play a central role in such evaluations, the paper proposes a quer

7、y optimization model based on aggregating the multi-attribute QoS parameters of different Web services. The model adjusts QoS through global constraints and preferences set by the user, a dynamic rating scheme, and multilevel matching. The rating gives an assessment of Web services behaviors. Multil

8、evel matching provides the expansion of the solution space by enabling similar and partial answers. The paper describes a genetic algorithm for solving the model, and compares the optimization performance of the genetic algorithm using various fitness functions varying in terms of static penalty, dy

9、namic penalty, and stretching. The proposed approach has been applied to a service query engine system for SEIFCW, which consequently shows its applicability, feasibility and efficiency.Keywords Web services; quality of service (QoS); service selection; constraint optimization; genetic algorithm1 引言

10、面向Internet的Web服務應用，比如信息門戶、實時網(wǎng)格計算和電子商務應用等，越來越關(guān)注提供給用戶的服務質(zhì)量(Quality of Service，QoS)1。從Web服務發(fā)現(xiàn)的角度看，如何從大量的Web服務中有效地快速選擇和集成最適合用戶需求的、高可信性的、QoS感知的Web服務成為面向服務軟件工程的一個新的挑戰(zhàn)。面向服務軟件工程代表了基于構(gòu)件軟件工程(Component-Based Software Engineering，CBSE)的自然演化。在CBSE中，一個構(gòu)件集成者搜索可重用構(gòu)件，然后使用一些膠合代碼(glue code) 2把它們集成到一個實際的新系統(tǒng)中。Web服務由服務提供

11、者在服務注冊中心發(fā)布其功能，并通過遠程服務調(diào)用操作供服務請求者綁定使用，進而沒有必要在開發(fā)時就把服務集成到應用中。Web服務的接口發(fā)布、發(fā)現(xiàn)和調(diào)用都是執(zhí)行基于XML的一些標準，例如WSDL、 UDDI和SOAP。因此，一個面向服務系統(tǒng)是由一些服務調(diào)用構(gòu)成，并使用膠合代碼或者一些具體的Web服務組合語言(如BPEL4WS)來合成。面向服務系統(tǒng)的最大期許是使用稍后的綁定機制。事實上，一些關(guān)鍵的業(yè)務應用場景(如面向服務ERP協(xié)同集成框架SEIFCW3中的組裝領(lǐng)域服務構(gòu)件)是給出某個領(lǐng)域服務的所需功能單元的具體特性描述(這個特色描述將據(jù)此作為一個抽象服務)，且在組裝實現(xiàn)時有多個符合該特性描述的服務(稱

12、為具體服務)可利用。一個抽象服務和對應的所有具體服務在功能上是等價的，因而可相互取代。它們之間的選擇由非功能屬性來確定，例如QoS屬性。一個用戶可決定挑選最便宜的和最快的服務，或者是兩者之間的折中。參照文獻4，QoS的屬性包括費用、響應時間、可用性、聲譽。此外，還可能有一些領(lǐng)域特定的QoS屬性，例如一個運輸服務的QoS屬性可能有溫度或濕度。通常，一個用戶可能對某些QoS屬性給出限制值，例如費用不能大于某個給定值，進而來影響服務的選擇。另一方面，服務提供者可以把QoS屬性值的估計范圍作為和潛在用戶之間契約的一部分，例如服務等級協(xié)定(Service Level Agreement，SLA)。SLA

13、是用戶與服務提供者之間達成的有關(guān)服務內(nèi)容、服務質(zhì)量等方面的合約，它規(guī)定了服務提供者必須為用戶提供的具體服務參數(shù)。SLA評價的最大優(yōu)點是賦予用戶獲知系統(tǒng)性能的權(quán)利，SLA評價也為系統(tǒng)提供者提供了一種競爭依據(jù)。服務查詢引擎(service query engine)是SEIFCW的核心模塊之一，它的主要功能包括領(lǐng)域服務查詢請求提交、服務檢索、服務選擇、服務組合并生成基于XML的服務組合描述語言等。由于QoS對于Web服務在領(lǐng)域的成功應用非常關(guān)鍵，因此，如何使查詢的組合服務提供預期的服務質(zhì)量正成為服務查詢引擎設計面臨的重要挑戰(zhàn)。其中, 一個有關(guān)的問題是如何使抽象服務與具體服務之間的快速綁定，且使實際

14、的Web服務滿足SLA規(guī)定的QoS約束，并使服務集成者所選擇的一些適應度標準最優(yōu)化(例如，費用最小)。另外，求解QoS感知組合問題的解是一個NP難題5。一些方法，主要是基于線性規(guī)劃, 已經(jīng)在一些文獻中提出6。為此，本文提出了一種新穎的服務查詢和優(yōu)化模型用于保障SEIFCW應用的QoS感知的服務組合，并用遺傳算法(Genetic Algorithm，GA)來解決QoS感知的組合問題。所提模型的主要特點是：使用關(guān)系表達查詢請求；領(lǐng)域服務的抽象化；可擴展的Web服務QoS度量；基于多度量的組合服務QoS優(yōu)化。論文的隨后部分組織如下：小節(jié)2介紹一種基于關(guān)系和抽象操作的QoS感知的Web服務多層查詢體系

15、結(jié)構(gòu)；小節(jié)3建立QoS感知的Web服務查詢優(yōu)化數(shù)學模型，并使用遺傳算法對其目標進行求解；小節(jié)4給出模型在SEIFCW中的實現(xiàn)，并報告和討論了仿真的結(jié)果；小節(jié)5介紹一些相關(guān)工作，并和相關(guān)研究作比較；小節(jié)6是最后的結(jié)論，同時對未來的工作進行展望。2 Web 服務的查詢模式Web服務的使用主要由通過發(fā)送和接收消息的一組調(diào)用操作組成。盡管這可滿足簡單應用的需求，但對訪問千變?nèi)f化的Web服務的復雜應用，需要使用一種集成方式去操作與交付Web服務的功能。此外，隨著Web服務的廣泛應用，提供相同功能的服務越來越多。但由于競爭，Web服務提供的這些功能(例如，要求不同的輸入和輸出參數(shù))和使用條件(QoS的等級

16、不同)的方式方面是有區(qū)別的。另外，滿足用戶的需求有時并不需要返回精確的答案。事實上，用戶可能對可供選擇的或部分的答案滿意。針對上述挑戰(zhàn)，需要提出一個在操作調(diào)用期間查詢Web服務和信息流的新方法，以便決定各種Web服務操作的調(diào)用，返回相應輸出結(jié)果的整合。該方法強調(diào)查詢決策過程的優(yōu)化，同時應允許部分的答案。2.1 Web服務查詢模式的體系結(jié)構(gòu)為了方便用戶和Web服務的交互，需要使用一個通用的方法表達給定應用領(lǐng)域的Web服務空間。為此，我們提出了圖1所示的三層查詢模式，并定義了一組稱為抽象操作的特定領(lǐng)域操作，它是對特定領(lǐng)域Web服務應用共用操作的抽象化(虛擬化)，不屬于任何實際的Web服務。查詢層(

17、query layer)：由提供給用戶一個表達和提交查詢語句到Web服務接口的關(guān)系集組成，可使用一種從XML文檔中抽取數(shù)據(jù)的查詢語言規(guī)范XQuery來構(gòu)造。用戶從查詢層提交關(guān)系聯(lián)合查詢(關(guān)系和條件的聯(lián)合)，其通用形式如下：其中，符號:-表示映射，Ri是來自查詢層的關(guān)系，X和Xi是變量元組；Ck代表查詢中出現(xiàn)的變量條件。條件的形式是Ck = x op c, 式中x是出現(xiàn)在任何一個Xi中的輸入或輸出變量，或者是QoS 規(guī)格的元素(參見小節(jié)3)，c是一個常量，op=, , <, >, , 。查詢模型根據(jù)各種映射規(guī)則把每個關(guān)系映射到對應的抽象操作中。圖1 QoS感知服務查詢的三層體系結(jié)構(gòu)用

18、戶Q(X)查詢層抽象層QoS接口尺度屬性領(lǐng)域量制*1*1*1操作*11實現(xiàn)1實現(xiàn)1具體層服務服務等級SLAAgreement請求者提供者1*1*1*1*抽象層(abstract layer)：由一個特定領(lǐng)域典型地提供的類Web服務操作組成的，可采用基于XML的WSDL對包含其操作的服務接口進行描述。標準WSDL不提供對QoS支持，需要對WSDL進行擴展，以便能使WSDL恰當?shù)靥峁㏎oS信息。例如，通過擴展WSDL提供一個服務提供者和請求者之間的Web服務SLA文檔引用，可使WSDL的每個操作和一個由Web服務SLA定義的QoS相關(guān)聯(lián)，其格式為：<operation name="

19、opName" WSLA="WSLAOfferedURL"><input message="tns:opName"/><output message="tns:opNameResponse"/></operation>QoS是一個屬性集，它的每一個屬性, 例如領(lǐng)域(domain)、尺度(scale)和量制(metrics)等需要根據(jù)具體應用場景來精確定義。這些QoS屬性的抽象集都需要綁定到某個接口操作，以便規(guī)定它的應用屬性集。具體層(concrete layer)：代表Web上提供的

20、Web服務空間，即潛在的目標查詢侯選者，包括元服務與組合服務，且與服務等級(service level)有關(guān)。當一個服務提供者在注冊中心的數(shù)據(jù)庫保存他的服務和服務等級時，其應用范圍相應地被定義。一個提供者和一個請求者能協(xié)商更精確的屬性，并創(chuàng)建一個SLA作為契約。由于Web服務開始是未知的，查詢模型需要發(fā)現(xiàn)它們，并與出現(xiàn)在查詢中的抽象操作相匹配。使用該查詢模式的優(yōu)點之一是容易使用UML的模式驅(qū)動方法(model-driven methodology)建模和開發(fā)實現(xiàn)7。下面是抽象層到具體層的轉(zhuǎn)換定義。定義1。 假設抽象服務接口I的QoS集定義為如下的一個屬性Pi集：QI = P1，Pn。其中，對每

21、個PiQI ，1in 都有一個領(lǐng)域dom(Pi)和尺度scale(Pi)的度量值。當然，屬性被度量或賦值的前提條件是首先定義好每個屬性的量制metric(Pi)。此外，假設。那么，一個接口I到一個QoS等級為LS的具體服務SI的映射定義如下：式中符號是條件連接詞，符號的右邊謂詞邏輯規(guī)定了映射需滿足的約束。2.2 關(guān)系到抽象操作的映射查詢層的關(guān)系定義了應用域一個具體的視圖，可表達為針對抽象操作的連接查詢，似乎抽象操作就是關(guān)系。定義2。 假設R是查詢層定義的關(guān)系集合，V是抽象操作集合，則對任何關(guān)系RiR,式中xi是Ri的屬性，VjV，yji是相應操作的輸入和輸出變量。這個定義意味著為了獲得Ri的元

22、組，需要調(diào)用不同的操作Vj，但并不要求對這些操做任何的排序或限制并發(fā)。用戶能直接地使用抽象操作訪問Web服務，但關(guān)系的使用有兩個好處。首先，讓用戶使用一個自然的方式表達和提交類似數(shù)據(jù)庫的查詢；另一方面，為對服務空間一些特定部分感興趣的某個特定用戶組提供了量身定制的視圖。2.3 抽象操作表示抽象操作代表了一個特定應用域所能提供的典型功能。對在查詢中出現(xiàn)的任何抽象操作，最終都要定位到相關(guān)的Web服務操作，因此抽象操作需要有一個語義描述和句法屬性，同時還要有描述具體Web服務和抽象操作的一個共同的本體(ontology)8。任何一個操作，無論是抽象的還是具體的，語義上都可以通過它的功能(functi

23、on)和類別(category)來描述。功能包含兩個屬性：功能性(functionality)，代表該操作所提供的業(yè)務功能；術(shù)語(term)，包含該操作的一個可替代功能性命名術(shù)語列表。類別同樣也包含兩個屬性：領(lǐng)域(domain)，給出操作的具體應用領(lǐng)域；術(shù)語，抽取出與具體應用領(lǐng)域類似的領(lǐng)域分類術(shù)語詞表。任何一個操作在調(diào)用前都要求它的輸入變量被賦值。在構(gòu)造查詢時，用戶可為不同的變量自由地指定任意類型的條件。 這可能導致一種情形，就是系統(tǒng)不能調(diào)用操作，這是由于一些輸入變量遺漏了賦值。如果所有的抽象操作描述都給出了其輸入變量的各種可能值，上述問題就會解決(盡管對所有的輸入變量不可能總是做到這一點)。

24、本文擴展每個輸入變量到所有可能取值，以便盡量滿足出現(xiàn)在查詢中任意一個條件。下面的五元組形式化地表達了每個抽象操作：Vop = <In, Out, Restriction, Category, Function>上式中，In是輸入變量的集合；Out是輸出變量的集合；Restriction是輸入變量的定義域，它由一組對偶(x, range)構(gòu)成的集合, 其中x是In中的枚舉變量，而range是x的所有可能值的集合；Category描述興趣域；Function描述業(yè)務功能。2.4 抽象操作的匹配類型由于Web服務提供者之間的競爭，必然在請求輸入、返回輸出和QoS等方面存在差異。例如，不同

25、運輸服務提供者的運輸費用、快捷性和服務內(nèi)容等可能有所區(qū)別。這就意味著對某個給定的抽象操作并不總能找到一個精確的匹配。作為替代，僅查找與聯(lián)合查詢中出現(xiàn)的抽象操作精確匹配的具體操作，一個允許抽象操作和具體操作的屬性不一致的更靈活的匹配方案可能更滿足用戶的需求。首先定義一個相似函數(shù)Similarity來檢查兩個操作中的兩個屬性是否相似：如果x和y 符合應用域本體庫所定義的相似概念，那么Similarity (x, y)就為真。定義3(操作的輸入變量集相等)。 對任意的兩個操作op1和op2，In(op1)=In(op2)，當且僅當： In(op1)和In(op2)變量數(shù)相同，且 xIn(op1),y

26、In(op2)，或者xIn(op2),yIn(op1)，使Similarity (x, y)滿足真值。類似地能定義Out(op1)=Out(op2)。用同樣的方法，也可以分別定義In(op1)In(op2)和Out(op1)Out(op2), 其中第一個集合是第二個集合的子集。假如v和c分別表示抽象操作和具體操作，通過改變抽象操作和實際操作的比較方式，可以識別出四種不同的匹配類型。定義4(抽象操作匹配類型)。 如果兩個操作v和c有相同的輸入和輸出變量，以及相同的Category和Function，稱之為精確匹配Exact(v, c)；如果兩個操作v和c有同樣的輸入和輸出變量，且它們的Categ

27、ory和Function發(fā)生交疊，稱為重疊匹配overlap(v, c)；假如兩個操作v和c有同樣的Category 和Function, 且Out(c)Out(v)或者In(c)In(v)，稱為部分匹配partial(v, c)；如果兩個操作c和v滿足Out(c)Out(v)或者In(c)In(v)，且它們的Category和Function屬性交疊，稱為部分和重疊匹配composite(v, c)。由定義4可知，精確匹配要求具體操作與抽象操作的每個屬性概念都相同，這是最高級別的匹配；重疊匹配提供抽象操作的相近功能的具體操作；部分匹配符合兩個操作的輸入和輸出屬性不一致的情形；部分和重疊匹配組

28、合了重疊匹配和部分匹配，并且各種匹配存在如下關(guān)系。命題1。 “=>”表示蘊含關(guān)系，“”表示邏輯析取關(guān)系，“”表示邏輯合取關(guān)系，則存在Exact(v, c) => partial(v, c)overlap(v, c)；Exact(v, c)partial(v, c)overlap(v, c)=>composite(v, c)。為了量化各種匹配類型的匹配精確度，還需要給每一個匹配類型賦予了一個匹配度(matching degree)，以此直接地影響查詢結(jié)果的質(zhì)量。上述每個匹配類型分別獲得1、3/4、1/2 和1/4的匹配度。該取值是任意指定的，主要是為了區(qū)分不同的匹配精確度。3

29、基于遺傳算法的Web服務查詢優(yōu)化方法描述由于存在不同Web 服務的幾個服務執(zhí)行計劃能潛在地解決相同的查詢。因此，需要為在所有可能的執(zhí)行規(guī)劃中挑選最優(yōu)的Web 服務建立適當?shù)臉藴?。相互競爭的Web 服務之間的一個關(guān)鍵特色是他們的QoS，它包含幾個定量的和定性的參數(shù)，該參數(shù)度量了Web 服務所發(fā)布的功能是否好?，F(xiàn)在已經(jīng)建立了描述響應時間(time)、服務費用(cost)、可用性(availability)和可靠性(reliability) 的通用QoS 規(guī)格4。對于領(lǐng)域具體QoS 規(guī)格要根據(jù)具體領(lǐng)域進行定義，本文利用可擴展本體技術(shù)建立起來了領(lǐng)域內(nèi)專門的QoS 規(guī)格。通常，每個Web服務都包含一組操

30、作，調(diào)用的最小粒度為操作(operation)。Web 服務ws的操作op的QoS 定義如下：QoS(ws, op) =<T(ws, op), C(ws, op), R(ws, op), A(ws, op), U(ws, op)>, 其各參數(shù)的含義為：T(ws, op)表示執(zhí)行時間；C(ws, op)表示費用；R(ws, op)表示可靠性；A(ws, op)表示可用性；U(ws, op)表示領(lǐng)域QoS規(guī)格，定義為：(U1(ws, op), U2(ws, op) , , Un(ws, op)，即n個用戶定義的屬性組成的向量。為便于QoS模型的建立和求解，把某個Web 服務ws的調(diào)用操

31、作op 記為任務t，則上面給出的QoS模型可簡化為如下的一個5元組，即QoS(t) =<T(t)，C(t)，R(t)，A(t)，U(t)>。每個質(zhì)量標準都有相應的計算和評價方法，并且QoS模型有一個總體評價方法。優(yōu)化過程的目的是使下面QoS 參數(shù)的每一個值為最大或最小：響應時間(T)：代表一個服務操作在被調(diào)用后平均返回結(jié)果的時間，包括服務計算時間(Tcom)、中間件開銷(Tmid)和往返通信時間(Tnet)?？偟捻憫獣r間T(t)= Tcom(t)+ Tmid(t)+ Tnet(t)。服務費用(C)：是一個Web服務消費者每次服務調(diào)用所必須支付的相關(guān)費用。可靠性(R)：表示服務操作可

32、用的概率，其定義如下：，其中MTTF(t)表示操作的平均無故障時間，MTTR(t)表示操作的平均修復時間?？捎眯?A)：代表一個Web服務正常運行的概率。取值越大意味著有較高的可用性，而較小的取值表示可用性低。由于Web服務是按次進行調(diào)用的，可以采用離散時間模型來描述其可用性：，其中(t)i定義如下：用戶定義(U)：服務消費者定義的領(lǐng)域QoS規(guī)格，如聲譽(reputation)、安全性(security)和互操作性(interoperability)等。優(yōu)化的目標是使負向參數(shù)(如反應時間和費用)減少到最小值，同時使正向參數(shù)(如可用性和可靠性)取得最大值。正如引言所描述的那樣，本工作的一個目標是

33、基于GA的方法，能迅速地確定綁定到抽象服務的一個具體服務集，構(gòu)成一個組合服務的工作流。其中的需求包括：滿足基于SLA的QoS約束。例如，服務的用戶可能有一個有限的預算，因此服務費用受到一定的約束，或者響應時間不能超過某個約定。時常，局部限制(例如，特定操作的費用不能超過限制)和全局限制(例如，總的響應時間受約束)需要同時被滿足；使一些特別的QoS 參數(shù)的某個函數(shù)最優(yōu)化。例如，用戶可能想使響應時間最段，同時保持費用低于某個限制。隨之而來，還應該考慮由N個抽象服務(操作)構(gòu)成的一個組合服務S=ws1，ws2，wsN，其結(jié)構(gòu)通過一些工作流描述語言來定義。每個元素wsi能被綁定到M個具體服務csi1，

34、csiM，它們在功能上是等價的。在描述使用GA找到最優(yōu)化問題的解之前，還需要描述怎樣計算一個組合服務的QoS，這要從從元服務的QoS屬性值計算開始。3.1 計算組合服務的QoS計算組合服務的QoS方法類似文獻4提出的方法，工作流的描述語言限定為BPEL4WS。對工作流中的一個Switch構(gòu)造，每個Case語句被標注為可能的選擇。例如，對一個包含Switch的工作流，它由兩個Case語句組成，費用分別是C1和C2且出現(xiàn)的概率為p和1 p，則總的費用計算公式如下：pC1 + (1-p)C2 顯然，概率是由工作流設計者初始指定，最終還需要通過監(jiān)測工作流執(zhí)行所獲得的信息加以更新。While不同于文獻4

35、的Loop處理，主要地建議采納一個到達Switch構(gòu)造的機制(基于進入/退出While的概率)。我們的方法類似文獻6所采用的方法。例如，While被標記為一個估計的迭代數(shù)k。代替展開的While，這里的While的 QoS計算考慮迭代因子k。例如，假如While復合體有一個代價Cl，那么While的估計代價將是kCl。這種處理While方法有兩個優(yōu)勢：能迅速計算總的工作流QoS，而不必展開While；被估計的QoS反映了While的迭代數(shù)。表1計算單個工作流構(gòu)造的QoS屬性的聚集函數(shù)QoS 屬性SequenceSwitchFlowWhileT(t)C(t)A(t)R(t)U(t)表1顯示了單個

36、工作流構(gòu)造的QoS屬性的聚合函數(shù)。一個組合服務的具體應用例子就是一個組合服務的描述，在該描述里，每個抽象服務被綁定到某個相應的具體服務中，總的QoS能通過應用表1描述的規(guī)則被計算。盡管對一些標準的QoS 屬性聚合函數(shù)已經(jīng)被清楚地指定了4,6，但可能有其它屬性(例如，依賴領(lǐng)域的屬性)需要用戶基于抽象操作本體庫來定義，其單個工作流的聚合函數(shù)也要用戶指定(見表1的最后一行)，并和標準的QoS屬性一樣發(fā)布到服務注冊中心的WS-QoS本體庫中（見圖3）。該表并不是完備的，它只包含原型系統(tǒng)要使用的規(guī)則，且除了While，聚合函數(shù)和文獻4所提出的計算方法基本一致。這些函數(shù)能被遞歸地定義在工作流的復合節(jié)點，即

37、對任務t1，tm的一個Sequence構(gòu)造，響應時間和費用函數(shù)是加法，而可用性和可靠性是乘法。Switch 構(gòu)造的Case 1，n，其相應概率分別為pa1，pan，并滿足 ，任務分別為 t1，tn，總是被估計為每個任務的屬性值之和，乘上它所屬Case的概率。Flow構(gòu)造的聚合函數(shù)基本上同Sequence構(gòu)造相同，除了時間屬性，它是并行任務t1，tp的最大值。最后，具有任務t迭代k次的While構(gòu)造等于k次t的Sequence構(gòu)造。3.2 Web服務等級一個Web服務在其生命期可能存在起伏，因而它不可能完全實現(xiàn)SLA所廣告的QoS參數(shù)。一般來說，大部分用戶能接受QoS參數(shù)的實際值和廣告值之間的細

38、微偏差。然而，巨大的差距就表明了Web服務所提交功能的性能正在下降。由于上述原因，系統(tǒng)需要對被調(diào)用的Web服務的QoS參數(shù)實施監(jiān)控。本質(zhì)上，QoS參數(shù)波動的度量是給Web服務提供一個評估，而這種評估在優(yōu)化過程中扮演一個重要的角色。一個用戶每次選擇和調(diào)用一個Web服務的某個操作op時, 我們度量期望的QoS和實際發(fā)布的QoS之間的距離。此處的QoS 距離是所有QoS參數(shù)的偏差(或它們的倒數(shù))加權(quán)之和。更精確地說，假設pQi 和dQi分別是QoS的第i個參數(shù)的期望值和實際交付值，pos和neg分別是取最大值和最小值的QoS參數(shù)序號集，i指一個服務集成者(或用戶)給一個特定的QoS屬性所賦予的重要性

39、，則QoS距離(DQoS)的計算公式如下： (1)Web服務等級用下面公式來刻畫： (2)式(2)中的負閥值和正閥值+分別稱為置信下限和置信上限；q為調(diào)整QoS距離波動參數(shù)，通常取值為1。公式表明：如果一個Web 服務的QoS距離滿足SLA所規(guī)定的QoS參數(shù)波動區(qū)間(,+)，那么它接收正常的等級1；如果一個Web 服務的QoS距離低于負閥值, 那么它的等級將減少；如果一個Web 服務的QoS距離高于正閥值+, 那么它的等級將增加。一個簡單的Web服務等級把所有的QoS 波動歸納到單一的公式中。通過分配給每個參數(shù)的各自等級，我們能分別處理每個服務的QoS。下節(jié)將使用每個參數(shù)的等級給目標函數(shù)中相應

40、的QoS 賦權(quán)值，或聚集所有等級，并用它們度量整個優(yōu)化公式。在Web中，目前已存在多個等級方案系統(tǒng)，其實現(xiàn)主要是依賴用戶的反饋，包括消費者對產(chǎn)品和服務的評價，以及來自提供者的個人體驗。本文基于圖1的查詢基礎(chǔ)結(jié)構(gòu)，使用了一個專用Agent9負責對Web服務操作調(diào)用的監(jiān)控，從而能方便地定期更新并細化自己的服務等級。3.3 目標函數(shù)和約束條件Web服務是否成功地發(fā)布了它們的功能主要取決于QoS。因而，優(yōu)化過程的目標是選擇和使用具有最優(yōu)QoS參數(shù)的Web服務。另外兩個參數(shù)等級(rating)和匹配度(md)進一步細化了服務功能發(fā)布成功的定義。因此，我們能通過下面三個度量，即期望的QoS參數(shù)、等級和匹配

41、度，來刻畫解決一個查詢所涉及的任何Web服務操作。已存在計算一個基于它的QoS參數(shù)的操作總體質(zhì)量的各種方法。在決策過程中廣泛地使用的簡單添加權(quán)重方法通常取得了非常接近更為復雜的方法取得的排序結(jié)果。該方法包括以下三個基本步驟，操作質(zhì)量是最后一步獲得的數(shù)值之和。對L個不同的QoS參數(shù)標準化，以便使它們可比較。為參與查詢的每一個QoS參數(shù)施加用戶指定的權(quán)重i，并且滿足為每一個操作添加經(jīng)過加權(quán)和標準化處理后的QoS參數(shù)。為解析一個查詢過程中的每個抽象操作opj(對應匹配的具體服務數(shù)組項目索引)，只要定義一個取最大值的目標函數(shù)fj(opj)： (3)式中 (4) (5)其中pQimax(opj)是匹配相

42、同抽象操作opj的所有具體操作中第i個QoS參數(shù)的最大值，而pQimin(opj)是其最小值。對目標fj(opj)(j=1，2，N)正規(guī)化處理，設fjmax(opj)和fjmin(opj)分別為目標fj(opj)的最大值和最小值，線性正規(guī)化后的目標值vj(opj)為： (6)若是操作opj其權(quán)重，并滿足 ，而ci(g)是聯(lián)合查詢的約束條件，可由算法直接從查詢中獲得(等式條件)，或者從抽象操作定義的范圍獲得(不等式條件)，則查詢過程的可行解向量g=(op1，op2，opN)是下列多目標優(yōu)化問題的解： (7)3.4 使用遺傳算法的搜索策略GA本質(zhì)上是一個通過群體的迭代來不斷優(yōu)化的過程10。它簡單、

43、通用, 對問題的種類有很強的魯棒性，很適合解決NP問題。與線性整數(shù)規(guī)劃不同，GA對優(yōu)化問題的目標函數(shù)和約束條件的線性化不施加限制，從而允許優(yōu)化模型使用各種可能的QoS屬性(甚至定制)。為了讓GA找到問題的一個解，首先需要使用一個合適的基因組給問題編碼。在本文中，基因組使用了一個整數(shù)數(shù)組來表示，數(shù)組中的項目數(shù)為組成我們服務的抽象服務數(shù)，數(shù)組中的每個元素依次包含一個與抽象服務相匹配的具體服務數(shù)組項目索引。圖2給出了基因組是怎樣產(chǎn)生的原理。圖2 基因組編碼CS21CS25OP1OP2OPN基因組CS11CS12CS13CSNkCSN1具體服務交叉(crossover)算子是標準的兩點交叉，而變異(m

44、utation)算子隨機地選擇一個抽象服務(即基因組中一個位置)，并且隨機地用另一個可利用具體服務取代對應的具體服務。顯然，能從GA進化中獲得僅有一個具體服務可利用的抽象服務。選擇(selection)算子采用經(jīng)典的輪盤賭(roulette wheel)選擇法。其中，若某個個體i，其適應度為Fitness(i)，則被選中的概率Pi為。算法還在新一代個體產(chǎn)生之后采用最佳個體保存方法(elitist model)，即如果新一代群體中適應度最高的個體適應度小于老一代最佳個體，而把老一代最佳個體保存入新一代。接下來的問題是設計一個適應度(fitness)函數(shù)。適應度函數(shù)需要使一些QoS屬性(如可靠性)

45、最大化，而其它一些屬性(例如費用)最小化。當使用用戶定義的領(lǐng)域特定的QoS 屬性時，適應度函數(shù)規(guī)約留給工作流設計者。另外，適應度函數(shù)必須懲罰不滿足約束條件的個體，驅(qū)動進化有助于約束滿足。考慮到初始種群(設大小為m)滿足式(7)中約束條件，結(jié)合問題所采用的編碼和遺傳算子，滿足約束條件g0是顯然的。為此，可定義如下的一個約束滿足的罰函數(shù)： (8) 式(8)中系數(shù)yi為： 進而得到，包含一個罰函數(shù)的基因組g的適應度函數(shù)如下： (9)式(9)中r為罰函數(shù)尺度系數(shù)，r>0。最后，有必要定義GA的優(yōu)化準則。根據(jù)離線性能函數(shù)(off-line performance)： (10)其中T為當前計算中所出

46、現(xiàn)的遺傳代數(shù)，f(*,t)=maxf(1,t), f(2,t), f(m,t)，即第t代中的最佳個體適應值。該函數(shù)指標反映了群體中最佳個體適應值經(jīng)平滑處理后的變化情況，描述了個體的進化能力和GA的搜索能力，并最終趨向一個收斂值，所以可以用PF(T+1)-PF(T)作為終止循環(huán)的條件之一，文中取=1.0×10-5。為了防止群體規(guī)模太大，搜索精度要求太高，導致搜索時間過長，本文同時采用設定最大代數(shù)的方法作為另一個終止循環(huán)條件。3.5 動態(tài)適應度函數(shù)定義在等式(9)中的適應函數(shù)對違反約束的個體包含了一個靜態(tài)懲罰。換句話說，每一代的懲罰是同樣的。通常，如果懲罰因子的權(quán)重r高，那么違反約束的個

47、體存在某種風險，但卻可能放棄了一個最為接近的好方案。作為替代，可以采用一個動態(tài)的懲罰，即懲罰的權(quán)重隨著代數(shù)而增加。在遺傳的早期世代，還可能需要考慮一些個體違反約束。經(jīng)過若干世代后，種群大體上應能滿足約束，進化余下的工作是如何改進適應度函數(shù)。動態(tài)適應度函數(shù)的定義如下： (11)這里t是當前代數(shù)，tMax是最大遺傳代數(shù)。3.6 適應度函數(shù)的拉伸方法遺傳算法在運行早期個體差異較大，當采用輪盤賭方式選擇時，后代產(chǎn)生個數(shù)與父個體適應度大小成正比，因此在早期容易使個別好的個體的后代充斥整個種群，造成早熟(premature)；在遺傳算法后期，適應度趨向一致，優(yōu)秀的個體在產(chǎn)生后代時，優(yōu)勢不明顯，從而使整個種

48、群進化停滯不前(stalling)。因此，對適應度適當?shù)乩?stretching)是必要的。本文借鑒模擬退火(simulated annealing)10思想，提出如下適應度拉伸方法： (12)其中，式中系數(shù)決定了復制的強制性，其值越小，復制的強制就越趨向于那些具有最大適應度的個體。實驗表明：當取0.951.05 之間時，所取得的性能最好，本文選取=1。4 原型系統(tǒng)的實現(xiàn)和仿真4.1 原型系統(tǒng)的實現(xiàn)為了驗證所提的查詢基礎(chǔ)結(jié)構(gòu)及其優(yōu)化模型, 我們從高端實現(xiàn)了一個服務查詢引擎(service query engine)，應用于我們開發(fā)的基于服務的企業(yè)資源計劃協(xié)同集成框架SEIFCW中，完成對特定

49、企業(yè)應用域的基本W(wǎng)eb服務構(gòu)件的組合查詢和優(yōu)化。如圖3所示，SEIFCW使用包含語義屬性的WSDL描述企業(yè)基本W(wǎng)eb服務，使用UDDI tModels廣播SLA中的QoS參數(shù)，并且在UDDI注冊中心注冊。UDDI注冊中心包含如下兩類：(1)基于Internet的全局UDDI企業(yè)注冊表(UBR), 實現(xiàn)公共UDDI注冊存儲的組織管理，例如企業(yè)信息門戶(PL)、電子商務(EC)和領(lǐng)導查詢系統(tǒng)(LQ)等；(2)私有UDDI注冊中心，企業(yè)內(nèi)部的基本業(yè)務功能Web服務在這里注冊，例如購銷存管理(BM)、總賬系統(tǒng)(FS)、人力資源管理(PM)、經(jīng)營管理(RM)、基礎(chǔ)定義(BD)和控制臺(CP)等。服務查詢

50、引擎(service query engine)，作為在SEIFCW中實現(xiàn)本文所提查詢方法的一個核心部分，包括如下組件：查詢優(yōu)化器(query optimizer)，查詢引擎的核心組件，它基于QoS、服務等級、匹配度并調(diào)用GA算法庫，以便確定最好的服務組合執(zhí)行計劃。發(fā)現(xiàn)中間件(discovery middleware)，使用了一種基于多Agent和語義驅(qū)動的Web服務有效發(fā)現(xiàn)和搜索平臺（MASWEM），可在適當配置后能自動訪問UDDI 注冊中心，發(fā)現(xiàn)經(jīng)過篩選處理后的企業(yè)基本W(wǎng)eb服務構(gòu)件的WSDL描述。一旦發(fā)現(xiàn)中間件返回一個服務, 查詢引擎通過SOAP綁定存根，并使用Apache SOAP A

51、PI調(diào)用它的操作。操作映射器(operation mapper)，通過與發(fā)現(xiàn)中間件交互分析WSDL及其組成部分的QoS文檔，決定服務執(zhí)行計劃中滿足QoS屬性約束的具體操作。監(jiān)視代理(monitoring agent)，監(jiān)控Web服務調(diào)用，它的目標是根據(jù)已交付的QoS對其行為作出評價。執(zhí)行引擎(execution engine)，在優(yōu)化器產(chǎn)生一個有效的服務執(zhí)行計劃后，通過SOAP調(diào)用實際的Web服務來行使組合服務執(zhí)行計劃。圖3 應用SEIFCW框架的Web服務查詢基礎(chǔ)結(jié)構(gòu)基于Web的查詢接口Web服務XML查詢組合服務流程規(guī)約UDDIUDDI服務注冊中心WS-QoS 本體 企業(yè)基本W(wǎng)eb服務PL

52、ECLQBMFSPMRMBDCP服務查詢引擎XML 查詢解析器查詢優(yōu)化器操作映射器等級 數(shù)據(jù)庫監(jiān)視代理發(fā)現(xiàn)中間件執(zhí)行引擎XML-QL 本體 服務調(diào)用(SOAP)GA 數(shù)據(jù)庫Web服務查詢的處理過程是：用戶通過可視化查詢接口，首先使用一種從XML文檔中抽取數(shù)據(jù)的查詢語言規(guī)范XQuery11構(gòu)造一個面向抽象服務關(guān)系庫的聯(lián)合查詢Q；然后XML查詢解析器(XML query resolver)搜索抽象操作的本體庫(XML-QL ontology)獲得對應的抽象操作集；最后查詢引擎根據(jù)這些抽象操作的Category和Function把它們與企業(yè)基本W(wǎng)eb服務的各種操作(符合任一個匹配度)相匹配，并負責S

53、EIFCW 中的Web服務的正確性和最優(yōu)化執(zhí)行。4.2 仿真和性能評價本節(jié)通過實驗分析所提模型的性能，包括：觀察適應度因子隨GA代數(shù)的進化；比較各種適應度函數(shù)(即具有靜態(tài)和動態(tài)約束懲罰以及拉伸)。GA的主要參數(shù)取值如下：每個抽象操作的服務提供者數(shù)為163，選擇機制采用輪盤賭選擇，保留2個最佳個體一直保持活躍整個世代，交叉概率Pc=0.7，變異概率Pm=0.05，最大迭代數(shù)tMAX=100，種群大小pSize=50，搜索精度=1.0×10-5，復制的強制性系數(shù)=1，匹配度md=1。圖4 最大適應度值的進化過程此外，在適應度函數(shù)中，對不同QoS屬性賦予均等的權(quán)值，對某些案例場景的研究最終

54、還要禁用一些屬性。對每次實驗，GA 被執(zhí)行50次，報道的是平均值。標準偏差總是控制在平均值的5% 之下。為了比較不同的適應度函數(shù)，這里提出的結(jié)論來自優(yōu)化一個由包含9個截然不同抽象服務的12個原子操作調(diào)用構(gòu)成的工作流，其圈復雜度(cyclomatic complexity)等于10?；蚪M的二進制編碼長度是72。圖4和圖5分別從不同的角度，給出了三個不同適應度函數(shù)的查詢服務的QoS參數(shù)總體演化過程。圖4采用當前群體發(fā)現(xiàn)的最佳可行解的改善情況指標，即式(10)中的f(*,t)來反映GA搜索到全局最優(yōu)解的過程、速度和早熟等情況，這里考慮 GA用于函數(shù)優(yōu)化的目的是發(fā)現(xiàn)問題的全局最優(yōu)解。圖5使用式(10

55、)的離線性能反映群體中最佳個體適應值經(jīng)平滑處理后的變化情況，描述了個體的進化能力和GA的搜索能力。進化顯示三個不同的適應度函數(shù)都能使GA是找到滿足約束的解，同時，使全局的QoS參數(shù)總體最優(yōu)化。圖5離線性能的進化過程對本案例的優(yōu)化問題，動態(tài)適應度并不比靜態(tài)適應度強，甚至適應度權(quán)重的不同刻度對優(yōu)化也不提供幫助。除了動態(tài)適應度的啟動快以及獲得結(jié)果的最終進化不同，顯著性水平(significance level) = 5%的t-檢驗表明差別并不是很大。但通過對動態(tài)適應度作適當?shù)睦?，獲得最優(yōu)解的波動性、迭代代數(shù)和收斂時間等性能有明顯提高。實驗在不同規(guī)模工作流、復雜性重復做，基本上確認上述結(jié)論。5 相關(guān)

56、工作由于面向服務集成環(huán)境中應用之間的資源競爭，如何基于QoS約束能快速地發(fā)現(xiàn)、選擇并組合成最能滿足用戶需求的服務，已成為面向服務軟件工程中的一個感興趣話題1,6。動態(tài)服務發(fā)現(xiàn)和QoS感知組合的優(yōu)化模型的約束處理方法主要來自運籌學或人工智能的搜索策略。事實上，在面向服務體系結(jié)構(gòu)中，約束集是用來表達搜索或監(jiān)控服務的功能性和非功能性屬性，且該服務可能根據(jù)一些QoS優(yōu)化標準被選擇。更多的挑戰(zhàn)是組合服務的情況，它的結(jié)構(gòu)被抽象流程描述，即包含抽象服務的流程，目標是從QoS觀點動態(tài)地找到最好的具體服務組合。由于Web服務環(huán)境的動態(tài)特性，這種組合可能在執(zhí)行過程中隨時改變，因此，一個重要的需求是一個可行的并符合

57、SLA方案在短期內(nèi)應該被發(fā)現(xiàn)。文獻8設計了一個用于語義Web服務的QoS描述的本體，并提供了一個QoS度量定義模型。文獻12提出了一種有效的、動態(tài)的、QoS感知的Web服務選擇和監(jiān)控方法，但沒有解釋優(yōu)化問題怎樣能被解決。文獻13設計了一種基于服務質(zhì)量的Web服務描述語言QWSDL，并提出了一種前提條件是服務提供者發(fā)布的廣告描述是真實可信的匹配模型。服務發(fā)現(xiàn)問題轉(zhuǎn)化為請求描述與廣告描述之間的匹配問題。文獻14提出了一種服務質(zhì)量計算模型，并通過增加QoS注冊中心支持了基于QoS的Web服務選擇。服務注冊中心根據(jù)反饋信息對QoS排序，同時對QoS屬性進行規(guī)范化處理。不過在對QoS進行規(guī)范化處理時沒有考慮用戶的個性化需求。文獻15認為質(zhì)量驅(qū)動的Web服務組合選擇可歸結(jié)為優(yōu)化問題，并能使用有效的線性規(guī)劃方法解決。文獻16提出一種用于QoS感知的選擇Web服務的遺傳算法。與已有的研究工作相比，本文提