求解Web服务组合QoS优化的多属性决策及自适应遗传算法

随着面向服务计算(Service-oriented Computing,SOC)的不断发展,基于服务质量(Quality of Service,QoS)的Web服务组合研究成为了必然趋势。鉴于QoS属性的多维性及相互矛盾性,提出将基于QoS的Web服务组合优化问题转化为多属性决策问题进行求解。采用折中系数 对每个组合服务实例到正负理想点的距离进行累加求和,最终得到一组最优服务排序结果,用户可以根据自身偏好进行选择。传统的多属性决策方法无法有效地处理大规模的组合服务搜索空间,因此,为了有效地解决Web服务组合优化这一NP难题,提出一种结合多属性决策方法和自适应遗传算法的新型优化算法来解决该问题。实验采用真实的QoS综合服务数据集进行验证,实验结果表明,该方法能够在较短时间内找到全局近似最优解,且解集的排序结果接近于实际的最优服务排序。同时,该方法对于解决大规模的Web服务组合优化问题具有良好的可伸缩性。     

事件驱动的动态服务组合策略在线自适应优化

针对复杂应用环境中网络新媒体服务系统的特点,提出一种事件驱动的动态服务组合策略及其在线优化算法,在保证各类业务服务质量（QoS）的同时,提高系统资源的利用率．通过定义不同类型的事件,驱动服务组合的动态调整,实现对各类业务Qos的保障和对业务需求变化的感知．构建基于半Markov切换空间控制过程的系统分析模型,利用模型的动态结构特点,提出一种结合随机逼近和策略迭代的在线优化算法．该算法不依赖系统参数信息,对环境具有良好的自适应性．仿真实验结果验证了算法的有效性．     

Multi-objective service composition model based on cost-effective optimization

The widespread application of cloud computing results in the exuberant growth of services with the same functionality. Quality of service (QoS) is mostly applied to represent nonfunctional properties of services, and has become an important basis for service selection. The object of most existing optimization methods is to maximize the QoS, which restricts the diversity of users’ requirements. In this paper, instead of optimization for the single object, we take maximization of QoS and minimization of cost as two objects, and a novel multi-objective service composition model based on cost-effective optimization is designed according to the complicated QoS requirements of users. Furthermore, to solve this complex optimization problem, the Elite-guided Multi-objective Artificial Bee Colony (EMOABC) algorithm is proposed from the addition of fast nondominated sorting method, population selection strategy, elite-guided discrete solution generation strategy and multi-objective fitness calculation method into the original ABC algorithm. The experiments on two datasets demonstrate that EMOABC has an advantage both on the quality of solution and efficiency as compared to other algorithms. Therefore, the proposed method can be better applicable to the cloud services selection and composition.     

基于改进磷虾群算法的服务组合优化

面向服务的架构（SOA）下,针对服务组合优化过程中易陷入局部最优、时间开销大的问题,提出一种加入自适应交叉算子和随机扰动算子的改进磷虾群算法PRKH。首先基于服务质量（QoS）建立了服务组合优化模型,并给出不同结构下QoS的计算公式和归一化处理方法。然后在磷虾群（KH）算法的基础上加入自适应的交叉概率和基于实际偏移量的随机扰动,从而在磷虾群的全局搜索能力和局部搜索能力之间达到良好平衡。最后通过仿真,把所提算法与KH算法、粒子群优化（PSO）算法、人工蜂群（ABC）算法和花朵授粉算法（FPA）进行对比,实验结果表明,PRKH算法能够更快找到QoS更优的复合服务。     

GACRM: A dynamic multi-Attribute decision making approach to large-Scale Web service composition

