用于評價(jià)通信網(wǎng)節(jié)點(diǎn)重要性的多參數(shù)優(yōu)化算法

張 品，董志遠(yuǎn)，沈 政

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

1 概述

網(wǎng)絡(luò)的可靠性是研究和合理規(guī)劃通信網(wǎng)的一項(xiàng)重要指標(biāo)，而研究節(jié)點(diǎn)的重要性是研究通信網(wǎng)絡(luò)可靠性課題的重要組成部分，因此，研究節(jié)點(diǎn)的重要性是當(dāng)前網(wǎng)絡(luò)可靠性研究亟待解決的問題之一[1]。文獻(xiàn)[1-2]對單個(gè)節(jié)點(diǎn)的刪除進(jìn)行研究，根據(jù)最小生成樹定理，通過計(jì)算單個(gè)節(jié)點(diǎn)刪除后子網(wǎng)絡(luò)最小生成樹數(shù)目的變化，評估每個(gè)節(jié)點(diǎn)的重要性，若變化越大，反映系統(tǒng)對該節(jié)點(diǎn)的依賴程度越高，則該節(jié)點(diǎn)越重要。

文獻(xiàn)[3-4]綜合考慮了網(wǎng)絡(luò)的 3個(gè)指標(biāo)參數(shù)，即度、鏈路數(shù)和鄰居節(jié)點(diǎn)的度，并根據(jù)不同的網(wǎng)絡(luò)環(huán)境調(diào)節(jié)各參數(shù)在網(wǎng)絡(luò)中所占的比重，其結(jié)果作為評價(jià)節(jié)點(diǎn)重要性的參數(shù)，實(shí)驗(yàn)證明該算法更細(xì)致地表現(xiàn)了節(jié)點(diǎn)間的差異性。文獻(xiàn)[4]通過設(shè)計(jì)一個(gè)三角模型綜合考慮網(wǎng)絡(luò)的傳輸特性(指各節(jié)點(diǎn)在節(jié)點(diǎn)間以最短距離傳輸?shù)穆窂街兴嫉谋戎?和網(wǎng)格特性(指節(jié)點(diǎn)收縮后以最短距離傳輸路徑的總數(shù)倒數(shù))，并對每個(gè)參數(shù)進(jìn)行高斯分布處理，該算法提供一種直觀合理的評價(jià)標(biāo)準(zhǔn)，有效地評價(jià)網(wǎng)絡(luò)節(jié)點(diǎn)的重要性，且具有高精確度。這些方法雖然可以有效地判定出各節(jié)點(diǎn)的重要性，但是實(shí)驗(yàn)發(fā)現(xiàn)，其對部分節(jié)點(diǎn)的重要性判定可能相同，不能完全區(qū)分開來。文獻(xiàn)[5]提出一種評價(jià)無線網(wǎng)絡(luò)中每條鏈路重要性的新方法，即兩測度法，并給出了歸一化表達(dá)式。通過比較第 i條鏈路失效時(shí)整個(gè)網(wǎng)絡(luò)的生成樹數(shù)目和節(jié)點(diǎn)兩兩之間最短距離的總和，評價(jià)第i條鏈路的重要性。該方法可以用來判定全網(wǎng)絡(luò)鏈路的重要性，并比較任意 2條鏈路的相對重要性。

文獻(xiàn)[6]首次根據(jù)受影響支撐樹數(shù)量的多少定義了鏈路重要性的概念，根據(jù) Kirchoff矩陣確立了支撐樹的算法。文獻(xiàn)[7-8]提出一種評價(jià)通信網(wǎng)節(jié)點(diǎn)重要性的新方法——節(jié)點(diǎn)孤立法，并提出節(jié)點(diǎn)核度積的概念，認(rèn)為通信網(wǎng)中最重要的節(jié)點(diǎn)是孤立后所對應(yīng)的節(jié)點(diǎn)核度積最大的節(jié)點(diǎn)。該方法考慮了網(wǎng)絡(luò)的連接狀況，并且動態(tài)地考慮了網(wǎng)絡(luò)中所有節(jié)點(diǎn)相互通信的最短路徑總長度的增加值。

