CN109445946B - Unmanned aerial vehicle cloud task deployment method and device - Google Patents

Abstract

The present invention provides a method and device for unmanned aerial vehicle cloud task deployment. The method includes: dividing the overall task of a specific application into different subtasks according to different functions, and each subtask corresponds to at least one executable program; according to the subtask The data flow relationship among them, build the task execution flow chart, and convert the task execution flow chart into a directed acyclic graph; after determining the objective function and constraint function according to the specific application, the division result of the directed acyclic graph is obtained by solving the objective function , the division result is used to indicate the deployment position of each subtask when it is executed. The present invention effectively solves the problem of rationally deploying the overall task of a specific application between the UAV end and the cloud platform end so that the system performance can be optimized, and in the process of task execution, it can also be based on the UAV itself. State changes, adaptively adjust the task execution position, thereby improving system performance.

Description

A method and device for deploying unmanned aerial vehicle cloud tasks

Technical Field

The present invention relates to the technical field of cloud platform task deployment, and in particular to a method and device for deploying unmanned aerial vehicle (UAV) cloud tasks.

Background Art

Due to its small size, fast take-off and landing, and no personnel on board, drones have been rapidly developed and applied in large-area coverage and real-time data collection applications. However, due to the limited computing and storage capabilities of drones themselves, it is necessary to use cloud platforms to expand the resources of drones. After the introduction of cloud platforms, how to reasonably deploy tasks between drones and cloud platforms to optimize system performance has become a new research issue, especially in drone swarm applications.

At present, there are relatively few studies on deployment strategies for UAV missions. It is obviously not the optimal strategy to deploy the mission completely on the cloud platform or UAV. Therefore, the existing deployment method is to deploy based on human experience, deploying some algorithms with complex calculations and low real-time performance on the cloud platform, and deploying algorithms with high real-time performance and hardware-related performance on UAVs. However, this deployment method requires personnel with rich experience in a specific field, and there are usually few such personnel, so it is relatively difficult to implement; and even if experienced people are used to deploy, due to the limitations of their experience and subjective factors, it is often difficult to achieve the optimal deployment strategy.

Summary of the invention

The embodiments of the present invention provide a method and device for deploying unmanned aerial vehicle cloud tasks to solve the problem in the prior art of how to reasonably deploy unmanned aerial vehicle tasks between an unmanned aerial vehicle terminal and a cloud platform so as to achieve optimal system performance.

In a first aspect, an embodiment of the present invention provides a method for deploying unmanned aerial vehicle cloud tasks, comprising:

Divide the overall task of a specific application into different subtasks according to different functions, each of which corresponds to at least one executable program; wherein the executable programs are deployed on the drone and the cloud platform respectively;

According to the data flow relationship between the subtasks, a task execution flowchart is constructed, and the task execution flowchart is converted into a directed acyclic graph;

After determining the objective function and the constraint function according to the specific application, the partitioning result of the directed acyclic graph is obtained by solving the objective function, and the partitioning result is used to indicate the deployment position of each subtask when it is executed.

As a preferred embodiment of the first aspect of the present invention, it also includes:

receiving an execution status parameter fed back when each of the subtasks is executed at the current deployment location;

When there is a difference between the execution state parameter and the corresponding preset parameter, the execution state parameter is determined as the updated preset parameter, and the partitioning result of the directed acyclic graph is obtained by re-solving the objective function, and the partitioning result is used to indicate the redeployment position when each subtask is executed.

As a preferred embodiment of the first aspect of the present invention, determining the objective function and the constraint function according to a specific application specifically includes:

determining at least one cost function corresponding to a specific application;

According to the requirements of a specific application, one of the cost functions is determined as the objective function, and the remaining cost functions are determined as constraint functions.

As a preferred embodiment of the first aspect of the present invention, the cost function at least includes a task execution time function, a task execution energy consumption function and a communication distance function.

As a preferred embodiment of the first aspect of the present invention, the drone is provided with a corresponding virtual mirror unit on the cloud platform.

In a second aspect, an embodiment of the present invention provides a drone cloud task deployment device, comprising:

A task division unit, used to divide the overall task of a specific application into different subtasks according to different functions, each of which corresponds to at least one executable program; wherein the executable programs are deployed on the drone and the cloud platform respectively;

A conversion unit is constructed to construct a task execution flow chart according to the data flow relationship between the subtasks, and convert the task execution flow chart into a directed acyclic graph;

The task deployment unit is used to determine the objective function and the constraint function according to the specific application, and obtain the partition result of the directed acyclic graph by solving the objective function, wherein the partition result is used to indicate the deployment position of each subtask when it is executed.

As a preferred embodiment of the second aspect of the present invention, it also includes:

A parameter feedback unit, used to receive the execution status parameters fed back when each of the subtasks is executed at the current deployment position;

A redeployment unit is used to determine the execution state parameter as the updated preset parameter when there is a difference between the execution state parameter and the corresponding preset parameter, and to obtain the partition result of the directed acyclic graph by re-solving the objective function, wherein the partition result is used to indicate the redeployment position when each subtask is executed.

As a preferred embodiment of the second aspect of the present invention, the task deployment unit is specifically used for:

determining at least one cost function corresponding to a specific application;

According to the requirements of a specific application, one of the cost functions is determined as the objective function, and the remaining cost functions are determined as constraint functions.

As a preferred embodiment of the second aspect of the present invention, the cost function at least includes a task execution time function, a task execution energy consumption function and a communication distance function.

As a preferred embodiment of the second aspect of the present invention, the drone is correspondingly provided with a virtual mirror unit on the cloud platform.

A method and device for deploying unmanned aerial vehicle cloud tasks provided by an embodiment of the present invention divides the overall task of a specific application into different subtasks, constructs a task execution flowchart according to the data flow relationship between the subtasks, and then converts the task execution flowchart into a directed acyclic graph. After further determining the objective function and constraint function according to the specific application, the objective function is solved to obtain the division result of the directed five-ring graph. According to the division result, a deployment plan for the subtasks can be obtained, that is, which subtasks are deployed on the unmanned aerial vehicle for execution and which subtasks are deployed on the cloud platform for execution, thereby solving the problem of reasonably deploying the overall task of the specific application between the unmanned aerial vehicle end and the cloud platform end so as to achieve the optimal system performance.

The method and device provided by the embodiments of the present invention can be applied to heterogeneous UAV systems and are suitable for UAVs with different computing and storage capabilities. During the execution of a task, the task execution position can be adaptively adjusted according to the changes in the UAV's own state, thereby improving system performance.

BRIEF DESCRIPTION OF THE DRAWINGS

In order to more clearly illustrate the technical solutions in the embodiments of the present invention, the drawings required for use in the description of the embodiments will be briefly introduced below. Obviously, the drawings described below are only some embodiments of the present invention. For ordinary technicians in this field, other drawings can be obtained based on these drawings without creative work.

FIG1 is a flow chart of a method for deploying unmanned aerial vehicle cloud tasks provided by an embodiment of the present invention;

FIG2 is a schematic diagram of a task execution flow chart provided by an embodiment of the present invention;

FIG3 is a schematic diagram of a directed acyclic graph provided by an embodiment of the present invention;

FIG4 is a schematic diagram of the structure of a UAV cloud mission deployment device provided by an embodiment of the present invention.

DETAILED DESCRIPTION

In order to enable those skilled in the art to better understand the scheme of the present invention, the technical scheme in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments are only part of the embodiments of the present invention, not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by ordinary technicians in this field without creative work should fall within the scope of protection of the present invention.

1, an embodiment of the present invention discloses a method for deploying a UAV cloud task, which mainly includes the following steps:

101. Divide the overall task of a specific application into different subtasks according to different functions, and each subtask corresponds to at least one executable program; wherein the executable programs are deployed on the drone and the cloud platform respectively;

102. According to the data flow relationship between subtasks, construct a task execution flowchart and convert the task execution flowchart into a directed acyclic graph;

103. After determining the objective function and constraint function according to the specific application, the partition result of the directed acyclic graph is obtained by solving the objective function, and the partition result is used to indicate the deployment position of each subtask when it is executed.

