協(xié)同業(yè)務(wù)過程的相容性檢測及修正*

鄭 明，莫 啟,2+，周小煊，李 彤,2，謝仲文,2，向文坤

1.云南大學 軟件學院，昆明 650500

2.云南省軟件工程重點實驗室，昆明 650500

協(xié)同業(yè)務(wù)過程的相容性檢測及修正*

鄭 明1，莫 啟1,2+，周小煊1，李 彤1,2，謝仲文1,2，向文坤1

1.云南大學 軟件學院，昆明 650500

2.云南省軟件工程重點實驗室，昆明 650500

隨著經(jīng)濟全球化的發(fā)展，企業(yè)的業(yè)務(wù)活動已從企業(yè)內(nèi)單獨的業(yè)務(wù)過程發(fā)展成為跨企業(yè)多個協(xié)同業(yè)務(wù)過程的模式，為了確保協(xié)同業(yè)務(wù)過程實施的正確性，協(xié)同業(yè)務(wù)過程相容性及修正是一個不可或缺的研究問題。為此，結(jié)合Petri網(wǎng)及過程挖掘的相關(guān)理論，提出了一種跨組織協(xié)同業(yè)務(wù)過程的相容性檢測及修正方法。首先基于Petri網(wǎng)對業(yè)務(wù)過程及協(xié)同業(yè)務(wù)過程進行建模；然后對業(yè)務(wù)過程和協(xié)同業(yè)務(wù)過程的相容性進行定義，并分別給出了相應(yīng)的檢測算法；最后以現(xiàn)實中的購買過程為案例，檢測出該購買過程中存在的不相容的協(xié)同業(yè)務(wù)過程，并予以修正。結(jié)果表明，在不改變局部業(yè)務(wù)過程的情況下，對本來不相容的協(xié)同業(yè)務(wù)過程進行修正，并最終達到一種好的滿足相容性的協(xié)同業(yè)務(wù)過程模型。

協(xié)同業(yè)務(wù)過程；相容性；修正方法

1 引言

以往，信息系統(tǒng)被設(shè)計用來支持單個任務(wù)的執(zhí)行，如今的信息系統(tǒng)的關(guān)注點不再是任務(wù)，而是業(yè)務(wù)過程。由于業(yè)務(wù)過程重組（business process reengineering，BPR）和持續(xù)過程改進（continuous process improvement，CPI）等概念受到業(yè)務(wù)過程的影響而面世，人們越來越意識到業(yè)務(wù)過程的重要性，并且現(xiàn)在的組織機構(gòu)需要提供更廣闊的產(chǎn)品范圍和服務(wù)范圍，組織內(nèi)的業(yè)務(wù)過程一直呈現(xiàn)持續(xù)增長的趨勢。比如抵押貸款，幾十年前只有少量的幾種類型的貸款方式，而如今，有著各種各樣的貸款方式可以選擇。不只大量的產(chǎn)品和服務(wù)在持續(xù)增長，產(chǎn)品和服務(wù)的生命周期也同樣在增長，因此，業(yè)務(wù)過程也在不斷進行變化，而且這些業(yè)務(wù)過程也將變得相當復雜，組織結(jié)構(gòu)內(nèi)部的信息系統(tǒng)的這些變化，使得業(yè)務(wù)過程成為一個促進信息系統(tǒng)發(fā)展的關(guān)鍵性問題[1]。

隨著全球經(jīng)濟化的發(fā)展和企業(yè)信息化程度的不斷提高，企業(yè)的經(jīng)營模式發(fā)生了重大的變化，企業(yè)的業(yè)務(wù)活動已從企業(yè)內(nèi)單目標為導向的獨立發(fā)展模式發(fā)展成為跨企業(yè)多目標合作的協(xié)同模式[2]。近年來，Internet成為主流的計算平臺，尤其是面向服務(wù)計算（service-oriented computing，SOC）的快速興起，使得不同組織業(yè)務(wù)過程間的交互成為可能。在現(xiàn)代商業(yè)環(huán)境下，沒有一個企業(yè)是獨立存在的，為實現(xiàn)共同的商業(yè)目標，每個組織的業(yè)務(wù)過程常常需要跨越組織邊界，同其他組織的業(yè)務(wù)過程進行交互和協(xié)作，以形成相對穩(wěn)定的過程視圖，從而滿足商業(yè)需求。這種復雜的業(yè)務(wù)過程被學術(shù)界和工業(yè)界稱為協(xié)同業(yè)務(wù)過程[3]。

由于跨組織協(xié)同業(yè)務(wù)過程是一個復雜并且容易出錯的過程，在跨組織協(xié)同業(yè)務(wù)過程結(jié)合業(yè)務(wù)語義投入使用之前，需要對跨組織協(xié)同業(yè)務(wù)過程進行建模和相容性分析，防止組織和企業(yè)的協(xié)同業(yè)務(wù)過程出現(xiàn)錯誤，因為此時修復錯誤的代價將是難以估計的。因此，對跨組織協(xié)同業(yè)務(wù)過程進行建模、相容性分析以及相容性修正等問題的解決勢在必行。

本文的工作主要有如下幾部分：首先，基于Petri網(wǎng)對業(yè)務(wù)過程和協(xié)同業(yè)務(wù)過程進行建模；然后，分別對業(yè)務(wù)過程和協(xié)同業(yè)務(wù)過程的相容性進行定義；其次，提出了業(yè)務(wù)過程和協(xié)同業(yè)務(wù)過程的相容性檢測算法，對跨組織協(xié)同業(yè)務(wù)過程的相容性進行判斷；最后，對于跨組織業(yè)務(wù)協(xié)同中出現(xiàn)的不相容的情形，提出了一種相容性修正機制，根據(jù)該修正機制進行逆向修復，使得本來不相容的跨組織業(yè)務(wù)協(xié)同在不改變局部業(yè)務(wù)過程的情況下修正為一種好的相容的跨組織協(xié)同業(yè)務(wù)過程模型。本文的主要貢獻如下：

