基于需求/服務(wù)模式的大規(guī)模個性化網(wǎng)絡(luò)服務(wù)定制方法

陳春榮，何 霆+，廖永新，李海波，黃雙喜

(1.華僑大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，福建 廈門 361021；2.清華大學(xué) 國家CIMS工程技術(shù)研究中心，北京 100084)

1 問題的提出

服務(wù)互聯(lián)網(wǎng)環(huán)境[1]下，服務(wù)組合優(yōu)化技術(shù)是實現(xiàn)服務(wù)體系正常運(yùn)營的方法，它將分散的、相互獨(dú)立的、由不同提供者提供的多項服務(wù)通過某種合適的方式整合在一起，形成新的大粒度的服務(wù)業(yè)務(wù)并向外提供。對計算機(jī)而言，其執(zhí)行該類任務(wù)的過程一般是通過基于智能規(guī)劃理論的服務(wù)組合優(yōu)化算法來實現(xiàn)。算法處理步驟一般是先對服務(wù)和用戶需求進(jìn)行預(yù)處理和形式化轉(zhuǎn)化；然后，從已有服務(wù)出發(fā)挖掘其隱含的邏輯或業(yè)務(wù)關(guān)系，為服務(wù)發(fā)現(xiàn)和復(fù)雜的服務(wù)組合準(zhǔn)備更大粒度的素材，降低服務(wù)組合的復(fù)雜度；最后，逐步將用戶需求分解為服務(wù)可執(zhí)行的功能單位，進(jìn)而從互聯(lián)網(wǎng)上找到相應(yīng)的服務(wù)，并對其進(jìn)行編排形成服務(wù)業(yè)務(wù)系統(tǒng)，從而滿足用戶需求[2]?，F(xiàn)有服務(wù)組合優(yōu)化算法主要從服務(wù)功能和服務(wù)質(zhì)量兩方面來進(jìn)行[3-6]。功能方面的服務(wù)組合優(yōu)化算法主要運(yùn)用自動發(fā)現(xiàn)和流程規(guī)劃等技術(shù)手段來匹配用戶的功能需求[7]。這些方法大多采用智能演化算法來編排可用服務(wù)，算法的主要優(yōu)化目標(biāo)是提高需求與服務(wù)在功能上的匹配度；在服務(wù)質(zhì)量方面，主要是進(jìn)行基于服務(wù)質(zhì)量(Quality of Service，QoS)感知的服務(wù)選擇[8-9]。這些方法在一定條件下可以選出最佳的組合服務(wù)，但大都從用戶需求一側(cè)出發(fā)，沒有考慮服務(wù)提供者的成本問題，甚至可能造成成本無效[10]。成本無效在本文中是指服務(wù)提供者獲得的收入小于其提供組合服務(wù)所付出的成本。在正常的服務(wù)系統(tǒng)中，只有兼顧用戶和服務(wù)提供商的利益才能維護(hù)服務(wù)體系的正常運(yùn)行，否則這種狀態(tài)注定無法持續(xù)。

如今也有一些研究者開始關(guān)注服務(wù)收益問題，文獻(xiàn)[11-12]借鑒交易市場中的商品定價機(jī)制，通過對服務(wù)解決方案中成員服務(wù)的按需定價，保證在服務(wù)組合過程中最大化服務(wù)提供者的收益。文獻(xiàn)[13-14]分別在在動態(tài)定價和靜態(tài)定價環(huán)境下，提出了一種劃分選擇的服務(wù)選擇方法。這些方法在面對單一用戶需求時收益效果較好，但不適用于大規(guī)模用戶需求環(huán)境。典型的大規(guī)模整合型服務(wù)應(yīng)用面向特定領(lǐng)域匯集海量的服務(wù)資源和用戶需求，使得相同或者相似的用戶需求得以在短時間內(nèi)大量、持續(xù)地出現(xiàn)，從而表現(xiàn)出大規(guī)模、個性化的特征。

