Movatterモバイル変換

[0]ホーム
URL:

CN111552313B - Multi-unmanned aerial vehicle path planning method based on edge calculation dynamic task arrival - Google Patents

Multi-unmanned aerial vehicle path planning method based on edge calculation dynamic task arrivalDownload PDF

Info

Publication number
CN111552313B
CN111552313BCN202010357106.2ACN202010357106ACN111552313BCN 111552313 BCN111552313 BCN 111552313BCN 202010357106 ACN202010357106 ACN 202010357106ACN 111552313 BCN111552313 BCN 111552313B
Authority
CN
China
Prior art keywords
user
time slot
unmanned aerial
aerial vehicle
optimization
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CN202010357106.2A
Other languages
Chinese (zh)
Other versions
CN111552313A (en
Inventor
孙文煜
王霏霏
钱玉文
李骏
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nanjing University of Science and Technology
Original Assignee
Nanjing University of Science and Technology
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nanjing University of Science and TechnologyfiledCriticalNanjing University of Science and Technology
Priority to CN202010357106.2ApriorityCriticalpatent/CN111552313B/en
Publication of CN111552313ApublicationCriticalpatent/CN111552313A/en
Application grantedgrantedCritical
Publication of CN111552313BpublicationCriticalpatent/CN111552313B/en
Expired - Fee Relatedlegal-statusCriticalCurrent
Anticipated expirationlegal-statusCritical

Links

Images

Classifications

Landscapes

Abstract

Translated fromChinese

本发明公开了一种基于边缘计算动态任务到达的多无人机路径规划方法，包括：建立多无人机协同服务用户的系统模型；构建多无人机路径规划问题；将问题简化为单个时隙内的优化问题；将优化问题分解为用户频率优化子问题和多无人机路径优化与用户关联子问题的联合优化问题。相对于单无人机场景，本发明增加了多个无人机的多个任务和能量队列，且增加了调度限制条件来保证多无人机之间的协作通信。此外为解决复杂的多无人机路径规划调度问题，将李雅普诺夫队列优化理论和块迭代下降算法结合，并利用线性松弛和连续凸近似进一步降低问题复杂度。仿真结果显示多无人机服务地面用户系统相对单无人机系统而言，无人机能耗有所下降并且队列积压任务量减少。

Figure 202010357106

The invention discloses a multi-UAV path planning method based on the arrival of dynamic tasks based on edge computing, including: establishing a system model for multi-UAV cooperative service users; building a multi-UAV path planning problem; simplifying the problem into a single time The optimization problem in the gap; the optimization problem is decomposed into the user frequency optimization sub-problem and the joint optimization problem of multi-UAV path optimization and user-related sub-problem. Compared with a single UAV scenario, the present invention increases multiple tasks and energy queues of multiple UAVs, and adds scheduling constraints to ensure cooperative communication among multiple UAVs. In addition, in order to solve the complex multi-UAV path planning and scheduling problem, the Lyapunov queue optimization theory and block iterative descent algorithm are combined, and linear relaxation and continuous convex approximation are used to further reduce the complexity of the problem. The simulation results show that compared with the single UAV system, the multi-UAV serving ground user system reduces the energy consumption of the UAV and reduces the backlog of tasks in the queue.

Figure 202010357106

Description

Translated fromChinese
基于边缘计算动态任务到达的多无人机路径规划方法Multi-UAV Path Planning Method Based on Dynamic Task Arrival of Edge Computing

技术领域technical field

本发明属于无线通信技术领域，特别是一种基于边缘计算动态任务到达的多无人机路径规划方法。The invention belongs to the technical field of wireless communication, in particular to a multi-UAV path planning method based on edge computing dynamic task arrival.

背景技术Background technique

随着时代的发展和用户对通信及数据处理的需求，无人机结合小型基站实时为地面用户提供通信服务已得到广泛应用。而考虑到无人机自身能耗限制，为了最大化无人机的工作能效，需要对无人机的飞行路径进行合理规划。With the development of the times and the needs of users for communication and data processing, UAVs combined with small base stations to provide real-time communication services for ground users have been widely used. Considering the limitation of the UAV's own energy consumption, in order to maximize the energy efficiency of the UAV, it is necessary to reasonably plan the flight path of the UAV.

通过优化其飞行路径，无人机可以往偏向用户的方向飞行，从而缩短两者之间的距离，提高信道容量。但是，过于靠近某一用户又意味着与其他用户距离变远(假设用户在某一范围内均匀分布)，导致远端用户的通信服务质量变差。与此同时，频繁的移动会导致无人机的耗能过多，缩短其服务时间。因此，设置一条合理的飞行路径，在满足每个用户需求的同时最大化系统效能是无人机研究方向的重点所在。论文1“Joint Trajectory andCommunication Design for UAV-Enabled Multiple Access”利用连续凸优化技术来规划无人机基站的飞行路径。在无人机飞行速度的限制下，该文将问题首先建模为非凸混合整数优化问题，其次再通过迭代算法将问题根据优化变量的不同进行分解，最终再利用连续凸优化技术来解得无人机最优飞行轨迹。从而最大化最小吞吐量，保证公平性的同时显著提升了系统性能。论文2“Joint Trajectory and Communication Design for Multi-UAVEnabled Wireless Networks”在论文1的基础上设想了多无人机作为基站的通信模型。利用多无人机协同服务地面用户来进一步提升了系统的吞吐量。不同于论文2考虑多无人机，论文3“Common Throughput Maximization in UAV-Enabled OFDMA Systems With DelayConsideration”为了更好的服务用户，考虑到了用户所提出的延迟限制。并进一步在OFDM通信机制的基础上，利用连续凸优化技术规划出最佳无人机路径。By optimizing its flight path, the drone can fly in a direction that is biased towards the user, thereby shortening the distance between the two and increasing the channel capacity. However, being too close to a certain user means that the distance from other users becomes farther (assuming users are evenly distributed in a certain range), resulting in poor communication service quality for remote users. At the same time, frequent movement can cause the drone to consume too much energy and shorten its service time. Therefore, setting a reasonable flight path and maximizing system performance while meeting the needs of each user is the focus of UAV research.Paper 1 "Joint Trajectory and Communication Design for UAV-Enabled Multiple Access" uses continuous convex optimization technique to plan the flight path of UAV base station. Under the limitation of the flying speed of the UAV, this paper firstly models the problem as a non-convex mixed integer optimization problem, and then decomposes the problem according to the different optimization variables through an iterative algorithm, and finally uses the continuous convex optimization technique to solve the problem. The optimal flight path of the UAV. In this way, the minimum throughput is maximized, and the system performance is significantly improved while ensuring fairness.Paper 2 "Joint Trajectory and Communication Design for Multi-UAVEnabled Wireless Networks", based onPaper 1, envisages a communication model with multiple UAVs as base stations. The throughput of the system is further improved by using multiple UAVs to serve ground users collaboratively. Unlikepaper 2 which considers multiple UAVs, paper 3 "Common Throughput Maximization in UAV-Enabled OFDMA Systems With DelayConsideration" takes into account the delay constraints proposed by users in order to better serve users. And further on the basis of OFDM communication mechanism, the optimal UAV path is planned by using continuous convex optimization technology.

综上所述，现阶段对无人机的路径规划方案并没有考虑无人机的能量消耗，并且在无人机服务用户的过程中忽略了基站服务器本身处理能力受限而带来的等待延迟。同时，单无人机路径规划由于自身能力受限，存在大范围区域内通信效能低下的情况。In summary, the current path planning scheme for UAVs does not consider the energy consumption of UAVs, and ignores the waiting delay caused by the limited processing capacity of the base station server itself in the process of UAV serving users. . At the same time, due to the limited capability of the single UAV path planning, there is a situation of low communication efficiency in a large area.

发明内容SUMMARY OF THE INVENTION

本发明的目的在于提供一种基于边缘计算动态任务到达的多无人机路径规划方法。The purpose of the present invention is to provide a multi-UAV path planning method based on edge computing dynamic task arrival.

实现本发明目的的技术解决方案为：基于边缘计算动态任务到达的多无人机路径规划方法，所述方法包括：The technical solution for realizing the object of the present invention is: a multi-UAV path planning method based on edge computing dynamic task arrival, the method includes:

步骤1，建立多无人机协同服务地面用户的系统模型；Step 1, establish a system model of multi-UAV cooperative service for ground users;

步骤2，基于系统模型构建整个周期内的多无人机路径规划问题；Step 2, based on the system model, construct the multi-UAV path planning problem in the whole cycle;

步骤3，利用Lyapunov队列优化理论简化所述整个周期内的多无人机路径规划问题，获得单个时隙内的优化问题；Step 3, using the Lyapunov queue optimization theory to simplify the multi-UAV path planning problem in the entire cycle to obtain the optimization problem in a single time slot;

步骤4，按照时间顺序，依次对每个所述单个时隙内的优化问题进行进一步优化：将所述单个时隙内的优化问题分解为用户频率优化子问题和多无人机路径优化与用户关联子问题的联合优化问题，并求解两个子问题。Step 4, according to the time sequence, further optimize the optimization problem in each of the single time slot: decompose the optimization problem in the single time slot into the user frequency optimization sub-problem and the multi-UAV path optimization and user A joint optimization problem that correlates subproblems and solves both subproblems.

进一步地，步骤1所述建立多无人机协同服务地面用户的系统模型，具体包括：Further, instep 1, a system model for establishing a multi-UAV cooperative service for ground users specifically includes:

步骤1-1，定义地面用户的相关变量，包括：Step 1-1, define the relevant variables of the ground user, including:

定义用户数量为K；Define the number of users as K;

定义用户地理位置：Define user geographic location:

zk＝(xk,yk),k∈{1,2,…K}zk =(xk ,yk ),k∈{1,2,…K}

式中，zk为第k个用户的地理位置，(xk,yk)为第k个用户的地理位置坐标；In the formula, zk is the geographic location of the k th user, and (xk , yk ) is the geographic location coordinates of the k th user;

步骤1-2，定义无人机的相关变量，包括：Step 1-2, define the relevant variables of the drone, including:

定义无人机服务用户的任务周期

Figure BDA0002473838220000021
Defining mission cycles for UAV service users
Figure BDA0002473838220000021

Figure BDA0002473838220000022
Figure BDA0002473838220000022

该式表示一个任务周期

Figure BDA0002473838220000023
内包括T个时隙，每个时隙的长度均为δ；This formula represents a task period
Figure BDA0002473838220000023
It includes T time slots, and the length of each time slot is δ;

定义无人机数量集

Figure BDA0002473838220000024
Define the set of drone numbers
Figure BDA0002473838220000024

Figure BDA0002473838220000025
Figure BDA0002473838220000025

该式表示无人机数量集

Figure BDA0002473838220000026
包括N个无人机；This formula represents the number set of UAVs
Figure BDA0002473838220000026
Including N drones;

定义每个无人机的飞行高度：

Figure BDA0002473838220000027
Hn表示第n个无人机的飞行高度；Define the flying height of each drone:
Figure BDA0002473838220000027
Hn represents the flying height of the nth drone;

定义每个无人机在单个时隙的水平位置：Define the horizontal position of each drone in a single time slot:

Figure BDA0002473838220000028
Figure BDA0002473838220000028

式中，wn(t)为第n个无人机在第t个时隙的水平位置，(xn(t),yn(t))为第n个无人机在第t个时隙的水平位置坐标，

Figure BDA0002473838220000031
In the formula, wn (t) is the horizontal position of the n-th UAV at the t-th time slot, and (xn (t), yn (t)) is the n-th UAV at the t-th time slot. the horizontal position coordinates of the gap,
Figure BDA0002473838220000031

定义每个无人机在单个时隙内的水平飞行速度：Define the horizontal flight speed of each drone in a single time slot:

Figure BDA0002473838220000032
Figure BDA0002473838220000032

式中，νn(t)表示第n个无人机在第t个时隙内的水平飞行速度，νmax为单个时隙无人机所能达到的最大水平飞行速度，其值自定义设置；In the formula, νn (t) represents the horizontal flight speed of the n-th UAV in the t-th time slot, νmax is the maximum horizontal flight speed that the UAV can achieve in a single time slot, and its value is customized ;

步骤1-3，构建数据传输模型，包括：Steps 1-3, build a data transmission model, including:

定义二进制变量αk,n(t)，该变量表示在第t个时隙内第n个无人机与第k个用户之间建立通信链接；记该二进制变量为用户关联变量；Define a binary variable αk,n (t), which represents the establishment of a communication link between the n-th UAV and the k-th user in the t-th time slot; denote this binary variable as a user-related variable;

对所述二进制变量αk,n(t)进行条件限制，所用公式为：Conditioning the binary variable αk,n (t), the formula used is:

Figure BDA0002473838220000033
Figure BDA0002473838220000033

Figure BDA0002473838220000034
Figure BDA0002473838220000034

定义第n个无人机与第k个用户之间在单个时隙的上传速率：Define the upload rate between the nth drone and the kth user in a single slot:

Figure BDA0002473838220000035
Figure BDA0002473838220000035

其中，Rk,n(t)表示第n个无人机与第k个用户之间在第t个时隙的上传速率，hk,n(t)表示第k个用户与第n个无人机之间的信道增益，公式为：Among them, Rk,n (t) represents the upload rate between the n-th drone and the k-th user in the t-th time slot, and hk,n (t) represents the k-th user and the n-th unmanned aerial vehicle. The channel gain between man and machine, the formula is:

Figure BDA0002473838220000036
Figure BDA0002473838220000036

式中，ρ0为单位距离内的信道增益，σ2为AWGN功率，p0为用户发射功率；In the formula, ρ0 is the channel gain within a unit distance, σ2 is the AWGN power, and p0 is the user transmit power;

根据二进制变量αk,n(t)和上传速率Rk,n(t)计算在单个时隙内无人机与用户之间传输的数据量大小：Calculate the amount of data transmitted between the UAV and the user in a single time slot according to the binary variable αk,n (t) and the upload rate Rk,n (t):

Figure BDA0002473838220000037
Figure BDA0002473838220000037

式中，

Figure BDA0002473838220000038
表示在第t个时隙内第n个无人机与第k个用户之间传输的数据量大小，B为信道带宽；In the formula,
Figure BDA0002473838220000038
Indicates the amount of data transmitted between the n-th UAV and the k-th user in the t-th time slot, and B is the channel bandwidth;

步骤1-4，构建任务队列模型，具体包括：Steps 1-4, build a task queue model, including:

(1)构建单个时隙用户端任务队列集合：(1) Construct a single-slot user-side task queue set:

Figure BDA0002473838220000041
Figure BDA0002473838220000041

式中，Qk(t)表示在第t个时隙第k个用户的任务队列，在t＝0时，初始化Qk(t)＝0；在第t+1个时隙第k个用户的任务队列Qk(t+1)为：In the formula, Qk (t) represents the task queue of the k-th user in the t-th time slot. When t=0, initialize Qk (t)=0; in the t+1-th time slot, the k-th user is initialized. The task queue Qk (t+1) of is:

Figure BDA0002473838220000042
Figure BDA0002473838220000042

式中，ak(t)表示第k个用户在第t个时隙接收任务量的大小，

Figure BDA0002473838220000043
表示第k个用户在第t个时隙上传给无人机的任务量总和，
Figure BDA0002473838220000044
表示第k个用户在第t个时隙处理完成的本地任务量大小，公式为：In the formula, ak (t) represents the size of the task received by the kth user in the tth time slot,
Figure BDA0002473838220000043
represents the sum of the tasks uploaded by the kth user to the UAV in the tth time slot,
Figure BDA0002473838220000044
Indicates the amount of local tasks processed by the kth user in the tth time slot, and the formula is:

Figure BDA0002473838220000045
Figure BDA0002473838220000045

式中，ζk表示第k个用户每计算1bit的任务量所需的CPU转数，

Figure BDA0002473838220000046
表示第k个用户在第t个时隙内的CPU计算频率；In the formula, ζk represents the number of CPU revolutions required by the kth user to calculate the task amount of 1 bit,
Figure BDA0002473838220000046
Indicates the CPU computing frequency of the kth user in the tth time slot;

(2)构建单个时隙无人机端的任务队列集合：(2) Construct a task queue set on the UAV side of a single time slot:

Figure BDA0002473838220000047
Figure BDA0002473838220000047

式中，Mk,n(t)表示在第t个时隙第n个无人机为第k个用户所储存的任务队列长度，在t＝0时，初始化Mk,n(t)＝0；在第t+1个时隙第n个无人机为第k个用户所储存的任务队列长度Mk,n(t+1)为：In the formula, Mk,n (t) represents the task queue length stored by the n-th UAV for the k-th user in the t-th time slot. When t=0, initialize Mk,n (t)= 0; the task queue length Mk,n (t+1) stored by the n-th UAV for the k-th user in the t+1-th time slot is:

Figure BDA0002473838220000048
Figure BDA0002473838220000048

其中，

Figure BDA0002473838220000049
表示第n个无人机为第k个用户在第t个时隙内所处理任务量的大小，
Figure BDA00024738382200000410
表示第n个无人机在第t个时隙内为第k个用户分配的处理频率；in,
Figure BDA0002473838220000049
Represents the size of the task that the n-th UAV handles for the k-th user in the t-th time slot,
Figure BDA00024738382200000410
represents the processing frequency allocated by the nth UAV for the kth user in the tth time slot;

步骤1-5，构建能量队列模型，具体包括：Steps 1-5, build an energy queue model, including:

(1)构建单个时隙用户端的计算能耗：(1) Constructing the computational energy consumption of a single time slot user end:

Figure BDA0002473838220000051
Figure BDA0002473838220000051

其中，

Figure BDA0002473838220000052
表示第k个用户在第t个时隙内的计算能耗，公式为：in,
Figure BDA0002473838220000052
Represents the computing energy consumption of the kth user in the tth time slot, and the formula is:

Figure BDA0002473838220000053
Figure BDA0002473838220000053

式中，γ为有效开关电容常数；where γ is the effective switched capacitance constant;

(2)构建单个时隙无人机端的能量队列集合：(2) Construct a set of energy queues on the UAV side of a single time slot:

Figure BDA0002473838220000054
Figure BDA0002473838220000054

式中，En(t)表示第n个无人机在第t个时隙内电池电量的大小，在t＝0时，初始化En(t)＝0；第n个无人机在第t+1个时隙内电池电量的大小En(t+1)为：In the formula, En (t) represents the size of the battery power of the n-th UAV in the t-th time slot. When t=0, initializeEn (t)=0; the n-th UAV is in the t-th time slot. The size of the battery power in t+1 time slots,En (t+1), is:

Figure BDA0002473838220000055
Figure BDA0002473838220000055

其中，

Figure BDA0002473838220000056
表示在第t个时隙内第n个无人机所吸收的太阳能量，且当无人机电池电量充满时，该值为0；
Figure BDA0002473838220000057
分别表示第n个无人机在第t个时隙内的计算能耗和飞行能耗，表达式分别为：in,
Figure BDA0002473838220000056
Represents the solar energy absorbed by the n-th drone in the t-th time slot, and when the battery of the drone is fully charged, the value is 0;
Figure BDA0002473838220000057
respectively represent the computing energy consumption and flight energy consumption of the nth UAV in the tth time slot, and the expressions are:

Figure BDA0002473838220000058
Figure BDA0002473838220000058

Figure BDA0002473838220000059
Figure BDA0002473838220000059

式中，κ＝0.5Mδ，M为无人机的重量，单个时隙单无人机耗能总和限制为：In the formula, κ=0.5Mδ, M is the weight of the UAV, and the total energy consumption of a single UAV in a single time slot is limited to:

Figure BDA00024738382200000510
Figure BDA00024738382200000510

进一步地，步骤2所述基于系统模型构建整个周期内的多无人机路径规划问题，具体包括：Further, according tostep 2, the multi-UAV path planning problem in the whole cycle is constructed based on the system model, which specifically includes:

步骤2-1，定义时间平均函数并给出限制条件，具体包括：Step 2-1, define the time average function and give constraints, including:

定义所有无人机在单个时隙飞行的能耗总和为

Figure BDA00024738382200000511
其时间平均函数为：Define the sum of the energy consumption of all drones flying in a single time slot as
Figure BDA00024738382200000511
Its time-averaged function is:

Figure BDA0002473838220000061
Figure BDA0002473838220000061

式中，

Figure BDA0002473838220000062
表示期望值；In the formula,
Figure BDA0002473838220000062
represents the expected value;

定义所有用户耗能总和的时间平均函数为：The time-averaged function that defines the sum of all user energy consumption is:

Figure BDA0002473838220000063
Figure BDA0002473838220000063

定义用户端的任务队列、无人机端的任务队列以及能量队列的时间平均函数分别为：The time-averaged functions that define the task queue on the user side, the task queue on the UAV side, and the energy queue are:

Figure BDA0002473838220000064
Figure BDA0002473838220000064

Figure BDA0002473838220000065
Figure BDA0002473838220000065

Figure BDA0002473838220000066
Figure BDA0002473838220000066

对以上时间平均函数限制如下：The above time-averaged functions are restricted as follows:

Figure BDA0002473838220000067
Figure BDA0002473838220000067

Figure BDA0002473838220000068
Figure BDA0002473838220000068

步骤2-2，定义问题优化变量，具体包括：Step 2-2, define problem optimization variables, including:

定义待优化用户CPU频率Flocal：Define the user CPU frequency Flocal to be optimized:

Figure BDA0002473838220000069
Figure BDA0002473838220000069

定义用户关联变量A：Define user-related variable A:

Figure BDA00024738382200000610
Figure BDA00024738382200000610

定义多无人机整个周期内的飞行路径W：Define the flight path W over the entire cycle of the multi-UAV:

Figure BDA00024738382200000611
Figure BDA00024738382200000611

步骤2-3，基于步骤2-1和步骤2-2，构建整个周期内的多无人机路径规划问题如下：Step 2-3, based on Step 2-1 and Step 2-2, construct the multi-UAV path planning problem in the whole cycle as follows:

Figure BDA0002473838220000071
Figure BDA0002473838220000071

Figure BDA0002473838220000072
Figure BDA0002473838220000072

Figure BDA0002473838220000073
Figure BDA0002473838220000073

Figure BDA0002473838220000074
Figure BDA0002473838220000074

Figure BDA0002473838220000075
Figure BDA0002473838220000075

Figure BDA0002473838220000076
Figure BDA0002473838220000076

Figure BDA0002473838220000077
Figure BDA0002473838220000077

Figure BDA0002473838220000078
Figure BDA0002473838220000078

Figure BDA0002473838220000079
Figure BDA0002473838220000079

进一步地，步骤3所述利用Lyapunov队列优化理论简化所述整个周期内的多无人机路径规划问题，获得单个时隙内的优化问题，具体过程包括：Further, in step 3, the Lyapunov queue optimization theory is used to simplify the multi-UAV path planning problem in the entire cycle, and the optimization problem in a single time slot is obtained, and the specific process includes:

步骤3-1，定义李雅普诺夫函数：Step 3-1, define the Lyapunov function:

Figure BDA00024738382200000710
Figure BDA00024738382200000710

步骤3-2，定义李雅普诺夫漂移惩罚函数：Step 3-2, define the Lyapunov drift penalty function:

Figure BDA00024738382200000711
Figure BDA00024738382200000711

式中，

Figure BDA00024738382200000712
VUAV与VUE分别为控制用户和无人机能耗最小这一优化目标，在整个问题中所占权重的扰动参数；In the formula,
Figure BDA00024738382200000712
VUAV and VUE are the perturbation parameters of the weight in the whole problem, which are the optimization goals of controlling the user and the UAV to minimize energy consumption respectively;

步骤3-3，利用Lyapunov队列优化理论确定李雅普诺夫漂移惩罚函数的上界为：Steps 3-3, using the Lyapunov queue optimization theory to determine the upper bound of the Lyapunov drift penalty function:

Figure BDA0002473838220000081
Figure BDA0002473838220000081

式中，C为常数，

Figure BDA0002473838220000082
where C is a constant,
Figure BDA0002473838220000082

由此将整个周期内的多无人机路径规划问题分解为单个时隙内的优化问题。This decomposes the multi-UAV path planning problem in the whole cycle into an optimization problem in a single time slot.

进一步地，步骤4所述将所述单个时隙内的优化问题分解为用户频率优化问题和多无人机路径优化与用户关联联合优化问题，并求解两个子问题，具体包括：Further, in step 4, the optimization problem in the single time slot is decomposed into the user frequency optimization problem and the multi-UAV path optimization and user association joint optimization problem, and two sub-problems are solved, including:

步骤4-1，根据用户频率变量、多无人机位置变量以及用户关联变量，将单个时隙内的优化问题分解为用户频率优化子问题和多无人机路径优化与用户关联子问题的联合优化问题；Step 4-1, according to the user frequency variable, the multi-UAV position variable and the user-related variable, decompose the optimization problem in a single time slot into the user frequency optimization sub-problem and the combination of the multi-UAV path optimization and the user-related sub-problem Optimization;

步骤4-2，利用三次函数求解用户频率优化子问题的极值，作为其最优解；Step 4-2, use the cubic function to solve the extreme value of the user frequency optimization sub-problem as its optimal solution;

步骤4-3，求解多无人机路径优化与用户关联子问题，具体过程包括：Step 4-3, solve the sub-problem of multi-UAV path optimization and user association, the specific process includes:

步骤4-3-1，将所述多无人机路径优化与用户关联子问题分解为单无人机路径优化与用户关联子问题；Step 4-3-1, decompose the multi-UAV path optimization and user association sub-problems into single UAV path optimization and user association sub-problems;

步骤4-3-2，求取单无人机路径优化与用户关联子问题，过程包括：Step 4-3-2, find the sub-problem of single UAV path optimization and user correlation, the process includes:

步骤4-3-2-1，初始化迭代次数r＝0，以及无人机初始位置w0(t)；Step 4-3-2-1, the number of initialization iterations r=0, and the initial position of the UAV w0 (t);

步骤4-3-2-2，根据无人机位置wr(t)，利用线性松弛法求解用户关联变量αr+1(t)；Step 4-3-2-2, according to the UAV position wr (t), use the linear relaxation method to solve the user-related variable αr+1 (t);

步骤4-3-2-3，根据所述用户关联变量αr+1(t)，优化单无人机位置wr+1(t)，具体包括：Step 4-3-2-3, according to the user-related variable αr+1 (t), optimize the single UAV position wr+1 (t), specifically including:

(1)利用李普希兹连续和泰勒展开求解上传速率的凸上下界，将优化单无人机位置wr+1(t)的问题转化为凸问题；(1) Use Lipschitz continuum and Taylor expansion to solve the convex upper and lower bounds of the upload rate, and transform the problem of optimizing the position wr+1 (t) of a single UAV into a convex problem;

(2)利用凸优化工具求解所述凸问题；(2) using a convex optimization tool to solve the convex problem;

步骤4-3-2-4、更新迭代次数r＝r+1，若r＜r0，返回执行步骤4-3-2-2，否则停止迭代。Step 4-3-2-4, update the number of iterations r=r+1, if r<r0 , return to step 4-3-2-2, otherwise stop the iteration.

本发明与现有技术相比，其显著优点为：1)增加了多个无人机的多个任务和能量队列，使得系统所有队列能够在短时间内快速趋于稳定；2)增加了调度限制条件，保证了多无人机之间的协作通信；3)将李雅普诺夫队列优化理论和块迭代下降算法结合，有效降低了问题求解复杂度；4)仿真结果显示多无人机服务地面用户系统相对单无人机系统而言，系统能效显著提升。Compared with the prior art, the present invention has the following significant advantages: 1) multiple tasks and energy queues of multiple UAVs are added, so that all queues in the system can be quickly stabilized in a short time; 2) scheduling is increased 3) Combining the Lyapunov queue optimization theory with the block iterative descent algorithm, the problem solving complexity is effectively reduced; 4) The simulation results show that the multi-UAV serves the ground Compared with the single UAV system, the energy efficiency of the user system is significantly improved.

