支持跨組織協(xié)作服務(wù)的組合研究報告(共28頁).doc

1、目錄第1章緒論11.1研究背景11.2研究意義11.3研究內(nèi)容和組織結(jié)構(gòu)2第2章服務(wù)組合及其支撐技術(shù)研究綜述4服務(wù)組合定義4組合服務(wù)研究問題框架5基于QoS的服務(wù)選擇6第3章多網(wǎng)絡(luò)域環(huán)境下組合服務(wù)的QoS模型優(yōu)化83.1問題分析83.2相關(guān)工作93.3問題建模11第4章基于遺傳算法的QoS策略構(gòu)建154.1遺傳算法簡介154.2混合啟發(fā)式遺傳修補算子遺傳算法154.3算法執(zhí)行過程20第5章實驗仿真與結(jié)果分析215.1優(yōu)化效果測試225.2算法收斂性測試23第6章結(jié)束語24第1章緒論1.1研究背景當今競爭激烈的商業(yè)社會，要求企業(yè)對瞬息萬變的市場需求做出迅速的響應(yīng)，企業(yè)需要不斷地調(diào)整自身業(yè)務(wù)，拓展

2、業(yè)務(wù)范圍，傳統(tǒng)的開發(fā)一交付升級的軟件開發(fā)模式己顯得日漸落后，如何實現(xiàn)企業(yè)應(yīng)用系統(tǒng)“隨需應(yīng)變”成為了當今軟件產(chǎn)業(yè)的焦點問題。同時，隨著企業(yè)間的兼并，收購以及企業(yè)全球化發(fā)展，各分支機構(gòu)的應(yīng)用系統(tǒng)需要安全、有效地整合，以提高效率，降低成本。這些需求使得企業(yè)對于提高應(yīng)用系統(tǒng)的構(gòu)建效率，加強企業(yè)內(nèi)部及企業(yè)之間業(yè)務(wù)合作、信息共享以及系統(tǒng)集成的需求也越發(fā)迫切。無論是從技術(shù)發(fā)展還是企業(yè)的實際需求上來說，對軟件的開發(fā)模式、交付方式和軟件形態(tài)都提出了新的要求，軟件應(yīng)用環(huán)境從封閉、靜態(tài)向開放、動態(tài)轉(zhuǎn)變;信息共享和應(yīng)用集成需求從單一系統(tǒng)向異構(gòu)平臺擴展，從單一企業(yè)整合內(nèi)部向跨多個企業(yè)的業(yè)務(wù)合作延伸，需要一種新的計算泛型

3、來指導軟件產(chǎn)業(yè)的發(fā)展。1.2研究意義Web服務(wù)，或者說面向服務(wù)的應(yīng)用，最吸引人的地方在于服務(wù)可以組件化地在不同系統(tǒng)中復用，不同的服務(wù)可以被組合起來完成原有服務(wù)所不能實現(xiàn)的功能，以達到增值的目的。基于組合的Web服務(wù)技術(shù)能夠包容電子商務(wù)，企業(yè)應(yīng)用集成，傳統(tǒng)的中間件以及Web技術(shù)。它為企業(yè)提供許多好處：l)將遺留系統(tǒng)的功能轉(zhuǎn)換為可復用的、自包含、自描述的服務(wù)的標準方法。這些轉(zhuǎn)換而來的服務(wù)能夠以一種標準的、可管理的方式與其他服務(wù)進行交互。2) 方便靈活地進行應(yīng)用集成的標準方式。通過這種方式，可將實現(xiàn)應(yīng)用功能的己測試過的、可信的、可互操作的模塊快速裝配成新的應(yīng)用。3) 開發(fā)、裝配純粹的互聯(lián)網(wǎng)應(yīng)用的標準

4、方法。這些應(yīng)用既可以應(yīng)用于企業(yè)內(nèi)部，也可以用于跨企業(yè)協(xié)作。該方法可將內(nèi)部或外部創(chuàng)建的服務(wù)作為構(gòu)件，并將這些構(gòu)件裝配到應(yīng)用中。1.3研究內(nèi)容和組織結(jié)構(gòu)基于Web服務(wù)的應(yīng)用并不是一件簡單的工作，要使其正確、安全而又高效地為企業(yè)服務(wù)，則需要一整套Web服務(wù)組合及其相關(guān)技術(shù)作為支撐。根據(jù)組合服務(wù)的生命周期，服務(wù)組合的研究框架所覆蓋的問題劃分為兩大類：服務(wù)組合構(gòu)建問題和服務(wù)組合運行支撐問題。前者主要包含了組合服務(wù)計劃生成，服務(wù)發(fā)現(xiàn)和選擇、以及服務(wù)組合等問題;后者則包含了組合服務(wù)的執(zhí)行和協(xié)同、性能監(jiān)控和保障、服務(wù)組合的安全和事務(wù)管理以及容錯等問題。當前，針對服務(wù)構(gòu)建問題，已經(jīng)有了相當多的理論成果和實際工業(yè)

