基于改進蟻群算法的服務組合研究

摘要：在服務計算過程中，服務組合問題是其中關鍵的技術之一。在原子候選服務數目巨大的情況下，經典的算法一般都是尋找問題的最優解，存在運算量大，運行時間長的缺點，蟻群算法并不是尋找服務組合問題的最優解，而是得到用戶能夠認同的可行解。為了能夠更有效的為用戶提供各種服務，在靜態的服務組合建立過程中，以服務發現的候選原子服務集合中的服務質量為權重，將服務組合問題分解成一個有向無環圖，在組合代價為最小的原則下，采用改進的蟻群算法為搜索方法，迭代一定的次數或者達到用戶設定的服務質量為算法的終止條件，找到能夠組合為用戶需要的原子候選服務集合，進而快速、準確的得到用戶期望的服務。

關鍵詞：服務計算；服務組合；蟻群算法；服務質量；組合代價

Service Composition Based on Improved Ant Colony Algorithm

Niu Yong Jie 1， Zhang Cheng 2

(1. Computing Center， Yan’an University;

2. Network Center， Yan’an University; Yan’an， 716000)

Abstract: In service computing， service composition problem is one of the key technologies. Large number of candidate services in the atomic case， the classical algorithms are generally looking for the optimal solution， there is large amount of computation， the shortcomings of a long running time， ant colony optimization services portfolio problem is not finding the optimal solution， but the user can identify a feasible solution. In order to more effectively provide various services for users， a static portfolio of services in the building process， to serve a collection of atomic services discovered in the candidate quality of service for weight， the service composition problem into a directed acyclic graph， in combination of the principle of minimum costs， an improved ant colony algorithm for the search method， the number of iterations or a certain quality of service to the user to set the termination conditions for the algorithm to find that combination of candidates for service users need a collection of atoms， then fast and accurate service to the user expectations.

Keywords: service computing; service component; ant colony optimization; quality of services; component costs

1研究背景及現狀

目前，萬維網信息的來源主要是靜態數據的提供者，這些提供者逐漸形成了很多個信息的“孤島”。在很多應用領域，要求很多的Web服務聯合起來以提供更加完整、全面的信息，服務計算就應運而生。面向服務的計算（SOC，Service-orientedcomputing）技術又稱服務計算（Service Computing），已成為軟件領域最熱門的話題之一，是標識分布式系統和軟件集成等方向技術進步的一個新的里程碑。作為一種新型的計算模式，SOC把服務作為基本的組件，用來支持快速、低成本和簡單的分布式，甚至異構環境的應用組合[1]；在服務計算中，服務描述、服務發現、服務組合是其中關鍵的幾個問題。

關于服務組合的方法有很多[2-5]，有基于領域本體、基于語義、基于范例、基于服務關系、采用概率及接口連接關系的各種方法。Lassila等人提出一種基于工作流的Web服務發現和組合方法，但只能處理一般的順序組合問題；付燕寧等提出基于服務鏈的Web服務組合方法，采用從目標服務出發搜索到源服務的反向鏈接方法[6]。但這些方法在進行服務組合時，往往只考慮服務組合的精度問題，而忽略了服務組合的代價問題，當進行服務組合的服務數量規模較小時，大部分的方法都能達到良好的效果，但是當服務的數量較大時，這些方法往往存在組合時間太長甚至在客戶能夠容忍的時間內不能得到組合服務。鑒于上述的問題，本文提出了基于蟻群算法的服務組合方法。

2服務組合

由于服務計算是以服務為最基本的單元，當沒有單個服務滿足某特定服務請求時，可能找到一組Web服務，它們的組合能夠滿足該請求。面向服務的方法要構建的是松耦合、可復用的軟件系統，其中一個關鍵問題是如何將單一功能模塊組合為功能更為復雜的模塊（組合電子服務），從而滿足用戶需求。

服務組合可以通過把小粒度服務組合成大粒度的、具有業務含義的組合服務，可使客戶僅僅關心組合服務的接口和功能而不必知道組合服務的內部組成和結構，有效降低了客戶使用系統的復雜性[7]。同時，電子服務的組合能夠增加互聯網上可用服務的數量。此外，服務組合技術的發展為未來的軟件開發模式奠定了可靠基礎。服務組合可分為兩個階段：服務組合建立階段和運行階段，如圖1所示。組合建立階段依據應用領域和自動化程度，其組合方法分為動態和靜態組合兩類[8]。靜態組合意味著請求者應在組合計劃實施前創建一個抽象的過程模型，即流程建模。抽象的過程模型包括任務的集合以及任務間的數據依賴關系，每個任務包含一個查詢的子句，用來查找完成任務的真正的Web服務。

圖1服務組合實施過程

（1）靜態組合指請求者在組合計劃實施前創建了一個抽象的過程模型，即流程建模。抽象的過程模型包括任務的集合以及任務間的數據依賴關系，每個任務包含一個查詢的子句，用來查找完成任務的Web服務。在靜態組合中，被組合的過程具有固定的特性，被組合的服務在設計時由設計者選擇。

（2）動態組合指組合過程具有動態的特性，通過一定的算法或按照一定的規則選擇所需的原子服務進行組合操作。

在靜態服務組合中，經典的方法是將服務發現中尋找到的原子服務作為候選服務集合，按照服務組合需要的流程將這些候選服務分為不同的層，一個組合服務就是從源頭經過第一層、第二層，…，到達目的地的過程。然后將每個候選的原子服務提供服務時的服務質量作為權重，尋找源頭到目的地之間服務代價最小的路徑，于是就把問題轉換為求解有向無環圖中的最短路徑問題，如圖2所示，其中Si，j中的i表示服務組合中的層數，j表示該層擁有的候選原子服務個數。解決最短路徑的經典算法有Dijkstra算法、Bellman-Ford算法還有很對其他的變形形式，這些方法都是尋找問題的最優解，當候選服務的集合規模比較小時，這些方法有較好的效果，但是當候選服務集合的問題規模比較大時，存在運算量大，運行時間長的問題，通常不能滿足用戶的要求。在實際情況中，對于一些問題的求解往往不需要求解問題的最優解，而只需要求解問題的可行解或者用戶的滿意解。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文