劉玉娜，李海濤

(山東師范大學數(shù)學與統(tǒng)計學院，山東濟南 250014)

1 引言

互聯(lián)網(wǎng)網(wǎng)絡是經(jīng)濟發(fā)展，社交生活等領域的重要支撐工具，是信息社會的基礎.隨著當今信息技術(shù)的快速發(fā)展，人們對網(wǎng)絡服務質(zhì)量的要求越來越高.由于物理損壞、黑客攻擊、帶寬限制等因素的影響，互聯(lián)網(wǎng)網(wǎng)絡路段上經(jīng)常發(fā)生一些故障，為提高網(wǎng)絡服務的質(zhì)量，精確定位故障發(fā)生的路段十分重要[1].隨著一些實時程序的廣泛應用以及網(wǎng)絡直播的流行，精確定位故障的發(fā)生位置以便網(wǎng)絡服務供應商及時采取相應的措施就顯得十分必要.

對于故障定位的研究，很多學者提出了不同的方法.文獻[2]提出了一種通過從多個源到多個目的地測量適當路徑上的端到端數(shù)據(jù)包丟失率定位擁塞段的實用方法.基于斷層掃描的疊加監(jiān)測系統(tǒng)，文獻[3]通過監(jiān)測路徑基礎集的數(shù)據(jù)包損失率來推斷所有端到端路徑的數(shù)據(jù)包的損失率，從而根據(jù)已有的閾值確定發(fā)生故障的路徑.當網(wǎng)絡拓撲結(jié)構(gòu)為有向樹時，最小一致故障集原則[4]將最接近根節(jié)點的鏈接指定為與觀察到的壞路徑模式一致的鏈接.基于聚類技術(shù)的網(wǎng)絡斷層攝影方法，文獻[5]提出了一種通過沿多個路徑的周期性端到端分組延遲測量在因特網(wǎng)上定位擁塞段的實用方法，有效地解決了延遲變化之間的相關(guān)性.

近年來，程代展教授提出了一種新的矩陣乘法，矩陣半張量積[6-12].它突破了傳統(tǒng)矩陣乘法對矩陣維數(shù)的限制，同時保持了普通矩陣乘法的性質(zhì).矩陣半張量積的一個重要應用是它可以將邏輯表達式轉(zhuǎn)化為等價的代數(shù)形式，從而方便人們使用矩陣來研究邏輯運算過程.矩陣半張量積已經(jīng)被成功地應用到有限自動機[13-14]、Petri網(wǎng)[15-16]、布爾網(wǎng)絡[17-22]、博弈論[23-24]、移位寄存器[25-26]、模糊控制[27-28]等領域.矩陣半張量積也被應用于電路和網(wǎng)絡的故障診斷[6-8].文獻[6]中研究了布爾導數(shù)的計算方法并應用到組合電路的故障檢測，所給出的檢測方法可以有效檢測兩個以上的故障.文獻[7]通過分析布爾控制網(wǎng)絡的輸入輸出軌跡的完備性和T完備性給出了檢測有意義故障的算法.文獻[8]使用矩陣半張量積工具通過求解邏輯方程確定有可能發(fā)生故障的鏈接.

本文研究互聯(lián)網(wǎng)網(wǎng)絡中的故障定位問題.利用矩陣半張量積方法給出網(wǎng)絡中路徑的代數(shù)表示.基于該代數(shù)表示，將故障定位問題對應的邏輯方程轉(zhuǎn)化為等價的代數(shù)方程.通過分析代數(shù)方程的解，確定網(wǎng)絡中發(fā)生故障的鏈接.使用矩陣半張量積方法與文獻[2-5]相較而言可以更大限度地確定發(fā)生故障的鏈接，只涉及矩陣運算便于使用MATLAB數(shù)學軟件檢驗.

下面列出本文中用到的符號:Mm×n表示m×n維實矩陣所組成的集合;N+表示正整數(shù)集合;Colj(A)表示矩陣A的第j列;其中In是單位矩陣;若矩陣M∈Mm×n滿足Col(M)?Δm，則稱矩陣M為邏輯矩陣，并且Lm×n表示m×n維邏輯矩陣.

2 預備知識

本文使用的主要工具為矩陣半張量積，這里只介紹本文將會用到的矩陣半張量積的預備知識，關(guān)于矩陣半張量積的詳細知識請參照文獻[8].

定義1對于給定的兩個矩陣A∈Mm×n和B∈Mp×q，矩陣A，B 的半張量積記為AB，定義為

其中:t=lcm(n，p)表示n和p的最小公倍數(shù)，?表示矩陣的Kronecker積.

注1當n=p時矩陣半張量積即為普通矩陣乘法.本文中，在不引起混淆的情況下省略符號“”.