5、平臺。然而在實際應(yīng)用中，要真正完全享受基于服務(wù)組合的業(yè)務(wù)協(xié)作所帶來的好處，在組合服務(wù)運行支撐階段，尚有相當多的問題未得到解決，這也是制約SOA與Web服務(wù)進一步普及和發(fā)展的重要原因。本文主要關(guān)注的組合服務(wù)支撐問題為組合服務(wù)性能優(yōu)化軟件應(yīng)用的性能是企業(yè)最為關(guān)注的一個話題。與傳統(tǒng)軟件基于單機的進程間通信或者基于高速企業(yè)總線的遠程過程調(diào)用相比，Web服務(wù)基于SOAP消息的機器到機器通信所帶來的額外開銷，使得基于服務(wù)的軟件應(yīng)用的性能成為一個廣受垢病的問題。在基于公共網(wǎng)絡(luò)的跨企業(yè)組合服務(wù)中，組件服務(wù)之間的數(shù)據(jù)及控制依賴，會在運行時產(chǎn)生大量的跨域消息傳輸。由于各網(wǎng)絡(luò)域間地理位置、網(wǎng)絡(luò)位置的分布以及安全策略

6、的部署，為跨域服務(wù)組合造成額外的執(zhí)行成本，從而對組合服務(wù)性能帶來難以忽視的影響。本文的研究工作以Internet環(huán)境下跨企業(yè)的業(yè)務(wù)協(xié)作和集成為背景，針對目前組合服務(wù)部分支撐技術(shù)所存在不足，圍繞著組合服務(wù)流程兼容性驗證，服務(wù)訪問控制、以及性能優(yōu)化等幾個方面展開研究。第二章對本文的研究基礎(chǔ)進行了綜述。首先簡要介紹了組合服務(wù)的基本概念和研究方法以及當前國內(nèi)外著名的組合服務(wù)研究項目和平臺。隨后詳細地討論了服務(wù)組合及其相關(guān)的支撐技術(shù)，對服務(wù)組合模型和方法、服務(wù)組合安全性、服務(wù)組合性能優(yōu)化的相關(guān)工作進行了綜述。第五章提出了組合服務(wù)分布式協(xié)調(diào)環(huán)境下，面向組合服務(wù)性能優(yōu)化的服務(wù)部署策略。本章以組合服務(wù)分布式執(zhí)

7、行為討論基礎(chǔ)，以服務(wù)執(zhí)行成本作為組合服務(wù)性能優(yōu)化指標，通過分析后指出網(wǎng)絡(luò)傳輸成本優(yōu)化是服務(wù)執(zhí)行成本優(yōu)化的一個有效途徑。提出了服務(wù)間交互強度的概念，并試圖通過對企業(yè)內(nèi)服務(wù)部署區(qū)間的調(diào)整，來達到降低服務(wù)執(zhí)行成本的目的。通過將服務(wù)可部署區(qū)域的作為限制條件，將問題轉(zhuǎn)化為多約束條件的下的最優(yōu)化問題。隨后提出了一個基于遺傳算法建模方法對這一優(yōu)化問題進行求解，將基因中的每個染色體表示為部署區(qū)間可變的服務(wù)，而染色體的值則代表這一服務(wù)的部署位置。為了解決經(jīng)過交叉和變異之后基因不符合約束條件，提出了一種混合啟發(fā)式修補算子對基因進行修補。第六章總結(jié)了全文工作，并對未來的研究方向和內(nèi)容進行了展望。第2章服務(wù)組合及其支

8、撐技術(shù)研究綜述Web服務(wù)組合是一個龐大的系統(tǒng)工程，基于Web服務(wù)構(gòu)建應(yīng)用系統(tǒng)并不是一件簡單的工作。尤其是對于跨越多個不同企業(yè)邊界、基于公共網(wǎng)絡(luò)的企業(yè)間業(yè)務(wù)協(xié)作來說，要使其正確、安全而又高效地為企業(yè)服務(wù)，則需要一整套Web服務(wù)組合及其相關(guān)技術(shù)作為支撐。2.1.1服務(wù)組合定義本文對服務(wù)組合的定義：服務(wù)組合是根據(jù)用戶提出的需求(包含功能需求以及非功能需求)，在服務(wù)組合的支撐環(huán)境下，從現(xiàn)有的Web服務(wù)中，選擇一系列符合需求的單個服務(wù)，并按規(guī)則構(gòu)建為服務(wù)流程，通過流程執(zhí)行過程中服務(wù)間的互相協(xié)作來最終滿足用戶的需求。通常將組合后的服務(wù)流程稱為組合服務(wù)，而組合服務(wù)中所涉及的單個服務(wù)稱為組件服務(wù)。Web服務(wù)組

