面向航空自组网的节点失效波及影响分析模型

谢丽霞，严莉萍，杨宏宇

（中国民航大学计算机科学与技术学院，天津 300300）

0 引言

航空自组网（Aircraft Ad Hoc Network，AANET）是在各类航空器和少量必要基站之上建立的能够覆盖航空领域的业务需求，集成多种通信系统、功能网和信息系统的复杂网络［1-2］。航空自组网在提高航空网通信质量的同时也面临着多种网络威胁。由于网络中节点业务处理能力有限，当网络安全事件发生时，易引起节点失效波及反应，进而造成网络节点大量失效。节点失效波及反应［3］是指当网络中节点失效时，网络为保障整体业务质量，将失效流量分配至相邻节点而引起节点连续失效的现象。因此，为给网络管理员维护网络安全提供参考，本文分析航空自组网中节点失效波及影响过程并量化网络波及影响程度，对维护网络稳定提供有效参考。

目前，关于节点失效波及影响分析主要研究成果包括相依网络模型［4］、失效节点波及影响分析模型、失效流量再分配算法等。相依网络模型通过分析网络之间的物理依赖、逻辑映射、协同合作等关联关系对复杂网络进行多维度建模。文献［3］中提出具有单一依赖关系的相依网络模型，但实际相依网络节点间大多存在多重关联关系；文献［5］中提出具有多重依赖关系的相依网络模型；文献［6］中提出一种基于多属性决策的电力通信网络节点重要性综合评估方法，提供一种相依网络模型节点加权方式，但是缺少对业务节点重要性的考虑。

在节点失效波及影响分析模型方面，文献［7］中提出经典的节点失效传播模型模拟节点失效传播过程，模型中每个节点以固定的失效概率转换为失效节点，但实际网络是动态的，不同时刻节点失效概率不同。文献［8］中提出使用改进失效传播模型分析航空网络中节点失效波及影响分析情况，定义网络节点存在恢复状态并且不会再受到波及影响，这不符合网络实际情况。文献［9］中提出传统负载−容量模型，模型中各节点具有一定的初始负载和容量，当节点负载超过容量时节点成为失效节点进而引发新一轮负载转移，模型中规定失效流量总是沿最短路径传输，但这种流量传输方式与网络实际流量传输情况不符。文献［10］中在负载−容量模型的基础上提出基于加权无标度网络参数可调的级联失效模型，当节点失效时，按照节点权重再分配失效流量，模型仅考虑节点自身属性而未考虑通信链路对节点失效波及反应的影响。文献［11］中提出面向空中交通物理信息系统的节点失效波及影响分析模型，改进传统负载−容量模型，提出基于度、介数中心性和剩余容量的节点流量分配策略，但模型并未考虑到网络中信息流具有链路持续时间。

通过失效流量再分配算法可得到节点失效发生波及反应之后受影响的节点集合，并对此节点集合进行波及影响分析。不同的失效流量再分配算法对网络的波及影响不同。文献［12］中提出一种基于节点度的流量再分配策略，根据邻居节点度与邻居节点总度数比值分配流量；文献［13］中提出基于边的空闲容量比例分配机制；文献［14］中提出一种基于聚类系数的流量再分配算法。但以上算法均没有考虑到实际网络流量的分配遵循相应的路由规则，并不是所有邻居节点都会分配流量。

针对现有航空自组网领域缺乏相应节点失效波及影响分析模型的问题，本文提出一种面向航空自组网的节点失效波及影响分析模型，在建立业务−物理相依网络模型的基础上，提出面向航空自组网的失效传播模型，通过对失效流量再分配算法的改进，得到因节点失效波及反应转换成失效节点和业务降级节点的节点集合，计算网络波及影响值并确定网络各时刻波及影响程度。

1 节点失效波及影响分析模型

面向航空自组网的节点失效波及影响分析模型如图1所示，该模型由两部分组成：

图1 节点失效波及影响分析模型Fig.1 Node failure ripple effect analysis model

