张兆晨，钱宁

(中国电子科技集团公司 第28研究所 信息系统工程重点实验室，江苏 南京 210007)

0 引言

飞机编队执行任务通常以空中分层网络的形式进行组网。空中分层网络为飞行编队间的信息交互提供了通信保障，主要包括一个拓扑相对稳定的骨干网和若干动态移动的子网，具有链路质量不稳定、通信距离受限、拓扑变化快[1]等特点。由于空中分层网络受到能量、干扰等内外部因素的限制，为保证网络的连通性，最有效的手段是增加飞行器作为通信中继节点。因此，如何以尽量小的代价部署中继节点并生成中继航线，成为亟待解决的问题。

从研究对象、实现连通性的方法以及针对的问题等方面看，目前的研究成果还不能满足空中分层网络的连通性需求。一些文献[2-5]主要针对拓扑固定、不随时间变化的无线传感器网络(wireless sensor networks, WSN)的中继节点放置问题，解决方法通常是调整节点发射功率以实现拓扑中边的连通，不能适用于节点分布区域广、通信能源受限的空中分层网络。还有一些文献的研究对象虽然是空中网络，但是由于优化目标、限制条件等不同，都不能解决航空平台拓扑随时间快速变化的网络连通性问题。例如，文献[6]提出一种无人机群网络连通性的实时动态规划方法，主要关注中继节点的位置对任务的满足程度，没有给出具体的中继节点路径生成方法；文献[7]研究了优化自组织网络连通性的无人机部署和移动算法，但其目的是保证网络的4种连通属性，没有考虑采用的无人机数量最小；文献[8]提出了一种WSN网络维护和恢复算法，虽然寻找到了中继的最小个数和位置，但其目标是提高网络生存时间和重建网络连接；文献[9]提出了一种动态环境下的无人机多目标协同路径规划方法，其目标是任务风险和任务延迟的最小化；文献[10]对空中自组织网络进行了中继节点优化配置，但是仅在单一时刻最优配置，没有考虑整个飞行过程中的全局优化；文献[11]提出了一种无人机飞行模型，但主要针对无人机为地面移动自组网提供中继服务的问题；文献[12]在中继个数固定的条件下实现了网络连通和中继运动距离最小，但没有考虑中继个数最小化。文献[13]提出一种增加固定节点以提高网络连通性的算法，但是不能满足飞行编队前出执行任务的通信保障需求。

为此，针对现有空中网络连通性实现方法、中继节点部署等问题中存在的不足，本文提出一种面向空中分层网络连通性的中继航线规划方法，该方法从整个航线全局优化的角度出发，以尽可能增加中继节点在不同时间、空间上的复用率为目标，生成中继节点的航线，在解决空中分层网络通信问题的基础上，减少了中继节点飞行器的使用量。

1 问题分析

空中分层网络的骨干网拓扑相对稳定，主要为编队提供各种信息业务支撑，节点之间通过宽带链路连接；子网拓扑变化较快，由子网长机和子网成员飞机组成，主要执行机动任务，子网节点之间以及子网与骨干网节点之间通过窄带链路连接。空中分层网络是飞机编队完成任务的基础，航线规划[14]要求保证空中分层网络拓扑中骨干网节点之间以及骨干网与子网长机节点之间连通，以支持数据信息的交互。

由于链路支持的通信距离与链路端机的发射功率有关，而无限制地增加链路端机的发射功率不但增加了飞机的负担，影响续航时间，而且往往不可能实现。因此，保证连通性最有效的方法是增加中继节点。飞机编队在飞行前必须依据任务进行航线规划，而任务航线规划的结果并没有考虑通信保障问题。本文以任务航线规划的骨干网和子网长机节点的飞行路径为输入，面向上述空中分层网络的连通性需求，提出一种空中分层网络中继航线规划方法，在不改变飞机编队规划任务航线的条件下，生成中继节点的航线，并且考虑增加尽量少的中继节点，同时中继节点飞行尽量短的距离，以降低通信保障的成本，保证算法的优化。

设任务航线规划结果中不存在位于相同经纬度、不同高度上的节点，即将本文的规划问题简化为二维平面网络问题。为便于形式化描述本文的方法，定义以下参数：

(1)t：输入的任务航线规划时间点，t=0,1,…,Nt，Nt为任务航线时长；

(2)U：骨干网和子网长机节点组成的拓扑；

