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

1、計算機(jī)學(xué)報2009年 5期動態(tài)的QoS感知Web服務(wù)選擇和組合優(yōu)化模型*蔣哲遠(yuǎn) 韓江洪 王釗(合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院 合肥 230009)摘 要 Web服務(wù)軟件工程的實用化挑戰(zhàn)之一是QoS感知的選擇、組合和稍后的綁定，表現(xiàn)為允許在運行時綁定一組領(lǐng)域Web服務(wù)構(gòu)成面向服務(wù)的系統(tǒng)。這些領(lǐng)域Web服務(wù)在提供要求的功能同時，還滿足一些非功能約束，例如總的費用或響應(yīng)時間，并且使之最優(yōu)化。提出了一種把Web服務(wù)看作為首類構(gòu)件對象的關(guān)系查詢基礎(chǔ)結(jié)構(gòu)，它通過各種Web服務(wù)操作調(diào)用評估查詢。由于個性化和效率在這種評估中起重要作用，提出了一個基于聚合不同Web服務(wù)的多屬性QoS參數(shù)的查詢優(yōu)化模型，該模型通過

2、用戶設(shè)定的全局約束和偏好、一個動態(tài)的等級方案、以及多級匹配來調(diào)整QoS。等級提供了一個Web服務(wù)的行為評估，而多級匹配通過使能類似的和部分的答案對解決方案的空間進(jìn)行擴(kuò)展。給出了模型求解的遺傳算法，并從適應(yīng)度函數(shù)的靜態(tài)懲罰、動態(tài)懲罰以及拉伸三個方面對優(yōu)化性能進(jìn)行了比較。該文最后介紹了一個從高端實現(xiàn)的服務(wù)查詢引擎原型系統(tǒng), 用以展示該方法的適應(yīng)性、可行性和有效性。 關(guān)鍵詞 Web服務(wù); 服務(wù)質(zhì)量; 服務(wù)選擇; 約束優(yōu)化; 遺傳算法中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：AAn Optimization Model for Dynamic QoS-Aware Web Services Selection

3、 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 QoSaware selection, composition and late-binding. This allows y

4、ou 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 response time. This paper presents a query infrastructure that

5、 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 query optimization model based on aggregating the multi-attrib

6、ute 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. Multilevel matching provides the expansion of the solution space

7、 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, dynamic penalty, and stretching. The proposed approach has b

8、een 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 algorithm* 基金項目：本課題得到國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2002AA415280)、教育部博士點基金項目(2005

9、0359004)、教育部新世紀(jì)優(yōu)秀人才計劃項目(NCET-04-050562)、合肥工業(yè)大學(xué)科學(xué)研究發(fā)展基金項目(2007GDBJ012)資助.作者簡介: 蔣哲遠(yuǎn),男,1966年生,博士,副研究員,主要研究領(lǐng)域為面向服務(wù)軟件工程、軟件體系結(jié)構(gòu)和軟件工程環(huán)境. jzheyuan. 韓江洪,男,1954年生,教授,博士生導(dǎo)師,主要研究領(lǐng)域為智能控制技術(shù)和分布式系統(tǒng). 王釗,男,1958年生,副教授,主要研究領(lǐng)域為電子商務(wù)和軟件工程.通信地址：安徽省合肥市屯溪路193號 合肥工業(yè)大學(xué)微機(jī)所13信箱郵政編碼：230009電 話：(0551)2902075, (0-mail:

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

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

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

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

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

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

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

17、際的Web服務(wù)。查詢層(query layer)：由提供給用戶一個表達(dá)和提交查詢語句到Web服務(wù)接口的關(guān)系集組成，可使用一種從XML文檔中抽取數(shù)據(jù)的查詢語言規(guī)范XQuery來構(gòu)造。用戶從查詢層提交關(guān)系聯(lián)合查詢(關(guān)系和條件的聯(lián)合)，其通用形式如下：Q(X):-Ri(Xi),Ck ik其中，符號:-表示映射，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)系映射到對應(yīng)的抽象操作中。3

