面向过程的资源组合排斥冲突检测方法

孟庆丰 李海波

面向过程的资源组合排斥冲突检测方法

孟庆丰 李海波

(华侨大学计算机科学与技术学院 福建 厦门 361021)

由于云制造环境下服务于业务过程的资源集中可能存在相互排斥的资源，在运行阶段可能会产生资源冲突。针对这种情况，提出了面向业务过程的资源组合排斥冲突检测方法。以工作流模型为基础，提出资源服务链模型(RSCM)并分析在资源服务链模型中可能出现排斥冲突的情况；提出有效子图的概念。最后基于资源服务链模型和有效子图，提出面向过程的资源组合冲突检测算法。实验结果表明，该算法能有效地检测出面向过程的资源组合过程中因资源排斥关系而产生的资源冲突。

云制造 业务过程 资源组合 冲突检测

0 引 言

云制造是一种利用网络和云制造服务平台，按用户需求组织网上制造资源(制造云)，为用户提供各类按需制造服务的一种网络化制造新模式[1]。资源组合是指将云制造环境下能够完成特定制造任务所需的各类制造资源聚集在一起，为资源虚拟化提供支持，从而提高云制造中资源的利用率，实现资源增值[2]。云制造环境下，制造资源因具有多样性、异构性、分散性、协同性和专业性等特点[3-5]，资源之间存在着排斥关系、依赖关系、可替换关系等关系[6]。其中，资源排斥关系可能会导致业务过程执行失败：一方面，在建模阶段，如果将相互排斥的资源组合在一起，在运行阶段，业务过程就可能会产生资源冲突(称为排斥冲突)；另外一方面，在云制造环境下，资源组合往往比较复杂，建模人员很难兼顾到所有资源之间的排斥关系。所以需要给出一种冲突检测方法，在资源组合的模型阶段对其进行检测，提前测出可能存在的排斥冲突，使得模型能够及时被修改，从而减少业务过程执行失败的几率。

针对这种减少制造任务执行失败的几率的问题，当前主要的研究有：利用形式化的方法(Petri网、进程代数和有限自动机等)，通过验证服务状态的可达性、死锁和活锁等来验证服务组合的正确性[7-9]；对工作流语义失败的处理可以事先在模型中描述出来，如WAMO模型[10]；还有一种给资源枷锁的方法，试图避免工作流之间的资源冲突[11]；通过分析约束在工作流模型和运行层次所起的不同作用，识别出无效路径[12]。然而，关于云制造面向过程资源组合中的排斥冲突检测问题，目前的研究较少。

鉴于此，本文展开了对面向过程资源组合的排斥冲突检测问题的探索：首先，给出资源排斥关系和资源服务链模型的定义，并分析面向过程的资源组合模型阶段排斥冲突；然后，引入有效子图的概念，并基于此给出面向过程的资源组合排斥冲突的检测方法。利用本方法，可以在模型阶段提前检测出资源组合中可能存在的排斥冲突，从而降低制造任务执行出错的几率。

1 面向过程的资源组合排斥冲突分析

1.1 资源排斥关系

云制造环境下，服务于业务过程资源集中，可能存在相互冲突的资源。相互冲突的资源不能共同服务于同一个业务过程。由此，下面给出资源排斥关系的定义：

定义1 资源排斥关系。设R为服务于某业务过程的资源集合，∀ri,rj∈R，如果ri和rj之间存在冲突，则称ri与rj在该业务过程中相互排斥，记作Xor(ri,rj)=TRUE。

1.2 资源服务链模型

资源服务链模型RSCM(Resources Service Chain Model)，是指面向过程的资源组合在模型阶段建立的模型。该模型为工作流模型中各个活动定义所需的资源集。首先,借鉴文献[13]，给出工作流模型的定义：

定义3 资源服务链模型。设资源服务链模型为RSCM= (id,wfm,RS,F)，其中id是RSCM的唯一标识；wfm是对应的工作流模型；RS={R1,R2,… ,Rn}，n≥1，其中Ri∈RS表示服务于wfm中某个活动的资源集；F表示由RS到wfm中活动集合A的映射，∀R∈RS,F(R)∈A。

图1描述的是某齿轮制造过程的资源服务链模型，其中wfm表示资源服务链模型中定义的工作流模型，RS表示模型中服务于对应工作流的资源集的集合，RS中的资源集与wfm中的活动一一对应。

图1 某齿轮制造过程的资源服务链模型

1.3 面向过程的资源组合排斥冲突

面向过程的资源组合排斥冲突，是指在模型阶段，RSCM中定义了相互排斥的资源，并且这些相互排斥的资源能够服务于同一个过程实例，使得在运行阶段某个过程实例产生的资源冲突。因此，面向过程的资源组合中排斥冲突有以下两个特点：

(1) RSCM中定义了相互排斥的资源。根据定义3，如果RSCM中相互排斥的资源，其在RSCM中可能的分布情况有：分布于在同一个资源集中；在不同的资源集中。如图2所示，资源r1和r4位于同一个资源集R1中；r31和r34位于不同的资源集R13和R14中。

图2 相互排斥的资源的分布情况

(2) 相互排斥的资源可能服务于同一个过程实例。显然，如果相互排斥的资源位于同一个资源集中，则必然服务于同一个过程实例；如果相互排斥的资源位于不同的资源集中，根据定义2和定义3，在工作流模型控制结构的控制下，服务处于XOR不同分支的活动的资源集，不能共同服务于同一过程实例。如图1所示，资源集R13和R14分别处于一个XOR类型控制块的不同分支上，不能服务于同一过程实例。

2 面向过程的资源组合冲突检测方法

综上所述，对面向过程的资源组合冲突检测，即检测对应的RSCM的各个资源集中是否可能服务于同一个过程实例并且存在相互排斥的资源。首先，要判断RSCM中任意两个资源集是能够服务于同一个过程实例。为此，引入有效子图的概念。

2.1 有效子图

定义4 有效子图。设G=(V,E)是工作流模型wfm的时序关系图，其中V=A,E=S,G′=(V′,E′)为wfm的一个实例的时序关系图，容易证明G′是G的子图，称G′为G的一个有效子图。图3中描述的是某齿轮制造过程的时序关系图G和有效子图ESG。

图3 某齿轮制造过程的时序关系图与有效子图

显然，在wfm的控制下，有效子图G′有如下性质：

(1)as∈V′,ae∈V′。

(2) ∃ai∈V′,aj∈V′，使得∈V′，即G′是连通的，记作Connected(G′) =TRUE。

(3) 符合wfm中控制结构C的语义，即∀c∈C,e∈E′,bi∈B(c),e∈E(c,bi)，如果T(c) =XOR，则bj∈B(c),e′∈E(c,bj)，都有e′∈E′，其中bj≠bi；如果T(c)=AND，则bj∈B(c)，e′∈E(c,bj)，使得e′∈E。记作ValiCtrl(G′,wfm)=TRUE。

由有效子图的定义和性质，给出有效子图的判定规则：

有效子图的判定规则 设G是RSCM中wfm所对应的时序关系图，vs和ve是G的唯一开始节点和结束节点，G′=(V′,E′)是G的子图，并且vs,ve∈V′，如果Connected(G′) =TRUE并且ValiCtrl(G′,wfm)=TRUE，则G′是G的一个有效子图。

根据有效子图的判定规则，给出求wfm对应的时序关系图G中的有效子图算法：

算法1 GetESGSet(wfm,G)

输入：工作流模型wfm

输出：有效子图集ESGSet={G1,G2,…,Gt}

begin

ESGSet=∅;

temp = GetSubG(G,G.vs,G.ve);

for all G′∈temp do

if Connected(G′,wfm)=TRUE and

ValiCtrl(G′,wfm)=TRUE then

end if

end for

return ESGSet;

end GetESGSet

算法GetESGSet实际上通过遍历图，调用GetSubG(G,G.vs,G.ve)找出所包含开始节点G.vs和结束节点G.ve的子图集合，然后根据有效子图的判定规则进行筛选，找出有效子图集ESGSet。算法的时间复杂度为O(n×m)，其中n是所求子图的个数，m是有效子图的活动节点个数。

2.2 面向过程的资源组合排斥冲突检测方法

算法GetESGSet求出了有效子图集ESGSet，根据定义3和定义4，可以通过验证有效子图中是否存对应的活动节点，来判断对应的资源集能否服务于同一个过程实例。由此，给出算法2，判断工作流模型中任意两个活动节点是否在同一个有效子图中。

算法2 InSameESG(ESGSet,v1,v2)

输入：ESGSet和wfm中任意的v1和v2

输出：布尔值

begin

for all G′∈ESGSet do

if Search(G′,v1) = TRUE and

Search (G′,v2) = TRUE then

return TRUE;

end if

end for

return FALSE;

end InSameESG

在算法InSameESG(ESGSet,v1,v2)中，Search(G′,v1)用于判断节点v1是否存在于图G′中。算法中时序关系图G是邻接表结构，该算法的时间复杂度最好的情况为O(1)，最坏为O(t×(n+e))，其中n为ESGSet中平均每个有效子图的活动节点个数，e为边的平均个数，t为ESGSet中元素的个数。

根据给定的资源排斥关系集合Xor，给出算法3，判断资源服务链模型中定义的任意两个资源集是否存在相互排斥的资源。

算法3 ExistXorRes(Xor,Ri,Rj)

输入：资源集Ri、Rj和排斥关系集Xor

输出：布尔值

begin

for all r1∈Ri,r2∈Rj,r1≠r2 do

if ∈Xor then

return TRUE;

end if

end for

return FLASE;

end ExistXorRes

在算法ExistXorRes(Xor,Ri,Rj)中，Xor是当前业务过程的资源排斥关系集合。该算法的时间复杂度为O(m×n)，m与n分别是Ri和Rj中的资源数量。

综上，下面给出面向过程的资源组合排斥冲突检测算法，其核心思想是：遍历RSCM中的RS，对于能够服务于同一个过程实例的资源集，判断其中是否存在相互排斥的资源，如果存在，则返回存在排斥冲突的两个资源集。在给出算法之前，首先给出算法中可能出现的基本定义和操作：Xor是某业务过程中排斥关系的集合；根据资源服务链模型获取RS—GetRS(RSCM)；获取资源服务链模型对应的工作流模型wfm—GetWfm(RSCM)；获取工作流模型的时序关系图—GetTG(wfm)。

算法4 XorConfDetection(RSCM)

输入：RSCM和资源排斥关系集Xor

输出：存在排斥冲突的位置集合Addr

begin

wfm=GetWfm(RSCM);

G=GetTG(wfm);

ESGSet=GetESGSet(wfm,G);

RS=GetRS(RSCM);

Addr=∅;

for all RiRS,RjRS do

if InSameESG(ESGSet,F(Ri),F(Rj))=TRUE

and ExistXor (Xor,Ri,Rj)=TRUE then

Addr←Addr∪{};

end if

end for

return Addr;

end XorConfDetection

3 实例分析

以云制造环境下面向某种齿轮制造过程的资源组合为例。该齿轮生产加工过程的RSCM如图1所示，各个业务活动和活动所需的资源集如表1所示(对于模型中每个活动所需资源的详细信息，参见文献[15])。下面应用本文提出的冲突检测方法来对该模型进行检测。

表1 活动及其资源集

现已知该业务过程的排斥关系集合Xor={,,,,,,}。设rscm为该业务过程的资源服务链模型，调用面向过程资源组合的排斥冲突检测算法XorConfDetection(rscm)，对rscm进行排斥冲突检测，其执行步骤如下：

步骤1 由算法GetESGSet求出的有效子图集ESGSet={G1,G2,G3,G4,G5,G6}，如图4所示。

图4 所有的有效子图

步骤2 遍历rscm中所有的资源集，由InSameESG和ExistXorRes，求出rscm中所有存在排斥冲突的资源集。所得检测结果如表2所示。

表2 检测结果

实例分析：

(1) 如表2中所示，在rscm中存在排斥冲突的资源集，应该修改rscm，以减少过程执行失败的几率。

(2) 除了表2中所示的存在相互排斥资源的资源集之外，还有一些资源集中存在相互排斥的资源，如r31和r34。然而，由于这些资源集在运行阶段，不会服务于同一个过程实例，所以不存在排斥冲突。

(3) 冲突集的大小对于该算法的效率有直接影响，对于同一个业务过程，给定的冲突集越大算法准确率越高。

