Unmanned aerial vehicle (UAV) task cooperation method based on overlapping coalition formation (OCF) game

Abstract

An unmanned aerial vehicle (UAV) task cooperation method based on an overlapping coalition formation (OCF) game includes: constructing a sequential OCF game model for a UAV multi-task cooperation problem; using a bilateral mutual benefit transfer (BMBT) order that is biased toward the utility of a whole coalition to evaluate a preference of a UAV for a coalitional structure; optimizing task resource allocation of the UAV under an overlapping coalitional structure by using a preference gravity-guided Tabu Search algorithm to form a stable coalitional structure; and optimizing a transmission strategy based on the current coalitional structure, an updated status of a task resource allocation scheme of the UAV, and a current fading environment, so as to maximize task execution utility of a UAV network. The method quantifies characteristics of resource properties of the UAV and a task, and optimizes the task resource allocation of the UAV under the overlapping coalitional structure.

Claims

1. An unmanned aerial vehicle (UAV) task cooperation method based on an overlapping coalition formation (OCF) game, comprising: step 1: considering an overlapping and complementary relationship between resource properties of a UAV and a task and a task priority, quantifying characteristics of the resource properties of the UAV and the task, optimizing task resource allocation of the UAV under an overlapping coalitional structure, and constructing a sequential OCF game model for a UAV multi-task cooperation problem; step 2: using a bilateral mutual benefit transfer (BMBT) order that is biased toward utility of a whole coalition to evaluate a preference of the UAV for the overlapping coalitional structure, wherein all coalition members cooperate with each other to achieve mutual benefits and further improve total task execution utility of a whole network; step 3: optimizing the task resource allocation of the UAV under the overlapping coalitional structure by using a preference gravity-guided Tabu Search algorithm based on a preference relationship between the UAV and tasks with a same type of resource to form a stable coalitional structure; step 4: optimizing a transmission strategy based on a current coalitional structure, an updated status of a task resource allocation scheme of the UAV, and a current fading environment, to maximize the task execution utility of the UAV network; and step 5: performing, by the UAV, the task according to the optimized task resource allocation and the optimized transmission strategy; wherein in step 1, the sequential OCF game model is constructed for the UAV multi-task cooperation problem; and in the sequential OCF game model, the UAV serves as a player and is assumed to allocate a resource and form an overlapping coalition to cooperatively complete the task, wherein a quantity of coalitions is equal to a quantity of tasks; a task cooperation model based on the OCF game is defined as ={N, U.sub.m, SC, X}, wherein N represents a UAV player; U.sub.m represents a utility function of a task point coalition m; SC={A.sub.1, . . . A.sub.m}, Mem(A.sub.m)∈N represents the overlapping coalitional structure; Mem(A.sub.m) represents a coalition member set of UAVs that allocate resources to an m.sup.th task point and is expressed as Mem(A.sub.m)={n∈N|A.sub.m.sup.(n)≠Ø}; and X={x.sub.1, . . . , x.sub.n, . . . , x.sub.N} represents a UAV decision-making vector for determining the task resource allocation, and a resource allocation vector of each UAV is defined as X.sub.n=[A.sub.1.sup.(n), . . . , A.sub.m.sup.(n), . . . , A.sub.m.sup.(n)]; and each UAV gets a share of a revenue from a coalition that the UAV joins, a revenue sharing problem is resolved according to basic proportional fairness of a Shapley value, and utility of a UAV n is expressed as follows: $u_n=\underset{m\in ℳ}{.Math.}{\mho }_n^{\left(m\right)}{U}_m\left({𝒜}_m\right)$ wherein .sub.n.sup.(m) represents a proportion of UAV resource allocation for the task point coalition m to guarantee that a utility back deserved by the UAV from the coalition increases as the task resources of the UAV allocated to the coalition increases, and .sub.n.sup.(m) is expressed as follows: ${\mho }_n^{\left(m\right)}=\frac{O_n^{\left(m\right)}}{\underset{n\in \mathrm{Mem}\left(A_m\right)}{.Math.}{O}_n^{\left(m\right)}}$ wherein O.sub.n.sup.(m) represents an amount of resources allocation of the UAV n to the task point coalition m, and O.sub.n.sup.(m) is expressed as follows: $O_n^{\left(m\right)}=\underset{{\tau }_{n,m}^{\left(z_b\right)},{\epsilon }_{n,m}^{\left(z_c\right)}\in A_m^{\left(n\right)}}{.Math.}\left(.Math.{\tau }_{n,m}^{\left(z_b\right)}.Math.+.Math.{\epsilon }_{n,m}^{\left(z_c\right)}.Math.\right);$ wherein in the sequential OCF game model in step 1, for a UAV player n, two coalitional structures SC.sub.Q and SC.sub.P are provided, and the coalitional structure SC.sub.Q is superior to the coalitional structure SC.sub.P, which is expressed as SC.sub.Q.sub.n SC.sub.P; SC.sub.Q.sub.n SC.sub.P indicates that the UAV player n prefers to allocate the task resources by using the coalitional structure SC.sub.Q instead of the coalitional structure SC.sub.P; a coalitional structure SC.sub.P={A.sub.l.sup.(p), . . . , A.sub.m.sup.(p)} is considered, wherein for some resources δ.sub.n.sup.(z.sup.b.sup.) of the UAV player n, |δ.sub.n.sup.(z.sup.b.sup.)|≤|τ.sub.n.sup.(z.sup.b.sup.)| is satisfied; a switch operation is defined as an action of moving some consumable resources from a coalition A.sub.i.sup.(p) to a coalition A.sub.j.sup.(p) to generate a new coalitional structure SC.sub.Q=SC.sub.p\{A.sub.i.sup.(p),A.sub.j.sup.(p)}∪{A.sub.i.sup.(q),A.sub.j.sup.(q)}, wherein A.sub.i.sup.(q)=A.sub.j.sup.(p)\{δ.sub.n.sup.(z.sup.b.sup.)} and A.sub.j.sup.(q)=A.sub.j.sup.(p)∪{δ.sub.n.sup.(z.sup.b.sup.)}; and for a non-consumable resource μ.sub.n.sup.(z.sup.c.sup.), the switch operation is defined as an action of leaving or joining the coalition A.sub.i.sup.(p) to generate a new coalitional structure SC.sub.Q=SC.sub.P\{A.sub.i.sup.(p)}∪{A.sub.i.sup.(q)}, wherein A.sub.i.sup.(q)=A.sub.i.sup.(p)\{μ.sub.n.sup.(z.sup.c.sup.)} or A.sub.j.sup.(p)∪{μ.sub.n.sup.(z.sup.c.sup.)}, and the two coalitional structures obtained after the switch operation need to satisfy a preference decision, namely, SC.sub.Q.sub.n SC.sub.P; wherein the BMBT order in step 2 is specifically as follows: for any UAV n∈N and any two coalitional structures SC.sub.P and SC.sub.Q that are generated through a switch operation, wherein A(n)={A.sub.n∈SC|A.sub.m.sup.(n)≠Ø, m∈M} represents a set of other task point coalitions to which the UAV n allocates resources, $S{C}_Q{\succ }_{u}S{C}_p\iff u_n\left(S{C}_Q\right)+\underset{g\in \mathrm{Mem}\left(A_j\right):\left\{n\right\}}{.Math.}\left[u_g\left(S{C}_Q\right)-u_g\left(S{C}_P\right)\right]+\underset{a\in \mathrm{Mem}\left(A\left(n\right)\right)\backslash \left\{n\right\}}{.Math.}{u}_o\left(S{C}_Q\right)>u_n\left(S{C}_P\right)+\underset{h\in \mathrm{Mem}\left(A_j\right)\gamma ,\left\{n\right\}}{.Math.}\left[u_h\left(S{C}_P\right)-u_h\left(S{C}_Q\right)\right]+\underset{n\in \mathrm{Mem}\left(A\left(n\right)\right)\backslash \left\{n\right\}}{.Math.}{u}_o\left(S{C}_P\right);$ and when the UAV n performs a resource switch operation, a proposed preference decision indicates that total coalitional utility containing utility of the UAV n and utility of a resource transfer coalition is greater than that before resource transfer; and when this condition is satisfied, the switch operation is successful; otherwise, the switch operation fails; wherein the step of optimizing the task resource allocation of the UAV under the overlapping coalitional structure by using the preference gravity-guided Tabu Search algorithm based on the preference relationship between the UAV and tasks with the same type of resource to form the stable coalitional structure in step 3 specifically comprises: defining a resource allocation vector of a UAV n for an m.sup.th task point in a k.sup.th iteration as A.sub.m.sup.(n)={τ.sub.n,m.sup.(1)(k), . . . , τ.sub.n,m.sup.(z.sup.b.sup.)(k), . . . , ε.sub.n,m.sup.(z.sup.c.sup.)(k), . . . , ε.sub.n,m.sup.(Z)(k)}, and obtaining a coalitional structure SC.sup.(k)={A.sub.l.sup.(k), . . . , A.sub.m.sup.(k)} under resource allocation in the k.sup.th iteration; establishing a Tabu list Tabu.sub.SC={SC.sup.(k-L.sup.tabu.sup.), . . . , SC.sup.(k-1)} based on resource allocation under a historical coalitional structure, wherein L.sub.tabu represents a Tabu length, indicating existence time of the coalitional structure in the Tabu list; introducing a concept of preference gravity based on tasks of remaining unallocated resources and UAVs of remaining unused resources, and defining a vector of a remaining resource required by the m.sup.th task point as L.sub.m.sup.(less)(k)={Le.sub.m.sup.(1)(k), . . . , Le.sub.m.sup.(z.sup.b.sup.)(k), . . . , Re.sub.m.sup.(z.sup.c.sup.)(k), . . . , Re.sub.m.sup.(Z)(k)}, wherein Le.sub.m.sup.(z.sup.b.sup.)(k) and Re.sub.m.sup.(z.sup.c.sup.)(k) are expressed as follows: $L{e}_m^{\left(z_b\right)}\left(k\right)=\max \left\{0,l_m^{\left(z_b\right)}-\underset{n\in N}{.Math.}{\tau }_{n,m}^{\left(z_b\right)}\left(k\right)\right\}$ $R{e}_m^{\left(z_c\right)}\left(k\right)=\max \left\{0,{\xi }_m^{\left(z_c\right)}-\underset{n\in N}{.Math.}{\epsilon }_{n,m}^{\left(z_c\right)}\left(k\right)\right\}$ wherein Le.sub.m.sup.(z.sup.b.sup.)(k) and Re.sub.m.sup.(z.sup.c.sup.)(k) vary with a UAV resource allocation decision; defining the preference gravity as a degree of preference between the remaining resource required by the task point and a remaining resource carried by the UAV; defining a preference gravity vector of a z.sup.th type of resource of the UAV n for each task as follows: F.sub.n.sup.(z)(k)=[f.sub.1,n.sup.(z)(k), . . . , f.sub.m,n.sup.(z)(k)], wherein f.sub.m,n.sup.(z)(k) represents preference gravity for the m.sup.th task point, and f.sub.m,n.sup.(z)(k) is expressed as follows: $f_{m,n}^{\left(z\right)}\left(k\right)=\{\begin{array}{cc}\frac{{\left({\beta }_m\right)}^{2}L{e}_m^{\left(z_b\right)}\left(k\right){\delta }_n^{\left(z_b\right)}}{d_{m,n}},& \mathrm{when}z=z_b;\\ \frac{{\left({\beta }_m\right)}^{2}R{e}_m^{\left(z_c\right)}\left(k\right){\mu }_n^{\left(z_c\right)}}{d_{m,n}},& \mathrm{when}z=z_c\end{array}$ and defining a probability vector of the z.sup.th type of resource δ.sub.n.sup.(z) of the UAV n for being allocated to each task, namely, P.sub.n.sup.(z)(k)=[p.sub.n,1.sup.(z)(k), . . . , p.sub.m,n.sup.(z)(k), . . . , p.sub.n,M.sup.(z)(k)], wherein a corresponding expression is as follows: $p_{m,n}^{\left(z\right)}\left(k\right)=\frac{\exp \left[f_{m,n}^{\left(z\right)}\left(k\right)\Gamma \left(k\right)\right]}{\underset{m\in M}{.Math.}\exp \left[f_{m,n}^{\left(z\right)}\left(k\right)\Gamma \left(k\right)\right]}$ wherein Γ(k) represents a Boltzmann coefficient; the UAV performs a switch operation according to a selection probability established based on the preference gravity; and when proposed priority is satisfied, the UAV performs a switch operation of resource allocation to improve the total task execution utility of the network; otherwise, the UAV maintains the original coalitional structure under the resource allocation; wherein step 3 specifically comprises the following substeps: a) initialization: setting a quantity k of iterations to 0, namely k=0, denoting a coalitional structure under resource allocation in each iteration as SC.sup.(k)={A.sub.l.sup.(k), . . . , A.sub.m.sup.(k)}, establishing a Tabu list Tabu.sub.SC={SC.sup.(k-L.sup.tabu.sup.), . . . , SC.sup.(k-1)}, initializing the Tabu list to empty, setting a Tabu length as L.sub.tabu, and inputting a remaining initially-carried resource L.sub.m.sup.(less)(0) to obtain F.sub.n.sup.(z)(0) and P.sub.n.sup.(z)(0); and allocating an initially carried resource of the UAV to each task point based on P.sub.n.sup.(z)(0), and performing step b), step c), and step d) cyclically; b) setting k=k+1, updating a vector L.sub.m.sup.(less)(k) and the Tabu list Tabu.sub.SC based on a coalitional structure SC.sup.(k-1), and updating the Boltzmann coefficient according to a rule
Γ(k+1)=Γ(k)+k(Γ.sub.max−Γ(k))/K.sub.max; c) randomly selecting some consumable UAV resources δ.sub.n.sup.(z.sup.b.sup.) or non-consumable resources μ.sub.n.sup.(z.sup.c.sup.), inputting δ.sub.n.sup.(z.sup.b.sup.) or μ.sub.n.sup.(z.sup.c.sup.), and L.sub.m.sup.(less)(k) into a preference gravity expression to obtain P.sub.n.sup.(z)(k), and performing, by a UAV n, a switch operation based on the vector P.sub.n.sup.(z)(k), wherein a coalitional structure obtained after the switch operation is SC.sub.switch.sup.(k); and when the new coalitional structure SC.sub.switch.sup.(k) is different from any one in the Tabu list Tabu.sub.SC, performing step d), otherwise, performing step b); d) updating, by the UAV n, the coalitional structure according to the following order: $S{C}^{\left(k\right)}=\{\begin{array}{cc}S{C}_{\mathrm{swicth}}^{\left(k\right)},& \mathrm{if}S{C}_{\mathrm{swicth}}^{\left(k\right)}{\succ }_{n}S{C}^{\left(k-1\right)}\\ S{C}^{\left(k-1\right)},& \mathrm{else}\end{array};$ and e) ending the process when the utility is still not improved after K.sub.stable iterations are performed or a total quantity of iterations reaches K.sub.max, to obtain a final convergence structure SC.sup.(*).

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a flowchart of a method according to the present invention;