18、圖1 QoS感知服務(wù)查詢的三層體系結(jié)構(gòu)抽象層(abstract layer)：由一個特定領(lǐng)域典型地提供的類Web服務(wù)操作組成的，可采用基于XML的WSDL對包含其操作的服務(wù)接口進(jìn)行描述。標(biāo)準(zhǔn)WSDL不提供對QoS支持，需要對WSDL進(jìn)行擴(kuò)展，以便能使WSDL恰當(dāng)?shù)靥峁㏎oS信息。例如，通過擴(kuò)展WSDL提供一個服務(wù)提供者和請求者之間的Web服務(wù)SLA文檔引用，可使WSDL的每個操作和一個由Web服務(wù)SLA定義的QoS相關(guān)聯(lián)，其格式為：QoS是一個屬性集，它的每一個屬性, 例如領(lǐng)域(domain)、尺度(scale)和量制(metrics)等需要根據(jù)具體應(yīng)用場景來精確定義。這些QoS屬性的抽象集都

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

20、換定義。定義1。 假設(shè)抽象服務(wù)接口I的QoS集定義為如下的一個屬性Pi集：QI = P1，Pn。其中，對每個PiQI ，1in 都有一個領(lǐng)域dom(Pi)和尺度scale(Pi)的度量值。當(dāng)然，屬性被度量或賦值的前提條件是首先定義好每個屬性的量制metric(Pi)。此外，假設(shè)dom(QI)= dom(P)。那么，一個接口I到一個QoS等級為LS的具體服務(wù)SI的映射定義如下：PQI:QIdom(QI)|(PQI)(P)dom(P)式中符號是條件連接詞，符號的右邊謂詞邏輯規(guī)定了映射需滿足的約束。2.2 關(guān)系到抽象操作的映射查詢層的關(guān)系定義了應(yīng)用域一個具體的視圖，可表達(dá)為針對抽象操作的連接查詢，似

21、乎抽象操作就是關(guān)系。定義2。 假設(shè)R是查詢層定義的關(guān)系集合，V是抽象操作集合，則對任何關(guān)系RiR,Rj(x1,x2, ,xn):-Vj(yjj1,yj2, ,yjm)式中xi是Ri的屬性，VjV，yji是相應(yīng)操作的輸入和輸出變量。這個定義意味著為了獲得Ri的元組，需要調(diào)用不同的操作Vj，但并不要求對這些操做任何的排序或限制并發(fā)。用戶能直接地使用抽象操作訪問Web服務(wù)，但關(guān)系的使用有兩個好處。首先，讓用戶使用一個自然的方式表達(dá)和提交類似數(shù)據(jù)庫的查詢；另一方面，為對服務(wù)空間一些特定部分感興趣的某個特定用戶組提供了量身定制的視圖。2.3 抽象操作表示抽象操作代表了一個特定應(yīng)用域所能提供的典型功能。對

22、在查詢中出現(xiàn)的任何抽象操作，最終都要定位到相關(guān)的Web服務(wù)操作，因此抽象操作需要有一個語義描述和句法屬性，同時還要有描述具體Web服務(wù)和抽象操作的一個共同的本體(ontology)8。任何一個操作，無論是抽象的還是具體的，語義上都可以通過它的功能(function)和類別(category)來描述。功能包含兩個屬性：功能性(functionality)，代表該操作所提供的業(yè)務(wù)功能；術(shù)語(term)，包含該操作的一個可替代功能性命名術(shù)語列表。類別同樣也包含兩個屬性：領(lǐng)域(domain)，給出操作的具體應(yīng)用領(lǐng)域；術(shù)語，抽取出與具體應(yīng)用領(lǐng)域類似的領(lǐng)域分類術(shù)語詞表。任何一個操作在調(diào)用前都要求它的輸入變

