張曉紅，黃繼海

(中州大學(xué) 信息工程學(xué)院，鄭州 450005)

1 引言

對(duì)于運(yùn)營(yíng)商而言，提供網(wǎng)絡(luò)服務(wù)的成本越來(lái)越高?？紤]到當(dāng)前網(wǎng)絡(luò)的復(fù)雜性，即使是針對(duì)突發(fā)需求而實(shí)施的簡(jiǎn)單升級(jí)，也可能需要數(shù)月甚至數(shù)年的時(shí)間才能完成。然而，在計(jì)算技術(shù)的進(jìn)步和IT 環(huán)境中虛擬技術(shù)成功的鼓舞下，網(wǎng)絡(luò)運(yùn)營(yíng)商正努力推動(dòng)類(lèi)似的技術(shù)，希望以此作為解決擴(kuò)展性問(wèn)題的一種辦法。網(wǎng)絡(luò)功能虛擬化(Network Function Virtualization，NFV)［1］便是此類(lèi)選擇中的一種。它利用標(biāo)準(zhǔn)的IT 虛擬化技術(shù)，將多種類(lèi)型的網(wǎng)絡(luò)設(shè)備合并到業(yè)界標(biāo)準(zhǔn)的高容量服務(wù)器、交換機(jī)和存儲(chǔ)設(shè)備中，并將其置于數(shù)據(jù)中心、網(wǎng)絡(luò)節(jié)點(diǎn)等地。

NFV 的重要技術(shù)支撐是服務(wù)功能鏈(Service Function Chain，SFC)的構(gòu)建。通過(guò)將特定的網(wǎng)絡(luò)服務(wù)抽象為一系列有序的報(bào)文處理功能實(shí)體，可以實(shí)現(xiàn)新網(wǎng)絡(luò)服務(wù)的靈活部署與服務(wù)隔離。然而，現(xiàn)有研究對(duì)NFV 中的SFC 構(gòu)建技術(shù)依然停留在資源分配［2－3］和標(biāo)準(zhǔn)建立［4－5］階段，無(wú)法實(shí)現(xiàn)SFC 的服務(wù)最優(yōu)組合。

在計(jì)算機(jī)網(wǎng)絡(luò)中，針對(duì)服務(wù)組合優(yōu)化問(wèn)題的研究主要集中在基于構(gòu)件的軟件工程(Component－Based Software Engineering，CBSE)和面向服務(wù)體系結(jié)構(gòu)(Service－Oriented Architecture，SOA)等領(lǐng)域。雖然一個(gè)抽象的服務(wù)功能對(duì)應(yīng)的所有具體服務(wù)實(shí)體在功能上是等價(jià)的，但在其他屬性上是存在差異的，所以可以根據(jù)非功能屬性進(jìn)行服務(wù)實(shí)體選擇和組合優(yōu)化。在不同領(lǐng)域，非功能屬性具有不同含義，基于這些屬性約束建立服務(wù)組合優(yōu)化模型并求解，已成為CBSE 和SOA 中的熱點(diǎn)問(wèn)題。比如QoS 感知［6］的Web Services 組合問(wèn)題的研究，文獻(xiàn)［7－8］針對(duì)順序、并發(fā)、分支、循環(huán)等4 種控制結(jié)構(gòu)的Web Services 組合模型，建立了包括費(fèi)用、響應(yīng)時(shí)間、信譽(yù)、可用性等參數(shù)的評(píng)價(jià)體系來(lái)評(píng)價(jià)組合的效果，并利用整數(shù)規(guī)劃方法從全局角度進(jìn)行最優(yōu)化求解。文獻(xiàn)［9－10］的研究思路與文獻(xiàn)［7－8］類(lèi)似，提出了遺傳算法來(lái)解決QoS 感知的Web Services 組合問(wèn)題。此外，文獻(xiàn)［11－13］以云計(jì)算系統(tǒng)為背景，建立基于QoS 的服務(wù)組合模型，并提出各種啟發(fā)算法。文獻(xiàn)［14］將信任概念和信任度引入到Web Services 組合中，分別基于信任感知和信任增強(qiáng)建立數(shù)學(xué)模型，并采用蟻群算法求解之。

