服務(wù)網(wǎng)絡(luò)的啟發(fā)式定制方法

王忠杰，王少鵬，徐 飛

（哈爾濱工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001）

0 引言

服務(wù)組合［1－2］是利用小粒度Web服務(wù)組合形成大粒度服務(wù)，以滿足客戶個性化需求的有效手段，也是近年來服務(wù)計算領(lǐng)域的研究熱點之一。雖然目前研究成果非常豐富，但多側(cè)重于為單一需求構(gòu)建組合方案，在應(yīng)對大規(guī)?？蛻粜枨髸r存在成本有效性方面的不足。具體來說，當(dāng)多請求抵達(dá)時，需要針對每個需求分別構(gòu)造組合方案，忽略了需求間的相似性和由此導(dǎo)致的方案間可能存在的共享，需求滿足的成本較高。

服務(wù)網(wǎng)絡(luò)（Service Network，SN）［3］是應(yīng)對該挑戰(zhàn)的有效方法。SN采用類窮舉機(jī)制將分散在互聯(lián)網(wǎng)上的開放網(wǎng)絡(luò)服務(wù)（Web service）和應(yīng)用程序接口（Application Programming Interface，API）連接形成網(wǎng)絡(luò)，彼此之間通過標(biāo)準(zhǔn)化互操作協(xié)議進(jìn)行交互。與傳統(tǒng)的服務(wù)組合方法相比，它不是根據(jù)特定需求構(gòu)造的組合方案，而是根據(jù)可用服務(wù)之間的相關(guān)性／相似性以及歷史需求體現(xiàn)出的共性特征，提前將可用服務(wù)組織在一起，構(gòu)造出具有滿足大規(guī)模需求能力的持久性基礎(chǔ)設(shè)施。當(dāng)新需求抵達(dá)時，只需對服務(wù)網(wǎng)絡(luò)進(jìn)行定制即可得到一個滿足需求的子網(wǎng)絡(luò)。該方式的優(yōu)勢為：用一套基礎(chǔ)設(shè)施為同一領(lǐng)域內(nèi)相似需求的客戶提供持續(xù)服務(wù)，達(dá)到成本有效性，較好地支持服務(wù)的大規(guī)模個性化定制。

服務(wù)網(wǎng)絡(luò)可以是自然形成的，也可由特定組織根據(jù)領(lǐng)域需求自行構(gòu)建，在使用過程中不斷進(jìn)行擴(kuò)展和調(diào)整，使其符合客戶需求特征的變化趨勢。本文關(guān)注的是服務(wù)網(wǎng)絡(luò)的定制階段：根據(jù)客戶的個性化需求找到服務(wù)網(wǎng)絡(luò)的最優(yōu)定制方案。隨著服務(wù)網(wǎng)絡(luò)規(guī)模和復(fù)雜度的增加，定制的難度也會越來越大。一個服務(wù)網(wǎng)絡(luò)可能存在多種定制方案均可滿足客戶需求，如何找出最優(yōu)的定制方案，是一種挑戰(zhàn)。另一方面，服務(wù)網(wǎng)絡(luò)的能力是有限的，可能無法完全滿足客戶在功能上或性能上的期望。因此，在對服務(wù)網(wǎng)絡(luò)進(jìn)行定制時，需要能夠識別出它相對于需求所缺失的能力，以便在后續(xù)的生長階段對其進(jìn)行能力增強(qiáng)。

本文首先給出服務(wù)網(wǎng)絡(luò)的數(shù)學(xué)描述，建立服務(wù)網(wǎng)絡(luò)優(yōu)化定制問題的數(shù)學(xué)模型，對其能力缺陷進(jìn)行分類。進(jìn)而研究優(yōu)化定制算法，分為預(yù)處理、輸入?yún)?shù)補(bǔ)充、服務(wù)網(wǎng)絡(luò)定制三個階段。由于搜索空間很大，采用啟發(fā)式算法求解輸入?yún)?shù)補(bǔ)充的問題，采用人工蜂群算法求解服務(wù)網(wǎng)絡(luò)定制的問題。通過仿真實驗對算法性能進(jìn)行測試，并分析相關(guān)參數(shù)對算法求解結(jié)果的影響。

相比已有工作，本文的貢獻(xiàn)是：①與傳統(tǒng)的服務(wù)組合方法針對單一需求從零開始構(gòu)造組合方案的方式不同，本文針對一個已存在的服務(wù)網(wǎng)絡(luò)進(jìn)行定制，該途徑能夠以成本有效的方式實現(xiàn)面向多客戶需求的服務(wù)大規(guī)模定制；②與傳統(tǒng)的服務(wù)大規(guī)模個性化定制研究不同，本文中服務(wù)網(wǎng)絡(luò)的可定制特征并非預(yù)先設(shè)計出來的，而是由各服務(wù)節(jié)點在功能和服務(wù)質(zhì)量（Quality of Service，QoS）方面表現(xiàn)出的差異以及服務(wù)之間連接關(guān)系的多樣性構(gòu)成的，從而提升了客戶個性化需求被滿足的程度。

1 相關(guān)研究

大規(guī)模定制［4］起源于生產(chǎn)制造領(lǐng)域，其基本思想是：基于產(chǎn)品族零部件和產(chǎn)品結(jié)構(gòu)的相似性和通用性，利用標(biāo)準(zhǔn)化模塊化的方法降低產(chǎn)品的內(nèi)部多樣性，通過產(chǎn)品和過程重組將產(chǎn)品定制生產(chǎn)轉(zhuǎn)化為零部件的批量生產(chǎn)，向客戶提供低成本、高質(zhì)量的定制產(chǎn)品。該思想在軟件工程領(lǐng)域也得到應(yīng)用［5］，例如動態(tài)軟件產(chǎn)品線、面向復(fù)用的軟件工程等方法強(qiáng)調(diào)利用標(biāo)準(zhǔn)化的、可復(fù)用的小粒度構(gòu)件來快速組裝領(lǐng)域內(nèi)的相似應(yīng)用，為領(lǐng)域內(nèi)的特定需求展開定制（架構(gòu)的裁剪與擴(kuò)展、構(gòu)件選擇與組裝），以提升開發(fā)效率、降低開發(fā)成本。

