基于節(jié)點(diǎn)偽近鄰的電路板近鄰網(wǎng)絡(luò)排序算法

曾佩佩 穆東旭 賈春宇

摘 ?要： 在運(yùn)用近鄰網(wǎng)絡(luò)排序集生成邊界掃描測(cè)試向量方法中，多以網(wǎng)絡(luò)局部或全局信息進(jìn)行節(jié)點(diǎn)近鄰關(guān)系排序，導(dǎo)致偽近鄰點(diǎn)的識(shí)別排序能力較差。該文結(jié)合LeaderRank算法引入節(jié)點(diǎn)偽近鄰作為局部重要性指標(biāo)，首先利用LeaderRank求得網(wǎng)絡(luò)節(jié)點(diǎn)的全局重要度，然后基于相關(guān)鄰居關(guān)系提出節(jié)點(diǎn)偽近鄰比計(jì)算方法，最后綜合LeaderRank的全局重要度值與節(jié)點(diǎn)偽近鄰性求得總體重要度，從而獲得近鄰網(wǎng)絡(luò)重要度排序。采用所提方法和以往近鄰排序算法對(duì)實(shí)際電路板網(wǎng)絡(luò)模型進(jìn)行近鄰關(guān)系排序，對(duì)排序結(jié)果進(jìn)行比較，并用SIR傳染病模型進(jìn)行仿真分析。實(shí)驗(yàn)結(jié)果表明，所提方法能夠彌補(bǔ)以往排序算法的不足，從而獲得更為精確的排序結(jié)果。

關(guān)鍵詞： 近鄰網(wǎng)絡(luò)排序; 節(jié)點(diǎn)偽近鄰; LeaderRank; 重要度排序; SIR模型; 仿真分析

中圖分類號(hào)： TN710?34; TP301.6 ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2020）02?0005?04

Circuit board neighboring network sorting algorithm based on node pseudo?adjacency

ZENG Peipei1， MU Dongxu2， JIA Chunyu2

Abstract： In the method of generating the boundary scan testing vector with the neighboring network sorting sets， the node adjacent relationship is sorted mostly according to the local or global network information， which results in poor recognition and sorting abilities of the pseudo?adjacent nodes. The pseudo?adjacency node is introduced as the local importance index by means of the LeaderRank algorithm. The global importance of the network node is obtained with the LeaderRank， and then the calculation method of the node pseudo?adjacency ratio is proposed based on the related neighboring relationship. The overall importance of the network node is acquired by synthesizing the global importance value of LeaderRank and the pseudo?adjacency property of nodes， so as to obtain the importance sorting of the neighboring networks. The neighboring relationship of the real circuit board network models is sorted by means of the method proposed in this paper and the previous neighboring sorting algorithm. The sorting results are compared， and the SIR infectious disease model is used for the simulation analysis. The experimental results show this method can make up for the shortcomings of the previous sorting algorithms， so as to obtain the more accurate sorting results.

Keywords： neighboring network sorting; node pseudo?adjacency; LeaderRank; importance sorting; SIR model; simulation analysis

0 ?引 ?言

