地域通信网节点重要性评价方法*

刘道伟，蔡 啸，郝旭东，翟 洁

（1.中国洛阳电子装备试验中心，河南 洛阳 471003；2.解放军91269部队，广东 湛江 524000）

地域通信网节点重要性评价方法*

刘道伟1，蔡 啸1，郝旭东1，翟 洁2

（1.中国洛阳电子装备试验中心，河南 洛阳 471003；2.解放军91269部队，广东 湛江 524000）

为了更全面、更客观地评价地域通信网节点的重要性，提出了综合考虑节点边权值和节点地位双重因素的评价方法，该方法既刻画了节点间的作用细节，又反映出节点在网络中的位置和节点间连接紧密程度，克服了以往无权网络中评价节点重要性存在的不足。最后，通过实例验证了该方法的有效性和全面性。

节点重要性，可靠度，时延，节点边权值，节点地位

引言

地域通信网是在一定作战地域内开设若干通信节点，用微波接力、卫星等通信链路连接，构成的栅格状通信网络，能为作战地域内移动和固定的用户提供多种通信业务［1］。地域通信网是当今陆军部队作战的主要通信保障手段，同时也是战时敌人火力打击和电磁干扰的重要目标。为了保证地域通信网的安全性，就必须重点保护那些一旦遭到攻击可能对网络性能造成重大危害的节点或节点集合。所以，对地域通信网中节点重要性进行分析显得尤为重要。

目前，节点重要性的研究方法主要有两类：一类是根据节点的连接度［2］、介数［3］等确定性指标的大小来衡量节点重要性；另一类是根据度量节点删除后对网络连通的破坏程度来反映节点重要性，如生成树数目法［4］。这些方法从不同的角度衡量了节点重要性，但是又存在一定的局限性。例如，当用节点的连接度来评价节点重要性时，忽略了节点位置所起的作用；对于生成树数目法等节点删除的评估方法，无法区别删除多个节点后造成网络不连通的节点的重要性。另外，上述节点重要性的研究方法大多集中在无权网络上，而在实际的通信网中，无权网络只反映出节点之间的连接方式或网络结构的拓扑特性，并不能描述节点间各链路使用的通信体制、环境因素等对节点重要性影响，使得在无权网络中确定节点重要性存在一定的片面性。

为了对节点重要性进行全面、客观地分析，本文综合考虑了影响节点重要性的双重因素：节点边权值和节点地位，其中，节点边权值定义为与节点直接连接的边的权值之和，它真实地刻画了节点与其周围节点的作用细节；节点地位定义为节点在网络中所处位置的量化值和节点间连接紧密程度的量化值的乘积，它形象地反映出节点在网络中所处的位置和连接紧密程度，另外，在对节点地位分析过程中采用降低边的权值的方法，避免节点不连通时无法对节点重要性进行评价的情况。

1 节点重要性评价模型

1.1 地域通信网网络模型与基本假设

网络模型既是对具体系统的抽象，又是研究复杂系统的有力工具［5］。对地域通信网进行合理的抽象，建立相应的网络模型，是研究地域通信网节点重要性的基础。本文将地域通信网中的通信实体（干线节点、大小用户节点等）抽象为网络节点，把通信信道（连接实体的光纤、卫星、微波接力机等连接方式）抽象为网络边，把通信信道的各种能力限制抽象为附加在网络节点、边上的权值，得到地域通信网网络模型。具体描述如下：

在无向有权网络［8］G=（V，E，W）中，V={v1，v2，…，vn}表示节点集合，E={e1，e2，…，en}表示边集合，W={wij＞0|i，j=1，2，…，m}表示节点i和节点j之间边的权值集合。G的邻接矩阵A是一个n阶方阵，A中元素A［i］［j］定义如下：

地域通信网节点上附加的权值有很多，而时延是衡量网络传输能力的重要指标之一，可靠性是衡量网络质量优劣的一个重要指标，另外，从用户的角度来看，它们同时又是度量网络服务质量的常用参数。因此，本文选择时延和可靠性作为研究对象，权值W由二者共同决定，为了简单明了地分析网络性能，对无向有权网络G，作如下假设：

（1）网络中不考虑节点对链路的影响，任意节点之间最多存在一条连边，边的权值的处理采取权值越大，节点间关系越紧密的原则，这里W∈［1，∞），1代表关系最疏远，∞代表关系最紧密。

（2）通信信道分为3种：光纤、卫星、微波接力机，相应的可靠度R分别设为9、8、7，时延T分别设为2 ms、10 ms、1 ms。

（3）网络中各节点相互独立，节点边权值

且∈（1，∞），即权值越大，与周围节点联系越紧密。

1.2 节点边权值的评价分析

