莫 啟,代 飛,笪 建,朱 銳,謝仲文,李 彤

1(云南大學 軟件學院,云南 昆明 650091)

2(云南省軟件工程重點實驗室(云南大學),云南 昆明 650091)

3(西南林業(yè)大學 大數(shù)據(jù)與智能工程學院,云南 昆明 650091)

4(淮安開放大學 信息工程系,江蘇 淮安 223001)

隨著全球經(jīng)濟化的發(fā)展和企業(yè)信息化程度的不斷提高,企業(yè)的經(jīng)營模式發(fā)生了重大的變化,企業(yè)的業(yè)務(wù)活動已從企業(yè)內(nèi)單目標為導向的獨立發(fā)展模式發(fā)展成為跨企業(yè)多目標合作的協(xié)同模式[1].在現(xiàn)代商業(yè)環(huán)境下,沒有一個企業(yè)是孤立的[2,3].企業(yè)作為參與者參與到協(xié)作中,在協(xié)作過程中,它們彼此進行交互以完成特定業(yè)務(wù)功能.近年來,隨著Internet 成為主流的計算平臺,尤其是面向服務(wù)計算(service-oriented computing,簡稱SOC)的快速興起,使得不同組織業(yè)務(wù)過程間的交互成為可能,如企業(yè)信息系統(tǒng)[4]、電子商務(wù)[5]等.為實現(xiàn)共同的商業(yè)目標,每個組織的業(yè)務(wù)過程通常需要跨越組織邊界,與其他組織的業(yè)務(wù)過程進行交互和協(xié)作以形成相對穩(wěn)定的過程視圖.學術(shù)界和工業(yè)界稱這種存在復(fù)雜交互關(guān)系的業(yè)務(wù)過程為協(xié)同業(yè)務(wù)過程[6].

針對協(xié)同業(yè)務(wù)過程,國內(nèi)外研究者提出多種建模方法.歸納起來,這些建模方法可分為兩類:(1)自頂向下建模方法[7,8].該方法要求首先給出協(xié)同全局契約,然后定義映射規(guī)則并以此為基礎(chǔ)從契約中生成每個組織的業(yè)務(wù)過程;(2)自底向上建模方法[9].該方法允許組織獨立地定義各自的業(yè)務(wù)過程,之后以此為基礎(chǔ)直接構(gòu)建具有協(xié)同功效的協(xié)同業(yè)務(wù)過程.由于受限于映射規(guī)則集,利用自頂向下建模方法通常僅能建立具有有限結(jié)構(gòu)形態(tài)業(yè)務(wù)過程,靈活性和普適性不足[7,8].因此,本文關(guān)注自底向上建模方法.

然而,自底向上建模方法中的業(yè)務(wù)過程由不同組織開發(fā),無法在設(shè)計階段就預(yù)見其潛在的所有交互可能,因此在實際協(xié)作中,參與協(xié)作的業(yè)務(wù)過程間可能存在不一致(如死鎖等),無法保證協(xié)同業(yè)務(wù)過程正確地實施.因此,對協(xié)同業(yè)務(wù)過程的正確性(正確性可根據(jù)實際需要定義,如合理性等,在此不作區(qū)分)進行分析是當前業(yè)務(wù)過程管理(business process management,簡稱BPM)領(lǐng)域內(nèi)的研究熱點.

針對協(xié)同業(yè)務(wù)過程正確性分析,國內(nèi)外學者做了大量工作[9,10].這些研究工作主要圍繞正確性檢測方法開展.該方法先構(gòu)建形式化的協(xié)同業(yè)務(wù)過程并定義正確性約束(如無死鎖、無活鎖及未指定接收等),然后采用某種形式的驗證技術(shù)(如模型檢測等)在協(xié)同業(yè)務(wù)過程中檢測相容性是否滿足.正確性檢測方法通常具有檢測過程自動化,不需要人工干預(yù),且在檢測失敗時能夠給出診斷信息,便于業(yè)務(wù)設(shè)計人員發(fā)現(xiàn)并修正錯誤.但其不足是,若協(xié)同業(yè)務(wù)過程中存在多處不正確,則需要經(jīng)過多次檢測,且在每次檢測后都需要對協(xié)同業(yè)務(wù)過程重新調(diào)整.重復(fù)地進行檢測及調(diào)整使得協(xié)同業(yè)務(wù)過程正確性分析復(fù)雜且耗時.

一種替代方法是正確性修正方法.該方法關(guān)注早期設(shè)計階段,根據(jù)正確性約束對業(yè)務(wù)過程內(nèi)部結(jié)構(gòu)進行修改以自動構(gòu)建滿足正確性約束的業(yè)務(wù)過程[11,12].這方面的研究工作較少,且大多關(guān)注組織內(nèi)單個業(yè)務(wù)過程,能夠用于協(xié)同業(yè)務(wù)過程正確性修正方法[13-15]也存在如下不足:(1)修正后的協(xié)同業(yè)務(wù)過程是集中式的,與協(xié)同業(yè)務(wù)過程的實際特征(如自治、分布及面向流程協(xié)作等)[16]不符;(2)這些方法基于過程挖掘技術(shù)[17]而提出,不能夠保證修正協(xié)同業(yè)務(wù)過程中含有修正前協(xié)同業(yè)務(wù)過程中的所有完整軌跡(即完整的簡單路徑對應(yīng)活動執(zhí)行序列),還可能引入隱藏軌跡(即不屬于修正前協(xié)同業(yè)務(wù)過程中的其他軌跡),這需要進行額外確認;(3)協(xié)同業(yè)務(wù)過程實質(zhì)上是由多個業(yè)務(wù)過程構(gòu)成的并發(fā)交互系統(tǒng),復(fù)雜程度高[16].直接利用這些方法對其進行修正存在修正效率低下的問題.例如,我們課題組最近的工作[13]即結(jié)合Petri 網(wǎng)和過程挖掘的相關(guān)理論,提出了一種針對協(xié)同業(yè)務(wù)過程修正方法.但是,該方法構(gòu)建的協(xié)同業(yè)務(wù)過程存在中心流程(即只能通過該中心流程協(xié)調(diào)原有業(yè)務(wù)過程執(zhí)行).同時,修正協(xié)同業(yè)務(wù)過程與修正前協(xié)同業(yè)務(wù)過程中含有的所有完整軌跡也可能不一致,且存在執(zhí)行失敗的情況.這在后文的實驗部分將給出詳細闡述.

針對上述問題,本文采用標號遷移系統(tǒng)LTS(labeled transition system)來描述業(yè)務(wù)過程,并將其并發(fā)組合建模協(xié)同業(yè)務(wù)過程.在考慮活動同步及異步交互的情況下,通過將協(xié)同業(yè)務(wù)過程的行為抽象為簡單路徑,在此基礎(chǔ)上,提出了針對部分正確的協(xié)同業(yè)務(wù)過程修正方法.該修正方法能夠確保修正協(xié)同業(yè)務(wù)過程與修正前的協(xié)同業(yè)務(wù)過程中含有的軌跡相一致,且修正協(xié)同業(yè)務(wù)過程具有自治、分布及面向流程組合等特性.

本文主要貢獻如下:

(1)在考慮活動同步及異步交互的情況下,提出了簡單路徑用來刻畫協(xié)同業(yè)務(wù)過程的行為,并提出將完整的簡單路徑合并為核的算法.本質(zhì)上,核中包含了修正前的協(xié)同業(yè)務(wù)過程中所有正確的任務(wù)執(zhí)行系列(即完整軌跡).以核為基礎(chǔ),提出了將其映射為修正業(yè)務(wù)過程的方法,將所有的修正業(yè)務(wù)過程并發(fā)組合建立修正的協(xié)同業(yè)務(wù)過程;

(2)理論上證明了修正協(xié)同業(yè)務(wù)過程與修正前協(xié)同業(yè)務(wù)過程中含有的軌跡是一致的,從而避免了額外確認,降低了修正代價;

(3)通過實驗分析得出:相對已有方法,在考慮協(xié)同業(yè)務(wù)過程實際特征(如自治、分布及面向流程組合等)的情況下,本文方法可實現(xiàn)更加有效的正確性修正并能夠極大地提高修正效率,縮短修正時間.

本文第1 節(jié)給出方法概覽.第2 節(jié)給出協(xié)同業(yè)務(wù)過程定義.第3 節(jié)對正確性進行分析.第4 節(jié)對正確性修正方法進行討論.第5 節(jié)通過實驗對本文方法的有效性及效率進行評估.第6 節(jié)為相關(guān)工作.第7 節(jié)為全文總結(jié).

1 方法概述

本文正確性修正方法提出是建立在如下一種事實,即采用自底向上建模方法在建立協(xié)同業(yè)務(wù)過程中無法預(yù)見其所有潛在的交互可能,從而導致建立模型中可能存在異常(如死鎖等),這將嚴重地阻礙業(yè)務(wù)過程間的正確協(xié)作.本文提出的正確性修正方法框架如圖1 所示.

Fig.1 Overview of correctness repair圖1 正確性修正方法概覽

具體地,該正確性修正方法由如下兩個階段組成.

(1)建模階段.參與組織首先獨立地采用LTS 建模各自業(yè)務(wù)過程,并將這些業(yè)務(wù)過程并發(fā)組合建立協(xié)同業(yè)務(wù)過程;之后參與組織間經(jīng)協(xié)商,確定期望的系統(tǒng)正確性,本文以弱合理[11]定義;