1）业务−物理网络构建。首先，将航空自组网中业务抽象为业务节点，根据节点业务优先级、使用业务的用户优先级以及实时业务数据量计算业务节点权值，得到有向加权业务网络；其次，根据实时航空自组网建立物理网络，计算实体节点凝聚度作为实体节点权值，得到无向加权物理网络；最后，根据业务−物理网络之间的映射关系，建立相依网络依赖矩阵，得到业务−物理相依网络模型。

2）波及影响分析。首先，建立面向航空自组网的失效传播模型，模型中节点存在工作、业务降级和失效三种状态，节点之间根据波及影响概率转换状态；其次，通过空间位置信息计算节点之间链路持续时间，根据邻居节点属性定义链路剩余容量，依据链路持续时间和链路剩余容量计算链路生存性；再次，提出基于链路生存性的失效流量再分配算法并应用于构建的业务−物理网络模型上，得到因节点失效波及反应转化成失效节点和业务降级节点的节点集合，计算网络波及影响值并确定网络各时刻波及影响程度。

2 业务−物理网络构建

航空自组网由大量作为传输节点的航空器、少量提供信息的地面基站和参与信息交互的卫星组成（如图2 所示），节点间通过通信链路传输信息。网络的通信系统可实现飞行数据传输、空中交通管制、航空器位置追踪和机内娱乐等业务，系统各业务有序交互构成全系统业务流程，业务节点间存在有向关联关系。

图2 航空自组网Fig.2 Aircraft ad hoc network

由分析可知，航空自组网不同类型节点之间具有不同关联关系，现有单一的网络模型建模不能满足航空自组网建模需求，需构造一种多层网络模型对航空自组网进行建模。因此，航空自组网可表示为如图3 所示网络模型。图3 中，物理网络由实体节点和通信链路构成，业务网络由业务节点和节点间的有向关联关系构成。模型通过两层网络节点之间的逻辑映射关系进行耦合。

图3 业务−物理网络模型Fig.3 Business-physical network model

2.1 业务网络

业务网络GB是有向加权网络，表示为GB=（VB，EB，WB），其中VB表示业务节点集合，VB=｛Ni|i=1，2，…，NB｝；EB表示边的集合，EB=｛qi|i=1，2，…，LB｝，表示业务节点之间的有向关联关系；WB表示业务节点权重的集合，WB=｛ωi|i=1，2，…，NB｝。

航空自组网业务分为4 类：空中交通管制、飞行数据传输、航空器位置追踪和机内娱乐。根据对网络服务质量要求不同，可依次划分业务优先级为1、2、3、4，其中1 表示最高优先级。同时，使用业务的用户身份也影响业务重要性，根据用户身份不同，包括空中管制人员、飞行员、空中服务人员、乘客，可划分用户优先级为1、2、3、4。

首先根据业务优先级和用户优先级划分航空自组网的业务静态影响力。业务优先级与用户优先级越高，业务重要性越大，代表业务静态影响力越大。据此，本文制定的业务静态影响力如表1 所示。

表1 业务静态影响力Tab.1 Business static influence

由于航空自组网具有高动态的特性，本文引入业务量作为量化业务节点动态影响力的指标。设单位时间内网络处理业务数据总量为TB，节点Ni的业务数据量为Ti，则业务节点的动态影响力DIi可表示为单位时间内节点业务数据量和网络业务总数据量的比值，节点业务量越大节点影响力越大，即：

根据节点静态影响力和动态影响力，计算业务节点权重为：

业务网络由矩阵AB=表示：

其中：对角线元素aii为业务节点权重，非对角线元素aij表示业务节点间有向关联关系，若业务节点间存在关联关系，则aij=1；否则，aij=0。

2.2 物理网络

物理网络GP是无向加权网络，表示为GP=（VP，EP，WP），其中：VP表示实体节点集合，VP=｛Ni|i=1，2，…，NP｝，对应实体节点为各类航空器；EP表示边的集合，EP=｛qi|i=1，2，…，LP｝，表示实体节点之间存在通信链路；WP表示实体节点权重的集合，WP=｛ϖi|i=1，2，…，NP｝，实体节点权重由节点的凝聚度决定。