文獻(xiàn)[9]對高度動態(tài)的戰(zhàn)地網(wǎng)絡(luò)的可靠性進(jìn)行分析，提出一種快速評價(jià)野戰(zhàn)地域通信網(wǎng)可靠性的方法。文獻(xiàn)[10-11]提出以多目標(biāo)規(guī)劃的方法求解分析網(wǎng)絡(luò)可靠性問題。文獻(xiàn)[12]對網(wǎng)絡(luò)可靠性問題涉及的基礎(chǔ)理論進(jìn)行綜述。本文在節(jié)點(diǎn)刪除算法的基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)生成樹數(shù)目、節(jié)點(diǎn)兩兩間最短距離、節(jié)點(diǎn)的度，提出一種評價(jià)通信網(wǎng)節(jié)點(diǎn)重要性的多參數(shù)優(yōu)化算法。

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

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

通信網(wǎng)絡(luò)可以基于圖論的知識來表示，設(shè)其為G=(V,E)，其中，V={v1,v2,…, vn}對應(yīng)網(wǎng)絡(luò)中節(jié)點(diǎn)的集合；E={e1,e2,…,em}對應(yīng)網(wǎng)絡(luò)中鏈路的集合，設(shè)其共有n個(gè)節(jié)點(diǎn)、m條邊，為一無自環(huán)的無向連通圖。

設(shè)G的全頂點(diǎn)完全關(guān)聯(lián)矩陣為 Ac=[aij]n×m，其中，n對應(yīng)圖中的頂點(diǎn)數(shù)；m對應(yīng)圖中的鏈路數(shù)。當(dāng)G是有向圖時(shí)，完全關(guān)聯(lián)矩陣Ac中的元素aij可以表述為[5]：

為了有效評估節(jié)點(diǎn)的重要性，對網(wǎng)絡(luò)模型做如下假設(shè)：通信網(wǎng)絡(luò)具有固定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，且各節(jié)點(diǎn)相互統(tǒng)計(jì)獨(dú)立互不影響，并具有相同的損壞概率。節(jié)點(diǎn)只存在正常和損壞2種工作狀態(tài)，而鏈路保持正常的工作[6-7]。

2.2 理論基礎(chǔ)

根據(jù)MatrixTree定理，設(shè)G為無向連通圖，B是由G的每條鏈路任意標(biāo)定方向后所得到的有向圖的關(guān)聯(lián)矩陣，可得：

其中，τ為圖G的生成樹數(shù)目；(B BT)n?1為基爾霍夫矩陣的任意一個(gè)n?1階主子式。

根據(jù)Dijkstra算法，在無向圖 G=(V,E)中，設(shè)每條邊的權(quán)值已知，找出任意節(jié)點(diǎn)到其余各節(jié)點(diǎn)的最短距離之和d。

二里半把煙袋給老太太吸，她拿過煙袋，連擦都沒有擦，就放進(jìn)嘴去。顯然她是熟悉吸煙，并且十分需要。她把肩膀抬得高高，她緊合了眼睛，濃煙不住從嘴冒出，從鼻孔冒出。那樣很危險(xiǎn)，好像她的鼻子快要著火。

頂點(diǎn)的度是指和 e相關(guān)的邊的數(shù)目，記為TD(v)。對有向圖而言，以v為尾的弧的數(shù)目稱為v的出度，記為ID(v)，以v為頭的弧的數(shù)目稱為v的入度，記為OD(v)。對無向圖，則：

3 算法介紹

