基于栅格化空域的数据链站点选址优化*

刘宏波，高俊，古尚利

（1.海军工程大学电子工程学院，武汉430033；2.中国船舶重工集团公司第七○九研究所，武汉430205）

基于栅格化空域的数据链站点选址优化*

刘宏波1，高俊1，古尚利2

（1.海军工程大学电子工程学院，武汉430033；2.中国船舶重工集团公司第七○九研究所，武汉430205）

针对对空数据链站点选址优化实际问题，引入栅格化分析方法进行数据链站点的精细化规划和优化，综合考虑站点保障能力、飞行航线、站点建设费用等能力因素，通过栅格化分析方法进行数学建模，将数据链站点选址优化问题转换为0-1整数规划问题，通过案例想定，利用优化软件LINGO进行模型求解，给出了一种栅格化空域的数据链站点优化选址的方法。

栅格法，数据链，LINGO，优化，0-1整数规划

1 概述

目前在对空数据链站点规划建设方面，缺乏对飞机作战任务区域，飞行航线等作战需求的考虑，致使现有站点的分布位置无法满足飞机在任务区域的通信保障需求。同时，随着复杂国际形势的变化，将呈现出空中作战力量越来越多，作战空域越来越复杂的特点，使得现有站点的通信保障能力已不能够满足部队作战需求，迫切需要优化建设数据链站点。

栅格法是1968年由W.E.Howden所提出的方法［1］，指将整个区域分解成具有价值信息的网格单元，然后通过优化算法完成搜索功能［2］；在栅格法上可运用很多成熟算法，例如深度优先算法、遗传算法和蚁群算法等。栅格法在移动机器人运动规划、仿生机器鱼路径规划等方面得到重要应用［3-5］。

数据链站点的选择问题和数据链规划问题不同，数据链网络规划问题是被证明是NP-hard问题［6］，而数据链站点的选择兼顾动态空域配置和空域建模［7］，同时考虑站点建设费用等约束条件，因此，数据链站点选址优化问题综合考虑站点保障能力、飞行航线、站点建设费用等能力因素，结合栅格法，建模成0-1整数规划问题［8-9］。

2 总体思路和方法

2.1 总体思路

以往数据链站点建立时，参考的因素较少，使得建立的站点难以有效保障部队的通信需求。因此，需要找到一种新的方式方法，使得新建的站点能够更好地满足部队通信需求。在新建站点时，采用将空域栅格化的方式，对这些飞行区域进行编号，同时收集部队飞行航线，确定每一个栅格化飞行区域所能保障的航线数，然后根据备选站点保障范围，综合度量各站点的通信保障能力，为站点建设优先顺序有效的决策支持。

数据链站点保障栅格化空域示意图如图1所示。

（1）空域按照一定的标准划分栅格，将空域划分成行号为M个，列号为N个，共计M×N个栅格，对每一个栅格进行编号为aij。

（2）数据链站点采用拟建设的地理位置。

（3）飞行航线采用实际工作的飞行航线，收集的飞行航线越多，分析得越准确。

2.2 空域栅格化方法

栅格化分析方法把区域细化到以平方公里或者更小区域进行规划优化分析的方法［10］，其中最简单的栅格形状是正方形，按照一定规模划分栅格［11］，然后在地图上形成固定的分区，每个栅格都可以用两种方法进行标识：

（1）坐标系法：建立坐标系建模，每个栅格用直角坐标进行唯一表示，如图1所示。

（2）编号法：按照从左到右、从上到下的顺序开始对每个栅格进行编号，每个栅格对应唯一编号。

空域栅格化可以更加贴近数据链的实际需求，可将重点保障区域精细化到指定的部分区域，在站点建设方面有利于保障重点空域，空域栅格化的基本步骤如下：

（1）首先设定栅格大小，栅格大小直接影响栅格分析结果的可靠性和使用性，若栅格设置过小，则无法反映区域性能，只能反映单个数据链站点的性能；若栅格设置过大，则无法准确定位问题点。根据经验，栅格大小可以根据数据链站点间距进行选取。