(3)dij：节点i与节点j之间的距离；

(4)RKDL：宽带链路的可通信距离；

(5)RZDL：窄带链路的可通信距离；

(6)eu(t)：t时刻点u的连通分量，即t时刻与点u可以连通的所有点的集合；

(7)Eac：拓扑U的全连通边的集合，边的权重为边的长度；

(8)Tmst：拓扑U的MST；

(9)Tadj：优选后的拓扑U的生成树，即选择的拓扑U的节点之间的连接边组成的集合；

(10)Ere：中继段向量的连接边的集合；

(11)Econ：优选后的中继段向量的连接边的集合；

(12)vre：中继节点的最大运动速度。

需要说明的是，本文生成树优选只适用于2个飞机间添加1个中继节点的情况，因为当2个飞机间距离急剧增大时，可能会造成添加中继节点个数剧增，故假设本文航线规划在2个飞机间的最大距离小于等于相应链路的可通信距离2倍的情况下进行。

2 中继航线规划方法

2.1 生成树优选策略

为添加尽量少的中继节点，需要尽可能增加中继节点在不同时间、空间上的复用率。因此，在计算t时刻拓扑U的生成树时，本文考虑了t-1时刻中继节点的位置。通过比较t时刻拓扑U的MST边的顶点的连通分量是否与t-1时刻相同，来决定t时刻生成树的边的选择。若当t时刻MST的一条边的两端点的连通分量与t-1时刻相同，且在t-1时刻这2个连通分量由另一条边通过中继节点连接，则选择t-1时刻生成树中连接这2个连通分量的边，并入t时刻的生成树。

首先，根据Kruskal算法[15]计算拓扑U的MST为Tmst，然后对Tmst进行优选，生成树优选策略的具体过程如下：

(1) 对Tmst的每一组边(u,v)，判断边的长度duv与链路的可通信距离R的大小关系；其中，若边(u,v)由宽带链路连接时，则R=RKDL，若边(u,v)由窄带链路连接时，则R=RZDL。

(2) 若duv>R，则表示边(u,v)不可连通，执行下一步；否则对Tmst中的边(u,v)不作替换。

(3) 计算点u和v在t时刻的连通分量eu(t)和ev(t)，若eu(t)=eu(t-1)且ev(t)=ev(t-1)，并且eu(t-1)和ev(t-1)由另一条边(g,k)通过中继节点连接，如图1所示，则将Tmst中的边(u,v)替换为边(g,k)；否则，对Tmst中的边(u,v)不作替换。

(4) 判断是否对Tmst的每一组边(u,v)均进行过处理，若均进行过处理，则得到优选后的生成树Tadj，否则返回步骤(1)。

图1 生成树优选Fig.1 MST optimization

2.2 确定中继节点位置并生成中继段向量

对2.1节中得到的t时刻的生成树Tadj中的每一组边(u,v)，计算中继节点的位置，并连接生成中继段向量：

(1) 若R

(2) 查找(u,v)在t-1时刻是否存在中继，若不存在中继，则在(u,v)的中点添加中继节点zuv(t)，并执行步骤(4)；否则设(u,v)在t-1时刻存在中继节点zuv(t-1)，并执行步骤(3)。

(3) 在(u,v)的中点添加中继节点zuv(t)，并将zuv(t-1)到zuv(t)用带箭头的直线连接，形成t-1时刻到t时刻的中继段向量Li，如图2所示。

(4) 判断是否对Tadj中的每一组边(u,v)均进行过处理，若均进行过处理，则得到拓扑U在t-1时刻到t时刻的中继段向量，否则返回步骤(1)。

图2 连接中继段向量Fig.2 Connecting relay segment vector

2.3 基于权重的中继段向量连接方法

对任务航线时长Nt内的所有时刻进行2.1和2.2节所述方法的计算，若计算得到的各时间间隔的中继段向量首尾连续，则将它们连接成为一个向量，从而得到拓扑U在Nt内的中继段向量集合L。下面计算L中可连接的向量，并优选和连接中继段向量，形成各中继节点的航线。为了将尽量多的中继段向量连接起来，并耗费尽量少的中继节点飞行时间，以减少增加的中继节点的数量和飞行距离，降低保障连通性的成本，本文考虑将L的中继段向量的顶点的度，以及中继节点在2个中继段向量间的运动时间作为联合权重，优先选择度较小和耗时较小的边进行连接。基于权重的中继段向量连接方法具体过程如下：

