CN116634452A - Deployment and offloading method of UAV-assisted edge computing network - Google Patents

Abstract

The invention discloses a deployment and unloading method of an unmanned aerial vehicle auxiliary edge computing network, which mainly solves the problem of high cost caused by the fact that the number of unmanned aerial vehicles is not deployed according to the number of users in the existing unmanned aerial vehicle provided with an edge computing server, and the implementation scheme is as follows: setting relevant parameters of a user and an unmanned aerial vehicle auxiliary network; setting constraint conditions according to network characteristics; establishing a minimum energy consumption problem P according to the initialized network parameters and constraint conditions; determining the number N of unmanned aerial vehicles, an incidence matrix C, an unloading matrix U, a computing resource matrix F and an unmanned aerial vehicle position matrix Z in a problem P by using an upper layer iteration method and a lower layer iteration method; and carrying out network deployment and calculation task unloading according to the five calculated parameters. According to the invention, under the constraint condition that the tolerable time delay of the calculation task and the upper limit of the calculation resources of the unmanned aerial vehicle are met, the unloading decision and the deployment scheme are optimized according to the position of the user and the calculation task information, the task is completed by using the minimum number of unmanned aerial vehicles, and the network cost can be minimized while the total energy consumption of the system is reduced.

Description

Deployment and offloading method of UAV-assisted edge computing network

technical field

The invention belongs to the field of communication technology, and in particular relates to a UAV-assisted edge computing network deployment and unloading method, which can be used for emergency communication and edge computing services under the condition of limited energy consumption of UAVs.

Background technique

With the development of communication technology, the Internet has developed from a peer-to-peer network to the World Wide Web, and from a mobile Internet to the Internet of Things. Immediately, the demand for data services, computing resources, and network infrastructure has increased significantly to meet the needs of a large number of interconnected devices. In order to provide users with a better immersive service experience, mobile edge computing MEC deploys cloud resources at the edge of the radio access network. The UAV UAV has good channel quality, strong mobility, and flexible deployment. It can be quickly deployed at a designated location as an air base station, which is an effective supplement and extension of the ground communication network. The combination of the two can not only further expand the service scope of MEC, but also improve the quality of service, and provide low-latency, high-reliability communication and computing services for mountainous areas where the network is paralyzed, the base station is damaged, and there is no coverage. Conventional edge computing systems usually deploy edge servers on a fixed infrastructure on the ground, but in order to better support UAV-assisted edge computing networks, UAVs must be deployed more flexibly. However, due to the limited power carried by drones, they cannot support long-term hovering and communication computing services, and the economic cost of purchasing a drone cannot be ignored. The more drones used, the greater the total cost. Therefore, in the UAV-assisted edge computing system, it is necessary to reduce the number of deployed UAVs, save costs, and reduce energy consumption through reasonable deployment and task scheduling schemes.

In order to ensure the service quality of users in the target area and avoid the problem of communication interruption, it is necessary to reasonably deploy the UAV position based on the user's location and computing tasks to determine the computing offloading scheme. Zhaohui Yang published Energy Efficient Resource Allocation in UAV-Enabled Mobile Edge Computing Networks[J] in IEEE Transactions on Wireless Communications in 2019, considering multi-UAV assisted mobile edge computing networks, and jointly optimizing user association, power control, and computing resources allocation and location planning, thereby minimizing overall power consumption. In order to solve non-convex problems, it proposes a low-complexity algorithm to solve three sub-problems through iteration. In this solution, only a fixed number of UAVs are considered to assist the edge computing network to provide computing services for users, and the edge computing server carried by UAVs is not considered to have limited computing power, so it cannot meet the needs of a large number of users. The number of UAVs deployed is not reasonably arranged according to the specific number of users, so the cost is relatively high.

Contents of the invention

The purpose of the present invention is to address the shortcomings of the above-mentioned existing technologies, and propose a method for deploying and unloading UAV-assisted edge computing networks, so as to meet the service needs of a large number of users under the condition of satisfying the tolerable delay constraints of computing tasks, Reduce network costs and reduce system energy consumption.

The technical solution of the present invention is: according to the user's location and computing task information, optimize the number and location of deployed drones, the association between users and UAVs, the unloading scheme of user computing tasks, and the computing resources allocated to unloading tasks by UAVs. Its implementation steps include the following:

(1) Set user-related parameters and drone-assisted network-related parameters:

M ground users are randomly distributed in a circular fault area Y with a radius of L, the set of which is O={1,…,m,…,M}, and the location of user m is (x _m ,y _m ,0) ; User m needs to complete the calculation task A _m = (F _m , D _m , T), where F _m represents the number of CPU revolutions required for calculation; D _m represents the amount of calculation data; T is the delay constraint;

Let the set of UAVs be G={1,...,n,...,N}, N is the total number of UAVs to be determined, and the coordinates of the nth UAV are (x _n , y _n , H _n ), The depression angle is fixed at θ, the maximum coverage radius R is H _n tanθ, U _n is the maximum number of users that UAV n can access, f _n,max is the upper limit of computing resources of UAV n, and the transmission power is The hovering power is P ^H , which cannot be adjusted; let the coordinates of the neighbor base station be (x ₀ ,y ₀ ,H);

(2) Establish the minimization energy consumption problem P according to the above initialization parameters:

stC1:

C2:

C3: u _mn ≤ c _mn , m ∈ O, n ∈ G,

C4:

C5: c _mn d _mn ≤ R, m ∈ O, n ∈ G,

C6: t _m ≤ T, m ∈ O,

C7:(x _n ,y _n )∈Y,

Among them, C is the association matrix between the UAV and the user, and c _mn is the element in the mth row and nth column of C;

U is the unloading matrix, u _mn is the element in row m and column n of U, and Z is the position matrix of the UAV;

F is the UAV computing resource allocation matrix, and f _mn is the element in row m and column n in F,

Communication energy consumption for user m to send computing tasks to UAV n; /> Computational energy consumption for UAV n to complete user m tasks, /> The communication energy consumption of transferring the computing task of user m to the neighbor base station for UAV n, /> is the hovering energy consumption of UAV n; α represents the weight coefficient of UAV energy consumption compared with user energy consumption, t _m is the total time for user m to complete the calculation task, d _mn is the distance the horizontal distance between

(3) Determine the initial number N ⁰ of the drone and the initial position Z ⁰ of the drone; according to M ⁰ and Z ⁰ determine the initial correlation matrix C ⁰ , whether the correlation matrix is a feasible solution fsb_C, the initial unloading matrix U ⁰ , Whether the unloading matrix is a feasible solution is fsb_U, the initial resource allocation matrix F ⁰ , the minimum energy consumption E _min and the maximum number of completed tasks num _max ;

(4) Use the upper and lower layer iterative method to solve N, Z, C, U, F in the problem P:

(4a) Set the number of solutions to NoS, the maximum number of iterations to solve is NoS _max , stop deleting the number of drones as flag, the number of infeasible current solutions is not, initialize NoS=0, flag=0, not=0, NoS _max = 1000;

(4b) Determine whether the current solution is a feasible solution and whether the number of drones can continue to decrease:

If fsb_C=fsb_U=1 and flag=0, then the current solution is a feasible solution and the number of drones can continue to decrease, execute (4c); otherwise, jump to step (4f);

(4c) Save the current feasible solution N, Z, C, U, F, and remove a redundant unmanned aerial vehicle to obtain the current number N of unmanned aerial vehicles and the deployment position Z of the unmanned aerial vehicle;

