基于逻辑方程求解的网络故障定位规则的验证与实现

刘玉娜，李海涛

(山东师范大学数学与统计学院，山东济南 250014)

1 引言

互联网网络是经济发展，社交生活等领域的重要支撑工具，是信息社会的基础.随着当今信息技术的快速发展，人们对网络服务质量的要求越来越高.由于物理损坏、黑客攻击、带宽限制等因素的影响，互联网网络路段上经常发生一些故障，为提高网络服务的质量，精确定位故障发生的路段十分重要[1].随着一些实时程序的广泛应用以及网络直播的流行，精确定位故障的发生位置以便网络服务供应商及时采取相应的措施就显得十分必要.

对于故障定位的研究，很多学者提出了不同的方法.文献[2]提出了一种通过从多个源到多个目的地测量适当路径上的端到端数据包丢失率定位拥塞段的实用方法.基于断层扫描的叠加监测系统，文献[3]通过监测路径基础集的数据包损失率来推断所有端到端路径的数据包的损失率，从而根据已有的阈值确定发生故障的路径.当网络拓扑结构为有向树时，最小一致故障集原则[4]将最接近根节点的链接指定为与观察到的坏路径模式一致的链接.基于聚类技术的网络断层摄影方法，文献[5]提出了一种通过沿多个路径的周期性端到端分组延迟测量在因特网上定位拥塞段的实用方法，有效地解决了延迟变化之间的相关性.

近年来，程代展教授提出了一种新的矩阵乘法，矩阵半张量积[6-12].它突破了传统矩阵乘法对矩阵维数的限制，同时保持了普通矩阵乘法的性质.矩阵半张量积的一个重要应用是它可以将逻辑表达式转化为等价的代数形式，从而方便人们使用矩阵来研究逻辑运算过程.矩阵半张量积已经被成功地应用到有限自动机[13-14]、Petri网[15-16]、布尔网络[17-22]、博弈论[23-24]、移位寄存器[25-26]、模糊控制[27-28]等领域.矩阵半张量积也被应用于电路和网络的故障诊断[6-8].文献[6]中研究了布尔导数的计算方法并应用到组合电路的故障检测，所给出的检测方法可以有效检测两个以上的故障.文献[7]通过分析布尔控制网络的输入输出轨迹的完备性和T完备性给出了检测有意义故障的算法.文献[8]使用矩阵半张量积工具通过求解逻辑方程确定有可能发生故障的链接.

本文研究互联网网络中的故障定位问题.利用矩阵半张量积方法给出网络中路径的代数表示.基于该代数表示，将故障定位问题对应的逻辑方程转化为等价的代数方程.通过分析代数方程的解，确定网络中发生故障的链接.使用矩阵半张量积方法与文献[2-5]相较而言可以更大限度地确定发生故障的链接，只涉及矩阵运算便于使用MATLAB数学软件检验.

下面列出本文中用到的符号:Mm×n表示m×n维实矩阵所组成的集合;N+表示正整数集合;Colj(A)表示矩阵A的第j列;其中In是单位矩阵;若矩阵M∈Mm×n满足Col(M)⊆Δm，则称矩阵M为逻辑矩阵，并且Lm×n表示m×n维逻辑矩阵.

2 预备知识

本文使用的主要工具为矩阵半张量积，这里只介绍本文将会用到的矩阵半张量积的预备知识，关于矩阵半张量积的详细知识请参照文献[8].

定义1对于给定的两个矩阵A∈Mm×n和B∈Mp×q，矩阵A，B 的半张量积记为AB，定义为

其中:t=lcm(n，p)表示n和p的最小公倍数，⊗表示矩阵的Kronecker积.

注1当n=p时矩阵半张量积即为普通矩阵乘法.本文中，在不引起混淆的情况下省略符号“”.

下面给出换位矩阵的定义.

定义2换位矩阵W[m，n]为mn×mn维矩阵，表示为

换位矩阵的主要作用是交换两个列向量的位置.

引理1设X∈Rm，Y∈Rn，则

引理2设Φk=为k维降阶矩阵，若x∈Δk，则x2=Φkx.

下面给出网络中链接、节点、路径的相关定义.

定义3一个网络由节点集N和链接集L组成，其中节点集为N={A，B，C，·}，链接集为L={a，b，c，·}，则一个网络可以表示为一个对(N，L).

定义4在网络中，路径指从起点到终点的全程路由，即路径为从起点到终点经过所有链接的组合.

定义5没有自相交的路径称为合法路径，否则称为非合法路径.

注2一个路径有两个端点，如果路径r在节点A和B之间，记为r=r(A，B).

注3一个链接若可通过则称为“好”～1，向量形式为若不能通过则称为“坏”～0，向量形式为

注4在计算路径的逻辑结构矩阵时只计算合法路径.

一个路径由许多链接组成，下面将链接作为参数给出路径的代数形式.

如图1所示，链接a和b并联，则路径r(A，B)=a ∨b，它的代数形式为r(A，B)=M∨ab，其中M∨=δ2[1 1 1 2].

图1 并联结构Fig.1 Parallel structure

