CN119676718A

CN119676718A - Method and device for optimizing coordinated deployment of multiple UAV base stations under building obstacles

Info

Publication number: CN119676718A
Application number: CN202411599319.0A
Authority: CN
Inventors: 石建迈; 靳晓洁; 陈超; 黄魁华; 刘忠; 黄金才; 程光权; 范长俊
Original assignee: National University of Defense Technology
Current assignee: National University of Defense Technology
Priority date: 2024-11-11
Filing date: 2024-11-11
Publication date: 2025-03-21
Anticipated expiration: 2044-11-11
Also published as: CN119676718B

Abstract

The embodiment of the invention provides a multi-unmanned aerial vehicle base station collaborative deployment optimization method and device under the condition of building obstacle, and the method comprises the steps of randomly distributing position coordinates in a candidate space for all unmanned aerial vehicles for a plurality of times to obtain a plurality of solutions, calculating the number of users of all unmanned aerial vehicles in the solutions as corresponding fitness values of the solutions according to each solution, sequencing all the solutions according to ascending sequences of the corresponding fitness values to obtain solution sequences, taking the solution with the largest fitness value in the solution sequences as a global optimal solution and the corresponding fitness value as the global optimal fitness value, carrying out cyclic iteration update on the solutions based on an improved biological geography optimization algorithm, sequencing the solutions according to the updated fitness values, updating the global optimal solution and the global optimal fitness value according to the obtained sequences, stopping iteration until the iteration times reach the maximum iteration times or the continuous non-improvement times, and using the global optimal solution for collaborative deployment of the multi-unmanned aerial vehicle base station.

Description

Multi-unmanned aerial vehicle base station collaborative deployment optimization method and device under condition of building obstacle

Technical Field

The invention relates to the technical field of unmanned aerial vehicles, in particular to a multi-unmanned aerial vehicle base station collaborative deployment optimization method and device under the condition of building obstacle.

Background

The rapid development of the technology of the internet of things has made the internet of things a key infrastructure of modern society, and the wide application of the internet of things in the fields of daily life and industry has highlighted the urgent need for a robust and flexible temporary network system. However, the inability of conventional network infrastructure to cope with bursty network demands in emergency communication scenarios such as disaster response and military operations, highlights the necessity of adopting innovative solutions to meet temporary network demands.

The unmanned aerial vehicle base station provides an innovative solution for emergency communication by virtue of the characteristics of economy, high efficiency and quick response. The low cost nature makes it more readily available to form a wide range of deployments during critical periods of disaster response and the like. The agility feature allows it to be deployed quickly to areas that are far away, providing immediate network access to the user. Meanwhile, the unmanned aerial vehicle base station can be deployed at a lower height, and a visible line link is easily established with a ground user, so that high-quality communication is provided. These advantages make it an ideal choice to restore or enhance network coverage when ground facilities are damaged or overloaded.

Determining the optimal deployment location of the drone base station is a critical and complex challenge. As a major obstacle in urban environments, buildings not only occupy the deployment space of the unmanned aerial vehicle, but also are key elements that hinder communication signals propagation between the unmanned aerial vehicle base station and users. Thus, the type of communication link between the drone base station and the user needs to be determined according to whether it is blocked by the building, and if so, is an invisible line of sight link, otherwise is an visible line of sight link. The deployment of a limited unmanned base station to provide maximum coverage for randomly distributed users is necessary in situations where resources are limited. By ensuring that the unmanned aerial vehicle base station remains doubly-connected with other unmanned aerial vehicle base stations, a robust unmanned aerial vehicle network can be realized, which is beneficial to dealing with the damage of potential threats to the unmanned aerial vehicle network.

Many scholars have studied the multi-drone base station deployment problem. However, most current research on deployment of unmanned aerial vehicle base stations relies on statistical channel models with standard building distributions, and cannot capture the communication link blockage caused by the actual building distribution in different environments. More importantly, the optimization problem of unmanned aerial vehicle deployment is a leading edge application of facility site selection problems, and modeling is generally performed based on a maximum coverage position problem (Maximum Covering Location Problem, MCLP) model by combining consideration of unmanned aerial vehicle communication characteristics, and key constraints include deployment height, service capacity, user allocation and connectivity among unmanned aerial vehicles. However, maintaining a dual connection for each drone to form a robust drone network has not been sufficiently studied. Therefore, there is an urgent need to study new unmanned aerial vehicle deployment methods, taking into account building obstructions and robust unmanned aerial vehicle networks.

In carrying out the present invention, the applicant has found that at least the following problems exist in the prior art:

How to deploy unmanned aerial vehicle network base stations in a multi-building obstacle environment so as to enable the unmanned aerial vehicle network to reach the maximum coverage range.

Disclosure of Invention

The embodiment of the invention provides a multi-unmanned aerial vehicle base station collaborative deployment optimization method and device under the condition of building obstacle, which solve the problem of how to deploy unmanned aerial vehicle network base stations under the environment of multi-building obstacle so as to enable an unmanned aerial vehicle network to reach the maximum coverage range.

In order to achieve the above objective, in one aspect, an embodiment of the present invention provides a method for optimizing cooperative deployment of multiple unmanned aerial vehicle base stations under a building obstacle condition, including:

randomly distributing position coordinates for all unmanned aerial vehicles in a candidate space for a plurality of times to obtain a plurality of solutions, wherein each solution comprises the position coordinates of all unmanned aerial vehicles;

For each solution, calculating the number of users of all unmanned aerial vehicles in the solution according to the position coordinates of all unmanned aerial vehicles in the solution and preset user coordinates of a plurality of users, and taking the number of users of all unmanned aerial vehicles in the solution as the corresponding fitness value of the solution;

sequencing all solutions according to ascending sequences of the corresponding fitness values to obtain solution sequences, taking the solution with the largest fitness value in the solution sequences as a global optimal solution, and taking the fitness value corresponding to the global optimal solution as a global optimal fitness value;

And carrying out cyclic iteration update on the solutions based on an improved biological geography optimization algorithm, sorting the solutions according to the updated fitness value when the solutions are subjected to the iterative update, and updating the global optimal solution and the global optimal fitness value according to the obtained sorting until the cyclic iteration number reaches the preset maximum iteration number or the continuous non-improvement number reaches the preset maximum continuous non-improvement number, wherein the obtained global optimal solution is used for collaborative deployment of a plurality of unmanned aerial vehicle base stations, and the obtained global optimal fitness value is the number of users which can be served after collaborative deployment of the plurality of unmanned aerial vehicle base stations is carried out according to the obtained global optimal solution.

On the other hand, the embodiment of the invention provides a multi-unmanned aerial vehicle base station collaborative deployment optimizing device under the condition of building obstacle, which is characterized by comprising the following components:

The system comprises an initial solution determining module, a calculation module and a calculation module, wherein the initial solution determining module is used for randomly distributing position coordinates for all unmanned aerial vehicles in a candidate space for a plurality of times to obtain a plurality of solutions, and each solution comprises the position coordinates of all unmanned aerial vehicles;

The fitness value determining module is used for calculating the number of users of all unmanned aerial vehicles in the solutions according to the position coordinates of all unmanned aerial vehicles in the solutions and preset user coordinates of a plurality of users for each solution, and taking the number of users of all unmanned aerial vehicles in the solutions as the fitness value corresponding to the solutions;

The global optimal determining unit is used for sorting all solutions according to ascending order of the corresponding fitness values to obtain solution sorting, taking the solution with the largest fitness value in the solution sorting as a global optimal solution, and taking the fitness value corresponding to the global optimal solution as a global optimal fitness value;

