基于层次化的云制造服务组合研究

刘卫宁 马 刚 刘 波

重庆大学信息物理社会可信服务计算教育部重点实验室，重庆，400044

0 引言

云制造是一种面向多用户需求的不确定性制造［1-2］。用户需求的多样性和不确定性导致用户对云制造任务的执行要求不同，即不同用户对云制造任务执行各环节的关注度不尽相同。如何精确调控云制造资源和制造能力，找到一条组合云服务执行路径，使其整体服务质量(quality of service，QoS)最优并满足各子路径中不同用户多样化的QoS需求，即是本文研究的云服务组合(manufacturing cloud services composition，MCSC)路径优选问题［3-5］。

云制造服务组合研究受启发于服务计算(service－oriented computing，SOC)理论的相关研究成果［2，6-8］，主要包括:①任务分解技术，如基于层次任务网(hierarchical task network，HTN)规划的方法［9-11］等;②服务发现与匹配，如基于关键字的Web服务发现与匹配、基于语义的Web服务发现与匹配;③服务形式化表达与验证，如基于Petri网的Web服务组合验证、基于自动机理论的Web服务组合验证、基于进程代数的Web服务组合验证等;④服务组合方法，如基于人工智能和规划的服务组合、基于图搜索的服务组合、基于QoS的服务组合等。但是，鉴于制造资源的多样性、复杂性、规模性等特点，上述服务组合方法不能直接应用到制造领域的服务组合中。近年来，服务计算领域中基于QoS的服务组合方法同制造网格等面向服务的网络化制造模式不断融合，逐渐形成了基于QoS的制造服务组合及优选方法体系［3-5，12-16］。但制造网格系统中的服务组合重在体现“分散资源集中使用”的思想，侧重于实现资源协同的整体优化目标。而云制造致力于为制造活动中的各利益主体构造可充分沟通的制造环境，体现出“分散资源集中使用”与“集中资源分散服务”的融合，其服务组合的优化目标不仅表现在整体需求的实现，还渗透在制造全生命周期的每个环节［2］。无论是面向计算领域还是制造领域，现有的服务组合研究都集中于追求服务组合路径的整体QoS最优，很少关注服务组合路径结构上的层次化特性及各层次上子路径的不同QoS需求。

从以上分析可以看出，现有的服务组合研究存在以下问题:①一味追求服务组合整体的服务质量最优，忽略了各层次组合过程中的局部服务质量约束，导致服务组合路径存在服务质量瓶颈，从而影响全局的服务质量;②在QoS计算过程中，服务组合路径的整体服务质量直接取决于基本云服务的服务质量及其整体路径的结构特性，忽略了中间各层次的结构特性，而根据服务组合的基本原理可知，不同结构服务组合路径的QoS值计算方法不同［8，17］，从而导致计算结果可能存在偏差。

上述问题使得既有的制造服务组合模型及组合过程与其追求全局服务质量最优的初衷背道而驰。因此，本文在力求云服务组合全局服务质量最优的情况下，重点考虑云服务层次性组合过程的局部服务质量保障，提出了基于层次化的云制造服务组合(hierarchicalmanufacturing cloud services composition，H－MCSC)优选建模方法，并对模型进行了算法求解和验证。

1 问题提出

现阶段，大多数网络化制造的研究将云服务组合分为任务分解、候选云服务推荐、云服务组合与优选三个阶段［2-5，16］。网络化制造过程将云制造任务分解为多个原子任务，分别选取功能相匹配的服务，形成全局QoS最优的服务组合，将制造过程和服务组合为一个顺序化的任务流程。

然而，制造过程管理的相关研究表明，制造过程是层次化执行的［9，17］。文献［17］提出了基于层次链的产品装配过程建模方法，将制造任务描述为一系列子任务按一定层次结构的聚合;文献［9］使用基于HTN的规划方法，建立了产品装配序列生成的任务分解策略。基于HTN的任务规划是当前服务组合中任务分解的重要方法［10-11］，该方法在制造任务分解中的广泛应用正是制造过程层次化特性的有力证明。而云服务组合过程可以看成是任务分解的逆过程，所以层次化特性在云制造服务组合中也具有一般性。

本文结合云制造中服务组合的相关研究，将制造任务的层次化特性引入到云制造的服务组合过程中，提出基于 H－MCSC的模型，如图1所示。

在图1所描述的基于层次化的制造云服务组合过程中，首先对云制造任务进行层次化分解，每个非原子任务都可以分解为一系列的子任务(图1a→图1b)。找到各原子任务与功能匹配的一组服务候选集，选取服务候选集中的某个云服务并构造一个云服务组合来执行其上层任务(图1b→图1c)，该上层任务又可以由这一系列组合服务的组合来执行，最终形成一个层次化的组合服务集群(图1d)，共同完成用户提交的云制造任务。具体的层次化服务组合过程描述如图2所示。

2 问题建模

2.1 问题描述

云制造的层次化服务组合是一个递归的迭代过程，其制造任务可按任务层次和性质分为顶级任务、原子任务和中间子任务，顶级任务即为用户提交的云制造请求，中间子任务则是由一系列的原子任务或其他的中间子任务组合而成的非顶级任务。只有原子任务可以被单个的云服务独立执行，其他任务需要根据任务层次由多个云服务逐层组合执行。显而易见，各层次间的服务组合具有相同的迭代性质，本文特别针对3层的云服务组合问题进行研究。

图1 基于层次化的制造云服务组合模型

基于层次化的服务组合问题形式化描述如下:

图2 基于层次化的服务组合流程

组合优选过程要遵循以下原则:

原则1 云服务组合路径中的各制造云服务必须满足云平台最低的服务质量约束。

原则2 必须使层次化服务组合路径中各中间层服务组合子路径的服务质量满足用户对相应子任务的服务质量要求。

原则3 要尽可能使层次化云服务组合形成的最终复合云服务组合执行路径的整体服务质量最优。

2.2 QoS 评估模型

受启发于服务计算领域中基于QoS的服务组合研究，网络化制造领域中的许多研究也采用了QoS来评价制造服务的优劣。文献［18］研究了制造网格中的QoS建模和评价方法，但只给出了一系列QoS属性的概念性定义;文献［4］针对时间、成本、可用性等QoS属性给出了相应的量化计算方法。本文选取时间、成本、可靠度、信誉度4个具有代表性的QoS属性为云制造服务质量的评价指标，并给出了各QoS属性的具体定义及其量化计算方法，详见表1。

表1 QoS属性定义及量化方法

对于每个制造云服务RS，系统给出其各QoS属性值，即可计算各服务组合路径的QoS。文献［7］将云计算中的服务组合路径描述为4种类型(顺序结构、并行结构、选择结构、循环结构)，给出了其相应的QoS计算方法。文献［6，8］直接将这4种结构引入到制造领域的服务组合QoS的计算中。本文将云制造任务分解为一系列的制造子任务序列，很显然任务执行路径已经确定。考虑到制造云服务独占、成本高、执行周期长等特性，云制造服务组合路径一般不会出现选择结构和循环结构，故本文只考虑服务组合中的顺序结构和并行结构两种情况，并据此给出了服务组合中QoS值的计算方法，详见表2。

表2 服务组合QoS计算方法

综上所述，定义各制造云服务RS的QoS为Q(RS)=〈T(RS)，C(RS)，Rel(RS)，Rep(RS)〉;相应的对于每个装配任务的执行路径Pj，定义其QoS 为Q(Pj)=〈T(Pj)，C(Pj)，Rel(Pj)，Rep(Pj)〉;对于整个云制造任务执行的服务组合路径P，定义其QoS为Q(P)=〈T(P)，C(P)，Rel(P)，Rep(P)〉。

为计算服务组合路径P的服务质量Q(P)，假设路径P中的顺序结构、并行结构的比例分别为f1(P)和f2(P)，f1(P)+f2(P)=1。

为避免路径P的整体结构失衡造成服务质量计算偏差，将其结构特性分散到各子路径中Pj中，分别以f1(Pj)、f2(Pj)表示服务组合路径Pj中的顺序结构与并行结构的比例，且对于任意的Pj，有f1(Pj)+f2(Pj)=1。则服务组合路径P及其各子路径Pj的QoS计算方法如下。

顺序结构下Pj的服务质量Qseq(Pj):

并行结构下Pj的服务质量Qprl(Pj):

服务组合子路径Pj的服务质量Q(Pj)为

顺序结构下P的服务质量Qseq(P):

并行结构下P的服务质量Qprl(P):

则服务组合路径P的服务质量Q(P)为

