用于評價通信網節點重要性的多參數優化算法

張 品，董志遠，沈 政

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

1 概述

網絡的可靠性是研究和合理規劃通信網的一項重要指標，而研究節點的重要性是研究通信網絡可靠性課題的重要組成部分，因此，研究節點的重要性是當前網絡可靠性研究亟待解決的問題之一[1]。文獻[1-2]對單個節點的刪除進行研究，根據最小生成樹定理，通過計算單個節點刪除后子網絡最小生成樹數目的變化，評估每個節點的重要性，若變化越大，反映系統對該節點的依賴程度越高，則該節點越重要。

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

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

文獻[9]對高度動態的戰地網絡的可靠性進行分析，提出一種快速評價野戰地域通信網可靠性的方法。文獻[10-11]提出以多目標規劃的方法求解分析網絡可靠性問題。文獻[12]對網絡可靠性問題涉及的基礎理論進行綜述。本文在節點刪除算法的基礎上，結合網絡生成樹數目、節點兩兩間最短距離、節點的度，提出一種評價通信網節點重要性的多參數優化算法。

2 網絡模型與理論基礎

2.1 網絡模型

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

設G的全頂點完全關聯矩陣為 Ac=[aij]n×m，其中，n對應圖中的頂點數；m對應圖中的鏈路數。當G是有向圖時，完全關聯矩陣Ac中的元素aij可以表述為[5]：

為了有效評估節點的重要性，對網絡模型做如下假設：通信網絡具有固定的網絡拓撲結構，且各節點相互統計獨立互不影響，并具有相同的損壞概率。節點只存在正常和損壞2種工作狀態，而鏈路保持正常的工作[6-7]。

2.2 理論基礎

根據MatrixTree定理，設G為無向連通圖，B是由G的每條鏈路任意標定方向后所得到的有向圖的關聯矩陣，可得：

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

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

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

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

3 算法介紹

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

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

圖1 本文算法流程

節點失效可能造成網絡不連通，當網絡不連通時，di為無窮大，Ri也為無窮大，若兩節點都使Ri為無窮大，則其重要性不好區分開來。文獻[2]證明當某節點及相關鏈路被刪除后造成圖不連通，則該節點被認為在網絡拓撲中具有最重要的地位，這證明式(4)的正確性。而節點刪除后造成網絡不連通，使用節點刪除算法計算網絡生成樹數目，即1 ?tit ，其歸一化結果都為 1，同樣不能有效地區分開這些節點間相對重要性。但此時仍可以從每個節點的度出發考慮節點的重要性，因此，若節點刪除后造成網絡不連通，另外定義節點的NII為：

其中，ti指當網絡中第i個節點失效后子網絡的生成樹數目；di指當網絡中第i個節點失效后子網絡中節點兩兩之間最短距離的總和；si指當網絡中第i個節點失效時子網絡中節點度的總和；t指當網絡正常工作時整個網絡的生成樹數目；d指當網絡正常工作時整個網絡節點兩兩間最短距離的總和；s指當網絡正常工作時整個網絡節點度的總和。

本文算法節點失效后，若網絡連通，則使用式(4)來判定節點重要性；若網絡不連通，則該節點的重要性大于其他節點刪除后網絡連通的重要性；若存在多個這樣的節點，則使用式(5)加以區分。

4 實驗結果與分析

4.1 實驗設計

圖2 節點無向圖和有向圖

通信網絡中不同算法的節點重要性參數比較結果如表1所示。

表1 通信網絡中不同算法的節點重要性參數比較

對通信網絡各節點的重要性參數進行統計，并對 2種算法實驗進行比較，結果如圖3所示。

圖3 2種算法實驗結果比較

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

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

圖4 節點重要性排序結果

4.2 復雜度分析

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

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

圖5 運行時間與網絡節點數的關系

一般的大型網絡由25個～30個主干節點組成。在網絡節點數為 40個的全連通網絡中，運行本文算法時間不足1 s(運行時間為0.88 s)。節點數在100個以內，近似保持一致。由圖5可知，本文算法具有理想的計算能力。

5 結束語

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

[1]陳 勇,胡愛群,胡 駿.通信網中最重要節點的確定方法[J].高技術通訊,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]董志遠,張 品,沈 政.一種基于兩測度的無線鏈路重要性評價方法[J].杭州電子科技大學學報,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]姜 禹,胡愛群,潘婷婷.一種評價通信網節點重要性的新方法——節點孤立法[J].高技術通訊,2008,18(7): 673-678.

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

[9]郭 偉.野戰地域通信網可靠性的評價方法[J].電子學報,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]羅錦峰.一種全終端網絡可靠性多目標優化模型及求解[J].計算機技術與發展,2007,17(8): 748-754.

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