And the global optimal iteration unit is used for carrying out cyclic iteration update on the solutions based on an improved biological geography optimization algorithm, sequencing the solutions according to the updated fitness value when the solutions are subjected to each iteration update, updating the global optimal solution and the global optimal fitness value according to the obtained sequencing, stopping iteration until the cyclic iteration number reaches the preset maximum iteration number or the continuous non-improvement number reaches the preset maximum continuous non-improvement number, and obtaining the global optimal solution for the collaborative deployment of the multi-unmanned aerial vehicle base stations, wherein the obtained global optimal fitness value is the number of users which can be served after the collaborative deployment of the multi-unmanned aerial vehicle base stations is carried out according to the obtained global optimal solution.

The technical scheme has the following beneficial effects that the solution deployed by the unmanned aerial vehicle is circularly iterated and updated to update the global optimal solution through the improved biological geography optimization algorithm, so that the effective collaborative deployment of the base stations of the unmanned aerial vehicle considering the building obstacle can be realized. The scheme not only can generate an optimal result, but also can show a faster convergence speed, and is more suitable for solving the collaborative deployment optimization problem of the base stations of the multiple unmanned aerial vehicles.

Drawings

In order to more clearly illustrate the embodiments of the invention or the technical solutions in the prior art, the drawings that are required in the embodiments or the description of the prior art will be briefly described, it being obvious that the drawings in the following description are only some embodiments of the invention, and that other drawings may be obtained according to these drawings without inventive effort for a person skilled in the art.

FIG. 1 is a flow chart of a method for optimizing cooperative deployment of multiple unmanned aerial vehicle base stations in the event of a building obstacle in accordance with one embodiment of the present invention;

FIG. 2 is a block diagram of a multi-unmanned base station co-deployment optimization device in the event of a building obstacle in accordance with one embodiment of the present invention;

FIG. 3 is a schematic view of a deployment of unmanned aerial vehicle base stations taking into account building obstructions in one embodiment of the invention;

Fig. 4 is a schematic diagram of Los links and NLoS links between a base station of a drone and a user according to one embodiment of the present invention;

FIG. 5 is a schematic diagram of a straddle method according to one embodiment of the present invention;

FIG. 6 is a two-dimensional plan view of the North Star delta region of one embodiment of the present invention;

FIG. 7 is a schematic diagram of a simulated distribution of North Star delta buildings and users in accordance with one embodiment of the present invention;

FIG. 8 is a three-dimensional optimal deployment result solved by the RD+BBO method according to one embodiment of the present invention;

FIG. 9 is a two-dimensional optimal deployment result solved by the RD+BBO method according to one embodiment of the present invention;

FIG. 10 is a three-dimensional optimal deployment result solved by a KMC+BBO method according to one embodiment of the present invention;

FIG. 11 is a two-dimensional optimal deployment result solved by a KMC+BBO method according to one embodiment of the present invention;

FIG. 12 is a convergence curve of RD+BBO and KMC+BBO methods according to one embodiment of the present invention;

Fig. 13 is a schematic diagram of a drone providing wireless services according to one embodiment of the present invention.

Detailed Description

The following description of the embodiments of the present invention will be made clearly and completely with reference to the accompanying drawings, in which it is apparent that the embodiments described are only some embodiments of the present invention, but not all embodiments. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.

With the rapid development of the technology of the Internet of things, the technology of the Internet of things is increasingly widely applied to social life and industrial production, and higher requirements are put on the robustness and flexibility of network infrastructures. In particular, in emergency situations such as disaster response, limitations of the conventional network are prominent, and innovative solutions are needed to meet the temporary network demands. Unmanned aerial vehicles carry mobile base stations and are becoming an effective means for providing network services in emergency situations due to the characteristics of low cost and rapid deployment. One key challenge is how to deploy a limited unmanned base station, maximizing coverage for ground users, taking into account building obstructions and unmanned network robustness. In view of the shielding of urban buildings to wireless signals, a binary channel model is adopted to divide a communication link between a user and a base station of an unmanned aerial vehicle into a visible line link or a non-visible line link. Under the condition of considering capacity, coverage range and double-connectivity constraint, the problem of collaborative deployment optimization of the base stations of the multiple unmanned aerial vehicles is solved. Based on the characteristics of the unmanned aerial vehicle cluster, an improved biophysical optimization algorithm is designed to solve the problem. Finally, a practical case is applied to verify the validity of the proposed method.

The embodiment of the invention solves a key challenge of how to deploy a limited number of unmanned aerial vehicle base stations to achieve maximum coverage under the conditions of building obstacle and unmanned aerial vehicle network robustness. Depending on whether there is an obstacle occlusion between the drone and the user, the communication links may be divided into Line of Sight (LoS) and Line of Sight (Non Line of Sight, NLoS). And establishing a collaborative deployment optimization problem of the base stations of the multiple unmanned aerial vehicles based on MCLP, and considering user coverage and double-connection constraint of the unmanned aerial vehicles. By utilizing the intelligence of the unmanned aerial vehicle cluster, an improved biological geography optimization algorithm is designed, and an actual case is applied to verify the effectiveness of the unmanned aerial vehicle cluster. Unmanned aerial vehicle is abbreviated as unmanned aerial vehicle basic station in this patent commonly used.

On the one hand, as shown in fig. 1, an embodiment of the present invention provides a method for optimizing cooperative deployment of multiple unmanned aerial vehicle base stations under a building obstacle condition, including:

Step S10, randomly distributing position coordinates for all unmanned aerial vehicles in a candidate space for a plurality of times to obtain a plurality of solutions, wherein each solution comprises the position coordinates of all unmanned aerial vehicles;

Step S11, calculating the number of users of all unmanned aerial vehicles in each solution according to the position coordinates of all unmanned aerial vehicles in the solution and preset user coordinates of a plurality of users, and taking the number of users of all unmanned aerial vehicles in the solution as an adaptability value corresponding to the solution;

step S12, sorting all solutions according to ascending order of the corresponding fitness values to obtain a solution sorting, taking the solution with the largest fitness value in the solution sorting as a global optimal solution, and taking the fitness value corresponding to the global optimal solution as a global optimal fitness value;

And S13, carrying out cyclic iteration update on the solutions based on an improved biological geography optimization algorithm, sequencing the solutions according to the updated fitness value when the updated fitness value of the solutions is obtained, and updating the global optimal solution and the global optimal fitness value according to the obtained sequencing until the cyclic iteration number reaches the preset maximum iteration number or the continuous non-improvement number reaches the preset maximum continuous non-improvement number, wherein the obtained global optimal solution is used for collaborative deployment of a plurality of unmanned aerial vehicle base stations, and the obtained global optimal fitness value is the number of users which can be served after collaborative deployment of the plurality of unmanned aerial vehicle base stations according to the obtained global optimal solution.

The embodiment of the invention has the following technical effects that the solution for deployment of unmanned aerial vehicles (unmanned aerial vehicles are provided with base stations for wireless communication with users) is circularly iterated and updated to globally optimal solution through an improved biological geography optimization algorithm, so that the effective collaborative deployment of the base stations of the unmanned aerial vehicles considering building obstacles can be realized. The scheme not only can generate an optimal result, but also can show a faster convergence speed, and is more suitable for solving the collaborative deployment optimization problem of the base stations of the multiple unmanned aerial vehicles.

Further, the distributing position coordinates for all the unmanned aerial vehicles randomly in the candidate space for multiple times to obtain multiple solutions, wherein each solution comprises the position coordinates of all the unmanned aerial vehicles, and the method comprises the following steps:

The method comprises the steps of obtaining space information of an environment space, namely, rasterizing the environment space into a plurality of vertically arranged square grids to obtain a grid set of a building and a grid set of a candidate space in the environment space, wherein the grid set comprises the plurality of square grids;

three-dimensional position coordinates of all the drones in each solution are generated in a random manner within the grid set of candidate spaces, and/or,

Generating horizontal coordinates of all unmanned aerial vehicles in a candidate space by using a k-means clustering method, and randomly determining the height coordinates of all unmanned aerial vehicles in a preset candidate space height range, wherein the position coordinates of the unmanned aerial vehicles are central coordinates of a cubic grid occupied by the unmanned aerial vehicles, and the position coordinates comprise the horizontal coordinates and the height coordinates.

