馬 亮，錢雪忠

（江南大學物聯(lián)網(wǎng)工程學院，江蘇無錫214122）

基于QoS的Web服務(wù)調(diào)用最短路徑確定方法

馬 亮，錢雪忠

（江南大學物聯(lián)網(wǎng)工程學院，江蘇無錫214122）

針對目前企業(yè)選擇的Web服務(wù)無針對性且調(diào)用效率低下的問題，提出一種確定Web服務(wù)調(diào)用最短路徑的方法。將Web服務(wù)的響應時間、安全性和價格這3個服務(wù)質(zhì)量度量屬性引入到Web服務(wù)選擇算法中，獲取滿足用戶需求的待選服務(wù)，使Web服務(wù)調(diào)用過程抽象為帶權(quán)有向無環(huán)活動邊（AOE）網(wǎng)圖，結(jié)合最短路徑算法，計算出從源點到其余頂點的最短路徑，得到Web服務(wù)調(diào)用最短路徑的AOE網(wǎng)圖。SAP平臺下的應用結(jié)果表明，該方法能有效縮短Web服務(wù)調(diào)用的響應時間，提高整體執(zhí)行效率。

服務(wù)質(zhì)量；Web服務(wù)選擇；Web服務(wù)調(diào)用；最短路徑；活動邊網(wǎng)；SAP平臺

1 概述

面向服務(wù)架構(gòu)（Service Oriented Architecture，SOA）在現(xiàn)代軟件開發(fā)技術(shù)中得到廣泛應用，為企業(yè)信息集成提供了保證［1］。而Web服務(wù)技術(shù)是SOA技術(shù)的實現(xiàn)，它采用標準的接口描述、統(tǒng)一的通信協(xié)議、開發(fā)平臺及語言的無關(guān)性為異構(gòu)系統(tǒng)間資源靈活共享提供了技術(shù)支持［2-3］。如何從眾多服務(wù)中選擇質(zhì)量保證的服務(wù)是目前學術(shù)界和工業(yè)界研究的重點［4］。

文獻［5］概括了性能、可用性、可訪問性、完整性、可靠性、規(guī)范性和安全性7個與用戶緊密相關(guān)的Web服務(wù)的非功能屬性需求，但是對服務(wù)性能的波動性考慮欠佳，從而引入人際交往網(wǎng)絡(luò)中信任這一概念［6］。文獻［7-8］研究了Web服務(wù)的信譽模型，但忽略了用戶的主觀惡意評價這個核心問題。文獻［9］針對性地選取服務(wù)能力、安全性能和聲譽構(gòu)建服務(wù)信任模型，但所提方法可行性較差［10］。文獻［11］建立服務(wù)質(zhì)量（Quality of Service，QoS）的發(fā)布、監(jiān)控和反饋機制來獲得QoS相關(guān)數(shù)據(jù)，并將其暫存至QoS數(shù)據(jù)庫中，通過功能匹配、服務(wù)質(zhì)量約束篩選和評價排序，完成最優(yōu)Web服務(wù)發(fā)現(xiàn)。文獻［12］動態(tài)評估了服務(wù)的QoS屬性值，較真實地反映了Web服務(wù)質(zhì)量，同時將權(quán)重和匹配度引入到服務(wù)查找過程中，以選擇符合用戶實際需求的服務(wù)。

本文結(jié)合企業(yè)自身的領(lǐng)域應用情況，將服務(wù)響應時間、安全性、價格這3個企業(yè)較關(guān)心的QoS屬性融入到服務(wù)選擇算法中，篩選出若干符合調(diào)用條件的待選Web服務(wù)。結(jié)合工程學中最短路徑的相關(guān)概念，提出一種基于QoS選擇算法的Web服務(wù)調(diào)用最短路徑確定方法。

2 基于QoS的Web服務(wù)選擇

2.1 服務(wù)質(zhì)量度量屬性

