基于SMDP模型的Web服务组合优化方法

柴雪霞， 马学森，2， 周 雷， 唐 昊，2

（1.合肥工业大学 计算机与信息学院，安徽 合肥 230009；2.合肥工业大学 安全关键工业测控技术教育部工程研究中心，安徽 合肥230009）

随着网络上Web服务数量的急剧增加，在动态Web服务组合过程中，提供相同功能的 Web服务大量出现，对于众多功能相同的Web服务，服务选择的标准不仅要满足功能需求，还要满足非功能需求，因此QoS就成为了服务选择的一个标准。传统的Web服务架构中因缺乏对QoS的描述而难以从功能相同的众多服务中为用户选择最佳服务［1－2］，因此目前基于QoS的服务选择成为研究的重点。基于QoS的Web服务组合的选择问题的研究主要分为Web服务组合模型的建立和针对具体模型服务选择算法的研究［3］。

在Web服务组合模型方面，文献［4］提出了基于Petri网的Web服务组合模型，但是在服务选择时没有考虑服务的QoS。文献［5－6］利用离散时间的马尔可夫决策过程（Markov Decision Process，简称MDP）对服务组合建模，把QoS各个指标的综合值作为即时报酬，然后用Bellman最优方程求解最优策略，但在求解过程中需要了解各个状态的转移概率，而转移概率在实际系统中是很难得到的，并且不能解决连续时间的服务组合问题。在服务选择算法方面，文献［7］提出了适用于不同应用场景的局部优化与全局优化2种算法，局部优化算法只对组合中的某个任务有QoS约束，全局优化算法对组合中的所有任务都有QoS约束，但相对于前者来讲，后者计算量更大。文献［8］使用遗传算法从适应度函数的静态惩罚、动态惩罚及拉伸3个方面对系统优化性能进行比较。本文在文献［6］的基础上，借鉴了文献［7］中QoS模型的优点，对服务组合模型进一步扩展，使用有限状态连续时间SMDP对服务组合建模，利用模型无关的Q学习算法求解，得到最优的服务组合。

1 Web服务组合

1.1 Web服务组合系统

不同标准和研究组织对Web服务组合的定义不同，文献［9］给出了一个相对完整和通用的定义，即Web服务组合是利用Internet上分布的现有Web服务，根据用户需求，自动选择用户所需要的服务，在服务组合支撑平台的支持下，按照一定的规则协同完成服务请求。

Web服务组合系统包含2个用户角色（服务请求者和服务提供者）和5个部件（翻译器、组合管理器、执行引擎、服务匹配器和UDDI）。Web服务提供者把服务信息注册发布到UDDI，当服务请求者提出请求时，翻译器接受用户的请求，并将其请求转换为机器能够识别的语义表达，然后提交给组合管理器。组合管理器接受语义解释后，结合UDDI中的服务描述生成抽象的组合方案，并提交给执行引擎。执行引擎把抽象的服务描述发送给服务匹配器，服务匹配器结合UDDI中的QoS描述，把寻找到的最适合的具体 Web服务句柄返回给执行引擎。通过组合方案和查找到的具体 Web服务，执行引擎去调用和监督Web服务的执行，最后系统把执行结果返回给服务请求者。具体的实现过程如图1所示。

图1 Web服务组合系统

1.2 Web服务的QoS模型

目前学术界和工业界对QoS的认识有一定的差别，其中国际标准ISO8402和ITUE.800对QoS的定义更准确地反映了Web服务的QoS特点，同时也反映了用户的实际需要。QoS由一些非功能属性组成，为了讨论方便，本文的QoS模型只采用了有限的若干指标，以下分别给出这些指标的定义：

（1）服务费用C（S）指调用服务S所必须支付的费用，它由服务提供商指定，是一个确定的值，不随环境的动态改变而变化。

（2）响应时间T（S）指服务请求者从发送服务请求到收到结果的延迟时间，主要包括服务处理时间和网络传输时间，其中网络传输时间又可以分为发送请求的传输时间tra1和返回结果的传输时间tra2，服务处理时间表示为pr，因此响应时间T（S）＝tra1＋pr＋tra2。

（3）可用性A（S）表示服务S可以被访问，即可用的概率，可以通过服务S的平均无故障时间MTTF（S）和平均修复时间 MTTR（S）来定义，因此A（S）

（4）可靠性R（S）表示服务请求被成功响应的概率，并通过以往服务被成功调用的次数Nc（S）与服务被调用的总次数Ninvoke比值来衡量，即服务S的可靠性R（S）＝Nc（S）／Ninvoke。

QoS指标可以分为2种：① 正向质量指标，即指标值越大，服务质量越好，如可用性和可靠性；② 负向质量指标，即指标值越大，服务质量越差，如服务费用和响应时间。因此为了使各个指标对其性能影响一致，要对QoS指标归一。正向指标归一为：

负向指标归一为：

根据归一化后的值可以计算每个服务S的综合评价值，于是得到其中，二维矩阵Q为一组服务的QoS指标值；i为服务个数；j为指标的个数为第j个指标的最大值为第j个指标的最小值；wj为每个指标的权值，并有QoS（S）值越大，说明服务质量越好。

