協同工作中沖突消解機制的研究
2012-04-29 00:00:00屈正庚
計算技術與自動化 2012年3期
摘要：協同工作就是利用網絡技術眾多設計者共同合作完成任務，及時更新信息，保證網絡信息的一致性與快速響應性。但是在協同工作過程設計成員自身條件差異，不可避免在協同設計中會產生沖突，所以準確及時對沖突檢測與消解是協同工作的關鍵。因此提出一種新的集成化沖突消解模型，給出模型算法，利用模式匹配技術在這個模型中進行沖突檢測與消解，采用克莫普匹配法進行沖突消解。通過實驗證明，集成化模型和模式匹配技術很有效，對沖突檢測準確，對沖突消解效率高，尤其處理大批量沖突時速度很快，效果非常顯著，算法復雜度也很低。
關鍵詞：協同工作；沖突檢測與消解；集成化模型；模式匹配技術
中圖分類號：TP391.9 文獻標識碼：A
Collaborative Work in Conflict Resolution Mechanism
QU Zhenggeng
（The department of computer science， Shangluo University， Shangluo726000，China）
Abstract：Collaborative work is the use of network technology， many designers work together to complete the task， and update the information in a timely manner to ensure consistency with the rapid response of the network information. But the difference in the process of working together members of its own conditions， unavoidable in collaborative design conflict， so accurate and timely conflict detection and digestion is the key to work together. Therefore， a new integrated conflict resolution model， the model algorithm， pattern matching In this model， collision detection and digestion， with KMP matching method for conflict resolution. The experiments show that the integrated model and pattern matching techniques is very effective， accurate conflict detection， conflict resolution， high efficiency， especially when dealing with large quantities of conflict quickly， the effect is very significant， the complexity of the algorithm is very low.
Key words：collaborative work； conflict detection and resolution；integrated model； pattern matching techniques
1引言
協同工作是指利用計算機網絡技術，多個設計人員圍繞同一個設計項目展開自己的設計任務，并行交互的工作，最終得到符合設計條件的結果。在協同工作中，設計人員的工作思路、考慮問題角度、參考標準、知識領域的不同，肯定會在設計過程中產生沖突。沖突對協同工作過程既起到消極作用，又起到積極作用，一方面沖突的存在必然會導致設計的不和諧，數據的不一致；另一方面沖突是一個優秀產品設計的開端，沖突不斷產生與消解，使一個最優的設計誕生了，提高了產品的整個性能指標。
目前國內外對沖突消解做了深入研究，常見的方法有基于規則、基于實例、基于約束以及基于協商的沖突消解技術[1，2]。但是這些消解技術只是從單一的角度去考慮問題，在實際應用中具有一定的片面性和局限性。協同工作是一個復雜的、多樣的、動態的變化過程，協同工作系統中發生的沖突不可能依賴于某一種沖突消解方案可以化解掉的，需要將多種策略科學的、合理的結合起來才能達到理想的狀態。因此提出了集成化的沖突消解模型，并利用模式匹配算法進行驗證，得到了很好的效果。
2沖突消解的概述
2.1沖突概念
協同沖突是指多個相互有聯系的對象之間存在一種不一致、不穩定、不和諧、不兼容的狀態。防止和解決沖突是沖突管理追求的目標。一般來說，進行沖突管理會涉及到三個方面關鍵技術：沖突避免技術、沖突檢測技術和沖突消解技術，它們相輔相成，彼此影響，如1圖所示。
圖1沖突管理
沖突避免就是在沖突發生之前弄清楚沖突的根源，然后通過一定的技巧和措施避免潛在沖突的發生。沖突檢測主要利用領域相關法和領域無關法。沖突消解主要對無法避免沖突采用合理的辦法去有效地化解。
2.2沖突消解現狀
沖突消解在協同工作系統中具有特殊的位置，選擇最優的措施來解決已發生的沖突。引起沖突發生的原因復雜多樣，形成沖突類型也很繁瑣，造成沖突消解很艱難。目前國內外對沖突消解進行了大量研究[3，4]，主要的方法有基于規則、基于實例、基于約束以及基于協商的沖突消解技術。對于產品開發過程中的個人矛盾可以利用基于規則、基于實例、基于約束的方式解決，合作團隊、知識領域、部門專家之間的矛盾一般協商技術。但是這些技術只從單一角度考慮問題，只能解決一些簡單問題，對于實際存在的復雜問題無法實現，而且協同工作本身是一個動態變化的過程，需要一種全面的技術在實際工作中使用。
3集成化沖突消解的模型
3.1消解模型
在建立協同工作沖突消解模型過程中，需要考慮很多方面的因素：第一，設計小組之間信息的傳遞速度和反饋意見[5，6]；第二，消解沖突使用的方法應該如何實施；第三，各種沖突消解方法在解決問題是如何有效的集成起來；第四，消解過程實時調度問題。
計算技術與自動化2012年9月
第31卷第3期屈正庚：協同工作中沖突消解機制的研究
認真分析與考慮上述要求后提出沖突消解模型如2圖所示。
圖2沖突消解模型
沖突消解過程大致分為以下幾個步驟：第一步，通過沖突檢測工具對設計過程進行沖突檢測，對檢測到的沖突分類匯總，按照一定的規律排序。第二步，根據沖突的關聯性，判斷沖突是否有連鎖效應，如果有則采用約束消解技術，否則采用事例和規則消解技術。第三步，通過上述三種方法都無法解決的沖突則采用協商消解技術。在協商過程中，大家提出各自的意見，共同商量、溝通、探討，確定出一致性的決策。如果失敗則進行仲裁。第四步，仲裁人綜合考慮各方面的因素后，提出最為恰當的方案，供大家去解決沖突[7，8]。最終還有人不接受則只有轉換沖突消解策略，將沖突轉移到協同設計的上一層，重新對協同工作進行設計與規劃。
3.2消解算法
利用特定工具檢測出來的沖突進行消解的算法描述如下：
沖突進行分類與排序
{ if沖突有關聯性then
{約束技術
if解決成功then
沖突化解
}
else 實例或者規則技術
if解決成功then
沖突化解
else
{協商技術
if 協商成功 then
沖突化解
else
{仲裁
if 仲裁成功 then
沖突化解
else
沖突層次轉換
}
}
}
4模式匹配的沖突消解技術
4.1基本思想
根據協同工作中沖突的類型與含意，建立一個實例庫和規則集，設計人員進行協同工作。如果不可避免的發生了沖突，判斷出沖突類別，根據類別在實例庫或規則集中進行匹配，匹配成功，則沖突就可以解決，失敗則匹配最相似的沖突，對最相似的沖突進行修改，修改后就可以消解沖突；如果仍然不能解決則轉換思維，對沖突進行分解，反復匹配，直到解決為止[9]。
假設實例庫和規則集為S=”ababcabcacb”，產生的沖突集：C=”abcac”。C在S中進行匹配，匹配過程如3圖所示。
圖3沖突匹配過程
4.2沖突消解過程
采用模式匹配消解沖突時，需要考慮到四個方面的因素：第一、建立的實例庫和規則集必須詳細，盡可能的多；第二、對發生的沖突進行匹配時，要利用快速有效地方法去分類；第三，如果匹配幾次仍無法解決，及時換轉思維，調換策略，防止死“循環”。第四，設計人員要有豐富的工作經驗。
模式匹配沖突消解基本結構如4圖所示，主要有沖突檢測器、沖突分類器、匹配器、消解器組成[10]。
模式匹配沖突消解過程：首先在沖突檢測器中檢測到的沖突信息傳遞給分類器，分類器根據沖突的破壞性、根源、大小、類別詳細的分類；然后再匹配器中進匹配，匹配成功則消解，不成功改變策略，對沖突分解后再次匹配；最后在消解其中對沖突評價和修改，進一步更新匹配器[11，12]。
圖4模式匹配沖突消解結構
4.3沖突消解的算法
沖突信息的具體描述：
Des_ConflictDescribe
{ public：
int Des_ConflictHarm；//沖突破壞性
int Des_ConflictSour； //沖突根源
int Des_ConflictClass； //沖突類別
int Des_ConflictSize； //沖突大小
voidDes_Collect //實例庫和規則集的總和
voidDes_ConflictSolve //對應的沖突消解成功
}
算法描述如下：
for（i=1；i { if（Des_ConflictSour Des_ConflictClass） == Des_Collect thenDes_ConflictSolve else分解沖突模塊 { if（Des_ConflictSour Des_ConflictClass） == Des_Collect thenDes_ConflictSolve elsestop } 對沖突評價 修改Des_Collect } 字符串匹配算法中，實例庫和規則集用數組S，沖突集用數組C，next數組表示next函數的相關值。從數組S中的K位置尋找和沖突集C相匹配的解決方案，具體如下： inti，j i=K， j=1； while （ i<=S[0] j<=C[0] ）//沒有找見結束 if（ j==0||S[i]==C[j] ） { i++； j++； } elsej=next[j]； //右滑 if（j>C[0]） return i—C[0]； //匹配成功，消解沖突 else return 0； //匹配失敗 } inti，j // 沖突集C的next值并入next數組中 i=1， j=0； next[1]=0； while （ i { if（ j==0||C[i]==C[j]） { i++； j++； next[i]=i； } else j=next[j]； } 4.4算法效果分析 發生的沖突與實例庫和規則集匹配時，可以采用兩種模式匹配算法：基本匹配法（BF）和克莫普匹配法（KMP）[13，14]。為了測試BF算法和KMP算法性能，選取2.5Mbit的英文文本，在其中查找多個模式串，找出所有出現的位置。在實驗中，選取3組不同長度的模式串，每組的模式串數目從1到25以4為單位遞增。測試環境為Pentium3.0GHz、內存1GB，操作系統Windows XP，編譯環境VC++6.0。實驗結果如表3所示。 表3查找時間（單位：ms） 模式串長度 算法 模式串數目 1 5 9 13 17 21 25 2 BF算法 643 657 688 721 745 760 795 KMP算法 225 238 255 279 296 327 347 10 BF算法 655 678 693 733 767 793 833 KMP算法 220 228 245 268 279 290 310 18 BF算法 668 689 703 747 779 801 855 KMP算法 208 212 227 243 253 265 270 5結語 協同工作最主要的任務就是沖突檢測與消解，并且保證協同數據一致性與及時響應性。通過實際應用，上述的研究方案有很好的效果，提高了工作效率[15，16]。算法也是可行的，復雜度比較低，運行速度快。但是在沖突消解過程中協同數據傳輸有點遲緩，需要進一步研究。 參考文獻 [1]孟秀麗.協同設計支持環境及沖突消解理論與方法[M].南京：東南大學出版社，2010. [2]孫博，張榮國，王艷艷，等.協同設計中的模糊沖突消解方法[J].計算機工程與應用，2009，45（3）：84—86. [3]李海波，余金山，陳維斌.一種本體協同沖突的檢測方法[J].華僑大學學報：自然科學版，2011，32（6）：66—69. [4]楊育，王小磊，曾強.協同產品創新設計優化中的多主體沖突協調[J]. 計算機集成制造系統，2011，17（1）：255—258. [5]蔣國瑞，段曉敏，張瀚林.基于沖突檢測的供應鏈協同計劃[J]，計算機工程，2010，6：86—89. [6]孟秀麗，易紅，倪中華.基于模糊評價的協同設計沖突仲裁技術研究[J].計算機集成制造系統，2005，3（11）：399—405. [7]汪大勇，金煒東.協同設計中的并行沖突檢測算法[J].計算機應用，2007，3（27）：650—653. [8]曹將棟.采用模糊估算的產品協同開發中成本沖突消解方法的研究[J].現代制造工程，2011，（1）：18—21. [9]錢屹，侯義斌.一種快速的字符串匹配算法[J].小型微型計算機系統，2004， 25（3）：410—413. [10]王麗萍，江波，邱飛岳.基于多目標進化算法的協同設計沖突消解方法[J].計算機集成制造系統，2010，16（9）：174—176. [11]張莉.縫制設備協同開發過程中沖突消解方法的研究[J].工程設計學報，2010，17（2）：188—190. [12]趙陽，劉弘.協同設計中基于規則推理的沖突消解研究[J].計算機應用研究，2006，10（1）：54—57. [13]PIERRE A Y.A CSP approach for the network of product life cycle constraints consistency in a collaborative design context[J].Engineering Applications of Artificial Intelligence，2009（06）：123—126. [14]SIDHARTHA P，NARAYANA P P.Comparison of particle swarm optimization and genetic algorithm for FACTS—based controller design[J]. Applied Soft Computing Journal， 2008（04）：66—69. [15]SLIMANI K，FERREIRA D S C，MEDINI L.Conflict mitigation in collaborative design[J]. International Journal of Production Research， 2006（09）：106—109. [16]CHEN Ming，LIU Jinfei，KONG Qinghua.Application of ontological thought in collaborative product R D oriented to automobile lifecycle[M]. Washington，DC：IEEE，2010：326—319.
