基于链路特征的电力通信网探测选择算法

苟晓军，罗顺辉，肖 良

(国网信通亿力科技有限责任公司北京分公司，北京 100000)

0 引言

随着5G网络在各行各业中应用的快速增长，核心网承载的业务类型和规模快速增长。为了保证5G业务的稳定运行，必须对核心网的性能进行实时监测。主动网络探测技术是网络性能检测的一种关键技术[1]。需要向网络中发送探测，并通过探测结果推断网络的性能。所以，如何通过尽可能少的探测掌握网络的性能，已成为一个关键的研究问题。已有研究主要包括：探测数据报文的收集和分析，最优化探测选择。为了实现探测数据报文的收集和分析，Handigol等[2]采用在交换机上部署探测报文流表分析技术，实现了探测报文所经过路径的快速分析，为探测站点选择提供了基础数据支持。Dai等[3]以SDN环境下的探测选择为研究目标，采取FPGA协议对研究问题进行建模和分析，不但能够对单条探测进行分析，而且可对并发探测路径的探测效果进行有效分析。为了选择最优化的探测，Ali等[4]为解决光网络中部署探测的问题，分析了单链路故障和多链路故障两种情况下的探测选择问题，并采用预测技术提出了探测选择算法。Jeswani等[5]以解决网络动态环境下的探测站点选择问题为目标，采用周期性的探测站点选择算法，实现了主动获取网络特征的功能。在具体的探测站点优化研究方面，智能算法[6]、模糊分析理论[7]、专家系统[8]等理论也被成功应用到已有研究中，并取得了较好的结果。

在探测数据包分析、探测站点优化方面，已经取得较好的研究成果。但是，在探测选择时，对探测之间的关联性分析研究较少，导致探测中出现重复探测现象，给网络正常运行带来了负面影响。本研究基于网络拓扑与探测的关联关系，构建了探测与节点的贝叶斯模型。创建探测矩阵并基于高斯约旦消元法将探测矩阵化简为最简行阶梯探测矩阵，提出了基于链路特征的电力通信网探测选择算法，该算法包括：基于链路覆盖关系求解初始探测集合、构建探测矩阵并化简、基于节点覆盖的探测数量选择最优探测节点。

1 模型

1.1 网络拓扑G

网络拓扑G是由网络节点和网络链路构成的无向图。网络节点被网络链路连接起来。X={X1，X2，…，Xi}表示节点集合。使用L={L1，L2，…，Lj}表示链路集合。两个网络节点之间是否有网络链路，由实际网络运营商的网络情况决定。20个节点的网络拓扑如图1所示。

图1 20个节点的网络拓扑举例

1.2 探测

探测是指从探针节点发送数据包到指定节点所经过的节点和链路。使用T={T1，T2，…，Tm}表示由m个探测构成的探测集合。例如，探测1表示为11→12→2→4→6→18。

1.3 探测与节点的贝叶斯模型

为了将探测与网络关联，建立探测与节点的贝叶斯模型，包括上下两层(见图2)。上层为网络节点，下层为探测。上下层之间的有向连线表示探测经过的节点。网络节点和探测都是二进制取值。当取值为1时，表示网络节点和探测都不正常。当取值为0时，表示网络节点和探测都正常。当探测正常时，表示当前探测经过的所有节点都正常。否则，表示至少有一个节点不正常。

图2 探测与节点关系的贝叶斯模型

2 链路特征

为了选择最少的探测，覆盖所有的网络节点，从而快速了解网络性能，下面首先介绍本研究提出的链路覆盖关系概念，其次给出探测矩阵及化简方法。

2.1 链路覆盖关系

探测的主要用途是覆盖所有网络节点。一般来说，探测选择算法对执行时间都比较敏感。通过分析节点和链路的关系可知，如果想让探测覆盖节点，只要探测能够覆盖经过该节点的链路，就可以实现覆盖当前节点的目标。所以，本研究从覆盖链路的角度出发，进行节点覆盖，基于链路覆盖关系，可以有效缩短链路选择花费的时间。

对于任意两点s、d间的路径Ps，d，其包含的链路数量使用Us，d表示，则Us，d=|Ps，d|。使用最短路径算法Dijkstra可以获得任意两个网络节点之间的最短路径。所以，将两点s、d作为探针，采用最短路径算法Dijkstra获得的路径发送探测，就可以对两点s、d间的链路进行覆盖。任意两点间最短路径最长的探测，其覆盖的链路数量最多，该探测的价值越大。所以，在选择探测时，首先，对所有节点中的任意两个节点采用最短路径算法Dijkstra，获得包含的链路数量。其次，按照链路数量降序排列，并逐个选择链路数量最多的两个节点的两端节点作为探针，将其覆盖的链路标记为已探测，直到所有链路已经覆盖。此种方法选择的探测数量将快速减少。

2.2 探测矩阵及化简