（1）基于跨組織工作流網(wǎng)（interorganizational workflows，IOWF）對業(yè)務(wù)過程和協(xié)同業(yè)務(wù)過程分別進行建模。

（2）對于業(yè)務(wù)過程和協(xié)同業(yè)務(wù)過程出現(xiàn)的不相容性情況分別提出了相應(yīng)的檢測算法。

（3）能對檢測出的不相容的協(xié)同業(yè)務(wù)過程進行修正。購買過程實例表明，該方法確實能夠?qū)Σ幌嗳莸膮f(xié)同業(yè)務(wù)過程進行修正并最終得到一個好的滿足相容性的協(xié)同業(yè)務(wù)過程模型。

本文組織結(jié)構(gòu)如下：第2章介紹了當前國內(nèi)外的相關(guān)工作；第3章對一些基本概念進行定義并基于Petri網(wǎng)對業(yè)務(wù)過程和協(xié)同業(yè)務(wù)過程進行建模；第4章介紹協(xié)同業(yè)務(wù)過程的相容性及檢測；第5章概述了跨組織協(xié)同業(yè)務(wù)過程相容性檢測及修正方法，并以一個典型購物過程為案例，詳細闡述了協(xié)同業(yè)務(wù)過程相容性的修正過程；第6章為結(jié)束語及未來展望。

2 相關(guān)工作

有關(guān)跨組織協(xié)同業(yè)務(wù)過程相容性問題的分析已逐漸成為當前研究的一個熱點問題。目前，在這一問題上，國內(nèi)外學者主要從Petri網(wǎng)、進程代數(shù)和自動機這三方面進行了研究。

Petri網(wǎng)方面：文獻[4]基于工作流網(wǎng)中的良構(gòu)性，提出了服務(wù)良構(gòu)性的概念，為了簡化相容性的驗證條件，將服務(wù)之間的相容性分析簡化為只需驗證其組合服務(wù)從初始標識是否總是能夠到達終止標識。文獻[5]基于BPEL對服務(wù)組合進行描述，進一步借鑒有色Petri網(wǎng)對BPEL描述的服務(wù)組合進行建模，并使用Petri網(wǎng)的結(jié)構(gòu)化分析技術(shù)對組合服務(wù)之間的相容性進行分析。文獻[6]基于Petri網(wǎng)對業(yè)務(wù)流程進行建模，并提出了一種基于交互沖突的業(yè)務(wù)流程互操作性檢測方法，該方法利用局部交互之間的行為約束關(guān)系檢測復雜業(yè)務(wù)流程互操作的匹配性。文獻[7]通過Petri網(wǎng)，基于協(xié)作點的語義對業(yè)務(wù)過程單元間存在的協(xié)作關(guān)系進行劃分，應(yīng)用等價劃分的思想對跨組織業(yè)務(wù)過程協(xié)同進行并行建模，實驗表明，通過并行建模的跨組織業(yè)務(wù)過程協(xié)同模型能夠提高模型的相容性驗證效率，減少了形式驗證時間。文獻[8]以Petri網(wǎng)為基礎(chǔ)，提出了一種分而治之的方法，來分析在時間約束下的Web服務(wù)流程的相容性，該方法在生成模塊化的時間狀態(tài)圖的情況下，不僅能夠有效地檢測違反時間約束的多個Web服務(wù)組合，而且也提供了可靠和可用的服務(wù)執(zhí)行路徑以確保用戶服務(wù)的成功執(zhí)行。文獻[9]對基于虹吸管、陷阱、S-不變量、加模S-不變量等結(jié)構(gòu)特性以及基于狀態(tài)方程解存在性的不可達標識判定方法進行分析，研究了這些方法可以判定的不可達標識之間的相互關(guān)系，建立了Petri網(wǎng)不可達標識的分類體系，通過一個跨組織協(xié)同業(yè)務(wù)過程模型的不相容狀態(tài)，檢測說明了標識不可達判定方法的應(yīng)用。

進程代數(shù)方面：文獻[10]提出了一種基于分布式協(xié)調(diào)模型的方法，該方法通過失敗等價行為語義保持的投影規(guī)則，使用CSP對協(xié)作流程進行建模，并將協(xié)作流程的相容性分析轉(zhuǎn)換為對分布式下的協(xié)作子流程的成對相容性檢查，并進一步提出了一種基于適配的檢查方法。文獻[11]基于Pi演算對協(xié)同業(yè)務(wù)過程進行建模，并使用Pi演算的約簡規(guī)則對業(yè)務(wù)過程間的交互協(xié)議進行約簡，以判斷是否存在交互異常。文獻[12]基于Pi演算提出一種Web服務(wù)行為相容性的定性判定與定量計算方法，該方法首先通過算法自動地將Web服務(wù)行為和Web服務(wù)之間的交互行為表達成Pi演算進程，然后借助Pi演算的操作語義和形式化推演實現(xiàn)服務(wù)行為相容性自動的定性判定，隨后在Pi演算的進程變換理論的基礎(chǔ)上提出算法，實現(xiàn)服務(wù)相容性自動的定理計算。

自動機方面：文獻[13]為區(qū)分未指定接收的失配和死鎖，采用標簽轉(zhuǎn)換系統(tǒng)對Web服務(wù)業(yè)務(wù)的行為協(xié)議進行描述，并提出了一種基于該描述的失配類型判定方法，該方法不僅能識別常見的失配類型，而且還能借助對組合的可比較路徑的判定區(qū)分未指定接收的失配和死鎖。文獻[14]對于Pi演算擴展了事務(wù)語義，將進程間的動作交互與跨組織膜活動相關(guān)聯(lián)來刻畫多業(yè)務(wù)事務(wù)協(xié)調(diào)行為，并基于等價自動機轉(zhuǎn)換思路繼承現(xiàn)有模型檢驗技術(shù)，驗證多業(yè)務(wù)事務(wù)是否滿足人們需要的各種性質(zhì)。

