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

摘要

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