下面结合附图对本发明作进一步详细描述。The present invention will be described in further detail below with reference to the accompanying drawings.

附图说明Description of drawings

图1为一个实施例中基于边缘计算动态任务到达的多无人机路径规划方法的流程图。FIG. 1 is a flowchart of a multi-UAV path planning method based on edge computing dynamic task arrival in one embodiment.

图2为一个实施例中基于边缘计算动态任务到达的无人机系统的路径优化算法仿真结果图。FIG. 2 is a simulation result diagram of a path optimization algorithm of an unmanned aerial system based on edge computing dynamic task arrival in one embodiment.

图3为一个实施例中针对某一用户的队列长度随时间变化仿真结果图，其中图(a)为某一用户端任务队列长度随时间变化仿真图，图(b)为该用户分别在不同无人机端任务队列长度随时间变化仿真结果图。Fig. 3 is a simulation result diagram of a user's queue length over time in one embodiment, wherein Fig. (a) is a simulation diagram of a certain user's task queue length over time, and Fig. Simulation results of the UAV-side task queue length changing with time.

具体实施方式Detailed ways

为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。In order to make the purpose, technical solutions and advantages of the present application more clearly understood, the present application will be described in further detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present application, but not to limit the present application.

在一个实施例中，结合图1，提供了一种基于边缘计算动态任务到达的多无人机路径规划方法，所述方法包括：In one embodiment, with reference to FIG. 1 , a method for multi-UAV path planning based on dynamic task arrival based on edge computing is provided, and the method includes:

步骤1，建立多无人机协同服务地面用户的系统模型；Step 1, establish a system model of multi-UAV cooperative service for ground users;

步骤2，基于系统模型构建整个周期内的多无人机路径规划问题；Step 2, based on the system model, construct the multi-UAV path planning problem in the whole cycle;

步骤3，利用Lyapunov队列优化理论简化所述整个周期内的多无人机路径规划问题，获得单个时隙内的优化问题；Step 3, using the Lyapunov queue optimization theory to simplify the multi-UAV path planning problem in the entire cycle to obtain the optimization problem in a single time slot;

步骤4，按照时间顺序，依次对每个所述单个时隙内的优化问题进行进一步优化：将所述单个时隙内的优化问题分解为用户频率优化子问题和多无人机路径优化与用户关联子问题的联合优化问题，并求解两个子问题。Step 4, according to the time sequence, further optimize the optimization problem in each of the single time slot: decompose the optimization problem in the single time slot into the user frequency optimization sub-problem and the multi-UAV path optimization and user A joint optimization problem that correlates subproblems and solves both subproblems.

进一步地，在其中一个实施例中，步骤1所述建立多无人机协同服务地面用户的系统模型，具体包括：Further, in one of the embodiments, the establishment of a system model for multi-UAV cooperative services for ground users described instep 1 specifically includes:

步骤1-1，定义地面用户的相关变量，包括：Step 1-1, define the relevant variables of the ground user, including:

定义用户数量为K；Define the number of users as K;

定义用户地理位置：Define user geographic location:

zk＝(xk,yk),k∈{1,2,…K}zk =(xk ,yk ),k∈{1,2,…K}

式中，zk为第k个用户的地理位置，(xk,yk)为第k个用户的地理位置坐标；In the formula, zk is the geographic location of the k th user, and (xk , yk ) is the geographic location coordinates of the k th user;

步骤1-2，定义无人机的相关变量，包括：Step 1-2, define the relevant variables of the drone, including:

定义无人机服务用户的任务周期

Figure BDA0002473838220000101
Defining mission cycles for UAV service users
Figure BDA0002473838220000101

Figure BDA0002473838220000102
Figure BDA0002473838220000102

该式表示一个任务周期

Figure BDA0002473838220000103
内包括T个时隙，每个时隙的长度均为δ；This formula represents a task period
Figure BDA0002473838220000103
It includes T time slots, and the length of each time slot is δ;

定义无人机数量集

Figure BDA0002473838220000104
Define the set of drone numbers
Figure BDA0002473838220000104

Figure BDA0002473838220000105
Figure BDA0002473838220000105

该式表示无人机数量集

Figure BDA0002473838220000106
包括N个无人机；This formula represents the number set of UAVs
Figure BDA0002473838220000106
Including N drones;

定义每个无人机的飞行高度：

Figure BDA0002473838220000107
Hn表示第n个无人机的飞行高度；Define the flying height of each drone:
Figure BDA0002473838220000107
Hn represents the flying height of the nth drone;

定义每个无人机在单个时隙的水平位置：Define the horizontal position of each drone in a single time slot:

Figure BDA0002473838220000108
Figure BDA0002473838220000108

式中，wn(t)为第n个无人机在第t个时隙的水平位置，(xn(t),yn(t))为第n个无人机在第t个时隙的水平位置坐标，

Figure BDA0002473838220000109
In the formula, wn (t) is the horizontal position of the n-th UAV at the t-th time slot, and (xn (t), yn (t)) is the n-th UAV at the t-th time the horizontal position coordinates of the gap,
Figure BDA0002473838220000109

定义每个无人机在单个时隙内的水平飞行速度：Define the horizontal flight speed of each drone in a single time slot:

Figure BDA00024738382200001010
Figure BDA00024738382200001010

式中，νn(t)表示第n个无人机在第t个时隙内的水平飞行速度，νmax为单个时隙无人机所能达到的最大水平飞行速度，其值自定义设置；In the formula, νn (t) represents the horizontal flight speed of the n-th UAV in the t-th time slot, νmax is the maximum horizontal flight speed that the UAV can achieve in a single time slot, and its value is customized ;

步骤1-3，构建数据传输模型，包括：Steps 1-3, build a data transmission model, including:

定义二进制变量αk,n(t)，该变量表示在第t个时隙内第n个无人机与第k个用户之间建立通信链接；记该二进制变量为用户关联变量；Define a binary variable αk,n (t), which represents the establishment of a communication link between the n-th UAV and the k-th user in the t-th time slot; denote this binary variable as a user-related variable;

对所述二进制变量αk,n(t)进行条件限制，所用公式为：Conditioning the binary variable αk,n (t), the formula used is:

Figure BDA0002473838220000111
Figure BDA0002473838220000111

Figure BDA0002473838220000112
Figure BDA0002473838220000112

定义第n个无人机与第k个用户之间在单个时隙的上传速率：Define the upload rate between the nth drone and the kth user in a single slot:

Figure BDA0002473838220000113
Figure BDA0002473838220000113

其中，Rk,n(t)表示第n个无人机与第k个用户之间在第t个时隙的上传速率，hk,n(t)表示第k个用户与第n个无人机之间的信道增益，公式为：Among them, Rk,n (t) represents the upload rate between the n-th drone and the k-th user in the t-th time slot, and hk,n (t) represents the k-th user and the n-th unmanned aerial vehicle. The channel gain between man and machine, the formula is:

Figure BDA0002473838220000114
Figure BDA0002473838220000114

式中，ρ0为单位距离内的信道增益，σ2为AWGN功率，p0为用户发射功率；In the formula, ρ0 is the channel gain within a unit distance, σ2 is the AWGN power, and p0 is the user transmit power;

根据二进制变量αk,n(t)和上传速率Rk,n(t)计算在单个时隙内无人机与用户之间传输的数据量大小：Calculate the amount of data transmitted between the UAV and the user in a single time slot according to the binary variable αk,n (t) and the upload rate Rk,n (t):