上述相關(guān)工作都為本文進一步展開跨組織協(xié)同業(yè)務(wù)過程的相容性檢測及修正提供了較好的研究基礎(chǔ)。然而，不論上述工作是采用Petri網(wǎng)、進程代數(shù)或者其他形式化工具對協(xié)同業(yè)務(wù)過程的相容性進行分析，都只是對是否滿足相容性進行了檢測，或者給出一些驗證方法，而并沒有針對檢測出來的不滿足相容性的情況提出一個系統(tǒng)的修正方法。

為了解決上述問題，本文提出了一種協(xié)同業(yè)務(wù)過程的相容性檢測及修正方法，該方法不僅能夠檢測出不相容的業(yè)務(wù)過程和協(xié)同業(yè)務(wù)過程，還能在不改變局部業(yè)務(wù)過程的情況下，對協(xié)同業(yè)務(wù)過程進行修正。

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

Petri網(wǎng)的概念是由德國科學家Petri在1962年他的博士論文“Kommunikation mit Automaten”中首次提出[15]。由于Petri網(wǎng)具有形式化語義、直觀的圖形表示、狀態(tài)的顯示表示以及大量成熟的分析工具支持等優(yōu)勢，目前Petri網(wǎng)在計算機、自動化等科學技術(shù)領(lǐng)域得到了廣泛的應(yīng)用。因此，本著Petri網(wǎng)的特點及優(yōu)勢，借鑒Aalst教授基于Petri網(wǎng)提出的工作流網(wǎng)（workflow net，WF-net）[1]以及面向跨組織管理提出的跨組織工作流網(wǎng)（IOWF）[16]，對業(yè)務(wù)過程和協(xié)同業(yè)務(wù)過程進行建模。

3.1 模型概述

協(xié)同業(yè)務(wù)過程中各個組織的業(yè)務(wù)過程間的關(guān)系形成了如圖1所示的協(xié)同業(yè)務(wù)過程模型：組織內(nèi)部的任務(wù)的執(zhí)行和狀態(tài)的轉(zhuǎn)換組成了一個業(yè)務(wù)過程，不同的業(yè)務(wù)過程之間通過消息庫所進行通信活動，構(gòu)成了協(xié)同業(yè)務(wù)過程。

Fig.1 Collaborative business process圖1 協(xié)同業(yè)務(wù)過程

3.2 業(yè)務(wù)過程

業(yè)務(wù)過程作為構(gòu)建跨組織協(xié)同業(yè)務(wù)過程模型中最小的、可重用的單元，被用來建模一個組織內(nèi)部的業(yè)務(wù)流程，表示該組織內(nèi)的所有活動及活動間關(guān)系的描述。

定義1（業(yè)務(wù)過程）業(yè)務(wù)過程是一個擴展的基本Petri網(wǎng)BP=(P,T,F,M,A,fm,i,o)，其中：

（1）P表示有限的庫所集合，且P?T≠?；P=PM?PG，PM表示特殊的庫所集合，即消息庫所，PG表示普通的庫所集合。

（2）T表示有限的變遷集合，且P?T=?。

（3）F表示業(yè)務(wù)過程中的流關(guān)系，且F?(P×T)?(T×P)。

（4）M：M?P，稱為業(yè)務(wù)過程的一個狀態(tài)，初始狀態(tài)用M0表示，記為M0={i}。

（5）A表示語義標識有限集。

（6）fm：PM→A，為消息庫所到語義標識的映射，表示每個消息庫所pm關(guān)聯(lián)一個唯一的語義標識a。

（7）i、o表示兩個特殊的庫所，且i,o∈P，其中庫所i表示起始庫所，即●i=?，庫所o表示結(jié)束庫所，即o●=?。

（8）假如增加新變遷t*到BP，用來連接起始庫所i和結(jié)束庫所o（●t*={o}∧t*●={i}），那么這時所得的BP是強連通的。

在定義1中，BP中的每一個變遷表示組織內(nèi)部的一個具體的任務(wù)；流關(guān)系用來表示組織中任務(wù)與任務(wù)之間執(zhí)行的順序；任務(wù)的運行狀態(tài)由組織中的托肯分布情況表示，即狀態(tài)M。對于?p∈P，p中只有無托肯和只含1個托肯這兩種情況，若p中含有1個托肯，則p∈M，否則p?M。?BP，BP中的庫所記為BP.P，BP中的變遷記為BP.T，BP中的流關(guān)系記為BP.F，BP中的起始庫所記為BP.i，BP中的結(jié)束庫所記為BP.o。

3.3 協(xié)同業(yè)務(wù)過程

當企業(yè)的業(yè)務(wù)活動不再局限于內(nèi)部的以單目標為導向的業(yè)務(wù)過程時，企業(yè)的需求往往會超越傳統(tǒng)的組織界限，此時跨組織協(xié)同業(yè)務(wù)過程應(yīng)運而生，基于消息通信，不同組織業(yè)務(wù)過程之間進行交互構(gòu)成了協(xié)同業(yè)務(wù)過程，協(xié)同業(yè)務(wù)過程的定義如下。

定義2（協(xié)同業(yè)務(wù)過程）協(xié)同業(yè)務(wù)過程為一個二元組CBP=(MBP,AC)，其中：

（1）MBP表示業(yè)務(wù)過程的集合，即MBP={BP1,BP2,…,BPn}，n≥2。