基于探测与节点的贝叶斯模型，创建探测矩阵，该矩阵为二维坐标，且矩阵的元素值为二进制0或1。其中，行向量表示每个探测及经过的节点，当探测经过某个节点，该元素为1，否则为0。列向量表示每个节点包含在哪些探测中，如当前节点包含在某个探测中，该元素为1，否则为0。例如，包含6个探测、7个节点的探测矩阵A如公式(1)所示。

(1)

从矩阵的线性变换关系可知，探测矩阵的一些行可以通过其他行进行表示。这种关系对应到探测矩阵的物理意义为：一些探测可以使用其他探测进行代替。所以，如果能找到这些探测之间的代替关系，就可以减少探测的数量。高斯约旦消元法可以通过线性变换，将探测矩阵化简为最简行阶梯探测矩阵，从而减少探测的数量。在使用高斯约旦消元法时，由于线性变换会导致矩阵元素变为负值，此种情况会导致探测不可用，所以，当某步骤导致矩阵元素出现负值时，高斯约旦消元法不执行此步骤。例如，矩阵A通过变换，可以得到矩阵B。此时，矩阵中的每一行表示一个独立的探测，探测之间没有关联关系，从而大大减少了探测的数量和探测的复杂度。

3 基于链路特征的电力通信网探测选择算法

本研究提出的基于链路特征的电力通信网探测选择算法(Probe selection algorithm of power communication network based on link characteristics，PSA-LC)如表1所示，该算法包括基于链路覆盖关系求解初始探测集合、构建探测矩阵并化简、基于节点覆盖的探测数量选择最优探测节点。

表1 基于链路特征的电力通信网探测选择算法

4 性能分析

实验中的网络拓扑环境使用BRITE[9]工具生成。考虑到网络节点的度数对探测数量影响较大，在生成网络拓扑时，生成了网络节点度数平均值为3和6的两种网络拓扑。为验证本研究提出算法PSA-LC的性能，将本研究算法与随机选择探测站点算法PSA-RD(Probe selection algorithm based on RanDom)进行了比较。其中，算法PSA-RD是根据网络规模限制条件随机从网络节点中选择探测节点，直到覆盖所有节点。在性能分析指标方面，使用探测站点数量和选择探测站点时长作为评价指标。

两种算法的探测站点数量比较结果如图3—4所示，X轴表示网络节点的数量从100个增加到600个，Y轴表示探测站点的数量。从图3—4可知，随着网络节点数量增加，两种算法的探测站点数量都在快速增加。这是因为网络规模增加，需要覆盖全部网络节点和网络链路，需要更多的探测站点。对图3和图4进行比较可知，图3中两种算法选择的探测站点数量都高于图4中选择的探测站点数量。这是因为图4中网络拓扑的平均度数加大，从而使网络链路增加，每个探测所经过的网络节点和网络链路数量增加，所以探测站点的数量都会减少。从两种算法的探测站点数量比较结果可知，两种网络拓扑下，本研究算法PSA-LC的探测站点数量比算法PSA-RD的探测站点数量少，这是因为本研究算法通过链路的覆盖关系，能够找到比较优化的探测，从而减少重复探测。

图4 平均度数为6的网络拓扑的探测站点数量比较

两种算法的探测选择时长比较结果如图5—6所示，X轴表示网络节点的数量从100个增加到600个，Y轴表示探测选择时长。可知，随着网络节点数量增加，两种算法的探测选择时长都在快速增加。这是因为网络规模增加，需要覆盖全部网络节点和网络链路，需要更多的探测选择过程。对图5—6进行比较可知，图5中两种算法的探测选择时长都低于图6中探测选择时长，因为图6中网络拓扑的平均度数加大，从而使网络链路增加，为覆盖更多的网络链路，两个算法的探测选择时长都会增加。两种网络拓扑下，本研究算法PSA-LC的探测选择时长比算法PSA-RD的探测选择时长要大。这是因为本研究算法PSA-LC需要对探测之间的关系进行分析，导致探测选择的时间较长。随着服务器性能和云计算技术的提升，可以通过部署高性能计算环境，解决此问题。

图5 平均度数为3的网络拓扑的探测选择时长比较

图6 平均度数为6的网络拓扑的探测选择时长比较

5 结语

主动网络探测技术通过向网络中发送探测，并通过探测结果推断网络性能，对网络性能进行实时监测、保证网络业务的稳定运行起到非常重要的作用。基于链路覆盖关系降低了链路选择花费的时长，构建了探测与节点的贝叶斯模型。提出了基于链路特征的电力通信网探测选择算法，并且从探测站点数量和选择探测站点时长两个方面验证了算法性能。在网络设备发生故障时，快速准确地定位故障是保证网络业务可靠性的关键技术。下一步工作中，将基于文章的探测站点选择成果，对网络故障定位问题进行深入研究。