基于QoS的Web服务调用最短路径确定方法

马 亮，钱雪忠

（江南大学物联网工程学院，江苏无锡214122）

基于QoS的Web服务调用最短路径确定方法

马 亮，钱雪忠

（江南大学物联网工程学院，江苏无锡214122）

针对目前企业选择的Web服务无针对性且调用效率低下的问题，提出一种确定Web服务调用最短路径的方法。将Web服务的响应时间、安全性和价格这3个服务质量度量属性引入到Web服务选择算法中，获取满足用户需求的待选服务，使Web服务调用过程抽象为带权有向无环活动边（AOE）网图，结合最短路径算法，计算出从源点到其余顶点的最短路径，得到Web服务调用最短路径的AOE网图。SAP平台下的应用结果表明，该方法能有效缩短Web服务调用的响应时间，提高整体执行效率。

服务质量；Web服务选择；Web服务调用；最短路径；活动边网；SAP平台

1 概述

面向服务架构（Service Oriented Architecture，SOA）在现代软件开发技术中得到广泛应用，为企业信息集成提供了保证［1］。而Web服务技术是SOA技术的实现，它采用标准的接口描述、统一的通信协议、开发平台及语言的无关性为异构系统间资源灵活共享提供了技术支持［2-3］。如何从众多服务中选择质量保证的服务是目前学术界和工业界研究的重点［4］。

文献［5］概括了性能、可用性、可访问性、完整性、可靠性、规范性和安全性7个与用户紧密相关的Web服务的非功能属性需求，但是对服务性能的波动性考虑欠佳，从而引入人际交往网络中信任这一概念［6］。文献［7-8］研究了Web服务的信誉模型，但忽略了用户的主观恶意评价这个核心问题。文献［9］针对性地选取服务能力、安全性能和声誉构建服务信任模型，但所提方法可行性较差［10］。文献［11］建立服务质量（Quality of Service，QoS）的发布、监控和反馈机制来获得QoS相关数据，并将其暂存至QoS数据库中，通过功能匹配、服务质量约束筛选和评价排序，完成最优Web服务发现。文献［12］动态评估了服务的QoS属性值，较真实地反映了Web服务质量，同时将权重和匹配度引入到服务查找过程中，以选择符合用户实际需求的服务。

本文结合企业自身的领域应用情况，将服务响应时间、安全性、价格这3个企业较关心的QoS属性融入到服务选择算法中，筛选出若干符合调用条件的待选Web服务。结合工程学中最短路径的相关概念，提出一种基于QoS选择算法的Web服务调用最短路径确定方法。

2 基于QoS的Web服务选择

2.1 服务质量度量属性

在服务调用过程中，除了准确地发现服务、匹配服务、完成调用以外，越来越多的专家学者将研究重点转移到Web服务质量上，Web服务质量用于判定Web服务质量的好坏。

目前，学术界从从宿主结点、服务和方法这3个层面对Web服务进行QoS度量。其中，宿主结点层面，包括网络正常可达概率、最近时间段内网络是否正常可达、Web服务容器可使用的主存上限、最近时间段内Web服务容器可用主存与最大可用主存的比值、处理器的时钟频率、最近时间段内处理器的占有率、最大带宽以及最近时间段内带宽占用率等属性；服务层面，包括可访问性、可靠性、性能、容量、鲁棒性、互操作性、可移植性等属性；方法层面，包括响应时间、安全性等属性，这3个层面之间彼此正交且存在层次关系：宿主结点层面是基础维度，服务层面是标准维度，而方法层面是高层维度［13］。

（1）响应时间：是衡量Web服务性能的重要参数，系统响应时间指从客户端提交服务请求到获得服务端响应的时间间隔，其计算公式为：响应时间=执行时间+等待时间。执行时间是从服务开始到结束的处理时间，等待时间是各种系统延迟时间的总和。

（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）类情况，提出一个按照路径长度递增次序产生最短路径的算法，前提条件是已知整个拓扑结构图和各分支路径长度。本文创新性地将已知的各分支路径的长度改为服务调用的时延或费用，这就相当于求任意两结点之间具有最小时延或最小费用的路径，本文的最短路径算法在工程实践中具有普遍的应用推广价值。

3.2 最短路径求解

活动边（Activity on Edge，AOE）网是一个用边来表示活动的网，它是一个带权的有向无环图，本文AOE网的顶点代表Web服务实例，弧代表一次服务调用，弧上对应的权值代表一个服务调用持续的时间。假设AOE网源点为，从到AOE网中其余各顶点的最短路径求解过程如下：

（1）标记辅助向量D，其中每个分量D［i］表示从起始点到其他各终点的最短路径长度，如果到有弧存在，则D［i］长度值为对应弧上的权值；否则D［i］为。由此可见，D［j］=m in｛D［i］|V｝的路径就是从出发的一条最短路径（ν0，νj）。

（2）确定长度次短的最短路径。假设该次短路径的终点是，那么这条路径可能是（ν0，νK），也可能是（ν0，νj，νK），它的长度是从到对应弧上的权值，也可能是D［j］与从到对应弧上的权值之和。

在通常情况下，假设S为已求得最短路径的终点集合，那么下一条最短路径可能是弧（ν0，χ）（设其终点为χ），也可能是中途经过S中的顶点而最后到达顶点χ的路径。

由上述内容可知，下一条长度次短的最短路径的长度必然是D［j］=m in｛D［i］|V-S｝，其中，D［i］可能是弧（ν0，νi）上对应的权值，也可能是D［K］（S）与弧（νK，νi）上对应的权值之和。