在服務(wù)調(diào)用過程中，除了準確地發(fā)現(xiàn)服務(wù)、匹配服務(wù)、完成調(diào)用以外，越來越多的專家學者將研究重點轉(zhuǎn)移到Web服務(wù)質(zhì)量上，Web服務(wù)質(zhì)量用于判定Web服務(wù)質(zhì)量的好壞。

目前，學術(shù)界從從宿主結(jié)點、服務(wù)和方法這3個層面對Web服務(wù)進行QoS度量。其中，宿主結(jié)點層面，包括網(wǎng)絡(luò)正?？蛇_概率、最近時間段內(nèi)網(wǎng)絡(luò)是否正?？蛇_、Web服務(wù)容器可使用的主存上限、最近時間段內(nèi)Web服務(wù)容器可用主存與最大可用主存的比值、處理器的時鐘頻率、最近時間段內(nèi)處理器的占有率、最大帶寬以及最近時間段內(nèi)帶寬占用率等屬性；服務(wù)層面，包括可訪問性、可靠性、性能、容量、魯棒性、互操作性、可移植性等屬性；方法層面，包括響應時間、安全性等屬性，這3個層面之間彼此正交且存在層次關(guān)系：宿主結(jié)點層面是基礎(chǔ)維度，服務(wù)層面是標準維度，而方法層面是高層維度［13］。

（1）響應時間：是衡量Web服務(wù)性能的重要參數(shù)，系統(tǒng)響應時間指從客戶端提交服務(wù)請求到獲得服務(wù)端響應的時間間隔，其計算公式為：響應時間=執(zhí)行時間+等待時間。執(zhí)行時間是從服務(wù)開始到結(jié)束的處理時間，等待時間是各種系統(tǒng)延遲時間的總和。

（2）安全性：保證了Web服務(wù)能夠被正常調(diào)用，表示服務(wù)在調(diào)用過程中，可以通過身份驗證、消息加密、訪問控制等保障機制來有效提高系統(tǒng)交互通信的性能。

（3）價格：指服務(wù)提供者給出的服務(wù)請求者使用此服務(wù)的花費，它與該服務(wù)功能的價值有關(guān)，功能相對越完善，價格花費就越高。

2.2 QoS數(shù)據(jù)形式化表示

QoS數(shù)據(jù)形式化表示具體如下：

（1）K個服務(wù)的3個QoS屬性的矩陣表示如下：

（2）QoS需求數(shù)組對應的權(quán)重表示為w=｛w1，w2，w3｝；

（3）將備選服務(wù)矩陣S和數(shù)組w中的元素相乘，得到權(quán)值矩陣Q中的元素：hij=qi，j×wj；

（4）計算服務(wù)的QoS值：QoS（Si）=∑Kj=1hi，j。

2.3 基于QoS的Web服務(wù)選擇算法描述

基于QoS的服務(wù)選擇算法偽代碼具體如下：輸入 用戶QoS需求向量aq和權(quán)值w，服務(wù)列表R

輸出 符合用戶QoS滿意度的服務(wù)序列

3 最短路徑確定

3.1 最短路徑分類

最短路徑可以分為2類：（1）從某個源點到其余各頂點的最短路徑；（2）每一對頂點之間的最短路徑。本文著重討論第（1）類情況，提出一個按照路徑長度遞增次序產(chǎn)生最短路徑的算法，前提條件是已知整個拓撲結(jié)構(gòu)圖和各分支路徑長度。本文創(chuàng)新性地將已知的各分支路徑的長度改為服務(wù)調(diào)用的時延或費用，這就相當于求任意兩結(jié)點之間具有最小時延或最小費用的路徑，本文的最短路徑算法在工程實踐中具有普遍的應用推廣價值。

3.2 最短路徑求解

