激勵(lì)機(jī)制下負(fù)載均衡和QoS感知服務(wù)組合方法

劉英， 焦竽鑫， 吳小竹

(福州大學(xué) 數(shù)字中國(guó)研究院(福建)， 福建 福州 350108)

近年來(lái)，隨著Web服務(wù)技術(shù)的快速發(fā)展，越來(lái)越多的Web服務(wù)被發(fā)布到網(wǎng)絡(luò)端實(shí)現(xiàn)共享，使具有相同功能但不同服務(wù)質(zhì)量(QoS)的Web服務(wù)數(shù)量劇增[1].單個(gè)Web服務(wù)由于功能簡(jiǎn)單很難滿足用戶的復(fù)雜需求，QoS感知服務(wù)組合(QSC)研究應(yīng)運(yùn)而生[2].歐陽(yáng)超等[3]結(jié)合模擬退火算法和遺傳算法提出一種新的服務(wù)組合方法，加速解的收斂.馬力等[4]針對(duì)傳統(tǒng)缺乏語(yǔ)義信息支持的Web服務(wù)選擇問(wèn)題，量化QoS屬性并將該問(wèn)題轉(zhuǎn)化為圖搜索問(wèn)題，利用AO*算法求解.Hwang等[5]將QoS作為具有概率質(zhì)量函數(shù)的離散隨機(jī)變量進(jìn)行服務(wù)選擇.Yuan等[6]提出基于自適應(yīng)全局QoS約束分解的動(dòng)態(tài)服務(wù)選擇方法，采用模糊邏輯和文化遺傳算法獲取局部約束組合，縮小服務(wù)的搜索范圍.Alayed等[7]提出改進(jìn)蟻群優(yōu)化算法(EACO)，該方法能有效避免局部最優(yōu)，減少搜索時(shí)間.傳統(tǒng)服務(wù)組合方法容易忽略參與者的競(jìng)爭(zhēng)關(guān)系，部分學(xué)者引入博弈論思想.馬同偉等[8]針對(duì)分配中買(mǎi)賣(mài)雙方的利益問(wèn)題，提出雙向拍賣(mài)資源分配模型，保證雙方在公平公正的環(huán)境中競(jìng)爭(zhēng)和購(gòu)買(mǎi).Wang等[9-10]認(rèn)為在服務(wù)選擇過(guò)程中，參與者具有自私性且不愿完全暴露自己的信息，針對(duì)信息不完整的決策問(wèn)題，考慮Web服務(wù)存在納什均衡競(jìng)爭(zhēng)關(guān)系，提出一種激勵(lì)機(jī)制選擇最優(yōu)Web服務(wù)；并且基于激勵(lì)合同提出一種新的激勵(lì)機(jī)制，在該激勵(lì)機(jī)制中，請(qǐng)求者向提供者提供激勵(lì)合同，根據(jù)提供者對(duì)激勵(lì)合同的反應(yīng)獲取私有信息，不斷迭代直到為每個(gè)任務(wù)均選擇出最優(yōu)服務(wù).激勵(lì)機(jī)制是將博弈論應(yīng)用到服務(wù)組合中的一次大膽且成功的創(chuàng)新，有效地解決了服務(wù)選擇中尋找最優(yōu)解的問(wèn)題，并且對(duì)參與者都有著正向、積極的作用.