(2)分析階段.分析階段將協(xié)同業(yè)務(wù)過程和正確性約束輸入,自動構(gòu)建具有正確性的協(xié)同業(yè)務(wù)過程.分析階段包含如下4 個具體步驟.

(a)基于弱合理將協(xié)同業(yè)務(wù)過程行為抽象為完整的簡單路徑;

(b)將抽象的完整簡單路徑合并以構(gòu)建核,核中包含修正前的協(xié)同業(yè)務(wù)過程中所有正確的任務(wù)執(zhí)行系列;

(c)將核隱藏、最小化后生成每個參與組織的中間業(yè)務(wù)過程;

(d)將中間業(yè)務(wù)過程協(xié)調(diào)映射為修正業(yè)務(wù)過程,通過將修正業(yè)務(wù)過程并發(fā)組合建立修正協(xié)同業(yè)務(wù)過程.

下面將對圖1 所示的正確性修正方法進行詳細的闡述.

2 協(xié)同業(yè)務(wù)過程定義

為了實現(xiàn)協(xié)同業(yè)務(wù)過程與需求一致性檢測,參與組織需要首先對協(xié)同業(yè)務(wù)過程及期望需求進行建模.

2.1 協(xié)同業(yè)務(wù)過程建模

對協(xié)同業(yè)務(wù)過程進行形式定義是實現(xiàn)協(xié)同業(yè)務(wù)過程正確性修正的基礎(chǔ).本節(jié)采用標號遷移系統(tǒng)對業(yè)務(wù)過程建模,并將其并發(fā)組合形成協(xié)同業(yè)務(wù)過程.

業(yè)務(wù)過程由參與組織活動集和建立其上的控制流組成,它由該組織自治管理,是構(gòu)建協(xié)同業(yè)務(wù)過程的基礎(chǔ).本文采用標號遷移系統(tǒng)建模業(yè)務(wù)過程.

定義1(業(yè)務(wù)過程).業(yè)務(wù)過程是一個遷移系統(tǒng)BP=(S,s0,F,A,Δ),其中,

(1)S為狀態(tài)集合;

(2)s0∈S為初始狀態(tài);

(3)F?S為終止狀態(tài)集合;

(4)A=Al∪Ai為活動集合,其中,Al為本地活動集合,Ai為交互活動集合;

(5)Ai=Asi∪Aai,其中,Asi為同步交互活動集合,Aai為異步交互活動集合;

(6)Aai=Aas∪Aar,其中,Aas為異步發(fā)送活動集合,Aar為異步接收活動集合;

(7)Δ?S×A×S為狀態(tài)遷移關(guān)系集,用來刻畫活動間執(zhí)行順序,即控制流.對于?(r,a,s)∈Δ,記為遷移,表示BP在執(zhí)行活動a后由狀態(tài)r轉(zhuǎn)換為狀態(tài)s.

特別地,稱BP是確定的當且僅當對于其中的任意兩條遷移,若a1=a2,則s1=s2.本文中所討論的業(yè)務(wù)過程均默認是確定的.對于任意同步交互活動a∈Asi,則協(xié)同業(yè)務(wù)過程中至少存在一個其他業(yè)務(wù)過程BP′,BP′的同步交互活動集合中包含a;而對于任意異步交互活動a∈Aai,若a∈Aas,則a記為!m,表示發(fā)送消息m的活動,“!”表示發(fā)送動作,若a∈Aar,則a記為?m,表示接收消息m的活動,“?”表示接收動作.對于業(yè)務(wù)過程BP,其發(fā)送消息集為={m|!m∈Aas},而接收消息集為={m|?m∈Aar}.

采用標號遷移系統(tǒng)建模業(yè)務(wù)過程有如下3 個方面的原因:(1)標號遷移系統(tǒng)具有直觀圖形表示,可以形式化地刻畫系統(tǒng)的行為,是系統(tǒng)行為深入分析的可靠工具[17];(2)遷移系統(tǒng)作為一種中間表示,任意具有執(zhí)行語義的過程模型(如利用Petri 網(wǎng)或進程代數(shù)建模過程模型)都可以方便地轉(zhuǎn)換為本文中以標號遷移系統(tǒng)描述業(yè)務(wù)過程[17];(3)便于后文中映射生成修正業(yè)務(wù)過程.特別需要說明的是,由于Petri 網(wǎng)具有直觀圖形化表示,嚴格形式語義和豐富的形式分析技術(shù),被廣泛地用于業(yè)務(wù)過程建模和分析中.本文沒有采用Petri 網(wǎng)進行協(xié)同業(yè)務(wù)過程修正的根本原因是在具體修正中需要首先生成協(xié)同業(yè)務(wù)過程完整簡單路徑,然后合成核(本質(zhì)上是標號遷移系統(tǒng)),最后通過對核進行協(xié)調(diào)映射生成每個修正業(yè)務(wù)過程(也為標號遷移系統(tǒng)).而若采用Petri 網(wǎng)建模協(xié)同業(yè)務(wù)過程,則具體修正仍然需要對應(yīng)到標號遷移系統(tǒng)上開展,不夠直觀.

以業(yè)務(wù)過程為基礎(chǔ)可建模協(xié)同業(yè)務(wù)過程.本質(zhì)上,協(xié)同業(yè)務(wù)過程可視為由多個業(yè)務(wù)過程構(gòu)成的并發(fā)交互系統(tǒng).進程代數(shù)能夠自然地以模塊的方式構(gòu)建復(fù)雜的交互并發(fā)系統(tǒng)[18],借鑒其思想,本文提出并發(fā)操作符概念.并發(fā)操作符提供了一種通過組合業(yè)務(wù)過程構(gòu)建協(xié)同業(yè)務(wù)過程方法.

定義2(協(xié)同業(yè)務(wù)過程).設(shè)參與協(xié)同的業(yè)務(wù)過程為BP1,…,BPn,由這n個業(yè)務(wù)過程構(gòu)成的協(xié)同業(yè)務(wù)過程記為CBP=BP1||…||BPn.

特性需要說明的是,定義2 只是將多個業(yè)務(wù)過程在形式上列為并發(fā)關(guān)系,CBP中的活動執(zhí)行及交互可按實際場景來定義.本文同時考慮活動間同步交互及基于消息通信的活動間異步交互,參見定義5.

對于任意協(xié)同業(yè)務(wù)過程,其狀態(tài)用格局來表示.它由每個參與組織的運行狀態(tài)及所配置的先進先出消息隊列組成向量表示,其形式定義如下.

定義3(格局).協(xié)同業(yè)務(wù)過程CBP狀態(tài)表示為一個格局c=〈s1,Q1,…,sn,Qn〉,其中,?i∈[1..n],si為業(yè)務(wù)過程BPi的運行狀態(tài);Qi為業(yè)務(wù)過程BPi的先進先出消息隊列,用來存儲其接收消息,本文中Qi的長度默認為無窮.

特別地,CBP的初始格局記為c0=〈s01,NIL,…,s0n,NIL〉,其中,?i∈[1..n],s0i為BPi的初始狀態(tài),且其消息隊列為空,即為NIL;CBP的終止格局記為ce=〈se1,NIL,…,sen,NIL〉,其中,?i∈[1..n],sei為BPi的終止狀態(tài),且其消息隊列為空,表示所有的消息均被接收.

可對格局中的運行狀態(tài)及消息隊列進行重置,形式定義如下.

定義4(格局重置).設(shè)格局c=〈s1,Q1,…,sn,Qn〉,將業(yè)務(wù)過程BPi的運行狀態(tài)由si重置為s′i,記為,而將BPi的消息隊列由Qi重置為Q′i,記為.

在協(xié)同業(yè)務(wù)過程中,活動執(zhí)行除了受到本地控制流的約束外,還受到其他業(yè)務(wù)過程中活動執(zhí)行情況的影響.歸納起來,可分為如下3 種情況.

1)若a∈Al,則活動a執(zhí)行僅受到本地控制流的影響;

2)若a∈Asi,則活動a執(zhí)行除了受到本地控制流的影響外,還需要所有含有同步交互活動a的業(yè)務(wù)過程同時參與完成;

3)若a=!m,則活動a執(zhí)行除了受到本地控制流的影響外,還受到其他需要接收消息m的業(yè)務(wù)過程的消息隊列Q的影響,即Q不滿,且存在接收消息m的業(yè)務(wù)過程BP.在發(fā)送消息m之后,消息m被添加至BP消息隊列的尾部;而若a=?m,則活動a執(zhí)行除了受到本地控制流的影響外,還受到自身消息隊列Q的影響,即Q不空,且Q的第1 個元素是消息m.在接收消息m之后,消息m從Q的頭部移除.

根據(jù)上述對活動執(zhí)行情況的分析,我們定義協(xié)同業(yè)務(wù)過程點火規(guī)則.

定義5(點火規(guī)則).設(shè)CBP=BP1||BP2||…||BPn為一個協(xié)同業(yè)務(wù)過程,其格局為c=〈s1,Q1,…,sn,Qn〉,則其點火規(guī)則定義如下.

(1)若a∈Al,則,當且僅當;

(2)若a∈Asi,則,當且僅當;

(3)若a=!m,則,當且僅當(是Qj的長度);

(4)若a=?m,則,當且僅當.