设Ni是GP中的一个节点，用GP×Ni表示将节点Ni收缩后所得到的网络。节点Ni收缩是指用一个新节点代替节点Ni和节点Ni的所有邻居节点［15］。因此，物理层网络GP的凝聚度α可表示为总节点数NP和网络平均最短路径长度乘积的倒数：

其中：NP≥2；di，j代表节点Ni和Nj之间的最短距离。节点凝聚度越大，节点越重要，对网络影响力越大。由此，实体节点权重为：

物理网络由矩阵BP=表示：

其中：对角线元素bii为实体节点权重；非对角线元素bij表示节点间的通信链路。若实体节点间存在通信链路，则bij=1；否则bij=0。

2.3 业务−物理网络模型

由前文分析可知，在航空自组网中，若实体节点同时运行多个业务，则在业务网络中也存在多个业务节点，因此，航空自组网中物理网络和业务网络间具有多重映射关系［5］，即一个实体节点可能是多个业务节点的物理基础，而一个业务节点必须依靠一个实体节点才能正常提供服务。用EC=表示相依网络之间映射关系：

若实体节点与业务节点之间存在逻辑映射关系，则eij=1；否则eij=0。

综上所述，可建立面向航空自组网的业务−物理相依网络模型，用多元组BP=（GB，GP，EC）表示，其中GB表示业务网络，GP表示物理网络，EC表示业务−物理网络映射关系。

3 节点失效波及影响分析

3.1 失效传播模型

失效传播模型定义网络中受到失效节点波及影响的节点将处于三种状态：第一种状态是节点收到的流量不超过自身处理业务能力，为正常工作节点，记作W（Working）；第二种状态是节点收到一定流量，造成自身业务处理能力降级，如带宽降低、延时增大，成为业务降级节点，记作A（Affected）；第三种状态是节点接收到超过自身业务处理能力的流量，成为失效节点，记作F（Failed）。

定义W（ti）为ti时刻工作节点的数量，F（ti）为ti时刻失效节点的数量，A（ti）为ti时刻受到业务降级节点的数量。工作节点受到失效节点的波及影响有一定概率转换为失效节点或业务降级节点。设节点波及影响概率为pi，节点的转换过程可表示为：

面向航空自组网的失效传播模型的波及影响概率会同时受到W（ti）、F（ti）和A（ti）的影响。因此，将网络中工作节点、失效节点和业务降级节点的比例随时间变化表示为：

其中：NA代表某一时间内网络节点总数；pWF则表示增加的失效数量；pWA表示增加的业务降级节点数量；W（0）则是网络处于初始状态下工作节点数量，F（0）则是网络处于初始状态下失效节点数量。

3.2 波及影响分析

在航空自组网中，节点受自身性能和在网络中位置等因素影响，承担不同的业务量并具备不同的业务处理能力。当发生安全事件引起节点失效时，通常采取将其流量分配到可用邻居节点的方式来保障整个网络业务持续运行，因此，可通过分析航空自组网中节点初始流量和业务处理能力，根据基于链路生存性的流量再分配算法得到相应失效节点和业务降级节点，并将此结果用于波及影响分析。

1）节点初始流量和业务处理能力。

首先，根据节点Ni在网络中所处位置与自身属性，定义网络开始时节点初始流量为：

其中：ki表示节点Ni的度；kj表示邻居节点Nj的度；Γi表示节点Ni的邻居节点集合；α为可调参数，用于调节节点自身属性和相关度数对波及效应的影响程度。文献［16］在其他条件不变的情况下，随着可调参数α从0.5 到1.0、1.5 和2.0 的变化，节点失效波及反应的可能性增大，因此选择α=0.5 作为本文取值。节点业务处理能力Ci与节点初始流量成正比关系，可表示为：

