基于拉普拉斯矩陣的網(wǎng)絡(luò)社區(qū)劃分算法在電纜網(wǎng)測試中的應(yīng)用

王 兵，魏志強(qiáng)，蔡文杰，閆佳暉，張莉莉，趙 凱

（1.北京航天計量測試技術(shù)研究所，北京 100076；2.中國運(yùn)載技術(shù)火箭研究院，北京 100076）

1 引 言

在大型工程項(xiàng)目中使用大量電纜，這些電纜盤根錯節(jié)構(gòu)成了復(fù)雜的電纜網(wǎng)，各種控制和供電信號在其中穿梭，猶如人體中的神經(jīng)系統(tǒng)，支撐著大型工程項(xiàng)目各種重要信息的交互。其中的低頻電纜如同裝備中的血液，為各種元器件傳輸能量。在大型工程項(xiàng)目使用前，為保證任務(wù)的成功率，必須要進(jìn)行低頻電纜網(wǎng)的導(dǎo)通絕緣性能測試。低頻電纜網(wǎng)的測試從早期的絕緣電表和萬用表測試，發(fā)展到今天的使用自動化儀器電纜網(wǎng)測試儀進(jìn)行測試，測試效率成倍提升。電纜網(wǎng)測試儀通過轉(zhuǎn)接電纜將被測電纜網(wǎng)的芯點(diǎn)統(tǒng)一到統(tǒng)一的接口連接器接入電纜網(wǎng)測試儀進(jìn)行測試。其中轉(zhuǎn)接電纜起到橋梁作用，將工裝不一的被測電纜統(tǒng)一到相同的工裝中。轉(zhuǎn)接電纜的常規(guī)設(shè)計方法是針對每一個測試節(jié)點(diǎn)工裝設(shè)計相應(yīng)的轉(zhuǎn)接電纜，然后根據(jù)測試網(wǎng)絡(luò)芯點(diǎn)間連接關(guān)系，使用對應(yīng)轉(zhuǎn)接電纜進(jìn)行測試，如圖1所示。但是這種測試方案由于單次測試接入測試儀的統(tǒng)一接口數(shù)量有限，導(dǎo)致測試效率較低。所以需要設(shè)計新型的轉(zhuǎn)接電纜和測試方案提高電纜網(wǎng)測試效率。

圖1 常規(guī)轉(zhuǎn)接電纜設(shè)計示意圖Fig.1 Schematic diagram of conventional converter cable design

本文從實(shí)際需求出發(fā)，采用改進(jìn)型轉(zhuǎn)接電纜設(shè)計方法，如圖2所示，通過將不同工裝對應(yīng)的轉(zhuǎn)接電纜設(shè)計到同一根轉(zhuǎn)接電纜中，充分利用統(tǒng)一工裝接口的芯點(diǎn)，以達(dá)到提高測試效率的目的。針對其中復(fù)雜電纜網(wǎng)子網(wǎng)絡(luò)劃分困難的問題，提出基于拉普拉斯矩陣的網(wǎng)絡(luò)社區(qū)劃分算法完成復(fù)雜關(guān)聯(lián)性強(qiáng)的電纜網(wǎng)子網(wǎng)絡(luò)劃分，從而確定轉(zhuǎn)接電纜和測試方案的設(shè)計，開展了網(wǎng)絡(luò)社區(qū)劃分算法在電纜網(wǎng)測試中的應(yīng)用研究，從方案原理和仿真對比兩方面進(jìn)行了驗(yàn)證。

圖2 改進(jìn)的轉(zhuǎn)接電纜設(shè)計示意圖Fig.2 Schematic diagram of improved conversion cable design

2 算法原理及應(yīng)用分析

2.1 算法原理

對電纜網(wǎng)進(jìn)行導(dǎo)通絕緣測試時，需要設(shè)計轉(zhuǎn)接電纜，將電纜接口統(tǒng)一為相同的連接器。將整個電纜網(wǎng)劃分為小于電纜網(wǎng)測試儀最大接入芯點(diǎn)數(shù)的子網(wǎng)絡(luò)，并設(shè)計轉(zhuǎn)接電纜和測試方案進(jìn)行測試。

在電纜網(wǎng)測試中，在忽略電纜網(wǎng)各接口節(jié)點(diǎn)芯點(diǎn)數(shù)量的前提下，可將被測電纜網(wǎng)抽象為具有n個節(jié)點(diǎn)，且節(jié)點(diǎn)間存在連接關(guān)系的無向節(jié)點(diǎn)網(wǎng)絡(luò)G，如圖3所示。測試電纜網(wǎng)絕緣導(dǎo)通關(guān)系即可抽象為測試無向節(jié)點(diǎn)網(wǎng)絡(luò)G中n個節(jié)點(diǎn)的連接關(guān)系。所以，轉(zhuǎn)接電纜的設(shè)計問題轉(zhuǎn)化為無向節(jié)點(diǎn)網(wǎng)絡(luò)G的子網(wǎng)絡(luò)劃分問題，只要將完整的電纜網(wǎng)劃分為關(guān)聯(lián)性弱的一個個子網(wǎng)絡(luò)，就可以根據(jù)子網(wǎng)絡(luò)進(jìn)行轉(zhuǎn)接電纜的優(yōu)化設(shè)計。