9、合主要具備以下幾個特點：遞歸性。組合服務(wù)是通過重用和組裝現(xiàn)有的服務(wù)來生成更大粒度的服務(wù)，而生成的服務(wù)又可以作為基本服務(wù)被重用。動態(tài)性。服務(wù)組合是一個動態(tài)的/按需組裝0的過程。隨著需求的變化或者組件服務(wù)本身的變化，組合服務(wù)可以在運行時實現(xiàn)服務(wù)替換和重組。高效性。服務(wù)組合對Web服務(wù)的重用和組裝，改變了原有的軟件生產(chǎn)方式，極大地提高了軟件的生產(chǎn)效率。2.1.2組合服務(wù)研究問題框架圖2.1簡要展示了組合服務(wù)的生命周期，本文將服務(wù)組合的研究框架所覆蓋的問題劃分為兩大類：服務(wù)組合構(gòu)建問題和服務(wù)組合運行支撐問題。前者主要包含了組合服務(wù)計劃生成，服務(wù)發(fā)現(xiàn)和選擇、以及服務(wù)組合等問題;后者則包含了組合服務(wù)的執(zhí)行

10、和協(xié)同、性能監(jiān)控和保障、服務(wù)組合的安全和事務(wù)管理以及容錯等問題。2.4.1基于QoS的服務(wù)選擇Qos是服務(wù)質(zhì)量(Quality of Service)的縮寫，它指的是服務(wù)所能提供的一種質(zhì)量保證，保證服務(wù)能響應(yīng)預期的請求，并能以符合期望的質(zhì)量來完成相應(yīng)的任務(wù)。QoS不是單一性能指標，而是一個多屬性復合指標，綜合文獻55115碩57等的定義，web服務(wù)最主要的Qos屬性有：響應(yīng)時間，價格，可靠性，聲望，等。這些指標對于保持服務(wù)的競爭力與業(yè)務(wù)可行性具有非常重要的影響，因此Qos已經(jīng)成為了衡量服務(wù)性能與效用的重要標準。組合服務(wù)流程執(zhí)行通常采用運行時綁定的策略，即在流程制定時只為每個活動定義需完成的任務(wù)

11、，而不指定具體由哪一個服務(wù)來實現(xiàn)，常常將活動稱作抽象服務(wù)。在開放的網(wǎng)絡(luò)環(huán)境下，每個抽象服務(wù)往往存在多個實際服務(wù)均可完成相同的任務(wù)。這些服務(wù)可以看作這一抽象服務(wù)的候選服務(wù)，它們從功能上看是可以互相替換的，但是往往具備不同的QoS屬性。組合服務(wù)用戶會從自身需求出發(fā)對組合服務(wù)提出一個總體的QoS期望，因此如何在執(zhí)行時根據(jù)候選服務(wù)的QoS屬性為抽象服務(wù)選取合適的組件服務(wù)成為了組合服務(wù)性能優(yōu)化中的一個主要問題，近年來成為了Web服務(wù)研究領(lǐng)域所關(guān)注的焦點問題之一。在獲得了組合服務(wù)的Qos計算方法之后，則可以用戶提出的Qos期望和限制作為約束條件，基于約束滿足方法為組合服務(wù)中的每個活動選取最合適的候選服務(wù)。

12、假設(shè)組合服務(wù)中具有n個抽象服務(wù)，每個抽象服務(wù)具有m個候選服務(wù)，則共有mn種組合方案可供選擇，從其中選擇最優(yōu)解是一個NP難問題57，因此研究人員引入了各種方法來獲得局部或全局優(yōu)化解。第3章多網(wǎng)絡(luò)域環(huán)境下組合服務(wù)的QoS模型優(yōu)化3.1問題分析為了更好地對問題進行描述，首先提出一個概念，稱為組合服務(wù)執(zhí)行成本(Execution Cost，ExCost)。組合服務(wù)的執(zhí)行成本由組合服務(wù)中的組件服務(wù)執(zhí)行成本與服務(wù)間的數(shù)據(jù)傳輸成本共同構(gòu)成，其中a和p代表兩者分別所占據(jù)的權(quán)重。顯然，執(zhí)行成本越高則代表組合服務(wù)的性能越差。對于組合服務(wù)來說，組件服務(wù)的執(zhí)行成本是不可避免的，為了簡化問題，此處將忽略執(zhí)行成本，只考慮

13、數(shù)據(jù)傳輸成本，從而有。而數(shù)據(jù)傳輸成本則是由服務(wù)間的數(shù)據(jù)傳輸量和數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)成本構(gòu)成。由于在組合服務(wù)分布式執(zhí)行中，數(shù)據(jù)是在組件服務(wù)之間直接傳輸?shù)?，因此公?5一l)可以改寫成：其中，有序?qū)?si，sj)表示組合服務(wù)中組件服務(wù)sj到組件服務(wù)sj的數(shù)據(jù)傳輸，而(Dsi，Dsj)則表示51所在的網(wǎng)絡(luò)域和sj所在的網(wǎng)絡(luò)域之間的數(shù)據(jù)傳輸成本。仍以圖5.2(b)中的組合服務(wù)為例，假設(shè)組合引擎，服務(wù)l，2，3所在的網(wǎng)絡(luò)域分別為DO，DI，D：和D3，根據(jù)公式5一2，其執(zhí)行成本可以展開為：網(wǎng)絡(luò)域之間的網(wǎng)絡(luò)傳輸成本受到許多因素的影響，不同網(wǎng)絡(luò)域間的網(wǎng)絡(luò)狀況，例如鏈接速度、帶寬、通訊費用、地理距離等常常是各不相同

