王發(fā)麟， 廖文和， 郭 宇， 鞠傳海

（南京航空航天大學(xué)機(jī)電學(xué)院，江蘇 南京 210016）

復(fù)雜機(jī)電產(chǎn)品線(xiàn)纜信息本體表達(dá)與存儲(chǔ)分析

王發(fā)麟， 廖文和， 郭 宇， 鞠傳海

（南京航空航天大學(xué)機(jī)電學(xué)院，江蘇 南京 210016）

針對(duì)復(fù)雜機(jī)電產(chǎn)品中線(xiàn)纜工程語(yǔ)義信息統(tǒng)一表達(dá)難、線(xiàn)纜復(fù)雜拓?fù)浣Y(jié)構(gòu)難以表示和存儲(chǔ)的問(wèn)題，提出基于本體和無(wú)向圖的復(fù)雜線(xiàn)纜信息表達(dá)與存儲(chǔ)分析方法。首先建立了基于布線(xiàn)設(shè)計(jì)、裝配工藝規(guī)劃和仿真分析3個(gè)維度的線(xiàn)纜信息集成模型；然后利用本體技術(shù)對(duì)模型信息進(jìn)行了本體建模，增強(qiáng)了線(xiàn)纜語(yǔ)義信息的表達(dá)；最后利用一種水平分割算法將線(xiàn)纜零件劃分成一個(gè)無(wú)向圖，在此基礎(chǔ)上建立鄰接表，實(shí)現(xiàn)了線(xiàn)纜零件無(wú)向圖在計(jì)算機(jī)中的存儲(chǔ)和表達(dá)。通過(guò)將該方法應(yīng)用到某線(xiàn)纜零件的實(shí)際分析中，驗(yàn)證了文中方法的可行性。

線(xiàn)纜；本體；無(wú)向圖；信息集成模型；復(fù)雜機(jī)電產(chǎn)品

線(xiàn)纜作為傳輸能量和信號(hào)的介質(zhì)，被大量應(yīng)用于航空、航天、汽車(chē)、船舶等各類(lèi)復(fù)雜機(jī)電產(chǎn)品中，是連接電子設(shè)備與各分機(jī)模塊的“紐帶”，線(xiàn)纜的優(yōu)化布局和裝配質(zhì)量已成為衡量產(chǎn)品整機(jī)性能和可靠性的一個(gè)重要指標(biāo)[1-2]。在工程應(yīng)用中，線(xiàn)纜具有復(fù)雜的拓?fù)浣Y(jié)構(gòu)，涵蓋了大量的幾何拓?fù)湫畔?、工程語(yǔ)義信息和分散的布線(xiàn)信息。工程語(yǔ)義信息的不一致性、線(xiàn)纜拓?fù)浣Y(jié)構(gòu)的復(fù)雜性以及線(xiàn)纜在計(jì)算機(jī)中的難以存儲(chǔ)表示，是制約線(xiàn)纜虛擬布線(xiàn)設(shè)計(jì)與裝配過(guò)程仿真的主要因素。對(duì)上述信息建立一個(gè)統(tǒng)一的信息集成模型，并對(duì)模型信息采用適當(dāng)?shù)姆椒ㄟM(jìn)行工程語(yǔ)義表達(dá)，解決線(xiàn)纜拓?fù)浣Y(jié)構(gòu)的表示和存儲(chǔ)問(wèn)題，是實(shí)現(xiàn)線(xiàn)纜三維布線(xiàn)設(shè)計(jì)、裝配工藝規(guī)劃和仿真分析的基礎(chǔ)，也是建立復(fù)雜機(jī)電產(chǎn)品數(shù)字化樣機(jī)的信息基礎(chǔ)。

