# A User-Priority-Driven Multi-UAV Cooperative Reconnaissance Strategy

Authors: Zeyuan Liu; Cuntao Liu; Wendong Zhao; Aijing Li
Journal: International Journal of Aerospace Engineering
 (2021)

---

## Abstract

This paper considers a reconnaissance scenario where multiple unmanned aerial vehicles (UAVs) provide services cooperatively for multiple users with different priorities. Although users all expect to acquire their needed information in a short time, the degree of urgency to meet their demands is different when taking their diverse priorities into account. A priority-driven multiuser satisfaction model is designed, where users’ satisfaction is quantified based on their different priorities, information acquisition demands, and the time they obtain their desired information. To ensure high priority users’ fast information acquisition while avoiding excessive delay in low priority users’ information acquisition, a batchwise information backhaul strategy is adopted. In each batch, a UAV is selected as the data ferry through a consultative mechanism to carry information back to users. This reconnaissance process is formulated as a cooperative path planning problem, where the optimization objective is maximizing users’ total satisfaction, while an intelligent algorithm is proposed to solve this problem effectively. The simulation results show that compared with traditional path planning algorithms without considering user satisfaction, our proposed algorithm can guarantee faster information acquisition for users with higher priorities, which leads to higher satisfaction. In addition, the applicability of our proposed reconnaissance strategy and path planning algorithm in different situations is also analyzed.


---

## Body

## 1. Introduction

Unmanned aerial vehicles (UAVs) have been widely used as mobile carriers to store information in many fields, such as military reconnaissance and disaster relief, due to their mobility and flexibility [1–3]. Usually, users need to obtain information on distant targets in a short time for their decision. In this case, using UAVs to reconnoiter distant targets and deliver information back to users is an excellent strategy [4]. Due to the limited capability of a single UAV, multiple UAVs are usually used to conduct cooperative reconnaissance to deal with complex tasks [5], e.g., providing reconnaissance services simultaneously for multiple users with different requirements or conducting a reconnaissance process with dynamic and uncertain task flows.Unlike reconnaissance scenarios where only a single user exists [6, 7], we consider the scenario where multiple users need different target information, and all expect to obtain this information in a short time. UAVs need to meet their differentiated demands as best as possible while considering service fairness for different users. In addition, users may have different statuses or perform tasks with different importance; thus, we need to consider that they have different priorities. The higher the user’s priority, the faster the information acquisition should be guaranteed. To accomplish this, effective task assignment and path planning strategies are essential. Current studies on multi-UAV cooperative reconnaissance with multiple users usually ignore the differences between users, i.e., users are supposed to obtain the same target’s information or have the same priorities [8–11]. The other work did not consider different information acquisition time of different priority users [12–20], or their information backhaul strategies did not balance the demand of different priority users well [21–25]. The impact of differences among users is not considered in task assignment and path planning. These above studies’ path planning methods and evaluation criteria do not work well in scenarios where users’ priorities and demands are different.In this paper, we consider a reconnaissance scenario where multiple UAVs are used to provide services cooperatively for multiple users with different priorities. Taking users’ diverse priorities into account, a multiuser satisfaction model and a user-priority-driven reconnaissance strategy are proposed. Then, the cooperative path planning problem of multiple UAVs is considered and optimized with the goal of maximizing multiuser satisfaction. Our main contributions are summarized as follows:(i)
A priority-driven multiuser satisfaction model is proposed, where users’ satisfaction is described and quantified according to their different priorities, information acquisition demands, and the time they obtain their desired information. It comprehensively considers the information acquisition time of each user and achieves a good trade-off between the needs of high priority and low priority users(ii)
A batchwise information backhaul strategy is proposed to ensure high priority users’ fast information acquisition while avoiding excessive delay in low priority users’ information acquisition. In each batch, by adopting a cooperative consultative and information sharing mechanism, one of the task execution UAVs is selected as a data ferry to carry the information collected by all UAVs back to users(iii)
The above reconnaissance process with a batchwise information backhaul strategy is formulated as a cooperative path planning problem, where the optimization objective is maximizing users’ total satisfaction. To solve this problem effectively, a batchwise information transmission-based path planning algorithm (BITPP) is proposed. Simulation results show the effectiveness of our proposed BITPP algorithm in ensuring lower information acquisition time and higher user satisfaction for users with higher priorities


## 2. Related Work

To date, much research has been done on the path planning problem in cooperative reconnaissance, which is beneficial for shortening the information acquisition time as well as reducing UAVs’ energy consumption [12–21] Among them, to ensure users’ fast information acquisition, some studies have focused on minimizing the maximum reconnaissance time of UAVs [10–12]. However, in these studies, the difference in the information acquisition demands of users was not well considered, and users’ information acquisition time was not evaluated comprehensively regarding their different priorities. When considering tasks’ different priorities, several studies used the priorities as different weights to maximize the task metrics’ weighted results [13–15]. Several studies designed reward values and penalty values pertaining different tasks according to their priorities to maximize the final reward [16, 17]. However, these means cannot guarantee that higher priority tasks can be completed before low priority tasks. If an evaluation criterion was to be that UAVs completed their tasks sequentially according to the order of their priorities, it could cause too much delay for the completion of low priority tasks, such as [18], or the low priority tasks will be given up, such as [19], which is not fair to low priority users.In addition, different information backhaul strategies have been proposed and adopted in several studies. Among them, Ref. [20–22] favored a one-time strategy of information backhaul, where UAVs transmitted information to users after finishing the reconnaissance process of all targets. Under this condition, higher priority users cannot obtain their desired information until the UAV assigned to provide service for them has reconnoitered all targets, which will significantly prolong the time for their obtaining information. To address this problem, Ref. [23] proposed a multiround information backhaul strategy, where UAVs conducted multiple trips between the reconnaissance area and users to realize data unloading. During each trip, multiple UAVs cooperatively performed reconnaissance a group of targets and deliver corresponding information to the users who need it. Although higher priority users can obtain their desired information much more quickly, users with lower priorities will experience much more delay in their information acquisition, especially when users are far away from the reconnaissance area or too many round trips are needed because of several factors, e.g., the number of available UAVs is limited, the distribution of target points is overly discrete, or the number of users is large, and the information acquisition delay for lower priority users may be too long to be acceptable. Ref. [24] adopted an immediate information backhaul strategy by using UAVs as fixed relays to construct available communication links between the reconnaissance area and users. However, when facing situations where users are far away from the reconnaissance area or the number of users is large, too many UAVs are needed to maintain effective communication links, which will result in a huge reconnaissance cost.


## 3. System Model and Problem Formulation

### 3.1. Scenario Description

We consider a scenario in which UAVs need to reconnoiter targets and distribute information to users in the user area. The set of users and targets ise denoted asM=1,⋯M, m∈M, and K=1,⋯K, k∈K. Each user is interested in multiple target points, and the information requirement relationship of users with targets is denoted as a binary variable rmk, where rmk=1 represents that m needs the information of k, and rmk=0 represents others. The number of UAVs is N, and this set is denoted as N=1,⋯N, n∈N. We assumed that UAVs need to be near the user when they transmit information. In addition, it is assumed that the UAVs involved in reconnaissance have sufficient flight time to complete the assigned targets’ reconnaissance.All users need to obtain information as soon as possible, and each user gives a degree of satisfaction for the UAV reconnaissance service according to their information acquisition time. The faster a user obtains the required information, the more satisfied it is with the UAVs’ reconnaissance service. Each user has a priority value to measure the importance of the user and determine the order in which the information is obtained. Users with higher priority need to obtain information faster than users with lower priority.λm represents the priority value of m. Although users all expect a short information acquisition time, UAVs cannot ensure that each user obtains the same high service quality under a limited number. Thus, we pursue maximizing the overall user satisfaction and propose a batchwise information backhaul strategy to improve multiuser satisfaction.


### 3.2. Priority-Based Multiuser Satisfaction Model

We propose a priority-based multiuser satisfaction model to measure the information acquisition time of users with different priorities and measure the order in which the user obtains the information. In this model,sm represents the satisfaction of user m, and tm,end represents the time when m obtains all information it needs. The sm will change with the size of time tm,end. We assumed that each user has a uniform expected time for obtaining the needed information and is denoted as Texpect. We denoted a satisfaction constant γ to represent one user obtaining the required information at time Texpect. When tm,end is earlier than Texpect, sm will equal γ, and when tm,end is later than Texpect, sm will decrease over time. In addition, each user has a maximum tolerance time Tdeadline, and user satisfaction becomes 0 when tm,end is later than Tdeadline. Thus, sm is calculated by equation (1).
(1)sm=γtm,endTexpectγTdeadline−Tm,endTdeadline−TexpectTexpect<tm,end<Tdeadline0tm,endTdeadline.Multiuser satisfaction is represented byξ, which is determined following two principles. The first is that a user must obtain information earlier than a user with lower priority. The second is that the impact of higher priority user satisfaction on ξ must be greater than the impact of lower priority user satisfaction. We denoted variable δ to measure whether users obtain information following the order of priority. When the user obtains information later than the user with a lower priority than it, δ takes the value of negative infinity to represent the penalty for violating the user priority order, which is calculated as follows:
(2)δ=−∞iftm,end−tj,endλm−λj00other.Subsequently, each user’s priority values are normalized, and then the processing results are used as weighting coefficients to weigh the satisfaction of each user. The equation ofξ is as follows:
(3)ξ=δ+∑m=1Mλmsm∑m=1Mλm.


### 3.3. Batchwise Information Backhaul Strategy

This section proposes a batchwise information backhaul strategy; that is, UAVs leave the reconnaissance area in batches to provide information for users. We divide the entire reconnaissance process intoL batches. In each batch, the UAV serves one or more users. They first come in the reconnaissance phase and reconnoiter the targets in which these users are interested. KlKl⊆K represents the target set that UAVs need to reconnoiter in the lth batch. Kl,nKl,n⊆Kl represents the target set assigned to n in the lth batch. Ml represents the user set that UAVs need to serve in the lth batch. λminMl represents the priority value of the user with the lowest priority in Ml, and λmaxMl represents the priority value of the user with the lowest priority in Ml. The priority of users served in the previous batch is generally higher than that of users served in the latter batch, with the constraint expressed as (4).
(4)λminMl−1>λmaxMl.After completing the reconnaissance of the assigned target, the UAV enters the information sharing phase. A ferry UAV per batch is selected to share information with other UAVs to obtain the information ofKl. exitl represents the ferry UAV in the lth batch. We assumed that other UAVs only share information with the ferry UAV of the current batch and that ferry UAVs share information with only one UAV at the same time. We denoted srexitl,n as the information sharing point of n and exitl, and they share information near it. Thus, in a batch, the ferry UAV has multiple information sharing points, and other UAVs have one information sharing point. These UAVs that share information with exitl move on to the next batch’s reconnaissance phase immediately after sharing information, while exitl proceeds to the information distribution phase. During the information distribution phase, exitl travels to the user area and distributes information to users in order of priority. Note that the UAV finished information distribution returns to the take-off position and is no longer involved in subsequent reconnaissance activity. The status of n in the batch l is denoted as bl,n, where bl,n=1 represents that n has entered the information distribution phase before entering the lth batch. bl,n=0 indicates that n continues to reconnoiter targets in the lth batch. In addition, exitl can only be selected among the UAVs involved in the reconnaissance activity within the lth batch, with the constraint expressed as (5).
(5)bl,exitl=0&bl+1,exitl=1.To simplify the model, we assumedLN; thus, only one UAV per batch is selected to transmit information for the user. The UAVs that are not selected at the last batch return directly to the take-off position after finishing the information sharing phase.An example is shown in Figure1. There are two UAVs, n1 and n2, and three users, m1, m2, and m3, and the priority relationship of users is λ3<λ2<λ1. User m1 needs the information of target 1, m2 is interested in target 2, and m3 needs the information of target 3. The user sets that are served in each batch are M1=m1,m2 and M2=m3. In the first batch, UAV n1 reconnoiters target 1, and n2 reconnoiters target 2 during the reconnaissance phase. Then, n1 and n2 went to the information sharing position after finishing the reconnaissance of the assigned target. n1 obtains the information of target 2 by sharing information with n2. Subsequently, n1 comes to the information distribution phase and transmits information for users m1 and m2, while n2 comes to the second batch and reconnoiter targets 3. Finally, n2 transmits information for m3.Figure 1
Schematic of batchwise information backhaul strategy.