（2）AC表示異步通信關(guān)系集合，且AC?PM×IP(TM)×IP(TM)：

①PM表示消息庫所集合；

②TM=?j∈{1,2,…,n}Tj，表示協(xié)同業(yè)務(wù)過程中業(yè)務(wù)過程參與通信活動的變遷集合；

③IP(TM)≠?∧IP(TM)?TM，表示IP(TM)為TM的非空子集。

?ac∈AC，ac=＜pij,Ti,Tj＞(i≠j)，其中：

（1）pij表示BPi中消息庫所pi和BPj中消息庫所pj的融合，使得BPi和BPj共享消息庫所pij。

（2）Ti和Tj表示BPi和BPj中與消息庫所pij存在流關(guān)系的變遷集合。

（3）fm(pi)=fm(pj)，表示庫所pi和庫所pj的語義標識相匹配，也是pi和pj可以融合成消息庫所的前提條件。

根據(jù)定義2，圖1可以形式化描述為CBP=(MBP,AC)，其中：

（1）MBP={BP1,BP2}

（2）AC?PM×IP(TM)×IP(TM)

①PM={pm1,pm2,pm3}；

②TM={t11,t13,t14,t21,t22,t24}；

③IP(TM)為TM的非空子集。

為了更好地分析跨組織協(xié)同業(yè)務(wù)過程并對其相容性進行分析，將協(xié)同業(yè)務(wù)過程進行展開得到協(xié)同業(yè)務(wù)過程展開模型如圖2所示，并給出定義。

Fig.2 Unfolding of collaborative business process圖2 協(xié)同業(yè)務(wù)過程展開

定義3（協(xié)同業(yè)務(wù)過程展開）U(CBP)=(PU,TU,FU)是CBP的展開，其中：

（1）PU=P*?PM?{i,o}

①P*=?j∈{1,2,…,n}BPj.P，表示協(xié)同業(yè)務(wù)過程中業(yè)務(wù)過程的庫所集合；

②PM表示消息庫所集合；

③i為起始庫所，用于標識協(xié)同業(yè)務(wù)過程展開模型執(zhí)行的開始；

④o為結(jié)束庫所，用于標識協(xié)同業(yè)務(wù)過程展開模型執(zhí)行的結(jié)束。

（2）TU=T*?{ti,to}

①T*表示協(xié)同業(yè)務(wù)過程中業(yè)務(wù)過程的變遷集合；

②ti為協(xié)同業(yè)務(wù)過程展開模型的起始變遷；

③to為協(xié)同業(yè)務(wù)過程展開模型的結(jié)束變遷。

（3）FU=F*?TM×PM?PM×TM?{(i,ti)}?{(to,o)}?j∈{1,2,…,n}{(ti,BPj.i)}?j∈{1,2,…,n}{(BPj.o,to)}，F(xiàn)* 表示協(xié)同業(yè)務(wù)過程中業(yè)務(wù)過程的流關(guān)系集合。

根據(jù)定義3，圖2中展開的協(xié)同業(yè)務(wù)過程模型可形式化描述為U(CBP)=(PU,TU,FU)，其中：

（1）PU=P*?PM?{i,o}

①P*={p11,p12,p21,p22,p23,p24}；

②PM={pm1,pm2,pm3}；

③i為起始庫所；

④o為結(jié)束庫所。

（2）TU=T*?{ti,to}

①T*={t11,t12,t13,t14,t21,t22,t23,t24}；

②ti為起始變遷；

③to為結(jié)束變遷。

（3）FU={(i,ti),(ti,i1),(ti,i2),(i1,t11),(t11,p11),(p11,t13),(t12,p12),(t13,p12),(p12,t14),(t14,o1),(o1,to),(to,o),(i2,t21),(t21,pm1),(pm1,t11),(t21,p21),(t21,p22),(p21,t22),(p22,t23),(t23,p23),(t22,p24),(p24,t24),(p23,t24),(t24,pm3),(t13,pm2),(pm2,t22),)(t24,o2),(o2,to)}

根據(jù)協(xié)同業(yè)務(wù)過程展開模型的形式化描述可知，通過增加的開始變遷ti和結(jié)束變遷to與局部業(yè)務(wù)過程的開始庫所和結(jié)束庫所連接在一起，同時，增加了全局起始庫所i和全局結(jié)束庫所o并分別與起始變遷ti和結(jié)束變遷to相連，最終得到了協(xié)同業(yè)務(wù)過程展開模型。異步通信關(guān)系通過語義標識映射到消息庫所PM。通過對變遷的顏色分類來區(qū)分跨組織協(xié)同業(yè)務(wù)過程中的變遷是否具有異步通信關(guān)系，有關(guān)系的用黑色的變遷表示，無關(guān)系的用白色變遷表示。

根據(jù)文獻[16]可知，協(xié)同業(yè)務(wù)過程CBP=(MBP,AC)的展開U(CBP)=(PU,TU,FU)是一個WF-net。因此本文的業(yè)務(wù)過程和協(xié)同業(yè)務(wù)過程展開模型都是基于基本Petri網(wǎng)的拓展，故可借鑒基本Petri網(wǎng)的變遷發(fā)生規(guī)則和可達圖的理論對本文的模型點火規(guī)則和可達圖進行定義。

定義4[17]（變遷發(fā)生規(guī)則）設(shè)U(CBP)=(PU,TU,FU)是一個協(xié)同業(yè)務(wù)過程的展開，并具有下述變遷發(fā)生規(guī)則：