Figure BDA0002473838220000115
Figure BDA0002473838220000115

式中，

Figure BDA0002473838220000116
表示在第t个时隙内第n个无人机与第k个用户之间传输的数据量大小，B为信道带宽；In the formula,
Figure BDA0002473838220000116
Indicates the amount of data transmitted between the n-th UAV and the k-th user in the t-th time slot, and B is the channel bandwidth;

步骤1-4，构建任务队列模型，具体包括：Steps 1-4, build a task queue model, including:

(1)构建单个时隙用户端任务队列集合：(1) Construct a single-slot user-side task queue set:

Figure BDA0002473838220000117
Figure BDA0002473838220000117

式中，Qk(t)表示在第t个时隙第k个用户的任务队列，在t＝0时，初始化Qk(t)＝0；在第t+1个时隙第k个用户的任务队列Qk(t+1)为：In the formula, Qk (t) represents the task queue of the k-th user in the t-th time slot. When t=0, initialize Qk (t)=0; in the t+1-th time slot, the k-th user is initialized. The task queue Qk (t+1) of is:

Figure BDA0002473838220000118
Figure BDA0002473838220000118

式中，ak(t)表示第k个用户在第t个时隙接收任务量的大小，

Figure BDA0002473838220000119
表示第k个用户在第t个时隙上传给无人机的任务量总和，
Figure BDA00024738382200001110
表示第k个用户在第t个时隙处理完成的本地任务量大小，公式为：In the formula, ak (t) represents the size of the task received by the kth user in the tth time slot,
Figure BDA0002473838220000119
represents the sum of the tasks uploaded by the kth user to the UAV in the tth time slot,
Figure BDA00024738382200001110
Indicates the amount of local tasks processed by the kth user in the tth time slot, and the formula is:

Figure BDA0002473838220000121
Figure BDA0002473838220000121

式中，ζk表示第k个用户每计算1bit的任务量所需的CPU转数，

Figure BDA0002473838220000122
表示第k个用户在第t个时隙内的CPU计算频率；In the formula, ζk represents the number of CPU revolutions required by the kth user to calculate the task amount of 1 bit,
Figure BDA0002473838220000122
Indicates the CPU computing frequency of the kth user in the tth time slot;

(2)构建单个时隙无人机端的任务队列集合：(2) Construct a task queue set on the UAV side of a single time slot:

Figure BDA0002473838220000123
Figure BDA0002473838220000123

式中，Mk,n(t)表示在第t个时隙第n个无人机为第k个用户所储存的任务队列长度，在t＝0时，初始化Mk,n(t)＝0；在第t+1个时隙第n个无人机为第k个用户所储存的任务队列长度Mk,n(t+1)为：In the formula, Mk,n (t) represents the task queue length stored by the n-th UAV for the k-th user in the t-th time slot. When t=0, initialize Mk,n (t)= 0; the task queue length Mk,n (t+1) stored by the n-th UAV for the k-th user in the t+1-th time slot is:

Figure BDA0002473838220000124
Figure BDA0002473838220000124

其中，

Figure BDA0002473838220000125
表示第n个无人机为第k个用户在第t个时隙内所处理任务量的大小，
Figure BDA0002473838220000126
表示第n个无人机在第t个时隙内为第k个用户分配的处理频率；in,
Figure BDA0002473838220000125
Represents the size of the task that the n-th UAV handles for the k-th user in the t-th time slot,
Figure BDA0002473838220000126
represents the processing frequency allocated by the nth UAV for the kth user in the tth time slot;

步骤1-5，构建能量队列模型，具体包括：Steps 1-5, build an energy queue model, including:

(1)构建单个时隙用户端的计算能耗：(1) Constructing the computational energy consumption of a single time slot user end:

Figure BDA0002473838220000127
Figure BDA0002473838220000127

其中，

Figure BDA0002473838220000128
表示第k个用户在第t个时隙内的计算能耗，公式为：in,
Figure BDA0002473838220000128
Represents the computing energy consumption of the kth user in the tth time slot, and the formula is:

Figure BDA0002473838220000129
Figure BDA0002473838220000129

式中，γ为有效开关电容常数；where γ is the effective switched capacitance constant;

(2)构建单个时隙无人机端的能量队列集合：(2) Construct a set of energy queues on the UAV side of a single time slot:

Figure BDA00024738382200001210
Figure BDA00024738382200001210

式中，En(t)表示第n个无人机在第t个时隙内电池电量的大小，在t＝0时，初始化En(t)＝0；第n个无人机在第t+1个时隙内电池电量的大小En(t+1)为：In the formula, En (t) represents the size of the battery power of the n-th UAV in the t-th time slot. When t=0, initializeEn (t)=0; the n-th UAV is in the t-th time slot. The size of the battery power in t+1 time slots,En (t+1), is:

Figure BDA0002473838220000131
Figure BDA0002473838220000131

其中，

Figure BDA0002473838220000132
表示在第t个时隙内第n个无人机所吸收的太阳能量，且当无人机电池电量充满时，该值为0；
Figure BDA0002473838220000133
分别表示第n个无人机在第t个时隙内的计算能耗和飞行能耗，表达式分别为：in,
Figure BDA0002473838220000132
Indicates the solar energy absorbed by the n-th drone in the t-th time slot, and when the battery of the drone is fully charged, the value is 0;
Figure BDA0002473838220000133
respectively represent the computing energy consumption and flight energy consumption of the nth UAV in the tth time slot, and the expressions are:

Figure BDA0002473838220000134
Figure BDA0002473838220000134

Figure BDA0002473838220000135
Figure BDA0002473838220000135

式中，κ＝0.5Mδ，M为无人机的重量，单个时隙单无人机耗能总和限制为：In the formula, κ=0.5Mδ, M is the weight of the UAV, and the total energy consumption of a single UAV in a single time slot is limited to:

Figure BDA0002473838220000136
Figure BDA0002473838220000136

进一步地，在其中一个实施例中，步骤2所述基于系统模型构建整个周期内的多无人机路径规划问题，具体包括：Further, in one of the embodiments, the construction of the multi-UAV path planning problem in the whole cycle based on the system model instep 2 specifically includes:

步骤2-1，定义时间平均函数并给出限制条件，具体包括：Step 2-1, define the time average function and give constraints, including:

定义所有无人机在单个时隙飞行的能耗总和为

Figure BDA0002473838220000137
其时间平均函数为：Define the sum of the energy consumption of all UAVs flying in a single time slot as
Figure BDA0002473838220000137
Its time-averaged function is:

Figure BDA0002473838220000138
Figure BDA0002473838220000138

式中，

Figure BDA0002473838220000139
表示期望值；In the formula,
Figure BDA0002473838220000139
represents the expected value;

定义所有用户耗能总和的时间平均函数为：The time-averaged function that defines the sum of all user energy consumption is:

Figure BDA00024738382200001310
Figure BDA00024738382200001310

定义用户端的任务队列、无人机端的任务队列以及能量队列的时间平均函数分别为：The time-averaged functions that define the task queue on the user side, the task queue on the UAV side and the energy queue are:

Figure BDA00024738382200001311
Figure BDA00024738382200001311

Figure BDA00024738382200001312
Figure BDA00024738382200001312

Figure BDA0002473838220000141
Figure BDA0002473838220000141

对以上时间平均函数限制如下：The above time-averaged functions are restricted as follows:

Figure BDA0002473838220000142
Figure BDA0002473838220000142

Figure BDA0002473838220000143
Figure BDA0002473838220000143

步骤2-2，定义问题优化变量，具体包括：Step 2-2, define problem optimization variables, including:

定义待优化用户CPU频率Flocal：Define the user CPU frequency Flocal to be optimized:

Figure BDA0002473838220000144
Figure BDA0002473838220000144

定义用户关联变量A：Define user-related variable A:

Figure BDA0002473838220000145
Figure BDA0002473838220000145

定义多无人机整个周期内的飞行路径W：Define the flight path W over the entire cycle of the multi-UAV:

Figure BDA0002473838220000146
Figure BDA0002473838220000146

步骤2-3，基于步骤2-1和步骤2-2，构建整个周期内的多无人机路径规划问题如下：Step 2-3, based on Step 2-1 and Step 2-2, construct the multi-UAV path planning problem in the whole cycle as follows:

Figure BDA0002473838220000147
Figure BDA0002473838220000147

Figure BDA0002473838220000148
Figure BDA0002473838220000148

Figure BDA0002473838220000149
Figure BDA0002473838220000149

Figure BDA00024738382200001410
Figure BDA00024738382200001410

Figure BDA00024738382200001411
Figure BDA00024738382200001411

Figure BDA00024738382200001412
Figure BDA00024738382200001412

Figure BDA00024738382200001413
Figure BDA00024738382200001413

Figure BDA0002473838220000151
Figure BDA0002473838220000151

Figure BDA0002473838220000152
Figure BDA0002473838220000152