特別需要說明的是,給定協(xié)同業(yè)務(wù)過程CBP,若利用點火規(guī)則可產(chǎn)生無窮個格局,則稱CBP具有無窮狀態(tài)空間,否則稱其具有有窮狀態(tài)空間.本文關(guān)注具有有窮狀態(tài)空間的協(xié)同業(yè)務(wù)過程.

基于點火規(guī)則,我們可定義協(xié)同業(yè)務(wù)過程的行為,表示為路徑.下面給出幾個與路徑相關(guān)的定義.

定義6(路徑).給定協(xié)同業(yè)務(wù)過程CBP,其行為表示為路徑,是CBP的格局和活動(即本地活動或交互活動)組成的有窮或無窮序列.對于任意路徑σ,其形如:,其中,?i∈[1..n],遷移符合定義5 給出的點火規(guī)則,ci為CBP的格局,c0為初始格局.

定義7(路徑的軌跡).對于任意路徑r,r=,則將r中的活動依次連接,得到活動執(zhí)行序列l(wèi)=a0∧a1…an-1∧an∧…稱為r的跡,表示為trace(r).

特別地,若格局c可通過執(zhí)行跡l遷移至格局c′,則記為.

定義8(路徑一致).設(shè)為兩條有窮路徑,稱rp和rq一致,記為rp=rq,當且僅當rp的跡與rq的跡相同.

3 正確性分析

為了對協(xié)同業(yè)務(wù)過程進行修正,首先需要明確協(xié)同業(yè)務(wù)過程的正確性.目前,研究者提出多種針對協(xié)同業(yè)務(wù)過程的正確性標準,其中,以合理性[9]及其變體(如弱合理[11]等)應(yīng)用最為廣泛.由于合理性主要用于定義組織內(nèi)業(yè)務(wù)過程的正確性且較為嚴格[11],因此本文利用弱合理性定義協(xié)同業(yè)務(wù)過程的正確性.

定義9(弱合理).給定協(xié)同業(yè)務(wù)過程CBP,c0和ce分別為初始格局和終止格局,稱CBP是弱合理的,當且僅當對于從c0可達的任意格局c,存在跡σ,使得.

從定義9 可以看出,弱合理性要求從初始格局可達的任意格局都能夠到達終止格局.這可確保每個業(yè)務(wù)過程均能到達終止狀態(tài),因此可避免協(xié)同業(yè)務(wù)過程運行中可能出現(xiàn)的死鎖和活鎖等情形.同時,終止格局(見定義3)要求每個業(yè)務(wù)過程的消息隊列均為空,能夠確保協(xié)同中產(chǎn)生的消息均可合理地被接收.

本文中的正確性分析是基于路徑開展的.實際中的協(xié)同業(yè)務(wù)過程通常含有循環(huán)結(jié)構(gòu),循環(huán)結(jié)構(gòu)將導致路徑數(shù)量和長度變?yōu)闊o窮,進而導致正確性檢測無法判定.為了將問題收縮至有窮范圍,同時記錄下必要的循環(huán)結(jié)構(gòu),本文定義簡單路徑如下.

定義10(簡單路徑).設(shè)為協(xié)同業(yè)務(wù)過程CBP中的一條路徑,稱σ是簡單路徑,當且僅當對于任意格局ci在σ中最多出現(xiàn)2 次,即對于?ci,N={cj|ci=cj∧j≠i}∧|N|≤2.

特別地,簡單路徑對應(yīng)的軌跡稱為簡單軌跡.下面給出算法1 用來計算一個協(xié)同業(yè)務(wù)過程中的簡單路徑.

Algorithm1.Generating simple routes.

本質(zhì)上,算法1 是一種深度優(yōu)先搜索算法.設(shè)CBP中格局數(shù)為n,且在搜索過程中每個格局入棧次數(shù)為{c1,…,cn},則算法1 的時間復(fù)雜度為.進一步地,對于?i∈[1..n],根據(jù)定義10 可知,ci最大值為2(對應(yīng)算法第8 行),即ci存在于循環(huán)結(jié)構(gòu)中被記錄2 次.因此,算法1 在最壞情況下的時間復(fù)雜度為O(2n2).特別地,由于本文關(guān)注具有有窮狀態(tài)空間的協(xié)同業(yè)務(wù)過程,即其中含有的格局數(shù)是有窮的.因此,可推出算法1 是可以終止的,進而可推出其中含有的簡單路徑數(shù)量及長度也是有窮的.

定義11(完整的簡單路徑).設(shè)為協(xié)同業(yè)務(wù)過程CBP中的一條簡單路徑,稱σ為完整簡單路徑,當且僅當cn為終止格局.

特別地,完整的簡單路徑所對應(yīng)的軌跡稱為完整軌跡.由弱合理及簡單路徑,對協(xié)同業(yè)務(wù)過程進行合理性分析可轉(zhuǎn)換為對簡單路徑的分析,見定理1.

定理1.設(shè)R為協(xié)同業(yè)務(wù)過程CBP中所有的簡單路徑集合,若對于任意簡單路徑r∈R,r是完整簡單路徑,則CBP是弱合理的.

證明:設(shè)cm為從c0出發(fā)且經(jīng)跡σ到達的任意一個格局,則可推出存在路徑,滿足trace(r)=σ,分下面兩種情況加以討論.

1)若cm為終止格局,則推出存在空跡t,使得.

2)若cm為非終止格局,再分下面兩種情況加以討論.

(1)若r滿足?1≤i,j≤m∧j≠i,ci≠cj,則可知r為某條簡單路徑ra∈R的前綴片段.由于rs是完整路徑,則可知必定存在跡t,使得.

(2)若r存在片段,滿足ci=cj=ck∧?i

綜合上述(1)和(2)及定義9,結(jié)論成立.證畢. □

基于定理1,設(shè)R為協(xié)同業(yè)務(wù)過程CBP中所有的簡單路徑集合,R中所有的完整簡單路徑為Rc.若|Rc|=0,表示R中每條簡單路徑均不是完整路徑,則稱CBP是完全不正確的;若|Rc|≠0∧|Rc|<|R|,表示R中有部分簡單路徑是完整簡單路徑,則稱CBP是部分正確的;若|Rc|=|R|,表示R中所有的簡單路徑均是完整路徑.根據(jù)定理1 可知,CBP滿足弱合理性,稱CBP是完全正確的.

只有在部分正確的情況下,才可能且有必要對協(xié)同業(yè)務(wù)過程進行修正.以獲得的所有完整簡單路徑為基礎(chǔ),下面詳細地闡述針對協(xié)同業(yè)務(wù)過程的修正方法.

4 正確性修正

針對部分正確的協(xié)同業(yè)務(wù)過程,其修正可分3 步進行:(1)將所有完整的簡單路徑合并為核;(2)將核映射為修正業(yè)務(wù)過程;(3)將產(chǎn)生的修正業(yè)務(wù)過程利用并發(fā)操作符組合,構(gòu)建修正協(xié)同業(yè)務(wù)過程.

對于部分正確的協(xié)同業(yè)務(wù)過程而言,根據(jù)第3 節(jié)中的闡述可知,其中必定含有完整的簡單路徑(即能夠正確地執(zhí)行完成路徑)和非完整的簡單路徑(即導致協(xié)同業(yè)務(wù)過程執(zhí)行失敗路徑).為了捕獲其中含有的所有正確路徑(即完整的簡單路徑),本文提出了核的概念.本質(zhì)上,對于一個部分正確的協(xié)同業(yè)務(wù)過程,它對應(yīng)的核是含有其中所有完整簡單路徑的一個遷移系統(tǒng).

定義12(核).核是五元組c=(C,c0,Ce,A,Δ),其中,

(1)C為格局集合;

(2)c0∈C為初始格局;

(3)Ce∈C為終止格局集;

(4)A為活動集合;

(5)Δ∈C×A×C為格局遷移關(guān)系集合.

特別地,對于任意核c,其行為也可由路徑表示.對于c中任意路徑,滿足?i∈[1..n],,當且僅當(ci-1,ai,ci)∈Δ.

下面提出算法2,用來將所有完整的簡單路徑合并以構(gòu)建核.

Algorithm2.Generating core.

算法2 的基本思想是通過將完整的簡單路徑中的格局集和格局遷移集分別設(shè)置為核中的格局集和格局遷移集,從而構(gòu)建核.算法2 的時間復(fù)雜度取決于完整的簡單路徑的條數(shù)及其長度.不妨設(shè)完整的簡單路徑條數(shù)為m,每條完整的簡單路徑的長度為n,則算法2 的時間復(fù)雜度為O(m×n).

特別需要說明的是:由于完整的簡單路徑中記錄了循環(huán)結(jié)構(gòu),因此最終構(gòu)建的核中循環(huán)結(jié)構(gòu)不會丟失.由此可以推斷,對于部分正確的協(xié)同業(yè)務(wù)過程,通過算法2 生成的核中只含有此協(xié)同業(yè)務(wù)過程中所有完整的簡單路徑,見定理2.

定理2.給定部分正確的協(xié)同業(yè)務(wù)過程CBP,CBP中含有的所有完整的簡單路徑記為Rc.設(shè)c是根據(jù)Rc構(gòu)建的核,則對于CBP中任意完整的簡單路徑rc,c中也存在rc,反之亦然.

1)若rc滿足?1≤i,j≤n∧j≠i,ci≠cj,可知rc為完整的簡單路徑,推出rc∈Rc.由算法2 可知,由Rc構(gòu)建后的c中必定存在格局遷移關(guān)系集合{(c0,a1,c1),…,(cn-1,an,cn)}?Δ,由此格局遷移關(guān)系可生成路徑rc.