(2) FIG. 2 shows a scenario of a heterogeneous UAV network based a task-driven overlapping coalition;

(3) FIG. 3 shows utility convergence curves of various algorithms under different coalition models; and

(4) FIG. 4 shows a curve in which average execution utility of task points varies with a quantity of UAVs.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(5) The embodiments of the present invention are further described in detail below with reference to the accompanying drawings.

(6) The embodiments are established based on a system model shown in FIG. 2. FIG. 2 shows a scenario of a heterogeneous UAV network based on a task-driven overlapping coalition. The current network includes eight UAVs and five task points in total, and labels of different shapes are used to represent the UAVs, the task points, and corresponding resources. A circle represents a UAV and a five-pointed star represents a task point. Without loss of generality, initial position vectors and resource vectors of all the UAVs and task points are randomly and uniformly generated in a current delimited region.

(7) As shown in FIG. 1, specific implementation steps of the present invention are as follows:

(8) Step 1: Consider an overlapping and complementary relationship between resource properties of a UAV and a task and a task priority, quantify characteristics of the resource properties of the UAV and the task, optimize task resource allocation of the UAV under an overlapping coalitional structure, and construct a sequential OCF game model for a UAV multi-task cooperation problem.

(9) (1) The quantifying characteristics of the resource properties of the UAV and the task is specifically as follows:

(10) A cluster network consisting of N heterogeneous UAVs is considered, where a set of the UAVs is expressed as N={1, . . . n . . . , N}. The UAVs need to complete M tasks randomly distributed in the network, and a set of the tasks is expressed as M={1, . . . m . . . , M}. It is assumed that there are Z types of task resources. A set of sub-task types is T={TB.sub.1, . . . , TB.sub.z.sub.b, . . . , TC.sub.z.sub.c, . . . , TC.sub.Z}, where TB represents a consumable resource required to execute a type of task, and TC represents a non-consumable resource required to execute this type of task. The UAVs executing the tasks in the network are heterogeneous, in other words, the UAVs are equipped with different types and quantities of resources, which are defined as B.sub.n={b.sub.n.sup.(1), . . . , b.sub.n.sup.(z.sup.b.sup.), . . . , μ.sub.n.sup.(z.sup.c.sup.), . . . , μ.sub.n.sup.(Z)}, indicating a vector of a resource carried by each UAV to execute each task. b.sub.n.sup.(z.sup.b.sup.) represents a type and a quantity of consumable resources, for example, fire rescue materials and battery capacities, and μ.sub.n.sup.(z.sup.c.sup.) is defined as a non-consumable communication capacity resource. A required vector of a resource required by an m.sup.th task is defined as L.sub.m={l.sub.m.sup.(1), . . . , l.sub.m.sup.(z.sup.b.sup.), . . . , I.sub.m.sup.(z.sup.c.sup.), . . . , I.sub.m.sup.(Z)}, l.sub.m.sup.(z.sup.b.sup.), I.sub.m.sup.(z.sup.c.sup.)≥0, indicating a type and a quantity of resources required to execute a task in one target region. l.sub.m.sup.(z.sup.b.sup.) and I.sub.m.sup.(z.sup.c.sup.) represent types and quantities of consumable and non-consumable resources required to execute one task respectively. A task execution priority of each region is different, and a priority set is defined as β={β.sub.1, . . . , β.sub.m, . . . , β.sub.M}. A set of resources allocated by each UAV to an m.sup.th task point is defined as A.sub.m={A.sub.m.sup.(1), . . . , A.sub.m.sup.(n), . . . , A.sub.m.sup.(N)}, where A.sub.m.sup.(n) represents a quantity of resources allocated by a UAV n to the m.sup.th task point, and is expressed as A.sub.m.sup.n={τ.sub.n,m.sup.(1), . . . , τ.sub.n,m.sup.(z.sup.b.sup.), . . . , ε.sub.n,m.sup.(z.sup.c.sup.), . . . , ε.sub.n,m.sup.(Z)}. Mem(A.sub.m) is defined as a coalition member set of UAVs that allocate resources to the m.sup.th task point, and is expressed as Mem(A.sub.m)={n∈N|A.sub.m.sup.(n)≠Ø}.