為此，國(guó)內(nèi)外一些學(xué)者圍繞線(xiàn)纜拓?fù)浣Y(jié)構(gòu)的表示及信息模型的建立作了相關(guān)的研究。如 Conru[3]將線(xiàn)纜的布局問(wèn)題分解為線(xiàn)纜拓?fù)浣Y(jié)構(gòu)的生成和線(xiàn)纜敷設(shè)兩部分，并提出了以無(wú)向圖的形式來(lái)表達(dá)線(xiàn)纜的拓?fù)浣Y(jié)構(gòu)，但因受限于當(dāng)時(shí)的技術(shù)條件而并未實(shí)現(xiàn)；Hergenr?ther和Dahne[4]建立了用于虛擬環(huán)境中交互式布線(xiàn)設(shè)計(jì)中的線(xiàn)纜定長(zhǎng)模型，同時(shí)提出將線(xiàn)纜束分為簡(jiǎn)單的線(xiàn)纜段以表達(dá)其整體結(jié)構(gòu)，但是該文獻(xiàn)沒(méi)有對(duì)線(xiàn)纜信息的語(yǔ)義進(jìn)行表達(dá)；魏發(fā)遠(yuǎn)等[5]建立了一個(gè)面向虛擬布線(xiàn)的電纜信息模型，該模型由電氣模型、拓?fù)淠Ｐ秃蛶缀文Ｐ偷?個(gè)部分組成，但文中沒(méi)有對(duì)線(xiàn)纜拓?fù)浣Y(jié)構(gòu)的建立及存儲(chǔ)過(guò)程進(jìn)行論述；萬(wàn)畢樂(lè)等[6]對(duì)導(dǎo)線(xiàn)、線(xiàn)束和導(dǎo)線(xiàn)單元等元素進(jìn)行了定義，并建立了基于離散控制點(diǎn)的線(xiàn)纜模型，實(shí)現(xiàn)了對(duì)線(xiàn)纜主干、分支結(jié)構(gòu)和導(dǎo)線(xiàn)信息的表達(dá)，但該模型對(duì)線(xiàn)纜結(jié)構(gòu)的表達(dá)因?qū)Ь€(xiàn)的定義不同而不同，且在通用性、信息可拓展性等方面也受到較多的限制；王金芳等[7]根據(jù)線(xiàn)纜在復(fù)雜機(jī)電產(chǎn)品中存在方式和面向?qū)ο蟮慕Ｋ枷敕謩e建立了基線(xiàn)纜信息模型和線(xiàn)纜分支信息模型，體現(xiàn)了線(xiàn)纜信息的層次性，但也只限于信息的層次分類(lèi)上，對(duì)信息語(yǔ)義并未處理；尚煒等[8]提出了一種以拓?fù)浣Y(jié)構(gòu)信息為骨架的線(xiàn)纜數(shù)字化模型，該模型雖然通過(guò)線(xiàn)纜基本元素間的包含關(guān)系和連接關(guān)系無(wú)向圖建立了線(xiàn)纜的拓?fù)浣Y(jié)構(gòu)信息，但對(duì)于線(xiàn)纜拓?fù)浣Y(jié)構(gòu)圖的建立過(guò)程并沒(méi)有進(jìn)行詳細(xì)闡述；劉佳順等[9]在分析線(xiàn)纜設(shè)計(jì)與制造流程的基礎(chǔ)上，提出了一種虛擬環(huán)境下復(fù)雜線(xiàn)纜的集成信息模型，對(duì)不同類(lèi)型的線(xiàn)纜信息進(jìn)行了梳理，而對(duì)信息語(yǔ)義存在的沖突性和不一致性沒(méi)有進(jìn)行分析。

上述研究成果分別從線(xiàn)纜建模的不同方面進(jìn)行了研究，但在線(xiàn)纜工程語(yǔ)義信息的不一致性和線(xiàn)纜拓?fù)浣Y(jié)構(gòu)表示及存儲(chǔ)的解決方面還有待進(jìn)一步研究。本文在前人研究的基礎(chǔ)上提出基于本體和無(wú)向圖的復(fù)雜線(xiàn)纜信息表達(dá)與存儲(chǔ)分析方法。該方法首先從布線(xiàn)設(shè)計(jì)、裝配工藝規(guī)劃和仿真分析 3個(gè)維度建立線(xiàn)纜信息集成模型(cable harness information integrated model, ChIIM)；為增加線(xiàn)纜在布局設(shè)計(jì)和裝配過(guò)程仿真及分析中的語(yǔ)義信息，利用本體技術(shù)對(duì)線(xiàn)纜信息進(jìn)行本體建模；最后利用一種水平分割算法將線(xiàn)纜零件劃分為一個(gè)無(wú)向圖，通過(guò)建立無(wú)向圖的鄰接表來(lái)實(shí)現(xiàn)線(xiàn)纜零件無(wú)向圖在計(jì)算機(jī)中的存儲(chǔ)和表達(dá)。該方法能較好地解決工程實(shí)際中線(xiàn)纜語(yǔ)義信息統(tǒng)一表達(dá)難和線(xiàn)纜的存儲(chǔ)問(wèn)題，從而滿(mǎn)足在布線(xiàn)設(shè)計(jì)、工藝規(guī)劃和仿真分析中對(duì)線(xiàn)纜信息有效檢索的要求。

1 線(xiàn)纜信息集成模型

在復(fù)雜機(jī)電產(chǎn)品設(shè)計(jì)中，線(xiàn)纜因其具有柔性特性而包含大量的信息，線(xiàn)纜信息的完整性和良好的語(yǔ)義表達(dá)是開(kāi)展基于產(chǎn)品數(shù)字樣機(jī)的線(xiàn)纜虛擬布線(xiàn)設(shè)計(jì)、線(xiàn)纜裝配工藝規(guī)劃和線(xiàn)纜裝配過(guò)程仿真及分析的重要前提條件。本文遵從“產(chǎn)品設(shè)計(jì)→工藝規(guī)劃→產(chǎn)品加工”的實(shí)際產(chǎn)品研制流程，從布線(xiàn)設(shè)計(jì)、裝配工藝規(guī)劃和仿真分析3個(gè)坐標(biāo)維度建立了ChIIM，如圖1所示。