2)若rc中存在路徑片段,滿足ci=cj=ck∧?ig),使得cu=cv,r′c中存在,由算法2 可知,(cg-1,ag,cg)∈Δ.因此,從左至右掃描rc,對于非循環(huán)結(jié)構(gòu)路徑片段,r′c中存在,則可推出其可由c中(cg-1,ag,cg)∈Δ生成,而對于多次重復(fù)的循環(huán)結(jié)構(gòu),r′c中存在,則可推出其可由{(ci,ai+1,ci+1),…,(cj-1,aj,ci)}?Δ生成,重復(fù)這一過程,最終可由c生成rc.

必要性.可按類似方式證明,限于篇幅,這里從略. □

給定部分正確協(xié)同業(yè)務(wù)過程CBP=BP1||BP2||…||BPn,根據(jù)算法2 生成的CBP的核為c.本文中,對CBP進行修正目標是要保證CBP中完整簡單路徑對應(yīng)軌跡可在修正后的協(xié)同業(yè)務(wù)過程CBPr=BPr1||BPr2||…||BPrn中重現(xiàn),且CBPr中僅含有這些完整簡單路徑的軌跡,以避免后續(xù)有效性確認,提高修正效率.其中,BPr1,…,BPrn分別為業(yè)務(wù)過程BP1,…,BPn對應(yīng)的修正業(yè)務(wù)過程.根據(jù)定理2,這一問題可轉(zhuǎn)換為保證CBPr和核c的行為一致.

為了生成與CBP行為一致的CBPr,基于核c,本文提出協(xié)調(diào)映射概念.協(xié)調(diào)映射是指在映射過程中引入?yún)f(xié)調(diào)因子(對應(yīng)活動),用于建模協(xié)調(diào)交互以實現(xiàn)協(xié)調(diào)邏輯,從而確保由映射生成BPr1,…,BPrn并發(fā)組合形成CBPr能夠遵循cc行為.從外界視角來觀察,在忽視協(xié)調(diào)因子的情況下,協(xié)調(diào)映射可使得CBPr只包含CBP中所有完整簡單路徑的軌跡.

在實際應(yīng)用中,不是CBP中的每個活動都需要進行協(xié)調(diào).以核為基礎(chǔ),本文提出協(xié)調(diào)活動的概念.

定義13(協(xié)調(diào)活動).給定部分正確協(xié)同業(yè)務(wù)過程CBP=BP1||BP2||…||BPn,CBP對應(yīng)的核c=(C,c0,Ce,A,Δ),稱活動a∈A1∪A2∪…∪An為協(xié)調(diào)活動,當且僅當存在格局c1∈C,使得,且c2?C,其中,?i∈[1..n],Ai為業(yè)務(wù)過程BPi的活動集.

由定義13 可知,協(xié)調(diào)活動是指在協(xié)同業(yè)務(wù)過程執(zhí)行中若不加以控制,則可能導致隱藏路徑產(chǎn)生的活動,即從初始格局c0至c2或由c2引出路徑.因此,需要對這些活動進行協(xié)調(diào),使其執(zhí)行后到達正確格局c1,避免達到異常格局c2.而對于除協(xié)調(diào)活動以外的其他活動,由于其執(zhí)行后總能夠到達正確狀態(tài),因此無需協(xié)調(diào).

以核為基礎(chǔ),映射生成修正業(yè)務(wù)過程之前需先將核中不相關(guān)活動(即不屬于此業(yè)務(wù)過程及不是協(xié)調(diào)活動的其他活動)隱藏,形式定義如下.

定義14(隱藏).給定部分正確協(xié)同業(yè)務(wù)過程CBP,BP=(S,s0,F,A,Δ)為CBP中一個業(yè)務(wù)過程,CBP對應(yīng)的核c=(C,c0,Ce,A,Δ),協(xié)調(diào)活動集為Ac,則根據(jù)BP及Ac對c進行隱藏后得到隱藏核為c′=(C′,c′0,C′e,A′,Δ′),其中,

(1)C′=C;

(2)A′={τ}∪{a|?(r,a,s)∈c.Δ∧a∈A∪Ac};

(3)對于?(r,a,s)∈Δ,如果a∈A∪Ac,則(r,a,s)∈Δ′,否則,τ格局遷移關(guān)系(r,τ,s)∈Δ′.

由定義14 可知,隱藏是將c中格局遷移關(guān)系重置.即若格局遷移關(guān)系中活動是BP中活動或是協(xié)調(diào)活動,則在重置的格局遷移關(guān)系中保持不變,否則將其設(shè)置為不可見活動τ.

在對c進行隱藏后,需要將產(chǎn)生的隱藏核c′最小化以生成修正業(yè)務(wù)過程.當前,研究者提出多種行為最小化技術(shù)[19],如軌跡最小化、分支最小化及互模擬最小化等.由于本文關(guān)注協(xié)同業(yè)務(wù)過程間的路徑一致,即路徑對應(yīng)軌跡相同,因此我們采用文獻[20]中提出的弱軌跡最小化算法對隱藏核進行最小化操作,最小化后生成一個中間有窮自動機.本質(zhì)上,標號遷移系統(tǒng)是一類特殊有窮自動機.因此,通過將中間有窮自動機中的狀態(tài)集、開始狀態(tài)、結(jié)束狀態(tài)集、活動集及狀態(tài)遷移關(guān)系分別對應(yīng)到標號遷移系統(tǒng)中的狀態(tài)集、初始狀態(tài)、終止狀態(tài)集、活動集及狀態(tài)遷移關(guān)系,則可由隱藏核生成一個中間業(yè)務(wù)過程.這種轉(zhuǎn)換過程非常直觀,限于篇幅,這里不再贅述.通過利用文獻[20]中提出的最小化方法,可確保中間業(yè)務(wù)過程與隱藏核保持弱軌跡等價,且中間業(yè)務(wù)過程中不含有不可見活動.

基于最小化后生成的中間業(yè)務(wù)過程,根據(jù)協(xié)調(diào)活動集,下面給出協(xié)調(diào)映射定義,以生成修正業(yè)務(wù)過程.

定義15(協(xié)調(diào)映射).給定部分正確協(xié)同業(yè)務(wù)過程CBP=BP1||BP2||…||BPn,BP=(S,s0,F,A,Δ)為CBP中的一個業(yè)務(wù)過程,Ac為CBP中的協(xié)調(diào)活動集,最小化后生成中間業(yè)務(wù)過程為BPm=(Sm,sm0,Fm,Am,Δm),則根據(jù)BP和Ac對BPm進行協(xié)調(diào)映射后得到修正業(yè)務(wù)過程為BPr=(Sr,sr0,F,Ar,Δr),其中,

(1)Sr=Sm∪{sc|?(r,a,s)∈Δm∧a?A∧a∈Ac}∪{sc1,sc2|?(r,a,s)∈Δm∧a∈A∧a∈Ac};

(2)sr0=sm0;

(3)Fr=Fm;

(4)Ar={a|?(r,a,s)∈cc.Δm∧a∈A∧a?Ac}∪{SYNC_1_a,SYNC_2_a|?(r,a,s)∈Δm∧a∈A∧a∈Ac}∪{SYNC_1_a,SYNC_2_a|?(r,a,s)∈Δm∧a?A∧a∈Ac};

(5)Δr={(r,SYNC_1_a,sc),(sc,SYNC_2_a,s)|?(r,a,s)∈Δm∧a?A∧a∈Ac}∪{(r,SYNC_1_a,sc1),(sc1,a,sc2),(sc2,SYNC_2_a,s)|?(r,a,s)∈Δm∧a∈A∧a∈Ac}∪{(r,a,s)|?(r,a,s)∈cc.Δm∧a∈A∧a?Ac}.

定義15 中,對于BPm中的一個活動a:(1)若a不屬于BP但需協(xié)調(diào),則引入?yún)f(xié)調(diào)因子SYNC_1_a、SYNC_2_a及協(xié)調(diào)狀態(tài)sc,用于將BPm中的格局遷移關(guān)系(r,a,s)設(shè)置為(r,SYNC_1_a,sc)和(sc,SYNC_2_a,s),表示在狀態(tài)r通過協(xié)調(diào)因子SYNC_1_a對活動a開始進行協(xié)調(diào),并通過協(xié)調(diào)因子SYNC_2_a對活動a結(jié)束協(xié)調(diào);(2)若a屬于BP且需協(xié)調(diào),則引入?yún)f(xié)調(diào)因子SYNC_1_a、SYNC_2_a及協(xié)調(diào)狀態(tài)sc1和sc2,用于將格局遷移關(guān)系(r,b,s)設(shè)置為3 個狀態(tài)遷移關(guān)系(r,SYNC_1_a,sc1)、(sc1,a,sc2)和(sc2,SYNC_2_a,s),表示在a執(zhí)行前需進行協(xié)調(diào),通過SYNC_1_a來實現(xiàn),執(zhí)行完成后進行結(jié)束協(xié)調(diào),通過SYNC_2_a來實現(xiàn);(3)若a屬于BP且無需協(xié)調(diào),則格局遷移關(guān)系(r,b,s)保持不變.