(11) (2) The optimizing task resource allocation of the UAV under an overlapping coalitional structure is specifically as follows:

(12) A satisfaction function is introduced to measure a satisfaction degree of the task. A utility function of the m.sup.th task point may be expressed as follows:

(13) $U_m\left({𝒜}_m\right)=\frac{1}{1+{\exp }^{-{\beta }_m\left(C_m-C_m^{\left(\mathrm{req}\right)}+\omega /{\beta }_m\right)}}$

(14) where C.sub.m.sup.(req) represents a service completion requirement of the task point, and C.sub.m(A.sub.m) represents a service revenue of the task point, which comprehensively considers a task completion status and an energy loss and is defined as follows:

(15) $C_m\left({𝒜}_m\right)=D+{\omega }_{1}r\left({\mathrm{??}}_m\right)-{\omega }_2{t}_m^{\left(\mathrm{wait}\right)}-{\omega }_3\underset{n\in \mathrm{Mem}\left({𝒜}_m\right)}{.Math.}{e}_m^{\left(n\right)}$

(16) where D represents a constant to ensure that C.sub.m>0; ω.sub.1, ω.sub.2, and ω.sub.3 are weight coefficients to evaluate proportions of impact of a task revenue, waiting time, and UAV energy consumption on network utility; r(A.sub.m) represents a completion degree of the m.sup.th task point; t.sub.m.sup.(wait) represents waiting time of the m.sup.th task point; and e.sub.m.sup.(n) represents a flight loss of the UAV n for task execution at the m.sup.th task point, which is calculated based on a proportion of a quantity of resources allocated by the UAV to the task point to a total quantity of resources allocated to the task point, and is expressed as follows:

(17) $e_m^{\left(n\right)}=\frac{E_n.Math.A_m^{\left(n\right)}.Math.}{\underset{m\in M}{.Math.}.Math.A_m^{\left(n\right)}.Math.}$

(18) where E.sub.n represents total propulsion energy consumption of the UAV n. These performance indicators are defined as follows:

(19) 1) Task completion degree: In a resource allocation process of the UAV, quality and a quantity of completed task types need to be considered. The task completion degree represents a proportion of a resource actually allocated to the m.sup.th task point to a resource demand of the task point. When a total quantity of resources allocated by a UAV coalition exceeds the demand of the task point, the task completion degree reaches 100%. Otherwise, the task completion degree is less than 100%. An average task completion degree r(A.sub.m) of the m.sup.th task point is defined as follows:

(20) $r\left(A_m\right)=\frac{\underset{z_b\in \mathrm{TB},l_m^{\left(z_b\right)}\ne 0}{.Math.}\frac{{\lambda }_m^{\left(z_b\right)}}{l_m^{\left(z_b\right)}}+\underset{z_c\in \mathrm{TC},{\xi }_m^{\left(z_c\right)}\ne 0}{.Math.}\frac{{\sigma }_m^{\left(z_c\right)}}{{\xi }_m^{\left(z_c\right)}}}{.Math.{\mathrm{res}}_m.Math.},$

(21) where

(22) 0$\frac{{\lambda }_m^{\left(z_b\right)}}{l_m^{\left(z_b\right)}}$
and

(23) $\frac{{\sigma }_m^{\left(z_c\right)}}{{\xi }_m^{\left(z_c\right)}}$
represent proportions of allocated consumable and non-consumable resources to the resource demand of the m.sup.th task point respectively,

(24) ${\lambda }_m^{\left(z_b\right)}=\underset{n\in \mathrm{Mem}\left({𝒜}_m\right)}{.Math.}{\tau }_{n,m}^{\left(z_b\right)}$
represents a total quantity of a z.sub.b.sub.th type of resource allocated by the UAV to the m.sup.th task point,

(25) ${\sigma }_m^{\left(z_c\right)}=\underset{n\in \mathrm{Mem}\left({𝒜}_m\right)}{.Math.}{\epsilon }_{n,m}^{\left(z_c\right)}$
represents a total quantity of a z.sub.c.sub.th type of communication resource allocated by the UAV to the m.sup.th task point, ξ.sub.m.sup.(z.sup.c.sup.) represents a quantity of the z.sub.c.sub.th type of communication resource required by the m.sup.th task point, ∥ represents a size of the set, and re res.sub.m represents a set of resource types required by the m.sup.th task point and is expressed as follows: res.sub.m={T.sub.z.sub.b, T.sub.z.sub.c∈T|l.sub.m.sup.(z.sup.b.sup.), I.sub.m.sup.(z.sup.c.sup.)∈L.sub.m, l.sub.m.sup.(z.sup.b.sup.), l.sub.m.sup.(z.sup.c.sup.)≠0}.

(26) 2) Waiting time of the task: Time consumed by the UAV n for task execution is decomposed into total flight duration t.sub.n.sup.(fly) and total hovering duration t.sub.n.sup.(hover). The UAV sorts, based on task priorities, task points to which resources are allocated, and generates a task execution sequence, such that a position sequence of the tasks executed by the UAV n is obtained based on the current coalitional structure, namely, Task.sub.n.sup.(UAV)={task.sub.n.sup.(1), . . . , task.sub.n.sup.(i), . . . , task.sub.n.sup.(ζ)}, task.sub.n.sup.(i)∈M, where ζ represents a length of the task execution sequence. In a task execution process, because each UAV has a different position status and flight path, resulting in inconsistent time of arriving at a task position, and task start time of each coalition is determined by a UAV that arrives last, t.sub.task.sub.n.sub.(i).sub.,task.sub.n.sub.(i+t).sup.(fly) is defined as flight duration of the UAV from a task point task.sub.n.sup.(i) to a task point task.sub.n.sup.(i+1), and a flight speed of the UAV n between the task points is set as v.sub.task.sub.n.sub.(i).sub.,task.sub.n.sub.(i+1).sup.(fly), which is determined by the UAV that arrives last. Assuming that the UAV n arriving at the task point task.sub.n.sup.(i+1) last moves from a previous task point to a next task point at a maximum speed v.sub.n.sup.(max), time consumed by the UAV is

