基于Ｐｅｔｒｉ網的協同三維建模工作流模型研究

摘 要:通過分析大規模三維場景單機建模所面臨的局限性問題，對三維場景協同建模理論進行了描述。結合workflow net的定義以及建立工作流模型的方法，采用基于Petri網擴展的、用于復雜工作流模型設計的建模方法建立協同三維建模的工作流模型，并通過Petri網相關理論分析得出所建模型具有可達性、有界性、活性，并且是安全可靠的，同時對系統中必須加以解決的并發問題進行了相關的探討。

關鍵詞:協同建模; Petri網; 工作流; 可達性; 可覆蓋性樹

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2009)09-3300-04

doi:10.3969/j.issn.1001-3695.2009.09.028

Research on workflow model of cooperative three-dimensionalmodeling based on Petri net

WEIShuanga，b， ZHAO Hong-lingb， ZHANGTaoa，b， WANG Zong-minb

(a. College of Information Engineering， b.Henan Provincial Key Lab on Information Network， Zhengzhou University， Zhengzhou 450001， China)

Abstract:By analyzing the problems of single modeling large-scale virtual three-dimensional scene and considering the collabo-rative theory in scene modeling， this article described the theory of collaborative modeling of three-dimensional scene. And then built the Petri net model using workflow-net and its associated rules， which was based on Petri net and used for complicated workflow model design. Through analysis of the Petri net theory， provided the accessibility， community， activity， safe and reliable of the model， meanwhile discussed concurrent problem that needed to be solved within the system.

Key words:collaborative modeling; Petri net; workflow; accessibility; coverability tree

0 引言

近年來，虛擬校園、虛擬城市等作為一種可視化的信息平臺[1]，其包含的信息量越來越豐富，規模也越來越大，給場景建模和管理帶來極大挑戰。以往的建模方法和工具沒有考慮網絡技術的應用，只是單機集中完成建模，不僅工作效率低，也不利于基于網絡的協同建模，已經滿足不了實際生產的需求。解決這一問題的一個可行方法就是為三維模型的建模系統提供協作成員之間的協同支持，建立相應的計算機輔助協同建模系統，這有利于多空間分布的建模人員能夠根據自己的建模任務共同創建分布式模型對象，從而高效地完成建模的工作。計算機支持的協同工作(computer supported cooperation work，CSCW)是一個利用計算機技術、網絡與通信技術、多媒體技術、人機接口技術，將時間上分離、空間上分布，而工作上又相互依賴的多個協作成員及其活動有機地組織起來，以共同完成某一項任務的分布式計算機環境[2]。隨著計算機通信、分布式計算機、多媒體技術等的發展，CSCW正從概念逐步走向應用。文獻[3]在對網絡化協同產品開發基本概念和內涵特征進行詳細分析的基礎上，依次從概念模型、協同模型和形成過程三個方面對網絡化協同產品開發機理進行深入研究，構建由組織模型、過程模型、產品模型和資源模型四類子模型所組成的網絡化協同產品開發概念模型，分析協同發生的三維場景(時間維、空間維和對象維)，探索網絡化協同產品開發的形成過程。文獻[4]針對當前油田注水生產現狀和注水生產管網建模的局限性，通過對協同工作理論的研究，分析管網建模和協同工作的結合點，建立起油田注水生產過程仿真分布式協同建模系統，為油田地面工程建立仿真模型提供了一種實用的技術和工具。在虛擬場景三維建模的開發中，協同已經被廣泛地應用在產品開發、機械設計等領域，主要集中在對協同CAD建模[5，6]的研究。在“鄭州大學數字化校園”項目中，采用的是Multigen Creator模型，這就需要考慮如何實現協同Creator建模，目前還沒有廣泛深入的研究。因此，把CSCW引入三維模型協同建模系統，將增強協作人員的協同工作能力，提高合作效率。

在進行協同建模系統的工作流程設計中，清晰描述復雜的各項工作流程的條件和分支邏輯是比較困難的。Petri網有精確的定義，是一個模型化的工具，它用于模型化離散事件的系統問題，與許多其他非形式化的框圖技術相比，避免了模糊性、不確定性和矛盾性，并且可以有效地解決工作流中的沖突問題，用Petri網定義工作流并且建立模型，對設計開發復雜的項目流程有直接的指導意義。

