何健文

摘要：近年來，隨著以服務(wù)為導(dǎo)向的框架技術(shù)的產(chǎn)生和發(fā)展，web服務(wù)技術(shù)已經(jīng)獲得了信息技術(shù)社區(qū)和商業(yè)社會的廣泛關(guān)注和研究。Web服務(wù)是一種跟傳統(tǒng)面向?qū)ο箝_發(fā)模式所不一樣的新型模塊化開發(fā)模式，具有面向功能的更高抽象粒度。但是，隨著web服務(wù)數(shù)量的逐漸增多，單一功能的Web服務(wù)面臨著難以滿足用戶復(fù)雜多變的實(shí)時(shí)需求。在很多場景下必須把單一功能的Web服務(wù)整合成具有更復(fù)雜功能的復(fù)合Web服務(wù)。因此，人們提出很多優(yōu)化算法來解決基于Qos屬性的Web服務(wù)組合問題。該文針對以上Web服務(wù)組合問題，引入一種新型的基于群體智能的優(yōu)化算法來解決Web服務(wù)組合問題。實(shí)驗(yàn)結(jié)果表明了改進(jìn)后的狼群算法跟傳統(tǒng)的優(yōu)化算法相比在效率和性能有一定的提高。

關(guān)鍵詞：面向功能框架；Web服務(wù)組合；QoS屬性；狼群算法

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）01-0070-04

WCA-based Web Service Composition Optimization Research

HE Jian-wen

（School of Software Engineering，Tongji University， Shanghai 201804，China）

Abstract： Thanks to the emergence and widespread of Service-oriented Architecture（SOA），Web service technology has got its attention around the Internet Community. However， single simple web service face the challenge of being unable to satisfy users complex requirements in runtime environment as the amounts of web services become larger and larger. Therefore a lot of optimization solution has been proposed aimed to address the web service composition issue. Whereas most of them are of low efficiency and accuracy. The paper has introduced a new kind of colony intelligent algorithm to address the QoS-based web service composition， which is called Wolf Colony Algorithm. The experimental results show that the WCA outperform in comparison with traditional heuristic algorithm such as particle swarm algorithm.

Key words： SOA； web service composition； QoS property； WCA

Web服務(wù)作為一種新型的web應(yīng)用模式，近年來得到了迅速的發(fā)展。如何動態(tài)地把現(xiàn)存的各種web服務(wù)整合起來以形成新的、滿足不同用戶需求的、增值的復(fù)雜服務(wù)已成為新的應(yīng)用需求和研究熱點(diǎn)。為了解決現(xiàn)有服務(wù)組合中服務(wù)選擇技術(shù)的不足，已經(jīng)提出了多種解決服務(wù)組合中服務(wù)動態(tài)選擇QoS全局最優(yōu)化問題的實(shí)現(xiàn)算法，例如粒子群算法和遺傳算法等。但是這些群體智能優(yōu)化算法不同程度地都存在著一些不足，如算法后期收斂速度較慢，易陷入局部最優(yōu)或計(jì)算精度不高等問題。因此有必要針對該類問題引入新的優(yōu)化算法。該文的主要研究工作集中在如何幫助用戶獲取滿足用戶特定約束條件的最優(yōu)化組合服務(wù)。

服務(wù)組合技術(shù)今年獲得了廣泛的關(guān)注和應(yīng)用，主要用來為企業(yè)或個(gè)人提供商業(yè)業(yè)務(wù)工作流過程模型。通過使用不同web服務(wù)提供商提供的現(xiàn)存的web服務(wù)，企業(yè)或者個(gè)人可以建立基于自身業(yè)務(wù)需求的商業(yè)業(yè)務(wù)過程?，F(xiàn)金商業(yè)社區(qū)經(jīng)常用分布式系統(tǒng)的方式來建立web服務(wù)。在這種框架中web服務(wù)用一種稱為WSDL的語言描述，并且用BPEL語言來進(jìn)行工作流整合。這種方法專注于復(fù)合web服務(wù)的執(zhí)行過程，而并不需要太多地考慮驅(qū)動開發(fā)過程的需求。

