基于扩展图规划的Top-K服务组合方法研究

doi:10.3969/j.issn.0372-2112.2012.07.019

电子学报

基于扩展图规划的Top-K服务组合方法研究

徐猛, 崔立真, 李庆忠

山东大学计算机科学与技术学院, 山东济南 250101

收稿日期:2010-12-15 修回日期:2011-07-10 出版日期:2012-07-25
- 通讯作者:
- 李庆忠
- 作者简介:
- 徐猛男,1978年10月出生于青海格尔木.博士研究生,研究方向为软件与数据工程. E-mail:xumeng_wf@163.com 崔立真男,1976年生,博士,副教授,主要研究方向为软件与数据工程、服务计算. E-mail:clz@sdu.edu.cn 李庆忠男,1965年生,博士,教授,博士生导师,研究领域是大规模网络数据管理、数据集成等. E-mail:lqz@sdu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61003253); 国家科技支撑计划 (No.2009BAH44B02); 山东省自然科学基金 (No.ZR2010FQ010,No.ZR2010FM031); 山东省科技发展计划 (No.2009GG10001002); 高等学校博士学科点专项科研基金 (No.200804221031); 山东大学自主创新基金 (No.2009TS030)

An Extended Graph-Planning Based Top-K Service Composition Method

XU Meng, CUI Li-zhen, LI Qing-zhong

School of Computer Science and Technology, Shandong University, Jinan, Shandong 250101, China

Received:2010-12-15 Revised:2011-07-10 Online:2012-07-25 Published:2012-07-25
- Supported by:
- National Natural Science Foundation of China (No.61003253); National Key Technology Research and Development Program of the Ministry of Science and Technology (No.2009BAH44B02); Natural Science Foundation of Shandong Province (No.ZR2010FQ010, No.ZR2010FM031); Science and Technology Development Program of Shandong Province (No.2009GG10001002); Research Fund for the Doctoral Program of Higher Education of China (No.200804221031); Independent Innovation Fund of Shandong University (No.2009TS030)

摘要/Abstract

摘要： 自动服务组合是目前云计算中的关键技术与研究热点.为大规模用户提供多个满足个性化需求的组合服务是当前云环境下自动服务组合中急需解决的问题.提出了基于扩展图规划的Top-K服务组合方法,借助服务索引和增加图规划中的辅助节点,使得经过一次规划搜索即可找到Top-K个满足用户QoS要求的组合服务.实验表明,该方法能够有效提高服务组合的效率,并保证服务组合结果的正确性,更加适用于云计算环境下海量网络服务及大规模用户个性化需求的自动服务组合问题.

关键词: 服务组合, Top-K, 扩展图规划, 辅助节点

Abstract: ASC (Automatic Service Composition) is the key issue in cloud computing.It is an urgent problem of ASC in cloud computing to provide multiple composition service which can satisfy the personalized requirements for large-scale users.An extended graph-planning based Top-K service composition method is proposed in this paper.By using service indexes and the auxiliary nodes in extended planning graph,Top-K composition service can be found through one search.The approach can improve the efficiency of service composition and ensure the correctness of the result.It applies to the ASC problem in cloud which has a large number of services and the users' requirements are personalized.

Key words: service composition, Top-K, extended graph-planning, auxiliary node

中图分类号:

TP393

徐猛, 崔立真, 李庆忠. 基于扩展图规划的Top-K服务组合方法研究[J]. 电子学报, DOI: 10.3969/j.issn.0372-2112.2012.07.019.

XU Meng, CUI Li-zhen, LI Qing-zhong . An Extended Graph-Planning Based Top-K Service Composition Method[J]. Acta Electronica Sinica, DOI: 10.3969/j.issn.0372-2112.2012.07.019.

参考文献

[1] Zhenqiu Huang,Wei Jiang,Songlin Hu,Zhiyong Liu.Effective pruning algorithm for qoS-aware service composition.Proceedings of the 2009 IEEE Conference on Commerce and Enterprise Computing.Washington DC,USA:IEEE Computer Society,2009.519-522.

[2] Yixin Yan,Bin Xu,Zhifeng Gu,Sen Luo.A qoS-driven approach for semantic service composition.Proceedings of the 2009 IEEE Conference on Commerce and Enterprise Computing.Washington DC,USA:IEEE Computer Society,2009.523-526.

[3] 李鑫,程渤,杨国纬,刘启和.一种基于事件的Web服务组合方法[J].软件学报,2009,20(12):3101-3116. Li Xin,Cheng Bo,Yang Guowei,Liu Qihe.Method of web services composition based on events[J].Journal of Software,2009,20(12):3101-3116.(in Chinese)

[4] 范小芹,蒋昌俊,王俊丽,庞善臣.随机QoS感知的可靠Web服务组合[J].软件学报,2009,20(3):546-556. Fan Xiaoqin,Jiang Changjun,Wang Junli,Pang Shanchen.Random-QoS-aware reliable web service composition[J].Journal of Software,2009,20(3):546-556.(in Chinese)

[5] Blum A,Furst M.Fast planning through planning graph analysis[J].Artificial Intelligence,1997,90:281-300.

[6] Q A Liang,S YW Su.And/or graph and search algorithm for discovering composite web services[J].International Journal of Web Services Research,2005,2(4):48-67.