ChIIM主要描述了線(xiàn)纜各種屬性的相關(guān)信息，如線(xiàn)纜幾何信息、線(xiàn)纜拓?fù)湫畔?、線(xiàn)纜物理屬性信息、電氣功能信息、線(xiàn)纜材料信息、輔助材料信息等，每一類(lèi)信息又包含更多表征線(xiàn)纜實(shí)際工作狀態(tài)的信息內(nèi)容。在含有柔性線(xiàn)纜的復(fù)雜機(jī)電產(chǎn)品系統(tǒng)的裝配仿真過(guò)程中，布線(xiàn)設(shè)計(jì)決定了裝配工藝，裝配工藝是進(jìn)行裝配過(guò)程模擬的依據(jù)，而ChIIM的建立則是上述工作開(kāi)展的基礎(chǔ)和前提條件，是每一階段所需的數(shù)據(jù)來(lái)源。

為保證極其復(fù)雜的產(chǎn)品設(shè)計(jì)在最短的設(shè)計(jì)周期內(nèi)盡量達(dá)到性能最優(yōu)，應(yīng)盡可能地在產(chǎn)品的系統(tǒng)設(shè)計(jì)階段即引入仿真分析，以幫助設(shè)計(jì)人員及早發(fā)現(xiàn)問(wèn)題。相較于傳統(tǒng)的將與線(xiàn)纜相關(guān)的信息進(jìn)行羅列而生成的模型，基于布線(xiàn)設(shè)計(jì)、工藝規(guī)劃和仿真分析3個(gè)維度而建立的ChIIM不僅將線(xiàn)纜的相關(guān)信息進(jìn)行了集成表達(dá)，實(shí)現(xiàn)在布線(xiàn)設(shè)計(jì)-工藝規(guī)劃、工藝規(guī)劃-仿真分析、布線(xiàn)設(shè)計(jì)-仿真分析這3個(gè)層面進(jìn)行信息的多次、循環(huán)調(diào)用，而且更能體現(xiàn)出3個(gè)不同研制階段（布線(xiàn)設(shè)計(jì)、工藝規(guī)劃和仿真分析）的內(nèi)在關(guān)聯(lián)性。

需要指出的是，在復(fù)雜機(jī)電產(chǎn)品的設(shè)計(jì)過(guò)程中，除了線(xiàn)纜信息作為數(shù)據(jù)來(lái)源外，剛性組件裝配信息和電氣組件信息也是必不可少的數(shù)據(jù)來(lái)源。因此，在上述ChIIM中對(duì)這兩類(lèi)信息進(jìn)行了擴(kuò)展，如電氣組件信息包括組件的CAD模型、組件統(tǒng)一ID號(hào)、組件名、電氣接口等；剛性組件裝配信息包括各機(jī)械零部件、電氣元器件間的相對(duì)位置和方向定位關(guān)系以及各機(jī)械零部件、電氣元器件參與裝配的局部幾何結(jié)構(gòu)之間的配合關(guān)系等。

圖1 線(xiàn)纜信息集成模型

2 線(xiàn)纜信息本體建模

本體是共享概念模型的明確形式化規(guī)范說(shuō)明[10]，是目前廣泛接受的語(yǔ)義 Web知識(shí)表示方法，具有很強(qiáng)的語(yǔ)義表達(dá)能力，能夠描述概念與概念之間的繼承(is-a)關(guān)系、部分與整體(part-of)關(guān)系、概念實(shí)例與概念(instance-of)關(guān)系以及概念的屬性(attribute-of)關(guān)系。本體確定了該領(lǐng)域內(nèi)共同認(rèn)可的概念明確定義，通過(guò)概念之間的關(guān)系描述了概念的語(yǔ)義，其任務(wù)是對(duì)某種形式化描述的近似，以建立一套計(jì)算機(jī)可以識(shí)別并理解的“機(jī)器描述”，從而使得人與人之間、人與機(jī)器之間以及機(jī)器與機(jī)器之間不但可以基于語(yǔ)法上而且可以基于語(yǔ)義上的交互。在針對(duì)復(fù)雜機(jī)電產(chǎn)品開(kāi)展并行設(shè)計(jì)過(guò)程中，需要多次用到線(xiàn)纜相關(guān)信息，這些信息有的是本領(lǐng)域的知識(shí)，有的是其他領(lǐng)域的知識(shí)；有的是本地?cái)?shù)據(jù)庫(kù)、本地信息模型里的知識(shí)，有的是異地?cái)?shù)據(jù)庫(kù)、異地信息模型里的知識(shí)。這些不同存儲(chǔ)源、不同層次的線(xiàn)纜設(shè)計(jì)信息之間由于其差異性導(dǎo)致的語(yǔ)義沖突和不一致，會(huì)造成設(shè)計(jì)過(guò)程中數(shù)據(jù)共享和數(shù)據(jù)重用困難等問(wèn)題。因此，對(duì)于線(xiàn)纜信息所涉及的數(shù)據(jù)多、模型亂和系統(tǒng)異構(gòu)等問(wèn)題，本體技術(shù)可以通過(guò)建立統(tǒng)一模型對(duì)與線(xiàn)纜相關(guān)的信息進(jìn)行組織，解決線(xiàn)纜工程語(yǔ)義信息的不一致，以最大限度實(shí)現(xiàn)數(shù)據(jù)共享，大幅提高線(xiàn)纜設(shè)計(jì)信息的使用效率。

基于 ChIIM的線(xiàn)纜信息本體建?？梢詮木€(xiàn)纜類(lèi)型和線(xiàn)纜信息分類(lèi)2個(gè)大方面進(jìn)行分析?！熬€(xiàn)纜類(lèi)型”本體類(lèi)描述了工程實(shí)際中常用的線(xiàn)纜表現(xiàn)形式，主要包括單芯導(dǎo)線(xiàn)、多芯線(xiàn)纜、扁平線(xiàn)纜以及線(xiàn)束等4類(lèi)子本體?！熬€(xiàn)纜信息分類(lèi)”本體類(lèi)按照 ChIIM 的分類(lèi)表示法，主要由線(xiàn)纜幾何信息、線(xiàn)纜拓?fù)湫畔?、線(xiàn)纜物理屬性信息、線(xiàn)纜管理信息、線(xiàn)纜輔助材料信息等組成。每一個(gè)子本體類(lèi)可以再細(xì)劃分為子子本體，如“線(xiàn)纜幾何信息”本體類(lèi)可以細(xì)劃分為線(xiàn)纜分支空間路徑、線(xiàn)纜分支情況、分支空間位姿、分支截面形狀、分支截面大小等；“分支截面形狀”本體類(lèi)又可以細(xì)劃分為圓形、扇形等?！拔锢韺傩孕畔ⅰ北倔w類(lèi)可以細(xì)劃分為線(xiàn)纜密度、抗彎特性、抗拉特性、最小折彎半徑等?！熬€(xiàn)纜管理屬性信息”本體類(lèi)可以細(xì)劃分為線(xiàn)纜名稱(chēng)、線(xiàn)纜代號(hào)、技術(shù)要求、設(shè)計(jì)版本等。基于 ChIIM的線(xiàn)纜信息本體模型如圖2所示。

圖2 線(xiàn)纜信息本體模型（部分）

圖2中“線(xiàn)纜標(biāo)識(shí)”類(lèi)用來(lái)唯一標(biāo)識(shí)該線(xiàn)纜信息（規(guī)格型號(hào)等）；“信息描述”類(lèi)主要幫助設(shè)計(jì)人員對(duì)線(xiàn)纜信息的理解；圓形、扇形和瓦形以實(shí)例形式附屬于“分支截面形狀”本體類(lèi)。例如，在一項(xiàng)復(fù)雜機(jī)電產(chǎn)品設(shè)計(jì)任務(wù)中，設(shè)計(jì)人員被要求設(shè)計(jì)一根型號(hào)為BVV的銅芯聚氯乙烯絕緣氯乙烯護(hù)套圓形線(xiàn)纜，要求包括線(xiàn)纜類(lèi)型為多芯線(xiàn)纜，芯線(xiàn)數(shù)為3根，截面形狀為圓形，最小折彎半徑為0.5 mm，單根導(dǎo)線(xiàn)直徑為2.5 mm，護(hù)線(xiàn)套為絕緣膠帶。設(shè)計(jì)信息的本體表達(dá)如下。

＜線(xiàn)纜設(shè)計(jì)信息 rdf:ID="多芯線(xiàn)纜的設(shè)計(jì)"＞

＜線(xiàn)纜標(biāo)識(shí) rdf:datatype="http://www.w3.org/2001/XMLSchema#string"＞spool標(biāo)識(shí)365＜/線(xiàn)纜標(biāo)識(shí)＞

＜信息描述 rdf:datatype="http://www.w3.org/2001/XMLSchema#string"＞

設(shè)計(jì)一根型號(hào)為BVV的銅芯聚氯乙烯絕緣氯乙烯護(hù)套圓形線(xiàn)纜

＜/信息描述＞

＜規(guī)格＞

＜線(xiàn)纜類(lèi)型設(shè)計(jì) rdf:ID="多芯線(xiàn)纜設(shè)計(jì)"＞

＜類(lèi)型 rdf:datatype="http://www.w3.org/2001/XMLSchema#string"＞多芯＜/類(lèi)型＞

＜/線(xiàn)纜類(lèi)型設(shè)計(jì)＞