如图2所示，链接a和b串联，则路径r(A，B)=a ∧b，它的代数形式为r(A，B)=M∧ab，其中M∧=δ2[1 2 2 2].

图2 串联结构Fig.2 Serial structure

如图3所示，链接a 和b 先并联再和c 串联，则路径r(A，C)=(a ∨b)∧c，它的代数形式为r(A，C)=M∧M∨abc=δ2[1 2 1 2 1 2 2 2]abc.

图3 串并联结构Fig.3 Serial-parallel structure

如图4所示，链接a，b，c，d，e的并联和串联结构复杂，容易看出从A 到D 有4 条路径，分别为:a-d，b-e，a-c-e，b-c-d，则路径r(A，D)=(a ∧d)∨(b ∧e)∨(a ∧c ∧e)∨(b ∧c ∧d)，它的代数形式为

图4 复合结构Fig.4 Composite structure

3 主要结果

3.1 一般树形网络

关于在矩阵半张量积框架下将逻辑方程转化为等价的代数方程，通过分析代数方程的解来定位网络中故障链接的详细内容请参照文献[8].本节主要讨论树形网络中故障链接的定位.为了更精确地确定发生故障的链接位置，沿用以下假设:很多场合下，故障并不是经常发生，故障发生的概率很低，即假设1[8].

假设1最有可能发生故障的情况为具有最少数量“坏”的链接的路径.

对于一般情况的树形网络，即从单个源点到多个目的地的树状拓扑，本文讨论最小一致故障集原则[4].

下面给出树形网络及子节点和父节点的定义.

定义6树形网络T=(V，L)中，V 为节点集，L为链接集.对T中的链接，通常将在节点k处终止的链接称为链接k.根节点为{0}，记V{0}=U.

定义7对于树形网络中的节点i，k，若k=f(i)，则k为i的父节点.若i是k的一个后代，则k=fm(i)(m∈N+).

注5与f类似，若k=φ(i)，称k为i的子节点.

定义8若某个节点i的测试结果为“好”，则从根节点到节点i的路径完全由“好”的链接组成.

定义9若某个节点i的测试结果为“坏”，但其父节点f(i)为“好”，称以i为根的子树为最大坏子树.

一般的树形网络中，定位故障链接主要基于最小一致故障集原则[4]:若某个节点i的测试结果为“坏”，当它没有子链接且父节点属性“好”时，故障链接为链接i;当它有子链接或者父节点为“坏”时，故障链接为该节点的最大坏子树的根链接.

如图5 所示为一个树形网络.已知节点a 处为“坏”，由定义9知，最大坏子树为L9和L10，由最小一致故障集原则得L6发生故障.下面使用矩阵半张量积方法说明最小一致故障集原则的有效性，路径的逻辑形式为

等价的代数方程为ra=M1L，其中:

由ra=易知代数方程的解为，对应的布尔表示分别为

由于假设1，故障发生对应的解为[1 1 0 1 1]，即L6发生故障，结果与最小一致故障集原则相同.

图5 树形网络图Fig.5 Tree network

同样地，对于节点b为“坏”的情形，计算可得L8为故障链接，结果如图6所示.

图6 图5中故障链接已确定的树形网络图Fig.6 Tree network with the fault link identified in Fig.5

下面讨论任意层树形网络情况下的最小一致故障集原则.

首先对该网络中的所有链接进行编号，以便于计算.设树形网络有n层，第k(k≤n)层从左至右共有nk个节点，相应的每层共有nk个链接，将每一层的节点从左至右编号为k1，k2，…，则它们分别对应的父节点为f(k1)，f(k2)，…，

对于树形网络第k层第m个节点即第km个节点，对应的父节点为f(km)，依次类推，可得到节点km所有的父节点:f(km)，f2(km)，…，fk-1(km).不失一般性，假设节点km对应的当前路径中参与到的所有子链接数量为n-k，分别记为Lφ(k+1)，Lφ(k+2)，…，Lφ(n).经计算，对应的代数方程为r=ML，其中:

链接km为“坏”，故代数方程r=ML的解为对应的布尔表示分别为由于假设1，可以确定故障发生所即链接km为故障链接.

由此得到以下结论:

定理1在任意层树形网络中，定位故障链接的最小一致故障集原则是有效的.对应的布尔表示为

注6从以上的推导过程可以看出，在任意层的树形网络中，将路径的逻辑形式转化为代数方程，通过求解代数方程并分析代数方程的解来确定故障链接是有效的.

3.2 汇集树网络

本部分把一般树形网络扩展到汇集树(sink tree)和汇集树组合的网络中，即从多个源点到多个目的地的树状拓扑网络.对于文献[2]中提出的通过从多个源到多个目的地测量适当路径上的端到端数据包丢失率定位拥塞段方法，同样地用矩阵半张量积进行说明.

如图7所示，链接L1，L2，L3，两个路径P1，P2分别从o1至d3，o2至d3，故障发生时判断故障链接基于以下两个规则:

规则1若路径Pi为“好”的同时Pj(i，j=1，2，i/=j)为“坏”，则当链接Li和L3为“好”时，Lj为“坏”(i，j=1，2，i/=j);

