語義Web服務的非功能性匹配研究

向朝參，田 暢，趙文棟，聶景楠

（解放軍理工大學 通信工程學院，南京 210007）

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，服務規(guī)模日益擴大，對用戶的同一服務需求，可能出現(xiàn)多個提供者提供功能相似的服務[1]；同時，現(xiàn)在很多用戶要求服務不僅滿足一定的功能屬性（function），而且還要滿足一定的非功能屬性（non-function）。因此，如何從眾多功能相似的服務中選擇最好且最適合用戶的服務，成為首要問題。首先，根據(jù)服務的功能性匹配選擇出功能相似的候選服務；然后，利用服務的非功能性匹配從候選服務中選擇最好的服務給用戶；從而，使匹配的服務更滿足用戶的需求，提高服務發(fā)現(xiàn)的精度和成功率?？梢钥吹剑Z義服務的非功能性匹配是服務匹配的關鍵，直接決定著用戶獲取服務的效率和精度，并成為近年來的研究熱點。學術(shù)界從不同側(cè)面對它進行了研究[1－15]，取得了很多研究成果和進展。文獻[16]對2004年以前的Web服務核心技術(shù)進行了綜述，由于語義Web服務的非功能性匹配是近年來的新概念和熱點，因此，在該文獻中較少討論。文獻[17]只重點對近年來的語義描述語言以及發(fā)布模型等基礎技術(shù)進行總結(jié)。雖然文獻[18]綜述了基于QoS的Web服務選擇算法，但它主要從選擇問題模型、選擇策略和選擇算法3方面進行總結(jié)，筆者從完全不同的視角對近年來語義Web服務的非功能性匹配研究進行梳理和綜述，為語義Web服務的進一步發(fā)展提供技術(shù)支持和幫助。

1 語義Web服務匹配的基本概念

語義Web服務匹配是指利用服務的語義描述，根據(jù)用戶的服務需求選擇相應的服務，是語義服務發(fā)現(xiàn)的關鍵，其成功與否直接影響服務發(fā)現(xiàn)的結(jié)果。

按照服務匹配個數(shù)可分為單服務匹配和服務組合匹配。服務組合匹配是利用服務的可重用性，將多個服務進行組合，以滿足用戶的需求，為用戶提供更加豐富和強大的服務。按照服務匹配的依據(jù)條件可分為服務的功能性匹配和服務的非功能性匹配。服務的功能性匹配是指依據(jù)服務的功能選擇用戶所請求的服務；服務的非功能性匹配是指在服務的功能性匹配基礎上，根據(jù)服務的非功能屬性選擇更加滿足用戶需求的服務。在這兩種匹配方式中，服務的功能性和非功能性匹配是基礎，單服務匹配和服務組合匹配都需基于服務的功能性和非功能性匹配進行服務選擇，其關系如圖1所示。

圖1 語義服務匹配關系圖Fig.1The relationships of semantic service matching

2 語義Web服務的非功能性匹配

語義Web服務的非功能性匹配是指依據(jù)服務的非功能屬性進行匹配。非功能屬性是指關于服務除了功能屬性以外的任何性質(zhì)，一般包括服務的QoS（Quality of Service）和Context，如，獲取時間、費用、獲取率、信譽度和上下文等。由于最近幾年研究服務的QoS匹配比較多，是當前Web服務發(fā)現(xiàn)研究的一個熱點，因此下面重點對當前服務的QoS匹配的研究進行分析和總結(jié)。

服務的QoS是指服務質(zhì)量，如，費用、獲取率和獲取時間等，在不同的應用場景中其定義不同。服務QoS匹配的一般原理：從已匹配的滿足用戶功能需求的候選服務集中，根據(jù)各服務的QoS，選擇出滿足該用戶請求服務的QoS約束條件且QoS性能最好的服務給用戶。

根據(jù)近年服務QoS匹配研究和發(fā)展情況，按照層層遞進的關系，對服務QoS匹配問題進行分解、歸納和組織，研究框架結(jié)構(gòu)圖如圖2所示。首先，研究單個服務的QoS，包含3個子問題：1）服務QoS屬性值的定義和表示；2）服務QoS屬性值的計算；3）服務QoS值的注冊和更新。然后，根據(jù)單個服務的QoS值，研究組合服務QoS值的計算問題。最后，對于單服務和組合服務，根據(jù)服務的QoS值，研究服務的匹配問題。下面將分別從這5個問題討論語義Web服務的QoS匹配。

圖2 服務QoS匹配研究框架Fig.2The research framework of service QoS matching

2.1 服務QoS屬性值的定義和表示

服務QoS，由多個服務QoS屬性值組成。目前在學術(shù)界沒有給出一個明確、統(tǒng)一的分類方式，按照QoS屬性值大小和服務質(zhì)量的關系可分為：QoS正比屬性和QoS反比屬性。QoS正比屬性是指屬性的值與服務質(zhì)量成正比，屬性值越大，服務的質(zhì)量越好；QoS反比屬性是指服務質(zhì)量與屬性值成反比，屬性值越大，服務的質(zhì)量越差[1]。按照QoS屬性值的來源可分為：服務提供者發(fā)布的QoS屬性值（Provider-QoS）和服務使用者反饋的QoS屬性值（Client-QoS）[4]。前者由服務提供者確定和發(fā)布，屬于服務提供者對該服務質(zhì)量的承諾[1，6，8－10，19－23]；后者由使用過該服務的用戶反饋獲得，屬于服務使用者對使用服務后的反饋[11]。還有很多QoS屬性值分類方式，這里不再一一列舉，其中最常見的分類方式是按照服務QoS屬性值的來源分類，因此，下面幾個問題的討論都是基于該分類方式進行的。