14、的。通常來說，通過公共網(wǎng)絡(luò)進行數(shù)據(jù)傳輸，顯然要比在同一子網(wǎng)內(nèi)傳輸成本要高;而從紐約到北京數(shù)據(jù)傳輸成本要比從紐約到波士頓的成本要高。在服務(wù)間的數(shù)據(jù)傳輸無法避免的情況下，優(yōu)化網(wǎng)絡(luò)傳輸成本，成為了執(zhí)行成本優(yōu)化的一種主要方式。3.2相關(guān)工作當前面向組合服務(wù)性能優(yōu)化的方法里，較少考慮了網(wǎng)絡(luò)傳輸成本。正如在2.4.1小節(jié)中所綜述的，在大多數(shù)基于QoS組合服務(wù)優(yōu)化研究中，對組合服務(wù)的響應(yīng)時間屬性，只是籠統(tǒng)地以服務(wù)本身的響應(yīng)時間進行聚合，如表2.1所示。而在面向服務(wù)覆蓋網(wǎng)的執(zhí)行路徑選擇中，則簡單地以最小跳數(shù)為優(yōu)化目標，并未考慮到節(jié)點之間的網(wǎng)絡(luò)屬性。本文作者所在的研究小組在對Internet環(huán)境下跨多域組合服務(wù)

15、的Qos模型進行研究時，考慮了組合服務(wù)引擎所處的位置對組合服務(wù)性能的影響。文章以經(jīng)典的基于QoS的服務(wù)選擇問題為背景，服務(wù)組合集中式執(zhí)行，每個組件服務(wù)存在多個候選服務(wù)，位于不同的網(wǎng)絡(luò)域中。與其他研究有所不同的是，文章假設(shè)存在多個組合服務(wù)引擎可供選擇，在動態(tài)運行時，從服務(wù)分布和組合服務(wù)引擎位置兩個方向同時考慮，選擇位置相近的服務(wù)引擎和組件服務(wù)，充分利用引擎與組件服務(wù)在同一網(wǎng)絡(luò)域內(nèi)傳輸成本較低這一特性，提高組合服務(wù)的總體QoS。Kang等人則從組合服務(wù)分布式執(zhí)行出發(fā)，由于分布式執(zhí)行環(huán)境下，組合服務(wù)間數(shù)據(jù)傳輸是直接進行的，因此文章提出一種服務(wù)間數(shù)據(jù)依賴分析方法，對組合服務(wù)中組件服務(wù)之間的數(shù)據(jù)依賴進行

16、建模。在服務(wù)選擇時，盡量從同一個網(wǎng)絡(luò)域內(nèi)選擇那些相互之間數(shù)據(jù)依賴較強的服務(wù)，從而降低組合服務(wù)的跨域數(shù)據(jù)傳輸。與以上這些面向Internet環(huán)境下即時求解型組合服務(wù).5有所不同，面向企業(yè)協(xié)作的流程驅(qū)動型組合服務(wù)主要具備如下幾個特點：(l)服務(wù)組合的結(jié)構(gòu)比較穩(wěn)定，一旦業(yè)務(wù)協(xié)作的流程被確定下來，這些流程會比較穩(wěn)定地運行較長的時間。(2)每個組件服務(wù)只有少數(shù)幾個甚至只有固定一個實例。對于這一類組合服務(wù)，顯然其性能優(yōu)化方法應(yīng)當有所不同。針對這一環(huán)境，Chaflel20提出跨域組合服務(wù)數(shù)據(jù)最優(yōu)化路由的方法，文章通過分析組合服務(wù)的結(jié)構(gòu)，枚舉了其所有可行的數(shù)據(jù)流拓撲線路，并選擇性能最優(yōu)的線路來執(zhí)行組合服務(wù)。在

17、運行時，系統(tǒng)動態(tài)監(jiān)控所有網(wǎng)絡(luò)域之間的網(wǎng)絡(luò)帶寬狀況，并評估其在組合服務(wù)各種不同的拓撲結(jié)構(gòu)下對性能的影響。一旦當前的拓撲結(jié)構(gòu)無法滿足SLA時，接下來的服務(wù)請求將會被切換到新的拓撲結(jié)構(gòu)，同時不會影響己經(jīng)在執(zhí)行的流程。然而，當前較少有工作通過服務(wù)的部署策略來進行性能優(yōu)化。研究了基于Internet的企業(yè)內(nèi)部應(yīng)用中，面向組合的服務(wù)初始化部署問題，文章假設(shè)一個服務(wù)可以有多個實例部署于內(nèi)網(wǎng)的不同節(jié)點中，從負載均衡，網(wǎng)絡(luò)流量以及副本部署規(guī)模等多個方面對服務(wù)部署進行約束，并提出了一個近似最優(yōu)的服務(wù)部署算法。3.3問題建模對于管理著多個網(wǎng)絡(luò)域的大型企業(yè)來說，其組件服務(wù)被不屬于不同的網(wǎng)絡(luò)中，本文試圖從服務(wù)部署方面著

