航空集群网络路由约束连通支配集路由算法*

张步硕，吕 娜，陈柯帆，曹芳波，刘 创

（空军工程大学信息与导航学院，西安 710077）

0 引言

未来航空作战具有高度对抗性、高度不确定性，少量的有人或无人航空作战平台无法满足未来信息化航空战场的需要[1-3]。受自然界生物行为启发，产生了航空集群作战这一未来航空作战的重要模式[4-6]。作为军事航空通信发展的方向，航空集群网络在这些需求背景下被提出。航空集群网络是无线自组织网在航空集群应用背景下产生的具体网络，无线自组织网络中路由协议是影响其性能的关键技术，因此，路由协议也是影响航空集群网络的关键技术[7]。航空集群网络具有以下特点：网络规模较大，平台类型多样；传输范围不一，航空集群作战平台一般搭载多个数据链通信设备，由于数据链通信设备的差异，导致节点的传输范围不一；针对多种作战任务，任务的多样性导致节点间需经常性地随机组合，节点的这种经常性的随机组合会导致网络拓扑变化，执行具体单一任务时，网络拓扑会维持一段时间，因此，航空集群网络的拓扑呈现出阶段性变化。现有的平面结构路由协议不能很好地适应于航空集群网络，因为平面结构路由协议可扩展性较差，适用于规模较小的无线自组网。对于航空集群网络来说，为了适应其大规模性、提高其可扩展性，本文针对航空集群网络采用分层结构路由协议。利用图论中的连通支配集理论是解决分层路由的一种有效的方法[8]，一方面可以方便地进行网络建模，另一方面将路由过程简化到支配集形成的骨干网中，可以有效减小网络开销。

但是现有对支配集理论构造路由算法的研究很少，在航空集群环境下结合支配集理论的路由算法还没有相关研究。

对此，本文以支配集理论为基础，研究基于连通支配集的路由算法。

对支配集理论的研究已经开展多年，对基于路由约束的连通支配集已经有相关研究，文献[9]在无向图的基础上提出a-moc-cds（a-Minimum rOuting Cost Connected Dominating Set），通过使用 a-2hop-DS（a-2hop-Dominating Set）解决问题，文献[10]提出一种集中式机制解决a-moc-cds问题，针对路径长度数不超过4的节点对使用一种集中式算法连接最短路径构造连通支配集，并且它们证明了a-moc-cds问题为NP-难。

但是以上研究工作还存在许多不足之处：大多数的研究都基于无向图，航空集群网络由于平台类型多样，传输范围不一，必须在有向图中研究；都简单考虑能耗问题，没有考虑节点带宽资源，与航空集群环境不符；少数基于有向图的支配集研究在构建连通支配集过程中都没有考虑路由约束，平均传输路径较长，相应的端端时延较大。路由约束是指基于有向图构建的支配集形成连通支配集所需的特殊条件。文献[10]指出在构建连通支配集过程中，将节点数不超过4的支配节点连接起来作为形成连通支配集的条件。但文献[10]仅仅考虑图论中的支配集问题研究，并没有将支配集理论与路由算法结合起来，也没有考虑航空集群网络中节点ID号分配的问题。文献[11-13]考虑了一种支配集维护算法，对于航空集群网络进行支配集维护具有启发意义，但是文献[11-13]仅在无向图中考虑支配集维护问题，对有向图中的研究没有论述。

针对以上问题，本文以航空集群环境为背景，在有向图的基础上，考虑节点带宽资源，构造节点权值函数，并提出一种分布式算法构建路由约束连通支配集形成骨干网，有效延长网络生命周期，减少平均传输路径，在此基础上，构建路由约束连通支配集路由算法，并提出基于有向图的骨干网维护机制，增加航空集群网络的鲁棒性和可扩展性。

1 网络模型

航空集群网络中，利用有向图G=（V，E）描述网络拓扑结构，V代表网络中所有节点，E代表网络中所有边。由于网络中飞行器平台类型不一，各个节点的通信半径不一定相同。若节点v在节点u的通信半径内，称u为v的入点；相反，若节点u在节点v的通信半径内，称v为u的入点。为方便理解，对基本概念解释如下：

定义1支配邻居：在有向图G中，若节点u，v互为出入点，则称节点u、节点v互为支配邻居。

定义2网络生命周期：网络中第一个节点耗尽自身资源死亡的时间。

定义3死亡节点数：网络中耗尽自身资源不能提供路由转发的节点个数。

定义4支配集：有向图G=（V，E），若存在节点集S，∀p∈V，要么p∈S，要么与S中的某一节点互为支配邻居，则S为支配集。

定义5支配节点：S中的节点。

定义6被支配节点：不属于S的节点。

定义7连通支配集：对有向图G=（V，E）。存在节点集S（S⊆V），如果由S导出的子图是连通图，且S是一个支配集，则称S为连通支配集。

