航空集群网络虚拟骨干网分布式构建算法*

张步硕，李 凡

（1.解放军93790 部队，河北 保定 074212；2.空军工程大学信息与导航学院，西安 710077）

0 引言

20 世纪末，网络中心战（Network-centric warfare，NCW）作战理念的提出，促进了现代战场信息化的转变。随着信息化技术的迅猛发展，战场环境更加复杂多变，少量作战平台网络化完成单一作战任务已不能满足信息化战争的发展需求，需要多平台、多任务的综合化体系化作战，集群作战理念应运而生［1］，航空集群作战这一未来航空作战模式逐渐受到重视［2］。而航空集群成员间的信息传输网络（以下简称航空集群网络）对集群作战任务的执行效能有很大的影响［3］。航空集群网络具有以下特点：1）网络节点多质性、能力差异性。航空集群中通常存在预警机、侦察机、轰炸机、电子战飞机和无人机等多种类型的作战平台，因此，网络节点具有多种角色、属性和特质，从而导致节点能力具有差异性。2）网络规模较大，分布范围较广。航空集群中平台数量一般达到几十、上百架。另外，大量的航空集群平台在作战过程中机动飞行，飞行距离以及飞行空间远而广。3）带宽需求差异化。由于要支持整个OODA 各阶段不同作战任务的连续、闭环作战，航空集群网络节点间交互的业务类型多、业务数量大，并且业务需求差异大。4）拓扑的阶段性变化，航空集群网络针对多种作战任务，任务的多样性导致节点间需经常性随机组合，节点经常性的随机组合会导致网络拓扑快速变，执行具体单一任务时，网络拓扑会维持一段时间，因此，航空集群网络的拓扑呈现出阶段性变化。5）更苛刻的时效性和更高的可靠性。战场环境瞬息万变，要求集群成员间网络管理控制信息和战术信息的传输时延尽可能低，以保证作战任务的高效完成。另外，航空集群作战的电磁环境已处于双方电子对抗激烈的拒止空间环境，敌方的电磁干扰将带来大量的信息传输错误或信息丢失。航空集群网络应尽量减少数据传输过程中包的丢失对作战任务实施的影响，因此，集群成员间的信息交互具有更高的可靠性要求。

航空集群网络对信息传输的实时性和可靠性要求高，通过构建虚拟骨干网，能够降低参与路由计算的节点数，从而减少网络中洪泛的控制分组数；进而，可以节省节点的可用带宽，从而保证带宽需求较高业务的有效传输，以及实时性要求较高业务的低时延传输；另外，能够增加业务信息占用物理信道的概率，减少业务排队等待时间，降低业务丢包等风险，从而保证业务信息的低时延、高可靠传输。

未来航空集群作战下的作战平台自身都能够达到高带宽传输的需求，但可能存在某些平台同时传输几种不同的业务信息，导致自身转发能力不够的情况出现，相应的路由转发出现拥堵、丢包现象，可能导致某些有用的业务信息丢失。为了解决这一问题，美军现阶段采用构建骨干网的方式，集群飞机在空中完成组网之前，相应的骨干节点已经定好，选那些转发能力强的大平台作为骨干节点，但这大大限制了集群作战的效率。动态分布式选取骨干节点构成虚拟骨干网，基于虚拟骨干网设计合适路由协议是一种更好的方案［3］。而这关键的一步就是虚拟骨干网的构建，选取一些高转发能力的节点构建虚拟骨干网，尽可能满足业务信息的转发需求，在骨干节点转发业务信息时，也可能出现能力不足的情况，此时就需要设计合理的路由协议来实现，针对航空集群网络的路由协议也在积极地研究改进［4］。

图论中的连通支配集理论提供了一种程式化构造具有连通性结构网络拓扑的方法，非常适合于航空集群网络虚拟骨干网的构建。其中，最小连通支配集（MCDS，Minimum Connected Dominating Set）研究以最少数量的节点构建连通支配集问题，是一个研究热点。MCDS 构建问题研究模型有单位圆盘图（UDG，Unit Disk Graph）和双向圆盘图（DGB，Disk Graph Bidirectional）两种，前者假设网络中所有节点的通信半径一致，后者考虑网络节点通信半径不一致的情况［5-6］。在航空集群网络中，基于UDG 模型研究MCDS 构建问题。