1 大規模三維場景協同建模理論

1.1 大規模三維場景建模的特點

一個大規模的虛擬場景往往由許多不同的對象組成，如學校的校園由多個校區組成，每個校區又包含了樹木、草地、樓房等三維模型，它們之間形成一種層次包含關系。因此，可以把校區、樹木、草地、樓房等對象看做特殊“零部件”對象，整個校園就是由這些特殊零部件組成的“產品”。目前人們對大規模的虛擬場景的一次性生成技術和相應軟件工具的研究還不成熟，并且由于精度等原因而難以達到實用效果。人們的研究更多地集中在如何快速地、盡可能自動地生成樓房、樹木等對象，然后再人工集成這些對象形成復雜的場景。根據這些對象的特點，人們已經研究出不少比較成熟的相關技術，并開發出相應的系統工具，所以，創建一個大規模的虛擬場景時，往往要用到各種開發工具。但是這些系統工具只支持單用戶、單機操作，所涉及的知識也不盡相同，并且為了達到一定的設計精度往往需要更多的人為參與，顯然對于設計一個由成千上萬對象組成的復雜虛擬場景來說，這種串行設計方法具有開發周期長、設計成本高等缺點。

通過分析不難發現，一個大規模的虛擬場景的創建過程具有以下幾個特點[1]:

a)多主體性。在設計活動中一般由Creator建模人員、攝影師、貼圖人員等相互獨立的并具有不同領域知識的許多人員參與。

b)協同性。各種設計人員之間需要相互通信，以便共享和交換信息，并且工作中一旦發生沖突，需要進行協調和溝通。

c)共同性。設計人員要實現的最終設計目標是相同的，因此應具有一致的設計環境和上下文信息。

這些特點表明，采用協同技術可以實現大規模場景設計從傳統單機單用戶的串行設計模式向以網絡為中心的分布式多用戶的協同設計模式轉變，使得處于不同地理位置的多個用戶同時對同一場景進行設計成為可能。

在這里，引入協同思想來設計一個面向大規模虛擬場景協同建模的支撐模型，功能包括:可實現不同地理位置的多個用戶共同對同一場景建模，并獲得各地的模型增量信息，減少網絡傳輸量;可實現大規模場景增量數據的統一管理，為用戶的查詢與共享提供了極大的方便;可提供過程的管理與監控，為場景的協同設計提供必要的支持。

1.2 協同建模的系統框架

協同建模系統由分布式客戶端和服務器兩部分構成，總體框架如圖1所示。

協同開發人員通過本地分布式客戶端實現協同建模過程。分布式客戶端包括模型編輯模塊和增量信息模塊。其中，模型編輯模塊實現對三維模型的建模以及對已有模型的結構和屬性進行編輯;增量信息模塊實現三維模型之間的對比操作，獲得本地協同建模的增量信息數據，并實現增量信息的傳輸。

服務器主要是對協作開發成員上傳的模型增量數據進行有效的版本管理，包括模型版本庫和模型版本顯示兩部分。模型版本庫用于存儲協同用戶上傳的三維模型增量信息，包括增量信息所屬的版本號、模型名、模型的節點名、節點屬性及提交時間等。模型版本顯示主要是通過讀取模型版本庫中的增量信息并進行版本增量信息重組而形成各個版本完整的模型信息，并且以版本樹的形式顯示出來，管理員可以進行有效的添加、刪除等操作。

客戶端、服務器分別維護一個動態客戶端列表，用于記錄所有協同開發客戶端的動態信息，包括客戶端的在線情況、編輯模型的版本及下載時間等。在協同建模系統中，客戶端與服務器端之間的消息和數據的網絡通信與傳輸是支撐系統的核心，它包括主動傳輸和被動傳輸兩種方式。一方面協同用戶主動與服務器通信并發送增量數據;另一方面服務器在接收新版本的增量請求后，會主動向其他在線的客戶端發送當前最新版本的三維模型數據信息，使協作開發人員可以隨時了解當前最新版本模型，避免協同建模過程中沖突、碰撞的概率，而且能夠降低服務器的工作量，縮短處理時間，從整體上提高工作效率。