The problem of QoS-aware Web service composition (QWSC), i.e., how to select from a pool of candidate services to construct a composite service with the best overall QoS performance, is an NP-hard problem. To address a large-scale QWSC problem, a novel method is proposed based on information theory, multi-attribute decision making (MADM) and genetic algorithm. To capture complex judgments, the QWSC problem is formulated into a MADM representation which aims to find acceptable solutions assessed by multiple QoS attributes with varying distributions. To solve the MADM problem for QWSC, each QoS attribute is weighted in both a priori, subjective perspective and a posteriori, information-based perspective based on the discriminative capability of QoS attributes for a dynamic pool of candidate services. Furthermore, to solve the large-scale QWSC problem that conventional MADM methods cannot navigate, we develop a GACRM algorithm by integrating genetic algorithm (GA) with Compromise Ratio Method (CRM). Experiments demonstrate that GACRM obtains nearly the same solution ranking by the CRM but scales much better in terms of computation time for large-scale QWSC problems.     

一种高效的服务组合优化算法

随着功能性属性相同而非功能性属性各异的Web服务的大量涌现,如何在服务组合业务流程中为各个任务选择相应的组件服务以达到组合服务的QoS(quality of service)最大化,并在此基础上满足不同用户的需求,已成为了国内外研究的热点.由于该问题的复杂性(NP-hard),目前存在的大多数方法都并不十分适合需要相对精确、实时决策的Web服务组合系统.因此,本文提出了一种基于凸包构建的组合服务优化算法(CM-HEU)用以解决QoS感知的服务组合优化问题.CM-HEU首先通过对组合服务中的每组任务进行凸包构建,以减少搜索空间.然后通过对初始解向量的多次升级和一次降级操作以达到全局优化的目标.实验表明:相对于现阶段存在的一些主流方法,CM-HEU不仅能得到一个比较理想的结果,并且具有良好的效率.     

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.     

A new QoS ontology and its QoS-based ranking algorithm for Web services

Web service composition is a promising solution for building distributed applications on the Internet in which Web service discovery is a key step. With a number of Web services having similar functionality, it is necessary to rank those services to select the best Web services for a request. QoS information which can reflect user’s expectation and experience of using a service is often used as a distinguish factor in a service ranking algorithm. Different service providers and participants may use different QoS concepts for describing service quality information. Therefore, it leads to the issue of semantic interoperability of QoS. In this paper, we propose a novel approach for designing and developing a QoS ontology and its QoS-based ranking algorithm for evaluating Web services. The QoS ontology can support not only describing QoS information in great detail but also facilitating various service participants expressing their QoS offers and demands at different levels of expectation. The QoS-based ranking algorithm adopted Analytic Hierarchy Process (AHP), a multiple criteria decision making technique, as an underlying mechanism for developing a flexible and dynamic ranking algorithm. The proposed QoS ontology and ranking algorithm can be used in various applications in order to facilitate automatic and dynamic discovery and selection of Web services.     

QoS Requirement Generation and Algorithm Selection for Composite Service Based on Reference Vector

Under SOA (Service-Oriented Architecture), composite service is formed by aggregating multiple component services together in a given workflow. One key criterion of this research topic is QoS composition. Most work on service composition mainly focuses on the algorithms about how to compose services according to assumed QoS, without considering where the required QoS comes from and the selection of user preferred composition algorithm among those with different computational cost and di?erent selection resu...     

一种工作流环境下能耗感知的多路径服务组合方法

当前,服务组合方法只考虑组合服务QoS的优化而不考虑组合服务的能耗优化.针对这一问题,文中首先根据不同情况提出了两种服务能耗模型;其次在基于工作流的服务组合环境下,提出了一种能耗感知的多路径服务组合方法 EAMSC.该方法对服务组合的能耗优化问题进行了数学建模,并提出了一种基于启发式的多路径服务组合算法,该算法包括两个部分:一是组合服务的可行路径查找,即在满足端到端QoS约束的前提下找出若干条可行的服务组合路径;二是请求速率的分配,即在可行的服务组合路径上依据服务能耗模型分配请求流量以降低组合服务的总体能耗.最后,仿真实验结果表明:能耗感知的多路径服务组合方法与传统的服务组合方法相比,能够在保证端到端QoS约束的基础上有效地减少组合服务的总能耗.     

基于可信QoS的路径查找及负载均衡策略研究

