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

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

2、用戶設(shè)定的全局約束和偏好、一個(gè)動(dòng)態(tài)的等級(jí)方案、以及多級(jí)匹配來(lái)調(diào)整QoS。等級(jí)提供了一個(gè)Web服務(wù)的行為評(píng)估，而多級(jí)匹配通過(guò)使能類似的和部分的答案對(duì)解決方案的空間進(jìn)行擴(kuò)展。給出了模型求解的遺傳算法，并從適應(yīng)度函數(shù)的靜態(tài)懲罰、動(dòng)態(tài)懲罰以及拉伸三個(gè)方面對(duì)優(yōu)化性能進(jìn)行了比較。該文最后介紹了一個(gè)從高端實(shí)現(xiàn)的服務(wù)查詢引擎原型系統(tǒng), 用以展示該方法的適應(yīng)性、可行性和有效性。 關(guān)鍵詞 Web服務(wù); 服務(wù)質(zhì)量; 服務(wù)選擇; 約束優(yōu)化; 遺傳算法中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：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* 基金項(xiàng)目：本課題得到國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2002AA415280)、教育部博士點(diǎn)基金項(xiàng)目(2005

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

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

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

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

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

14、之間的快速綁定，且使實(shí)際的Web服務(wù)滿足SLA規(guī)定的QoS約束，并使服務(wù)集成者所選擇的一些適應(yīng)度標(biāo)準(zhǔn)最優(yōu)化(例如，費(fèi)用最小)。另外，求解QoS感知組合問(wèn)題的解是一個(gè)NP難題5。一些方法，主要是基于線性規(guī)劃, 已經(jīng)在一些文獻(xiàn)中提出6。為此，本文提出了一種新穎的服務(wù)查詢和優(yōu)化模型用于保障SEIFCW應(yīng)用的QoS感知的服務(wù)組合，并用遺傳算法(Genetic Algorithm，GA)來(lái)解決QoS感知的組合問(wèn)題。所提模型的主要特點(diǎn)是：使用關(guān)系表達(dá)查詢請(qǐng)求；領(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é)模型，并使用遺傳算法對(duì)其目標(biāo)進(jìn)行求解；小節(jié)4給出模型在SEIFCW中的實(shí)現(xiàn)，并報(bào)告和討論了仿真的結(jié)果；小節(jié)5介紹一些相關(guān)工作，并和相關(guān)研究作比較；小節(jié)6是最后的結(jié)論，同時(shí)對(duì)未來(lái)的工作進(jìn)行展望。2 Web 服務(wù)的查詢模式Web服務(wù)的使用主要由通過(guò)發(fā)送和接收消息的一組調(diào)用操作組成。盡管這可滿足簡(jiǎn)單應(yīng)用的需求，但對(duì)訪問(wèn)千變?nèi)f化的Web服務(wù)的復(fù)雜應(yīng)用，需要使用一種集成方式去操作與交付Web服務(wù)的功能。此外，隨著Web服務(wù)的廣泛應(yīng)用，提供相同功能的服務(wù)越來(lái)越多。但由于競(jìng)爭(zhēng)，Web服務(wù)提供的這些功能(例如，要求不同的輸入和輸出參數(shù))

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

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

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

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

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

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

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

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

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

25、的輸入變量集相等)。 對(duì)任意的兩個(gè)操作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), 其中第一個(gè)集合是第二個(gè)集合的子集。假如v和c分別表示抽象操作和具體操作，通過(guò)改變抽象操作和實(shí)際操作的比較方式，可以識(shí)別出四種不同的匹配類型。定義4(抽象操作匹配類型)。 如果兩個(gè)操作v和c有相

26、同的輸入和輸出變量，以及相同的Category和Function，稱之為精確匹配Exact(v, c)；如果兩個(gè)操作v和c有同樣的輸入和輸出變量，且它們的Category和Function發(fā)生交疊，稱為重疊匹配overlap(v, c)；假如兩個(gè)操作v和c有同樣的Category 和Function, 且Out(c)Out(v)或者In(c)In(v)，稱為部分匹配partial(v, c)；如果兩個(gè)操作c和v滿足Out(c)Out(v)或者In(c)In(v)，且它們的Category和Function屬性交疊，稱為部分和重疊匹配composite(v, c)。由定義4可知，精確匹配要求具體

27、操作與抽象操作的每個(gè)屬性概念都相同，這是最高級(jí)別的匹配；重疊匹配提供抽象操作的相近功能的具體操作；部分匹配符合兩個(gè)操作的輸入和輸出屬性不一致的情形；部分和重疊匹配組合了重疊匹配和部分匹配，并且各種匹配存在如下關(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)。為了量化各種匹配類型的匹配精確度，還需要給每一個(gè)匹配類型賦予了一個(gè)匹配度(matching degree)，以此直接

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