服務QoS的表示一般采用單個數(shù)值的形式，如文獻[1，13]等，但由于應用場景和QoS屬性多種多樣，用單個數(shù)值很難準確地描述服務QoS的各種屬性值，如服務獲取時間需要采用區(qū)間范圍的形式，可靠性需要采用模糊等級的形式等。因此，文獻[20]針對服務QoS屬性表示的多樣性，提出了3種表示方法：單個數(shù)值、區(qū)間和模糊語言，并采用去模糊化、標準化以及歸一化對這3種QoS表示方式的屬性值進行統(tǒng)一處理，便于組合服務的QoS計算。該方法較全面地包含了當前服務研究中所涉及的QoS屬性值的幾種表示方式。

2.2 服務QoS屬性值的計算

服務提供者發(fā)布的QoS屬性（Provider-QoS）由服務提供者直接發(fā)布和設定，無需計算。對服務QoS屬性值計算的研究都集中于服務使用者反饋的QoS屬性值（Client-QoS）的計算，如服務的信譽度Reputation和可靠性等。在Client-QoS屬性中，一種是直接利用用戶反饋的歷史信息預測其服務QoS值，如可靠性、獲取時間和獲取率等；另一種是根據(jù)用戶反饋的QoS值結(jié)合服務提供者發(fā)布的QoS值計算其服務的信譽度Reputation。下面將分別從這兩個方面對服務QoS屬性值的計算進行分析和討論。

2.2.1 基于用戶反饋的歷史QoS信息預測服務的QoS屬性值

Client-QoS計算的關鍵是如何根據(jù)歷史服務QoS信息準確地預測現(xiàn)在服務的QoS值。文獻[24]針對單純利用歷史服務QoS信息的平均值預測現(xiàn)在的QoS信息，而不考慮各個歷史服務QoS信息的貢獻程度不同，導致預測服務QoS不準確這一問題，通過計算服務之間和用戶之間的相似度，對歷史服務QoS信息進行加權(quán)求和，以提高服務QoS預測的準確度，其預測準確度較取平均值有很大提高，但由于根據(jù)服務和用戶之間相似度確定權(quán)重不太準確，QoS預測還存在較大的誤差。文獻[3]利用Markov鏈進行服務QoS的預測，以提高服務QoS的預測精度。這種方法預測精度高，但缺點是時間復雜度是指數(shù)階。因此，如何根據(jù)各種不同的應用場景，折衷服務QoS預測的精度和計算復雜度是需要進一步研究的問題。同時，對于各種各樣的服務QoS預測算法，如何評價和比較各種預測算法也是一個難點。文獻[22]利用連續(xù)4個月每天觀察24h的6個服務的QoS實際數(shù)據(jù)，用預測準確率和違反約束檢測概率兩個指標，對幾種經(jīng)典的、簡單的服務QoS預測方法進行比較，從而選擇出最好的預測方法。但該方法只是針對了幾個簡單的預測算法進行比較，如，平均值法、最新值法和線性預測算法等，并且其考慮的指標比較少，不夠全面，沒有考慮其預測算法的時間復雜度等。

2.2.2 信譽度Reputation的計算

信譽度是指服務的可信程度，其提出的背景是：在松散的SOA架構(gòu)中，各服務提供者和用戶之間松散動態(tài)耦合，可能出現(xiàn)服務提供者提供的服務QoS不可靠的情況，因此需要信譽度這一指標作為服務QoS的一個屬性描述服務的性能。例如，它可以通過用戶實際獲得的服務QoS值與服務提供者發(fā)布的QoS值之間的差值決定，差值越大，服務的信譽度越低，反之亦然。

文獻[2]通過獲取該服務提供者的歷史用戶反饋的信譽度，計算其服務提供者的信譽度，同時，在計算過程中考慮了各個歷史用戶以及反饋信譽度值的權(quán)重等因素。其優(yōu)點是對影響服務提供者信譽度值的因素考慮比較全面，計算的信譽度值較準確，但是計算較復雜，且需要大量的關于該服務提供者的交互歷史信息，對剛進入系統(tǒng)的提供者或歷史交互信息缺乏的服務提供者不公平。文獻[15]為了提高公平性，采用了兩種方法計算歷史交互信息缺乏的服務提供者的信譽度：1）利用其服務提供者開始幾次交互信息的信譽度計算其初始信譽度；2）通過中間管理者計算其信譽度。文獻[25]為解決在實體交互反饋信息較少的情況下，能準確地計算實體信譽度這一問題，根據(jù)實體對其直接交互實體的直接信譽度矩陣以及其他實體之間交互反饋的QoS信息，計算實體對其它未直接交互實體的間接信譽度矩陣，以豐富實體之間的信譽度信息。前面都是針對計算單服務的信譽度，對于組合服務的信譽度計算，文獻[26]提出根據(jù)用戶對組合服務反饋的信譽度計算其各原子服務的信譽度的方法，以保證公平性，它根據(jù)各原子服務的權(quán)重和歷史信譽度將組合服務的信譽度公平地分配到各原子服務中。