Web服务是云计算中资源调用的有效方式。单一Web服务功能往往有限,只能完成特定任务。服务组合则可以将多种Web服务形成有效的调用序列,实现更为强大的功能。服务发布量以及服务请求量的迅速激增带来了新的安全问题。首先,现有的服务组合方案均以服务质量(QoS)为依据进行Web服务选择,但服务质量通常由服务发布者提供,存在服务发布者发布虚假QoS值诱骗用户的欺诈现象;其次,传统的服务组合方案只生成一条最优路径,当恶意请求持续访问时,会造成某服务节点瘫痪,甚至整个服务组合系统失效。因此,针对服务质量恶意欺诈的问题,文章提出一种可信的QoS计算模型,根据Web服务发布者的信用综合评估服务质量;针对单一最优路径无法满足大量请求的问题,文章提出一种路径发现和负载均衡的多路径方法。仿真结果表明,文章提出的方法不仅能提高服务组合的成功率,满足用户的需求,而且能找到更多的服务组合方案执行。     

Hybrid Metaheuristics Web Service Composition Model for QoS Aware Services

Recent advancements in cloud computing (CC) technologies signified that several distinct web services are presently developed and exist at the cloud data centre. Currently, web service composition gains maximum attention among researchers due to its significance in real-time applications. Quality of Service (QoS) aware service composition concerned regarding the election of candidate services with the maximization of the whole QoS. But these models have failed to handle the uncertainties of QoS. The resulting QoS of composite service identified by the clients become unstable and subject to risks of failing composition by end-users. On the other hand, trip planning is an essential technique in supporting digital map services. It aims to determine a set of location based services (LBS) which cover all client intended activities quantified in the query. But the available web service composition solutions do not consider the complicated spatio-temporal features. For resolving this issue, this study develops a new hybridization of the firefly optimization algorithm with fuzzy logic based web service composition model (F3L-WSCM) in a cloud environment for location awareness. The presented F3L-WSCM model involves a discovery module which enables the client to provide a query related to trip planning such as flight booking, hotels, car rentals, etc. At the next stage, the firefly algorithm is applied to generate composition plans to minimize the number of composition plans. Followed by, the fuzzy subtractive clustering (FSC) will select the best composition plan from the available composite plans. Besides, the presented F3L-WSCM model involves four input QoS parameters namely service cost, service availability, service response time, and user rating. An extensive experimental analysis takes place on CloudSim tool and exhibit the superior performance of the presented F3L-WSCM model in terms of accuracy, execution time, and efficiency.     

QoS-aware web services composition using GRASP with Path Relinking

In service oriented scenarios, applications are created by composing atomic services and exposing the resulting added value logic as a service. When several alternative service providers are available for composition, quality of service (QoS) properties such as execution time, cost, or availability are taken into account to make the choice, leading to the creation of QoS-aware composite web services. Finding the set of service providers that result in the best QoS is a NP-hard optimization problem. This paper presents QoS-Gasp, a metaheuristic algorithm for performing QoS-aware web service composition at runtime. QoS-Gasp is an hybrid approach that combines GRASP with Path Relinking. For the evaluation of our approach we compared it with related metaheuristic algorithms found in the literature. Experiments show that when results must be available in seconds, QoS-Gasp improves the results of previous proposals up to 40%. Beside this, QoS-Gasp found better solutions than any of the compared techniques in a 92% of the runs when results must be available in 100 ms; i.e., it provides compositions with a better QoS, implying cost savings, increased availability and reduced execution times for the end-user.     

QoS全局最优的多目标Web服务选择算法*

针对现有方法的不足,提出一种基于QoS全局最优的多目标动态Web服务选择算法。在给出动态服务组合模型的基础上,以“抽象服务规划”为输入,以用户的非功能性需求为全局约束,将动态服务选择问题转换为一个带QoS约束的多目标服务组合优化问题;利用多目标蚁群算法,多个目标函数被同时优化并产生一组满足约束条件的Pareto优化解。通过运用实验与基于多目标遗传算法的Web服务选择算法进行对比,证明了该方法的可行性和有效性。     

基于动态匹配网络的制造服务组合自适应方法