在服務(wù)組合過(guò)程中，請(qǐng)求者的主要目的是在滿足其功能需求下獲取具有良好質(zhì)量保障的組合服務(wù)，提供者則需要優(yōu)化QoS和保證負(fù)載均衡[11].傳統(tǒng)服務(wù)選擇策略傾向于選擇QoS更優(yōu)的Web服務(wù)，使該Web服務(wù)的負(fù)載增加.服務(wù)的負(fù)載能力往往是有限的[12]，若達(dá)到最大負(fù)載量后，其QoS可能無(wú)法保證，并且負(fù)載不均會(huì)導(dǎo)致服務(wù)出現(xiàn)過(guò)載或空閑的狀態(tài)，這將影響系統(tǒng)的整體性能.李文中等[13]提出一種自適應(yīng)分布式負(fù)載均衡(LCB)算法，使用負(fù)載容率測(cè)度衡量各服務(wù)副本的負(fù)載狀況.楊石等[14]針對(duì)任務(wù)調(diào)度中的時(shí)間和通信成本問(wèn)題，提出基于蜜蜂覓食行為的負(fù)載均衡(HBB-LB)算法，有效平衡虛擬機(jī)的負(fù)載和響應(yīng)時(shí)間.任金霞等[15]為縮短任務(wù)完成時(shí)間和提高負(fù)載均衡，提出一種具有QoS約束的模擬退火的任務(wù)調(diào)度算法，使參與者的效用均能獲得滿足.Pushpavati等[16]提出一種改進(jìn)最大完成時(shí)間和遷移性能的配對(duì)樹(shù)算法，提高了響應(yīng)時(shí)間、成本、活力和吞吐量等綜合服務(wù)質(zhì)量指標(biāo).Arabinda等[17]提出一種基于改進(jìn)粒子群算法的負(fù)載均衡技術(shù)(LBMPSO)，能夠縮短虛擬機(jī)完工時(shí)間，提高資源的利用率.施凌鵬等[18]提出微服務(wù)鏈感知的請(qǐng)求負(fù)載均衡算法，減少請(qǐng)求響應(yīng)的延遲時(shí)間，平衡主機(jī)間的負(fù)載.Muthsamy等[19]考慮完工時(shí)間、響應(yīng)時(shí)間、執(zhí)行時(shí)間和任務(wù)優(yōu)先級(jí)等多種QoS屬性，提出人工蜜蜂覓食優(yōu)化任務(wù)調(diào)度(TSABF)算法，以獲得虛擬機(jī)上的最優(yōu)任務(wù)調(diào)度和負(fù)載均衡.Li等[20]考慮用戶偏好、服務(wù)水平協(xié)議和成本等因素，提出邊緣云資源模型，能在滿足負(fù)載均衡要求的同時(shí)使成本降到最低.Mohanty等[21]認(rèn)為負(fù)載均衡的基本目標(biāo)是最小化時(shí)間和提高系統(tǒng)性能，采用Jaya算法實(shí)現(xiàn)了云環(huán)境中的負(fù)載均衡.Asghari等[22]同時(shí)考慮負(fù)載均衡和QoS感知問(wèn)題，提出反向蟻群優(yōu)化(IACO)算法，以解決云服務(wù)器的負(fù)載均衡效率低下問(wèn)題.

考慮QoS的負(fù)載均衡策略不僅能夠合理分配資源的工作負(fù)載，實(shí)現(xiàn)資源的有效利用，還能夠獲取到滿足請(qǐng)求的優(yōu)質(zhì)方案.因此，QoS感知負(fù)載均衡的研究具有必要性.基于此，本文提出一種基于激勵(lì)機(jī)制的負(fù)載均衡和QoS感知服務(wù)組合(LBQSC)方法，通過(guò)動(dòng)態(tài)調(diào)整QoS改變Web服務(wù)的選擇概率，并權(quán)衡請(qǐng)求和提供者的雙方需求，以解決服務(wù)組合的負(fù)載均衡QoS感知問(wèn)題.

1 負(fù)載均衡和QoS感知服務(wù)組合問(wèn)題

1.1 相關(guān)定義

定義1Web服務(wù)(s)是一個(gè)獨(dú)立的、功能完整的可以通過(guò)網(wǎng)絡(luò)進(jìn)行發(fā)布、定位及訪問(wèn)的最小資源單位，包含功能屬性和非功能屬性，可用6元組s={id，b，f，QoS，lw，lmw}表示，其中，id為s的唯一標(biāo)識(shí)；b為s的基本信息，包括提供者、名稱(chēng)和發(fā)布時(shí)間等；f為s的功能屬性，是服務(wù)被發(fā)現(xiàn)的首要依據(jù)；QoS為s的非功能屬性，是服務(wù)被選擇的重要評(píng)判標(biāo)準(zhǔn)；lw為s的實(shí)時(shí)負(fù)載量，是Web服務(wù)當(dāng)前的服務(wù)對(duì)象個(gè)數(shù)；lmw為s的最大負(fù)載量，是被服務(wù)對(duì)象個(gè)數(shù)的最大值，lw≤lmw，一旦實(shí)時(shí)工作量達(dá)到最大負(fù)載量，服務(wù)立刻停止為其他對(duì)象提供服務(wù).