18、手，將依賴關(guān)系較強的服務(wù)部署到同一個網(wǎng)絡(luò)域中，以此來優(yōu)化網(wǎng)絡(luò)傳輸成本。圖5.3簡要刻畫了這樣一個跨多網(wǎng)絡(luò)域服務(wù)組合基礎(chǔ)框架。在基于云的基礎(chǔ)設(shè)施和虛擬化技術(shù)的支撐下，運行在云平臺上的服務(wù)在不同數(shù)據(jù)中心之間遷移并不存在技術(shù)上的困難。顯然，一種最為直接的方式顯然是將所有的組件服務(wù)都部署進同一個網(wǎng)絡(luò)域中，但是在實際環(huán)境中，服務(wù)部署區(qū)域存在諸多限制，其中主要的有.安全性限制：這一限制在對數(shù)據(jù)安全較高的領(lǐng)域，如軍事、金融等領(lǐng)域比較常見。不同的服務(wù)所涉及的業(yè)務(wù)和數(shù)據(jù)的安全性是不同的，高機密性的服務(wù)需要被部署在安全性更高的網(wǎng)絡(luò)域或子網(wǎng)中。.業(yè)務(wù)和地域限制：-不同的服務(wù)根據(jù)所涉及的業(yè)務(wù)類型會被要求部署在不同的區(qū)

19、域內(nèi)，例如大型跨國企業(yè)中，處理歐洲業(yè)務(wù)的服務(wù)顯然不應(yīng)該被部署在位于亞洲的網(wǎng)絡(luò)域中。同時，商業(yè)伙伴所提供的服務(wù)是總是在企業(yè)外部的。企業(yè)內(nèi)部服務(wù)中那些與外部服務(wù)有較強數(shù)據(jù)交互的服務(wù)，應(yīng)當被部署到與其間數(shù)據(jù)交互成本較低的域內(nèi)。.資源限制：每個服務(wù)均代表一類資源的請求。例如CPU，內(nèi)存，其他軟件和硬件設(shè)備。在服務(wù)運行時，一些資源會被占用，而一個單域內(nèi)的資源總是有限的。將所有服務(wù)部署在同一個域內(nèi)會面對嚴重的性能問題。因此，基于服務(wù)部署的網(wǎng)絡(luò)傳輸成本優(yōu)化問題最終轉(zhuǎn)化為一個多限制條件下的最優(yōu)化問題。為了對問題進行表達，首先對相關(guān)概念進行定義。定義：網(wǎng)絡(luò)域(NetworkDomains，ND)為網(wǎng)絡(luò)域的集合，

20、m為網(wǎng)絡(luò)域的個數(shù)。是內(nèi)部網(wǎng)絡(luò)域的集合，所謂內(nèi)部網(wǎng)絡(luò)域是由企業(yè)自身所控制的網(wǎng)絡(luò)域，對于大型跨國企業(yè)來說，它的網(wǎng)絡(luò)域地理上可能位于世界上多個不同的地方。相應(yīng)地是不由企業(yè)控制的網(wǎng)絡(luò)域，例如業(yè)務(wù)伙伴提供的服務(wù)所在的網(wǎng)絡(luò)域。這里的內(nèi)部和外部既是地理概念，又是邏輯概念。企業(yè)和業(yè)務(wù)伙伴完全可能在使用一個數(shù)據(jù)中心，但是邏輯上兩者仍然是位于不同的安全子網(wǎng)內(nèi)。以屬性C表示網(wǎng)絡(luò)域的資源容量。定義：組件服務(wù)(eomPonentservice)為企業(yè)內(nèi)的組件服務(wù)，N是組件服務(wù)的總數(shù)量。定義屬性為組件服務(wù)的類型，。從企業(yè)本身的角度來講，服務(wù)被分為兩種類型：內(nèi)部服務(wù)和外部服務(wù)。內(nèi)部服務(wù)由企業(yè)本身所完全控制，其中包括服務(wù)的升

21、級，更新，維護以及部署等。而外部服務(wù)則由業(yè)務(wù)伙伴所提供，僅能通過標準的操作方式來查詢和調(diào)用。以Ds(s)來表示服務(wù)S可部署的網(wǎng)絡(luò)區(qū)間，根據(jù)前述的分析，企業(yè)內(nèi)部服務(wù)在多個限制條件下，可以部署在一個或多個內(nèi)部網(wǎng)絡(luò)域中。而由合作伙伴提供的外部服務(wù)則只能固定在某個外部網(wǎng)絡(luò)域中。定義：服務(wù)資源需求屬性時為服務(wù)51的資源需求。服務(wù)資源請求是由服務(wù)在運行時所需占用資源來表示。事實上這個指標是由多種環(huán)境資源的抽象而成，例如CPU占用，內(nèi)存占用，等等。假設(shè)有k個組件服務(wù)部署于域Di中，則其所有的資源消耗不能超過域的總?cè)萘?，即：定義：網(wǎng)絡(luò)傳輸成本(Network Cost)本文將網(wǎng)絡(luò)域之間的傳輸成本抽象為一個單一