其中：γ为容忍系数，表示节点在发生过载之后的容忍能力。文献［17］中就不同容忍系数对网络的波及影响进行分析，实验结果表明当容忍系数过大时，流量重分配对网络影响不大，而当γ=0.06 时网络连通性较好，因此，此处选择γ=0.06作为本文的取值。

2）链路生存性。

链路生存性是指在网络发生安全事件后利用网络中空闲资源为受影响业务重新路由，减少因节点失效而造成通信或业务损失的能力。链路生存性由链路生存周期和链路质量共同决定，故根据链路持续时间和链路剩余容量计算链路生存性，过程设计如下：

①链路持续时间。

设节点Ni空间位置信息为（Nlongitude，Nlatitude，Naltitude），分别代表节点的经度、纬度和海拔高度，地球半径R取6 371 km，v为节点速度，Ψ为航迹角，r为通信半径，节点Ni的坐标表示为：

节点Ni在Δt时间后的坐标可表示为：

同理，用式（10）求解邻居节点Nj的坐标，则t0时刻节点Ni和Nj之间的距离为：

当 Δt=1 时，节点Ni和节点Nj的相离速度。由此，可求得两节点之间的相离距离Δdi，j为：

因此，可求得此时节点Ni和Nj之间链路持续时间LDT为：

②链路剩余容量。

链路剩余容量LRC受链路两端节点Ni和Nj属性限制，故本文定义链路剩余容量为邻居节点Nj剩余业务处理能力，即：

根据链路持续时间和链路剩余容量，链路生存性σi可表示为：

其中：n表示邻居节点数量。

3）基于链路生存性的流量再分配算法。

在设计流量再分配算法时，为有效分析波及影响情况，使波及影响分析更加符合实际网络波及影响情况，采用基于链路生存性的流量再分配算法。本文提出基于链路生存性的流量再分配算法工作流程如图4 所示。

图4 本文算法流程Fig.4 Flowchart of the proposed algorithm

基于链路生存性的流量再分配算法设计如下：

步骤1 在集合N=｛ni|n1，n2，…，nn｝中存储可用的邻居节点。

步骤2 根据节点实时空间位置信息计算链路持续时间。

步骤3 根据邻居节点剩余业务处理能力计算链路剩余容量。

步骤4 根据链路持续时间和链路剩余容量计算链路生存性σi，得到可用链路的平均链路生存性为：

其中：n为邻居节点总数。

步骤5 根据链路生存性σ选择可用链路。若所得链路生存性大于集合中可用链路生存性平均值，则这条链路可靠性高，选为可用链路；反之，则放弃这条链路。

步骤6 计算邻居节点Ni增加流量ΔLi，将流量根据式（18）分配到各可用节点：

其中：ξi为失效流量再分配比例；L为失效节点待分配流量。若节点因再分配的流量失效，将节点加入失效节点集合F；若节点因再分配流量业务降级，则将节点加入业务降级节点集合A。

步骤7 重复步骤1～6，直到网络中没有失效节点增加，停止循环。

在本文提出的流量再分配算法中，计算每条可用链路的生存性，选取合适链路并根据节点业务处理能力对失效流量进行再分配，这个过程的算法复杂度是O（n）。

4）节点状态判定和波及影响定级。

当节点流量不超过节点业务处理能力时，有概率pi发生节点失效，当节点流量超过节点业务处理能力时，则pi=1 节点必定失效。由式（18）可得邻居节点Ni可能接连失效的波及影响概率pi。

由于节点失效波及影响概率不同，故节点失效形式不同，根据失效模型与影响分析［18］划分节点波及影响程度等级，如表2 所示。当节点的失效模式为“较高”时，定义节点为业务降级节点；当节点失效模式为“失效”时，定义节点为失效节点；其余模式时，节点为工作节点。

表2 节点波及影响程度等级Tab.2 Node ripple effect degree

节点失效波及的失效节点和业务降级节点数量越多，节点重要度越高对网络波及影响越大，故航空自组网节点失效波及影响值可由失效节点、业务降级节点与网络总节点数的比值表示：