In the embodiment of the present invention, the front end is a heterogeneous drone node, and the back end is a cloud platform composed of a computer cluster. The drone is provided with a corresponding virtual image unit on the cloud platform, that is, each front-end drone node has a corresponding virtual image on the cloud platform, so that during the task execution, the virtual image units on the drone and the cloud platform are abstracted into the same logical unit, which facilitates the seamless migration of tasks between the drone and the cloud platform.

In step 101, for a specific application of the drone, the overall task of the specific application is divided into different subtasks according to the different functions to be implemented, and each subtask corresponds to one or more executable programs, which can be started through commands or scripts.

After dividing the overall task of a specific application into different subtasks, it is necessary to determine the executable program corresponding to each subtask launched on the drone or cloud platform to achieve optimal system performance.

These executable programs are deployed on drones and cloud platforms respectively. After determining that the deployment location of each subtask can achieve optimal system performance when it is executed, that is, after determining whether each subtask is executed on the drone or on the cloud platform, the corresponding executable program can be started through commands or scripts.

When any subtask needs to be started, the executable program corresponding to the subtask can be started without being constrained by other subtasks.

In step 102, after the overall task of the specific application is divided into different subtasks, a task execution flow chart is constructed according to the data flow relationship between the subtasks, as shown in FIG. 2.

Then, the task execution flow chart constructed above is converted into a directed acyclic graph, as shown in Figure 3. The nodes in Figure 3 represent subtasks, the edges between nodes represent the data flow between subtasks, and the nodes in the same layer can be executed concurrently, and the serial execution is connected in sequence using arrows.

In step 103, how to determine the deployment position of each subtask when it is executed so as to optimize the system performance requires solving the above-mentioned directed acyclic graph to obtain a partitioning result indicating the deployment position of each subtask when it is executed.

Specifically, the objective function and constraint function should be determined according to the specific application of the UAV, so as to obtain the partitioning result of the directed acyclic graph by solving the objective function.

In a possible implementation, determining the objective function and the constraint function according to a specific application may be performed according to the following steps:

1031. Determine at least one cost function corresponding to a specific application;

1032. According to the requirements of a specific application, one of the cost functions is determined as the objective function, and the remaining cost functions are determined as constraint functions.

For the application of drones, since most drones have a short flight time, it is necessary to ensure that the drone’s power is not consumed before the mission is completed, and the time constraints must be met during the mission. At the same time, the drone is constantly moving during the mission and needs to transmit data with the cloud platform in real time, so the communication distance of the drone needs to be considered when deploying the mission. In summary, for the application of drones, there are generally three cost functions, namely: mission execution time function, mission execution energy consumption function and communication distance function. After determining the cost function, determine the constraint function and objective function for different applications.

It should be noted that, for a specific application of the UAV, those skilled in the art may also add or reduce other cost functions according to actual needs and use them as optimized constraint functions.

Before determining each cost function, the parameters are defined first:

Specifically, the process of determining each cost function is as follows:

(1) Task execution time function

The task execution time consists of two parts: the drone execution time and the cloud platform execution time. When the subtask is executed on the drone, the execution time is determined by the execution time of the executable program corresponding to the subtask; when the subtask is executed on the cloud platform, the execution time is the sum of the subtask's computing time, communication time, and resource establishment time on the cloud platform.

Specifically, the task execution time function is as follows:

in,

_TC ＝ _TCC + _TCS + _TCR ，

_TR = _TRc ,

(2) Task execution energy consumption function

The energy consumption of drones when performing tasks mainly comes from three aspects: motion energy consumption, computing energy consumption and communication energy consumption. When the subtask is executed on the drone, the drone energy consumption is composed of motion energy consumption and computing energy consumption; when the subtask is executed on the cloud platform, the drone energy consumption is composed of motion energy consumption and communication energy consumption.

Specifically, the task execution energy consumption function is as follows:

in,

_ER ＝ _PC · _TRC ，

E _C = PC _M ·T _CR .

的值，从而确定这N个子任务的部署位置。After determining the objective function according to the needs of a specific application, calculate N

The value of is used to determine the deployment locations of these N subtasks.

(3) Communication distance function

The current position of the drone may change during the mission, so it is necessary to determine whether the communication distance meets the distance constraint when the drone performs the current subtask.

