kaiyun官方注册
您所在的位置: 首页> 通信与网络> 设计应用> 基于社会网络的Web服务选择算法的研究
基于社会网络的Web服务选择算法的研究
来源:微型机与应用2012年第6期
苏佰川,张国义,许胤龙
(中国科学技术大学 计算机科学学院,安徽 合肥230026)
摘要:针对现有服务选择技术的不足,提出一种应用服务社会网络SSN(Service Social Network)机制的方法。算法主要通过社会网络原理,将Web候选服务根据联系紧密程度和服务本身的QoS属性选择满足用户需求的组合Web服务,理论分析和实验表明算法的有效性和可行性。
Abstract:
Key words :

摘 要:针对现有服务选择技术的不足,提出一种应用服务社会网络SSN(Service Social Network)机制的方法。算法主要通过社会网络原理,将Web候选服务根据联系紧密程度和服务本身的QoS属性选择满足用户需求的组合Web服务,理论分析和实验表明算法的有效性和可行性。
关键词:服务选择;社会网络;服务质量

随着面向服务计算技术的深入发展,通过组合Web服务建立分布式应用系统逐渐成为基于Web应用开发的主流技术。在众多可获得的Web服务资源中,如何选择合适的服务实例进行组合,使之既能满足应用的功能需求,又能满足用户提出的QoS需求,是一个备受关注的问题,并已得到了广泛的研究。
QoS约束的Web服务选择与组合是一类组合优化问题。到目前为止,求解该问题比较典型的方法有线性规划算法[1-2]和遗传算法[3-6]。线性规划算法在候选服务集规模较小时是非常有效的,但是随着规模的加大,计算耗时增长速度明显加快,可扩展性变差。遗传算法被用于QoS的全局组合优化已有许多成功的案例,但是,由于在诸多的研究中一般采用随机交叉和变异操作,没有考虑候选服务实例之间实际存在的连接偏好,组合服务的可靠性难以得到有效的保证。连接频率反映了服务之间的连接偏好,频率越高,下一次连接的可能性就越大,在一定程度上可增强组合服务的可靠性。如何利用候选服务实例之间的连接偏好优化服务的随机选择,提高服务组合的效率与成功率是本文主要关注的问题。
根据软件工程的一般常识可知,一个复杂的组合服务包含平行、分支、选择、循环等结构,可以利用数据流聚合方法形成颗粒较大的结构块。而对于一个大规模的候选服务集合,应用社会网络社区形成机制[7],也可以形成与服务流程聚合块功能相一致的服务子集,即所谓的服务社区。这样,服务选择就演化成社区选择问题,运用遗传算法能较好地保证结构性选择,且依据连接权重形成的服务社区能充分体现服务之间的连接偏好。根据这一思想,本文提出了一个基于社区形成机制和遗传算法的服务选择方法,与传统遗传算法不同的是,设计了一个依据连接偏好的效用函数估算随机选择概率。初步的实验结果证明,该方法行之有效,且具有较高的计算效率。
1 问题描述
对于用户提出的服务需求首先建立组合服务流程,图1所示为一个有8个原子服务S1,S2,…,S8的服务流程。
如图1所示,一般一个组合Web服务流程由多个Web原子服务组成,每个Web原子服务又对应有多个候选服务。这些候选服务可能由不同的服务提供者提供,具有相同的功能和不同的QoS度量值。




随着服务计算的迅速发展,可利用的Web服务资源越来越多,候选服务结点的规模也越来越大。本文总结了近期相关的工作,提出了一种基于社会网络社区形成机制的Web服务选择方法。将Web服务选择问题转换到社会网络中,利用社会网络特有的性质结点联系强度等来解决服务选择问题。提出了一种服务社会网络概率选择方法,此方法与遗传算法的不同之处在于变异结点的选择不是随机的,而是根据结点之间的连接频率,它反映了服务之间的连接偏好,频率越高,下一次连接的可能性就越大。
虽然最终算法给出了很好的性能,但还有待进一步改进,如本文算法是基于单目标优化的,希望今后在多目标优化方面有所进展。同时本文算法是基于历史信息(服务实例)的,因此当历史信息较少或刚开始没有历史信息时性能方面可能会很差,希望今后在这方面也有所研究。
参考文献
[1] Zeng Liangzhao,BENATALLAH B,DUMAS M,et al.Quality driven Web services composition[C].Proceedings of the 12th International Conference on World Wide,2003.
[2] ARDAGNA D,PERNICI B.Adaptive service composition in flexible processes[J].IEEE Trans.Software Eng,2007,33(6):369-384.
[3] HWANG S Y,WANG H,TANG J,et al.A probabilistic approach to modeling and estimating the QoS of Web-Services-based Workflows[J].Information Sciences,2007,23(177):5484-5503.
[4] KLEIN A,ISHIKAWA F,BAUER B.A probabilistic approach to service selection with conditional contracts and usage patterns[C].ICSOC-ServiceWave2009,2009:253-268.
[5] Tang Maolin,Ai Lifeng.A hybrid genetic algorithm for the optimal constrained Web service selection problem in Web Service composition[C].WCCI 2010 IEEE World Congress on Computational Intelligence,2010.
[6] Liu Shulei,Liu Yunxiang,Jing Ning,et al.A dynamic Web service selection strategy with QoS global optimization based on multi-objective genetic algorithm[C].GCC2005,2005:84-89.
[7] KUMPULA J M,ONNELA J P,SARAMAKI J,et al.Model of community emergence in weighted social networks[J]. Computer Physics Communication,2009(180):517.
[8] YU T,ZHANG Y,LIN K J.Efficient algorithms for Web services selection with end-to-end qos constraints[J].ACM Transactions on the Web,2007,1(1):1-26.
[9] NEWMAN M E J.Analysis of weighted networks[J].Physical review,2004,70(05):1-9.
[10] WASSERMAN S,FAUST K.Introduction to social network analysis[M].Cambridge Cambridge Univ.Press,1994.

此内容为AET网站原创,未经授权禁止转载。
Baidu
map