(4d) update the above-mentioned parameters C, fsb_C, U, fsb_U, F, E _min , num _max according to current N and Z, and make NoS=NoS+1, execute step (4g);

(4f) Utilize the improved differential evolution algorithm to determine the parameters Z, fsb_C, U, fsb_U, F, E _min , num _max under the current unmanned aerial vehicle number N;

(4g) Determine whether NoS<NoS _max is true, if true, return to step (4b) to continue iterative solution; otherwise, the iteration is terminated, and the final solution UAV number N', UAV position Z', correlation matrix C', Unloading matrix U', computing resource allocation matrix F';

(5) Select N' unmanned aerial vehicles to deploy according to the deployment matrix Z';

(6) Determine the relevance between the user and the UAV according to the association matrix C': if the element c _mn =1 in C', associate the user m with the UAV n, and transfer the computing tasks of the user m to the UAV. Human-machine n; otherwise, user m is not associated with drone n;

(7) According to the element value u _mn in the unloading decision matrix U', determine the execution object of the user computing task:

If u _mn = 1, the drone n allocates computing resources to the user according to the element f _mn in the resource allocation matrix F', and completes the computing task of the user m;

Otherwise, the associated drone n transfers the computing task of user m to the neighbor base station, and the neighbor base station completes the computing task.

Compared with the prior art, the present invention has the following advantages:

First, the present invention improves the stability of the network and satisfies the service needs of a large number of users by combining neighbor base stations with stronger computing capabilities and drones to provide communication and computing services for users in service-damaged areas.

Second, the present invention is based on the joint optimization method of the upper and lower iterative method, because the problem is divided into two layers to solve, that is, the upper layer optimizes the UAV deployment problem, which includes the number of UAVs and the position of each UAV; the lower layer Optimize task scheduling for the upper-layer deployment plan, which includes the association between users and UAVs, the offloading scheme of computing tasks, and the computing resources allocated by UAVs to unloading tasks, and obtains the deployment and offloading scheme of the network, thus reducing system energy consumption , to solve the problem of blocked user services.

Third, since the present invention solves the minimum number of unmanned aerial vehicles required to complete all tasks according to the user's location and calculation tasks, it can reduce energy consumption while reducing the economic cost of deploying too many unmanned aerial vehicles. cost, minimizing network cost.

Simulation results prove that the present invention reduces system energy consumption, reduces network costs, and can provide users with stable services on the premise of satisfying user task time delay constraints.

Description of drawings

Fig. 1 is the realization flowchart of the present invention;

Fig. 2 is a system scene diagram of the present invention;

Fig. 3 is a comparison diagram of the total energy consumption of the system and the number of unmanned aerial vehicles deployed when the present invention and the comparison method are completed with different numbers of users;

Fig. 4 is a comparison diagram of tasks completed at different time points when the user's tolerable time delay is 1s in the present invention and the comparison method.

Detailed ways

Embodiments and effects of the present invention will be further described in detail below in conjunction with the accompanying drawings.

Referring to Figure 2, the scenario used in this example is two adjacent cellular networks. One of the base stations in the cellular network fails to provide services to users. In this example, another drone equipped with a mobile edge computing server is used as a temporary emergency base station , the UAV and neighbor base stations jointly serve users in the fault area. The user's computing tasks are forwarded to the associated UAV, and the UAV can calculate by itself, or relay the task to the neighbor base station to ensure the stability of the network. According to the location of ground users and calculation tasks in the service area of each base station stored in the control center, determine the number of UAVs, the deployment location and the execution plan of the calculation task. The whole process is completed in the control center, and after the implementation plan is obtained The drone is driven by the control center to perform tasks.

Referring to Figure 1, the implementation steps of this example include the following:

Step 1, initialize parameters.

For the usage scenario in Figure 2, initialize the following network parameters:

(1.1) User-related parameter settings:

M ground users are randomly distributed in a circular fault area Y with a radius of L, the set of which is O={1,...,m,,M}, and the position of user m is (x _m ,y _m ,0); User m needs to complete the calculation task A _m = (F _m , D _m , T), where F _m represents the number of CPU revolutions required for calculation; D _m represents the amount of calculation data; T is the delay constraint;

(1.2) Related parameter setting of UAV auxiliary network:

Assume that N drones equipped with edge computing servers and neighbor base stations provide computing services for users in the fault area. The set of drones is G={1,...,n,,N}, and N is the drone to be determined The total number, the coordinates of the nth UAV is (x _n , y _n , H _n ), the depression angle is fixed as θ, the maximum coverage radius R is H _n tanθ, let U _n be the number of users that UAV n can access The maximum value, f _n,max is the upper limit of computing resources of UAV n, and the transmission power is The hovering power is P ^H , which cannot be adjusted;

Let the coordinates of the neighboring base stations be (x ₀ , y ₀ , H).

Step 2, establish the energy consumption minimization problem P according to the above initialization parameters.

(2.1) According to the position coordinates of user m and UAV n, the horizontal distance d _mn between them and the horizontal distance d _nB between UAV n and the neighbor base station are obtained:

(2.2) According to the horizontal distance d _mn in (2.1) and the horizontal distance d _nB between UAV n and neighboring base stations, establish a channel model based on free space path loss, that is, the channel power from user m to UAV n Gain h _mn and channel power gain h _nB between UAV n and neighboring base stations:

Among them, β ^G2A and β ^A2A represent the air-to-ground channel gain and the air-to-air channel gain when the reference distance is one meter, respectively;

(2.3) According to the channel power gain h _mn from user m to UAV n in (2.2) and the channel power gain h _nB between UAV n and neighboring base stations, Shannon’s theorem is used to obtain the channel power gain from user m to UAV n The transmission rate r _mn and the transmission rate r _nB between the UAV n and the neighbor base station:

Among them, B ₁ represents the transmission bandwidth between the user and the UAV, B ₂ represents the transmission bandwidth between the UAV and the neighbor base station, P _m is the transmission power of user m equipment, is the transmitting power of UAV n, N ₀ is the noise power spectral density;

(2.4) Calculate the communication transmission time for user m to send computing tasks to UAV n and communication energy consumption/>

(2.5) Calculate the communication transmission time for UAV m to transfer the computing task of user n to the neighbor base station and communication energy consumption/>

(2.6) Calculate the processing time required for UAV n to complete the task of user m and computing power consumption/>

Among them, f _mn represents the CPU frequency assigned by UAV n to user m, and ε represents the effective capacitance coefficient of the UAV airborne server chip;

(2.7) Calculate the hovering energy consumption of UAV n

(2.8) Set the following correlation matrix and variables:

Let C=[c _mn ] _M×N be the correlation matrix between drones and users, c _mn =1 means that user m is associated with drone n, and c _mn =0 means not associated;

Let U=[u _mn ] _M×N be the user’s calculation offloading decision matrix, when c _mn =1 and u _mn =1 means UAV n provides services for user m, c _mn =1 and u _mn =0 means association UAV n transfers the computing task of user m to the neighbor base station, and the neighbor base station completes the computing task;

Let F=[f _mn ] _M×N be the computing resource allocation matrix;

Let Z=[(x _n ,y _n )] _N×1 be the position matrix of the UAV;

Suppose the total time for the user's computing task to be completed is:

According to the results of (2.4)(2.5)(2.6)(2.7), the total energy consumption of the system is:

(2.9) Set constraints:

According to the characteristic that a user can only be associated with one drone and all users need to be covered, set the first constraint:

