一种基于BFS的数据链站点优化选址算法

赵延龙，滑 楠，于振华

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

0 引言

目前，针对数据链的研究主要集中在数据链系统建模仿真[1-4]和数据链网络规划[5-7]两方面，然而针对实际中数据链站点优化选址的研究相对较少。文献[8]中提出了一种引入栅格化方法的数据链站点选址方法，通过建立数学模型，将站点优化问题转换为0-1整数规划问题，并通过LINGO软件对具体实例进行编程求解，验证了该方法的可行性。数据链站点选址问题与数据链网络规划问题不同，在文献[9-10]中已被证明是NP难问题，因而当问题的数据规模很大时，在现有的计算条件下很难求得全局最优解。

深度优先搜索算法（Depth First Search，DFS）[11]与广度优先搜索算法（Breadth First Search，DFS）[12]两者相同点都是在计算机应用领域中常用的搜索算法，不同点主要体现在搜索策略方面：DFS算法遵循尽可能深的搜索策略，对于新发现的结点进行优先扩展，一直到某一确定的层为止，如果达不到目标要求则回溯到上一个结点继续搜索，直到全部遍历为止；BFS算法遵循在某一层尽可能宽的搜索策略，深度越小的结点优先进行搜索，然后逐层扩展。

本文采用栅格化思想，综合考虑地理高程信息对电磁信号覆盖范围的影响以及特定标志点等因素，建立数据链站点优化选址的整数规划模型，并提出一种基于BFS的数据链站点选址算法（Data-link Site Optimization Location，DSOL），最后通过具体实例进行验证。

1 数据链站点优化选址模型

传统的数据链站点选址作业往往以人工型、经验型为主，科学性不强，难以充分发挥数据链网络的通信效能。本文从实际出发，采用栅格化的方法对数据链站点选址区域进行划分，综合考虑电磁信号覆盖范围、特定标志点等影响因素建立数学模型。

1.1 区域划分

本文采用文献[9]中栅格化的方法对数据链站点布设区域进行区域划分，如图1所示。

图1 数据链站点布设区域

设东西南北各相隔T km进行采样取点，地球半径为R km，将对应的高程数据放到矩阵M中，最终获得高程矩阵的规模为X×Y，其中：

1.2 电磁信号覆盖范围

数据链地面站装备一般为短波和超短波装备，属于UHF和VHF波段范围内的无线通信装备，主要传播模式为视距传播，因此，在某一具体高空处，电磁信号覆盖范围主要受布设点周围建筑物或地形的影响，这些影响因素归结为受不同地理高程的影响。假设电磁信号有效传播距离为l，信号源为O，信号源在某一方向上且在海拔h处的电磁信号传播示意图如图2所示。

图2 电磁信号传播示意图

图2（a）中，在没有障碍物阻挡时，由勾股定理得，电磁信号在海拔h处的最远有效传播距离为：

图2（b）中，在有障碍物阻挡时，电磁信号在海拔h处的最远有效传播距离取决于不同地理位置处的最高点与信号源O的最大夹角α和β，即：

将电磁信号从信号源O在某一方向上的传播情况拓展到任意方向上即可得到信号源O在海拔h处的电磁信号覆盖范围。

1.3 地球曲率对高程的影响

由于受地球曲率的影响，地球上某一点的实际高程在视距的影响下会有一定的偏差，如下页图3所示。

设B点的实际高程为h；地球半径R=6 400 km；OA与OB的夹角为α；A点到B点最高点处的仰角，即；OA垂直于AB；OC垂直于AC；A点到OB的距离为l，即AC=l，由此得出：

图3 地球曲率对高程影响示意图

将式（11）代入式（10）得：

将式（9）、式（12）代入式（8）得：

由式（7）得：

将式（14）代入式（13）得：

从而求得B点在A点处实际高程为：

1.4 数学模型建立

1.4.1 决策变量设计

xij：取值0或1。当xij=1表示选择点作为数据链站点地址；当xij=0表示不作为数据链站点地址；

Sh：表示需满足在海拔h处的电磁信号覆盖范围。

1.4.2 设计优化目标及约束条件

数据链站点优化选址模型主要从装备数量、布设地点与特定标志点的关系两方面考虑。

1）装备数量尽可能少

其中，X，Y分别表示对保障区域采样后的高程矩阵规模大小。数据链要求在给定高度上空处的航路被电磁信号无缝覆盖，即需满足如下约束条件：

式（18）表示所有布设点处装备电磁波信号覆盖范围必须完全包含航路范围。其中表示即设数据链地面站在海拔h处的电磁信号覆盖范围。

2）布设点尽可能靠近标志点

装备布设点尽可能靠近标志点是指在数据链实际组网建链过程中，为了便于实施保障要求装备在满足电磁信号覆盖范围前提下尽可能靠近路口、光纤接入点、水源等正标志点，以及为了减少对居民生活的辐射影响要求尽可能远离居民点等负标志点。

式（19）中，R表示道路口的个数；rk表示第k个道路口；表示第k个道路口在划分区域内的位置坐标；L表示光纤接入点的个数；lk表示第k个光纤接入点；表示第k个光纤接入点的位置坐标；W表示水源的个数；wk表示第 k个水源；表示第k个水源点的位置坐标；Q表示居民点的个数；qk表示第k个居民点；表示第k个居民点的位置坐标；表示装备布设地点与相应标志点rk之间的距离。分别表示装备布设地点与4种不同标志点之间距离的权值。权值为正表示正标志点，为负则表示负标志点，并且绝对值越大，表示该类标志点对装备布设地点的重要程度就越高。

