基于时序约束分解的QoS感知的Web服务组合

doi:10.3969/j.issn.0372-2112.2017.05.018

电子学报 ›› 2017, Vol. 45 ›› Issue (5): 1150-1157.DOI: 10.3969/j.issn.0372-2112.2017.05.018

基于时序约束分解的QoS感知的Web服务组合

叶恒舟^1,2, 李陶深³, 关云慧²

1. 广西大学电气工程学院, 广西南宁 530004;
2. 桂林理工大学信息科学与工程学院, 广西桂林 541000;
3. 广西大学信息与工程学院, 广西南宁 530004

收稿日期:2015-10-20 修回日期:2016-05-06 出版日期:2017-05-25
- 作者简介:
- 叶恒舟 男,1980年出生于湖北汉川,广西大学电气工程学院博士研究生,桂林理工大学信息科学与工程学院副教授,研究方向:Web服务组合、优化设计.E-mail:18123408@qq.com;李陶深 男,1957年出生于广西南宁,广西大学计算机与电子信息学院教授,博士生导师,研究方向:CAD理论与应用、分布式工程数据库、遗传优化设计、网络计算与信息安全、无线Mesh网络.E-mail:tshli@gxu.edu.cn;关云慧 女,1990年出生于安徽安庆,桂林理工大学硕士研究生,研究方向:Web服务技术、组合优化.
- 基金资助:
- 国家自然科学基金 (No.51365010）; 广西自然科学基金 (No.2014GXNSFBA118269）

QoS-Aware Web Service Composition Based on Temporal Constraints Decomposition

YE Heng-zhou^1,2, LI Tao-shen³, GUAN Yun-hui²

1. College of Electrical Engineering, Guangxi University, Nanning, Guangxi 530004, China;
2. College of Information Science and Engineering, Guilin University of Technology, Guilin, Guangxi 541000, China;
3. College of Information and Engineering, Guangxi University, Nanning, Guangxi 530004, China

Received:2015-10-20 Revised:2016-05-06 Online:2017-05-25 Published:2017-05-25
- Supported by:
- National Natural Science Foundation of China (No.51365010); Natural Science Foundation of Guangxi Zhuang Autonomous Region, China (No.2014GXNSFBA118269)

摘要/Abstract

摘要：

基于时序约束的QoS感知的Web服务组合（TC_QSC）问题是在考虑时序约束的基础上寻找满足QoS约束或效用最大化的Web服务组合问题，受到了越来越多的关注.本文提出了一种时序约束分解方法，把施加于整个或部分工作流的时序约束分解为施加于每个活动的局部时序约束，从而将TC_QSC问题转换为一般的QoS感知的Web服务组合（QSC）问题，并通过过滤不满足局部时序约束的候选服务，一定程度上减小原问题的规模.这种时序约束分解过程主要依赖于工作流及其涉及的活动，而与各活动的候选服务关联不大，复杂度较低.实验测试了该方法的效果与时间开销，验证了其对于局部优选算法的必要性.

关键词: 时序约束, 约束分解, QoS感知, Web服务组合, 贪心算法

Abstract:

The problem of Temporal Constraints based QoS-aware web Service Composition (TC_QSC) is becoming increasingly critical in recent years.Its objective is to select the Web service composition which maximizes the QoS utility while preserving QoS constraints and temporal constraints.This paper proposes a temporal constraints decomposition method that formulates the TC_QSC problem into a general QoS-aware Web service composition (QSC) problem by means of decomposing the temporal constraints imposed on the whole or part of the workflow to a set of local temporal constraints for each activity.So the problem scale is reduced by filtering out those candidate web services violating local temporal constraints.The temporal constraints decomposition process is mainly dependent on the workflow and activities involved in it,while it has little to do with the candidate services.Therefore,its complexity is lower.The experiments have demonstrated the effectiveness and time cost of the proposed method and verify its necessity to local selection algorithm.

Key words: temporal constraint, constraint decomposition, QoS-aware, Web service composition, greedy algorithm

中图分类号:

TP393

叶恒舟, 李陶深, 关云慧. 基于时序约束分解的QoS感知的Web服务组合[J]. 电子学报, 2017, 45(5): 1150-1157.

YE Heng-zhou, LI Tao-shen, GUAN Yun-hui . QoS-Aware Web Service Composition Based on Temporal Constraints Decomposition[J]. Acta Electronica Sinica, 2017, 45(5): 1150-1157.

参考文献

[1] Zou Guobing,Lu Qiang,Chen Yixin,et al.QoS-aware dynamic composition of web services using numerical temporal planning[J].IEEE Transactions on Services Computing,2014,7(1):18-31.
[2] Wang Pengwei,Ding Zhijun,Jiang Changjun,et al.Constraint-aware approach to web service composition[J].IEEE Transactions on Systems,Man,and Cybernetics:System,2014,44(6):770-784.
[3] Virginie G,Maude M,Cécile M.Web services composition:complexity and models[J].Discrete Applied Mathematics,2015,196(2):67-82.
[4] Mohammad A,Thomas R.Combining global optimization with local selection for efficient QoS-aware service composition[A].World Wide Web Conference Series[C].New York:ACM Press,2009.881-890.
[5] Yu Tao,Zhang Yue,Lin Kwei-Jay.Efficient algorithms for web services selection with end-to-end QoS constraints[J].ACM Transactions on the Web,2007,1(1):1-26.
[6] Luo Yuansheng,Qi Yong,Hou Di.A novel heuristic algorithm for QoS-aware end-to-end service composition[J].Computer Communications,2011,34(9):1137-1144.
[7] Zeng Liangzhao,Boualem B,Anne H H N,et al.Qos-aware middleware for web services composition[J].IEEE Transactions on Software Engineering,2004,30(5):311-327.
[8] Palanikkumar D,Kousalya G.An evolutionary algorithmic approach based optimal web service selection for composition with quality of service[J].Journal of Computer Science,2012,8(4):573-578.
[9] Erdinc Y A,Pinar K.Improved genetic algorithm based approach for QoS aware web service composition[A].IEEE International Conference on Web Services[C].New York:IEEE Press,2014.463-470.
[10] Wang Dandan,Yang Yang,Mi Zhenqiang.A genetic-based approach to web service composition in geo-distributed cloud environment[J].Computers and Electrical Engineering,2015,43(C):129-141.
[11] Liao Jianxin,Liu Yang,Wang Jingyu,et al.Service composition based on niching particle swarm optimization in service overlay networks[J].KSII Transactions on Internet and Information Systems,2012,6(4):1106-1127.
[12] Wang Shangguang,Sun Qibo,Zou Hua,et al.Particle swarm optimization with skyline operator for fast cloud-based web service composition[J].Mobile Networks and Applications,2013,18(1):116-121.
[13] 王尚广,孙其博,杨放春.基于全局QoS约束分解的Web服务动态选择[J].软件学报,2011,22(7):1426-1439. Wang Shangguang,Sun Qibo,Yang Fangchun.Web service dynamic selection by the decomposition of global QoS constraints[J].Journal of Software,2011,22(7):1426-1439.(in Chinese)
[14] Farhad M,Naser N B,Kamran Z,et al.QoS decomposition for service composition using genetic algorithm[J].Applied Soft Computing,2013,6(5):3409-3421.
[15] 尹浩,张长胜,张斌等.一种求解SLA等级感知服务组合问题的多目标离散粒子群优化算法[J].电子学报,2014,42(10):1983-1990. Yin Hao,Zhang Changsheng,Zhang Bin,et al.A multi-objective discrete particle swam optimization algorithm for SLA-aware service composition problem[J].Acta Electronica Sinica,2014,42(10):1983-1990.(in Chinese)
[16] 徐猛,崔立真,李庆忠.基于扩展图规划的Top-k服务组合方法研究[J].电子学报,2012,40(7):1404-1409. Xu Meng,Cui Lizhen,Li Qingzhong.An extended Graph-planning based Top-k service composition method[J].Acta Electronica Sinica,2012,40(7):1404-1409.(in Chinese)
[17] Sherry X S,Jing Zhao.A decomposition-based approach for service composition with global QoS guarantees[J].Information Sciences,2012,199(15):138-153.
[18] Liu Zhizhong,Xue Xiao,Shen Jiquan,et al.Web service dynamic composition based on decomposition of global QoS constraints[J].Int J Adv Manuf Technol,2013,69(9):2247-2260.
[19] Nawal G,Olivier P,Christophe R.Timed specification for web services compatibility analysis[J].Electronic Notes in Theoretical Computer Science,2008,200(3):155-170.
[20] Du Yanhua,Tan Wei,Zhou Mengchu.Timed compatibility analysis of Web service composition:a modular approach based on Petri nets[J].IEEE Transactions on Automation Science and Engineering,2014,11(2):594-606.
[21] Jerry R H,Feng Pan.An ontology of time for the semantic web[J].ACM Transactions on Asian Language Information Processing(TALIP),2004,3(1):66-85.
[22] Chen Jinjun,Yang Yun.Localizing temporal constraints in scientific workflows[J].Journal of Computer and System Sciences,2010,76(2):464-474.
[23] Zhou Zhangbin,Laurence T Y,Sami B,et al.Verifying mediated service interactions considering expected behaviors[J].Journal of Network and Computer Applications,2011,34(4):1043-1053.
[24] 杜彦华,范玉顺.基于生成图的工作流多过程动态时序一致性验证方法[J].电子学报,2009,37(10):2181-2186. Du Yanhua,Fan Yushun.A sprouting graph based approach to dynamic check the temporal consistency of workflow multi-process[J].Acta Electronica Sinica,2009,37(10):2181-2186.(in Chinese)
[25] Du Yanhua,Wang Xiaofei,Yao Jianshi.Probability based timed compatibility of Web service composition[J].Practical Applications of Intelligent Systems,2012,124(1):31-39.
[26] 徐红霞,杜彦华,董绍华.时序约束下Web服务组合的兼容性及修正研究[J].计算机集成制造系统,2012,18(11):2562-2572. Xu Hongxia,Du Yanhua,Dong Shaohua.Study on the compatibility and modification of web service composition with temporal constraints[J].Computer Integrated Manufacturing System(CIMS),2012,18(11):2562-2572.(in Chinese)
[27] Eyhab A M,Qusay H M.Discovering the best web service[A].International Conference on World Wide Web(WWW)[C].New York:ACM Press,2007.257-1258.
[28] Eyhab A M,Qusay H M.QoS-based discovery and ranking of Web services[A].International Conference on Computer Communications and Networks (ICCCN)[C].New York:IEEE Press,2007.529-534.

基于时序约束分解的QoS感知的Web服务组合

QoS-Aware Web Service Composition Based on Temporal Constraints Decomposition

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

[1]	杨洋. 改进帕累托算法求解超大规模多选择背包问题[J]. 电子学报, 2020, 48(6): 1205-1212.
[2]	曲长文, 冯奇, 李廷军. 基于分治-贪心算法的高斯混合多观测站CPHD滤波器[J]. 电子学报, 2018, 46(10): 2472-2479.
[3]	吉顺慧, 李必信, 邱栋. 基于XCFG的BPEL数据流属性分析与验证[J]. 电子学报, 2013, 41(7): 1365-1370.
[4]	吴吉庆;彭宇行;刘锋. DSF:一种时序约束下的快速数据分发算法[J]. 电子学报, 2012, 40(2): 365-370.
[5]	田野;刘大有;. 求解流水车间调度问题的混合粒子群算法[J]. 电子学报, 2011, 39(5): 1087-1093.
[6]	张广泉;戎玫;朱雪阳;何亚丽;石慧娟. 基于XYZ/ADL的Web服务组合描述与验证[J]. 电子学报, 2011, 39(3A): 86-93.
[7]	毕敬;朱志良;范玉顺. Web服务组合中行为兼容性分析与优化控制策略[J]. 电子学报, 2011, 39(12): 2842-2849.
[8]	杜彦华;范玉顺. 基于生成图的工作流多过程动态时序一致性验证方法[J]. 电子学报, 2009, 37(10): 2181-2186.