According to the number of users connected to each UAV cannot exceed the limit of the maximum number of users connected, set the second constraint

According to the characteristic that the UAV can only provide services to its associated users, set the third constraint u _mn ≤ c _mn ;

According to the limitation that the sum of the computing resources allocated to users within the coverage area by UAV m does not exceed the maximum value of its computing resources, set the fourth constraint

According to the fact that the user associated with the UAV needs to be within its coverage area, set the fifth constraint c _mn d _mn ≤ R;

According to the task completion time of user n does not exceed the limit of the maximum tolerable delay, set the sixth constraint t _m ≤ T;

According to the limitation that the horizontal position of the UAV needs to be within the scope of the faulty base station, the seventh constraint condition (x _n , y _n )∈Y is obtained;

(2.10) Combining the above constraints and parameters, the energy consumption minimization problem P is expressed as follows:

stC1:

C2:

C3: u _mn ≤ c _mn , m ∈ O, n ∈ G,

C4:

C5: c _mn d _mn ≤ R, m ∈ O, n ∈ G,

C6: t _m ≤ T, m ∈ O,

C7:(x _n ,y _n )∈Y,

Among them, α represents the weight coefficient of UAV energy consumption compared with user energy consumption.

In this example, but not limited to L=300 meters, F _m =100～200cycles/bit, D _m =[10,800]KB, H _n =100m, θ=π/4, R=H _n tanθ=100m, β ^G2A =β ^A2A =1.42×10 ^-4 , B ₁ =B ₂ =1MHz, P ^H =100W, N ₀ =10 ^-20 W/Hz, U _n =20, f _n,max =2GHz, ε=10 ^-28 , (x ₀ ,y ₀ ,H ₀ )=(600,300,100).

Step 3, determine the initial number N ⁰ of the drone and the initial position Z ⁰ of the drone;

(3.1) Initialize the number of drones to a larger value N ⁰ =2×(M/U _n );

(3.2) Determine the initial position Z ⁰ of the drone through the Kmeans++ algorithm, and set the number of cycles iter=0:

(3.2.1) With the help of the Kmeans++ algorithm, the number ^N of drones is used as the number of classes, clustering is performed according to the user's position, and the clustering center is used as the deployment position of the drone;

(3.2.2) Determine the candidate set V _m for each user m to perform tasks according to the UAV deployment position obtained in (3.2.1):

(3.2.2.1) Calculate the distance d _mn between the user m and the drone n;

(3.2.2.2) Determine whether d _mn < R is true: if it is true, it means that the distance between the UAV and the user is less than the coverage radius of the UAV, and the UAV n is included in the candidate set V m of user _m middle;

(3.2.3) Determine the initial position Z ⁰ of the UAV:

(3.2.3.1) Judge whether the candidate set of all users is empty: if not empty, then use the current drone position as the initial position Z ⁰ ; otherwise, make iter=iter+1, and perform step (3.2.3.2) ;

(3.2.3.2) Judging whether iter>1000 is true:

If it is true, it means that the initial position of the UAV that satisfies the constraints has not been found after multiple clusterings, and the cluster center obtained in the last iteration is used as the initial position of the UAV;

Otherwise, return to step (3.2.1) to re-solve the initial position of the UAV.

Step 4, according to N ⁰ and Z ⁰ , determine whether the initial correlation matrix C ⁰ and the correlation matrix are feasible solutions fsb_C.

(4.1) Use the greedy association strategy to obtain the association matrix C ⁰ and whether the association is a feasible solution fsb_C:

(4.1.1) Calculate the distance d _mn between the user m and the drone n, and include the drone n with d _mn <R in the candidate set V _m of the user m;

(4.1.2) Divide all users into two categories according to the following criteria:

The first category: there is only one UAV candidate in the candidate set _Vm , that is, the user is only within the coverage radius of one UAV;

The second category: there are multiple drone candidates in the candidate set V _m , indicating that the user is within the coverage of multiple drones;

The associated priority of the first type of task is higher than that of the second type of task;

(4.1.3) Perform association according to the following association criteria to obtain the association matrix C ⁰ and whether the solution is a feasible solution fsb_C:

(4.1.3.1) Judging whether the UAVs in the first type of user candidate set are full: if not, make the corresponding c _mn =1, which means association; otherwise, c _mn =0, which means no association;

(4.1.3.2) According to the number of elements in the second type of user candidate set V _m , sort them in ascending order, give priority to users with small candidate sets to determine the association situation, for user m, according to each candidate in its candidate set V _m The distance from the drone to the user m is sorted in ascending order. If the distance is equal, it is sorted in ascending order according to the number of drone access users, and the user is preferentially associated with the drone with the shortest distance and few access users;

(4.1.3.3) According to the above strategy, judge whether there is a situation where the candidate set is empty or the connected UAVs in the candidate set are full:

If so, the association fails, fsb_C=0;

Otherwise, the association is successful, and fsb_C=1.

Step 5, according to N ⁰ , Z ⁰ , and C ⁰ , determine the initial offloading matrix U ⁰ , whether the offloading matrix is a feasible solution fsb_U, the initial resource allocation matrix F ⁰ , the minimum energy consumption E _min and the maximum number of completed tasks num _max .

(5.1) The minimum resource f _mn,min required by each user for computing at different UAVs is deduced from the following formula:

(5.2) Solve the initialization unloading matrix U ⁰ :

(5.2.1) According to N ⁰ , Z ⁰ , C ⁰ and f _mn,min, the problem P is reduced to a 0-1 programming problem P1 about the unloading matrix U ⁰ :

P1:

s.t.P1:C3,C4,C6

(5.2.2) Utilize the branch and bound method to solve P1, obtain U ⁰ and fsb_U representing whether the unloading matrix is a feasible solution, that is, use the library function about the branch and bound method in the simulation software to solve;

(5.3) Calculate the elements in F ⁰ according to the element u _mn in U ⁰ : f _mn =u _mn f _mn,min , and finally obtain the calculation resource allocation matrix F ⁰ =[f _mn ] _M×N ;

(5.4) Judging whether the initial solution is a feasible solution, that is, whether fsb_C=fsb_U=1 is established:

If it is a feasible solution, calculate the total system energy consumption E ⁰ corresponding to the current solution according to N ⁰ , Z ⁰ , C ⁰ , U ⁰ , and F ⁰ , initialize the minimum system energy consumption E _min =E ⁰ , and complete the maximum number of tasks num _max = M;

Otherwise, calculate the number num ⁰ of users who complete tasks within the delay constraint, initialize the minimum energy consumption E _min of the system to a maximum value, and complete the maximum number of tasks num _max = num ⁰ .

Step 6, use the upper and lower layer iterative method to solve N, Z, C, U, F in the problem P.

(6.1) Set the number of solutions to NoS, the maximum number of iterations to solve is NoS _max , stop deleting the number of drones as flag, the number of infeasible current solutions is not, initialize NoS=0, flag=0, not=0, NoS _max = 1000, initialize N, Z, C, U, F to be equal to N ⁰ , Z ⁰ , C ⁰ , U ⁰ , F ⁰ respectively;

(6.2) Determine whether the current solution is a feasible solution and whether the number of drones can continue to decrease:

If fsb_C=fsb_U=1 and flag=0, then the current solution is a feasible solution and the number of drones can continue to decrease, perform (6.3); otherwise, jump to step (6.5);

(6.3) Save the current feasible solutions N, Z, C, U, F, and remove a redundant UAV to obtain the current number N of UAVs and the deployment position Z of UAVs:

(6.3.1) Set five temporary values of N _temp , Z _temp , C _temp , U _temp , and F _temp and assign a value of 0 to save feasible N, Z, C, U, and F;

(6.3.2) Let N _temp , Z _temp , C _temp , U _temp , F _temp be equal to N, Z, C, U, F respectively;

(6.3.3) Calculate the Euclidean distance d _n1-n2 between each drone in Z, where d _n1-n2 represents the distance between the drone n1 and the drone n2;

(6.3.4) Find out the two drones n1' and n2' with the smallest distance between each drone according to the calculated Euclidean distance d _n1-n2 ;

(6.3.5) Use the distance between UAV n1' and other UAVs to form the first set {d _n1'-1 ,d _n1'-2 ,…,d _n1'-n }, and the UAV The distance between n2' and other drones constitutes the second set {d _n2'-1 ,d _n2'-3 ,…,d _n2'-n }, and sort the elements in these two sets in ascending order;

(6.3.6) Compare the smallest distance value in the distance set of UAV n1' with the smallest distance value in the distance set of UAV n2':

If the minimum distance value in drone n1' is smaller than the minimum distance value in drone n2', delete drone n1';

If the minimum distance value in drone n1' is greater than the minimum distance value in drone n2', delete drone n2';

If the two are equal, compare the next smallest distance value in the two UAV sets;

By analogy, until the two are not equal, the number of drones and the deployment position after the deletion are finally obtained, which is the current number N of drones and the deployment position Z;

(6.4) Update the above parameters C, fsb_C, U, fsb_U, F, E _min , num _max according to the current N and Z:

(6.4.1) Determine the association matrix C and whether the association is a feasible solution fsb_C according to the greedy association strategy:

(6.4.1.1) According to the distance d _mn between user m and drone n, construct a set of candidate drones V _m for each user m to complete the task:

First, calculate the distance d _mn between user m and drone n;

Then, judge whether d _mn < R holds true:

If it is established, it means that the distance between the drone and the user is less than the coverage radius of the drone, and the drone n is included in the candidate set V _m of the user m;

Otherwise, UAV n is not included in the candidate set V _m of user m;

(6.4.1.2) Divide all users into two categories according to the following criteria:

Take the set of only one UAV candidate in the candidate set V _m as the first category;

There are multiple unmanned aerial vehicles in the candidate set _Vm as the second category;

The associated priority of the first type of task is higher than that of the second type of task;

(6.4.1.3) Perform association according to the following association criteria to obtain the association matrix C and whether the association matrix is a feasible solution fsb_C:

First, judge whether the UAVs in the first type of user candidate set are fully connected: if not, set the corresponding c _mn =1, indicating association; otherwise, c _mn =0;

Then, sort them in ascending order according to the number of elements in the candidate set V _m of the second type of users, and give priority to users with smaller candidate sets to determine the association situation. For user m, according to each candidate UAV in its candidate set V _m The distance to user m is sorted in ascending order. If the distance is equal, it is sorted in ascending order according to the number of drone access users, and the user is preferentially associated with the distance

UAVs that are close and have a small number of access users;

(6.4.1.4) According to the above strategy, judge whether there is a situation where the candidate set is empty or the connected UAVs in the candidate set are full:

If so, the association fails, fsb_C=0;

Otherwise, the association is successful, fsb_C=1;

(6.4.2) The minimum resource f _mn,min required by each user for computing at different UAVs is deduced from the following formula:

(6.4.3) Solve the initialization unloading matrix U:

(6.4.3.1) According to N, Z, C and f _mn,min, the problem P is reduced to a 0-1 programming problem P1 about the unloading matrix U:

P1:

s.t.P1:C3,C4,C6

(6.4.3.2) Use the branch and bound method to solve P1, obtain U and fsb_U indicating whether the decision is a feasible solution, that is, use the library function of the branch and bound method in the simulation software to solve;

(6.4.4) Calculate the elements in F according to the elements u _mn in U: f _mn =u _mn f _mn,min , finally get the computing resource allocation matrix F=[f _mn ] _M×N , and set NoS=NoS+ 1;

(6.4.5) Judging whether the initial solution is a feasible solution, that is, whether fsb_C=fsb_U=1 is established:

If it is established, then calculate the total energy consumption E of the system corresponding to the current solution according to N, Z, C, U, and F, let E _min =E, and complete the maximum number of tasks num _max =M;

If not, find the number of calculation tasks num completed by this group of solutions, and judge whether num>num _max is true:

If so, then make num _max =num, return to step (6.2);

Otherwise, do not modify num _max and directly return to step (6.2);

(6.5) Use the improved differential evolution algorithm to determine the parameters Z, C, fsb_C, U, fsb_U, F, E _min , num _max under the current number of drones N:

(6.5.1) The current drone deployment position Z is used as the parent population Q, so the population size is N, and the i-th individual value in the population corresponds to the deployment position of the drone, and the i-th individual in the population is obtained q _i is: q _i =[q _ix ,q _iy ];

(6.5.2) Perform N times of mutation and crossover operations on the population Q to obtain N experimental vector individuals, forming the experimental vector population A:

(6.5.2.1) Perform the mutation operation according to the following formula to obtain the mutation vector e _i :

Among them, λ ₁ , λ ₂ , and λ ₃ are three unequal individuals randomly selected from Q, and g is the differential variation factor, with a value of 0.4.

(6.5.2.2) After the mutation vector is established, cross the mutation vector e _i with a random individual q _i in Q to obtain an experimental individual vector a _i :

Among them, the first dimension a _ix of the experimental individual vector a _i is:

The second dimension a _iy of the experimental individual vector a _i is:

In the above formula, rate _c ∈ [0,1] is the crossover rate, and J _r is a dimension randomly selected in x and y;

(6.5.2.3) The experimental vector population A is composed of N experimental individual vectors a _i ;

(6.5.3) Randomly replace an individual in Q with an individual in A in turn to obtain a new population W;

(6.5.4) According to the UAV deployment position Z _W corresponding to the population W and the number N of UAVs, use the method in (6.2) to determine the corresponding correlation matrix C _W , unloading matrix U _W , and resource allocation matrix F _W , fsb_C and fsb_U;

(6.5.5) According to N, Z _W , C _W , U _W , F _W , calculate the number of completed tasks num _W , let NoS=NoS+1;

(6.5.6) Judging whether num _W > num _max holds true: if so, set the maximum number of completed user tasks num _max = num _W , and let Z, C, U, F be equal to Z _W , C _W , U _W , F respectively _W ; otherwise, no operation is performed;

(6.5.7) Judging whether num _W = M is true:

If it is established, it means that the current solution is a feasible solution, and then calculate the corresponding system energy consumption E _W according to N, Z _W , C _W , U _W , F _W , and execute (6.5.8);

If not established, it means that the current solution is an infeasible solution, that is, num _W < M, set not=not+1, and execute (6.5.9);

(6.5.8) Judging whether E _W > E _min holds true:

If it is true, it means that the solution obtained by the corresponding deployment position of the current population is a feasible solution with lower energy consumption. Let E _min =E _W , and let five temporary solutions N _temp , Z _temp , C _temp , U _temp , F _temp is respectively equal to N, Z _W , C _W , U _W , F _W , judge whether the flag is 0 at this time: if so, it means that the number of unmanned aerial vehicles can continue to be deleted, let not=0; otherwise, execute step (6.5 .9);

If not established, do not operate;

