摘 要：针对现有服务选择技术的不足，提出一种应用服务社会网络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.