22、的參數(shù)，稱為網(wǎng)絡(luò)成本。由矩陣。其中代表域Di和Dj之間的網(wǎng)絡(luò)成本。假設(shè)同一個網(wǎng)絡(luò)域中網(wǎng)絡(luò)成本可以被忽略不計，則有些壑龍廳，。定義：組合服務(wù)一個組合服務(wù)S由一組組件服務(wù)構(gòu)成，他們聚合在一起實現(xiàn)跨企業(yè)的業(yè)務(wù)流程。為企業(yè)內(nèi)所有的組合服務(wù)，t為組合服務(wù)的總數(shù)量。每個組件服務(wù)都可以被多個組合服務(wù)中所共享。pi是組合服務(wù)S;在企業(yè)中重要程度的衡量指標，這一指標可以由管理員人工指定，也可以由組合服務(wù)的歷史運行情況所決定。通過這一指標即可表示出5.2.1小節(jié)中提出的服務(wù)優(yōu)先級問題。定義：服務(wù)間依賴強度(Interaction Dependency)定義矩陣為組合服務(wù)Sk中的服務(wù)間依賴矩陣。為服務(wù)si和服務(wù)sj

23、的之間依賴強度，如果si和sj不存在交互關(guān)系，則idij=o，顯然idii=0根據(jù)以上的定義，一個企業(yè)內(nèi)所有服務(wù)執(zhí)行成本ExCost可以通過以下公式計算得到定義：服務(wù)部署方案定義n維向量是服務(wù)部署方案，其中代表服務(wù)si部署在網(wǎng)絡(luò)域中至此，服務(wù)部署優(yōu)化的目標可以表達為，在公式(5一3)和(5一4)的限制下，調(diào)整服務(wù)部署位置DeP，從而最小化組合服務(wù)執(zhí)行成本ExCost。針對這一部署目標，本文提出了一個基于遺傳算法的最優(yōu)部署策略構(gòu)建方法，第4章基于遺傳算法的QoS策略構(gòu)建4.1遺傳算法簡介遺傳算法12z(genetic，algorithm，GA)是一種用來尋找精確最優(yōu)或者近似最優(yōu)解的搜索技術(shù)。它模

24、擬生物界的進化規(guī)律，用編碼染色體表示物種中的個體，通過非確定性遺傳算子(比如交叉和變異)對一組候選的解的群體進行計算，再選擇優(yōu)良的個體繼續(xù)生成下一代不斷迭代直到己經(jīng)超出定義的執(zhí)行最大代數(shù)或者有滿足要求的個體為止。4.2混合啟發(fā)式遺傳修補算子遺傳算法遺傳算法主要有基因編碼，適度函數(shù)定義，初始化種群，基因交叉與變異等關(guān)鍵步驟，本節(jié)將對這些步驟進行逐一介紹。1.1.1.1基因編碼本算法采用基于整數(shù)數(shù)組的基因組編碼方式，數(shù)組中的第n個元素的值代表第n個共享的原子服務(wù)所部署的區(qū)域(domain)的索引，每個基因(數(shù)組中的每個元素)取值范圍為2一m(共有m個區(qū)域可供每個服務(wù)部署)?；蚓幋a只關(guān)注那些部署區(qū)

25、域可變的服務(wù)，而部署區(qū)域不可變服務(wù)則無需編碼。則由于每個服務(wù)可部署的區(qū)域是不同的，因此其m值也是各不相同的。圖5.4展示這一編碼方式，每個基因組就代表了一種服務(wù)的部署結(jié)果。1.1.1.2適應(yīng)度函數(shù)適應(yīng)度函數(shù)用于衡量每一代群體中每個個體的質(zhì)量，也反映了所要優(yōu)化的目標函數(shù)，而最優(yōu)化部署的目標函數(shù)己經(jīng)在ExCost中給出。由于適應(yīng)度往往為正數(shù)且適應(yīng)度越大代表個體質(zhì)量越好，因此將優(yōu)化目標改為刀一Excost來作為本算法的適應(yīng)度函數(shù)，其中月足夠大以保證結(jié)果是正數(shù)。1.1.1.3遺傳算子當遺傳算法中的一個原始種群(組件服務(wù)的初始部署)產(chǎn)生后，采用基于輪盤賭的個體選擇策略在每一代中選擇個體來參與交叉和變異。