在松散的SOA架構(gòu)中，不僅服務提供者不可靠，而且部分服務使用者也可能不可靠，從而導致反饋的QoS值虛假，如，某個用戶和某個服務提供者合謀，虛假地反饋很高的QoS值，實行共謀欺騙等。針對服務提供者和用戶發(fā)布QoS不可靠的問題，文獻[27]針對虛擬計算環(huán)境中各自主節(jié)點為追求自身利益最大化而不合作的問題，提出非重復博弈的懲罰激勵機制，促使各節(jié)點自覺采取誠實合作策略，同時避免了節(jié)點進行共謀欺騙。由于松散耦合的SOA架構(gòu)中各節(jié)點也是自主節(jié)點，并且服務提供者和服務反饋者發(fā)布QoS不可靠問題也是因為它們不合作導致的，因此該問題可以借鑒非重復博弈的懲罰激勵方法，但也存在一定的區(qū)別，如兩個問題中的收益矩陣不同，則兩問題的解決方法也有所不同。文獻[25]基于每個用戶只相信自己反饋的QoS信息這一前提，每個用戶獨立地建立自己對其他服務提供者的信任度矩陣，然后，根據(jù)自己的信任度矩陣選取服務，因而，能識別出不可靠的節(jié)點，且計算的服務信譽度值比較準確，但這種方法比較復雜，每個用戶都需要維護一個對其他節(jié)點的信任度矩陣，內(nèi)存消耗大。如何解決服務提供者和服務反饋者的不可靠性問題是計算信譽度的一個難點。

計算信譽度需要收集歷史交互用戶反饋的QoS信息，然而，當歷史交互用戶數(shù)量龐大時，收集歷史用戶反饋的QoS信息將導致網(wǎng)絡開銷和計算資源耗費很大。文獻[28]針對在開放的系統(tǒng)中廣泛收集服務的反饋信息帶來網(wǎng)絡開銷大的問題，在收集服務的反饋信息前，計算各反饋者的信譽，從信譽最高的幾個用戶收集信息，這樣既保證了反饋信息的準確性，又減少了網(wǎng)絡開銷，然而，這種方法的缺點是反饋者信譽計算復雜。

2.3 服務QoS值的注冊和更新

由于服務QoS值由服務提供者發(fā)布或用戶反饋，而服務匹配是在服務注冊代理中進行，因此需要服務提供者或用戶到服務注冊代理中進行服務QoS注冊，從而便于服務注冊代理進行服務QoS的匹配，同時，由于服務QoS值隨著時間可能發(fā)生動態(tài)變化，因此，需要對服務注冊代理中的服務QoS值進行及時更新。

最簡單的服務QoS注冊方式是將作為服務描述的一部分包含到服務描述本體中，和服務的功能描述一起注冊，文獻[29]將基于語義的服務描述語言OWL-S進行擴展，以包含服務的QoS信息，提出了OWL-QoS服務描述語言。這種方法簡單，不需要對以前的基于語義的服務發(fā)現(xiàn)結(jié)構(gòu)進行太大改變，但服務功能一般比較穩(wěn)定，變化較慢，而服務QoS值隨著時間動態(tài)變化，在對服務的QoS進行更新時也要對不需更新的服務功能描述進行更新，從而造成計算資源的浪費和更新開銷的大幅度增加。文獻[30]隨機抽查了正在運行的Internet服務注冊庫，發(fā)現(xiàn)在測試的1 405個服務樣本中，只有17%的服務有效，由此更加說明了服務的QoS動態(tài)變化快，因此，需要將服務的QoS和服務功能描述進行分開注冊，便于服務QoS的及時更新[31]。服務QoS的注冊方法與服務功能描述的發(fā)布方法和原理類似。

服務QoS的更新可以分為周期查詢式、集中監(jiān)管式和判斷＋更新方式[4]。周期查詢式是指服務匹配代理周期性地向服務QoS發(fā)布者查詢和獲取最新的服務QoS值，然而，這種方法受查詢周期影響較大，如果更新過快，網(wǎng)絡負載較大，且存在很多無效查詢；如果更新太慢，服務QoS更新不及時[4]。集中監(jiān)管方式是指設置一個集中監(jiān)管服務器進行服務QoS的評估、監(jiān)管和更新[7]，但由于采用集中式，存在單點故障和系統(tǒng)瓶頸等缺點。判斷＋更新方式是指根據(jù)一定的準則判斷服務QoS值是否過期，如果判斷過期，則進行更新，所以既避免了頻繁更新增加網(wǎng)絡負載，又保證了服務QoS及時更新。文獻[32，33]以服務注冊代理為中心，采用兩種方法：一種方法是判斷如果服務提供者發(fā)布的QoS與用戶反饋的QoS差值大于某個閾值，則增加服務QoS值的更新頻率[33]；另一種方法是判斷如果用戶反饋的QoS值超出原QoS值某個置信度下的范圍，表明服務原QoS值可能過期，則對服務QoS進行重新計算和更新[32]。文獻[4]以服務QoS發(fā)布者為中心，采用發(fā)布／訂閱機制，服務注冊代理向各服務QoS存儲節(jié)點訂閱服務QoS更新服務，提出服務QoS更新條件，當該服務的QoS變化滿足訂閱的服務QoS更新條件時，則服務QoS存儲節(jié)點主動將服務QoS發(fā)給服務注冊代理進行更新，同時，對組合服務QoS更新進行優(yōu)化。因只有當整個組合服務的QoS更新條件滿足時才進行更新，所以既保證了服務QoS的及時更新，又降低了網(wǎng)絡開銷，但各節(jié)點交互、合作機制較復雜。如何在保證服務QoS實時更新的情況下，盡量降低網(wǎng)絡QoS注冊和更新的開銷是當前研究的一個方向。