設(shè)v是圖 G=(V,E)的一個(gè)節(jié)點(diǎn)；G?v代表G中節(jié)點(diǎn)v以及與其相關(guān)聯(lián)的鏈路被刪除后所得的子圖。生成樹是由圖G中所有正常工作的節(jié)點(diǎn)和鏈路計(jì)算所得，當(dāng)某個(gè)節(jié)點(diǎn)i失效后，該節(jié)點(diǎn)以及相關(guān)鏈路會同時(shí)失效，造成網(wǎng)絡(luò)生成樹數(shù)目t、節(jié)點(diǎn)度總和s、節(jié)點(diǎn)間兩兩最短距離之和d發(fā)生變化，假定變化后的相應(yīng)參數(shù)為 ti、si、di。其中，生成樹數(shù)目、節(jié)點(diǎn)度總和的變化方向一致，當(dāng)節(jié)點(diǎn)失效時(shí)，網(wǎng)絡(luò)生成樹數(shù)目、節(jié)點(diǎn)度總和與原來相比，會變小，變化越大，則該節(jié)點(diǎn)越重要，而節(jié)點(diǎn)兩兩間最短距離總和與其他2個(gè)因子變化方向相反，與原來相比變大，變化越大，則該節(jié)點(diǎn)越重要，因此，可以將這 3個(gè)因子做d(t ×s)處理，其大小則作為節(jié)點(diǎn)的重要性，值越大，該節(jié)點(diǎn)越重要[8]。當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，網(wǎng)絡(luò)的生成樹數(shù)目、節(jié)點(diǎn)度的總和、節(jié)點(diǎn)間兩兩最短距離總和計(jì)算會很大，數(shù)據(jù)統(tǒng)計(jì)復(fù)雜，故需對其指標(biāo)作歸一化處理，設(shè)生成樹數(shù)目為1?tit，節(jié)點(diǎn)度總和為1?sis，節(jié)點(diǎn)間兩兩最短距離總和為did，相乘結(jié)果定義為節(jié)點(diǎn)重要性參數(shù)(Node Importance Index,NII)，作為評價(jià)網(wǎng)絡(luò)節(jié)點(diǎn)重要性的指標(biāo)[9]。因此，當(dāng)節(jié)點(diǎn)刪除后網(wǎng)絡(luò)連通時(shí)，定義該節(jié)點(diǎn)的NII為：

本文算法流程如圖1所示。

圖1 本文算法流程

節(jié)點(diǎn)失效可能造成網(wǎng)絡(luò)不連通，當(dāng)網(wǎng)絡(luò)不連通時(shí)，di為無窮大，Ri也為無窮大，若兩節(jié)點(diǎn)都使Ri為無窮大，則其重要性不好區(qū)分開來。文獻(xiàn)[2]證明當(dāng)某節(jié)點(diǎn)及相關(guān)鏈路被刪除后造成圖不連通，則該節(jié)點(diǎn)被認(rèn)為在網(wǎng)絡(luò)拓?fù)渲芯哂凶钪匾牡匚唬@證明式(4)的正確性。而節(jié)點(diǎn)刪除后造成網(wǎng)絡(luò)不連通，使用節(jié)點(diǎn)刪除算法計(jì)算網(wǎng)絡(luò)生成樹數(shù)目，即1 ?tit ，其歸一化結(jié)果都為 1，同樣不能有效地區(qū)分開這些節(jié)點(diǎn)間相對重要性。但此時(shí)仍可以從每個(gè)節(jié)點(diǎn)的度出發(fā)考慮節(jié)點(diǎn)的重要性，因此，若節(jié)點(diǎn)刪除后造成網(wǎng)絡(luò)不連通，另外定義節(jié)點(diǎn)的NII為：

其中，ti指當(dāng)網(wǎng)絡(luò)中第i個(gè)節(jié)點(diǎn)失效后子網(wǎng)絡(luò)的生成樹數(shù)目；di指當(dāng)網(wǎng)絡(luò)中第i個(gè)節(jié)點(diǎn)失效后子網(wǎng)絡(luò)中節(jié)點(diǎn)兩兩之間最短距離的總和；si指當(dāng)網(wǎng)絡(luò)中第i個(gè)節(jié)點(diǎn)失效時(shí)子網(wǎng)絡(luò)中節(jié)點(diǎn)度的總和；t指當(dāng)網(wǎng)絡(luò)正常工作時(shí)整個(gè)網(wǎng)絡(luò)的生成樹數(shù)目；d指當(dāng)網(wǎng)絡(luò)正常工作時(shí)整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)兩兩間最短距離的總和；s指當(dāng)網(wǎng)絡(luò)正常工作時(shí)整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)度的總和。