### 3.4. Path Planning Problems

In this section, we model the reconnaissance process as a path planning problem to maximize multiuser satisfaction. The two-dimensional trajectory of the UAVn is denoted as pnt. In the lth batch, UAV first reconnoiter targets of Kl,n. The relationship between UAV and target reconnaissance is represented by binary function fnkt, where fnkt=1 means that the n reconnoiter for the target k at time t. fnkt=0 for other cases. UAVs must stay or hover in the area over the target for Ttarget time to obtain information, and the constraint is expressed by Equations (6) and (7).
(6)fnktpnt−ck=0,(7)∫0Tmaxfnktdt=Ttarget,whereck represents the target’s two-dimensional coordinates, and Tmax represents the UAV’s maximum flight time. The UAV needs to return the take-off position before reaching the maximum flight time. The constraint is expressed as
(8)pnTmax=pn0.UAVn goes to the predetermined information sharing point after finishing the reconnaissance phase. The information sharing relationship between UAVs is represented as a binary function gn,ikt, where gn,ikt=1 means that i provides information about target k for n at time t, and gn,ikt=0 represents the other cases. In addition, the remaining UAVs that share information with exitl can only provide the target information that they have obtained, with the constraint shown in (9).
(9)gexitl,ikt∫0tfikt/Ttargetdt.Whenexitl and i share information, they are near the information sharing point, which can be approximately regarded as two UAVs in the same two-dimensional coordinate. This constraint is expressed as (10).
(10)gexitl,iktpexitlt−pit=0.Because the two UAVs are close to each other, the information transmission speed is faster, and the shared information time can be ignored compared with the flight time. We assume that the two UAVs can complete the information sharing in an instant.tl,exitl is used to indicate the time when exitl ends the information sharing phase and enters the information distribution phase in the lth batch. After that, exitl will not participate in the subsequent reconnaissance activity. The constraints are shown in (11).
(11)bl,exitl∫tl,exitlTmaxfexitlkt+∑i=1Ngexitl,iktdt=0.In the information distribution phase, the information transmission relationship between the UAV and user is denoted as binary functionsnm, where snm=1 indicates that UAV n transmits information to user m, and snm=0 indicates that n does not transmit information to m. We assumed that the UAV is close to the user when it transmits information for this user, and it finishes information transmission instantly. The constraint is shown in (12).
(12)sexitlmpexitltm,end−cm=0.This equation indicates that the UAV must be at the user’s location when its transmission pertains to the user, wherecm represents the two-dimensional coordinate of m, and tm,end represents the time when m obtains the needed information. exitl needs to transmit all the information needed by the user at one time. That is, exitl needs to obtain this information through reconnaissance and information sharing before transmitting them. The constraint is represented as follows.
(13)∫0tm,endfexitlkt/Ttarget+∑i=lNgexitl,iktdt=sexitlmrmk.In addition, constraint (14) indicates that the time the user obtains information is below the UAV’s maximum flight time, and constraint (15) indicates that each UAV flies at a constant speed v.
(14)tm,endTmax,(15)dpntdt=v.The UAV path planning optimization objective is to maximize multiuser satisfaction, and the UAV path planning problem is formalized as follows.(16)maxpnt,snm,fnkt,gn,lktξs.t.6−15.


## 3.1. Scenario Description

We consider a scenario in which UAVs need to reconnoiter targets and distribute information to users in the user area. The set of users and targets ise denoted asM=1,⋯M, m∈M, and K=1,⋯K, k∈K. Each user is interested in multiple target points, and the information requirement relationship of users with targets is denoted as a binary variable rmk, where rmk=1 represents that m needs the information of k, and rmk=0 represents others. The number of UAVs is N, and this set is denoted as N=1,⋯N, n∈N. We assumed that UAVs need to be near the user when they transmit information. In addition, it is assumed that the UAVs involved in reconnaissance have sufficient flight time to complete the assigned targets’ reconnaissance.All users need to obtain information as soon as possible, and each user gives a degree of satisfaction for the UAV reconnaissance service according to their information acquisition time. The faster a user obtains the required information, the more satisfied it is with the UAVs’ reconnaissance service. Each user has a priority value to measure the importance of the user and determine the order in which the information is obtained. Users with higher priority need to obtain information faster than users with lower priority.λm represents the priority value of m. Although users all expect a short information acquisition time, UAVs cannot ensure that each user obtains the same high service quality under a limited number. Thus, we pursue maximizing the overall user satisfaction and propose a batchwise information backhaul strategy to improve multiuser satisfaction.


## 3.2. Priority-Based Multiuser Satisfaction Model

We propose a priority-based multiuser satisfaction model to measure the information acquisition time of users with different priorities and measure the order in which the user obtains the information. In this model,sm represents the satisfaction of user m, and tm,end represents the time when m obtains all information it needs. The sm will change with the size of time tm,end. We assumed that each user has a uniform expected time for obtaining the needed information and is denoted as Texpect. We denoted a satisfaction constant γ to represent one user obtaining the required information at time Texpect. When tm,end is earlier than Texpect, sm will equal γ, and when tm,end is later than Texpect, sm will decrease over time. In addition, each user has a maximum tolerance time Tdeadline, and user satisfaction becomes 0 when tm,end is later than Tdeadline. Thus, sm is calculated by equation (1).
(1)sm=γtm,endTexpectγTdeadline−Tm,endTdeadline−TexpectTexpect<tm,end<Tdeadline0tm,endTdeadline.Multiuser satisfaction is represented byξ, which is determined following two principles. The first is that a user must obtain information earlier than a user with lower priority. The second is that the impact of higher priority user satisfaction on ξ must be greater than the impact of lower priority user satisfaction. We denoted variable δ to measure whether users obtain information following the order of priority. When the user obtains information later than the user with a lower priority than it, δ takes the value of negative infinity to represent the penalty for violating the user priority order, which is calculated as follows:
(2)δ=−∞iftm,end−tj,endλm−λj00other.Subsequently, each user’s priority values are normalized, and then the processing results are used as weighting coefficients to weigh the satisfaction of each user. The equation ofξ is as follows:
(3)ξ=δ+∑m=1Mλmsm∑m=1Mλm.


## 3.3. Batchwise Information Backhaul Strategy

This section proposes a batchwise information backhaul strategy; that is, UAVs leave the reconnaissance area in batches to provide information for users. We divide the entire reconnaissance process intoL batches. In each batch, the UAV serves one or more users. They first come in the reconnaissance phase and reconnoiter the targets in which these users are interested. KlKl⊆K represents the target set that UAVs need to reconnoiter in the lth batch. Kl,nKl,n⊆Kl represents the target set assigned to n in the lth batch. Ml represents the user set that UAVs need to serve in the lth batch. λminMl represents the priority value of the user with the lowest priority in Ml, and λmaxMl represents the priority value of the user with the lowest priority in Ml. The priority of users served in the previous batch is generally higher than that of users served in the latter batch, with the constraint expressed as (4).
(4)λminMl−1>λmaxMl.After completing the reconnaissance of the assigned target, the UAV enters the information sharing phase. A ferry UAV per batch is selected to share information with other UAVs to obtain the information ofKl. exitl represents the ferry UAV in the lth batch. We assumed that other UAVs only share information with the ferry UAV of the current batch and that ferry UAVs share information with only one UAV at the same time. We denoted srexitl,n as the information sharing point of n and exitl, and they share information near it. Thus, in a batch, the ferry UAV has multiple information sharing points, and other UAVs have one information sharing point. These UAVs that share information with exitl move on to the next batch’s reconnaissance phase immediately after sharing information, while exitl proceeds to the information distribution phase. During the information distribution phase, exitl travels to the user area and distributes information to users in order of priority. Note that the UAV finished information distribution returns to the take-off position and is no longer involved in subsequent reconnaissance activity. The status of n in the batch l is denoted as bl,n, where bl,n=1 represents that n has entered the information distribution phase before entering the lth batch. bl,n=0 indicates that n continues to reconnoiter targets in the lth batch. In addition, exitl can only be selected among the UAVs involved in the reconnaissance activity within the lth batch, with the constraint expressed as (5).
(5)bl,exitl=0&bl+1,exitl=1.To simplify the model, we assumedLN; thus, only one UAV per batch is selected to transmit information for the user. The UAVs that are not selected at the last batch return directly to the take-off position after finishing the information sharing phase.An example is shown in Figure1. There are two UAVs, n1 and n2, and three users, m1, m2, and m3, and the priority relationship of users is λ3<λ2<λ1. User m1 needs the information of target 1, m2 is interested in target 2, and m3 needs the information of target 3. The user sets that are served in each batch are M1=m1,m2 and M2=m3. In the first batch, UAV n1 reconnoiters target 1, and n2 reconnoiters target 2 during the reconnaissance phase. Then, n1 and n2 went to the information sharing position after finishing the reconnaissance of the assigned target. n1 obtains the information of target 2 by sharing information with n2. Subsequently, n1 comes to the information distribution phase and transmits information for users m1 and m2, while n2 comes to the second batch and reconnoiter targets 3. Finally, n2 transmits information for m3.Figure 1
Schematic of batchwise information backhaul strategy.


## 3.4. Path Planning Problems

