Abstract: In recent years, natural disasters such as the “7·20 Extraordinarily Heavy Rainstorm in Zhengzhou” and the “9·5 Luding Earthquake” have occurred frequently, causing severe casualties and economic losses. After the disasters, the communication infrastructure was severely damaged, resulting in communication interruptions and affecting emergency rescue operations. In the era of the low-altitude economy, the Unmanned Aerial Vehicle (UAV) equipment technology has developed rapidly. By equipping UAVs with communication devices, temporary communication services can be provided to the disaster-stricken areas, which often have the advantages of strong signals, wide coverage and flexible movement. In this context, how to rationally layout UAV communication base stations after a disaster to maximize the number of demand coverage has become an important decision-making problem faced by emergency command departments.
The layout of UAV communication base stations falls within the category of facility location. The maximum coverage model, as a classic location model, has received widespread attention. The classic maximum coverage model uses a fixed coverage radius to determine the facility’s service area in order to seek the location solution that covers the most demands. The layout of UAV emergency communication base stations can be regarded as an extension of the classic maximum coverage location problem, which expands the problem from a two-dimensional plane to a three-dimensional space and adds the decision of hovering altitude. However, through a literature review, it is found that the existing research on the location of UAV communication base stations mainly focuses on static situations and cannot be applied to the dynamic changes in the emergency rescue environment. Therefore, this paper expands the existing research on the location of UAV communication base stations and further considers the dynamic change characteristics of the location of demand points after a disaster. By constructing a multi-period nonlinear mixed-integer model, an integrated solution to the spatial positioning, movement trajectory, demand allocation and adjustment of the UAV swarm in multiple periods is obtained. To solve this model, an improved genetic algorithm is designed. The improvements of the algorithm are reflected in: (1)improving the initial population generation method based on the distribution of demand points, (2)generating and importing elite individuals in combination with the K-means algorithm and (3)designing a greedy algorithm to achieve demand allocation.
Finally, we compare the solution effects of the genetic algorithm before and after the improvement with the effect of the mathematical software BARON. The results show that: (1)The computing time of the two types of genetic algorithms in solving large-scale problems is significantly less than that of the BARON solver. (2)After the improvement of the genetic algorithm, the error rate decreases from 20% to 4.5%. In addition, in order to verify the feasibility of the model and algorithm in this paper in a real-world scenario, we also conduct a case study based on the “8·8 Jiuzhaigou Earthquake” to obtain the communication base station location and demand allocation plan.

Key words: 3D space, covering location, unmanned aerial vehicles, emergency communication

摘要： 灾后利用无人机搭载通信基站可为灾区提供临时通信保障,通过优化无人机基站布局将有助于提高通信能力。为此,提出一类全新的无人机通信基站覆盖选址问题,该问题将传统“二维平面”覆盖选址问题拓展到“三维空间”,将静态选址问题延伸到多周期情形,并考虑了通信损失、容量约束、飞行距离限制等现实因素。针对该问题,以需求覆盖数量最大为目标,构建一类多周期非线性混合整数模型并设计模型简化方法。针对模型,设计改进遗传算法求解,一是基于需求点分布改进初始种群生成方法,二是结合K-means算法导入精英个体,三是设计贪心算法优化需求分配。最后,以“8·8九寨沟地震”为背景进行算例分析,可获得关于无人机定位、飞行轨迹和需求点分配的集成优化方案。

关键词: 三维空间, 覆盖选址, 无人机, 应急通信