在本課題中，我們提出了在動態(tài)環(huán)境下解決web服務(wù)組合問題的新的最優(yōu)化算法。通過用QoS屬性來衡量web服務(wù)，我們建立了web服務(wù)組合流程模型的數(shù)據(jù)模型，并且對最優(yōu)化算法做出了一些改進(jìn)。在完成了算法的設(shè)計(jì)和部署后，用對比實(shí)驗(yàn)驗(yàn)證算法的性能特點(diǎn)。

1 QoS驅(qū)動的web服務(wù)組合數(shù)據(jù)模型

1.1 web服務(wù)的QoS模型

實(shí)際上，Web服務(wù)組合過程可以看成是一種基于Web 服務(wù)的工作流模型。在這個(gè)工作流模型中，每一個(gè)結(jié)點(diǎn)都表示為一個(gè)抽象的Web服務(wù)接口，每一個(gè)接口都有相對應(yīng)的輸入和輸出。在運(yùn)行時(shí)，每一個(gè)抽象的Web服務(wù)接口根據(jù)服務(wù)的Qos值調(diào)用具體功能的Web服務(wù)。Web服務(wù)的Qos模型是指每一個(gè)Web服務(wù)的Qos值作為在多個(gè)相同功能的Web 服務(wù)中選擇的標(biāo)準(zhǔn)。結(jié)果，一系列具體的Web 服務(wù)會根據(jù)其對應(yīng)的Qos屬性被選中形成一個(gè)復(fù)合的web 服務(wù)。

每一個(gè)web服務(wù)都有多種的QoS屬性，也就是非功能屬性。例如，最常見的有價(jià)格，響應(yīng)時(shí)間，可靠性和名聲等級。一般來說，QoS屬性可以分為兩種，一種是積極的QoS屬性，一種是消極的QoS屬性。像響應(yīng)時(shí)間和執(zhí)行時(shí)間等是消極的QoS屬性而可用性和名聲等級是積極的QoS屬性。對于消極的QoS屬性來說，值越高，說明質(zhì)量指數(shù)越低，而積極的QoS屬性正好相反。在本課題中，我們將用一個(gè)四維向量的形式來定義一個(gè)web服務(wù)的QoS屬性，如：[q=[QoS1，QoS2，QoS3，QoS4]]。

一般來說，有四種計(jì)算QoS屬性值的基本模型。這四種模型分別是串行，并行，條件和循環(huán)模型。在這四種模型里，我們假設(shè)每個(gè)web服務(wù)包含以下四種QoS屬性：執(zhí)行時(shí)間、執(zhí)行成本、名聲等級和可行性。

1.2 web服務(wù)組合的數(shù)學(xué)模型

根據(jù)前面的描述，我們可以總結(jié)出Web服務(wù)組合優(yōu)化問題可以簡化成一種多目標(biāo)優(yōu)化的數(shù)學(xué)模型。

顯然，這是一種多目標(biāo)優(yōu)化問題。然后我們可以為多目標(biāo)Web服務(wù)組合問題建立以下模型：

[MAX fr（x）=frj=1n1x1j，j=1n2x2j，...，j=1nix2i]r=1，...，m