定義2服務(wù)質(zhì)量指Web服務(wù)的非功能屬性，包括一組QoS屬性QoS={q1，…，qν}.一個(gè)QoS屬性qν可用3元組qν={nν，dν，rν}表示，其中，nν為qν的名稱(chēng)，如響應(yīng)時(shí)間、聲譽(yù)、價(jià)格、可行性等，dν為qν的初始狀態(tài)默認(rèn)值，rν為dν的可變性，存在兩種情況:1) 當(dāng)rν=0時(shí)，dν不發(fā)生改變；2) 當(dāng)rν≠0且rν∈(0，1)時(shí)，dν可發(fā)生改變，變化區(qū)間為[dν×(1-rν)，dν×(1+rν)].

在服務(wù)組合中，不同QoS屬性的數(shù)量級(jí)往往不同，因此，需要進(jìn)行歸一化處理.施凌鵬等[18]將非功能屬性分成積極屬性和消極屬性，通過(guò)簡(jiǎn)單加權(quán)(SAW)技術(shù)[19]進(jìn)行歸一化.對(duì)于積極屬性(聲譽(yù)、可行性等)，屬性值越大，表示服務(wù)質(zhì)量越好，按照式(1)歸一化，即

(1)

對(duì)于消極屬性(響應(yīng)時(shí)間、價(jià)格等)，屬性值越小，表示服務(wù)質(zhì)量越好，按照式(2)歸一化，即

(2)

定義3抽象服務(wù)(AS)代表具有相同功能、不同QoS的一組Web服務(wù)，這組服務(wù)被稱(chēng)為該抽象服務(wù)的候選(具體)服務(wù)集.

定義4工作流(F)可用2元組F={AS_set，str}表示，其中，AS_set={AS1，…，ASi，…，ASm}為一組抽象服務(wù)，ASi為第i個(gè)抽象服務(wù)且ASi={si，1，si，2，…，si，j，…，si，n}；str為抽象服務(wù)的組織結(jié)構(gòu).

工作流管理聯(lián)盟(WFMC)提出順序、選擇、循環(huán)和并行4種結(jié)構(gòu)，用以支持Web服務(wù)組合建模[1].其中，選擇、循環(huán)和并行結(jié)構(gòu)均可通過(guò)文獻(xiàn)[20]中的技術(shù)轉(zhuǎn)化成順序結(jié)構(gòu).

(3)

組合服務(wù)的QoS屬性值是由構(gòu)成該服務(wù)的各個(gè)原子服務(wù)的QoS屬性值聚合而成.不同QoS屬性在不同工作流中的聚合公式不同，不同QoS屬性在同一工作流中的聚合公式也不同[21].Web服務(wù)的聲譽(yù)(R)、響應(yīng)時(shí)間(T)和價(jià)格(P)3個(gè)QoS屬性在順序工作流下的聚合公式分別為

定義6服務(wù)負(fù)載(load)指服務(wù)資源利用率，用Web服務(wù)在某一時(shí)刻工作量與最大工作量的比值表示，即load=lw/lmw.

定義7用戶請(qǐng)求(r)用來(lái)存放請(qǐng)求者的需求信息，可用2元組r={id，C}表示，其中，id表示r的唯一標(biāo)識(shí)；C表示全局QoS約束，是請(qǐng)求者對(duì)組合服務(wù)QoS的基本要求.

定義8全局QoS約束C={c1，c2，…，c?}，其個(gè)數(shù)不得超過(guò)Web服務(wù)QoS個(gè)數(shù)，即?≤ν.全局QoS約束是對(duì)組合服務(wù)QoS的基本約束，它要求組合服務(wù)的QoS應(yīng)該優(yōu)于用戶請(qǐng)求中對(duì)應(yīng)的全局QoS.

1.2 問(wèn)題描述

minδ，

(4)

(5)

mint，

(6)

(7)

則SOL為最優(yōu)解決方案.

式(4)～(6)是最優(yōu)解決方案的評(píng)判標(biāo)準(zhǔn)，其中，式(4)表示在獲得SOL后，Web服務(wù)的總體負(fù)載標(biāo)準(zhǔn)差最?。皇?5)表示SOL具有最大的平均效用；式(6)表示獲取SOL的執(zhí)行時(shí)間最少.式(7)是SOL作為最優(yōu)解決方案存在的基本條件，它要求每個(gè)組合服務(wù)CSk中QoS屬性qν整合后均優(yōu)于請(qǐng)求rk中對(duì)應(yīng)的全局QoS約束qν.

