易變信息全局距離最優動態選擇算法

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

關鍵詞：Web Services；DSAGOD（Dynamic Selection Algorithm with Global Optimal Distance）；服務組合；最優動態選擇

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

1 引言

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

2 DSAGOD算法思想

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

3 DSAGOD算法過程描述

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

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

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

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

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

而如果第i+1次這個Web Service的調用拋出異常或者是不符合用戶的約束條件C，那么，δi+1(W)=δi(W)＋1/2Fail(W)，其中：Success(W)為這個Web Service的調用成功總次數；Fail(W)為這個Web Service的調用失敗總次數。

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

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

4 結束語

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

參考文獻：

[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]. 計算機技術與發展， 2008，(02)，104-107.

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