基于ＱｏＳ的組合服務發現與選擇研究
2009-01-01 00:00:00楊清平蒲國林邱玉輝
計算機應用研究 2009年2期
（1.四川文理學院 計算機科學系， 四川 達州 635000;2.西南大學 語義網格實驗室， 重慶 400715）
摘 要：分析了服務間的組合語義和QoS語義，研究了組合服務的發現與選擇過程，并提出了高性價比的服務推薦原則。在組合服務的描述中借鑒了進程代數的思想，對順序組合、選擇組合和并發組合等語義進行了刻畫，這些語義是服務組合的紐帶。在服務發現的過程中，闡釋了exact、plugin、subsume、overlap和fail匹配，兩個服務的匹配度越高表示它們在語義上越相似；在服務選擇的過程中，依據服務的性價比進行選擇推薦，將性價比最高的服務推薦給用戶，讓用戶獲得滿意的服務。該原則在有償服務環境中對普通用戶特別適用。
關鍵詞：組合服務；服務發現；服務選擇；服務質量
中圖分類號：TP393.04 文獻標志碼：A
文章編號：10013695(2009)02056604
Discovery and selection of composite services based on QoS
YANG Qingping1，2，PU Guolin1，2，QIU Yuhui2
(1.Dept. of Computer Science， Sichuan University of Arts Science， Dazhou Sichuan 635000， China;2.Laboratory of Semantic Grid， Southwest University， Chongqing400715， China)
Abstract:This paper analyzed the semantics of composition and QoS between services， and studied the discovery and selection process of composite services，showed a recommend principle of services with high performanceprice. In the description of composite service， through process algebra，depicted the semantics of sequence， selection and subsequence. In the course of service discovery，studied the exact，plugin，subsume，overlap and fail match. Two services were similar on semantics if they matched well.In the process of service selection，selected the service based on the performanceprice， and recommended the service to users with high performanceprice， and made users satisfied. The principle is useful to the ordinary users in the market environment.
Key words:composite services；services discovery；services selection；QoS
0 引言
用戶對服務的內容和質量要求越來越高，而服務的現狀并不令人滿意，主要體現在：a)大量涌現，服務的大量涌現使提供相同功能的服務越來越多；b)缺乏語義，沒有語義描述的服務的發現速度和精度都很低；c)重復匹配，大量重復的服務匹配過程降低了整個系統的效率；d)需求膨脹，在線服務已經不能滿足用戶需求的日益膨脹。因此，通過在線服務的組合形成新的服務成為了研究熱點。
國內外對服務組合的研究很多，也提出了各自的組合方法。這些方法主要有基于工作流的組合方法，如文獻[1~3]；基于規劃的組合方法，如文獻[4~6]；基于服務鏈的組合方法；基于圖搜索的方法等，如文獻[7]。本文對組合服務的研究主要體現在服務組合的語義描述、服務的組合過程、服務發現和服務選擇等方面。對組合服務的描述，既要充分考慮語義問題，又要注重服務質量，使組合而成的新服務不僅在功能上滿足用戶的需求，而且服務質量也有保證。
1 服務和QoS
定義1 服務。服務S在功能上形式化為S=(ID，precondition，input，effect，output，QoS)。其中：ID是服務的惟一標志；precondition是服務執行的前提條件；input是服務的輸入參數集合；effect是服務執行后的顯現效果；output是服務的輸出集合；QoS是服務質量描述，具體見定義2。Precondition、input、effect和output統稱為服務的IOPE。例如，在描述語言OWLS[8]中，ServiceProfile中就有IOPE等內容的描述。
定義2 QoS。服務的QoS是一個可擴展的n元組：QoS=(time，cost，security，reliability， … )。其中:time是服務的平均響應時間；cost是獲取該服務所支付的費用；security是服務的安全等級；reliability是服務的可靠性等。還可以根據需要進行語義擴展。
設id( )、precondition( )、input( )、effect( )、output( )等為服務的特征提取函數，time( )、cost( )、security( )和reliabi-lity( )等為服務的QoS提取函數。例如input(S)表示服務S可以提供的輸入參數集合(如果S是請求服務)，或表示服務S需要的輸入參數集合(如果S是響應服務)；cost(S)表示用戶愿為獲取服務S而支付的最高費用(如果S是請求服務)，或表示服務S的執行費用(如果S是響應服務)。
2 組合服務的語義
2.1 組合服務的描述
定義3 組合服務。組合服務CS定義如下：
CS∷=0|S|!S|S1.S2|S1+S2|(S1|S2)|…
a）0表示空服務。
b）S表示基本服務。本文用基本服務來表示注冊服務庫中的服務。基本服務也可能是經過注冊的更小粒度的組合服務。
c）S1.S2表示服務的順序組合，Si.Sj表示先執行服務Si，Si執行完后再執行服務Sj。
d）!S表示服務S的有限次循環。!S=S.S.S.….S，因此循環可看做是特殊的順序組合。
e）S1+S2表示服務的選擇組合，Si+Sj表示以概率p選擇服務Si，以概率(1-p)選擇服務Sj。
f）S1|S2表示服務的并發組合，Si|Sj表示同時選擇執行服務Si和Sj。
從a）和b）可知，該定義明確地描述了參加組合的實體可以是空服務0、基本服務S和組合服務CS，即組合服務的組合實體可以是粒度更小的組合服務。c）~f）給出了常見的服務組合關系，即服務間的順序組合、循環組合、選擇組合和并發組合等，其中的“…”表示還可擴展加入新的語義組合操作。
本文為了討論的簡易性，假定組合服務CS總可用上述四個基本的組合語義關系進行描述，且定義組合關系運算的優先級由高到低為“（）”“！”“.”“|”“+”。
2.2 服務組合的語義規則
服務在按照一定的語義關系進行組合時，它們之間必須滿足該語義關系的語義組合規則。這些規則描述了兩個服務進行組合時的必要條件，為服務的組合提供了語義基礎。本文主要是從I/O參數和QoS參數進行研究。
1）順序組合的語義規則
規則1 if Si.Sj then input(Sj)output(Si)；
2）選擇組合的語義規則
規則2 if (Si+Sj).Sk then
(input(Sk)output(Si))∧(input (Sk)output(Sj))；
規則3 if Sk.(Si+Sj) then
(input(Si)output(Sk))∧(input(Sj)output(Sk))；
3）并發組合的語義規則
規則4 if (Si|Sj).Sk then input(Sk)(output(Si)output(Sj))；
規則5 if Sk.(Si||Sj) then (input(Si)∪input(Sj))output(Sk)；
4）可擴展規則
可擴展產生其他組合操作，并生成相應的規則。
2.3 服務組合時的QoS語義
1)順序組合時的QoS語義
對于順序組合的n個服務，它們的QoS計算式為
time(CS)=ni=1time(Si)（1）
cost(CS)=ni=1cost(Si)（2）
security(CS)=ni=1security(Si)（3）
reliability(CS)=ni=1reliability(Si)（4）
以上各式同樣適用于循環關系。對于循環次數不確定的，其n的取值用歷史數據的平均值表示。
2)選擇組合時的QoS語義
對于用選擇關系組合的n個服務，它們的QoS計算式為
time(CS)=ni=1pi×time(Si)（5）
cost(CS)=ni=1pi×cost(Si)（6）
security(CS)=ni=1pi×security(Si)（7）
reliability(CS)=ni=1pi×reliability(Si)（8）
其中：pi是服務Si被選擇的概率， 且ni=1pi=1。
3)并發組合時的QoS語義
對于并發組合的n個服務，它們的QoS計算式為
time(CS)=max{time(Si)，i∈{1，…，n}}（9）
cost(CS)=ni=1cost(Si)（10）
security(CS)=ni=1security(Si)（11）
reliability(CS)=ni=1reliability(Si)（12）
4)可擴展的QoS語義
擴展組合操作所對應的QoS語義。
2.4 請求服務和組合服務間的接口語義
服務組合的目的是為了讓用戶獲得滿意的服務。設組合服務CS由服務集{S1，S2，S3，…，Sn}按照上述的組合語義關系組合而成，則（用RS表示請求服務）
input(CS)(∪ni=1input(Si)-∪ni=1output(Si))（13）
output(CS)(∪ni=1output(Si))（14）
顯然CS和RS間的接口滿足如下的語義關系：
input(RS)input(CS)（15）
precondition(RS)precondition(CS)（16）
output(CS)output(RS)（17）
effect(CS)effect(RS)（18）
RS和CS間的QoS還應該滿足：
time(CS)≤time(RS)（19）
cost(CS)≤cost(RS)（20）
security(CS)≥security(RS)（21）
reliability(CS)≥reliability(RS)（22）
式（19）表示服務的響應時間不能高于用戶給定的最長響應時間；式（20）表示服務的收費不能高于用戶愿承擔的最高費用；式（21）表示服務的安全等級不能低于用戶要求的最低安全等級；式（22）表示服務的可靠性級別不能低于用戶要求的可靠性級別。
3 組合服務發現
組合服務發現主要包括基本服務發現、服務組合、排除冗余組合服務和基于QoS的過濾等過程。
3.1 基本服務發現
基本服務發現就是從注冊服務庫中的在線服務中發現可用于組合的服務子集的過程，它是組合服務發現的基礎，它直接關系到用戶能否獲得滿意的服務。本文主要通過語境匹配和輸入/輸出匹配來發現基本服務。
3.1.1 語境匹配
語境匹配有效地解決了同義詞和一詞多義的現象，并得到與當前語境有關的服務集。
在文獻[9]中介紹了當前語境信息的語義抽取過程。其過程簡述如下：首先建立基于WordNet[10]的與當前語境相關的詞法空間；然后根據詞法空間建立本體的概念集；再根據概念集生成詞法本體，該詞法本體表示了當前語境的語義抽取結果。于是語境匹配問題就轉換為詞法本體的匹配問題，本體的匹配技術已經相對成熟。
3.1.2 輸入/輸出匹配
按輸入/輸出的匹配度從大到小分成如下幾個等級：exact、plugin、subsume、overlap和fail匹配[11~13]。Fail匹配表示匹配失敗，所以它不包含在輸入/輸出匹配器中。
假設服務S用本體描述，則從I/O來看有如下定義：
定義4 Exact匹配。服務Si和服務Sj是exact匹配表示為
exact(Si，Sj)={(input(Si) equivalentClass input(Sj))∧
(output(Si) equivalentClass output(Sj))}
定義5 Plugin匹配。服務Si和服務Sj是plugin匹配表示為
plugin(Si，Sj)={(input(Si) subClassof input(Sj))∧(output(Si) subClassof output(Sj))}
定義6 Subsume匹配。服務Si和服務Sj是subsume匹配表示為
subsume(Si，Sj)={(input(Sj) subClassof input(Si))∧(output(Sj) subClassof output(Si))}
定義7 Overlap匹配。服務Si和服務Sj是overlap匹配表示為
overlap(Si，Sj)={(input(Sj) intersectionof input(Si))∧(output(Sj) intersectionof output(Si))}
定義8 Fail匹配。服務Si和服務Sj是fail匹配表示為
fail(Si，Sj)={(input(Sj) disjointWith input(Si))∧(output(Sj) disjointWith output(Si))}
Exact和plugin匹配發現的服務能滿足服務請求的所有要求；subsume匹配只發現了滿足部分服務請求的服務；fail匹配發現的服務不能滿足服務請求；overlap匹配的程度可以通過相似度或語義距離的計算得到，本文不作研究。在輸入/輸出匹配器中，首先進行exact匹配，如果沒有發現原子服務則降低匹配要求進行plugin匹配，依此類推。這個匹配過程是條件泛化繼續匹配直至發現原子服務的過程。一般情況下，通過exact和plugin匹配就能發現多個服務，它們是由不同公司開發的能滿足同一服務請求的服務。正因為如此，必須還要對這些服務進行過濾。
3.2 基本服務的組合過程
以S1.S2組合為例來分析服務組合的過程，如圖1[14]所示。
假設基本服務S1和S2分別用本體O和O′表示，如果O和O′是用不同的本體描述語言描述，則其匹配過程為：
a)將S1和S2中的I/O術語用公共本體中的術語進行描述；
b)將output(S1)和input(S2)在匹配器matcher中進行語義匹配，并將其對應關系保存在A中；
c)中間件mediator利用A中的對應關系完成output(S1)和input(S2)之間的轉換，實現S1.S2的組合。
如果O和O′是用相同的本體描述語言描述，則跳過步驟a)。
3.3 過濾
3.3.1 排除冗余的組合服務
運用集合就可以完成冗余的組合服務。設組合成CS1的基本服務集為S，組合成CS2的基本服務集為S*。如果SS*，則CS*是冗余的，因此從組合服務集中刪除CS2。
3.3.2 基于QoS的過濾
先用式（1）~（12）計算各組合服務的QoS性能參數值，然后用式（19）~（22）對組合服務進行過濾，刪除那些能滿足用戶功能但不能滿足用戶對服務質量要求的組合服務。
通過QoS過濾得到一個服務集，其中的每一個組合服務都能滿足用戶的服務請求，同時也符合用戶對服務質量的要求。
4 組合服務選擇
當組合服務發現的組合服務集中不止一個組合服務時，究竟選擇哪一個組合服務作為推薦服務呢？在此，首先給出基于QoS的服務性價比的定義。
定義9 服務性價比。用(time， cost， security， reliability， … ，)描述服務S的QoS，則其性價比λ(S)定義如下：
λ(S)=security(S)×reliability(S)/（time(S)×cost(S)）（23）
其中：security(S)×reliability(S)/time(S)是對QoS性能的刻畫，它與安全和可靠性成正比，與響應時間成反比；cost(S)是價格。
對于組合服務CS，首先用式（1）~（12）計算出CS的QoS各屬性值，然后利用式（23）計算λ(S)。雖然不同的用戶群對QoS的要求不同，但追求高性價比是用戶的普遍要求，于是按高性價比選擇原則從組合服務集中選擇服務推薦給用戶。
5 實例分析
設注冊服務Si和請求服務RS的各參數描述如表1所示。其中的QoS參數是某一時刻的參數值，并假定除S1到S7以外的其他服務都與RS無關。
表1 服務參數值表
服務inputoutputtimecostreliabilitysecurity
S1A，B，CD，E，F350.980.83
S2D，E，FG， H570.960.86
S3D，EG120.910.95
S4E，FH330.940.89
S5G，HM，N240.950.90
S6A， JK130.870.93
S7D， F，H，J，K700.910.96
…………………
RSA，B，CM，N10180.750.6
由表1可知，注冊服務庫中沒有一個服務能直接滿足用戶的服務請求RS。顯然只能通過服務組合的方式來滿足用戶的服務需求。
系統首先發現有多種服務組合可以完全滿足用戶服務請求的功能，它們分別是CS1=S1.S2.S5，CS2=S1.(S3|S4).S5，CS3=S1.(S2|S3).S5，CS4=S1.(S2|S4).S5，
CS5=S1.(S2|S3|S4).S5。但是，這些組合服務中的CS3、CS4和CS5對CS1來說是冗余的，應該排除。
緊接著再對剩余的組合服務CS1和CS2進行基于QoS的過濾。它們的QoS屬性值經過計算列于表2。通過該表發現，它們都符合用戶的服務質量要求。
表2 基于QoS的服務過濾表
服務timecostreliabilitysecurity
CS110160.893 760.642 42
CS28140.796 377 40.631 588 5
RS10180.750.6
最后按高性價比原則從其中選擇一個組合服務作為推薦服務。利用式（23）和表2計算各組合服務的性價比，得到
λ(CS1)=3.588 555 812×10-3，λ(CS2)=4.490 917 924×10-3
該結果已經說明CS2的性價比比CS1的性價比高，所以推薦CS2作為RS的響應服務。當然也可對結果進行歸一化處理后再比較，這樣更直觀。
服務的性能是變化的，如響應的時間就與網絡的狀態有關。具體到本例來說，完全有可能在某時刻CS1的性價比比CS2的高，此時就應該推薦CS1作為用戶請求的響應服務。通過下面的方法可以將這兩種情況統一起來。
比如，對過去的一個時間段進行統計，得知CS2作為響應服務的概率為p，而CS1作為響應服務的概率為1-p，則CS1和CS2可以組合成一個新的組合服務CS，其組合方式為CS=S1.(S2+S3|S4).S5，也可直觀地表示為圖2的形式。
組合服務一旦形成，就可以注冊成為一個基本的服務，這樣可提高服務發現的速度。當然該組合服務也可作為粒度更大的組合服務的基本服務。
6 結束語
服務組合主要有兩種情況：用戶提出的服務請求超出了在線服務的服務能力；服務提供商有意識地挖掘可組合的服務，以形成新的服務點。因此，服務組合不僅能滿足用戶的更多需求，而且還給服務提供商創造了新的商機。
本文重點分析了服務組合時的順序、選擇和并發語義以及QoS語義，對其他復雜的語義關系沒有深入研究；在服務組合時，主要考慮了I/O參數和QoS參數，而對PE參數等研究較少。這些也正是下一步的研究重點。
參考文獻：
［1］
CARDOSO J，SHETH A.Semantic eworkflow composition[J].Journal of Intelligent Information System，2003，12(3):191225.
[2]HAMADI R，BENATALLAH B.A Petri netbased model for Web service composition[C]//Proc of the 14th Australasian Database Conference.2003:191200.
[3]胡海濤，李剛，韓燕波.一種面向業務用戶的大粒度服務組合方法[J].計算機學報，2005，28(4):694703.
[4]WU D，PARSIA B，SIRIN E，et al.Automating DAMLS Web services composition using SHOP2 [C]//Proc of Int’l Semantic Web Conference.2003:250262.
[5]RAO J H，KUNGAS P，MATSKIN M.Logicbased Web services composition: from service description to process model [C]//Proc of Int’l Conference on Web Services.San Diego:IEEE Computer Society，2004:446453.
[6]AKKIRAJU R， SRIVASTAVA B，IVAN A A，et al.SEMAPLAN:combining planning with semantic matching to achieve Web service composition[C]//Proc of Int’l Conference on Web Services.2006:3744.
[7]劉家茂，顧寧，施伯樂.基于mediator的Web services 無回溯反向鏈動態合成[J].計算機研究與發展，2005，42(7):11531158.
[8]MARTIN D，BURSTEIN M，HOBBS J，et al.OWLS:Semantic markup for Web Services[EB/OL].(2004).http://www.w3.org/Submission/OWLS.
[9]陳旺虎，劉晨，李厚福，等.支持虛擬組織的語義基礎設施的動態構建方法研究[J].計算機學報，2006，29(7):11301132.
[10]KORNILAKIS H，GRIGORIADOU M，PAPANIKOLAOU K A，et al.Using WordNet to support interactive concept map construction[C]//Proc of IEEE International Conference on Advanced Learning Technologies.Washington DC:IEEE Computer Society，2004:600604.
[11]PAOLUCCI M，KAWAMURA T，PAYNE T R，et al.Semantic matching of Web services capabilities[C]//Proc of International Semantic Web Conference.2002:333347.
[12]CONSTANTINESCU I，FALTINGS B，BINDER W.Large scale typecompatible service composition[C]//Proc of IEEE International Conference on Web Services.2004:506513.
[13]LI Lei，HORROCKS I.A software framework for matchmaking based on semantic Web technology[C]//Proc of the 12th International World Wide Web Conference.2003:331339.
[14]EUZENAT J，SHVAIKO P.Ontology matching [M].Berlin:Springer，2007:1920.