[7] Zhifeng Gu,Bin Xu,Juanzi Li.Inheritance-aware document-driven service composition.Proceedings of CEC/EEE'07.Tokyo,Japan:IEEE Computer Society,2007.513-516.

[8] Liangzhao Zeng,B Benatallah,AHH Ngu,M Dumas,J Kalagnanam,H Chang.Qos-aware middleware for web services composition[J].IEEE Transactions on Software Engineering,2004,30(5):311-327.

[9] Mahsa Naseri,Ahmad Towhidi.Qos-aware automatic composition of web services using ai planners.Proceedings of the Second International Conference on Internet and Web Applications and Services.Washington DC,USA:IEEE Computer Society,2007.29-29.

[10] Tao Yu,Yue Zhang,Kwei-Jay Lin.Efficient algorithms for web services selection with end-to-end qos constraints[J].ACM Trans Web,2007,1(1):6.

[11] 万长林,韩旭,牛温佳,王文杰,史忠植.基于动态描述逻辑的服务组合及质量模型[J].电子学报,2010,38(8):1923-1928. Wan Changlin,Han Xu,Niu Wenjia,Wang Wenjie,Shi Zhongzhi.Dynamic description logic based web service composition and QoS model[J].Acta Electronica Sinica,2010,38(8):1923-1928.(in Chinese)

[12] 张广泉,戎玫,朱雪阳,何亚丽,石慧娟.基于XYZ/ADL的Web服务组合描述与验证[J].电子学报,2011,39(3A):86-93. Zhang Guangquan,Rong Mei,Zhu Xueyang,He Yali,Shi Huijuan.Specification and verification of web service composition based on XYZ/ADL[J].Acta Electronica Sinica,2011,39(3A):86-93.(in Chinese)

[13] 王文彬,孙其博,赵新超,杨放春.基于非均衡变异离散粒子群算法的QoS 全局最优Web服务选择方法[J].电子学报,2010,38(12):2774-2779. Wang Wenbin,Sun Qibo,Zhao Xinchao,Yang Fangchun.Web services selection approach with QoS global optimal based on discrete particle swarm optimization with non-uniform mutation algorithm[J].Acta Electronica Sinica,2010,38(12):2774-2779.(in Chinese)

[14] Xianrong Zheng,Yuhong Yan.An efficient syntactic web service composition algorithm based on the planning graph model.Proceedings of the 2008 IEEE International Conference on Web Services.Washington DC,USA:IEEE Computer Society,2008.691-699.

[1]	杨震, 杨甜甜, 范科峰, 王勇. 基于信任合成的云服务动态组合机制研究[J]. 电子学报, 2018, 46(3): 614-620.
[2]	张以文, 崔光明, 郭星, 张燕平. 一种基于任务粒化的服务组合优化方法[J]. 电子学报, 2018, 46(1): 245-251.
[3]	叶恒舟, 李陶深, 关云慧. 基于时序约束分解的QoS感知的Web服务组合[J]. 电子学报, 2017, 45(5): 1150-1157.
[4]	张元鸣, 倪宽, 陆佳炜, 徐俊, 肖刚. 基于全局依赖网的Web服务组合自动演化方法研究[J]. 电子学报, 2017, 45(2): 267-277.
[5]	王慧强, 邹世辰, 林俊宇, 吕宏武, 冯光升. 基于信任路径搜索的分布式虚拟化环境下可信服务组件选择方法——HA_OTPS[J]. 电子学报, 2017, 45(1): 192-199.
[6]	张涛, 马建峰, 习宁, 刘西蒙, 熊金波. 面向服务移动社交网络中基于信任的分布式服务组合方法[J]. 电子学报, 2016, 44(2): 258-267.
[7]	李庆新, 刘淑芬, 曲明. 基于本体的Web服务行为语义建模方法[J]. 电子学报, 2015, 43(3): 601-604.
[8]	王新军, 闫实, 彭朝晖, 李庆忠. Extractor：支持查询重构的高效数据库关键词检索系统[J]. 电子学报, 2014, 42(2): 209-216.
[9]	杜玉越, 薛洁, 李彦成. 基于服务簇的服务组合替换与分析[J]. 电子学报, 2014, 42(11): 2231-2238.
[10]	梁俊斌, 马行坡, 奎晓燕. 查询驱动模式下两层传感器网络Top-k查询汇聚算法研究[J]. 电子学报, 2014, 42(10): 2075-2080.
[11]	吉顺慧, 李必信, 邱栋. 基于XCFG的BPEL数据流属性分析与验证[J]. 电子学报, 2013, 41(7): 1365-1370.
[12]	黄龙涛, 邓水光, 戴康, 李莹, 尹建伟. 基于MapReduce的并行Web服务自动组合[J]. 电子学报, 2012, 40(7): 1397-1403.
[13]	杨汝涛, 张绍谦, 窦万春. 一种基于QoS剪枝的Top-k自动服务组合方法[J]. 电子学报, 2012, 40(7): 1489-1491.
[14]	龙军, 袁鑫攀, 桂卫华. 基于环境感知的可信QoS评价与服务选取策略[J]. 电子学报, 2012, 40(6): 1133-1140.
[15]	马环宇, 姜伟, 虎嵩林. QSynth-TopK:一个支持Top K查询的质量敏感的自动服务组合系统[J]. 电子学报, 2012, 40(10): 1933-1937.

基于扩展图规划的Top-K服务组合方法研究

An Extended Graph-Planning Based Top-K Service Composition Method

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics