任广建 朱金福 卢朝阳

(南京航空航天大学民航学院 南京 211106)

0 引 言

航路网络是航空运输的主要载体，对于空中交通的高效性和有序性有重要作用.交通运输网络的规划研究不仅要从外部指标进行评价，还要分析整体性能.航路网络系统作为一个复杂系统，其拓扑结构特性的研究，为网络整体规划研究提供了重要理论基础，而鲁棒性是复杂网络系统最基本和最重要的特征之一.

在受扰或不确定的情况下，鲁棒性是复杂系统抗拒干扰生存的关键.鲁棒性已经成为交通网络领域中的热点问题.文献[1]研究了无标度网络在随机攻击和蓄意攻击下的鲁棒性，结果表明，无标度网络在蓄意攻击下鲁棒性较弱，而随机攻击时鲁棒性较强.文献[2]利用蒙特卡洛方法估计最短路的分布情况，并以此评估了交通网络的鲁棒性.刘宏鲲等[3]研究了中国城市航空网络的拓扑结构，并指出中国航空网的小世界特性，进一步分析了网络的鲁棒特性.文献[4]分析了社交网络的特性，并对网络的鲁棒中心性进行了研究.航路网络的稳定性直接影响空中交通管制流量控制的有效性，因此，提高航路的稳定性对于流量管理具有支撑作用.文献[5]就如何改进航空运输网络的结构特性，提高鲁棒性进行了深入研究，并给出了改进方案.周漩等[6]利用紧密度和特征向量等结构参数对网络的鲁棒性进行研究，并且得出节点度和介数对网络鲁棒性影响较大.文献[7]提出利用节点效率来评估复杂网络的鲁棒性，实验表明，该方法对于大型复合网络具有良好的效果.赖丽萍[8]分析了轨道交通网络的特性，并对其鲁棒性进行了深入的研究.网络中节点重要性度量对于网络鲁棒性具有重要意义，度和聚集系数可以有效的度量节点重要性.文献[9]用一种节点演化级联失效模型，对网络脆弱度进行了评估研究，仿真实验表明，此方法是有效的.Schneider等[10]提出一种减缓网络攻击的方法，并证明了其提高网络鲁棒性的可行性.文献[11]基于鲁棒优化问题，对城市交通网络进行了研究，建立了不确定情况下的城市交通网路鲁棒性优化模型，并进行了优化求解.

近年来，熵理论越来越多的被应用到复杂网络系统中.文献[12]利用相对熵理论对系统中的决策排序问题进行了研究.Anand等[13]定义了熵的构造特性并指出香农熵结构特性与吉布斯和冯诺依曼熵的关联性.Xu等[14]提出了一种新的系统度依存熵指标，来描述度与相应特征的关系.文献[15]利用相对熵原理对中国铁路拓扑结构的鲁棒性进行了研究，对复杂网络中节点相似度进行了研究，这对于进一步研究网络的结构特性和鲁棒性具有重要意义.

基于以上研究，以相对熵理论为基础，针对航路网络受到随机攻击和故意攻击的情况，分析航路节点平均距离和聚类系数的分布变化情况，进而分析计算相对熵的大小，建立相对熵评估模型，来衡量航路网络鲁棒性强弱.

1 相对熵理论

1.1 相对熵的概念

相对熵(relative entropy)，又称KL散度(kullback leibler divergence, KLD),是描述两个概率分布P和Q差异的一种方法.

设P(x)和Q(x)是X取值的两个离散概率分布，则P对Q的相对熵为

D(P‖Q)=∑(P(x)log(P(x)/Q(x))) (1)

对于连续的随机变量，定义为

相对熵是两个概率分布P和Q差别的非对称性的度量，即D(P‖Q)≠D(Q‖P)，因此它并不表示一个真正的度量或者距离.在信息论领域，D(P‖Q)为用概率分布Q来拟合真实分布P时，产生的信息消耗，这里P为真实的概率分布，Q为真实分布的拟合分布.此外，相对熵的值是非负的，即D(P‖Q)≥0.

1.2 相对熵的意义

信息领域中，相对熵是用来度量使用基于Q的编码来编码来自P的样本平均所需的比特个数.特别情况下，P为数据的真实分布，Q为数据的理论分布、模型分布或P的近似分布.

由信息论的知识可知，给定一个字符集的概率分布，就可以设计一种编码，使得表示该字符集组成的字符串平均需要的比特数最少.假定，该字符集为X，对于x∈X，其出现概率为P(x)，这时最优编码平均需要的比特数等于这个字符集的熵：

(3)

(4)

由于对数函数为上凸函数，因此

(5)

由式(5)可知，相对熵始终是大于等于0的，并且只有当两个分布相同时，相对熵等于0.相对熵可以衡量两个随机分布之间的距离，当两个分布越相近时，相对熵的值越小；两个分布的差别增大时，相对熵的值也会增大.所以，相对熵可以比较事物分布的相似度，评估事物变化的相对大小.本文利用相对熵的理论对航路网络在受扰情况下的鲁棒性进行分析.

2 航路网络相关参数

2.1 节点距离分布

对于航路网络G=(N,E).式中：N为节点数；E为节点边数，网络平均距离是途径的平均边数量(每条边长度为1).本文考虑单个节点到其他所有节点的平均距离分布情况，即节点i到节点j(i≠j,j∈N)的途径边数，为

(6)

式中：Li(i=1,2,…,N)为第i节点的平均距离；dij为节点i与节点j之间的距离.

整个网络的平均距离L定义为所有节点对之间距离的平均值，即

(7)

当网络受到攻击节点被删除时，节点的平均距离就会发生变化，变化的相对大小可以作为衡量航路网络鲁棒性的指标.

2.2 节点聚类系数

(8)

聚类系数的几何意义为

(9)

与节点i相连的三元组是指包含节点i的三个节点，并且至少存在从节点i到其他两个节点的两条边，见图1.

图1 以节点i为顶点之一的三元组的两种可能形式

整个网络的聚类系数C就是所有节点i的聚类系数Ci的平均值，即

(10)

航路网络受到攻击时，有的节点被删除，进而与其相连的边也被删除，因此，节点的聚类系数会发生变化.节点聚类系数变化幅度大小可用于衡量网络的鲁棒性.

3 航路网络鲁棒性相对熵模型

鲁棒性用以表征控制系统对特性或参数扰动的不敏感性，即系统的抗干扰能力.这里用以表征航路网路受到攻击时，结构特性发生变化的程度，航路网络所呈现的后果，即航路网络抗干扰性.这里航路网络受到攻击删除节点的方式为两种，见图2.

图2 航路网络拓扑结构受攻击节点失效

航路节点平均距离和聚类系数在相对熵鲁棒模型中的应用具有相似性，这里以节点平均距离为例来说明相对熵鲁棒模型的建立过程.

令航路节点平均距离分布在[Lmin,Lmax]范围内，把该区间平均分成m段，原始网络节点平均距离值落在每个区间内的概率为P(xi)=pi(i=1,2,…,m)；当网络受到随机攻击时，随机删除一定的节点，这时网络节点平均距离值落在每个区间内的概率为Q(xi)=qi(i=1,2,…,m)；网络受到基于度故意攻击时，删除度较大的节点，这时网络节点平均距离值落在每个区间内的概率为R(xi)=ri(1=1,2,…,m).则随机变量x的分布律为

(11)

由相对熵理论可得

(12)

DR=D(P‖R)=

(13)

比较两个相对熵值可知，当DQ>DR时，随机攻击对航路网络的影响较大，网络鲁棒性在故意攻击下要比在随机攻击下保持的要好；当DR>DQ时，故意攻击对航路网络的影响较大，鲁棒性在随机攻击下的保持度要好于故意攻击情况.特别的，当DQ=DR时，这说明航路网络在受到随机攻击和故意攻击时，结构特性受影响程度相同，两种攻击对网络鲁棒特性的影响基本是一样的.

4 实例分析

以上海管制区域航路运输网络为研究对象,上海区域航路运输网络是中国最复杂，最繁忙的航空运输系统之一，因此，研究上海航空运输网络系统结构特性，可以较好的反映当前空中运行的复杂情况，有利于进一步了解航空运输系统整体特性.上海区域航路网中大约有218个航路段，每个航路段以机场、导航点和航路交叉点相连接构成了航路网络图.以区域航路段为边，航路点为节点构成了航路网络拓扑图，见图3.

图3 上海管制区域航路网络图和拓扑图