為了實現(xiàn)大規(guī)模用戶需求環(huán)境下的成本有效性，一個服務(wù)解決方案不應(yīng)該只針對一個用戶需求。實現(xiàn)服務(wù)解決方案以及單個原子服務(wù)的復(fù)用可能給服務(wù)提供者帶來更大的收益。文獻(xiàn)[15]在大規(guī)模用戶需求的環(huán)境下，從服務(wù)收益出發(fā)采用一種漸進(jìn)迭加的策略來優(yōu)化服務(wù)提供者的利益。文獻(xiàn)[16-17]采用服務(wù)網(wǎng)絡(luò)的方法來實現(xiàn)大規(guī)模服務(wù)定制，這些方法都是單純從服務(wù)功能或者服務(wù)質(zhì)量出發(fā)，不能完全體現(xiàn)用戶需求的個性化主張，同時算法在海量用戶需求環(huán)境下的服務(wù)定制效率有待提高。特別是平臺整合型應(yīng)用(如美團(tuán)、攜程)的興起，使得服務(wù)解決方案定制效率問題進(jìn)一步突顯。為了提高服務(wù)定制的效率，基于文獻(xiàn)[18]中需求模式和服務(wù)模式的概念，本文使用需求模式來代替多個子需求，縮減問題規(guī)模；使用服務(wù)模式整合多個原子服務(wù)，構(gòu)建大粒度的服務(wù)流程，減小服務(wù)搜索空間。

在服務(wù)解決方案構(gòu)造過程中，用戶支付費(fèi)用一定的情況下，超過用戶需求服務(wù)質(zhì)量約束的解決方案不會給提供者帶來額外收益。服務(wù)的服務(wù)質(zhì)量越高，價格越高。如圖1所示為服務(wù)解決方案質(zhì)量與服務(wù)成本以及收益的關(guān)系。圖1中實線代表服務(wù)解決方案成本與服務(wù)質(zhì)量的變化，虛線代表服務(wù)提供者獲得的收入與服務(wù)質(zhì)量的變化。由圖1可以看出，追求服務(wù)解決方案服務(wù)質(zhì)量最優(yōu)不能給服務(wù)提供者帶來最大收益。因此，在服務(wù)組合過程中，一方面在用戶需求約束下保障用戶價值的實現(xiàn)，一方面優(yōu)化服務(wù)提供者的利益是保證服務(wù)系統(tǒng)能夠正常運(yùn)行的關(guān)鍵。

特別的，筆者曾提出一種基于模式的個性化服務(wù)定制方法來解決服務(wù)定制的效率問題[18]。但該方法僅面向單用戶需求，不適用于大規(guī)模用戶需求環(huán)境，同時也沒有考慮服務(wù)成本問題。有鑒于此，本文在此基礎(chǔ)上提出一種基于需求/服務(wù)模式的大規(guī)模個性化網(wǎng)絡(luò)服務(wù)定制方法，該方法不但使用具有先驗知識、經(jīng)過歷史數(shù)據(jù)驗證的需求模式和服務(wù)模式、以及可以復(fù)用的服務(wù)網(wǎng)絡(luò)來提升服務(wù)定制的效率，而且還可以從服務(wù)提供者和用戶雙方的角度來實現(xiàn)用戶服務(wù)價值—供應(yīng)商服務(wù)成本的均衡優(yōu)化。

2 問題定義

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

服務(wù)網(wǎng)絡(luò)(service network)是將分散在互聯(lián)網(wǎng)和現(xiàn)實中的各類服務(wù)(e-Service、人工服務(wù)、信息、資源等)按特定方式連接形成的網(wǎng)絡(luò)，彼此之間通過特定的協(xié)同與互操作協(xié)議進(jìn)行交互[16]。服務(wù)網(wǎng)絡(luò)不是針對單個用戶需求的，而是面向大規(guī)模用戶需求的。圖2顯示了一個服務(wù)網(wǎng)絡(luò)的示例，在服務(wù)網(wǎng)絡(luò)中主要包含4個部分：輸入?yún)?shù)、輸出參數(shù)、具體的服務(wù)以及它們之間的有向邊。

在服務(wù)網(wǎng)絡(luò)中，對于給定的用戶需求，可以對用戶需求定制個性化的服務(wù)解決方案。在滿足用戶需求功能約束和服務(wù)質(zhì)量約束下，服務(wù)網(wǎng)絡(luò)中一個服務(wù)子網(wǎng)代表了一種服務(wù)解決方案。對于一個用戶需求，服務(wù)網(wǎng)絡(luò)中可能存在不同的服務(wù)子網(wǎng)都滿足當(dāng)前需求。例如在圖2中對于服務(wù)節(jié)點(diǎn)s6,存在著3條有向邊均傳遞參數(shù)p4到服務(wù)s6，在最終的服務(wù)解決方案定制中只需要選擇一條有向邊。

2.2 問題定義

下面對本文提出的候選服務(wù)，服務(wù)模式，用戶需求以及需求模式做出形式化定義，并提出本文算法的優(yōu)化目標(biāo)。

(1)候選服務(wù)與服務(wù)模式