进一步地，在其中一个实施例中，步骤3所述利用Lyapunov队列优化理论简化所述整个周期内的多无人机路径规划问题，获得单个时隙内的优化问题，具体过程包括：Further, in one of the embodiments, in step 3, the Lyapunov queue optimization theory is used to simplify the multi-UAV path planning problem in the entire cycle, and the optimization problem in a single time slot is obtained, and the specific process includes:

步骤3-1，定义李雅普诺夫函数：Step 3-1, define the Lyapunov function:

Figure BDA0002473838220000153
Figure BDA0002473838220000153

步骤3-2，定义李雅普诺夫漂移惩罚函数：Step 3-2, define the Lyapunov drift penalty function:

Figure BDA0002473838220000154
Figure BDA0002473838220000154

式中，

Figure BDA0002473838220000155
VUAV与VUE分别为控制用户和无人机能耗最小这一优化目标，在整个问题中所占权重的扰动参数；In the formula,
Figure BDA0002473838220000155
VUAV and VUE are the perturbation parameters of the weight in the whole problem, which are the optimization goals of controlling the user and the UAV to minimize energy consumption respectively;

步骤3-3，利用Lyapunov队列优化理论确定李雅普诺夫漂移惩罚函数的上界为：Steps 3-3, using the Lyapunov queue optimization theory to determine the upper bound of the Lyapunov drift penalty function:

Figure BDA0002473838220000156
Figure BDA0002473838220000156

式中，C为常数，

Figure BDA0002473838220000157
where C is a constant,
Figure BDA0002473838220000157

由此将整个周期内的多无人机路径规划问题分解为单个时隙内的优化问题。This decomposes the multi-UAV path planning problem in the whole cycle into an optimization problem in a single time slot.

进一步地，在其中一个实施例中，步骤4所述将所述单个时隙内的优化问题分解为用户频率优化问题和多无人机路径优化与用户关联联合优化问题，并求解两个子问题，具体包括：Further, in one of the embodiments, the optimization problem in the single time slot is decomposed into the user frequency optimization problem and the multi-UAV path optimization and user association joint optimization problem described in step 4, and two sub-problems are solved, Specifically include:

步骤4-1，根据用户频率变量、多无人机位置变量以及用户关联变量，将单个时隙内的优化问题分解为用户频率优化子问题和多无人机路径优化与用户关联子问题的联合优化问题；Step 4-1, according to the user frequency variable, the multi-UAV position variable and the user-related variable, decompose the optimization problem in a single time slot into the user frequency optimization sub-problem and the combination of the multi-UAV path optimization and the user-related sub-problem Optimization;

步骤4-2，利用三次函数求解用户频率优化子问题的极值，作为其最优解；Step 4-2, use the cubic function to solve the extreme value of the user frequency optimization sub-problem as its optimal solution;

步骤4-3，求解多无人机路径优化与用户关联子问题，具体过程包括：Step 4-3, solve the sub-problem of multi-UAV path optimization and user association, the specific process includes:

步骤4-3-1，将所述多无人机路径优化与用户关联子问题分解为单无人机路径优化与用户关联子问题；Step 4-3-1, decompose the multi-UAV path optimization and user correlation sub-problem into a single UAV path optimization and user correlation sub-problem;

步骤4-3-2，求取单无人机路径优化与用户关联子问题，过程包括：Step 4-3-2, find the sub-problem of single UAV path optimization and user correlation, the process includes:

步骤4-3-2-1，初始化迭代次数r＝0，以及无人机初始位置w0(t)；Step 4-3-2-1, the number of initialization iterations r=0, and the initial position of the UAV w0 (t);

步骤4-3-2-2，根据无人机位置wr(t)，利用线性松弛法求解用户关联变量αr+1(t)；Step 4-3-2-2, according to the UAV position wr (t), use the linear relaxation method to solve the user-related variable αr+1 (t);

步骤4-3-2-3，根据所述用户关联变量αr+1(t)，优化单无人机位置wr+1(t)，具体包括：Step 4-3-2-3, according to the user-related variable αr+1 (t), optimize the single UAV position wr+1 (t), specifically including:

(1)利用李普希兹连续和泰勒展开求解上传速率的凸上下界，将优化单无人机位置wr+1(t)的问题转化为凸问题；(1) Use Lipschitz continuum and Taylor expansion to solve the convex upper and lower bounds of the upload rate, and transform the problem of optimizing the position wr+1 (t) of a single UAV into a convex problem;

(2)利用凸优化工具求解所述凸问题；(2) using a convex optimization tool to solve the convex problem;

步骤4-3-2-4、更新迭代次数r＝r+1，若r＜r0，返回执行步骤4-3-2-2，否则停止迭代。Step 4-3-2-4, update the number of iterations r=r+1, if r<r0 , return to step 4-3-2-2, otherwise stop the iteration.

作为一种具体示例，对本发明进行进一步仿真验证说明，包括以下内容：As a specific example, the present invention is further simulated and verified, including the following contents:

设定仿真条件：无人机初始飞行路径被设置为半环形。用户每个时隙任务到达量ak(t)(Mbits)服从区间[0,1]且期望值

Figure BDA0002473838220000161
的独立同分布。Set the simulation conditions: the initial flight path of the UAV is set as a semicircle. The task arrival amount ak (t) (Mbits) of each time slot of the user obeys the interval [0, 1] and the expected value
Figure BDA0002473838220000161
independent and identically distributed.

图2为上述条件下动态多无人机在保持队列稳定的条件下的飞行路径优化图，其中无人机初始点分别为(1000，0)和(1000，500)，初始电池电量5000J。另一方面，图中星形标志分别代表各个用户的水平位置，无人机的水平飞行路径采样间隔为50。由图2可知，多无人机能根据用户任务队列的状态并考虑各个无人机当前位置实时调整其飞行轨迹来服务用户，由此说明本发明有着良好的实时动态性能。Figure 2 is the optimization diagram of the flight path of the dynamic multi-UAV under the condition of keeping the queue stable under the above conditions. The initial points of the UAV are (1000, 0) and (1000, 500) respectively, and the initial battery power is 5000J. On the other hand, the stars in the figure represent the horizontal position of each user respectively, and the sampling interval of the horizontal flight path of the drone is 50. It can be seen from FIG. 2 that the multi-UAV can adjust its flight trajectory in real time according to the status of the user's task queue and consider the current position of each UAV to serve the user, which shows that the present invention has good real-time dynamic performance.

图3为上述条件下某一用户在自身设备端和无人机端的队列长度随时间变化图。由图可知，用户在各个设备和无人机端的任务积压变化趋势都是先增加然后稳定于60Mbits，证明了本发明所提出的多无人机路径规划算法能有效使任务队列保持稳定。Figure 3 is a graph showing the change of the queue length of a user on the device side and the drone side with time under the above conditions. It can be seen from the figure that the change trend of the user's task backlog on each device and the UAV side first increases and then stabilizes at 60Mbits, which proves that the multi-UAV path planning algorithm proposed in the present invention can effectively keep the task queue stable.

以上显示和描述了本发明的基本原理、主要特征及优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。The foregoing has shown and described the basic principles, main features and advantages of the present invention. Those skilled in the art should understand that the present invention is not limited by the above-mentioned embodiments. The above-mentioned embodiments and descriptions only illustrate the principle of the present invention. Without departing from the spirit and scope of the present invention, the present invention will also have Various changes and modifications fall within the scope of the claimed invention. The claimed scope of the present invention is defined by the appended claims and their equivalents.

Claims (2)