隨著電路板的不斷集成化，電路網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜化，掃描測(cè)試難度也不斷加大。在應(yīng)用邊界掃描技術(shù)對(duì)電路板進(jìn)行相關(guān)測(cè)試時(shí)，難點(diǎn)在于如何生成緊湊性更好，完備性更高的測(cè)試向量。目前，主流的測(cè)試向量生成算法設(shè)計(jì)思想來源于1989年C.W.YAU和Jarwala提出的近鄰網(wǎng)絡(luò)排序集最大獨(dú)立性算法。但由于無法有效獲得準(zhǔn)確的近鄰排序網(wǎng)絡(luò)集，所以只能在理論上探討。隨后有關(guān)學(xué)者相繼提出了多種近鄰網(wǎng)絡(luò)排序算法，如Jarwala后來提出的基于近鄰獨(dú)立性的測(cè)試生成優(yōu)化方法，該方法前提是已獲得近鄰網(wǎng)絡(luò)排序集，然后根據(jù)近鄰獨(dú)立性對(duì)測(cè)試向量生成進(jìn)行相關(guān)優(yōu)化，并獲得了較好效果。近年來，學(xué)者在網(wǎng)絡(luò)重要節(jié)點(diǎn)近鄰排序上提出了很多指標(biāo)和算法，如基于電路板結(jié)構(gòu)信息的近似近鄰網(wǎng)絡(luò)排序算法，該算法運(yùn)用有限制短路故障模型[1?2]，根據(jù)網(wǎng)絡(luò)間短路可能性大小，利用最短路徑法得到該電路板網(wǎng)絡(luò)結(jié)構(gòu)的一個(gè)近似近鄰排序網(wǎng)絡(luò)集。但該方法不僅概率閾值難以確定，而且只從局部重要度指標(biāo)考慮，排序結(jié)果并不理想。LeaderRank算法是對(duì)PageRank算法進(jìn)一步優(yōu)化，通過在原網(wǎng)絡(luò)中加入背景節(jié)點(diǎn)，相當(dāng)于PageRank中的跳轉(zhuǎn)概率S，從而使得算法的收斂速度和魯棒性有了明顯提升，相比其他同類型近鄰節(jié)點(diǎn)重要性排序方法，該方法更有優(yōu)勢(shì)[3?4]。

雖然上述方法能夠較好地解決近鄰網(wǎng)絡(luò)排序問題，但多數(shù)只片面從節(jié)點(diǎn)的全局重要度或局部重要度上進(jìn)行考慮，忽略了電路網(wǎng)絡(luò)節(jié)點(diǎn)間相互作用對(duì)整個(gè)網(wǎng)絡(luò)的影響，從而導(dǎo)致在復(fù)雜網(wǎng)絡(luò)偽近鄰節(jié)點(diǎn)排序不明確，不能獲得更精確的網(wǎng)絡(luò)排序集。為解決上述問題，本文在LeaderRank的基礎(chǔ)上引入節(jié)點(diǎn)偽近鄰性作為局部重要性指標(biāo)，提出了基于節(jié)點(diǎn)偽近鄰性的PseudoRank電路板近鄰網(wǎng)絡(luò)排序方法。首先結(jié)合相關(guān)鄰居關(guān)系從局部表征節(jié)點(diǎn)偽近鄰;然后將其擴(kuò)展到全局，提出一種綜合方法來獲得節(jié)點(diǎn)的偽近鄰比;最后結(jié)合LeaderRank算法求得節(jié)點(diǎn)的總體重要度值。該方法綜合利用節(jié)點(diǎn)全局和局部重要性指標(biāo)對(duì)節(jié)點(diǎn)進(jìn)行近鄰重要度評(píng)價(jià)，最終和其他幾種經(jīng)典算法進(jìn)行比較，從實(shí)驗(yàn)結(jié)果可以看出，本文方法能夠克服以往的不足，從而獲得更為準(zhǔn)確的近鄰網(wǎng)絡(luò)排序，實(shí)現(xiàn)測(cè)試向量的進(jìn)一步優(yōu)化。

1 ?PseudoRank近鄰網(wǎng)絡(luò)排序算法

1.1 LeaderRank算法

LeaderRank算法是在原網(wǎng)絡(luò)基礎(chǔ)上增加一個(gè)節(jié)點(diǎn)[vg]與其余所有[n]個(gè)節(jié)點(diǎn)相連，組成一個(gè)節(jié)點(diǎn)數(shù)為[n+1]的強(qiáng)連接網(wǎng)絡(luò)。

定義1 ?[LRi]定義為節(jié)點(diǎn)[vi]的全局重要度。[LRi（k）]為經(jīng)過[t]次迭代系統(tǒng)達(dá)到穩(wěn)態(tài)后節(jié)點(diǎn)[vi]的重要度初值。隨后，背景節(jié)點(diǎn)[g]將其重要度值平均分配給網(wǎng)絡(luò)其他[n]個(gè)節(jié)點(diǎn)，從而得到節(jié)點(diǎn)[vi]的全局重要度。因此節(jié)點(diǎn)[vi]的最終的全局重要度[LRi]值為：

[LRi（0）=1nLRi（t）=j=0naijdjLRj（t-1） ， t=1，2，…LRi=LRi（t）+LRg（t）·n-1] ? ? ?（1）

