【作者】 黄利萍；

【导师】 张斌；

【作者基本信息】 东北大学 ， 计算机应用技术， 2018， 博士

【摘要】 随着服务计算、云计算的快速发展,网络上被部署了大量的服务资源,由于网络服务访问的便利性,越来越多的用户通过网络使用各种各样的服务资源以完成其业务应用。服务资源的快速增长,导致提供相近功能的服务数量日益增多,服务资源访问的频繁性使得服务请求数量在某一时间间隔可能会迅速增大,这使得服务选取问题不仅要考虑功能相近服务的质量,同时要考虑服务质量在大规模请求下的变化。而目前的服务选取问题大都没有考虑大规模请求下服务质量的变化以及对服务选取问题的影响,因此本文针对目前工作在这方面存在的问题开展研究工作。本文研究大规模服务请求下,基于海量服务资源的服务选取的效率提升和效果保证问题。在服务组合过程中,为了优化执行阶段组合服务的运行质量,往往将该过程分为两个阶段,一是流程设计阶段,二是基于服务选取的流程实例化阶段。流程设计阶段主要依据业务逻辑,设计抽象业务流程,抽象业务流程包括一组任务和它们之间关系,实现该任务功能的服务构成一个服务类。基于服务选取的流程实例化阶段,实例化的过程是为抽象业务流程中的每个任务从服务类中选取质量较好的一个服务,从而构建的组合服务实例满足用户的质量要求。组合服务实例在面对大量的用户访问时,其请求具有瞬时高并发性,同时用户因个性化需求而对服务请求有不同的质量要求,这导致了服务请求的多样性;组合服务实例在面对大量用户持续访问时,服务请求形成了请求流,请求流是动态变化的,组合服务实例面对动态变化的请求流,如何保证其自身的稳定性和收益最大化是一个值得研究的问题。因此本文针对服务请求的高并发性、多样性、流特性和组合服务收益性这四个问题进行研究,提出了相应的求解方法。(1)针对组合服务在面对大规模高并发服务请求时,一个组合服务实例难以满足用户需求的问题,本文构建了基于图的组合服务优化选取模型,提出了一个基于蚁群算法的多目标服务选取方法。该方法应用蚁群算法在图中搜索,一次优化选取多个组合服务实例,通过负载均衡实现请求分发,以保证大规模高并发服务请求的有效执行。为了提高求解效率,该方法应用Pareto模型,使用蚁群算法一次求解多个最优解,即Pareto解集,在此基础上,对解集中的解进行资源冲突检测,以保证并发量满足要求。通过实验证明,该方法在面对高并发的服务请求下,其求解效率得到有效提升,同时能够保证大规模高并发的服务请求有效执行。(2)针对于组合服务面对大规模服务请求时,服务请求的个性化导致同一时刻需要满足多种个性化的服务请求需求从而导致选取过程需要多次进行,降低选取效率的问题,本文构建了一个基于图的并行组合服务优化选取模型,在此基础上提出了一个基于并行蚁群算法的多目标服务选取方法。该方法首先将用户的个性化请求使用聚类算法进行聚类,形成多个请求类别,降低服务请求的个性化数量;然后应用并行蚁群算法对所有请求类别进行服务选取,每个蚁群针对一个请求类别求解,多个蚁群并行工作,通过并行交流策略解决各类别的最优解之间的冲突,最终形成一组没有冲突的最优解。实验表明,该方法可有效提高求解效率,同时在服务请求的规模化和个性化之间做到一个有效平衡。(3)针对由持续用户请求所构成的服务请求流的质量优化问题,本文构建了一个基于概率的解结构,在此基础上提出了一个基于人工蜂群算法的多目标服务选取方法。该方法给出了服务请求流质量约束描述方法,定义了一种新的解结构,该解由多个组合服务实例组成,每个组合服务实例有一个分配概率,请求来临时,根据分配概率分发请求。根据这种解结构,定义了解结构的请求流约束满足评价方法。在解评价的基础上,将约束满足问题转换为组合服务选取问题,然后应用人工蜂群算法一次求解多个组合服务实例和它的分配概率。通过实验证明,该方法可有效保证请求流约束,同时求解速度不会随着解空间的大小而有大的变化,基本适合大规模的问题求解。(4)针对组合服务提供者在服务请求流下,面向组合服务收益的持续优化选取问题,本文构建了一个基于马尔科夫决策过程的组合服务优化选取模型,在此基础上提出了一个基于Lyapunov优化理论的多目标服务选取方法。该方法首先将持续优化选取过程建模为一个马尔科夫决策过程,在该过程中将请求流按时间槽进行分片,同时为组合服务中的每个任务下的服务设置一个缓冲队列,当请求来临时,根据组合服务系统当前排队情况对当前时间槽下的请求进行分派,通过分派保证缓冲队列不无限增长,花费最小,在有限时间内用户请求能够得到响应,从而将组合服务持续优化选取问题转换为请求分派问题。但是由于服务众多,服务请求分派过程中,面临状态空间爆炸的问题,因此本方法应用Lyapunov队列稳定性理论,提出LBO算法,在分派的过程中保证缓冲队列稳定的前提下最小化时间平均运营成本,使得组合收益最大化,同时避免了状态空间爆炸问题。通过实验证明,该方法有效保证了持续请求流下,组合服务收益最大化,缩短了服务请求的平均等待时间,解决了状态空间爆炸问题。更多还原