在面向服務(wù)的架構(gòu)（Service Oriented Architecture，SOA）和服務(wù)計算領(lǐng)域，研究者提出了面向大規(guī)模定制的服務(wù)系統(tǒng)的設(shè)計和定制方法［6－7］。利用服務(wù)族、語義本體、規(guī)則等方式［8－9］刻畫服務(wù)可配置點和彼此間的依存關(guān)系［10－11］，在運(yùn)行階段則以動態(tài)工作流等技術(shù)加以支持。軟件即服務(wù)（Software as a Service，SaaS）是實現(xiàn)服務(wù)大規(guī)模個性化定制的另一種實踐，其基本思想是使用元數(shù)據(jù)模型、策略（policy）等方式設(shè)定可變點來支持個性化配置［12］，用一個服務(wù)系統(tǒng)運(yùn)行實例滿足多租戶的個性化需求。

但這些支持大規(guī)模個性化定制的服務(wù)系統(tǒng)本質(zhì)上都是“封閉”的，通常由服務(wù)提供者遵循特定的模型驅(qū)動過程構(gòu)建，其中包含的可定制點也是由建模者根據(jù)經(jīng)驗與領(lǐng)域知識識別出來的。這與服務(wù)的“開放”特性相違背，較難充分利用互聯(lián)網(wǎng)上持續(xù)增長的可用服務(wù)，限制了服務(wù)系統(tǒng)的可定制能力。

在開放環(huán)境下利用“窮舉”的方式構(gòu)造服務(wù)網(wǎng)絡(luò)，是近年來服務(wù)計算領(lǐng)域出現(xiàn)的一種流行策略［13－14］。該策略針對各類開放 Web服務(wù)和 API，分析它們之間的功能／語義相關(guān)性／相似性，或者基于對歷史需求特征和服務(wù)使用特征的挖掘，將它們逐漸融合起來形成支持后續(xù)需求的服務(wù)網(wǎng)絡(luò)。研究者使用了諸如服務(wù)生態(tài)系統(tǒng)［15］、組合服務(wù)網(wǎng)絡(luò)［16］、Web 2.0服務(wù)網(wǎng)絡(luò)［17］、全球社會化服務(wù)網(wǎng)絡(luò)［18］等不同名稱，來描述此類依賴于“自然生長”機(jī)制所形成的服務(wù)間連接關(guān)系，逐漸發(fā)展成為可滿足各類客戶需求的社會化持久基礎(chǔ)設(shè)施。典型工作包括：服務(wù)網(wǎng)絡(luò)的構(gòu)建機(jī)制（如“滾雪球”方法［13］、服務(wù)鏈方法［19］、服務(wù)社交化方法［18，20］等）和服務(wù)網(wǎng)絡(luò)的演化與生長機(jī)理（利用復(fù)雜網(wǎng)絡(luò)和圖論的相關(guān)方法來分析服務(wù)之間的靜態(tài)關(guān)聯(lián)與動態(tài)連接性質(zhì)［15］，滿足尺度無關(guān)和小世界網(wǎng)絡(luò)特性［16－17，21］，代表了海量客戶在使用服務(wù)過程中所形成的群體智能）。這些研究為服務(wù)網(wǎng)絡(luò)作為支持服務(wù)大規(guī)模個性化定制的重要工具奠定了理論基礎(chǔ)。

2 服務(wù)網(wǎng)絡(luò)及定制

2.1 服務(wù)網(wǎng)絡(luò)

上述給出的服務(wù)網(wǎng)絡(luò)結(jié)構(gòu)中隱含著兩種關(guān)系：兩個服務(wù)節(jié)點若相互連接，則意味著它們之間存在“關(guān)聯(lián)性”（related-to），它們通過接口進(jìn)行數(shù)據(jù)傳遞，以實現(xiàn)更大粒度的服務(wù)功能；包含在同一服務(wù)節(jié)點內(nèi)的各原子服務(wù)之間具有功能上的等價性或相似性（similar-as），意即它們具有相似的輸入輸出接口和功能語義，可以相互替換，在實際定制時僅需選擇一個原子服務(wù)即可。

2.2 服務(wù)網(wǎng)絡(luò)的可定制性

服務(wù)網(wǎng)絡(luò)的定制是指給定一個具有特定功能和QoS約束的需求，從服務(wù)網(wǎng)絡(luò)中找到一個子網(wǎng)絡(luò)，能夠以最小的代價滿足需求中的各類約束。針對不同的客戶需求，可定制出不同的個性化方案。服務(wù)網(wǎng)絡(luò)的可定制性體現(xiàn)在功能的可定制性和QoS的可定制性兩方面。

OR關(guān)系的存在意味著SN有多種方式來生成特定數(shù)據(jù)，從而以不同方式滿足需求，這是SN在功能上的定制能力。在針對具體需求的定制方案中，所有OR關(guān)系都將被消除，只保留其中唯一的一條邊和相應(yīng)的服務(wù)節(jié)點并提供給客戶使用。將SN中滿足｜Φ（sj，pk）｜＞1或｜Θ（pk）｜＞1的參數(shù)pk稱為“多源參數(shù)”。

（2）QoS的可定制性 在定制時從每個服務(wù)sj的原子服務(wù)集Aj中選擇一個特定的原子服務(wù)，由此影響最終定制方案的QoS水平。將滿足｜Aj｜＞1的服務(wù)sj稱為復(fù)合服務(wù)節(jié)點，在圖1中使用雙線圓形表示，以區(qū)別于｜Aj｜＝1的非復(fù)合服務(wù)節(jié)點。

歸納起來，SN的可定制機(jī)制包含兩方面：①參數(shù)生成方式的多樣性，體現(xiàn)為服務(wù)連接中的OR關(guān)系，即多源參數(shù)；②服務(wù)節(jié)點QoS的多樣性，體現(xiàn)為復(fù)合節(jié)點。前者支持SN以不同方式滿足同樣的功能需求，后者使定制方案具有不同的QoS水平。這與傳統(tǒng)的服務(wù)組合研究思路類似：基于人工智能規(guī)劃的服務(wù)組合方法擅長構(gòu)造服務(wù)之間連接關(guān)系的多樣性（對應(yīng)于SN的多源參數(shù)），而QoS感知的服務(wù)組合方法則擅長從每個服務(wù)任務(wù)的候選服務(wù)集（對應(yīng)于SN的復(fù)合服務(wù)節(jié)點）中進(jìn)行選擇，以構(gòu)造不同QoS水平的組合方案。SN則將二者有機(jī)結(jié)合，以更好地支持客戶個性化需求的實現(xiàn)。