Communication is possible only when the communication distance function is satisfied: S _tineed ≤ S _tiallow .

After obtaining the above cost function, it is necessary to determine the objective function and constraint function according to the needs of different applications. For drone applications, there are mainly two objective functions and corresponding constraint functions.

(1) Minimize task execution time

Find:

Among them, Min:T _total ,

St:E _total ＜E _allow ,

The deployment plan of the subtask is to minimize the task execution time, while ensuring that the execution energy consumption of the drone is less than the total energy consumption that the drone can provide, and the distance between the drone and the cloud platform when performing the task is less than its maximum communication distance.

(2) Minimize the energy consumption of drone execution

Find:

Among them, Min:E _total ,

St:T _total ＜T _deadline ,

The deployment plan of the subtask should minimize the energy consumption of the drone while meeting the maximum execution time required by the overall mission. In addition, the distance between the drone and the cloud platform when performing the mission should be less than its maximum communication distance.

的值，也即得到了有向无环图的划分结果，从而确定这N个子任务的部署位置。

的值只能取0或1，0表示在云平台执行，1表示在无人机执行。Genetic algorithm is used to solve the above objective function and calculate N

The value of , that is, the partition result of the directed acyclic graph, is obtained, thereby determining the deployment locations of the N subtasks.

The value can only be 0 or 1, 0 means execution on the cloud platform, and 1 means execution on the drone.

The genetic algorithm is used to solve the objective function. The specific process can be carried out according to the following steps:

(1) Initialize the population

During initialization, a set of chromosome codes is first randomly generated as the initial population. At the same time, for some tasks that must be performed on the drone, they are forcibly assigned to the drone for execution by setting their corresponding vector values to 1.

(2) Crossover and mutation

Improve sample diversity through crossover and mutation.

(3) Constrained individual fitness evaluation

When the objective function is to minimize the task execution time, the smaller the fitness function value, the better the individual. For individuals that do not meet the constraints, the fitness score is set to the maximum value. In the selection stage, the individuals with higher fitness scores have a lower probability of being selected, thereby reducing the probability of their inheritance to the next generation.

(4) Selection with elite retention

Before each generation of population evolution, the individual with the lowest fitness score is retained to increase the possibility of converging to the global optimal solution. After performing crossover, mutation, and selection in sequence, if the next generation of population does not have the previously saved optimal individual, then the individual is added to the next generation of population and the individual with the highest fitness score is eliminated.

(5) Stop criteria

When the fitness value reaches a certain value and does not change in a fixed number of generations, the genetic algorithm will stop running. At this time, it is considered that the optimal solution has been found and it will be used as the task deployment plan. If this condition is not met, the evolutionary iteration will stop when the maximum number of iterations is reached, and the individual with the lowest fitness score will be used as the task deployment plan.

After step 103, the process also includes the step of adaptive task deployment. During the execution of each subtask of a specific application, the execution position of the subtask can be adaptively adjusted according to the state change of the drone itself, thereby improving the overall operation performance.

Specifically, the above steps of adaptive task deployment can be performed as follows:

Receive the execution status parameters fed back when each subtask is executed at the current deployment location;

When there is a difference between the execution state parameter and the corresponding preset parameter, the execution state parameter is determined as the updated preset parameter, and the partition result of the directed acyclic graph is obtained by re-solving the objective function. The partition result is used to indicate the redeployment position of each subtask when it is executed.

Since tasks can be seamlessly migrated between drones and cloud platforms, the first objective function is solved based on historical data, the division results are used as the initial state of subtask deployment, and the corresponding execution program is started; during the execution process, the deployment position of the subtask when it is executed can be adaptively adjusted according to the current state.

It should be noted that the above deployment method is not only for a single drone, but can also effectively adapt to the application of drone clusters.

To further explain the method described in the embodiment of the present invention, the search and rescue application of drone swarm is used as a specific application. The overall task of the application is divided into the following subtasks according to different functions: image data acquisition, thermal imaging image acquisition, real-time map construction, drone positioning, obstacle avoidance, navigation, target detection (detection of humans with vital signs), target positioning, tracking pedestrians, delivering supplies, and pushing safe paths to people.

