摘要：当前，面向服务的计算方式发展迅猛，出现了聚合多个个体服务的组合服务。同时，多个原子服务可能实现一个服务功能。在这种环境下，如何选择合适的服务以实现服务组合是当前研究的热点问题。然而，传统的选择方法难以应对大规模的服务场景。首先对服务选择的问题模型进行了描述；其次提出了基于蒙特卡罗法的并行选择算法；最后，提出了实现并行化的服务选择基本框架。
关键词：组合服务；计算方式；服务选择;并行优化;蒙特卡罗法
中图分类号：TP301文献标识码：A文章编号：1672-7800（2012）003-0006-03
作者简介：朱勇（1977-），男，江苏南京人，硕士，南京陆军指挥学院教育技术中心讲师，研究方向为计算机网络与软件；钱建新（1964-），男，江苏南京人，南京陆军指挥学院教育技术中心讲师，研究方向为计算机网络；叶丛如（1971-），男，江苏南京人，南京陆军指挥学院教育技术中心讲师，研究方向为多媒体技术。
0引言
当前，面向服务的计算方式发展迅猛，出现了聚合多个个体服务的组合服务。这些组合服务可以为用户提供以往单个服务无法提供的功能。通过聚合有关服务，开发者可以快速构建和部署面向服务的软件应用系统，为用户提供前所未有的体验；同时，众多提供商发布了大量功能类似但具有不同非功能属性（如QoS，Quality of Service）的服务。在众多功能相同或相似的服务集合中选择服务，生成满足用户QoS需求的组合服务，已经成为研究的热点。
然而在数量庞大的服务集合中进行QoS感知的服务选择面临诸多挑战。巨大的计算量就是其中之一。由于传统的服务选择方法难以适应服务规模的快速增长，当服务数量增加时，其计算量大幅增加。为解决这类问题，许多启发式算法被相继提出。然而，当服务规模较大时，服务选择的计算量仍然会成为其性能瓶颈。近几年来，随着云计算等新兴计算方式的逐步兴起，为进一步减少服务选择的时间提供了有力的技术支撑。实际上，服务选择的计算过程可以划分为多个子任务分配到多台机器进行并行处理，大大减少了服务选择的时间。
蒙特卡罗法是一种随机模拟方法，以概率和统计理论，使用随机数（或伪随机数）来解决很多计算问题。它通过将所求解的问题同一定的概率模型相联系，用计算机实现统计抽样模拟，以获得问题的近似解。蒙特卡罗法是一种非确定的方法，由于其比较适用于解决规模较大的组合问题，故本文基于蒙特卡罗法提出了一种并行优化服务选择的方法。该方法具有两个优点：一是利用多台计算机进行服务选择优化，缩短了服务选择的时间；二是可以应用于分布式环境中，提高系统的容错性和对负载的适应性。
1服务选择问题模型
设一个组合服务有n个任务组成，每个任务可以由一个原子服务来完成。假设具有相同功能和不同QoS的服务有m个。通常服务QoS有响应时间、可用性等。为完成服务组合，满足用户的需求，需要为每一个任务选择一个合适的原子服务来执行。
例如，当构建一个面向服务的旅游咨询软件系统，可以利用目前网络上已有的现成服务来实现。该系统具体有以下几项任务：①推荐旅游目的地；②天气查询；③旅行社报名；④费用结算。一个面向服务的旅游咨询软件系统实例见图1。每个任务都存在多个原子服务可以完成。如，在网络上天气查询存在多个天气查询系统，它们虽然功能相似，但却具有不同的QoS（其请求的响应时间和用户的服务评价可能各不相同），该旅游咨询系统完全基于面向服务的计算平台，所有任务的完成都基于这些服务。当然，用户希望该旅游咨询系统的服务质量越高越好，而旅游咨询系统的服务质量取决于其选择的相关服务。
本文要解决的问题就是如何选择合适的服务，使得这些服务构成的组合服务在满足一定约束的前提下优化服务质量。为便于描述本文做出如下限定：
限定1：构成组合服务的任务之间是顺序执行的关系。如图2所示。
限定2：每个服务有α个QoS参数，QoS参数分为正向参数和负向参数，正向参数值越大用户越满意，如可用性；负向参数值越小用户越满意，如响应时间。由于正向参数可以通过乘以-1而转化成负向参数，故本文仅考虑QoS参数为负向参数的情况。
限定3：QoS参数通常具有可加性或可乘性。如一个组合服务由n个原子服务构成，其总的响应时间为两个原子服务的响应时间之和（可加性）；其总的可用性为n个原子服务的可用性之积（可乘性）。对于具有可乘性的QoS参数可以通过取对数得方法使其变成具有可加性，因此，本文仅考虑QoS参数具有可加性的情况。QoS聚合计算还涉及到其它情况，具体参见文献。
限定4：各维QoS参数均已归一化，其值在0和1之间，归一方法如下：
qijk=qmaxik-qoijkqmaxik-qminik（1）
其中，qijk为归一化后的服务sij（该服务可以处理任务i）的第k维QoS值；qoijk为原始的服务sij的第k维QoS值；qmaxik和qminik分别为所有可以处理任务i的服务组成的集合中第k维最大和最小QoS值。
经过归一化处理之后，各QoS参数已处于同一数量级，因此服务sij的效用Uij可以计算如下：
Uij=∑αr=1wrqijk（2）
其中，wr为第r维QoS权重，其值在0和1之间，并且所有维的QoS权重之和为1。
于是，服务选择的数学模型可以表示为混合整数规划（MIP, Mixed Integrate Programming）模型：
maximizeU=∑ni=1∑ mj=1xijUij
∑ni=1∑ mj=1xijqijk≤Rk(1≤k≤α)
s.t∑ni=1∑ mj=1xij=1xij∈{0,1}（3）
其中，xij是指示变量，只有两个值0或1，值为1时表示选择服务sij来处理任务i，值为0时表示服务sij未被选择处理任务i； Rk表示对组合服务中第k个参数的最大限制，如组合服务的最大响应时间不得超过7秒，则R=7。模型的目标是最大化组合服务的总效用U；xij是模型的解；约束条件有两个：第一个条件保证了各维QoS参数之和不超过用户需求的上界Rk；第二个条件保证一个任务只能也必须选择一个服务来处理。
2基于蒙特卡罗法的并行服务选择
由上面的分析可以看出，服务选择就是求解一个MIP数学模型，该模型是NP难的。传统的方法采用线性规划工具来求解。然而随着服务规模的增加，传统的方法需要大量的计算时间和集中的计算环境。已经不能适应用户需要快速完成服务选择的需求以及分布式的服务运行环境。因此，本文提出一种基于蒙特卡罗法的并行服务选择算法MCBPSS（Monte Carlo Based Parallelized Service Selection）。MCBPSS算法的主要思想是基于蒙特卡罗方法对服务进行并行选择。首先将服务选择划分为c并行执行的任务，分别在c台物理上独立的机器上运行；其次，对具有相同功能的服务进行筛选，按照启发式规则缩小候选服务的数量，并分发到c台独立的机器上；最后，在每台机器上，基于蒙特卡罗法经多次重复选择的选出一个局部最优组合服务，并在比较c台机器上选择结果的基础上选出一个全局近似最优的组合服务。
MCBPSS算法：
（1) 对每个服务sij，计算其评价值Rateij。Rateij计算如下：
Rateij=Uij∑αk=1ωkqijk（4）
(2) 对每个服务sij中，按Rateij值排序,选出最大的d个候选服务组成候选服务集合Si，并分发到c台机器上。
(3) 对每个Si，计算各服务sij的启发式函数：
ψij=∑αk=1wkRk-qijkRk�k:qijk≤Rk
0�k:qijk＞Rk（5）
（4) 对每个Si中的服务sij，按每个服务的概率pij选择一个服务，其中pij越大的服务被选中的机会越大。pij的计算如下:
pij=ψij∑|Si|u=1ψiu（6）
（5) 判断选出的组合服务是否满足约束条件。如满足则加入解的集合Y。
（6) 重复步骤（4)和（5)共h次。
（7) 如果|Y|>0,选出所有组合服务中总效用最大的组合服务。
（8） 比较c台机器上的服务选择结果，选择全局近似最优的结果。
3并行化的服务选择实现框架
为了实现服务选择的并行优化，本文提出了一个并行化的服务选择实现框架。具体过程见图3。
如图3所示，用户向代理服务器提出请求，代理服务器根据组合服务所涉及的任务，从服务库中分别获取有关服务的QoS信息，经过统一的预处理后将筛选过的服务信息发送到若干台并行运行的服务器上；在每台机器上基于蒙特卡罗法进行服务选择，并将服务选择结果返回给代理服务器；最后，在代理服务其上比较各返回的并行处理结果，并选择最优的组合服务，完成最终的服务组合，快速生成面向服务的软件应用系统，返回满足用户需求的结果。
在模拟仿真环境下，通过与基于整数规划的服务选择方法（表示为IP，利用Lpsolver 实现）相比，本文方法(用MCBPSS表示，算法参数为：c=3；d =30； h=100)的服务选择时间大大减少。表1列出了在几种不同服务规模参数下本文方法的计算时间。
4结束语
面向服务的软件应用系统需要组合已有的服务资源，快速构建软件应用系统。因而，如何进行服务选择是一个关键的问题。
本文针对分布式环境下的服务选择问题进行了研究，提出了一种并行化的服务选择方法，该方法利用了蒙特卡罗法在多台机器上分布执行服务选择，并将并行执行结果返回比较，选择最优的结果。该方法可以适应互联网环境中较大的服务规模，快速生成组合服务，构建满足用户需求的面向服务的软件应用系统。
参考文献：
\[1\]PAPAZOGLOU M P,TRAVERSO P,DUSTDAR S,LEYMANN F.Service-oriented computing:state of the art and research challenges\[J\].Computer,2007(11).
\[2\]ZENG L B,BENATALLAH，AHH N. QoS-aware middleware for Web services composition\[J\].IEEE Transactions on Software Engineering,2004(5).
\[3\]刘书雷，刘云翔，张帆,等.一种服务聚合中QoS 全局最优服务动态选择算法\[J\].软件学报，2007(3).
\[4\]TAO YU, YUE ZHANG,KWEI-JAY LIN.Efficient algorithms for web services selection with end-to-end QoS constraints\[J\].ACM Transaction on Web (Tweb),2007(1).
\[5\]HUANG A F,C W LAN, et al.An optimal QoS-based web service selection scheme\[J\].Information Sciences, 2009(19).
\[6\]莫振华，蔡鸿明，姜丽红． 基于遗传算法的多QoS 约束服务选择［J］． 计算机应用与软件，2009( 3)．
\[7\]方其庆，刘庆华，彭晓明，等． QoS 全局最优的多目标Web 服务选择算法［J］． 计算机应用研究，2009( 12)．
\[8\]彭晓明，何炎祥，朱兵舰． 蚁群算法在Web 服务组合中的应用［J］． 计算机工程，2009(10)．
\[9\]LIU DONG-MEI，SHAO ZHI-QING，YU CAI-ZHU，et al． A heuristic QoS aware service selection approach to web service composition\[A\]. Proceedings of the 8th IEEE/ACIS International Conference on Computer and Information Science,Washington DC: IEEE Computer Society，2009．
\[10\]徐钟济.蒙特卡罗方法\[M\].上海:上海科学技术出版社,1985.
\[11\]JAEGER M C，ROJEC-GOLDMANN G,MHL G.QoS aggregation for web service composition using workflow patterns\[A\]. Proceedings of the 8th IEEE International Enterprise Distributed Object Computing Conference, Monterey, CA, 2004.
\[12\]K E MICHEL BERKELAAR,P NOTEBAERT. open source(mixed-integer) linear programming system.Sourceforge\[EB/OL\]. http://lpsolve.省略/
（责任编辑：杜能钢）
A parallelized Optimization Approach for Service
Selection Based on Monte Carlo Method
Abstract:Currently, with the development of SOC (Service-Oriented Computing), there are some composite services which are composed of some individual services. On the other hand, the services with the same function can offer the different quality level for users. This paper addresses the problem on service selection. In order to optimize the composite service, the service selection approach needs to tackle with the large-scale service environment. The mathematic model is established for the problem and the monte carlo-based algorithm is proposed to solve it. Finally, the paralleized framework is proposed to realize the approach.
Key Words: Service Selection； Parallelized Optimization； Monte Carlo