In this section, we model the reconnaissance process as a path planning problem to maximize multiuser satisfaction. The two-dimensional trajectory of the UAVn is denoted as pnt. In the lth batch, UAV first reconnoiter targets of Kl,n. The relationship between UAV and target reconnaissance is represented by binary function fnkt, where fnkt=1 means that the n reconnoiter for the target k at time t. fnkt=0 for other cases. UAVs must stay or hover in the area over the target for Ttarget time to obtain information, and the constraint is expressed by Equations (6) and (7).
(6)fnktpnt−ck=0,(7)∫0Tmaxfnktdt=Ttarget,whereck represents the target’s two-dimensional coordinates, and Tmax represents the UAV’s maximum flight time. The UAV needs to return the take-off position before reaching the maximum flight time. The constraint is expressed as
(8)pnTmax=pn0.UAVn goes to the predetermined information sharing point after finishing the reconnaissance phase. The information sharing relationship between UAVs is represented as a binary function gn,ikt, where gn,ikt=1 means that i provides information about target k for n at time t, and gn,ikt=0 represents the other cases. In addition, the remaining UAVs that share information with exitl can only provide the target information that they have obtained, with the constraint shown in (9).
(9)gexitl,ikt∫0tfikt/Ttargetdt.Whenexitl and i share information, they are near the information sharing point, which can be approximately regarded as two UAVs in the same two-dimensional coordinate. This constraint is expressed as (10).
(10)gexitl,iktpexitlt−pit=0.Because the two UAVs are close to each other, the information transmission speed is faster, and the shared information time can be ignored compared with the flight time. We assume that the two UAVs can complete the information sharing in an instant.tl,exitl is used to indicate the time when exitl ends the information sharing phase and enters the information distribution phase in the lth batch. After that, exitl will not participate in the subsequent reconnaissance activity. The constraints are shown in (11).
(11)bl,exitl∫tl,exitlTmaxfexitlkt+∑i=1Ngexitl,iktdt=0.In the information distribution phase, the information transmission relationship between the UAV and user is denoted as binary functionsnm, where snm=1 indicates that UAV n transmits information to user m, and snm=0 indicates that n does not transmit information to m. We assumed that the UAV is close to the user when it transmits information for this user, and it finishes information transmission instantly. The constraint is shown in (12).
(12)sexitlmpexitltm,end−cm=0.This equation indicates that the UAV must be at the user’s location when its transmission pertains to the user, wherecm represents the two-dimensional coordinate of m, and tm,end represents the time when m obtains the needed information. exitl needs to transmit all the information needed by the user at one time. That is, exitl needs to obtain this information through reconnaissance and information sharing before transmitting them. The constraint is represented as follows.
(13)∫0tm,endfexitlkt/Ttarget+∑i=lNgexitl,iktdt=sexitlmrmk.In addition, constraint (14) indicates that the time the user obtains information is below the UAV’s maximum flight time, and constraint (15) indicates that each UAV flies at a constant speed v.
(14)tm,endTmax,(15)dpntdt=v.The UAV path planning optimization objective is to maximize multiuser satisfaction, and the UAV path planning problem is formalized as follows.(16)maxpnt,snm,fnkt,gn,lktξs.t.6−15.


## 4. Algorithm Description

The difficulty in solving the above problems is mainly due to two aspects. First, the three functionsf, g and s are tightly coupled with many optimization variables. Second, the solution to the UAV path planning function p is known as an NP problem, which is challenging to find the optimal solution or cannot be solved in a short time [25]. The four functions are coupled with each other, which makes the problem more difficult to solve. To this end, we proposed the batchwise information transmission path planning algorithm (BITPP) to solve the above problems.Algorithm 1: BRPPA algorithm.
Input:M,N,K,LOutput:PN1for each n∈Ndo2pn=∅pn∈PN;3end4updatePN;5M1⋯ML=A1M,N,L;6PN0=PN;7N1=N;8forl=1 to Ldo9PNl=A2Ml,PNl−1,Nl,K;10Nl+1,exitl,PNl=A3Nl,PNl;11for each m∈rankMldo12pexitl=addpexitl,m;13end14end15updatePN;Three subproblems need to be solved sequentially for planning the UAV cooperative reconnaissance paths. The first is to determine which users are served by UAVs in each batch. The second and third are to determine UAVs’ paths of the reconnaissance phase and the information sharing phase during each batch. Thus, the BITPP algorithm is proposed, which includes three subalgorithms A1, A2, and A3 to solve the above subproblems. The algorithm inputs areN, M, and K, and the output is PN. PNpn∈PN represents the path set of the UAVs in set N and is constantly updated in the running of the BITPP algorithm. Nl represents the UAV set that continues to reconnoiter the targets in the lth batch, and PNl represents the path set of the UAVs in set Nl, where PNl⊆PN. BITPP first establishes an empty path array for each UAV (steps 1-4). Then, it uses subalgorithm A1 to determine the set of served users in each batch (step 5). Subsequently, L cycles are performed, and each cycle determines the path of each UAV in a batch. For example, in the lth cycle, step 9 uses algorithm A2 to determine the path of the UAVs in Nl when they complete the reconnaissance phase in the lth batch, and step 10 determines UAVs’ path when they complete the information sharing phase by algorithm A3. In addition, step 10 also determines the ferry UAV exitl and the set Nl+1. Then, the information distribution paths for the ferry UAVs in this batch are determined (steps 11-13), where the function rank() represents ranking the UAVs in order of priority from large to small. Step 15 updates set PN and obtains the final path of each UAV.


### 4.1. Determining the Users Served in Each Batch

Algorithm 2: A1.
Input:M,N,LOutput:M1⋯ML1Msort=rankM;2forl=1 to Ldo3λtotal=0;4for each m∈Msortdo5λtotal+=λm;6end7res=L−l+1;8λaverage=λtotal/res9Ml=∅10λpro=011foreachm∈Msortdo12λpro+=λm13Ml=Ml∪m14Msort=removeMsort,m;15ifλpro>λaveragethen16   break;17end18end19endPlanning a path for UAVs starts with determining that the users are served in each batch. Subalgorithm A1 arranges the served users following the principle that higher priority users are served preferentially. A1 inputs areN, M, and L, and outputs are Ml⋯ML. Ml represents the user set that is served by UAVs in the lth batch. Step 1 obtains set Msort by sorting the users in set M in descending order of priority. The user priority value sorted before in Msort is greater than the user sorted after. In steps 3-6, λtotal is the sum of all users’ priority values in the current Msort. In steps 7 and 8, res is the number of remaining batches, and λaverage is the average priority value of each batch and is calculated by equation λtotal/res. Step 9 creates empty set Ml, and step 10 uses λpro to represent the sum of all users’ priority values in the current Ml. Steps 11-18 add users from Msort to Ml in descending order of priority until λpro is greater than λaverage; then, it stops adding users and proceeds to the next loop.For example, users 1-5 have priority values of 50, 40, 30, 20, and 10, and the UAVs perform reconnaissance tasks in three batches. When searching for the users to be served in the first batch, we judgeres as 3 and calculate λtotal as 150, where λaverage is 50. Thus, user 1 is served in the first batch. Subsequently, res is 2, and λtotal is 100. Then, λaverage is 50, and users 2 and 3 are served in the second batch. Following this process, the third batch serves users 4 and 5.


### 4.2. Planning Path in the Reconnaissance Phase

The set of targetsKl can be determined based on the users served in the lth batch and the relationship between the user’s demand for targets. UAVs need to plan paths that can traverse all the targets in Kl during the lth batch’s reconnaissance phase, which is similar to the multiple traveling salesman problem [26]. To solve this problem, people usually use graph theory to construct targets as an undirected graph and find multiple routes that can traverse all the vertices in the graph with the least total cost [27]. In this paper, the target in Kl and the starting point of the UAVs entering the reconnaissance phase are used as vertices to construct an undirected graph GVl,El,Wl.In the first batch, the UAV’s starting point in the reconnaissance phase is its take-off position. In the other batches, the starting point is the endpoint of the UAV’s information sharing phase during the previous batch.Vl is the set of vertices, and the vertex vl,i∈Vl represents a starting point or targets. El is the set of edges, el,i,j∈El represents the edges from vl,i to vl,j, and UAVs need to fly along the edges. Wl is the weight set, wvl,i∈Wl is the point weight and represents the time of UAV reconnoiter vl,i, and wel,i,j∈Wl is the edge weight, representing the time spent by the UAV flying along edge el,i,j. wvl,i,vl,j represents the cost time that the UAV departed from vl,i to complete the reconnaissance of vl,j. It includes the time spent by the UAV flying along edge el,i,j and the time spent on reconnoiter vl,j. The calculation formula is as follows: wvl,i,vl,j=wel,i,j+wvl,j. Assuming that the UAVs fly at the same speed and have the same reconnaissance time at each target, they share the same weight set.Algorithm 3: A2.
Input:Ml,PNl−1,Nl,KOutput:PNl1 GetKl according to Ml and K;2 Get undirected graphGlVl,El according to Kl;3whileVl≠∅do4for each n∈Nldo5vl,n,end=endpn;6vnext=chosevl,n,end,Vl;7pn=addpn,vnext;8Vl=removeVl,vnext;9ifVl=∅then10   break;11end12end13end14whiletruedo15timemax,max,pmax=maxtimePNl;16ppro=pmax17Npro=removeNl,max18forn∈Nprodo19pn=addpn,vl,max,end20pmax=removepmax,vl,max,end21iftpntime_maxthen22Npro=removeNpro,n;23pn=removepn,vl,max,end;24pmax=addpmax,vl,max,end;25end26iftpn<time_maxthen27   break;28end29end30updatePNl;31ifppro=pmaxthen32  break;33end34endThe UAV’s path in the reconnaissance phase can be represented as a combination of a series of vertices. We obtain it by using subalgorithm A2, which is divided into two parts: forming the initial path (steps 1-13) and path adjustment (steps 14-34). When running A2 in thelth cycle, the algorithm inputs are Nl, Ml, and PNl−1, and the outputs are PNl. Nl represents the UAV set that continues to reconnoiter targets in the l batch. PNl represents the path set of the UAVs in Nl. Moreover, Nl−1=N when l=1. The first part is to search UAVs’ initial paths based on a greedy strategy. Each UAV takes turns to find the next vertex, which costs the least when the UAV departs from its current position to complete this vertex reconnaissance. The initial flight path of UAVs is obtained when all the vertices are traversed. Step 5 uses function endpn to find the endpoint vl,n,end of the current pn, and step 6 uses function chosevl,n,end,Vl to find the next visit vertex vnext when UAV n completes the reconnaissance of vertex vl,n,end. Step 7 uses function addpn,vnext to add vnext to the end of pn. Then, vnext is removed from Vl in step 8. When Vl becomes an empty set, the loop is terminated, and PNl is updated.In the second part,pmax and max, respectively, represent the most time-consuming path in PNl and the UAV corresponding to this path. time_max represents the time of UAV max fly along pmax. We need to adjust each UAV’s path by iterating. In each iteration, we first judge the pmax of the current set PNl, and then the endpoint of pmax is transferred to the end of the other path in PNl. If the algorithm can find the UAV path in which time_max in PNl decreases after it receives the endpoint of pmax, the algorithm continues to adjust the path in set PNl in the next iteration. Otherwise, this adjustment operation is canceled, and the iteration is terminated. In detail, step 15 searches pmax and time_max in PNl by function maxtimePNl. Function tpn calculates the time of n fly along path pn. Steps 18-30 adjust pmax and update the PNl. Steps 31-34 determine whether the pmax has changed. If there is no change, the path adjustment operation cannot be performed, and the iteration is terminated.For example, we obtain three paths by running subalgorithm A2, represented asp1=1,4,5, p2=2,6,7, and p3=3,8,9, and the relationship of these path’s cost time is represented as tp1>tp2>tp3. In the second step, we first judge time_max=tp1 and pmax=p1. Then, the endpoint of p1 is judged as vertex 5. If tp2+w7,5<time_max, we remove vertex 5 from p1 to the end of p2. The adjusted paths are p1=1,4, p2=2,6,7,5, and p3=3,8,9. Then, the next iteration of adjustment is entered. If tp2+w7,5>time_max and tp3+w7,5>time_max, no path can receive the endpoint of p1; so, path adjustment can no longer be performed, and the current UAV path is output as the final result.