2.4 組合服務的QoS值計算

組合服務的QoS計算是指根據(jù)各個服務的QoS值和服務功能組合流程，計算服務組合總的QoS值。服務功能組合流程一般包含4種結(jié)構(gòu)（見圖3），不同結(jié)構(gòu)對應服務組合總的QoS值的計算公式也不同。文獻[1]分別對這4種結(jié)構(gòu)進行了分析，并給出了各種結(jié)構(gòu)的服務組合QoS值的計算公式。大部分結(jié)構(gòu)組合服務QoS的值計算比較簡單，然而由于條件結(jié)構(gòu)的組合服務具有多條執(zhí)行路徑，并且各條路徑執(zhí)行是隨機的，具有一定的概率，其中P1和P2分別表示兩執(zhí)行路徑發(fā)生的概率，因此計算條件結(jié)構(gòu)的組合服務QoS的值較復雜。一種計算方法是文獻[1]采用的以各執(zhí)行路徑QoS的概率平均值作為組合服務QoS的值。該方法簡單，且能較準確地描述組合服務總的QoS值，因此現(xiàn)在的服務組合匹配一般都采用這種計算方法，但因只是通過概率平均值描述組合服務QoS的值，不夠準確。如果要求服務的QoS值嚴格滿足用戶的約束要求，則可以采用執(zhí)行路徑中最小的QoS值作為組合服務的QoS值[21]。但由于各執(zhí)行路徑具有一定概率，因此，組合服務的QoS值是隨機值。文獻[21]提出了組合服務QoS值具有不確定性這一概念，通過將服務組合結(jié)構(gòu)轉(zhuǎn)換為樹形結(jié)構(gòu)，計算組合服務總的QoS值的概率分布，從而能更準確地描述組合服務QoS的值，但問題的關鍵和難點是如何基于不確定的組合服務QoS值匹配服務。為了解決基于隨機性服務QoS值的匹配問題，文獻[13]首先選擇出具有一定置信度的服務集，然后用戶根據(jù)自己的需求從中選擇所需的服務，從而避免了由服務QoS值的隨機性帶來的服務匹配不準確的問題。文獻[32]將基于隨機QoS值的服務組合匹配問題轉(zhuǎn)化為隨機型離散事件系統(tǒng)動態(tài)尋優(yōu)過程，并采用馬爾可夫決策模型進行基于隨機QoS值的服務組合，以提高服務發(fā)現(xiàn)的精度。這兩種方法解決了具有隨機性的服務QoS的匹配問題，但具有一定概率分布的服務QoS匹配問題還有待進一步的研究。

圖3 服務組合流程的4種結(jié)構(gòu)Fig.3The workflow of service composition

2.5 服務QoS的匹配

當各服務的QoS值都已經(jīng)計算出來，如何進行服務匹配。這對于單服務，是一個遍歷候選服務集、時間復雜度為O（N）的簡單問題；而對于組合服務，是個較復雜的問題，其匹配策略通常包括局部最優(yōu)、全局最優(yōu)和混合式3種。由于在組合服務QoS的局部最優(yōu)組合匹配中，單個子功能的服務QoS匹配等同于單服務的QoS匹配，組合服務的局部最優(yōu)匹配問題包含單個服務的QoS匹配問題，因此，很少單獨研究和討論單服務的QoS匹配問題，下面將分別從局部最優(yōu)、全局最優(yōu)以及混合式3種策略討論組合服務的QoS匹配問題。

2.5.1 局部最優(yōu)組合匹配

分別對服務功能組合流程中的各子功能基于服務QoS選擇出最好的服務，然后將服務按照服務功能組合流程的結(jié)構(gòu)組合起來[34]。即局部最優(yōu)組合匹配的核心是基于服務QoS的單服務匹配。而要實現(xiàn)單服務的QoS匹配，首先要將服務的各QoS屬性值根據(jù)其權(quán)重加權(quán)求和，計算出服務總的QoS；然后根據(jù)服務總的QoS，選擇滿足用戶約束條件且最好的服務。因此，單服務QoS匹配的核心是服務QoS各屬性值的定義、表示和計算以及權(quán)重的確定。下面主要對服務各QoS屬性值的權(quán)重確定問題進行分析和討論。

