何健文

摘要：近年來，隨著以服務(wù)為導向的框架技術(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ù)面臨著難以滿足用戶復雜多變的實時需求。在很多場景下必須把單一功能的Web服務(wù)整合成具有更復雜功能的復合Web服務(wù)。因此，人們提出很多優(yōu)化算法來解決基于Qos屬性的Web服務(wù)組合問題。該文針對以上Web服務(wù)組合問題，引入一種新型的基于群體智能的優(yōu)化算法來解決Web服務(wù)組合問題。實驗結(jié)果表明了改進后的狼群算法跟傳統(tǒng)的優(yōu)化算法相比在效率和性能有一定的提高。

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

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

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

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

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

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

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

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

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

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

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

顯然，這是一種多目標優(yōu)化問題。然后我們可以為多目標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]限制了每個web服務(wù)有且僅有兩個狀態(tài)：選擇或者是不選。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[xid=1 （if（rand（）

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

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

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

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

2.3 狼群算法的適應度計算函數(shù)

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

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

3 實驗分析

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

為了更好地進行性能評估，算法操作中的許多參數(shù)已經(jīng)被提前設(shè)定。在以下實驗中，基于準確性和有效性的考慮，我們?yōu)槊總€關(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。

算法的實驗環(huán)境為：

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

處理器：Intel Core i5

運行時：Java Version 1.7.0 JDK

實驗仿真結(jié)果如圖1所示。

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

4 結(jié)束語與展望

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

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

參考文獻：

[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）.