基于图模型的Web服务组合算法研究

摘要

现阶段，大多数Web服务组合算法侧重于寻找一个服务质量(Quality of Service，QoS)最优的服务组合方案，但是单一的服务组合方案不能很好的满足用户的偏好需求，并且单一的选择容易给系统带来性能瓶颈隐患;同时，由于网络环境动态变化导致的服务失效问题的存在，使得单一服务组合方案的可用性大大降低。因此，为用户提供基于QoS的Topk个服务组合方案，更具可用性和有效性。
　　然而，现有的基于QoS的Topk服务组合算法，不能保证求得的Topk服务组合结果的精度和时间性能。为此，本文在服务依赖图的基础上，提出了解决服务组合Topk问题的QWSC-K算法。该算法利用服务依赖图构建服务之间的关系，进而采用多种优化策略来提高算法的运行效率:首先，通过前向层次过滤和后向层次过滤去除同服务请求参数无关的服务，缩减遍历的服务集空间;然后，采用一种组合路径序列的方式来表示生成的服务组合，避免耗时的组合回溯过程;最后，在搜索遍历过程中，利用动态规划的思想约减组合路径序列的数量，减少组合路径序列的合并开销。与此同时，为了保证了服务组合结果的精度，在遍历过程中，利用优先队列保存组合路径序列，避免了局部最优的情况的出现。
　　同时，已有的服务组合方法大多都假定在服务固定不变的静态环境下，如何求取服务QoS最优或是近似最优的组合服务。然而，互联网上动态变化的服务环境，使得原有的服务组合方案可能由于包含任一失效服务而无法继续使用。现阶段虽然有针对动态环境的服务组合算法的研究，但大多数侧重于对最优服务组合进行动态的更新，缺少对Topk服务组合算法进行专门性的研究。为此，本文在QWSC-K的基础上提出了动态环境下的Topk服务组合算法DQWSC-K。该算法主要是利用发布/订阅网络，监控和获取服务变化的动态事件来更新原有的服务依赖图，然后在更新后的服务依赖图上，利用增量自适应算法仅更新部分受影响服务的状态，而不用搜索整个服务集空间。同已有的方法相比，DQWSC-K算法通过缓存中间的遍历结果，并对中间结果进行动态的更新，来避免低效率的重新计算，能够在保证服务组合质量的前提下获得更高的算法性能。
　　最后，在静态环境中，通过与现有算法的对比实验，验证了本文提出的QWSC-K算法在时间性能和服务组合结果精度上都具有优势;而在动态环境中，通过与重新计算方式的比较，验证了本文提出的DQWSC-K算法具有良好的性能优势。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 相关工作和研究现状

1．2．1 基于最优QoS的Web服务组合方法

1．2．2 基于QoS的Topk的服务组合方法

1．2．3 面向动态环境的Web服务组合方法

1．3 研究内容

1．4 本文内容组织

第二章 相关概念及定义

2．1 Web服务相关定义和概念

2．2 服务依赖图模型的构建

2．3 全局QoS计算规则

2．3．1 QoS类型和组合模式

2．3．2 GQoS的计算规则

2．4 基于QoS的Topk服务组合问题定义

2．5 本章小结

第三章 基于QoS的Topk服务组合算法

3．1 算法思想和框架

3．2 算法模块描述

3．2．1 有效服务候选集获取

3．2．2 获取组合路径序列

3．2．3 组合路径序列转化

3．3 算法分析

3．3．1 时间复杂度

3．3．2 算法最优性证明

3．4 本章小结

第四章 动态环境下Topk服务组合算法

4．1 算法思想和框架

4．2 算法模块描述

4．2．1 动态服务获取与分类

4．2．2 服务组合中间结果获取

4．2．3 服务依赖图更新

4．2．4 增量自适应更新

4．3 算法时间复杂度分析

4．4 本章小结

第五章 实验结果与分析

5．1 实验流程及数据集

5．1．2 DQWSC-K算法实验设置

5．2 对比实验

5．2．1 QWSC-K算法实验比较

5．2．2 DQWSC-K算法实验比较

5．3 本章小结

第六章 总结与展望

致谢

参考文献