定義服務(wù)網(wǎng)絡(luò)中一個具體服務(wù)si為si={Ii,Oi,Qi,Pi,NCi}。其中：Ii,Oi分別代表服務(wù)的輸入?yún)?shù)和輸出參數(shù)。Qi代表服務(wù)的服務(wù)質(zhì)量集，Qi={Ai,Ei,Ti,}。Ai代表服務(wù)可用性即服務(wù)請求成功的數(shù)量/所有請求數(shù)量，Ei代表服務(wù)可靠性即服務(wù)正常運(yùn)行時間/總運(yùn)行時間[5]。Ti為服務(wù)響應(yīng)時間，Pi代表服務(wù)價格，NCi是用戶與服務(wù)提供商關(guān)于服務(wù)的協(xié)商成本。

服務(wù)網(wǎng)絡(luò)中一個服務(wù)模式被定義為sp=(spin,spout,spq,spp,spnc)。服務(wù)模式代表從一定規(guī)模的歷史服務(wù)記錄中抽取出來的頻繁出現(xiàn)的完整/部分服務(wù)組合[18]。例如在旅游團(tuán)中，旅行社會為用戶提供一個完整的旅行服務(wù)套餐，服務(wù)套餐中的這些服務(wù)在歷史服務(wù)方案中經(jīng)常以一定的順序頻繁出現(xiàn)。本文對這些高頻使用的服務(wù)流程進(jìn)行分析和挖掘，從而形成服務(wù)模式。spin，spout分別代表服務(wù)模式的功能輸入和輸出；spq代表服務(wù)模式的各項性能參數(shù)，spq=(spA,spE,spT)，spA,spE,spT分別代表服務(wù)模式的可用性，可靠性以及響應(yīng)時間；spp代表服務(wù)模式價格；spnc代表服務(wù)模式的協(xié)商成本。spq,spp,spnc三者性能指標(biāo)可由工作流聚合函數(shù)根據(jù)服務(wù)流程計算得出。

(2)用戶需求與需求模式

需求模式rp定義為rp=(rpin,rpout,rpq,rpp)。需求模式rp代表在多個歷史需求中抽取出來的頻繁連續(xù)的需求片段[18]。例如在用戶旅行需求中，用戶在預(yù)定機(jī)票的同時，通常需要預(yù)定酒店，本文將這種經(jīng)常一起出現(xiàn)的連續(xù)需求片段刻畫為需求模式。其中：rpin表示需求模式期望輸入?yún)?shù)，rpout表示需求模式輸出參數(shù)，rpq表示需求模式的服務(wù)質(zhì)量約束水平，rpp表示需求模式被滿足時支付的費(fèi)用。

(3)優(yōu)化目標(biāo)

在處理大規(guī)模用戶需求中，服務(wù)提供者所獲得的收入為滿足用戶需求時用戶所支付的費(fèi)用。服務(wù)提供者付出的成本主要是服務(wù)提供者提供組合服務(wù)方案所付出的構(gòu)建成本。服務(wù)構(gòu)建成本由服務(wù)資源提供成本以及協(xié)商成本決定。因此，服務(wù)提供者獲得的利益為收入與構(gòu)建成本的差值，計算公式如下：

(1)

(2)

式中：CC表示服務(wù)的總構(gòu)建成本；Pi表示服務(wù)資源提供成本，當(dāng)服務(wù)被用來滿足多個用戶需求時，Pi應(yīng)該計算多次；|SRi|表示服務(wù)si參與滿足用戶需求的次數(shù)；NC代表服務(wù)構(gòu)建成本中的總服務(wù)協(xié)商成本，

(3)

式中：NC表示服務(wù)的協(xié)商成本，服務(wù)協(xié)商成本是服務(wù)提供者之間就服務(wù)使用方式以及使用時間達(dá)成一致所需付出的成本；u代表服務(wù)網(wǎng)中單位節(jié)點(diǎn)的維護(hù)成本；|SN|代表服務(wù)網(wǎng)絡(luò)中總的服務(wù)節(jié)點(diǎn)數(shù)。

綜上所述，本文的優(yōu)化目標(biāo)函數(shù)為最大化Rev-CC。

3 服務(wù)網(wǎng)絡(luò)構(gòu)建方法

3.1 服務(wù)網(wǎng)絡(luò)構(gòu)建

