基于QoS的Web服務調用最短路徑確定方法

馬 亮，錢雪忠

（江南大學物聯網工程學院，江蘇無錫214122）

基于QoS的Web服務調用最短路徑確定方法

馬 亮，錢雪忠

（江南大學物聯網工程學院，江蘇無錫214122）

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

服務質量；Web服務選擇；Web服務調用；最短路徑；活動邊網；SAP平臺

1 概述

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

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

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

2 基于QoS的Web服務選擇

2.1 服務質量度量屬性

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

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

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

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

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

2.2 QoS數據形式化表示

QoS數據形式化表示具體如下：

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

（2）QoS需求數組對應的權重表示為w=｛w1，w2，w3｝；

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

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

2.3 基于QoS的Web服務選擇算法描述

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

輸出 符合用戶QoS滿意度的服務序列

3 最短路徑確定

3.1 最短路徑分類

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

3.2 最短路徑求解

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

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

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

在通常情況下，假設S為已求得最短路徑的終點集合，那么下一條最短路徑可能是?。é?，χ）（設其終點為χ），也可能是中途經過S中的頂點而最后到達頂點χ的路徑。

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

3.3 最短路徑算法

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

（1）用帶權的鄰接矩陣arcs表示帶權有向圖，arcs［i］［j］表示?。糣i，Vj＞上的權值。若＜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 測試結果分析

4.1 測試環(huán)境

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

4.2 測試步驟與測試方法

測試步驟具體如下：

（1）計算各Web服務的QoS值

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

表1 Web服務的QoS值

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

表2 取不同權值時的Web服務QoS值

（2）確定服務調用的最短路徑

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

圖1 服務調用的AOE網

圖2 AOE網的帶權鄰接矩陣

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

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

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

表3 AOE網中從ν0到其余各終點的最短路徑

圖4 AOE網的最短路徑調用

（3）縮短最短路徑上的服務調用時間

在步驟（2）的基礎上，SAP（System s，Applications and Products in Data Processing）系統客戶端使用緩沖管理、業(yè)務代理等技術減少Web服務調用次數，加速Web服務調用效率。SAP系統Web服務調用的層次結構如圖5所示。

圖5 SAP系統的Web服務調用層次結構

緩沖管理模式的具體實現方法：調用業(yè)務代理層的類方法，先從緩沖區(qū)中讀取數據，若找不到，則再向服務器端發(fā)送請求。客戶端更新信息時，先更新服務器上的信息，使所有客戶端更新本地緩沖區(qū)。然后在本地緩沖區(qū)更新該記錄，將請求次數減到最少。

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

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

由SAP系統向中國出口信用保險公司（中信保）信保通系統調用100次服務請求［14-15］，系統架構如圖6所示。

圖6 SAP系統與信保通系統的Web服務調用架構

4.3 結果分析

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

圖7 系統響應時間與Web服務調用數量的關系

5 結束語

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

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

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

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

［4］ 王永明，張英俊，謝斌紅，等.基于模糊聚類優(yōu)化的語義Web服務發(fā)現［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服務信任評估模型［J］.計算機學報，2008，31（8）：1471-1477.

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

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

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

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

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

［15］ 元祥波，南 琳，張福順.基于元數據和XML的信息抽取與集成技術研究［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服務調用最短路徑確定方法［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服務技術，企業(yè)SAP系統；錢雪忠，副教授。

2014-08-18

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