圖1 LBQSC的總體框架 Fig.1 Overall framework of LBQSC

2 LBQSC方法設(shè)計(jì)

2.1 LBQSC的總體框架

基于LBQSC方法求解負(fù)載均衡和QoS感知服務(wù)組合問(wèn)題主要分為全局約束分解(GCD)模型求解和局部服務(wù)選擇2個(gè)步驟.LBQSC的總體框架，如圖1所示.

GCD模型求解被認(rèn)為是組合優(yōu)化問(wèn)題，文化遺傳算法(CGA)在處理此類(lèi)問(wèn)題時(shí)具有快速收斂和防止早熟等優(yōu)點(diǎn)[9，23-24]，因此，文中采用CGA算法.在局部服務(wù)過(guò)程中，Web服務(wù)選擇激勵(lì)機(jī)制[5]，通過(guò)合同激勵(lì)服務(wù)提供者更改自身服務(wù)QoS屬性，再迭代選擇QoS更高的Web服務(wù)，從而提高服務(wù)請(qǐng)求者的效用.但是這種機(jī)制并沒(méi)有考慮服務(wù)的負(fù)載情況，因此，對(duì)合同進(jìn)行改進(jìn)，使其不僅能夠約束服務(wù)的QoS和負(fù)載，還能提供更高報(bào)酬來(lái)激勵(lì)服務(wù)提供者將本身服務(wù)的QoS根據(jù)當(dāng)前負(fù)載整體水平進(jìn)行動(dòng)態(tài)調(diào)整，在此基礎(chǔ)上，提出一種基于激勵(lì)機(jī)制的服務(wù)選擇方法.最后，組合局部選擇的服務(wù)形成組合服務(wù).

2.2 GCD模型求解

全局QoS約束分解過(guò)程的主要目的是將服務(wù)請(qǐng)求者的全局QoS約束合理地分解為一組局部約束，確保滿足局部約束的Web服務(wù)復(fù)合而成的組合服務(wù)一定滿足服務(wù)請(qǐng)求者的全局QoS約束.保留更多的組合方案考慮2個(gè)原則：1) 確保滿足每個(gè)局部約束的候選服務(wù)個(gè)數(shù)盡量多；2) 確保滿足每個(gè)局部約束的候選服務(wù)個(gè)數(shù)盡量均衡[25].其評(píng)價(jià)公式為

E=ωsum×S+ωmul×M.

(8)

GCD模型求解過(guò)程包括初始化質(zhì)量等級(jí)和尋找最優(yōu)局部約束組合2個(gè)步驟.

尋找最優(yōu)局部約束組合是將質(zhì)量等級(jí)進(jìn)行組合，從而使E近似最大化的過(guò)程.采用CGA求解該過(guò)程，通過(guò)文化算法從進(jìn)化種群中抽象待解決問(wèn)題的知識(shí)，反饋這些知識(shí)以指導(dǎo)算法的搜索過(guò)程，從而保證解的收斂.CGA的實(shí)現(xiàn)框架，如圖3所示.圖3中：種群空間由個(gè)體組成；Update()函數(shù)用于更新信仰空間的知識(shí)；Accept()函數(shù)用于從種群空間選擇一定數(shù)量的個(gè)體進(jìn)入信仰空間以形成知識(shí)；Influence()函數(shù)主要通過(guò)信仰空間中的知識(shí)影響社會(huì)群體空間的進(jìn)化方向；Generate()函數(shù)用于構(gòu)造個(gè)體；Evaluate()函數(shù)用于評(píng)價(jià)個(gè)體的適應(yīng)度；Select()函數(shù)用于遺傳操作中選擇交叉的個(gè)體.

圖2 質(zhì)量等級(jí)分解 圖3 CGA的實(shí)現(xiàn)框架 Fig.2 Quality level decomposition Fig.3 CGA implementation framework of CGA

2.3 基于激勵(lì)機(jī)制的服務(wù)選擇