2 数据链站点选址算法DSOL

在整数规划问题中，最可靠的求解方法为枚举法，这种方法枚举出每一种可行解，最终求出全局最优解，然而枚举法最大的缺陷是当问题的规模较大时，时间复杂度O（2n）将会急剧增大。因此，有学者提出隐枚举法[13]来解决整数规划问题，它的基本思想是忽略不可行组合方案，只检查部分可行组合方案，虽然在一定程度上减少花费时长，但算法时间复杂度仍然为 O（2n）。

数据链站点选址模型中，由于第一个子目标函数为装备尽可能少，即组合方案中“1”的个数尽可能少，因此，模型的规模是动态变化的。DFS算法中，首先需要确定搜索的层数，模型的规模为固定的；而BFS算法是按照层次不断向外扩展，模型的规模是动态变化的，因此，BFS算法更适合数据链站点优化选址模型的求解。

2.1 DSOL算法基本思想

为便于利用BFS算法对优化选址模型进行求解，需要引入覆盖矩阵Pij、判别矩阵Q、距离矩阵Dij以及目标矩阵S。

2.1.1 覆盖矩阵Pij

2.1.2 判别矩阵Q

其中，qij取值0或1。1表示覆盖，0表示未覆盖。

2.1.3 距离矩阵Dij

2.1.4 目标矩阵S

其中，sij取值0或1。1表示覆盖，0表示不覆盖。

DSOL算法的基本思想是从判别矩阵中选择一个非零点o作为初始点；从o点开始按照广度优先依次向外层进行搜索，即在覆盖矩阵中查找与o点相关联且能覆盖目标区域S的其他点；判断在所有已选择点处布设数据链地面站的电磁信号是否满足完全覆盖目标区域S，如果满足，则选择距离特定标志点较近的方案，否则继续搜索。

2.2 DSOL算法实现

依据DSOL算法的基本思想，得到的算法流程图如图4所示。

图4 DSOL算法流程图

3 仿真分析

为验证基于BFS算法的数据链站点优化选址算法DSOL的有效性，本文利用Matlab2016a软件，在硬件环境Intel 3.2 GHz，内存4 GB和软件环境Microsoft Windows 7仿真实验环境条件下对数据链补盲典型案例进行仿真验证。

3.1 数据链补盲典型案例

如图1所示的数据链站点布设区域，假设经过1.1区域划分处理后的区域如下页图5所示。

图5 栅格化后的布设区域

现有XXX型歼击机需在3 km高空处从A（2，7）地经 B（4，2）地飞往 C（8，4）地执行巡逻任务。已知既设数据链地面站布设位置为A、B、C 3点，并且在3 km高空处未能完全覆盖；道路口R1（2，3）、R2（8，2），光纤接入点L（4，5），水源W（5，4），居民点Q（5，1）；，。求需补盲的最少的数据链站点以及在布设区域中相对应的位置。

3.2 计算覆盖矩阵Pij

假设在图5布设区域中的一点X（i，j）处布设数据链地面站后，电磁信号覆盖范围为包含点X在内的周围共9个布设点所在的区域，分为3种情形，分别如式（24）～式（26）所示。

式（24）中，P11表示在布设区域4个角处的电磁信号覆盖情况；式（25）中，P14表示在布设区域4条边上的电磁信号覆盖情况；式（26）中，P45表示在布设区域内部的电磁信号覆盖情况。

3.3 计算判别矩阵Q及目标矩阵S

判别矩阵中的元素qij表示在位置（i，j）处布设数据链地面站时对目标区域的覆盖情况，从图5中分析得出，判别矩阵Q和目标矩阵S分别如式（27）、式（28）所示。

最终通过Matlab2016a仿真平台，采用DSOL算法计算出的布设矩阵：

即所需布设的最少数数据链地面站为3；最优布设方案为（3，4）、（3，7）、（6，3）。算法花费时间为0.012 435 s。

为验证DSOL算法的正确性和有效性，将文献[9]中利用Lingo软件优化数据链站点选址的方法与本文所提的DSOL算法进行对比仿真实验。优化目标为使得f1+f2值最小。程序代码设计为：

仿真结果如图6所示。

图6 Lingo仿真实验结果

通过Lingo软件对数据链补盲案例进行优化，所求得全局最优布设方案为（3，4）、（3，7）、（6，3），最少布设数量为3，与本文所提算法DSOL求解结果一致，从而验证了DSOL求解结果的正确性；DSOL算法求解花费时长为0.012 435 s，而通过Lingo进行求解所需花费时长为1 s，远大于利用DSOL算法进行求解花费的时长，从而验证了DSOL算法在数据链站点优化选址中的有效性。

4 结论

本文通过对数据链站点选址问题进行分析，综合考虑地理高程信息对电磁信号覆盖范围的影响以及特定标志点等因素，建立数据链站点优化选址模型；采用栅格化方法对数据链站点布设区域进行划分，并结合广度优先搜索算法的特点，提出了一种数据链站点选址算法DSOL，算法中引入覆盖矩阵、判别矩阵、距离矩阵，可以快速寻找数据链站点最优布设方案。通过与利用Lingo软件优化数据链站点选址进行对比仿真实验，仿真结果验证了DSOL算法的正确性和有效性。