本文采用一種迭代增強(qiáng)的策略來構(gòu)建服務(wù)網(wǎng)絡(luò)，對于每個用戶需求，可以通過定制服務(wù)網(wǎng)絡(luò)中的具體服務(wù)子網(wǎng)來生成滿足用戶需求的服務(wù)解決方案。方法中首先對大規(guī)模用戶需求進(jìn)行排序，然后依次處理各用戶需求。在處理當(dāng)前用戶需求時首先利用ORSC(requirement oriented service composition)算法尋找基于服務(wù)模式構(gòu)建的服務(wù)解決方案，同時檢查當(dāng)前服務(wù)網(wǎng)絡(luò)中是否存在一個服務(wù)子網(wǎng)滿足當(dāng)前需求。若服務(wù)網(wǎng)絡(luò)中不存在服務(wù)子網(wǎng)滿足當(dāng)前需求，則采用ORSC算法中利用服務(wù)模式構(gòu)建的服務(wù)解決方案，并將其融入服務(wù)網(wǎng)絡(luò)中；若服務(wù)網(wǎng)絡(luò)存在服務(wù)子網(wǎng)滿足當(dāng)前用戶需求，比較兩種方案的成本，采用具有較低成本的服務(wù)解決方案。

算法1服務(wù)網(wǎng)絡(luò)構(gòu)建算法SN_CT。

輸入:CS, R；

輸出:SN, SR,{CNi}。

1.R←Sort(R)

2.if n=1

3.SN(n)←ORSC(r,CS),CNn=SN(n)

4.Else

5.SN(n-1)=SN_CT(R/rn,CS)

8.soln←ORSC(r,CS)

12.Else

13.SN(n-1)←soln

14.SN(n)←merge(SN(n), SN(n-1))

15.return

3.2 基于服務(wù)水平協(xié)議的用戶需求排序

在大規(guī)模的用戶需求中，存在著大量功能相似但性能不同的需求。用戶需求處理順序的不同會給服務(wù)提供者帶來不同的收益。根據(jù)用戶需求的服務(wù)質(zhì)量約束對應(yīng)的服務(wù)水平協(xié)議對用戶需求進(jìn)行排序，可以得到按照降序排列的用戶需求集R。從而在處理用戶需求時可以盡可能實現(xiàn)原子服務(wù)的復(fù)用，達(dá)到優(yōu)化服務(wù)提供者利益的目的。

服務(wù)水平協(xié)議集[19]SetSLA={SLA1,SLA2,..SLAn}，對于每一個服務(wù)水平協(xié)議，Qsetn為服務(wù)水平協(xié)議對應(yīng)的服務(wù)質(zhì)量標(biāo)準(zhǔn)集合，Qsetn={qn1,qn2,..,qnk}。本文選取的服務(wù)指標(biāo)有服務(wù)可用性、可靠性和響應(yīng)時間，故k=3。確定用戶需求所屬的服務(wù)水平協(xié)議后，定義各服務(wù)水平協(xié)議之間的質(zhì)量優(yōu)劣關(guān)系，構(gòu)造一個服務(wù)質(zhì)量關(guān)系圖，這是一個有向無環(huán)圖，如圖3所示。

在圖3中對于任意一條邊相鄰的兩個頂點(diǎn)，出度節(jié)點(diǎn)代表的服務(wù)質(zhì)量約束優(yōu)于入度節(jié)點(diǎn)。同一層中不直接相鄰的兩個頂點(diǎn)代表的服務(wù)質(zhì)量約束關(guān)系是一種不等關(guān)系。例如在圖3中，對于SLA1和SLA2兩個頂點(diǎn)，SLA1代表的服務(wù)質(zhì)量標(biāo)準(zhǔn)集Qset1優(yōu)于SLA2代表的服務(wù)質(zhì)量標(biāo)準(zhǔn)集Qset2。同時Qset1與Qset2存在以下關(guān)系:

(4)

式中：>表示優(yōu)于符號，對于正向Qos屬性指標(biāo)，表示q1i大于q2i，對于負(fù)向的Qos屬性指標(biāo)表示q1i小于q2i。

對于同一層中的SLA2和SLA3兩個節(jié)點(diǎn)，所代表的服務(wù)質(zhì)量標(biāo)準(zhǔn)集是一種不等關(guān)系，如式(5)所示：

(5)

通過構(gòu)造一個服務(wù)質(zhì)量關(guān)系圖，可以得到各用戶需求服務(wù)質(zhì)量的相對優(yōu)劣關(guān)系。通過服務(wù)質(zhì)量關(guān)系圖廣度優(yōu)先遍歷節(jié)點(diǎn)時，可以得到按照降序排列的用戶需求集R。

3.3 面向個性化需求的服務(wù)定制算法