活動邊（Activity on Edge，AOE）網(wǎng)是一個用邊來表示活動的網(wǎng)，它是一個帶權(quán)的有向無環(huán)圖，本文AOE網(wǎng)的頂點代表Web服務(wù)實例，弧代表一次服務(wù)調(diào)用，弧上對應的權(quán)值代表一個服務(wù)調(diào)用持續(xù)的時間。假設(shè)AOE網(wǎng)源點為，從到AOE網(wǎng)中其余各頂點的最短路徑求解過程如下：

（1）標記輔助向量D，其中每個分量D［i］表示從起始點到其他各終點的最短路徑長度，如果到有弧存在，則D［i］長度值為對應弧上的權(quán)值；否則D［i］為。由此可見，D［j］=m in｛D［i］|V｝的路徑就是從出發(fā)的一條最短路徑（ν0，νj）。

（2）確定長度次短的最短路徑。假設(shè)該次短路徑的終點是，那么這條路徑可能是（ν0，νK），也可能是（ν0，νj，νK），它的長度是從到對應弧上的權(quán)值，也可能是D［j］與從到對應弧上的權(quán)值之和。

在通常情況下，假設(shè)S為已求得最短路徑的終點集合，那么下一條最短路徑可能是弧（ν0，χ）（設(shè)其終點為χ），也可能是中途經(jīng)過S中的頂點而最后到達頂點χ的路徑。

由上述內(nèi)容可知，下一條長度次短的最短路徑的長度必然是D［j］=m in｛D［i］|V-S｝，其中，D［i］可能是?。é?，νi）上對應的權(quán)值，也可能是D［K］（S）與弧（νK，νi）上對應的權(quán)值之和。

3.3 最短路徑算法

最短路徑算法具體步驟如下：

（1）用帶權(quán)的鄰接矩陣arcs表示帶權(quán)有向圖，arcs［i］［j］表示?。糣i，Vj＞上的權(quán)值。若＜Vi，Vj＞不存在，則arcs［i］［j］為。S為從出發(fā)的最短路徑的終點集合，它的初始狀態(tài)為空集。那么從出發(fā)到圖上其余各頂點（終點）可能達到的最短路徑長度的初值為：D［i］=arcs［Locate Veχ（G，ν）［i］］，νi∈V。

（2）選擇νj，使得D［j］=m in｛D［i］|V-S｝，是當前求得的一條從ν0出發(fā)的最短路徑的終點，令S=S∪｛j｝。

（3）修改從出發(fā)到集合V-S上任一頂點可達的最短路徑長度。如果D［j］+arcs［j］［K］＜D［K］，則修改D［K］為D［K］=D［j］+arcs［j］［K］。

（4）重復操作步驟（2）、步驟（3）共n-1次，由此求得從ν0到圖上其余各頂點的最短路徑是依路徑長度遞增的序列。

4 測試結(jié)果分析

4.1 測試環(huán)境

測試環(huán)境為一臺戴爾品牌個人PC，CPU為Pentium（R）Dual-Core E5400、主頻為2.70 GHz、內(nèi)存為2 GB、操作系統(tǒng)為W indow s XP。

4.2 測試步驟與測試方法

測試步驟具體如下：

（1）計算各Web服務(wù)的QoS值

表1列出了中國出口信用保險公司對外提供的10個可供外部企業(yè)訪問的以Web服務(wù)為實驗對象的QoS信息，4個QoS屬性的權(quán)重值w都取0.25。其中，Qc（Si）表示使用服務(wù)所支付的費用；Qt（Si）表示服務(wù)的響應時間，該值在第三方QoS認證中心內(nèi)嵌計時器代碼中獲??；Qa（Si）表示服務(wù)的安全性，即服務(wù)的安全系數(shù)；Qr（Si）表示服務(wù)的誠信度，其值越大，表示執(zhí)行結(jié)果越接近用戶期望值，該值由歷史統(tǒng)計數(shù)據(jù)獲得。

表1 Web服務(wù)的QoS值

