Web服务组合与验证相关技术研究
|
摘要
随着Web服务技术的快速发展,越来越多的稳定易用的Web服务共享在网络上,但是单个Web服务的功能一般比较简单,很多情况下不能满足用户的实际需要,为了更加充分地利用这些共享的Web服务,有必要将这些Web服务组合起来,提供更为强大的功能,满足用户的实际需求。Web服务组合验证能提前发现Web服务组合中存在的缺陷,是提高Web服务组合执行的成功率和增强用户满意度的关键,对Web服务组合的正确运行具有十分重要的意义。本文的主要工作如下：
1.提出一种基于与或图的Web服务组合方法。该组合方法可分为两个步骤,首先根据已有可用的Web服务和用户提出的服务请求,从服务请求的输出对象到输入对象反向生成服务参数与或图。然后在与或图中搜索能够满足服务请求的服务组合图,该方法可以提高服务组合的效率和成功率。
2.提出一种利用Pi演算对Web服务组合的正确性进行验证的方法。先用Pi演算对Web服务组合进行建模,然后在Pi演算辅助工具MWB中验证该服务组合方案是否存在死锁和是否满足用户需求。
3.利用Pi演算对Web服务组合中一个服务是否可以被另一个服务替换进行验证。先用Pi演算对进行服务替换后新的组合服务进行建模,并根据新的组合服务是否兼容来判断该服务替换的可行性。
本文对Web服务组合和Web服务组合验证进行了深入的研究,提出了有效的解决方案,对于推进Web服务组合技术的理论研究和应用具有一定的价值。
With the rapid development of Web service technology, more and more stable and ease-to-use Web services are shared on the Internet. But the function of a single Web service is simple, it can not meet the actual needs of users in many cases.In order to utilize the shared Web services more fully, it is necessary to combine these Web services together so that these Web services can provide more powerful functions and meet the actual needs of users. Verification of Web service composition can find existed defects in Web service composition in advance. It is a key to improve the success rate of execution of Web service composition and to enhance the user's satisfaction degree, and it has very important significance to the correct operation of Web service composition. The major works are as follows:
1. Proposing a Web service composition method based on AND/OR graph. It includes two steps. First, according to the existing Web services available and the user's service request, generating the service parameter AND/OR graph from the output object of service request to input object of service request reversely. Then searching for the service composition graph which can meet the service request in the AND/OR graph. This method can improve the efficiency and success rate of service composition.
2. Proposing a method which uses Pi calculus to verify the correctness of Web service composition. First using the Pi calculus to model Web service compostion, then verifying the service composition method whether it exists deadlocks and can meet user's needs or not.
3. Using Pi calculus to verify if a service can be substituted by another service. At first using Pi calculus to model the new compositional service after service substitution. Determining the feasibility of the service substitution according to whether the new service composition is compatible.
In this paper, Web service composition and Web service composition verification are conducted in-depth research and effective solutions are put forward, which have certain meaning for promoting theory research and application of Web service composition.
1.提出一种基于与或图的Web服务组合方法。该组合方法可分为两个步骤,首先根据已有可用的Web服务和用户提出的服务请求,从服务请求的输出对象到输入对象反向生成服务参数与或图。然后在与或图中搜索能够满足服务请求的服务组合图,该方法可以提高服务组合的效率和成功率。
2.提出一种利用Pi演算对Web服务组合的正确性进行验证的方法。先用Pi演算对Web服务组合进行建模,然后在Pi演算辅助工具MWB中验证该服务组合方案是否存在死锁和是否满足用户需求。
3.利用Pi演算对Web服务组合中一个服务是否可以被另一个服务替换进行验证。先用Pi演算对进行服务替换后新的组合服务进行建模,并根据新的组合服务是否兼容来判断该服务替换的可行性。
本文对Web服务组合和Web服务组合验证进行了深入的研究,提出了有效的解决方案,对于推进Web服务组合技术的理论研究和应用具有一定的价值。
With the rapid development of Web service technology, more and more stable and ease-to-use Web services are shared on the Internet. But the function of a single Web service is simple, it can not meet the actual needs of users in many cases.In order to utilize the shared Web services more fully, it is necessary to combine these Web services together so that these Web services can provide more powerful functions and meet the actual needs of users. Verification of Web service composition can find existed defects in Web service composition in advance. It is a key to improve the success rate of execution of Web service composition and to enhance the user's satisfaction degree, and it has very important significance to the correct operation of Web service composition. The major works are as follows:
1. Proposing a Web service composition method based on AND/OR graph. It includes two steps. First, according to the existing Web services available and the user's service request, generating the service parameter AND/OR graph from the output object of service request to input object of service request reversely. Then searching for the service composition graph which can meet the service request in the AND/OR graph. This method can improve the efficiency and success rate of service composition.
2. Proposing a method which uses Pi calculus to verify the correctness of Web service composition. First using the Pi calculus to model Web service compostion, then verifying the service composition method whether it exists deadlocks and can meet user's needs or not.
3. Using Pi calculus to verify if a service can be substituted by another service. At first using Pi calculus to model the new compositional service after service substitution. Determining the feasibility of the service substitution according to whether the new service composition is compatible.
In this paper, Web service composition and Web service composition verification are conducted in-depth research and effective solutions are put forward, which have certain meaning for promoting theory research and application of Web service composition.
引文
[1]Chung, Jen-Yao, An industry view on service-oriented architecture and web services, In Proceedings-SOSE 2005:IEEE International Workshop on Service-Oriented System Engineering,2005.59
[2]龚玲,张云涛.Web服务原理和技术.北京：机械工业出版社,2010.6
[3]Berners-Lee T, James Hendler, Ora Lassila.The Semantic Web, Scientific American, 2001
[4]邓水光,吴朝晖.Web服务组合方法综述.中国科技论文在线,2008,3(2)：79-84
[5]Sirin E,Parsia B,Wu D,et al. HTN Planning for Web Service Composition Using SHOP2. Journal of Web Semantics,2004,1(4):377-396
[6]McIlraith S,Son T.Adapting Golog for Composition of Semantic Web Services Foster H.Proc.of the Eighth International Conference on Knowledge Representation and Reasoning.San Francisco:Morgan Kaufmann publishers,2002.482-493
[7]李曼,王大治,杜小勇,等.基于领域本体的Web服务动态组合.计算机学报,2005,28(4)：644-650
[8]邓水光,吴健,李莹,等.基于回溯树的Web服务自动组合.软件学报,2007,18(8)：1896-1910
[9]邹金安,杨艳萍.图在自动Web服务组合中的应用研究.小型微型计算机系统,2008,29(11):2020-2026
[10]Qianhui Althea Liang, Stanley Y.W. Su. AND/OR graph and search algorithm for discovering composite web services. International Journal of Web Services Research,2005.48-68
[11]Li Ying. A Method of Automatic Web Services Composition Based on Directed Graph. In:2010 International Conference on Communications and Mobile Computing. 2010.527-531
[12]张佩云,黄波,孙亚民.基于Petri网的Web服务组合模型描述和验证.系统仿真学报,2007,19(12)：2872-2876
[13]罗楠,严隽薇,刘敏.一种基于有色Petri网的语义Web服务组合验证机制.计算机集成制造系统,2007,13(11)：2203-2210
[14]陈丁剑,吴健,马满福,等.基于Petri网的Web服务组合建模.计算机科学,2006,33(5)：128-135
[15]闫春钢,蒋昌俊,李启炎.基于Petri网的Web服务组合与分析.计算机科学, 2007,34(2):100-103
[16]Haiqiang Dun, Haiying Xu, Lifu Wang. Transformation of BPEL Precesses to Petri Nets. International Symposium on Theoretical Aspects of Software Engineering,2008.
[17]Haiqiang Dun,Wen Zhao, Yu Huang. Modeling and Analysis of WS-BPEL Business Processes Based on ServiceNet*.15th Asia-Pacific Software Engineering Conference.2008.265-272
[18]于守健,李卫民,吴国文,等.BPEL中基于有限状态自动机的Web服务自动组合.小型微型计算机系统，2007,28(4):742-747
[19]L.Lei,Z.Dun. An Extended Deterministic Finite Automata Based Method for the Verification of Composite web Services. Journal of Software,2007,18(12):2980-2990
[20]H. Foster, S. Uchitel, J. Magee, J. Kramer. Compatibility Verification for Web Service Choreography. IEEE International Conference on Web Services.2004.738-741
[21]廖军,谭浩,刘锦德.基于Pi-演算的Web服务组合的描述和验证.计算机学报,2005,28(4)：635-643
[22]康辉,苑森淼,浦洁,等.基于Pi演算的Web服务建模与WSDL转换.北京工业大学学报,2008,34(11)：1202-1206
[23]辜希武,卢正鼎.基于Pi-演算的BPEL4WS Web服务组合形式化模型.计算机科学,2007,34(3)：69-74
[24]卢锦运,张为群.一种基于与或图的语义Web服务自动组合研究.计算机科学,2010,37(3)：188-190
[25]W3C Working Draft. Web Service Architecture. http://www.w3.org/TR/ws-arch/.14 November 2002
[26]袁金平,姚莉,鲍爱华,等.一种基于主体的语义Web服务模型.计算机科学,2009,36(6)：171-177
[27]W3C.Extensible Markup Language(XML) 1.0. http://www.w3.org/TR/xml/.
[28]W3C. Simple Object Access Protocol (SOAP) 1.1. http://www.w3.org/TR/SOAP/
,2001.
[29]胡方霞,曾一,高旻. Web Services技术应用与探讨.计算机科学,2007,34(3)：75-77
[30]OASIS UDDI Spec TC. http://www.uddi.org/pubs/uddi_v3.htm.20041019
[31]岳昆,王晓玲,周傲英.Web服务核心支撑技术：研究综述.软件学报2004,15(3)：428-442
[32]David Martin, Mark Bursten. OWL-S:Semantic Markup for Web Services. http://www.Daml.org/services/owl-s/1.1/overview/2004
[33]张佩云,孙亚民.动态Web服务组合研究.计算机科学,2007,34(5)：4-7
[34]Gu Xiwu, Lu Zhengding. A Formal Model for BPEL4WS Description of Web Service Composion. Wuhan University Journal of Natural Sciences,2006.1311-1319
[35]冯名正.Web服务组合研究综述.计算机应用与软件,2007,24(2)：23-27
[36]J.Yang, W.J.van den Jeuvel, M.P.Papazoglon. Tacking the Challenges of Service Composition in e-Marketplaces. In proceedings of Research Issues in Data Engineering. February 2002, San Jose,USA.
[37]Hoare C A R. Communicating Sequential Processes. New York:Prentice Hall,2004
[38]Nilner R. Communication and Concurrency. New York:Prentice Hall,1989
[39]Milner R. Communicating and Mobile Systems:The Pi Calculus. Cambridge:Cambridge University Press,1999
[40]R.Milner, Y. Parrow, D.Walker.A calculus of mobile processes Part I and11, Information and omputation.1992.1-77
[41]邓水光.Web服务自动组合与形式化验证的研究：[博士学位论文].杭州：浙江大学,2007
[42]Ying Li,Baotian Dong. An Algorithm for Semantic Web Services Compostion Based on Output and Input Matching. In:IFIP International Federation for Information Processing, Volume 252, Integration and Innovation Orient to E-Society Volume2,Boston:Springer,2007.297-307
[43]Yixin Yan,Bin Xu,Zhifeng Gu. Automatic Service Composition Using AND/OR graph. In:10th IEEE Conference on E-Commerce Technology and the Fifth IEEE Conference on Enterprise Computing, E-Commerce and E-Services.2008.335-338
[44]叶恒舟,罗晓娟,牛秦洲.基于与或图的Web服务自动组合.计算机工程与设计,2010,31(11)：2645-2653
[45]刘家茂,顾宁,施伯乐.基于Mediator的Web Services无回溯反向链动态合成.计算机研究与发展,2005,42(7)：1153-1158
[46]Snehal Thakkar, Craig A, Knoblock, et al. A view integration approach to dynamic composition of Web services.2003 ICAPS Workshop on Planning for Web services, Trento, Italy,2003
[47]程永上,王志坚.语义Web服务组合的形式化描述与验证研究.计算机科学,2008,35(4)：40-43
[48]郭小群,郝克刚.Web服务的Pi演算描述.计算机科学,2006,33(3)：261-262
[49]Pierce,B.C., "Programming in the Pi-Calculus:An Experiment in Programming Language Design." Lecture notes for a course at the LFCS, University of Edinburgh. 1994
[50]Victor B, Moller F. The Mobility Workbench-A Tool for the Pi-Calculus,In: Proceedings of the 6th International Conference on Computer Aided Verification.USA,1994
[51]Bjorn Victor. The Mobility Workbench User's Guide Polyadic version 3.122.1995
[52]Yong-Lian Wang, Xue-Li Yu. Formalization and Verification of Automatic Composition Based on Pi-Calculus for Semantic Web Service.2009 Second International Symposium on Knowledge Acquisition and Modeling.2009.103-106
[53]Salaun G, Bordeaux L, Schaerf M. Describing and reasoning on Web services using process algebra. In:Proceedings of the 2nd IEEE International Conference on Web Services, San Diego, California, USA,2004
[54]廖军.面向服务的计算(SOC)中服务组合的研究：[博士学位论文].成都：电子科技大学,2006
[55]廖军,谭浩,刘锦德.基于Pi-演算的Web服务可替换性验证.华中科技大学学报,2005：168-171
[56]李喜彤,范玉顺.Web服务流程相容性和相似性分析.计算机学报,2009,32(12)：2429-2437
[57]刘方方,史玉良,张亮,等.基于进程代数的Web服务合成的替换分析.计算机学报,2007,30(11)：2033-2039
[58]贾志淳,陈荣,张维石.航空订票业务的Web服务建模及组合兼容性验证.计算机工程与应用,2010,46(24)：237-242
[59]喻坚,韩燕波.面向服务的计算——原理和应用.北京：清华大学出版社,2006.204
[60]Tim Berners-Lee. http://www.w3.org/2000/Talks/1206-xml2k-tbl/slide10-0.html
[61]T. Berners-Lee, R.Fielding, L.Masinter. "Uniform Resource Identifiers (URI): Generic Syntax". RFC2396, Internet Engineering Task Force, August 1998. http://www.ietf.org/rfc/rfc2396.txt
[62]Wu Chongyun,Wen Jun. Semantic Web Services Composition Model Based On Domain Ontology Cost Graph. In:2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing.2009.175-178
[2]龚玲,张云涛.Web服务原理和技术.北京：机械工业出版社,2010.6
[3]Berners-Lee T, James Hendler, Ora Lassila.The Semantic Web, Scientific American, 2001
[4]邓水光,吴朝晖.Web服务组合方法综述.中国科技论文在线,2008,3(2)：79-84
[5]Sirin E,Parsia B,Wu D,et al. HTN Planning for Web Service Composition Using SHOP2. Journal of Web Semantics,2004,1(4):377-396
[6]McIlraith S,Son T.Adapting Golog for Composition of Semantic Web Services Foster H.Proc.of the Eighth International Conference on Knowledge Representation and Reasoning.San Francisco:Morgan Kaufmann publishers,2002.482-493
[7]李曼,王大治,杜小勇,等.基于领域本体的Web服务动态组合.计算机学报,2005,28(4)：644-650
[8]邓水光,吴健,李莹,等.基于回溯树的Web服务自动组合.软件学报,2007,18(8)：1896-1910
[9]邹金安,杨艳萍.图在自动Web服务组合中的应用研究.小型微型计算机系统,2008,29(11):2020-2026
[10]Qianhui Althea Liang, Stanley Y.W. Su. AND/OR graph and search algorithm for discovering composite web services. International Journal of Web Services Research,2005.48-68
[11]Li Ying. A Method of Automatic Web Services Composition Based on Directed Graph. In:2010 International Conference on Communications and Mobile Computing. 2010.527-531
[12]张佩云,黄波,孙亚民.基于Petri网的Web服务组合模型描述和验证.系统仿真学报,2007,19(12)：2872-2876
[13]罗楠,严隽薇,刘敏.一种基于有色Petri网的语义Web服务组合验证机制.计算机集成制造系统,2007,13(11)：2203-2210
[14]陈丁剑,吴健,马满福,等.基于Petri网的Web服务组合建模.计算机科学,2006,33(5)：128-135
[15]闫春钢,蒋昌俊,李启炎.基于Petri网的Web服务组合与分析.计算机科学, 2007,34(2):100-103
[16]Haiqiang Dun, Haiying Xu, Lifu Wang. Transformation of BPEL Precesses to Petri Nets. International Symposium on Theoretical Aspects of Software Engineering,2008.
[17]Haiqiang Dun,Wen Zhao, Yu Huang. Modeling and Analysis of WS-BPEL Business Processes Based on ServiceNet*.15th Asia-Pacific Software Engineering Conference.2008.265-272
[18]于守健,李卫民,吴国文,等.BPEL中基于有限状态自动机的Web服务自动组合.小型微型计算机系统，2007,28(4):742-747
[19]L.Lei,Z.Dun. An Extended Deterministic Finite Automata Based Method for the Verification of Composite web Services. Journal of Software,2007,18(12):2980-2990
[20]H. Foster, S. Uchitel, J. Magee, J. Kramer. Compatibility Verification for Web Service Choreography. IEEE International Conference on Web Services.2004.738-741
[21]廖军,谭浩,刘锦德.基于Pi-演算的Web服务组合的描述和验证.计算机学报,2005,28(4)：635-643
[22]康辉,苑森淼,浦洁,等.基于Pi演算的Web服务建模与WSDL转换.北京工业大学学报,2008,34(11)：1202-1206
[23]辜希武,卢正鼎.基于Pi-演算的BPEL4WS Web服务组合形式化模型.计算机科学,2007,34(3)：69-74
[24]卢锦运,张为群.一种基于与或图的语义Web服务自动组合研究.计算机科学,2010,37(3)：188-190
[25]W3C Working Draft. Web Service Architecture. http://www.w3.org/TR/ws-arch/.14 November 2002
[26]袁金平,姚莉,鲍爱华,等.一种基于主体的语义Web服务模型.计算机科学,2009,36(6)：171-177
[27]W3C.Extensible Markup Language(XML) 1.0. http://www.w3.org/TR/xml/.
[28]W3C. Simple Object Access Protocol (SOAP) 1.1. http://www.w3.org/TR/SOAP/
,2001.
[29]胡方霞,曾一,高旻. Web Services技术应用与探讨.计算机科学,2007,34(3)：75-77
[30]OASIS UDDI Spec TC. http://www.uddi.org/pubs/uddi_v3.htm.20041019
[31]岳昆,王晓玲,周傲英.Web服务核心支撑技术：研究综述.软件学报2004,15(3)：428-442
[32]David Martin, Mark Bursten. OWL-S:Semantic Markup for Web Services. http://www.Daml.org/services/owl-s/1.1/overview/2004
[33]张佩云,孙亚民.动态Web服务组合研究.计算机科学,2007,34(5)：4-7
[34]Gu Xiwu, Lu Zhengding. A Formal Model for BPEL4WS Description of Web Service Composion. Wuhan University Journal of Natural Sciences,2006.1311-1319
[35]冯名正.Web服务组合研究综述.计算机应用与软件,2007,24(2)：23-27
[36]J.Yang, W.J.van den Jeuvel, M.P.Papazoglon. Tacking the Challenges of Service Composition in e-Marketplaces. In proceedings of Research Issues in Data Engineering. February 2002, San Jose,USA.
[37]Hoare C A R. Communicating Sequential Processes. New York:Prentice Hall,2004
[38]Nilner R. Communication and Concurrency. New York:Prentice Hall,1989
[39]Milner R. Communicating and Mobile Systems:The Pi Calculus. Cambridge:Cambridge University Press,1999
[40]R.Milner, Y. Parrow, D.Walker.A calculus of mobile processes Part I and11, Information and omputation.1992.1-77
[41]邓水光.Web服务自动组合与形式化验证的研究：[博士学位论文].杭州：浙江大学,2007
[42]Ying Li,Baotian Dong. An Algorithm for Semantic Web Services Compostion Based on Output and Input Matching. In:IFIP International Federation for Information Processing, Volume 252, Integration and Innovation Orient to E-Society Volume2,Boston:Springer,2007.297-307
[43]Yixin Yan,Bin Xu,Zhifeng Gu. Automatic Service Composition Using AND/OR graph. In:10th IEEE Conference on E-Commerce Technology and the Fifth IEEE Conference on Enterprise Computing, E-Commerce and E-Services.2008.335-338
[44]叶恒舟,罗晓娟,牛秦洲.基于与或图的Web服务自动组合.计算机工程与设计,2010,31(11)：2645-2653
[45]刘家茂,顾宁,施伯乐.基于Mediator的Web Services无回溯反向链动态合成.计算机研究与发展,2005,42(7)：1153-1158
[46]Snehal Thakkar, Craig A, Knoblock, et al. A view integration approach to dynamic composition of Web services.2003 ICAPS Workshop on Planning for Web services, Trento, Italy,2003
[47]程永上,王志坚.语义Web服务组合的形式化描述与验证研究.计算机科学,2008,35(4)：40-43
[48]郭小群,郝克刚.Web服务的Pi演算描述.计算机科学,2006,33(3)：261-262
[49]Pierce,B.C., "Programming in the Pi-Calculus:An Experiment in Programming Language Design." Lecture notes for a course at the LFCS, University of Edinburgh. 1994
[50]Victor B, Moller F. The Mobility Workbench-A Tool for the Pi-Calculus,In: Proceedings of the 6th International Conference on Computer Aided Verification.USA,1994
[51]Bjorn Victor. The Mobility Workbench User's Guide Polyadic version 3.122.1995
[52]Yong-Lian Wang, Xue-Li Yu. Formalization and Verification of Automatic Composition Based on Pi-Calculus for Semantic Web Service.2009 Second International Symposium on Knowledge Acquisition and Modeling.2009.103-106
[53]Salaun G, Bordeaux L, Schaerf M. Describing and reasoning on Web services using process algebra. In:Proceedings of the 2nd IEEE International Conference on Web Services, San Diego, California, USA,2004
[54]廖军.面向服务的计算(SOC)中服务组合的研究：[博士学位论文].成都：电子科技大学,2006
[55]廖军,谭浩,刘锦德.基于Pi-演算的Web服务可替换性验证.华中科技大学学报,2005：168-171
[56]李喜彤,范玉顺.Web服务流程相容性和相似性分析.计算机学报,2009,32(12)：2429-2437
[57]刘方方,史玉良,张亮,等.基于进程代数的Web服务合成的替换分析.计算机学报,2007,30(11)：2033-2039
[58]贾志淳,陈荣,张维石.航空订票业务的Web服务建模及组合兼容性验证.计算机工程与应用,2010,46(24)：237-242
[59]喻坚,韩燕波.面向服务的计算——原理和应用.北京：清华大学出版社,2006.204
[60]Tim Berners-Lee. http://www.w3.org/2000/Talks/1206-xml2k-tbl/slide10-0.html
[61]T. Berners-Lee, R.Fielding, L.Masinter. "Uniform Resource Identifiers (URI): Generic Syntax". RFC2396, Internet Engineering Task Force, August 1998. http://www.ietf.org/rfc/rfc2396.txt
[62]Wu Chongyun,Wen Jun. Semantic Web Services Composition Model Based On Domain Ontology Cost Graph. In:2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing.2009.175-178