(4) 资源排斥关系是不是一成不变的，随着科技的发展，有些制造资源可能不会相互排斥了，所以需要经常维护排斥集。

(5) 可以通过对大量已经执行的业务过程的挖掘，找出更多的资源排斥关系，不仅可以对面向过程资源组合的排斥冲突检测提供决策支持，更能减少业务过程执行失败的几率。

4 结 语

本文通过引入资源排斥关系和资源服务链模型的定义，并分析在资源服务链模型中可能存在资源冲突情况，然后引入有效子图，进而给出冲突检测算法，并通过实例验证了算法的有效性。本方法可以在面向过程资源组合的建模阶段，提前检测出可能的资源排斥冲突，能够降低业务过程执行失败的几率。

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

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

[3] 张霖,罗永亮,范文慧,等. 云制造及相关先进制造模式分析[J]. 计算机集成制造系统,2011,17(3): 458-468.

[4] 张霖,罗永亮,陶飞,等. 制造云构建关键技术研究[J]. 计算机集成制造系统,2010,16(11): 2510-2520.

[5] 任磊,张霖,张雅彬,等. 云制造资源虚拟化研究[J]. 计算机集成制造系统,2011,17(3): 511-518.

[6] 郏维强,冯毅雄,谭建荣,等. 制造资源混合粒度优化组合方案求解技术[J]. 计算机辅助设计与图形学学报,2012,24(3): 281-289.

[7] 陈丁剑,吴健,马满福,等. 基于Petri网的Web服务组合建模[J]. 计算机科学,2006,33(5): 128-135.

[8] 廖军,谭浩,刘锦德. 基于Pi-演算的Web服务组合的描述和验证[J]. 计算机学报,2005,28(4): 635-643.

[9] 雷丽晖,段振华. 一种基于扩展有限自动机验证组合Web服务的方法[J].软件学报. 2007,18(12): 2980-2990.

[10] Ellis C A,Keddara K,Rozenberg G. Dynamic change within workflow systems[C]//Proceedings of International Conference on Organis Computer System. New York,NY,USA: ACM Press,1995: 10-21.

[11] 胡乃静,顾宁,施伯乐. 基于语义约束的资源工作流并发正确性保证[J].计算机研究与发展,2003,40(5): 712-719.

[12] 李海波,郭春丽,战德臣. 基于约束满足性的工作流执行成功率提高方法[J].计算机集成制造系统,2010,16(6): 1300-1306.

[13] 李海波. 工作流模型复杂控制结构构造方[J]. 计算机科学. 2012,39(11),106-110,136.

[14] Bae J,Caverlee J,Liu Ling, et al. Process mining by measuring process block similarity[C]//Business Process Management Workshops. 2006: 141-252.

[15] 《齿轮制造手册》编写委员会. 齿轮制造手册[M]. 北京: 机械工业出版社,1997: 3-11.

PROCESS-ORIENTED COLLISION DETECTION METHOD FOR RESOURCES COMPOSITION EXCLUSION

Meng Qingfeng Li Haibo

(CollegeofComputerScienceandTechnology,HuaqiaoUniversity,Xiamen361021,Fujian,China)

Because of the possible existence of mutually exclusive resources in resource concentration that serving the business process in cloud manufacturing environment,resource collisions may occur in running phase. To cope with this problem,we proposed a business process-oriented collision detection method for resources composition exclusion. Based on workflow model,we proposed the resources service chain model (RSCM) and analysed the situation of collision in exclusion possibly occurring in RSCM; we proposed the concept of effective sub-graph as well. Finally,based on RSCM and effective sub-graph,we proposed the business process-oriented collision detection algorithm for resources composition exclusion. Experimental results showed that the algorithm could effectively detect the resource collision caused due to resource exclusion relations in process-oriented resource composition process.

Cloud manufacturing Business process Resources composition Collision detection

2014-10-16。福建省自然科学基金项目(2012J012 72);厦门市科技计划项目(3502z20110013);泉州市科技计划项目(2011G5);华侨大学中央高校基本科研业务费项目(JB-ZR1147)。孟庆丰，硕士生，主研领域：服务计算与云计算。李海波，副教授。

TP391

A

10.3969/j.issn.1000-386x.2016.04.006