鉴于制造过程中各环节具有不同的重要性，用户不仅需要追求全局最优的服务质量，还需要使各子任务的服务组合路径Pj的服务质量得到保障。定义用户对各子任务Pj的最低可靠性和最低信誉度约束:

其中，Relu(Pj)、Repu(Pj)分别为用户针对Pj对应子任务的重要性给出的最低的可靠性和信誉度保障。

综上所述，我们将基于层次化的服务组合优化问题表达如下:

基于层次化的服务组合优化问题本质上是一个多目标多约束规划问题，利用权重系数α和β，将其转化成为了单目标规划，其中，α和β分别为QoS中时间与价格的权重系数，满足α+β=1;Relsys、Repsys分别为系统预设的云服务最低的可靠性和信誉度需求，Rel0、Rep0分别为用户给定的全局服务组合路径最低的可靠性和信誉度。

3 问题求解

本文提出的基于层次化的云制造服务组合模型是一个典型NP组合优化问题，其层次性决定了其解空间为一个多维的复合型解空间，较一般的服务组合问题求解更为复杂。模拟退火算法被证明是能够以概率1收敛到全局最优解的智能优化算法。考虑模型求解过程中的运算量随服务组合层次增加而显著增加，本文采用较为简单的模拟退火算法进行求解，以保证模型层次化可扩展性和算法的实用性。同时，为了保证算法性能，提高算法效率，本文设计了提前剪枝的策略。

基于层次化的云制造服务组合问题的模拟退火算法求解过程如下:

(1)解空间。层次化服务组合路径P包含一系列的子路径P={P1，P2，…，PJ}，Pj中的节点Pjk对应候选云服务集RSSjk中的某个候选云服务RSjkh，用xjk表示云服务RSjkh在RSSjk中的序号h(为方便，以Xjk表示RSjkh)，则层次化的云服务组合问题的解空间S可表示为

①对二维解空间S，取其中的一维S［j］;

②对S［j］中的xjk，分别取Xjk所有可能的取值中可靠性和信誉度最大的元素，计算S［j］对应路径的最大可靠性Relmax和信誉度Repmax;

③分别取Xjk所有可能的取值中可靠性和信誉度最小的元素，计算S［j］对应路径的最小可靠性Relmin和信誉度Repmin;

④ 取(RelmaxRelmin)1/2、(Repmax+Repmin)/2 为S［j］对应子路径的Pj的QoS约束(Relu和Repu);

⑤ 对空间S［j］所有可能出现的解S0［j］，根据式(1)、式(2)计算对应的可靠性Rel和信誉度Rep;

(3)目标函数。本文以时间T和成本C为服务质量的评价指标，在式(9)定义了基于权重系数的目标函数:

(4)约束条件。式(11)、式(12)分别定义了子路径Pj和路径P的QoS约束，解空间S对应的服务组合路径必须满足这两个约束。

(5)新解的产生。对当前解S0取任意的xjk，根据可选的云服务，替换为x'jk，得到S0的邻域S'，结合式(13)推导得

(6)代价函数。设新的解S'对应的服务组合路径为P'，其代价函数Δf表示如下:

(7)接受准则。对新的解空间S'，按以下概率进行接受:

只有在新路径满足约束条件的情况下，才允许接受新路径。如果Δf＜0，则接受新路径;否则，以概率exp(－Δf/T)接受新的路径。

(8)降温。利用选定的降温系数λ(0＜λ＜1)进行降温得到新的温度，即T←λT。λ可根据算法要求进行调整，降温越慢，算法找到全局最优解的可能性越大，但执行的时间也越久。

(9)结束条件。用选定的终止温度e，判断退火过程是否结束。若T＜e，则算法结束，得到最终的解。

4 实验仿真

为验证本文中模型和算法的有效性，本文假设云制造任务MT包含4个中间子任务，每个中间子任务由4个原子任务构成，每个原子任务有4个云服务可供选择，并在MATLAB7.1的环境中对算法进行了仿真实验。其中，各云服务的QoS属性值均随机生成，各子路径的QoS约束根据数据中组合所有可能出现的情况综合设置(取均值等)。MT对应的服务组合路径P有16个路径节点，有232种组合方案。

4.1 模型的有效性验证