本文算法節(jié)點(diǎn)失效后，若網(wǎng)絡(luò)連通，則使用式(4)來判定節(jié)點(diǎn)重要性；若網(wǎng)絡(luò)不連通，則該節(jié)點(diǎn)的重要性大于其他節(jié)點(diǎn)刪除后網(wǎng)絡(luò)連通的重要性；若存在多個(gè)這樣的節(jié)點(diǎn)，則使用式(5)加以區(qū)分。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

圖2 節(jié)點(diǎn)無向圖和有向圖

通信網(wǎng)絡(luò)中不同算法的節(jié)點(diǎn)重要性參數(shù)比較結(jié)果如表1所示。

表1 通信網(wǎng)絡(luò)中不同算法的節(jié)點(diǎn)重要性參數(shù)比較

對通信網(wǎng)絡(luò)各節(jié)點(diǎn)的重要性參數(shù)進(jìn)行統(tǒng)計(jì)，并對 2種算法實(shí)驗(yàn)進(jìn)行比較，結(jié)果如圖3所示。

圖3 2種算法實(shí)驗(yàn)結(jié)果比較

由圖 3可知，本文算法和節(jié)點(diǎn)刪除算法的大致曲線是一致的。在節(jié)點(diǎn)刪除算法中，節(jié)點(diǎn)v1與v2、節(jié)點(diǎn)v5與v6的歸一化結(jié)果相等，說明它們的重要性相同，而根據(jù)本文算法，節(jié)點(diǎn)v2的重要性大于節(jié)點(diǎn)v1的重要性，節(jié)點(diǎn)v5的重要性大于節(jié)點(diǎn)v6的重要性，說明它們的重要性是不同的。因此，與節(jié)點(diǎn)刪除算法相比，本文算法具有更高的精確度。

節(jié)點(diǎn)重要性排序結(jié)果如圖 4所示。分別使用本文算法(由式(4)、式(5)可知，歸一化結(jié)果越大則節(jié)點(diǎn)越重要)、節(jié)點(diǎn)刪除算法對圖 2的節(jié)點(diǎn)重要性進(jìn)行排序，箭頭指向的方向表明節(jié)點(diǎn)的重要性越低。

圖4 節(jié)點(diǎn)重要性排序結(jié)果

4.2 復(fù)雜度分析

對于n個(gè)節(jié)點(diǎn)、m條鏈路的無向圖G(m基本上都大于n)，運(yùn)行本文算法分別對最小生成樹數(shù)目、節(jié)點(diǎn)兩兩間最短距離總和以及節(jié)點(diǎn)度總和進(jìn)行時(shí)間復(fù)雜度計(jì)算，依次為 O(n2)、O(n ×n× m)、 O(n3)，然后將這些因子連乘作為節(jié)點(diǎn)重要性結(jié)果，則本文算法的時(shí)間復(fù)雜度為O(n×n×m) 。而文獻(xiàn)[1]算法復(fù)雜度則為 O(n2)，但是本文算法的精確度高于節(jié)點(diǎn)刪除算法。文獻(xiàn)[7]節(jié)點(diǎn)孤立法對于n個(gè)節(jié)點(diǎn)、m條鏈路的無向圖G，需先計(jì)算獲得一個(gè)新的n×n矩陣，新矩陣的每個(gè)元素需要n次1位的二進(jìn)制邏輯與及n?1次1位運(yùn)算，整個(gè)算法需進(jìn)行 C× n4次1位邏輯與和C× n3(n ?1)次1位邏輯或運(yùn)算，則算法總的時(shí)間復(fù)雜度為O(C ×n4)，C=1對應(yīng)全連通網(wǎng)絡(luò)，C=n對應(yīng)網(wǎng)絡(luò)完全斷開。所以，本文算法的時(shí)間復(fù)雜度小于節(jié)點(diǎn)孤立算法。算法采用Matlab(版本7.0.0)語言編寫，在1.69 GHz主頻的 AMD處理器的微機(jī)上運(yùn)行圖 1的例子，時(shí)間不到70 ms。