The method for generating horizontal coordinates of all unmanned aerial vehicles in the candidate space by using the k-means clustering method specifically comprises the following steps:

According to horizontal coordinates in preset user coordinates of a plurality of users, k-means clustering is carried out on the plurality of users to obtain horizontal coordinates of a plurality of class centers, and the horizontal coordinates of the plurality of class centers are respectively used as horizontal coordinates of a plurality of unmanned aerial vehicles;

The horizontal coordinates are generated based on user clusters, the class center is used as the horizontal coordinates of the unmanned aerial vehicle, compared with the random method, the method has the advantages that the initial solution is randomly generated in the whole space, the k-means clusters limit the space range generated by the initial solution, and the optimal coverage is theoretically closer. Therefore, the initial solution generated based on k-means clustering has higher quality and is closer to global optimum;

randomly determining the height coordinates of all unmanned aerial vehicles in a preset candidate space height range, wherein the method comprises the following steps:

for each unmanned aerial vehicle, determining a height range of the unmanned aerial vehicle according to the path loss (under LoS and nLoS links) between the unmanned aerial vehicle and a user, wherein the path loss is not greater than a preset loss threshold value and the maximum radius which can be covered by the receiving and transmitting power of the unmanned aerial vehicle, and distributing height coordinates for the unmanned aerial vehicle randomly in the obtained height range;

For each unmanned aerial vehicle, an optimal deployment height corresponding to the maximum coverage radius of the unmanned aerial vehicle can be determined based on a probability statistical channel model, the optimal deployment height is taken as a center, the upper limit and the lower limit of the height of the random selection range of the height coordinates of the unmanned aerial vehicle are determined, the upper limit of the height is equal to the optimal deployment height plus a preset upward offset value, the lower limit of the height is equal to the optimal deployment height minus the preset downward offset value, and the probability statistical channel model means that the path loss between the unmanned aerial vehicle and a user is respectively formed by LoS and nLoS links with a certain fixed probability. The path loss depends on building related environmental parameters, distance between the drone and the user, and elevation angle. Users typically have minimum requirements for quality of service, which can be expressed in terms of path loss. If a certain path loss threshold is given, a nonlinear implicit function of the service height with respect to the coverage radius can be obtained through simplification, and the optimal service height (optimal deployment height) corresponding to the maximum coverage radius can be obtained through deviation derivation. The connection of the drone to the user is propagated through an air-to-ground channel. The air-to-ground channel model is formed by LoS and nLoS links with a certain probability respectively, so the path loss from the unmanned aerial vehicle k to the user i can be expressed as formula (1):

L(h,d_ik)＝L_LoS×P(L_LoS,θ_ik)+L_nLoS×P(L_nLoS,θ_ik) (1)

the probability of LoS links depends on building density, proportion of building area, and positions of the unmanned aerial vehicle and the user, etc., and can be expressed as formula (2):

Where a and b are constant coefficients determined by the environment (suburban, urban, dense urban, high building urban, etc.), For the elevation angle from the unmanned aerial vehicle k to the user i, h is the height of the unmanned aerial vehicle, and d _ik is the distance from the user i to the circle center of the coverage circle of the unmanned aerial vehicle k, as shown in fig. 13. The probability of nLoS link is then formula (3):

P(nLoS,θ_ik)＝1-P(LoS,θ_ik) (3)。

The path loss of LoS and nLoS links can be expressed as equation (4) and equation (5), respectively:

where ηlos and ηnlos are the average parasitic losses of LoS and nLoS, respectively, f _c is the carrier frequency of the air-to-ground channel and c is the speed of light.

Then, equation (1) can be simplified to equation (6):

Under the condition of presetting a given path loss threshold L (h, d _ik), the formula (6) is a nonlinear hidden function of the height of the unmanned aerial vehicle with respect to the distance from the user to the circle center of the unmanned k coverage circle. By deriving the bias of equation (6), the inflection point of the function, i.e., the optimal height (optimal deployment height) H, and the maximum value of d _ik, i.e., the maximum coverage radius R, can be found.

Further, for each solution, according to the position coordinates of all the unmanned aerial vehicles in the solution and the preset user coordinates of the plurality of users, calculating the number of users of all the unmanned aerial vehicle services in the solution, and taking the number of users of all the unmanned aerial vehicle services in the solution as the fitness value corresponding to the solution, including:

For each solution, calculating whether building shielding exists between each user and each unmanned aerial vehicle in the solution according to preset user coordinates of each user, position coordinates of each unmanned aerial vehicle in the solution and space information of all buildings in an environment space, wherein the space information of the buildings comprises the position coordinates, length, width and height of the buildings;

for each user, calculating NLoS received power obtained by the user from the unmanned aerial vehicle with building shielding for the link between the unmanned aerial vehicle with building shielding for the user, and calculating LoS received power obtained by the user from the unmanned aerial vehicle without building shielding for the link between the unmanned aerial vehicle without building shielding for the user;

for each user, the user is distributed to all NLoS receiving power of the user and unmanned aerial vehicles corresponding to the maximum value in the LoS receiving power to provide service;

And counting the total number of users of all unmanned aerial vehicles in each solution, serving as the corresponding fitness value of the solution.

Further, for each solution, according to preset user coordinates of each user, position coordinates of each unmanned aerial vehicle in the solution, and space information of all buildings in an environment space, calculating whether building shielding exists between each user and each unmanned aerial vehicle in the solution, including:

determining whether building shielding exists between each unmanned aerial vehicle and a user by using a straddling method in a calculation geometry;

the straddling method judges whether two line segments are intersected by utilizing mathematical properties of vector cross multiplication and dot multiplication, and specifically comprises the following steps that the intersecting requirement of the line segments P ₁P₂ and Q ₁Q₂ is two:

condition one:

Wherein, Deriving a vectorSum vectorThe direction of the cross product vector is chosen,Deriving a vectorSum vectorThe direction of the vector of the cross product can only lead the line segment P ₁P₂ to cross the line segment Q ₁Q₂ if the dot product of the two result vectors is larger than 0;

Condition II:

The second condition is that the line segment Q ₁Q₂ is distributed on two sides of the line segment P ₁P₂;

If the two conditions are met at the same time, the line segment P ₁P₂ is intersected with the line segment Q ₁Q₂, and then it can be judged that building shielding exists between the unmanned aerial vehicle and the user.

In a specific application, the line segment P ₁P₂ refers to a connection line of the user and the unmanned plane projected on the bottom surface, and the line segment Q ₁Q₂ refers to four sides of the bottom surface of the building.

Further, the calculating the NLoS received power of the user obtained from the unmanned aerial vehicle with building shielding, for the link between the unmanned aerial vehicle with the user without building shielding, and the calculating the LoS received power of the user obtained from the unmanned aerial vehicle without building shielding specifically includes:

based on the binary channel model, the power loss of the air-to-ground communication is calculated by the following formula:

PL_LoS＝20lg(d_ij)+20lg(f_c)+η_LoS (9)

PL_NLoS＝20lg(d_ij)+20lg(f_c)+η_NLoS (10)

Wherein f _c is the carrier frequency, d _ij is the distance between user i and unmanned plane j, and eta _LoS and eta _NLoS respectively represent the additional path power loss under the link state LoS and NLoS, eta _LoS＝92.4,η_NLoS＝92.4+L_s, and the additional random path loss under the building shielding condition Normrnd (μ, σ) represents a normal distribution, θ _ij is the elevation angle of user i to drone j, g _μ、g_σ、h_μ、h_σ、i_μ、i_σ is an empirical parameter;

the NLoS received power and the LoS received power are calculated by the following formulas:

P_LoS＝P_t-PL_LoS (11)

P_NLoS＝P_t-PL_NLoS (12)

