基于三角模糊数的Web服务QoS量化算法

基于三角模糊数的Web服务QoS量化算法 摘要：在Web服务中用实数形式给出的QoS属性缺乏灵活性和精确性，但使用语言型数据表示的QoS属性无法用于计算，为了使语言型数据可以用于计算多属性群决策问题，本文提出了一种基于联系数的三角模糊数的Web服务选择算法。该算法基于多个用户对于Web服务的语言型评价进行服务选择，同时将三角模糊数转化为联系数并建立了联系数决策模型，给出了决策步骤，基于此对Web服务的安全等级进行了排序。该算法结合了联系数和三角模糊数的特点，具有客观性。实验表明，相比其他Web服务选择算法，该算法计算简便，服务选择结果符合用户的意愿。关键字：多属性群决策； Web服务；联系数；三角模糊数 Abstract: In the process of Web service selection, users can easily use language-based data to describe their real requirements. However, such type of data is hardly to quantized. To solve this problem, this paper proposes a Web service selection algorithm using triangular fuzzy number. The algorithm based on users for the language of the Web service type evaluation for service selection, and converting the triangular fuzzy number to connection numbers and connection numbers decision model is established. The decision-making steps are given. Based on the Web services security level for the order. The algorithm combines the characteristics of connection numbers and triangular fuzzy number, it is more objectivity. Experimental results show that compared with other Web services selection algorithm, the algorithm is simple, the service selection results conform to the users real wishes.Key words：multi-attribute group decision-making;Web services ;connection number;triangular fuzzy number1 引言多属性群决策问题是多个决策者依据自己的知识、经验和喜好对决策空间（即方案X）进行优劣排序或评估信息的过程。它在工程系统、社会、经济、管理、军事及其他领域是十分普遍和重要的。目前，多属性群决策的研究已取得了重大的成就。对模糊形式的研究已经逐渐引起人们的关注了。然而，对模糊多属性群决策问题实用方法的研究还比较少，并且这些方法在计算机上的适用范围有限，计算复杂。Web服务在面向服务的体系结构下，成为了企业级服务集成的关键技术之一。在Web服务中属性分为功能属性和非功能属性，进行Web服务选择时是在用户的约束条件下通过结合服务的选择结果并保证服务质量而生成的组合服务，在此过程中既要注重满足用户服务需求的功能属性，又要注重使所选择的Web服务组合达到最优的非功能属性。目前，基于QoS的比较流行的Web服务选择算法主要是采用启发式选择算法，比如遗传算法、粒子群优化算法、蚁群算法等。这些算法有着通用性强、简单易于实现、高并发、高可移植性等优点，但同时也存在着易于陷入局部最优解、结果不稳定、收敛性差、对算法参数有依赖性等缺点，同时这些所有算法有一个限制，即所有的QoS数据必须以实数形式明确给出，这种限制导致对QoS的描述缺乏灵活性，进而造成有效信息的丢失以及无法满足对QoS精确描述的需求。例如，用户更喜欢用“较高”、“一般”这样的语言来形容Web服务的安全等级，而非明确的实数来表达。这样的语言型数据无法直接进行数学计算。基于三角模糊数的应用受到了越来越多人的关注，三角模糊数是确定与不确定的结合，三角模糊数在中值上的取值相对确定，在上下确界中间取中值以外的其他值是相对不确定的，结合这一特点，我们可以把三角模糊数转化为集对分析（Set Pair Analysis,SPA ）理论中的联系数。本文提出了一种基于三角模糊数的Web服务QoS量化算法(Web service using triangular fuzzy number )。该算法是把多个用户对于Web服务QoS属性的语言型评价转化为三角模糊数初始评价矩阵，然后进行去模糊化处理，该算法共包括6个主要步骤：语言型描述数据转化得到三角模糊数的初始评价矩阵、三角模糊数初始评价矩阵的规格化、规格化后的评价矩阵转化为联系数的形式、权值计算、依据公式求综合决策值、稳定性检验。本文设计并实现了一个基于三角模糊数的多用户评价的服务选择系统，系统中的三角模糊数算法可以在一定程度上解决用户对不熟悉领域进行评价时的推荐问题。2 基本概念2.1 三角模糊数、联系数定义1 若，其中，称为一个三角模糊数，其中、分别表示三角模糊数的下确界和上确界，表示三角模糊数的中值，把称为三角模糊数的取值区间。设有两个三角模糊数，它们之间的运算有加法运算、乘法运算、除法运算和数乘运算。定义2 设R为实数集，,则称为联系数，其中为任意非负实数，称为确定数，为非负实数，称为不确定数，是一个不确定量，需要根据问题的具体情况确定取值，有时也可仅作为一个不确定量的标记使用，i对于结果的影响可以用统计试验和其他方法来确定，参考文献11。若，称为归一化联系数。对于不满足要求的可转化为满足要求的形式： （1） 设，是两个联系数，则它们之间的运算有加法运算、乘法运算，在此我们可以证明联系数的加法运算和乘法运算满足交换律，同时，联系数的加法运算还满足结合律。2.2 三角模糊数向联系数的转换根据三角模糊数的确定性与不确定性的特点，三角模糊数可以转化为联系数表示，若有一个三角模糊数为，转化为联系数的形式为，其中的取值范围为： 该公式建立了三角模糊数与联系数的关系，在联系数的基础上，可以进行三角模糊数的多属性问题的决策。2.3 Web服务的QoS属性Web服务的服务质量(quality of service,QoS)是用户选择服务的一个重要依据，是对web服务满足服务请求者需求能力的一种度量，QoS模型是一个可扩充向量，可以从很多方面来描述服务质量，如：可扩展性、并发处理能力、响应时间、可靠性、服务价格、吞吐量、可用性、安全性、准确性等等，这些分别是从不同的角度对QoS进行评估。由于QoS属性包括的因素很多，本文的算法可以分别用于这些方面，在本文中我们是以QoS属性中的安全性为例来说的。3 算法的设计该算法以多用户评价信息为基础，先进行去模糊化的处理，然后对相应的服务进行排序，根据输出的结果进行Web服务选择，以语言型描述的安全等级属性为例，具体步骤如下：1） 用户在访问服务之后，可以对其安全等级属性进行语言型的描述，再由QoS专家把用户的评价转化为三角模糊数，用户的语言型描述向三角模糊数进行转化时可以使用三角模糊数值表，如表1所示。 表1 三角模糊数索引表 指标评语评价模糊数很差0,0,0.1差0,0.1,0.3中下0.1,0.3,0.5中0.3,0.5,0.7中高0.5,0.7,0.9高0.7,0.9,1很高0.9,1,1 用三角模糊数值表将语言型描述转化为三角模糊数的方法有很多，文献14中提出一个5个等级的公式，(不重要，较不重要，一般，较重要，重要)。本文依据的是一个7等级的模糊数表，比如用户的评价为“中高”时，转化为对应的三角模糊数为（0.5,0.7,0.9）。假设对于一个具体的Web服务类S，它有n个原子候选服务，有d个专家参与这n个原子服务的评价，则它形成一个d*n三角模糊数的初始评价矩阵R，其中第i行j列表示第i个专家对第j个原子候选服务的评价。 2）属性指标之间不仅存在量纲上的差别，而且在尺度上也有所不同，如果不进行规格化处理，指标仍存在一些问题，故我们在此利用公式对得到的初始评价矩阵进行规格化处理，进而减少人的主观性。进行规格化的方法有很多种，如果我们采用，在进行规格化时若用户的评价转化为三角模糊数（0,0,0.1），则0就会出现在分母上；同时第一个数也可能会出现负数，这与三角模糊数的定义相矛盾，故我们不采取这种规格化方法。在进行规格化的时候，我们采用如下公式进行： （2）3） 将规格化后的三角模糊数初始评价矩阵转化为对应的联系数，仍用矩阵的形式表示。4） 确定加权向量 : (3) 模糊语义量化算子 且，对应于模糊语义量化准则，“大多数”、“至少半数”和“尽可能多”的算子Q中参数对分别为：(a,b)=(0.3,0.8)，(a,b)=(0,0.5)和(a,b)=(0.5,1)。 5）利用联系数决策模型计算各个原子候选服务的综合决策值，并对这些综合决策值进行排序，综合决策值大的候选服务优于综合决策值小的候选服务。利用联系数的加法和数乘的定义，我们可以得到由权重与属性值三角模糊数对于某原子候选服务的综合评价值，将此称为三角模糊数多属性决策基本模型，其值称为联系数决策值，得出的结果表示为：。 在联系数的决策模型中，i根据“i的比例取值原理”取值，计算出最后的综合决策值，决策值大的优先于决策值小的。6）稳定性检验。取i在区间内的其他值，检验前述排序的稳定性。4 应用分析1） 现假设有3个原子候选服务，有3个专家参与这3个原子服务的评价，则它形成一个3*3三角模糊数的初始评价矩阵R，其中第i行j列表示第i个专家对第j个原子候选服务的评价，得到的初始评价矩阵为： 2）利用公式2对初始评价矩阵进行规格化后得到为： 3）将规格化后的评价矩阵转化为联系数的表示形式为： 4）利用公式3对3个专家进行权重向量的计算，得到他们的权重向量为： 5) 由步骤4得到的权重与属性值三角模糊数利用联系数决策模型对于所有原子候选服务进行综合评价并得出综合评价值：M(1)=0.1809+0.3043i M(2)=0.8476+0.0948iM(3)=0.4667+0.2687i 根据公式1按照“i的比例取值原理”可以计算出i的取值，进而得到综合决策值，经过比较得出这三个原子候选服务的排序为：2,3,1. 6) 稳定性检验。当i=0时，排序的结果不变，仍为2,3,1。当i=0.5时，排序结果仍不变，为2,3,1（i的取值是在-1,1的区间内取值的）。 5 实验分析5.1 实验理论分析在多属性群决策的Web服务选择算法中，三角模糊数是用的最多的，三角模糊数的互补判断矩阵就是排序方法中的一个。现假设对于一个具体的Web服务类S，它有n个原子候选服务，有d个QoS专家，则它形成一个d*n三角模糊数的初始评价矩阵，在基于互补判断矩阵的算法中三角模糊数初始评价矩阵转化为三角模糊数互补判断矩阵时需要进行原子候选服务的两两比较得出互补判断矩阵，对于一个d*n的矩阵，需要计算d*n!次才能求出互补判断矩阵，而本文中的算法在将三角模糊数初始判断矩阵转化为联系数的形式时是一对一转化的，而且都是减法运算，只需要计算d*n次就可以求出了。本算法的主要优点是算法清晰，计算简单，结论合理，与运用三角模糊数的互补判断矩阵算法的结论是相同的。 图1 n=5图2 n=10 上图1和图2是和的比较，n分别为5和10，从图中我们可以看出随着n的增大，n!的增长速度远远大于n，故随着原子候选服务的增多，本文中算法的计算简单的特点会越来越明显。5.2 联系数中不确定量i对算法结果准确性的影响分析在算法中，最后一步是进行稳定性检验，主要是在区间内取除根据i的比例取值之外的其他i值进行验证，看是否结果一致，若一致则i在该区间内对于结果的稳定性无影响，否则就要对影响排序结果稳定的i的取值进行合理性的讨论。下图3是对于应用分析中i在-1,1之间的取值对结果稳定性影响的验证，从图中可以看出i在区间-1,1内的取值对排序结果没有任何的影响，即该排序结果是稳定的。 图3 i取值对结果稳定性的影响5.3权值参数对算法准确性的影响分析 在本算法中参数主要是出现在求权值的过程中，模糊语义量化准则中将“大多数”、“至少半数”和“尽可能多”的参数对分别设为（0.3,0.8）、（0,0.5）和（0.5,1)，如下图4所示，在这三种情况下，排序结果没有发生变化，这个结果表明在Web服务选择中原子候选服务1是理论上的最优值。在Web服务中去模糊化后的QoS属性值差别越大越好，这样不同的原子候选服务的QoS属性值的相似度就越低，这样在进行Web服务选择时出错的概率就越低。本文采用“多数”的 态度，取(a,b)=(0.3,0.8)。 (a,b)=(0.3,0.8) (a,b)=(0,0.5) (a,b)=(0.5,1) 图4 a、b的取值对算法的影响5.4基于联系数和基于互补判断矩阵的结果对比现假设有6个原子候选服务，有6个专家参与这6个原子服务的评价，将基于联系数和基于互补判断矩阵的结果进行对比，结果如下所示：图5 基于联系数和基于互补判断矩阵的结果对比 图5是有6个原子服务，由QoS专家的数据分别采用三角模糊数中的联系数和互补判断矩阵进行Web服务的排序，由上图可以看出两种方法的排序结果是相同的，都是1、3、2、4、6、5.6 结束语 本文给出的算法是一种基于联系数的三角模糊数的Web服务选择算法，它是模糊多属性群决策问题在Web服务选择上的实际应用。该算法仍有进一步改进的必要，比如，在算法中求权值向量时，如果原子候选服务的个数足够大的话，就会导致两端的专家的权重为0的现象；对QoS属性的描述不止语言型一种，还需对其进行改进让其可以适应不同的QoS属性。参考文献1 刘满凤，宋颖.考虑决策者行为偏好的三角模糊数多属性决策方法J.统计与决策，2014,9:44-46.2 陈晓红，阳熹.一种基于三角模糊数的多属性群决策方法J.系统工程与电子技术，2008,30(2)：278-282.3 陈彦萍.Web服务选择优化算法的设计与实现J.东南大学学报(自然科学版)，2008,38(1):288-291.4 蒋哲远，韩江洪，王钊.动态的QoS感知Web服务选择和组合优化模型J.计算机学报，2009,32(5):1014-1025.5 刘莉平，陈志刚，刘爱心.基于粒子群算法的Web服务组合研究J.计算机工程，2008,34(5):104-112.6 王勇，代桂平，侯亚荣.信任感知的组合服务动态选择方法J.计算机学报，2009,32(8):1668-1675.7 Xixiang Zhang,Weimin Ma,Liping Chen. New Similarity of Triangular Fuzzy Number and Its ApplicationJ.The Scientific World Journal, 2014, Vol.2014 .8 赵克勤.集对分析中的不确定系统理论在AI中应用J.智能系统学报，2006，1(2)：16-25.9 冯向前.区间数不确定多属性决策方法研究D.南京航空大学，2007.10 吴朱军，南振岐，孙艳川.基于联系数的三角模糊数评估软件风