Process-context aware matchmaking for web service composition

Web service composition can help software developer design more powerful and flexible applications according to requirements of enterprise. But during compositing, how to discover suitable web services is a critical problem in design and implementing application-oriented web service technologies. The traditional keyword-based matchmaking approach is difficult to help developer to find suitable service. Current researches find that to attaching semantics to each registered service can help improve the precision of matchmaking. The improvement can help developer find more suitable service for business process. This paper proposes a novel approach of semantics-based matchmaking, which is named process-context aware matchmaking. The process-context aware matchmaking discovers the suitable service during web service composite modeling. During matchmaking, the approach utilizes not only semantics of technical process but also that of business process of a registered service, thus further improving the precision of matchmaking. We integrate the process-context aware matchmaking with business-process-driven web service composition in an integrated development environment based on Eclipse. The performance evaluation shows that performance overhead of this novel approach is acceptable.     

Semantic web service composition testbed

A huge amount of web services are deployed on the Web, nowadays. These services can be used to fulfill online requests. Requests are getting more and more complicated over time. So, there exists a lot of frequent request that cannot be fulfilled using just one web service. For using web services, composing individual services to create the added-value composite web service to fulfill the user request is necessary in most cases. Web services can be composed manually but it is a too tedious and time consuming task. The ability of automatic web service composition to create a new composite web service is one of the key enabling features for the future for the semantic web. There are some successful methods for automatic web service composition, but the lack of standard, open, and lightweight test environment makes the comparison and evaluation of these composition methods impossible. In this paper we propose an architecture for a light weight and scalable testbed to execute, test and evaluate automatic web service composition algorithms. The architecture provides mandatory components for implementing and evaluation of automatic web service composition algorithms. Also, this architecture provides some extension mechanisms to extend its default functionalities. We have also given reference implementations for web service matchmaking and composition. Also, some scenarios for testing and evaluating the testbed are given. We have found that the performance of the composition method will dramatically decrease as the number of web services increases.     

Quality-of-service oriented web service composition algorithm and planning architecture

In the next few decades, it is expected that web services will proliferate, many web services will offer the same services, and the clients will demand more value added and informative services rather than those offered by single, isolated web services. As the result, the problem of synthesizing web services of high quality will be raised as a prominent issue. The clients will face the trouble of choosing or creating composition plans, among numerous possible plans, that satisfy their quality-of-service (QoS) requirements. Typical QoS properties associated with a web service are the execution cost and time, availability, successful execution rate, reputation, and usage frequency. In engineering perspective, generating the composition plan that fulfills a client’s QoS requirement is a time-consuming optimization problem. To resolve the problem in a timely manner, we propose a constraint satisfaction based web service composition algorithm that combines tabu search and simulated annealing meta-heuristics. As an implementation framework of the algorithm, we suggest a QoS-oriented web service composition planning architecture. The architecture maintains expert made composition schemas in a service category and assists the client as pure user to choose the one he/she wants to use. The main modules of the architecture are composition broker and execution plan optimizer. With the aid of the UDDI server, the composition broker discovers candidate outsourced web services for each atomic process of the selected schema and gathers QoS information on the web services. After that, the execution plan optimizer runs the web service composition algorithm in order to generate a QoS-oriented composition plan. The performance of the algorithm was tested in a simulated environment.     

基于语义的动态服务组合的改进

Web服务应用已经广泛深入,而已存在的服务也越来越不满足客户的需求,解决应用服务之间的共享和应用协作问题成为关键.基于语义的Web服务的动态组合无疑可以很好的解决这个问题,但是OWL-S还有许多方面需要完善特别是在服务质量、花费、可靠性等问题上.本论文通过对OWL-S的扩充解决了其中部分问题,并且通过描述并实现一个动态服务组合框架来验证.     

On the computational complexity of qualitative coalitional games

We study coalitional games in which agents are each assumed to have a goal to be achieved, and where the characteristic property of a coalition is a set of choices, with each choice denoting a set of goals that would be achieved if the choice was made. Such qualitative coalitional games (qcgs) are a natural tool for modelling goal-oriented multiagent systems. After introducing and formally defining qcgs, we systematically formulate fourteen natural decision problems associated with them, and determine the computational complexity of these problems. For example, we formulate a notion of coalitional stability inspired by that of the core from conventional coalitional games, and prove that the problem of showing that the core of a qcg is non-empty is D^p₁-complete. (As an aside, we present what we believe is the first “natural” problem that is proven to be complete for D^p₂.) We conclude by discussing the relationship of our work to other research on coalitional reasoning in multiagent systems, and present some avenues for future research.     

On the computational complexity of coalitional resource games