服務QoS屬性值的權(quán)重是指各QoS屬性值對總的服務質(zhì)量的重要程度。其權(quán)重確定模式一般分為主觀賦權(quán)模式、客觀賦權(quán)模式、主客觀賦權(quán)模式和無權(quán)模式4種。主觀賦權(quán)模式是指用戶指定每個QoS屬性值的權(quán)重，這種方式比較簡單、易用[1，8]，但沒有考慮實際客觀的QoS屬性值。而客觀賦權(quán)模式避免用戶對各個QoS屬性值賦權(quán)的主觀性，從QoS屬性值的客觀性出發(fā)，根據(jù)實際服務QoS屬性值計算出其權(quán)重。文獻[34]根據(jù)QoS屬性值在各個服務中的一致性度量該QoS屬性值的權(quán)重，一致性好的QoS屬性值權(quán)重高。主客觀賦權(quán)模式在對服務各QoS屬性值賦權(quán)重時，既考慮了用戶的主觀性，又考慮了實際QoS值的客觀性，綜合前面兩種賦權(quán)模式。文獻[34]將主客觀賦權(quán)模式的權(quán)重計算問題轉(zhuǎn)化為一個雙目標的優(yōu)化問題來計算。無權(quán)模式則避免了各QoS屬性權(quán)重的不確定性和用戶主觀賦權(quán)的不準確性，在服務匹配過程中不考慮各QoS屬性的權(quán)重，如文獻[13]為了避免用戶描述各QoS屬性權(quán)重的不準確性問題，首先利用數(shù)據(jù)庫研究中常用的Skyline計算選擇候選服務集，然后用戶根據(jù)自己的需要和偏好從中選擇服務。由于其服務集中最差的服務都至少存在一個屬性值比服務集以外的任何服務都好，因此，無論用戶指定的各服務QoS屬性值的權(quán)重是多少，選出的服務都能滿足用戶的需求。為了解決由于QoS各個屬性值之間存在不確定的關系導致其權(quán)重很難確定的問題，文獻[35]采用無權(quán)模式，先定義了聯(lián)合計算公式計算多個QoS屬性聯(lián)合對服務質(zhì)量的貢獻值，然后根據(jù)這個貢獻值選擇服務。這4種賦權(quán)模式各有優(yōu)缺點和適用條件，總結(jié)如表1所示。

表1 局部最優(yōu)服務組合匹配的4種賦權(quán)模式的比較Tab.1Comparison in four modes of locally optimal service composition matching

2.5.2 全局最優(yōu)組合匹配

基于服務QoS的全局最優(yōu)組合匹配是指根據(jù)整個組合服務的QoS值選擇出滿足用戶QoS約束條件且QoS值最優(yōu)的服務。它是多約束的單目標優(yōu)化問題[1]，其基本模型如式（1）所示，其中F（qi）表示第i個服務組合總的QoS值qi對服務質(zhì)量的效用函數(shù)值，qji表示第i個服務組合中第j個QoS屬性值，Qj表示用戶對服務組合中第j個QoS屬性值的約束要求

由于全局最優(yōu)組合匹配問題是個 NP完全問題，通常采用啟發(fā)式算法[1，8，9，19，36]求解。文獻[1]將這個多約束的目標優(yōu)化問題轉(zhuǎn)化為0-1整數(shù)規(guī)劃問題和有向無循環(huán)圖的多約束最優(yōu)路徑選擇問題，提出了時間復雜度為指數(shù)階的最優(yōu)化算法和時間復雜度為多項式階的啟發(fā)算法。文獻[9，19，36]采用遺傳算法解決這個多約束的目標優(yōu)化NP完全問題。為提高最優(yōu)解的收斂速度，文獻[37]采用離散微粒群進化算法。文獻[8]采用啟發(fā)算法，以最快的速度和步數(shù)找到滿足用戶QoS約束的服務組合次優(yōu)解代替最優(yōu)解，以降低服務組合匹配的時間復雜度，并盡可能找到接近最優(yōu)解的次優(yōu)解。因此，在保證接近服務組合的最優(yōu)解情況下，盡量降低服務匹配的復雜度是當前全局最優(yōu)服務組合匹配研究的一種趨勢，如何在這兩個指標上進行很好的折衷是當前一個難點。

2.5.3 混合式組合匹配

將全局最優(yōu)組合匹配和局部最優(yōu)組合匹配方法進行結(jié)合和折衷，以利用兩種匹配方法的優(yōu)點，在保證得到的匹配結(jié)果接近最優(yōu)解的情況下，盡量降低服務匹配的時間復雜度。由于組合服務的全局最優(yōu)解的子服務一般都在各個子功能的局部最優(yōu)解附近[34]，因此，文獻[12，34，38]采用基于服務QoS的混合式組合匹配，先根據(jù)局部最優(yōu)縮小各子功能候選服務集的范圍，并按照服務的QoS對候選服務進行排序，然后根據(jù)得到的各子功能局部最優(yōu)候選集和排序結(jié)果選擇滿足用戶QoS的全局約束條件的最優(yōu)服務組合，文獻[39]提出將組合服務的用戶QoS全局約束條件按照一定的準則分配到各個子功能中，然后各子功能基于被分配的QoS約束條件進行局部最優(yōu)服務匹配，最后將各子功能的局部最優(yōu)解進行組合。由于其準則保證了滿足各子功能QoS約束條件的子服務的組合也能滿足用戶的QoS全局約束條件，因此，該方法在滿足用戶QoS全局約束條件下，將局部最優(yōu)解進行組合，以得到近似最優(yōu)解。這兩種方法的優(yōu)點是在得到近似最優(yōu)解的情況下，降低了服務匹配的時間復雜度，但得到的近似解接近最優(yōu)解的程度較難控制。