2.3 個性化需求

服務(wù)網(wǎng)絡(luò)面向特定的客戶需求進(jìn)行定制，包含功能需求和質(zhì)量需求，抽象定義為r＝（I，O，Q）。其中：I和O分別表示客戶所提供的輸入?yún)?shù)集合和期望獲得的輸出參數(shù)集合，共同作為功能需求；Q表示質(zhì)量需求，其中的元素表示為二元組（QParami，QConsi），表示客戶期望的服務(wù)組合方案的各質(zhì)量參數(shù)QParami（如執(zhí)行時間、可靠性、價格）需滿足的最低期望為QConsi。

2.4 能力缺陷分類

根據(jù)需求r對SN進(jìn)行定制，相當(dāng)于對SN的兩類可定制點（多源參數(shù)、復(fù)合服務(wù)節(jié)點）具體化，去掉與之無關(guān)的節(jié)點和邊后形成一個子網(wǎng)絡(luò)CN。該子網(wǎng)絡(luò)在使用不超過I（r）中提供的參數(shù)的情況下生成O（r）中的全部輸出參數(shù)，且該子網(wǎng)絡(luò)的全局QoS指標(biāo)滿足質(zhì)量期望Q（r）。

若找不到這樣的子網(wǎng)絡(luò)，則意味著SN相對于r來說是“能力缺陷”的，分為以下三類情況：

（1）輸出參數(shù)缺失SN無法生成客戶期望的某些輸出參數(shù)，即O（r）＼O（SN）≠?，這意味著不管對SN做何種定制，需求一定無法完全滿足。

（2）輸入?yún)?shù)不足SN的任何定制方案CN都無法僅使用客戶提供的輸入?yún)?shù)I（r）就可以完全生成O（r）中的所有輸出參數(shù)。這種情況下，可以要求客戶補(bǔ)充某些輸入?yún)?shù)以生成期望的全部輸出。需補(bǔ)充的輸入?yún)?shù)越多，意味著初始需求被滿足的程度就越低。

（3）QoS水平不足 在輸入／輸出參數(shù)均足夠的情況下，SN的任何定制方案都無法滿足Q（r）中的某些QoS約束。在這種情況下，需要找到離QoS期望最近的定制方案，距離越近，需求被滿足的程度就越大。

假設(shè)存在r1，r2和r3三個需求，I（r1）＝I（r3）＝｛p1，p2，p3，p6｝，I（r2）＝｛p4，p5，p10｝，O（r1）＝｛p9，p11，p15｝，O（r2）＝｛p7，p8，p12，p13｝，O（r3）＝｛p9，p11，p14｝，則圖1的SN對r1而言存在輸出參數(shù)缺失，因為O（r1）＼O（SN）＝｛p15｝≠?；對r2而言，在給定I（r2）的情況下無法生成p8，輸入?yún)?shù)不足，可以通過補(bǔ)充輸入?yún)?shù)p1來生成所需的p8，圖2給出了補(bǔ)充p1之后的一個配置方案；對r3而言，給定I（r3）可以生成O（r3），圖3是它的一種可能定制方案，但仍需計算該方案整體的QoS水平以判斷可否滿足期望。

3 問題數(shù)學(xué)模型

服務(wù)網(wǎng)絡(luò)定制問題可定義為：給定一個服務(wù)網(wǎng)絡(luò)SN和一個特定的客戶需求r，找出最優(yōu)的定制方案CN，它滿足r中的功能與QoS需求。該問題的輸出包含CN，EI和LO三部分，具體含義如下：

（1）CN是SN的一個 子網(wǎng)絡(luò)，CN的 輸 入 是SN輸入?yún)?shù)的子集，也是客戶提供的輸入?yún)?shù)的子集，即I（CN）?I（SN），I（CN）?I（r）；CN的輸出是SN輸出參數(shù)的子集，并完全等于客戶要求的輸出，即O（CN）?O（SN），O（CN）＝O（r）；CN中不存在任何復(fù)合服務(wù)節(jié)點和多源參數(shù)，這意味著對SN中可定制特征的完全消除，CN是一個無冗余的組合服務(wù)。

（2）EI是待補(bǔ)充的輸入?yún)?shù)，滿足EI∩I（r）＝?，EI∩O（r）＝?，即要求補(bǔ)充的輸入?yún)?shù)不包含在客戶提供的輸入?yún)?shù)集中，也不能要求客戶補(bǔ)充他自己期望得到的輸出參數(shù)；EI?I（SN），即只能在SN的輸入?yún)?shù)集內(nèi)補(bǔ)充，否則就超出了SN的能力范疇。

（3）LO是R中無法被當(dāng)前SN生成的輸出參數(shù)，即LO?O（r），LO∩O（SN）＝?。若LO≠?，則必然有CN＝?，EI＝?，這意味著：若SN中不包含客戶期望的某些輸出參數(shù)，則不再尋找定制方案，也無需補(bǔ)充任何輸入?yún)?shù)，問題無解；若LO＝?，則必然至少存在一個CN可以完全或部分滿足客戶需求，CN≠?。

該問題的優(yōu)化目標(biāo)是使SN最大程度地滿足R的期望，體現(xiàn)在DF和DQ兩個方面，追求二者的最小化：

4 算法求解

4.1 求解策略分析

第3章給出的兩個優(yōu)化目標(biāo)DF和DQ不是并列的，只有在SN能夠滿足功能需求的情況下，判定QoS的可滿足性才有意義。首先，應(yīng)分析當(dāng)前SN是否有足夠的能力滿足功能需求，若無法滿足，則以最小代價進(jìn)行需求的輸入?yún)?shù)補(bǔ)充，追求DF的最小化；進(jìn)而對SN加以定制，找到與期望的QoS水平最接近的定制方案，追求DQ的最小化。故將問題求解分為三個階段：

（1）預(yù)處理 判斷初始服務(wù)網(wǎng)絡(luò)SN（I）是否有能力生成全部的輸出，若不能，則得到LO，算法結(jié)束；否則，對SN（I）進(jìn)行剪枝，將客戶不需要的輸出參數(shù)和無法提供的輸入?yún)?shù)完全剪掉。若無法滿足全部期望的輸出，則進(jìn)入第（2）階段，否則進(jìn)入第（3）階段。