表2是對上述10個服務(wù)按照本文服務(wù)選擇方法計算得到的QoS值，R表示服務(wù)的相關(guān)度排名，方法1基于平均權(quán)值，如果請求者沒有提供對應的具體參數(shù)和權(quán)值，就使用平均權(quán)值方法計算。方法2側(cè)重價格因素，相對應的權(quán)重值w分別取1，0，0，0，可得QoS值最大的是S8，根據(jù)表1可以清楚地看到價格最低的服務(wù)也是S8，實際結(jié)果與預期值一致。方法3兼顧價格和響應時間因素，w分別取值0.6，0.4，0，0。在方法2中只考慮了價格，QoS值相同的是S3，S7，S9，此時加上響應時間因子，QoS值：S9＞S3＞S7，同樣對照表1，響應時間為S9＜S3＜S7，所得結(jié)果的準確度很高。方法4綜合考慮服務(wù)價格、響應時間、安全性因素。w分別取值0.4，0.3，0.3，0，可以看出請求用戶質(zhì)量需求越精細，計算結(jié)果也會越準確，提高了服務(wù)選擇效率。

表2 取不同權(quán)值時的Web服務(wù)QoS值

（2）確定服務(wù)調(diào)用的最短路徑

在步驟（1）的基礎(chǔ)上，將QoS值符合用戶要求的服務(wù)抽象成AOE網(wǎng)表示，如圖1所示，圖中權(quán)值表示完成一個服務(wù)調(diào)用所需的單位時間，圖1所示AOE網(wǎng)的帶權(quán)鄰接矩陣、從到其余各終點的最短路徑如圖2、圖3所示。

圖1 服務(wù)調(diào)用的AOE網(wǎng)

圖2 AOE網(wǎng)的帶權(quán)鄰接矩陣

圖3 AOE網(wǎng)中從ν0到各終點的D值和最短路徑的求解過程

在圖3中，i=1，2，…，5表示到達每個終點的最大頂點數(shù)；“∞”表示任意2個頂點沒有直接相連的弧；“無”表示任意2個頂點沒有相通路徑；“10（0，2）”中“10”表示完成一個服務(wù)調(diào)用所需的單位時間，“（0，2）”表示一條調(diào)用路徑，起點為0，終點為2；“j”表示終點序號；“S”表示符合調(diào)用條件的服務(wù)集合。

通過計算確定圖1中從到其余各終點的最短路徑如表3、圖4所示。

表3 AOE網(wǎng)中從ν0到其余各終點的最短路徑

圖4 AOE網(wǎng)的最短路徑調(diào)用

（3）縮短最短路徑上的服務(wù)調(diào)用時間

在步驟（2）的基礎(chǔ)上，SAP（System s，Applications and Products in Data Processing）系統(tǒng)客戶端使用緩沖管理、業(yè)務(wù)代理等技術(shù)減少Web服務(wù)調(diào)用次數(shù)，加速Web服務(wù)調(diào)用效率。SAP系統(tǒng)Web服務(wù)調(diào)用的層次結(jié)構(gòu)如圖5所示。

圖5 SAP系統(tǒng)的Web服務(wù)調(diào)用層次結(jié)構(gòu)

緩沖管理模式的具體實現(xiàn)方法：調(diào)用業(yè)務(wù)代理層的類方法，先從緩沖區(qū)中讀取數(shù)據(jù)，若找不到，則再向服務(wù)器端發(fā)送請求?？蛻舳烁滦畔r，先更新服務(wù)器上的信息，使所有客戶端更新本地緩沖區(qū)。然后在本地緩沖區(qū)更新該記錄，將請求次數(shù)減到最少。

