一种故障定位的探测选择方法
一种故障定位的探测选择方法
【技术领域】
[0001] 本发明属电力调度数据网运行智能化和自愈性方面的技术，尤其是故障定位的探 测选择方法。
【背景技术】
[0002] 故障定位是保证电力调度数据网运行智能化和自愈性的重要手段，监测到网络中 存在故障W后，我们会对探测结果进行分析，进行故障定位阶段的探测选择，目的是定位故 障的根源，为了达到运个目的，需要发送合适的探测来获取更多的信息。
[0003] 首先，我们先对故障检测的探测结果进行分析。若探测成功，我们认为成功探测经 过的所有节点均为正常节点，并将运些节点加入正常节点集合(Normal Node),若有节点之 前被判定为可疑节点，将其从可疑节点集合中删除;若探测失败，则失败探测路径上所有之 前未被判定为正常节点的节点均为可疑节点，并加入可疑节点集合(Suspicious Node);若 一条失败探测所经过的所有节点中，仅有一个节点为可疑节点，其他节点都被某些成功探 测经过，那么该可疑节点即为故障节点，并被加入故障节点集合(化ult Node)。
[0004] 然后，通过对故障检测阶段探测返回结果的分析，我们可W得出正常节点集合，可 疑节点集合W及故障节点集合。而可疑节点集合作为状态不确定的节点集合，将成为故障 定位阶段的探测的目标。目前故障定位阶段的探测选择方法有两大类:预先选择探测方式 和交互式选择探测方式。前者一次性选择出所有故障定位探测集合，发送到网络中并接收 探测结果，预先选择的方式对网络施加固定的负荷，虽然运种方式计算过程比较简单，但是 对所有的探测执行如此方式是极其低效的;交互式的探测方式每次根据上一次探测的探测 结果自适应地选择下一个探测，运样可W有效的减少所需执行探测的数量，从而得到更好 的时效性和更低的额外网络负载，但计算过程往往异常复杂。
[0005] 为了解现有技术的发展状况，对已有的论文和专利进行了检索、比较和分析，筛选 出如下与本发明相关度比较高的技术信息：
[0006] 已有技术方案1:专利号为CN103164775A的《一种电网设备状态自动评价平台及方 法》专利，设及电力系统分析与控制领域，尤其设及一种电网设备状态自动评价平台及方 法。，主要通过两步完成:第一，在线实时抽取监测数据，检索发生变化数据，依据发生变化 数据找出所属设备分类，调用评从模型进行评价;第二，对评价结果进行评分定级，提出检 修建议。
[0007] 已有技术方案2:专利号为CN103178991A的《一种多网络关系分析的方法和系统》 专利，设及网络监测技术领域，尤其设及一种多网络关系分析的方法和系统，主要通过Ξ步 完成:第一，首先通过虚拟路由器采集路由协议发现网络设备，并对网络设备协议状态进行 实时监测和诊断分析，发生异常变化时产生告警;第二，对承载网络、信令网络和传输网络 进行跨专业告警关联分析;第Ξ，当网络设备发生故障时，对所述网络设备所在网络中与之 关联的网络设备进行资源分析定位，判断影响程度，并在拓扑界面中呈现影响结果状态信 息。
[000引已有技术方案3:专利号为CN103188716A的《RUDP链路故障定位方法及装置》专利， 设及无线通信领域，尤其设及一种抓DP(Reliable User化化gramProtocol，可靠用户数据 报协议)链路故障定位方法及装置。预先在RUDP报文的报文头中增加故障定位字段，源节点 向目的节点间发送数据时，将故障定位参数填充到RUDP报文的故障定位字段中，发送给传 输路径上的下一跳节点，当上述传输路径发生故障时，上述源节点根据预设策略确定故障 点;上述装置包括RUDP报文管理模块和故障确定模块。
[0009] 已有技术方案1采用一种电网设备状态自动评价平台，可根据多种试验信息及设 备运行情况，综合诊断设备绝缘情况，为故障定位及设备检修提供决策支持，能对电网设备 状态进行实时、高效和准确的评价。该方案并没有具体的介绍如何实现故障定位，只是为提 出一种网络分析方法，为故障定位提供了有力的支持。已有技术方案2公开了一种多网络关 联分析的方法和系统，为快速故障定位修复提供有力支撑，并能够全面准确地掌握对全网 的影响范围，有效提升客户感知，保障网络高稳定、高质量、高效率地运行。该方案实现起来 比较复杂，需要分析拳王的拓扑，虽然故障定位准确，但是代价高。已有技术方案3预先在 RUDP报文的报文头中增加故障定位字段，源节点向目的节点间发送数据时，将故障定位参 数填充到RUDP报文的故障定位字段中，发送给传输路径上的下一跳节点，当上述传输路径 发生故障时，上述源节点根据预设策略确定故障点减少了数据的发送量，减轻网络负荷，但 是需要改变发送数据的格式，且不能完成故障的实时监测与定位。
【发明内容】
[0010] 本发明的目的正是为了克服上述现有技术存在的缺陷而提供一种故障定位的探 测选择方法，本发明在故障定位阶段的探测选择要求选择一个新的探测，该探测将要使得 可疑节点集合中的节点数量尽量减少，运样选择的探测次数才会更少，同时提高判断故障 节点的正确率，能够带来更少的额外网络负担。
[0011] 本发明是通过如下技术方案来实现的：
[0012] -种故障定位的探测选择方法，本发明的特征在于，包括:确定故障检测的探测选 择集合和确定故障定位的探针选择集合。
[0013] 在该方法中，确定故障检测的探测选择集合的步骤为：
[0014] S1:初始化，设探测集合为空；
[0015] S2:选取被最少探测覆盖的节点Nj，即探测依赖矩阵中列向量的权值最小的列对 应的节点；
[0016] S3:从能覆盖到节点的的探测中选出覆盖最多节点的探测Ti，然后删除该探测所覆 盖的所有节点，即探测依赖矩阵中能覆盖节点的的行向量的权值最大的列，然后删除该列 覆盖的节点所对应的列；
[0017] S4:重复S2，S3，直到所有的节点被覆盖。
[0018] 确定故障定位的探针选择集合的步骤为：
[0019] S1 :若I化η I为空或者备用探测集合中不包含经历可疑节点的探测则退出，否则将 备用测试集合中所有经历化η的探测从备用测试集合中删除，然后转入S2;
[0020] S2:在备用探测集合选择经历化η中节点最少且至少为1个的探测Ti，然后转入S3; [002。 S3:若Ti探测结果返回成功，则将该探测中经历Nsn中节点从Nsn中删除并加入Nnn， 并转入S4;若Τι探测结果返回失败，将该探测加入Tft，若在结果返回失败且该探测中只有1 个可疑节点，则将该可疑节点从化η中删除并加入化η中，然后转入S1 ;
[00。] S4:历遍Tft，将其中满足有且只有一个可疑节点的探测中的可疑节点从Nsn中删除 并加入化η中，并转入S1。
[0023] 在确定故障检测的探测选择集合和确定故障定位的探针选择集合之间，还包括W 下步骤:确定减少可疑节点的方法;遍历所有探测选择集合;其中，确定减少可疑节点的方 法，包括：
[0024] 1)若只覆盖一个可疑节点的探测测试结果返回失败，则表明该可疑节点为故障节 占.
[0025] 2)若覆盖可疑节点的探测测试结果返回成功，则表明运些可疑节点为正常节点； 当把运些可疑节点从可疑节点集合删除，加入正常节点集合之后，之前测试集合中结果返 回失败且覆盖多个可疑节点的探测若现在只含有一个可疑节点，则需要对所有的然后失败 的探测集合重新进行情况1)的判定。
[0026] 遍历所有探测选择集合，包括：
[0027] 在历遍过程中若路径返回正常，则将该路径的所有节点加入Νηη，否则将节点加入 Νηη 或 IMsno
[0028] 首故障定位阶段的探测选择的建模也是探测依赖矩阵，和故障探测阶段的探测选 择不同的是，本阶段的探测选择是从备选探测集合(未被作为探测的探测集合，在故障检测 阶段表示除了故障检测集合W外的可用探测集合，在故障定位阶段表示除了故障检测集合 和之前故障定位探测W外的可用探测集合）里面选取满足使得可疑节点数尽量减少的探 测。所W本阶段的探测必须覆盖可疑节点。
[0029] 故障定位阶段的探测选择有两种基本思路：
[0030] -是MAX算法:每次选择一个经历化η中节点最多的探测。若运次探测成功，则将使 得Nsn中的节点减少很多，反之，不能减少Nsn的节点。注意经历Nsn中所有节点的探测除外，因 为该探测一定返回失败。
[0031] 二是MIN算法:每次选择经历化η中节点最少(至少为1个)的探测。若运次探测成功， 则将使得Nsn中的节点减少至少1个，若探测失败，且当且仅当它经历一个节点时，我们把该 节点从化η中删除并加入化η。
[0032] -般来说，考虑到网络中出现故障的节点总是少数的，相对来说即使经历化η中节 点较多的探测成功的可能性也高于失败的可能性，选择MAX算法会更好一些，但是由于我们 在探测站点的选择上只使用3个节点，会导致很多可疑节点是故障节点的后续节点，即运些 可疑节点会伴随着故障节点一起出现，导致经历化η中节点较多的探测失败的可能性大大增 加，所W选择ΜΙΝ算法。
[0033] 算法改进：[0034] 对图2中160节点网络在存在2个故障时的故障定位阶段ΜΙΝ算法的探测选择过程 分析，在经历第114条测试路径（即故障定位阶段的第一次探测)之后，实际上已经把所有故 障节点确定下来了，但是由于不知道故障节点个数导致下面每次探测都选择经历可疑节点 最少的节点，运导致了测试次数的增多，如果一下测试都选择MAX算法就可W减少测试次 数。基于W上的思考，结合MIN算法和MAX算法，提出了一种改进算法。
[0035] 改进算法除了基于MIN和MAX算法，还有基于W下考虑：
[0036] 1.对于一个网络，节点故障概率比较低，存在的故障节点比较少；
[0037] 2.将网络中的所有节点和探测返回结果建立成贝叶斯网络，所有节点为因，探测 返回结果为果。信息增益最高的可疑节点最有可能是故障节点。
[0038] 那么改进后的算法思路为：
[0039] 1.假设存在可疑节点的网络只有1个故障节点，先算出所有可疑节点的信息增益， 选择信息增益最高的可疑节点；
[0040] 2.寻找只含该节点一个可疑节点的备用探测集合去验证该节点是否为故障节点， 若不是，则说明该节点为正常节点，并从新进行选择剩余疑节点的信息增益最高的来验证 的循环，若是，则假设该网络已无故障，使用MAX算法对其余可疑节点验证；
[0041] 3.若选择的MAX算法的探测结果返回正确，则确定了较多的节点是正常节点，继续 进行MAX算法验证循环，若返回失败，则说明该网络还存在故障节点，假设故障节点个数为 1，从新从第1步验证其余可疑节点。
[0042] 4.直到所有可疑节点都被确定或者备用探测集合中不在含有经过可疑节点的探 测为止。
[0043] 本发明的技术关键点在于：
[0044] 1、从备选探测集合里面选取满足使得可疑节点数尽量减少的探测，建立探测依赖 矩阵；
[0045] 2、分别提出基于MIN的算法和基于MIN和MAX算法的改进算法，能够有效减少探测 次数。
[0046] 本发明的有益效果:本专利提出一种故障定位探测选择技术，其优点在于，该技术 立足于探测依赖矩阵表示，利用MIN算法实现故障定位，首先建立探测依赖矩阵，之后针对 该探测依赖矩阵，利用MIN算法一次删除节点，直到最后剩下一个节点。则故障定位完成。之 后对算法加 W改进，提出基于MIN和MAX算法的改进算法。仿真试验表明，本发明所提方案， 可W有效减少故障探测的次数，而判断的正确率也得到了很大的提高。
【附图说明】
[0047] 图1为本发明算法流程图；
[0048] 图2为160节点网络在存在2个故障时的故障定位阶段MIN算法的探测选择过程。
【具体实施方式】
[0049] 见图1，一种故障定位的探测选择方法，本发明的特征在于，包括:确定故障检测的 探测选择集合和确定故障定位的探针选择集合。
[0050] 在该方法中，确定故障检测的探测选择集合的步骤为：
[0051] S1:初始化，设探测集合为空；
[0化2] S2:选取被最少探测
[0053] 覆盖的节点Nj，即探测依赖矩阵中列向量的权值最小的列对应的节点；
[0054] S3:从能覆盖到节点Nj的探测中选出覆盖最多节点的探测Ti，然后删除该探测所覆 盖的所有节点，即探测依赖矩阵中能覆盖节点的的行向量的权值最大的列，然后删除该列 覆盖的节点所对应的列；
[0055] S4:重复S2，S3，直到所有的节点被覆盖。
[0056] 确定故障定位的探针选择集合的步骤为：
[0057] S1:若I化η I为空或者备用探测集合中不包含经历可疑节点的探测则退出，否则将 备用测试集合中所有经历化η的探测从备用测试集合中删除，然后转入S2;
[005引S2:在备用探测集合选择经历化η中节点最少且至少为1个的探测Ti，然后转入S3; [0化9] S3 :若Ti探测结果返回成功，则将该探测中经历化η中节点从化η中删除并加入Nnn， 并转入S4;若Τι探测结果返回失败，将该探测加入Tft，若在结果返回失败且该探测中只有1 个可疑节点，则将该可疑节点从化η中删除并加入化η中，然后转入S1 ;
[0060] S4:历遍Tft，将其中满足有且只有一个可疑节点的探测中的可疑节点从化η中删除 并加入化η中，并转入S1。
[0061] 在确定故障检测的探测选择集合和确定故障定位的探针选择集合之间，还包括W 下步骤:确定减少可疑节点的方法;遍历所有探测选择集合;其中，确定减少可疑节点的方 法，包括：
[0062] 1)若只覆盖一个可疑节点的探测测试结果返回失败，则表明该可疑节点为故障节 占.
[0063] 2)若覆盖可疑节点的探测测试结果返回成功，则表明运些可疑节点为正常节点； 当把运些可疑节点从可疑节点集合删除，加入正常节点集合之后，之前测试集合中结果返 回失败且覆盖多个可疑节点的探测若现在只含有一个可疑节点，则需要对所有的然后失败 的探测集合重新进行情况1)的判定。
[0064] 遍历所有探测选择集合，包括：
[0065] 在历遍过程中若路径返回正常，则将该路径的所有节点加入Νηη，否则将节点加入 Νηη 或 IMsno
[0066] 表1 MAX与MIN算法的探测选择结果
[0067]
[006引
[0069]由表1可知，MAX算法虽然有着与MIN算法相同的故障定位能力，但是MAX算法选择 的探测次数远远大于MIN算法，所WMIN算法更好。MIN算法能够使用更少的探测次数找出所 有的故障节点，确定故障节点的正确率也是100%。很明显，通过故障定位就能够把所有的 故障找到，即完成了故障诊断。
【主权项】
1. 一种故障定位的探测选择方法，其特征在于，包括:确定故障检测的探测选择集合和 确定故障定位的探针选择集合;其中， 确定故障检测的探测选择集合的步骤为： S1:初始化，设探测集合为空； S2:选取被最少探测覆盖的节点Nj，即探测依赖矩阵中列向量的权值最小的列对应的节 占. S3:从能覆盖到节点化的探测中选出覆盖最多节点的探测，然后删除该探测所覆盖的 所有节点，即探测依赖矩阵中能覆盖节点K的行向量的权值最大的列，然后删除该列覆盖 的节点所对应的列； S4:重复S2，S3，直到所有的节点被覆盖； 确定故障定位的探针选择集合的步骤为： S1:若|Nsn |为空或者备用探测集合中不包含经历可疑节点的探测则退出，否则将备用 测试集合中所有经历他"的探测从备用测试集合中删除，然后转入S2; S2:在备用探测集合选择经历Nsn中节点最少且至少为1个的探测1\，然后转入S3;S3:gT1探测结果返回成功，则将该探测中经历队"中节点从Nsn中删除并加入Nnn，并转入 SLgTi探测结果返回失败，将该探测加入Tft，若在结果返回失败且该探测中只有1个可疑 节点，则将该可疑节点从Nsn中删除并加入阶"中，然后转入S1; S4:历遍Tft，将其中满足有且只有一个可疑节点的探测中的可疑节点从Nsn中删除并加 入Nfn中，并转入S1。2. 根据权利要求1所述的一种故障定位的探测选择方法，其特征在于，在确定故障检测 的探测选择集合和确定故障定位的探针选择集合之间，还包括以下步骤： 确定减少可疑节点的方法； 遍历所有探测选择集合。3. 根据权利要求2所述的一种故障定位的探测选择方法，其特征在于，所述确定减少可 疑节点的方法，包括： 1) 若只覆盖一个可疑节点的探测测试结果返回失败，则表明该可疑节点为故障节点； 2) 若覆盖可疑节点的探测测试结果返回成功，则表明这些可疑节点为正常节点；当把 这些可疑节点从可疑节点集合删除，加入正常节点集合之后，之前测试集合中结果返回失 败且覆盖多个可疑节点的探测若现在只含有一个可疑节点，则需要对所有的然后失败的探 测集合重新进行情况1)的判定。4. 根据权利要求2所述的一种故障定位的探测选择方法，其特征在于，所述遍历所有探 测选择集合，包括： 在历遍过程中若路径返回正常，则将该路径的所有节点加入Nnn，否则将节点加入Nnn或 Nsn〇
【专利摘要】一种故障定位的探测选择方法，包括：确定故障检测的探测选择集合和确定故障定位的探针选择集合。本发明提出一种故障定位探测选择的技术方法，该技术立足于探测依赖矩阵表示，利用MIN算法实现故障定位，首先建立探测依赖矩阵，之后针对该探测依赖矩阵，利用MIN算法一次删除节点，直到最后剩下一个节点。则故障定位完成。之后对算法加以改进，提出基于MIN和MAX算法的改进算法。仿真试验表明，本发明所提方案，可以有效减少故障探测的次数，而判断的正确率也得到了很大的提高。
【IPC分类】G01R31/08
【公开号】CN105486976
【申请号】CN201510807970
【发明人】田丰, 刘宇明, 刘彤, 何林宏, 李辉, 苏进, 李晓耕, 李朝广, 韩熙媛
【申请人】云南电力调度控制中心
【公开日】2016年4月13日
【申请日】2015年11月19日
【技术领域】
[0001] 本发明属电力调度数据网运行智能化和自愈性方面的技术，尤其是故障定位的探 测选择方法。
【背景技术】
[0002] 故障定位是保证电力调度数据网运行智能化和自愈性的重要手段，监测到网络中 存在故障W后，我们会对探测结果进行分析，进行故障定位阶段的探测选择，目的是定位故 障的根源，为了达到运个目的，需要发送合适的探测来获取更多的信息。
[0003] 首先，我们先对故障检测的探测结果进行分析。若探测成功，我们认为成功探测经 过的所有节点均为正常节点，并将运些节点加入正常节点集合(Normal Node),若有节点之 前被判定为可疑节点，将其从可疑节点集合中删除;若探测失败，则失败探测路径上所有之 前未被判定为正常节点的节点均为可疑节点，并加入可疑节点集合(Suspicious Node);若 一条失败探测所经过的所有节点中，仅有一个节点为可疑节点，其他节点都被某些成功探 测经过，那么该可疑节点即为故障节点，并被加入故障节点集合(化ult Node)。
[0004] 然后，通过对故障检测阶段探测返回结果的分析，我们可W得出正常节点集合，可 疑节点集合W及故障节点集合。而可疑节点集合作为状态不确定的节点集合，将成为故障 定位阶段的探测的目标。目前故障定位阶段的探测选择方法有两大类:预先选择探测方式 和交互式选择探测方式。前者一次性选择出所有故障定位探测集合，发送到网络中并接收 探测结果，预先选择的方式对网络施加固定的负荷，虽然运种方式计算过程比较简单，但是 对所有的探测执行如此方式是极其低效的;交互式的探测方式每次根据上一次探测的探测 结果自适应地选择下一个探测，运样可W有效的减少所需执行探测的数量，从而得到更好 的时效性和更低的额外网络负载，但计算过程往往异常复杂。
[0005] 为了解现有技术的发展状况，对已有的论文和专利进行了检索、比较和分析，筛选 出如下与本发明相关度比较高的技术信息：
[0006] 已有技术方案1:专利号为CN103164775A的《一种电网设备状态自动评价平台及方 法》专利，设及电力系统分析与控制领域，尤其设及一种电网设备状态自动评价平台及方 法。，主要通过两步完成:第一，在线实时抽取监测数据，检索发生变化数据，依据发生变化 数据找出所属设备分类，调用评从模型进行评价;第二，对评价结果进行评分定级，提出检 修建议。
[0007] 已有技术方案2:专利号为CN103178991A的《一种多网络关系分析的方法和系统》 专利，设及网络监测技术领域，尤其设及一种多网络关系分析的方法和系统，主要通过Ξ步 完成:第一，首先通过虚拟路由器采集路由协议发现网络设备，并对网络设备协议状态进行 实时监测和诊断分析，发生异常变化时产生告警;第二，对承载网络、信令网络和传输网络 进行跨专业告警关联分析;第Ξ，当网络设备发生故障时，对所述网络设备所在网络中与之 关联的网络设备进行资源分析定位，判断影响程度，并在拓扑界面中呈现影响结果状态信 息。
[000引已有技术方案3:专利号为CN103188716A的《RUDP链路故障定位方法及装置》专利， 设及无线通信领域，尤其设及一种抓DP(Reliable User化化gramProtocol，可靠用户数据 报协议)链路故障定位方法及装置。预先在RUDP报文的报文头中增加故障定位字段，源节点 向目的节点间发送数据时，将故障定位参数填充到RUDP报文的故障定位字段中，发送给传 输路径上的下一跳节点，当上述传输路径发生故障时，上述源节点根据预设策略确定故障 点;上述装置包括RUDP报文管理模块和故障确定模块。
[0009] 已有技术方案1采用一种电网设备状态自动评价平台，可根据多种试验信息及设 备运行情况，综合诊断设备绝缘情况，为故障定位及设备检修提供决策支持，能对电网设备 状态进行实时、高效和准确的评价。该方案并没有具体的介绍如何实现故障定位，只是为提 出一种网络分析方法，为故障定位提供了有力的支持。已有技术方案2公开了一种多网络关 联分析的方法和系统，为快速故障定位修复提供有力支撑，并能够全面准确地掌握对全网 的影响范围，有效提升客户感知，保障网络高稳定、高质量、高效率地运行。该方案实现起来 比较复杂，需要分析拳王的拓扑，虽然故障定位准确，但是代价高。已有技术方案3预先在 RUDP报文的报文头中增加故障定位字段，源节点向目的节点间发送数据时，将故障定位参 数填充到RUDP报文的故障定位字段中，发送给传输路径上的下一跳节点，当上述传输路径 发生故障时，上述源节点根据预设策略确定故障点减少了数据的发送量，减轻网络负荷，但 是需要改变发送数据的格式，且不能完成故障的实时监测与定位。
【发明内容】
[0010] 本发明的目的正是为了克服上述现有技术存在的缺陷而提供一种故障定位的探 测选择方法，本发明在故障定位阶段的探测选择要求选择一个新的探测，该探测将要使得 可疑节点集合中的节点数量尽量减少，运样选择的探测次数才会更少，同时提高判断故障 节点的正确率，能够带来更少的额外网络负担。
[0011] 本发明是通过如下技术方案来实现的：
[0012] -种故障定位的探测选择方法，本发明的特征在于，包括:确定故障检测的探测选 择集合和确定故障定位的探针选择集合。
[0013] 在该方法中，确定故障检测的探测选择集合的步骤为：
[0014] S1:初始化，设探测集合为空；
[0015] S2:选取被最少探测覆盖的节点Nj，即探测依赖矩阵中列向量的权值最小的列对 应的节点；
[0016] S3:从能覆盖到节点的的探测中选出覆盖最多节点的探测Ti，然后删除该探测所覆 盖的所有节点，即探测依赖矩阵中能覆盖节点的的行向量的权值最大的列，然后删除该列 覆盖的节点所对应的列；
[0017] S4:重复S2，S3，直到所有的节点被覆盖。
[0018] 确定故障定位的探针选择集合的步骤为：
[0019] S1 :若I化η I为空或者备用探测集合中不包含经历可疑节点的探测则退出，否则将 备用测试集合中所有经历化η的探测从备用测试集合中删除，然后转入S2;
[0020] S2:在备用探测集合选择经历化η中节点最少且至少为1个的探测Ti，然后转入S3; [002。 S3:若Ti探测结果返回成功，则将该探测中经历Nsn中节点从Nsn中删除并加入Nnn， 并转入S4;若Τι探测结果返回失败，将该探测加入Tft，若在结果返回失败且该探测中只有1 个可疑节点，则将该可疑节点从化η中删除并加入化η中，然后转入S1 ;
[00。] S4:历遍Tft，将其中满足有且只有一个可疑节点的探测中的可疑节点从Nsn中删除 并加入化η中，并转入S1。
[0023] 在确定故障检测的探测选择集合和确定故障定位的探针选择集合之间，还包括W 下步骤:确定减少可疑节点的方法;遍历所有探测选择集合;其中，确定减少可疑节点的方 法，包括：
[0024] 1)若只覆盖一个可疑节点的探测测试结果返回失败，则表明该可疑节点为故障节 占.
[0025] 2)若覆盖可疑节点的探测测试结果返回成功，则表明运些可疑节点为正常节点； 当把运些可疑节点从可疑节点集合删除，加入正常节点集合之后，之前测试集合中结果返 回失败且覆盖多个可疑节点的探测若现在只含有一个可疑节点，则需要对所有的然后失败 的探测集合重新进行情况1)的判定。
[0026] 遍历所有探测选择集合，包括：
[0027] 在历遍过程中若路径返回正常，则将该路径的所有节点加入Νηη，否则将节点加入 Νηη 或 IMsno
[0028] 首故障定位阶段的探测选择的建模也是探测依赖矩阵，和故障探测阶段的探测选 择不同的是，本阶段的探测选择是从备选探测集合(未被作为探测的探测集合，在故障检测 阶段表示除了故障检测集合W外的可用探测集合，在故障定位阶段表示除了故障检测集合 和之前故障定位探测W外的可用探测集合）里面选取满足使得可疑节点数尽量减少的探 测。所W本阶段的探测必须覆盖可疑节点。
[0029] 故障定位阶段的探测选择有两种基本思路：
[0030] -是MAX算法:每次选择一个经历化η中节点最多的探测。若运次探测成功，则将使 得Nsn中的节点减少很多，反之，不能减少Nsn的节点。注意经历Nsn中所有节点的探测除外，因 为该探测一定返回失败。
[0031] 二是MIN算法:每次选择经历化η中节点最少(至少为1个)的探测。若运次探测成功， 则将使得Nsn中的节点减少至少1个，若探测失败，且当且仅当它经历一个节点时，我们把该 节点从化η中删除并加入化η。
[0032] -般来说，考虑到网络中出现故障的节点总是少数的，相对来说即使经历化η中节 点较多的探测成功的可能性也高于失败的可能性，选择MAX算法会更好一些，但是由于我们 在探测站点的选择上只使用3个节点，会导致很多可疑节点是故障节点的后续节点，即运些 可疑节点会伴随着故障节点一起出现，导致经历化η中节点较多的探测失败的可能性大大增 加，所W选择ΜΙΝ算法。
[0033] 算法改进：[0034] 对图2中160节点网络在存在2个故障时的故障定位阶段ΜΙΝ算法的探测选择过程 分析，在经历第114条测试路径（即故障定位阶段的第一次探测)之后，实际上已经把所有故 障节点确定下来了，但是由于不知道故障节点个数导致下面每次探测都选择经历可疑节点 最少的节点，运导致了测试次数的增多，如果一下测试都选择MAX算法就可W减少测试次 数。基于W上的思考，结合MIN算法和MAX算法，提出了一种改进算法。
[0035] 改进算法除了基于MIN和MAX算法，还有基于W下考虑：
[0036] 1.对于一个网络，节点故障概率比较低，存在的故障节点比较少；
[0037] 2.将网络中的所有节点和探测返回结果建立成贝叶斯网络，所有节点为因，探测 返回结果为果。信息增益最高的可疑节点最有可能是故障节点。
[0038] 那么改进后的算法思路为：
[0039] 1.假设存在可疑节点的网络只有1个故障节点，先算出所有可疑节点的信息增益， 选择信息增益最高的可疑节点；
[0040] 2.寻找只含该节点一个可疑节点的备用探测集合去验证该节点是否为故障节点， 若不是，则说明该节点为正常节点，并从新进行选择剩余疑节点的信息增益最高的来验证 的循环，若是，则假设该网络已无故障，使用MAX算法对其余可疑节点验证；
[0041] 3.若选择的MAX算法的探测结果返回正确，则确定了较多的节点是正常节点，继续 进行MAX算法验证循环，若返回失败，则说明该网络还存在故障节点，假设故障节点个数为 1，从新从第1步验证其余可疑节点。
[0042] 4.直到所有可疑节点都被确定或者备用探测集合中不在含有经过可疑节点的探 测为止。
[0043] 本发明的技术关键点在于：
[0044] 1、从备选探测集合里面选取满足使得可疑节点数尽量减少的探测，建立探测依赖 矩阵；
[0045] 2、分别提出基于MIN的算法和基于MIN和MAX算法的改进算法，能够有效减少探测 次数。
[0046] 本发明的有益效果:本专利提出一种故障定位探测选择技术，其优点在于，该技术 立足于探测依赖矩阵表示，利用MIN算法实现故障定位，首先建立探测依赖矩阵，之后针对 该探测依赖矩阵，利用MIN算法一次删除节点，直到最后剩下一个节点。则故障定位完成。之 后对算法加 W改进，提出基于MIN和MAX算法的改进算法。仿真试验表明，本发明所提方案， 可W有效减少故障探测的次数，而判断的正确率也得到了很大的提高。
【附图说明】
[0047] 图1为本发明算法流程图；
[0048] 图2为160节点网络在存在2个故障时的故障定位阶段MIN算法的探测选择过程。
【具体实施方式】
[0049] 见图1，一种故障定位的探测选择方法，本发明的特征在于，包括:确定故障检测的 探测选择集合和确定故障定位的探针选择集合。
[0050] 在该方法中，确定故障检测的探测选择集合的步骤为：
[0051] S1:初始化，设探测集合为空；
[0化2] S2:选取被最少探测
[0053] 覆盖的节点Nj，即探测依赖矩阵中列向量的权值最小的列对应的节点；
[0054] S3:从能覆盖到节点Nj的探测中选出覆盖最多节点的探测Ti，然后删除该探测所覆 盖的所有节点，即探测依赖矩阵中能覆盖节点的的行向量的权值最大的列，然后删除该列 覆盖的节点所对应的列；
[0055] S4:重复S2，S3，直到所有的节点被覆盖。
[0056] 确定故障定位的探针选择集合的步骤为：
[0057] S1:若I化η I为空或者备用探测集合中不包含经历可疑节点的探测则退出，否则将 备用测试集合中所有经历化η的探测从备用测试集合中删除，然后转入S2;
[005引S2:在备用探测集合选择经历化η中节点最少且至少为1个的探测Ti，然后转入S3; [0化9] S3 :若Ti探测结果返回成功，则将该探测中经历化η中节点从化η中删除并加入Nnn， 并转入S4;若Τι探测结果返回失败，将该探测加入Tft，若在结果返回失败且该探测中只有1 个可疑节点，则将该可疑节点从化η中删除并加入化η中，然后转入S1 ;
[0060] S4:历遍Tft，将其中满足有且只有一个可疑节点的探测中的可疑节点从化η中删除 并加入化η中，并转入S1。
[0061] 在确定故障检测的探测选择集合和确定故障定位的探针选择集合之间，还包括W 下步骤:确定减少可疑节点的方法;遍历所有探测选择集合;其中，确定减少可疑节点的方 法，包括：
[0062] 1)若只覆盖一个可疑节点的探测测试结果返回失败，则表明该可疑节点为故障节 占.
[0063] 2)若覆盖可疑节点的探测测试结果返回成功，则表明运些可疑节点为正常节点； 当把运些可疑节点从可疑节点集合删除，加入正常节点集合之后，之前测试集合中结果返 回失败且覆盖多个可疑节点的探测若现在只含有一个可疑节点，则需要对所有的然后失败 的探测集合重新进行情况1)的判定。
[0064] 遍历所有探测选择集合，包括：
[0065] 在历遍过程中若路径返回正常，则将该路径的所有节点加入Νηη，否则将节点加入 Νηη 或 IMsno
[0066] 表1 MAX与MIN算法的探测选择结果
[0067]
[006引
[0069]由表1可知，MAX算法虽然有着与MIN算法相同的故障定位能力，但是MAX算法选择 的探测次数远远大于MIN算法，所WMIN算法更好。MIN算法能够使用更少的探测次数找出所 有的故障节点，确定故障节点的正确率也是100%。很明显，通过故障定位就能够把所有的 故障找到，即完成了故障诊断。
【主权项】
1. 一种故障定位的探测选择方法，其特征在于，包括:确定故障检测的探测选择集合和 确定故障定位的探针选择集合;其中， 确定故障检测的探测选择集合的步骤为： S1:初始化，设探测集合为空； S2:选取被最少探测覆盖的节点Nj，即探测依赖矩阵中列向量的权值最小的列对应的节 占. S3:从能覆盖到节点化的探测中选出覆盖最多节点的探测，然后删除该探测所覆盖的 所有节点，即探测依赖矩阵中能覆盖节点K的行向量的权值最大的列，然后删除该列覆盖 的节点所对应的列； S4:重复S2，S3，直到所有的节点被覆盖； 确定故障定位的探针选择集合的步骤为： S1:若|Nsn |为空或者备用探测集合中不包含经历可疑节点的探测则退出，否则将备用 测试集合中所有经历他"的探测从备用测试集合中删除，然后转入S2; S2:在备用探测集合选择经历Nsn中节点最少且至少为1个的探测1\，然后转入S3;S3:gT1探测结果返回成功，则将该探测中经历队"中节点从Nsn中删除并加入Nnn，并转入 SLgTi探测结果返回失败，将该探测加入Tft，若在结果返回失败且该探测中只有1个可疑 节点，则将该可疑节点从Nsn中删除并加入阶"中，然后转入S1; S4:历遍Tft，将其中满足有且只有一个可疑节点的探测中的可疑节点从Nsn中删除并加 入Nfn中，并转入S1。2. 根据权利要求1所述的一种故障定位的探测选择方法，其特征在于，在确定故障检测 的探测选择集合和确定故障定位的探针选择集合之间，还包括以下步骤： 确定减少可疑节点的方法； 遍历所有探测选择集合。3. 根据权利要求2所述的一种故障定位的探测选择方法，其特征在于，所述确定减少可 疑节点的方法，包括： 1) 若只覆盖一个可疑节点的探测测试结果返回失败，则表明该可疑节点为故障节点； 2) 若覆盖可疑节点的探测测试结果返回成功，则表明这些可疑节点为正常节点；当把 这些可疑节点从可疑节点集合删除，加入正常节点集合之后，之前测试集合中结果返回失 败且覆盖多个可疑节点的探测若现在只含有一个可疑节点，则需要对所有的然后失败的探 测集合重新进行情况1)的判定。4. 根据权利要求2所述的一种故障定位的探测选择方法，其特征在于，所述遍历所有探 测选择集合，包括： 在历遍过程中若路径返回正常，则将该路径的所有节点加入Nnn，否则将节点加入Nnn或 Nsn〇
【专利摘要】一种故障定位的探测选择方法，包括：确定故障检测的探测选择集合和确定故障定位的探针选择集合。本发明提出一种故障定位探测选择的技术方法，该技术立足于探测依赖矩阵表示，利用MIN算法实现故障定位，首先建立探测依赖矩阵，之后针对该探测依赖矩阵，利用MIN算法一次删除节点，直到最后剩下一个节点。则故障定位完成。之后对算法加以改进，提出基于MIN和MAX算法的改进算法。仿真试验表明，本发明所提方案，可以有效减少故障探测的次数，而判断的正确率也得到了很大的提高。
【IPC分类】G01R31/08
【公开号】CN105486976
【申请号】CN201510807970
【发明人】田丰, 刘宇明, 刘彤, 何林宏, 李辉, 苏进, 李晓耕, 李朝广, 韩熙媛
【申请人】云南电力调度控制中心
【公开日】2016年4月13日
【申请日】2015年11月19日
最新回复(0)