20 世纪90 年代开始了基于UDG 网络模型的MCDS 问题的理论研究和分析，取得了大量的研究成果［7-11］。文献［7］最早证明基于UDG 模型的MCDS 求解问题是NP-难问题，因此，后续研究主要采用近似算法求其解。主要研究思路一般分为两类：一类是先构造极大独立集，然后选取一些连接节点连通极大独立集，形成连通支配集［8-10］，这类算法的代表是Wan 算法［8］。Wan 算法通过构造生成树，为网络中每个节点确定相对于根节点的层次来构造极大独立集，基于极大独立集近似求解MCDS。Wan 算法的优点是时间复杂度和消息复杂度较低，分别是O（n）、O（nlogn），其中n 为网络节点数；缺点是极大独立集构造过程繁琐。另一类是基于修剪策略的方法，首先构造一个拥有较多冗余节点的连通支配集，之后利用一些修剪规则去除连通支配集中的冗余节点［11-13］，这类算法的代表是Wu 算法［11］。Wu 算法先产生一个规模比较大的CDS，再通过相应的策略将冗余节点去除。算法的时间复杂度和消息复杂度分别是O（Δ^3）、O（n^2），其中Δ 为最大节点度。Wu 算法的优点是利用了节点的局部信息，扩展性好，缺点是会产生较多的冗余节点且计算复杂度偏高。在理论研究不断深化的基础上，学者们逐步结合实际应用场景开展MCDS 问题的研究，目前主要侧重于无线传感器网络连通支配集的构造算法［14-16］。文献［14］基于Wu 算法提出了一种启发式算法近似求解MCDS，算法通过启发式修剪策略剔除冗余节点，减小连通支配集（CDS，Connected Dominating Set）规模；文献［15］基于Wan 算法提出一种新的图着色算法，通过极小支配集构建CDS，算法时间复杂度和消息复杂度分别为O（n^2）、O（nΔ）；文献［16］同样基于Wan 算法提出一种基于广度优先搜索的生成树算法，通过构造极大独立集来构建连通支配集，算法考虑节点能量及节点到基站的路径，时间复杂度和消息复杂度分别为O（nΔlogn）、O（nΔ）。基于无线传感器网络的特点，上述研究多考虑节点能量利用问题。近期，出现了应用于信息化战场的MCDS 问题研究，如文献［17］针对战场应用环境中数据链网络的实时性要求，基于Wan 算法的研究思路，改进其极大独立集构造流程和连通节点的选取流程，提出DCDS 算法。优点是将消息复杂度和时间复杂度降为O（n），缺点是只考虑了拓扑时变问题，未考虑战场环境中的可用带宽等因素。

基于以上分析，本文采用连通支配集理论，研究航空集群网络的虚拟骨干网构建问题。针对航空集群网络应用场景，借鉴Wan 算法和DCDS 算法的研究思路，采用极大独立集的方式构造连通支配集；同时根据航空集群网络的特点，将可用带宽和节点度作为重要考虑因素，提出航空集群网络虚拟骨干网的CDS 近似构建算法（Distributed Construction Algorithm for virtual backbone network of Aeronautic Swarm Network，DCAASN）。

1 网络模型

采用图论中支配集的相关理论对航空集群网络建模［5］。将航空集群网络拓扑以图G=（V，E）进行表示。

结合航空集群网络实际情况，建模时设定网络节点通信半径相同，因此，选择单位圆盘图模型（即UDG 模型）进行算法研究。

基于单位圆盘图的航空集群网络拓扑模型如图1 所示，图中平台对应集合V 的节点，表示网络节点；虚线对应集合E 的边，表示节点间的通信链路；节点的通信半径为R。

为方便理解，对基本概念做如下定义：

定义2 支配节点：支配集S 中的节点称为支配节点。

定义3 被支配节点：图G 中不属于支配集S 的节点称为被支配节点。

图1 航空集群网络模型示意图

定义4 连通支配集：给定图G=（V，E），图G 的节点集S（S⊆V）满足如下条件：由S 导出的子图是连通图，且S 是图G 的一个支配集，则称S 为连通支配集（CDS，Connected Dominating Set）。