上述研究主要針對(duì)Web Services 的組合優(yōu)化問(wèn)題，其考慮的QoS 屬性并不適用于NFV 體系，且忽略了屬性的匹配約束。為此，本文提出一種適合于NFV 架構(gòu)的服務(wù)實(shí)體性能模型，并根據(jù)服務(wù)實(shí)體間的性能匹配和資源總量約束，形式化分析服務(wù)組合優(yōu)化問(wèn)題;在求解過(guò)程中，為減輕大量無(wú)效解的干擾，提出了改進(jìn)的模擬退火算法SCM－SA，該算法包含基于層次屬性的產(chǎn)生函數(shù)和基于偏離度的目標(biāo)函數(shù)。

本文的后續(xù)部分組織如下:第2 節(jié)提出一種針對(duì)服務(wù)實(shí)體的性能模型，并在此基礎(chǔ)上分析基于性能的服務(wù)組合優(yōu)化問(wèn)題;第3 節(jié)提出改進(jìn)的模擬退火算法SCM－SA 及其相關(guān)函數(shù)設(shè)定;第4 節(jié)對(duì)提出的SCM－SA 算法進(jìn)行實(shí)驗(yàn)評(píng)估;第5 節(jié)為結(jié)束語(yǔ)。

2 問(wèn)題描述

2.1 服務(wù)功能鏈模型

定義1 服務(wù)拓?fù)?。在NFV 體系中，服務(wù)功能鏈可以抽象為服務(wù)拓?fù)銰c=(V，E，s，t)。其中，V 為服務(wù)功能集合，E 為服務(wù)間的連接關(guān)系，s 為該服務(wù)功能鏈的源節(jié)點(diǎn)，t 為該服務(wù)功能鏈末節(jié)點(diǎn)。

服務(wù)功能鏈的構(gòu)建過(guò)程分為兩步:服務(wù)拓?fù)溆成浜头?wù)組合優(yōu)化。對(duì)于第一步，我們通過(guò)虛擬網(wǎng)映射技術(shù)［2－3］，將服務(wù)拓?fù)淝度氲降讓泳W(wǎng)絡(luò)中，并為其分配節(jié)點(diǎn)資源和帶寬資源。對(duì)于第二步，我們需要描述服務(wù)組合的實(shí)體和約束條件。

定義2 服務(wù)實(shí)體。提供具體服務(wù)的功能實(shí)體稱(chēng)之為服務(wù)實(shí)體。每個(gè)服務(wù)對(duì)應(yīng)大量的服務(wù)實(shí)體，雖然它們的服務(wù)屬性相同，但是具有多樣化的性能參數(shù)，所以我們將服務(wù)i 的第j個(gè)服務(wù)實(shí)體抽象為

式中，Configin為服務(wù)實(shí)體的輸入性能矢量，Configout為服務(wù)實(shí)體的輸出性能矢量，Res 為服務(wù)實(shí)體運(yùn)行時(shí)所占用的系統(tǒng)資源矢量，k 為所考慮的資源類(lèi)型數(shù)，分別為第i個(gè)輸入性能屬性和輸出性能屬性，m 為所考慮的性能屬性個(gè)數(shù)。特別地，若為，則說(shuō)明服務(wù)實(shí)體不受該性能屬性的約束;若為，則說(shuō)明服務(wù)實(shí)體不對(duì)外提供該性能屬性的信息。

性能屬性是指服務(wù)實(shí)體在運(yùn)行時(shí)所需要的或表現(xiàn)出的某一性能方面的特性。例如某一報(bào)文分類(lèi)實(shí)體在運(yùn)行時(shí)輸入報(bào)文的到達(dá)速率需小于10 Gb/s，而輸出的分類(lèi)結(jié)果速率為125 Mb/s。

兩個(gè)同種類(lèi)型的性能屬性c1和c2進(jìn)行疊加，記為c1c2。根據(jù)性能屬性類(lèi)型不同，疊加符號(hào)對(duì)應(yīng)的數(shù)學(xué)運(yùn)算可以是交集運(yùn)算、并集運(yùn)算、求和運(yùn)算或最小(大)值運(yùn)算等。例如，當(dāng)性能屬性為傳輸速率時(shí)，c1c2=c1+c2;當(dāng)性能屬性為最大時(shí)延時(shí)，c1c2=max(c1，c2);當(dāng)性能屬性為執(zhí)行時(shí)間時(shí)，c1和c2均為取值區(qū)間，c1c2=c1∪c2。特別地，若c2=，則c1c2=c1;若c1=，則c1c2=c2。