（2）輸入?yún)?shù)補(bǔ)充 采用啟發(fā)式策略尋求代價最低的輸入?yún)?shù)補(bǔ)充方案EI，進(jìn)入第（3）階段。

（3）定制方案生成 補(bǔ)足輸入?yún)?shù)后，定制得到與客戶QoS期望距離最近的定制方案CN。

4.2 階段1：預(yù)處理

預(yù)處理階段的目標(biāo)是：①發(fā)現(xiàn)LO；②對初始服務(wù)網(wǎng)絡(luò)進(jìn)行剪枝，去掉與需求無關(guān)的部分，為后續(xù)兩個階段做好準(zhǔn)備。具體算法如下：

算法1 預(yù)處理。輸入：SN（I），r；

輸出：LO，SN（P），SN（M）。

算法的（1）～（3）步檢查初始網(wǎng)絡(luò)SN（I）是否可滿足需求期望的全部輸出參數(shù)，若不能滿足，則直接退出，SN存在輸出參數(shù)缺失的能力缺陷。否則，在第（5）步中對SN（I）進(jìn)行剪枝，將客戶不需要的輸出參數(shù)和無法提供的輸入?yún)?shù)完全剪掉，進(jìn)而將由于上述剪枝導(dǎo)致的某些輸入?yún)?shù)不足的服務(wù)節(jié)點也剪掉，最終形成剪枝網(wǎng)絡(luò)SN（P）。設(shè)I（r）＝｛p1，p2，p3，p6｝，O（r）＝｛p9，p11，p14｝，針對r對圖1的SN進(jìn)行剪枝，得到的SN（P）如圖4所示，針對輸入?yún)?shù)的剪枝過程是從SN的輸入?yún)?shù)逐層向后進(jìn)行，針對輸出參數(shù)的剪枝過程則是從SN的輸出參數(shù)逐層向前進(jìn)行。

步驟（6）用于在SN（P）的基礎(chǔ)上發(fā)現(xiàn)滿足需求的骨架網(wǎng)絡(luò)SN（M），它包含了滿足該需求的所有必需的節(jié)點和邊。采用逐個服務(wù)節(jié)點處理的方式：針對SN（P）中的每個服務(wù)節(jié)點s，將它以及所有與它相關(guān)的邊剪掉，檢查剩余網(wǎng)絡(luò)中是否仍可生成客戶期望的全部輸出參數(shù)；若是，則s不是必需的，不包含在SN（M）中，在第（7）～（8）步中將s標(biāo)識為可選節(jié)點（optional）；否則即表示s一定要出現(xiàn)在最終的定制方案中。例如，處理圖4中的s1和s2，可發(fā)現(xiàn)剪掉s1之后仍然可以生成｛p9，p11，p14｝，而剪掉s2之后無法生成｛p14｝，故s1是可選節(jié)點、s2是必需節(jié)點。圖5給出了最終得到的骨架子網(wǎng)絡(luò)SN（M），圖4中的黑色節(jié)點是經(jīng)過標(biāo)識的可選節(jié)點。

在第（9）～（12）步中，若SN（P）無法滿足需求中全部期望的輸出，則進(jìn)入階段2進(jìn)行輸入?yún)?shù)的補(bǔ)充，否則進(jìn)入階段3進(jìn)行定制。通過剪枝和發(fā)現(xiàn)骨架網(wǎng)絡(luò)，可極大地降低階段2和階段3的搜索空間。

4.3 階段2：輸入?yún)?shù)補(bǔ)充算法

若發(fā)現(xiàn)SN（P）無法生成全部的期望輸出，則進(jìn)行輸入?yún)?shù)補(bǔ)充，找出客戶在當(dāng)前所提供的輸入?yún)?shù)I（r）的基礎(chǔ)上需要最少補(bǔ)充的其他輸入?yún)?shù)集EI，這是對第3章中目標(biāo)DF的優(yōu)化。該階段的輸入是：

（1）LO＝O（r）＼O（SN（P）），表示剪枝網(wǎng)絡(luò)SN（P）無法生成的某些需求輸出參數(shù)，來自階段1；

該階段的輸出為EI，滿足EI?I（SN（I）），EI∩I（r）＝?，EI∩O（r）＝?。

優(yōu)化目標(biāo)為 min（DF）；在O（r）?O（SN（I））的情況下，一定存在一種輸入?yún)?shù)補(bǔ)充方案可生成全部期望輸出，最差的情況是令EI＝I（SN（I））＼（I（r）∪O（r）），即希望客戶將初始SN的全部輸入?yún)?shù)均補(bǔ)充齊全。但這樣的代價太高（DF＝1），是最差的可行解。因此，算法需要從I（SN（I））＼（I（r）∪O（r））中選擇一個最小子集使DF最小化。搜索算法的本質(zhì)是從SN（I）中選擇某些不包含在SN（P）中的服務(wù)節(jié)點和邊加入SN（P）中，確保所有期望的輸出參數(shù)O（r）都可被生成，且引入的服務(wù)節(jié)點數(shù)目和為支持這些服務(wù)節(jié)點所必需補(bǔ)充的SN（I）輸入?yún)?shù)數(shù)目應(yīng)盡可能小。這里采用啟發(fā)式策略進(jìn)行搜索，啟發(fā)式規(guī)則如下：

規(guī)則1 補(bǔ)充輸入?yún)?shù)的數(shù)目越少越好。

規(guī)則2 為補(bǔ)充輸入?yún)?shù)而向SN（P）引入的服務(wù)節(jié)點數(shù)目越少越好。

規(guī)則1與DF直接相關(guān)，規(guī)則2是對階段3定制時的考慮，所引入的必需服務(wù)節(jié)點越多，有很大概率會導(dǎo)致最終定制方案中包含的服務(wù)節(jié)點數(shù)目越多，從而對最終QoS的影響程度越大。

為采用啟發(fā)式策略求解，作如下狀態(tài)定義：E＝〈LI，AS，CS，AO〉表示在搜索過程中所產(chǎn)生的各個狀態(tài)，其中：LI為當(dāng)前狀態(tài)下需要補(bǔ)充的輸入?yún)?shù)集；AS為搜索過程中選中并加入到SN（P）的服務(wù)節(jié)點集合；CS為不包含在SN（P）中但可生成LI中1或多個參數(shù)的服務(wù)節(jié)點集合；AO為當(dāng)前狀態(tài)下SN（P）可提供的全部輸出參數(shù)集合。

