摘要：Web服務組合問題中數(shù)以千計的Web Service的信息可能會隨時改變，如何發(fā)現(xiàn)這些易變Web Service描述信息（包括服務提供者和服務消費者的描述信息），如何根據(jù)用戶的需求來自動組合Web Services，生成滿足用戶需求的組合業(yè)務，并及時應用到業(yè)務執(zhí)行流程中。本文設計了一種基于用戶需求服務全局距離最優(yōu)動態(tài)選擇算法（Dynamic Selection Algorithm with Global Optimal Distance），用于發(fā)現(xiàn)動態(tài)調用Web Services來自動生成滿足用戶所需目標的Web Service組合。

關鍵詞：Web Services；DSAGOD（Dynamic Selection Algorithm with Global Optimal Distance）；服務組合；最優(yōu)動態(tài)選擇

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)19-30119-01

1 引言

Web Services是一種用于分布式應用程序之間通信的接口技術，它構建于通行的internet標準協(xié)議棧之上，提供了一種B2B應用程序的耦合方式[2]流行的Web Services實現(xiàn)一般都是構建在XML，SOAP，WSDL，WSFL等技術上。然而，人們需要的往往不是單一的、簡單的Web Services，而是Web Services組合出來的新業(yè)務。比如，服務消費者需要考慮花多少錢購買股票或購買多少股，旅行訂票服務需要考慮天氣狀況、火車或飛機到達時間， 音樂會訂票服務考慮什么座位有利些，哪些資源在網(wǎng)格計算環(huán)境中有用等這些動態(tài)易變信息。服務提供者可能為了適應業(yè)務需求往往也會不斷提交不同版本的服務，提交時間上沒有規(guī)律的，服務描述也可能發(fā)生變化。但是分布式計算技術的缺點在于需要專業(yè)的人員手工生成業(yè)務，而不能根據(jù)用戶的需求直接通過機器生成業(yè)務。在實現(xiàn)Web服務組合問題中，組合引擎的許多信息都來自Web Service，數(shù)以千計的Web Service的信息可能會隨時改變。如何發(fā)現(xiàn)這些易變Web Service描述信息（包括服務提供者和服務消費者的描述信息），如何根據(jù)用戶的需求來自動組合Web Services，生成滿足用戶需求的組合業(yè)務，本文設計了一種基于用戶需求服務全局距離最優(yōu)動態(tài)選擇算法（Dynamic Selection Algorithm with Global Optimal Distance ），DSAGOD算法還能將整個Web Services的組合和調用是聯(lián)系在一起的，并根據(jù)已有的Web Services的動態(tài)地進行組合。

2 DSAGOD算法思想

DSAGOD算法的主要思想是基于多目標遺傳算法的服務全局最優(yōu)距離動態(tài)選擇實現(xiàn)算法，判斷其與目標的距離，然后調用目標距離最優(yōu)的Web Service，從而高效地實現(xiàn)Web Services的組合。通過把服務組合中的服務動態(tài)選擇全局最優(yōu)距離問題轉化為一個帶約束條件的多目標服務組合優(yōu)化問題，利用多目標遺傳算法的智能優(yōu)化原理，通過同時優(yōu)化多個目標參數(shù)，即在不同的目標之間取均衡，最終產(chǎn)生一組滿足約束條件的最優(yōu)非劣服務組合流程集；用戶可以根據(jù)特定需要從中選擇最滿意組合流程，同時，未被選中的非劣路徑可以作為備選方案，以便所選聚合路徑發(fā)生意外時啟用。

3 DSAGOD算法過程描述

多目標優(yōu)化的特點在于各目標之間的相互沖突性（執(zhí)行時間短的服務其執(zhí)行費用往往比較高），所以，多目標服務聚合優(yōu)化模型最后的結果不是單一解，即一個Web Service組合問題可能出現(xiàn)不同的解決辦法，優(yōu)選目標距離最優(yōu)的Web Service，這是本文算法的基礎。優(yōu)化解集中各條路徑之間的比較采用了相對優(yōu)于的概念，由于帶約束的多目標優(yōu)化問題不同于不帶約束的問題，它比絕對的優(yōu)化解集優(yōu)于關系要復雜，DSAGOD算法針對當前狀態(tài)下可行的Web Service，對于這些Web Service進行判斷，計算其與目標的距離，然后調用目標距離最優(yōu)的Web Service，從而高效地實現(xiàn)Web Services的組合。

本文采用文獻算法框圖如圖1所示，首先需要定義兩個基本概念：目標距離因子和目標距離。