這3種服務QoS的匹配方式各有優(yōu)缺點和適用條件（見表2），需要根據(jù)服務發(fā)現(xiàn)的不同要求采取相應的服務QoS匹配方式。

表2 服務QoS匹配3種方式的比較Tab.2Comparison in three ways of service QoS matching

3 總結(jié)與展望

近年來，語義Web服務成為SOA架構(gòu)研究的一個主要領域[40]，成為當前研究的熱點[41]。它的應用規(guī)模和范圍日益擴大，不僅局限于互聯(lián)網(wǎng)中傳統(tǒng)的web服務，還可以將不同硬件設備互聯(lián)，便于其功能共享和重組，如 RBS[42]，ISR[43]、信息柵格（Information Grid）等。在語義 Web服務的實現(xiàn)和研究中，服務匹配是關鍵和難點，而語義Web服務的非功能性匹配又是服務匹配的關鍵和當前研究的熱點。工業(yè)界和學術(shù)界都從不同方面對此進行研究，并從理論和應用兩個方面提出了各種原型系統(tǒng)和實際應用產(chǎn)品。筆者重點從5個問題出發(fā)，全面而又細致地總結(jié)和分析了當前研究熱點——語義Web服務的非功能性匹配的研究現(xiàn)狀，既討論了各種匹配方法提出的背景，又分析了它們之間的關系，還比較了各自的優(yōu)缺點。

雖然語義Web服務的非功能性匹配是近兩年研究的熱點，研究較多，但從前面的分析中發(fā)現(xiàn)還存在很多值得研究的問題，如，如何對QoS屬性值進行統(tǒng)一的、比較完整地分類；如何在實際工程中定義服務的QoS屬性值以及實現(xiàn)服務QoS的匹配；采用何種算法使基于用戶歷史反饋QoS信息更加準確地預測服務現(xiàn)在的QoS值；如何比較和評估各種預測算法；如何更加準確地計算服務的信譽度值；如何解決服務提供者和用戶反饋QoS值不可靠的問題；如何使服務QoS實時更新且保持低的網(wǎng)絡開銷；如何解決服務QoS注冊、更新負載均衡；如何解決隨機變化的或具有一定概率分布的QoS值的服務匹配問題；在保持服務匹配QoS全局最優(yōu)性基本不變的情況下，如何盡量提高服務組合發(fā)現(xiàn)的速度以及降低組合的開銷等。筆者正在對這些問題進行進一步研究。

：

[1]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，2007，1（1）：1-26.

[2]MALIK Z，BOUGUETTAYA A.RATEWeb：Reputation Assessment for Trust Establishment among Web Services[J].The VLDB Journal，2009，18（2）：885-911.

[3]STRUNK A.An Algorithm to Predict the QoS-Reliability of Service Compositions[C]∥2010IEEE 6th World Congress on Services.[S.l.]：IEEE Computer Society，2010：205-212.

[4]鄭嘯，羅軍舟，曹玖新，等.基于發(fā)布／訂閱機制的 Web服務QoS信息分發(fā)模型[J].計算機研究與發(fā)展，2010，47（6）：1088-1097.

ZHENG Xiao，LUO Jun-zhou，CAO Jiu-xin，et al.A Publish／Subscribe Based Information Dissemination Model for QoS of Web Services[J].Journal of Computer Research and Development，2010，47（6）：1088-1097.

[5]蔣哲遠，韓江洪，王釗.動態(tài)的QoS感知 Web服務選擇和組合優(yōu)化模型[J].計算機學報，2009，32（5）：1014-1025.JIANG Zhe-yuan，HAN Jiang-hong，WANG Zhao.An Optimization Model for Dynamic QoS-Aware Web Services Selection and Composition[J].Chinese Journal of Computers，2009，32（5）：1014-1025.

[6]LI S C，CHEN H P，CHEN X.A Mechanism for Web Service Selection and Recommendation Based on Multi-QoS Constraints[C]∥2010 6th World Congress on Services.[S.l.]：IEEE Computer Society，2010：221-228.

[7]BENHARREF A，SERHANI M A，BOUKTIF S，et al.A Managerial Community of Web Services for Management of Communities of Web Services[C]∥10th Annual International Conference on New Technologies of DIstributed Systems.Tozeur，Tunisia：IEEE Computer Society，2010：97-104.

[8]MENASC'E D A，CASALICCHIO E，DUBEY V.A Heuristic Approach to Optimal Service Selection in Service Oriented Architectures[C]∥WOSP（ACM）.Princeton，New Jersey，USA：ACM，2008：13-23.