2 協同建模的核心流程

協同建模系統包含協同人員、模型版本號、版本信息、管理等多方面的因素，一般至少會有兩個分布式的協同客戶端共同承擔協同建模的任務，根據協同用戶工作的進程以及當前的狀態和動作，采用有效的方法解決可能出現的問題。協同建模過程主要體現在協同用戶在完成本地建模之后向服務器端傳輸模型版本增量信息直至服務器成功接收的整個過程，如圖2所示。當有協同用戶向服務器提交版本增量信息時，首先要判斷模型版本庫是否為空，如果為空，就直接存儲至模型版本庫，作為三維模型的最原始版本;否則，就要判斷提交的模型版本號是否與當前模型版本庫中的版本號一致。如果不一致，服務器就會主動向該協同用戶發送新版本的模型;如果一致，接著判斷提交的增量信息間是否存在操作沖突，然后才能決定客戶端是否接收此次提交。

在上述判斷提交的增量信息是否有沖突的過程中，當只有一個協同用戶提交時，不可能存在沖突的問題;只有當多個用戶同時處于提交增量信息時，提交的信息才有可能發生沖突。根據上述流程圖，增量信息的沖突判斷包括版本沖突判斷和操作沖突判斷兩個順序的判斷過程。

2.1 版本沖突判斷

假設有兩個用戶A、B目前正在參與協同工作，而且模型的版本均為2.1，當前模型庫中最新的版本為2.2，那么如果在同一時間A、B同時上傳版本為2.2的增量信息，服務器會順序依次接收增量信息，即在協作模型中，各個分布式協作開發端可能會并行提交增量信息，但是在服務器端這些增量信息會被串行化。這時，如果服務器先處理了其中一個的增量信息，那么此時版本庫中的模型最新版本就會發生變化，意味著另一個用戶提交的增量信息就有可能無效，因為這些增量信息是與舊版本進行對比生成的。

2.2 操作沖突判斷

為了統一管理增量操作的版本數據，通過保存每個版本中的增量操作信息就可以建立一個版本的增量操作信息表。一個版本的增量操作的數據結構如下:

versionactionparnodenodeIDnodetypetextureuser

其中:version表示用戶每次提交的修改增量所屬的版本號，當用戶原子操作提交成功時，所屬版本號為最新版本號加1;action表示模型的幾何修改操作，包括createnode、deletenode、modifynodeID等;parnode表示當前操作節點所屬的父節點;nodeID表示當前操作節點的節點名字;nodetype表示當前操作節點的節點類型，包括root(根節點)、group(組節點)、object(體節點)、face(面節點);texture表示當前節點所引用的紋理，其中只有面節點才有紋理;user表示提交當前修改操作的用戶。

當多個用戶并發提交增量信息時，通過增量信息屬性間的對比，就可以進行操作沖突判斷。當A、B提交的增量信息有沖突時，服務器返回沖突提示，本次提交結束。

3 基于Petri網的三維建模協同工作流模型

3.1 Petri網的基本理論

Petri網作為一種形式化描述工具，主要用來對系統進行設計、分析和模擬[7]。Petri網的特點在于它側重于系統的變化，包括變化發生的條件、變化的結果以及變化之間的內在聯系。一個Petri網可以形式化地定義如下:

定義1 Petri網PN是一個三元組PN=(P， T， F)。其中:P是有限個庫所的集合;T是有限個變遷的集合(P∩T=);F是由一個P元素和一個T元素組成的有序偶的集合，稱為PN的流關系。庫所和變遷分別稱為P元素和T元素，X=P∪T稱為PN的元素集，其充分必要條件是:

a)P∩T=;

b)P∪T≠;

c)FP×T∪T×P(×為笛卡爾積);

d)dom(F)∪cod(F)=P∪T。