定義3 性能矢量疊加。兩個(gè)性能矢量Config1和Config2進(jìn)行疊加，記為Config1Config2=［c11，c12，…，c1m］［c21，c22，…，c2m］。具體表達(dá)式為

2.2 服務(wù)組合優(yōu)化

服務(wù)組合優(yōu)化問(wèn)題就是從每個(gè)服務(wù)i 對(duì)應(yīng)的候選服務(wù)實(shí)體集合Si中挑選出合適的實(shí)體eij，從而得到成本最優(yōu)的服務(wù)組合模式SCMbest，且滿足性能約束和資源約束。圖1 中的SCM1={e11，e21，e31，e41，e51}和SCM2={e13，e22，e32，e42，e52}即為兩種可能的服務(wù)組合模式。

圖1 服務(wù)組合優(yōu)化問(wèn)題Fig.1 Service composition optimization problem

服務(wù)組合優(yōu)化問(wèn)題的關(guān)鍵在于使所有服務(wù)實(shí)體的性能需求得到滿足。

定義4 性能滿足。若服務(wù)實(shí)體eij的輸入性能矢量Configin被所依賴(lài)的服務(wù)實(shí)體{e1，e2，…，el}所滿足，則下式成立:

此外，在虛擬網(wǎng)構(gòu)建過(guò)程中，Resource=［R1，R2，…，Rk］是服務(wù)組合的資源約束條件;服務(wù)組合后的服務(wù)功能鏈也需要滿足虛擬網(wǎng)的整體性能需求Configreq=［c1，c2，…，cm］，所以末節(jié)點(diǎn)候選服務(wù)實(shí)體的輸出性能矢量需要與Configreq相匹配。

綜合上述設(shè)定，服務(wù)組合優(yōu)化問(wèn)題可以描述為:尋找一個(gè)服務(wù)組合模式SCMbest=，n 表示候選實(shí)體集合個(gè)數(shù)，ai表示第i個(gè)候選服務(wù)實(shí)體集合中選擇的實(shí)體序號(hào)，1≤i≤n，1≤ai≤M，使其滿足

(1)除源節(jié)點(diǎn)外，其他服務(wù)實(shí)體的性能需求均得到滿足;

(3)組合模式中所有實(shí)體占用的資源不超過(guò)虛擬網(wǎng)限定的資源閾值Resource;

(4)在滿足上述3個(gè)條件下，選取成本最低的服務(wù)組合模式。

形式化描述如下:

式(2)表示組合模式中所有服務(wù)實(shí)體的總成本，而每個(gè)服務(wù)實(shí)體的成本=所占各種資源的成本+實(shí)體的固有成本，其中wj為資源屬性rj的單位成本;pi為候選服務(wù)實(shí)體的固有成本，為了便于描述，式(3)中將作為源節(jié)點(diǎn)、作為末節(jié)點(diǎn)，分別描述了上文中(1)、(2)和(3)三種約束條件;M為候選服務(wù)實(shí)體集合大小的上界。

服務(wù)組合優(yōu)化問(wèn)題是一個(gè)具有復(fù)雜約束的整數(shù)規(guī)劃問(wèn)題，其復(fù)雜性為NP－h(huán)ard。如果采用遍歷方式，則最壞情況下搜索的模式數(shù)為O(Mn)，模式的有效性判別時(shí)間復(fù)雜度為O(n2)，所以總的時(shí)間復(fù)雜度為O(Mnn2)，僅適用于小規(guī)模服務(wù)組合。為適應(yīng)不同規(guī)模的服務(wù)組合，需要采用啟發(fā)算法。

現(xiàn)有啟發(fā)式算法如模擬退火算法、遺傳算法、粒子群算法等主要采用罰函數(shù)方法或者松弛方法消除約束條件，但考慮到本文提出的服務(wù)組合優(yōu)化問(wèn)題的約束條件屬于整數(shù)約束而且較為復(fù)雜，上述方法均難以保證能以較大概率收斂到有效解。因此，本文提出一種改進(jìn)的啟發(fā)式算法，能夠有目的性地產(chǎn)生新解，從而提高算法收斂到有效解的概率。然而，遺傳算法和粒子群算法的新解產(chǎn)生過(guò)程相對(duì)受限，因此后文對(duì)模擬退火算法進(jìn)行改進(jìn)，利用解的性能需求約束的分層特性，設(shè)計(jì)適合服務(wù)組合優(yōu)化問(wèn)題的新解產(chǎn)生函數(shù)和目標(biāo)函數(shù)。