1. A multi-unmanned aerial vehicle path planning method based on edge computing dynamic task arrival is characterized by comprising the following steps:
step 1, establishing a system model of a multi-unmanned aerial vehicle cooperative service ground user; the method specifically comprises the following steps:
step 1-1, defining relevant variables of a ground user, comprising:
Defining the number of users as K;
defining the user geographical location:
zk＝(xk,yk),k∈{1,2,…K}
in the formula, zkIs the geographic location of the kth user, (x)k,yk) Geographical location coordinates for the kth user;
step 1-2, defining relevant variables of the unmanned aerial vehicle, including:
defining a task period for a drone service user
Figure FDA0003558635820000011
Figure FDA0003558635820000012
The formula represents a task cycle
Figure FDA0003558635820000013
The time slot comprises T time slots, and the length of each time slot is delta;
defining a set of unmanned aerial vehicle quantities
Figure FDA0003558635820000014
Figure FDA0003558635820000015
The formula represents the number set of unmanned aerial vehicles
Figure FDA0003558635820000016
The unmanned aerial vehicle comprises N unmanned aerial vehicles;
defining the flight altitude of each drone:
Figure FDA0003558635820000017
Hnrepresenting the flight altitude of the nth drone;
defining the horizontal position of each drone in a single timeslot:
Figure FDA0003558635820000018
in the formula, wn(t) horizontal position of nth UAV at t time slot, (x)n(t),yn(t)) is the horizontal position coordinate of the nth drone at the tth time slot,
Figure FDA0003558635820000019
defining the horizontal flight speed of each drone within a single time slot:
Figure FDA00035586358200000110
in the formula, vn(t) represents the horizontal flight speed of the nth unmanned plane in the tth time slot, vmaxSetting the maximum horizontal flying speed which can be reached by the unmanned aerial vehicle in a single time slot in a self-defined manner;
step 1-3, constructing a data transmission model, comprising:
defining a binary variable alphak,n(t), the variable representing establishment of a communication link between the nth drone and the kth user in the tth time slot; recording the binary variable as a user associated variable;
For the binary variable alphak,n(t) conditional constraints are imposed by the formula:
Figure FDA0003558635820000021
Figure FDA0003558635820000022
defining an upload rate between the nth drone and the kth user in a single timeslot:
Figure FDA0003558635820000023
wherein R isk,n(t) represents the upload rate between the nth drone and the kth user in the tth time slot, hk,n(t) represents the channel gain between the kth user and the nth drone, with the formula:
Figure FDA0003558635820000024
in the formula, ρ0Channel gain, σ, in unit distance2For AWGN power, p0Transmitting power for the user;
according to a binary variable alphak,n(t) and upload Rate Rk,n(t) calculating the size of the amount of data transmitted between the drone and the user in a single time slot:
Figure FDA0003558635820000025
in the formula,
Figure FDA0003558635820000026
the data size transmitted between the nth unmanned aerial vehicle and the kth user in the t-th time slot is represented, and B is the channel bandwidth;
step 1-4, constructing a task queue model, specifically comprising:
(1) constructing a single time slot user side task queue set:
Figure FDA0003558635820000027
in the formula, Qk(t) denotes a task queue of the kth user at the tth slot, and Q is initialized when t is 0k(t) ═ 0; task queue Q of kth user at t +1 th time slotk(t +1) is:
Figure FDA0003558635820000031
in the formula, ak(t) represents the size of the amount of tasks received by the kth user in the tth time slot,
Figure FDA0003558635820000032
represents the sum of the task amount transmitted to the unmanned aerial vehicle by the kth user in the t-th time slot,
Figure FDA0003558635820000033
Denotes the firstThe local task amount processed and completed by k users at the t-th time slot is as follows:
Figure FDA0003558635820000034
in the formula, ζkIndicates the number of CPU revolutions required for each calculation of 1bit of task amount by the kth user,
Figure FDA0003558635820000035
the CPU calculation frequency of the kth user in the t time slot is shown;
(2) constructing a task queue set at the unmanned aerial vehicle end of a single time slot:
Figure FDA0003558635820000036
in the formula, Mk,n(t) indicates the length of the task queue stored by the nth drone for the kth user at the tth time slot, and when t is equal to 0, M is initializedk,n(t) ═ 0; the length M of a task queue stored by the nth unmanned aerial vehicle for the kth user in the t +1 th time slotk,n(t +1) is:
Figure FDA0003558635820000037
wherein,
Figure FDA0003558635820000038
indicating the size of the task volume processed by the nth drone for the kth user in the tth time slot,
Figure FDA0003558635820000039
indicating the processing frequency allocated by the nth unmanned plane to the kth user in the tth time slot;
step 1-5, constructing an energy queue model, specifically comprising:
(1) and (3) constructing the computing energy consumption of a single time slot user side:
Figure FDA00035586358200000310
wherein,
Figure FDA00035586358200000311
the calculated energy consumption of the kth user in the t-th time slot is represented by the formula:
Figure FDA00035586358200000312
wherein γ is the effective switched capacitance constant;
(2) constructing an energy queue set at the unmanned aerial vehicle end of a single time slot:
Figure FDA0003558635820000041
in the formula, En(t) represents the size of the battery capacity of the nth unmanned aerial vehicle in the tth time slot, and when t is equal to 0, the initialization E is carried outn(t) ═ 0; size E of battery capacity of nth unmanned aerial vehicle in t +1 time slotn(t +1) is:
Figure FDA0003558635820000042
wherein,
Figure FDA0003558635820000043
represents the solar energy absorbed by the nth drone during the t-th timeslot and is 0 when the drone is fully charged with battery;
Figure FDA0003558635820000044
respectively representing the calculation of the nth unmanned plane in the t time slotEnergy consumption and flight energy consumption, the expression respectively is:
Figure FDA0003558635820000045
Figure FDA0003558635820000046
wherein, k is 0.5M δ, M is the weight of the drone, and the energy consumption sum of the single slot drone is limited as follows:
Figure FDA0003558635820000047
step 2, constructing a multi-unmanned aerial vehicle path planning problem in the whole period based on a system model; the method specifically comprises the following steps:
step 2-1, defining a time average function and giving out a limiting condition, wherein the method specifically comprises the following steps:
the sum of the energy consumption of all unmanned aerial vehicles flying in a single time slot is defined as
Figure FDA0003558635820000048
The time-averaged function is:
Figure FDA0003558635820000049
in the formula,
Figure FDA00035586358200000410
representing a desired value;
the time-averaged function defining the sum of the energy consumptions of all users is:
Figure FDA00035586358200000411
defining time average functions of a task queue at a user side, a task queue at an unmanned aerial vehicle side and an energy queue as follows:
Figure FDA0003558635820000051
Figure FDA0003558635820000052
Figure FDA0003558635820000053
the time-averaged function above is limited as follows:
Figure FDA0003558635820000054
Figure FDA0003558635820000055
step 2-2, defining a problem optimization variable, which specifically comprises the following steps:
defining the CPU frequency F of the user to be optimizedlocal：
Figure FDA0003558635820000056
Defining a user associated variable A:
Figure FDA0003558635820000057
Defining the flight path W in the whole period of the multiple unmanned planes:
Figure FDA0003558635820000058
step 2-3, based on step 2-1 and step 2-2, constructing a multi-unmanned aerial vehicle path planning problem in the whole period as follows:
Figure FDA0003558635820000059
s.t.
Figure FDA00035586358200000510
Figure FDA00035586358200000511
Figure FDA0003558635820000061
Figure FDA0003558635820000062
Figure FDA0003558635820000063
Figure FDA0003558635820000064
Figure FDA0003558635820000065
Figure FDA0003558635820000066
step 3, simplifying the multi-unmanned aerial vehicle path planning problem in the whole period by utilizing a Lyapunov queue optimization theory, and obtaining an optimization problem in a single time slot; the specific process comprises the following steps:
step 3-1, defining a Lyapunov function:
Figure FDA0003558635820000067
step 3-2, defining a Lyapunov drift penalty function:
Figure FDA0003558635820000068
in the formula,
Figure FDA0003558635820000069
VUAVand VUEDisturbance parameters which are respectively the optimal target of controlling the minimum energy consumption of the user and the unmanned aerial vehicle and account for the weight of the whole problem;
step 3-3, determining the upper bound of the Lyapunov drift penalty function by utilizing a Lyapunov queue optimization theory as follows:
Figure FDA00035586358200000610
wherein, C is a constant, and C is a linear alkyl group,
Figure FDA00035586358200000611
therefore, the path planning problem of the multiple unmanned aerial vehicles in the whole period is decomposed into an optimization problem in a single time slot;
and 4, sequentially further optimizing the optimization problem in each single time slot according to the time sequence: and decomposing the optimization problem in the single time slot into a user frequency optimization sub-problem and a joint optimization problem of multi-unmanned aerial vehicle path optimization and user association sub-problems, and solving the two sub-problems.
2. The method for planning paths of multiple unmanned aerial vehicles based on edge-computed dynamic task arrival according to claim 1, wherein the step 4 decomposes the optimization problem in the single time slot into a user frequency optimization problem and a multi-unmanned aerial vehicle path optimization and user association joint optimization problem, and solves two sub-problems, specifically comprising:
step 4-1, decomposing an optimization problem in a single time slot into a user frequency optimization sub-problem and a combined optimization problem of multi-unmanned aerial vehicle path optimization and user association sub-problems according to a user frequency variable, a multi-unmanned aerial vehicle position variable and a user association variable;
step 4-2, solving the extreme value of the user frequency optimization subproblem by utilizing a cubic function to serve as the optimal solution;
4-3, solving a sub-problem of multi-unmanned aerial vehicle path optimization and user association, wherein the specific process comprises the following steps:
4-3-1, decomposing the sub-problem of multi-unmanned aerial vehicle path optimization and user association into a sub-problem of single-unmanned aerial vehicle path optimization and user association;
step 4-3-2, solving a sub-problem of single unmanned aerial vehicle path optimization and user association, wherein the process comprises the following steps:
step 4-3-2-1, initializing the number of iterations r to 0, and setting the initial position w of the unmanned aerial vehicle0(t)；
Step 4-3-2-2, according to the position w of the unmanned aerial vehicler(t) solving the user-associated variable alpha by using a linear relaxation methodr+1(t)；
Step 4-3-2-3, according to the user association variable alphar+1(t) optimizing Single drone position wr+1(t), specifically including:
(1) solving convex upper and lower bounds of uploading rate by utilizing Lipschitz continuity and Taylor expansion, and optimizing the position w of the single unmanned aerial vehicler+1(t) the problem translates into a convex problem;
(2) solving the convex problem by using a convex optimization tool;
step 4-3-2-4, updating the iteration number r ═ r +1, if r is less than r0And returning to execute the step 4-3-2-2, otherwise, stopping iteration.
CN202010357106.2A2020-04-292020-04-29Multi-unmanned aerial vehicle path planning method based on edge calculation dynamic task arrivalExpired - Fee RelatedCN111552313B (en)