下面說明目標距離因子的計算，Web Services的目標距離因子可以看作是Web Services執(zhí)行的一個代價。Web Services的目標距離因子δ根據(jù)以下的公式計算：

對于所有Web Services W，目標距離因子δ0(W)的初始值為1；

當這個Web Service第i次調用以后，如果第i+1次調用成功，δi+1(W)=δi(W)-1/2Success(W)。

而如果第i+1次這個Web Service的調用拋出異?；蛘呤遣环嫌脩舻募s束條件C，那么，δi+1(W)=δi(W)＋1/2Fail(W)，其中：Success(W)為這個Web Service的調用成功總次數(shù)；Fail(W)為這個Web Service的調用失敗總次數(shù)。

由以上目標距離因子的計算方法可以看出，若一個Web Service調用成功的次數(shù)越多，則其目標距離因子越小；若一個Web Service調用失敗的次數(shù)越多，則其目標距離因子越大。算法認為，一個Web Service執(zhí)行成功一次和執(zhí)行失敗一次，其差距是顯然的。而一個Web Service執(zhí)行成功/失敗100次和101次，其差距則并不明顯。因此，算法定義的公式在連續(xù)成功/失敗后，對目標距離因子的調整量呈指數(shù)方式衰減。顯然，0<δ<2，然后我們在取距離因子時，使用的是該距離因子的左右一個范圍，而不是一個值，就而我們根據(jù)算法而產(chǎn)生一組目標距離最優(yōu)的Web Service最優(yōu)解的集合。

基于上述思想和模型，本文基于多目標算法設計了求解服務聚合中服務動態(tài)選擇全局距離最優(yōu)化問題的實現(xiàn)算法DSAWGOD；通過同時優(yōu)化聚合路徑的多個距離目標參數(shù)，最終產(chǎn)生一組目標距離最優(yōu)的Web Service最優(yōu)解的集合，用戶可以根據(jù)特定需要從中選擇最滿意解；未被選中的非劣路徑可以作為備選方案，在所選聚合路徑發(fā)生意外時啟用。

4 結束語

Web服務組合問題中，組合引擎的許多信息都來自Web Service，數(shù)以千計的Web Service的信息可能會隨時改變。如何發(fā)現(xiàn)這些易變Web Service描述信息（包括服務提供者和服務消費者的描述信息），如何根據(jù)用戶的需求來自動組合Web Services，生成滿足用戶需求的組合業(yè)務，Web服務動態(tài)選擇是服務組合的一個重要問題，本文提出了動態(tài)服務選擇全局距離最優(yōu)模型，并基于多目標智能優(yōu)化的思想，將服務動態(tài)選擇全局距離最優(yōu)問題轉化為一個帶約束條件的多目標優(yōu)化問題。

參考文獻：

[1] Web Services Shalil M，Walker DW，Gray WA.A framework for automated service composition in service-oriented architectures，In:Bussler C，ed.Proc.of the ESWS 2004.LNCS 3053，Heraklion，Berlin:Spdnger-Verlag，2004，269-283.

[2] 耦合方式. Benatallah B，Dumas M，Sheng QZ，Ngu A.Declarative composition and peer-to-peer provisioning of dynamic Web services，In:Proc.of the l 8th Int'l Conf.on Data Engineering.San Jose:IEEE Computer Society.2002.297-308．

[3] SOAP WSFL Zeng LZ，Benatallah B，Dumas M.Quality driven Web service composition.In:Proc.of the WWW 2003，Budapest:ACM，2003.411-421.

[4] WSDL Casati F，Ilnicki S，Jin LJ，Krishnamoorthy V，Shah MC.eFlow:A platform for developing and managing composition e-services.Technical Report，HPL-2000-36，HP Laboratories Palo Alto，2000.

[5] 實例算法.Journal of Software，Vol.18， No.1， January 2007， pp.86-87.

[6] HTNErol K，Hendler J，Nau DS. UMCP: A sound and complete procedure for hierarchical task-network planning. In: Proc. of the Int' l Conf. on AI Planning Systems (AIPS).1994. 249-254. http://www.cs.umd.edu/~nau/publications.html.

[7] 劉祾頠，夏元友，姜建華.基于Dijkstra算法的Web服務合成選擇策略研究[J]. 計算機技術與發(fā)展， 2008，(02)，104-107.

[8] 蔣運承，湯庸.服務組合的質量估計模型[J]. 小型微型計算機系統(tǒng)，2006，(08).1519-1525.