3 服務(wù)組合優(yōu)化算法

模擬退火算法是一種適合解決NP－h(huán)ard 問(wèn)題的通用有效的全局優(yōu)化算法，其基本思想是從任意解出發(fā)，每次產(chǎn)生一個(gè)鄰居解，直接接受使目標(biāo)函數(shù)更優(yōu)的鄰居解，或以一定概率接受使目標(biāo)函數(shù)變差的鄰居解，不斷迭代上述過(guò)程，最終得到使目標(biāo)函數(shù)全局最優(yōu)的近似解。采用改進(jìn)的模擬退火算法解決服務(wù)組合優(yōu)化問(wèn)題，關(guān)鍵在于確定新解的產(chǎn)生函數(shù)(Generation Function)和目標(biāo)函數(shù)(Cost Function)的計(jì)算公式，以便克服無(wú)效解的干擾。

3.1 基于層次屬性的產(chǎn)生函數(shù)

首先，需要對(duì)問(wèn)題的解進(jìn)行編碼。服務(wù)組合優(yōu)化問(wèn)題的解(即服務(wù)組合模式)使用了一個(gè)整數(shù)數(shù)組來(lái)表示，數(shù)組的長(zhǎng)度為組成服務(wù)功能鏈的服務(wù)實(shí)體數(shù)n，數(shù)組中的每個(gè)元素為該服務(wù)實(shí)體所對(duì)應(yīng)的索引號(hào)，比如服務(wù)組合模式SCMi={e13，e21，e32，e42，e54}可以被編碼為［3，1，2，2，4］的數(shù)組。然后，算法的初始化過(guò)程就是對(duì)數(shù)組中的元素賦予隨機(jī)的正整數(shù)值，并且取值范圍不超過(guò)相應(yīng)候選服務(wù)實(shí)體集合的大小。

成立金融改革工作領(lǐng)導(dǎo)小組，政府主要領(lǐng)導(dǎo)任組長(zhǎng)，駐地金融監(jiān)管部門(mén)和相關(guān)部門(mén)為成員單位，建立健全跨行業(yè)、跨部門(mén)的工作聯(lián)動(dòng)機(jī)制，加強(qiáng)統(tǒng)籌協(xié)調(diào)，整體推進(jìn)和監(jiān)督落實(shí)，協(xié)調(diào)重大金融項(xiàng)目和金融改革政策落地實(shí)施；領(lǐng)導(dǎo)小組下設(shè)辦公室在政府金融辦，政府金融辦主任兼任辦公室主任負(fù)責(zé)領(lǐng)導(dǎo)小組日常工作；領(lǐng)導(dǎo)小組及其辦公室不刻制印章，如因工作需要由市政府金融辦代章；各地也要建立相應(yīng)的工作推進(jìn)機(jī)制，形成上下齊抓共管的金融改革工作新格局。

為了更好地逼近有效解，模擬退火算法設(shè)計(jì)了具有記憶性的新解產(chǎn)生函數(shù)。所謂有記憶性是指新解產(chǎn)生函數(shù)能夠記錄當(dāng)前解的層次屬性(見(jiàn)定義5)，并且根據(jù)具體情況產(chǎn)生三種類(lèi)型的新解:具有相同層次屬性的新解;具有更高層次屬性的新解;具有更低層次屬性的新解。下面給出解的層次屬性定義。

定義5 解的層次屬性。根據(jù)圖論中的反向拓?fù)渑判蛩惴ǎ鈹?shù)組中的每個(gè)元素所代表的候選服務(wù)實(shí)體都存在唯一的層次編號(hào)。新解是通過(guò)隨機(jī)改變舊解數(shù)組中的若干元素得到的，并且這些元素所代表的候選服務(wù)實(shí)體具有相同的層次編號(hào)，所以每個(gè)解的產(chǎn)生都與一個(gè)層次編號(hào)相關(guān)聯(lián)，該編號(hào)稱(chēng)為解的層次屬性。

在對(duì)候選服務(wù)實(shí)體的層次編號(hào)進(jìn)行預(yù)計(jì)算后，新解產(chǎn)生函數(shù)的處理流程如下所示:

GenFunc 函數(shù)每次只針對(duì)首先出現(xiàn)性能約束不匹配的一層進(jìn)行隨機(jī)改變生成新解;如遇有效解，則隨機(jī)從某一層開(kāi)始新解的生成。經(jīng)過(guò)逐層推進(jìn)，解的性能約束條件逐漸得到滿足，從而趨近有效解。這種方式有利于避免普通隨機(jī)生成方式的盲目性，提高有效解的搜索效率。

3.2 基于偏離度的目標(biāo)函數(shù)

對(duì)于當(dāng)前解Mold和新產(chǎn)生的解Mnew，若目標(biāo)函數(shù)值f(Mnew)＜f(Mold)，則直接接受Mnew為當(dāng)前解;若f(Mnew)≥f(Mold)，則依接受概率接受Mnew。接受概率P(Mold，Mnew，t)的計(jì)算公式如下:

根據(jù)公式(4)，定義如下的目標(biāo)函數(shù)計(jì)算公式:

式(5)中的Cost 函數(shù)用來(lái)計(jì)算當(dāng)前解(服務(wù)組合模式)所消耗的成本值，具體見(jiàn)公式(2);Conflict.size()表示當(dāng)前層次的服務(wù)實(shí)體集合中違反與上層服務(wù)實(shí)體性能依賴(lài)關(guān)系的個(gè)數(shù)，1 +Conflict.size()即為解的偏離度。

3.3 基于模擬退火的服務(wù)組合模式搜索

基于上述函數(shù)設(shè)計(jì)，可以得到基于模擬退火的服務(wù)組合模式搜索算法(Service Composition Mode search algorithm based on Simulated Annealing，SCM－SA)的完整處理流程如下:

3.4 復(fù)雜度分析

由于SCM－SA 算法是基于模擬退火算法，因此新解的迭代產(chǎn)生次數(shù)是受參數(shù)影響的，如果將算法參數(shù)視作常數(shù)，則迭代次數(shù)的復(fù)雜度是O(1)。對(duì)于新解產(chǎn)生函數(shù)GenFunc，其計(jì)算復(fù)雜性主要體現(xiàn)在第8步“while j ＜L do”中，其復(fù)雜度為O(n2)，而該步的執(zhí)行次數(shù)由服務(wù)拓?fù)涞淖畲蠊?jié)點(diǎn)度D 和最大層次數(shù)H決定，最壞情況下次數(shù)為O(D +H)，因此函數(shù)Gen-Func 的最壞情況復(fù)雜度為O(n2(D+H))。

4 實(shí)驗(yàn)評(píng)估

4.1 實(shí)驗(yàn)設(shè)置

通過(guò)C++編程模擬服務(wù)組合優(yōu)化問(wèn)題并實(shí)現(xiàn)模擬退火算法。實(shí)驗(yàn)方案主要為了評(píng)估SCM－SA算法相比于其他啟發(fā)式算法在服務(wù)組合成功率和組合代價(jià)上的優(yōu)勢(shì)。服務(wù)組合成功率CSR 是指所有服務(wù)組合請(qǐng)求中成功的比例。

在實(shí)驗(yàn)數(shù)據(jù)上，利用TGFF［15］工具隨機(jī)生成具有指定節(jié)點(diǎn)數(shù)的服務(wù)拓?fù)洌抑豢紤]有向無(wú)環(huán)圖(DAG)。利用C++語(yǔ)言生成候選服務(wù)實(shí)體集合，其中每個(gè)候選服務(wù)實(shí)體集合大小在［3，10］內(nèi)均勻分布。每個(gè)候選服務(wù)實(shí)體的性能矢量長(zhǎng)度為3，且性能屬性的取值為0 或1，疊加符號(hào)對(duì)應(yīng)最小值運(yùn)算，其中1 的概率為90%。候選服務(wù)實(shí)體的資源屬性個(gè)數(shù)為3，且取值在［10，100］內(nèi)均勻分布，各資源屬性的單位成本w1、w2和w3分別設(shè)為1.0、1.0 和1.0，總量均設(shè)為4000。此外，候選服務(wù)實(shí)體的固有成本取值在［10，15］內(nèi)均勻分布。

4.2 性能評(píng)估