We study Coalitional Resource Games (crgs), a variation of Qualitative Coalitional Games (qcgs) in which each agent is endowed with a set of resources, and the ability of a coalition to bring about a set of goals depends on whether they are collectively endowed with the necessary resources. We investigate and classify the computational complexity of a number of natural decision problems for crgs, over and above those previously investigated for qcgs in general. For example, we show that the complexity of determining whether conflict is inevitable between two coalitions with respect to some stated resource bound (i.e., a limit value for every resource) is co-np-complete. We then investigate the relationship between crgs and qcgs, and in particular the extent to which it is possible to translate between the two models. We first characterise the complexity of determining equivalence between crgs and qcgs. We then show that it is always possible to translate any given crg into a succinct equivalent qcg, and that it is not always possible to translate a qcg into an equivalent crg; we establish some necessary and some sufficient conditions for a translation from qcgs to crgs to be possible, and show that even where an equivalent crg exists, it may have size exponential in the number of goals and agents of its source qcg.     

On computational complexity of impossible differential cryptanalysis

Impossible differential cryptanalysis is one of the conventional methods in the field of cryptanalysis of block ciphers. In this paper, a general model of an impossible differential attack is introduced. Then, according to this model, the concept of an ideal impossible differential attack is defined and it is proven that the time complexity of an ideal attack only depends on the number of involved round key bits in the attack.     

基于行为投影的Web服务组合行为兼容性研究

Web服务兼容性是确保组合系统能够正常运行的前提。首先提出既包含服务接口调用方法又包含逻辑行为的服务视图,根据服务间的连接关系,将服务行为投影到不同的连接件上。其次根据在连接件上的消息收发关系,将两个服务在该连接上的交互过程表示为两个LTS投影间同步变迁,通过同步积模拟在该连接上的交互行为,检查同步积中是否出现死锁状态来进行行为兼容性判定,并设计了判定算法以实现兼容性的自动分析,最后通过一个电子商务应用示例说明该方法有效性。     

基于邻接矩阵的Web服务组合

针对当前Web服务组合方法在动态性和算法时间复杂度方面存在的不足,提出一种基于邻接矩阵的服务组合方法,使用邻接矩阵表示服务间的顺序及并发关系,在构建抽象服务基础上由领域专家初步建立抽象服务的组合关系,利用Warshall算法计算传递闭包来判定服务请求是否可满足,同时构建动态服务组合流程。方法操作简单,Warshall算法时间复杂度为O(n3),在服务组合中有较好的实用性。     

基于服务上下文的Web服务发现机制

服务发现成为Web服务组合研究的重点,为解决服务组合过程中服务发现方法存在动态适应能力不足,提出了一种基于服务上下文的Web服务发现机制.该机制将一种服务本体描述语言OWL-S和一种基于服务上下文的服务发现算法相结合,利用语义描述服务的信息,同时定义了服务上下文信息并进行服务上下文匹配来发现所需服务.实验结果表明,基于服务上下文的Web服务发现机制能够提高服务发现的准确性,具有较好地动态适应性.     

基于聚类Web服务的组合服务模式规约*

Web服务组合是提高服务质量的实用方法,但如何实施有效的服务组合一直是研究的难点。基于此,提出了一种通过建立组合服务模式规约来验证服务组合有效性的方法。依据经过聚类后各个类别服务间的关联性关系分析,首先提出组合服务模式的概念和确定其方法、原则;然后给出Web服务中组合服务模式规约;最后通过使用组合服务模式规约,应用飞机订票的实验验证了Web服务组合的有效性。     

一种快速易用的基于行为描述的服务组合方法*

为了提高基于行为描述的服务组合方法的易用性和效率,首先对服务和服务请求进行建模;然后使用一个三层图模型组织服务之间的关系,并基于这个三层图模型提出一种快速易用的服务组合方法;最后通过实例说明了该方法的组合过程,并从理论上分析了该方法的时间复杂度。理论分析显示该方法具有较好的效率。     

分布式Web服务合成的恢复机制

Web服务合成已成为一种重要的分布式网络应用开发模式。网络应用要求Web服务具有较高的可用性,进而要求Web服务必须具有快速恢复的特点。基于分布式Web服务合成的模式开发合成服务的恢复机制适合网络环境下的服务交互方式。分布式Web服务合成模式中包含有一个中心合成引擎和若干本地合成引擎,恢复机制由中心合成引擎与本地合成引擎合作实现,确保了唯一执行语义,同时又可保持Web服务的特性,并降低I/O代价。     

分布式资源的Web服务组合机制

单个资源的服务往往不能满足任务需求,而多个服务的组合却可以派生出新的服务。为此,模拟迷宫求解的思路,设计了一套通用服务组合算法,将分布式资源提供的可用服务看作为迷宫中的条条道路,而将服务组合方案看作为连接迷宫入口和出口的一条通路,通过服务与服务、服务与需求之间的功能性关联,自动生成满足任务需求的服务组合方案。模拟实验验证了方法的有效性。     

Dynamic web service composition based on OWL-S

Composing existing web services for enterprise applications may enable higher level of reuse. However the composition processes are mostly static and lack of support for runtime redesign. In this paper, we describe our approach to the extension of the OWL-S ontology framework for dynamic web service composition. We raise the level of abstraction and propose an abstract service layer so that web services can be com- posed at the abstract service level instead of the concrete level. Each abstract service is attached with an instance pool including all instances of the abstract service to facilitate fail-over and dynamic compositions.