（2）然后将空域范围转换为墨卡托坐标系的坐标范围，确认需要重点保障的空域范围，实现对栅格空域进行精细化管理。

2.3 站点保障范围与空域叠加方法

站点保障范围与空域叠加原理：首先根据视距通信的特点计算出拟建设站点的保障范围，然后将站点保障范围叠加到空域中，计算保障站点的覆盖空域，并标记该站点保障的空域。基本步骤如下：

（1）计算出数据链站点保障半径r：

式中h1为站点高度，h2为保障空域的高度。

（2）将数据链站点的经纬度通过墨卡托投影到世界坐标系下（x0，y0），根据数据站点保障半径，判断保障范围与栅格空域关系，若保障范围覆盖该空域则进行标记。

2.4 飞行航线与栅格空域叠加关联方法

为了统计栅格空域的实际使用需求，在确定空域栅格后，尽量多地收集飞行航线，收集的航线越多，实际需求分析得越准确，然后按照一定的关联方法，将航线到整个空域进行关联，并标记经过的空域，从而确认空域的重要性。航线与栅格空域关联的基本步骤如下：

（1）将航线映射到墨卡托坐标系下。

（2）判断航线与栅格空域的位置关系，与相交的栅格空域做标记。

（3）依次将所有航线按进行计算，统计所有栅格空域包含的航线条数，航线条数取值取决于收集的航线信息，取值越大表示空域的重要程度越高。

2.5 站点费用估算方法

费用估算是根据一定的文字资料和图纸资料，就拟制的工程项目，通过一定的人类脑力活动的分工与合作，用报表的形式，把费用的开发费用数字计算出来。费用估算受多种因素影响，包括国家政策、价格因素等因素影响，费用估算的计算方法可以根据建筑指标法、测算法、专业归类法等方法进行估算［12］。

3 站点保障能力综合评定

为了综合评定站点对栅格化空域的保障能力，根据问题分析和模型假设，在考虑投资有最高上限的约束条件下，模型I求解站点覆盖面积最大，模型II求解站点覆盖栅格价值最大。

3.1 数学模型建立

（1）引入覆盖矩阵Bk，定义bkij（其中1≤k≤K）为第k个站点对第aij栅格的覆盖情况，若覆盖为值1，未覆盖值为0；

（2）引入栅格价值矩阵D，定义dij为栅格内保障飞行航线的数量，取值越大表示空域的重要程度越高；

（3）引入站点建设矩阵C，定义ci为数据链站点是否建设，若建设为1，否则为0。

3.2 目标I

投资建设数据链站点的最大覆盖面积：

约束条件：

式中：Mi为第i个数据链站点的建设费用，H为数据链站点建设的总费用，OR表示或的关系。

3.3 目标II

求解建设数据链站点的覆盖栅格价值最大，即保障飞行航线数量最多：

约束条件：

式中：Mi为第i个数据链站点的建设费用，H为数据链站点建设的总费用，OR表示或的关系。

4 案例分析

4.1 案例想定

案例想定：准备在一个区域开展数据链站点建设，该区域由5×5个栅格组成，每个栅格100 km× 100 km，假设有4个位置具备建设条件，每个站点计划覆盖3 000 m高度的空域，保障半径r=200 km，初步设想如图1所示。同时，假设计划投资300万元，每个站点的建设费用如表1所示，求解建设哪些数据链站点保障覆盖栅格价值最大。

表1 每个站点建设费用

用最优化方法解决决策问题包括两个基本步骤：首先，需要把实际决策问题用数学建模的方法建立优化模型；其次，选择利用优化方法和工具求解模型。

4.2 初步分析

（1）分析每个站点覆盖的栅格，如表2所示。

（2）根据每个栅格内保障飞行航线的数量，得到栅格价值矩阵D。

表2 每个站点覆盖的栅格情况

4.3 利用LINGO编程求解

利用LINGO工具求解优化模型，其中LINGO是美国LINDO系统公司推出的求解最优化问题专业软件包，优势在于求解各种大型线性、非线性和整数规划方面。数学求解公式如3.3所示，可利用LINGO编程求解，关键代码如表3所示。