[9]FANJIANG Y-Y，SYU Y，WU C-H，et al.Genetic Algorithm for QoS-Aware Dynamic Web Services Composition[C]∥2010International Conference on Machine Learning and Cybernetics（ICMLC）.[S.l.]：IEEE Computer Society，2010：3246-3251.

[10]BAKHSHI M，MARDUKHI F，NEMATBAKHSH D N.A Fuzzy-Based Approach for Selecting the Optimal Composition of Services According to User Preferences[C]∥2010the 2nd International Conference on Computer and Automation Engineering（ICCAE）.[S.l.]：IEEE Computer Society，2010：129-135.

[11]NEPAL S，SHERCHAN W，HUNKLINGER J，et al.A Fuzzy Trust Management Framework for Service Web[C]∥2010IEEE International Conference on Web Services.[S.l.]：IEEE Computer Society，2010：321-328.

[12]YU Q，BOUGUETTAYA A.Computing Service Skylines over Sets of Services[C]∥2010IEEE International Conference on Web Services.[S.l.]：IEEE Computer Society，2010：481-488.

[13]YU Q，BOUGUETTAYA A.Computing Service Skyline from Uncertain QoS[J].IEEE Transactions on Services Computing，2010，3（1）：16-29.

[14]BALFAGIH Z，HASSAN M F B.Agent Based Monitoring Framework for SOA Applications Quality[C]∥2010International Symposium in Information Technology（ITSim）.[S.l.]：IEEE Computer Society，2010：1124-1129.

[15]MALIK Z，BOUGUETTAYA A.Reputation Bootstrapping for Trust Establishment among Web Services[J].IEEE Internet Computing，2009，13（1）：1-13.

[16]岳昆，王曉玲，周傲英.Web服務核心支撐技術(shù)：研究綜述[J].軟件學報，2004，15（3）：428-442.YUE Kun，WANG Xiao-ling，ZHOU Ao-ying.Underlying Techniques for Web Services：A Survey[J].Journal of Software，2004，15（3）：428-442.

[17]劉華文，申春，楊冬，等.語義 Web服務基礎技術(shù)研究綜述[J].吉林大學學報：信息科學版，2010，28（1）：47-54.

LIU Hua-wen，SHEN Cun，YANG Dong，et al.Survey of Semantic Web Service Techniques[J].Journal of Jilin University：Information Science Edition，2010，28（1）：47-54.

[18]李金忠，夏潔武，唐衛(wèi)東，等.基于 QoS的 Web服務選擇算法綜述[J].計算機應用研究，2010，27（10）：3622-3628.

LI Jin-zhong，XIA Jie-wu，TANG Wei-dong，et al.Survey on Web Services Selection Algorithms Based on QoS[J].Application Research of Computers，2010，27（10）：3622-3628.

[19]ZHANG Pei-yun，SUN Ya-min.Web Services Composition Based on Global Semantics and QoS-Aware Aspect[J].Journal of Southeast University，2008，24（3）：296-299.

[20]LI Z，YANG F，SU S.QoS-Aware Semantic Web Service Composition with Uncertainties[J].Chinese Journal of Electronic（SCI），2008，17（4）：703-709.

[21]ZHENG H，ZHAO W，YANG J，et al.QoS Analysis for Web Service Composition[C]∥2009IEEE International Conference on Services Computing.[S.l.]：IEEE Computer Society，2009：235-242.

[22]CAVALLO B，PENTA M D，CANFORA G.An Empirical Comparison of Methods to Support QoS-Aware Service Selection[C]∥Proceeding of the PESOS.Cape Town，South Africa：[s.n.]，2010：64-70.

[23]李禎，楊放春，蘇森.基于模糊多屬性決策理論的語義 Web服務組合算法[J].軟件學報，2009，20（3）：583-596.

LI Zhen，YANG Fang-chun，SU Shen.Fuzzy Multi-Attribute Decision Making-Based Algorithm for Semantic Web Service Composition[J].Journal of Software，2009，20（3）：583-596.

[24]邵凌霜，周立，趙俊峰，等.一種 Web Service的服務質(zhì)量預測方法[J].軟件學報，2009，20（8）：2062-2073.

SHAO Ling-shuang，ZHOU Li，ZHAO Jun-feng，et al.Web Service QoS Prediction Approach[J].Journal of Software，2009，20（8）：2062-2073.

[25]陳志剛，劉莉平，劉安豐.基于黑白板的信任敏感 Web服務組合策略[J].通信學報，2010，31（6）：25-35.

CHEN Zhig-ang，LIU Li-peng，LIU An-feng.Trust-Sensitive Web Service Composition Strategy Based on Black and White Board[J].Journal on Communications，2010，31（6）：25-35.

[26]NEPAL S，MALIK Z，BOUGUETTAYA A.Reputation Propagation in Composite Services[C]∥2009IEEE International Conference on Web Services.[S.l.]：IEEE Computer Society，2009：295-302.

[27]桂春梅，蹇強，王懷民，等.虛擬計算環(huán)境中基于重復博弈的懲罰激勵機制[J].軟件學報，2010，21（12）：3042-3055.