＜/規(guī)格＞

＜規(guī)格＞

＜電氣參數(shù)設(shè)計(jì) rdf:ID="多芯線(xiàn)纜電氣參數(shù)設(shè)計(jì)"＞

＜芯線(xiàn)數(shù) rdf:datatype="http://www.w3.org/2001/XMLSchema#int"＞3＜/芯線(xiàn)數(shù)＞

＜截面形狀 rdf:datatype="http://www.w3.org/2001/XMLSchema#string"＞圓形＜/截面形狀＞

＜單根導(dǎo)線(xiàn)直徑 rdf:datatype="http://www.w3.org/2001/XMLSchema#float"＞2.5＜/單根導(dǎo)線(xiàn)直徑＞

＜物理屬性＞

＜最小折彎半徑 rdf:datatype="http://www.w3.org/2001/XMLSchema# float"＞ 0.5 ＜/最小折彎半徑＞

＜/物理屬性＞

＜/規(guī)格＞

＜輔助材料＞

＜護(hù)線(xiàn)套 rdf:datatype="http://www.w3.org/2001/XMLSchema#string"＞絕緣膠帶＜/護(hù)線(xiàn)套＞

＜/輔助材料＞

＜/線(xiàn)纜設(shè)計(jì)信息＞

3 線(xiàn)纜拓?fù)浣Y(jié)構(gòu)表示及存儲(chǔ)

3.1 線(xiàn)纜圖像劃分及無(wú)向圖建立

線(xiàn)纜拓?fù)浣Y(jié)構(gòu)中包含線(xiàn)纜圖像特征最有效的數(shù)字化信息。為了表達(dá)線(xiàn)纜的拓?fù)浣Y(jié)構(gòu)，建立一個(gè)信息完整的線(xiàn)纜數(shù)字化模型，文獻(xiàn)[3,8,11-12]進(jìn)行了相關(guān)的研究，雖然對(duì)線(xiàn)纜無(wú)向圖的建立及存儲(chǔ)方法有所提及，但只停留在方法的表述上，具體的無(wú)向圖建立過(guò)程沒(méi)有作詳細(xì)介紹和分析。

本文以圖3中某三維線(xiàn)纜零件作為劃分對(duì)象，采用文獻(xiàn)[13-14]提出的劃分算法對(duì)線(xiàn)纜圖像進(jìn)行劃分，并在線(xiàn)纜劃分結(jié)果的基礎(chǔ)上建立線(xiàn)纜的無(wú)向圖，用圖論的思想[15]來(lái)表達(dá)線(xiàn)纜零件的拓?fù)浣Y(jié)構(gòu)。因篇幅有限，具體的劃分步驟在此省略。

圖3 某三維線(xiàn)纜零件

按照上述劃分算法將圖 3劃分成圖 4(b)中CabS1,CabS2,…,CabS9共9個(gè)線(xiàn)纜段部分(這里只考慮圖4(b)中Ⅰ區(qū)域所示線(xiàn)纜零件)。

圖4 線(xiàn)纜零件劃分圖像及無(wú)向圖的建立

用無(wú)向圖的頂點(diǎn)來(lái)表示線(xiàn)纜段的端點(diǎn)及線(xiàn)纜段與線(xiàn)纜段之間的連接點(diǎn)，用無(wú)向圖的邊（或?。﹣?lái)表示端點(diǎn)與連接點(diǎn)（或連接點(diǎn)與連接點(diǎn)）之間的關(guān)系。如果線(xiàn)纜段連接點(diǎn)間是上下緊密相連的，則端點(diǎn)或連接點(diǎn)所對(duì)應(yīng)的頂點(diǎn)之間存在邊，否則就不存在。令G表示無(wú)向圖，V表示頂點(diǎn)集，E表示邊（或?。┘?， vi表示頂點(diǎn)， ei表示邊。利用上述無(wú)向圖建立方法，對(duì)圖4(a)、(b)建立的線(xiàn)纜無(wú)向圖如圖4(c)所示。為方便下文線(xiàn)纜無(wú)向圖的存儲(chǔ)分析，將圖4(c)單獨(dú)表示成如圖5所示。其中邊ei(·)括號(hào)內(nèi)的數(shù)值代表該段線(xiàn)纜展平后的長(zhǎng)度。

圖5 線(xiàn)纜零件無(wú)向圖

根據(jù)上述分析，有：線(xiàn)纜無(wú)向圖G=(V,E)；頂點(diǎn)集V(G)={v1,v2,…,v10}；邊集E(G)={e1,e2,…,e9},或E(G)={(v1,v2,8),(v1,v3,10),(v1,v4,6),(v1,v5,16), (v5,v6,20),(v6,v7,18),(v7,v8,15),(v8,v9,7),(v8,v10,9)}。上述邊的集合E(G)中，每個(gè)元素的第3個(gè)分量表示該邊的權(quán)值(長(zhǎng)度值)。