26、在這一策略中，個體按照適應(yīng)度函數(shù)來排序，適應(yīng)度大的個體被選擇的概率也大。算法中采用單點交叉和單點變異的方式實現(xiàn)交叉算子和變異算子，作用于選擇算子選擇出的個體。對于交叉操作，一對個體會基于單點交叉方法產(chǎn)生兩個后代。而變異操作則通過隨機選擇染色體中的基因并用另外一個滿足限制條件的基因進行替換。此外，優(yōu)異性保持策略使得上一代的中的最優(yōu)染色體可以得到保留。在本文的算法中，每一代中的最佳的兩個個體直接進入下一代。1.1.1.4混合啟發(fā)式修補算子然而，交叉和變異后的個體所對應(yīng)的服務(wù)部署方案往往會違背約束條件而變得無效。因此，本算法采用一個混合啟發(fā)式修補算子來確保個體的有效性。該算子可以快速地將無效個體做修

27、補同時保證每一代中個體的多樣性。這一混合的啟發(fā)式修補算子是一個啟發(fā)式修補過程和一個普通的修補過程的混合，在每次修補前，首先按照概率，隨機選擇啟發(fā)式修復過程(HRP)和正常修復過程(NRP)，稱為啟發(fā)因子。對于某個無效個體(服務(wù)部署結(jié)果矩陣Dep)的修補過程的算法如表5.1所示。啟發(fā)式的修補過程類似一個爬山優(yōu)化過程，修補算法中的每次迭代都向著最大化提高適應(yīng)值的方向來推進，因此，該修補過程有利于快速提高個體進化速率。此外，普通的修補過程有利于減少每次修補的時間和保持群體中個體的多樣性。因此，結(jié)合了啟發(fā)式修補過程和普通修補過程的混合啟發(fā)式修補算子綜合了兩者的優(yōu)勢，從而提高算法性能。1.1.1.5群體

28、多樣性保持策略為了保證遺傳算法的全局適應(yīng)值快速收斂同時避免局部最優(yōu)，在每一代需要有相應(yīng)的保持群體多樣性的相關(guān)策略。本章設(shè)計了基于信息墑l241的個體選擇策略來維持每個群體中個體的多樣性，該方法具體定義和實現(xiàn)如下：聯(lián)合信息嫡被定義為：，其中M代表每代群體中的基因組數(shù)目，代表其中第j個基因組的信息嫡。，其中Pij代表第i個基因符號出現(xiàn)在第j個基因位上的概率。群體相似度表示，當群體相似度大于某個閡值時，群體需要做自我更新，更新的步驟如下：(l)如果群體相似度大于某個閉值A(chǔ)，則生成P個新的基因組個體，否則群體更新完畢;(2)從上一代群體中的(M+P)個個體中選擇M個各不相同的適應(yīng)值最高的個體，和步驟一

29、中新生成的P個個體組成新的群體;(s)如果在步驟(2)中發(fā)現(xiàn)上一代群體中只存在N(N<M)個互不相同的個體，則首先新生成M一個個體來替換群體(M+P)個個體中適應(yīng)值最低的個體，然后再執(zhí)行步驟(2)，否則執(zhí)行步驟(l)。4.3算法執(zhí)行過程至此，本章提出的基于MHR一GA算法構(gòu)建最優(yōu)部署策略的過程可以總結(jié)如下：步驟1：隨機生成M，個初始種群，種群中每個個體代表一種部署方案，確保每個可部署服務(wù)都被指定到一個可部署網(wǎng)絡(luò)域中。步驟2：由于種群中的個體是隨機生成的，并未考慮到它是否滿足約束。因此先對初始種群應(yīng)用啟發(fā)式修補算子，使初始種群中的所有個體均可滿足限制條件。步驟3：從初始種群中基于輪盤賭策略

30、選擇M個個體作為第一代種群。步驟4：對于當前種群基于遺傳算子對種群實施交叉和變異操作。對交叉和變異后的種群個體實施啟發(fā)式修補。并對當前種群實施適應(yīng)度保持算子。步驟5：評估當前種群中的每個個體的適應(yīng)度。步驟6：如果己到達算法的結(jié)束條件(例如遺傳代數(shù)、每代之間結(jié)果變化小于閡值等)，返回當前具有最大適應(yīng)度的個體，其基因編碼即為最終部署策略。步驟7：從當前種群中選擇M個個體作為下一代種群，重新執(zhí)行步驟4。第5章實驗仿真與結(jié)果分析本節(jié)的仿真實驗，試圖通過隨機數(shù)據(jù)來模擬真實環(huán)境下的場景，從而對算法進行考察，其目的是為了驗證本章中多網(wǎng)絡(luò)域環(huán)境下基于遺傳算法的組件服務(wù)部署優(yōu)化策略的效果，同時也驗證算法本身的性