激勵(lì)機(jī)制來(lái)源于激勵(lì)理論，主要包括激勵(lì)主體、激勵(lì)客體和激勵(lì)手段3部分.在激勵(lì)機(jī)制中，激勵(lì)主體通過(guò)各種手段引導(dǎo)、激發(fā)激勵(lì)客體的潛能，從而實(shí)現(xiàn)激勵(lì)主體的戰(zhàn)略目標(biāo).在服務(wù)選擇過(guò)程中，請(qǐng)求者、提供者和選擇策略分別對(duì)應(yīng)激勵(lì)主體、激勵(lì)客體和激勵(lì)手段.于是，Wang等[9]提出一種Web服務(wù)選擇激勵(lì)機(jī)制，將激勵(lì)機(jī)制的優(yōu)勢(shì)充分應(yīng)用于服務(wù)選擇.該機(jī)制針對(duì)不同QoS提供具有不同報(bào)酬的合同來(lái)調(diào)動(dòng)服務(wù)提供者的積極性，能夠幫助請(qǐng)求者快速獲取質(zhì)量更優(yōu)的服務(wù)，并保證服務(wù)本身的基本利益.但是，該機(jī)制并沒(méi)有考慮服務(wù)的負(fù)載能力.因此，對(duì)文獻(xiàn)[9]的方法進(jìn)行改進(jìn)，使之能夠解決負(fù)載均衡和QoS感知服務(wù)組合問(wèn)題.通過(guò)節(jié)2.2獲取近似最優(yōu)局部約束組合，排除不滿足約束要求的候選服務(wù)，縮小服務(wù)選擇的搜索范圍.此時(shí)，提供一種新的合同，通過(guò)給不同的QoS和服務(wù)負(fù)載支付不同的報(bào)酬，激勵(lì)服務(wù)提供者動(dòng)態(tài)調(diào)整其自身服務(wù)的QoS來(lái)積極競(jìng)爭(zhēng)合同.同時(shí)，為了選擇最適合的服務(wù)，設(shè)計(jì)一個(gè)基于合同的服務(wù)選擇策略.在此基礎(chǔ)上，構(gòu)建基于激勵(lì)機(jī)制的服務(wù)選擇算法，具體描述如算法1.激勵(lì)合同構(gòu)造、QoS動(dòng)態(tài)調(diào)整和Web服務(wù)選擇是其中的3個(gè)關(guān)鍵步驟.

算法1 基于激勵(lì)機(jī)制的服務(wù)選擇算法

輸入： csSet ∥滿足局部約束的候選服務(wù)集合

輸出： bos ∥最優(yōu)可選服務(wù)

1. ∥M為最大迭代次數(shù)，Size為候選服

務(wù)個(gè)數(shù)

2. IF j≤ M OR Size!=0

3. ∥構(gòu)造合同

4. conj=offerContract(s_set， canSet， j)

5. ∥滿足當(dāng)前合同的候選服務(wù)集中存放

到osSetj

7. ∥添加到osSet中

8. osSet←osSetj

9. ∥不滿足的動(dòng)態(tài)調(diào)整其QoS后存放到

csSet中

10. csSet=AdjustQoSValue(Unsatisfy

(conj))

11. ENDIF

12. ∥選擇服務(wù)

13. bos=ServiceSelect(osSet)

帶合閘電阻斷路器裝置示意如圖3所示，其中R1為合閘電阻，D1為輔助觸頭，D2為主觸頭。合閘命令發(fā)出后，D1先合閘，合閘電阻投入并作用一段時(shí)間，而后D2合閘，合閘電阻旁路退出運(yùn)行，D1再分閘。

14. Return bos∥最優(yōu)可選服務(wù)

2.3.1 激勵(lì)合同構(gòu)造 合同(con)是請(qǐng)求者對(duì)負(fù)載和服務(wù)質(zhì)量這2個(gè)影響因子提出的要求，并確保若服務(wù)提供者可以提供滿足合同約束的Web服務(wù)，服務(wù)請(qǐng)求者會(huì)支付合同中所給定的報(bào)酬.一個(gè)合同用4元組conτ=(τ，QoS，τ，loadτ，rewardτ)表示，其中，τ為合同的唯一標(biāo)識(shí)；QoS，τ為合同中除價(jià)格之外的QoS屬性約束；loadτ為合同中的服務(wù)負(fù)載約束；rewardτ為針對(duì)當(dāng)前的負(fù)載和服務(wù)質(zhì)量，服務(wù)請(qǐng)求者支付的費(fèi)用，也是服務(wù)價(jià)格的上限.

