面向過程的資源組合排斥沖突檢測方法

孟慶豐 李海波

面向過程的資源組合排斥沖突檢測方法

孟慶豐 李海波

(華僑大學計算機科學與技術學院 福建 廈門 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