在只考虑权值情况下，节点重要性大小是通过节点边权值的大小来评价的，Si越大或小，节点vi的重要性越大或小。而边的权值大小又决定了Si的大小，因此，对边的权值进行合理分析，也体现了对节点边权值评价的合理性。

本文在对边的权值分析的过程中，综合考虑了节点间链路的可靠度和时延对边的权值的影响，采用代价函数的方法计算边的权值，代价函数公式如下：

式中，∂和β为指标体系的权重系数，且∂+β=1；Rij和Tij为节点vi和节点vj通信信道的可靠度和时延。

1.3 节点地位的评价分析

为了单独从网络拓扑结构出发，有效、可靠地分析节点位置和节点间连接紧密程度对节点地位的影响，将网络中每条边的权值设为相同的数值，并采用降低边的权值的方法，以避免当删除某节点使网络变得不连通时［4，7］，无法评价节点重要性的问题。

定义1：η（vi）为删除节点vi后网络中所有节点之间最短路径长度的平均值，即：

η表示没有删除节点的初始状态下网络中所有节点间最短路径长度的平均值，且η＞η（vi）。

式中，mij为任意两点vi，vj（j＞i；0＜i＜n，0＜j＜n）间不同的路径条数；W'kij为节点vi和vj间第k条路径上边权倒数和。

W'min表示没有删除节点的初始状态下整个网络路径上边权倒数和最小值的平均值，且W'min＜W'min（vi）。

G（vi）越大，节点vi的地位越高，重要性越大，G（vi）越小，节点vi的地位越低，重要性越小。

1.4 节点重要性的评价函数

由上文可知，在只考虑权值的情况下，Si越大，节点vi的重要性越大，在只考虑网络拓扑结构的情况下，G（vi）越大，节点vi的地位越高。Si和G（vi）相对独立，并且共同决定着节点重要性的大小。由假设3和式（6）分析可知，Si＞1、0＜G（vi）＜1，为了公平、客观地体现出节点边权值和节点地位对节点重要性的影响，通过乘积综合法拟合影响节点重要性的因素Si和G（vi），得出节点重要性的评价函数如下：

I（vi）越大，节点vi的重要性越大，I（vi）越小，节点vi的重要性越小。

2 实例分析

由于作战地形影响地域通信网可采用分布式组网方式，组成相对独立的地域通信网，本文选取摩托化步兵师进攻战斗中干线节点分布组网内的部分干线节点和用户节点为研究对象，分析各节点重要性，探讨评价节点重要性在电子对抗作战过程中，对敌网络中重点节点进行火力打击或电磁干扰的重要意义。

图1 干线节点分布组网示意图

图2为某摩托化步兵师进攻战斗中干线节点分布组网拓扑结构图，根据1.1章节对通信信道的基本假设和图1中8个节点之间连接方式的不同，将图中10条边分为3种类型，如表1所示，并在图2中标注出各边类型情况，对图中的8各节点分别从节点边权值和节点地位两方面入手，对节点重要性进行全面和有效的评价。

图2 带边类型情况的干线节点分布组网拓扑结构图

表1 边类型表

2.1 节点边权值评价

不同类型边的可靠度和时延不同，其边的权值也不同，为了分析链路对可靠度和时延要求不同的情况下，节点重要性变化的情况，将权重系数分别设为0.8.2、0.5.5、0.2.8，计算得到边的权值，如表2所示。

表2 不同权重系数下边的权值表

表3 节点边权值评价表

在只考虑权值情况下，Si越大，节点vi的重要性越大。根据式（1）计算在不同权重系数情况下，各节点边权值Si，如表3所示。当∂、β为0.8.2、0.5.5时，节点边权值排序为v5＞v6＞v4＞v2=v3＞v7＞v1＞v8，表示节点边权值在更多考虑链路可靠性、同时考虑链路可靠性和时延这两种情况下，v5重要性最大，v8重要性最小；当∂、β为0.2.8时，节点边权值之和排序为v2=v3=v6＞v4=v5＞v1=v7＞v8，表示节点边权值在更多考虑链路时延的情况下，v2、v3重要性最大，v8重要性最小。

2.2 节点地位评价

采用降低边的权值方法对节点地位进行评价，为了忽略权值的影响，将图2中所有边的权值置为100，将与被删除节点vi连接的所有边的权值置为1，如图3所示。

通过式（3）和式（5）计算删除节点vi后的η（vi）和W'min（vi），其中，没有删除节点的初始状态下的η=225、W'min=0.022 5，最后通过式（6）得到节点地位G（vi），如表4所示。

图3 删除节点v1后的网络拓扑结构图

表4 节点地位评价数据表