### 4.3. Planning Path in the Information Sharing Phase

UAVs’ flight paths in the information sharing phase can be translated into a series of visited sequences of information sharing points. The ferry UAV has multiple information sharing points in each batch, while the remaining UAVs have only one information sharing point. We obtain the path of the UAVs’ information sharing phase by subalgorithm A3. In thelth batch, A3’s inputs are Nl and PNl, and the outputs are Nl+1, exitl, and PNl. A3 includes two parts. The first part is to determine the ferry UAV of the current batch, and the main idea is to select the UAV that ends the reconnaissance phase earliest as the ferry UAV exitl. In the second part, UAV exitl searches other UAVs and corresponding information sharing points for sharing information based on the earliest encounter principle. The behavior of two UAVs heading to the information sharing point in this principle is regarded as making a relative motion from the departure point.The departure point is the position where the UAV changes from the current flight direction to the direction of the next information sharing point. The next UAV shared with the ferry UAV encountered the earliest with the ferry UAV when they made the relative motion. Their encounter position is regarded as their information sharing point.srn,l,i represents the ith information point of UAV n in the lth batch. Assuming n is the second UAV that shares information with exitl in l, their information sharing point srexitl,n is the first information sharing point of n and the second information sharing point of exitl. That is, srn,l,1=srexitl,l,2=srn,exitl. Ferry UAV exit has multiple departure points. When it searches the first information sharing point, its departure point is the reconnaissance phase’s endpoint in the current batch. When it searches the ith information sharing point, its departure point is the previous information sharing point srexitl,l,i−1. Other UAVs have one departure point at which the reconnaissance phase endpoint is in the current batch.When running subalgorithm 3 in thelth cycle of BITPP, steps 1-7 find the UAV with the fastest ending reconnaissance phase in batch l as the ferry UAV exitl. Step 8 removes exitl from set Nl and obtain sets Npro and Nl+1, where Npro represents the UAV set that currently needs to share information with exitl. Step 9 determines the number of UAVs that need to share information with exitl. Step 11 establishes tpro to record the current fastest encounter time between exitl and other UAVs. Steps 12-20 find the UAV in set Npro that encounters exitl the earliest and use next to represent the UAV that can make the earliest encounter exitl in the current iteration. In step 13, function meet_time calculates the relative motion time between exitl and n, taking their current path end positions as the departure point.Algorithm 4: A3.
Input:Nl, PNlOutput:Nl+1,exitl,PNl1tpro=∞;2for each n∈Nldo3iftpntprothen4exitl=n;5tpro=tpn;6end7end8Nl+1=Npro=removeNl,exitl;9number=Npro10fori=1 to numberdo11tpro=∞12for each n∈Nprodo13meet_texitl,n=meet_timeexitl,n,pn,pexitl;14ifmeet_texitl,ntprothen15next=n16tpro=meet_texitl,n;17srexitl,l,i=meet_pointexitl,n,pn,pexitl;18srnext,l,1=srexitl,l,i;19end20end21pexitl=addpexitl,srexitl,l,i;22pnext=addpnext,srnext,l,1;23updatePNl;24removeNpro,next;25endIn addition, because the time when UAVs arrive at their respective departure point is different, it is necessary to calculate the time interval betweenexitl and n arriving at their respective departure point. This time interval is expressed by Δtexitl,n,i, and the formula is as follows:
(17)Δtexitl,n=tpn−tpexitl.meet_texitl,n represents the encounter time between exitl and n, and the formula is as follows:
(18)meet_texitl,n=dendpexitl,endpn−Δtexitl,i,n·v/2v,wheredendpexitl,endpn represents the distance between the endpoints of paths pexitl and pn. In step 17, the function meet_pointexitl,n,pn,pexitl calculates the encounter coordinates of exitl and n. Steps 21-22 add this encounter point to the end of the paths pexitl and pnext. In addition, it is used as the information sharing point of exitl and next. Step 23 updates PNl. Step 24 removes next from the set Npro and then enters the next cycle.An example of UAVs searching for information sharing points is shown in Figure2. There are four UAVs in the picture. Assuming UAV 1 ends the reconnaissance phase earliest, it is regarded as the ferry UAV of the current batch. In subfigure 2.1, the time for UAV 1 to reach the departure point is t1, and the time for UAVs 2, 3, and 4 to reach their respective departure points is t2, t3, and t4. The encounter time of UAV 1 with UAVs 2, 3, and 4 in relative motion is t1,2, t1,3, and t1,4, respectively. Assuming that t1,2<t1,3<t1,4, UAV 1 encounters UAV 2 at the earliest. The encounter position s1 between them is regarded as the first information sharing point of UAV 1 and UAV 2. In subfigure 2.2, UAV 1 arrives at the position of s1 and uses it as the departure point to calculate the time of encounter with UAVs 3 and 4. Assuming UAV 1 has the fastest encounter with UAV 3, UAV 3 is thus the next UAV that shares information with it. Their encounter point s2 is the first information sharing point of UAV 3 and the second of UAV 1. Then, UAV 1 arrives at s2 in subfigure 2.3 and uses it as the departure points to calculate the time of encounter with UAV 4. Their encounter point is the first information sharing point of UAV 4 and the third of UAV 1. In subfigure 2.4, UAV 1 arrives at s3, and the flight path of each UAV in the information sharing phase is determined.Figure 2
Schematic of the information sharing phase.


### 4.4. Complexity Analysis

In the BITPP algorithm, subalgorithm A1 is run once in total, and subalgorithms A2 and A3 are run L times. A1 iterates through each user in setM at most twice. Thus, its complexity is OM. A2 includes initial path planning and path adjustment. The complexity of these two parts is related to the number of targets in Kl. After A2 is run L times, its complexity is OK. The complexity of A3 is related to the number of UAVs in Nl. It includes two parts: finding the ferry UAV and the planning path of the information sharing phase. When determining the ferry UAV, it needs to traverse the Nl set once, and its complexity is not higher than ON. Thus, the complexity that runs this part L times is OLN. When planning the information sharing path, it is necessary to traverse the number of UAVs in set Nl minus one squared at most. Thus, the complexity of running the second part L times is OLN−12. In conclusion, the complexity of the BITPP algorithm is OM+K+LN2−N+1.


## 4.1. Determining the Users Served in Each Batch

Algorithm 2: A1.
Input:M,N,LOutput:M1⋯ML1Msort=rankM;2forl=1 to Ldo3λtotal=0;4for each m∈Msortdo5λtotal+=λm;6end7res=L−l+1;8λaverage=λtotal/res9Ml=∅10λpro=011foreachm∈Msortdo12λpro+=λm13Ml=Ml∪m14Msort=removeMsort,m;15ifλpro>λaveragethen16   break;17end18end19endPlanning a path for UAVs starts with determining that the users are served in each batch. Subalgorithm A1 arranges the served users following the principle that higher priority users are served preferentially. A1 inputs areN, M, and L, and outputs are Ml⋯ML. Ml represents the user set that is served by UAVs in the lth batch. Step 1 obtains set Msort by sorting the users in set M in descending order of priority. The user priority value sorted before in Msort is greater than the user sorted after. In steps 3-6, λtotal is the sum of all users’ priority values in the current Msort. In steps 7 and 8, res is the number of remaining batches, and λaverage is the average priority value of each batch and is calculated by equation λtotal/res. Step 9 creates empty set Ml, and step 10 uses λpro to represent the sum of all users’ priority values in the current Ml. Steps 11-18 add users from Msort to Ml in descending order of priority until λpro is greater than λaverage; then, it stops adding users and proceeds to the next loop.For example, users 1-5 have priority values of 50, 40, 30, 20, and 10, and the UAVs perform reconnaissance tasks in three batches. When searching for the users to be served in the first batch, we judgeres as 3 and calculate λtotal as 150, where λaverage is 50. Thus, user 1 is served in the first batch. Subsequently, res is 2, and λtotal is 100. Then, λaverage is 50, and users 2 and 3 are served in the second batch. Following this process, the third batch serves users 4 and 5.


## 4.2. Planning Path in the Reconnaissance Phase