23、量被賦值。在構(gòu)造查詢時，用戶可為不同的變量自由地指定任意類型的條件。 這可能導(dǎo)致一種情形，就是系統(tǒng)不能調(diào)用操作，這是由于一些輸入變量遺漏了賦值。如果所有的抽象操作描述都給出了其輸入變量的各種可能值，上述問題就會解決(盡管對所有的輸入變量不可能總是做到這一點)。本文擴(kuò)展每個輸入變量到所有可能取值，以便盡量滿足出現(xiàn)在查詢中任意一個條件。下面的五元組形式化地表達(dá)了每個抽象操作：Vop = 上式中，In是輸入變量的集合；Out是輸出變量的集合；Restriction是輸入變量的定義域，它由一組對偶(x, range)構(gòu)成的集合, 其中x是In中的枚舉變量，而range是x的所有可能值的集合；Categ

24、ory描述興趣域；Function描述業(yè)務(wù)功能。2.4 抽象操作的匹配類型由于Web服務(wù)提供者之間的競爭，必然在請求輸入、返回輸出和QoS等方面存在差異。例如，不同運輸服務(wù)提供者的運輸費用、快捷性和服務(wù)內(nèi)容等可能有所區(qū)別。這就意味著對某個給定的抽象操作并不總能找到一個精確的匹配。作為替代，僅查找與聯(lián)合查詢中出現(xiàn)的抽象操作精確匹配的具體操作，一個允許抽象操作和具體操作的屬性不一致的更靈活的匹配方案可能更滿足用戶的需求。首先定義一個相似函數(shù)Similarity來檢查兩個操作中的兩個屬性是否相似：如果x和y 符合應(yīng)用域本體庫所定義的相似概念，那么Similarity (x, y)就為真。定義3(操作

25、的輸入變量集相等)。 對任意的兩個操作op1和op2，In(op1)=In(op2)，當(dāng)且僅當(dāng)： In(op1)和In(op2)變量數(shù)相同，且 xIn(op1),yIn(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有相

26、同的輸入和輸出變量，以及相同的Category和Function，稱之為精確匹配Exact(v, c)；如果兩個操作v和c有同樣的輸入和輸出變量，且它們的Category和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可知，精確匹配要求具體

27、操作與抽象操作的每個屬性概念都相同，這是最高級別的匹配；重疊匹配提供抽象操作的相近功能的具體操作；部分匹配符合兩個操作的輸入和輸出屬性不一致的情形；部分和重疊匹配組合了重疊匹配和部分匹配，并且各種匹配存在如下關(guān)系。命題1。“=” 表示蘊(yùn)含關(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)，以此直接

28、地影響查詢結(jié)果的質(zhì)量。上述每個匹配類型分別獲得1、3/4、1/2 和1/4的匹配度。該取值是任意指定的，主要是為了區(qū)分不同的匹配精確度。3 基于遺傳算法的Web服務(wù)查詢優(yōu)化方法描述由于存在不同Web 服務(wù)的幾個服務(wù)執(zhí)行計劃能潛在地解決相同的查詢。因此，需要為在所有可能的執(zhí)行規(guī)劃中挑選最優(yōu)的Web 服務(wù)建立適當(dāng)?shù)臉?biāo)準(zhǔn)。相互競爭的Web 服務(wù)之間的一個關(guān)鍵特色是他們的QoS，它包含幾個定量的和定性的參數(shù)，該參數(shù)度量了Web 服務(wù)所發(fā)布的功能是否好。現(xiàn)在已經(jīng)建立了描述響應(yīng)時間(time)、服務(wù)費用(cost)、可用性(availability)和可靠性(reliability) 的通用QoS 規(guī)格4