2 Web服务组合的数学模型和优化算法

文献［6］考虑了离散时间的 MDP，而在实际的服务组合中，系统在各个状态的逗留时间服从一般分布，因此Web服务组合的优化问题可建模为连续时间SMDP来研究。

2.1 Web服务组合的SMDP模型

Web服务组合将现有的一组服务按照一定的逻辑进行集成，从而更好地满足用户的需求。静态服务组合在创建一个新服务前就了解用户的需求，在服务提供给用户后不再发生变化，而动态服务组合则根据运行时出现的需求自动生成组合流程，并能够自动查找、组合服务。本文是在自动生成流程结构的基础上研究服务组合的，因此属于动态服务组合。Web服务组合通常有4种结构［5］：顺序、并行、选择和循环结构。根据文献［10］，这4种结构可以转化为如图2所示的顺序结构。其中ti表示服务组合中的一个任务节点。

图2 顺序结构

Web服务组合可以看成是从初始状态到终止状态的任务流程图，根据生成的流程结构，系统分别为每一个任务节点选择具体的Web服务，如果为当前的任务节点选择服务成功，则转到下一个任务节点，否则继续为当前的任务节点选择服务，直到成功为止。

设Tn表示第n个决策时刻，n＝0，1，2，…，N。系统状态用各个任务节点的执行情况来表示，对于包含m个任务的流程图，系统状态用m元组〈t1，t2，…，ti，…，tm〉表示，第n个决策时刻系统的状态记作sn，其中ti＝1，2，…，m∈｛0，1｝，ti＝1表示已经为节点ti绑定了具体的 Web服务，ti＝0表示还未为节点ti绑定具体服务。假设第n个决策时刻采取的行动（即调用的服务）为an，状态sn下的行动集A（sn）是任务节点可调用的候选服务，所有状态下的行动集构成了系统的行动集A，其中每个任务下的候选服务功能相同而QoS不同，不同任务对应的候选服务集是不同的。根据文献［5］，把调用服务的可靠性作为转移概率，则系统在当前状态sn以psnsn＋1（an）＝R（an）的概率转移到下一状态，以1－psnsn＋1（an）的概率停留在当前状态。若服务请求时间、处理服务时间和返回处理结果时间均服从指数分布，则在状态sn的逗留时间Fsnsn＋1（t，an）服从Erlang分布［11］，根据文献［12］，通过 Q（sn，sn＋1，an，t）＝psnsn＋1（an）Fsnsn＋1（t，an）可以求得半马尔可夫核，此式表示系统在状态sn采取行动an，转移到下一状态sn＋1前所需时间小于或等于t的概率。

从Tn到Tn＋1共经历3个阶段：发送服务请求、处理服务和返回处理结果。其中，tra1和tra2分别表示发送服务请求时间和返回处理结果时间，pr表示处理服务的时间，因此有Tn＋1＝Tn＋tra1＋pr＋tra2。系统运行的时间轴如图3所示。

图3 系统运行时间轴

由于服务组合包含有限个任务节点，因此本文采用有限时段连续时间SMDP。定义在策略v下的有限时段折扣代价准则为：

其中，G（iN）为最终状态的代价；g（sn，an，sn＋1）定义为系统在当前状态sn采取行动an转移到下一状态sn＋1之前的单位时间期望代价；α为折扣因子，当α＞0时表示状态s的折扣代价，当α＝0时，表示状态s的累积代价。优化目标就是在策略空间中找到一个最优策略，使得（3）式代价最小。

2.2 服务组合的Q学习算法

文献［5－6］使用数值迭代的方法求解最优策略，而当系统状态空间巨大时，数值迭代通常存在着“维数灾”问题。因此为了避免此问题的出现，本文采用Q学习方法，其最大的优点是不依赖系统模型，为解决系统信息未知或不完全知的情况提供了便利。

假设系统从状态sn转移到状态sn＋1，在此期间分别会产生发送请求服务代价、处理服务代价和返回处理结果代价。此外，在状态sn调用服务后会产生一个立即报酬，设Can为采取行动an所对应的立即报酬，则累积代价的计算公式为：

其中，f′（sn，an，sn＋1）为系统从决策时刻 Tn到Tn＋1所获得的累积代价；k1为处理服务单位时间代价；k2为在网络上传输单位时间代价。由于Web服务的不确定性，在调用的过程中可能成功也可能失败，若调用服务成功，Can＝QoS（S），否则Can＝0，QoS（S）指Web服务的综合评价值。

在学习优化过程中，从Web服务组合的任意状态出发到终止状态作为一个仿真片段（episode），记为h。在仿真片段结束后，折扣准则下差分dh的计算公式为：

其中，T0＝0为第h个仿真片段的第n步；仿真片段的长度为lh＋1；Qα为第h个仿真片段的初始状态行动对值。

其中，γh为学习步长。

在Q学习中对于行动的选取，一般采用εgreedy方法（0≤ε＜1，取接近0的小数），即在当前状态s以1－ε的概率选取当前最优行动a＊∈，以ε的概率随机选择一个行动。