本質(zhì)上,修正業(yè)務(wù)過程是一個遷移系統(tǒng).特別地,給定一個業(yè)務(wù)過程BP,其修正業(yè)務(wù)過程BP′受BP行為(即遷移序列)和協(xié)調(diào)因子的影響.根據(jù)我們的實驗可以發(fā)現(xiàn)(見第5.2 節(jié)),BP′結(jié)構(gòu)通常較BP更復(fù)雜.同時,本文中BP′采用LTS 進行描述,LTS 描述模型較其他圖形化方式(如BPMN、BPEL 和Petri 網(wǎng))描述的模型復(fù)雜、難懂.這就限制了本文方法在實際中被用戶接受的程度.事實上,研究者已經(jīng)提出了一些方法[21]用于將以LTS 描述模型轉(zhuǎn)換為Petri 網(wǎng)描述模型,且能夠保持轉(zhuǎn)換前后行為一致(如保持強互模擬等).因此,針對修正業(yè)務(wù)過程對于用戶較難理解這個問題,可以考慮利用工具Petrify(https://www.merriam-webster.com/dictionary/petrify)將其轉(zhuǎn)換為Petri網(wǎng)來增強其實用性.有關(guān)Petrify 介紹及使用可以參見文獻[21],限于篇幅,這里不再闡述.

通過將修正業(yè)務(wù)過程集利用并發(fā)操作符加以組合,得到如下定義的修正協(xié)同業(yè)務(wù)過程.

定義16(修正協(xié)同業(yè)務(wù)過程).給定部分正確協(xié)同業(yè)務(wù)過程CBP=BP1||BP2||…||BPn,BPr1,…,BPrn分別為業(yè)務(wù)過程BP1,…,BPn對應(yīng)的修正業(yè)務(wù)過程,則修正協(xié)同業(yè)務(wù)過程為CBPr=BPr1||BPr2||…||BPrn.

在忽視協(xié)調(diào)因子的情況下,修正協(xié)同業(yè)務(wù)過程中只含有修正前的協(xié)同業(yè)務(wù)過程中的所有完整軌跡,可見定理3.

定理3.給定部分正確協(xié)同業(yè)務(wù)過程CBP=BP1||BP2||…||BPn,CBPr=BPr1||BPr2||…||BPrn為CBP的修正協(xié)同業(yè)務(wù)過程,則如下結(jié)論成立.

(1)對于CBP中任意完整的簡單路徑r,CBPr中存在一條完整的簡單路徑r′,滿足trace(r)=trace(r′)↑Acf;

(2)對于CBPr中任意完整的簡單路徑r,CBP中存在一條完整的簡單路徑r′,滿足trace(r′)=trace(r)↑Acf;

其中,Acf為CBP中所有協(xié)調(diào)因子集合;trace(r)↑Acf表示將r的任務(wù)執(zhí)行序列中的協(xié)調(diào)因子移除后形成的新任務(wù)執(zhí)行序列.

證明:1)設(shè)c為根據(jù)算法2 生成CBP的核,為c中任意一條完整的簡單路徑.由定義14 可知,對于r中任意遷移,每個業(yè)務(wù)過程BPn(1≤i≤n)對應(yīng)隱藏核中存在如下遷移,記為C1:

由文獻[20]中提出的最小化方法可知,所有的τ-格局遷移關(guān)系(即由τ引起的格局遷移關(guān)系)均被移除,且滿足弱軌跡等價,則最小化隱藏核后生成的業(yè)務(wù)過程BP中有如下遷移,記為C2:

根據(jù)定義15,每個修正業(yè)務(wù)過程BPrj(1≤j≤n)中的遷移進行如下協(xié)調(diào)映射,記為C3:

從左至右依次掃描r,根據(jù)定義5 中的點火規(guī)則可生成如下路徑r′,滿足:

根據(jù)C3,由于r為完整的簡單路徑,則可推出r′中km也為終止格局,故r′是完整的簡單路徑.進一步地,推出trace(r)=trace(r′)↑Acf成立.根據(jù)定理2,c與CBP中完整的簡單路徑一致,故結(jié)論(1)成立.

2)采用反證法證明.設(shè)CBPr中存在路徑片段,且c中存在對應(yīng)路徑片段r2,滿足trace(r2)=trace(r1)↑Acf.但CBPr中存在后續(xù)遷移使得路徑片段不為c中任意完整的簡單路徑的前綴.按如下兩步證明后續(xù)活動a不能發(fā)生.

(1)首先明確活動a是協(xié)調(diào)活動,即a∈Ac.針對路徑片段r1,由于c中存在對應(yīng)路徑片段r2,滿足trace(r2)=trace(r1)↑Acf.因此,從左至右掃描r1,對于r1中路徑片段:,或者ki-1ki,則用替換,重復(fù)這一過程,最終可求得kk對應(yīng)于ck.由C3 可知,若后續(xù)遷移發(fā)生后使得r3不為c中任意完整簡單路徑的前綴,那么a∈Ac.

(2)再證明協(xié)調(diào)活動a在CBPr中不能發(fā)生.分下面兩種情況加以討論.

i)a不在c中出現(xiàn),即a?c.A.由C3 可知,后續(xù)遷移不存在;

ii)a在c中出現(xiàn),即a∈c.A.設(shè)有后續(xù)有效遷移,使得為c中某條完整簡單路徑的前綴.若活動a能執(zhí)行,再分如下兩種情況進行討論.

①若a和b屬于同一個修正業(yè)務(wù)過程BPrj(1≤j≤n),則推出a和b處于選擇關(guān)系.由C3 可知,若a能夠執(zhí)行,則b不能執(zhí)行.但遷移是有效的,故活動a不能執(zhí)行;

② 若a和b屬于不同的修正業(yè)務(wù)過程,不妨設(shè)分別屬于業(yè)務(wù)過程BPri和BPrj(1≤i,j≤n).根據(jù)C3 可推出,BPrj中存在遷移.根據(jù)定義5 給出的點火規(guī)則,若活動a能夠執(zhí)行,則活動b不能執(zhí)行.但遷移是有效的,故活動a不能執(zhí)行.

綜合上述(1)和(2)推導可知,結(jié)論(2)成立. □

定理3 中的結(jié)論(1)表明修正前的協(xié)同業(yè)務(wù)過程中所有完整的簡單路徑都可以在修正協(xié)同業(yè)務(wù)過程中重現(xiàn);而結(jié)論(2)則表明未引入隱藏軌跡.這將避免修正后進行有效性確認,從而提高了修正效率.

特別需要明確的是,本文方法可支持帶有一般循環(huán)結(jié)構(gòu)的過程模型,其原因在于修正是基于完整簡單路徑開展.完整簡單路徑能夠記錄循環(huán)結(jié)構(gòu)(即自循環(huán)和一般循環(huán)結(jié)構(gòu)[17]),故通過算法2 構(gòu)建的核中循環(huán)結(jié)構(gòu)也不會丟失.最終,通過對核進行協(xié)調(diào)映射產(chǎn)生修正業(yè)務(wù)過程也含有已有環(huán)結(jié)構(gòu).

5 實驗評價

本文提出一種協(xié)同業(yè)務(wù)過程正確性修正方法.為了評估該方法的有效性,本節(jié)使用具有實際意義的協(xié)同業(yè)務(wù)過程集,通過與相關(guān)正確性修正方法進行實驗對比,從修正協(xié)同業(yè)務(wù)過程具有協(xié)同業(yè)務(wù)過程實際特征、重現(xiàn)完整軌跡及未引入隱藏軌跡等方面來分析不同正確性修正方法之間的有效性差異.

5.1 實驗準備