3.2 線(xiàn)纜無(wú)向圖的存儲(chǔ)

關(guān)于圖的存儲(chǔ)表示方法有很多種，常用的有3種：鄰接矩陣(adjacency matrix)、鄰接表(adjacency list)和鄰接多重表(adjacency multilists)。對(duì)圖5中的線(xiàn)纜零件無(wú)向圖分析可得無(wú)向圖G的鄰接矩陣為：

對(duì)()AG求平方，得：

首先對(duì)A2(G)進(jìn)行分析。由A2(G)的主對(duì)角線(xiàn)上元素非零可知，每個(gè)頂點(diǎn)vi(i=1,2,…,10)都有長(zhǎng)度（此處“長(zhǎng)度”表示邊的數(shù)量）為2的回路，其中頂點(diǎn) v1有4條，分別為：v1v2v1、 v1v3v1、 v1v4v1和v1v5v1；頂點(diǎn) v5、v6和 v7各有2條，分別為：v5v1v5和v5v6v5、v6v5v6和v6v7v6、v7v6v7和v7v8v7；頂點(diǎn) v8有3條，分別為：v8v7v8、v8v9v8和v8v10v8；頂點(diǎn) v2、v3、v4、v9和 v10只有1條，分別為：v2v1v2、v3v1v3、v4v1v4、v9v8v9和v10v8v10。分析每個(gè)頂點(diǎn)的回路數(shù)，有助于對(duì)圖G的連通性和不同頂點(diǎn)所屬的連通分支進(jìn)行判斷，進(jìn)而判斷線(xiàn)纜段之間的連接和分支情況。

記無(wú)向圖的邊數(shù)為N(E)，頂點(diǎn)數(shù)為n，易知N(E)=9，n=10，鄰接矩陣A(G)中的元素個(gè)數(shù)為n×n=100。由于N(E)＜＜n×n，邊的數(shù)目相對(duì)于A(G)中的元素個(gè)數(shù)比較少，鄰接矩陣?yán)锎鎯?chǔ)了較多的無(wú)用信息，使用鄰接矩陣存儲(chǔ)會(huì)浪費(fèi)較多的存儲(chǔ)空間，而用鄰接表存儲(chǔ)則可以節(jié)省較多的存儲(chǔ)空間。因此，本文采用鄰接表的形式來(lái)存儲(chǔ)線(xiàn)纜零件無(wú)向圖。

(1) 建立頂點(diǎn)數(shù)組。頂點(diǎn)數(shù)組用來(lái)記錄線(xiàn)纜零件無(wú)向圖中各個(gè)頂點(diǎn)的信息。數(shù)組元素下標(biāo)從0開(kāi)始計(jì)起。對(duì)于圖5中的線(xiàn)纜零件無(wú)向圖，頂點(diǎn)集為V(G)={v1,v2,…,v10}，數(shù)組元素下標(biāo)為0,1,…,9。據(jù)此建立的頂點(diǎn)數(shù)組如圖6所示。

圖6 線(xiàn)纜無(wú)向圖的頂點(diǎn)數(shù)組

(2) 建立鄰接表。在線(xiàn)纜無(wú)向圖頂點(diǎn)數(shù)組的基礎(chǔ)上，建立圖5所示無(wú)向圖對(duì)應(yīng)的鄰接表如圖7所示。在鄰接表的頂點(diǎn)數(shù)組中，每個(gè)元素有兩個(gè)成員：一個(gè)成員用來(lái)存儲(chǔ)頂點(diǎn)信息；另一個(gè)成員為該頂點(diǎn)的邊鏈表的表頭指針，指向該頂點(diǎn)的邊鏈表。如果沒(méi)有從某個(gè)頂點(diǎn)發(fā)出的邊，則該頂點(diǎn)沒(méi)有邊鏈表，因此表頭指針為空(用符號(hào)“∧”表示)。此外，為了在鄰接表中將邊的權(quán)值也進(jìn)行存儲(chǔ)，在邊結(jié)點(diǎn)中增加了一個(gè)存儲(chǔ)單元，如邊結(jié)點(diǎn)中的中間數(shù)值“8”即代表邊的權(quán)值。

(3) 線(xiàn)纜無(wú)向圖最短路徑搜索。最短路徑問(wèn)題要解決的就是求加權(quán)圖G=(V,E,W)(W表示邊ei上的權(quán)值)中兩個(gè)給定頂點(diǎn)之間的最短路徑。為實(shí)現(xiàn)對(duì)線(xiàn)纜拓?fù)浣Y(jié)構(gòu)中某些特定信息的查詢(xún)，如任意兩頂點(diǎn)間的最短路徑搜索、通路搜索等，可利用Floyd-Warshall算法[16]求得。Floyd-Warshall算法用于求解任意兩點(diǎn)間的最短距離，算法通過(guò)考慮最佳子路徑來(lái)得到最佳路徑，其時(shí)間復(fù)雜度為O(n3)(n為頂點(diǎn)數(shù))。