(1)对随机生成了20组数据，分别根据式(12)对不满足子路径约束的服务组合进行剪枝，得到其解空间大小和无约束条件下解空间大小的比，见表3。

表3 剪枝前后解空间大小的比 ‰

可以看出，根据子路径约束提前对服务组合路径进行剪枝，能够使解空间大小减小到原来的1‰ ～1%，从而提高了算法的搜索效率。本文主要研究3层的服务组合，对于更多层的服务组合，效果将更为明显。

图3 未分层结构的QoS评价值与分层结构的比例因子

从图3可以看出，虽然比值比较接近，但并不线性相关。从式(2)、式(5)可以看出，在不分层的情况下，并行结构的计算很容易受路径结构影响。本文通过分层对服务进行组合，将路径结构对QoS的影响分散到各层次的组合服务中，避免因单一考虑整体的结构特性造成QoS计算偏差。

(3)对其中某一组数据，分别计算了文中带有子路径约束的分层服务组合情况下的dest的值(实线)和不分层的服务组合下dest值(虚线)的概率分布，如图4所示。

图4 QoS评价值的区间概率曲线

从图4可以看出，在所有的服务组合路径中，满足用户对各子路径约束的服务组合只是其中的一小部分，而且一部分全局QoS较优的服务组合并不满足局部QoS约束。所以，一味追求服务组合的全局最优QoS，可能导致因为局部服务质量偏低，使得云制造任务的服务质量难以保证。

4.2 算法的有效性验证

图4中的虚线为利用穷举法计算得到的层次降化服务组合下的所有QoS评价值dest的概率曲线，其全局最优解为4.3334，本文中，降温系数λ取0.90、0.95、0.99，对该数据分别各执行10次，求得的最优解如表4所示。

表4 模拟退火算法求得的最优目标dest值

其中，当降温系数取0.90和0.95时，找到全局最优解(表4中带下划线的数值，即4.3334)的概率分别为40%和70%，当降温系数增大到0.99或更大时，基本上能以接近1的概率找到全局最优解。在文中给出的问题规模下，计算过程都能在以秒为单位的时间内完成。在不对解空间预先剪枝的情况下，当降温系数小于0.999时，很难收敛到全局最优解。

5 结论

(1)本文在分析了制造任务执行过程层次化特性的基础上，对云制造及其相关领域的服务组合进行了研究，提出了基于层次化的云制造服务组合模型。

(2)通过各层服务组合的QoS属性约束，提前剔除服务组合路径中不满足局部QoS约束的子路径，提高了服务组合路径搜索的效率，避免了一味追求全局QoS最优而忽略局部组合服务QoS过低的问题。同时，也满足了各服务组合子路径不同 QoS约束限制，保证了关重节点的服务质量。

(3)本文提出了层次化的云服务组合方法，分层计算组合服务的QoS值，将服务组合的结构特性均匀分布到服务组合路径的各个层次中，避免因单一考虑整体的结构特性造成在QoS计算时产生偏差。

(4)本文对提出的层次化云制造服务组合模型进行了求解，分析了该模型对算法效率的影响，及服务组合结构均衡性对QoS的影响。

［1］李伯虎，张霖，王时龙，等.云制造——面向服务的网络化制造新模式［J］.计算机集成制造系统，2010，16(1):1-7.

Li Bohu，Zhang Lin，Wang Shilong，et al.Cloud Manufacturing:a New Service－oriented Networked Manufacturing Model［J］.Computer Integrated Manufacturing Systems，2010，16(1):1-7.

［2］陶飞，张霖，郭华，等.云制造特征及云服务组合关键问题研究［J］.计算机集成制造系统，2011，17(3):477-486.

Tao Fei，Zhang Lin，Guo Hua，et al.Typical Characteristics of Cloud Manufacturing and Several Key Issues of Cloud Service Composition［J］.Computer Integrated Manufacturing Systems，2011，17(3):477-486.

［3］刘卫宁，刘波，孙棣华.面向多任务的制造云服务组合研究［J/OL］.计算机集成制造系统，2012［2012-03-16］.http://www.cnki.net/kcms/detail/11.3619.TP.20120201.1556.003.htm l.

［4］Tao Fei，Zhao Dongming，Hu Yefa，et al.Resource Service Composition and Its Optimal Selection Based on ParticlesWarm Optimization in Manufacturing Grid System［J］.IEEE Transactions on Industrial Informatics，2008，4(4):315-327.