(1) 计算中继段向量的可连接边

对L的任意2个中继段向量Li和Lj，进行以下处理：

1) 设Li的起始节点和结束节点分别为u和v，Lj的起始节点和结束节点分别为g和k，判断tk和tu的大小，若tk

图3 可连接的中继段向量Fig.3 Relay segment vector can be connected

3) 判断是否对L中所有的向量Li和Lj均进行过处理，若均进行过处理，则得到L的可连接边的集合Ere，之后执行步骤(2)，否则返回步骤1)。

(2) 优选可连接边并连接中继段向量

对Ere中的每一条边(k,u)，将与顶点k和u连接的中继段向量Lj和Li分别各自进行首尾连接并删除向量，然后进行以下处理：

3) 计算边(k,u)的权重：W=w1w2.

4) 判断是否对Ere中所有的边(k,u)均进行过处理，若均进行过处理，则得到Ere中所有边的权重，之后执行步骤5)；否则返回步骤1)。

5) 按照权重由大到小的顺序，将Ere中权重W所对应的边(k,u)放入边集合Econ中，并删除Ere中的边(k,u)以及与边(k,u)的顶点k和u存在公共节点的边。

6) 判断Ere中是否还存在边，若不存在，则根据Econ将相应的中继段向量连接，得到中继节点的航线，否则返回步骤5)。

下面用一个示例说明上述算法，如图4a)所示，图中包含4个中继段向量和5条可连接边：

1) 中继段向量分别各自进行首尾连接并删除向量，计算图中各边的权重w1，如图4b)所示。

3) 计算各边的权重W，如图4d)所示。

4) 依次按照权重W由大到小，首先在Ere中取出并删除边(a,u)，将边(a,u)放入边集合Econ中，并且删除Ere中的边(k,u)和(c,u)；再在Ere中取出并删除边(c,g)，将边(c,g)放入边集合Econ中；最后，在Ere中取出并删除边(k,b)，将边(k,b)放入边集合Econ中；Ere中不存在边，选择结束，得到的Econ中包含的边为(a,u)，(c,g)，(k,b)；可以看出，原本4个中继段向量连接成为1条中继航线，如图4e)所示。

图4 优选中继段向量的连接边示例Fig.4 Example of optimizing connected edges of relay segment vectors

至此，基于空中分层网络的连通性需求，生成了中继节点航线，实现了对中继节点的航线规划，同时保证了算法在降低飞行成本上的优化作用。

2.4 中继航线规划流程

中继航线规划方法的流程如图5所示。在任务航线时长Nt内的每个时间点，对拓扑U进行2.1和2.2节所述的生成树优选计算与中继节点位置确定，生成每个时间点的中继段向量。对得到的任务航线时长Nt内的中继段向量集合L进行2.3节所述的基于权重的中继段向量连接，最终生成中继节点的航线。

图5 中继航线规划方法流程Fig.5 Process of the relay route planning method

3 仿真试验与结果分析

为了验证本文算法的有效性和相较传统算法的优化作用，在基于地图数据的显示平台上进行仿真试验，分别对生成树优选策略和基于权重的中继段向量连接方法进行功能试验和性能对比试验。显示平台中用红色带箭头的折线表示骨干网飞机飞行任务航线，蓝色带箭头的折线表示子网长机飞行任务航线，黄色线段表示同一时刻2个任务航线节点之间的可连通性，绿色带箭头的折线表示本算法生成的中继节点的飞行航线。

3.1 功能试验

3.1.1 生成树优选策略

以骨干网飞机飞行任务航线为例进行生成树优选策略功能试验，其中RKDL=200 km，航线规划的实际时间间隔为100 s，骨干网飞机速度为250 m/s。如图6a)为输入的骨干网飞行任务航线，对该任务航线进行中继航线规划，生成中继节点航线。由于飞行航线具有时序特性，为清楚地表示增加中继节点的过程，将任务航线和中继航线按照时序进行推演，并在时刻1和时刻2进行截图，得到图6b)和6c)。可以看到，图6b)时刻的MST为(1,2),(2,3)，优选的生成树为(1,2),(2,3)；图6c)时刻的MST为(1,3),(2,3)，而经过优选的生成树仍然为(1,2),(2,3)，因此，本文算法需要添加的中继节点个数为1。若图6c)时刻不进行生成树优选，而直接由MST决定增加中继节点的位置，则需要在(1,3)之间增加另一个中继节点，由此增加的中继节点个数为2，故通过本文算法的生成树优选策略能够实现增加中继个数的优化。