本節(jié)將介紹SN_CT算法中所使用的面向個性化需求的服務(wù)定制算法ORSC算法[18]。算法中首先利用頻繁模式挖掘算法FP-growth[20]，基于一定規(guī)模的歷史數(shù)據(jù)集，構(gòu)建面向領(lǐng)域/跨領(lǐng)域的需求模式庫和服務(wù)模式庫，并建立雙邊模式映射匹配概率。然后，對于用戶的個性化需求，利用遺傳算法在需求模式庫中找到最佳的需求模式集來代替當(dāng)前用戶需求。如果需求模式集為空，則代表沒有任何的先驗知識可用于當(dāng)前需求，傳統(tǒng)的擴(kuò)展多目標(biāo)演化算法(Extended Multi-Objective Evolutionary Algorithm, EDMOEA)[5]將被調(diào)用，以此生成服務(wù)解決方案。最后,對于代替當(dāng)前用戶需求的需求模式集，利用建立的需求模式和服務(wù)模式之間的匹配概率來尋找最佳的服務(wù)模式集，并以此生成滿足當(dāng)前需求的服務(wù)解決方案。當(dāng)服務(wù)模式生成的服務(wù)解決方案不能完全滿足用戶需求時，對于缺失的服務(wù)節(jié)點(diǎn)，從成本出發(fā)選擇最佳的候選服務(wù)與原有服務(wù)模式相結(jié)合來生成完整的服務(wù)解決方案。算法2詳細(xì)闡述了ORSC算法的步驟。

算法2面向個性化需求的服務(wù)定制算法ORSC。

輸入：ri,HR, HS；

輸出：solni。

1.PR, SP←FP-growth(HR,HS)

2.map←match(RP,SP)

3.RPi←cover(ri,RP)

4.if RPi=?

5. solni=EDMOEA(ri,CS)

6.else

7. RPi←GA(RPi)

8.SPi←FindSP(map,RPi,SP)

9.solni←combine(SPi)

10.return

算法的輸入為需求ri，歷史需求集HR以及歷史服務(wù)解決方案記錄集HS，算法輸出為根據(jù)用戶需求約束定制的個性化服務(wù)解決方案solni。算法中第1行利用頻繁模式挖掘算法FP-growth構(gòu)建需求/服務(wù)模式庫。第2行利用match函數(shù)建立了需求模式與服務(wù)模式的匹配關(guān)系。第3行從需求模式庫中找到能夠覆蓋用戶需求的需求模式集RPi。如果需求模式集RPi為空，代表當(dāng)前用戶需求沒有任何歷史先驗知識可用，算法將調(diào)用傳統(tǒng)的服務(wù)組合方法EDMOEA生成服務(wù)解決方案。最后算法利用FindSP函數(shù)找到需求模式集對應(yīng)的最佳服務(wù)模式集來生成個性化服務(wù)解決方案。

3.3.1 需求模式/服務(wù)模式映射

如圖4所示，利用模式挖掘算法可以從一定規(guī)模的歷史需求和對應(yīng)的服務(wù)解決方案中挖掘出需求模式和服務(wù)模式，之后建立雙邊模式之間的匹配概率。需求模式和服務(wù)模式間的匹配概率主要考慮以下兩個因素：

(1)先驗知識 先驗知識體現(xiàn)了在歷史服務(wù)請求及其服務(wù)解決方案中，服務(wù)模式spj滿足需求模式rpi的概率，這個概率是從一定規(guī)模的歷史數(shù)據(jù)中抽象出的經(jīng)驗知識。可以使用樸素貝葉斯定理來進(jìn)行表示，如式(6)所示：

(6)

式中:p(spj)=sp+/n，n表示歷史數(shù)據(jù)集中服務(wù)解決方案總個數(shù)；sp+表示服務(wù)模式spj在歷史服務(wù)解決方案中出現(xiàn)的總次數(shù)；p(rpi)=rp+/n,rp+表示需求模式rpi在歷史服務(wù)請求中出現(xiàn)的總次數(shù)；p(spj/rpi)=c+/rp+,c+表示需求模式rpi與服務(wù)模式spj在歷史服務(wù)請求響應(yīng)記錄中共同出現(xiàn)的次數(shù)。

(2)需求模式與服務(wù)模式的相似性 需求模式與服務(wù)模式的相似性包含了服務(wù)質(zhì)量和服務(wù)功能兩方面，如式(7)所示。式(7)中I表示服務(wù)性能指示函數(shù)，當(dāng)指示函數(shù)I中表達(dá)式為真時，值為1，否則為0；⊕表示服務(wù)性能比較符號，當(dāng)服務(wù)模式spj的服務(wù)性能滿足需求模式rpi的服務(wù)性能約束時，指示函數(shù)I的值為1，否則為0。當(dāng)服務(wù)模式的輸出參數(shù)與需求模式的期望輸出參數(shù)重疊的比例越高時，aij概率值也就越高，從而表示服務(wù)模式spj更容易滿足需求模式rpi。

