一种基于云模型的组合服务选择方法

谢晓燕, 钱 宇, 王 丽

(西安邮电大学 计算机学院，陕西 西安 710121)



一种基于云模型的组合服务选择方法

谢晓燕, 钱 宇, 王 丽

(西安邮电大学 计算机学院，陕西 西安 710121)

针对Web服务选择问题，提出一种以云模型为基础的代表性Skyline服务选择方法。该方法利用云模型进行服务不确定性的筛选，从中选取代表性Skyline服务，建立代表性服务树作为整数规划选择模型的输入，最后通过整数规划模型求解出满足需求的最优服务。对比结果表明，该方法能够快速、准确地选择出满足用户需求的服务，在保证成功率的基础上使得时间花费有所提升。

云模型；不确定性；代表性Skyline；服务选择

Web服务[1]作为一种开放的业务提供方式，是Web集成技术中最具有活力的应用技术之一，已广泛应用在银行、金融服务机构和电子商务等方面[2]。

Web服务选择的方法主要有以下4种。(1)采用全局最优化的策略，运用整数规划的方法从QoS(Quality of Service)属性方面实现服务选择[1]。(2)基于服务多维QoS信息，从局部最优进行服务选择[2]。(3)运用Agent理论技术, 在面向服务计算领域,实现Web服务的自动发现、交互以及自动组合[3]。(4)基于多属性群决策理论的混合QoS感知web服务组合群决策算法，支持多决策者和具有混合QoS信息(实数、区间数、三角模糊数、直觉模糊数)的服务组合[4]。

随着研究的深入，将Skyline计算[5]应用到服务选择中，通过对服务实现功能或者QoS层次的Skyline建模，从而根据服务间的支配关系选择出符合要求的性能较优的服务。该方法通过Skyline筛选，可以缩小服务选择的范围，提高服务选择的效率。利用MapReduce思想进行并行Skyline服务选择的方法，通过优势度提高了服务选择效率，但随着属性的增多，Skyline服务数目的增大，选择效率变低[6]；基于云模型的Skyline服务选择方法(Skyline service selection based on cloud model，SSSCM)通过云模型计算QoS的不确定性,采用Skyline计算提取Web服务中的Skyline服务，剔除冗余服务，最后利用混合整数规划在Skyline服务中进行服务选择，但该方法的自适应性不足，当服务的数目很大时，很难有效处理，导致服务选择效率不高[7]。本文拟提出一种改进的服务选择方法，采用云模型进行候选服务预处理，利用层次聚类算法对Skyline服务进行聚类，确定代表性服务树，最后通过混合整数规划进行服务选择的求解。

1 云模型与Skyline计算

1.1 云模型

云模型[7]是在概率论和模糊数学理论两者交互的基础上，通过特定的结构算法所形成的定性概念与其定量表示之间的转换模型[8]。在服务选择中，如果对服务的多个QoS属性进行定量到定性的转换，并根据设置的门限值来进行服务不确定性的度量，就可以把服务属性的定量数字转换为不确定性的定性概念。定性概念到定量的转换过程称为正向云发生器；定量到定性概念的转换过程称为逆向云发生器[9]。逆向云发生器通过已知云滴[7]，得到描述定性概念的3个数字特征期望Ex、熵En和超熵He[10]，转换过程如图1所示。

图1 逆向云发生器过程

1.2 Skyline计算

服务选择的过程即是从服务发布者发布的海量服务中选择出最能够符合用户需求的服务。Skyline计算是从一个数据库中抽取不被其他任何数据对象支配的数据对象集合，将不被其他服务支配的服务作为候选服务，可降低服务选择的搜索空间，提高服务选择效率。

2 基于云模型的代表性Skyline服务选择

2.1 云模型计算

假设两个相同功能的服务S1和S2的属性值分别为S1(x11,…,x1m)和S2(x11,…,x1n)，通过逆向云发生器计算其各自的数字特征，即期望Ex、熵En和超熵He，用以表示各服务的不确定度。比较服务S1和S2的熵En和超熵He,可得服务S1和S2不确定性的大小，从而能确定出哪个服务的的QoS较为稳定。设置云模型中En和He参数的门限值，可以剔除不确定性较大的服务，从而保留较为稳定的服务作为候选服务。

2.2 代表性Skyline服务计算

Skyline算法可将一部分被支配的服务剔除，降低服务的搜索空间，从而降低服务选择的时间花费，但是，当某一服务类S的Skyline服务数目K太大，从而不能有效处理时，引入代表性Skyline计算，通过从中选择具有代表性的服务作为整数规划优化选择模型的输入，可以减少算法计算复杂度空间，并能够快速准确地选择出符合要求的服务。

每一个服务都有响应时间和可用性两个QoS属性， Skyline服务示例如图2所示。

图2 Skyline服务示例

由图2可以看出，服务S1不被任何其他服务支配，即没有任何其他服务的响应时间低于S1，并且可用性高于S1，因此S1为Skyline服务，同理，S2，S3，S4也是Skyline服务。

