الگوریتم هیوریستیک جدید برای ترکیب خدمات پایان به پایان کیفیت خدمات

Many works have been carried out to find the efficient algorithms for QoS-aware service composition in recent years. Nevertheless, on one hand, some of these works only consider the local QoS attributes in Web services composition; on the other hand, some ideas derived from QoS selection algorithms for network routing are directly applied in service composition without any adaption. A service composition model with end-to-end QoS constraints has been presented in this paper. An improved heuristics HCE based on the observation of characteristic of end-to-end service composition is proposed as a novel solution. Simulation results reveal the better performance of proposed heuristic compared to the other two heuristics, HMCOP and generic CE algorithm.

Research on Service Oriented Architecture (SOA) and Service Oriented Computing (SOC) brings a promising technique to create value-added business applications composed by dynamically selected individual services. This technology is so called service composition. Nevertheless, the terminology “service composition” not only is used in SOA and SOC in application level, but also appears in autonomic communication system [1] at network level. There are two differences between their functionality attributes. Firstly, the functionalities of services at application level are more abundant than those of services at network level. The services at network level are commonly the communication services, while the services at application level are designed for all kinds of business domain. Secondly, the application level services are loosely-coupled in comparison with the network level services. For example, the autonomous systems at network level share their information and cooperate with each other by Border Gateway Protocol (BGP), while the Web services at application level provide functionality to users independently and communicate with each other by end-to-end message exchange using network protocols. Due to the differences between the functionality attributes of services at the two levels, the non-functionality attributes, which commonly refers to quality of service (QoS), are also different. Without special emphasis, we focus on service composition with end-to-end QoS constraints in this paper, especially the QoS-aware Web service composition, which is not only a problem for local QoS policy guarantee of composite service, but also a optimization procedure for network QoS delivering. QoS-aware Web service composition (QWSC) has drawn much attention in recent years. Some works have been carried out on service selection algorithms for composing services with multiple QoS constraints to find an optimal solution, which is a NP-complete problem [2], [3], [4], [5] and [6]. Zeng et al. suggested solving this problem by Linear Integer Programming (LIP) [2]. Although LIP is an optimal algorithm, its computation time tends to grow exponentially with the size of the problem instance, thus it is limited to use the LIP algorithm in real scenarios, especially in time-critical scenario. And the network constraint is omitted in this paper. Several researchers put forward heuristic algorithms to find a near-optimal solution. Berbner et al. [4] presented an algorithm using the result of linear programming relaxation of LIP as the heuristic hint. The network constraint also is omitted in this paper. Yu et al. [3] and [6] presented a heuristic algorithm, which was developed by [7] and uses the concept named ‘aggregate resource’, to find a near-optimal solution for QWSC. They also consider the network constraints of Web service and propose another heuristic algorithm deriving from [8] named HMCOP to solve the service composition with end-to-end constraints. When the network attribute is considered in QWSC, the computation model becomes Multi-Constraints Optimal Path (MCOP) problem, which cannot be solved by LIP anymore. The MCOP has been studied for QoS guarantee in packet network [8] and QoS-aware service composition in autonomous network communication [1]. As aforementioned, there are some differences between the service composition at network level and the Web service composition. There is a type of heuristic algorithms called meta-heuristics which are adaptive to most of scenarios of combinatorial optimization problem [9], such as the evolutionary computation, tabu search, simulated annealing, ant colony optimization and cross-entropy algorithm. It is widely studied to utilize these meta-heuristics for QWSC [5], [10] and [11]. Nevertheless, most of these works just treated the QWSC as the common combinatorial optimization problem and there is less work adopting special optimization strategy by observing the different characteristics of service composition with end-to-end QoS constraints. In this paper, we firstly introduce the decentralized Web service composition system architecture; according to the system architecture, the computation model and QoS model of QWSC is presented. After that, two efficient heuristics used in QWSC, HMCOP and CE algorithms are studied and on the basis of these two algorithms, an improvement strategy is proposed, which is intuitively derived from the observation of the characteristic of QWSC. The simulation experiments will be conducted to compare these three algorithms and the results will reveal the better performance of proposed strategy than original ones.

In this paper, we developed a novel heuristic algorithm for Web service composition (QWSC) with end-to-end QoS constraints on the basis of the generic cross-entropy algorithm for combinatorial optimization problem and HMCOP algorithm for multi-constraints optimal path (MCOP) find problem. We analyzed the characteristic of QWSC problem, which usually is omitted by other related works, and the properties of generic CE and HMCOP. We argued that the HMCOP can perform well in a specific area of problem, and generic CE has a good scalability but it lacks the adaptive strategy for QWSC. We proposed the heuristic-enhanced cross-entropy algorithm (HCE) for QWSC. This algorithm uses the heuristic from HMCOP to enhance the generic CE and we argue that the HCE should outperform generic CE and HMCOP for it is more adaptive to the QWSC. The theoretical analysis and simulation results can support our arguments. The weighting scheme for evaluating the utility/profit value of composite service in this paper is similar to what is introduced in [2]. This simple additive weighting scheme is easily implemented but is limited in flexibility and diversity at the same time. Research on some more delicate evaluation strategies should be our future work.