其中，dom(F)={x|y:(x，y)∈F}，cod(F)={y|x:(x，y)∈F}分別為F的定義域和值域。

3.2 基于Petri網的工作流技術

工作流是人們為了提高辦公效率， 針對工作中具有固有程序的常規活動提出的一個概念。按照工作流管理聯盟(WfMC)的定義:全部或部分由計算機支持或自動處理的業務過程稱之為工作流，它是業務流程在計算機上的形式化描述和實現[8]。由定義可知，工作流的處理過程具有自動性、并行性和離散性等特點。目前已經有多種工作流形式化建模方法，如有向圖、Petri網、對象模型以及基于約束條件的形式語言文法表示等。

工作流網是在Petri網的基礎上發展起來的，專門用于業務流程的建模，是一種特殊的Petri網。鑒于三維模型協同建模系統具有并發性、分布式等特點，結合系統設計應用基于Petri網的工作流理論對系統進行結構化建模。對工作流的控制流維度建模的Petri網稱為工作流網(WF-Net)[9，10]。

定義2 Petri網PN=(P， T， F)是WF-Net。當且僅當:a)存在一個源庫所i∈P，使得#8226;i=;b)存在一個匯結庫所o∈P，使得o#8226;=;c)每個節點x∈P∪T都位于從i到o的一條路徑上。

WF-Net有如下的性質:

Petri網PN=(P， T， F)是一個工作流網，則:a)如果PN是一個擁有源庫所i 的WF-Net，那么對于任何庫所p∈P:p#8226;≠或p=i，即i是惟一的源庫所;b)如果PN是一個擁有匯結庫所o的WF-Net， 那么對于任何庫所p∈P:p#8226;≠或p=o，即o是惟一的匯結庫所;c)如果添加一個變遷t到PN， 用來連接匯結庫所o和源庫所i， 那么所得到的Petri網是強連通的。

在工作流網絡模型中，任務包括四種路由結構， 即順序、并行、選擇和循環，如圖3所示。在實現時， 通過引入下面的符號來描述路由類別:變遷的輸出端用符號<來表示與分支;變遷的輸入端用符號>來表示與合并;變遷的輸出端用符號>來表示或分支;變遷的輸入端用符號<來表示或合并。

3.3 基于Petri網的三維建模協同工作流模型

通過上述對協同建模過程的流程分析，可建立協同建模過程Petri網模型(圖4)。圖4中的庫所集元素如表1所示，變遷集元素如表2所示。

在整個協同建模的過程中，客戶端初始化申請連接服務器，服務器端生成最新版本模型并同時發送給所有要求連接的客戶端，P0就是服務器端生成最新版本模型的過程，它在初始狀態有多個令牌，分別與申請連接服務器客戶端相對應的。

通過變遷T0將令牌傳給P1，若P1獲得令牌，協同用戶就會接收最新版本模型并在本地進行模型存儲和模型顯示，為協作開發提供方便。

通過變遷T1將令牌傳給P2，若P2獲得令牌，說明協同用戶正在對模型進行操作，即開發人員可以在模型編輯模塊進行相應的編輯操作，同時保存編輯后的模型。如果在當前客戶端修改的過程中，有其他人員提交了新版本的增量信息，那么開發人員會將自己的修改操作與當前最新版本的模型進行對比，從而獲得本地修改的增量信息。

通過變遷T2將令牌傳給P3，若P3獲得令牌，說明某個協同用戶正在提交版本增量信息。如果提交的版本與當前服務器的最新版本號不一致，則通過變遷T4返回客戶端重新提取有效的增量信息;如果一致就通過變遷T3將令牌傳給P4。若P4獲得令牌，也即將服務器接收提交的版本信息同時進行版本信息的存儲。

4 沖突模型分析及正確性驗證

當多個協同用戶同時向服務器提交本地建模的增量信息時，就要考慮到操作的并發性以及提交的增量信息是否存在沖突等問題。假設有A、B兩個協同用戶目前處于提交狀態，建立它的Petri網模型如圖5所示。圖5中的庫所集元素如表3所示，變遷集元素如表4所示。