29、。對于領(lǐng)域具體QoS 規(guī)格要根據(jù)具體領(lǐng)域進(jìn)行定義，本文利用可擴(kuò)展本體技術(shù)建立起來了領(lǐng)域內(nèi)專門的QoS 規(guī)格。通常，每個Web服務(wù)都包含一組操作，調(diào)用的最小粒度為操作(operation)。Web 服務(wù)ws的操作op的QoS 定義如下：QoS(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

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

31、(t)表示操作的平均修復(fù)時間。MTTF(t)MTTF(t)+MTTR(t)，其中MTTF(t)表示操作的平均無故障時可用性(A)：代表一個Web服務(wù)正常運行的概率。取值越大意味著有較高的可用性，而較小的取值表示可用性低。由于Web服務(wù)是按次進(jìn)行調(diào)用的，可以采用離散時間模型來描述其可用性：n(t)iA(t)=limi=1nn，其中(t)i定義如下：(t)i=1，如果第i次操作返回成功0，否則結(jié)果用戶定義(U)：服務(wù)消費者定義的領(lǐng)域QoS規(guī)格，如聲譽(yù)(reputation)、安全性(security)和互操作性(interoperability)等。 優(yōu)化的目標(biāo)是使負(fù)向參數(shù)(如反應(yīng)時間和費用)減少

32、到最小值，同時使正向參數(shù)(如可用性和可靠性)取得最大值。正如引言所描述的那樣，本工作的一個目標(biāo)是基于GA的方法，能迅速地確定綁定到抽象服務(wù)的一個具體服務(wù)集，構(gòu)成一個組合服務(wù)的工作流。其中的需求包括：滿足基于SLA的QoS約束。例如，服務(wù)的用戶可能有一個有限的預(yù)算，因此服務(wù)費用受到一定的約束，或者響應(yīng)時間不能超過某個約定。時常，局部限制(例如，特定操作的費用不能超過限制)和全局限制(例如，總的響應(yīng)時間受約束)需要同時被滿足；使一些特別的QoS 參數(shù)的某個函數(shù)最優(yōu)化。例如，用戶可能想使響應(yīng)時間最段，同時保持費用低于某個限制。 隨之而來，還應(yīng)該考慮由N個抽象服務(wù)(操作)構(gòu)成的一個組合服務(wù)S=ws1，

33、ws2，wsN，其結(jié)構(gòu)通過一些工作流描述語言來定義。每個元素wsi能被綁定到M個具體服務(wù)csi1，csiM，它們在功能上是等價的。在描述使用GA找到最優(yōu)化問題的解之前，還需要描述怎樣計算一個組合服務(wù)的QoS，這要從從元服務(wù)的QoS屬性值計算開始。3.1 計算組合服務(wù)的QoS計算組合服務(wù)的QoS方法類似文獻(xiàn)4提出的方法，工作流的描述語言限定為BPEL4WS。對工作流中的一個Switch構(gòu)造，每個Case語句被標(biāo)注為可能的選擇。例如，對一個包含Switch的工作流，它由兩個Case語句組成，費用分別是C1和C2且出現(xiàn)的概率為p和1 p，則總的費用計算公式如下：pC1 + (1-p)C2顯然，概率是

34、由工作流設(shè)計者初始指定，最終還需要通過監(jiān)測工作流執(zhí)行所獲得的信息加以更新。While不同于文獻(xiàn)4的Loop處理，主要地建議采納一個到達(dá)Switch構(gòu)造的機(jī)制(基于進(jìn)入/退出While的概率)。我們的方法類似文獻(xiàn)6所采用的方法。例如，While被標(biāo)記為一個估計的迭代數(shù)k。代替展開的While，這里的While的 QoS計算考慮迭代因子k。例如，假如While復(fù)合體有一個代價Cl，那么While的估計代價將是kCl。這種處理While方法有兩個優(yōu)勢：能迅速計算總的工作流QoS，而不必展開While；被估計的QoS反映了While的迭代數(shù)。表1 計算單個工作流構(gòu)造的QoS屬性的聚集函數(shù)QoS 屬性

35、T(t)SequencemnSwitch FlowMaxT(ti)|i1,2, ,pWhilek*T(t)T(ti)i=1mi=1npai*T(ti) pai*C(ti) pai*A(ti) pai*R(ti)pC(t)C(ti)i=1mi=1nC(ti)i=1pk*C(t)A(t)i=1mA(ti) R(ti)i=1ni=1pA(ti)A(t) R(t) fL(k,U(t)kkR(t)i=1i=1R(ti)i=1U(t)fs(U(ti)i1,2, ,mfB(pai,U(ti)i1,2, ,nfF(U(ti)i1,2, ,p表1顯示了單個工作流構(gòu)造的QoS屬性的聚合函數(shù)。一個組合服務(wù)的具體應(yīng)用

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

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

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

39、下：DQoS(op)=i(dQi(op)-ipospQi(op)+i(dQ1(op)inegi-1pQi(op) (1)Web服務(wù)等級用下面公式來刻畫：1，DQoS(op)+-q(DQoS(op)-+)1+e (2)式(2)中的負(fù)閥值和正閥值+分別稱為置信下限和置信上限；q為調(diào)整QoS距離波動參數(shù)，通常取值為1。公式表明：如果一個Web 服務(wù)的QoS距離滿足SLA所規(guī)定的QoS參數(shù)波動區(qū)間(,+)，那么它接收正常的等級1；如果一個Web 服務(wù)的QoS距離低于負(fù)閥值, 那么它的等級將減少；如果一個Web 服務(wù)的QoS距離高于正閥值+, 那么它的等級將增加。一個簡單的Web服務(wù)等級把所有的QoS

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

41、rating)和匹配度(md)進(jìn)一步細(xì)化了服務(wù)功能發(fā)布成功的定義。因此，我們能通過下面三個度量，即期望的QoS參數(shù)、等級和匹配度，來刻畫解決一個查詢所涉及的任何Web服務(wù)操作。已存在計算一個基于它的QoS參數(shù)的操作總體質(zhì)量的各種方法。在決策過程中廣泛地使用的簡單添加權(quán)重方法通常取得了非常接近更為復(fù)雜的方法取得的排序結(jié)果。該方法包括以下三個基本步驟，操作質(zhì)量是最后一步獲得的數(shù)值之和。對L個不同的QoS參數(shù)標(biāo)準(zhǔn)化，以便使它們可比較。L為參與查詢的每一個QoS參數(shù)施加用戶指定的權(quán)重i，并且滿足i0，i=1i=1為每一個操作添加經(jīng)過加權(quán)和標(biāo)準(zhǔn)化處理后的QoS參數(shù)。為解析一個查詢過程中的每個抽象操作op

42、j(對應(yīng)匹配的具體服務(wù)數(shù)組項目索引)，只要定義一個取最大值的目標(biāo)函數(shù)fj(opj)： fj(opj)=rating(opj)*md(opj)*(iNi(opj)+iPi(opj) (3)inegipos式中pQimax(opj)-pQi(opj)maxmin，如果pQi(opj)-pQi(opj)0maxminpQi(opj)-pQi(opj)Ni(opj)=1，否則 (4)7 pQi(opj)-pQimin(opj)maxmin，如果pQi-pQi0maxminpQi(opj)-pQi(opj)Pi(opj)=1，否則 (5)其中pQimax(opj)是匹配相同抽象操作opj的所有具體操作中

43、第i個QoS參數(shù)的最大值，而pQimin(opj)是其最小值。對目標(biāo)fj(opj)(j=1，2，N)正規(guī)化處理，設(shè)fjmax(opj)和fjmin(opj)分別為目標(biāo)fj(opj)的最大值和最小值，線性正規(guī)化后的目標(biāo)值vj(opj)為：vj(opj)=fj(opj)-ffjmaxminj(opj)(opj)(opj)-fminj (6)N若j是操作opj其權(quán)重，并滿足 j0,ji=1而ci(g)是聯(lián)合查詢的約束條件，可由算法直接從查詢中獲得(等式條件)，=1，或者從抽象操作定義的范圍獲得(不等式條件)，則查詢過程的可行解向量g=(op1，op2，opN)是下列多目標(biāo)優(yōu)化問題的解：Nmax F(

44、g)=jvj(opj)j=1s.t.ci(g)0,i=1,2, ,K (7)g03.4 使用遺傳算法的搜索策略GA本質(zhì)上是一個通過群體的迭代來不斷優(yōu)化的過程10。它簡單、通用, 對問題的種類有很強(qiáng)的魯棒性，很適合解決NP問題。與線性整數(shù)規(guī)劃不同，GA對優(yōu)化問題的目標(biāo)函數(shù)和約束條件的線性化不施加限制，從而允許優(yōu)化模型使用各種可能的QoS屬性(甚至定制)。為了讓GA找到問題的一個解，首先需要使用一個合適的基因組給問題編碼。在本文中，基因組使用了一個整數(shù)數(shù)組來表示，數(shù)組中的項目數(shù)為組成我們服務(wù)的抽象服務(wù)數(shù)，數(shù)組中的每個元素依次包含一個與抽象服務(wù)相匹配的具體服務(wù)數(shù)組項目索引。圖2NkCSCSCSN1

45、具體服務(wù)基因組OP1 OP2 OPN圖2 基因組編碼交叉(crossover)算子是標(biāo)準(zhǔn)的兩點交叉，而變異(mutation)算子隨機(jī)地選擇一個抽象服務(wù)(即基因組中一個位置)，并且隨機(jī)地用另一個可利用具體服務(wù)取代對應(yīng)的具體服務(wù)。顯然，能從GA進(jìn)化中獲得僅有一個具體服務(wù)可利用的抽象服務(wù)。選擇(selection)算子采用經(jīng)典的輪盤賭(roulette wheel)選擇法。其中，若某個個體i，其適應(yīng)度為Fitness(i)，則被選中的概率Pi為pi=Fitness(i)Fitnessi=1(i)。算法還在新一代個體產(chǎn)生之后采用最佳個體保存方法(elitist model)，即如果新一代群體中適應(yīng)度

46、最高的個體適應(yīng)度小于老一代最佳個體，而把老一代最佳個體保存入新一代。接下來的問題是設(shè)計一個適應(yīng)度(fitness)函數(shù)。適應(yīng)度函數(shù)需要使一些QoS屬性(如可靠性)最大化，而其它一些屬性(例如費用)最小化。當(dāng)使用用戶定義的領(lǐng)域特定的QoS 屬性時，適應(yīng)度函數(shù)規(guī)約留給工作流設(shè)計者。另外，適應(yīng)度函數(shù)必須懲罰不滿足約束條件的個體，驅(qū)動進(jìn)化有助于約束滿足。考慮到初始種群(設(shè)大小為m)滿足式(7)中約束條件，結(jié)合問題所采用的編碼和遺傳算子，滿足約束條件g0是顯然的。為此，可定義如下的一個約束滿足的罰函數(shù)：KH(g)=ci(g)*yi (8)i=1式(8)中系數(shù)yi為：yi=0,ci(g)o1,ci(g)0

47、。最后，有必要定義GA的優(yōu)化準(zhǔn)則。根據(jù)離線性能函數(shù)(off-line performance)：PF(T)=f(*,t)/T (10)t=1T其中T為當(dāng)前計算中所出現(xiàn)的遺傳代數(shù)，f(*,t)=maxf(1,t), f(2,t), f(m,t)，即第t代中的最佳個體適應(yīng)值。該函數(shù)指標(biāo)反映了群體中最佳個體適應(yīng)值經(jīng)平滑處理后的變化情況，描述了個體的進(jìn)化能力和GA的搜索能力，并最終趨向一個收斂值，所以可以用PF(T+1)-PF(T)作為終止循環(huán)的條件之一，文中取=1.010-5。為了防止群體規(guī)模太大，搜索精度要求太高，導(dǎo)致搜索時間過長，本文同時采用設(shè)定最大代數(shù)的方法作為另一個終止循環(huán)條件。3.5 動態(tài)

48、適應(yīng)度函數(shù)定義在等式(9)中的適應(yīng)函數(shù)對違反約束的個體包含了一個靜態(tài)懲罰。換句話說，每一代的懲罰是同樣的。通常，如果懲罰因子的權(quán)重r高，那么違反約束的個體存在某種風(fēng)險，但卻可能放棄了一個最為接近的好方案。作為替代，可以采用一個動態(tài)的懲罰，即懲罰的權(quán)重隨著代數(shù)而增加。在遺傳的早期世代，還可能需要考慮一些個體違反約束。經(jīng)過若干世代后，種群大體上應(yīng)能滿足約束，進(jìn)化余下的工作是如何改進(jìn)適應(yīng)度函數(shù)。動態(tài)適應(yīng)度函數(shù)的定義如下：Fit(g,t)=F(g)+rH(g)*ttMax (11)這里t是當(dāng)前代數(shù)，tMax是最大遺傳代數(shù)。3.6 適應(yīng)度函數(shù)的拉伸方法遺傳算法在運行早期個體差異較大，當(dāng)采用輪盤賭方式選擇

49、時，后代產(chǎn)生個數(shù)與父個體適應(yīng)度大小成正比，因此在早期容易使個別好的個體的后代充斥整個種群，造成早熟(premature)；在遺傳算法后期，適應(yīng)度趨向一致，優(yōu)秀的個體在產(chǎn)生后代時，優(yōu)勢不明顯，從而使整個種群進(jìn)化停滯不前(stalling)。因此，對適應(yīng)度適當(dāng)?shù)乩?stretching)是必要的。本文借鑒模擬退火(simulated annealing)10思想，提出如下適應(yīng)度拉伸方法：Fit=1e-(1-Fit(g,t),0 (12)其中，式中系數(shù)決定了復(fù)制的強(qiáng)制性，其值越小，復(fù)制的強(qiáng)制就越趨向于那些具有最大適應(yīng)度的個體。實驗表明：當(dāng)取0.951.05 之間時，所取得的性能最好，本文選取=1。

50、4 原型系統(tǒng)的實現(xiàn)和仿真4.1 原型系統(tǒng)的實現(xiàn)為了驗證所提的查詢基礎(chǔ)結(jié)構(gòu)及其優(yōu)化模型, 我們從高端實現(xiàn)了一個服務(wù)查詢引擎(service query engine)，應(yīng)用于我們開發(fā)的基于服務(wù)的企業(yè)資源計劃協(xié)同集成框架SEIFCW中，完成對特定企業(yè)應(yīng)用域的基本W(wǎng)eb服務(wù)構(gòu)件的組合查詢和優(yōu)化。如圖3所示，SEIFCW使用包含語義屬性的WSDL描述企業(yè)基本W(wǎng)eb服務(wù)，使用UDDI tModels廣播SLA中的QoS參數(shù)，并且在UDDI注冊中心注冊。UDDI注冊中心包含如下兩類：(1)基于Internet的全局UDDI企業(yè)注冊表(UBR), 實現(xiàn)公共UDDI注冊存儲的組織管理，例如企業(yè)信息門戶(PL)

51、、電子商務(wù)(EC)和領(lǐng)導(dǎo)查詢系統(tǒng)(LQ)等；(2)私有UDDI注冊中心，企業(yè)內(nèi)部的基本業(yè)務(wù)功能Web服務(wù)在這里注冊，例如購銷存管理(BM)、總賬系統(tǒng)(FS)、人力資源管理(PM)、經(jīng)營管理(RM)、基礎(chǔ)定義(BD)和控制臺(CP)等。服務(wù)查詢引擎(service query engine)，作為在SEIFCW中實現(xiàn)本文所提查詢方法的一個核心部分，包括如下組件：查詢優(yōu)化器(query optimizer)，查詢引擎的核心組件，它基于QoS、服務(wù)等級、匹配度并調(diào)用GA算法庫，以便確定最好的服務(wù)組合執(zhí)行計劃。發(fā)現(xiàn)中間件(discovery middleware)，使用了一種基于多Agent和語義驅(qū)動

52、的Web服務(wù)有效發(fā)現(xiàn)和搜索平臺（MASWEM），可在適當(dāng)配置后能自動訪問UDDI 注冊中心，發(fā)現(xiàn)經(jīng)過篩選處理后的企業(yè)基本W(wǎng)eb服務(wù)構(gòu)件的WSDL描述。一旦發(fā)現(xiàn)中間件返回一個服務(wù), 查詢引擎通過SOAP綁定存根，并使用Apache SOAP API調(diào)用它的操作。操作映射器(operation mapper)，通過與發(fā)現(xiàn)中間件交互分析WSDL及其組成部分的QoS文檔，決定服務(wù)執(zhí)行計劃中滿足QoS屬性約束的具體操作。監(jiān)視代理(monitoring agent)，監(jiān)控Web服務(wù)調(diào)用，它的目標(biāo)是根據(jù)已交付的QoS對其行為作出評價。執(zhí)行引擎(execution engine)，在優(yōu)化器產(chǎn)生一個有效的服務(wù)執(zhí)

53、行計劃后，通過SOAP調(diào)用實際的Web服務(wù)來行使組合服務(wù)執(zhí)行計劃。圖3 應(yīng)用SEIFCW框架的Web服務(wù)查詢基礎(chǔ)結(jié)構(gòu)Web服務(wù)查詢的處理過程是：用戶通過可視化查詢接口，首先使用一種從XML文檔中抽取數(shù)據(jù)的查詢語言規(guī)范XQuery11構(gòu)造一個面向抽象服務(wù)關(guān)系庫的聯(lián)合查詢Q；然后XML查詢解析器(XML query resolver)搜索抽象操作的本體庫(XML-QL ontology)獲得對應(yīng)的抽象操作集；最后查詢引擎根據(jù)這些抽象操作的Category和Function把它們與企業(yè)基本W(wǎng)eb服務(wù)的各種操作(符合任一個匹配度)相匹配，并負(fù)責(zé)SEIFCW 中的Web服務(wù)的正確性和最優(yōu)化執(zhí)行。 4.2

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

55、標(biāo)準(zhǔn)偏差總是控制在平均值的5% 之下。為了比較不同的適應(yīng)度函數(shù)，這里提出的結(jié)論來自優(yōu)化一個由包含9個截然不同抽象服務(wù)的12個原子操作調(diào)用構(gòu)成的工作流，其圈復(fù)雜度(cyclomatic complexity)等于10。基因組的二進(jìn)制編碼長度是72。圖4和圖5分別從不同的角度，給出了三個不同適應(yīng)度函數(shù)的查詢服務(wù)的QoS參數(shù)總體演化過程。圖4采用當(dāng)前群體發(fā)現(xiàn)的最佳可行解的改善情況指標(biāo)，即式(10)中的f(*,t)來反映GA搜索到全局最優(yōu)解的過程、速度和早熟等情況，這里考慮 GA用于函數(shù)優(yōu)化的目的是發(fā)現(xiàn)問題的全局最優(yōu)解。圖5使用式(10)的離線性能反映群體中最佳個體適應(yīng)值經(jīng)平滑處理后的變化情況，描述了

56、個體的進(jìn)化能力和GA的搜索能力。進(jìn)化顯示三個不同的適應(yīng)度函數(shù)都能使GA是找到滿足約束的解，同時，使全局的QoS參數(shù)總體最優(yōu)化。圖5 離線性能的進(jìn)化過程對本案例的優(yōu)化問題，動態(tài)適應(yīng)度并不比靜態(tài)適應(yīng)度強(qiáng)，甚至適應(yīng)度權(quán)重的不同刻度對優(yōu)化也不提供幫助。除了動態(tài)適應(yīng)度的啟動快以及獲得結(jié)果的最終進(jìn)化不同，顯著性水平(significance level) = 5%的t-檢驗表明差別并不是很大。但通過對動態(tài)適應(yīng)度作適當(dāng)?shù)睦?，獲得最優(yōu)解的波動性、迭代代數(shù)和收斂時間等性能有明顯提高。實驗在不同規(guī)模工作流、復(fù)雜性重復(fù)做，基本上確認(rèn)上述結(jié)論。5 相關(guān)工作由于面向服務(wù)集成環(huán)境中應(yīng)用之間的資源競爭，如何基于QoS約束能快速地發(fā)現(xiàn)、選擇并組合成最能滿足用戶需求的服務(wù)，已成為面向服務(wù)軟件工程中的一個感興趣話題1,6。動態(tài)服務(wù)發(fā)現(xiàn)和QoS