将Skyiline服务SL聚类为m个簇(cluster)，m=2,4,6,8,16…, |SL| ，从各簇中选择具有最高效用的服务作为代表性服务，建立代表性服务的树结构，如图3所示。

(a) 1簇

(b) 2簇

(c) 4簇

(d) 候选服务S3

树中各叶子节点对应1个SL中的Skyline服务，根节点和中间节点则对应在相应簇中选择的代表性服务。综合服务运行时，一旦接受到用户给组合服务的请求时，就从树的根节点开始启动搜索，也就是只考虑每个服务类中的顶层代表性服务，如图3(d)所示。

利用K-means算法[11]，建立代表服务树算法。输入为服务类S的Skyline服务Si,输出为1个代表性服务的二叉树。确定SL中效用值最大的服务根节点S，将S聚类为2个子簇，并分别将这2个簇中效用值最大的服务作为S的子节点。对每个子簇不断重复这个过程，直到不能再生成新的簇。

2.3 服务选择

给定的抽象流程组合服务集合SA={S1,S2,…,Sj,…,Sn}和全局约束向量C=[c1,c2,…,ck,…,cm]。SA服务类别Sj有l个功能属性相同但QoS值不同的候选服务，即Sj={sj1,…,sji,…,sjl}，并且每个服务受约束向量C的限制。通过为每个Sj绑定1个sjl∈Sj，将SA={S1,S2,…,Sn}进行实例化，使得

(2)U(SA)是组合服务集合的QoS效用函数。

通过该效用函数值表示服务类Sj中所有候选服务中第k个属性值。让SA中的每个组合服务满足U最大化，即整体效用U(SA)最大化。

对于本文的顺序结构的服务组合，其优化问题可以用整数规划方法来解决。利用0-1二元决策变量xji表示是否选择服务sji,sji表示服务类Sj中的候选服务。如果xji设置为1，则候选服务被包含在优化组合中，而在同一个服务类Sj中的其他候选服务则会被忽略。将决策变量xji引入效用函数，则服务选择问题就可以被形式化为最大组合服务效用的问题，其目标函数f(x)可以表示为

(1)

为确保选择的组件服务满足全局的QoS约束，则需加入约束条件

同时决策变量xji需满足xji∈[0,1]，还需满足分配约束，以确保为每一个服务类别Sj只绑定一个组件服务，即

(2)

其中n为服务中类的个数，l为每个服务类中的候选服务数量，r为候选服务的QoS属性个数，Ck为QoS的约束值。

采用云模型进行候选服务预处理，利用层次聚类算法对Skyline服务进行聚类，确定代表性服务树，屏蔽了 QoS 不确定性较大的服务,且通过Skyline计算剔除了冗余服务,从而在保证获得可靠服务的同时,降低了服务选择的搜索空间。在所选择的组合服务和全局约束向量下，通过约束条件可以快速、有效的选择出满足用户需求的全局QoS约束最优的组合服务。

3 仿真与验证

实验基于Pentium Dual 2.4 GHz,2.0 GB RAM，Windows 7,Microsoft Visual C++6.0软硬件环境进行，采用2 500个网络上收集到的真实数据集QWS (Quality of Web Service)[12]，将该方法与文献[7]的成功率进行对比，并在保证成功率的基础上对运行时间进行分析评价。

3. 1 成功率对比

成功率 (success ratio，SR)[6]指在某个组合服务运行t次,QoS总效用函数(overall utility,OU)与其实际运行监测结果(monitoring result,MR)的比值不小于设定门限值h,组合服务集合SA中抽取的所有服务都是相同属性下QoS值最高的，由于QoS聚合函数的单调性，即越大的QoS属性值产生越大的QoS聚合值U(SA)。且该用户的全局QoS约束向量C的属性值ci与监测到的该属性的聚合值U(SA)之间的比值w也不小于设定门限值h的次数与t的百分比,即

(4)

其中SR越大，表示成功率越高。本文方法与文献[7]方法的成功率对比结果如图4所示。

图4 本文方法与文献[7]方法成功率对比

图4中可以看出，当候选服务数目在1～1 000之间时，两种方法的成功率相差不是很大，但是当候选服务数目增大到1 000～2 000时，本文方法的成功率整体略优于文献[7]方法的成功率，但当服务数目增加到2 000～2 500时，本文方法的成功率明显优于文献[7]方法。本文方法采用云模型对服务进行不确定性计算，剔除了不确定性较高的服务，通过聚类选择出代表性Skyline服务，保证了候选服务QoS的稳定性和可用性，提高了服务选择的可靠性。

3.2 运行时间对比

图5为本文方法和文献[7]方法在相同的QoS数据类型上时间花费的对比结果。

图5 本文方法与文献[7]方法运行时间对比