圖6為上述Petri網的可達標志圖，其初始狀態Mo=[ 1， 0， 0， 0， 0， 0， 0， 0， 0 ]。根據可覆蓋性樹的構造方法， 可以生成這個Petri網模型的可覆蓋性樹，如圖6所示。

從可達標志圖中可以得到這個Petri網模型的特性[11]:

a)這個Petri網模型是有界的， 因為在其可覆蓋性樹中沒有出現ω。

b)這個Petri網模型是安全的， 因為只有“0”和“1”出現在可覆蓋性樹節點的標志中。

圖5中的所有轉移都出現在圖6的覆蓋性樹中， 這說明所有的轉移都是“活的”。同時也說明了在模型中所有的轉移都是必要的， 模型中不存在冗余。

c)這個Petri網模型中雖然存在著沖突， 但可有一定的辦法化解。例如，T4、T5和T6之間， T7和T8之間。T4、T5和T6之間的沖突是指兩個協同用戶A、B同時提交的增量版本號與當前服務器中的最新版本號是否都一致。如果一致， 則觸發T4進入判斷沖突狀態;如果A不一致則觸發T5發送版本不一致提示， 并返回到協同用戶A的操作狀態;如果B不一致則觸發T6發送版本不一致提示， 并返回到協同用戶B的操作狀態。T7和T8之間的沖突是指協同用戶A、B同時提交的增量信息之間是否有沖突。如果沒有， 則觸發T7進入接收狀態;否則觸發T8返回到協同用戶A、B的操作狀態，請求用戶重新提交。由此可見， 在協同建模系統的Petri網模型中，這種沖突可以作為一種引起Petri狀態變化的觸發條件，并可以通過協同用戶之間的協商進行化解。

從以上Petri網模型及其可覆蓋性樹的特點可以看出， 這是一個具有可達性、有界性、活性的網， 并且是不可逆的。根據Petri網的研究， 具有這些特性的Petri網是安全的、可行的。

5 結束語

本文從當前三維場景建模的需求出發，詳細分析和闡述了協同建模的系統框架和協同過程，采用工作流Petri網建立了協同建模系統的Petri網模型，根據Petri網的相關理論分析得知，該模型是安全的， 可以用來設計協同建模系統。同時也看到， 在該模型中反映出必須在系統中加以解決的并發問題。可見，采用工作流Petri網使得協同建模系統的仿真更加簡化、實用和易于理解，也降低了系統的復雜性。

參考文獻:

[1]楊承磊，孟祥旭，龔斌，等.支持大規模虛擬場景快速設計的分布式數據管理系統的研究[J].系統仿真學報，2001，13(增刊):206-209.

[2]史美林，向勇，楊光信，等.計算機支持的協同工作理論與應用[M].北京:電子工業出版社， 2000:2-22.

[3]楊煜俊.網絡化協同產品開發理論及其關鍵技術研究[D]. 湖北:華中科技大學， 2005.

[4]朱保國.油田注水生產過程仿真分布式協同建模系統研究[D].黑龍江:大慶石油學院， 2004.

[5]朱劍飛.網絡環境下三維模型的協同瀏覽、查詢和批注技術研究[D].西安:西北工業大學， 2003.

[6]方萃浩.網絡化幾何造型關鍵技術研究[D].浙江:浙江大學， 2006.

[7]吳哲輝. Petri網導論[M]. 北京:機械工業出版社， 2006:1-312.

[8]JENG M D， PENG M Y. Augmented reachability trees for 1-placeunbounded generalized Petri nets [J]. IEEE Trans on Systems， Man， and Cybernetics-Part A:Systems and Humans， 1999， 29(2): 173-182.

[9]AALST W， HEE K van.工作流管理:模型、方法和系統[M].王建民， 聞立杰，譯.北京:清華大學出版社，2004.

[10]LIU Yi， ZHANG Zi-gang. Overview of workflow models [J]. Computer Engineering and Design， 2007，28(2):448-451.

[11]ZHOU Fu-ming， WU Bin， GU Qing， et al. Modeling and correctness checking of Petri-Net-based workflow [J]. Computer Science， 2005， 32(2):121-124.