网络中节点位置的排序为v5＞v4＞v6＞v2=v3＞v7＞v1＞v8；删除节点后由节点间连接紧密程度的变化得出节点重要程度的排序为 v4=v5＞v6＞v1=v2=v3=v7=v8，在考虑节点位置和节点间连接紧密程度基础上，节点地位的排序为v5＞v4＞v6＞v2=v3＞v7＞v1＞v8，即v5的节点地位最高；v8的节点地位最低。

为了进一步验证本文方法的正确性，将本文方法和节点收缩法进行比较，由表5可知，节点收缩法区别出了v5最重要、v7＞v1＞v8，没识别出v4、v6、v2、v3节点之间的重要性，从网络拓扑结构图直观上看，在不考虑权值情况下，断开v4和v6都不同程度上使得网络变得不连通，因此，v4重要性应该大于v6，而v6大于v2、v3。

由此可见，本文提出的降低边的权值的方法能更有效和准确地评价出网络中位置重要的节点，另外，节点收缩法每次收缩节点后，拓扑结构就会发生改变，需要重新计算网络的邻接矩阵，而本文方法只需要更改节点相应的权值，并不会发生拓扑变化，在程序上更容易实现。

表5 节点收缩法和本文方法比较

2.3 节点重要性评价

在全面分析节点边权值和节点地位对节点重要性影响的情况下，得到链路对可靠度和时延侧重不同时各节点重要性I（Vi），如表6所示。

表6 节点重要性评价表

由表6可知，随着链路对节点重要度和时延要求的变化，各节点之间重要程度的差距也发生了变化，例如，当∂、β分别为0.82、0.5.5和0.2.8时，即链路对节点可靠度的要求降低时，v5和v4重要性的差距逐渐缩小，由∂、β为0.82时的1.484 7，缩小到0.2.8时的0.002 5，但是，整体来说不论链路对节点可靠度和时延的要求如何，节点重要性的排序都为v5＞v4＞v6＞v2=v3＞v7＞v1＞v8，说明链路对节点性能要求的不同，只是在一定程度上影响着节点重要性，节点重要性还要受节点地位的制约，保证了节点重要性评价的有效性。

3 结束语

本文对现有节点重要性评价方法的不足之处进行分析，提出了综合考虑节点边权值和节点地位等因素全面评价节点重要性，其评价结果有助于对我方网络中重要节点进行有效的防护，对敌方网络中重要节点进行重点的打击破坏，是执行电子对抗“重点时节、重点部位的重点干扰”作战原则的前提。但是，本文对节点边权值评价分析过程中只考虑了节点的可靠度和时延两个因素，在实际过程中影响节点边权值的因素很多，下一步将考虑各方因素综合评价分析节点边权值，以达到更全面评价节点重要性的目的。

［1］尤增录.战术互联网［M］.北京:解放军出版社，2010.

［2］Callaway D S，Newman M E J，Strogatz S H，et al.Network robustness and fragility Percolation on random graphs［J］. PhysRev Lett，2000，85（25）:5468-5471.

［3］ Barthelemy M.Betweenness Centrality in Large Complex Networks［J］.Euro.Phys.J.B，2004，38（2）:163-168.

［4］陈 勇，胡爱群，胡 啸.通信网中节点重要性的评价方法［J］.通信学报，2004，25（8）:129-134.

［5］乔晓东.基于路径的加权地域通信网可靠性研究［D］.长沙:国防科技大学，2011:23-24.

［6］马润年，文 刚.链路赋权的通信网络抗毁性评价方法［J］.计算机工程与设计，2012，33（10）:3762-3766.

［7］饶育萍，林竞羽，侯德亭.基于最短路径数的网络抗毁评价方法［J］.通信学报2009，30（4）:113-117.

Evaluation Method for Nodes Importance of Field Communication Network

LIU Dao-wei1，CAI Xiao1，HAO Xu-dong1，ZHAI Jie2
（1.Luoyang Electronic Equipment Test Center of China，Luoyang 471003，China；
2.Unit 91269 of PLA，Zhanjiang 524000，China）

In order to evaluate the importance of nodes in regional communication network more comprehensively and more objectively，an evaluation method which synthetically considers the edge weight and the position of node is proposed，the method not only depicts the details of roles between the nodes，but also reflects the location of node in the network and the tightness of connectivity between the nodes，and overcomes the shortages of the past on evaluating the importance of nodes in the unweight network.Finally，the effectiveness and comprehensiveness of this method has been verified by examples.

node importance，reliability，latency，edge weight of node，position of node

TN915.02

A

1002-0640（2014）11-0047-04

2013-08-05

2013-11-07

军队预研基金资助项目（51333030103）

刘道伟（1985- ），男，河南周口人，硕士研究生。研究方向：通信对抗技术。