图3b)中三角形为度较大的节点，该节点对航路结构特性影响较大，航路受到随机攻击时度大的节点不一定会受影响，而故意攻击时往往从度较大的节点开始.因此，随机攻击和故意攻击可以反映网络系统不同的鲁棒特性.通过对上海航路结构特性数据的计算与分析，可得到该航路网络的节点平均距离分布和节点聚类系数分布情况，见图4.

图4 上海航路网络节点平均距离和聚类系数分布

对于上海航路网络分别进行节点随机攻击和节点按度大小攻击，由此相应的节点失效后，对剩余航路网络的节点平均距离进行计算和统计分析见表1.

表1 网络遭受攻击时，不同节点失效比例情况下的节点平均距离分布

上海航路网络遭受不同比例的随机攻击和故意攻击后，各个节点的聚类系数分布情况见表2.

表2 网络遭受攻击时，不同节点失效比例情况下的节点聚类系数分布

基于相对熵原理，分别对航路网络遭受随机和故意攻击下，计算相应的相对熵值.这里以航路有5%节点遭受攻击失效时，节点平均距离变化情况为例来说明相对熵理论的应用.令pi为原始航路网络的节点平均距离分布，qi为航路网络遭受随机攻击时节点的平均距离分布，ri为航路网络遭受故意攻击时节点的平均距离分布.航路网遭受随机和故意攻击时节点平均距离的分布律为

(14)

分别对随机攻击和故意攻击后，上海航路的网络平均距离和网络聚类系数的分析见图5.

图5 随机攻击与故意攻击下的网络平均距离和聚类系数变化情况

由图5a)可知，上海航路网络遭受攻击时，随着节点失效比例的增加，网络平均距离不断增加，其中故意攻击时，网络平均距离的增长幅度较大且变化速度较快，这时网络鲁棒性较弱.由图5b)可知，网络聚类系数随着节点失效比例的增加而减小，其中，故意攻击时，网络聚类系数呈快速下降趋势，而随机攻击时，变化趋势比较缓和，说明随机攻击的网络鲁棒性要强于故意攻击.

在两种攻击情况下，对节点平均距离和节点聚类系数的相对熵进行计算和分析，可知该航路网络参数的相对熵变化情况见图6.

图6 随机攻击与故意攻击下的节点平均距离和聚类系数相对熵变化

由图6a)可知，上海航路网络的节点平均距离随着遭受攻击节点比例的增加，相对熵变化幅度也逐渐增大.其中，遭受随机攻击时，航路节点平均距离相对熵呈现缓慢增长趋势；遭受故意攻击时，航路节点平均距离相对熵增长幅度较快.航路网络遭受故意攻击时，节点平均距离相对熵变化幅度大于遭受随机攻击时，这说明故意攻击对航路网络节点平均距离的影响大于随机攻击.由图6b)可知，航路网络的节点聚类系数随着遭受攻击节点比例的增加，相对熵也不断增大.而且，遭受随机攻击时，航路聚类系数相对熵变化比较缓慢；遭受故意攻击时，航路节点聚类系数相对熵呈快速变化趋势.航路网络遭受故意攻击时，节点聚类系数相对熵变化幅度大于遭受随机攻击时，这说明故意攻击对航路网络节点聚类系数的影响大于随机攻击.

总体而言，上海航路网络遭受故意攻击时，网络节点参数的相对熵变化值要大于随机攻击，且变化速度也较快.因此，上海航路网络遭受故意攻击时，航路结构特性变化较大，即抗干扰能力较差，鲁棒性较弱；遭受随机攻击时，航路特性在一定的范围内保持较好，且结构受损程度呈缓慢趋势，这时鲁棒性较好.

5 结 论

1) 航路网络遭受基于度的故意攻击时，节点平均距离和聚类系数的相对熵都较大且随节点失效比例的增大而呈快速变化趋势，这时航路网络表现出较弱的鲁棒性.

2) 遭受随机攻击时，相关参数的相对熵都较小且随节点失效比例的增大而呈缓慢变化趋势，航路网络表现出较强的鲁棒性.

同时，也验证了基于相对熵航路网络鲁棒性分析模型的有效性和适用性.因此，航路网络中度较大的航路节点，对于航空运输的安全性、畅通性和高效性具有重要意义，为了提高航空运输效率减少延误应重点关注度大的航路点.