一种基于多维服务质量的局部最优服务选择模型

书书书第３３卷　第３期２０１０年３月计　　算　　机　　学　　报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ．３３Ｎｏ．３Ｍａｒ．２０１０　收稿日期：２００８０４１５；最终修改稿收到日期：２００９１１１０．本课题得到国家“九七三”重点基础研究发展规划项目基金（２００７ＣＢ３１０８０３）、中国博士后科学基金（２００７０４１００６１）和武汉大学软件工程国家重点实验室开放基金项目（ＳＫＬＳＥ２００８０７０４）资助．胡建强，男，１９７１年生，博士，主要研究方向为分布计算技术、语义Ｗｅｂ和软件工程．Ｅｍａｉｌ：[e-mail]．李涓子，女，１９６４年生，教授，博士生导师，主要研究领域为语义Ｗｅｂ和文本挖掘．廖桂平，男，１９６４年生，教授，博士生导师，主要研究领域为信息智能和可视化．一种基于多维服务质量的局部最优服务选择模型胡建强１），２），３）　李涓子２）　廖桂平１）１）（湖南农业大学信息学院　长沙　４１０１２８）２）（清华大学计算机科学与技术系　北京　１０００８４）３）（武汉大学软件工程国家重点实验室　武汉　４３００７２）摘　要　全局最优和局部最优是服务选择的两种策略．现有的全局最优服务选择算法提供端对端约束下最优单解而非可接受的多解，既无法充分体现用户偏好和服务个性，也不利于激励服务提供者优化服务质量．首先，在引入序数效用函数作为局部服务排序的数值尺度的基础上，提出一种基于多维服务质量的局部最优服务选择模型ＭＬＯＭＳＳ（ＭｕｌｔｉＱｏＳｂａｓｅｄＬｏｃａｌＯｐｔｉｍａｌＭｏｄｅｌｏｆＳｅｒｖｉｃｅＳｅｌｅｃｔｉｏｎ），为自动选取优质服务提供重要依据．然后，构造客观赋权模式、主观赋权模式和主客观赋权模式来确定各服务质量属性的权重，既体现用户偏好和服务质量的客观性，又有助于快速生成聚合服务链．最后，通过语义Ｗｅｂ服务集成平台ＳＥＷＳＩＰ（ＳｅｍａｎｔｉｃＥｎａｂｌｅＷｅｂＳｅｒｖｉｃｅＩｎｔｅｇｒａｔｉｏｎＰｌａｔｆｏｒｍ）证明ＭＬＯＭＳＳ模型的有效性和灵活性．关键词　局部最优服务选择模型；序数效用函数；主客观赋权模式中图法分类号ＴＰ３９３　　　犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１０．００５２６犃犕狌犾狋犻犙狅犛犅犪狊犲犱犔狅犮犪犾犗狆狋犻犿犪犾犕狅犱犲犾狅犳犛犲狉狏犻犮犲犛犲犾犲犮狋犻狅狀ＨＵＪｉａｎＱｉａｎｇ　ＬＩＪｕａｎＺｉ　ＬＩＡＯＧｕｉＰｉｎｇ１）（犛犮犺狅狅犾狅犳犐狀犳狅狉犿犪狋犻狅狀犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犎狌狀犪狀犃犵狉犻犮狌犾狋狌狉犪犾犝狀犻狏犲狉狊犻狋狔，犆犺犪狀犵狊犺犪　４１０１２８）２）（犇犲狆犪狉狋犿犲狀狋狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲牔犜犲犮犺狀狅犾狅犵狔，犜狊犻狀犵犺狌犪犝狀犻狏犲狉狊犻狋狔，犅犲犻犼犻狀犵　１０００８４）３）（犛狋犪狋犲犓犲狔犔犪犫狅狉犪狋狅狉狔狅犳犛狅犳狋狑犪狉犲犈狀犵犻狀犲犲狉犻狀犵，犠狌犺犪狀犝狀犻狏犲狉狊犻狋狔，犠狌犺犪狀　４３００７２）犃犫狊狋狉犪犮狋　Ｇｌｏｂａｌｏｐｔｉｍａｌａｎｄｌｏｃａｌｏｐｔｉｍａｌａｒｅｔｗｏｓｔｒａｔｅｇｉｅｓｏｆｓｅｒｖｉｃｅｓｅｌｅｃｔｉｏｎ．Ｔｈｅｃｕｒｒｅｎｔｇｌｏｂａｌｏｐｔｉｍａｌａｌｇｏｒｉｔｈｍｓｏｆｓｅｒｖｉｃｅｓｅｌｅｃｔｉｏｎｐｒｏｖｉｄｅｓｉｎｇｌｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｉｎｓｔｅａｄｏｆｍｕｌｔｉａｃｃｅｐｔａｂｌｅｓｏｌｕｔｉｏｎｓｕｎｄｅｒｅｎｄｔｏｅｎｄｃｏｎｓｔｒａｉｎｔｓ，ｗｈｉｃｈｃａｎｎｏｔｆｕｌｌｙｒｅｆｌｅｃｔｕｓｅｒｓ’ｐｒｅｆｅｒｅｎｃｅａｎｄｓｅｒｖｉｃｅｐｅｒｓｏｎａｌｉｔｙ，ａｎｄｉｓｎｏｔｃｏｎｄｕｃｉｖｅｔｏｅｎｃｏｕｒａｇｅｓｅｒｖｉｃｅｐｒｏｖｉｄｅｒｔｏｏｐｔｉｍｉｚｅｔｈｅｓｅｒｖｉｃｅｑｕａｌｉｔｙ．Ｉｎｔｈｉｓｐａｐｅｒ，ａｎｏｒｄｉｎａｒｙｕｔｉｌｉｔｙｆｕｎｃｔｉｏｎｉｓｕｓｅｄａｓａｎｕｍｅｒｉｃａｌｓｃａｌｅｏｆｏｒｄｅｒｉｎｇｌｏｃａｌｓｅｒｖｉｃｅｓ，ａｎｄｍｅａｎｗｈｉｌｅａＭｕｌｔｉＱｏＳｂａｓｅｄＬｏｃａｌＯｐｔｉｍａｌＭｏｄｅｌｏｆＳｅｒｖｉｃｅＳｅｌｅｃｔｉｏｎ（ＭＬＯＭＳＳ）ｉｓｐｒｏｐｏｓｅｄｆｉｒｓｔｌｙｔｏｐｒｏｖｉｄｅｉｍｐｏｒｔａｎｔｇｒｏｕｎｄｓｔｏｃｈｏｏｓｅｔｈｅｂｅｓｔｓｅｒｖｉｃｅ．Ｔｈｅｎ，ｓｕｂｊｅｃｔｉｖｅｗｅｉｇｈｔｍｏｄｅ，ｏｂｊｅｃｔｉｖｅｗｅｉｇｈｔｍｏｄｅ，ａｎｄｓｕｂｊｅｃｔｏｂｊｅｃｔｉｖｅｗｅｉｇｈｔｍｏｄｅａｒｅｃｏｎｓｔｒｕｃｔｅｄｔｏｄｅｔｅｒｍｉｎｅｔｈｅｗｅｉｇｈｔｏｆｅａｃｈＱｏＳｐｒｏｐｅｒｔｙ，ｗｈｉｃｈｎｏｔｏｎｌｙｓｈｏｗｓｕｓｅｒｓ’ｐｒｅｆｅｒｅｎｃｅａｎｄｔｈｅｏｂｊｅｃｔｉｖｉｔｙｏｆｓｅｒｖｉｃｅｑｕａｌｉｔｙｂｕｔａｌｓｏｈｅｌｐｓｔｏｇｅｎｅｒａｔｅｓｅｒｖｉｃｅｃｏｍｐｏｓｉｔｉｏｎｃｈａｉｎｓ．Ａｔｌａｓｔ，ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｉｎｄｉｃａｔｅｔｈｅｆｌｅｘｉｂｉｌｉｔｙａｎｄｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｉｓｍｏｄｅｌｂａｓｅｄｏｎＳＥＷＳＩＰ（ＳｅｍａｎｔｉｃＥｎａｂｌｅＷｅｂＳｅｒｖｉｃｅＩｎｔｅｇｒａｔｉｏｎＰｌａｔｆｏｒｍ）．犓犲狔狑狅狉犱狊　ｌｏｃａｌｏｐｔｉｍａｌｍｏｄｅｌｏｆｓｅｒｖｉｃｅｓｅｌｅｃｔｉｏｎ；ｏｒｄｉｎａｒｙｕｔｉｌｉｔｙｆｕｎｃｔｉｏｎ；ｓｕｂｊｅｃｔｏｂｊｅｃｔｉｖｅｗｅｉｇｈｔｍｏｄｅ１　引　言开放的网络化应用和“软件作为服务”的理念必将导致基于Ｉｎｔｅｒｎｅｔ环境下软件系统的主要形态、运行方式、生产方式和使用方式发生巨大的变化．未来网络软件的一种趋势表现为构造若干服务动态聚合、渐趋稳定的软件应用系统［１］．随着服务数量的爆炸性成长，存在大量的服务功能相同、非功能特性各异的服务，这一类服务称为服务本体［２］．服务聚合过程实现由服务本体到具体服务的绑定，其中，服务选择直接关系到服务聚合的全局质量以及绑定关系是否需要动态调整．服务质量作为非功能特性的重要组成部分，基于服务质量的服务选择问题倍受学术界和工业界的关注．服务聚合主要有两种服务选择策略：全局最优策略和局部最优策略．以基于流程的服务聚合为例，全局最优策略只是关注服务聚合后服务质量的全局优化效果，不强调局部服务的优劣；局部最优策略以活动为粒度，基于局部最优原则从服务本体中选择合适的局部服务．（１）全局最优策略其在端对端的服务质量的约束下，通常将服务选择的全局服务质量优化问题转化为整数规划、多选择背包算法和模拟退火等数学求解问题．文献［３４］定义了五维的服务质量模型，基于整数规划论提出了满足全局最优的服务选择算法；文献［５］在综合考虑系统负载和代价的基础上，定义了效用函数来选择服务使得服务聚合的端对端响应时间的效用最大化；面向服务网络的模拟退火算法［６］、基于信任感知的蚁群系统优化算法［２］和基于多目标遗传算法ＧＯＤＳＳ［７］都针对全局最优选择服务，并且求解效率会制约服务动态绑定的性能．这类方法构造的聚合服务链是满足约束条件的目标最优单解而非可接受的多解，用户无法根据偏好选择聚合服务链，不能充分体现服务个性和激励服务提供者优化服务质量．（２）局部最优策略其基于局部最优原则对候选服务的服务质量加权和打分，为每个活动选择得分最优的局部服务，其中如何确定评价因子和权重是关键．文献［８］提出由领域专家根据领域经验定制评价因子（包括服务质量属性和服务业务属性），利用先验知识采用机器学习算法计算权重；文献［９］提出基于动态偏好的服务选择算法，针对每次服务配置的最大请求效用来确定权重，并结合声明式逻辑匹配来克服随机选择服务的不足；文献［１０］提出面向分布式环境的迭代选择算法聚合局部最优服务以适应网络环境变化．这类方法未能有效保证服务个性和用户偏好的平衡，更重视服务选择的理论研究而在实用性和通用性方面略显不足．针对上述问题，我们在引入真实度作为附加属性来增强多维服务质量模型的合理性和公正性的基础上，提出了一个基于多维服务质量的局部最优服务选择模型ＭＬＯＭＳＳ（ＭｕｌｔｉＱｏＳｂａｓｅｄＬｏｃａｌＯｐｔｉｍａｌＭｏｄｅｌｏｆＳｅｒｖｉｃｅＳｅｌｅｃｔｉｏｎ），为自动选取优质服务提供重要依据．主要工作包括：引入序数效用函数作为服务排序的数值尺度；构造客观赋权模式、主观赋权模式和主客观赋权模式来确定各服务质量属性的权重；构造实验证明ＭＬＯＭＳＳ模型的有效性和灵活性．本文第２节建立了多维服务质量模型，在引入序数效用函数的基础上给出局部最优服务选择模型；第３节将线性局部最优服务选择模型的权重确定问题建模为多属性决策问题，设计了客观赋权模式、主观赋权模式和主客观赋权模式；第４节构造相关实验证明模型的方法的灵活性和有效性，说明服务局部优先选择算法能有效缩小全局最优服务选择的求解空间；最后对全文的内容进行总结．２　局部最优服务选择模型２．１　多维服务质量模型服务质量的建模对刻画服务聚合的质量需求和系统质量评估至关重要．当前对服务质量的建模呈现出一些特点：（１）针对不同应用需求，服务质量属性集合的组成存在差异性．文献［１１］只定义四维通用的服务质量属性，包括执行代价、执行时间、可靠性和可用性；文献［４］认为服务质量属性应包括可用性、可靠性、费用、吞吐量、精确性和声誉等；文献［１２］定义了五维服务质量属性，包括执行代价、执行时间、可靠性、可用性和声誉；文献［１３］将服务质量属性分为通用属性（包括执行代价、执行时间和声誉等）和业务相关属性（事务、补偿率和惩罚率）．（２）注重服务整体服务质量的真实性，但没有度量各个服务质量属性的可信程度．目前获取服务质量信息主要采用探针法和客户收集法［１４］．文献［１２］使用客户收集法收集服务质量信息；文献［１３，１５］通过探针法收集信息并采用自动７２５３期胡建强等：一种基于多维服务质量的局部最优服务选择模型化的计算服务质量信息，从而保证服务质量的真实性；文献［１６］基于Ｗｅｂ服务服务质量的管理体系结构对ＵＤＤＩ中的服务质量信息进行检测和自动更新．由于服务的自治和分布等特点，实际应用中存在很大局限性．很多服务提供商直接将服务质量信息直接扩展到服务描述中，但容易存在主观的和非公正的因素，通常采用声誉度［１６］或信任度来度量整个服务的可信程度．针对上述问题，可构造一种多维服务质量模型来提高应用的通用性，并引入真实度作为附加属性来增强服务质量属性的合理性和公正性．定义１．　多维服务质量模型是一个狀维可扩充的向量：犙狅狊＝｛狇１，狇２，…，狇狀｝．定义２（真实度ｆｉｄｅｌｉｔｙ）．　设服务狊的真实度狇犳犻犱（狊）是用户对狀维服务质量属性的评价，即狇犳犻犱（狊）＝｛犳犻犱１（狊），犳犻犱２（狊），…，犳犻犱狀（狊）｝，其中犳犻犱犻（狊）＝∑犿犻犼＝１狉犻犼（狊）犿犻表示用户对第犻个服务质量属性的评价，狉犻犼（狊）表示第犻个服务质量属性被第犼次访问给出的评价值，犿犻表示第犻个服务属性被评价的总次数．一个包括执行代价狇犮狅狊狋（狊）、执行时间狇狋犻犿犲（狊）、可靠性狇狉犲犾（狊）和可用性狇犪狏（狊），并以真实度为附加属性的四维服务质量模型可记为犙狅狊＝｛狇犮狅狊狋（狊），狇狋犻犿犲（狊），狇狉犲犾（狊），狇犪狏（狊）｝∪｛狇犳犻犱（狊）｝（１）多维服务质量模型的主要优点：（ａ）良好的开放性和可扩充性：主要表现在应用可灵活定制或加入新的服务质量属性而无需改变模型结构．（ｂ）具有合理性和公共性：针对当前服务选择算法中假定服务质量整体可信的不足，利用真实度增强每个服务质量属性的公正性，可以更合理地指导和监督服务聚合．（ｃ）具有适应服务质量动态变化的能力：受网络环境和服务升级等影响，服务质量可能发生变化，真实度能及时反映服务质量的变化趋势，促进服务提供者提高服务质量．２．２　多维服务质量属性的规范化处理由于多维服务质量属性有不同类型的取值范围，需要对服务质量数据进行规范化处理，将所有服务质量属性的值域调整到统一的区间．由于多数服务质量属性的效用评估与它的值域具有线