一種基于兩測(cè)度的無(wú)線鏈路重要性評(píng)價(jià)方法

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

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

0 引言

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

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

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

無(wú)線網(wǎng)絡(luò)可以用圖G=(V，E)來(lái)表示，設(shè)G為有n個(gè)節(jié)點(diǎn)和m條邊的無(wú)自環(huán)無(wú)向連通圖。V={v1，v2，…，vn－1，vn}代表頂點(diǎn)的合集，圖的頂點(diǎn)對(duì)應(yīng)網(wǎng)絡(luò)中的節(jié)點(diǎn)，E={e1，e2，…，en－1，en}代表邊的集合，圖的邊對(duì)應(yīng)網(wǎng)絡(luò)中的鏈路。假設(shè)無(wú)線網(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):正常工作和失效，且每個(gè)節(jié)點(diǎn)的故障發(fā)生是相互獨(dú)立的，通信鏈路不會(huì)發(fā)生故障。

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

1.2 理論基礎(chǔ)

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

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

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

2 兩測(cè)度法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 鏈路有向圖G

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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