Q学习具体算法过程为：

（1）初始化参数。令h＝0，设置折扣因子α，学习步长γh，学习片段数H，初始化所有状态行动对的Q值。

（6）h：＝h＋1，若h＝H，学习结束，否则转步骤（2）。

3 仿真结果

鉴于目前没有相关的标准平台和测试数据集，本文采用随机生成的大量数据进行仿真，在仿真中设定k1＝40，k2＝20，tra1和tra2均服从参数为λtra1＝λtra2＝2的指数分布，pr服从参数为λpr＝1的指数分布。

在仿真中设定服务组合有10个任务，每个任务有10个候选服务。不同折扣因子下的优化曲线如图4所示，从图4可以看出，使用Q学习算法，能很快收敛到最优或次优策略。在折扣因子α＝0时，经过450次迭代后，性能逐渐趋于稳定，最终策略v＊＝［10，10，1，6，3，7，4，9，3，1］，在该策略下的代价为2.019 4，其中策略v＊中的数字代表在不同的任务下所调用的具体服务。

图4 不同折扣因子的优化曲线

为了分析流程中不同任务数以及每个任务下不同候选服务数对系统计算代价的影响，本文对顺序结构分别包含10、20以及最多80个任务的流程图进行仿真实验，其中每个任务又分别有10、20以及30个候选服务，结果如图5所示。

图5 不同任务数和候选服务数的代价

图5表明随着任务数和候选服务数的增加，得到最终策略的计算代价也随之增加。当任务数小于30个，候选服务10～30时，对计算代价的影响不是很大，但当任务数大于50个时，计算代价会随着候选服务数的增多而剧烈增加。

不同任务数和候选服务数的情况下组合成功率如图6所示。由图6可以看出，使用Q学习算法可以得到相对高的服务组合成功率。并且服务组合时，组合成功率与任务数和候选服务数都有关系，在任务数确定的情况下，其对应的候选服务数10～30时，对组合成功率的影响不是很大，但随着任务数的增加，组合成功率会降低。候选服务数较多，组合成功率变化缓慢，说明候选服务数越多，系统的性能越稳定，但同时系统的代价也会增大，这与实际是相符合的。

图6 不同任务数和候选服务数成功率

在相同的实验环境下对文献［7］提出的整数规划方法和本文的优化方法进行比较，结果如图7所示。从图7可以看出，本文的方法具有较高的服务组合成功率，因为整数规划是静态的方法，如果在组合过程中出现服务失效或者调用异常，则只能进行重规划，而本文是动态寻找最优规划的方法。

图7 组合成功率的比较

4 结束语

本文给出了Web服务组合的实现过程以及QoS模型，并针对Internet环境的动态性和Web服务的随机性，给出了有限状态连续时间SMDP模型的Web服务组合学习优化方法，最后的仿真实验也说明了该方法的可行性和有效性。另外，可用分层强化学习如Option、MAXQ等研究Web服务组合，可以解决大规模系统的“维数灾”问题，同时可以加速策略学习。

［1］郝轩史，维 峰.基于SOA的Web服务动态组合研究与实现［J］.计算机工程与设计，2008，29（15）：3929－3932.

［2］岳 昆，王晓玲，周傲英.Web服务核心支撑技术：研究综述［J］.软件学报，2004，15（3）：428－442.

［3］袁小玲，李心科.基于双向动态规划质量有保障的组合服务选取［J］.合肥工业大学学报：自然科学版，2009，32（4）：465－469，499.

［4］范贵生，刘冬梅，陈丽琼，等.可靠服务组合的协调策略与分析［J］.计算机学报，2008，31（8）：1445－1457.

［5］Gao Aiqiang，Yang Dongqing，Tang Shiwei.Web service composition using Markov decision processes［C］／／Proc of the 6th Int Conf on Web－Age Information Management，LNCS 3739，2005：308－319.

［6］范小芹，蒋昌俊，王俊丽，等.随机QoS感知的可靠 Web服务组合［J］.软件学报，2009，20（3）：546－556.

［7］Zeng Liangzhao，Benatallah B.QOS－aware middleware for Web service composition［J］.IEEE Transaction on Software Engineering，2004，30（5）：311－327.

［8］蒋哲元，韩江洪，王 钊.动态的QoS感知Web服务选择和组合优化模型［J］.计算机学报，2009，32（5）：1014－1025.

［9］冯明正.Web服务组合综述［J］.计算机应用与软件，2007，24（2）：23－27.

［10］Cardoso J，Sheth A，Miller J，et al.Quality of service for workflow and Web service processes［J］.Web Semantics：Science，Services and Agents on the World Wide Web，2004，1（3）：281－308.

［11］胡奇英，刘建庸.马尔可夫决策过程引论［M］.西安：西安电子科技大学出版社，2000：94－125.

［12］Tang Hao，Yin Baoqun，Xi Hongsheng.Error bound of optimization algorithms for semi－Markov decision processes［J］.International Journal of Systems Science，2007，38（9）：725－736.