在合同中，2個(gè)影響因子的數(shù)值不同，提供的報(bào)酬也隨之發(fā)生變化.就服務(wù)請(qǐng)求者而言，在其預(yù)算范圍內(nèi)，他們?cè)敢庵Ц陡嗟膱?bào)酬去獲取QoS更優(yōu)、負(fù)載更低的Web服務(wù).對(duì)于一個(gè)抽象服務(wù)，以其局部約束為依據(jù)，提供一組合同Con={con1，…，conτ-1，conτ}，合同conτ的負(fù)載和服務(wù)質(zhì)量均優(yōu)于合同conτ-1的負(fù)載和服務(wù)質(zhì)量，且前者的報(bào)酬高于后者，則這組合同被稱(chēng)為激勵(lì)合同.服務(wù)提供者若想獲得更多的報(bào)酬，就需要調(diào)整服務(wù)自身的QoS來(lái)進(jìn)行競(jìng)爭(zhēng).將滿足合同約束的候選服務(wù)稱(chēng)作可選服務(wù)(os)，將效用值最大的服務(wù)稱(chēng)作最優(yōu)可選Web服務(wù)(bos).

2.3.2 QoS動(dòng)態(tài)調(diào)整 在不滿足當(dāng)前合同的情況下，候選服務(wù)若還想獲得被選擇的機(jī)會(huì)且獲得更高的報(bào)酬，就必須改變自身的QoS屬性去參與新的合同的競(jìng)爭(zhēng).就候選服務(wù)來(lái)說(shuō)，若改變當(dāng)前的響應(yīng)時(shí)間、聲譽(yù)等QoS屬性使之較先前更優(yōu)，則其價(jià)格也會(huì)隨之增長(zhǎng).因此，給定一個(gè)服務(wù)提供策略：1) 如果候選服務(wù)的負(fù)載小于服務(wù)的總體負(fù)載均值，則優(yōu)化候選服務(wù)除價(jià)格以外的QoS屬性，并提高候選服務(wù)的價(jià)格；2) 如果候選服務(wù)的負(fù)載等于服務(wù)的總體負(fù)載均值，則保持候選服務(wù)的所有QoS屬性不變；3) 如果候選服務(wù)的負(fù)載大于服務(wù)的總體負(fù)載均值，則劣化候選服務(wù)的除價(jià)格以外的QoS屬性，并減少候選服的價(jià)格.

2.3.3 服務(wù)選擇策略 激勵(lì)機(jī)制運(yùn)行完畢后，得到多組可選服務(wù)集，提供一個(gè)服務(wù)選擇策略確定最終選擇的服務(wù)，即確定可選服務(wù)os個(gè)數(shù)最多的可選服務(wù)集，選擇該服務(wù)集中的最優(yōu)可選服務(wù)bos.

3 實(shí)驗(yàn)分析

通過(guò)實(shí)驗(yàn)對(duì)比LBQSC，EACO[7]，IACO[22]方法，驗(yàn)證LBQSC方法在處理負(fù)載均衡和QoS感知服務(wù)組合問(wèn)題時(shí)的優(yōu)越性.

3.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

