基于特征優先關系的沖突消解方法
2009-01-01 00:00:00丁博孫立鐫
計算機應用研究 2009年1期
（哈爾濱理工大學 計算機科學與技術學院， 哈爾濱 150080）
摘 要：提出了一種基于特征優先關系的沖突消解方法，該方法通過制定設計人員的靜態優先級和特征操作的動態優先級，可以有效地預防、檢測和消解沖突，維護了協同模型的一致性。同時，還采用了負載平衡技術，保證了協同建模的效率。
關鍵詞：同步協同設計；沖突消解；特征優先關系；負載平衡技術
中圖分類號：TP391 文獻標志碼：A
文章編號：10013695(2009)01036603
Conflict resolve method based on feature precedence relation
DING Bo，SUN Lijuan
(College of Computer Science Technology， Harbin University of Science Technology， Harbin 150080， China)
Abstract:This paper proposed a conflict resolve method based on feature precedence relation，which could prevent，detect and resolve conflict effectively， maintain consistency of the models by the way of making static priority of designers and dynamic priority of feature operation. Besides， this paper used load balancing technology to ensure the efficiency of collaborative design.
Key words:collaborative design；conflict resolve；feature precedence relation；load balancing technology
CSCW[1]的基本含義是在計算機技術支持的環境中，一個群體協作地完成一項共同的任務。由于CSCW是一種基于網絡的分布式系統，在協同設計過程中就必然存在并發沖突[2]，沖突破壞了模型數據的完整性和一致性，使系統無法正常運行。由于CAD模型具有復雜度和耦合度高等特點，給沖突控制帶來了難度。沖突控制[3]的目的是對并發操作進行有序控制，正確協調系統中出現的并發操作。
本文針對本實驗室實現的混合式同步協同平臺提出了一種基于特征優先關系的沖突消解方法。該方法進一步強調管理在協同建模時的重要性，在協同設計開始前，先將所要完成的任務劃分成若干個子任務，確定每個設計人員應完成的子任務，根據每個設計人員擔任的任務不同為其分配不同的角色；并通過角色機制為其分配相應的靜態優先級，角色機制是并發控制的基礎。此混合式系統支持設計人員傳輸特征、零件或裝配體，并采用特征依賴圖[4]記錄模型構造的全過程，通過細胞元[5]語義特征造型技術[6]中特征間的依賴關系確定了特征動態優先關系，使并發沖突得到有效的控制。
1 相關知識介紹
11 并發沖突的種類
1）因果沖突 是指系統在沒有執行因操作前，先被要求執行果操作。此沖突有可能是由網絡延時造成的。
2）意圖沖突 是指當操作在一個站點生成后被傳送給其他站點進行同步執行，但在這個操作到達某個站點執行之前這個站點的對象模型已經被本地操作或其他遠程并發操作修改，因此當這個操作執行時它所基于的模型上下文環境已經發生改變。這樣操作執行的結果可能與操作在本地站點的執行結果大相徑庭，從而不滿足設計者的原有意圖。
3）分歧沖突 是指不同設計者對模型的同一特征的同一屬性共同關注而產生的。這些操作無論誰先執行誰后執行對象模型都能且僅能體現其中一個操作的意圖，其他操作的執行結果無法表現出來。
12 并發控制方法
1）并發沖突防止 是通過某種規則對用戶操作進行一定限制，使他們不會發生并發沖突。
2）并發沖突檢測與解決 是通過一定的操作沖突判別規則對系統中的并發操作進行沖突判斷，然后再依據一定規則來對發生沖突的操作進行協調處理。
本文提出的基于特征優先關系的沖突消解方法，充分分析了沖突產生的原因，結合了以上兩種基本并發控制方法，可以有效地預防、檢測和消解沖突。
2 系統框架
本實驗室研發的混合式平臺由一個主站點和若干從站點組成。主站點不從事任何構建模型的工作，它只用來接收和發送從站點的建模指令，驗證建模指令的合法性，并對各建模指令進行合理的調度，維護整個建模過程；從站點的任務是構建模型。主站點由四個模塊組成，即消息控制模塊、權限模塊、調度模塊和負載平衡模塊，如圖1所示。
1）消息控制模塊 用來驗證并接收從站點傳送來的建模數據。驗證一個操作是否可執行，通過檢查操作對象特征的直接依賴特征在站點中是否均已存在來判斷。若驗證成功，則說明此操作對象特征的直接依賴特征已存在，主站點便發送驗證成功消息給此從站點；若失敗，主站點則發送驗證失敗的消息給此從站點，并說明驗證失敗的原因。消息控制模塊監控任意操作執行情況的全過程，當某一從站點傳送的建模數據經驗證成功并被其他各從站點接收時，消息控制模塊將發送傳送成功的消息給此從站點。若發生傳送超時等異常狀況時，消息控制模塊將發送消息給此從站點，讓其重新傳送相關建模數據。
2）權限模塊 采用角色機制，其作用是獲取用戶的靜態優先級數。系統根據設計人員所擔任的不同角色事先劃定相應的靜態優先級。角色作為中間橋梁將設計人員與權限聯系起來，一個角色與權限關聯可以看做是該角色擁有的一組權限的集合，與設計人員關聯又可以看做是若干具有相同身份的設計人員的集合。一個登錄于某一系統的設計人員，可以通過他所具有角色的權限來確定其可訪問的系統資源和對系統資源可以進行的操作。角色機制使若干設計人員可以共同承擔一個角色，當其中一名設計人員因某種原因不能繼續工作時，也不會影響工作進程。由于本文已事先確定不同角色的設計人員應完成的子任務，要求設計人員不能越權對模型進行操作，在修改某一特征時，只有該特征的創建者才能對其進行修改操作，拒絕其他設計人員對其的修改請求，有效避免了分歧沖突的產生。
3）調度模塊 為每一個子站點創建一個子中性建模隊列，每個子站點的建模操作按時間順序依次放入到各自的子中性建模隊列中；然后根據特征優先關系將待執行的操作放入中性建模隊列中。
4）負載平衡模塊 采用負載平衡技術對調度模塊中的各子中性建模隊列進行實時監控，根據各子中性建模隊列中的待處理操作數量的多少進行任務調度。當設計人員間不存在并發操作時，便通過負載平衡技術先執行待處理操作數量多的子中性建模隊列中的操作，此技術使每個設計人員的建模操作能夠盡量快地被執行，不會因長期等待而影響他們的設計積極性。由于本混合式系統支持設計人員傳輸特征、零件和裝配體，就可能出現設計人員在某一時間段內，只是設計模型，而沒有傳輸設計完成的模型，使主站點處于空閑狀態。這時，通過負載平衡技術，系統將從靜態優先級最高的站點開始，向各站點發送消息，讓它們傳輸建模數據。
3 特征間的優先關系
31 特征依賴集
特征依賴圖是有向無環圖，圖中的一個節點對應模型中的一個特征，存在有向邊連接的兩個節點表示節點對應的兩個特征存在直接特征依賴關系，有向邊的始點是父特征，終點(即箭頭所指方向)是子特征，子特征因父特征的存在而存在。若兩個特征間不存在依賴關系，則稱這兩個特征互為獨立特征。圖2為一特征依賴圖實例。
對于模型中的所有特征構成的集合S，假設特征集S中有任意三個特征F1、F2、F3，則可知它們滿足下面的三個性質：
a)傳遞性，如果F1優先F2，F2優先F3，則F1優先F3。
b）單向性，如果F1優先F2，則F2不優先F1。
c)自反性，F1不優先于自己。
如果特征F1的構造直接引用了特征F2，或與特征F1有直接的約束關系，則稱F2是F1的直接依賴特征。同樣，如果特征F1是通過特征依賴的傳遞性而對特征F2產生的依賴關系，則稱F2是F1的間接依賴特征。
特征依賴關系描述了特征間的工程語義關系，體現了一種特征間的相互影響特性，即特征的變動只影響依賴于它的特征，而與其互為獨立特征的特征是不受直接影響的。當在原有模型中添加、修改、刪除特征時只會影響到它所依賴的父特征的拓撲結構，從而可能影響到依賴于該父特征的所有特征。因此，對于任意特征F1的依賴特征可能有多個，包括直接依賴特征和間接依賴特征，這些特征的集合構成了特征依賴集dependSet(F1)。
在進行同步協同建模時，如果要對特征F1進行修改，可以通過遍歷特征依賴圖，確定特征操作所影響的特征依賴集dependSet(F1)。由于僅需對dependSet(F1)中的特征進行相應的修改，而不用重構整個原有模型，極大提高了建模效率。
32 動態優先級的確定
基于細胞元表示的語義特征模型構建造型時，其特征間的優先次序是動態改變的，可以根據特定階段特征之間的依賴關系來確定優先次序，因此，每次特征操作的優先次序也應隨著特征間的優先次序的改變而動態改變，每次進行特征操作時均要對特征間的優先性進行分析。本文就依據語義特征模型的這一特性來定義協同建模過程中特征操作的動態優先級。
根據特征依賴圖及特征間的優先關系，特征操作時的動態優先級應遵守以下三條原則：
a）特征依賴圖中的每一條邊表明了模型中兩個特征之間的優先關系：若F2依賴于F1，則F1的動態優先性高于F2。
b）屬性不同的兩個特征（一個為正特征，一個為負特征），原先互不相交（互為獨立特征）。在經過修改后，兩特征相交，若重疊是F2造成的，那么F1動態優先級高于F2。
c）屬性相同的兩個特征F1和F2（同為正特征或同為負特征）。經過修改特征F1后，兩特征相交，生成一個新的細胞元。則新生成的細胞元在特征模型中的動態優先級調整為未經修改時的特征F2的優先級。
4 沖突消解方法
定義1 操作M。M=(Mid，Fid，Uid，sta_prio，FS，Type， dyn_prio，dependSet(Fid)，Attribute，Ts，Te)。其中：Mid是設計人員Uid在系統中作用于特征Fid之上任一操作的惟一標志符；sta_prio是設計人員Uid的靜態優先級；FS是該操作的類型；Type是該操作的子類型；dyn_prio是該操作的動態優先級；dependSet(Fid)是該操作對象特征的特征依賴集；Attribute是該操作涉及的所有屬性列表；Ts是操作開始時刻；Te是操作結束時刻。
定義2 并發沖突。對于協同設計中的任意兩個操作Mi和Mj，它們的操作對象特征分別是Fi和Fj，如果這兩個操作同時滿足如下條件:a)Mi×Uid ≠Mj×Uid；b)[Mi×Ts，Mi×Te]∩[Mj×Ts，Mj×Te]≠；c)dependSet(Fi)∩dependSet(Fj)≠。這兩個操作存在并發沖突。
本文通過自定義的靜態優先級和動態優先級，提出了基于特征動態優先關系的沖突消解方法。其步驟如下：
a)對于任意兩個并發操作Mi和Mj，首先比較這兩個并發操作的操作對象是否為同一特征，若為同一特征，則必有一個操作是越權操作，應放棄該操作。其次比較兩者的特征依賴集，如果dependSet(Fi)∩dependSet(Fj)≠，則存在沖突，轉c)；否則轉b)。
b)比較并發操作Mi和Mj的靜態優先級，若兩者的靜態優先級不同，且Mi×sta_prio＞Mj×sta_prio，則按靜態優先級將操作Mi和Mj依次放到中性建模隊列中并等待執行；若兩者的靜態優先級相同，轉d)。
c)比較并發操作Mi和Mj的靜態優先級，若Mi×sta_prio＞Mj×sta_prio，則執行操作Mi，放棄操作Mj；若兩者的靜態優先級相同，轉e)。
d)比較兩者的動態優先級，如果Mi×dyn_prio＞Mj×dyn_prio，將按動態優先級將Mi和Mj操作依次放到中性建模隊列中并執行。
e)比較兩者的動態優先級，如果Mi×dyn_prio＞Mj×dyn_prio，則將動態優先級高的操作Mi放到中性建模隊列中并等待執行，放棄操作Mj。
由于本系統支持設計人員一次性傳輸特征、零件或裝配體，對零件和裝配體只需提取其父特征，按以上步驟執行便可。
5 系統實現
本文以一臺主服務器和三個協同建模站點為例，驗證了基于特征優先關系沖突消解方法的有效性（圖3）。其中站點1與2的靜態優先級相同，站點1大于3的靜態優先級。
時間流水線A時刻是初始模型，各站點的模型均是一致的。B時刻站點1將圓柱體高度降低，站點3將圓柱體高度增加，雖然站點1高于站點3的靜態優先級，但該圓柱體是由站點3創建的，系統判定站點1發生越權操作，放棄執行，只執行站點3的操作。C時刻站點1將盲孔的半徑增大，而站點2將模型的一條棱邊倒圓，經驗證這兩個操作的特征依賴集并不相交，即不存在并發沖突。由于兩者的靜態優先級相同，比較其動態優先級，站點2大于站點1動態優先級，將這兩個操作依次放入中性建模隊列中，服務器先執行站點2的操作。
6 結束語
并發沖突的預防、檢測和消解在同步協同設計過程中是至關重要的。本文采用基于特征優先關系的沖突消解方法，通過特征依賴圖記錄模型構造的全過程，制定設計人員的靜態優先級和特征操作的動態優先級，有效維護了協同模型的視圖一致性，并以高層語義造型命令為傳輸載體，通過負載平衡技術，充分利用了網絡資源，減少了網絡的負荷，支持了協同設計的有效進行。
參考文獻：
［1］
MORTEN O F，KRISTINA L，MARTIN B，et al.Physical and virtual tools:activity theory applied to the design of groupware[J].Computer Supported Cooperative Work，2002， 11（12）：153180.
［2］IONESCU M，MARSIC I.Treebased concurrency control in distributed groupware[C]//Proc of ACM Conference on Computer Supported Cooperative Work.Norwell，MA:Kluwer Academic Publishers，2003:329350.
［3］余春燕，侯宏侖，吳明暉.協同設計中以實體為中心的并發操作控制機制[J].計算機輔助設計與圖形學學報，2004，16(9)：12891295.
［4］BIDARRA R，BRONSVOORT W F.Semantic feature modeling[J].Computer Aided Design，2000，32(3)：201225.
［5］BIDRRA R，NEELS W J，BRONSVOORT W F.Boundary evaluation for a cellular model[C]//Proc of Computers and Information in Engineering Conference.Chicago:[s.n.]，2003：255265.
［6］LIA W D，ONGB S K，JERRY Y H，et al.Featurebased design in a distributed and collaborative environment[J].Computer Aided Design，2004，36(9)：775793.