實(shí)驗(yàn)中，SCM－SA 算法的主要參數(shù)取值如下:初始溫度Ts=1000，終止溫度Te=10，降溫比例a=0.9，每個(gè)溫度下迭代的次數(shù)L=5 ×n(n 為服務(wù)拓?fù)涔?jié)點(diǎn)數(shù))，收斂條件R=50。在不同服務(wù)組合規(guī)模下(n=10，15，20，25，30，35，40)，分別進(jìn)行60 次服務(wù)組合問(wèn)題求解，計(jì)算不同算法的服務(wù)組合成功率CSR，結(jié)果如圖2 所示?？梢钥闯觯S著服務(wù)組合規(guī)模的擴(kuò)大，服務(wù)間的性能依賴(lài)關(guān)系更加復(fù)雜化，從而使各種算法的CSR 值逐漸降低。其中，SCM－ SA算法的CSR 值保持在46.7%以上，高于其他算法;單純考慮有效解的模擬退火算法Feasible－ SA 的CSR 值始終低于SCM－SA 算法，且隨組合規(guī)模n 的擴(kuò)大而下降至16.7%;不考慮解有效性的基本遺傳算法GA 的CSR 值最低，不超過(guò)10%。上述結(jié)果表明，單純考慮有效解方式會(huì)使部分搜索陷入僵局，降低CSR 值，基本啟發(fā)式算法(GA)則很難在復(fù)雜約束條件下收斂到有效解，所以CSR 值最低。

圖2 不同算法的服務(wù)組合成功率(CSR)比較Fig.2 CSR comparison among different algorithms

相同實(shí)驗(yàn)環(huán)境下，比較不同算法的最優(yōu)服務(wù)組合模式成本值，如圖3 所示。從實(shí)驗(yàn)結(jié)果可以看出，不同算法的服務(wù)組合模式成本值的大小關(guān)系為CSCM－SA＜ CFeasible－SA＜ CGA，其中Feasible－ SA 和GA 算法的成本值比較接近。隨著服務(wù)組合規(guī)模n的擴(kuò)大，不同算法的成本值差距逐漸增大。上述結(jié)果表明，單純考慮有效解方式會(huì)使結(jié)果陷入局部最優(yōu)，而基本啟發(fā)式算法又易受無(wú)效解的干擾，從而使算法得到的成本值偏大。

圖3 不同算法得到的最優(yōu)組合代價(jià)Fig.3 Composition cost comparison among different algorithms

比較不同算法的時(shí)間消耗，如圖4 所示。從實(shí)驗(yàn)結(jié)果可以看出，基本遺傳算法GA 的時(shí)間消耗最小且波動(dòng)不明顯，單純考慮有效解的模擬退火算法Feasible－SA 的時(shí)間消耗最大，且隨問(wèn)題規(guī)模呈非線性增長(zhǎng)，而SCM－SA 算法的時(shí)間消耗低于Feasible－SA，原因在于，GA 的新解產(chǎn)生函數(shù)跟問(wèn)題規(guī)模無(wú)關(guān)，而Feasible－SA 和SCM－SA 的新解產(chǎn)生函數(shù)跟問(wèn)題規(guī)模有關(guān)，并且Feasible－SA 只考慮有效解，導(dǎo)致調(diào)用新解產(chǎn)生函數(shù)的次數(shù)多于SCM－SA，因此時(shí)間消耗大于SCM－SA。

圖4 不同算法的時(shí)間消耗Fig.4 Time cost comparison among different algorithms

上述實(shí)驗(yàn)在不同組合規(guī)模和仿真數(shù)據(jù)下重復(fù)進(jìn)行，結(jié)果表明SCM－SA 算法在服務(wù)組合成功率和服務(wù)組合成本上優(yōu)于其他算法。

5 結(jié)束語(yǔ)

本文對(duì)網(wǎng)絡(luò)功能虛擬化中的服務(wù)功能鏈構(gòu)建和服務(wù)組合優(yōu)化問(wèn)題進(jìn)行了論述。首先，針對(duì)服務(wù)實(shí)體的性能描述需求和匹配約束特性，給出了一種服務(wù)實(shí)體性能模型，并在此基礎(chǔ)上形式化分析服務(wù)組合優(yōu)化問(wèn)題。然后，為減輕大量不滿足性能約束的無(wú)效解對(duì)搜索過(guò)程的干擾，提出了改進(jìn)的模擬退火算法SCM－SA。最后，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了SCMSA 算法在服務(wù)組合成功率和組合成本上具有明確的優(yōu)勢(shì)。

