基于邏輯方程求解的網(wǎng)絡(luò)故障定位規(guī)則的驗(yàn)證與實(shí)現(xiàn)

劉玉娜，李海濤

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

1 引言

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

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

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

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

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

2 預(yù)備知識(shí)

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

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

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

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

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

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

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

引理1設(shè)X∈Rm，Y∈Rn，則

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

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

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

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

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

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

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

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

一個(gè)路徑由許多鏈接組成，下面將鏈接作為參數(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)復(fù)雜，容易看出從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 復(fù)合結(jié)構(gòu)Fig.4 Composite structure

3 主要結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 匯集樹網(wǎng)絡(luò)

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

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

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

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

圖7 一個(gè)簡單的路徑拓?fù)銯ig.7 A simple path topology

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

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

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

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

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

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

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

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

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

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

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

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

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

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

iv) 當(dāng)P1“壞”，P2“壞”，P3“壞”時(shí)，代數(shù)方程r=ML的解為對應(yīng)的布爾表示分別為[0 1 0]和[0 0 0].由于假設(shè)1，可以確定故障發(fā)生對應(yīng)的布爾表示為[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的分析推導(dǎo)過程中，通過將邏輯方程轉(zhuǎn)化為對應(yīng)的代數(shù)方程并分析代數(shù)方程的解，可以確定一般的樹形網(wǎng)絡(luò)和匯集樹網(wǎng)絡(luò)中發(fā)生故障的鏈接，所使用的矩陣半張量積方法不僅便于計(jì)算，而且確定發(fā)生故障的鏈接更精確.

3.3 一般網(wǎng)絡(luò)

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

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

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

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

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

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

4 結(jié)論

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