用于评价通信网节点重要性的多参数优化算法

张 品，董志远，沈 政

(杭州电子科技大学通信工程学院，杭州 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.