定义5 独立集：给定图G=（V，E），M⊆V 且M≠Φ，若M 中任意两个节点均互不相邻，则称集合M 为G 的独立集（IS，Independent Set）。

定义6 极大独立集：如果在独立集M 中再添加任何节点vi∈V 且vi∉M 后，M 不再是G 的独立集，则称集合M 为图G 的极大独立集（MIS，Maximal Independent Set）。

定义7 节点度：指与该点相关联的边的条数。

2 权值函数

DCAASN 算法中，MIS 节点的选择依据是节点权值。节点权值由权值函数确定，用于反映节点的路由转发能力。为了满足航空集群应用需求，设计节点权值影响因素时，充分考虑了航空集群网络通信资源的特殊性，即无论是物理层的频谱资源，还是MAC 层的信道资源，最终都将转化为网络中端到端的带宽资源［18］。因此，将可用带宽作为衡量节点权值的一个要素，反映节点提供路由转发时的通信能力。

因此，选择节点的可用带宽作为权值函数的重要参数。节点可用带宽值越大，表明其可用通信资源越多，从而路由转发的通信能力越大，路由转发能力越强。

另外，考虑虚拟骨干网的规模，从构建较小规模CDS 的角度，采用节点度作为衡量节点权值的又一要素。通过节点度反映节点提供路由转发的连通能力。节点度越大，表示节点输入输出链路越多，可选择的路由路径越多，从而连通能力越大，路由转发能力越强。节点度和节点带宽是影响虚拟骨干网性能的最大因子，其余影响因子影响很小，包括计算能力、存储，且考虑这些因子所设计的权值函数运算复杂度提高，影响节点自身处理转发业务信息，且在处理器、存储介质高速发展的情况下，这些影响因素的影响因子越来越小。因此，本文考虑节点度和节点带宽作为影响因子

参考文献［19］权值函数构造方法，本节以节点可用带宽和节点度为参数，构造节点权值函数公式如式（1）。通过该式刻画节点提供路由转发能力的大小，权值越大，节点路由转发能力越强。

其中，d（u）为节点度；N 是一个支配点可以支配其他被支配点的理想数量，其取值与网络密度和通信距离有关，通常取网络的平均节点度；δ 是恒大于零的常数，通常取值为0.01；Bu是节点可用带宽，Bthr是节点可用带宽阈值。当可用资源一旦小于阈值时，权值将减小，选择该节点的可能性就减小。节点度和可用带宽越大，w（u）值越大，节点提供路由转发的能力越强，被选择的优先级越高。

3 算法实现

航空集群网络虚拟骨干网的构建通过以下3步实现，即邻居表建立、极大独立集构造和极大独立集连通。

3.1 邻居表建立

首先，网络中节点通过广播HELLO 分组进行邻居表建立，为同时获得邻节点的权值w（u），将权值w（u）填充到HELLO 分组中，通过HELLO 分组的交互，节点建立邻居表，并保存邻节点权值w（u），为构造MIS 打好基础。

3.2 极大独立集构造