Wherein, P _t is unmanned plane transmission power, PL _LoS and PL _NLoS respectively represent path loss under LoS and NLoS links, and P _LoS and P _NLoS respectively represent LoS reception power and NLoS reception power of a user under the condition that link states are LoS and NLoS.

Further, the method for optimizing the biological geography based on the improvement comprises the steps of carrying out cyclic iteration update on the solutions, sorting the solutions according to the updated fitness value when the solutions are subjected to each iteration update, updating the global optimal solution and the global optimal fitness value according to the obtained sorting, stopping iteration until the cyclic iteration number reaches the preset maximum iteration number or the continuous non-improvement number reaches the preset maximum continuous non-improvement number, and using the obtained global optimal solution for collaborative deployment of a plurality of unmanned aerial vehicle base stations, wherein the obtained global optimal fitness value is the number of users which can be served after collaborative deployment of the plurality of unmanned aerial vehicle base stations according to the obtained global optimal solution, and comprises the following steps:

Initializing elite rate, determining the number of reserved solutions and the number of updated solutions in each iteration according to the elite rate and the total number of preset solutions, and setting a preset mutation probability p _M;

the following iteration loop is executed until the maximum number of iterations is reached, or the number of consecutive no improvement times reaches the maximum number of consecutive no improvement times, the iteration is stopped:

According to the solution sequence of all solutions, taking the solution with high fitness value and the number of reserved solutions as the solution with unchanged reservation in all solutions, and taking the solution with low remaining fitness and the number of updated solutions as the solution to be updated in all solutions;

executing migration operation on each solution in solutions to be updated, and updating the solutions to be updated;

Executing mutation operation on the solution to be updated after the migration operation is executed, and updating the solution to be updated;

evaluating and correcting all solutions based on connectivity constraints, wherein the connectivity constraints are used for constraining each unmanned aerial vehicle to at least have two neighbor unmanned aerial vehicles, and the neighbor unmanned aerial vehicles are unmanned aerial vehicles with a distance smaller than a preset neighbor distance threshold;

Calculating the number of users of all unmanned aerial vehicles in the solution according to the position coordinates of all unmanned aerial vehicles in the solution and preset user coordinates of a plurality of users for each solution, and updating the fitness value corresponding to the solution by using the number of users of all unmanned aerial vehicles in the solution;

Updating the solution sequence according to the ascending sequence of the updated fitness value of each solution, updating the global optimal solution by using the solution with the largest fitness value in the solution sequence, and updating the global optimal fitness value by using the fitness value corresponding to the global optimal solution;

And when iteration is stopped, outputting the global optimal solution and the global optimal fitness value.

The method includes, for each solution, calculating the number of users of all unmanned aerial vehicles in the solution according to the position coordinates of all unmanned aerial vehicles in the solution and the preset user coordinates of a plurality of users, updating the fitness value corresponding to the solution by using the number of users of all unmanned aerial vehicles in the solution, and referring to each solution in the foregoing embodiment, calculating the number of users of all unmanned aerial vehicles in the solution according to the position coordinates of all unmanned aerial vehicles in the solution and the preset user coordinates of a plurality of users, and taking the number of users of all unmanned aerial vehicles in the solution as an explanation of the fitness value corresponding to the solution.

Further, performing a migration operation on each solution in the solutions to be updated, and updating the solutions to be updated includes:

Setting mobility and migration rate for all solutions according to the solution sequence of all solutions, wherein the mobility corresponding to the solution with large fitness value is large, the mobility and migration rate are both smaller than or equal to 1, and the sum of the mobility and migration rate of the same solution is 1;

Generating a first random number corresponding to the solution in a section (0, 1) aiming at each solution needing updating, taking the solution as an immigrate solution if the first random number corresponding to the solution is smaller than the immigrate corresponding to the solution, and randomly selecting the horizontal coordinate of one unmanned aerial vehicle from the immigrate solution to replace the horizontal coordinate of the randomly selected unmanned aerial vehicle in the immigrate solution, wherein the immigrate solution is selected by using a roulette algorithm to remove the rest solution after the immigrate solution from all solutions.

Further, the setting mobility and migration rate for all solutions according to the solution ordering includes:

generating an ascending arithmetic progression between [0,1], wherein the arithmetic progression contains the same number of terms as the plurality of solutions, and wherein the terms in the arithmetic progression are used as the mobility;

And according to the order of the solutions in the solution sequence, the solutions are sequentially and one-to-one corresponding to the terms in the arithmetic sequence, so that the mobility corresponding to each solution is obtained, and the mobility corresponding to each solution is equal to 1 minus the mobility of the solution to one.

Further, executing mutation operation on the solution to be updated after executing migration operation, updating the solution to be updated, including:

generating a second random number from the interval (0, 1) for each of the solutions that need to be updated, and if the second random number is less than or equal to the preset mutation probability, taking the solution as a mutation solution;

For each drone in the abrupt solution, replacing the location coordinates of the drone with location coordinates randomly generated in the candidate space.

Further, the evaluating and correcting all solutions based on connectivity constraints includes:

aiming at each solution, taking each unmanned aerial vehicle in the solution as a target unmanned aerial vehicle one by one, calculating the distance between the target unmanned aerial vehicle and other unmanned aerial vehicles in the solution, and adding the other unmanned aerial vehicles as neighbor unmanned aerial vehicles of the target unmanned aerial vehicle if the obtained distance is smaller than a preset neighbor distance threshold;

Checking whether each target unmanned aerial vehicle has at least two neighbor unmanned aerial vehicles;

If less than two neighbor unmanned aerial vehicles of the target unmanned aerial vehicle are detected, the nearest non-neighbor unmanned aerial vehicle connecting line with the target unmanned aerial vehicle is taken as a direction, the target unmanned aerial vehicle is adjusted to the nearest non-neighbor unmanned aerial vehicle by a moving distance, so that connectivity constraint is met, and the moving distance is the actual distance between the target unmanned aerial vehicle and the non-neighbor unmanned aerial vehicle minus a preset neighbor distance threshold.

On the other hand, as shown in fig. 2, an embodiment of the present invention provides a multi-unmanned aerial vehicle base station cooperative deployment optimization device under a building obstacle condition, including:

An initial solution determining unit 200, configured to randomly allocate position coordinates in a candidate space for all unmanned aerial vehicles for multiple times, to obtain multiple solutions, where each solution includes position coordinates of all unmanned aerial vehicles;

An fitness value determining unit 201, configured to calculate, for each solution, a number of users of all unmanned aerial vehicles in the solution according to position coordinates of all unmanned aerial vehicles in the solution and preset user coordinates of a plurality of users, and take the number of users of all unmanned aerial vehicles in the solution as a fitness value corresponding to the solution;

A global optimal determining unit 202, configured to sort all solutions according to ascending order of fitness values corresponding to the solutions to obtain a solution sort, use a solution with a largest fitness value in the solution sort as a global optimal solution, and use a fitness value corresponding to the global optimal solution as a global optimal fitness value;

The global optimal iteration unit 203 is configured to perform cyclic iteration update on the solutions based on an improved biological geographic optimization algorithm, sort the solutions according to the updated fitness value when the solutions are updated in each iteration, update the global optimal solution and the global optimal fitness value according to the obtained sorting, stop iteration until the number of cyclic iterations reaches a preset maximum number of iterations or the number of continuous non-improvement times reaches a preset maximum number of continuous non-improvement times, and use the obtained global optimal solution for collaborative deployment of multiple unmanned aerial vehicle base stations, where the obtained global optimal fitness value is the number of users that can be served after collaborative deployment of multiple unmanned aerial vehicle base stations according to the obtained global optimal solution.

Further, the initial solution determining unit 200 includes:

The system comprises an environment space rasterization module, a grid set and a candidate space, wherein the environment space rasterization module is used for acquiring space information of an environment space, rasterizing the environment space into a plurality of vertically arranged square grids to obtain a grid set of a building in the environment space and a grid set of the candidate space, the grid set comprises the plurality of square grids, the space information of the environment space comprises the length, the width and the height of the environment space and the space information of one or more buildings in the environment space, and the space information of the building comprises the position coordinates, the length, the width and the height of the building;