Each of the above subtasks corresponds to one or more independently run executable programs. The executable program corresponding to the subtask can be started whenever the subtask needs to be started, and is not constrained by other subtasks.

The task execution flowchart is constructed according to the data flow relationship between each subtask, as shown in Figure 2. Then the task execution flowchart is further converted into a directed acyclic graph, as shown in Figure 3.

For the search and rescue application of drone swarm, the drone cannot be powered by an external power supply during the movement. At the same time, the shorter the execution time of the search and rescue application, the more conducive to the search and rescue. Therefore, the objective function determined by the search and rescue application is to minimize the task execution time, and the other two cost functions are used as constraint functions.

The genetic algorithm is used to solve the objective function, and the solution is the partition result of the above directed acyclic graph, that is, the task deployment plan.

During the task execution process, the execution status parameters will be continuously fed back. If it is found that the currently set preset parameters are different from the fed-back execution status parameters, the preset parameters are updated, and the genetic algorithm is re-executed to obtain a new task deployment plan; if the new task deployment plan is different from the currently executed task deployment plan, the task deployment plan is updated to trigger the migration of each subtask. In addition, when abnormal conditions are detected, such as the failure of unmanned system nodes, the communication distance cannot meet the constraints, etc., the execution of the genetic algorithm program is immediately triggered to obtain a new task deployment plan and redeploy the subtasks to adapt to the changes.

Through the above steps, the adaptive deployment process of subtasks can be completed, so that the execution time of the overall task is minimized, while also meeting the energy consumption and communication distance constraints during the execution process.

It should be noted that the embodiments of the present invention are mainly described for the scenario of drone cluster executing tasks. The method is also applicable to other drone task deployment schemes with limited computing or storage capabilities. For example, a service robot can use this method to deploy some subtasks on a cloud platform, thereby improving its intelligence level.

It should be noted that, for the sake of simplicity, the embodiments of the above method are described as a series of action combinations, but those skilled in the art should know that the present invention is not limited by the described action sequence. Secondly, those skilled in the art should also know that the embodiments described in the specification are all preferred embodiments, and the actions involved are not necessarily required by the present invention.

Based on the same technical concept, the embodiment of the present invention also discloses a UAV cloud task deployment device, as shown in FIG4 , which mainly includes:

The task division unit 401 is used to divide the overall task of the specific application into different subtasks according to different functions, and each subtask corresponds to at least one executable program; wherein the executable programs are deployed on the drone and the cloud platform respectively;

A construction conversion unit 402 is used to construct a task execution flow chart according to the data flow relationship between the subtasks, and convert the task execution flow chart into a directed acyclic graph;

The task deployment unit 403 is used to determine the objective function and the constraint function according to the specific application, and then obtain the partition result of the directed acyclic graph by solving the objective function, and the partition result is used to indicate the deployment position of each subtask when it is executed.

Preferably, it also includes:

A parameter feedback unit 404 is used to receive the execution status parameters fed back when each subtask is executed at the current deployment location;

The redeployment unit 405 is used to determine the execution state parameter as the updated preset parameter when there is a difference between the execution state parameter and the corresponding preset parameter, and to obtain the partition result of the directed acyclic graph by re-solving the objective function. The partition result is used to indicate the redeployment position when each subtask is executed.

Preferably, the task deployment unit 403 is specifically used for:

determining at least one cost function corresponding to a specific application;

According to the requirements of a specific application, one of the cost functions is determined as the objective function and the remaining cost functions are determined as constraint functions.

Preferably, the cost function includes at least a task execution time function, a task execution energy consumption function and a communication distance function.

Preferably, the drone is provided with a corresponding virtual mirror unit on the cloud platform.

It should be understood that the units included in the above drone cloud task deployment device are only logical divisions based on the functions implemented by the device. In actual applications, the above units can be superimposed or split. In addition, the functions implemented by the drone cloud task deployment device provided in this embodiment correspond one-to-one to the drone cloud task deployment method provided in the above embodiment. The more detailed processing flow implemented by the device has been described in detail in the above method embodiment and will not be described in detail here.

