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

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