董志遠(yuǎn)，張 品，陳 磊

(杭州電子科技大學(xué)通信學(xué)院，浙江杭州310018)

0 引言

在無線網(wǎng)絡(luò)的設(shè)計和維護(hù)過程中，網(wǎng)絡(luò)的可靠性是一項重要指標(biāo)。鏈路失效，輕則可以引起通信網(wǎng)絡(luò)性能的下降，重則可能造成網(wǎng)絡(luò)的局部癱瘓，故在國內(nèi)外，對無線網(wǎng)絡(luò)中鏈路的重要性進(jìn)行評價，對研究通信網(wǎng)絡(luò)的可靠性有著重要的意義［1～5］。而往往各種算法對網(wǎng)絡(luò)中存在的串聯(lián)鏈路視為等重要性，但現(xiàn)實(shí)中的網(wǎng)絡(luò)往往為非對稱網(wǎng)絡(luò)，各條串接鏈路之間也不是對稱的關(guān)系，故將某些串聯(lián)鏈路的重要性視為相等是不妥當(dāng)?shù)?。因此，?dāng)串聯(lián)鏈路上多條鏈路發(fā)生故障時，應(yīng)如何考慮確定維修的先后順序，使網(wǎng)絡(luò)遭受的損失最小，以提高網(wǎng)絡(luò)的可靠性。文獻(xiàn)1提出了一種基于生成樹數(shù)目的重要性評價方法，定義最重要的鏈路刪除后，圖的生成樹數(shù)目最少，則這條邊最重要，是一種可靠的評價方法。本文在鏈路刪除法的基礎(chǔ)上，提出一個基于兩種測度的鏈路重要性評價方法，該方法不僅可以評價每條鏈路的重要性，同時還能夠區(qū)分那些在網(wǎng)絡(luò)中處于串聯(lián)的鏈路的重要性，在不改變鏈路重要性的趨勢的基礎(chǔ)上評價串聯(lián)鏈路的重要性，與鏈路刪除法相比具有更高的精確度。

1 網(wǎng)絡(luò)模型與理論基礎(chǔ)

1.1 網(wǎng)絡(luò)模型

無線網(wǎng)絡(luò)可以用圖G=(V，E)來表示，設(shè)G為有n個節(jié)點(diǎn)和m條邊的無自環(huán)無向連通圖。V={v1，v2，…，vn－1，vn}代表頂點(diǎn)的合集，圖的頂點(diǎn)對應(yīng)網(wǎng)絡(luò)中的節(jié)點(diǎn)，E={e1，e2，…，en－1，en}代表邊的集合，圖的邊對應(yīng)網(wǎng)絡(luò)中的鏈路。假設(shè)無線網(wǎng)的拓?fù)浣Y(jié)構(gòu)固定不變，節(jié)點(diǎn)之間不能夠相互備份;所有節(jié)點(diǎn)的損壞概率相同，均為p(0＜p＜1);網(wǎng)絡(luò)中的節(jié)點(diǎn)只有兩種狀態(tài):正常工作和失效，且每個節(jié)點(diǎn)的故障發(fā)生是相互獨(dú)立的，通信鏈路不會發(fā)生故障。

G的全頂點(diǎn)完全關(guān)聯(lián)矩陣Ac=［aij］由n行和m列組成，每一行表示一個頂點(diǎn)，每一列表示一條鏈路。當(dāng)G是有向圖時，完全關(guān)聯(lián)矩陣Ac中的元素aij定義如下:

1.2 理論基礎(chǔ)

Kirchhoff矩陣，對于無向圖G，假設(shè)它的完全關(guān)聯(lián)矩陣為B，則其Kirchhoff矩陣為BBT。

MatrixTree定理，設(shè)G為無向連通圖，G的所有不同的生成樹的個數(shù)等于其Kirchhoff矩陣任何一個n－1階主子式的行列式的絕對值。即:

式中，為圖G的生成樹數(shù)目，Cj為圖G的Kirchhoff矩陣任何一個n－1階主子式。

2 兩測度法

所謂的兩測度分別是指當(dāng)鏈路失效時整個網(wǎng)絡(luò)的生成樹數(shù)目以及圖中節(jié)點(diǎn)兩兩之間最短距離的總和。因此，一條鏈路的重要性可定義為:

ti代表當(dāng)網(wǎng)絡(luò)中第i條鏈路失效時整個網(wǎng)絡(luò)的生成樹數(shù)目，di當(dāng)網(wǎng)絡(luò)中第i條鏈路失效時圖中節(jié)點(diǎn)兩兩之間最短距離的總和，Ri定義為第i條鏈路的重要程度。但是當(dāng)網(wǎng)絡(luò)規(guī)模較大時，網(wǎng)絡(luò)的生成樹數(shù)目會很大，不利于數(shù)據(jù)統(tǒng)計，因此可將鏈路的重要性歸一化為:

t表示網(wǎng)絡(luò)中全部鏈路都正常工作時圖的生成樹數(shù)目，ti表示網(wǎng)絡(luò)中全部鏈路都正常工作時網(wǎng)絡(luò)中全部節(jié)點(diǎn)兩兩之間最短距離的總和。由于ti與鏈路的重要性成反比，di與鏈路的重要性成正比關(guān)系，故ri的值越小代表鏈路越重要。

令無線傳感器網(wǎng)絡(luò)的抽象模型為無自環(huán)連通圖G。

輸入:圖G的完全關(guān)聯(lián)矩陣。

輸出:按重要性的大小輸出每條鏈路的重要性歸一化后的結(jié)果。

(1)輸入G的完全關(guān)聯(lián)矩陣。

(2)計算圖G的生成樹數(shù)目t以及全部節(jié)點(diǎn)兩兩之間最短距離的總和d。

(3)刪除需要評估的鏈路。

(4)計算鏈路i刪除后圖的生成樹數(shù)目及全部節(jié)點(diǎn)兩兩之間最短距離的總和d。

(5)計算鏈路的歸一化的結(jié)果。

(6)若還有鏈路未計算，則返回第三步;若全部鏈路都已經(jīng)計算完畢，程序終止。

3 實(shí)驗(yàn)仿真

對算法進(jìn)行說明如圖1所示。圖1(a)為系統(tǒng)隨機(jī)產(chǎn)生的一個有向圖，圖1(b)為在節(jié)點(diǎn)V3和V10間刪除鏈路e15后生成的圖的拓?fù)浣Y(jié)構(gòu)。圖1(a)共有11個節(jié)點(diǎn)和15條鏈路，刪除鏈路e15后節(jié)點(diǎn)和鏈路的數(shù)目分別變?yōu)?1和14。以鏈路e15為例，刪除后分別計算其生成樹的數(shù)目，全部節(jié)點(diǎn)兩兩之間最短距離的總和，并作歸一化處理，其值作為鏈路e15的重要性的評價標(biāo)準(zhǔn)。運(yùn)用本文算法對圖1進(jìn)行鏈路重要性的評估，并對比文獻(xiàn)1，結(jié)果如表1所示。

圖1 鏈路有向圖G

表1 無線網(wǎng)絡(luò)中不同方法的鏈路重要性比較

對算法進(jìn)行說明如圖2所示。采用Hasse圖對圖1的鏈路重要性進(jìn)行排序(由公式(4)可知?dú)w一化結(jié)果越小則節(jié)點(diǎn)越重要)，結(jié)果如圖2(a)所示，自上到下代表鏈路的重要性從高到低。對比鏈路刪除法的算法對圖1重要性評價的結(jié)果可以得出圖2(b)，比較可知，本文的算法在對鏈路的重要性的評估上與文獻(xiàn)1是趨向一致的。進(jìn)一步比較每條鏈路的重要性，由表結(jié)果表明，刪除鏈路e4后，由鏈路刪除法可知e4、e5、e6所對應(yīng)的歸一化結(jié)果最小，可知e4、e5、e6是等重要的鏈路，而由兩測度法可知e4所對應(yīng)的歸一化結(jié)果最小，可知e4是最重要的鏈路。通過比較可以發(fā)現(xiàn)，與鏈路刪除法相比，兩測度法具有更高的精確度。由兩測度法易知，在網(wǎng)絡(luò)發(fā)生故障時各條鏈路的維修的先后順序，以使網(wǎng)絡(luò)遭受的損失最小，提高網(wǎng)絡(luò)的可靠性。

圖2 鏈路重要性排序結(jié)果

4 結(jié)束語

本文提出了一種評價網(wǎng)絡(luò)中鏈路重要性的新方法，并給出了歸一化的表達(dá)式。通過比較生成樹的增加數(shù)目和全部節(jié)點(diǎn)兩兩之間最短距離的總和，可以比較網(wǎng)絡(luò)中任意條鏈路的相對重要性。在評價鏈路重要性的同時，還解決了串聯(lián)鏈路的等重要性問題，進(jìn)一步區(qū)分重要性，與文獻(xiàn)1相比更具有實(shí)用性，是一種可靠的鏈路重要性評價方法。

［1］ Tsen F P，T Y Sung，M Y Lin，et al.Finding the most vital edges with respect to the number of spanning trees［J］.IEEE Trans Reliability，1994，43(4):600 －602.

［2］ 陳勇，胡愛群，胡駿.通信網(wǎng)中最重要節(jié)點(diǎn)的確定方法［J］.高技術(shù)通訊，2004，14(1):21－24.

［3］ 陳四軍，賈連興，李晶晶.基于通信網(wǎng)抗毀性的鏈路重要性比較［J］.計算機(jī)工程與應(yīng)用，2009，45(1):118－120.

［4］ 李方敏，劉新華，徐文君，等.無線傳感器網(wǎng)絡(luò)的鏈路穩(wěn)定成簇與功率控制算法［J］.計算機(jī)學(xué)報，2008，31(6):969－978.

［5］ 任智，郭偉，蘇靜，等.基于跨層協(xié)同設(shè)計的高效AODV改進(jìn)路由算法［J］.計算機(jī)學(xué)報，2007，3(5):839－843.