對于全連通網(wǎng)絡(luò)G(V,E)，其總鏈路數(shù)為L=n×(n ?1)/2，對具有不同鏈路數(shù)m的網(wǎng)絡(luò)，其運(yùn)行時(shí)間如圖5所示，其中，L表示總鏈路數(shù)。

圖5 運(yùn)行時(shí)間與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的關(guān)系

一般的大型網(wǎng)絡(luò)由25個(gè)～30個(gè)主干節(jié)點(diǎn)組成。在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為 40個(gè)的全連通網(wǎng)絡(luò)中，運(yùn)行本文算法時(shí)間不足1 s(運(yùn)行時(shí)間為0.88 s)。節(jié)點(diǎn)數(shù)在100個(gè)以內(nèi)，近似保持一致。由圖5可知，本文算法具有理想的計(jì)算能力。

5 結(jié)束語

本文提出一種用于評價(jià)通信網(wǎng)節(jié)點(diǎn)重要性的多參數(shù)優(yōu)化算法。實(shí)驗(yàn)結(jié)果表明，與節(jié)點(diǎn)刪除算法相比，該算法更具有實(shí)用性、精確性，是一種可靠的節(jié)點(diǎn)重要性評價(jià)方法。然而，本文只討論了節(jié)點(diǎn)的重要性，但是網(wǎng)絡(luò)是由節(jié)點(diǎn)和鏈路組成的，鏈路也是網(wǎng)絡(luò)的重要組成部分，下一步將研究網(wǎng)絡(luò)的鏈路重要性和通信網(wǎng)的可靠性。

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

[2]Chen Yong,Hu Aiqun,Yip Kun-Wah,et al.Finding the Most Vital Node with Respect to the Number of Spanning Trees[C]//Proc.of International Conference on Neural Networks and Signal Processing.[S.l.]: IEEE Press,2003.

[3]Page L B,Perry J E.Reliability Polynomials and Link Importance in Networks[J].IEEE Transactions on Reliability,1994,43(1): 51-58.

[4]Wu Runze,Hu Xiuyuan,Tang Liangrui.Node Importance Evaluation Based on Triangle Module for Optical Mesh Networks[C]//Proc.of Wireless Communications,Networking and Mobile Computing.Beijing,China: [s.n.],2011.

[5]董志遠(yuǎn),張 品,沈 政.一種基于兩測度的無線鏈路重要性評價(jià)方法[J].杭州電子科技大學(xué)學(xué)報(bào),2011,31(5): 159-163.

[6]Tsen F P,Sung Ting-Yi,Lin Menyang,et al.Finding the Most Vital Edges with Respect to the Number of Spanning Trees[J].IEEE Transactions on Reliability,1994,43(4): 600-602.

[7]姜 禹,胡愛群,潘婷婷.一種評價(jià)通信網(wǎng)節(jié)點(diǎn)重要性的新方法——節(jié)點(diǎn)孤立法[J].高技術(shù)通訊,2008,18(7): 673-678.

[8]姜 禹,胡愛群,潘婷婷.基于鏈路重要性的分布式網(wǎng)絡(luò)可靠性評價(jià)方法[J].東南大學(xué)學(xué)報(bào),2008,38(4): 547-552.

[9]郭 偉.野戰(zhàn)地域通信網(wǎng)可靠性的評價(jià)方法[J].電子學(xué)報(bào),2000,28(1): 3-6.

[10]Hu Jun,W ang Bing,Lee D.Evaluating Node Importance with Multi-criteria[C]//Proc.of IEEE/ACM International Conference on & International Conference on Cyber,Physical and Social Computing,Green Computing and Communications.[S.l.]:IEEE Press,2010.

[11]羅錦峰.一種全終端網(wǎng)絡(luò)可靠性多目標(biāo)優(yōu)化模型及求解[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(8): 748-754.

[12]戴伏生,董學(xué)勵.基于可靠性指標(biāo)的通信鏈路重要性評估方法[J].南京郵電大學(xué)學(xué)報(bào): 自然科學(xué)版,2007,27(1):11-19.