The set of targetsKl can be determined based on the users served in the lth batch and the relationship between the user’s demand for targets. UAVs need to plan paths that can traverse all the targets in Kl during the lth batch’s reconnaissance phase, which is similar to the multiple traveling salesman problem [26]. To solve this problem, people usually use graph theory to construct targets as an undirected graph and find multiple routes that can traverse all the vertices in the graph with the least total cost [27]. In this paper, the target in Kl and the starting point of the UAVs entering the reconnaissance phase are used as vertices to construct an undirected graph GVl,El,Wl.In the first batch, the UAV’s starting point in the reconnaissance phase is its take-off position. In the other batches, the starting point is the endpoint of the UAV’s information sharing phase during the previous batch.Vl is the set of vertices, and the vertex vl,i∈Vl represents a starting point or targets. El is the set of edges, el,i,j∈El represents the edges from vl,i to vl,j, and UAVs need to fly along the edges. Wl is the weight set, wvl,i∈Wl is the point weight and represents the time of UAV reconnoiter vl,i, and wel,i,j∈Wl is the edge weight, representing the time spent by the UAV flying along edge el,i,j. wvl,i,vl,j represents the cost time that the UAV departed from vl,i to complete the reconnaissance of vl,j. It includes the time spent by the UAV flying along edge el,i,j and the time spent on reconnoiter vl,j. The calculation formula is as follows: wvl,i,vl,j=wel,i,j+wvl,j. Assuming that the UAVs fly at the same speed and have the same reconnaissance time at each target, they share the same weight set.Algorithm 3: A2.
Input:Ml,PNl−1,Nl,KOutput:PNl1 GetKl according to Ml and K;2 Get undirected graphGlVl,El according to Kl;3whileVl≠∅do4for each n∈Nldo5vl,n,end=endpn;6vnext=chosevl,n,end,Vl;7pn=addpn,vnext;8Vl=removeVl,vnext;9ifVl=∅then10   break;11end12end13end14whiletruedo15timemax,max,pmax=maxtimePNl;16ppro=pmax17Npro=removeNl,max18forn∈Nprodo19pn=addpn,vl,max,end20pmax=removepmax,vl,max,end21iftpntime_maxthen22Npro=removeNpro,n;23pn=removepn,vl,max,end;24pmax=addpmax,vl,max,end;25end26iftpn<time_maxthen27   break;28end29end30updatePNl;31ifppro=pmaxthen32  break;33end34endThe UAV’s path in the reconnaissance phase can be represented as a combination of a series of vertices. We obtain it by using subalgorithm A2, which is divided into two parts: forming the initial path (steps 1-13) and path adjustment (steps 14-34). When running A2 in thelth cycle, the algorithm inputs are Nl, Ml, and PNl−1, and the outputs are PNl. Nl represents the UAV set that continues to reconnoiter targets in the l batch. PNl represents the path set of the UAVs in Nl. Moreover, Nl−1=N when l=1. The first part is to search UAVs’ initial paths based on a greedy strategy. Each UAV takes turns to find the next vertex, which costs the least when the UAV departs from its current position to complete this vertex reconnaissance. The initial flight path of UAVs is obtained when all the vertices are traversed. Step 5 uses function endpn to find the endpoint vl,n,end of the current pn, and step 6 uses function chosevl,n,end,Vl to find the next visit vertex vnext when UAV n completes the reconnaissance of vertex vl,n,end. Step 7 uses function addpn,vnext to add vnext to the end of pn. Then, vnext is removed from Vl in step 8. When Vl becomes an empty set, the loop is terminated, and PNl is updated.In the second part,pmax and max, respectively, represent the most time-consuming path in PNl and the UAV corresponding to this path. time_max represents the time of UAV max fly along pmax. We need to adjust each UAV’s path by iterating. In each iteration, we first judge the pmax of the current set PNl, and then the endpoint of pmax is transferred to the end of the other path in PNl. If the algorithm can find the UAV path in which time_max in PNl decreases after it receives the endpoint of pmax, the algorithm continues to adjust the path in set PNl in the next iteration. Otherwise, this adjustment operation is canceled, and the iteration is terminated. In detail, step 15 searches pmax and time_max in PNl by function maxtimePNl. Function tpn calculates the time of n fly along path pn. Steps 18-30 adjust pmax and update the PNl. Steps 31-34 determine whether the pmax has changed. If there is no change, the path adjustment operation cannot be performed, and the iteration is terminated.For example, we obtain three paths by running subalgorithm A2, represented asp1=1,4,5, p2=2,6,7, and p3=3,8,9, and the relationship of these path’s cost time is represented as tp1>tp2>tp3. In the second step, we first judge time_max=tp1 and pmax=p1. Then, the endpoint of p1 is judged as vertex 5. If tp2+w7,5<time_max, we remove vertex 5 from p1 to the end of p2. The adjusted paths are p1=1,4, p2=2,6,7,5, and p3=3,8,9. Then, the next iteration of adjustment is entered. If tp2+w7,5>time_max and tp3+w7,5>time_max, no path can receive the endpoint of p1; so, path adjustment can no longer be performed, and the current UAV path is output as the final result.


## 4.3. Planning Path in the Information Sharing Phase

UAVs’ flight paths in the information sharing phase can be translated into a series of visited sequences of information sharing points. The ferry UAV has multiple information sharing points in each batch, while the remaining UAVs have only one information sharing point. We obtain the path of the UAVs’ information sharing phase by subalgorithm A3. In thelth batch, A3’s inputs are Nl and PNl, and the outputs are Nl+1, exitl, and PNl. A3 includes two parts. The first part is to determine the ferry UAV of the current batch, and the main idea is to select the UAV that ends the reconnaissance phase earliest as the ferry UAV exitl. In the second part, UAV exitl searches other UAVs and corresponding information sharing points for sharing information based on the earliest encounter principle. The behavior of two UAVs heading to the information sharing point in this principle is regarded as making a relative motion from the departure point.The departure point is the position where the UAV changes from the current flight direction to the direction of the next information sharing point. The next UAV shared with the ferry UAV encountered the earliest with the ferry UAV when they made the relative motion. Their encounter position is regarded as their information sharing point.srn,l,i represents the ith information point of UAV n in the lth batch. Assuming n is the second UAV that shares information with exitl in l, their information sharing point srexitl,n is the first information sharing point of n and the second information sharing point of exitl. That is, srn,l,1=srexitl,l,2=srn,exitl. Ferry UAV exit has multiple departure points. When it searches the first information sharing point, its departure point is the reconnaissance phase’s endpoint in the current batch. When it searches the ith information sharing point, its departure point is the previous information sharing point srexitl,l,i−1. Other UAVs have one departure point at which the reconnaissance phase endpoint is in the current batch.When running subalgorithm 3 in thelth cycle of BITPP, steps 1-7 find the UAV with the fastest ending reconnaissance phase in batch l as the ferry UAV exitl. Step 8 removes exitl from set Nl and obtain sets Npro and Nl+1, where Npro represents the UAV set that currently needs to share information with exitl. Step 9 determines the number of UAVs that need to share information with exitl. Step 11 establishes tpro to record the current fastest encounter time between exitl and other UAVs. Steps 12-20 find the UAV in set Npro that encounters exitl the earliest and use next to represent the UAV that can make the earliest encounter exitl in the current iteration. In step 13, function meet_time calculates the relative motion time between exitl and n, taking their current path end positions as the departure point.Algorithm 4: A3.
Input:Nl, PNlOutput:Nl+1,exitl,PNl1tpro=∞;2for each n∈Nldo3iftpntprothen4exitl=n;5tpro=tpn;6end7end8Nl+1=Npro=removeNl,exitl;9number=Npro10fori=1 to numberdo11tpro=∞12for each n∈Nprodo13meet_texitl,n=meet_timeexitl,n,pn,pexitl;14ifmeet_texitl,ntprothen15next=n16tpro=meet_texitl,n;17srexitl,l,i=meet_pointexitl,n,pn,pexitl;18srnext,l,1=srexitl,l,i;19end20end21pexitl=addpexitl,srexitl,l,i;22pnext=addpnext,srnext,l,1;23updatePNl;24removeNpro,next;25endIn addition, because the time when UAVs arrive at their respective departure point is different, it is necessary to calculate the time interval betweenexitl and n arriving at their respective departure point. This time interval is expressed by Δtexitl,n,i, and the formula is as follows:
(17)Δtexitl,n=tpn−tpexitl.meet_texitl,n represents the encounter time between exitl and n, and the formula is as follows:
(18)meet_texitl,n=dendpexitl,endpn−Δtexitl,i,n·v/2v,wheredendpexitl,endpn represents the distance between the endpoints of paths pexitl and pn. In step 17, the function meet_pointexitl,n,pn,pexitl calculates the encounter coordinates of exitl and n. Steps 21-22 add this encounter point to the end of the paths pexitl and pnext. In addition, it is used as the information sharing point of exitl and next. Step 23 updates PNl. Step 24 removes next from the set Npro and then enters the next cycle.An example of UAVs searching for information sharing points is shown in Figure2. There are four UAVs in the picture. Assuming UAV 1 ends the reconnaissance phase earliest, it is regarded as the ferry UAV of the current batch. In subfigure 2.1, the time for UAV 1 to reach the departure point is t1, and the time for UAVs 2, 3, and 4 to reach their respective departure points is t2, t3, and t4. The encounter time of UAV 1 with UAVs 2, 3, and 4 in relative motion is t1,2, t1,3, and t1,4, respectively. Assuming that t1,2<t1,3<t1,4, UAV 1 encounters UAV 2 at the earliest. The encounter position s1 between them is regarded as the first information sharing point of UAV 1 and UAV 2. In subfigure 2.2, UAV 1 arrives at the position of s1 and uses it as the departure point to calculate the time of encounter with UAVs 3 and 4. Assuming UAV 1 has the fastest encounter with UAV 3, UAV 3 is thus the next UAV that shares information with it. Their encounter point s2 is the first information sharing point of UAV 3 and the second of UAV 1. Then, UAV 1 arrives at s2 in subfigure 2.3 and uses it as the departure points to calculate the time of encounter with UAV 4. Their encounter point is the first information sharing point of UAV 4 and the third of UAV 1. In subfigure 2.4, UAV 1 arrives at s3, and the flight path of each UAV in the information sharing phase is determined.Figure 2
Schematic of the information sharing phase.


## 4.4. Complexity Analysis

In the BITPP algorithm, subalgorithm A1 is run once in total, and subalgorithms A2 and A3 are run L times. A1 iterates through each user in setM at most twice. Thus, its complexity is OM. A2 includes initial path planning and path adjustment. The complexity of these two parts is related to the number of targets in Kl. After A2 is run L times, its complexity is OK. The complexity of A3 is related to the number of UAVs in Nl. It includes two parts: finding the ferry UAV and the planning path of the information sharing phase. When determining the ferry UAV, it needs to traverse the Nl set once, and its complexity is not higher than ON. Thus, the complexity that runs this part L times is OLN. When planning the information sharing path, it is necessary to traverse the number of UAVs in set Nl minus one squared at most. Thus, the complexity of running the second part L times is OLN−12. In conclusion, the complexity of the BITPP algorithm is OM+K+LN2−N+1.


## 5. Simulation Results and Analysis

### 5.1. Simulation Setup

In this section, we discuss the performance and applicability of the BITPP algorithm by analyzing the simulation results. Assume that the UAV, user, and reconnaissance targets are in a square area with a side length of 3 km, the default parameters for the number of UAVs and users are 6, the number of batches is 6, and the two-dimensional coordinates of the UAV take-off position are (0, 0). The user’s priority value is uniformly distributed in the value range of 10 to 100. That is, the priority value of users 1-6 is 100, 82, 64, 46, 28, and 10 in turn. Users are randomly distributed within 300 meters from the starting point of the drone. That is, the vertical and horizontal coordinates of users are randomly generated within 0-0.3 km. By default, each user is interested in 10 targets, and there is no duplication of user needs. In addition, this paper considers the situation in which the reconnaissance area is far from the user. Therefore, it is assumed that the reconnaissance target’s vertical and horizontal coordinates are randomly generated in the range of 1 km to 3 km. The specific parameters of the satisfaction model and path planning are shown in Table1.Table 1
Simulation parameters.
DescriptionSymbolValueExpected time for information acquisitionTexpect200 sMaximum tolerance time for information acquisitionTdeadline1000sInitial satisfactionγ100Single target reconnaissance timeTtarget5 sUAV maximum flight timeTmax40 minUAV flight speedv20 m/sTo prove the proposed multiuser satisfaction model’s ability to reflect the user’s information acquisition time and verify the performance of the proposed batchwise information backhaul strategy and the BITPP algorithm, we compare with the following four algorithms.GRMRT: UAVs make multiple trips between the user and the reconnaissance area. On each trip, UAVs cooperate to reconnoiter the targets of one user interested and then all fly to the user area to transmit reconnaissance information. UAVs’ flight path is planned based on the greedy algorithm.GAMRT: UAVs make multiple trips between the user and the reconnaissance area. On each trip, UAVs cooperate to reconnoiter the targets of one user interested and then all fly to the user area to transmit reconnaissance information. UAVs’ flight path is planned based on the genetic algorithm.GRORT: UAVs make one trip between the user and the reconnaissance area. On this trip, UAVs cooperate to reconnoiter the targets of all users interested and then all fly to the user area to transmit reconnaissance information. UAVs’ flight path is planned based on the greedy algorithm.GAORT: UAVs make one trip between the user and the reconnaissance area. On this trip, UAVs cooperate to reconnoiter the targets of all users interested and then all fly to the user area to transmit reconnaissance information. UAVs’ flight path is planned based on the genetic algorithm.


