基于节点伪近邻的电路板近邻网络排序算法

发布时间：2020-12-31 05:42

　　在运用近邻网络排序集生成边界扫描测试向量方法中,多以网络局部或全局信息进行节点近邻关系排序,导致伪近邻点的识别排序能力较差。该文结合LeaderRank算法引入节点伪近邻作为局部重要性指标,首先利用LeaderRank求得网络节点的全局重要度,然后基于相关邻居关系提出节点伪近邻比计算方法,最后综合LeaderRank的全局重要度值与节点伪近邻性求得总体重要度,从而获得近邻网络重要度排序。采用所提方法和以往近邻排序算法对实际电路板网络模型进行近邻关系排序,对排序结果进行比较,并用SIR传染病模型进行仿真分析。实验结果表明,所提方法能够弥补以往排序算法的不足,从而获得更为精确的排序结果。 

【文章来源】：现代电子技术. 2020年02期 北大核心

【文章页数】：5 页

【部分图文】：

局部节点伪近邻性

对所提算法进行仿真与分析验证前，首先根据Protel DXP提供的电路板结构信息、网表信息建立短路故障网络模型。本文以某机载雷达信号处理板为样例建立短路故障模型[2]，如图2所示。分别用最短路径法、重要度评价矩阵法、LeaderRank、本文的PseudoRank算法对图2网络节点进行排序，结果如表1所示（由于篇幅限制，只列出排名前10的节点）。由表1可知，与其他算法相比，PseudoRank算法更容易对网络伪近邻节点进行有效区分。由图2可以看出，节点1和34有相同邻居节点14,20,22,32，但由式（1）可知，节点1,34的非共同邻居节点不同，导致对两节点影响不同。对于节点1，其邻居节点2,3,4的重要性相对较高，从而对其影响较大；相对节点34而言，能够对其有重要影响的邻居节点只有排名相对较高的节点33，故相比之下节点1重要性高于34更为合理。同样，本文算法所得到的重要性排序结果中，节点8要高于32，虽然节点32的邻居节点33,34重要性排名在节点8的邻居节点1,2,3,4之前，但节点32的邻居节点相对较多，因节点间相互影响，其他邻居节点反而削弱了节点33,34对节点32的影响。因此，本文算法求得节点8的近邻关系重要性排在节点32之前。

从图3知，重要度评价、LeaderRank和PseudoRank节点传播重要度分布线性程度、收敛程度较好，说明本文方法排序结果更为准确合理，且各方法SIR值逐渐增大即传播深度逐渐加深。同时，图3中本文算法节点传播重要度较高的部分，其离散程度相对较低，故PseudoRank算法的网络节点近邻重要度排序更合理。对各算法在图2的排序结果进行传播验证，选取传播步数为50，观察网络节点处于I状态节点个数SI占总数的比例随时间的变化情况。为确保仿真结果的准确性，分别选取各算法排序结果前10%的节点作为传播起始点，传播仿真结果如图4所示。


本文编号：2949076