A method and device for deploying unmanned aerial vehicle cloud tasks provided by an embodiment of the present invention divides the overall task of a specific application into different subtasks, constructs a task execution flowchart according to the data flow relationship between the subtasks, and then converts the task execution flowchart into a directed acyclic graph. After further determining the objective function and constraint function according to the specific application, the objective function is solved to obtain the division result of the directed five-ring graph. According to the division result, a deployment plan for the subtasks can be obtained, that is, which subtasks are deployed on the unmanned aerial vehicle for execution and which subtasks are deployed on the cloud platform for execution, thereby solving the problem of reasonably deploying the overall task of the specific application between the unmanned aerial vehicle end and the cloud platform end so as to achieve the optimal system performance.

The method and device provided by the embodiments of the present invention can be applied to heterogeneous UAV systems and are suitable for UAVs with different computing and storage capabilities. In addition, during the execution of a task, the task execution position can be adaptively adjusted according to the change of the UAV's own state, thereby improving system performance. In the above embodiments of the present invention, the description of each embodiment has its own emphasis. For parts not described in detail in a certain embodiment, please refer to the relevant description of other embodiments.

The above description is only a preferred embodiment of the present invention and is not intended to limit the present invention. Any modifications, equivalent substitutions, improvements, etc. made within the spirit and principle of the present invention should be included in the protection scope of the present invention.

Claims (6)

1. An unmanned aerial vehicle cloud task deployment method is characterized by comprising the following steps:

dividing the whole task of the specific application into different subtasks according to different functions, wherein each subtask corresponds to at least one executable program; wherein the executable programs are deployed on the unmanned aerial vehicle and the cloud platform respectively;

constructing a task execution flow chart according to the data flow relation among the subtasks, and converting the task execution flow chart into a directed acyclic graph;

after an objective function and a constraint function are determined according to specific application, a partitioning result of the directed acyclic graph is obtained by solving the objective function, and the partitioning result is used for indicating the deployment position of each subtask when executed;

the determining the objective function and the constraint function according to the specific application specifically includes:

determining at least one cost function corresponding to a particular application;

according to the requirements of specific applications, determining one of the cost functions as a target function, and determining the rest of the cost functions as constraint functions;

the cost function at least comprises a task execution time function, a task execution energy consumption function and a communication distance function.

2. The method of claim 1, further comprising:

receiving an execution state parameter fed back by each subtask when the current deployment position is executed;

when the execution state parameters are different from the corresponding preset parameters, determining the execution state parameters as the updated preset parameters, and obtaining the division result of the directed acyclic graph by solving the objective function again, wherein the division result is used for indicating the redeployment position of each subtask when being executed.

3. The method according to claim 1 or 2, wherein the unmanned aerial vehicle is correspondingly provided with a virtual mirror image unit on the cloud platform.

4. The utility model provides an unmanned aerial vehicle high in clouds task deployment device which characterized in that includes:

the task dividing unit is used for dividing the whole task of the specific application into different subtasks according to different functions, and each subtask corresponds to at least one executable program; wherein the executable programs are deployed on the drone and the cloud platform, respectively;

the construction conversion unit is used for constructing a task execution flow chart according to the data flow relation among the subtasks and converting the task execution flow chart into a directed acyclic graph;

the task deployment unit is used for obtaining a division result of the directed acyclic graph by solving an objective function after the objective function and the constraint function are determined according to specific application, and the division result is used for indicating the deployment position of each subtask when executed;

the task deployment unit is specifically configured to:

determining at least one cost function corresponding to a particular application;

according to the requirements of specific applications, determining one of the cost functions as a target function, and determining the rest of the cost functions as constraint functions;

the cost function at least comprises a task execution time function, a task execution energy consumption function and a communication distance function.

5. The apparatus of claim 4, further comprising:

the parameter feedback unit is used for receiving an execution state parameter fed back by each subtask when the current deployment position is executed;

and the redeploying unit is used for determining the execution state parameter as the updated preset parameter when the execution state parameter is different from the corresponding preset parameter, and obtaining a division result of the directed acyclic graph by solving the objective function again, wherein the division result is used for indicating the redeploying position of each subtask when being executed.

6. The device of claim 4 or 5, wherein the unmanned aerial vehicle is provided with a virtual mirror image unit on the cloud platform.

Images