業(yè)務(wù)代理模式的具體實現(xiàn)方法：分離GUI層和業(yè)務(wù)層邏輯?？蛻舳诉\行時，線程阻塞機制在服務(wù)端設(shè)置數(shù)據(jù)變更監(jiān)聽器，監(jiān)聽數(shù)據(jù)更新事件。如果客戶端更新了數(shù)據(jù)，則會觸發(fā)服務(wù)器端的數(shù)據(jù)改變事件，激活所有被阻塞的監(jiān)視線程，同時觸發(fā)緩沖區(qū)數(shù)據(jù)更新的SOAP調(diào)用，每個客戶端又會在服務(wù)器端注冊新的監(jiān)視線程，循環(huán)反復，當且僅當更新數(shù)據(jù)時，才發(fā)送調(diào)用請求，其他調(diào)用實際上是讀取緩沖區(qū)內(nèi)的數(shù)據(jù)，實現(xiàn)數(shù)據(jù)自動同步功能。

在圖4所示的用AOE網(wǎng)表示的最短路徑中，完成服務(wù)0→2調(diào)用需要2個單位時間，完成服務(wù)0→4調(diào)用需要4個單位時間，完成服務(wù)4→3調(diào)用需要2個單位時間，完成服務(wù)3→5調(diào)用需要3個單位時間，完成整體服務(wù)調(diào)用需要11個單位時間。使用緩沖管理、業(yè)務(wù)代理技術(shù)后，分別減少0.25個、0.8個、0.4個、0.55個單位時間，只需要9個單位時間，節(jié)省了2個單位時間，系統(tǒng)整體執(zhí)行效率提高18.18%，驗證了本文所提方法的正確性和有效性。

由SAP系統(tǒng)向中國出口信用保險公司（中信保）信保通系統(tǒng)調(diào)用100次服務(wù)請求［14-15］，系統(tǒng)架構(gòu)如圖6所示。

圖6 SAP系統(tǒng)與信保通系統(tǒng)的Web服務(wù)調(diào)用架構(gòu)

4.3 結(jié)果分析

系統(tǒng)響應時間與Web服務(wù)調(diào)用數(shù)量的關(guān)系如圖7所示。當Web服務(wù)數(shù)量小于200時，本文方法比未考慮用戶質(zhì)量需求的服務(wù)調(diào)用方法的系統(tǒng)響應時間有所降低；當Web服務(wù)數(shù)量大于200時，這種降低趨勢越發(fā)明顯，所以僅從系統(tǒng)響應時間這一性能參數(shù)驗證了本文方法的正確性。

圖7 系統(tǒng)響應時間與Web服務(wù)調(diào)用數(shù)量的關(guān)系

5 結(jié)束語

本文通過計算QoS值，獲取滿足用戶實際應用需求的Web服務(wù)，將Web服務(wù)調(diào)用抽象成一個帶權(quán)有向無環(huán)AOE網(wǎng)圖，利用最短路徑的相關(guān)概念和算法，提出一種基于QoS的企業(yè)SAP平臺Web服務(wù)調(diào)用最短路徑確定方法，使用緩沖管理、業(yè)務(wù)代理技術(shù)，縮短最短路徑上各服務(wù)調(diào)用的響應時間周期。測試結(jié)果驗證了本文方法的正確性，并表明其能提高能企業(yè)工作效率，降低運營成本。

［1］ 陳海燕，劉建勛，胡 蓉.可信Web服務(wù)合成研究綜述［J］.吉首大學學報：自然科學版，2011，32（1）：30-36.

［2］ 狄小峰，郭劍鋒，范玉順.基于分布式本體的服務(wù)選擇方法［J］.信息與控制，2013，42（1）：89-94.

［3］ 李小林，張力娜，張順利.基于服務(wù)質(zhì)量反饋的語義Web服務(wù)匹配算法［J］.計算機工程，2012，38（7）：60-62.

［4］ 王永明，張英俊，謝斌紅，等.基于模糊聚類優(yōu)化的語義Web服務(wù)發(fā)現(xiàn)［J］.計算機工程，2013，39（7）：219-223.

［5］ Liu Yutu，Ngu A H H，Zeng Liangzhao.QoS Computation and Policing in dynamic Web Service Selection［C］//Proceedings of the 13th International World Wide Web Conference on Alternate Track Papers&Posters.New York，USA：ACM Press，2004：66-73.