从图5中可以看出，不论候选服务的数目为多少，本文方法的运行时间都比文献[7]方法少，尤其在数据量在1 000～2 500之间，本文的运行时间平均在50 ms左右，较为平稳，而文献[7]中的方法随着数据量的增大在不断增加。本文方法在每个候选服务类的Skyline服务中选取了最高效用的代表性Skyline服务作为组合服务选择模型的输入，很大程度的降低了算法的时间复杂度，从而提高了服务选择的效率。

4 结语

通过云模型的逆向发生器进行不确定服务筛选，提高服务选择的可靠性，选取代表性Skyline服务并建立代表性服务树作为整数规划模型的输入。与文献[7]方法对比结果表明，该方法在保证成功率的基础上使得运行时间有所提升，减小了服务选择的搜索空间，降低了服务选择所需的时间花费。

[1] ZENG L H, BENATALLAH B, DUMAS M, et al. Quality driven Web services composition[C/OL]//Proceedings of the 12th International Conference on World Wide Web. Budapest: Hungary, 2003: 411-421[2015-09-08]. https://www.mysciencework.com/publication/show/8b420d8c6dd914be9f42d2d43b5e86e5.

[2] 胡建强，李涓子，廖桂平.一种基于多维服务质量的局部最优服务选择模型[J].计算机学报,2010,33(3)：526-534. DOI: 10.3724/ SP.J.1016 .2010.00526.

[3] 叶荣华,金枝,王璞巍,等.一种需求驱动的自主Web服务聚类方法[J].软件学报,2010,6(21):1181-1195. DOI:10.3724/SP.J.1001.2010.03666.

[4] 张龙昌. 混合QoS感知的服务组合群决策[J].北京邮电大学学报,2013,36(1):27-30.

[5] BORZSONYI S,KOSSMANN D,STOCKER K.The Skyline Operator[C/OL]//International Conference on Data Engineering.Germany:Heidelberg,2001:421-430 [2015-09-08].https://www.computer.org/csdl/proceedings/icde/2001/1001/00/10010421-abs.html .DOI:10.1109/ICDE.2001.914855.

[6] WU J, CHEN L, YU Q, et al. Selecting skyline services for QOS-aware composition by upgrading MapReduce paradigm[J/OL].Cluster Computing ,2013, 16(4):1-14[2016-05-10]. https://www.researchgate.net/publication/257548717_Selecting_skyline_services_for_QoS-aware_composition_by_upgrading_MapReduce_paradigm

[7] 王尚广,孙其博,张光卫,等.基于云模型的不确定性QoS感知的Skyline服务选择[J].软件学报,2012,23(6): 1397-1412.DOI:10.3724/SP.J.1001.2012.04084.

[8] 李德毅,孟海军,史雪梅.隶属云和隶属云发生器[J].计算机研究和发展,1995,32(6):16-21.

[9] 李德毅,李常昱，杜鹢,等.不确定性人工智能[J/OL].软件学报，2004,15(11):1583-1594[2015-09-08].http://www.jos.org.cn/1000-9825/15/1583.htm.DOI :10.13328/j.cnki.jos.2004.11.001

[10] 陈思,王曙燕,孙家泽.基于云模型的可信软件可靠性度量模型[J].计算机应用研究, 2014,31(9): 2729-2731.DOI:10.3969/j.issn.1001-3695.2014.09.039.

[11] 吴夙彗，成颖，郑彦宁，等.K-means研究算法综述[J/OL].现代图书情报技术, 2011,205(5):28-34[2016-05-10]. http://www.cnki.com.cn/Article/CJFDTotal-XDTQ201105007.htm.

[12] Al-MASARI E, MAHMOUD Q H. Discovering the best Web service[C/OL]// WWW ’07 Proceedings of the 16th international conference on World Wide Web, New York: ACM, 2007: 1257-1258[2016-05-10]. http://dl.acm.org/citation.cfm?id=1242572.1242795. DOI:10.1145/1242572.1242795.

[责任编辑：祝剑]

Research on representative Skyline service selection approach based on cloud model

XIE Xiaoyan, QIAN Yu, WANG Li

(School of Computer Science and Technology, Xi’an University of Posts and Telecommunications，Xi’an 710121, China)

A representative Skyline service selection approach based on cloud model is proposed in this paper for the efficiency, accuracy and reliability of the Web service selection. In this approach cloud model is used to filter the uncertainty of services and to select representative Skyline services, and to establish a representative service tree which is also the input of integer programming. Integer programming is then employed to select the best service to meet the need. Experimental results from the testing on the real datasets show that the proposed approach can meet users’ needs reliably and quickly, and improve 10 times of time spending in the premise of selecting the best service.

cloud model, uncertainty, representative Skyline, service selection

10.13682/j.issn.2095-6533.2016.06.022

2015-10-08

陕西省自然科学基金资助项目(2013JC2-32)

谢晓燕(1972-)，女，硕士，副教授，从事服务计算研究。E-mail：xxy@xupt.edu.cn 钱宇(1991-)，男，硕士研究生，研究方向为服务计算。E-mail：z69365656@163.com

TP311

A

2095-6533(2016)06-0114-04