下面給出換位矩陣的定義.

定義2換位矩陣W[m，n]為mn×mn維矩陣，表示為

換位矩陣的主要作用是交換兩個列向量的位置.

引理1設X∈Rm，Y∈Rn，則

引理2設Φk=為k維降階矩陣，若x∈Δk，則x2=Φkx.

下面給出網(wǎng)絡中鏈接、節(jié)點、路徑的相關(guān)定義.

定義3一個網(wǎng)絡由節(jié)點集N和鏈接集L組成，其中節(jié)點集為N={A，B，C，·}，鏈接集為L={a，b，c，·}，則一個網(wǎng)絡可以表示為一個對(N，L).

定義4在網(wǎng)絡中，路徑指從起點到終點的全程路由，即路徑為從起點到終點經(jīng)過所有鏈接的組合.

定義5沒有自相交的路徑稱為合法路徑，否則稱為非合法路徑.

注2一個路徑有兩個端點，如果路徑r在節(jié)點A和B之間，記為r=r(A，B).

注3一個鏈接若可通過則稱為“好”～1，向量形式為若不能通過則稱為“壞”～0，向量形式為

注4在計算路徑的邏輯結(jié)構(gòu)矩陣時只計算合法路徑.

一個路徑由許多鏈接組成，下面將鏈接作為參數(shù)給出路徑的代數(shù)形式.

如圖1所示，鏈接a和b并聯(lián)，則路徑r(A，B)=a ∨b，它的代數(shù)形式為r(A，B)=M∨ab，其中M∨=δ2[1 1 1 2].

圖1 并聯(lián)結(jié)構(gòu)Fig.1 Parallel structure

如圖2所示，鏈接a和b串聯(lián)，則路徑r(A，B)=a ∧b，它的代數(shù)形式為r(A，B)=M∧ab，其中M∧=δ2[1 2 2 2].

圖2 串聯(lián)結(jié)構(gòu)Fig.2 Serial structure

如圖3所示，鏈接a 和b 先并聯(lián)再和c 串聯(lián)，則路徑r(A，C)=(a ∨b)∧c，它的代數(shù)形式為r(A，C)=M∧M∨abc=δ2[1 2 1 2 1 2 2 2]abc.

圖3 串并聯(lián)結(jié)構(gòu)Fig.3 Serial-parallel structure

如圖4所示，鏈接a，b，c，d，e的并聯(lián)和串聯(lián)結(jié)構(gòu)復雜，容易看出從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)，它的代數(shù)形式為

圖4 復合結(jié)構(gòu)Fig.4 Composite structure

3 主要結(jié)果

3.1 一般樹形網(wǎng)絡

關(guān)于在矩陣半張量積框架下將邏輯方程轉(zhuǎn)化為等價的代數(shù)方程，通過分析代數(shù)方程的解來定位網(wǎng)絡中故障鏈接的詳細內(nèi)容請參照文獻[8].本節(jié)主要討論樹形網(wǎng)絡中故障鏈接的定位.為了更精確地確定發(fā)生故障的鏈接位置，沿用以下假設:很多場合下，故障并不是經(jīng)常發(fā)生，故障發(fā)生的概率很低，即假設1[8].

假設1最有可能發(fā)生故障的情況為具有最少數(shù)量“壞”的鏈接的路徑.

對于一般情況的樹形網(wǎng)絡，即從單個源點到多個目的地的樹狀拓撲，本文討論最小一致故障集原則[4].

下面給出樹形網(wǎng)絡及子節(jié)點和父節(jié)點的定義.

定義6樹形網(wǎng)絡T=(V，L)中，V 為節(jié)點集，L為鏈接集.對T中的鏈接，通常將在節(jié)點k處終止的鏈接稱為鏈接k.根節(jié)點為{0}，記V{0}=U.

定義7對于樹形網(wǎng)絡中的節(jié)點i，k，若k=f(i)，則k為i的父節(jié)點.若i是k的一個后代，則k=fm(i)(m∈N+).

注5與f類似，若k=φ(i)，稱k為i的子節(jié)點.

定義8若某個節(jié)點i的測試結(jié)果為“好”，則從根節(jié)點到節(jié)點i的路徑完全由“好”的鏈接組成.

定義9若某個節(jié)點i的測試結(jié)果為“壞”，但其父節(jié)點f(i)為“好”，稱以i為根的子樹為最大壞子樹.

一般的樹形網(wǎng)絡中，定位故障鏈接主要基于最小一致故障集原則[4]:若某個節(jié)點i的測試結(jié)果為“壞”，當它沒有子鏈接且父節(jié)點屬性“好”時，故障鏈接為鏈接i;當它有子鏈接或者父節(jié)點為“壞”時，故障鏈接為該節(jié)點的最大壞子樹的根鏈接.