图6 生成树优选试验Fig.6 Test of MST optimization

3.1.2 基于权重的中继段向量连接方法

以骨干网飞机飞行任务航线为例进行基于权重的中继段向量连接方法功能试验，其中RKDL=600 km，航线规划的实际时间间隔为1 000 s，骨干网飞机速度为250 m/s。如图7a)所示为输入的骨干网飞行任务航线为拓扑1时，生成的中继段向量为R0,R1,R2,R3，通过本文的中继段向量连接方法得到2条中继节点航线。以拓扑2的骨干网飞行任务航线为输入(拓扑2是在拓扑1的基础上添加了骨干网飞行任务航线5)，进行仿真试验得到图7b)。可以看出，生成的中继段向量为R0,R1,R2,R3,R4，通过本文的中继段向量连接方法得到2条中继节点航线；若按照拓扑1中中继段向量连接方式，将R0,R1,R3连接，则将形成3条中继节点航线，故通过本文基于权重的中继段向量连接方法，能够实现最终生成的中继节点航线个数的优化。

图7 生成树优选试验Fig.7 Test of MST optimization

3.2 性能试验

3.2.1 生成树优选策略

由于生成树优选策略只对添加中继节点个数不超过1的特定拓扑具有优化作用，因此，选取5个典型的拓扑为输入，分别采用传统MST算法和生成树优选策略进行对比试验。其中，RKDL=200 km，RZDL=100 km，航线规划的实际时间间隔为1 000 s，骨干网和子网飞机速度均为250 m/s，试验结果如图8所示，2种算法增加的中继节点个数对比如图9所示。可以看出，本文的生成树优选策略相较MST算法，能够有效减少增加中继节点的数量。

图9 中继节点个数对比Fig.9 Comparison of relay node number

3.2.2 基于权重的中继段向量连接方法

选取5个典型的拓扑为输入，在本文生成树优选策略的基础上，分别采用随机连接中继段向量方法和本文的基于权重的中继段向量连接方法，对中继航线规划进行对比试验。其中，拓扑1的RKDL=600 km，RZDL=600 km，拓扑2,3,4,5的RKDL=600 km，RZDL=500 km，航线规划的实际时间间隔均为1 000 s，骨干网和子网飞机速度均为250 m/s，试验结果如图10所示，2种中继段向量连接方法增加的中继节点个数对比如图11所示。可以看出，本文基于权重的中继段向量连接方法相较随机连接中继段向量方法，能够有效减少增加中继节点的数量。

图10 中继段向量连接方法试验Fig.10 Test of relay segment vector connection method

图11 中继节点个数对比Fig.11 Comparison of relay node number

4 结束语

飞行编队前出必须基于任务进行航线规划，空中分层网络的航线规划需要满足连通性需求，为飞机编队协同完成任务提供通信保障。本文以飞行编队任务航线规划结果为输入，通过在骨干网和子网的任务飞机节点之间添加中继节点的方式，实现空中分层网络的连通性。本文在MST算法的基础上考虑了相邻时刻生成树的变化对中继节点个数的影响，实现了生成树优选；以中继段向量的度和中继节点的飞行时间为权重，达到了将尽量多的中继段向量连接的目的。仿真结果验证了该方法能够有效减少使用的中继节点个数。空中分层网络可能具有各种复杂的拓扑结构，本文的方法只适用于两点之间的中继节点个数不超过1个的特定拓扑的连通性规划，适用性受限。后续研究应当关注在航线之间的距离较远的情况下，如何保障网络连通性并实现解决方案的优化。

[1] 赵悦,陈雷,程子傲,等.车载自组织网络中基于蚁群算法的簇路由协议[J].计算机测量与控制,2016,24(10):259-262. ZHAO Yue,CHEN Lei,CHENG Zi-ao,et al.Ant Colony Algorithm Based Cluster Routing Protocol Vehicular Ad Hoc Network[J].Computer Measurement & Control,2016,24(10):259-262.