GUI Chun-mei，JIAN Qiang，WANG Huai-ming，et al.Repeated Game Theory Based Penalty-Incentive Mechanism in Internet-Based Virtual Computing Environment[J].Journal of Software，2010，21（12）：3042-3055.

[28]潘靜，徐鋒，呂建.面向可信服務選取的基于聲譽的推薦者發(fā)現(xiàn)方法[J].軟件學報，2010，21（2）：388-400.

PANG Jing，XU Feng，LüJian.Reputation-Based Recommender Discovery Approach for Service Selection[J].Journal of Software，2010，21（2）：388-400.

[29]ZHANG Y，HUANG H，YANG D，et al.Bring QoS to P2PBased Semantie Service Discovery for the Universal Network[J].Journal Personal and Ubiquitous Computing，2009，13（7）：471-477.

[30]AL-MASRI E，MAHMOUD Q H.Investigating Web Services on the World Wide Web[C]∥Proc of the 17th Int Conf on World Wide Web.New York：ACM，2008：795-803.

[31]李飛，楊放春，蘇森.分布式 Web服務 QoS波冊中的高效負載均衡方法[J].電子與信息學報，2009，31（5）：1022-1025.

LI Fei，YANG Fang-chun，SU Sen.Efficient Load-Balance in Distributed QoS Registry for Web Service[J].Journal of Electronics ＆Information Technology，2009，31（5）：1022-1025.

[32]范小芹，蔣昌俊，王俊麗，等.隨機 QoS感知的可靠 Web服務組合[J].軟件學報，2009，20（3）：546-556.

FAN Xiao-qin，JIANG Chang－jun，WANG Jun-li，et al.Random-QoS-Aware Reliable Web Service Composition[J].Journal of Software，2009，20（3）：546-556.

[33]LAGES A G，PIRMEZ L，PIRES P F，et al.SATYA：A Reputation-Based Approach for Service Discovery and Selection in Service Oriented Architectures[C]∥Proceedings of the Annual ACM International Workshop on Web Information and Data Management.Lisbon，Portugal：ACM，2007：525-528.

[34]胡建強，李涓子，廖桂平.一種基于多維服務質(zhì)量的局部最優(yōu)服務選擇模型[J].計算機學報，2010，33（3）：526-534.

HU Jian-qiang，LI Juan-zi，LIAO Gui-ping.A Multi-QoS Based Local Optimal Model of Service Selection[J].Chinese Journal of Computers，2010，33（3）：526-534.

[35]岳昆，劉惟一，王曉玲，等.一種基于不確定性因素疊加的 Web服務質(zhì)量度量方法[J].計算機研究與發(fā)展，2009，46（5）：841-849.

YUE Kun，LIU Wei-yi，WANG Xiao-ling，et al.An Approach for Measuring Quality of Web Services Based on the Superposition of Uncertain Factors[J].Journal of Computer Research and Development，2009，46（5）：841-849.

[36]劉書雷，劉云翔，張帆，等.一種服務聚合中 QoS全局最優(yōu)服務動態(tài)選擇算法[J].軟件學報，2007，18（3）：646-656.

LIU Shu-lei，LIU Yun-xiang，ZHANG Fan，et al.A Dynamic Web Services Selection Algorithm with QoS Global Optimal in Web Services Composition[J].Journal of Software，2007，18（3）：646-656.

[37]范小芹，蔣昌俊，方賢文，等.基于離散微粒群算法的動態(tài) Web服務選擇[J].計算機研究與發(fā)展，2010，47（1）：147-156.

FAN Xiao-qin，JIANG Chang－jun，F(xiàn)ANG Xian-wen，et al.Dynamic Web Service Selection Based on Discrete Particle Swarm Optimization[J].Journal of Computer Research and Development，2010，47（1）：147-156.

[38]張佩云，黃波，孫亞民.一種基于語義與QoS感知的 Web服務匹配機制[J].計算機研究與發(fā)展，2010，47（5）：780-787.

ZHANG Pei-yun，HUANG Bo，SUN Ya-min.A Web Services Matching Mechanism Based on Semantics and QoS-A-ware Aspect[J].Journal of Computer Research and Development，2010，47（5）：780-787.

[39]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.Madrid，Spain：ACM，2009：881-890.

[40]PAPAZOGLOU P M，TRAVERSO P，DUSTDAR S S，et al.Service-Oriented Computing：State of the Art and Research Challenges[J].Computer，2007，40（11）：38-45.

[41]白同強，劉磊.語義 Web的研究與展望[J].吉林大學學報：信息科學版，2004，22（2）：154-159.

BAI Tong－qiang，LIU Lei.Research and Prospect in Semantic Web[J].Journal of Jilin University：Information Science Edition，2004，22（2）：154-159.

[42]FORD M，LJUNGBERG M，HOOK D J V，et al.Resource Brokering Service：Automatic Plan Composition and Execution[C]∥the 2010Military Communications Conference.[S.l.]：IEEE Computer Society，2010：2040-2045.

[43]VIGGH D H E M，WEED C，CHAN D M T，et al.Composable Applications Using Service Encapsulation[C]∥The 2010Military Communications Conference.[S.l.]：IEEE Computer Society，2010：2046-2051.