3.3 最短路径算法

最短路径算法具体步骤如下：

（1）用带权的邻接矩阵arcs表示带权有向图，arcs［i］［j］表示弧＜Vi，Vj＞上的权值。若＜Vi，Vj＞不存在，则arcs［i］［j］为。S为从出发的最短路径的终点集合，它的初始状态为空集。那么从出发到图上其余各顶点（终点）可能达到的最短路径长度的初值为：D［i］=arcs［Locate Veχ（G，ν）［i］］，νi∈V。

（2）选择νj，使得D［j］=m in｛D［i］|V-S｝，是当前求得的一条从ν0出发的最短路径的终点，令S=S∪｛j｝。

（3）修改从出发到集合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 测试环境

测试环境为一台戴尔品牌个人PC，CPU为Pentium（R）Dual-Core E5400、主频为2.70 GHz、内存为2 GB、操作系统为W indow s XP。

4.2 测试步骤与测试方法

测试步骤具体如下：

（1）计算各Web服务的QoS值

表1列出了中国出口信用保险公司对外提供的10个可供外部企业访问的以Web服务为实验对象的QoS信息，4个QoS属性的权重值w都取0.25。其中，Qc（Si）表示使用服务所支付的费用；Qt（Si）表示服务的响应时间，该值在第三方QoS认证中心内嵌计时器代码中获取；Qa（Si）表示服务的安全性，即服务的安全系数；Qr（Si）表示服务的诚信度，其值越大，表示执行结果越接近用户期望值，该值由历史统计数据获得。

表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）系统客户端使用缓冲管理、业务代理等技术减少Web服务调用次数，加速Web服务调用效率。SAP系统Web服务调用的层次结构如图5所示。

图5 SAP系统的Web服务调用层次结构

缓冲管理模式的具体实现方法：调用业务代理层的类方法，先从缓冲区中读取数据，若找不到，则再向服务器端发送请求。客户端更新信息时，先更新服务器上的信息，使所有客户端更新本地缓冲区。然后在本地缓冲区更新该记录，将请求次数减到最少。

业务代理模式的具体实现方法：分离GUI层和业务层逻辑。客户端运行时，线程阻塞机制在服务端设置数据变更监听器，监听数据更新事件。如果客户端更新了数据，则会触发服务器端的数据改变事件，激活所有被阻塞的监视线程，同时触发缓冲区数据更新的SOAP调用，每个客户端又会在服务器端注册新的监视线程，循环反复，当且仅当更新数据时，才发送调用请求，其他调用实际上是读取缓冲区内的数据，实现数据自动同步功能。

在图4所示的用AOE网表示的最短路径中，完成服务0→2调用需要2个单位时间，完成服务0→4调用需要4个单位时间，完成服务4→3调用需要2个单位时间，完成服务3→5调用需要3个单位时间，完成整体服务调用需要11个单位时间。使用缓冲管理、业务代理技术后，分别减少0.25个、0.8个、0.4个、0.55个单位时间，只需要9个单位时间，节省了2个单位时间，系统整体执行效率提高18.18%，验证了本文所提方法的正确性和有效性。

由SAP系统向中国出口信用保险公司（中信保）信保通系统调用100次服务请求［14-15］，系统架构如图6所示。

图6 SAP系统与信保通系统的Web服务调用架构

4.3 结果分析

系统响应时间与Web服务调用数量的关系如图7所示。当Web服务数量小于200时，本文方法比未考虑用户质量需求的服务调用方法的系统响应时间有所降低；当Web服务数量大于200时，这种降低趋势越发明显，所以仅从系统响应时间这一性能参数验证了本文方法的正确性。

图7 系统响应时间与Web服务调用数量的关系

5 结束语

本文通过计算QoS值，获取满足用户实际应用需求的Web服务，将Web服务调用抽象成一个带权有向无环AOE网图，利用最短路径的相关概念和算法，提出一种基于QoS的企业SAP平台Web服务调用最短路径确定方法，使用缓冲管理、业务代理技术，缩短最短路径上各服务调用的响应时间周期。测试结果验证了本文方法的正确性，并表明其能提高能企业工作效率，降低运营成本。

［1］ 陈海燕，刘建勋，胡 蓉.可信Web服务合成研究综述［J］.吉首大学学报：自然科学版，2011，32（1）：30-36.

［2］ 狄小峰，郭剑锋，范玉顺.基于分布式本体的服务选择方法［J］.信息与控制，2013，42（1）：89-94.

［3］ 李小林，张力娜，张顺利.基于服务质量反馈的语义Web服务匹配算法［J］.计算机工程，2012，38（7）：60-62.

［4］ 王永明，张英俊，谢斌红，等.基于模糊聚类优化的语义Web服务发现［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服务发现方法［J］.计算机工程与科学，2011，33（3）：194-198.

［11］ 王安华，胡国林，班晓娟，等.基于服务质量的Web服务发现研究与实现［J］.计算机工程与设计，2007，28（21）：5112-5114.

［12］ 蒋哲远，韩江洪，王 钊.动态的QoS感知Web服务发现机制［J］.计算机学报，2009，32（5）：1015-1025.

［13］ 郭得科，任 彦，陈洪辉，等.一种QoS有保障的Web服务分布式发现模型［J］.软件学报，2006，17（11）：2324-2334.

［14］ 王芳芳，廉东本，高 天，等.企业服务总线的协议转换器的研究与设计［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服务技术，企业SAP系统；钱雪忠，副教授。

2014-08-18

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