（1）初始狀態(tài)E0

1）LI＝LO，表示剪枝網(wǎng)絡(luò)無法生成的輸出參數(shù)集；

2）AS＝?，表示尚未向SN（P）加入任何服務(wù)節(jié)點；

3）CS，表示SN（I）中最靠近輸出且能直接生成LO中1個或多個參數(shù)的服務(wù)節(jié)點集，它們一定不包含在SN（P）中；

4）AO＝AI，表示當(dāng)前SN（P）可提供的全部輸出參數(shù)。

（2）目標(biāo)狀態(tài)EG

1）LI≠?，LI∩LO＝?，表示找到了所需補(bǔ)充的某些輸入?yún)?shù)；

2）AS≠?，表示已向SN（P）加入某些服務(wù)節(jié)點；

3）CS＝?，表示不存在可向SN（P）補(bǔ)充的服務(wù)節(jié)點；

4）AO?LO，表示可生成所有缺失的輸出參數(shù)。

根據(jù)規(guī)則1和規(guī)則2，從E0達(dá)到當(dāng)前狀態(tài)E的代價g＝｜LI∩LO｜＋｜AS｜，前者為當(dāng)前狀態(tài)需要引入的新輸入?yún)?shù)的數(shù)目，后者表示當(dāng)前狀態(tài)需引入的新服務(wù)節(jié)點的數(shù)目。從當(dāng)前狀態(tài)E到目標(biāo)狀態(tài)EG的距離h＝｜LO＼AO｜，表示當(dāng)前狀態(tài)尚無法生成的缺失輸出參數(shù)的數(shù)目，在h＞0時需要繼續(xù)迭代搜索。利用f＝g＋h作為啟發(fā)式規(guī)則進(jìn)行迭代搜索，算法如下。

算法2 尋找需求中待補(bǔ)充的最少輸入?yún)?shù)集。

輸入：LO，AI；

輸出：EI。

算法的第（3）～（11）步代表一次迭代，由狀態(tài)生成規(guī)則可知，每次迭代可補(bǔ)充至少1個缺失的輸出參數(shù)，故最多只需迭代｜LO｜次，可確保達(dá)到目標(biāo)狀態(tài)。而LO最大取值為需求r中期望的輸出參數(shù)個數(shù)，故最差的迭代次數(shù)為M＝｜O（r）｜。每次迭代分為兩部分：（4）～（8）步從當(dāng)前最優(yōu)狀態(tài)EC的候選服務(wù)集中取出每個服務(wù)節(jié)點，產(chǎn)生｜CS（EC）｜個新狀態(tài)。CS（EC）中最多包含的服務(wù)節(jié)點數(shù)量N＝｜S（SN（I））＼S（SN（P））｜，極端情況下N＝｜S（SN）｜。第（9）～（10）步從新狀態(tài)中選擇最優(yōu)的一個狀態(tài)，替換當(dāng)前的EC，最差情況下的時間復(fù)雜度也是N。第（12）～（15）步從所有已達(dá)目標(biāo)狀態(tài)中的生成狀態(tài)中選擇代價最小的一個，將其補(bǔ)充的輸入?yún)?shù)集合LI作為算法輸出，并更新SN（P）。歸納起來，算法2的時間復(fù)雜度為O（M×N）。

4.4 階段3：服務(wù)網(wǎng)絡(luò)定制算法

該階段的輸入是經(jīng)過階段1剪枝和階段2補(bǔ)充輸入?yún)?shù)之后形成的子網(wǎng)絡(luò)SN（P）。此時的SN（P）一定可以生成客戶期望的全部輸出參數(shù)，本階段的目標(biāo)是找到與客戶QoS期望距離最近的定制方案，即min（DQ）。定制過程相當(dāng)于對SN（P）中存在的每一個多源參數(shù)和復(fù)合節(jié)點進(jìn)行定制，即：為多源參數(shù)選擇一條具體的“源邊”、為復(fù)合節(jié)點選擇一個具體的原子服務(wù)。這兩方面選擇的結(jié)果都會對最終定制結(jié)果的全局QoS產(chǎn)生影響。

ABC算法借助于一群蜜蜂合作尋找蜜源的過程，將局部搜索和全局搜索相結(jié)合，逐步逼近最優(yōu)解。局部搜索是指：針對SN個食物源，按照特定標(biāo)準(zhǔn)對每個食物源進(jìn)行鄰域探索，適應(yīng)度越高的食物源得到的被探索機(jī)會就越大，探索后的新食物源若優(yōu)于原有食物源，則替換之；若探索達(dá)到Limit次之后仍無改進(jìn)，則跳出局部搜索，尋找一個新食物源代替它，即全局搜索。若連續(xù)迭代MCN次仍無法繼續(xù)改善全局最優(yōu)解，則算法結(jié)束，當(dāng)前搜索得到的最優(yōu)解為最終輸出結(jié)果。SN、Limit和MCN是ABC算法的三個基本控制參數(shù)。之所以選擇ABC求解，是因為它具有強(qiáng)大的并行化局部搜索的能力、跳出局部搜索進(jìn)行全局搜索的能力，以及根據(jù)優(yōu)化效果動態(tài)停止迭代的能力，且已在服務(wù)組合等類似問題上得到應(yīng)用，并被證實具有良好效果［23］。

以下對ABC求解SN定制問題中的若干關(guān)鍵要素進(jìn)行說明：

（1）食物源（解）的表示f＝（p1，p2，…，pm；s1，s2，…，sn），?i∈［1，m］，pi＝eiu表示第i個多源參數(shù)的第u條源邊被選中；?j∈［1，n］，sj＝ajv表示復(fù)合節(jié)點sj中的第v個服務(wù)ajv被選中。

（2）食物源的適應(yīng)度（fitness） 用DQ加以度量，根據(jù)食物源所代表的定制方案的流程結(jié)構(gòu)和被選中的各個服務(wù)節(jié)點的具體QoS值，計算定制方案的全局QoS，再計算相應(yīng)的DQ。