规则2若路径P1，P2同时为“坏”，则链接L3比L1，L2更容易“坏”.

图7 一个简单的路径拓扑Fig.7 A simple path topology

逻辑方程为r=P1∨P2，其中P1=L1∧L3，P2=L2∧L3，则

对应的代数方程为r=ML=δ2[1 2 1 2 1 2 2 2]·L1L2L3.

规则1中，Pi为“好”但同时Pj(i，j=1，2，i/=j)为“坏”，则r为“好”，即r=所以代数方程r=ML的解为对应的布尔表示分别为[1 1 1]，[1 0 1]，[0 1 1].由于假设1，可以确定故障发生对应的布尔表示为[1 0 1]，[0 1 1]，即当Li和L3为“好”时，Lj为坏(i，j=1，2，i/=j)，说明规则1的正确性.

规则2中，若P1，P2同时为“坏”，则r为“坏”，即r=所以代数方程r=ML的解为对应的布尔表示分别为[1 1 0]，[1 0 0]，[0 1 0]，[0 0 1]，[0 0 0].由于假设1，可以确定故障发生对应的布尔表示为[1 1 0]，即L3为故障链接，说明规则2的正确性.

注7以上两个规则适用于具有任意层的汇集树网络.

定理2在汇集树网络中，定位故障链接的两个规则是有效的.

下面通过例1说明矩阵半张量积方法相较于文献[2]的优越性.

例1如图8所示的网络图，L1，L2，L3为链接，P1，P2，P3表示3条路径.

图8 例1中的网络Fig.8 Network in Example 1

首先给出该网络的代数形式:

故该网络的代数方程为r=ML，其中M=δ8[1 4 3 4 7 8 7 8]，L=L1L2L3.

i) 当P1“好”，P2“坏”，P3“好”时，r==代数方程r=ML的解为L=对应的布尔表示为[1 0 1]，则故障链接为L2.

ii) 当P1“好”，P2“坏”，P3“坏”时，r==代数方程r=ML的解为L=对应的布尔表示分别为[1 1 0]和[1 0 0].由于假设1，可以确定故障发生对应的布尔表示为[1 1 0]，则L3为故障链接.

iii) 当P1“坏”，P2“坏”，P3“好”时，代数方程r=ML的解为对应的布尔表示分别为[0 1 1]和[0 0 1].由于假设1，可以确定故障发生对应的布尔表示为[0 1 1]，则故障链接为L1.

iv) 当P1“坏”，P2“坏”，P3“坏”时，代数方程r=ML的解为对应的布尔表示分别为[0 1 0]和[0 0 0].由于假设1，可以确定故障发生对应的布尔表示为[0 1 0]，则故障链接为L1，L3.

下面给出使用前文规则1与规则2和使用矩阵半张量积方法的比较，如表1和表2所示，其中:“√”表示“好”，“×”表示“坏”，“?”表示无法确定该链接是否发生故障.通过表1与表2的比较，可以清晰地看出，由于故障并不是经常发生，使用矩阵半张量积方法可以最大限度精确地确定发生故障的链接.

表1 使用规则1和规则2判断故障链接[2]Table 1 Use rule 1 and rule 2 to determine faulty links[2]

表2 使用矩阵半张量积方法判断故障链接Table 2 Use semi-tensor product of matrices method to determine faulty links

注8最小一致故障集原则和规则1与规则2的分析推导过程中，通过将逻辑方程转化为对应的代数方程并分析代数方程的解，可以确定一般的树形网络和汇集树网络中发生故障的链接，所使用的矩阵半张量积方法不仅便于计算，而且确定发生故障的链接更精确.

3.3 一般网络

使用矩阵半张量积方法可以定位一般网络中的故障链接.下面用一个例子来进行说明.

如图9所示为一个局域网，A-G表示路由器接口，a-h表示路径，根据数据包丢失率检测并与阈值比较知，E，F，G的状态分别为“好”、“坏”、“坏”，下面用矩阵半张量积方法确定发生故障的位置.

图9 一个简单的局域网络Fig.9 A simple local network

首先给出该局域网的代数形式:

由假设1，故障发生对应的解为[1 1 1 1 1 1 0 0]，即链接g和h发生故障.

因此，矩阵半张量积方法不仅可以在一般的树形网络和汇集树网络中定位故障链接，在一般的网络中也同样适用.

4 结论

本文研究了互联网网络中故障位置定位问题.基于矩阵的半张量积理论，给出了网络中路径的代数表示.基于该代数表示，通过将故障定位问题对应的逻辑方程转化为等价的代数方程，通过分析代数方程的解，给出了一般树形网络和汇集树网络拓扑结构中确定发生故障的链接.通过数值算例比较发现，本文所提出的矩阵半张量积方法比原有方法更精确.此外，本文还将所得的理论结果在一般网络中进行说明，充分展示了利用矩阵半张量积求解逻辑方程定位故障位置的有效性.未来的工作将考虑如何使用矩阵半张量积方法研究随机因素影响下网络故障定位问题，给出更易检验的方法.