［6］ Beth T，Borcherding M，Klein B.Valuation of Trust in Open Network［C］//Proceedings of the 3rd European Symposium on Research in Computer Security.London，UK：Springer-Verlag，1994：3-8.

［7］ Maximilien E M，Munindar P S.Reputation and Endorsement for Web Service［J］.ACM SIGECOM Exchanges，2001，3（1）：5-16.

［8］ Maximilien E M，Munindar P S.Conceptual Model of Web Service Reputation［J］.ACM SIGMOD Record，2002，31（4）：78-89.

［9］ 李海華，杜小勇，田 萱.一種能力屬性增強的Web服務(wù)信任評估模型［J］.計算機學報，2008，31（8）：1471-1477.

［10］ 袁東維，李蜀瑜.一種基于信任的Web服務(wù)發(fā)現(xiàn)方法［J］.計算機工程與科學，2011，33（3）：194-198.

［11］ 王安華，胡國林，班曉娟，等.基于服務(wù)質(zhì)量的Web服務(wù)發(fā)現(xiàn)研究與實現(xiàn)［J］.計算機工程與設(shè)計，2007，28（21）：5112-5114.

［12］ 蔣哲遠，韓江洪，王 釗.動態(tài)的QoS感知Web服務(wù)發(fā)現(xiàn)機制［J］.計算機學報，2009，32（5）：1015-1025.

［13］ 郭得科，任 彥，陳洪輝，等.一種QoS有保障的Web服務(wù)分布式發(fā)現(xiàn)模型［J］.軟件學報，2006，17（11）：2324-2334.

［14］ 王芳芳，廉東本，高 天，等.企業(yè)服務(wù)總線的協(xié)議轉(zhuǎn)換器的研究與設(shè)計［J］.計算機系統(tǒng)應用，2013，22（3）：132-135.

［15］ 元祥波，南 琳，張福順.基于元數(shù)據(jù)和XML的信息抽取與集成技術(shù)研究［J］.信息與控制，2008，37（1）：52-57.

編輯 陸燕菲

QoS-based Shortest Path Determination Method of Web Service Call

MA Liang，QIAN Xuezhong
（College of Internet of Things Engineering，Jiangnan University，Wuxi 214122，China）

Aim ing at the problems that Web service selection is non-targeted and Web service call is low-efficiency，this paper proposes a shortest path determination method of Web service call.It puts the system response time，safety and price attributes into service call algorithm to make the Web services which meet user needs most.It abstracts the process of Web service call into Activity on Edge（AOE）network diagram representation by weighted directed acyclic graph.The method combines shortest path selection algorithm to calculate the shortest path which a source point to the rest of the graph vertices and get the AOE network diagram of shortest path of Web service call.Application result on Systems，Applications and Products in Data Processing（SAP）platform show s that the method reduce the response time cycle of service call，and im prove the overall efficiency.

Quality of Service（QoS）；Web service selection；Web service call；shortest path；Activity on Edge（AOE）network；Systems，Applications and Products in Data Processing（SAP）platform

馬 亮，錢雪忠.基于QoS的Web服務(wù)調(diào)用最短路徑確定方法［J］.計算機工程，2015，41（9）：103-107.

英文引用格式：M a Liang，Qian Xuezhong.QoS-based Shortest Path Determination Method of Web Service Call［J］. Computer Engineering，2015，41（9）：103-107.

1000-3428（2015）09-0103-05

A

TP311

10.3969/j.issn.1000-3428.2015.09.018

國家自然科學基金資助項目（61103129，61202312）；江蘇省科技支撐計劃基金資助項目（BE2009009）。

馬 亮（1984-），男，碩士研究生、CCF會員，主研方向：Web服務(wù)技術(shù)，企業(yè)SAP系統(tǒng)；錢雪忠，副教授。

2014-08-18

2014-10-16 E-m ail：molloveby141012@126.com