如圖5 所示為一個樹形網(wǎng)絡.已知節(jié)點a 處為“壞”，由定義9知，最大壞子樹為L9和L10，由最小一致故障集原則得L6發(fā)生故障.下面使用矩陣半張量積方法說明最小一致故障集原則的有效性，路徑的邏輯形式為

等價的代數(shù)方程為ra=M1L，其中:

由ra=易知代數(shù)方程的解為，對應的布爾表示分別為

由于假設1，故障發(fā)生對應的解為[1 1 0 1 1]，即L6發(fā)生故障，結(jié)果與最小一致故障集原則相同.

圖5 樹形網(wǎng)絡圖Fig.5 Tree network

同樣地，對于節(jié)點b為“壞”的情形，計算可得L8為故障鏈接，結(jié)果如圖6所示.

圖6 圖5中故障鏈接已確定的樹形網(wǎng)絡圖Fig.6 Tree network with the fault link identified in Fig.5

下面討論任意層樹形網(wǎng)絡情況下的最小一致故障集原則.

首先對該網(wǎng)絡中的所有鏈接進行編號，以便于計算.設樹形網(wǎng)絡有n層，第k(k≤n)層從左至右共有nk個節(jié)點，相應的每層共有nk個鏈接，將每一層的節(jié)點從左至右編號為k1，k2，…，則它們分別對應的父節(jié)點為f(k1)，f(k2)，…，

對于樹形網(wǎng)絡第k層第m個節(jié)點即第km個節(jié)點，對應的父節(jié)點為f(km)，依次類推，可得到節(jié)點km所有的父節(jié)點:f(km)，f2(km)，…，fk-1(km).不失一般性，假設節(jié)點km對應的當前路徑中參與到的所有子鏈接數(shù)量為n-k，分別記為Lφ(k+1)，Lφ(k+2)，…，Lφ(n).經(jīng)計算，對應的代數(shù)方程為r=ML，其中:

鏈接km為“壞”，故代數(shù)方程r=ML的解為對應的布爾表示分別為由于假設1，可以確定故障發(fā)生所即鏈接km為故障鏈接.

由此得到以下結(jié)論:

定理1在任意層樹形網(wǎng)絡中，定位故障鏈接的最小一致故障集原則是有效的.對應的布爾表示為

注6從以上的推導過程可以看出，在任意層的樹形網(wǎng)絡中，將路徑的邏輯形式轉(zhuǎn)化為代數(shù)方程，通過求解代數(shù)方程并分析代數(shù)方程的解來確定故障鏈接是有效的.

3.2 匯集樹網(wǎng)絡

本部分把一般樹形網(wǎng)絡擴展到匯集樹(sink tree)和匯集樹組合的網(wǎng)絡中，即從多個源點到多個目的地的樹狀拓撲網(wǎng)絡.對于文獻[2]中提出的通過從多個源到多個目的地測量適當路徑上的端到端數(shù)據(jù)包丟失率定位擁塞段方法，同樣地用矩陣半張量積進行說明.

如圖7所示，鏈接L1，L2，L3，兩個路徑P1，P2分別從o1至d3，o2至d3，故障發(fā)生時判斷故障鏈接基于以下兩個規(guī)則:

規(guī)則1若路徑Pi為“好”的同時Pj(i，j=1，2，i/=j)為“壞”，則當鏈接Li和L3為“好”時，Lj為“壞”(i，j=1，2，i/=j);

規(guī)則2若路徑P1，P2同時為“壞”，則鏈接L3比L1，L2更容易“壞”.

圖7 一個簡單的路徑拓撲Fig.7 A simple path topology

邏輯方程為r=P1∨P2，其中P1=L1∧L3，P2=L2∧L3，則

對應的代數(shù)方程為r=ML=δ2[1 2 1 2 1 2 2 2]·L1L2L3.

規(guī)則1中，Pi為“好”但同時Pj(i，j=1，2，i/=j)為“壞”，則r為“好”，即r=所以代數(shù)方程r=ML的解為對應的布爾表示分別為[1 1 1]，[1 0 1]，[0 1 1].由于假設1，可以確定故障發(fā)生對應的布爾表示為[1 0 1]，[0 1 1]，即當Li和L3為“好”時，Lj為壞(i，j=1，2，i/=j)，說明規(guī)則1的正確性.

規(guī)則2中，若P1，P2同時為“壞”，則r為“壞”，即r=所以代數(shù)方程r=ML的解為對應的布爾表示分別為[1 1 0]，[1 0 0]，[0 1 0]，[0 0 1]，[0 0 0].由于假設1，可以確定故障發(fā)生對應的布爾表示為[1 1 0]，即L3為故障鏈接，說明規(guī)則2的正確性.