31、能。所有實驗結(jié)果均在一臺工作站上采集。工作站的配置Intel core2 Duo2.33GHz處理器，ZG內(nèi)存。軟件環(huán)境是WindowsXP，開發(fā)運行環(huán)境是JDKI.6_17。本章設(shè)計了一個模擬數(shù)據(jù)生成器來產(chǎn)生測試用例。程序主要有4個輸入?yún)?shù)：總的組件服務(wù)數(shù)目(TS)，總的網(wǎng)絡(luò)域數(shù)量(TD)，可部署網(wǎng)絡(luò)域數(shù)量(D)。對于其他參數(shù)，生成器會以合理的隨機分布來自動產(chǎn)生：.服務(wù)交互矩陣由給定上下限的高斯分布產(chǎn)生，保證有50%一70%的服務(wù)之間存在關(guān)聯(lián)關(guān)系。.每個服務(wù)的資源請求以及每個域的容量同樣由合理的隨機算法在給定的上下限中產(chǎn)生。5.1優(yōu)化效果測試算法優(yōu)化效果測試以多個不同數(shù)據(jù)集來模擬不同的場景，

32、通過對比優(yōu)化前和優(yōu)化后的網(wǎng)絡(luò)費用之間的差值，來驗證算法的優(yōu)化效果。共設(shè)計5組不同的輸入?yún)?shù)，作為5種不同的場景，如表5.2所示。在這一系列的實驗中，啟發(fā)因子林設(shè)定為30%，表示有30%的修復會采取啟發(fā)式，而70%的修復是普通修復。實驗的終止條件是連續(xù)1000代遺傳具有相同的適度值。算法產(chǎn)生100組隨機的部署策略作為初始染色體編碼。其中初始部署中的最佳策略(Ic)將用來和算法運行的最終結(jié)果做比較(oc)。優(yōu)化率由(Ic一OC)/Ic表示。算法總運行時間在最后一列中列出。表5.2的數(shù)據(jù)顯示了算法在各種不同的場景下均具有非常好的優(yōu)化效果，尤其在場景2下，降低總網(wǎng)絡(luò)成本比例超過了30%。這是由于在服務(wù)

33、個數(shù)較少的情況下，服務(wù)部署可以集中在少數(shù)幾個域中，從而極大地降低了跨域的網(wǎng)絡(luò)消耗。雖然場景1的服務(wù)個數(shù)更小，但是優(yōu)化效果較場景2比較不明顯，這是由于我們的初始化部署是隨機生成的，并經(jīng)過了修補算子進行修補，因而其初始結(jié)果即比較接近最優(yōu)結(jié)果。隨著服務(wù)數(shù)量的增加以及網(wǎng)絡(luò)域數(shù)量的增加，優(yōu)化效果逐漸降低，這種結(jié)果是可以理解的，因為組件服務(wù)的可部署區(qū)間是由多種因素所決定的，服務(wù)數(shù)量越多，則受限制的服務(wù)也越多，因此無法完全將服務(wù)藕合在少數(shù)的幾個網(wǎng)絡(luò)域中。然而與隨機生成的初始化部署相比，其優(yōu)化效果仍然比較明顯。最后一列顯示了在服務(wù)規(guī)模較小時，算法的運行時間是秒級，隨著組件服務(wù)數(shù)量及網(wǎng)絡(luò)域數(shù)量的增加而增加。由于

34、這是一個靜態(tài)的初始化部署優(yōu)化算法，它并不影響動態(tài)環(huán)境下組合服務(wù)的性能，因而這一算法運行時間是可接受的。5.2算法收斂性測試這一實驗主要評估不同的啟發(fā)因子對算法收斂速度的影響。采用上一節(jié)中場景2作為基準，同時將啟發(fā)因子分別調(diào)整為O%(無啟發(fā))，即普通的修補算法，100%(完全啟發(fā))。圖5.5中的橫軸表示遺傳算法的過程中的子代，縱軸表示總體的網(wǎng)絡(luò)費用。該實驗比較了3種啟發(fā)因子下前3000代的收斂速度。由圖中可以看出，較高的啟發(fā)因子可以獲得較快的收斂速度。同時，啟發(fā)式修補與非啟發(fā)是修補相比，可以獲得較優(yōu)的最終結(jié)果，證明了本章提出的基于啟發(fā)式修補的遺傳算法的有效性。然而，由于啟發(fā)修復的算法復雜度較高，因此其算法運行時間也比普通修復要長。3種啟發(fā)因子下的運行時間分別是10453ms(0%)，14890ms(30%)以及19750ms(1000%)。圖中顯示兩種不同的啟發(fā)因子下，雖然收斂速度上存在差異，但是最終結(jié)果差距比較小，因此，權(quán)衡算法運行時間與所獲得的優(yōu)化結(jié)果，中等的啟發(fā)因子是較好的選擇。第6章結(jié)束語隨著計算機技術(shù)以及網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，Internet己經(jīng)成為了企業(yè)之間協(xié)作以及企業(yè)向用戶提供服務(wù)的基礎(chǔ)平臺。面向服務(wù)的計算與面向服務(wù)的軟件架構(gòu)應(yīng)運而生，它有助于企業(yè)快速應(yīng)對業(yè)務(wù)需求變化，無縫、高效地對不同的系統(tǒng)進行銜接，實現(xiàn)跨企業(yè)的業(yè)務(wù)協(xié)作與集成?；诜?wù)組