(6.5.9) Judging whether the number of infeasible solutions not=100 holds true:

If it is established, it means that the current number of drones has not found a group of feasible solutions after multiple iterations, so that flag=1 means stop deleting the number of drones, and execute (6.5.10);

If not established, execute (6.5.10) directly;

(6.5.10) Judging whether N _temp , Z _temp , C _temp , U _temp , and F _temp have a preserved feasible solution:

If not, it means that no feasible solution to the problem has been found, and the maximum number of completed tasks num _max will be output, and the algorithm ends;

Otherwise, let N, Z, C, U, F be equal to N _temp , Z _temp , C _temp , U _temp , F _temp ;

(6.6) Judging whether NoS<NoS _max holds true:

If established, return to step (6.2) to continue iterative solution;

Otherwise, the iteration is terminated, and the final solution UAV number N', UAV position Z', correlation matrix C', unloading matrix U', and computing resource allocation matrix F' are obtained.

Step 7, implementing deployment and computing offloading according to the values of N', Z', C', U', and F'.

(7.1) Select N' unmanned aerial vehicles to deploy according to the deployment matrix Z';

(7.2) Determine the correlation between the user and the UAV according to the correlation matrix C':

If the element c _mn =1 in C', associate user m with UAV n, and transmit the computing task of user m to UAV n;

Otherwise, user m is not associated with drone n;

(7.3) According to the element value u _mn in the unloading decision matrix U', determine the execution object of the user computing task:

If u _mn = 1, the drone n allocates computing resources to the user according to the element f _mn in the resource allocation matrix F', and completes the computing task of the user m;

Otherwise, the associated drone n transfers the computing task of user m to the neighbor base station, and the neighbor base station completes the computing task.

Below in conjunction with simulation experiment, technical effect of the present invention is further described:

1. Simulation conditions

The simulation is carried out on the Matlab2019 software platform. Users are randomly distributed in a circular area with a radius of 300m. The number of users is set to _100-300 . Number F _m =100～200cycles/bit, tolerable delay T=1s; UAV height H _n =100m, maximum depression angle θ=π/4, coverage radius R=H _n tanθ=100m, hovering power P ^H =100W, upper limit of access users U _n =20, upper limit of computing resources f _n,max =2 GHz, when the reference distance is one meter, the air-to-ground channel gain β ^G2A and the air-to-air channel gain β ^A2A are both 1.42×10 ^-4 , Transmission power of user and UAV The coordinates of the neighboring base stations are (x ₀ , y ₀ , H ₀ )=(600, 300, 100).

Because what the present invention considers is a new scenario, there is no existing method that can directly solve it, so the solution framework is the upper and lower layer iterative method, but when solving the unloading matrix U and the two parameters of the UAV position Z, other parameters are used. The two algorithms of the method are used as comparison algorithms, wherein, when the prior UAV algorithm solves the unloading decision U, the calculation task is preferentially offloaded to the unmanned aerial vehicle for execution, while the present invention adopts the branch and bound method; PSO-Z solves the unmanned aerial vehicle Particle swarm optimization algorithm is adopted in position Z, while the present invention adopts differential evolution method.

2. Simulation content and results:

In simulation 1, the number of users is taken as 100-300 respectively, and the comparison algorithms of the present invention and the comparison algorithm respectively provide services for users in designated areas, and obtain the total energy consumption of the system and the number of deployed UAVs respectively. The results are shown in Figure 3 Show. in:

Figure 3(a) is a comparison chart of the total energy consumption of the system,

Figure 3(b) is a comparison of the number of deployed UAVs.

Observing Figure 3(a), it can be found that when the number of users is 100, the total energy consumption of the prior UAV is almost the same as that of the present invention, but as the number of users increases, the present invention based on the branch and bound method The gap between the total energy consumption of the system corresponding to the obtained unloading decision and the total energy consumption of the system corresponding to the prior UAV algorithm that is preferentially unloaded to the UAV is getting bigger and bigger, and the energy-saving advantages of the present invention are gradually reflected. From Fig. 3 (a), it can be clearly seen that the system energy consumption of the PSO-Z algorithm using the improved PSO to solve the UAV position is obviously greater than that of the present invention based on the improved differential evolution algorithm, which is mainly because the PSO algorithm is more random when searching. Large, the algorithm performance is not as good as the improved differential evolution algorithm.

It can be seen from Figure 3(b) that when the number of users is 200, the present invention needs to deploy 15 UAVs to complete all computing tasks, while the prior UAV needs to deploy 16 UAVs, and PSO-Z requires Only by deploying 18 drones can all computing tasks be completed, and regardless of the number of users is large or small, the number of drones deployed by the present invention is the least, and the cost is minimal.

Simulation 2, when the tolerable time delay is 1s and the number of users is 300, the task rate of the present invention and the comparative method prior UAV and PSO-Z providing services to users in the designated area is simulated at different time points, and the results are shown in Figure 4 shown.

It can be seen from FIG. 4 that the task completion rate of the present invention is always higher than that of the prior UAV algorithm at different time points, and the task completion rate of the present invention is the same as that of PSO-Z at some time points.

Fig. 3 and Fig. 4 show that the present invention can complete the user's computing task as soon as possible while reducing the cost, and provide the user with a good experience.

Claims (10)

1. The deployment and unloading method of the unmanned aerial vehicle auxiliary edge computing network is characterized by comprising the following steps of:

(1) Setting user related parameters and unmanned aerial vehicle auxiliary network related parameters:

m ground users are randomly distributed in a circular fault area Y with radius L, the set of which is o= {1, …, M, …, M }, and the position of user M is (x) _m ,y _m 0); user m needs to complete computing task A _m ＝(F _m ,D _m T), wherein F _m Representing the number of CPU revolutions required for calculation; d (D) _m Representing the calculated data amount; t is a time delay constraint;

let the unmanned aerial vehicle set be g= {1, …, N, …, N }, N be the total number of unmanned aerial vehicles to be determined, the coordinates of the nth unmanned aerial vehicle be (x) _n ,y _n ,H _n ) The depression angle is fixed to be theta, and the maximum covering radius R is H _n tan θ, set U _n For the maximum value of the number of access users of the unmanned aerial vehicle n, f _n,max Is the upper limit of the calculation resource of the unmanned aerial vehicle n, and the transmitting power isHover power of P ^H None of which is adjustable; let the coordinates of the neighbor base stations be (x ₀ ,y ₀ ,H)；

(2) And establishing a minimum energy consumption problem P according to the initialization parameters:

C3:u _mn ≤c _mn ,m∈O,n∈G，

C5:c _mn d _mn ≤R,m∈O,n∈G，

C6:t _m ≤T,m∈O，

C7:(x _n ,y _n )∈Y,

wherein C is the incidence matrix of the unmanned aerial vehicle and the user, and C _mn An nth column element of an mth row in C;

u is an unloading matrix, U _mn Z is a position matrix of the unmanned aerial vehicle, wherein the element is the mth row and the nth column in U;

f is unmanned aerial vehicle computing resource allocation matrix, F _mn For the nth column element of row m in F,

the communication energy consumption of the unmanned aerial vehicle n is sent to the calculation task for the user m; />Computing energy consumption for completing user m task for unmanned plane n,/->Communication energy consumption for transferring the calculation task of user m to the neighbor base station for unmanned plane n, < ->The energy consumption for hovering of the unmanned aerial vehicle n; alpha represents a weight coefficient of unmanned energy consumption compared with user energy consumption, t _m Calculating for user m the total time for task completion, d _mn Is the horizontal distance between user m and drone n;