表3 LINGO编程求解程序摘要

通过LINGO 11.0软件运行后，仿真界面如图2所示，包括求解状态（Solver Status）、扩展求解状态（Extended Solver Status）、变量数量（Variables）、约束数量（Constraints）、非零系数数量（Nonzeroes）、内存使用量（Generator Memory Used）、已运行时间（E-lapsed Runtime）。运行结果显示该案例想定是整数线性优化（ILP）、全局优化算法（Global Opt）问题，采用分支定界法（B-and-B），仿真结果为：建设站点1、站点2和站点3，最佳目标函数值是12。

图2 仿真结果界面

5 结束语

针对对空数据链站点选址优化实际问题，综合考虑站点保障能力、飞行航线、站点建设费用等能力因素，通过栅格化分析方法进行数学建模，将数据链站点选址优化问题转换为0-1整数规划问题。通过求解建设数据链站点保障覆盖栅格价值最大的案例想定，并利用优化软件LINGO进行模型优化求解，验证了栅格化空域方法的可行性。采用空域栅格化方法，在数据链站点在建设和规划方面，能够更加贴近实际需求；同时，结合飞机航线的实际情况，可更好地提高数据链站点的服务质量。

［1］夏梁盛，严卫生.基于栅格法的移动机器人运动规划研究［J］.计算机仿真，2012，29（12）：229-232.

［2］王晓林.基于栅格法的仿生机器鱼路径规划研究［D］.天津：天津大学，2010.

［3］孙璐.基于栅格法的三维六面体网格自适应生成算法及优化技术研究［D］.济南：山东大学，2012.

［4］王伟峰，吴勇超，张旭，等.基于栅格法的移动机器人单元分解遍历方法研究［J］.自动化技术与应用，2013，32（11）：34-38.

［5］司马文霞，李永福，杨庆，等.改进网格法及其在雷电参数统计中的应用［J］.高电压技术，2012，38（8）：1834-1841.

［6］司小江，吴礼发，胡谷雨.数据链规划问题的贪心算法［J］.国防科技大学学报，2013，25（6）：45-49.

［7］张晨，胡明华，张进.基于管型空域配置的交通复杂性管理［J］.系统管理学报，2012，21（5）：327-335.

［8］夏军，庞征斌，张峻，等.一种基于0_1整数规划的全局数据分布优化方法［J］.国防科技大学学报，2009，31（4）：62-67.

［9］朱利民，边计年，周强，等.基于整数规划的层次式FPGA布线算法［J］.计算机辅助设计与图形学学报，2010，20（10）：1687-1693.

［10］陈磊，江俊敏，袁汶雯.自动栅格化工具的实现及其在网规网优中的应用［J］.邮电设计技术，2010（12）：49-52.

［11］张慧文，鲍广宇，张义.栅格化网络态势感知能力评估模型［J］.指挥控制与仿真，2013，35（2）：9-12.

［12］赵源.开发商拟建项目建设费用估算谈［J］.建筑经济，2007（7）：252-255.

Research on Location Optimization of Data Link Site Based on Grid Airspace

LIU Hong-bo1，GAO Jun1，GU Shang-li2
（1.School of Electronics Engnieering，Naval University of Engineering，Wuhan 430033，China；
2.The 709th Research Institute，China Shipbuilding Industry Corporation，Wuhan 430205，China）

For the practical problem of optimizing the air data link site，this paper uses rasterized analysis method to carefully plan the data link site and optimize the comprehensive support capability，flight line and cost of building site.Translating the problem of location optimization of data link site to 0-1 Integer programming one，after carefully analyzing the cases，it conducts mathematical modeling with rasterized analysis method and solves the model with optimization software LINGO.Furthermore，the paper puts forward a location optimization of rasterized air data link site.

grid method，data link，LINGO，optimization，0-1 integer programming

TJ630

A

1002-0640（2015）12-0018-04?

2014-11-26

2015-01-05

国家自然科学基金（61372165）；国家“863”计划基金资助项目（2013AA7026058）

刘宏波（1979-），男，黑龙江齐齐哈尔人，博士生。研究方向：无线通信、网络通信。