### 5.2. Simulation Analysis

#### 5.2.1. UAV Trajectory in Different Batch

We reduce the number of UAVs and users to 3 for a clearer view of the UAV trajectory. Then, we show the UAV trajectory in batches 1 and 2. The green circle represents the information sharing point, the blue circle represents the user, the yellow circle represents the target point, the hollow circle represents the state where it has not been accessed by the drone, and the solid circle represents the state where it has been accessed by the drone. As shown in Figure3, UAV 2 is selected as the ferry UAV in the first batch. After finishing the reconnaissance for assigned targets, it shares information with UAVs 1 and 3 in turn and finally reaches the corresponding user. As shown in Figure 4, UAV2 does not involve the reconnaissance activity in the second batch. UAV 1 is selected as the ferry UAV in the second batch and shares information with UAV 3. UAV 3 will come in the third batch and reconnoiter the remaining targets not visited.Figure 3
UAV trajectory in the first batch.Figure 4
UAV trajectory in the second batch.


#### 5.2.2. Information Acquisition Time of Different Users

According to the default parameter settings for simulation, Figures5–7 are obtained. Figure 3 shows the comparison of the BITPP algorithm with GAMRT and GRMRT, and Figure 6 shows the comparison of the BITPP algorithm with GAORT and GRORT. Both figures reflect the information acquisition time of each user under different algorithms. Figure 7 reflects each user’s satisfaction under the different algorithms. The X-axis of these three figures represents the user series number sorted in descending order of priority. In Figures 5 and 6, the corresponding user information acquisition time increases with the user series number. In Figure 7, the corresponding user satisfaction decreases with increasing user series number. All five algorithms determine the order that transmits information to the user according to the priority level, and thus higher priority users obtain information earlier than lower priority users.Figure 5
Information acquisition time of different users.Figure 6
Information acquisition time of different users.Figure 7
Satisfaction of different users.In Figure5, the difference in each user’s information acquisition under BITPP is the smallest compared with the GAMRT and GRMRT algorithms. In addition, only the user with serial number 1 acquires information under the BITPP algorithm in a slightly higher time than the results using the other two algorithms. The rest of the users’ information acquisition time is lower than the results using the comparison algorithm. This is because all UAVs fly to the user area for information distribution after finishing reconnaissance for targets of one user interested under the GAMRT and GRMRT algorithms. Thus, the distance traveled by UAVs between the target area and the user area dramatically extends the time for the following users to obtain information. When the target is farther away from the user, the difference in information acquisition time between higher and lower priority users is more significant. This is likewise why lower priority user satisfaction decreases severely when the GAMRT and GRMRT algorithms are used, as shown in Figure 7. In contrast, only the ferry UAV in each batch transmits information to the user under the BITPP algorithm. When the ferry UAV flies to the user area, other UAVs can continue to reconnoiter the targets of the next user interested, and the next user does not need to wait according to the amount of time that UAVs travel between the user and the target area. Therefore, in Figures 5 and 7, the differences in information acquisition time and satisfaction between different users using the BITPP algorithm are minor compared to the GAMRT and GRMRT algorithms.As seen in Figure6, the difference in information acquisition time between different users under the GAORT and GRORT algorithms is slight. This reason is that both algorithms require UAVs traveling to the user area after reconnoitering the targets of interest to all users. However, it also causes the higher priority users’ information acquisition under the two algorithms to be much longer than using the BITPP algorithm. In contrast, the BITPP algorithm can make UAVs provide information to higher priority users in advance, thus ensuring that most higher priority users can obtain information faster. In addition, as seen in Figures 6 and 7, user 6 obtains information under the BITPP algorithm later than using the GAORT algorithm, and the satisfaction is also lower. In the BITPP algorithm, UAVs in each batch need to spend a small amount of time in the information sharing phase. As the batches increase, this time will continue to accumulate, and the information acquisition time for low priority users will be extended accordingly. However, compared with the GAORT and GRORT algorithms, the BITPP algorithm still ensures a lower information acquisition time for most users. Although the use of the BITPP algorithm leads to a higher information acquisition time for user 6 than the GAORT algorithm, this difference is very small. In summary, the BITPP algorithm can guarantee the higher priority users to obtain the information quickly while minimizing the time for the lower priority users to obtain the information.


#### 5.2.3. Different Number of Users

Keeping UAV numbers and other parameters unchanged, we measure the variation in multiuser satisfaction when the user number increases. As seen in Figure8, the multiuser satisfaction under each algorithm decreases as the number of users to be served increases. The fundamental reason is that UAVs need to reconnoiter more targets, and the total time that UAVs complete all user reconnaissance tasks is also increased. In addition, multiuser satisfaction showed different decreasing trends under different algorithms. Among the five algorithms, the decreasing trend of multiuser satisfaction under the BITPP algorithm was the slowest, while the satisfaction of the remaining four algorithms decreased faster. In GAORT and GRORT algorithms, UAVs need to reconnoiter all targets at one time before providing information for users. As the number of users increases and the targets for one-time reconnaissance increase, users’ time to obtain information increases together. In the GAMRT and GRMRT algorithms, UAVs prioritize reconnoitering targets of high priority users of interest. Thus, the information acquisition time for higher priority users is not affected as the number of users increases. However, the acquisition time for users with lower priority rankings is severely delayed. The BITPP algorithm ensures that the UAV priority reconnoiters the targets of interest to high priority users. It also dramatically reduces the impact on low priority users’ information acquisition time by avoiding the round trip time between the user area and the target area of the UAV. The above analysis shows that the BITPP algorithm can better cope with situations where the number of users is large or the number of UAVs is small.Figure 8
Multiuser satisfaction varies with the number of users.


#### 5.2.4. Different Numbers of the Total Batch

Assume that each user needs 25 goals, and that user needs are not repeated. Setting the total number of batches from 1 to 6, Figures9 and 10 are obtained by simulation. Figure 9 reflects the variation in multiuser satisfaction under different batch number settings in the BITPP algorithm, and Figure 10 reflects the change in each user’s information acquisition time. As shown in Figure 10, each user’s information acquisition time is close when the number of batches is 1. After setting the batch number to 2, UAVs serve users 1 and 2 in the first batch and 3-6 in the second batch. The information acquisition time of users 1 and 2 decreases substantially, while the remaining users’ information acquisition time increases slightly. At the time, multiuser satisfaction increases significantly in Figure 9 when the number of batches changes from 1 to 2. It shows that the multiuser satisfaction model is strongly influenced by the variation of the higher priority user’s information acquisition time.Figure 9
The variation of multiuser satisfaction with the number of batches.Figure 10
The variation of user information acquisition time with the number of batches.When the number of batches is set to 3, UAVs serve only user 1 in batch 1, users 2 and 3 in batch 2, and users 4-6 in batch 3. Therefore, the information acquisition time of users 1 and 3 is further reduced. The information acquisition time of user 2 increases but is still smaller than the information acquisition time when the batch number is set to 1. In addition, the multiuser satisfaction still increases when setting the batch number from 2 to 3 in Figure9, but the increase is smaller than the increase in the batch number from 1 to 2. These results show that the user satisfaction model takes the information acquisition time of high priority users as the main reference while taking into account the information acquisition time of lower priority users. As seen in Figure 9, the trend of multiuser satisfaction growth is faster and then slower as the number of batches increases. On the one hand, it reflects that when each user’s priority value is characterized by a uniform distribution, the multiuser satisfaction increases with the number of batch sets. On the other hand, the users whose information acquisition time is affected due to the increased number of batches are minority users, and most of them are lower priority users.


#### 5.2.5. Different User Priority Distributions

The difference between the user priority values plays an important role in considering UAV planning; thus, we set four different priority value distribution types. As shown in Table2, users’ priority values range from 10 to 100. In type 1, each user has the same priority value. The users’ priority values in type 2 are uniformly distributed, and the difference between adjacent users’ priority values is equal. In type 3, the difference between adjacent users’ priority values with the serial number from small to large is a descending arithmetic sequence with a tolerance of 6. In contrast to type 3, the difference between adjacent users’ priority values in type 4 from small to large is an increasing arithmetic sequence with a tolerance of 6. The first type represents the same importance of each user and the same urgency to obtain information, and UAVs do not need to pay more attention to any user than the others when providing service. The remaining three distribution types represent situations where the urgency of user needs varies. The second type represents a uniform distribution of urgency for each user to obtain information, the third type represents a scenario where a few users have high urgency to obtain information and most users have low urgency, and the fourth type represents a scenario where most users have high urgency to obtain information and a few users have low urgency to obtain information. Of these, the reconnaissance service environment for UAVs in type 3 is more relaxed because the urgency of the information needs of most users is concentrated toward the high value, and the reconnaissance service environment for UAVs in type 4 is more urgent because the urgency of most users is concentrated toward the high value.Table 2
User priority value distribution.
ValueUserUser 1User 2User 3User 4User 5User 6TypeType 1505050505050Type 2907560453015Type 31007046281610Type 41009482644010Figure11 shows the multiuser satisfaction results of different algorithms under the four types. The BITPP, GRMRT, and GAMRT algorithms all have the highest satisfaction level when dealing with type 3 and the lowest satisfaction level when dealing with type 2. The main reason is that these three algorithms can prioritize some users’ needs; so, they are more suitable for situations where there are differences in users’ priorities and situations where some users have very high priorities. The results show that the multiuser satisfaction under the GRORT and GAORT algorithms does not vary significantly with the change in priority distribution type. This is because the two algorithms require UAVs to reconnoiter targets needed by all users at one time. Thus, the change in user priority value has little effect on each user’s information acquisition time. The GRORT and GAORT algorithms are more suitable for situations where users have the same priority. BITPP combines the four algorithms’ advantages and can achieve higher multiuser satisfaction than the other four algorithms for different user priority distribution types. The algorithm works better in situations in which a few users have a very high priority value.Figure 11
Multiuser satisfaction under different user priority distributions.


## 5.1. Simulation Setup