(3) Determining the initial number N of unmanned aerial vehicles ⁰ Initial position Z of unmanned aerial vehicle ⁰ The method comprises the steps of carrying out a first treatment on the surface of the According to M ⁰ ，Z ⁰ Determining an initial correlation matrix C ⁰ Whether the correlation matrix is a feasible solution fsb_C or not, and an initial unloading matrix U ⁰ Whether the offload matrix is a feasible solution of fsb_U, initial resource allocation matrix F ⁰ Minimum energy consumption E _min And the maximum number of tasks completed num _max ；

(4) Solving N, Z, C, U, F in problem P using upper and lower layer iterative methods:

(4a) Setting the solving frequency as NoS, and setting the maximum iteration solving frequency as NoS _max Stopping deleting the number of unmanned aerial vehicles to be flag, performing current solution for non, initializing NoS=0, flag=0, non=0 and NoS _max =1000, initialisation N, Z, C, U, F is equal to N respectively ⁰ 、Z ⁰ 、C ⁰ 、U ⁰ 、F ⁰ ；

(4b) Judging whether the current solution is a feasible solution or not and whether the number of unmanned aerial vehicles can be continuously reduced or not:

if fsb_c=fsb_u=1 and flag=0, then the current solution is a feasible solution and the number of unmanned aerial vehicles can continue to decrease, execution (4C); otherwise, jumping to the step (4 e);

(4c) Storing the current feasible solution N, Z, C, U, F, and removing a redundant unmanned aerial vehicle to obtain the current unmanned aerial vehicle number N and unmanned aerial vehicle deployment position Z;

(4d) Updating the parameters C, fsb _ C, U, fsb _ U, F, E according to the current N and Z _min 、num _max Let nos=nos+1, and execute step (4 f);

(4e) Determining parameters Z and Cfsb_ C, U, fsb _ U, F, E of current unmanned aerial vehicle number N by using improved differential evolution algorithm _min 、num _max ；

(4f) Judging that NoS is less than NoS _max If so, returning to the step (4 b) to continue the iterative solution; otherwise, iteration is terminated to obtain the number N ' of the final solution unmanned aerial vehicle, the position Z ' of the unmanned aerial vehicle, the incidence matrix C ', the unloading matrix U ', and the computing resource allocation matrix F ';

(5) N 'unmanned aerial vehicles are selected to be deployed according to a deployment matrix Z';

(6) Determining the relevance of the user and the unmanned aerial vehicle according to the relevance matrix C': if element C in C _mn =1, associating user m with unmanned aerial vehicle n, and transmitting the calculation task of user m to unmanned aerial vehicle n; otherwise, user m is not associated with unmanned plane n;

(7) According to the element values U in the unloading decision matrix U _mn Determining an execution object of a user computing task:

if u _mn =1, then the drone n follows the element F in the resource allocation matrix F _mn Distributing computing resources to users to finish computing tasks of the user m;

otherwise, the associated unmanned aerial vehicle n transfers the calculation task of the user m to the neighbor base station, and the neighbor base station completes the calculation task.

2. The method of claim 1, wherein the minimizing energy consumption problem P is established in step (2) according to the initialization parameters, as follows:

(2a) According to the position coordinates of the user m and the unmanned plane n, obtaining a horizontal distance d between the user m and the unmanned plane n _mn And horizontal distance d between unmanned plane n and neighbor base station _nB ：

(2b) According to the horizontal distance d in (2 a) _mn And horizontal distance d between unmanned plane n and neighbor base station _nB Establishing a channel model based on free space path loss, namely channel power gain h from user m to unmanned plane n _mn And channel power gain h between unmanned plane n and neighbor base station _nB ：

Wherein beta is ^G2A And beta ^A2A The space-to-ground channel gain and the space-to-space channel gain when the reference distance is one meter are respectively represented;

(2c) According to the channel power gain h from user m to drone n in (2 b) _mn And channel power gain h between unmanned plane n and neighbor base station _nB Obtaining the transmission rate r from the user m to the unmanned plane n by using the shannon theorem _mn And the transmission rate r between the unmanned aerial vehicle n and the neighbor base station _nB ：

Wherein B is ₁ Representing transmission bandwidth between user and unmanned aerial vehicle, B ₂ Representing transmission bandwidth between unmanned aerial vehicle and neighbor base station, P _m For the transmit power of the user m device,for the transmitting power of unmanned plane N, N ₀ Is the noise power spectral density;

(2d) Calculating communication transmission time for transmitting calculation task to unmanned plane n by user mCommunication energy consumption->

(2e) Communication transmission time for transferring calculation task of user n to neighbor base station by unmanned aerial vehicle mCommunication energy consumption

(2f) Calculating processing time required by unmanned plane n to complete task of user mCalculating energy consumption->

Wherein f _mn The CPU frequency of the unmanned aerial vehicle n to the user m is represented, and epsilon represents the effective capacitance coefficient of the unmanned aerial vehicle on-board server chip;

(2g) Calculating hovering energy consumption of unmanned plane n

(2h) The following correlation matrix and variables are set:

let C= [ C ] _mn ] _M×N The association matrix of the unmanned aerial vehicle and the user, c _mn =1 means that user m is associated with drone n, c _mn =0 indicates no association;

let U= [ U ] _mn ] _M×N Unloading the decision matrix for the user's calculation, when c _mn =1 and u _mn =1 denotes that unmanned plane n serves user m, c _mn =1 and u _mn =0 means that the associated unmanned plane n transfers the calculation task of the user m to the neighbor base station, and the neighbor base station completes the calculation task;

let F= [ F _mn ] _M×N Allocating a matrix for computing resources;

let Z= [ (x) _n ,y _n )] _N×1 Is a position matrix of the unmanned plane;

the total time for completing the calculation task of the user is set as follows:

from the results of (2 d) (2 e) (2 f) (2 g), the total system energy consumption was:

(2i) Setting constraint conditions:

according to the characteristic that one user can only be associated with one unmanned aerial vehicle and all users need to be covered, a first constraint condition is set:

according to the limit that the number of users accessed by each unmanned aerial vehicle cannot exceed the maximum number of users accessed, setting a second constraint condition

According to which unmanned aerial vehicle can only be associatedIs provided with a third constraint u _mn ≤c _mn ；

Setting a fourth constraint according to the limit that the sum of the computing resources allocated to the users in the coverage area by the unmanned aerial vehicle m does not exceed the maximum value of the computing resources

According to the condition that the user associated with the unmanned aerial vehicle needs to be in the coverage range, setting a fifth constraint c _mn d _mn ≤R；

Setting a sixth constraint t according to the limit that the task completion time of the user n does not exceed the maximum tolerance time delay _m ≤T；

According to the limitation that the horizontal position of the unmanned aerial vehicle needs to be in the range of the fault base station, a seventh constraint condition (x _n ,y _n )∈Y；

(2j) The energy consumption minimization problem P is expressed as follows, in combination with the constraints and parameters described above:

C3:u _mn ≤c _mn ,m∈O,n∈G，

C5:c _mn d _mn ≤R,m∈O,n∈G，

C6:t _m ≤T,m∈O，

C7:(x _n ,y _n )∈Y,

where α represents a weight coefficient of unmanned energy consumption compared to user energy consumption.

3. The method according to claim 1, wherein the number N of unmanned aerial vehicles is determined in step (3) ⁰ Unmanned plane position Z ⁰ The implementation is as follows:

(3a) Initializing the number of unmanned aerial vehicles to be a larger value N ⁰ ＝2×(M/U _n )；

(3b) Determining an initial position Z of the unmanned aerial vehicle through Kmeans++ algorithm ⁰ The number of cycles iter=0 is set:

(3b1) The number N of unmanned aerial vehicles is calculated by means of Kmeans++ algorithm ⁰ As class number, clustering is carried out according to the position of the user, and a clustering center is used as the deployment position of the unmanned aerial vehicle;

(3b2) Determining a candidate set V of each user m to execute the task according to the unmanned aerial vehicle deployment position obtained in (3 b 1) _m ：

(3 b2 a) calculating the distance d between the user m and the unmanned plane n _mn ；

(3 b2 b) judgment of d _mn Whether < R holds: if so, the distance between the unmanned aerial vehicle and the user is smaller than the coverage radius of the unmanned aerial vehicle, and the unmanned aerial vehicle n is listed as a candidate set V of the user m _m In (a) and (b);

(3b3) Determining an initial position Z of an unmanned aerial vehicle ⁰ ：

(3 b3 a) determining whether the candidate set for all users is empty: if not, the current unmanned plane position is taken as an initial position Z ⁰ The method comprises the steps of carrying out a first treatment on the surface of the Otherwise, let iter=iter+1, execute step (3 b3 b);

(3 b3 b) judging whether the item > 1000 is true:

if so, the fact that the initial position of the unmanned aerial vehicle meeting the constraint is not found all the time through multiple clustering is indicated, and a clustering center obtained in the last iteration is used as the initial position of the unmanned aerial vehicle;

Otherwise, returning to the step (3 b 1) to solve the initial position of the unmanned aerial vehicle again.

4. According to claim 1The method is characterized in that in the step (3), the method is carried out according to N ⁰ ，Z ⁰ Determining an association matrix C ⁰ And whether the association is a viable solution fsb_c, implemented as follows:

(3c) Obtaining an association matrix C by adopting greedy association strategy ⁰ And whether the association is a feasible solution fsb_c:

(3c1) Calculating the distance d between the user m and the unmanned plane n _mn Will d _mn Unmanned plane n < R listed in candidate set V for user m _m In (a) and (b);

(3c2) All users are classified into two categories according to the following criteria:

first category: candidate set V _m Only one unmanned aerial vehicle alternative, namely the user is only in the coverage radius of one unmanned aerial vehicle;

the second category: candidate set V _m A plurality of unmanned aerial vehicle alternatives are provided, which indicates that the user is in the coverage range of a plurality of unmanned aerial vehicles;

the associated priority of the first type of task is higher than that of the second type of task;

(3c3) Performing association according to the following association criteria to obtain an association matrix C ⁰ Whether the solution is a viable solution fsb_c:

(3 c3 a) determining whether the drones in the first class of user candidate set are full: if not full, let the corresponding c _mn =1, representing association;

(3 c3 b) according to the second class of user candidate sets V _m The element numbers in the list are sequenced in an ascending order, the association condition is determined for the users with small candidate sets preferentially, and for the user m, the association condition is determined according to the candidate set V _m According to the distance from each candidate unmanned aerial vehicle to the user m, sorting according to ascending order of the number of access users of the unmanned aerial vehicles if the distances are equal, and preferentially associating the users to unmanned aerial vehicles which are close in distance and less in number of access users;

(3c4) Judging whether the candidate set is empty or whether associable unmanned aerial vehicles in the candidate set are all full according to the strategy:

if yes, the association fails, fsb_c=0;

otherwise, the association is successful, fsb_c=1.

5. The method according to claim 1, wherein in step (3) according to N ⁰ ，Z ⁰ Determining an unloading matrix U ⁰ Whether the offload matrix is a feasible solution fsb_U, resource allocation matrix F ⁰ The implementation is as follows:

(3d) The minimum resources f required for each user to calculate at different drones are deduced from _mn,min ：

(3e) Solving initialization unloading matrix U ⁰ ：

(3e1) According to N ⁰ ，Z ⁰ ，C ⁰ And f _mn,min Simplifying problem P as related to offload matrix U ⁰ 0-1 programming problem P1:

s.t.P1:C3,C4,C6

(3e2) Solving P1 by using branch delimitation method to obtain U ⁰ And fsb_U representing whether the offload matrix is a feasible solution, i.e. solving with library functions in simulation software for branch-and-bound methods;

(3f) According to U ⁰ Element u in (3) _mn Calculation F ⁰ Elements of (a) and (b): f (f) _mn ＝u _mn f _mn,min Finally, a computing resource allocation matrix F is obtained ⁰ ＝[f _mn ] _M×N 。

6. The method according to claim 1, wherein in step (3) according to N ⁰ ，Z ⁰ Determining minimum energy consumption E _min And a maximum number of tasks completed num _max The implementation is as follows:

(3g) It is determined whether the initial solution is a feasible solution, i.e., whether fsb_c=fsb_u=1 holds:

if a solution is feasible, according to N ⁰ 、Z ⁰ 、C ⁰ 、U ⁰ 、F ⁰ Calculating the total system energy consumption E corresponding to the current solution ⁰ Initializing a minimum energy consumption E of the system _min ＝E ⁰ Number of tasks at maximum num _max ＝M；

Otherwise, calculating the number num of users completing the task in the time delay constraint ⁰ Initializing a minimum energy consumption E of the system _min The maximum number of tasks num is completed with a maximum value _max ＝num ⁰ 。

7. The method of claim 1, wherein step (4C) stores the current feasible solutions N, Z, C, U, F and removes a redundant unmanned aerial vehicle to obtain the current N and Z, as follows:

(4c1) Setting N _temp ，Z _temp ，C _temp ，U _temp ，F _temp The five temporary values are assigned with 0 and are used for storing feasible N, Z, C, U and F;

(4c2) Let N _temp ，Z _temp ，C _temp ，U _temp ，F _temp Respectively equal to N, Z, C, U and F;

(4c3) Calculating Euclidean distance d between unmanned aerial vehicles in Z _n1-n2 D is as follows _n1-n2 Representing a distance between unmanned plane n1 and unmanned plane n 2;

(4c4) According to the calculated Euclidean distance d _n1-n2 Finding out two unmanned aerial vehicles n1 'and n2' with minimum distances among all unmanned aerial vehicles;

(4c5) Forming a first set { d ] by the distance between the unmanned aerial vehicle n1' and other unmanned aerial vehicles _n1'-1 ,d _n1'-2 ,…,d _n1'-n The distance between the unmanned plane n2' and other unmanned planes forms a second set { d }, and _n2'-1 ,d _n2'-3 ,…,d _n2'-n -and ordering the elements in the two sets in ascending order;

(4c6) Comparing the minimum distance value in the distance set of the unmanned plane n1 'with the minimum distance value in the distance set of the unmanned plane n 2':

if the minimum distance value in the unmanned plane n1' is smaller than the minimum distance value in the unmanned plane n2', deleting the unmanned plane n1';

if the minimum distance value in the unmanned plane n1' is larger than the minimum distance value in the unmanned plane n2', deleting the unmanned plane n2';

if the two are equal, comparing the next-smallest distance value in the two unmanned aerial vehicle sets, and the like until the two unmanned aerial vehicle sets are not equal;

and finally obtaining the number of the unmanned aerial vehicles and the deployment position after deletion, namely the current number N of the unmanned aerial vehicles and the deployment position Z.