其中：FB代表失效业务节点总量；FP代表失效实体节点总量；AB代表业务降级业务节点总量；AP代表业务降级实体节点总量；VB代表全部业务节点集合；VP代表全部实体节点总量。

网络波及影响值越高表示网络安全状况越差，定义波及影响程度如表3 所示，依据f值可判定航空自组网节点失效波及影响程度的等级。

表3 网络波及影响程度等级Tab.3 Network ripple effect degree

4 实验与分析

4.1 实验数据来源和初始网络构建

为验证本文模型有效性，利用网络仿真工具NS2（Network Simulator version 2）进行仿真实验获取实验数据，通过Matlab 编写算法完成相关对比实验和分析。

NS2 仿真实验关键参数设置与实验过程如下：

1）编写Otcl 脚本，生成一个5 000 m×5 000 m 的模拟区域，设置trace 文件追踪网络数据传输情况。

2）生成20 个网络节点、25 条数据流的网络，如图5所示。

图5 NS2中网络初始场景Fig.5 Initial network scene in NS2

3）AODV（Ad hoc On-Demand Distance Vector routing）协议作为路由协议。

4）修改Otcl 脚本设置节点为失效节点。根据攻击方式不同，设置不同节点作为网络初始失效节点。对于随机攻击，随机选择节点作为初始失效节点；对于蓄意攻击，选择实体节点权重最大的节点作为失效节点。

5）利用gawk 分析trace 文件，收集实验数据。

航空自组网仿真关键参数如表4 所示。

表4 参数设置Tab.4 Setting of parameters

依据仿真实验参数设置，共有20 个实体节点和25 条通信链路，每条通信链路传输一个业务，故抽象出25 个业务节点和24 条有向关联边。根据各节点之间的映射关系，构建初始业务−物理网络，实体节点通信范围取1 390 km［19］。

1）业务网络的邻接矩阵。

按照2.1 节的业务节点权重计算方法计算得到网络中各业务节点权重如表5 所示。

表5 业务节点权重Tab.5 Business node weight

构建25×25 的业务网络邻接矩阵AB如下所示：

2）物理网络的邻接矩阵。

按照2.2 节的方法计算节点凝聚度作为实体节点权重，结果如表6 所示。

表6 实体节点权重Tab.6 Physical node weight

构建20×20 的物理网络邻接矩阵BP如下所示：

3）业务−物理网络映射关系矩阵。

构建20×25 的业务−物理网络映射关系矩阵EC如下所示：

4.2 基于链路生存性的流量再分配算法实例分析

以针对物理网络的蓄意攻击为例，优先攻击实体节点权重最大的节点，即实体节点1，此时节点1 失效，需对实体节点1 的失效流量进行再分配，具体算法执行过程如下：

1）首先将可用性邻居节点存储在集合N中；

2）计算链路生存性以及可用链路的平均链路生存性；

3）选取可用链路并根据节点业务处理能力对失效流量进行再分配；

4）若节点受到波及失效则开始新一轮失效流量再分配，直到没有失效节点增加，终止算法。

第一轮失效流量再分配具体过程如图6 所示，节点1 首先因蓄意攻击失效，此时网络为保障业务持续运行，故将失效流量再分配至符合条件的邻居节点。根据3.2 节中所述链路生存性计算方法，计算邻居节点链路生存性，此时节点14 和节点18 链路生存性分别为0.573 0 和0.501 7，均大于平均链路生存性0.5，故节点14 和节点18 接收到来自节点1的失效流量。然而节点14 和节点18 的业务处理能力有限，故节点14 和节点18 因接收到超过自身业务处理能力的流量造成节点失效，进而引起新一轮失效流量再分配，依据3.2节中所述基于链路生存性的流量再分配算法进行迭代，直到网络中没有波及节点失效，算法结束。本次针对物理网络实体节点的波及影响分析算法总共迭代6 次。

图6 基于链路生存性的流量再分配算法实例Fig.6 An examples of traffic redistribution algorithm based on link survivability

4.3 不同攻击方式下节点失效波及影响分析