将节点权值w（u）作为重要依据，进行极大独立集的选取。设定网络节点数为n，∀u∈n，N（u）表示节点u 的一跳邻居集，Nu（w）表示节点N（u）中所有节点的权值信息集合，Nu（w）={w（i）|0

MIS 构造阶段的实现通过dominator 分组和dominated 分组的收发来完成，具体流程如下：

STEP 1：∀u∈n，初始化C（u）=0；

STEP 2：∀u∈n，判断是否存在w（i）（w（i）∈Nu（w））大于w（u）。若存在，则不进行任何操作；否则，转至STEP 3；

STEP 3：判断是否存在i（0

STEP 4：∀x∈n（x≠u，v），若收到dominator 分组，设置C（x）=1，广播dominated 分组；

STEP 5：∀y∈n（y≠x），判断C（y）是否等于2，若等于2，则不作任何操作；否则，y 从N（y）删除x；

STEP 6：∀u∈n，若不存在C（u）=0 的情况，则MIS 构造完成；否则，转至STEP 2。

为验证上述过程所得结果的正确性，给出引理1 如下。

引理1：C=2 的节点集合是一个MIS。

证明：根据图论中支配集理论，设所有C=2 的节点组成集合H。用反证法证明，假设集合H 中存在两个节点u、v，且u、v 互为邻节点。由上述极大独立集构建流程可知，任意C=2 的节点都会发送一个dominator 分组，邻节点在收到dominator 分组后，将自身C 值改为1，并发送dominated 分组，因此，对于任意C 值为2 的节点，其邻节点肯定是C 值为1 的节点。因此，假设不成立，集合H 为独立集。同时，如果向集合H 中加入任意节点后，H 都不能构成一个独立集，因为对于任意一个C 值为1 的节点，其肯定邻节点中有C 值为2 的节点，因此，该集合为MIS。从而得证。

3.3 极大独立集连通

上述步骤所得的MIS 由一组权值较高的不相邻节点组成，不具备连通性，因此，为完成航空集群网络虚拟骨干网的构建，在MIS 构建完成后，需要选取一些连通节点连通MIS 以构成CDS 完成虚拟骨干网的构建。

MIS 的连通通过CALL 分组和ACCESS 分组的收发实现。每个支配节点发送一个CALL 分组，CALL 分组的传播遵循以下规则：只要CALL 分组被发送或转发一次，count 值减1，直至count=0，则该CALL 分组失效。CALL 分组携带其自身权值w（u）和一个计数器count（初值为3）。

将上述MIS 构造阶段所得C 值为2 的所有节点u 构成集合D（n），C 值为1 的所有节点v 构成集合E（v）。由MIS 构建CDS 的流程如下。

STEP 1：∀u∈D（n），发送CALL 分组，∀v∈E（v），收到CALL 分组后，将自身w（u）添加到该CALL 分组中并转发该分组。若同一时刻收到多个支配节点发送的CALL 分组，则只转发w（u）最大的支配节点的CALL 分组，其余直接丢弃。

STEP 2：∀y∈D（n）（y≠u），收到CALL 分组后，若收到CALL 分组数只有一个，产生一个ACCESS分组，ACCESS 分组的传播路径正好与接收到CALL分组的传播路径相反。否则选取其中w（u）最大的CALL 分组，产生一个ACCESS 分组，ACCESS 分组的传播路径与该w（u）最大的CALL 分组的传播路径相反。

STEP 3：接收到ACCESS 分组的节点将自身C值设置为2，即将自身状态改为支配节点。

上述过程完成后，所有C 值为2 的节点即构成了CDS，CDS 构建完毕。

图2、图3 给出了某网络根据DCAASN 算法构建的极大独立集MIS 和连通支配集CDS 的一个示例。图2 中黑色实心节点b、g、h 构成的集合为算法步骤2）构造完成的极大独立集；图3 中黑色实心节点b、e、f、g、h 构成的集合为在步骤2）极大独立集的基础上，通过算法步骤3）构建完成的连通支配集。该集合节点作为骨干节点，该连通支配集形成航空集群网络的虚拟骨干网。

图2 极大独立集MIS 示意图

图3 连通支配集CDS示意图

4 复杂度和消息域分析

从消息复杂度、时间复杂度和消息域3 个方面，对DCAASN 算法性能进行定量分析。其中，消息复杂度表示算法执行过程中控制分组进行交互次数的量级；时间复杂度反映一个算法的运算量；消息域指算法在选定报文转发节点时，所必须感知的拓扑范围。

下面分析DCAASN 算法的性能，分析中假设网络节点数为n，MIS 构建阶段选择出的支配节点数为N（N < n）。

4.1 消息复杂度

首先分析算法的消息复杂度。DCAASN 算法实现共3 个阶段，每个阶段均有控制信息交互。邻居表建立阶段，算法中每个节点通过发送2 次HELLO分组获得邻居信息，因而整个网络将发送2 n 次控制分组。MIS 构造阶段，算法中任一节点发送1 次状态声明分组，其中支配节点发送dominator 分组，被支配节点发送dominated 分组，因而整个网络将发送n 次控制分组。MIS 连通阶段，算法中支配节点发送1 次CALL 分组和1 次ACCESS 分组，中间节点转发这两种消息分组；由于算法中设计的最大转发次数（即count 值）为3，连通MIS 支配节点的中间节点数最多为2，而中间节点收到CALL 和ACCESS分组都会进行转发，即中间节点最多转发2 N 次CALL 分组和2 N 次ACCESS 分组；因此，最坏情况下整个网络将发送6 N 次控制分组。

综合上述分析，整个DCAASN 算法执行过程中，将有3 n +6 N 次控制分组交互，因此，DCAASN算法消息复杂度为O（n）。

4.2 时间复杂度

以下分析时间复杂度。DCAASN 算法中，每个节点通过与其邻节点比较权值w（u）大小以确定自身的支配或被支配状态。极端情况下，某节点与网络其他节点均互为邻节点，此时该节点比较次数最大，为n-1 次。因而，节点确定自身状态的最大比较次数是n-1。由于DCAASN 为分布式处理算法，各节点并行处理，因此，DCAASN 算法的时间复杂度为O（n）。

4.3 消息域

MIS 构造阶段和MIS 连通阶段的相关步骤执行过程中，DCAASN 算法仅需要1 跳邻居信息即可，因此，DCAASN 算法的消息域为1 hop。

表1 4 种CDS 构建算法的性能

表1 列出了DCAASN 与Wu 算法、Wan 算法和DCDS 算法的性能，其中n 为网络节点数，Δ 为最大节点度。

比较表1 中的4 种CDS 构建算法，可以看出：1）DCAASN 算法的时间复杂度和消息复杂度均为O（n），优于Wu 和Wan 算法，与DCDS 处于同一量级；2）DCAASN 的消息域仅为1 hop，而其他CDS 构建算法的消息域均为2 hop，邻居信息维护成本更小。

5 仿真分析

采用MATLAB 仿真工具对DCAASN 算法进行仿真分析。现有集群环境的配置条件有限，对算法性能在实验室用仿真软件模拟。为使实验结果更具说服力，选择另外3 种算法Wu、Wan 和DCDS 作对比。仿真中，设置网络规模为50～200，随机分布在大小为500 km×500 km 的正方型区域，节点通信距离为50 km，节点可用带宽为2 Mb/s，带宽可用阈值为0.2 Mb/s，δ 为0.01。通过仿真，研究不同网络规模下，算法对网络生命周期和CDS 归一化节点数的影响。其中网络生命周期指网络开始运行到网络中第1 个节点因可用带宽不足无法提供数据转发而死亡的时间；CDS 归一化节点数指形成的CDS 节点数与网络节点总数的比值。

图4 网络生命周期与节点数关系图

4 种算法的网络生命周期对比如图4 所示。从图中可以看出，DCAASN 算法的网络生命周期大于Wu、Wan 和DCDS 算法，并且网络规模越大网络生命周期越长。因为DCAASN 算法根据节点权值选取CDS 节点，而节点权值的计算加入了节点可用带宽参数，权值大小在一定程度上反映出了节点通信资源的使用情况和节点所能提供的转发能力，使得选出的支配节点是一组可用带宽平均值较高、转发能力较强的节点。因此，在相同时间内，DCAASN 算法所构造的CDS 的节点可用带宽相对较高，从而降低了节点的转发失效概率，延长了网络生命周期。

4 种算法的CDS 归一化节点数对比如图5 所示。从图中可以看出，DCAASN 算法构建的CDS 规模小于Wu、Wan 和DCDS 算法。原因在于DCAASN算法将节点度作为权值函数的参数，选取出的支配节点输入输出链路更多，连通能力更强，可以使用更少的支配节点连接更多的非支配节点，从而构建的CDS 规模相对更小。

图5 CDS 归一化节点数和节点数关系图

6 结论

本文基于UDG 网络模型提出了一种航空集群网络虚拟骨干网的分布式构建算法——DCAASN算法。该算法改进了应用于战场宽带数据链作战环境的DCDS 算法，将可用带宽作为重要考虑因素设计节点权值函数，将节点权值大小作为构建连通支配集的重要依据。通过改进极大独立集构造流程，选出一组可用带宽较大的节点作为骨干节点，而后通过选取权值较大的连通节点完成分布式CDS 的构造，实现航空集群网络虚拟骨干网的构建。理论分析和仿真结果表明，与Wu、Wan 和DCDS 算法相比，DCAASN 算法构建的虚拟骨干网中，支配节点的平均权值更高，虚拟骨干网的生命周期更长，支配节点数目更少；而算法的时间开销和消息开销与DCDS 算法在同一量级，复杂性低，收敛速度快，能够较好地适用于航空集群网络。