8. The method according to claim 1, wherein step (4 d) determines, based on the current number N of drones and the deployment location Z, an association matrix C and whether the association is a feasible solution fsb_c, implemented as follows:

(4d1) Determining an association matrix C and whether the association is a feasible solution fsb_C according to a greedy association strategy:

(4 d1 a) according to the distance d from the user m to the unmanned plane n _mn Constructing a candidate unmanned aerial vehicle set V for each user m to complete tasks _m ：

First, the distance d between the user m and the unmanned plane n is calculated _mn ；

Then, judge d _mn Whether < R holds:

if so, the distance between the unmanned aerial vehicle and the user is smaller than the coverage radius of the unmanned aerial vehicle, and the unmanned aerial vehicle n is listed in a candidate set V of the user m _m In (a) and (b);

otherwise, not listing unmanned plane n in candidate set V of user m _m In (a) and (b);

(4 d1 b) classifying all users into two categories according to the following criteria:

will candidate set V _m Only one unmanned aerial vehicle alternative set is used as a first class;

will candidate set V _m A plurality of unmanned aerial vehicle alternative sets are used as a second class;

the associated priority of the first type of task is higher than that of the second type of task;

(4 d 1C) performing association according to the following association criteria to obtain an association matrix C and whether the association matrix is a feasible solution fsb_C:

firstly, judging whether unmanned aerial vehicles in a first type of user candidate set are full: if not full, let the corresponding c _mn =1, representing association; otherwise, c _mn ＝0；

Then, according to the second class of user candidate sets V _m The element numbers in the list are sequenced in an ascending order, the association condition is determined for the users with small candidate sets preferentially, and for the user m, the association condition is determined according to the candidate set V _m According to the distance from each candidate unmanned aerial vehicle to the user m, sorting according to ascending order of the number of access users of the unmanned aerial vehicles if the distances are equal, and preferentially associating the users to unmanned aerial vehicles which are close in distance and less in number of access users;

(4 d1 d) judging whether the candidate set is empty or the associable unmanned aerial vehicles in the candidate set are all full according to the strategy:

if yes, the association fails, fsb_c=0;

otherwise, the association is successful, fsb_c=1.

9. The method according to claim 1, wherein step (4 d) determines whether the offload matrix U, the offload matrix is a feasible solution fsb_u, the resource allocation matrix F, the minimum energy consumption E according to the current number of unmanned aerial vehicles N and the deployment location Z _min And a maximum number of tasks completed num _max The implementation is as follows:

(4d2) The minimum resources f required for each user to calculate at different drones are deduced from _mn,min ：

(4d3) Solving an initialization unloading matrix U:

(4 d3 a) is according to N, Z, C and f _mn,min Simplifying the problem P into a 0-1 programming problem P1 with respect to the offload matrix U:

s.t.P1:C3,C4,C6

(4 d3 b) solving the P1 by using a branch-and-bound method to obtain U and fsb_U which indicates whether the decision is a feasible solution, namely solving by using a library function related to the branch-and-bound method in simulation software;

(4d4) According to element U in U _mn Calculation F ⁰ Elements of (a) and (b): f (f) _mn ＝u _mn f _mn,min Finally, a computing resource allocation matrix F= [ F ] is obtained _mn ] _M×N ；

(4d5) It is determined whether the initial solution is a feasible solution, i.e., whether fsb_c=fsb_u=1 holds:

if yes, calculating the total system energy consumption E corresponding to the current solution according to N, Z, C, U, F, and letting E _min =e, the maximum number of tasks done num _max ＝M；

Otherwise, solving the number of calculation tasks num completed by the solution, and judging that num > num _max If true, let num _max =num; returning to step (4 b).

10. The method of claim 1, wherein the step (4 e) uses a modified differential evolution algorithm to find Z, C, fsb _ C, U, fsb _ U, F, E for the current number N of drones _min 、num _max The implementation is as follows:

(4e1) Taking the current unmanned aerial vehicle deployment position Z as a parent population Q, so the population size is N, and the ith individual value in the population corresponds to the unmanned aerial vehicle deployment position, so the ith individual Q in the population _i The method comprises the following steps: q _i ＝[q _ix ,q _iy ]；

(4e2) Performing mutation and crossover operation on the population Q for N times to obtain N experimental vector individuals, and forming an experimental vector population A:

(4 e2 a) performing a mutation operation according to the following formula to obtain a mutation vector e _i ：

Wherein lambda is ₁ ,λ ₂ ,λ ₃ For randomly selected in QThree mutually unequal individuals, g is a differential variation factor, and the value is 0.4.

(4 e2 b) after the mutation vector is established, the mutation vector e _i With one random individual Q of Q _i Crossing to obtain an experimental individual vector a _i ：

Wherein, the experimental individual vector a _i Is a first dimension a of (2) _ix The method comprises the following steps:

experimental individual vector a _i Is a second dimension a of (2) _iy The method comprises the following steps:

in the above formula rate _c ∈[0,1]Is the crossing rate, J _r Randomly selecting one dimension in x and y;

(4 e2 c) vector a from N experimental individuals _i Forming an experimental vector population A;

(4e3) Randomly replacing one individual in the Q with the individuals in the A in sequence to obtain a new population W;

(4e4) Unmanned aerial vehicle deployment position Z corresponding to population W _W And the number N of unmanned aerial vehicles, and determining a corresponding incidence matrix C by adopting the method in (4 b) _W Unloading matrix U _W Resource allocation matrix F _W fsb_C and fsb_U;

(4e5) According to N, Z _W 、C _W 、U _W 、F _W Calculating the number of completed tasks num _W Let nos=nos+1;

(4e6) Judging num _W ＞num _max Whether or not it is: if yes, make the number of tasks of the user number num at maximum _max ＝num _W And let Z, C, U, F respectivelyEqual to Z _W ，C _W ，U _W ，F _W The method comprises the steps of carrying out a first treatment on the surface of the Otherwise, not operating;

(4e7) Judging num _W Whether or not M holds:

if so, then the current solution is indicated as a feasible solution, again according to N, Z _W 、C _W 、U _W 、F _W Calculating corresponding system energy consumption E _W Executing (4 e 8);

if not, it indicates that the current solution is not a feasible solution, i.e., num _W Let not=not+1, execute (4 e 9);

(4e8) Judgment E _W ＞E _min Whether or not it is:

if yes, the solution obtained by the corresponding deployment position of the current population is a feasible solution, the energy consumption is lower, and E is caused to be _min ＝E _W And let five temporary solutions N _temp 、Z _temp 、C _temp 、U _temp 、F _temp Respectively equal to N, Z _W 、C _W 、U _W 、F _W Judging whether the flag is 0 at this time: if yes, the number of unmanned aerial vehicles can be continuously deleted, and the non=0; otherwise, executing the step (4 e 9);

if not, not operating;

(4e9) Judging whether the infeasible solution times not=100 is satisfied: if yes, the fact that the number of the current unmanned aerial vehicles still does not find a group of feasible solutions after multiple iterations is indicated, the flag=1 is indicated to stop deleting the number of the unmanned aerial vehicles, and the method is executed (4 e 10);

(4e10) Judging N _temp ，Z _temp ，C _temp ，U _temp ，F _temp Whether there are stored feasible solutions:

if not, the feasible solution of the problem is not found all the time, and the maximum number of tasks is num _max Outputting, and ending the algorithm;

otherwise, let N, Z, C, U, F respectively equal to N _temp ，Z _temp ，C _temp ，U _temp ，F _temp 。