2 路由约束连通支配集路由算法

航空集群网络中，构建路由约束连通支配集路由算法需要以下几步：1）路由约束连通支配集的构建；2）支配节点路由计算；3）连通支配集维护。

为有效延长航空集群网络生命周期，本文以节点带宽资源为因子，构建权值函数，计算节点权值大小。

航空集群网络中存在大型预警机或指通机这种空中枢纽，全网其他飞机要定时向空中枢纽回传自身状态及检测到的目标信息。在执行特定任务时，这种空中枢纽会事先对网络节点进行ID号再分配，分配的依据便是通过网络各节点最近一次传回的权值大小进行权值排序，分配ID号，权值越大，节点ID号越小。

航空集群网络中，带宽资源非常紧缺，因此，必须考虑支配节点自身带宽资源是否够用，对此，构造节点资源权值公式，对节点进行权值计算，具体节点权值如式（1）：

其中，d（u）为节点的度；N指网络的平均节点度；δ是恒大于零的常数，通常取值为0.01；Bu是节点所能提供的带宽资源，Bthr是节点带宽资源阈值；当所能提供资源一旦小于阈值时，权值将减小，选择该节点的可能性就减小，W（u）值越大，表示优先级越高。

航空集群网络针对多种作战任务，执行某一作战任务时，对应的网络拓扑的稳定时间可能较长，因此，基于支配集路由算法的支配集节点的生存时间应尽可能长，不同于一般网络中节点号分配的随机性，航空集群网络对节点进行权值计算，根据权值大小依次对节点进行排序，尽可能选取权值大的节点作为支配节点，以有效地延长网络生命周期[12-13]。

2.1 路由约束连通支配集的构建

参考文献[10]，有以下机制和引理。

机制1：考虑一个有向图G，和G的一个支配集C，对于任意一对 d（u，v）≤4 的节点 u，v∈C，使得满足d（u，v）≤4的最短路径上的所有节点加入集合S。

引理4：给定一个有向图G=（V，E），使用机制1从G获得的S是连通支配集。

引理4表明通过机制1构造的连通支配集是一个基于路由约束的连通支配集。

根据以上结论，可在有向图G=（V，E）的基础上分布式地构建路由约束连通支配集。对于任意一个节点v，用N（v）表示和v的支配邻居集。

2.1.1 构造支配集（DS）

航空集群网络中通过HELLO分组交换用以进行邻居发现。为有效地选出支配集节点，对OLSR算法中HELLO分组格式进行改进，增加对节点状态的描述，以及修改原保留字节为节点ID。具体修改如图1所示。

图1 修改后的HELLO分组

ID：源节点ID号；Htime：HELLO分组发送间隔；Willingness：节点愿意转发数据的意愿程度；IType：源节点状态，为支配节点或被支配节点；Link Code：链路类型，有未知链路、非对称链路、对称链路、丢失链路；Reserved：保留域；Link Message Size：链路消息的规模，即有多少该类型的邻居地址；Neighbor interface address：邻居地址。

支配集构造流程如下：

1）对于每一个节点依据权值大小分配不同的正整数ID，不同节点有不同的ID；

节点间通过修改后HELLO分组的交换获得支配邻居表 N（v）。

2）每个节点比较自己的ID和支配邻居表N（v）中的ID，如果自己的ID比双向邻居表中的ID都小，改变自身的状态为支配节点，并发送dominator消息给邻居节点。

3）对于接收到2中消息的节点，将自身状态改为被支配节点，并发送dominated消息给邻居节点。

4）每个节点更新自己的支配邻居表，删除状态为dominated的节点。

5）返回1），直到每个节点的状态都是dominator或 dominated。

构造基于路由约束的连通支配集有两步，第1步，使用以上流程构造一个支配集；第2步，连接支配集构成连通支配集。

2.1.2 构造路由约束连通支配集

1）DS中的每一个支配节点（id1）发送消息（id1）给所有的邻居节点。

2）对每一个被支配节点（id2），如果节点id1（STEP1）在自己的支配邻居表N（id2）中，添加自己的id2给每一个收到的ID id1，然后发送消息（id1，id2）给所有的邻居。

3）对每一个节点。

①对STEP1所有的支配节点IDS idi，每一对支配节点 id1 和 id1'，如果 id1＜id1'，发送消息（id1'，id*，id1）给支配节点 ID id1。

② 对每一个消息（id1，id2），id0（STEP1 中的支配节点），如果 id1＜id0，发送消息给（id0，id*，id2，id1）被支配节点 ID id2；否则（id1，id2，id*，id0），发送消息到支配节点ID id0。

4）当一个被支配节点ID id2收到一个消息（id0，id*，id2，id1），发送此消息给邻居支配节点ID id1。