式中：[n]為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù);若節(jié)點(diǎn)[vi]，[vj]直接相連，則[aij=1]，否則為0;[dj]為節(jié)點(diǎn)[vj]的度值;[LRg（t）]為系統(tǒng)穩(wěn)定狀態(tài)下背景節(jié)點(diǎn)[vg]的重要度。

1.2 ?節(jié)點(diǎn)偽近鄰性

在實(shí)際電路網(wǎng)絡(luò)中，隨著電路板的不斷集成化，器件管腳、焊點(diǎn)、網(wǎng)絡(luò)間距愈發(fā)密集，近鄰網(wǎng)絡(luò)間通常具有一定偽近鄰關(guān)系。如圖1所示，假定相連節(jié)點(diǎn)物理間距近似相等，由有限制短路故障模型理論[5]可知，相鄰網(wǎng)絡(luò)間短路的可能性相同。又由于節(jié)點(diǎn)1，2的一階近鄰度相同，均為4，故依據(jù)以往排序方法無法對(duì)兩節(jié)點(diǎn)有效排序。然而，節(jié)點(diǎn)1，2二階近鄰度不同，節(jié)點(diǎn)C與F相連，致使C的重要性增加，從而使得節(jié)點(diǎn)1，2的重要度略有差異，即節(jié)點(diǎn)間存在偽近鄰關(guān)系。

目前計(jì)算節(jié)點(diǎn)偽近鄰相似性算法大致分為兩種：一是局部節(jié)點(diǎn)近鄰相似性算法，如文獻(xiàn)[6?7]基于相關(guān)鄰居關(guān)系的節(jié)點(diǎn)偽近鄰度;二是全局節(jié)點(diǎn)近鄰相似性算法，如文獻(xiàn)[8?10]將網(wǎng)絡(luò)結(jié)構(gòu)局部特征信息擴(kuò)展到全局來求解節(jié)點(diǎn)的偽近鄰度。

本文綜合全局和局部重要度，利用相關(guān)鄰居關(guān)系從局部拓?fù)渖蟻砗饬抗?jié)點(diǎn)偽近鄰度，然后將其擴(kuò)展到全局來求解節(jié)點(diǎn)偽近鄰度。相關(guān)鄰居關(guān)系計(jì)算方法如下：

[P（vi，vj）=N（vi）?N（vj）+E[N（vi）?N（vj）]] ? ? （2）

式中：[N（vi）?N（vj）]為節(jié)點(diǎn)[i]，[j]間的共同鄰居節(jié)點(diǎn)數(shù);[E（G[N（vi）?N（vj）]）]為節(jié)點(diǎn)[i]，[j]共同鄰居間的邊數(shù)。

結(jié)合相關(guān)鄰居關(guān)系計(jì)算方法，本文定義局部節(jié)點(diǎn)偽近鄰比為：

[Lpse（vi，vj）=N（vi）?N（vj）+E [N（vi）?N（vj）]1+N（vi）?N（vj）+E [N（vi）?N（vj）]]

（3）

式中： [N（vi）?N（vj）]為節(jié)點(diǎn)[i]，[j]的一階共同鄰居節(jié)點(diǎn)數(shù);[E[N（vi）?N（vj）]]為節(jié)點(diǎn)[i]，[j]所有共同一階鄰居節(jié)點(diǎn)間的邊數(shù);[N（v1）?N（v2）]表示節(jié)點(diǎn)[i]，[j]非共同一階鄰居節(jié)點(diǎn)數(shù);[E[N（v1）?N（v2）]]表示節(jié)點(diǎn)[i]，[j]非共同一階鄰居節(jié)點(diǎn)間的邊數(shù)。如圖1所示，[N（v1）?N（v2）=2]，[E[N（v1）?N（v2）]=1]，[N（v1）?N（v2）=4]，[E[N（v1）?N（v2）]=3]，所以節(jié)點(diǎn)1和節(jié)點(diǎn)1之間的局部相似性為[（1+2+1）（1+4+3）]=0.5。

對(duì)式（3） 進(jìn)行推廣，定義全局節(jié)點(diǎn)偽近鄰比：[Gpse（vi，vj）=0， ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?i，j不可達(dá)k=1nLpse（vqk，vq（k+1））， ? i，j非鄰居但可達(dá)] ?（4）