(7)

由pij和aij兩者指標(biāo)可以得出需求模式rpi和服務(wù)模式spj之間的匹配概率，如式(8)所示，w1和w2分別表示兩個指標(biāo)的權(quán)重，w1與w2的和為1。

s(rpi,spj)=w1pij+w2aij。

(8)

本文中需求模式的先驗分?jǐn)?shù)定義為需求模式與相映射的服務(wù)模式的匹配分?jǐn)?shù)之和，如式(9)所示，需求模式的先驗分?jǐn)?shù)越高，越容易被服務(wù)服務(wù)模式所滿足。

(9)

3.3.2 需求模式集選擇

建立需求模式和服務(wù)模式匹配概率后，對于用戶個性化需求ri，在需求模式庫中利用遺傳算法找到一個最佳的需求模式集RPi來代替用戶需求。遺傳算法的適應(yīng)度函數(shù)主要考慮以下3個指標(biāo)：

(1)考慮服務(wù)收益，互聯(lián)網(wǎng)上存在大量功能相似但服務(wù)性能不同的服務(wù)，通常情況下性能越高的服務(wù)，價格也越高。當(dāng)一個用戶需求被需求模式集所覆蓋時，需求模式集的服務(wù)質(zhì)量約束和用戶需求的服務(wù)質(zhì)量約束越接近越好，從而在需求模式—服務(wù)模式匹配時，不用尋找服務(wù)性能過高的服務(wù)模式，因此式(10)中c1(X)應(yīng)該被最小化。

c1(X)=|riq-q(RPi)|，

(10)

式中q是計算服務(wù)性能指標(biāo)的聚合函數(shù)。

(2)考慮需求模式集RPi和用戶需求ri的期望功能輸出參數(shù)的重疊度，重疊度越大，用戶需求被覆蓋的程度越大，因此式(11)中c2(X)應(yīng)該最大化。

(11)

(3)考慮需求模式的先驗知識,需求模式的先驗分?jǐn)?shù)越高，在需求模式/服務(wù)模式的匹配過程中更容易被服務(wù)模式所滿足，因此式(12)中c3(X)應(yīng)該最大化。

(12)

綜上所述，遺傳算法的適應(yīng)度函數(shù)如式(13)所示，w1，w2，w3分別代表3個指標(biāo)的權(quán)重，權(quán)重值相加為1。

f(X)=w1c1(X)+w2c2(X)+w3c3(X)。

(13)

3.3.3 服務(wù)模式集選擇

在需求模式/服務(wù)模式的雙邊映射匹配中，SPi為需求模式集RPi相映射的服務(wù)模式集。為了找到最佳的服務(wù)模式集來滿足需求模式集RPi，首先利用式(14)找出與需求模式集RPi中每一個需求模式匹配分?jǐn)?shù)最高的服務(wù)模式spi，并將服務(wù)模式spi加入到SPi。

spi=?spj∈SPimaxs(rpi,spj)。

(14)

現(xiàn)實情境中，一個服務(wù)模式往往不能百分之百的滿足一個需求模式，因此大多數(shù)情況下算法需要尋找額外的服務(wù)模式來滿足需求模式集。通過式(15)可以計算出SPi中的每個服務(wù)模式與需求模式集RPi的相關(guān)度，相關(guān)度的大小代表了服務(wù)模式對需求模式集的作用程度，相關(guān)度越大，服務(wù)模式對當(dāng)前需求模式集越有用。

(15)

在計算相關(guān)度時，當(dāng)前服務(wù)模式與SPi中已選擇服務(wù)模式的重疊度對服務(wù)模式的選擇會產(chǎn)生影響，因此算法實際運(yùn)行過程中會設(shè)置一個閾值，將大于指定閾值的服務(wù)模式從SPi中去除掉。算法在每次迭代過程中選擇與需求模式集RPi相關(guān)度最大的服務(wù)模式加入到SPi中，同時設(shè)置閾值a，將相關(guān)度小于閾值a的服務(wù)模式從服務(wù)模式集SPi中過濾掉，算法迭代，直到SPi為空。

4 實驗

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