In this section, we discuss the performance and applicability of the BITPP algorithm by analyzing the simulation results. Assume that the UAV, user, and reconnaissance targets are in a square area with a side length of 3 km, the default parameters for the number of UAVs and users are 6, the number of batches is 6, and the two-dimensional coordinates of the UAV take-off position are (0, 0). The user’s priority value is uniformly distributed in the value range of 10 to 100. That is, the priority value of users 1-6 is 100, 82, 64, 46, 28, and 10 in turn. Users are randomly distributed within 300 meters from the starting point of the drone. That is, the vertical and horizontal coordinates of users are randomly generated within 0-0.3 km. By default, each user is interested in 10 targets, and there is no duplication of user needs. In addition, this paper considers the situation in which the reconnaissance area is far from the user. Therefore, it is assumed that the reconnaissance target’s vertical and horizontal coordinates are randomly generated in the range of 1 km to 3 km. The specific parameters of the satisfaction model and path planning are shown in Table1.Table 1
Simulation parameters.
DescriptionSymbolValueExpected time for information acquisitionTexpect200 sMaximum tolerance time for information acquisitionTdeadline1000sInitial satisfactionγ100Single target reconnaissance timeTtarget5 sUAV maximum flight timeTmax40 minUAV flight speedv20 m/sTo prove the proposed multiuser satisfaction model’s ability to reflect the user’s information acquisition time and verify the performance of the proposed batchwise information backhaul strategy and the BITPP algorithm, we compare with the following four algorithms.GRMRT: UAVs make multiple trips between the user and the reconnaissance area. On each trip, UAVs cooperate to reconnoiter the targets of one user interested and then all fly to the user area to transmit reconnaissance information. UAVs’ flight path is planned based on the greedy algorithm.GAMRT: UAVs make multiple trips between the user and the reconnaissance area. On each trip, UAVs cooperate to reconnoiter the targets of one user interested and then all fly to the user area to transmit reconnaissance information. UAVs’ flight path is planned based on the genetic algorithm.GRORT: UAVs make one trip between the user and the reconnaissance area. On this trip, UAVs cooperate to reconnoiter the targets of all users interested and then all fly to the user area to transmit reconnaissance information. UAVs’ flight path is planned based on the greedy algorithm.GAORT: UAVs make one trip between the user and the reconnaissance area. On this trip, UAVs cooperate to reconnoiter the targets of all users interested and then all fly to the user area to transmit reconnaissance information. UAVs’ flight path is planned based on the genetic algorithm.


## 5.2. Simulation Analysis

### 5.2.1. UAV Trajectory in Different Batch

We reduce the number of UAVs and users to 3 for a clearer view of the UAV trajectory. Then, we show the UAV trajectory in batches 1 and 2. The green circle represents the information sharing point, the blue circle represents the user, the yellow circle represents the target point, the hollow circle represents the state where it has not been accessed by the drone, and the solid circle represents the state where it has been accessed by the drone. As shown in Figure3, UAV 2 is selected as the ferry UAV in the first batch. After finishing the reconnaissance for assigned targets, it shares information with UAVs 1 and 3 in turn and finally reaches the corresponding user. As shown in Figure 4, UAV2 does not involve the reconnaissance activity in the second batch. UAV 1 is selected as the ferry UAV in the second batch and shares information with UAV 3. UAV 3 will come in the third batch and reconnoiter the remaining targets not visited.Figure 3
UAV trajectory in the first batch.Figure 4
UAV trajectory in the second batch.


### 5.2.2. Information Acquisition Time of Different Users

According to the default parameter settings for simulation, Figures5–7 are obtained. Figure 3 shows the comparison of the BITPP algorithm with GAMRT and GRMRT, and Figure 6 shows the comparison of the BITPP algorithm with GAORT and GRORT. Both figures reflect the information acquisition time of each user under different algorithms. Figure 7 reflects each user’s satisfaction under the different algorithms. The X-axis of these three figures represents the user series number sorted in descending order of priority. In Figures 5 and 6, the corresponding user information acquisition time increases with the user series number. In Figure 7, the corresponding user satisfaction decreases with increasing user series number. All five algorithms determine the order that transmits information to the user according to the priority level, and thus higher priority users obtain information earlier than lower priority users.Figure 5
Information acquisition time of different users.Figure 6
Information acquisition time of different users.Figure 7
Satisfaction of different users.In Figure5, the difference in each user’s information acquisition under BITPP is the smallest compared with the GAMRT and GRMRT algorithms. In addition, only the user with serial number 1 acquires information under the BITPP algorithm in a slightly higher time than the results using the other two algorithms. The rest of the users’ information acquisition time is lower than the results using the comparison algorithm. This is because all UAVs fly to the user area for information distribution after finishing reconnaissance for targets of one user interested under the GAMRT and GRMRT algorithms. Thus, the distance traveled by UAVs between the target area and the user area dramatically extends the time for the following users to obtain information. When the target is farther away from the user, the difference in information acquisition time between higher and lower priority users is more significant. This is likewise why lower priority user satisfaction decreases severely when the GAMRT and GRMRT algorithms are used, as shown in Figure 7. In contrast, only the ferry UAV in each batch transmits information to the user under the BITPP algorithm. When the ferry UAV flies to the user area, other UAVs can continue to reconnoiter the targets of the next user interested, and the next user does not need to wait according to the amount of time that UAVs travel between the user and the target area. Therefore, in Figures 5 and 7, the differences in information acquisition time and satisfaction between different users using the BITPP algorithm are minor compared to the GAMRT and GRMRT algorithms.As seen in Figure6, the difference in information acquisition time between different users under the GAORT and GRORT algorithms is slight. This reason is that both algorithms require UAVs traveling to the user area after reconnoitering the targets of interest to all users. However, it also causes the higher priority users’ information acquisition under the two algorithms to be much longer than using the BITPP algorithm. In contrast, the BITPP algorithm can make UAVs provide information to higher priority users in advance, thus ensuring that most higher priority users can obtain information faster. In addition, as seen in Figures 6 and 7, user 6 obtains information under the BITPP algorithm later than using the GAORT algorithm, and the satisfaction is also lower. In the BITPP algorithm, UAVs in each batch need to spend a small amount of time in the information sharing phase. As the batches increase, this time will continue to accumulate, and the information acquisition time for low priority users will be extended accordingly. However, compared with the GAORT and GRORT algorithms, the BITPP algorithm still ensures a lower information acquisition time for most users. Although the use of the BITPP algorithm leads to a higher information acquisition time for user 6 than the GAORT algorithm, this difference is very small. In summary, the BITPP algorithm can guarantee the higher priority users to obtain the information quickly while minimizing the time for the lower priority users to obtain the information.


### 5.2.3. Different Number of Users

Keeping UAV numbers and other parameters unchanged, we measure the variation in multiuser satisfaction when the user number increases. As seen in Figure8, the multiuser satisfaction under each algorithm decreases as the number of users to be served increases. The fundamental reason is that UAVs need to reconnoiter more targets, and the total time that UAVs complete all user reconnaissance tasks is also increased. In addition, multiuser satisfaction showed different decreasing trends under different algorithms. Among the five algorithms, the decreasing trend of multiuser satisfaction under the BITPP algorithm was the slowest, while the satisfaction of the remaining four algorithms decreased faster. In GAORT and GRORT algorithms, UAVs need to reconnoiter all targets at one time before providing information for users. As the number of users increases and the targets for one-time reconnaissance increase, users’ time to obtain information increases together. In the GAMRT and GRMRT algorithms, UAVs prioritize reconnoitering targets of high priority users of interest. Thus, the information acquisition time for higher priority users is not affected as the number of users increases. However, the acquisition time for users with lower priority rankings is severely delayed. The BITPP algorithm ensures that the UAV priority reconnoiters the targets of interest to high priority users. It also dramatically reduces the impact on low priority users’ information acquisition time by avoiding the round trip time between the user area and the target area of the UAV. The above analysis shows that the BITPP algorithm can better cope with situations where the number of users is large or the number of UAVs is small.Figure 8
Multiuser satisfaction varies with the number of users.


### 5.2.4. Different Numbers of the Total Batch

Assume that each user needs 25 goals, and that user needs are not repeated. Setting the total number of batches from 1 to 6, Figures9 and 10 are obtained by simulation. Figure 9 reflects the variation in multiuser satisfaction under different batch number settings in the BITPP algorithm, and Figure 10 reflects the change in each user’s information acquisition time. As shown in Figure 10, each user’s information acquisition time is close when the number of batches is 1. After setting the batch number to 2, UAVs serve users 1 and 2 in the first batch and 3-6 in the second batch. The information acquisition time of users 1 and 2 decreases substantially, while the remaining users’ information acquisition time increases slightly. At the time, multiuser satisfaction increases significantly in Figure 9 when the number of batches changes from 1 to 2. It shows that the multiuser satisfaction model is strongly influenced by the variation of the higher priority user’s information acquisition time.Figure 9
The variation of multiuser satisfaction with the number of batches.Figure 10
The variation of user information acquisition time with the number of batches.When the number of batches is set to 3, UAVs serve only user 1 in batch 1, users 2 and 3 in batch 2, and users 4-6 in batch 3. Therefore, the information acquisition time of users 1 and 3 is further reduced. The information acquisition time of user 2 increases but is still smaller than the information acquisition time when the batch number is set to 1. In addition, the multiuser satisfaction still increases when setting the batch number from 2 to 3 in Figure9, but the increase is smaller than the increase in the batch number from 1 to 2. These results show that the user satisfaction model takes the information acquisition time of high priority users as the main reference while taking into account the information acquisition time of lower priority users. As seen in Figure 9, the trend of multiuser satisfaction growth is faster and then slower as the number of batches increases. On the one hand, it reflects that when each user’s priority value is characterized by a uniform distribution, the multiuser satisfaction increases with the number of batch sets. On the other hand, the users whose information acquisition time is affected due to the increased number of batches are minority users, and most of them are lower priority users.


### 5.2.5. Different User Priority Distributions

The difference between the user priority values plays an important role in considering UAV planning; thus, we set four different priority value distribution types. As shown in Table2, users’ priority values range from 10 to 100. In type 1, each user has the same priority value. The users’ priority values in type 2 are uniformly distributed, and the difference between adjacent users’ priority values is equal. In type 3, the difference between adjacent users’ priority values with the serial number from small to large is a descending arithmetic sequence with a tolerance of 6. In contrast to type 3, the difference between adjacent users’ priority values in type 4 from small to large is an increasing arithmetic sequence with a tolerance of 6. The first type represents the same importance of each user and the same urgency to obtain information, and UAVs do not need to pay more attention to any user than the others when providing service. The remaining three distribution types represent situations where the urgency of user needs varies. The second type represents a uniform distribution of urgency for each user to obtain information, the third type represents a scenario where a few users have high urgency to obtain information and most users have low urgency, and the fourth type represents a scenario where most users have high urgency to obtain information and a few users have low urgency to obtain information. Of these, the reconnaissance service environment for UAVs in type 3 is more relaxed because the urgency of the information needs of most users is concentrated toward the high value, and the reconnaissance service environment for UAVs in type 4 is more urgent because the urgency of most users is concentrated toward the high value.Table 2
User priority value distribution.
ValueUserUser 1User 2User 3User 4User 5User 6TypeType 1505050505050Type 2907560453015Type 31007046281610Type 41009482644010Figure11 shows the multiuser satisfaction results of different algorithms under the four types. The BITPP, GRMRT, and GAMRT algorithms all have the highest satisfaction level when dealing with type 3 and the lowest satisfaction level when dealing with type 2. The main reason is that these three algorithms can prioritize some users’ needs; so, they are more suitable for situations where there are differences in users’ priorities and situations where some users have very high priorities. The results show that the multiuser satisfaction under the GRORT and GAORT algorithms does not vary significantly with the change in priority distribution type. This is because the two algorithms require UAVs to reconnoiter targets needed by all users at one time. Thus, the change in user priority value has little effect on each user’s information acquisition time. The GRORT and GAORT algorithms are more suitable for situations where users have the same priority. BITPP combines the four algorithms’ advantages and can achieve higher multiuser satisfaction than the other four algorithms for different user priority distribution types. The algorithm works better in situations in which a few users have a very high priority value.Figure 11
Multiuser satisfaction under different user priority distributions.