式中：[vq1=vi];[vq（n+1）=vj];[qk（k=1，2，…n）]為節(jié)點(diǎn)[i]到[j]的最短路徑上所有節(jié)點(diǎn)集合。

從而得到本文中節(jié)點(diǎn)間偽近鄰比：

[pse（vi，vj）=Lpse（vi，vj）， ? ? ?i，j相鄰Gpse（vi，vj）， ? ? 其他] （5）

定義2 ?PseudoRank矩陣[PseR]，節(jié)點(diǎn)[i]的[PR]重要度值如下：

[PRi=LRij∈αipse（vi，vj）+1ki+1LRj] （6）

式中，[αi]為節(jié)點(diǎn)[vj]的鄰居節(jié)點(diǎn)集合。從式（6）可以看出，節(jié)點(diǎn)重要度與其鄰居節(jié)點(diǎn)個(gè)數(shù)、鄰居節(jié)點(diǎn)重要度值以及節(jié)點(diǎn)對(duì)間的相互影響力有關(guān)。

2 ?算法仿真與分析

2.1 節(jié)點(diǎn)重要性排序

對(duì)所提算法進(jìn)行仿真與分析驗(yàn)證前，首先根據(jù)Protel DXP提供的電路板結(jié)構(gòu)信息、網(wǎng)表信息建立短路故障網(wǎng)絡(luò)模型。本文以某機(jī)載雷達(dá)信號(hào)處理板為樣例建立短路故障模型[2]，如圖2所示。

[6] BILAL S， ABDELOUAHAB M. Node similarity and modularity for finding communities in networks [J]. Physica a statistical mechanics & its applications， 2018， 492： 1958?1966.

[7] YANG Y， PEI J， AL?BARAKATI A. Measuring in?network node similarity based on neighborhoods： a unified parametric approach [J]. Knowledge & information systems， 2017， 53（1）： 43?70.

[8] JOCIC M， PAP E， SZAK?L A， et al. Managing big data using fuzzy sets by directed graph node similarity [J]. Acta polytechnica hungarica， 2017， 14（2）： 183?200.

[9] MOLLGAARD Anders， ZETTLER Ingo， DAMMEYER Jesper， et al. Measure of node similarity in multilayer networks [J]. Plos one， 2016， 11（6）： 0157436.

[10] 蒲國民，郁濱，朱璇.一種基于鄰居關(guān)系的ZigBee抗節(jié)點(diǎn)復(fù)制攻擊方法[J].系統(tǒng)仿真學(xué)報(bào)，2014，26（5）：1026?1031.

[11] 單治超.有限隨機(jī)圖上的隨機(jī)游動(dòng)和傳染病模型[J].數(shù)學(xué)進(jìn)展，2017，46（1）：1?12.

[12] T?NSING C， TIMMER J， KREUTZ C. Profile likelihood?based analyses of infectious disease models [J]. Statistical methods in medical research， 2018， 27（1）： 44?46.

[13] RUI X， MENG F， WANG Z， et al. SPIR： the potential spreaders involved sir model for information diffusion in social networks [J]. Physica a statistical mechanics & its applications， 2018， 506： 101?110.

[14] KUNIYA T， WANG J. Global dynamics of an SIR epidemic model with nonlocal diffusion [J]. Nonlinear analysis real world applications， 2018， 43： 262?282.

[15] YUAN X， WANG F， XUE Y， et al. Global stability of an SIR model with differential infectivity on complex networks [J]. Physica a statistical mechanics & its applications， 2018， 499： 162?168.

作者簡介：曾佩佩（1988—），男，助理工程師，主要研究方向?yàn)閳D像處理、飛行控制系統(tǒng)、機(jī)載電子系統(tǒng)故障診斷。

穆東旭（1992—），男，碩士研究生，主要研究方向?yàn)闄C(jī)載電子系統(tǒng)可測(cè)試性技術(shù)、故障診斷。

賈春宇（1993—），男，碩士研究生，主要研究方向?yàn)闄C(jī)載電子系統(tǒng)可測(cè)試性技術(shù)、故障診斷。