(27) $t_{{\mathrm{task}}_n^{\left(i\right)},{\mathrm{task}}_n^{\left(i+1\right)}}^{\left(\mathrm{fly}\right)}=\frac{d_{{\mathrm{task}}_n^{\left(i\right)},{\mathrm{task}}_n^{\left(i+1\right)}}}{v_n^{\left(\max \right)}},$
where d.sub.task.sub.n.sub.(i).sub.,task.sub.n.sub.(i+1) represents a distance between the task points. Other UAVs adjust their flight speeds v.sub.task.sub.n.sub.(i).sub.,task.sub.n.sub.(i+1).sup.(fly) to ensure that all UAVs participating in a task at the task point task.sub.n.sup.(i+1) arrive at the same time. Therefore, the total flight duration of the UAV is expressed as follows:

(28) $t_n^{\mathrm{fly}}=\{\begin{array}{cc}{t}_{{\mathrm{loc}}_n,{\mathrm{task}}_n^{\left(i\right)}}^{\mathrm{fly}}& \mathrm{if}\zeta =1;\\ t_{{\mathrm{loc}}_n,{\mathrm{task}}_n^{\left(i\right)}}^{\left(\mathrm{fly}\right)}+\underset{i=1}{\overset{\zeta -1}{.Math.}}{t}_{{\mathrm{task}}_n^{\left(i\right)},{\mathrm{task}}_n^{\left(i+1\right)}}^{\left(\mathrm{fly}\right)},& \mathrm{else}.\end{array}$

(29) where loc.sub.n represents an initial position of the UAV n; task execution duration (roughly about the hovering duration of the AUV) of the UAV at the m.sup.th task point is defined as t.sub.m.sup.(hover)=t.sub.m.sup.(com)+t.sub.m.sup.(tran), where t.sub.m.sup.(com) and t.sub.m.sup.(tran) represent duration of executing a consumable task and a non-consumable task by the UAV respectively; and based on total communication capacity σ.sub.m.sup.(z.sup.c.sup.) of the z.sub.c.sub.th type of sub-task resource, t.sub.m.sup.(com) is defined as follows:

(30) $t_m^{\left(\mathrm{tran}\right)}=\max \left\{\frac{I_m^{\left(1\right)}}{{\sigma }_m^{\left(1\right)}},.Math.,\frac{I_m^{\left(z_c\right)}}{{\sigma }_m^{\left(z_c\right)}}\right\},{\sigma }_m^{\left(z_c\right)}\ne 0$

(31) In conclusion, the total hovering duration of the UAV n is obtained according to the following formula:

(32) $t_n^{\left(\mathrm{hover}\right)}=\underset{i=1}{\overset{.Math.{\mathrm{Task}}_n^{\left(\mathrm{UAV}\right)}.Math.}{.Math.}}{t}_{{\mathrm{task}}_n^{\left(i\right)}}^{\left(\mathrm{hover}\right)}$

(33) After the sorting by task priority, an execution sequence before the m.sup.th task point is defined as follows:
Task.sub.m.sup.(point)={task.sub.m.sup.(l), . . . ,task.sub.m.sup.(j), . . . ,task.sub.m.sup.(J)},task.sub.m.sup.(j)∈M,task.sub.m.sup.(J)=m

(34) where J represents a length of the task execution sequence before the m.sup.th task point, and the waiting time of the m.sup.th task point is defined as follows:

(35) $t_m^{\left(\mathrm{wait}\right)}=\{\begin{array}{c}{t}_{{\mathrm{loc}}_n,{\mathrm{task}}_m^{\left(l\right)}}^{\left(\mathrm{fly}\right)},\\ t_{{\mathrm{loc}}_n,{\mathrm{task}}_m^{\left(1\right)}}^{\left(\mathrm{fly}\right)}+\underset{j=1}{\overset{J-1}{.Math.}}{t}_{{\mathrm{task}}_m^{\left(j\right)},{\mathrm{task}}_m^{\left(j+1\right)}}^{\left(\mathrm{fly}\right)}+\\ \underset{j=1}{\overset{J-1}{.Math.}}{t}_{{\mathrm{task}}_m^{\left(j\right)}}^{\left(\mathrm{hover}\right)},\end{array}\begin{array}{c}J=1;\\ \\ \\ \mathrm{Others}\end{array}$

(36) 3) Flight energy consumption of the UAV: Because propulsion energy consumption is far greater than communication energy consumption, communication power consumption is usually ignored compared with the propulsion power consumption. Therefore, when a speed of the UAV is V, propulsion power of the UAV is expressed as follows:

(37) $P\left(V\right)=P_0\left(1+\frac{3V^2}{U_{\mathrm{tip}}^2}\right)+{P_1\left(\sqrt{1+\frac{V^4}{4v_0^4}}-\frac{V^2}{2v_0^2}\right)}^{1/2}+\frac{1}{2}{f}_0\rho s_0\eta V^3$

(38) where P.sub.0 and P.sub.1 represent blade profile power and induced power in a hovering state respectively, U.sub.tip and v.sub.0 represent a tip speed of a rotor and a mean rotor velocity in the hovering state respectively, f.sub.0 and η represent a fuselage drag ratio and rotor solidity respectively, and ρ and s.sub.0 represent air density and disc area of the rotor respectively; and therefore, the total propulsion energy consumption of the UAV is as follows:

(39) 0$E_n=\underset{i=1}{\overset{\zeta }{.Math.}}P\left(0\right)t_{{\mathrm{task}}_n^{\left(i\right)}}^{\left(\mathrm{hover}\right)}+P\left(V_{{\mathrm{loc}}_n,{\mathrm{task}}_n^{\left(i\right)}}^{\left(\mathrm{fly}\right)}\right)t_{{\mathrm{loc}}_n,{\mathrm{task}}_n^{\left(i\right)}}^{\left(\mathrm{fly}\right)}+\underset{i=1}{\overset{\zeta -1}{.Math.}}P\left(V_{{\mathrm{task}}_n^{\left(i\right)},{\mathrm{task}}_n^{\left(i+1\right)}}^{\left(\mathrm{fly}\right)}\right)t_{{\mathrm{task}}_n^{\left(i\right)},{\mathrm{task}}_n^{\left(i+1\right)}}^{\left(\mathrm{fly}\right)}.$

(40) In addition, the consumable resources carried by the UAV are limited. After the consumable resources are exhausted, only the non-consumable task can be performed. Furthermore, fuel oil carried by the UAV is also limited. When a remaining fuel capacity of the UAV reaches a threshold, the UAV has to exit task allocation and return. Therefore, navigation of the UAV needs to satisfy the following energy constraint:
E.sub.n≤E.sub.n.sup.(threshold),n∈N.

(41) In conclusion, network optimization is performed to maximize the utility of the whole network by forming a better overlapping coalitional structure for resource allocation. Therefore, an optimization formula is as follows:

(42) $\begin{array}{cc}\underset{SC}{\mathrm{maximize}}& \underset{m\in ℳ}{.Math.}{U}_m\left({𝒜}_m\right),\\ s.t.& .Math.{𝒜}_m.Math.\ne \varnothing ,m\in ℳ,\\ & E_n\le E_n^{\left(\mathrm{threshold}\right)},n\in 𝒩\\ & \underset{m\in ℳ}{.Math.}{\tau }_{n,m}^{\left(z_b\right)}\le b_n^{\left(z_b\right)},n\in 𝒩,m\in ℳ\\ & {\epsilon }_{n,m}^{\left(z_c\right)}=0\mathrm{or}{\mu }_n^{\left(z_c\right)},n\in 𝒩,m\in ℳ\end{array}$

(43) (3) A task resource allocation problem of a heterogeneous coalition-based UAV network is modeled as an overlapping coalition game model with transferable utility. In the model, the UAV acts as a player. Assuming that the UAV allocates a resource and forms an overlapping coalition to cooperatively complete the task, a quantity of coalitions is equal to a quantity of tasks. A task cooperation model based on the OCF game is defined as ={N, U.sub.m, SC, X}, where N represents a UAV player; U.sub.m represents a utility function of a task point coalition m; SC={A.sub.1, . . . , A.sub.m}, Mem(A.sub.m)∈N represents the overlapping coalitional structure; Mem(A.sub.m) represents the coalition member set of the UAVs that allocate the resources to the m.sup.th task point and is expressed as Mem(A.sub.m)={n∈N|A.sub.m.sup.(n)≠Ø}; and X={x.sub.1, . . . , x.sub.n, . . . , x.sub.N} represents a UAV decision-making vector for determining the task resource allocation, and a resource allocation vector of each UAV is defined as X.sub.n=[A.sub.1.sup.(n), . . . , A.sub.m.sup.(n), . . . , A.sub.M.sup.(n)]. In addition, each UAV gets a share of a revenue from a coalition that the UAV joins, and a revenue sharing problem is resolved according to basic proportional fairness of a Shapley value. Utility of the UAV n may be expressed as follows:

(44) $u_n=\underset{m\in ℳ}{.Math.}{\mho }_n^{\left(m\right)}{U}_m\left({𝒜}_m\right)$

(45) where .sub.n.sup.(m) represents a proportion of UAV resource allocation for the task point coalition m to guarantee that a utility back deserved by the UAV from the coalition increases as the task resources of the UAV allocated to the coalition increases. A corresponding expression is as follows:

(46) ${\mho }_n^{\left(m\right)}=\frac{O_n^{\left(m\right)}}{\underset{n\in \mathrm{Mem}\left(A_m\right)}{.Math.}{O}_n^{\left(m\right)}}$

(47) where O.sub.n.sup.m represents an amount of resources allocation of the UAV n to the task point coalition m, and is expressed as follows:

(48) $O_n^{\left(m\right)}=\underset{{\tau }_{n,m}^{\left(z_b\right)},{\epsilon }_{n,m}^{\left(z_c\right)}\in {𝒜}_m^{\left(n\right)}}{.Math.}\left(.Math.{\tau }_{n,m}^{\left(z_b\right)}.Math.+.Math.{\epsilon }_{n,m}^{\left(z_c\right)}.Math.\right).$

(49) Two coalitional structures SC.sub.Q and SC.sub.P are provided, and the coalitional structure SC.sub.Q is superior to the coalitional structure SC.sub.P which is expressed as SC.sub.Q.sub.n SC.sub.P. SC.sub.Q.sub.n SC.sub.P indicates that the UAV player n prefers to allocate the task resources by using the coalitional structure SC.sub.Q instead of the coalitional structure SC.sub.P. A coalitional structure SC.sub.P={A.sub.l.sup.(p), . . . , A.sub.m.sup.(p)} is considered. For some resources δ.sub.n.sup.(z.sup.b.sup.) of the UAV player n, which satisfy a condition |δ.sub.n.sup.(z.sup.b.sup.)|≤|τ.sub.n.sup.(z.sup.b.sup.)|, a switch operation is defined as an action of moving some consumable resources from a coalition A.sub.i.sup.(p) to a coalition A.sub.j.sup.(p) to generate a new coalitional structure SC.sub.Q=SC.sub.P\{A.sub.i.sup.(p),A.sub.j.sup.(p)}∪{A.sub.i.sup.(q),A.sub.j.sup.(q)}, where A.sub.i.sup.(q)=A.sub.i.sup.(p)\{δ.sub.n.sup.(z.sup.b.sup.)} and A.sub.j.sup.(q)=A.sub.j.sup.(p)∪{δ.sub.n.sup.(z.sup.b.sup.)}.

(50) For a non-consumable resource μ.sub.n.sup.(z.sup.c.sup.), the switch operation is defined as an action of leaving or joining the coalition A.sub.i.sup.(p) to generate a new coalitional structure SC.sub.Q=SC.sub.P\{A.sub.i.sup.(p)}∪{A.sub.i.sup.(q)}, where A.sub.i.sup.(q)=A.sub.i.sup.(p)\{μ.sub.n.sup.(z.sup.c.sup.)} or A.sub.j.sup.(p)∪{μ.sub.n.sup.(z.sup.c.sup.)}. The two coalitional structures obtained after the switch operation need to satisfy a preference decision, namely, SC.sub.Q.sub.n SC.sub.P.

(51) Step 2: Propose a BMBT order to evaluate preferences of the UAV n for the two coalitional structures, to avoid falling into local optimization and create more total network utility.

(52) The BMBT order is defined as follows: For any UAV n∈N and any two coalitional structures SC.sub.P and SC.sub.Q that are generated through the switch operation, where A(n)={A.sub.n∈SC|A.sub.m.sup.(n)≠Ø, m∈M} represents a set of other task point coalitions to which the UAV n allocates resources,

(53) $S{C}_Q{\succ }_{n}S{C}_P\iff u_n\left(S{C}_Q\right)+\underset{g\in \mathrm{Mem}\left({𝒜}_j\right)\backslash \left\{n\right\}}{.Math.}\left[u_g\left(S{C}_Q\right)-u_g\left(S{C}_P\right)\right]+\underset{o\in \mathrm{Mem}\left(𝒜\left(n\right)\right)\backslash \left\{n\right\}}{.Math.}{u}_o\left(S{C}_Q\right)>u_n\left(S{C}_P\right)+\underset{h\in \mathrm{Mem}\left({𝒜}_j\right)\backslash \left\{n\right\}}{.Math.}\left[u_h\left(S{C}_P\right)-u_h\left(S{C}_Q\right)\right]+\underset{o\in \mathrm{Mem}\left(𝒜\left(n\right)\right)\backslash \left\{n\right\}}{.Math.}{u}_o\left(S{C}_P\right);$
and

(54) when the UAV n performs a resource switch operation, a proposed preference decision indicates that total coalitional utility containing utility of the UAV n and utility of a resource transfer coalition is greater than that before resource transfer. When this condition is satisfied, the switch operation is successful; otherwise, the switch operation fails.

(55) Step 3: Optimize the task resource allocation of the UAV under the overlapping coalitional structure by using a preference gravity-guided Tabu Search algorithm based on a preference relationship between the UAV and tasks with a same type of resource, to form a stable coalitional structure.

(56) Firstly, a resource allocation vector of the UAV n for the m.sup.th task point in a k.sup.th iteration is defined as A.sub.m.sup.(n)={τ.sub.n,m.sup.(1)(k), . . . , τ.sub.n,m.sup.(z.sup.b.sup.)(k), . . . , ε.sub.n,m.sup.(z.sup.c.sup.)(k), . . . , ε.sub.n,m.sup.(Z)(k)}, and a coalitional structure SC.sup.(k)={A.sub.1.sup.(k), . . . , A.sub.m.sup.(k)} under resource allocation in the k.sup.th iteration is obtained. A Tabu list Tabu.sub.SC={SC.sup.(k-L.sup.tabu.sup.), . . . , SC.sup.(k-1)} is established based on resource allocation under a historical coalitional structure, where L.sub.tabu represents a Tabu length, indicating existence time of the coalitional structure in the Tabu list. It should be noted that the UAV cannot perform a switch operation for resource allocation, which generates a coalitional structure that is the same as a coalitional structure in the Tabu list. Secondly, the Tabu Search algorithm is sensitive to an initial solution, such that a better initial solution can improve a convergence speed of the algorithm and quality of a final solution. To guide the UAV to search for an appropriate resource allocation decision, a concept of preference gravity is introduced based on tasks of remaining unallocated resources and UAVs of remaining unused resources. A vector of a remaining resource required by the m.sup.th task point is defined as L.sub.m.sup.(less)(k)={Le.sub.m.sup.(1)(k), . . . , Le.sub.m.sup.(z.sup.b.sup.)(k), . . . , Re.sub.m.sup.(z.sup.c.sup.)(k), . . . , Re.sub.m.sup.(Z)(k)}, where Le.sub.m.sup.(z.sup.b.sup.)(k) and Re.sub.m.sup.(z.sup.c.sup.)(k) are expressed as follows:

(57) $L{e}_m^{\left(z_b\right)}\left(k\right)=\max \left\{0,l_m^{\left(z_b\right)}-\underset{n\in 𝒩}{.Math.}{\tau }_{n,m}^{\left(z_b\right)}\left(k\right)\right\}$$R{e}_m^{\left(z_c\right)}\left(k\right)=\max \left\{0,{\xi }_m^{\left(z_c\right)}-\underset{n\in 𝒩}{.Math.}{\epsilon }_{n,m}^{\left(z_c\right)}\left(k\right)\right\}$

(58) Le.sub.m.sup.(z.sup.b.sup.)(k) and Re.sub.m.sup.(z.sup.c.sup.)(k) vary with a UAV resource allocation decision. The preference gravity may be regarded as a degree of preference between a remaining resource required by the task point and a remaining resource carried by the UAV. A preference gravity vector of a z.sup.th type of resource of the UAV n for each task is defined as F.sub.n.sup.(z)(k)=[f.sub.1,n.sup.(z)(k), . . . , f.sub.m,n.sup.(z)(k)], where f.sub.m,n.sup.(z)(k) represents preference gravity for the m.sup.th task point, and is expressed as follows:

(59) $f_{m,n}^{\left(z\right)}\left(k\right)=\{\begin{array}{cc}\frac{{\left({\beta }_m\right)}^{2}L{e}_m^{\left(z_b\right)}\left(k\right){\delta }_n^{\left(z_b\right)}}{d_{m,n}},& \mathrm{when}z=z_b;\\ \frac{{\left({\beta }_m\right)}^{2}R{e}_m^{\left(z_c\right)}\left(k\right){\mu }_n^{\left(z_c\right)}}{d_{m,n}},& \mathrm{when}z=z_c.\end{array}$

(60) A probability vector of the z.sup.th type of resource δ.sub.n.sup.(z) of the n.sup.th UAV for being allocated to each task is defined as P.sub.n.sup.(z)(k)=[p.sub.n,1.sup.(z)(k), . . . , p.sub.m,n.sup.(z)(k), . . . , p.sub.n,M.sup.(z)(k)], and is expressed as follows:

(61) $p_{m,n}^{\left(z\right)}\left(k\right)=\frac{\exp \left[f_{m,n}^{\left(z\right)}\left(k\right)\Gamma \left(k\right)\right]}{\underset{m\in M}{.Math.}\exp \left[f_{m,n}^{\left(z\right)}\left(k\right)\Gamma \left(k\right)\right]}.$

(62) where Γ(k) represents the Boltzmann coefficient. The UAV performs a switch operation according to a selection probability established based on the preference gravity. If proposed priority is satisfied, the UAV performs a switch operation of resource allocation to improve the total task execution utility of the network; otherwise, the UAV maintains the original coalitional structure under the resource allocation. A specific algorithm process is as follows:

(63) a) Initialization: Set a quantity k of iterations to 0, namely, k=0. A coalitional structure under resource allocation in each iteration is denoted as SC.sup.(k)={A.sub.1.sup.(k), . . . , A.sub.m.sup.(k)}, a Tabu list Tabu.sub.SC={SC.sup.(k-L.sup.tabu.sup.), . . . , SC.sup.(k-1)} is established and initialized to empty, and a Tabu length is set as L.sub.tabu. A remaining initially-carried resource L.sub.m.sup.(less)(0) is input to obtain F.sub.n.sup.(z)(0) and P.sub.n.sup.(z)(0). An initially carried resource of the UAV is allocated to each task point based on P.sub.n.sup.(z)(0), and step b), step c), and step d) are performed cyclically.