St. （1） [xi，j=0 or 1，0≤i

1） [xi，j=0 or 1]限制了每個(gè)web服務(wù)有且僅有兩個(gè)狀態(tài)：選擇或者是不選。

2） [i=1NLx1，j=1]可以保證在每個(gè)服務(wù)集里面只有一個(gè)服務(wù)會被選擇。

為了更清楚地描述所要解決的問題，在這個(gè)課題中我們會把執(zhí)行價(jià)格和成本設(shè)置為目標(biāo)變量，也就是說，我們需要把價(jià)格和成本降到盡可能低。然后名稱等級和可靠性被設(shè)置為兩個(gè)約束變量。[Rcp0]和[Ru]各自表示最低的名稱等級和最低的可靠性等級。因此，我們可以把多目標(biāo)組合優(yōu)化模型描述為：

MinF（P）=（T（P），C（P））

St. （1）[Rcp（P）≥Rcp0] （2）[R（P）≥R0]

多目標(biāo)優(yōu)化的最關(guān)鍵的一個(gè)特點(diǎn)是兩個(gè)不同的QoS屬性間的一個(gè)共同的矛盾性，在候選服務(wù)中需要更少執(zhí)行時(shí)間的會需要支付更高的價(jià)格。因此，組合優(yōu)化的最后目標(biāo)是輸出滿足約束條件的最優(yōu)化方案，而不是單個(gè)的Web服務(wù)。

2 web服務(wù)組合優(yōu)化的狼群算法

2.1 狼群算法的設(shè)計(jì)及其實(shí)現(xiàn)

跟其他群體智能算法類似，狼群算法的靈感來源于自然界中狼群的捕食行為。我們知道，在狼群社區(qū)中，有嚴(yán)格的等級制度，明確的責(zé)任分工以及為了高效地捕殺獵物而采取的同步行動。盡管狼是野性的和富有攻擊性的，但是在每一個(gè)狼群里，都有一個(gè)首領(lǐng)狼，在捕食行動中首領(lǐng)狼具有完全的控制權(quán)。正是由于狼群的這種組織原則，狼群才能夠成功地捕獲獵物并且在自然界中生存下去。但是，狼群中的首領(lǐng)狼并不是一成不變的，一些候選狼會定期地競爭狼群中首領(lǐng)狼的角色。這樣可以保證狼群的靈活性和社群的多樣性。在捕食獵物的過程當(dāng)中，在發(fā)現(xiàn)目標(biāo)的那一刻，首領(lǐng)狼會通過嚎叫來通知其他狼。在首領(lǐng)狼的控制下，狼群逐漸包圍目標(biāo)獵物。最終，一旦獵物抓到以后，狼群開發(fā)對獵物進(jìn)行分配，按照狼群的規(guī)則，強(qiáng)壯的狼會在分配獵物的過程中比弱小的狼分到更多的部分。這樣，按照適者生存的規(guī)則，強(qiáng)壯的狼在狼群中的數(shù)量會逐漸增多，狼群捕獲到食物的概率也會增高。在本課題中，狼群算法根據(jù)自然界中狼群的該種捕食行為來實(shí)現(xiàn)最優(yōu)結(jié)果的搜索。以下為狼群算法的實(shí)施步驟。

1） 數(shù)據(jù)初始化。在初始化步驟里，一些相關(guān)的參數(shù)被賦初值并且輸入數(shù)據(jù)也會被導(dǎo)入進(jìn)來。

2） 競選領(lǐng)導(dǎo)狼。一定數(shù)量的候選狼根據(jù)特定的規(guī)則競選成為領(lǐng)導(dǎo)狼。

3） 向領(lǐng)導(dǎo)狼靠近。一旦領(lǐng)導(dǎo)狼確定以后，狼群中的其他狼會逐漸向領(lǐng)導(dǎo)狼的位置靠近。

4） 包圍獵物。一旦目標(biāo)被發(fā)現(xiàn)以后，領(lǐng)導(dǎo)狼會通過發(fā)送信號來通知其他狼包圍獵物。

5） 狼群更新。根據(jù)優(yōu)勝劣汰的食物分配原則，在具體的算法實(shí)現(xiàn)中，一些弱小的狼會隨機(jī)性地被一些新的狼代替。

6） 連續(xù)性結(jié)果的離散化處理。因?yàn)樵趯?shí)際應(yīng)用過程中，web服務(wù)組合的最優(yōu)化方案是離散。但是狼群算法的搜索空間卻是連續(xù)的。因而根據(jù)以上規(guī)則搜尋得到的結(jié)果會根據(jù)特定的規(guī)則進(jìn)行離散化處理。

7） 終止條件判斷。當(dāng)狼群的一次迭代結(jié)束以后，下一次迭代會根據(jù)終止條件來決定是否繼續(xù)執(zhí)行。

2.2 連續(xù)域結(jié)果的離散化處理