（1）對于變遷t∈T，如果?p∈P:p∈●t→M(p)≥1，則說變遷t在狀態(tài)M下有發(fā)生權(quán)，記為M[t＞。

（2）若M[t＞，則在狀態(tài)M下，變遷t可以發(fā)生，從狀態(tài)M發(fā)生變遷t得到一個新的狀態(tài)M′，記為M[t＞M′，對?p∈P，滿足：

①M′(p)=M(p)-1，若p∈●t-t●；

②M′(p)=M(p)+1，若p∈t●-●t；

③M′(p)=M(p)，其他。

為了刻畫協(xié)同業(yè)務(wù)過程展開模型的可達圖，方便協(xié)同業(yè)務(wù)過程相容性修正工作的順利執(zhí)行，給出可達狀態(tài)集和可達圖的定義。

定義5[17]（可達狀態(tài)集）設(shè)U(CBP)=(PU,TU,FU)是一個協(xié)同業(yè)務(wù)過程的展開，其中M0∈M為U(CBP)的初始狀態(tài)。U(CBP)的可達狀態(tài)集R(M0)定義為滿足下面兩條件的最小集合：

（1）M0∈R(M0)；

（2）若M0∈R(M0)，且存在變遷t∈T使得M[t＞M′，則M′∈R(M0)。

定義6[17]（可達圖）設(shè)U(CBP)=(PU,TU,FU)是一個協(xié)同業(yè)務(wù)過程的展開，U(CBP)的可達圖定義為一個三元組RG[U(CBP)]=(R(M0),B,R)，其中：

（1）B={(Mi,Mj)|Mi,Mj∈R(M0)，且 ?tk∈T使得Mi[tk＞Mj}；

（2）R:B→T，R(Mi,Mj)=tk，當且僅當Mi[tk＞Mj。

4 協(xié)同業(yè)務(wù)過程相容性檢測

在協(xié)同業(yè)務(wù)過程中，協(xié)作過程涉及多個業(yè)務(wù)過程的交互，因此需要首先對每個參與協(xié)同的業(yè)務(wù)過程進行分析，在保證局部每個業(yè)務(wù)過程滿足相容性的條件下，進一步對跨組織協(xié)同業(yè)務(wù)過程進行全局觀的相容性分析。通過借鑒Aalst教授在文獻[16]中關(guān)于合理性的定義，給出業(yè)務(wù)過程相容性和協(xié)同業(yè)務(wù)過程相容性的定義。

定義7（業(yè)務(wù)過程相容性）一個業(yè)務(wù)過程BP=(P,T,F,M,PM,A,fm,i,o)是相容的，當且僅當 ?M(i→*M)?(M→*o)，表示對每個從初始狀態(tài)i可達的狀態(tài)M，必然存在一個從M到狀態(tài)o的發(fā)生序列，即起始庫所i中的托肯，總是能夠通過變遷到達結(jié)束庫所o中。為了能夠自動對業(yè)務(wù)過程是否滿足相容性進行檢測，基于深度優(yōu)先搜索（depth first search，DFS）提出了一種業(yè)務(wù)過程相容性檢測算法。

算法1業(yè)務(wù)過程相容性檢測算法

定義8（協(xié)同業(yè)務(wù)過程相容性）一個協(xié)同業(yè)務(wù)過程CBP=(MBP,AC)是相容的，當且僅當CBP滿足局部相容并且全局相容，其中：

（1）CBP局部相容是指CBP中的每一個BP都滿足業(yè)務(wù)過程相容性；

（2）CBP全局相容是指CBP的展開U(CBP)=(PU,TU,FU)滿足業(yè)務(wù)過程相容性。

根據(jù)定義8可知，協(xié)同業(yè)務(wù)過程的相容性不僅包括了構(gòu)成協(xié)同業(yè)務(wù)過程的局部業(yè)務(wù)過程的相容性，還包括了多個局部業(yè)務(wù)過程交互構(gòu)成的協(xié)同業(yè)務(wù)過程的相容性。算法2對本文所使用的協(xié)同業(yè)務(wù)過程相容性的檢測算法過程進行了描述。

算法2協(xié)同業(yè)務(wù)過程相容性檢測算法

5 協(xié)同業(yè)務(wù)過程相容性修正

跨組織協(xié)同業(yè)務(wù)過程相容性檢測及修正方法的研究思路大致如圖3所示。

本文方法分為3個過程：跨組織協(xié)同業(yè)務(wù)過程建模；協(xié)同業(yè)務(wù)過程相容性檢測；協(xié)同業(yè)務(wù)過程相容性修正。首先，跨組織協(xié)同業(yè)務(wù)過程采用Petri網(wǎng)作為形式化工具進行建模；然后，對業(yè)務(wù)過程和協(xié)同業(yè)務(wù)過程的相容性進行定義并分別給出檢測算法；最后是協(xié)同業(yè)務(wù)過程相容性的修正。下面將詳細闡述本文提出的協(xié)同業(yè)務(wù)過程相容性檢測及修正方法。

Fig.3 Method for compatibility detection and correction of collaborative business process圖3 協(xié)同業(yè)務(wù)過程相容性檢測及修正方法

本文以文獻[11]中的4個參與者構(gòu)成的購買過程案例為基礎(chǔ)進行擴展，詳細闡述本文如何在不改變企業(yè)局部業(yè)務(wù)過程的情況下對跨企業(yè)協(xié)同業(yè)務(wù)過程相容性進行修正的方法。

Fig.4 Purchasing process with 4 participants圖4 4個參與者構(gòu)成的購買過程

圖4展示的購買過程的執(zhí)行流程如下：客戶提交訂單給代理商（步驟1）；代理商收到訂單后，向銀行請求查詢該客戶的信用記錄（步驟2）和向供貨商請求查詢庫存信息（步驟4）；如果該客戶信用記錄良好（步驟3），并且?guī)齑鏀?shù)量足夠（步驟5），則代理商向客戶發(fā)送支付請求（步驟7）；客戶完成支付后（步驟8），代理商通知供貨商發(fā)貨（步驟9）；供貨商收到運輸請求后將貨物運輸給客戶（步驟10）；當客戶收到貨物后，發(fā)送確認消息給代理商（步驟12）和供貨商（步驟11），完成交易。注意：在上述購買過程中，客戶在訂單支付前，可以取消交易；此外，代理商在發(fā)送支付請求給客戶前，也可以取消交易（步驟6）。該實例是沒有非確定性選擇和循環(huán)的情況。

Fig.5 Business process with 4 participants圖5 4個參與者的業(yè)務(wù)過程

通過對上述案例的分析，根據(jù)定義1可以得到4個參與者的業(yè)務(wù)過程如圖5所示，限于篇幅，對其中最為復雜的業(yè)務(wù)過程代理商的形式化描述如下所示：

通過分析4個參與者業(yè)務(wù)過程在整個購買過程中的交互以及消息庫所的語義標識是否相匹配，并根據(jù)定義2可以得到4個參與者的協(xié)同業(yè)務(wù)過程的形式化描述如下所示：

進一步根據(jù)協(xié)同業(yè)務(wù)過程展開的定義3可以得到4個參與者協(xié)同業(yè)務(wù)過程展開的模型如圖6所示，其形式化描述如下所示：

Fig.6 Unfolding of collaborative business process with 4 participants圖6 4個參與者的協(xié)同業(yè)務(wù)過程展開

利用算法1及4個參與者業(yè)務(wù)過程的可達圖對圖5進行檢測可判定，購買過程中的4個參與者的業(yè)務(wù)過程均是滿足相容性的。4個參與者的業(yè)務(wù)過程可達圖如圖7所示。

Fig.7 Reachability graph of 4 participants'business process圖7 4個參與者業(yè)務(wù)過程的可達圖

利用算法2對圖6中的4個參與者的協(xié)同業(yè)務(wù)過程展開進行檢測可知，在購買過程實例中，4個參與者業(yè)務(wù)過程交互構(gòu)成的協(xié)同業(yè)務(wù)過程展開是不滿足相容性的，即該4個參與者的協(xié)同業(yè)務(wù)過程需要修正。由Petri網(wǎng)模擬工具PIPE（platform independent Petri net editor）模擬可知，4個參與者的協(xié)同業(yè)務(wù)過程的可達圖過于復雜，多達48維的狀態(tài)轉(zhuǎn)換，限于篇幅，本文不再列出。通過對4個參與者的協(xié)同業(yè)務(wù)過程的變遷執(zhí)行分析可得，滿足相容性定義的從起始庫所（PStart）到結(jié)束庫所（PEnd）的所有可達軌跡如圖8所示，一共有198條。

Fig.8 Compatible reachability trace(part)圖8 相容的可達軌跡（部分）

同時，因為4個參與者協(xié)同業(yè)務(wù)過程不滿足相容性，所以必然存在從起始庫所（PStart）出發(fā)，但結(jié)束庫所不是PEnd的不相容的可達軌跡，共有102條，如圖9所示。

Fig.9 Incompatible reachability trace(part)圖9 不相容的可達軌跡（部分）

將4個參與者協(xié)同業(yè)務(wù)過程中的不滿足相容性的102條可達軌跡剔除，對滿足相容性的198條可達軌跡進行提取并按照挖掘可擴展標記語言（mining extensible markup language，MXML）的標準和可擴展標記語言的（extensible markup language，XML）語法將提取的相容可達軌跡轉(zhuǎn)換成可擴展時間流（extensible event stream，XES）格式的文檔，部分如下：

ProM[18]是一個開源且成熟的過程挖掘平臺，可在http://www.processmining.org下載，本文在該平臺基于Aalst教授提出的α算法[19]對4個參與者協(xié)同業(yè)務(wù)過程進行挖掘，得到4個參與者協(xié)同業(yè)務(wù)過程，如圖10所示。

Fig.10 Business process with 4 participants after mining圖10 挖掘后的4個參與者協(xié)同業(yè)務(wù)過程

結(jié)合挖掘后的4個參與者的協(xié)同業(yè)務(wù)過程及各自的業(yè)務(wù)過程，得到經(jīng)過修正后的4個參與者的協(xié)同業(yè)務(wù)過程展開，如圖11所示。

圖11中，形如＜ta1,t1＞的符號表示同步因子，作用是使得4個參與者的局部業(yè)務(wù)過程中的變遷ta1與協(xié)同業(yè)務(wù)過程中的變遷t1之間滿足同步關(guān)系。通過算法1和算法2對修正后的4個參與者的協(xié)同業(yè)務(wù)過程進行檢測可知，4個參與者局部業(yè)務(wù)過程分別滿足相容性，并且修正后的協(xié)同業(yè)務(wù)過程同樣滿足相容性。

進一步，基于同步關(guān)系，對滿足同步關(guān)系的變遷進行融合，得到修正后的4個參與者的協(xié)同業(yè)務(wù)過程展開，如圖12所示。

Fig.12 Unfolding of collaborative business process with 4 participants after correcting圖12 修正后的4個參與者的協(xié)同業(yè)務(wù)過程展開

Fig.11 Collaborative business process with 4 participants after correcting圖11 修正后的4個參與者的協(xié)同業(yè)務(wù)過程

利用算法2對修正后的4個參與者的協(xié)同業(yè)務(wù)過程展開進行檢測可知，4個參與者協(xié)同業(yè)務(wù)過程展開同樣也滿足相容性，即在不改變局部業(yè)務(wù)過程的情況下，對本來不相容的協(xié)同業(yè)務(wù)過程進行修正，最終達到一種好的滿足相容性的4個參與者的協(xié)同業(yè)務(wù)過程模型。

6 結(jié)束語

針對跨組織協(xié)同業(yè)務(wù)過程中的相容性問題，目前大多數(shù)學者主要是從協(xié)同業(yè)務(wù)過程的相容性檢測方法進行分析和研究，而針對協(xié)同業(yè)務(wù)過程不相容情況下的修正方法的研究，尚屬鮮見。為此，本文結(jié)合Petri網(wǎng)及過程挖掘的相關(guān)理論，提出了一種跨組織協(xié)同業(yè)務(wù)過程的相容性檢測及修正方法。主要工作如下：

（1）基于擴展的基本Petri網(wǎng)對業(yè)務(wù)過程及協(xié)同業(yè)務(wù)過程進行建模。

（2）對業(yè)務(wù)過程和協(xié)同業(yè)務(wù)過程的相容性進行定義，并分別給出了相應(yīng)的檢測算法。

（3）以現(xiàn)實中的購買過程為案例進行說明，對于該購買過程中存在的不相容的協(xié)同業(yè)務(wù)過程，通過Petri網(wǎng)及過程挖掘技術(shù)對其進行修正。

結(jié)果表明，在不改變局部業(yè)務(wù)過程的情況下，對本來不相容的協(xié)同業(yè)務(wù)過程進行修正最終達到一種好的滿足相容性的協(xié)同業(yè)務(wù)過程模型。

下一步研究方向為考慮如何對具有個性化特征的協(xié)同業(yè)務(wù)過程進行相容性檢測和修正。

[1]Van der Aalst W M P.The application of Petri nets to workflow management[J].Journal of Circuits Systems&Computers,1998,8(1):21-66.

[2]Lu Yahui,Ming Zhong,Zhang Li.Collaborative patterns of business process[J].Computer Integrated Manufacturing Systems,2011,17(8):1569-1579.

[3]Dai Fei,Mo Qi,Lin Leilei,et al.Collaboration business process modeling based on Petri nets and Pi calculus[J].Journal of Frontiers of Computer Science and Technology,2015,9(6):692-706.

[4]Li Xitong,Fan Yushun.Analyzing compatibility and similarity of Web service processes[J].Chinese Journal of Computers,2009,32(12):2429-2437.

[5]Tan Wei,Fan Yushun,Zhou Mengchu.A Petri net-based method for compatibility analysis and composition of Web services in business process execution language[J].IEEE Transactions on Automation Science&Engineering,2009,6(1):94-106.

[6]Gong Shuai,Xiong Jinhua,Liu Zhiyong.Web service compatibility verification based on conflict interactions[J].Chinese Journal of Computers,2013,36(12):2479-2490.

[7]Mo Qi,Dai Fei,Zhu Rui,et al.Parallel modeling for crossorganization business process[J].Computer Integrated Manufacturing Systems,2015,21(4):1051-1062.

[8]Du Yanhua,Tan Wei,Zhou Mengchu.Timed compatibility analysis of Web service composition:a modular approach based on Petri nets[J].IEEE Transactions on Automation Science&Engineering,2014,11(2):594-606.

[9]Lu Faming,Zeng Qingtian,Duan Hua,et al.Decidability method of Petri net non-reachability marks and its application in deadlock detection[J].Computer Integrated Manufacturing Systems,2016,22(2):465-475.

[10]Qiao Xiaoqiang,Wei Jun,Huang Tao.Service collaboration approach based on decentralized mediation model:service collaboration approach based on decentralized mediation model[J].Journal of Software,2009,20(6):1470-1486.

[11]Zhang Li,Lu Yahui,Xu Faye.Unified modelling and analysis of collaboration business process based on Petri nets and Pi calculus[J].IET Software,2010,4(5):303-317.

[12]Deng Shuiguang,Li Ying,Wu Jian,et al.Determination and computation of behavioral compatibility for Web services[J].Journal of Software,2007,18(12):3001-3014.

[13]Zheng Jian,Jiang Jianhui.Labeled transition system based decision method for Web service behavior mismatch type[J].Computer Integrated Manufacturing Systems,2011,17(12):2743-2751.

[14]Yuan Min,Huang Zhiqiu,Hu Jun.Modeling and verification of cross-organizational multi-business transactions[J].Journal of Software,2012,23(3):517-538.

[15]Petri C A.Kommunikation mit automaten[D].Bonn:University of Bonn,1962.

[16]Van der Aalst W M P.Modeling and analyzing interorganizational workflows[C]//Proceedings of the 1st International Conference on Application of Concurrency to System Design,Fukushima,Japan,Mar 23-26,1998.Washington:IEEE Computer Society,1998:262-272.

[17]Wu Zhehui.Introduction to Petri net[M].Beijing:China Machine Press,2006:6-47.

[18]Van Dongen B F,de Medeiros A K A,Verbeek H M W,et al.The ProM framework:a new era in process mining tool support[C]//LNCS 3536:Proceedings of the 26th International Conference on Applications and Theory of Petri Nets,Miami,USA,Jun 20-25,2005.Berlin,Heidelberg:Springer,2005:444-454.

[19]Van der Aalst W M P,de Medeiros A K A,Weijters A J M M.Genetic process mining[C]//LNCS 3536:Proceedings of the 26th International Conference on Applications and Theory of Petri Nets,Miami,USA,Jun 20-25,2005.Berlin,Heidelberg:Springer,2005:48-69.

附中文參考文獻:

[2]盧亞輝,明仲,張力.協(xié)同業(yè)務(wù)過程模式的研究[J].計算機集成制造系統(tǒng),2011,17(8):1569-1579.

[3]代飛,莫啟,林雷蕾,等.結(jié)合Petri網(wǎng)和Pi演算的協(xié)同業(yè)務(wù)過程建模[J].計算機科學與探索,2015,9(6):692-706.

[4]李喜彤,范玉順.Web服務(wù)流程相容性和相似性分析[J].計算機學報,2009,32(12):2429-2437.

[6]公帥,熊錦華,劉志勇.基于交互沖突的服務(wù)互操作匹配性檢測[J].計算機學報,2013,36(12):2479-2490.

[7]莫啟,代飛,朱銳,等.跨組織業(yè)務(wù)過程協(xié)同并行建模[J].計算機集成制造系統(tǒng),2015,21(4):1051-1062.

[9]魯法明,曾慶田,段華,等.Petri網(wǎng)不可達標識的判定方法研究及其在死鎖檢測中的應(yīng)用[J].計算機集成制造系統(tǒng),2016,22(2):465-475.

[10]喬曉強,魏峻,黃濤.基于分布式協(xié)調(diào)模型的服務(wù)協(xié)作方法研究[J].軟件學報,2009,20(6):1470-1486.

[12]鄧水光,李瑩,吳健,等.Web服務(wù)行為相容性的判定與計算[J].軟件學報,2007,18(12):3001-3014.

[13]鄭劍,江建慧.基于標簽轉(zhuǎn)換系統(tǒng)的Web服務(wù)行為失配類型的判定方法[J].計算機集成制造系統(tǒng),2011,17(12):2743-2751.

[14]袁敏,黃志球,胡軍.跨組織多業(yè)務(wù)事務(wù)建模與驗證方法[J].軟件學報,2012,23(3):517-538.

[17]吳哲輝.Petri網(wǎng)導論[M].北京:機械工業(yè)出版社,2006:6-47.

Compatibility Detection and Correction of Collaborative Business Process*

ZHENG Ming1,MO Qi1,2+,ZHOU Xiaoxuan1,LI Tong1,2,XIE Zhongwen1,2,XIANG Wenkun1

1.School of Software,Yunnan University,Kunming 650500,China
2.Key Laboratory in Software Engineering of Yunnan Province,Kunming 650500,China

2017-03,Accepted 2017-06.

With the development of economic globalization,the business operations in enterprises have switched from in-company solo business process to inter-enterprise cooperative business process.Thus,the research on the compatibility and correction of cooperative business process is necessary to make sure that the cooperative business process can operate correctly.This paper comes up with a method about compatibility detection and correction for interorganization cooperative business process therefor,based on the theory of Petri nets and process mining:First of all,using Petri net to model the business process and cooperative business process;Then,defining the compatibility in business process and cooperative business process,and providing the corresponding detection algorithms respectively;Finally,taking an actual purchasing process as an example,and detecting and correcting the incompatible cooperative business process in it.Case study shows that it is feasible to correct the incompatible cooperative business process and end up in a well-compatible cooperative business process model without any changes in local business process.

collaborative business process;compatibility;corrective method

+Corresponding author:E-mail:moqiyueyang@163.com

10.3778/j.issn.1673-9418.1703075

*The National Natural Science Foundation of China under Grant Nos.61379032,61262024,61462092,61462095,61662085(國家自然科學基金);the Graduate Scientific Research Innovation Foundation of Yunnan University under Grant No.111(云南大學研究生科研創(chuàng)新基金項目).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-06-05,http://kns.cnki.net/kcms/detail/11.5602.TP.20170605.1343.002.html

ZHENG Ming，MO Qi，ZHOU Xiaoxuan,et al.Compatibility detection and correction of collaborative business process.Journal of Frontiers of Computer Science and Technology,2017,11(12)：1907-1921.

A

TP311

ZHENG Ming was born in 1992.He is an M.S.candidate at Yunnan University,and the student member of CCF.His research interests include software engineering,business process management and formal methods.

鄭明（1992—），男，安徽安慶人，云南大學碩士研究生，主要研究領(lǐng)域為軟件工程，業(yè)務(wù)過程管理，形式化方法。

MO Qi was born in 1986.He received the Ph.D.degree from Yunnan University in 2015.Now he is a lecturer at Yunnan University,and the member of CCF.His research interest is business process management.

莫啟（1986—），男，湖南岳陽人，2015年于云南大學獲得博士學位，現(xiàn)為云南大學講師，CCF會員，主要研究領(lǐng)域為業(yè)務(wù)過程管理。

ZHOU Xiaoxuan was born in 1993.She is an M.S.candidate at Yunnan University,and the student member of CCF.Her research interests include software engineering,software evolution and data mining.

周小煊（1993—），女，吉林長春人，云南大學碩士研究生，CCF學生會員，主要研究領(lǐng)域為軟件工程，軟件演化，數(shù)據(jù)挖掘。

LI Tong was born in 1963.He received the Ph.D.degree in software engineering from De Montfort University in 2007.Now he is a professor and Ph.D.supervisor at Yunnan University,and the senior member of CCF.His research interests include software engineering and information security.

李彤（1963—），男，河北石家莊人，2007年于英國De Montfort大學軟件工程專業(yè)獲得博士學位，現(xiàn)為云南大學教授、博士生導師，CCF高級會員，主要研究領(lǐng)域為軟件工程，信息安全。

XIE Zhongwen was born in 1982.He received the Ph.D.degree from Yunnan University in 2012.Now he is a lecturer at Yunnan University,and the member of CCF.His research interest is software engineering.

謝仲文（1982—），男，福建漳州人，2012年于云南大學獲得博士學位，現(xiàn)為云南大學講師，CCF會員，主要研究領(lǐng)域為軟件工程。

XIANG Wenkun was born in 1993.He is an M.S.candidate at Yunnan University.His research interests include software engineering,cloud computing and data mining.

向文坤（1993—），男，湖北仙桃人，云南大學碩士研究生，主要研究領(lǐng)域為軟件工程，云計算，數(shù)據(jù)挖掘。