注7以上兩個規(guī)則適用于具有任意層的匯集樹網(wǎng)絡.

定理2在匯集樹網(wǎng)絡中，定位故障鏈接的兩個規(guī)則是有效的.

下面通過例1說明矩陣半張量積方法相較于文獻[2]的優(yōu)越性.

例1如圖8所示的網(wǎng)絡圖，L1，L2，L3為鏈接，P1，P2，P3表示3條路徑.

圖8 例1中的網(wǎng)絡Fig.8 Network in Example 1

首先給出該網(wǎng)絡的代數(shù)形式:

故該網(wǎng)絡的代數(shù)方程為r=ML，其中M=δ8[1 4 3 4 7 8 7 8]，L=L1L2L3.

i) 當P1“好”，P2“壞”，P3“好”時，r==代數(shù)方程r=ML的解為L=對應的布爾表示為[1 0 1]，則故障鏈接為L2.

ii) 當P1“好”，P2“壞”，P3“壞”時，r==代數(shù)方程r=ML的解為L=對應的布爾表示分別為[1 1 0]和[1 0 0].由于假設1，可以確定故障發(fā)生對應的布爾表示為[1 1 0]，則L3為故障鏈接.

iii) 當P1“壞”，P2“壞”，P3“好”時，代數(shù)方程r=ML的解為對應的布爾表示分別為[0 1 1]和[0 0 1].由于假設1，可以確定故障發(fā)生對應的布爾表示為[0 1 1]，則故障鏈接為L1.

iv) 當P1“壞”，P2“壞”，P3“壞”時，代數(shù)方程r=ML的解為對應的布爾表示分別為[0 1 0]和[0 0 0].由于假設1，可以確定故障發(fā)生對應的布爾表示為[0 1 0]，則故障鏈接為L1，L3.

下面給出使用前文規(guī)則1與規(guī)則2和使用矩陣半張量積方法的比較，如表1和表2所示，其中:“√”表示“好”，“×”表示“壞”，“?”表示無法確定該鏈接是否發(fā)生故障.通過表1與表2的比較，可以清晰地看出，由于故障并不是經(jīng)常發(fā)生，使用矩陣半張量積方法可以最大限度精確地確定發(fā)生故障的鏈接.

表1 使用規(guī)則1和規(guī)則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最小一致故障集原則和規(guī)則1與規(guī)則2的分析推導過程中，通過將邏輯方程轉(zhuǎn)化為對應的代數(shù)方程并分析代數(shù)方程的解，可以確定一般的樹形網(wǎng)絡和匯集樹網(wǎng)絡中發(fā)生故障的鏈接，所使用的矩陣半張量積方法不僅便于計算，而且確定發(fā)生故障的鏈接更精確.

3.3 一般網(wǎng)絡

使用矩陣半張量積方法可以定位一般網(wǎng)絡中的故障鏈接.下面用一個例子來進行說明.

如圖9所示為一個局域網(wǎng)，A-G表示路由器接口，a-h表示路徑，根據(jù)數(shù)據(jù)包丟失率檢測并與閾值比較知，E，F(xiàn)，G的狀態(tài)分別為“好”、“壞”、“壞”，下面用矩陣半張量積方法確定發(fā)生故障的位置.

圖9 一個簡單的局域網(wǎng)絡Fig.9 A simple local network

首先給出該局域網(wǎng)的代數(shù)形式:

由假設1，故障發(fā)生對應的解為[1 1 1 1 1 1 0 0]，即鏈接g和h發(fā)生故障.

因此，矩陣半張量積方法不僅可以在一般的樹形網(wǎng)絡和匯集樹網(wǎng)絡中定位故障鏈接，在一般的網(wǎng)絡中也同樣適用.

4 結(jié)論

本文研究了互聯(lián)網(wǎng)網(wǎng)絡中故障位置定位問題.基于矩陣的半張量積理論，給出了網(wǎng)絡中路徑的代數(shù)表示.基于該代數(shù)表示，通過將故障定位問題對應的邏輯方程轉(zhuǎn)化為等價的代數(shù)方程，通過分析代數(shù)方程的解，給出了一般樹形網(wǎng)絡和匯集樹網(wǎng)絡拓撲結(jié)構(gòu)中確定發(fā)生故障的鏈接.通過數(shù)值算例比較發(fā)現(xiàn)，本文所提出的矩陣半張量積方法比原有方法更精確.此外，本文還將所得的理論結(jié)果在一般網(wǎng)絡中進行說明，充分展示了利用矩陣半張量積求解邏輯方程定位故障位置的有效性.未來的工作將考慮如何使用矩陣半張量積方法研究隨機因素影響下網(wǎng)絡故障定位問題，給出更易檢驗的方法.