## 5.2.1. UAV Trajectory in Different Batch

We reduce the number of UAVs and users to 3 for a clearer view of the UAV trajectory. Then, we show the UAV trajectory in batches 1 and 2. The green circle represents the information sharing point, the blue circle represents the user, the yellow circle represents the target point, the hollow circle represents the state where it has not been accessed by the drone, and the solid circle represents the state where it has been accessed by the drone. As shown in Figure3, UAV 2 is selected as the ferry UAV in the first batch. After finishing the reconnaissance for assigned targets, it shares information with UAVs 1 and 3 in turn and finally reaches the corresponding user. As shown in Figure 4, UAV2 does not involve the reconnaissance activity in the second batch. UAV 1 is selected as the ferry UAV in the second batch and shares information with UAV 3. UAV 3 will come in the third batch and reconnoiter the remaining targets not visited.Figure 3
UAV trajectory in the first batch.Figure 4
UAV trajectory in the second batch.


## 5.2.2. Information Acquisition Time of Different Users

According to the default parameter settings for simulation, Figures5–7 are obtained. Figure 3 shows the comparison of the BITPP algorithm with GAMRT and GRMRT, and Figure 6 shows the comparison of the BITPP algorithm with GAORT and GRORT. Both figures reflect the information acquisition time of each user under different algorithms. Figure 7 reflects each user’s satisfaction under the different algorithms. The X-axis of these three figures represents the user series number sorted in descending order of priority. In Figures 5 and 6, the corresponding user information acquisition time increases with the user series number. In Figure 7, the corresponding user satisfaction decreases with increasing user series number. All five algorithms determine the order that transmits information to the user according to the priority level, and thus higher priority users obtain information earlier than lower priority users.Figure 5
Information acquisition time of different users.Figure 6
Information acquisition time of different users.Figure 7
Satisfaction of different users.In Figure5, the difference in each user’s information acquisition under BITPP is the smallest compared with the GAMRT and GRMRT algorithms. In addition, only the user with serial number 1 acquires information under the BITPP algorithm in a slightly higher time than the results using the other two algorithms. The rest of the users’ information acquisition time is lower than the results using the comparison algorithm. This is because all UAVs fly to the user area for information distribution after finishing reconnaissance for targets of one user interested under the GAMRT and GRMRT algorithms. Thus, the distance traveled by UAVs between the target area and the user area dramatically extends the time for the following users to obtain information. When the target is farther away from the user, the difference in information acquisition time between higher and lower priority users is more significant. This is likewise why lower priority user satisfaction decreases severely when the GAMRT and GRMRT algorithms are used, as shown in Figure 7. In contrast, only the ferry UAV in each batch transmits information to the user under the BITPP algorithm. When the ferry UAV flies to the user area, other UAVs can continue to reconnoiter the targets of the next user interested, and the next user does not need to wait according to the amount of time that UAVs travel between the user and the target area. Therefore, in Figures 5 and 7, the differences in information acquisition time and satisfaction between different users using the BITPP algorithm are minor compared to the GAMRT and GRMRT algorithms.As seen in Figure6, the difference in information acquisition time between different users under the GAORT and GRORT algorithms is slight. This reason is that both algorithms require UAVs traveling to the user area after reconnoitering the targets of interest to all users. However, it also causes the higher priority users’ information acquisition under the two algorithms to be much longer than using the BITPP algorithm. In contrast, the BITPP algorithm can make UAVs provide information to higher priority users in advance, thus ensuring that most higher priority users can obtain information faster. In addition, as seen in Figures 6 and 7, user 6 obtains information under the BITPP algorithm later than using the GAORT algorithm, and the satisfaction is also lower. In the BITPP algorithm, UAVs in each batch need to spend a small amount of time in the information sharing phase. As the batches increase, this time will continue to accumulate, and the information acquisition time for low priority users will be extended accordingly. However, compared with the GAORT and GRORT algorithms, the BITPP algorithm still ensures a lower information acquisition time for most users. Although the use of the BITPP algorithm leads to a higher information acquisition time for user 6 than the GAORT algorithm, this difference is very small. In summary, the BITPP algorithm can guarantee the higher priority users to obtain the information quickly while minimizing the time for the lower priority users to obtain the information.


## 5.2.3. Different Number of Users

Keeping UAV numbers and other parameters unchanged, we measure the variation in multiuser satisfaction when the user number increases. As seen in Figure8, the multiuser satisfaction under each algorithm decreases as the number of users to be served increases. The fundamental reason is that UAVs need to reconnoiter more targets, and the total time that UAVs complete all user reconnaissance tasks is also increased. In addition, multiuser satisfaction showed different decreasing trends under different algorithms. Among the five algorithms, the decreasing trend of multiuser satisfaction under the BITPP algorithm was the slowest, while the satisfaction of the remaining four algorithms decreased faster. In GAORT and GRORT algorithms, UAVs need to reconnoiter all targets at one time before providing information for users. As the number of users increases and the targets for one-time reconnaissance increase, users’ time to obtain information increases together. In the GAMRT and GRMRT algorithms, UAVs prioritize reconnoitering targets of high priority users of interest. Thus, the information acquisition time for higher priority users is not affected as the number of users increases. However, the acquisition time for users with lower priority rankings is severely delayed. The BITPP algorithm ensures that the UAV priority reconnoiters the targets of interest to high priority users. It also dramatically reduces the impact on low priority users’ information acquisition time by avoiding the round trip time between the user area and the target area of the UAV. The above analysis shows that the BITPP algorithm can better cope with situations where the number of users is large or the number of UAVs is small.Figure 8
Multiuser satisfaction varies with the number of users.


## 5.2.4. Different Numbers of the Total Batch

Assume that each user needs 25 goals, and that user needs are not repeated. Setting the total number of batches from 1 to 6, Figures9 and 10 are obtained by simulation. Figure 9 reflects the variation in multiuser satisfaction under different batch number settings in the BITPP algorithm, and Figure 10 reflects the change in each user’s information acquisition time. As shown in Figure 10, each user’s information acquisition time is close when the number of batches is 1. After setting the batch number to 2, UAVs serve users 1 and 2 in the first batch and 3-6 in the second batch. The information acquisition time of users 1 and 2 decreases substantially, while the remaining users’ information acquisition time increases slightly. At the time, multiuser satisfaction increases significantly in Figure 9 when the number of batches changes from 1 to 2. It shows that the multiuser satisfaction model is strongly influenced by the variation of the higher priority user’s information acquisition time.Figure 9
The variation of multiuser satisfaction with the number of batches.Figure 10
The variation of user information acquisition time with the number of batches.When the number of batches is set to 3, UAVs serve only user 1 in batch 1, users 2 and 3 in batch 2, and users 4-6 in batch 3. Therefore, the information acquisition time of users 1 and 3 is further reduced. The information acquisition time of user 2 increases but is still smaller than the information acquisition time when the batch number is set to 1. In addition, the multiuser satisfaction still increases when setting the batch number from 2 to 3 in Figure9, but the increase is smaller than the increase in the batch number from 1 to 2. These results show that the user satisfaction model takes the information acquisition time of high priority users as the main reference while taking into account the information acquisition time of lower priority users. As seen in Figure 9, the trend of multiuser satisfaction growth is faster and then slower as the number of batches increases. On the one hand, it reflects that when each user’s priority value is characterized by a uniform distribution, the multiuser satisfaction increases with the number of batch sets. On the other hand, the users whose information acquisition time is affected due to the increased number of batches are minority users, and most of them are lower priority users.


## 5.2.5. Different User Priority Distributions

The difference between the user priority values plays an important role in considering UAV planning; thus, we set four different priority value distribution types. As shown in Table2, users’ priority values range from 10 to 100. In type 1, each user has the same priority value. The users’ priority values in type 2 are uniformly distributed, and the difference between adjacent users’ priority values is equal. In type 3, the difference between adjacent users’ priority values with the serial number from small to large is a descending arithmetic sequence with a tolerance of 6. In contrast to type 3, the difference between adjacent users’ priority values in type 4 from small to large is an increasing arithmetic sequence with a tolerance of 6. The first type represents the same importance of each user and the same urgency to obtain information, and UAVs do not need to pay more attention to any user than the others when providing service. The remaining three distribution types represent situations where the urgency of user needs varies. The second type represents a uniform distribution of urgency for each user to obtain information, the third type represents a scenario where a few users have high urgency to obtain information and most users have low urgency, and the fourth type represents a scenario where most users have high urgency to obtain information and a few users have low urgency to obtain information. Of these, the reconnaissance service environment for UAVs in type 3 is more relaxed because the urgency of the information needs of most users is concentrated toward the high value, and the reconnaissance service environment for UAVs in type 4 is more urgent because the urgency of most users is concentrated toward the high value.Table 2
User priority value distribution.
ValueUserUser 1User 2User 3User 4User 5User 6TypeType 1505050505050Type 2907560453015Type 31007046281610Type 41009482644010Figure11 shows the multiuser satisfaction results of different algorithms under the four types. The BITPP, GRMRT, and GAMRT algorithms all have the highest satisfaction level when dealing with type 3 and the lowest satisfaction level when dealing with type 2. The main reason is that these three algorithms can prioritize some users’ needs; so, they are more suitable for situations where there are differences in users’ priorities and situations where some users have very high priorities. The results show that the multiuser satisfaction under the GRORT and GAORT algorithms does not vary significantly with the change in priority distribution type. This is because the two algorithms require UAVs to reconnoiter targets needed by all users at one time. Thus, the change in user priority value has little effect on each user’s information acquisition time. The GRORT and GAORT algorithms are more suitable for situations where users have the same priority. BITPP combines the four algorithms’ advantages and can achieve higher multiuser satisfaction than the other four algorithms for different user priority distribution types. The algorithm works better in situations in which a few users have a very high priority value.Figure 11
Multiuser satisfaction under different user priority distributions.


## 6. Conclusions

This paper studies a multi-UAV cooperative reconnaissance scenario where multiple users with different priorities need to be served. A multiuser satisfaction model based on users’ diverse priorities and a batchwise information backhaul strategy are proposed. This reconnaissance process is formulated as a cooperative path planning problem, and the path planning algorithm BITPP is proposed to maximize multiuser satisfaction. The simulation results show that the BITPP algorithm can make higher priority users obtain information faster than using one round trip reconnaissance strategy. In addition, compared to other multiple round trip strategies, the BITPP algorithm can make lower priority users obtain information with less delay while ensuring higher priority users’ faster information acquisition. In addition, the applicability of the BITPP algorithm is simulated and analyzed in several different scenarios. Simulation results show that it can still produce good results with increased users, and it is more effective in situations where a small number of users exists with very high priority values. In future studies, we will focus on cases where multiple UAVs are selected as ferries in each batch while exploring a more complex and effective UAV collaboration mechanism to cope with a dynamic environment and task flow.



---

*Source: 9504056-2021-10-11.xml*