[2] 周涛,邢凯,刘刚,等.利用协作通信的中继节点放置问题研究[J].小型微型计算机系统,2013,34(11):2508-2512. ZHOU Tao,XING Kai,LIU Gang,et al.Research on Relay Node Placement via Cooperative Communication[J].Journal of Chinese Computer Systems,2013,34(11):2508-2512.

[3] 黄健文,倪卫明.一种通过加入中继节点以修复大面积网络损坏的能量均衡算法[J].微型电脑应用,2013,29(4):58-61. HUANG Jian-wen,NI Wei-ming.An Energy-Efficient Healing Algorithm for Connectivity Restoration in Wireless Sensor Networks through Relay Node Placement[J].Microcomputer Applications,2013,29(4):58-61.

[4] AZIZ A A,SEKERCIOGLU Y A,FITZPATRICK P,et al.A Survey on Distributed Topology Control Techniques for Extending the Lifetime of Battery Powered Wireless Sensor Networks[J].IEEE Communications Surveys & Tuyorials,2013,15(1):121-144.

[5] NIGAM A,AGARWAL Y K.Optimal Relay Node Placement in Delay Constrained Wireless Sensor Network Design[J].European Journal of Operational Research,2014,233(1):220-233.

[6] Andrew N Kopeikin,Sameera S Ponda,Luke B Johnson,et al.Real-Time Dynamic Planning to Maintain Network Connectivity in a Team of Unmanned Air Vehicles[J].IEEE Globecom Workshops,2011,12(1):1303-1307.

[7] ZHU Han,A Lee Swindlehurst,LIU K J R.Optimization of MANET Connectivity Via Smart Deployment/Movement of Unmanned Air Vehicles[J].IEEE Transactions on Vehicular Technology,2009,58(7):3533-3546.

[8] Ahmed S Ibrahim ,Karim G Seddik,LIU K J R.Connectivity-Aware Network Maintenance and Repair via Relays Deployment[J].IEEE Transactions on wireless communications,2009,8(1):356-366.

[9] Manisha Mishra,XU Han,David Sidoti,et al.Multi-Objective Coordinated Path Planning for a Team of UAVs in a Dynamic Environment:19th ICCRTS,2014[C]∥Command and Control Research Program,Washington D.C,USA,June 16-19,2014:30-45.

[10] 陈凌,梁加红,胡志伟,等.无人飞行器Ad Hoc网络中基于容错的中继节点配置[J].系统工程与电子技术,2012,34(1):179-184. CHEN Ling,LIANG Jia-hong,HU Zhi-wei,et al.Fault Tolerant Relay Node Placement in UAVs Ad Hoc Networks[J].Systems Engineering and Electronics,2012,34(1):179-184.

[11] 徐赞新,袁坚,王钺,等.一种支持移动自组网通信的多无人机中继网络[J].清华大学学报：自然科学版,2011,51(2):150-155. XU Zan-xin,YUAN Jian,WANG Yue,et al.UAV Relay in Network to Provide Communications Mobile Ad Hoc Networks[J].Journal of Tsinghua University:Natural Science ed,2011,51(2):150-155.

[12] 李杰,宫二玲,孙志强,等.航空自组网中面向容错的中继节点速度控制[J].国防科技大学学报,2015,37(4):158-164. LI Jie,GONG Er-ling,SUN Zhi-qiang,et al.Relay Speed Control for Realization of Fault-Tolerant Aeronautical Ad Hoc Networks[J].Journal of National University of Defense Technology,2015,37(4):158-164.

[13] Morteza Romoozi,VAHIDIPOUR S M,Hamideh Babaei.Improvement of Connectivity in Mobile Ad-Hoc Networks by Adding Static Nodes Based on a Realistic Mobility Model[C]∥The Second International Conference on Machine Vision,Washington D.C,USA,December 28-30,2009:138-142.

[14] 张臻,王光磊.基于改进蚁群算法的飞行器航迹规划[J].指挥信息系统与技术,2011,2(3):30-34. ZHANG Zhen,WANG Guang-lei.Aircraft Route Planning Based on Improved Ant Colony Algorithm[J].Command Information System and Technology,2011,2(3):30-34.

[15] 王桂平,王衍,任嘉辰.图论算法理论、实现及应用[M].北京:北京大学出版社,2012:88-109. WANG Gui-ping,WANG Yan,REN Jia-chen. Algorithm Theory,Implementation and Application of Graph Theory[M].Beijing:Peking University Press,2012:88-109.