Priority Applications (1)

Application NumberPriority DateFiling DateTitle
CN202010357106.2ACN111552313B (en)2020-04-292020-04-29Multi-unmanned aerial vehicle path planning method based on edge calculation dynamic task arrival

Applications Claiming Priority (1)

Application NumberPriority DateFiling DateTitle
CN202010357106.2ACN111552313B (en)2020-04-292020-04-29Multi-unmanned aerial vehicle path planning method based on edge calculation dynamic task arrival

Publications (2)

Publication NumberPublication Date
CN111552313A CN111552313A (en)2020-08-18
CN111552313Btrue CN111552313B (en)2022-06-28

Family

ID=72002621

Family Applications (1)

Application NumberTitlePriority DateFiling Date
CN202010357106.2AExpired - Fee RelatedCN111552313B (en)2020-04-292020-04-29Multi-unmanned aerial vehicle path planning method based on edge calculation dynamic task arrival

Country Status (1)

CountryLink
CN (1)CN111552313B (en)

Families Citing this family (12)

* Cited by examiner, † Cited by third party
Publication numberPriority datePublication dateAssigneeTitle
CN112668847B (en)*2020-12-172023-11-24国网山西省电力公司运城供电公司Autonomous inspection integrated management system for distribution network line unmanned aerial vehicle
CN113242077B (en)*2021-03-242022-04-26北京交通大学 A method for providing communication services for ground users as an aerial base station by a swarm of unmanned aerial vehicles
CN113159519B (en)*2021-03-252021-11-23重庆大学City sensing transportation cooperative scheduling method for multiplexing transportation unmanned aerial vehicle
CN113034981B (en)*2021-04-142022-07-08北京航空航天大学Multi-relay unmanned aerial vehicle flight path planning method and system in uncertain channel environment and storage medium
CN113282352B (en)*2021-06-022023-07-07南京邮电大学Energy-saving unloading method based on multi-unmanned aerial vehicle cooperative auxiliary edge calculation
CN113709883B (en)*2021-08-302023-12-05北京邮电大学Dynamic resource allocation method and device under multi-unmanned aerial vehicle auxiliary industrial scene
CN113847926B (en)*2021-09-182024-01-19上海电机学院Real-time path planning method based on edge microservice collaboration
CN113848904B (en)*2021-09-242023-05-16安徽工程大学Method for optimizing task allocation of multiple mobile robots based on punishment energy consumption
CN114020024B (en)*2021-11-052023-03-31南京理工大学Unmanned aerial vehicle path planning method based on Monte Carlo tree search
CN114640965A (en)*2022-03-012022-06-17北京邮电大学Calculation, communication and control method and system of networked unmanned aerial vehicle
CN115052297B (en)*2022-06-012023-10-17山东大学Power distribution and relay design method for land-sea communication network
CN116347479A (en)*2023-03-292023-06-27东南大学 A Dynamic Allocation Method of Multi-slot Computing Resources for Edge Computing Under UAV Collaboration

Citations (7)

* Cited by examiner, † Cited by third party
Publication numberPriority datePublication dateAssigneeTitle
CN108196575A (en)*2018-01-052018-06-22湖北工业大学A kind of unmanned plane task distribution and route planning method
CN109067490A (en)*2018-09-292018-12-21郑州航空工业管理学院Cellular Networks join lower multiple no-manned plane and cooperate with mobile edge calculations method for distributing system resource
CN109922137A (en)*2019-01-282019-06-21中国人民解放军国防科技大学 Drone-Assisted Computational Migration Method
CN110166110A (en)*2019-05-222019-08-23南京理工大学Unmanned plane paths planning method based on edge calculations
CN110428115A (en)*2019-08-132019-11-08南京理工大学Maximization system benefit method under dynamic environment based on deeply study
CN110488861A (en)*2019-07-302019-11-22北京邮电大学Unmanned plane track optimizing method, device and unmanned plane based on deeply study
CN110766159A (en)*2019-09-292020-02-07南京理工大学Task allocation method for multi-UAV service edge calculation based on improved genetic algorithm

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication numberPriority datePublication dateAssigneeTitle
US10643342B2 (en)*2018-02-082020-05-05Huawei Technologies Co., Ltd.Group optimization depth information method and system for constructing a 3D feature map

Patent Citations (7)

* Cited by examiner, † Cited by third party
Publication numberPriority datePublication dateAssigneeTitle
CN108196575A (en)*2018-01-052018-06-22湖北工业大学A kind of unmanned plane task distribution and route planning method
CN109067490A (en)*2018-09-292018-12-21郑州航空工业管理学院Cellular Networks join lower multiple no-manned plane and cooperate with mobile edge calculations method for distributing system resource
CN109922137A (en)*2019-01-282019-06-21中国人民解放军国防科技大学 Drone-Assisted Computational Migration Method
CN110166110A (en)*2019-05-222019-08-23南京理工大学Unmanned plane paths planning method based on edge calculations
CN110488861A (en)*2019-07-302019-11-22北京邮电大学Unmanned plane track optimizing method, device and unmanned plane based on deeply study
CN110428115A (en)*2019-08-132019-11-08南京理工大学Maximization system benefit method under dynamic environment based on deeply study
CN110766159A (en)*2019-09-292020-02-07南京理工大学Task allocation method for multi-UAV service edge calculation based on improved genetic algorithm

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
城市安防场景下基于边缘计算的三维侦测路径规划;强士卿;《工业控制计算机 》;20191230;第32卷(第12期);第15-18页*

Also Published As

Publication numberPublication date
CN111552313A (en)2020-08-18

Similar Documents

PublicationPublication DateTitle
CN111552313B (en)Multi-unmanned aerial vehicle path planning method based on edge calculation dynamic task arrival
Zhan et al.Completion time and energy optimization in the UAV-enabled mobile-edge computing system
Yang et al.Online trajectory and resource optimization for stochastic UAV-enabled MEC systems
Do et al.Deep reinforcement learning for energy-efficient federated learning in UAV-enabled wireless powered networks
CN112995913B (en) A joint optimization method for UAV trajectory, user association and resource allocation
Sun et al.AoI-energy-aware UAV-assisted data collection for IoT networks: A deep reinforcement learning method
Chai et al.Online trajectory and radio resource optimization of cache-enabled UAV wireless networks with content and energy recharging
WO2022160554A1 (en)Design method for green data collection system of high-energy-efficiency unmanned aerial vehicle
CN110730031B (en)Unmanned aerial vehicle track and resource allocation joint optimization method for multi-carrier communication
Guo et al.UAV trajectory and communication co-design: Flexible path discretization and path compression
CN112911648A (en)Air-ground combined mobile edge calculation unloading optimization method
CN113660681B (en)Multi-agent resource optimization method applied to unmanned aerial vehicle cluster auxiliary transmission
CN113254188B (en)Scheduling optimization method and device, electronic equipment and storage medium
CN110166110A (en)Unmanned plane paths planning method based on edge calculations
CN113627013A (en) System throughput maximization method based on UAV binary offloading edge computing
Liu et al.Deep reinforcement learning-based resource allocation for UAV-enabled federated edge learning
CN117580105A (en) An optimization method for unmanned aerial vehicle task offloading for power grid inspection
CN112579290A (en)Unmanned aerial vehicle-based calculation task migration method for ground terminal equipment
CN114500533A (en) Optimization method of UAV-assisted mobile edge computing system based on user collaboration
Liu et al.Joint stochastic computational resource and UAV trajectory for wireless-powered space-air-ground IoRT networks
CN116880559A (en)Unmanned aerial vehicle track planning optimization method and system
Sweidan et al.RL-based mobile edge computing scheme for high reliability low latency services in UAV-aided IIoT networks
Long et al.Exploiting deep reinforcement learning for stochastic AoI minimization in multi-UAV-assisted wireless networks
CN110207712A (en)The unmanned plane paths planning method reached based on edge calculations dynamic task
CN115278584A (en)NOMA-based unmanned aerial vehicle data acquisition system and acquisition method thereof

Legal Events

DateCodeTitleDescription
PB01Publication
PB01Publication
SE01Entry into force of request for substantive examination
SE01Entry into force of request for substantive examination
GR01Patent grant
GR01Patent grant
CF01Termination of patent right due to non-payment of annual fee

Granted publication date:20220628

CF01Termination of patent right due to non-payment of annual fee
[8]ページ先頭
©2009-2025 Movatter.jp