實驗候選服務(wù)數(shù)據(jù)集采用QWS[1]，WS-DREAM[7]兩個公開的服務(wù)數(shù)據(jù)集。這兩個數(shù)據(jù)集包含了大約6 000個公開的Web服務(wù)，這些服務(wù)來源于搜索引擎門戶網(wǎng)站等。數(shù)據(jù)集中包含了服務(wù)的QoS屬性信息,如服務(wù)價格，可靠性，響應(yīng)時間等。同時可從服務(wù)的 Web服務(wù)描述語言(Web Services Description Language，WSDL)[21]文件中提取服務(wù)的輸入以及輸出參數(shù)。實驗中服務(wù)提供者所獲得的收入為用戶需求被滿足時所支付的費(fèi)用，服務(wù)的構(gòu)建成本由服務(wù)資源提供成本與服務(wù)協(xié)商成本決定。服務(wù)協(xié)商成本為NC，服務(wù)提供商之間每協(xié)商一次都需要付出協(xié)商成本，具體的服務(wù)協(xié)商價格由服務(wù)提供者根據(jù)具體服務(wù)使用場景來確定。

對于大規(guī)模用戶請求集，由于沒有公開的服務(wù)請求集，本文模擬生成3 000個用戶服務(wù)請求。用戶需求通過以下規(guī)則產(chǎn)生。

(1)從公開的服務(wù)集中提取出1 000個輸入輸出參數(shù)，分成20組。從前10組任意選取5～10個參數(shù)作為需求輸入?yún)?shù)，從后10組參數(shù)中選取10～15個參數(shù)作為需求輸出參數(shù)。輸入?yún)?shù)與輸出參數(shù)最多來自3個組。

(2)需求的QoS約束水平即服務(wù)可靠性、可用性以及相應(yīng)時間取值范圍分別是[0.8,1.0],[0.9,1.0],[1,10]。

(3)用戶支付的費(fèi)用價格范圍為[100,1 000],用戶支付費(fèi)用與用戶的服務(wù)質(zhì)量約束水平一致，即需求的QoS屬性越高，用戶愿意支付的費(fèi)用越大。同時需求輸出參數(shù)越多，用戶支付費(fèi)用也會變大。

4.2 實驗結(jié)果與分析

基于上述數(shù)據(jù)，總共進(jìn)行如下3個方面的實驗來驗證文中所提方法的有效性。

實驗1在第一項實驗中比較了服務(wù)網(wǎng)絡(luò)構(gòu)建算法(SN_CT)，EDMOEA[5]，以及智能演化算法(Intellignet Evolutionary Algorithm，IEA)[16]三種算法在處理不同用戶規(guī)模的用戶需求時的收益以及服務(wù)定制效率。實驗中采用了2 000個用戶需求，需求變化個數(shù)從0～2 000。實驗中單個服務(wù)協(xié)商成本設(shè)置在[40,1 000]之間。實驗結(jié)果如圖5和圖6所示。

從圖5可以看到，本文提出的SN_CT算法在處理不同用戶需求規(guī)模時，收益相比傳統(tǒng)的服務(wù)組合算法EDMOEA有很大的優(yōu)勢，同時相比IEA算法，本文算法在處理不同的用戶需求時，在收益方面同樣稍具優(yōu)勢。這是由于SN_CT算法在處理過程中，每次都從成本出發(fā)，在實現(xiàn)服務(wù)復(fù)用的同時每次選擇成本最低的解決方案滿足用戶需求。從圖6可以看出，在執(zhí)行效率方面，本文所提算法相對于IEA以及EDMOEA都有較大的優(yōu)勢，用戶需求的規(guī)模越大，在執(zhí)行效率上本文所提算法的優(yōu)勢越大。這可能是由于SN_CT算法利用了大粒度的服務(wù)模式而不是從原子服務(wù)出發(fā)來構(gòu)造服務(wù)解決方案，從而極大加快了服務(wù)定制效率。

實驗2實驗2中觀察了SN_CT算法在迭代處理不同用戶需求時服務(wù)網(wǎng)絡(luò)成本的變化以及原子服務(wù)復(fù)用度的變化。服務(wù)復(fù)用度是指一個原子服務(wù)參與滿足服務(wù)解決方案的次數(shù)。實驗2中同樣采用了2 000個用戶需求來進(jìn)行實驗，同時實驗中單個服務(wù)協(xié)商成本設(shè)置在[40,1 000]之間。實驗結(jié)果如圖7和圖8所示。

從圖7可以看出，在需求數(shù)量比較少時，服務(wù)成本上升較快，曲線斜率較大。但當(dāng)需求越來越大時，斜率逐漸變小。這表明當(dāng)需求規(guī)模越來越大時，SN_CT算法在滿足每個用戶需求時的平均成本在逐漸減少。這也從側(cè)面證明了本文算法在處理大規(guī)模用戶需求時有較大的優(yōu)勢。從圖8中可以看到，服務(wù)的平均復(fù)用度呈現(xiàn)上升趨勢，這表面文本算法在盡可能地實現(xiàn)服務(wù)復(fù)用，以提高服務(wù)提供者的利益。同時從圖8中可以發(fā)現(xiàn)曲線在某一時刻服務(wù)復(fù)用度的增大趨勢減緩，這有可能是因為服務(wù)網(wǎng)絡(luò)中導(dǎo)入了大量新服務(wù)。