29、。對(duì)于領(lǐng)域具體QoS 規(guī)格要根據(jù)具體領(lǐng)域進(jìn)行定義，本文利用可擴(kuò)展本體技術(shù)建立起來(lái)了領(lǐng)域內(nèi)專門的QoS 規(guī)格。通常，每個(gè)Web服務(wù)都包含一組操作，調(diào)用的最小粒度為操作(operation)。Web 服務(wù)ws的操作op的QoS 定義如下：QoS(ws, op) =, 其各參數(shù)的含義為：T(ws, op)表示執(zhí)行時(shí)間；C(ws, op)表示費(fèi)用；R(ws, op)表示可靠性；A(ws, op)表示可用性；U(ws, op)表示領(lǐng)域QoS規(guī)格，定義為：(U1(ws, op), U2(ws, op) , , Un(ws, op)，即n個(gè)用戶定義的屬性組成的向量。為便于QoS模型的建立和求解，把某個(gè)Web

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

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

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

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

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

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

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

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

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

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

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

42、j(對(duì)應(yīng)匹配的具體服務(wù)數(shù)組項(xiàng)目索引)，只要定義一個(gè)取最大值的目標(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個(gè)QoS參數(shù)的最大值，而pQimin(opj)是其最小值。對(duì)目標(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，或者從抽象操作定義的范圍獲得(不等式條件)，則查詢過(guò)程的可行解向量g=(op1，op2，opN)是下列多目標(biāo)優(yōu)化問(wèn)題的解：Nmax F(

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

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

46、最高的個(gè)體適應(yīng)度小于老一代最佳個(gè)體，而把老一代最佳個(gè)體保存入新一代。接下來(lái)的問(wèn)題是設(shè)計(jì)一個(gè)適應(yīng)度(fitness)函數(shù)。適應(yīng)度函數(shù)需要使一些QoS屬性(如可靠性)最大化，而其它一些屬性(例如費(fèi)用)最小化。當(dāng)使用用戶定義的領(lǐng)域特定的QoS 屬性時(shí)，適應(yīng)度函數(shù)規(guī)約留給工作流設(shè)計(jì)者。另外，適應(yīng)度函數(shù)必須懲罰不滿足約束條件的個(gè)體，驅(qū)動(dòng)進(jìn)化有助于約束滿足?？紤]到初始種群(設(shè)大小為m)滿足式(7)中約束條件，結(jié)合問(wèn)題所采用的編碼和遺傳算子，滿足約束條件g0是顯然的。為此，可定義如下的一個(gè)約束滿足的罰函數(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)前計(jì)算中所出現(xiàn)的遺傳代數(shù)，f(*,t)=maxf(1,t), f(2,t), f(m,t)，即第t代中的最佳個(gè)體適應(yīng)值。該函數(shù)指標(biāo)反映了群體中最佳個(gè)體適應(yīng)值經(jīng)平滑處理后的變化情況，描述了個(gè)體的進(jìn)化能力和GA的搜索能力，并最終趨向一個(gè)收斂值，所以可以用PF(T+1)-PF(T)作為終止循環(huán)的條件之一，文中取=1.010-5。為了防止群體規(guī)模太大，搜索精度要求太高，導(dǎo)致搜索時(shí)間過(guò)長(zhǎng)，本文同時(shí)采用設(shè)定最大代數(shù)的方法作為另一個(gè)終止循環(huán)條件。3.5 動(dòng)態(tài)

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

49、時(shí)，后代產(chǎn)生個(gè)數(shù)與父?jìng)€(gè)體適應(yīng)度大小成正比，因此在早期容易使個(gè)別好的個(gè)體的后代充斥整個(gè)種群，造成早熟(premature)；在遺傳算法后期，適應(yīng)度趨向一致，優(yōu)秀的個(gè)體在產(chǎn)生后代時(shí)，優(yōu)勢(shì)不明顯，從而使整個(gè)種群進(jìn)化停滯不前(stalling)。因此，對(duì)適應(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)度的個(gè)體。實(shí)驗(yàn)表明：當(dāng)取0.951.05 之間時(shí)，所取得的性能最好，本文選取=1。

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

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

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

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

54、 仿真和性能評(píng)價(jià)本節(jié)通過(guò)實(shí)驗(yàn)分析所提模型的性能，包括：觀察適應(yīng)度因子隨GA代數(shù)的進(jìn)化；比較各種適應(yīng)度函數(shù)(即具有靜態(tài)和動(dòng)態(tài)約束懲罰以及拉伸)。GA的主要參數(shù)取值如下：每個(gè)抽象操作的服務(wù)提供者數(shù)為163，選擇機(jī)制采用輪盤賭選擇，保留2個(gè)最佳個(gè)體一直保持活躍整個(gè)世代，交叉概率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)化過(guò)程此外，在適應(yīng)度函數(shù)中，對(duì)不同QoS屬性賦予均等的權(quán)值，對(duì)某些案例場(chǎng)景的研究最終還要禁用一些屬性。對(duì)每次實(shí)驗(yàn)，GA 被執(zhí)行50次，報(bào)道的是平均值。

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

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