以上實(shí)現(xiàn)的狼群算法部分是用來解決連續(xù)域的最優(yōu)化問題。也就是說，狼群位置的變化以及其他變量在連續(xù)范圍內(nèi)變化，所涉及的計(jì)算規(guī)則也是針對連續(xù)型變量。但是，在實(shí)際應(yīng)用過程中，許多工程問題里需要離散化處理的。一般來說，有三種主要的離散化策略。

首先，受激發(fā)于解決0-1規(guī)劃問題的二進(jìn)制算法原理，我們可以通過把位置的改變看成一種概率性事件的方法來對算法結(jié)果離散化處理。也就是說，在離散化的狼群算法中，二維空間意味著一個(gè)超立方體空間，狼群中每個(gè)狼的位置可以表示為一個(gè)二進(jìn)制變量。因此狼群在搜索空間中的移動可以通過這些二進(jìn)制變量值的翻轉(zhuǎn)來捕獲。狼群位置的更新如下：

[xid=1 （if（rand（）

[sig（vid）]是一個(gè)特定的控制翻轉(zhuǎn)的約束函數(shù)，可以保證狼群位置的每個(gè)元素限制為0或1。rand（）是一個(gè)介于0和1之間的隨機(jī)數(shù)。

其次，連續(xù)域算法的離散化策略也可以通過對運(yùn)算符的重新定義來實(shí)現(xiàn)。這種方法意味著對狼群算法的某新參數(shù)操作的重新定義。這種方法具有較高的復(fù)雜性。

最后，另外一個(gè)可選方案是直接利用連續(xù)域狼群算法的結(jié)果來轉(zhuǎn)換為離散型結(jié)果。根據(jù)連續(xù)型結(jié)果變量和離散型變量的距離，選出和連續(xù)型變量最為接近的一個(gè)離散型變量作為離散處理后的結(jié)果。

由于上述描述的三種方法中，概率處理的方法在很多場景中并不適用，運(yùn)算符重新定義的方法具有較高復(fù)雜性。因此本課題采用直接轉(zhuǎn)換連續(xù)型變量的策略來對狼群算法進(jìn)行離散化處理。具體的實(shí)現(xiàn)操作是把離散域中最接近的值賦值給人工狼的位置，剩下的算法操作和原來一樣。連續(xù)域結(jié)果被賦值以后，系統(tǒng)計(jì)算解決方案的適應(yīng)度并根據(jù)特定規(guī)則決定是否激發(fā)下一次迭代。盡管在這種方法的執(zhí)行過程中，可能會有多個(gè)連續(xù)型結(jié)果變量指向同一個(gè)離散型結(jié)果變量而且離散化后的結(jié)果也有可能會溢出約束的范圍。然后計(jì)算結(jié)果表明，在結(jié)果高維優(yōu)化問題的時(shí)候，算法具有較高的穩(wěn)定性而且不會陷于局部最優(yōu)。

2.3 狼群算法的適應(yīng)度計(jì)算函數(shù)

在本課題的算法實(shí)現(xiàn)中，我們用以下的方式計(jì)算適應(yīng)性函數(shù)：

其中Agg是第d個(gè)QoS屬性的計(jì)算值，Con是用戶定義約束。w是第d個(gè)QoS屬性的權(quán)重。

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

根據(jù)前文的描述，我們介紹了一些傳統(tǒng)優(yōu)化算法的基本原理并且引入實(shí)現(xiàn)了改進(jìn)后的狼群算法。為了更好地比較和測量狼群算法和其他優(yōu)化算法的執(zhí)行效率和性能，相關(guān)的對比實(shí)驗(yàn)是很有必要的同時(shí)也能讓本課題的研究內(nèi)容更加有說服力。在本次實(shí)驗(yàn)中我們使用響應(yīng)時(shí)間和系統(tǒng)吞吐量來作為web服務(wù)的兩個(gè)QoS屬性，輸入數(shù)據(jù)在本章前面部分已經(jīng)介紹過。實(shí)驗(yàn)數(shù)據(jù)中QoS屬性每個(gè)矩陣代表339個(gè)用戶對于5825個(gè)web服務(wù)的實(shí)時(shí)環(huán)境使用歷史記錄。

為了更好地進(jìn)行性能評估，算法操作中的許多參數(shù)已經(jīng)被提前設(shè)定。在以下實(shí)驗(yàn)中，基于準(zhǔn)確性和有效性的考慮，我們?yōu)槊總€(gè)關(guān)鍵參數(shù)設(shè)置了相關(guān)的值。