5）每一个支配节点ID id1删除只有两个ID信息的ID分组，剩余信息组成集合M，M不等于φ，执行下列计算：

if：支配节点ID id1有两个相同的的信息（id0，id*，id2，id1），则删除该信息。

else：执行选择（idh，id2，id1）∈M，发送消息（idh，id2，id1）到节点 ID id2，删除所有从 idh 开始的信息。并向ID id2发送dominator消息，ID id2收到后将自身变为支配节点。

6）如果STEP5中没有消息通过，停止，否则，继续转到STEP5执行。

7）输出：所有的节点（dominator）组成一个基于路由约束的连通支配集。

2.2 支配节点路由计算

在构建好的支配集的基础上，为了进一步减少网络开销，被支配节点i只需维护支配邻居表即可，每个支配节点维护骨干网全网其他节点路由表以及一张邻居对照表。

接下来支配节点基于骨干网范围独立选择自身的MPR集，通过使用OLSR路由算法中的机制进一步减小网络开销。而后支配节点进行骨干网全网的路由计算，通过TC消息扩散建立拓扑，网络中被支配节点收到TC消息后直接丢弃，每个支配节点维护一张骨干网中所有支配节点的路由表。此外，支配节点需维护一张邻居对照表，用以知道所有被支配节点下相邻支配节点，便于进行数据转发。

基于路由约束的连通支配集路由算法描述如图2，图中深色节点表示支配节点，浅色节点为被支配节点。

图2 路由约束连通支配集路由算法描述

2.3 连通支配集维护

在执行特定任务时，网络拓扑需要维持一段时间，在此期间，当连通支配集构成的骨干网中的节点由于资源不足或突然被敌方攻击而死亡后，必须进行有效维护以确保网络的畅通，因此，必须研究连通支配集维护机制。连通支配集维护机制如图3所示。

图3 骨干网维护机制

通过以上机制进行连通支配集的维护确保骨干网的连通性，可以有效地增加航空集群网络的可扩展性和鲁棒性。

3 仿真验证

本文使用Qualnet仿真软件，针对航空集群作战的集群作战特点，设定仿真参数如表1所示。

表1 不同类型飞机参数设定

死亡节点数与总数据业务的实验结果如图4所示。

图4 死亡节点数与总数据业务曲线

AODV算法由于选择最少跳为转发路径，导致某些节点成为关键节点，频繁地完成转发任务，致使其所能提供的带宽资源被耗尽，无法继续正常提供路由转发功能，成为死亡节点，随着业务量的增大，死亡节点数目也随之上升。采用OLSR算法时，节点保持全网各节点的路由信息，发送数据时直接进行数据传送，但还是会有部分节点作为关键节点而耗尽资源，死亡节点数相较于AODV差别不大。本文算法中数据转发都在连通支配集形成的骨干网里进行，依据节点权值大小选取一组平均权值较大的节点作为支配节点，有效地延长网络生命周期，降低了网络死亡节点数，相较于以上两种算法，死亡节点数明显降低。

时延与总数据业务的实验结果如图5所示。

图5 时延与总数据业务曲线

采用AODV算法时，节点在需要进行数据通信时，才会发起路由发现，因此，时延较长，采用OLSR算法时，节点始终维护到任意节点的路由信息，因此，时延相较于AODV来说有明显优势，采用本文算法时，节点间需进行数据传送时，先将数据传送到连通支配集形成的骨干网中，再由骨干网转发至目的节点，由于构建的是基于路由约束的连通支配集，平均路径长度相较于现有的连通支配集明显减短，相应的时延也缩短，与OLSR算法时延基本一致，相比于AODV来说时延有明显改善。

路由开销与总数据业务实验结果如图6所示。

图6 路由开销与总数据业务曲线

此处的路由开销为成功发送一个数据分组需要的控制分组数，采用AODV算法时，数据在发送时才进行路由发现，路由开销较小，但当业务量增大时，AODV所产生的控制流量中路由开销随着同时处于活动状态的数据流数据的增加而增大；采用OLSR算法时，节点要时刻维护全网各节点的路由信息。因此，路由开销较于AODV较大，但是OLSR算法中节点定期广播路由流量，而不管有多少分组的产生，因此，路由开销基本保持平稳；采用本文算法时，只有支配节点须维护骨干网全网路由信息，非支配节点只需维护邻居列表信息，因此，路由开销相较于AODV，OLSR改善明显。

4 结论

本文针对航空集群网络提出了路由约束连通支配集路由算法，阐述了算法的相关思路，设计了节点权值函数和基于路由约束的连通支配集来减少网络死亡节点数、降低端端时延及路由开销，将本文算法与AODV、OLSR进行了对比分析，仿真结果表明，本文算法相较于AODV、OLSR路由算法对网络死亡节点数、时延以及路由开销都有明显改善，能够更好地适应于航空集群网络。