(64) b) Set k=k+1. A vector L.sub.m.sup.(less)(k) and the Tabu list Tabu.sub.SC are updated based on a coalitional structure SC.sup.(k-1). The Boltzmann coefficient is updated according to a rule Γ(k+1)=Γ(k)+k(Γ.sub.max−Γ(k))/K.sub.max.

(65) c) Some consumable UAV resources δ.sub.n.sup.(z.sup.b.sup.) or non-consumable resources μ.sub.n.sup.(z.sup.c.sup.) are randomly selected, and δ.sub.n.sup.(z.sup.b.sup.) or μ.sub.n.sup.(z.sup.c.sup.), and L.sub.m.sup.(less)(k) are input into a preference gravity expression to obtain P.sub.n.sup.(z)(k). Then, the UAV n performs a switch operation based on the vector P.sub.n.sup.(z)(k). A coalitional structure obtained after the switch operation is SC.sub.switch.sup.(k). If the new coalitional structure SC.sub.switch.sup.(k) is different from any one in the Tabu list Tabu.sub.SC, step d) is performed; otherwise, step b) is performed.

(66) d) The UAV n updates the coalitional structure according to the following order:

(67) $S{C}^{\left(k\right)}=\{\begin{array}{cc}S{C}_{\mathrm{swicth}}^{\left(k\right)},& \mathrm{if}S{C}_{\mathrm{swicth}}^{\left(k\right)}{\succ }_{n}S{C}^{\left(k-1\right)}\\ S{C}^{\left(k-1\right)},& \mathrm{else}\end{array}$

(68) e) End the process when the utility is still not improved after K.sub.stable iterations are performed or a total quantity of iterations reaches K.sub.max, to obtain a final convergence structure SC.sup.(*).