本文對(duì)單一服務(wù)組合請(qǐng)求下的優(yōu)化問(wèn)題進(jìn)行了研究，而實(shí)際的服務(wù)組合請(qǐng)求可以是在線到達(dá)的，所以下一步需對(duì)在線模式下的服務(wù)組合優(yōu)化問(wèn)題進(jìn)行研究。

［1］Network Functions Virtualisation(NFV).Network Operator Perspectives on Industry Progress，ETSI ［EB/OL］.2014－04－ 01［2015－ 01－ 05］.http://portal.etsi.org/NFV/NFV_White_Paper2.pdf.

［2］Yu M，Yi Y，Rexford J，et al.Rethinking virtual network embedding:substrate support for path splitting and migration［J］.ACM SIGCOMM Computer Communication Review，2008，38(2):17－29.

［3］Chowdhury M，Rahman M R，Boutaba R.Vineyard:Virtual network embedding algorithms with coordinated node and link mapping［J］.IEEE/ACM Transactions on Networking，2012，20(1):206－219.

［4］Boucadair M，Jacquenet C，Parker R，et al.Service Function Chaining:Framework ＆ Architecture［EB/OL］.2014－08－16［2015－01－05］.http://tools.ietf.org/html/draft－boucadair－sfc－framework－02.

［5］Quinn P，Beliveau A.Service Function Chaining(SFC)Architecture［EB/OL］.2014－02－04［2015－01－05］.http://tools.ietf.org/html/draft－merged－sfc－architecture－01.

［6］Menasce D.QoS issues in Web service［J］.Internet Computing，2002，6(6):72－75.

［7］Zeng L，Benatallah B，Ngu A H H，et al.Qos－aware middleware for web services composition［J］.IEEE Transactions on Software Engineering，2004，30(5):311－327.

［8］Zeng L，Benatallah B，Dumas M，et al.Quality driven web services composition［C］//Proceedings of the 12th International Conference on World Wide Web.New York:ACM，2003:411－421.

［9］張成文，蘇森，陳俊亮.基于遺傳算法的QoS 感知的Web服務(wù)選擇［J］.計(jì)算機(jī)學(xué)報(bào)，2006，29(7):1029－1037.ZHANG Chengwen，SU Sen，CHEN Junliang.Genetic algorithm on web services selection supporting QoS［J］.Chinese Journal of Computers，2006，29(7):1029－1037.(in Chinese)

［10］蔣哲遠(yuǎn)，韓江洪，王釗.動(dòng)態(tài)的QoS 感知Web 服務(wù)選擇和組合優(yōu)化模型［J］.計(jì)算機(jī)學(xué)報(bào)，2009(5):1014－1025.JIANG Zheyuan，HAN Jianghong，WANG Zhao.An Optimization Model for Dynamic QoS－Aware Web Services Selection and Composition［J］.Chinese Journal of Computers，2009(5):1014－1025.(in Chinese)

［11］Ma H，Bastani F，Yen I L，et al.QoS－ driven service composition with reconfigurable services［J］.IEEE Transactions on Services Computing，2013，6(1):20－34.

［12］Xiang F，Hu Y，Yu Y，et al.QoS and energy consumption aware service composition and optimal－ selection based on Pareto group leader algorithm in cloud manufacturing system［J］.Central European Journal of Operations Research，2014，22(4):663－685.

［13］Tao F，LaiLi Y，Xu L，et al.FC－PACO－RM:a parallel method for service composition optimal－selection in cloud manufacturing system［J］.IEEE Transactions on Industrial Informatics，2013，9(4):2023－2033.

［14］王勇，代桂平，侯亞榮.信任感知的組合服務(wù)動(dòng)態(tài)選擇方法［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32(8):1668－1675.WANG Yong，DAI Guiping，HOU Yarong.Dynamic methods of trust－aware composite service selection［J］.Chinese Journal of Computers，2009，32(8):1668－1675.(in Chinese)

［15］Dick R P，Rhodes D L，Wolf W.TGFF:task graphs for free［C］//Proceedings of the 6th International Workshop on Hardware/Software Codesign.Seattle:IEEE，1998:97－101.