云制造（cloud manufacturing,CMfg）模式下,制造任务和制造服务都处于动态变化的环境中,制造服务组合的动态适应能力问题亟待解决.针对这一问题,以制造任务和制造服务的匹配关系为基础,构建了制造任务-制造服务动态匹配网络（dynamic matching network,DMN）理论模型,在此基础上提出了一种三阶段的制造服务组合自适应方法（three-phase manufacturing service composition self-adaptive approach,TPMSCSAA）.第一阶段通过负载队列模型对QoS进行动态评估,以负载和动态QoS为优化目标,将最优制造服务组合问题转化为制造服务网络中最短路径的搜索,实现制造服务的动态调度;第二阶段对不同类型的制造任务和制造服务变更进行实时获取,同步更新制造任务网络和制造服务网络;第三阶段触发动态调度算法,完成动态匹配边的重构.最后,通过对电梯设计服务组合的实验仿真,验证了方法的可行性和有效性.     

基于禁忌搜索算法的Web服务组合优化

为有效集成网络中的Web服务,组成满足用户需求的服务链,提出了基于禁忌搜索算法的Web服务组合优化方法.建立了基于QoS感知的Web服务组合优化模型,该模型从全局限制了用户的QoS约束.简述了禁忌搜索算法求解的基本框架,在此基础之上分析了应用禁忌搜索算法求解过程中的关键设计步骤.实例仿真计算结果表明,该算法求解具有比线性规划算法更好的时间性能,并具有与遗传算法相仿的表现.     

Functionality Aware Dynamic Composition of Web Services

The composition of the web service is a common technique to attain the best results of complex web tasks. The selection of appropriate web services, linking those services in the action flow and attaining the actual functionality of the task are the important factors to be considered. Even though different frameworks and methods have been proposed to dynamically compose web services, each method has its advantage and disadvantage over the other. Most of the methods give much importance to the Quality of Service (QoS) but fail to achieve the actual functionality after composition. This paper proposes a functionality-oriented composition technique for composing web services. Moreover, this method helps reach the extreme functionality of each web service in the composition towards customer satisfaction. Apart from considering the overall QoS of every single service, the non-functional parameters associated with these services are also considered for achieving the expected functionality. Each of these non-functional parameters has a vital role in the functional performance of the web service. The web services that satisfy the non-functional requirements are chosen to form the composition to attain the best performance. The list of services in the proposed composition method is different from the conventional one, which is composed based on the overall QoS. The non-functional parametric values, the QoS of each web service and the overall QoS after composition are evaluated for the proposed method and experimentally analyzed to prove their advantage over the others.     

Iterative selection algorithm for service composition in distributed environments

In service oriented architecture （SOA）, service composition is a promising way to create new services. However, some technical challenges are hindering the application of service composition. One of the greatest challenges for composite service provider is to select a set of services to instantiate composite service with end- to-end quality of service （QoS） assurance across different autonomous networks and business regions. This paper presents an iterative service selection algorithm for quality driven service composition. The algorithm runs on a peer-to-peer （P2P） service execution environment--distributed intelligent service execution （DISE）, which provides scalable QoS registry, dynamic service selection and service execution services. The most significant feature of our iterative service selection algorithm is that it can work on a centralized QoS registry as well as cross decentralized ones. Network status is an optional factor in our QoS model and selection algorithm. The algorithm iteratively selects services following service execution order, so it can be applied either before service execution or at service run-time without any modification. We test our algorithm with a series of experiments on DISE. Experimental results illustrated its excellent selection and outstanding performance.     

基于图的Web服务组合优化的研究

单个Web服务难以满足实际应用的需求，如何组合已有的服务，形成新的服务，已成为此领域的研究热点。现在的组合方法极少考虑服务质量QoS（Quality of Service）。对于一些提供相似功能的Web服务，服务质量是判断是否选择此服务的关键因素，组合服务的质量必须满足用户的需求。本文基于SOA的服务开发思想，针对当前服务组合存在的问题，提出了一种基于QoS的服务组合方法，并给出了构建基于QoS的Web服务组合及选择最佳服务的策略，通过整合单个服务的质量以得到最终组合服务的整体最佳质量。在满足用户组合服务的功能需求的同时，也满足了用户对服务质量QoS的需求，实现了需求服务的优化。