(69) Simulation analysis is performed by using simulation parameters in Table 1.

(70) TABLE-US-00001 TABLE 1 Simulation parameters Parameter Value Required task completion time t.sub.m.sup.(com) ∈ (50 − 120), ∀m ∈ M Maximum flight speed of a UAV (m/s) v.sub.n ∈ (6 − 22), ∀n ∈ N Time consumption consumption weight ω.sub.2/ω.sub.1 = (0.01 − 0.04) coefficient Energy consumption weight coefficient ω.sub.3/ω.sub.1 = (0.01 − 0.04) Boltzmann coefficient Γ.sub.max = 2 Blade profile power p.sub.n = 0.2 W, ∀n ∈ N Fuselage drag ratio f.sub.0 = 0.3 Air density ρ = 1.125 Mean rotor velocity v.sub.0 = 200 m/s Tip speed of a rotor U.sub.tip = 7.3 m/s

(71) As shown in FIG. 3, a convergence speed and total network utility of the proposed preference gravity-guided Tabu search algorithm are higher than those of other algorithms. This verifies effectiveness of the proposed algorithm. A reason is that the setting of the preference gravity can guide the UAV to converge to a better coalitional structure. The proposed OCF scheme can make the UAV to form a more flexible resource allocation coalition structure. Therefore, with only a few extra iterations, the OCF game scheme generates higher network utility than the CF game scheme.

