基于森林火灾热点数据的无人机优化组合调度研究

李梦谣，吴梦青，陈天齐，高欣慧，赵 倩

(曲阜师范大学 工学院，山东 日照 276800)

澳大利亚位于南太平洋和印度洋之间，被海洋包围，陆地面积769.2万km2，但中部约70%的土地位于干旱或半干旱地区，极度缺水和荒凉。世界上绝大多数桉树均在澳大利亚种植，桉树占澳大利亚森林面积的70%。桉树是一种“易燃”树种，叶子富含蜡和油，容易引起森林火灾。澳大利亚著名生物学家和作家杰里米·格里菲斯说，澳大利亚严重的森林火灾是由桉树引起的[1]。

1 研究背景

在每年火灾多发季节，几乎所有州都受到火灾的影响，新南威尔士州和维多利亚州东部受影响最大。2019年10月1日至2020年1月7日澳大利亚东南部的火灾热点见图1。

图1 澳大利亚东南部火灾热点Fig.1 Fire hotspots in southeastern Australia

早在几年前，国家消防局(Country Fire Authority, CFA)就使用监视和态势感知无人机(Surveillance and Situational Awareness, SSA)进行火灾监测，以便紧急行动中心(Emergency Operations Center, EOC)能够最好地指挥前线人员。但是部署人员携带的手持双向无线电传输范围受到低发射功率(通常为5 W)的限制，其标称射程仅为5 km。因此单独的SSA无人机不能完美、快速地监测森林火灾。

搭载中继器无人机的出现解决了SSA无人机射程低的问题。中继器是一种收发机，能以更高的功率自动重播信号，并能扩大无线电信号达20 km的射程，因此可以使用带有中继器的无人机来扩展前线低功率无线电的范围，将火灾信号稳定传送给EOC(图2)。

图2 无人机与紧急行动中心位置关系Fig.2 Location relationship between UAV and Emergency Operations Center

本文根据已知的火灾热点实现无人机的最优调配，并在综合考虑地形因素对传输信号的影响后，实现无人机位置的优化。目前，国内外针对应急情况下无人机的调配和优化选址均有大量研究，并取得一定成果。白俊强等[2]利用蚁群算法提出了适用于航路规划的优化方法，通过无人机的攻击任务航路进行仿真计算，实现有效的线路规划。杨忠振等[3]针对大兴安岭地区森林火灾问题，以所需时间和费用最少为目标，建立多目标优化模型，并用免疫克隆算法进行求解，实现对救援车辆路径的优化调度。在优化选址问题中，苏宇轩[4]在森林防火视频监控点布局上，综合运用地理信息系统(Geographic Information System, GIS)空间分析法、层次分析法(Analytic Hierarchy Process, AHP)等，对监控点进行合理选址和布局，并通过优劣评价优化布局方案。张舒[5]针对森林防火应急物流系统中的服务中心选址问题进行优化研究，提出基于蚁群算法的优化模型，并将优化模型应用到广州市森林防火的具体实际问题中。傅伟等[6]提出一种基于地理位置的无人机包回传分段优化机制，根据路径采取的转发策略设置分段点，优化传输路径。而本文主要采用人工蜂群算法求解出无人机传输信号最短路径，利用GIS空间分析法和免疫优化算法求得无线电中继无人机的最优位置。

2 研究思路

通过采集地形和火灾数据，利用ArcGIS软件描绘当地的地形图和火灾热点分布，提取火灾热点核密度的经纬度坐标，通过人工蜂群算法求得核密度之间的最短路径。以最短路径及设备成本的经济性等限制因素构建多目标线性规划模型，利用该模型计算得到SSA无人机和无线电中继器无人机的最佳数量和组合。最后，分析地形对无人机信号传输的影响，利用GIS空间分析法和免疫优化算法求得优化后无线电中继无人机的最优位置。

3 基于火灾热点的无人机调度方案

3.1 分析思路

Carlos Paradis[7]整理了来自NASA卫星仪器MODIS C6和VIIRS 375 m的澳洲大火数据资料，并发布在Kaggle上。对这些数据进行整理，利用ArcGIS软件绘制出2019年9月至2020年1月澳洲大火的火情地图，得到澳大利亚东南部火灾热点分布及火灾等级，并根据核密度选取了代表性火灾热点(图3)。

图3 澳大利亚东南部代表性火灾热点分布Fig.3 Distribution of representative fire hotspots in southeastern Australia

根据提取的火灾热点，通过人工蜂群算法计算出紧急行动中心到各个着火热点的最短路径。人工蜂群算法是一种基于群智能的随机优化算法。蜜蜂根据各自的分工进行不同的活动，实现蜂群信息的共享和通信，从而为函数的数值优化找到最优解[8]。算法的具体步骤如图4所示。

图4 人工蜂群算法流程Fig.4 Flow chart of artificial bee colony algorithm