采用随机攻击和蓄意攻击两种不同攻击方法，分别以业务网络和物理网络作为攻击对象，将本文模型、空中交通物理信息系统波及影响分析模型ATCPS（Air Traffic Cyber Physical System）［11］、基于节点权重再分配算法的波及影响分析模型WR（Weight based Redistribution）［9］、传统失效传播（Failure Propagation，FP）模型［7］、传统负载−容量（Motter-Lai，ML）模型［8］用于分析航空自组网节点失效波及影响情况。

1）业务网络攻击。

从图7～8 可知，在针对业务网络攻击的场景下，结合表3可知实际波及影响情况已达“高”等级，采用本文提出模型得到的航空自组网波及影响分析结果和NS2 仿真实验的网络实际波及影响情况更加相近。原因分析如下：

图7 业务网络在随机攻击下的节点失效波及影响情况Fig.7 Ripple effect condition of node failure in business network under random attack

①FP 模型定义网络中每个节点以固定失效概率转变为失效节点，但航空自组网是动态变化的，各时刻节点失效概率不同，故模型分析可靠性不高。

②ML 模型规定网络分配失效流量时总是沿最短路径传输，但航空自组网分配失效流量时遵循的是相应路由规则，故模型分析准确性不高。

③WR 模型是一种可调参数的波及影响分析模型，但该模型仅考虑节点自身权重再分配失效流量，缺乏网络链路对波及影响的考虑。同失效传播模型和负载−容量模型相比，WR 模型对波及影响分析准确性有所提升，但同本文模型对比，WR 模型分析准确性较低。

④ATCPS 模型为面向空中交通网络和空中通信网络建立的波及影响分析模型，在传统负载−容量模型的基础上进行改进，基于节点度、介数中心性和节点剩余容量进行流量再分配，因此，分析准确性较传统负载−容量模型有所提升；但由于未考虑到通信网络中信息流的链路持续时间对网络波及反应的影响，因此同本文模型对比，模型的分析准确性较低。

⑤本文提出的模型中，节点失效波及影响概率随网络动态变化，改进现有失效流量再分配策略，提出基于链路生存性的失效流量再分配算法，根据链路生存性选择再分配链路并按照节点容量分配失效流量，故本文提出模型的波及影响分析结果与NS2 仿真实际波及影响情况更贴切，提高了波及影响分析准确性。

图8 业务网络在蓄意攻击下的节点失效波及影响情况Fig.8 Ripple effect condition of node failure in business network under intentional attack

2）物理网络攻击。

从图9～10 可知，以物理网络实体节点作为攻击对象，四种模型的分析结果与实际波及影响趋势一致，进一步验证了本文分析模型的有效性；同时，与以业务网络作为攻击对象的分析结果相似，蓄意攻击对网络造成的波及影响也大于随机攻击，这是由于蓄意攻击优先破坏网络中权重较大的关键节点，而关键节点一般拥有较高流量，一旦失效会对网络造成严重的波及影响。

图9 物理网络在随机攻击下的节点失效波及影响情况Fig.9 Ripple effect condition of node failure in physical network under random attack

图10 物理网络在蓄意攻击下的节点失效波及影响情况Fig.10 Ripple effect condition of node failure in physical network under intentional attack

5 结语

本文提出面向航空自组网的航空自组网波及影响分析模型，基于航空自组网建立业务−物理网络模型，建立面向航空自组网的动态失效传播模型，提出一种基于链路生存性的流量再分配算法，将该流量再分配算法应用于业务−物理相依网络模型，分析航空自组网节点失效波及影响。实验结果表明，本文提出的模型能有效分析节点失效对航空自组网造成的波及影响程度。

虽然本文模型在研究节点失效波及反应过程及评估节点失效对网络造成的波及影响程度方面取得良好成果，但是随着航空自组网的发展，许多研究将改进路由协议应用于航空自组网中，不同路由协议对网络节点失效波及反应影响不同，因此，在未来研究工作中，将重点分析适应不同路由协议的节点失效波及影响分析模型。