實(shí)驗(yàn)數(shù)據(jù)來(lái)源于綜合服務(wù)數(shù)據(jù)集QWS 2.0.該數(shù)據(jù)集包含真實(shí)世界中2 507個(gè)Web服務(wù)數(shù)據(jù)，每個(gè)Web服務(wù)有9個(gè)QoS屬性，包括響應(yīng)時(shí)間、聲譽(yù)、價(jià)格、吞吐量和可靠性等，具體信息可參考文獻(xiàn)[21].考慮到對(duì)比實(shí)驗(yàn)中數(shù)據(jù)條件的分配情況，僅挑選QWS 2.0數(shù)據(jù)集中的2 000個(gè)Web服務(wù)數(shù)據(jù)，并重點(diǎn)關(guān)注Web服務(wù)的聲譽(yù)、響應(yīng)時(shí)間、價(jià)格、實(shí)時(shí)工作量和最大工作量5個(gè)QoS屬性，聲譽(yù)和響應(yīng)時(shí)間可從數(shù)據(jù)集中獲取，價(jià)格、實(shí)時(shí)工作量和最大工作量則采用隨機(jī)算法構(gòu)造.其中，價(jià)格取值控制在50～500；最大工作量取值控制在50～100；實(shí)時(shí)工作量取值控制在0到最大工作量之間；假設(shè)響應(yīng)時(shí)間和價(jià)格均是可變的QoS屬性，其變化率分別設(shè)置為rt=0.2，rp=0.2.在計(jì)算組合服務(wù)的效用時(shí)，聲譽(yù)、響應(yīng)時(shí)間和負(fù)載的權(quán)重分別賦值為0.3，0.3，0.4.請(qǐng)求數(shù)據(jù)根據(jù)服務(wù)數(shù)據(jù)特征隨機(jī)構(gòu)造.實(shí)驗(yàn)結(jié)果都是運(yùn)行10次之后取平均值.

實(shí)驗(yàn)使用的算法開(kāi)發(fā)語(yǔ)言是Java，實(shí)現(xiàn)工具為MyEclipse 2016 CI，運(yùn)行環(huán)境的具體配置為Windows 7專(zhuān)業(yè)版操作系統(tǒng)，內(nèi)存為4 GB，處理器為Intel(R)Core(TM) i5-2500 CPU@3.30 GHz.

3.2 實(shí)驗(yàn)結(jié)果與分析

采用LBQSC，EACO和IACO方法在不同的數(shù)據(jù)條件下分別進(jìn)行實(shí)驗(yàn)，并對(duì)各指標(biāo)進(jìn)行評(píng)估.

3.2.1 負(fù)載標(biāo)準(zhǔn)差 為驗(yàn)證LBQSC，IACO和EACO在進(jìn)行大規(guī)模服務(wù)組合后，服務(wù)的負(fù)載標(biāo)準(zhǔn)差較初始狀態(tài)的優(yōu)化程度，進(jìn)行3組對(duì)比實(shí)驗(yàn)，具體如下.

1) 當(dāng)抽象服務(wù)數(shù)(Na)范圍為1～10且步長(zhǎng)為1，具體服務(wù)數(shù)(Nc)為200，請(qǐng)求數(shù)(Nr)為100時(shí)，3種方法的負(fù)載標(biāo)準(zhǔn)差(δ)對(duì)比，如圖4(a)所示.圖4(a)中：INT為初始狀態(tài)下服務(wù)總體的負(fù)載標(biāo)準(zhǔn)差.

2) 當(dāng)具體服務(wù)數(shù)范圍為40～400且步長(zhǎng)為40，Na=5，Nr=100時(shí)，3種方法的負(fù)載標(biāo)準(zhǔn)差對(duì)比，如圖4(b)所示.

(a) 不同抽象服務(wù)數(shù)

3) 當(dāng)請(qǐng)求數(shù)范圍為20～200且步長(zhǎng)為20，Na=5，Nc=200時(shí)，3種方法的負(fù)載標(biāo)準(zhǔn)差對(duì)比情況，如圖4(c)所示.

(b) 不同具體服務(wù)數(shù) (c) 不同請(qǐng)求數(shù)圖4 不同數(shù)據(jù)條件下3種方法的負(fù)載標(biāo)準(zhǔn)差對(duì)比 Fig.4 Comparison of load standard deviation in three methods under different data conditions

由圖4(a)可知：在相同具體服務(wù)數(shù)和請(qǐng)求數(shù)情況下，隨著抽象服務(wù)數(shù)的增加，3種方法的負(fù)載標(biāo)準(zhǔn)差比初始狀態(tài)均有所減小，其中，LBQSC方法減小得最明顯.由圖4(b)可知：不論具體服務(wù)數(shù)如何變化，LBQSC方法的負(fù)載標(biāo)準(zhǔn)差始終最小，其次為IACO方法.由圖4(c)可知：服務(wù)的數(shù)據(jù)條件相同，隨著請(qǐng)求數(shù)的增加，EACO方法的負(fù)載標(biāo)準(zhǔn)差雖低于INT，但基本沒(méi)有太大改變；而LBQSC和EACO方法的負(fù)載標(biāo)準(zhǔn)差都逐漸下降且很明顯，LBQSC方法下降尤為迅速.