實驗3在此項實驗中觀察了需求的Qos約束水平不同對SN_CT算法的影響。現(xiàn)實服務(wù)場景中可能存在一些極端情況，即一些用戶希望在較少費(fèi)用情況下確期望得到的服務(wù)解決方案具有更高的服務(wù)性能水平或者較高費(fèi)用情況下期望的服務(wù)性能水平卻較低。實驗選取了3組用戶需求，每組包含200個用戶需求。每組用戶需求的期望輸出的功能和支付的費(fèi)用是固定不變的，但每組需求期望的服務(wù)QoS水平是不同的，第一組用戶需求期望QoS水平較低,圖中標(biāo)志為Relaxed，第二組用戶需求期望的QoS水平和費(fèi)用一致,的圖中標(biāo)志為Aligned，第3組用戶需求期望的QoS水平較高,圖中標(biāo)志為Strict。同時,實驗中設(shè)置單個服務(wù)的協(xié)商成本為100。實驗中總共進(jìn)行了下面2個小實驗來觀察需求QoS水平的不同對SN_CT算法的影響。第一個實驗觀察了SN_CT算法在處理三組不同Qos水平的需求時，對服務(wù)收益和成本的影響；第二個實驗觀察了SN_CT算法在處理三組不同Qos水平的需求時，對服務(wù)網(wǎng)絡(luò)復(fù)雜度的影響，圖9和圖10分別顯示了實驗結(jié)果。

從圖9中可以看到當(dāng),用戶需求期望的QoS水平為Relaxed時，收益是最高的，成本是最低的。當(dāng)用戶需求期望的QoS水平為Strict時正好相反。這是由于當(dāng)需求期望的服務(wù)QoS水平很高時，服務(wù)網(wǎng)絡(luò)需要尋找性能更好,價格更高的服務(wù)解決方案來滿足用戶需求，但是由于用戶愿意支付的價格是不變的，故而造成服務(wù)解決方案定制成本的上升而服務(wù)提供者的服務(wù)收益下降。

觀察圖10中SN_CT算法在處理3組需求時服務(wù)網(wǎng)絡(luò)復(fù)雜度的變化。計算了在處理3組需求時，服務(wù)網(wǎng)絡(luò)中所包含的具體服務(wù)以及邊的個數(shù)。從實驗結(jié)果可以看到，隨著需求期望的QoS水平升高，服務(wù)網(wǎng)絡(luò)中包含的原子服務(wù)以及邊的數(shù)量都變化不大，說明用戶需求期望的QoS水平差異對服務(wù)網(wǎng)絡(luò)的復(fù)雜度影響比較有限。

5 結(jié)束語

本文針對大規(guī)模用戶需求環(huán)境下，如何實現(xiàn)成本有效的個性化服務(wù)定制問題，提出了一種基于需求/服務(wù)模式的大規(guī)模個性化網(wǎng)絡(luò)服務(wù)定制方法。在本文所提出的方法中首先根據(jù)用戶需求的服務(wù)質(zhì)量約束對用戶需求進(jìn)行排序，然后采用迭代增強(qiáng)的策略來構(gòu)建服務(wù)網(wǎng)絡(luò)。通過定制服務(wù)網(wǎng)絡(luò)中具體的服務(wù)子網(wǎng)可以生成滿足用戶需求的服務(wù)解決方案，從而可以最大可能地復(fù)用服務(wù)網(wǎng)絡(luò)中的原子服務(wù)，達(dá)到優(yōu)化服務(wù)提供者利益的目的。同時，在服務(wù)網(wǎng)絡(luò)構(gòu)建過程中，算法使用了經(jīng)過大量實踐驗證的需求/服務(wù)模式，從而極大地加快了服務(wù)解決方案的定制速率。最后，在實驗階段，通過將本文提出的算法與IEA，EDMOEA算法進(jìn)行對比，驗證了所提方法的有效性。未來可以進(jìn)一步提高服務(wù)網(wǎng)絡(luò)在面對并發(fā)需求時的服務(wù)定制效率，通過挖掘用戶需求之間的功能相似性關(guān)系，減少算法的調(diào)用次數(shù)，進(jìn)一步提高服務(wù)定制算法的效率；增加對并發(fā)需求的沖突處理。