A random allocation location module for randomly generating three-dimensional location coordinates of all the drones in each solution within the grid set of candidate spaces, and/or,

The clustering allocation position module is used for generating horizontal coordinates of all unmanned aerial vehicles in a candidate space by using a k-means clustering method, and then randomly determining the height coordinates of all unmanned aerial vehicles in a preset candidate space height range, wherein the position coordinates of the unmanned aerial vehicles are central coordinates of a cubic grid occupied by the unmanned aerial vehicles, and the position coordinates comprise the horizontal coordinates and the height coordinates.

The clustering allocation position module specifically comprises:

For each unmanned aerial vehicle, an optimal deployment height corresponding to the maximum coverage radius of the unmanned aerial vehicle can be determined based on a probability statistical channel model, the optimal deployment height is taken as a center, the upper limit and the lower limit of the height coordinate random selection range of the unmanned aerial vehicle are determined, the maximum coverage radius is determined according to the maximum radius which can be covered by the receiving and transmitting power of a base station on the unmanned aerial vehicle, the upper limit of the height is equal to the optimal deployment height plus a preset upward offset value, the lower limit of the height is equal to the optimal deployment height minus the preset downward offset value, and the probability statistical channel model means that the path loss between the unmanned aerial vehicle and a user is formed by LoS and nLoS links respectively with a certain fixed probability. The path loss depends on building related environmental parameters, distance between the drone and the user, and elevation angle. Users typically have minimum requirements for quality of service, which can be expressed in terms of path loss. If a certain path loss threshold is given, a nonlinear implicit function of the service height with respect to the coverage radius can be obtained through simplification, and the optimal service height corresponding to the maximum coverage radius can be obtained through deviation derivation.

Further, the fitness value determining unit 201 includes:

The system comprises a shielding judgment module, a shielding judgment module and a display module, wherein the shielding judgment module is used for calculating whether building shielding exists between each user and each unmanned aerial vehicle in the solution according to preset user coordinates of each user, position coordinates of each unmanned aerial vehicle in the solution and space information of all buildings in an environment space;

The power determining module is used for calculating NLoS receiving power obtained by the user from the unmanned aerial vehicle with the building shielding for each user and calculating LoS receiving power obtained by the user from the unmanned aerial vehicle without the building shielding for the link between the unmanned aerial vehicle with the building shielding for each user;

the system comprises a user allocation module, a service management module and a service management module, wherein the user allocation module is used for allocating all NLoS (non-local area network) receiving powers and maximum value of LoS receiving powers to each user to the user for providing service for unmanned aerial vehicles;

And the fitness determining module is used for counting the total number of users of all unmanned aerial vehicles in each solution, which provide services, as a fitness value corresponding to the solution.

Further, the shielding judgment module is configured to:

The first condition is formula (7), the second condition is formula (8), and the second condition is that line segment Q ₁Q₂ is distributed on two sides of line segment P ₁P₂;

Further, the power determination module is configured to:

Calculating power loss of the air-to-ground communication based on the binary channel model by the following formula (9) and formula (10);

The NLoS received power and the LoS received power are calculated by the following equation (11) and equation (12).

Further, the global optimal iteration unit 203 includes:

The initialization module is used for initializing elite rate, determining the number of reserved solutions and updated solutions in each iteration according to the elite rate and the total number of preset solutions, and setting the preset mutation probability p _M;

the loop control module is used for executing the following iteration loops until the maximum iteration times are reached or the continuous non-improvement times reach the maximum continuous non-improvement times, and stopping iteration:

The solution dividing module is used for sorting solutions according to all solutions, taking the solution with high fitness value and the number of reserved solutions as the solution with unchanged reservation in all solutions, and taking the solution with low remaining fitness and the number of updated solutions as the solution to be updated in all solutions;

The migration module is used for executing migration operation on each solution in the solutions to be updated and updating the solutions to be updated;

the mutation module is used for executing mutation operation on the solution to be updated after the migration operation is executed, and updating the solution to be updated;

The evaluation correction module is used for evaluating and correcting all solutions based on connectivity constraint, wherein the connectivity constraint is used for constraining each unmanned aerial vehicle to at least have two neighbor unmanned aerial vehicles, and the neighbor unmanned aerial vehicles are unmanned aerial vehicles with the distance smaller than a preset neighbor distance threshold;

the fitness value updating module is used for calculating the number of users of all unmanned aerial vehicles in the solutions according to the position coordinates of all unmanned aerial vehicles in the solutions and preset user coordinates of a plurality of users for each solution, and updating the fitness value corresponding to the solutions by using the number of users of all unmanned aerial vehicles in the solutions;

The optimal determination module is used for updating the solutions according to ascending order of the updated fitness values, updating the global optimal solution by using the solution with the largest fitness value in the solution ordering, updating the global optimal fitness value by using the fitness value corresponding to the global optimal solution, and outputting the global optimal solution and the global optimal fitness value when iteration is stopped.

Further, the migration module includes:

the migration rate determining module is used for setting migration rate and migration rate for all solutions according to the solution sequence of all solutions, wherein the migration rate corresponding to the solution with the large fitness value is large, the migration rate and the migration rate are both smaller than or equal to 1, and the sum of the migration rate and the migration rate of the same solution is 1;

The migration operation module is used for generating a first random number corresponding to each solution in the solutions to be updated in the intervals (0, 1), if the first random number corresponding to the solution is smaller than the mobility corresponding to the solution, the solution is taken as an migration solution, the horizontal coordinate of one unmanned aerial vehicle is randomly selected from migration solutions, the horizontal coordinate of one unmanned aerial vehicle randomly selected from the migration solutions is replaced, and the migration solutions are selected from all solutions by using a roulette algorithm to remove the remaining solutions after the migration solutions.

Further, the migration rate determining module is configured to:

Further, a mutation module configured to:

Further, the evaluation correction module is configured to:

For the device embodiment, since it is substantially similar to the method embodiment, the description is relatively simple, and reference is made to the section of the method embodiment for that matter

The foregoing technical solutions of the embodiments of the present invention will be described in detail with reference to specific application examples, and reference may be made to the foregoing related description for details of the implementation process that are not described.

Description of the problem

Urban dense building groups and irregular user distribution present a serious challenge for emergency communication network construction, and a stable and flexible emergency network deployment strategy is needed. Unmanned aerial vehicles are known for their agility, mobility and cost effectiveness and are increasingly being used in various areas of military and civilian use, such as logistics distribution, power inspection, reconnaissance surveillance, communication relays, and the like. And the integration of the unmanned aerial vehicle and the mobile base station is convenient for quickly constructing a wireless network, and provides an effective solution for communication recovery in a post-disaster urban scene by virtue of the characteristics of quick deployment, agile movement and high-quality connection.

That embodiment of the invention solves the problem of multi-unmanned aerial vehicle base station collaborative deployment optimization considering building obstacle.

When the problem of cooperative deployment optimization of multiple unmanned aerial vehicles (base stations) with building barriers is considered, as shown in fig. 3, buildings with different heights are randomly distributed in a target area, and multiple unmanned aerial vehicle base stations are deployed above the buildings to form a double-connection unmanned aerial vehicle network, so that communication services are cooperatively provided for users randomly distributed on the ground. If the communication path between the unmanned aerial vehicle and the user is not blocked by the building, the unmanned aerial vehicle and the user provide communication service through the LoS communication link, otherwise, the unmanned aerial vehicle and the user provide communication service through the NLoS communication link.

The application scene of the embodiment of the invention comprises the following main components:

The buildings are used as one of main obstacles and are randomly distributed in the urban environment, so that potential deployment positions of the unmanned aerial vehicle can be occupied in space to influence solution space, transmission of wireless communication signals can be blocked, and quality of signals received by users is influenced. The embodiment of the invention discloses a judging method for judging whether a communication path between an unmanned aerial vehicle and a user is blocked by a building. Even for users at the same distance from the drone base station, the signals they receive will vary due to differences in building distribution. And the shielding effect of the building can be processed through the cooperative coordination of a plurality of unmanned aerial vehicle base stations, if the communication link between a user and one unmanned aerial vehicle base station is blocked by the building, other unmanned aerial vehicle base stations with the communication link not blocked can be selected to acquire network services. Therefore, compared with a single unmanned aerial vehicle, the multi-unmanned aerial vehicle has wider cooperative coverage range and larger capacity, and the service efficiency is remarkably improved.

Firstly, the buildings in the urban environment are densely distributed, and the feasible deployment space of the unmanned aerial vehicle is occupied in a large space. Secondly, the unmanned aerial vehicle provides communication service for ground users by carrying a mobile base station, and generally builds a communication model based on an air-to-ground channel model. As shown in fig. 4, however, due to the shielding effect of the building, the communication link between the unmanned aerial vehicle and the user can be divided into a LoS link and an NLoS link, and the path loss of different communication links is different, so that the communication quality received by the user is different. The embodiment of the invention adopts the received power as an index for measuring the communication quality, and describes a communication channel model and a received power calculation mode. Also, the maximum number of users that each drone base station can serve is fixed due to broadband capacity limitations. Finally, in order to provide stable and reliable communication services for ground users, the unmanned aerial vehicle base stations need to meet double connection constraint to form a robust and flexible unmanned aerial vehicle network.

Users are randomly distributed on the two-dimensional floor of the target area, assuming they are homogenous, with the same minimum communication quality requirements. Only when the received power of the user reaches a preset threshold value, it can be ensured that the user obtains the communication service. Under the scene of the collaborative operation of multiple unmanned aerial vehicles, a user can select the unmanned aerial vehicle with the strongest receiving power to carry out communication access.

And (3) shielding judgment, namely under the condition that the unmanned aerial vehicle base station communicates with a user, when the transmission path is not shielded by an obstacle, signal propagation is direct, and the communication link is LoS. Conversely, when the transmission path is blocked by an obstruction, the signal undergoes reflection, refraction, and diffraction, where the link is NLoS. For the LoS link, users with the same distance from the base station of the unmanned aerial vehicle experience the same signal attenuation, and the same communication quality is obtained. However, building blockage can affect the quality of the communication signal received by the user. If there is a building blockage in the communication path of the signals received by the same part of the users from the unmanned aerial vehicle base station, i.e. the communication link is NLoS, these users will get a different communication quality than the LoS link.

To determine the type of communication link between the drone base station and the ground user, the four vertices in the overhead view of the building and the corresponding building heights may be used to represent the building within the target space. Meanwhile, a straddling method in the calculation geometry is utilized to determine whether obstacle shielding exists between the unmanned aerial vehicle base station and the ground user. The straddling method can rapidly judge whether two line segments are intersected or not by utilizing mathematical properties of vector cross multiplication and dot multiplication. The main method principle is as follows, as shown in fig. 5, the two conditions of intersection of the line segments P ₁P₂ and Q ₁Q₂ are two, namely, the formula (7) as the condition 1 and the formula (8) as the condition 2, if the two conditions are simultaneously satisfied, the line segment P ₁P₂ intersects with the line segment Q ₁Q₂.

Channel model to represent the characteristics of the air-to-ground channel, a simple binary channel state model may be used, which includes only the two states of the link LoS link or NLoS link. If the building does not obstruct the connection between the drone and the user, their communication link is considered to be a LoS link. Otherwise, the communication link between them will be regarded as NLoS link.

The power loss of the air-to-ground communication under the binary channel model is represented as formula (9) and formula (10);

The urban environment is densely populated with buildings for which additional random path loss L _s under building shading conditions must be defined as a function of tilt angle, taking into account the additional path loss due to shadowing effects of the buildings. Embodiments of the present invention contemplate a relatively stable system and therefore do not employ normally distributed random components as the positional variability. The expressions of eta _LoS and eta _NLoS are eta _LoS＝92.4,η_NLoS＝92.4+L_s, Wherein normrnd (μ, σ) represents the normal distribution, θ _ij is the elevation angle of user i to drone j, the remainder being empirical parameters. For f _c =2 GHz, table 1 is the values of the empirical parameters in all circumstances.

Table 1f _c = values of empirical parameters in all environments at 2GHz

After the path loss between the user and the unmanned aerial vehicle base station is obtained, the received power is equal to the transmission power minus the path loss, and the calculation formula is formula (11) and formula (12);

for each user, it is necessary to calculate the power values received from the different drone base stations. Only when a predetermined minimum threshold is reached, the user is able to receive communication services. The higher the power received by the user, the higher the quality of the communication obtained.

And (3) model:

the embodiment of the invention solves the problem of cooperative deployment optimization of the novel multi-unmanned aerial vehicle base station based on the binary channel model and MCLP model, and considers the deployment space limitation, the building obstacle, the user communication condition, the capacity limitation of the unmanned aerial vehicle and the double-connectivity constraint. Based on this, the optimization problem is expressed mathematically as follows.

The parameter variable symbols used in the model are shown in table 2:

TABLE 2 problem parameters

Objective function the collaborative deployment optimization problem of multiple unmanned aerial vehicle base stations aims to maximize the number of users served. In order to maintain communication availability, the received power of the user must exceed a given minimum threshold. The user preferably selects the unmanned aerial vehicle base station providing the highest receiving power for communication access. If the multi-drone base station reaches its service capacity, the user will not have access to it and other drone base stations must be selected for communication access according to the descending order of received power. The embodiment of the invention defines a decision variable b _ik for representing the access condition of a user:

in this regard, the objective function may be expressed as

The constraint conditions comprise candidate position constraint, unmanned aerial vehicle number constraint, feasibility constraint, uniqueness constraint, service capacity constraint and connectivity constraint among unmanned aerial vehicles.

① Candidate location constraint-in urban combat environment, the candidate location of the drone is obtained by rasterizing a given space by a cube in 1 meter units, Z being the set of all grid locations within the target space. Candidate position k is represented by the center coordinate (x _k,y_k,z_k) in the cube. Because urban environments are densely built, unmanned aerial vehicles can only be deployed in spaces outside the buildings. The grid set of the building is B and the drone cannot be deployed within these grids. Considering the form of the obstacle and the boundary of the deployment space, the spatial coordinates of candidate position k have the following constraints:

② The number of unmanned aerial vehicles is constrained, and the embodiment of the invention mainly establishes a multi-unmanned aerial vehicle base station collaborative deployment model based on the maximum coverage position model, so that given unmanned aerial vehicle resources are required to be fully utilized. The number of drones to be deployed finally should be defined as n.

③ The feasibility constraint is that for each user, when the drone provides communication services to it, its received power must be brought to a certain threshold. Therefore, if it is determined that unmanned aerial vehicle k serves user i, then user i must get an acceptable power P _ik for unmanned aerial vehicle k that is greater than or equal to minimum acceptable power threshold P _min. The key constraints can be described as:

④ The uniqueness constraint is that for each user, at most one unmanned aerial vehicle base station can be accessed, namely:

⑤ Service capacity constraint-for each unmanned aerial vehicle base station, the number of users that it can access cannot exceed its service capacity, namely:

⑥ Connectivity constraints between unmanned aerial vehicles

For each drone, it is necessary to be able to find at least two other drones with a distance not greater than R _max. Let i and j be respectively, the distance between them be d _ij. The communication condition between unmanned aerial vehicles is represented by a 0-1 variable c _ij:

The connectivity constraint between the drones is expressed as:

The embodiment of the invention provides an improved biological geography optimization (Biogeography-based optimization, BBO) algorithm based on the characteristics of an intelligent unmanned aerial vehicle cluster, which is used for solving the problem of collaborative deployment optimization of multiple unmanned aerial vehicle base stations. The inspiration of BBO algorithms comes from the theory of biophysics that mimics the species migration process between multiple habitats. The suitability of each habitat is represented by a Habitat Suitability Index (HSI) and is influenced by Suitability Index Variables (SIVs) such as temperature, rainfall and soil quality. The habitat of high HSI allows more species to be present, while the habitat of low HSI has fewer species, while HSI is determined by SIV. In the implementation of the BBO algorithm, two main operators, namely migration and mutation, are included, so that the method is very suitable for solving the combination optimization problem. The pseudo code for improving the BBO algorithm is detailed in algorithm 1.

Solution expression, redefining the known expression method for solving the problem of deployment of the base stations of the multiple unmanned aerial vehicles. Each solution contains the spatial cartesian coordinates of all the unmanned base stations, and the solution's fitness is the number of ground users served. According to the concept of the BBO algorithm, each solution is considered as a habitat, where the spatial cartesian coordinates of each drone are SIV and the fitness of the solution is HIS.

The fitness level of the solution reflects the size of the population. All solutions are ranked from low to high according to the fitness level, and the habitat represented by the solution with the lowest fitness has a population size of zero, mobility of 1 and mobility of 0. In contrast, the most suitable solution represents a habitat with a maximum population size, an mobility of 0 and a mobility of 1. Habitat represented by other solutions, whose population size increases with increasing fitness, and mobility decreases and mobility increases accordingly. In a practical application of the algorithm, the change in the shift-in rate and the shift-out rate may be set to be linear, and the sum of the two is 1.

Initial solution construction deployment of multiple unmanned aerial vehicle base stations is limited by target space boundaries and building space. Thus, candidate locations must be selected from the unobstructed space, and the locations of the drones in the solution must be adjusted when generating a solution to meet the double connectivity constraint between the drones. The embodiment of the invention provides two strategies for constructing an initial solution. The first method is to randomly generate three-dimensional coordinates of multiple unmanned aerial vehicles in an available deployment space. The second method utilizes a k-means clustering method to generate horizontal coordinates of multiple unmanned aerial vehicles in a deployable space, and then randomly determines the height (H _Kmin,H_Kmax) within a specified range. The BBO algorithm based on random initialization is denoted as RD+BBO, and the BBO algorithm based on k-means initialization is denoted as KMC+BBO.

Elite strategy the main idea of BBO algorithm is to use the optimal solution to enhance the difference solution. Elite strategies are a common technique that ensures that excellent solutions can be preserved to the next generation. Elite solutions are solutions that perform optimally in the current population, and these solutions are typically kept directly to the next generation to maintain or improve the solution quality of the entire population. For this, a retention, denoted by β e [0, 1), is introduced, which determines the elite solution ratio retained in each iteration. Lower beta means that the number of retained solutions is smaller. Let the total number of solutions be s. The number of elite solutions retained is s _Keep = βs. The new solution can be improved by migration and mutation, which in turn results in a better solution. The calculation method of the number of new solutions can be expressed as s _New＝s-s_Keep = (1- β) s. The elite strategy aims at maintaining diversity of the population, and simultaneously keeping excellent individual information, and avoiding premature convergence of the algorithm to a local optimal solution.

Migration operation-migration operator is a core operator in the BBO algorithm, which is critical for building new solutions. The characteristics of the solution are transferred between habitats mainly by the probabilities defined by the mobilities λ (i) and μ (i). BBO algorithms use mobility and mobility as a linear function of species count, as shown in the following equation,

Wherein I and E are the maximum shift-in rate and shift-out rate, respectively, and are usually set to 1. The symbol S denotes the number of species, and S _max denotes the maximum number of species.

The mobility λ (i) is used to select one solution x _i and the mobility μ (j) is used to select the other solution x _j. A random number τ is generated within the interval (0, 1). If τ is less than mobility λ (i), a migration operation is performed on solution i. The operation includes selecting two SIVs (horizontal coordinates of the drone location) from solution x _i and replacing it with the corresponding SIV from solution x _j.

Mutation operation mutation operators in the BBO algorithm simulate the change of habitat environment. The probability of mutation in a habitat is a function of the number of species in the habitat, expressed as follows:

Where m _s is the mutation probability when the number of species is s, m _max is the maximum mutation rate, P _s is the probability when the number of species is s, and P _max is the maximum value of P _s.

In the BBO algorithm, the original mutation operator involves a complex determination of the mutation probability for each solution. To simplify this, a constant value of the mutation probability p _M∈(0,1).p_M may be applied to each drone coordinate, which should be approximately zero, indicating that the drone position is less sensitive to mutation. Generating a random number sigma from the interval (0, 1), and carrying out mutation operation on the corresponding solution if sigma is less than or equal to p _M. The abrupt change operation refers to generating a new unmanned aerial vehicle coordinate in the available target space to replace the original unmanned aerial vehicle coordinate.

Improved biophysical optimization algorithm to further analyze the effectiveness of the proposed method and its feasibility in real-world applications, the North Star delta region of the chang city was selected as an example study for testing. The main experimental parameters are shown in table 3.

Case description North Star delta is located in the long sand of China, and occupies 1.1 square kilometers. The area outlined by the black line in fig. 6 is a top view of the North Star delta area. We have extracted more than 50 meters of building and selected 35 of them to be relatively regular in shape. And simulates 60 users with communication requirements, randomly distributed in the target area.

The distribution of buildings and users is shown in fig. 7.

TABLE 3 experimental parameters

Results and discussion in this example context, 6 drone base stations were deployed to provide wireless network services for 60 users. The example was solved using a random initialization based BBO algorithm (RD+BBO) and a k-means initialization based BBO algorithm (KMC+BBO), both methods having a maximum number of coverage users of 60.

The three-dimensional and two-dimensional optimal deployment results of the RD+BBO method are shown in FIG. 8 and FIG. 9 respectively. And the best results of the kmc+bbo method in three dimensions and two dimensions are shown in fig. 10 and 11. The convergence curves for both methods are shown in fig. 12. According to experimental results and convergence curves, the method can realize effective collaborative deployment of the base stations of the multiple unmanned aerial vehicles considering building obstacles. The kmc+bbo method not only produces optimal results, but also exhibits a faster convergence speed due to the high quality nature of its initial solution. Therefore, the KMC+BBO method is more suitable for solving the collaborative deployment optimization problem of the base stations of the multiple unmanned aerial vehicles.

It should be understood that the specific order or hierarchy of steps in the processes disclosed are examples of exemplary approaches. Based on design preferences, it is understood that the specific order or hierarchy of steps in the processes may be rearranged without departing from the scope of the present disclosure. The accompanying method claims present elements of the various steps in a sample order, and are not meant to be limited to the specific order or hierarchy presented.

In the foregoing detailed description, various features are grouped together in a single embodiment for the purpose of streamlining the disclosure. This method of disclosure is not to be interpreted as reflecting an intention that the claimed embodiments of the subject matter require more features than are expressly recited in each claim. Rather, as the following claims reflect, invention lies in less than all features of a single disclosed embodiment. Thus the following claims are hereby expressly incorporated into this detailed description, with each claim standing on its own as a separate preferred embodiment of this invention.

The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present application. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the disclosure. Thus, the present disclosure is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

The foregoing description includes examples of one or more embodiments. It is, of course, not possible to describe every conceivable combination of components or methodologies for purposes of describing the aforementioned embodiments, but one of ordinary skill in the art may recognize that many further combinations and permutations of various embodiments are possible. Accordingly, the embodiments described herein are intended to embrace all such alterations, modifications and variations that fall within the scope of the appended claims. Furthermore, as used in the specification or claims, the term "comprising" is intended to be inclusive in a manner similar to the term "comprising". Furthermore, any use of the term "or" in the specification of the claims is intended to mean "non-exclusive or".