（3）解的鄰域有兩種形式 ①對某個多源參數(shù)pi，若在當(dāng)前解中其值為eiu，則為其選擇其他源邊，其他所有與pi不同的參數(shù)以及復(fù)合服務(wù)的選擇方案均不變，即構(gòu)成了當(dāng)前解的鄰域；②復(fù)合節(jié)點sj，若在當(dāng)前解中的值為ajv，則為其選擇其他原子服務(wù)，其他所有多源參數(shù)和與sj不同的復(fù)合節(jié)點的選擇方案均不變，也構(gòu)成了當(dāng)前解的鄰域。

（4）鄰域搜索策略 ①完全隨機(jī)策略，在食物源處隨機(jī)選擇1個參數(shù)或1個復(fù)合節(jié)點，隨機(jī)在它的其他源邊或其他原子服務(wù)中選擇1個，替換形成新解；②啟發(fā)式策略，為了提高收斂速度，針對復(fù)合節(jié)點的鄰域使用如下啟發(fā)式規(guī)則：根據(jù)DQ對每個原子服務(wù)進(jìn)行估值，其DQ值越小，被選中的概率就越大，即那些具有更優(yōu)QoS的原子服務(wù)會被優(yōu)先探索。

（5）解的重復(fù)性檢查 按照解的結(jié)構(gòu)對SN（P）進(jìn)行刪減，剪掉那些對其他節(jié)點或輸出參數(shù)無貢獻(xiàn)的節(jié)點，若形成的定制方案與之前已經(jīng)探索過的解相同，則將其拋棄，重新隨機(jī)生成或探索新的鄰域。

（6）算法的停止條件 當(dāng)最優(yōu)解的質(zhì)量連續(xù)MCN次迭代均沒有改進(jìn)時，算法停止，將當(dāng)前最優(yōu)解輸出。

5 實驗與分析

5.1 數(shù)據(jù)準(zhǔn)備

編程環(huán)境：Visual Studio 2010C＋＋；運(yùn)行環(huán)境：Intel Core i3雙核3.10GHz，2.93G內(nèi)存，Windows 7操作系統(tǒng)。實驗數(shù)據(jù)采用仿真生成方式，生成100個客戶需求，輸入?yún)?shù)數(shù)目和輸出參數(shù)數(shù)目在［1，100］范圍內(nèi)，期望 QoS指標(biāo) Time，Reliability，Price的取值范圍分別為［20，100］，［0.5，1］，［25，500］。生成20個服務(wù)網(wǎng)絡(luò)，表1給出了其中10個網(wǎng)絡(luò)的基本信息，它們的規(guī)模、復(fù)雜度、可定制點數(shù)目均保持逐漸增加的趨勢。

表1 實驗所用服務(wù)網(wǎng)絡(luò)的基本信息

續(xù)表1

5.2 實驗1：需求特征對定制結(jié)果的影響

本實驗用來驗證需求特征對定制質(zhì)量的影響。選擇1個特定的SN和多個需求，分別利用算法求解，以分析需求處于不同苛刻程度下解的質(zhì)量的變化情況。這里“需求苛刻程度”分為三方面：①所提供的輸入?yún)?shù)數(shù)量；②所期望的輸出參數(shù)數(shù)量；③所期望的QoS水平。“解的質(zhì)量”分為三方面：①為補(bǔ)充輸入?yún)?shù)所付出的代價；②所得定制方案的適應(yīng)度（QoS水平）；③二者的綜合。需求提供的輸入越少、期望輸出越多、期望QoS水平越高，則表明該需求越“苛刻”，直觀可知SN滿足該需求的能力就越低、所付出的代價也就越高。

圖6給出了對具有不同輸入?yún)?shù)數(shù)目的多個需求進(jìn)行服務(wù)網(wǎng)絡(luò)定制的解質(zhì)量變化情況。這些需求除了輸入?yún)?shù)數(shù)目不同，所期望的輸出參數(shù)和QoS水平均相同。由圖6a可以看出，針對輸入?yún)?shù)較多的需求，無需補(bǔ)充很多輸入?yún)?shù)，為此所需付出的成本（AddedCost）較低；隨著輸入?yún)?shù)的逐漸減少，需要補(bǔ)充越來越多的輸入?yún)?shù)，故AddedCost呈階梯跳躍上升的狀態(tài)。之所以出現(xiàn)這種現(xiàn)象，是因為當(dāng)某個需求缺少了某個關(guān)鍵輸入?yún)?shù)后，很多原本可以參與定制的服務(wù)節(jié)點不再可用，不得不集中補(bǔ)充若干輸入?yún)?shù)，故成本出現(xiàn)跳躍上升。

對解的適應(yīng)度（fitness）來說，則呈現(xiàn)出一種“平穩(wěn)—上升—下降”的趨勢。這仍然是由補(bǔ)充輸入?yún)?shù)造成的：隨著輸入?yún)?shù)的減少，網(wǎng)絡(luò)中出現(xiàn)了一部分失效服務(wù)節(jié)點，而由于新補(bǔ)充了某些輸入?yún)?shù)，最終形成的定制方案中無需包含那些失效的服務(wù)節(jié)點，而是選擇其他更有效用的服務(wù)節(jié)點，故定制方案中包含的服務(wù)節(jié)點較原來變少，解的質(zhì)量上升；而當(dāng)可提供的輸入?yún)?shù)更少時，越來越多的服務(wù)節(jié)點都需要補(bǔ)充輸入?yún)?shù)，算法會再次傾向于生成包含較多服務(wù)節(jié)點的定制方案，解的質(zhì)量下降。

圖6b是將Fitness和AddedCost綜合在一起之后形成的綜合性能曲線。由此可以看出，隨著需求提供的輸入?yún)?shù)數(shù)量的下降，整體性能呈現(xiàn)一種階梯下降的趨勢。

圖7給出了針對具有不同輸出參數(shù)數(shù)目的多個需求的解質(zhì)量的變化情況。這些需求除了輸出參數(shù)的數(shù)目不同，其所提供的輸入?yún)?shù)和QoS水平均相同。該結(jié)果表明：需求的輸出參數(shù)越多，需要補(bǔ)充的輸入?yún)?shù)就越多，所需成本上升，解的質(zhì)量下降。

圖8展示了解的質(zhì)量受需求的QoS嚴(yán)格程度影響的曲線，隨著橫軸所表示的QoS需求越來越嚴(yán)格，SN滿足它的能力變得越來越弱，算法求解得到的最優(yōu)定制方案的質(zhì)量逐漸下降。