【Abstract】 With the rapid development of service computing and cloud computing,a large number of service resources have been deployed on the network.Because of the convenience of network service access,more and more users use various kinds of service resources through the network to complete their business applications.The rapid growth of service resources has led to an increasing number of services offering similar functions.The frequent access of service resources makes the number of service requests rapidly increase at a certain time interval.This makes the service selection problem not only consider the quality of similar services,but also consider the change of service quality under large-scale requests.However,most of the current service selection solutions do not consider the change of service quality and the influence of service selection on large scale requests.Therefore,this dissertation aims at the current existing problems in this field.This dissertation studies the efficiency enhancement and effectiveness assurance of service selection based on mass service resources.In the process of service composition,in order to optimize the operation quality of the composite services at the execution stage,the process is often divided into two stages:one is the process design phase,two is the process instantiation stage based on service selection.In the process design stage,the abstract business process is designed according to the business logic.business processes include a set of tasks and their relationships.The service that implements the task function constitutes a service class.In the process instantiation stage based on service selection,the process of instantiation is to select a better service from the service class for each task in the abstract business process,and construct the combined service instance to meet the user’s quality requirements.When composite service instance is facing large amount of user access,the requests have instantaneous high concurrency.At the same time,users have different quality requirements for service requests due to personalized requirements.This leads to the diversity of service requests.When a composite service instance is faced with a large number of users accessing continuously,the service requests forms a request flow.The request flow is dynamic.How to ensure the stability and maximization of the revenue of a composite service instance in the face of dynamically changing request flows is a problem worth studying.Therefore,this dissertation studies the four problems of high concurrency,diversity,flow characteristics and composite service profitability,and puts forward the corresponding solution methods.(1)In this dissertation,a graph based composite service selection model is constructed,and a multi-objective service selection method based on ant colony algorithm is proposed to solve the problem that one composite service instance is difficult to meet the needs of the users when composite services are facing large scale and high concurrent service requests.The method uses ant colony algorithm to search in graph,selects multiple composite service instances at one time,and achieves request distribution by load balancing to ensure the effective execution of large-scale and highly concurrent service requests.In order to improve the efficiency of the algorithm,the Pareto model is applied and the ant colony algorithm is used to solve multiple optimal solutions,i.e.Pareto solution set,at one time.On this basis,resource conflict detection is carried out to ensure the concurrency to meet the requirements.Experiments show that the efficiency of the proposed algorithm is improved effectively facing high concurrency of service requests.At the same time,it can ensure the effective execution of large-scale and highly concurrent service requests.(2)When composite services face large scale service requests,personalized service requests result in various personalized service requests should be satisfied at the same time.As a result,the selection process needs to be carried out many times and the efficiency of selection is reduced.Aiming at this problem,in this dissertation,a graph based parallel composite service optimization selection model is constructed,and on this basis a multi-objective service selection method based on parallel ant colony algorithm is proposed.This method first uses the clustering algorithm to cluster users’personalized requests,and forms multiple request categories to reduce the number of personalized requests.Then the parallel ant colony algorithm is applied to select services for all the request categories.Each ant colony is used to solve for a request category.Multiple ant colonies work concurrently.The conflict between the optimal solutions of different categories is solved through parallel communication strategy.Finally,a group of optimal solutions without conflicts are formed.Experiments show that this method can effectively improve the efficiency of solution and that at the same time,an effective balance between the scale and individuation of service requests is achieved.(3)Aiming at the quality optimization problem of service request flow,which is composed of continuous user requests,in this dissertation,a probability based solution structure is constructed,and on this basis,a multi-objective service selection method based on artificial bee colony algorithm is proposed.In this method,the quality constraint description method of service request flow is given,and a new solution structure is defined.The solution is composed of multiple composite service instances.Each combined service instance has a distribution probability.When the request comes,the request is distributed according to the distribution probability.According to this solution structure,the evaluation method satisfied by the request flow constraint is defined.Based on the evaluation of solutions,the constraint satisfaction problem is converted to the problem of composite service selection.Then,an artificial bee colony algorithm is used to give multiple composite service instances and their allocation probabilities at one time.The experiment shows that the method can effectively guarantee the constraint of the request flow,and the solution finding speed will not change with the size of the solution space,and it is basically suitable for large-scale problem solving.(4)In order to solve the problem of continuous optimization of composite service revenue for composite service providers in service request flow,in this dissertation,a selection model of composite services based on Markov decision process is built.On this basis,a multi-objective service selection method based on Lyapunov optimization theory is proposed.Firstly,the continuous optimization selection process is modeled as a Markov decision process.In this process,the request flow is fragmented by time slot and a buffer queue is set up for each service under each task in the composite service.When the request comes,the request under the current time slot is dispatched according to the current queuing condition of the composite service system.The dispatchment ensures that the buffer queue is not unlimited growth and the cost is minimal,and the user request can respond in a limited time.In this way,the continuous optimization selection problem of composite services is converted to request allocation problem.However,due to the large number of services,the problem of state space explosion is faced in the process of service request allocation.Therefore,applying Lyapunov queue stability theory,LBO algorithm is proposed.In the dispatching process,the time average operating cost is minimized on the premise of ensuring the stability of the buffer queue,the profit is maximized,and state space explosion problem is avoided.The experiment proves that the method effectively guarantees under the continuous request flow,maximizing the revenue of the composite service,shortening the average waiting time of the service request,and solving the problem of state space explosion.更多还原