无线电中继无人机在多火灾热点的规划问题可描述为：在紧急行动中心位置确定的条件下，设计一种可通过调节无线电中继无人机路径和火灾安全性代价的权重系数来实现SSA无人机和无线电中继无人机最优组合规划的方法，实现无人机费用支出最少的情况下救援火灾热点覆盖的最大化，从而确定出两种无人机数量的最优分配。

根据火灾热点覆盖度建立目标函数f1，由无线电中继无人机飞行距离建立目标函数f2。考虑到火灾热点附近的SSA无人机在无线电中继无人机射程范围内，并保证无线电中继无人机的飞行距离在其能力范围内，目标函数通过分配不同的权重将多目标寻优问题转换为单目标寻优问题。

f=min(-pf1+qf2)

(1)

式中：p和q为权重系数。约束条件包括无线电中继无人机执行飞行任务的能力约束，以及所有无线电中继无人机的路径约束，由此得出无人机的具体数量。

3.2 研究结果

使用多目标线性规划模型计算得到的两种无人机数量，能在保证安全性的情况下，实现经济的最优化。线性规划所得结果如表1所示。

表1 无人机数量Tab.1 Number of UAV

4 考虑地形因素的无人机位置优化

4.1 地形地貌对中继无人机分布的影响

在空旷地或地形起伏不大的环境下，无线电信号强度随着距离的增加而减弱，在某一个距离时信号有增强的趋势并出现峰值，此时信号受干扰的程度最低，随着距离的增加信号强度减小。因此可以在地理空间中应用干扰模型进行无线电中继无人机的布设。

影响野外无线电传输距离的因素主要有发射功率、接收灵敏度和工作频率。在实际应用中，设备的发射功率和工作频率是固定的，实际影响野外无线电传输距离的是接收灵敏度。而接收灵敏度主要受澳大利亚东南部地形地貌的影响。无线电波碰到高地等地形障碍物时，障碍物一般均会对无线电波产生吸收和反射，如果传输路径中地形地貌比较复杂，会显著影响数据传输的距离[9]。因此，地形越复杂，对信号的干扰就越强，故需要对无人机位置进行优化。

4.2 研究方案

结合 GIS 空间分析和免疫算法(Immune Algorithm, IA)，探究无人机选址的优化模型。在进行模型优化的过程中，遗传算法和免疫算法均能对模型进行优化。但是，免疫算法克服了遗传算法寻优过程中的早熟问题，具有良好的收敛速度。因此选择免疫算法来对模型进行进一步优化。

免疫算法[10]与生物免疫系统工作原理类似，算法中的目标函数相当于抗原，目标函数的解集对应抗体，通过评价个体的期望繁殖概率P来确定最优解。期望繁殖概率P的大小与抗体、抗原间亲和力A成正比，与抗体浓度C成反比，意味着适应度高的抗体会被鼓励，而浓度大的个体将被抑制，通过精英保留策略，将高浓度且与抗体适应度A高的个体存入记忆库，避免局部最优，获取全局最优解。

GIS空间分析是一种能够对整个或部分地球表层(包括大气层)空间中的有关地理分布数据进行采集、储存、管理、运算、分析、显示和描述的专业技术。在无线电中继无人机位置的优化过程中，采用GIS空间分析技术对选址影响因子进行空间分析，选出符合条件的无线电中继无人机选址点[11]。

4.3 研究过程与结果

1)建立免疫优化模型

首先根据澳大利亚东南部地形图分析火灾点地形对无线电中继无人机通信的影响，假设无人机数量不变，建立基于免疫算法的选址优化模型，确定无线电中继无人机优化点的位置。具体流程如图5所示。

图5 无线电中继无人机选址优化流程Fig.5 Flow chart of relay UAV site selection optimization

该模型考虑了地形因素对无线电中继无人机通信的影响，使用鲁棒性较高的免疫优化算法对地址进行了重新选取。但由于算法中对无人机以及火灾热点的数量进行了量化，故要进行回代处理，造成了一定的误差。

2)中继无人机选址优化模型算法求解

通过ArcGIS绘制的澳大利亚东南部火灾的热力图，提取出量化后的31个热点信息的坐标：Hotspots=(3525, 937; 3280, 1000; …; 4000, 2700; 3900, 3400)。

在满足约束的条件下，遍历从热力图上提取的所有热点，根据无线电中继无人机量化后的个数，利用免疫优化算法经过100次迭代计算出优化后的选址，优化的结果如图6所示。

图6 免疫算法优化结果Fig.6 Optimization results of immune algorithm

5 总结

通过搜集大量的数据，对澳大利亚东南部近年的火灾勘测数据以及当地地形数据整理、分析和量化。根据SSA无人机和无线电中继无人机之间的配合关系，利用人工蜂群算法、免疫优化算法，分别建立了多目标无人机路径线性规划模型以及无线电中继器无人机选址优化模型，得出SSA无人机与无线电中继无人机最佳组合与考虑地形后的最优选址。本文采用的免疫算法能够抑制优化过程中出现的退化现象，从而保证无人机信号传递的稳定性。但是由于无人机选址优化模型中只考虑地形因素的影响，未考虑其他影响信号传输距离的因素，故模拟情况与实际情况有一定差异。