Those of skill in the art will further appreciate that the various illustrative logical blocks (illustrative logical block), units, and steps described in connection with the embodiments of the invention may be implemented by electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of hardware and software (interchangeability), various illustrative components described above (illustrative components), elements, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design requirements of the overall system. Those skilled in the art may implement the described functionality in varying ways for each particular application, but such implementation is not to be understood as beyond the scope of the embodiments of the present invention.

The various illustrative logical blocks or units described in the embodiments of the invention may be implemented or performed with a general purpose processor, a digital signal processor, an Application Specific Integrated Circuit (ASIC), a field programmable gate array or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described. A general purpose processor may be a microprocessor, but in the alternative, the general purpose processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a digital signal processor and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a digital signal processor core, or any other similar configuration.

The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may be stored in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. In an example, a storage medium may be coupled to the processor such that the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC, which may reside in a user terminal. In the alternative, the processor and the storage medium may reside as distinct components in a user terminal.

In one or more exemplary designs, the above-described functions of embodiments of the present invention may be implemented in hardware, software, firmware, or any combination of the three. If implemented in software, the functions may be stored on a computer-readable medium or transmitted as one or more instructions or code on the computer-readable medium. Computer readable media includes both computer storage media and communication media that facilitate transfer of computer programs from one place to another. A storage media may be any available media that can be accessed by a general purpose or special purpose computer. For example, such computer-readable media may include, but is not limited to, RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium that may be used to carry or store program code in the form of instructions or data structures and other data structures that may be read by a general or special purpose computer, or a general or special purpose processor. Further, any connection is properly termed a computer-readable medium, e.g., if the software is transmitted from a website, server, or other remote source via a coaxial cable, fiber optic cable, twisted pair, digital Subscriber Line (DSL), or wireless such as infrared, radio, and microwave, and is also included in the definition of computer-readable medium. The disks (disks) and disks (disks) include compact disks, laser disks, optical disks, DVDs, floppy disks, and blu-ray discs where disks usually reproduce data magnetically, while disks usually reproduce data optically with lasers. Combinations of the above may also be included within the computer-readable media.

The foregoing description of the embodiments has been provided for the purpose of illustrating the general principles of the invention, and is not meant to limit the scope of the invention, but to limit the invention to the particular embodiments, and any modifications, equivalents, improvements, etc. that fall within the spirit and principles of the invention are intended to be included within the scope of the invention.

Claims

1. The multi-unmanned aerial vehicle base station collaborative deployment optimization method under the condition of building obstacle is characterized by comprising the following steps:

2. The method for optimizing the collaborative deployment of base stations of multiple unmanned aerial vehicles under the condition of building obstacle according to claim 1, wherein the steps of randomly distributing position coordinates in a candidate space for all unmanned aerial vehicles for multiple times to obtain multiple solutions, each solution including the position coordinates of all unmanned aerial vehicles, include:

3. The method for optimizing the collaborative deployment of base stations of multiple unmanned aerial vehicles under the condition of building obstacle according to claim 2, wherein the method for generating horizontal coordinates of all unmanned aerial vehicles in a candidate space by using a k-means clustering method and then randomly determining the height coordinates of all unmanned aerial vehicles in a preset candidate space height range comprises the following steps:

for each unmanned aerial vehicle, determining an optimal deployment height corresponding to the maximum coverage radius of the unmanned aerial vehicle based on a probability statistical channel model, and determining an upper limit and a lower limit of a preset candidate space height range of the height coordinates of the unmanned aerial vehicle by taking the optimal deployment height as a center, wherein the upper limit of the height is equal to the optimal deployment height plus a preset upward offset value, and the lower limit of the height is equal to the optimal deployment height minus a preset downward offset value;

Wherein the probabilistic statistical channel model is a model expressed by the following formula:

Wherein h is the height of the unmanned aerial vehicle, d _ik is the distance from the user i to the center of the coverage circle of the unmanned aerial vehicle k, a and b are constant coefficients determined by the environment, For the elevation angle of the drone k to user i, ηlos and ηnlos are the average parasitic losses of LoS and nLoS, respectively, f _c is the carrier frequency of the air-to-ground channel and c is the speed of light.

4. The method for optimizing cooperative deployment of multiple unmanned aerial vehicle base stations under the condition of building obstacle according to claim 1, wherein for each solution, calculating the number of users of all unmanned aerial vehicles in the solution according to the position coordinates of all unmanned aerial vehicles in the solution and preset user coordinates of a plurality of users, and taking the number of users of all unmanned aerial vehicles in the solution as the corresponding fitness value of the solution comprises:

5. The method for optimizing cooperative deployment of base stations of multiple unmanned aerial vehicles in a building according to claim 4, wherein the calculating the NLoS received power of the user from the unmanned aerial vehicle with building shielding in case of a barrier to the unmanned aerial vehicle with building shielding for the user, and the calculating the LoS received power of the user from the unmanned aerial vehicle without building shielding for the link to the unmanned aerial vehicle without building shielding for the user specifically comprises:

PL_LoS＝20lg(d_ij)+20lg(f_c)+η_LoS

PL_NLoS＝20lg(d_ij)+20lg(f_c)+η_NLoS

Wherein f _c is the carrier frequency, d _ij is the distance between user i and unmanned plane j, and eta _LoS and eta _NLoS respectively represent the additional path power loss under the link state LoS and NLoS, eta _LoS＝92.4,η_NLoS＝92.4+L_s, and the additional random path loss under the building shielding condition Representing normal distribution, θ _ij is the elevation angle of the user i to the unmanned aerial vehicle j, and g _μ、g_σ、h_μ、h_σ、i_μ、i_σ is an empirical parameter;

P_LoS＝P_t-PL_LoS

P_NLoS＝P_t-PL_NLoS

6. The multi-unmanned aerial vehicle base station collaborative deployment optimization method under the condition of building obstacle according to claim 1, wherein the improved biological geography optimization algorithm is used for carrying out cyclic iteration update on the solutions, sequencing the solutions according to the updated fitness value when the solutions are updated each time, updating a global optimal solution and a global optimal fitness value according to the obtained sequencing, stopping iteration until the number of cyclic iterations reaches a preset maximum iteration number or the number of continuous non-improvement times reaches a preset maximum continuous non-improvement number, and using the obtained global optimal solution for multi-unmanned aerial vehicle base station collaborative deployment, wherein the obtained global optimal fitness value is the number of users which can be served after the multi-unmanned aerial vehicle base station collaborative deployment according to the obtained global optimal solution, and the method comprises the following steps:

7. The method for optimizing the collaborative deployment of multiple unmanned aerial vehicle base stations in the case of a building obstacle according to claim 6, wherein the step of performing a migration operation on each of the solutions to be updated, and updating the solutions to be updated comprises:

8. The method for optimizing the cooperative deployment of multiple unmanned aerial vehicle base stations in the case of a building obstacle according to claim 7, wherein the setting of mobility and migration rate for all solutions according to the solution ordering comprises:

9. The method for optimizing the collaborative deployment of base stations for a multiple unmanned aerial vehicle in the event of a building obstacle according to claim 5, wherein said evaluating and correcting all solutions based on connectivity constraints comprises:

10. Multi-unmanned aerial vehicle base station collaborative deployment optimizing apparatus under building obstacle condition, characterized by comprising:

The system comprises an initial solution determining unit, a calculation unit and a calculation unit, wherein the initial solution determining unit is used for randomly distributing position coordinates in a candidate space for all unmanned aerial vehicles for a plurality of times to obtain a plurality of solutions, and each solution comprises the position coordinates of all unmanned aerial vehicles;

The fitness value determining unit is used for calculating the number of users of all unmanned aerial vehicles in the solution according to the position coordinates of all unmanned aerial vehicles in the solution and preset user coordinates of a plurality of users for each solution, and taking the number of users of all unmanned aerial vehicles in the solution as the fitness value corresponding to the solution;