綜合上述實驗結(jié)果可知，個性化需求的苛刻程度對定制結(jié)果的質(zhì)量有較大影響。

5.3 實驗2：服務(wù)網(wǎng)絡(luò)特征對定制結(jié)果的影響

本實驗用來驗證SN特征對定制結(jié)果質(zhì)量的影響。選擇1個特定的需求和多個SN，分別利用算法求解，以分析具有不同結(jié)構(gòu)特征的SN滿足同一需求的定制方案質(zhì)量變化情況。這里“SN的結(jié)構(gòu)特征”分為三方面：①包含多源參數(shù)的數(shù)量；②包含服務(wù)節(jié)點的數(shù)量；③包含復(fù)合服務(wù)節(jié)點的數(shù)量。解的質(zhì)量也分為三方面：①為補(bǔ)充輸入?yún)?shù)所付出的代價；②所得定制方案的適應(yīng)度；③二者的綜合。SN包含的多源邊越多、服務(wù)節(jié)點越多、復(fù)合服務(wù)節(jié)點越多，意味著SN的可定制能力越強(qiáng)，滿足需求的能力就越高，但定制時的搜索空間也越大。

圖9給出了解的質(zhì)量（fitness）和算法執(zhí)行時間（execution time）隨多源參數(shù)數(shù)目變化的趨勢。隨著SN中包含的多源參數(shù)越來越多，在進(jìn)行ABC搜索時的解空間越來越大，需要迭代的次數(shù)就越多，故執(zhí)行時間呈上升趨勢。同時，多源參數(shù)的增多為定制提供了更多可能，故SN滿足需求的能力也在提升，fitness上升。

圖10a展示了解的質(zhì)量（fitness，AddedCost）隨SN服務(wù)節(jié)點數(shù)目增加的變化趨勢?？梢钥闯?，隨著節(jié)點數(shù)目的增加，為滿足需求所需補(bǔ)充的輸入?yún)?shù)會逐漸下降，從而降低額外成本。但從fitness的變化看，定制方案滿足需求的水平呈先上升后下降的趨勢，這是因為：在SN規(guī)模較小時，為滿足需求需要補(bǔ)充更多的輸入?yún)?shù)，并且隨著SN規(guī)模的增大，補(bǔ)充輸入?yún)?shù)后找到的定制方案的質(zhì)量也越來越好；當(dāng)SN的規(guī)模越來越大時，代表著SN滿足需求的能力逐漸提高，需要客戶在需求中補(bǔ)充的輸入?yún)?shù)逐漸減少，算法逐步傾向于使用SN本身所提供的越來越豐富的服務(wù)節(jié)點來滿足需求。根據(jù)算法的設(shè)計思路可知，通過補(bǔ)充輸入?yún)?shù)來滿足需求時，算法傾向于尋求增加那些以最簡單的方式滿足需求的輸入?yún)?shù)，故定制方案的復(fù)雜度可保持較低，使用更少的服務(wù)節(jié)點即可滿足需求，解的QoS質(zhì)量較高；而若使用SN本身的服務(wù)來滿足需求，則算法不得不在SN自身結(jié)構(gòu)的限定下進(jìn)行搜索，所形成的定制方案結(jié)構(gòu)可能會相對復(fù)雜，從而影響解的全局QoS，其質(zhì)量變得稍差。但從圖上可以看出，解質(zhì)量的降低程度并不十分明顯，并且在SN的服務(wù)節(jié)點數(shù)目達(dá)到一定程度后即保持穩(wěn)定。

圖10b是解的綜合性能（global performance）和算法執(zhí)行時間（execution time）的變化趨勢。綜合性能呈現(xiàn)逐漸上升的趨勢，意味著SN中服務(wù)節(jié)點的數(shù)目對定制結(jié)果具有一定的正相關(guān)性，服務(wù)節(jié)點越多，SN的定制能力也越高。從算法執(zhí)行時間看，整體上也處于上升的趨勢，這表明服務(wù)節(jié)點數(shù)目增大了搜索空間，從而降低了算法效率。

圖11給出了定制方案質(zhì)量和算法執(zhí)行時間隨SN中復(fù)合服務(wù)節(jié)點數(shù)目增加的變化趨勢。從該圖可以看出，二者整體上均呈現(xiàn)非常緩慢的上升趨勢。這意味著復(fù)合服務(wù)節(jié)點并未顯著地增加服務(wù)網(wǎng)絡(luò)的定制能力，也沒有使算法搜索空間得到較大擴(kuò)展，故執(zhí)行時間不會有太大惡化。由此可得結(jié)論：在SN的各項結(jié)構(gòu)指標(biāo)中，服務(wù)節(jié)點數(shù)目和多源參數(shù)數(shù)目更影響SN的定制能力，而復(fù)合節(jié)點數(shù)目對SN定制能力的影響則相對較低。

分析原因在于：復(fù)合服務(wù)節(jié)點屬于一種局部可配置點，它只能改變定制方案某個局部的QoS，卻無法影響定制方案整體的結(jié)構(gòu)。而服務(wù)節(jié)點和多源參數(shù)則是從全局角度對定制方案的結(jié)構(gòu)起到了很大的作用。這也意味著為了提升SN的定制能力，首先應(yīng)豐富其服務(wù)節(jié)點和節(jié)點之間的邊，其次考慮為每個服務(wù)節(jié)點增加其他候選服務(wù)。

6 結(jié)束語

針對客戶的個性化需求，如何從包含多個可定制點的服務(wù)網(wǎng)絡(luò)中派生出與客戶需求距離最近的定制方案，是本文解決的核心問題。問題求解分為三個階段，分別采用啟發(fā)式方法和ABC方法進(jìn)行優(yōu)化求解，在有限時間內(nèi)尋求近似最優(yōu)解。實驗分析得到的結(jié)論是：①需求的苛刻程度對服務(wù)網(wǎng)絡(luò)定制的性能有較大影響：需求越苛刻，對服務(wù)網(wǎng)絡(luò)進(jìn)行定制的代價就越大、所獲得的定制結(jié)果質(zhì)量越低；②服務(wù)網(wǎng)絡(luò)的結(jié)構(gòu)特性對其定制性能有不同的影響：多源參數(shù)越多、服務(wù)節(jié)點越多、服務(wù)網(wǎng)絡(luò)的滿足需求的可定制能力就越強(qiáng)，而復(fù)合服務(wù)節(jié)點的數(shù)量對其定制能力的影響則不明顯。該結(jié)論可對現(xiàn)實中服務(wù)組織規(guī)劃和提供自己的服務(wù)網(wǎng)絡(luò)具有參考價值，傾向于將有限的成本用于增加服務(wù)網(wǎng)絡(luò)可定制能力。