圖7 線(xiàn)纜無(wú)向圖的鄰接表

4 方法驗(yàn)證

利用Visual C++6.0開(kāi)發(fā)環(huán)境，在鄰接表存儲(chǔ)算法基礎(chǔ)上，分別輸入線(xiàn)纜零件無(wú)向圖中的頂點(diǎn)數(shù)：10；邊數(shù)：9；所有頂點(diǎn)下標(biāo)：0，1，…，9；每條邊所連接的頂點(diǎn)對(duì)：(0, 1)、(0, 2)、(0, 3)、(0, 4)、(4, 5)、(5, 6)、(6, 7)、(7, 8)、(7, 9)。運(yùn)算結(jié)果如圖8所示。通過(guò)比較圖8的運(yùn)算結(jié)果和本文所建立的線(xiàn)纜無(wú)向圖的鄰接表(圖 7)可知，兩者的結(jié)果一致，表明本文建立的無(wú)向圖鄰接表可以有效地對(duì)線(xiàn)纜無(wú)向圖進(jìn)行存儲(chǔ)。需要說(shuō)明的是，權(quán)值的存儲(chǔ)在這里不作考慮。

圖8 線(xiàn)纜無(wú)向圖鄰接表的存儲(chǔ)實(shí)現(xiàn)

為求解線(xiàn)纜拓?fù)浣Y(jié)構(gòu)中任意兩頂點(diǎn)間的最短路徑值，由圖5可得線(xiàn)纜無(wú)向圖G的權(quán)值矩陣為：

其中，元素wij(1≤i,j≤10)表示邊vivj上的權(quán)值。若頂點(diǎn) vi與頂點(diǎn)vj無(wú)連邊，則 wij=∞。據(jù)此利用Floyd-Warshall算法可求出某一固定頂點(diǎn)到各個(gè)頂點(diǎn)之間的最短距離值。本文中將頂點(diǎn) v6設(shè)置為固定點(diǎn)，從而求得頂點(diǎn)v6到其他各個(gè)頂點(diǎn)(v1,v2,…,v10)之間的最短距離值分別為：36、44、46、42、20、0、18、33、40、42，其中值為“0”的數(shù)表示頂點(diǎn) v6到自身的距離。同時(shí)求得各條路徑所經(jīng)過(guò)的頂點(diǎn)分別為：v6→v5→v1→v1（對(duì)應(yīng)最短距離值36）、v6→v5→v1→v2（對(duì)應(yīng)最短距離值44）、v6→v5→v1→v3（對(duì)應(yīng)最短距離值46）、v6→v5→v1→v4（對(duì)應(yīng)最短距離值42）、v6→v5→v5（對(duì)應(yīng)最短距離值20）、 v6（對(duì)應(yīng)最短距離值0）、v6→v7（對(duì)應(yīng)最短距離值18）、v6→v7→v8（對(duì)應(yīng)最短距離值33）、v6→v7→v8→v9（對(duì)應(yīng)最短距離值40）、v6→v7→v8→v10（對(duì)應(yīng)最短距離值 42）。重復(fù)的頂點(diǎn)視為一個(gè)頂點(diǎn)。

5 結(jié) 束 語(yǔ)

線(xiàn)纜因具有復(fù)雜的拓?fù)浣Y(jié)構(gòu)和幾何形態(tài)、繁雜的工程語(yǔ)義信息而使得線(xiàn)纜的信息建模成為順利開(kāi)展布線(xiàn)設(shè)計(jì)、裝配工藝規(guī)劃和仿真分析的一個(gè)重要前提。本文提出了一種基于本體和無(wú)向圖的復(fù)雜線(xiàn)纜信息表達(dá)與分析方法，該方法從布線(xiàn)設(shè)計(jì)、裝配工藝規(guī)劃和仿真分析 3個(gè)維度建立ChIIM，從本體建模技術(shù)的角度分析并建立了線(xiàn)纜的工程語(yǔ)義信息本體模型，通過(guò)建立鄰接表來(lái)實(shí)現(xiàn)線(xiàn)纜零件無(wú)向圖在計(jì)算機(jī)中的存儲(chǔ)和表達(dá)。該方法能較好地解決工程實(shí)際中線(xiàn)纜語(yǔ)義信息統(tǒng)一表達(dá)難和線(xiàn)纜的存儲(chǔ)問(wèn)題。

[1] 寧汝新, 劉檢華, 唐承統(tǒng), 等. 虛擬裝配技術(shù)及其應(yīng)用[J]. 國(guó)防制造技術(shù), 2009, 4(2): 22-29.

[2] 尚 煒, 寧汝新, 劉檢華, 等. 復(fù)雜機(jī)電產(chǎn)品中的柔性線(xiàn)纜裝配過(guò)程仿真技術(shù)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2012, 24(6): 822-831.