對于狼群算法來說，參數(shù)值設(shè)定如下：

WOLF_SIZE=625，maxdh=15，stepa=1.5，stepb=0.9，h=4，cta=0.2，ramax=0.9，ramin=0。

算法的實(shí)驗(yàn)環(huán)境為：

操作系統(tǒng)：Ubuntu Linux OS

處理器：Intel Core i5

運(yùn)行時(shí)：Java Version 1.7.0 JDK

實(shí)驗(yàn)仿真結(jié)果如圖1所示。

實(shí)驗(yàn)結(jié)果表明狼群算法具有較高的運(yùn)算效率并且一定程度上優(yōu)于粒子群算法。

4 結(jié)束語與展望

本文就圍繞著Web服務(wù)組合中如何獲得全局最優(yōu)的web組合方案展開研究。我們的工作主要集中在建立基于QoS的web服務(wù)組合數(shù)據(jù)模型并且利用狼群算法來解決基于QoS的web服務(wù)組合問題。實(shí)驗(yàn)結(jié)果表明狼群算法具有較高的運(yùn)算效率并且一定程度上優(yōu)于粒子群算法。

本文針對Web服務(wù)組合優(yōu)化問題進(jìn)行研究，在充分掌握了當(dāng)前的研究存在的問題的基礎(chǔ)之上，提出了一些改進(jìn)的方法，并通過實(shí)驗(yàn)驗(yàn)證了這些改進(jìn)所取得的效果，但是本文在以下方面仍然存在著一些不足。在當(dāng)前互聯(lián)網(wǎng)快速發(fā)展的環(huán)境下，大數(shù)據(jù)、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等算法正在得到越來越多的關(guān)注。是否可以把數(shù)據(jù)挖掘，機(jī)器學(xué)習(xí)等算法運(yùn)用到Web服務(wù)的QoS預(yù)測或者服務(wù)推薦當(dāng)中，將是我們未來探索的一個(gè)方向。

參考文獻(xiàn)：

[1] Xianglan H.A Survey on QoS-Aware Dynamic Web Service Selection[C]//Wireless Communications， Networking and Mobile Computing （WiCOM）， 2011 7th International Conference on. 2011. IEEE.

[2] Alrifai M，Risse T.Combining global optimization with local selection for efficient QoS-aware service composition[C].Proceedings of the 18th international conference on World wide web，ACM. 2009.

[3] Wan S.Developing a Selection Model for Interactive Web Services[C].Web Services， 2006. ICWS'06. International Conference on. 2006. IEEE.

[4] Maximilien E M， Singh M P.A framework and ontology for dynamic web services selection[J].Internet Computing， IEEE， 2004，8（5）： 84-93.

[5] Wada H.Multiobjective optimization of SLA-aware service composition[C].Services-Part I，2008.IEEE Congress on. 2008. IEEE.

[6] Yu T，Zhang Y，Lin K-J.Efficient algorithms for Web services selection with end-to-end QoS constraints[J]. ACM Transactions on the Web （TWEB）， 2007，1（1）： 6.

[7] Trelea I C.The particle swarm optimization algorithm： convergence analysis and parameter selection[J]. Information processing letters， 2003，85（6）： 317-325.

[8] Ludwig S A.Applying Particle Swarm Optimization to Quality-of-Service-Driven Web Service Composition[C]. Advanced Information Networking and Applications （AINA）， 2012 IEEE 26th International Conference on. 2012. IEEE.

[9] LIU C.The Wolf Colony Algorithm and Its Application[J]. Chinese Journal of Electronics， 2011，20（2）.