﻿ 网络中多节点故障定位的探测路径选择算法
«上一篇
 文章快速检索 高级检索

 智能系统学报  2021, Vol. 16 Issue (4): 766-773  DOI: 10.11992/tis.202010007 0

### 引用本文

QI Xiaogang, WANG Zhiping, LI Jiahui, et al. Probing path selection algorithm for multi-node failure localization in networks[J]. CAAI Transactions on Intelligent Systems, 2021, 16(4): 766-773. DOI: 10.11992/tis.202010007.

### 文章历史

1. 西安电子科技大学 数学与统计学院，陕西 西安 710126;
2. 西安电子科技大学 计算机学院，陕西 西安 710071

Probing path selection algorithm for multi-node failure localization in networks
QI Xiaogang 1, WANG Zhiping 1, LI Jiahui 1, LIU Lifang 2
1. School of Mathematics and Statistics, Xidian University, Xi’an 710126, China;
2. School of Computer Science and Technology, Xidian University, Xi’an 710071, China
Abstract: A probing path selection algorithm based on active probing is proposed to solve the problem of existing fault localization algorithms’ inability to meet the requirements of multi-node failure localization, especially when a large number of failed nodes are present in the network. The algorithm mainly includes the greedy path selection algorithm for fault detection, which is used to iteratively select the probing path with the minimum weight to cover the nodes in the network, and the tabu link search algorithm for fault localization, which is used to generate the candidate path set multiple times to select the most suitable probing paths and thus solve the problem of multi-node failure localization. Simulation results on random network topologies and real network topologies show that the probing path selection algorithm has a higher successful localization ratio and lower probing cost than the existing node failure localization algorithms.
Key words: multi-node failure localization    active probing    probing path selection    greedy path selection    tabu link search    successful localization ratio    probing cost

Natu等[4]最先提出了基于自适应探测技术的探针选择算法。该算法主要包括贪婪故障检测算法GFD和贪婪故障定位算法GFL，能够很好地用于检测和定位网络中的少量节点故障。Lu等[6]提出了一种新的故障检测方法，目的是为了减轻基于主动探测引起的网络开销。该方法将整个网络的检测过程分为几个阶段。在每个阶段，只使用少量探针检测网络中的部分节点。Zheng等[7]提出了一种最小化探测成本的探测路径选择方法。该方法选择一组探测路径，这些路径对于实现可识别性和覆盖无法识别的目标链路最有用。Gyimothi等[8-9]研究了单节点故障定位的探测路径分配问题，提出了递归匹配收缩算法 RMCA来定位网络中的任何单个节点故障。Lin等[10]考虑最小化探针的数量和链路负载，并提出了一种选择探测路径的新方法。该方法对贪婪算法进行参数化，用来在探针数量和网络组件负载这两个目标上面达到平衡。Dusia等[11]提出了一种探针生成算法来生成候选探针集，从算法生成的候选探针集里选择探针能够降低监视网络的成本。在最近的研究中，Tayal等[12]认为应该将探针的长度限制在某个常数K上以减少探针的往返时间，并提出了根据网络中的链路流量测量结果动态地选择探针进行故障检测。

1 基本概念 1.1 问题描述

 Download: 图 1 选择探测路径识别目标节点 Fig. 1 Selecting probing paths to identify the target node
1.2 候选路径权重

 $w\left( p \right) = \frac{{\displaystyle \sum\limits_{l \in L\left( p \right)} {n\left( l \right)} }}{{\left| {M\left( p \right)} \right|}},p \in {\rm{CP}}$ (1)

2 探测路径选择算法 2.1 贪婪路径选择

1)初始化未覆盖节点集合NPN=V−PS，DP=Ø，n(l)=0，lE

2)对每一个探测站节点vi∈PS，使用Dijkstra最短路径算法计算节点vi到节点vj(ij)的最短路径pij，并将其加入到候选路径集CP中；

3)当NPN≠Ø时，从CP中选择权值最小的候选路径p

4)将路径p加入到探测路径集DP中；

5)从NPN中移除路径p上的所有节点；

6) for $\forall$ lL(p)

7) n(l)=n(l)+1

8) end for

9) end while

 Download: 图 2 选择探测路径进行故障检测 Fig. 2 Selecting probing paths for fault detection
2.2 禁忌链路搜索

1)初始化故障节点集Nf = Ø，正常节点集No = Ø，未知节点集Nu = Ø，n(l) = 0，lE，禁忌表T为空；

2)将正常探针经过的节点和故障探针经过的节点分别加入到正常节点集No和可疑节点集Ns中；

3) Ns=NsNo

4) while Ns≠Ø，生成探测站节点到所有可疑节点的候选路径集CP并计算每条候选路径的权重w(p)；

5) for $\forall$ nNs

6) if 节点n不在任何候选路径上，将节点n加入到Nu中；

7) end if

8) end for

9) Ns=NsNu

10) while Ns≠Ø & CP≠Ø

11) 选择具有最小权重w(p)的候选路径p，并沿路径p发送一个探针进行探测；

12) for $\forall$ lL(p)

13) n(l)=n(l)+1

14) end for

15) 从CP中移除候选路径p并根据探针结果更新NoNfNs

16) end while

17) for $\forall$ nNf

18)将所有与n关联的边加入禁忌表T中；

19) end for

20) end while

 Download: 图 3 选择探测路径进行故障定位 Fig. 3 Selecting probing paths for fault localization
3 实验与分析

3.1 BA无标度网络上的实验

 Download: 图 4 3种算法的比较结果 Fig. 4 Comparison results of the three algorithms

 Download: 图 5 本文算法在不同规模网络中的探测成本 Fig. 5 Probing cost of the algorithm in this paper in different scale networks
 Download: 图 6 本文算法在不同规模网络中的性能 Fig. 6 Performance of the algorithm in this paper in different scale networks
3.2 真实网络上的实验

4 结束语