當前針對協(xié)同業(yè)務(wù)過程沒有公開的數(shù)據(jù)集可供實驗[22],而為了評價本文提出方法的有效性,我們從已有的研究論文[23,24]及BPMN 案例庫(http://www.bpmn.org/)中選取6 個較為典型的協(xié)同業(yè)務(wù)過程進行實驗.其中,Order Product(記為OP)、Purchase Order(記為PO)及Travel Booking System(記為TBS)分別作為文獻[23,24]中的啟發(fā)案例,用來闡述跨組織業(yè)務(wù)過程建模并分析方法的有效性,代表性較強;Amazon Online Purchase(記為AOP)、The Nobel Prize(記為TNP)和Incident Management(記為IM)則來自BPMN 案例庫,能夠反映實際的協(xié)同業(yè)務(wù)過程場景.

選取的6 個協(xié)同業(yè)務(wù)過程具有的屬性見表1,其中,No.of peers 表示協(xié)同業(yè)務(wù)過程中含有參與組織的個數(shù),“No.of peer states,trans”表示協(xié)同業(yè)務(wù)過程中含有的狀態(tài)數(shù)及遷移數(shù).采用標號遷移系統(tǒng)表示過程模型中的結(jié)構(gòu)有順序、選擇和循環(huán)3 類.為了表明選取過程模型的普遍性,選取的6 個協(xié)同業(yè)務(wù)過程中含有這3 類結(jié)構(gòu).特別地,循環(huán)結(jié)構(gòu)包含自循環(huán)和一般意義上的循環(huán)結(jié)構(gòu)這兩類[17].這兩類循環(huán)結(jié)構(gòu)也反映在過程模型中,如Purchase Order 中含有自循環(huán),而Order 中則含有一般循環(huán)結(jié)構(gòu)等.

Table 1 Properties of collaborative business processes表1 協(xié)同業(yè)務(wù)過程屬性

特別地,由于本文提出正確性修正方法面向部分正確協(xié)同業(yè)務(wù)過程,因此通過項目組討論對選取6 個協(xié)同業(yè)務(wù)過程的內(nèi)部結(jié)構(gòu)進行修改以注入錯誤,其中錯誤類型為死鎖、活鎖及消息未合理接收等.

目前,針對協(xié)同業(yè)務(wù)過程的正確性修正方法較少.本文選擇此類中的典型方法[13-15]作為實驗比較對象,從支持協(xié)同業(yè)務(wù)過程的實際特征、重現(xiàn)完整軌跡及引入隱藏軌跡等方面進行對比分析.

特別地,文獻[13]中方法的處理步驟是:先將每個業(yè)務(wù)過程采用Petri 網(wǎng)進行建模,利用文獻[9]中提到的庫所熔合和變遷熔合技術(shù)構(gòu)建全局模型,并獲得其所有完備軌跡[17].這里的完備是指在全局模型中,若活動b能夠在活動a執(zhí)行后立即執(zhí)行,則存在一條軌跡σ,σ中存在位置i,滿足σ(i)=a,且σ(i+1)=b;然后,將獲得完備軌跡作為文獻[13]中正確性修正方法輸入,則可生成中心流程;最后,將中心流程與每個業(yè)務(wù)過程進行變遷熔合,則構(gòu)建修正協(xié)同業(yè)務(wù)過程.而文獻[14,15]中方法的處理步驟是:先將每個業(yè)務(wù)過程采用Petri 網(wǎng)進行建模;然后利用文獻[9]中庫所熔合和變遷熔合技術(shù)構(gòu)建全局模型.針對構(gòu)建的全局模型,為保持修正模型的一致性,獲得其完備軌跡;最后,將獲得的完備軌跡作為文獻[14,15]中模型修正方法輸入,即構(gòu)建出修正協(xié)同業(yè)務(wù)過程.

所有實驗在一臺PC 上開展,軟件環(huán)境為:Windows 10 及JDK 1.7,硬件環(huán)境為:處理器為Inter(R)Core(TM)i5-8250U CPU@ 1.60GHz、內(nèi)存為8GB.

5.2 實驗結(jié)果及分析

5.2.1 支持個性化特征分析

通過對修正協(xié)同業(yè)務(wù)過程進行分析,可以分析出本文方法在支持協(xié)同業(yè)務(wù)過程實際特征方面的有效性.跨組織業(yè)務(wù)過程建模研究表明[6-10],協(xié)同業(yè)務(wù)過程通常具有4 類特征:自治性、分布性、交互性和隱私性.其中,自治性是指每個業(yè)務(wù)過程由其所屬組織管理及運行;分布性是指協(xié)同業(yè)務(wù)過程在結(jié)構(gòu)和執(zhí)行上具有分布性;交互性是指業(yè)務(wù)過程在執(zhí)行中需要與其他業(yè)務(wù)過程進行交互以推動全局流程演進;隱私性是指在跨組織環(huán)境下,參與組織希望在建模及分析過程中避免將其內(nèi)部流程信息暴露給其他參與組織.特別地,在實際應(yīng)用中,這4 類特征主要是針對構(gòu)建后的協(xié)同業(yè)務(wù)過程形態(tài)(即是否表現(xiàn)為分布式、有無中心流程等)及構(gòu)建時是否暴露流程信息給參與組織來進行體現(xiàn).因此,上文在定義協(xié)同業(yè)務(wù)過程和闡述方法時沒有提及這4 類特征.此外,應(yīng)用這4 類特征對協(xié)同業(yè)務(wù)過程評價主要是從定性角度開展,因此本文未在上文具體證明中及本節(jié)中應(yīng)用實驗數(shù)據(jù)驗證這個結(jié)果.

特別需要說明的是,實驗中默認本文方法和文獻[13-15]中的方法對協(xié)同業(yè)務(wù)過程進行修正均是由可信第三方TTP(trusted third party)[25]來完成,因此均能支持隱私性.在實際應(yīng)用中,參與組織先將各自的業(yè)務(wù)過程提交給TTP;之后TTP 對由其組合建立協(xié)同業(yè)務(wù)過程,并對其修正;最后TTP 將每個修正業(yè)務(wù)過程返給對應(yīng)參與組織.在跨組織環(huán)境下,為保護隱私性,這種通過TTP 對協(xié)同業(yè)務(wù)過程進行分析是常見和合理的[25].

針對選取的5 個協(xié)同業(yè)務(wù)過程,本文方法和文獻[13-15]中的方法建立的修正協(xié)同業(yè)務(wù)過程對上述4 類特征支持情況見表2,其中.A表示自治性,D表示分布性,I表示交互性,P表示隱私性.

Table 2 Feature support results表2 特征支持結(jié)果

從表2 可以看出,經(jīng)本文方法建立的修正協(xié)同業(yè)務(wù)過程能夠良好地支持上述4 類特征,而經(jīng)文獻[13-15]中的方法建立的修正協(xié)同業(yè)務(wù)過程僅能支持隱私性.因此,相較文獻[13-15]中的方法,本文方法能夠更加有效地支持協(xié)同業(yè)務(wù)過程具有實際特征.

例如,對于協(xié)同業(yè)務(wù)過程集中訂單采購OP,OP 中業(yè)務(wù)過程Customer 和Vendor 如圖2 所示.

Fig.2 Business processes customer and vendor in OP圖2 OP 中業(yè)務(wù)過程Customer 及Vendor

利用本文方法建立修正協(xié)同業(yè)務(wù)過程OPr-o如圖3 所示,修正業(yè)務(wù)過程Customerr和Vendorr并發(fā)組合形成.

Fig.3 Repaired business processes Customerr and Vendorr圖3 修正業(yè)務(wù)過程Customerr 及Vendorr

利用文獻[13]中的方法建立的修正協(xié)同業(yè)務(wù)過程OPr-z如圖4 所示,其中,虛線表示任務(wù)同步關(guān)系.

利用文獻[14,15]的中方法建立的修正協(xié)同業(yè)務(wù)過程OPr-a如圖5 所示.

通過分析OPr-o、OPr-z和OPr-a可知,OPr-o由修正業(yè)務(wù)過程Customerr和Vendorr并發(fā)組合形成,即OPr-o=Customerr||Vendorr.由于這兩個修正業(yè)務(wù)過程獨立存在,且每個修正業(yè)務(wù)過程由各自組織管理,同時,OPr-o按照定義5 中給出的點火規(guī)則運行,表明其具有自治、分布及交互特性.同時,具體修正由TTP 完成,表明其具有隱私性;而由文獻[13-15]中的方法建立的修正協(xié)同業(yè)務(wù)過程OPr-z和OPr-a實質(zhì)上均是集中式的.特別地,業(yè)務(wù)過程Customer 和Vendor 中活動及活動間的交互不是并發(fā)執(zhí)行的,而是通過Center 和OPr-a中控制流的約束來執(zhí)行.例如,Customer 內(nèi)本地活動browProduct執(zhí)行需要與Center 內(nèi)活動browProduct執(zhí)行同步;而活動!orderA和?orderA間的交互則由Center 內(nèi)控制流來約束.

Fig.4 Repaired business process POr-z圖4 修正業(yè)務(wù)過程POr-z

Fig.5 Repaired business process POr-a圖5 修正業(yè)務(wù)過程POr-a

5.2.2 軌跡有效性分析

本小節(jié)分析修正協(xié)同業(yè)務(wù)過程中重現(xiàn)完整軌跡和未引入隱藏軌跡的有效性.基于簡單軌跡,本文提出精確度和泛化度這兩個有效性計算指標.

精確度的計算公式如式(1)所示.

式(1)中,TM′為修正協(xié)同業(yè)務(wù)過程中所有的簡單軌跡;TM為修正前協(xié)同業(yè)務(wù)過程中所有的完整簡單軌跡;acc(TM,TM′)為被TM接受的TM′中的軌跡子集.對于精確度而言,計算結(jié)果值越高,則表示修正協(xié)同業(yè)務(wù)過程中引入的隱藏軌跡越少,修正效果越好.

泛化度的計算公式如式(2)所示.

式(2)中,TM′為修正協(xié)同業(yè)務(wù)過程中所有的簡單軌跡;TM為修正前協(xié)同業(yè)務(wù)過程中所有的完整簡單軌跡;acc(TM′,TM)為被TM′接受的TM中的軌跡子集.對于泛化度指標,計算結(jié)果值越高,則表示修正協(xié)同業(yè)務(wù)過程中重現(xiàn)修正前協(xié)同業(yè)務(wù)過程中的完整簡單軌跡越多,修正效果越好.

根據(jù)式(1)和式(2),本文方法和文獻[13-15]中方法的精確度和泛化度的計算結(jié)果分別如圖6(a)～圖6(b)所示.

由圖6(a)可以看出,本文方法的精確度高于文獻[13-15]中方法的精確度.同時,本文方法的泛化度與文獻[14,15]中方法的泛化度相同,但遠高于文獻[13]中的方法.由此,我們可以得出如下結(jié)論.

(1)由于本文方法能夠事先保證修正協(xié)同業(yè)務(wù)過程中含有修正前協(xié)同業(yè)務(wù)過程中所有完整的軌跡,且未引入隱藏軌跡,使得本文方法的精確度和泛化度均為1.0.圖6 所示實驗結(jié)果也與理論分析相一致;

(2)文獻[14,15]中的方法在精確度方面表現(xiàn)良好,其均為1.0,表明修正協(xié)同業(yè)務(wù)過程能夠重現(xiàn)修正前的協(xié)同業(yè)務(wù)過程中所有完整的軌跡.在泛化度方面,文獻[14,15]中方法的值介于0.5～1.0 之間,表明在修正協(xié)同業(yè)務(wù)過程中引入了隱藏軌跡.分析發(fā)現(xiàn),這些隱藏軌跡是由修正協(xié)同業(yè)務(wù)過程中存在異常(如死鎖等)引起;

(3)文獻[13]中的方法在精確度和泛化度方面的表現(xiàn)都是最差的,其精確度和泛化度在選取的協(xié)同業(yè)務(wù)過程中大多為0.0,表明修正前協(xié)同業(yè)務(wù)過程中幾乎所有完整軌跡在修正協(xié)同業(yè)務(wù)過程中丟失.分析發(fā)現(xiàn),這是由于修正協(xié)同業(yè)務(wù)過程中存在異常(如死鎖等)和一些活動丟失(如POr-z中活動checkStock丟失等)所致.

Fig.6 Comparison in terms of precision and generality圖6 精確度和泛化度比較

5.2.3 修正時間耗費分析

通過分析建立修正協(xié)同業(yè)務(wù)過程時間耗費,可評價本文方法的修正效率.利用本文方法和文獻[13-15]中的方法對協(xié)同業(yè)務(wù)過程進行正確性修正所耗費的時間為Tcr=Tct+Tr,其中,Tct為獲取修正前協(xié)同業(yè)務(wù)過程中所有完整的軌跡時間,Tr為進行修正所耗費的時間;同時,利用文獻[13-15]中的方法對協(xié)同業(yè)務(wù)過程進行修正后還需要進行有效性確認,所耗費的時間為Tcv=Tvp+Tvg,其中,Tvp為計算精確度時間,Tvg為計算泛化度時間.本文方法和文獻[13-15]中的方法建立修正協(xié)同業(yè)務(wù)過程的時間耗費見表3,其中,Ttotal為修正總耗費時間,即為正確性修正耗費時間和有效性確認所耗費時間之和.特別地,為了確保結(jié)果的客觀性,每次實驗重復(fù)10 次,然后取平均值作為建立修正協(xié)同業(yè)務(wù)過程的時間耗費.

從表3 可以看出:

(1)利用本文方法修正所耗費的時間遠遠小于文獻[13-15]中的方法.例如,針對Travel Book System,本文方法的修正耗費時間為3 570ms,而文獻[13]和文獻[14,15]中的方法分別耗費133 750ms 和281 667ms.分析發(fā)現(xiàn),文獻[13-15]中方法修正效率低下的原因是由于上述6 個協(xié)同業(yè)務(wù)過程中含有較多完備軌跡(如Travel Book System 中含有1 458 條完備軌跡)和采用過程挖掘技術(shù)所致.可以預(yù)見,若對更加復(fù)雜的協(xié)同業(yè)務(wù)過程進行修正,則其時間將進一步增加.而本文方法只需獲取所有的完整簡單路徑(如Travel Book System 中只含有384 條),并對核協(xié)調(diào)映射即可生成修正協(xié)同業(yè)務(wù)過程,避免文獻[13-15]中方法使用過程模型挖掘算法(如α算法等)、案例差異檢測等步驟,從而縮短了修正時間;

(2)由于本文方法能夠事先保證修正協(xié)同業(yè)務(wù)過程中含有修正前協(xié)同業(yè)務(wù)過程中所有的完整軌跡,且未引入隱藏軌跡,這使得本文方法無須進行有效性確認,即有效性確認耗費時間為0ms.而文獻[13-15]中方法的有效性確認所耗費的時間均較高.例如,針對Travel Book System,文獻[13]和文獻[14,15]中方法進行有效性確認耗費的時間分別為20 900ms 和59 696ms.分析發(fā)現(xiàn),這是由于選取的協(xié)同業(yè)務(wù)過程和對應(yīng)修正協(xié)同業(yè)務(wù)過程中均含有較多的簡單軌跡和完整軌跡所致.可以預(yù)見,若對更加復(fù)雜的協(xié)同業(yè)務(wù)過程進行有效性確認,則其所耗費的時間將進一步增加;

(3)從修正耗費總時間來看,相較文獻[13]和文獻[14,15]中的方法,本文方法的修正效率有極大的提高,分別提高14 倍和42 倍.

綜上分析,可以得出如下結(jié)論:相比文獻[13-15]中所提出的正確性修正方法,在考慮協(xié)同業(yè)務(wù)過程實際特征的情況下,由于本文方法能夠事先確保修正協(xié)同業(yè)務(wù)過程中含有修正前協(xié)同業(yè)務(wù)過程中所有完整的軌跡,且未引入隱藏軌跡,從而使得本文方法可以對協(xié)同業(yè)務(wù)過程進行更加有效的修正,并且能夠極大地縮短修正所耗費的時間.

6 相關(guān)工作

目前,針對協(xié)同業(yè)務(wù)過程的正確性分析方法可分為兩類:正確性檢測方法和正確性修正方法.下面對這兩類方法中的一些典型文獻進行介紹和分析.

6.1 正確性檢測方法

國內(nèi)外研究者針對協(xié)同業(yè)務(wù)過程的正確性檢測方法開展了大量的研究.歸納起來,這些方法可分為3 類:基于Petri 網(wǎng)的檢測方法、基于進程代數(shù)的檢測方法及基于自動機的檢測方法.

以傳統(tǒng)的組織內(nèi)業(yè)務(wù)過程建模方法為基礎(chǔ),文獻[9]較早地在國際上提出了 IOWF(inter-organizational workflow)用于建?？缃M織業(yè)務(wù)過程.針對構(gòu)建跨組織業(yè)務(wù)過程提出合理性概念用來定義其正確性,并基于Petri網(wǎng)的可達圖提出跨組織業(yè)務(wù)過程正確性檢測方法.之后,國內(nèi)外研究者以此為基礎(chǔ)開展了大量的研究.如文獻[10]針對跨部門業(yè)務(wù)過程協(xié)同呈現(xiàn)出越來越復(fù)雜的特點,對WF-net 擴展資源和消息等要素以建模參與部門的業(yè)務(wù)過程,繼而使用庫所熔合技術(shù)將資源庫所和消息庫所加以熔合從而得到跨部門協(xié)調(diào)業(yè)務(wù)過程模型.針對構(gòu)建跨部門業(yè)務(wù)過程,基于合理性定義其正確性并提出驗證方法.跨組織工作流網(wǎng)IWF-nets(inter-organizational workflow nets)可以有效地建模協(xié)同業(yè)務(wù)過程間基于消息的協(xié)作.為了確保協(xié)同業(yè)務(wù)實施的正確性,文獻[26]引入了兼容性和弱兼容性的概念,并針對IWF-nets 的網(wǎng)結(jié)構(gòu)提出了用于判定兼容性或弱兼容性的充要條件.針對公共管理呈現(xiàn)出交互的特征,為確保其正確實施,文獻[27]首先使用BPMN(business process modeling notation)對其進行描述,之后將其BPMN 模型轉(zhuǎn)換成基于Petri 網(wǎng)的模型,并采用Petri 網(wǎng)的展開技術(shù)(unfolding-based technique)對相關(guān)性質(zhì)(如死鎖等)進行驗證.為了有效地驗證協(xié)同業(yè)務(wù)過程的行為正確性,文獻[28]首先利用BPMN 建模協(xié)同業(yè)務(wù)過程,然后將每個參與組織的流程轉(zhuǎn)換為一類高級Petri網(wǎng)ECATNets(recursive ECATNets),最后基于庫所熔合技術(shù)將其組合得到以ECATNets 來描述的模型.由于該模型的語義被解釋為條件重寫邏輯,進而可以利用Maude LTL 模型檢測器對協(xié)同業(yè)務(wù)過程的行為正確性性質(zhì)進行驗證.

基于Pi 演算,文獻[16]較早地提出一種利用進程代數(shù)建?？缃M織業(yè)務(wù)過程方法.即利用Pi 演算的并發(fā)算子,將跨組織業(yè)務(wù)過程建模為一組自治且并發(fā)執(zhí)行的組織內(nèi)子流程的組合,子流程建模為組織內(nèi)本地流程定義和組織間控制約束的組合,并利用工具MWB(mobile workbench)驗證抽象正確性.為了檢測協(xié)同業(yè)務(wù)過程能否正確地協(xié)調(diào),文獻[29]提出了一種針對多個業(yè)務(wù)過程組合驗證的概念框架.它將BPMN 建模的協(xié)同業(yè)務(wù)過程轉(zhuǎn)換以時間通信順序進程CSP+T(communicating sequential processes+time)表示進程,之后采用時序邏輯公式定義期望正確性性質(zhì),并利用模型檢測方法在工具FDR2(failures-divergences refinement)上自動驗證正確性性質(zhì)是否滿足.為實現(xiàn)面向Web 服務(wù)的流程無縫集成,文獻[30]提出了一種基于遞歸組合代數(shù)的Web 服務(wù)交互流程建模和驗證方法.首先利用遞歸組合代數(shù)建模Web 服務(wù)流程交互,并將其轉(zhuǎn)換為遞歸組合交互圖,之后利用遞歸組合規(guī)約語言來描述需求,并通過遞歸組合交互圖自動地驗證需求是否滿足與否.

為了使得多個基于Web 服務(wù)的業(yè)務(wù)過程的組合符合用戶定義適配需求,文獻[31]提出一種描述及驗證多業(yè)務(wù)過程間行為適配的方法.它采用LTS 描述業(yè)務(wù)過程及適配器,進而將業(yè)務(wù)過程與適配器組合來檢測其是否相容以判斷多業(yè)務(wù)過程的組合是否符合用戶定義適配的需求.互操作是業(yè)務(wù)協(xié)同正確實施須具備的先決條件,為確保每個參與組織的互操作是否符合規(guī)定的需求,文獻[32]首先使用BPMN 來描述協(xié)同業(yè)務(wù)過程,之后將其BPMN 模型轉(zhuǎn)換成模型檢測工具UPPAAL 中的時間自動機網(wǎng)絡(luò)(timed automata network,簡稱TAN),并采用時序邏輯TCTL(time computation tree logic)描述互操作需求,從而實現(xiàn)互操作自動檢測.特別地,BPMN 模型中每個參與組織業(yè)務(wù)過程在TAN 中對應(yīng)一個時間自動機(timed automata,簡稱TA),這些TA 并發(fā)組合構(gòu)成了TAN,即協(xié)同業(yè)務(wù)過程.在后續(xù)工作中,為了更加有效地存儲和描述互操作需求,文獻[33]首先提出了一種領(lǐng)域描述語言用來描述互操作需求,繼而將描述需求自動轉(zhuǎn)換為時序邏輯TCTL,并采用TAN 建模協(xié)同業(yè)務(wù)過程.通過UPPAAL 實現(xiàn)互操作需求的自動驗證.

上面提出的正確性檢測方法通常具有檢測過程自動化,不需要人工干預(yù),且在檢測失敗時能夠給出診斷信息,便于業(yè)務(wù)設(shè)計人員發(fā)現(xiàn)并修正錯誤.但其不足是,若協(xié)同業(yè)務(wù)過程中存在多處不正確,則需要經(jīng)過多次檢測,且在每次檢測后都需要對協(xié)同業(yè)務(wù)過程重新調(diào)整.這種設(shè)計、驗證、分析及糾錯的過程使得協(xié)同業(yè)務(wù)過程的正確性分析變得復(fù)雜且耗時.

6.2 正確性修正方法

相比正確性檢測方法,針對業(yè)務(wù)過程正確性修正方法是較新的課題,相關(guān)研究工作較少.文獻[11,12]針對以Artifact 為中心的業(yè)務(wù)過程提出一種正確性保持的設(shè)計方法.它首先采用Petri 網(wǎng)建模以Artifact 為中心的業(yè)務(wù)過程,之后以合規(guī)性和弱合理定義其正確性,最后將業(yè)務(wù)過程與正確性合成以自動構(gòu)建具有正確性的業(yè)務(wù)過程.文獻[34]采用開放工作流網(wǎng)oWFN(open workflow nets)建?？缃M織環(huán)境下的業(yè)務(wù)過程,利用CTL 公式定義期望正確性性質(zhì),根據(jù)以CTL 公式定義性質(zhì)對業(yè)務(wù)過程內(nèi)部結(jié)構(gòu)進行修改來構(gòu)建跨組織環(huán)境下具有正確性的業(yè)務(wù)過程.然而,上面提出的正確性修正方法均面向組織內(nèi)的單個業(yè)務(wù)過程.由于協(xié)同業(yè)務(wù)過程具有自治性、分布性及涉及多個業(yè)務(wù)過程間的同步或異步交互,因此上面提出的方法不適用于跨組織環(huán)境下的協(xié)同業(yè)務(wù)過程.

近年來,面向軌跡的業(yè)務(wù)過程修正方法引起一些學者的關(guān)注.文獻[14]首次在國際上提出此類方法.首先利用已有的一致性檢測來發(fā)現(xiàn)過程模型與軌跡間差異,并將體現(xiàn)這些差異的軌跡從原軌跡中分離出來,以子軌跡來加以表示.針對這些子軌跡,構(gòu)建其對應(yīng)子結(jié)構(gòu)并將其添加至原業(yè)務(wù)過程中,從而完成業(yè)務(wù)過程的修正.隨后,文獻[15]對文獻[14]的工作進行了一些改進,即針對一致性檢測中發(fā)現(xiàn)的循環(huán)結(jié)構(gòu),構(gòu)建其對應(yīng)的子過程并將其添加至修正模型中.文獻[35]提出的修正方法沿用了文獻[14,15]的思路.針對工作流模型,首先利用監(jiān)控矩陣刻畫實際工作流模型足跡,通過比較工作流模型的軌跡與足跡間的差異,提出4 種用于修正的工作流模型算法.我們課題組最近的工作[13]是結(jié)合Petri 網(wǎng)和過程挖掘的相關(guān)理論,提出一種針對協(xié)同業(yè)務(wù)過程的修正方法.該方法首先獲取部分正確協(xié)同業(yè)務(wù)過程中所有完整的軌跡,之后利用α算法從這些完整的軌跡構(gòu)建相容協(xié)同業(yè)務(wù)過程,最后通過設(shè)置協(xié)同業(yè)務(wù)過程與業(yè)務(wù)過程間的任務(wù)執(zhí)行同步關(guān)系以協(xié)調(diào)業(yè)務(wù)過程的正確運行.然而,利用上述方法建立的修正業(yè)務(wù)過程仍是集中式的,也存在修正前協(xié)同業(yè)務(wù)過程中完整軌跡可能會丟失和修正協(xié)同業(yè)務(wù)過程中可能會引入隱藏軌跡等問題.相較而言,本文方法構(gòu)建的協(xié)同業(yè)務(wù)過程是完全分布式的(即不存在中心流程),它的執(zhí)行能夠正確終止且與修正前協(xié)同業(yè)務(wù)過程中含有的所有完整軌跡相一致.

面向Web 服務(wù)流程的自動組合方法也是與協(xié)同業(yè)務(wù)過程正確性修正比較相關(guān)的工作.文獻[36]首先裁剪合理性定義正確性(即相容性),針對部分相容Web 服務(wù)流程采用Petri 網(wǎng)建模每個服務(wù)的流程,然后將其進行組合并分析其相容性.若分析結(jié)果部分相容,則產(chǎn)生適配器將來協(xié)調(diào)服務(wù)流程,使之前部分相容的服務(wù)流程轉(zhuǎn)換為完整相容,且未改變原有服務(wù)流程的內(nèi)部結(jié)構(gòu).為了應(yīng)對服務(wù)流程間存在時序約束及消息匹配問題,文獻[37]首先采用Petri 網(wǎng)建模每個服務(wù)的流程,然后根據(jù)消息匹配情況及時序約束構(gòu)建適配器,從而使得所有服務(wù)的流程與適配器組合執(zhí)行是正確的,以避免出現(xiàn)時序異常.面向Web 服務(wù)流程組合與通過傳統(tǒng)業(yè)務(wù)過程組合建立協(xié)同業(yè)務(wù)過程的最大區(qū)別是服務(wù)使用者通常沒有修改第三方服務(wù)的權(quán)限,也不能要求服務(wù)提供者按照自己的需求修改提供的服務(wù).因此,針對Web 服務(wù)流程自動組合通常利用適配器來實現(xiàn),而針對業(yè)務(wù)過程組合主要是由可信第三方在設(shè)計階段修改業(yè)務(wù)過程的內(nèi)部結(jié)構(gòu)來實現(xiàn)[36].

7 總結(jié)

在考慮活動同步及異步交互的情況下,本文基于完整簡單路徑提出一種協(xié)同業(yè)務(wù)過程正確性修正方法.該方法將部分正確的協(xié)同業(yè)務(wù)過程中所有的完整簡單路徑合并以構(gòu)建核,通過協(xié)調(diào)映射來生成修正業(yè)務(wù)過程,將修正業(yè)務(wù)過程并發(fā)組合建立修正協(xié)同業(yè)務(wù)過程.該方法一方面可確保修正協(xié)同業(yè)務(wù)過程符合其典型特征(如自治、分布等);另一方面,修正協(xié)同業(yè)務(wù)過程只含有修正前協(xié)同業(yè)務(wù)過程中所有完整簡單路徑對應(yīng)的軌跡,可避免有效性確認,提高了修正效率.

未來工作主要針對以下3 個方面的問題開展研究.

(1)本文定義正確性關(guān)注控制流,而數(shù)據(jù)流也是影響業(yè)務(wù)過程協(xié)作的一個重要因素.因此,下一步將提出同時考慮控制流和數(shù)據(jù)流的協(xié)同業(yè)務(wù)過程正確性修正方法;

(2)弱合理可歸于一般意義上的正確性[17],而參與組織期望系統(tǒng)功能或特性可能多種多樣.如何在考慮用戶需求層面對協(xié)同業(yè)務(wù)過程進行修正是值得深入研究的課題;

(3)本文方法在修正中需要首先生成協(xié)同業(yè)務(wù)過程完整簡單路徑,然后合成核,最后通過對核進行協(xié)調(diào)映射生成每個修正業(yè)務(wù)過程.在實際應(yīng)用中,由于受限于協(xié)同業(yè)務(wù)過程的狀態(tài)空間,本文方法也面臨狀態(tài)空間爆炸的問題.然而,本文主要關(guān)注修正方法的有效性(即修正協(xié)同業(yè)務(wù)過程符合實際特征及修正前后完整簡單軌跡保持一致)和效率(即修正耗費時間較短)問題.如何避免修正中出現(xiàn)的狀態(tài)空間爆炸問題將在未來工作中著重加以討論.