(a) 不同抽象服務(wù)數(shù)

(b) 不同具體服務(wù)數(shù) (c) 不同請(qǐng)求數(shù)圖5 不同數(shù)據(jù)條件下3種方法獲取的解決方案的平均效用對(duì)比 Fig.5 Comparison of average utility in three methods under different data conditions

(a) 不同抽象服務(wù)數(shù)

(b) 不同具體服務(wù)數(shù) (c) 不同請(qǐng)求數(shù)圖6 不同數(shù)據(jù)條件下3種方法的執(zhí)行時(shí)間對(duì)比 Fig.6 Comparison of execution time in three methods under different data conditions

由圖5(a)可知：在具體服務(wù)數(shù)和請(qǐng)求數(shù)相同時(shí)，隨著抽象服務(wù)數(shù)的增加，通過(guò)3種方法獲取的解決方案的平均效用也隨之增加，且平均效用與抽象服務(wù)數(shù)大小呈現(xiàn)近似線性關(guān)系.由圖5(b)可知：隨著具體服務(wù)數(shù)的增加，LBQSC方法的平均效用明顯高于其他兩種方法，但當(dāng)Na<4且Nc<120時(shí)，LBQSC方法的平均效用比其他兩種方法差，這是因?yàn)橄伻核惴ㄔ谛∫?guī)模服務(wù)組合下較激勵(lì)機(jī)制具有更好的收斂性.由圖5(c)可知：在服務(wù)數(shù)據(jù)相同的條件下，請(qǐng)求數(shù)越多，3種方法的平均效用越差，其主要原因是在大量請(qǐng)求下，QoS較高的Web服務(wù)被選擇達(dá)到最大負(fù)載量后，后續(xù)的請(qǐng)求只能選擇一些QoS較差的Web服務(wù)代替，使組合服務(wù)效用降低，從而使解決方案的平均效用減小.

3.2.3 執(zhí)行時(shí)間 為進(jìn)一步驗(yàn)證LBQSC，IACO，EACO方法的時(shí)間開(kāi)銷(xiāo)，同樣采用節(jié)3.2.1的3組數(shù)據(jù)進(jìn)行對(duì)比實(shí)驗(yàn).不同數(shù)據(jù)條件下，3種方法的執(zhí)行時(shí)間(t)對(duì)比，如圖6所示.

由圖6可知:不論數(shù)據(jù)條件如何變化，所提LBQSC方法的執(zhí)行時(shí)間均小于其他兩種方法，能快速地獲取解決方案.

結(jié)合3個(gè)指標(biāo)的對(duì)比結(jié)果可知，LBQSC方法能夠有效解決多請(qǐng)求下的負(fù)載均衡和QoS感知服務(wù)組合問(wèn)題，且具有較少的時(shí)間開(kāi)銷(xiāo).

4 結(jié)論

針對(duì)請(qǐng)求者的高QoS需求、提供者的負(fù)載均衡需求及QoS的動(dòng)態(tài)性等問(wèn)題，提出基于激勵(lì)機(jī)制的負(fù)載均衡和QoS感知服務(wù)組合(LBQSC)方法.首先，利用文化遺傳算法將全局QoS約束分解為一組局部約束；然后，基于激勵(lì)機(jī)制，在滿足局部約束且具有動(dòng)態(tài)QoS的候選服務(wù)中迭代選擇出最佳Web服務(wù)；最后，采用QWS 2.0數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明：與EACO和IACO方法相比，LBQSC方法能夠有效地處理負(fù)載均衡和QoS感知服務(wù)組合問(wèn)題.

在未來(lái)的工作中，將完善LBQSC方法，使其可靈活地運(yùn)用到工作流的其他3種基本結(jié)構(gòu)(并行、選擇、循環(huán))；改善激勵(lì)機(jī)制中的服務(wù)提供策略，使服務(wù)QoS的動(dòng)態(tài)調(diào)整更加依賴于激勵(lì)合同的變化，以更好地服務(wù)于服務(wù)選擇過(guò)程；考慮用戶請(qǐng)求的時(shí)序特征，研究面向多連續(xù)請(qǐng)求的負(fù)載均衡和QoS感知服務(wù)組合方法.