[3] Conru A B. A genetic approach to the cable harness routing problem [C]//Proceedings of the 1st IEEE Conference on Computational Intelligence. Washington, D. C., USA, 1994: 200-205.

[4] Hergenr?ther E, Dahne P. Real-time virtual cables based on kinematics simulation [C]//Proceedings of the WSCG 2000. Pilzěn, Czech Republic: University of West Bohemia, 2000: 402-409.

[5] 魏發(fā)遠(yuǎn), 陳新發(fā), 王峰軍. 電纜虛擬布線(xiàn)及其逆運(yùn)動(dòng)學(xué)仿真[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2006, 18(10): 1623-1627.

[6] 萬(wàn)畢樂(lè), 寧汝新, 劉檢華, 等. 虛擬環(huán)境中線(xiàn)纜建模及布線(xiàn)的研究與實(shí)現(xiàn)[J]. 中國(guó)機(jī)械工程, 2006, 17(20): 2135-2139.

[7] 王金芳, 閆 靜, 武 凱, 等. 基于Pro/E的線(xiàn)纜裝配工藝規(guī)劃系統(tǒng)關(guān)鍵技術(shù)研究[J]. 中國(guó)機(jī)械工程, 2008, 19(13): 1565-1569.

[8] 尚 煒, 寧汝新, 劉檢華, 等. 一種以拓?fù)浣Y(jié)構(gòu)信息為骨架的線(xiàn)纜數(shù)字化模型[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2012, 18(12): 2588-2594.

[9] 劉佳順, 劉檢華, 王志斌, 等. 虛擬環(huán)境下復(fù)雜線(xiàn)纜的集成信息模型[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2013, 19(5): 964-971.

[10] Studer R, Benjamins V R, Fensel D. Knowledge engineering: principles and methods [J]. Data & Knowledge Engineering, 1998, 25(1-2): 161-197.

[11] Parmantier J P, Junqua I, Bertuol S, et al. Simplification method for the assessment of the EM response of a complex cable harness [C]//Proceedings of the 20th Int. Zurich Symposium on EMC, Zurich, 2009: 161-164.

[12] Ridel M, Savi P, Alberti M, et al. Numerical simulation of aeronautic cable topology and experimental validation [C]//Proceedings of the 2011 International Conference on Electromagnetics in Advanced Applications (ICEAA), Torino, Italy, 2011: 1356-1359.

[13] 楊承磊, 孟祥旭. 一種新的快速細(xì)化算法的設(shè)計(jì)與實(shí)現(xiàn)[J]. 工程圖學(xué)學(xué)報(bào), 1998, 19(3): 87-93.

[14] 楊承磊, 孟祥旭, 李學(xué)慶, 等. 基于無(wú)向圖的圖像整體骨架表示模型及其算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2000, 23(3): 293-299.

[15] 蔣建國(guó), 張 婕, 詹 曙, 等. 層次式圖切分快速分割算法[J]. 圖學(xué)學(xué)報(bào), 2012, 33(1): 44-49.

[16] 王海英, 黃 強(qiáng), 李傳濤, 等. 圖論算法及其MATLAB實(shí)現(xiàn) [M]. 北京: 北京航空航天大學(xué)出版社, 2010: 154.

Stored Analysis and Ontology Expression of Cable Harness Information for Complex Mechatronic Products

Wang Falin, Liao Wenhe, Guo Yu, Ju Chuanhai

(College of Mechanical and Electrical Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing Jiangsu 210016, China)

It was difficult to afford unified expression and storage for semantic information and complex topological structure of the cable harness in complex mechatronic products. Aiming at this problem, a method of expression and stored analysis on complex cable harness information based on ontology and undirected graph was proposed. A cable harness information integrated model based on three-dimensional degrees of wiring design, assembly process planning and simulation analysis was established firstly. Then the expression of cable harness semantic information was enhanced through the ontology modeling of the model information by using the ontology technology. Finally, divide the cable harness part into an undirected graph by using a horizontal split algorithm. On this basis, an adjacency list of undirected graph was built, and the storage and expression of the cable harness undirected graph in the computer were realized. A certain cable harness part was taken as the application case to verify the feasibility of this method.

cable harness; ontology; undirected graph; information integrated model; complex mechatronic products

TP 391

A

2095-302X(2015)03-0376-08

2014-09-14；定稿日期：2014-12-10

國(guó)防基礎(chǔ)科研資助項(xiàng)目；江蘇省研究生培養(yǎng)創(chuàng)新工程資助項(xiàng)目(KYLX_0311)；中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助項(xiàng)目

王發(fā)麟(1986-)，男，江西吉安人，博士研究生。主要研究方向?yàn)閿?shù)字化制造技術(shù)、虛擬裝配。E-mail：wj54nh@sina.com