本文的研究具有實際應(yīng)用價值。由于客戶的需求越來越傾向于大粒度和跨領(lǐng)域性，為滿足需求所構(gòu)造的服務(wù)方案也必然需要集成多個跨領(lǐng)域的服務(wù)以形成服務(wù)網(wǎng)絡(luò)，需要在其上進(jìn)行快速準(zhǔn)確的個性化定制。典型實例是智能交通領(lǐng)域的交通應(yīng)急救援服務(wù)網(wǎng)絡(luò)，涉及城市交通監(jiān)控、交警、消防、醫(yī)院救護(hù)、環(huán)衛(wèi)和特種物品處置等多個服務(wù)領(lǐng)域，在面對突發(fā)交通意外時，如何快速對其進(jìn)行定制，選擇最優(yōu)服務(wù)投入運(yùn)作，是現(xiàn)實交通服務(wù)中真實面臨的挑戰(zhàn)。在制造服務(wù)、物流服務(wù)等其他生產(chǎn)服務(wù)領(lǐng)域，這種問題場景普遍存在。

［1］ HATZI O，VRAKAS D，BASSILIADES N，et al.The PORSCE II framework：using AI planning for automated semantic Web service composition［J］.The Knowledge Engineering Review，2013，28（2）：137-156.

［2］ ALRIFAI M，RISSE T，NEJDL W.A hybrid approach for efficient Web service composition with end-to-end QoS constraints［J］.ACM Transactions on the Web，2012，6（2）：1-31.

［3］ WANG Z，XU X.Mass customization oriented and cost-effective service network［J］.Lecture Notes in Business Information Processing，2013，144：172-185.

［4］ SILVEIRAA G D，BORENSTEINB D，F(xiàn)OGLIATTOC F S.Mass customization：literature review and research directions［J］.International Journal of Production Economics，2001，72（1）：1-13.

［5］ HALLSTEINSEN S，HINCHEY M，PARK S，et al.Dynamic software product lines［J］.IEEE Computer，2008，41（4）：93-95.

［6］ HU B，MA Y，ZHANG LJ，et al.A CCRA based mass customization development for cloud services［C］／／Proceedings of International Confrence on Service Computing.Washington，D.C.，USA：IEEE，2013：705-712.

［7］ DAN Bin，JING Youguo，SUN Min，et al.Intelligent need acquisition approach for heterogeneous customers under online mass customization［J］.Computer Integrated Manufacturing Systems，2012，18（1）：15-24（in Chinese）.［但 斌，經(jīng)有國，孫敏，等.在線大規(guī)模定制下面向異質(zhì)客戶的需求智能獲取方法［J］.計算機(jī)集成制造系統(tǒng)，2012，18（1）：15-24.］

［8］ SUN C，ROSSING R，SINNEMA M，et al.Modeling and managing the variability of Web service-based systems［J］.Journal of Systems and Software，2010，83（3）：502-516.

［9］ LIANG Q，WU X，PARK EK，et al.Ontology-based business process customization for composite Web services［J］.IEEE Transactions on Systems，Man and Cybernetics，Part A：Systems and Humans，2011，41（4）：717-729.

［10］ HADAYTULLAH H，KOSKIMIES K，SYSTA T.Using model customization for variability management in service compositions［C］／／Proceedings of International Confrence on Web Service. Washington，D.C.， USA：IEEE，2009：687-694.

［11］ NGUYEN T，COLMAN A，HAN J.Modeling and managing variability in process-based service compositions.serviceoriented computing［J］.Lecture Notes in Computer Science，2011，7084：404-420.

［12］ SUN W，ZHANG X，GUO C J，et al.Software as a service：configuration and customization perspectives［C］／／Proceedings of IEEE Congress on Services PartⅡ.Washington，D.C.，USA：IEEE，2008：18-25.

［13］ LIANG Q X，CHEN S Z，F(xiàn)ENG Z Y.Application of services relation tracing to automated Web service composition［J］.Applied Mathematics ＆Information Sciences，2013，7（S1）：243-251.

［14］ WANG Z，XU F，XU X.A cost-effective service composition method for mass customized QoS requirements［C］／／Proceedings of International Confrence on Service Computing.Washington，D.C.，USA：IEEE，2012：194-201.

［15］ HUANG K M，F(xiàn)AN Y S，TAN W.An empirical study of programmable web：a network analysis on a service-mashup system［C］／／Proceeding of International Confrence on Web Service.Washington，D.C.，USA：IEEE，2012：552-559.

［16］ TAO F，GUO H，ZHANG L，et al.Modelling of combinable relationship-based composition service network and the theoretical proof of its scale-free characteristics［J］.Enterprise Information Systems，2012，6（4）：373-404.

［17］ HWANG J，ALTMANN J，KIM K.The structural evolution of the Web 2.0service network［J］.Online Information Review，2009，33（6）：1040-1057.

［18］ CHEN W，PAIK I，HUANG P C K.Constructing aglobal social service network for better quality of Web service discovery［J］.IEEE Transactions on Services Computing，2015，8（2）：284-298.

［19］ JUNG J J.Service chain-based business alliance formation in service-oriented architecture［J］.Expert Systems with Applications，2011，38（3）：2206-2211.

［20］ MAAMAR Z，HACID H，HUHNS M N.Why Web services need social networks［J］.IEEE Internet Computing，2011，15（2）：90-94.

［21］ KIL H，OH S C，ELMACIOGLU E，et al.Graph theoretic topological analysis of Web service networks［J］.World Wide Web，2009，12（3）：321-343.

［22］ ZHENG H，ZHAO W，YANG J，BOUGUETTAYA A.QoS analysis for web service compositions with complex structures［J］.IEEE Transactions on Services Computing，2013，6（3）：373-386.

［23］ WANG X，WANG Z，XU X.An improved artificial bee colony approach to QoS-aware service selection［C］／／Proceedings of International Confrence on Web Service.Washington，D.C.，USA：IEEE，2013：395-402.