(72) FIG. 4 shows average utility of task points under different preference criteria as a quantity of UAVs increases when there are five tasks. First, the average utility of the task points increases as the quantity of UAVs increases. Furthermore, the task execution utility achieved based on the proposed BMBT order is obviously higher than that achieved based on a traditional Pareto order or selfish order. In the proposed BMBT order, each UAV plays more attention to cooperation in its own partially overlapping coalition, to improve the total utility of the network.

(73) To sum up, the existing CF game model usually assumes that different UAVs execute tasks separately, does not consider a cooperation relationship between heterogeneous UAVs, and only optimizes a composition structure of UAVs in a coalition.

(74) In view of this, considering the overlapping and complementary relationship between the resource properties of the UAV and the task and the task priority, the present invention provides the sequential OCF game model to quantify the characteristics of the resource properties of the UAV and the task, and optimize the task resource allocation of the UAV under the overlapping coalitional structure. In addition, the present invention provides a BMBT order maximizing a revenue of a UAV, to further prove that the OCF game under the BMBT order is an extract potential game. Then, the stability of the overlapping coalitional structure is ensured through Nash equilibrium (NE). Based on the preference relationship between the UAV and the tasks with the same type of resource, the present invention provides the preference gravity-guided Tabu search algorithm to obtain the stable coalitional structure. The proposed OCF game scheme based on the preference gravity-guided Tabu search algorithm in the present invention is superior to a non-overlapping CF game scheme. In addition, the proposed BMBT order is superior to other criteria.

(75) The above described are only preferred implementations of the present invention, and the protection scope of the present invention is not limited to the above embodiments. All technical solutions based on the idea of the present invention should fall within the protection scope of the present invention. It should be noted that several modifications and adaptations made by those of ordinary skill in the art without departing from the principle of the present invention should fall within the protection scope of protection of the present invention.