圖3 無向節(jié)點(diǎn)網(wǎng)絡(luò)GFig.3 Node network G

無向節(jié)點(diǎn)網(wǎng)絡(luò)G的子網(wǎng)絡(luò)劃分可以基于圖論中的子圖分割問題。對于無向節(jié)點(diǎn)網(wǎng)絡(luò)G，其節(jié)點(diǎn)間的連接關(guān)系A(chǔ)可表示為鄰接矩陣A，節(jié)點(diǎn)A表示節(jié)點(diǎn)i和節(jié)點(diǎn)j間的連接關(guān)系，如果A＝1，則節(jié)點(diǎn)i和節(jié)點(diǎn)j存在連通關(guān)系。反之，則不存在。而節(jié)點(diǎn)網(wǎng)絡(luò)G是無向網(wǎng)絡(luò)，所以A＝0，且A＝A。

同時無向節(jié)點(diǎn)網(wǎng)絡(luò)G某一節(jié)點(diǎn)i與其他節(jié)點(diǎn)連接關(guān)系的權(quán)值可構(gòu)造為度矩陣D。

從而可以得到拉普拉斯矩陣L＝D－A。

拉普拉斯矩陣有一些特性：

（1）在存在的特征值λ中，如果在G中存在k個子網(wǎng)絡(luò)，那么有k個λ＝0，這樣就可以通過特征值判斷網(wǎng)絡(luò)G中存在多少子網(wǎng)絡(luò)；

（2）最小特征值是0；

（3）最小非零特征值是圖的代數(shù)連通度，即表征網(wǎng)絡(luò)節(jié)點(diǎn)間的緊密程度，最小非零特征值越接近，網(wǎng)絡(luò)節(jié)點(diǎn)越緊密，反之越稀疏。同時最小非零特征值對應(yīng)的特征向量對應(yīng)各個網(wǎng)絡(luò)節(jié)點(diǎn)，特征向量的大小又反映了節(jié)點(diǎn)間的緊密程度。

所以可以借助拉普拉斯矩陣的以上特性作為網(wǎng)絡(luò)劃分的依據(jù)，得到最優(yōu)網(wǎng)絡(luò)節(jié)點(diǎn)劃分。

2.2 應(yīng)用分析

復(fù)雜電纜網(wǎng)導(dǎo)通絕緣測試網(wǎng)絡(luò)具備無向多分量的特點(diǎn)，并且往往是一個復(fù)雜的整體網(wǎng)絡(luò)，所以利用以上特性，可以利用無向網(wǎng)絡(luò)G的拉普拉斯矩陣的最小非零特征值對應(yīng)的特征向量得出哪些節(jié)點(diǎn)偏向組成一個子網(wǎng)絡(luò)的結(jié)論。

以某電纜網(wǎng)為例，設(shè)計過程如下：

（1）將復(fù)雜電纜網(wǎng)輸入文件抽象為無向網(wǎng)絡(luò)G；

（2）計算無向網(wǎng)絡(luò)的鄰接矩陣A和度矩陣D；

（3）得到拉普拉斯矩陣L＝D－A；

（4）計算拉普拉斯矩陣的特征值及特征向量；

（5）統(tǒng)計特征值等于0的個數(shù)，若大于1，則根據(jù)特征值0對應(yīng)的特征向量大小進(jìn)行子網(wǎng)絡(luò)劃分，得到的子網(wǎng)絡(luò)為完全獨(dú)立的子網(wǎng)絡(luò)。若第二小特征值大于0，則取第二小特征值對應(yīng)的特征向量作為拉普拉斯矩陣L的變換依據(jù)，將L矩陣中元素依據(jù)特征向量升序或降序進(jìn)行變換，可得最優(yōu)子網(wǎng)絡(luò)劃分矩陣K，可根據(jù)圖中的連接關(guān)系緊密程度逐個劃分子網(wǎng)絡(luò)以設(shè)計轉(zhuǎn)接電纜。同時根據(jù)矩陣K中的節(jié)點(diǎn)順序，得到電纜網(wǎng)測試順序優(yōu)化方案。

3 仿真驗(yàn)證

假設(shè)電纜網(wǎng)測試儀只有兩個插槽，每個插槽32芯點(diǎn)，共64芯點(diǎn)。每個節(jié)點(diǎn)都具有不同的芯點(diǎn)以及芯點(diǎn)間連接關(guān)系，如圖4所示。分別使用常規(guī)轉(zhuǎn)接電纜設(shè)計方法和測試方案與改進(jìn)后的設(shè)計方法和測試方案就測試效率做對比。