［5］Zhang L，Guo H，Tao F，et al.Flexible Management of Resource Service Composition in Cloud Manufacturing［C］//2010 IEEE International Conference on Industrial Engineering＆ Engineering Management(IE＆EM 2010).Macao，2010:2278-2282.

［6］邓水光，黄龙涛，尹建伟，等.Web服务组合技术框架及其研究进展［J］.计算机集成制造系统，2011，17(2):404-412.

Deng Shuiguang，Huang Longtao，Yin Jianwei，et al.Technical Framework for Web Services Composition and Its Progress［J］.Computer Integrated Manufacturing Systems，2011，17(2):404-412.

［7］Cardoso J，Sheth A，Miller J，et al.Quality of Service for Workflows and Web Service Processes［J］.Journal ofWeb Semantics，2004，1(3):281-308.

［8］Zeng L，Benatallah B，Ngu A H H，et al.QoS － aware Middleware for Web Services Composition［J］.IEEE Transactions on Software Engineering，2004，30(5):311-327.

［9］宋泾舸，查建中，陆一平.基于虚拟装配体绑定的产品层次化装配序列生成［J］.北京交通大学学报，2011，35(1):145-149.

Song Jingge，Cha Jianzhong，Lu Yiping.Assembly Sequence Generation for Hierarchical Structure Product Based on Virtual Assembly Binding［J］.Journal of Beijing Jiaotong University，2011，35(1):145-149.

［10］何凤英.基于用户偏好的HTN规划在网格服务组合中的研究［J］.福州大学学报(自然科学版)，2010，38(1):14-19.

He Fengying.The Research of HTN Planning in Grid Services Composition Based on User Preferences［J］.Journal of Fuzhou University(Natural Science Edition)，2010，38(1):14-19.

［11］萧毅鸿，周献中，朱亮，等.基于改进层级任务网络规划的Web服务自动组合［J］.江苏大学学报(自然科学版)，2012，33(1):77-82.

Xiao Yihong，Zhou Xianzhong，Zhu Liang，et al.Automatic Web Services Composition Based on Improved HTN Planning［J］.Journal of Jiangsu University(Natural Science Edition)，2012，33(1):77-82.

［12］李惠林，殷国富，谢庆生，等.面向网络化制造的制造资源组合评价方法研究［J］.计算机集成制造系统，2008，14(5):955-961.

Li Huilin，Yin Guofu，Xie Qingsheng，et al.Manufacturing Resource Combination Evaluation Method Oriented to Networked Manufacturing［J］.Computer Integrated Manufacturing Systems，2008，14(5):955-961.

［13］刘丽兰，俞涛，施战备.制造网格中服务质量管理系统的研究［J］.计算机集成制造系统－CIMS，2005，11(2):284-288.

Liu Lilan，Yu Tao，Shi Zhanbei.Quality of Service Management System in Manufacturing Grid［J］.Computer Integrated Manufacturing Systems － CIMS，2005，11(2):284-288.

［14］刘丽兰，俞涛，施战备.制造网格中基于服务质量的资源调度研究［J］.计算机集成制造系统 －CIMS，2005，11(4):475-480.

Liu Lilan，Yu Tao，Shi Zhanbei.Research on QoS －based Resource Scheduling in Manufacturing Grid［J］.Computer Integrated Manufacturing Systems－CIMS，2005，11(4):475-480.

［15］陶飞，胡业发，张霖.制造网格资源服务优化配置理论与方法［M］.北京:机械工业出版社，2010.

［16］Xu Xun.From Cloud Computing to Cloud Manufacturing［J］.Robotics and Computer－ Integrated Manufacturing，2011，2(1):75-86.

［17］侯伟伟，刘检华，宁汝新，等.基于层次链的产品装配过程建模方法［J］.计算机集成制造系统，2009，15(8):1522-1527.

Hou Weiwei，Liu Jianhua，Ning Ruxin，et al.Product Assembly Process Modeling Method Based on Hierarchy Chain Technique［J］.Computer Integrated Manufacturing Systems，2009，15(8):1522-1527.

［18］Tao Fei，Hu Yefa，Zhao Dongming，et al.Study on Manufacturing Grid Resource Service QoS Modeling and Evaluation［J］.International Journal of Advanced Manufacturing Technology，2009，41(9):1034-1042.