圖4 電纜網(wǎng)絡(luò)芯點(diǎn)連接關(guān)系圖Fig.4 Cable network core point connection diagram

3.1 轉(zhuǎn)接電纜常規(guī)設(shè)計法

轉(zhuǎn)接電纜常規(guī)設(shè)計法是針對每一根被測電纜的連接器設(shè)計對應(yīng)的專用轉(zhuǎn)接電纜，基于此得到的轉(zhuǎn)接電纜設(shè)計方案如表1所示。

表1 常規(guī)設(shè)計方法設(shè)計的轉(zhuǎn)接電纜設(shè)計方案Tab.1 Conventional design method to design the onversion cable design scheme

由轉(zhuǎn)接電纜設(shè)計方案和電纜網(wǎng)測試儀的接口信息，以及測試均最大化使用測試儀背板插槽的原則，得到電纜網(wǎng)測試插拔順序如表2所示。

表2 常規(guī)設(shè)計方法電纜網(wǎng)測試插拔順序Fig.2 Conventional design method cable network test plug and unplug sequence

需要制作1?！?＃八根轉(zhuǎn)接電纜。根據(jù)上表需要進(jìn)行9次電纜網(wǎng)測試，進(jìn)行9次插拔。

3.2 轉(zhuǎn)接電纜改進(jìn)設(shè)計方案

針對上述網(wǎng)絡(luò)使用基于拉普拉斯矩陣的社區(qū)劃分算法進(jìn)行轉(zhuǎn)接電纜和測試方案設(shè)計。根據(jù)第2章算法原理可得拉普拉斯矩陣，如圖5所示。

圖5 拉普拉斯矩陣表示的節(jié)點(diǎn)連接關(guān)系Fig.5 Node connection relationship represented by Laplace matrix

通過計算可得矩陣特征值分別為0，0.585 8，1，1，1.763 9，3.414 2，4，6.236 1。第二小特征值對應(yīng)特征向量為0.298，－0.393 4，－0.393 4，0.488 9，0.393 4，0.163，－0.163，－0.393 4。將L矩陣中元素依據(jù)特征向量升序進(jìn)行變換得到以下矩陣，如圖6所示。

圖6 經(jīng)變換后的節(jié)點(diǎn)連接關(guān)系Fig.6 The node connection relationship after transformation

從而得到轉(zhuǎn)接電纜設(shè)計方案見表3。表3中列出了優(yōu)化后的轉(zhuǎn)接電纜設(shè)計方案，根據(jù)節(jié)點(diǎn)劃分將關(guān)聯(lián)性較大的連接器集成在一個轉(zhuǎn)接電纜上，扁插頭芯點(diǎn)得到充分利用。

表3 改進(jìn)的轉(zhuǎn)接電纜設(shè)計方案Tab.3 Improved conversion cable design scheme

由于使用上述方案，扁插頭芯點(diǎn)數(shù)得以合理分配和充分利用，得到電纜網(wǎng)測試插拔順序，見表4。

表4 改進(jìn)的轉(zhuǎn)接電纜測試插拔順序Tab.4 Improved insertion and unplugging sequence of adapter cable test

共需6次測試，6次插拔，大大節(jié)省了電纜網(wǎng)測試儀轉(zhuǎn)接電纜的插拔時間，測試效率大大提高。

綜上所述，經(jīng)過改進(jìn)設(shè)計后的轉(zhuǎn)接電纜設(shè)計方法較常規(guī)轉(zhuǎn)接電纜設(shè)計方法，一方面減少了統(tǒng)一工裝連接器數(shù)量，降低了物料成本；另一方面通過減少插拔次數(shù)，減少了測試所需時間，提高了電纜網(wǎng)測試效率。

4 結(jié)束語

針對復(fù)雜電纜網(wǎng)中常規(guī)設(shè)計法設(shè)計的轉(zhuǎn)接電纜存在測試效率低的痛點(diǎn)問題，提出了基于拉普拉斯矩陣的社區(qū)網(wǎng)絡(luò)劃分算法進(jìn)行轉(zhuǎn)接電纜設(shè)計，實(shí)現(xiàn)了更高效率的電纜網(wǎng)測試。與常規(guī)轉(zhuǎn)接電纜設(shè)計方法相比，提升了單次接入電纜網(wǎng)有效測試芯點(diǎn)的數(shù)量，以此提高芯點(diǎn)的測試效率。本文設(shè)計的轉(zhuǎn)接電纜設(shè)計方案具有簡單易行的特點(diǎn)，為有效解決電纜網(wǎng)測試儀單次接入有效芯點(diǎn)最大化提出了合理方案。