# On-Demanding Information Acquisition in Multi-UAV-Assisted Sensor Network: A Satisfaction-Driven Perspective

Authors: Hua Yang; Jungang Yang; Wendong Zhao; Cuntao Liu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

When multiple heterogeneous unmanned aerial vehicles (UAVs) provide service for multiple users in sensor networks, users’ diverse priorities and corresponding priority-related satisfaction are rarely concerned in traditional task assignment algorithms. A priority-driven user satisfaction model is proposed, in which a piecewise function considering soft time window and users’ different priority levels is designed to describe the relationship between user priority and user satisfaction. On this basis, the multi-UAV task assignment problem is formulated as a combinatorial optimization problem with multiple constraints, where the objective is maximizing the priority-weighted satisfaction of users while minimizing the total energy consumption of UAVs. A multipopulation-based cooperation genetic algorithm (MPCGA) by adapting the idea of “exploration-exploitation” into traditional genetic algorithms (GAs) is proposed, which can solve the task assignment problem in polynomial time. Simulation results show that compared with the algorithm without considering users’ priority-based satisfaction, users’ weighted satisfaction can be improved by about 47% based on our algorithm in situations where users’ information acquisition is tight time-window constraints. In comparison, UAVs’ energy consumption only increased by about 6%. Besides, compared with traditional GA, our proposed algorithm can also improve users’ weighted satisfaction by about 5% with almost the same energy consumption of UAVs.


---

## Body

## 1. Introduction

Nowadays, unmanned aerial vehicles (UAVs) are gaining increasing popularity in various fields [1], such as situation awareness, intelligence reconnaissance, data collection, and relaying. Compared with traditional data collection means, UAVs possess significant advantages such as stronger mobility and flexibility, the ability to realize high-speed data transmission, and no risk of casualties, which makes them more suitable for data collection and transmission within sensor networks in complex environments [2, 3]. As the task execution capability of a single UAV is restricted by its limited flying capacity, battery capacity, reconnaissance capability, etc., it is imperative to use multiple UAVs to carry out cooperative data collection tasks. During this process, efficient task allocation [4–7] is one of the critical factors to improve the task execution efficiency of multiple UAVs effectively. Besides, since task allocation problems and path planning problems in UAV-based data collection are highly coupled, they are usually considered together in practice.Generally, a data collection task can be abstracted as a process of visiting multiple ground sensors (GSs). When considering multi-UAV-based data collection, a group of GSs and corresponding visiting sequence should be assigned to each UAV through a reasonable task assignment strategy. UAVs need to visit their assigned GSs in sequence, collecting data from the GSs and send it back, directly or indirectly, to users who need it. As a typical COP with multiple constraints, the multi-UAV-based data collection task assignment problem is NP-hard [8] and usually cannot be solved directly to get the optimal solution. Till now, a large amount of studies have focused on this problem and several customized COP method-based problem-solving models, such as cooperative multiple task assignment problem (CMTAP) model, multiple vehicle routing problem (MVRP) model, multiple traveling salesman problem (MTSP) model, and mixed-integer linear programming (MILP) model, have been proposed [9–12]. While several kinds of problem-solving methods, such as dynamic programming [13], stochastic and deterministic optimization approaches (cross-entropy method and branch and bound algorithm) [14, 15], heuristic [16, 17], swarm intelligence [18–20], reinforcement learning [21, 22], and game theory [23, 24], have been widely used in realizing an effective task assignment.Since UAV’s onboard battery capacity, flight ability, and payload capacity are limited, related constraints such as energy consumption, flight speed, and amount of data that need to be collected are usually considered during the process of task assignment and path planning. Correspondingly, various optimization objectives in solving task assignment and path planning problems have been constructed from different perspectives. For example, studies [25–28] devoted to studying the minimization problem of the total energy consumption of UAVs participating in the reconnaissance tasks. The authors of [29] studied the fairness problem of UAVs’ energy consumption. The authors of [30, 31] focused on the minimization problem of task completion time. While in these studies, problems of users’ diverse priority-related satisfaction towards the execution effect of tasks are rarely considered.However, in these studies, the influence of users’ satisfaction toward the information obtained is rarely taken into account. In practical, as the purposes of users’ acquiring information are different, the information from the same GS may also have different value/importance from users’ point of view. Correspondingly, even if users receive the information they need at the same time, different users are likely to have different levels of satisfaction. For example, suppose both usersu1 and u2 want to acquire information about target a. For u1, the information about a is vital, and the earlier the information is obtained, the higher the satisfaction of u1 will be. While for u2, the information about a is not important, and as long as the information can be obtained before a deadline, the satisfaction of u2 will be basically the same. In this situation, taking users’ satisfaction into account is meaningful, as data collection services are supposed to be user-centric.Generally, user satisfaction (US) is usually embodied in the process of users enjoying products/services [32], which is ubiquitous in nature and society. Kotler defines it as a psychological feeling derived from the comparison of the actual product/service experienced by users and their expectation [33], while Cardozo extends user satisfaction to the field of marketing, believing that it will influence customers’ subsequent purchase behavior [34]. At present, there is no consensus on the understanding of user satisfaction degree in academia, and the main ideas can be divided into three categories: (1) users’ expectation determines user satisfaction; (2) the quality of users’ experience dominates user satisfaction; (3) the degree to which users’ subjective expectation is consistent with their experience should be used to describe user satisfaction. In this paper, we adopt the idea of describing user satisfaction degree as the distance between users’ experience and psychological expectation of service quality, which can better reflect the connotation of user satisfaction in our opinions.Currently, the above ideas of describing user satisfaction have been adopted in wireless communication [35], network management [36] as well as in multi-UAV task assignment [37–39]. As described in [32], user satisfaction (US) is an abstract concept and may be measured differently in different scenarios. When considering user satisfaction degree in the above studies, a satisfaction function related to information transmission rate, information acquisition time, or energy efficiency was defined based on their different optimization objectives. For example, the authors focused on a competitive environment, where different users are trying to meet their different QoS requirements in terms of data rate in a selfish manner [35], and the user satisfaction is then considered a QoS-related concept. On which basis, the game theory is adopted to realize a “satisfaction equilibrium” among users to balance meeting users’ expectations and saving energy consumption. In [36], the authors focused on the network management problem, while the metric of user satisfaction is defined as a function of the network response time for serving the decision-making requests, which is used to help realizing an effective load-balancing of the decision-making requests. However, the diverse priorities of users were rarely considered in these studies. Generally, it is a simple but important aim to ensure that the demands of high-priority users should be met first in practice, i.e., users with higher priorities can get as higher satisfaction as possible. To do this, a user-priority-based satisfaction maximization problem related to users’ demanding should be considered.In this paper, we consider a scenario where multiple UAVs provide data collection services for multiple users with different priorities and optimize the task assignment problem by adopting a priority-based user satisfaction-driven strategy. The main contributions are as follows:Considering users’ diverse priorities, a priority-driven user satisfaction model is built to measure users’ differentiated satisfaction towards the information obtained. Specifically, a piecewise function considering soft time window and users’ priority levels is designed to describe the relationship between user priority and user satisfaction.A satisfaction-driven multi-UAV cooperative task assignment problem is formulated as a COP, where the problem of maximizing priority-weighted user satisfaction and minimizing UAVs’ total energy consumption is considered comprehensively, and weight factors are adapted to realize a trade-off between them.To solve the task assignment problem efficiently, a multipopulation-based cooperation genetic algorithm (MPCGA) by introducing the idea of “exploration-exploitation” into traditional GAs is proposed. Numerical results demonstrate the effectiveness of MPCGA in realizing an efficient user satisfaction-driven task assignment while minimizing total energy consumption.


## 2. System Model and Problem Formulation

### 2.1. System Model

As shown in Figure1, we consider a multi-UAV-based data collection scenario, including one base station (BS), one relay UAV (UAVr), N data collection UAVs (UAVs), denoted by N=1,2,…,N, M users, denoted by ℳ=1,2,…,M, and K GSs, denoted by K=1,2,…,K. Among them, rotary-wing UAVs that can hover above GSs when executing data collection are used. BS is responsible for receiving information requirements from users, assigning tasks to UAVs, and distributing the collected information obtained by UAVs to the corresponding users. UAVs is responsible for visiting all the GSs in K and send collected information back to BS, where the task of nn∈N is to detect a subset of K, which Kn denotes. In Kn, the order of the targets indicates the corresponding order that n visits them. Among them, the ith target in Kn is denoted by kni and the serial number of kni in K is denoted by fkni. UAVr is responsible for data relay, while its position is supposed to be determined by BS and remain unchanged during the process of data collection. We assume that there is no direct communication link between each UAVs and BS, while the data from a UAVs to BS should be relayed through UAVr, which can maintain connection with BS and UAVs during the process of data collection.Figure 1
System model.In this paper, our goal is to find an optimal task allocation strategy that maximizes users’ satisfaction with the information obtained while minimizing the total energy consumption of the data collection UAVs. The constraints, data collection and transmission process, energy consumption model, user satisfaction model, and optimization objective are described as follows.


#### 2.1.1. Constraints of Target Visiting

During the data collection process, all UAVs are assumed to take off from BS simultaneously (time 0) and return to BS after finishing their tasks, i.e., conducting data collection on the respective task targets in turn and sending the collected data collection on the respective task targets data back to BS. Besides, it is assumed that a UAV can only visit a target, and the UAV can only visit it once. On this basis, the constraints of target visiting can be described by equation (1), where Kn represents the number of elements in Kn.(1)K=∪n=1NKn,n∈N,Kn1∩Kn2=∅,n1,n2∈N∧n1≠n2,∑Kn=Kn∈N.


#### 2.1.2. Constraints of Flight Time

The location of the BS is denoted as (0, 0H0), where H0 is the height of BS. The location of target k is denoted by lket=xke,yke,Hke, and the location of UAVr is denoted by lrt=xr,yr,Hr. Besides, the location of n is denoted by lnut=xnut,ynut,Hn, where the horizontal coordinate of the UAVs’ initial and final locations is (0, 0). Ignoring the process of take off and landing, UAVsn is supposed to fly at a constant height Hn during the whole data collection process, and the flight heights of UAVs are supposed to be different from each other to realize collision avoidance. Besides, it is supposed that n hovers above kk∈Kn when collecting data from k, while flying in a straight line with a constant speed V0 in other cases. Denote the time when n arrives BS after finishing its data collection task as TnF, and then TnF can be calculated as follows:(2)TnF=Tnf+Tnh=ℒnV0+∑i=1KnIniCn,i,n∈N,where Tnf and Tnh represents the flight time and hover time of n, respectively. ℒn represents the flight trajectory of n, and ℒn represents the Euclidean norm of ℒn. Ini represents the total amount of data that should be retrieved from kni, and it is codetermined by the requirements of all users who need to acquire the information about kni. Here, we assume that the difference in users’ information acquirement demands about kni is only reflected in the amount of the data collected, and Ini is selected as the maximum amount of data required by the users, which can be described as Ini=maxxm,ni⋅Im,ni. Among them, m∈ℳ, Im,ni represents the amount of data, collected from kni, required by m, and xm,ni is an indicator variable, which is used to indicate whether m needs the information about target kni. If m needs the information about target kni, and then xm,ni=1; otherwise, xm,ni=0. Besides, Cn,i represents the data collection ability of n regard to kni, i.e., the amount of data that can be transmitted from kni to n per second. In this paper, we assume that the wireless channels between GSs and UAVs are dominated by line-of-sight (LoS) links, and the power gain of the channel between kni and n is represented by hn,i=β0/Hn−Hknie2, where β0 represents the power gain at the reference distance d0=1 m. Then, Cni can be calculated as follows.(3)Cn,i=Blog21+p0hn,iσ2,where p0 represents the transmit power of fkni, σ2 is the additive white Gaussian noise (AWGN) power at the receiver, and B represents the available channel bandwidth.DenoteTn,max as the maximum flight duration of UAVsn; then the constraints of flight time for UAVs can be expressed as follows.(4)TnF≤Tn,max,n∈N.Considering thatUAVr is the last one to depart from BS and the first one to return to BS after finishing the relay of data collected from the last target, we assume that the endurance of UAVr is sufficient enough during the data collection process as long as equation (4) can be satisfied.


#### 2.1.3. Data Collection and Transmission

Suppose the start and finish time of collecting data fromkni is tni,0 and tni,1, respectively, then tni,0 and tni,1 can be calculated as follows.(5)tni,0=tni−1,1+ℒni−1,iV0,tni,1=tni,0+InfniCn,i,where i∈1,Kn+1. Here, we use target sequence number 0 and Kn+1 to represent BS to simplify the analysis process, e.g., tn0,1 represents the time when n takes off from BS and tnKn+1,0 represents the time when n lands at BS. ℒni−1,i is the length of flight trajectory segment with kni−1 and kni as endpoints. Then, the time that BS receives the information about fkni, denoted by tB,ni, can be calculated as follows.(6)tB,ni=tni,1+IniCn,r+IniCr,B,where Cn,r represents the data transmission rate from n to UAVr and Cr,B represents the data transmission rate from UAVr to the BS. We suppose Cn,r and Cr,B to be constant during the whole data collection process, which can be guaranteed by reasonable channel bandwidth allocation and channel access strategy. In this paper, an orthogonal frequency division multiple access (OFDMA) strategy similar as described in [40] is adopted, where the total available bandwidth is divided into multiple subcarriers with equal bandwidth. When multiple data collection UAVs need to transmit data to the relay UAV simultaneously, different subcarriers can be allocated to different UAVs, and the communication interference among UAVs is therefore ignored.In this paper, the communication time between BS and users is not considered. That is, we take the time when BS receives the information aboutfkni as the time when the users, who need the information about fkni, obtain the required information. Denote the time when mm∈ℳ get the information about fkni as tm,ni. Then, it can be described as follows.(7)tm,ni=tB,ni,xm,ni=1,0,xm,ni=0.


#### 2.1.4. Energy Consumption Model

Generally, the energy consumption of UAVs during flight can be divided into two parts: motion energy consumption and communication energy consumption, while ignoring the energy consumption during the take off and landing stage. Since the position ofUAVr and BS remain unchanged during the data collection process, the communication energy consumption between them, as well as the motion energy consumption of UAVr, can be viewed as a constant term that is not affected by the task assignment strategies. In this section, we mainly consider the influence of task assignment strategies on the energy consumption of data collection UAVs.(1) Motion Energy Consumption. During the data collection process, UAVs’ movement state mainly includes two kinds: flying and hovering. The corresponding motion energy consumption is viewed as flight energy consumption and hover energy consumption, which mainly depends on the propulsion power of UAV in the two states. Here, the power consumption (watt) model derived in [27] is adopted, which is described as follows.(8)PV=P01+3V2Utip2+Piv0V+12d0ρsAV3,flightV≠0,Ph=P0+Pi,hoveringV=0,where P0=δ/8ρsAΩ3R3, Pi=1+lW3/2/2ρA, which represents the profile power and induced power of UAV in hovering state, respectively. δ is airfoil drag coefficient, W is the weight of the UAV (Newton), Ω is blade angular velocity (radians/second), R is rotor radius (m), l is an incremental correction factor of the induced power, Utip represents the tip velocity of the suspension blade, v0 represents the average rotor induced velocity during hovering, and d0 and s represent the fuselage resistance ratio and rotor compactness, respectively, while ρ and A represent air density and rotor disc area, respectively.ForUAVsn, when it arrives at BS after finishing its data collection tasks, the total motion energy consumption, denoted by EnM, can be calculated as follows.(9)EnM=∫0TnFPVntdt.Specially, whenn is in flying state from fkni to fkni+1 (i∈0,Kn) with constant speed V0, its propulsion power consumption remains constant, and the energy consumption can be expressed by PnV0⋅Tnfi,i+1, where Tnfi,i+1 represents the flying time spent from fkni to fkni+1. When n is in the hovering state while reconnaissance target fkni, its energy consumption can be expressed by Phn⋅Tnhi, where Tnhi represents the hovering time spent over fkni. On this basis, equation (9) can be reorganized as (10)EnM=∑i=0KnPnV0⋅Tnfi,i+1+Phn⋅Tnhi=PnV0⋅Tnf+Phn⋅Tnh.Combining equation (2) and equation (10), EnM can be calculated by (11)EnM=PnV0⋅ℒnV0+Phn⋅∑i=1KnIniCn.(2) Communication Energy Consumption. UAV communication-related energy consumption mainly occurs during the process of signal processing, signal radiation, signal reception, etc. Here, we assume that the transmitted power of UAVs remain constant and use equation (12) [29] to calculate the communication energy consumption of transmitting the data about kni from n to UAVr:(12)En,rkni=Inidn,rtni,0αetx,where dn,rtni,0 represents the communication distance between n and UAVr when n collects data from kni and etx represents the energy consumption generated by transmitting 1 bit data by 1 meter.Based on the above analysis, the total energy consumption of data collection UAVs, denoted byEsum, can be calculated by (13)Esum=∑n=1NEnM+∑i=1KnEn,rkni.


#### 2.1.5. User Satisfaction Model

When evaluating the satisfaction of users, several factors, such as information acquisition time and information acquisition quality (quantity, precision, etc.), are usually considered. Here, we suppose the information acquisition quality can be well guaranteed, and the information acquisition time is mainly considered when describing user satisfaction. To quantifying user satisfaction, the concept of soft time window is used. For userm, when xm,ni=1, denote the expected time window for obtaining the required information as 0,tm,ni,e, and the acceptable time window for obtaining the information as tm,ni,e,tm,ni,a. When tm,ni∈0,tm,ni,e, take the information acquisition satisfaction, denoted by Sm,ni, as 1; when tm,ni∈tm,ni,e,tm,ni,a, an exponential is designed to calculate the value of Sm,ni; when tm,ni∈tm,ni,a,∞, take Sm,ni as 0. Here, we use time 0 to represent the time when BS receives user’s request, as well as the approximate time when data collection UAVs take off from BS.Besides, considering different users usually possess different service priorities, their priorities are also considered when describing user satisfaction. Here, we suppose users’ priorities to be known when BS conducts task assignment process, and the priority ofm is denoted as Pm. Among them, Pm is a positive actual number, and the higher the value of Pm, the higher the priority of m. The priority-driven user satisfaction model with a soft time window is described as (14)Sm,ni=1,tm,ni∈0,tm,ni,e,Am⋅exptm,ni,a−tm,ni+Bm,tm,ni∈tm,ni,e,tm,ni,a,0,others,where Sm,ni,max=1 represents the maximum satisfaction of m toward the information about target fkni, A=1−Sm,ni,min/exptm,ni,a−tm,ni,e−1, and B=Sm,ni,min−A.As shown in Figure2, we appoint that the higher the priority of m, the smaller the value of the Sm,ni,min. In addition, we suppose that the higher the user’s priority, the more time-sensitive their satisfaction is. That is, when m1 and m2 both require the information about fkni and their time window of acquiring information is the same, if tm1,ni>tm1,ni,e, then the satisfaction of high-priority users declines even faster over information acquisition time.Figure 2
Change trend of users’ satisfaction with information acquisition time.On this basis, a priority-oriented strategy is adopted to determine the value ofSn,min, which is described as (15)Sm,ni,min=MaxPj−Pm+εMaxPj−MinPj+ε,j∈1,M,where ε is a positive real number used to make sure the formula always makes sense. Besides, it makes users, with different priorities, have different gradients of satisfaction on the information acquisition time. This is helpful to ensure that the satisfaction of high-priority users can be better guaranteed by the algorithm described in Section 2.2. In this paper, we choose ε as MaxPj−MinPj/2, i.e., the value of the minimum satisfaction of the highest priority users is Sm,ni,max/3, and that of the lowest priority users is 1.Generally, in addition to considering the total satisfaction of users, we also need to ensure that the satisfaction of high-priority users is as high as possible when assigning tasks. To this end, users’ satisfaction is weighed accordingly based on their priorities, and the weighted satisfaction of users, denoted bySsumW, can be described in equation (16). Among them, α is an amplification factor that is bigger than 1.(16)SsumW=∑m=1M∑n=1N∑i=1KnPmα⋅xm,ni⋅Sm,ni.


### 2.2. Problem Formulation

Our goal is to maximizeSsumW while minimizing Esum through practical task assignment, subject to the constraints of target visiting in (1) and the constraints of flight time in (4). Since it is difficult to meet the two objectives of maximizing user satisfaction and minimizing energy consumption at the same time, we introduce two weight factors ϖ1 and ϖ2 to achieve a trade-off between them. Among them, ϖ1,ϖ2∈0,1 and ϖ1+ϖ2=1. On this basis, our optimization objective is formulated as (17)P1:maxa∈Aϖ1SsumWSmaxW+ϖ2EminEsum,s.t.14,where A represents the set of task assignment strategies and a∈A represents a feasible solution in A. SmaxW represents the maximum user satisfaction that can be achieved if taking user satisfaction maximization as optimization objective only, while Emin represents the minimum energy consumption that can be achieved if taking energy consumption minimization as optimization objective only. In particular, if we take ϖ1=1, problem P1 will degenerate into a satisfaction maximization problem, while problem P1 will degenerate into an energy consumption minimization problem if ϖ1=0.Obviously, problem P1 is a nonconvex optimization problem due to the nonconvexity of the objective function, and it is not easy to be solved directly to obtain an optimal solution. In this paper, we propose a multipopulation cooperation-based genetic algorithm (MPCGA), which preserves the advantages of genetic algorithm, i.e., simple, efficient, and fast convergence, and combines the advantages of swarm intelligence, i.e., solid global search-ability and the ability to jump out of locally optimal solutions.


## 2.1. System Model

As shown in Figure1, we consider a multi-UAV-based data collection scenario, including one base station (BS), one relay UAV (UAVr), N data collection UAVs (UAVs), denoted by N=1,2,…,N, M users, denoted by ℳ=1,2,…,M, and K GSs, denoted by K=1,2,…,K. Among them, rotary-wing UAVs that can hover above GSs when executing data collection are used. BS is responsible for receiving information requirements from users, assigning tasks to UAVs, and distributing the collected information obtained by UAVs to the corresponding users. UAVs is responsible for visiting all the GSs in K and send collected information back to BS, where the task of nn∈N is to detect a subset of K, which Kn denotes. In Kn, the order of the targets indicates the corresponding order that n visits them. Among them, the ith target in Kn is denoted by kni and the serial number of kni in K is denoted by fkni. UAVr is responsible for data relay, while its position is supposed to be determined by BS and remain unchanged during the process of data collection. We assume that there is no direct communication link between each UAVs and BS, while the data from a UAVs to BS should be relayed through UAVr, which can maintain connection with BS and UAVs during the process of data collection.Figure 1
System model.In this paper, our goal is to find an optimal task allocation strategy that maximizes users’ satisfaction with the information obtained while minimizing the total energy consumption of the data collection UAVs. The constraints, data collection and transmission process, energy consumption model, user satisfaction model, and optimization objective are described as follows.


### 2.1.1. Constraints of Target Visiting

During the data collection process, all UAVs are assumed to take off from BS simultaneously (time 0) and return to BS after finishing their tasks, i.e., conducting data collection on the respective task targets in turn and sending the collected data collection on the respective task targets data back to BS. Besides, it is assumed that a UAV can only visit a target, and the UAV can only visit it once. On this basis, the constraints of target visiting can be described by equation (1), where Kn represents the number of elements in Kn.(1)K=∪n=1NKn,n∈N,Kn1∩Kn2=∅,n1,n2∈N∧n1≠n2,∑Kn=Kn∈N.


### 2.1.2. Constraints of Flight Time

The location of the BS is denoted as (0, 0H0), where H0 is the height of BS. The location of target k is denoted by lket=xke,yke,Hke, and the location of UAVr is denoted by lrt=xr,yr,Hr. Besides, the location of n is denoted by lnut=xnut,ynut,Hn, where the horizontal coordinate of the UAVs’ initial and final locations is (0, 0). Ignoring the process of take off and landing, UAVsn is supposed to fly at a constant height Hn during the whole data collection process, and the flight heights of UAVs are supposed to be different from each other to realize collision avoidance. Besides, it is supposed that n hovers above kk∈Kn when collecting data from k, while flying in a straight line with a constant speed V0 in other cases. Denote the time when n arrives BS after finishing its data collection task as TnF, and then TnF can be calculated as follows:(2)TnF=Tnf+Tnh=ℒnV0+∑i=1KnIniCn,i,n∈N,where Tnf and Tnh represents the flight time and hover time of n, respectively. ℒn represents the flight trajectory of n, and ℒn represents the Euclidean norm of ℒn. Ini represents the total amount of data that should be retrieved from kni, and it is codetermined by the requirements of all users who need to acquire the information about kni. Here, we assume that the difference in users’ information acquirement demands about kni is only reflected in the amount of the data collected, and Ini is selected as the maximum amount of data required by the users, which can be described as Ini=maxxm,ni⋅Im,ni. Among them, m∈ℳ, Im,ni represents the amount of data, collected from kni, required by m, and xm,ni is an indicator variable, which is used to indicate whether m needs the information about target kni. If m needs the information about target kni, and then xm,ni=1; otherwise, xm,ni=0. Besides, Cn,i represents the data collection ability of n regard to kni, i.e., the amount of data that can be transmitted from kni to n per second. In this paper, we assume that the wireless channels between GSs and UAVs are dominated by line-of-sight (LoS) links, and the power gain of the channel between kni and n is represented by hn,i=β0/Hn−Hknie2, where β0 represents the power gain at the reference distance d0=1 m. Then, Cni can be calculated as follows.(3)Cn,i=Blog21+p0hn,iσ2,where p0 represents the transmit power of fkni, σ2 is the additive white Gaussian noise (AWGN) power at the receiver, and B represents the available channel bandwidth.DenoteTn,max as the maximum flight duration of UAVsn; then the constraints of flight time for UAVs can be expressed as follows.(4)TnF≤Tn,max,n∈N.Considering thatUAVr is the last one to depart from BS and the first one to return to BS after finishing the relay of data collected from the last target, we assume that the endurance of UAVr is sufficient enough during the data collection process as long as equation (4) can be satisfied.


### 2.1.3. Data Collection and Transmission

Suppose the start and finish time of collecting data fromkni is tni,0 and tni,1, respectively, then tni,0 and tni,1 can be calculated as follows.(5)tni,0=tni−1,1+ℒni−1,iV0,tni,1=tni,0+InfniCn,i,where i∈1,Kn+1. Here, we use target sequence number 0 and Kn+1 to represent BS to simplify the analysis process, e.g., tn0,1 represents the time when n takes off from BS and tnKn+1,0 represents the time when n lands at BS. ℒni−1,i is the length of flight trajectory segment with kni−1 and kni as endpoints. Then, the time that BS receives the information about fkni, denoted by tB,ni, can be calculated as follows.(6)tB,ni=tni,1+IniCn,r+IniCr,B,where Cn,r represents the data transmission rate from n to UAVr and Cr,B represents the data transmission rate from UAVr to the BS. We suppose Cn,r and Cr,B to be constant during the whole data collection process, which can be guaranteed by reasonable channel bandwidth allocation and channel access strategy. In this paper, an orthogonal frequency division multiple access (OFDMA) strategy similar as described in [40] is adopted, where the total available bandwidth is divided into multiple subcarriers with equal bandwidth. When multiple data collection UAVs need to transmit data to the relay UAV simultaneously, different subcarriers can be allocated to different UAVs, and the communication interference among UAVs is therefore ignored.In this paper, the communication time between BS and users is not considered. That is, we take the time when BS receives the information aboutfkni as the time when the users, who need the information about fkni, obtain the required information. Denote the time when mm∈ℳ get the information about fkni as tm,ni. Then, it can be described as follows.(7)tm,ni=tB,ni,xm,ni=1,0,xm,ni=0.


### 2.1.4. Energy Consumption Model

Generally, the energy consumption of UAVs during flight can be divided into two parts: motion energy consumption and communication energy consumption, while ignoring the energy consumption during the take off and landing stage. Since the position ofUAVr and BS remain unchanged during the data collection process, the communication energy consumption between them, as well as the motion energy consumption of UAVr, can be viewed as a constant term that is not affected by the task assignment strategies. In this section, we mainly consider the influence of task assignment strategies on the energy consumption of data collection UAVs.(1) Motion Energy Consumption. During the data collection process, UAVs’ movement state mainly includes two kinds: flying and hovering. The corresponding motion energy consumption is viewed as flight energy consumption and hover energy consumption, which mainly depends on the propulsion power of UAV in the two states. Here, the power consumption (watt) model derived in [27] is adopted, which is described as follows.(8)PV=P01+3V2Utip2+Piv0V+12d0ρsAV3,flightV≠0,Ph=P0+Pi,hoveringV=0,where P0=δ/8ρsAΩ3R3, Pi=1+lW3/2/2ρA, which represents the profile power and induced power of UAV in hovering state, respectively. δ is airfoil drag coefficient, W is the weight of the UAV (Newton), Ω is blade angular velocity (radians/second), R is rotor radius (m), l is an incremental correction factor of the induced power, Utip represents the tip velocity of the suspension blade, v0 represents the average rotor induced velocity during hovering, and d0 and s represent the fuselage resistance ratio and rotor compactness, respectively, while ρ and A represent air density and rotor disc area, respectively.ForUAVsn, when it arrives at BS after finishing its data collection tasks, the total motion energy consumption, denoted by EnM, can be calculated as follows.(9)EnM=∫0TnFPVntdt.Specially, whenn is in flying state from fkni to fkni+1 (i∈0,Kn) with constant speed V0, its propulsion power consumption remains constant, and the energy consumption can be expressed by PnV0⋅Tnfi,i+1, where Tnfi,i+1 represents the flying time spent from fkni to fkni+1. When n is in the hovering state while reconnaissance target fkni, its energy consumption can be expressed by Phn⋅Tnhi, where Tnhi represents the hovering time spent over fkni. On this basis, equation (9) can be reorganized as (10)EnM=∑i=0KnPnV0⋅Tnfi,i+1+Phn⋅Tnhi=PnV0⋅Tnf+Phn⋅Tnh.Combining equation (2) and equation (10), EnM can be calculated by (11)EnM=PnV0⋅ℒnV0+Phn⋅∑i=1KnIniCn.(2) Communication Energy Consumption. UAV communication-related energy consumption mainly occurs during the process of signal processing, signal radiation, signal reception, etc. Here, we assume that the transmitted power of UAVs remain constant and use equation (12) [29] to calculate the communication energy consumption of transmitting the data about kni from n to UAVr:(12)En,rkni=Inidn,rtni,0αetx,where dn,rtni,0 represents the communication distance between n and UAVr when n collects data from kni and etx represents the energy consumption generated by transmitting 1 bit data by 1 meter.Based on the above analysis, the total energy consumption of data collection UAVs, denoted byEsum, can be calculated by (13)Esum=∑n=1NEnM+∑i=1KnEn,rkni.


### 2.1.5. User Satisfaction Model

When evaluating the satisfaction of users, several factors, such as information acquisition time and information acquisition quality (quantity, precision, etc.), are usually considered. Here, we suppose the information acquisition quality can be well guaranteed, and the information acquisition time is mainly considered when describing user satisfaction. To quantifying user satisfaction, the concept of soft time window is used. For userm, when xm,ni=1, denote the expected time window for obtaining the required information as 0,tm,ni,e, and the acceptable time window for obtaining the information as tm,ni,e,tm,ni,a. When tm,ni∈0,tm,ni,e, take the information acquisition satisfaction, denoted by Sm,ni, as 1; when tm,ni∈tm,ni,e,tm,ni,a, an exponential is designed to calculate the value of Sm,ni; when tm,ni∈tm,ni,a,∞, take Sm,ni as 0. Here, we use time 0 to represent the time when BS receives user’s request, as well as the approximate time when data collection UAVs take off from BS.Besides, considering different users usually possess different service priorities, their priorities are also considered when describing user satisfaction. Here, we suppose users’ priorities to be known when BS conducts task assignment process, and the priority ofm is denoted as Pm. Among them, Pm is a positive actual number, and the higher the value of Pm, the higher the priority of m. The priority-driven user satisfaction model with a soft time window is described as (14)Sm,ni=1,tm,ni∈0,tm,ni,e,Am⋅exptm,ni,a−tm,ni+Bm,tm,ni∈tm,ni,e,tm,ni,a,0,others,where Sm,ni,max=1 represents the maximum satisfaction of m toward the information about target fkni, A=1−Sm,ni,min/exptm,ni,a−tm,ni,e−1, and B=Sm,ni,min−A.As shown in Figure2, we appoint that the higher the priority of m, the smaller the value of the Sm,ni,min. In addition, we suppose that the higher the user’s priority, the more time-sensitive their satisfaction is. That is, when m1 and m2 both require the information about fkni and their time window of acquiring information is the same, if tm1,ni>tm1,ni,e, then the satisfaction of high-priority users declines even faster over information acquisition time.Figure 2
Change trend of users’ satisfaction with information acquisition time.On this basis, a priority-oriented strategy is adopted to determine the value ofSn,min, which is described as (15)Sm,ni,min=MaxPj−Pm+εMaxPj−MinPj+ε,j∈1,M,where ε is a positive real number used to make sure the formula always makes sense. Besides, it makes users, with different priorities, have different gradients of satisfaction on the information acquisition time. This is helpful to ensure that the satisfaction of high-priority users can be better guaranteed by the algorithm described in Section 2.2. In this paper, we choose ε as MaxPj−MinPj/2, i.e., the value of the minimum satisfaction of the highest priority users is Sm,ni,max/3, and that of the lowest priority users is 1.Generally, in addition to considering the total satisfaction of users, we also need to ensure that the satisfaction of high-priority users is as high as possible when assigning tasks. To this end, users’ satisfaction is weighed accordingly based on their priorities, and the weighted satisfaction of users, denoted bySsumW, can be described in equation (16). Among them, α is an amplification factor that is bigger than 1.(16)SsumW=∑m=1M∑n=1N∑i=1KnPmα⋅xm,ni⋅Sm,ni.


## 2.1.1. Constraints of Target Visiting

During the data collection process, all UAVs are assumed to take off from BS simultaneously (time 0) and return to BS after finishing their tasks, i.e., conducting data collection on the respective task targets in turn and sending the collected data collection on the respective task targets data back to BS. Besides, it is assumed that a UAV can only visit a target, and the UAV can only visit it once. On this basis, the constraints of target visiting can be described by equation (1), where Kn represents the number of elements in Kn.(1)K=∪n=1NKn,n∈N,Kn1∩Kn2=∅,n1,n2∈N∧n1≠n2,∑Kn=Kn∈N.


## 2.1.2. Constraints of Flight Time

The location of the BS is denoted as (0, 0H0), where H0 is the height of BS. The location of target k is denoted by lket=xke,yke,Hke, and the location of UAVr is denoted by lrt=xr,yr,Hr. Besides, the location of n is denoted by lnut=xnut,ynut,Hn, where the horizontal coordinate of the UAVs’ initial and final locations is (0, 0). Ignoring the process of take off and landing, UAVsn is supposed to fly at a constant height Hn during the whole data collection process, and the flight heights of UAVs are supposed to be different from each other to realize collision avoidance. Besides, it is supposed that n hovers above kk∈Kn when collecting data from k, while flying in a straight line with a constant speed V0 in other cases. Denote the time when n arrives BS after finishing its data collection task as TnF, and then TnF can be calculated as follows:(2)TnF=Tnf+Tnh=ℒnV0+∑i=1KnIniCn,i,n∈N,where Tnf and Tnh represents the flight time and hover time of n, respectively. ℒn represents the flight trajectory of n, and ℒn represents the Euclidean norm of ℒn. Ini represents the total amount of data that should be retrieved from kni, and it is codetermined by the requirements of all users who need to acquire the information about kni. Here, we assume that the difference in users’ information acquirement demands about kni is only reflected in the amount of the data collected, and Ini is selected as the maximum amount of data required by the users, which can be described as Ini=maxxm,ni⋅Im,ni. Among them, m∈ℳ, Im,ni represents the amount of data, collected from kni, required by m, and xm,ni is an indicator variable, which is used to indicate whether m needs the information about target kni. If m needs the information about target kni, and then xm,ni=1; otherwise, xm,ni=0. Besides, Cn,i represents the data collection ability of n regard to kni, i.e., the amount of data that can be transmitted from kni to n per second. In this paper, we assume that the wireless channels between GSs and UAVs are dominated by line-of-sight (LoS) links, and the power gain of the channel between kni and n is represented by hn,i=β0/Hn−Hknie2, where β0 represents the power gain at the reference distance d0=1 m. Then, Cni can be calculated as follows.(3)Cn,i=Blog21+p0hn,iσ2,where p0 represents the transmit power of fkni, σ2 is the additive white Gaussian noise (AWGN) power at the receiver, and B represents the available channel bandwidth.DenoteTn,max as the maximum flight duration of UAVsn; then the constraints of flight time for UAVs can be expressed as follows.(4)TnF≤Tn,max,n∈N.Considering thatUAVr is the last one to depart from BS and the first one to return to BS after finishing the relay of data collected from the last target, we assume that the endurance of UAVr is sufficient enough during the data collection process as long as equation (4) can be satisfied.


## 2.1.3. Data Collection and Transmission

Suppose the start and finish time of collecting data fromkni is tni,0 and tni,1, respectively, then tni,0 and tni,1 can be calculated as follows.(5)tni,0=tni−1,1+ℒni−1,iV0,tni,1=tni,0+InfniCn,i,where i∈1,Kn+1. Here, we use target sequence number 0 and Kn+1 to represent BS to simplify the analysis process, e.g., tn0,1 represents the time when n takes off from BS and tnKn+1,0 represents the time when n lands at BS. ℒni−1,i is the length of flight trajectory segment with kni−1 and kni as endpoints. Then, the time that BS receives the information about fkni, denoted by tB,ni, can be calculated as follows.(6)tB,ni=tni,1+IniCn,r+IniCr,B,where Cn,r represents the data transmission rate from n to UAVr and Cr,B represents the data transmission rate from UAVr to the BS. We suppose Cn,r and Cr,B to be constant during the whole data collection process, which can be guaranteed by reasonable channel bandwidth allocation and channel access strategy. In this paper, an orthogonal frequency division multiple access (OFDMA) strategy similar as described in [40] is adopted, where the total available bandwidth is divided into multiple subcarriers with equal bandwidth. When multiple data collection UAVs need to transmit data to the relay UAV simultaneously, different subcarriers can be allocated to different UAVs, and the communication interference among UAVs is therefore ignored.In this paper, the communication time between BS and users is not considered. That is, we take the time when BS receives the information aboutfkni as the time when the users, who need the information about fkni, obtain the required information. Denote the time when mm∈ℳ get the information about fkni as tm,ni. Then, it can be described as follows.(7)tm,ni=tB,ni,xm,ni=1,0,xm,ni=0.


## 2.1.4. Energy Consumption Model

Generally, the energy consumption of UAVs during flight can be divided into two parts: motion energy consumption and communication energy consumption, while ignoring the energy consumption during the take off and landing stage. Since the position ofUAVr and BS remain unchanged during the data collection process, the communication energy consumption between them, as well as the motion energy consumption of UAVr, can be viewed as a constant term that is not affected by the task assignment strategies. In this section, we mainly consider the influence of task assignment strategies on the energy consumption of data collection UAVs.(1) Motion Energy Consumption. During the data collection process, UAVs’ movement state mainly includes two kinds: flying and hovering. The corresponding motion energy consumption is viewed as flight energy consumption and hover energy consumption, which mainly depends on the propulsion power of UAV in the two states. Here, the power consumption (watt) model derived in [27] is adopted, which is described as follows.(8)PV=P01+3V2Utip2+Piv0V+12d0ρsAV3,flightV≠0,Ph=P0+Pi,hoveringV=0,where P0=δ/8ρsAΩ3R3, Pi=1+lW3/2/2ρA, which represents the profile power and induced power of UAV in hovering state, respectively. δ is airfoil drag coefficient, W is the weight of the UAV (Newton), Ω is blade angular velocity (radians/second), R is rotor radius (m), l is an incremental correction factor of the induced power, Utip represents the tip velocity of the suspension blade, v0 represents the average rotor induced velocity during hovering, and d0 and s represent the fuselage resistance ratio and rotor compactness, respectively, while ρ and A represent air density and rotor disc area, respectively.ForUAVsn, when it arrives at BS after finishing its data collection tasks, the total motion energy consumption, denoted by EnM, can be calculated as follows.(9)EnM=∫0TnFPVntdt.Specially, whenn is in flying state from fkni to fkni+1 (i∈0,Kn) with constant speed V0, its propulsion power consumption remains constant, and the energy consumption can be expressed by PnV0⋅Tnfi,i+1, where Tnfi,i+1 represents the flying time spent from fkni to fkni+1. When n is in the hovering state while reconnaissance target fkni, its energy consumption can be expressed by Phn⋅Tnhi, where Tnhi represents the hovering time spent over fkni. On this basis, equation (9) can be reorganized as (10)EnM=∑i=0KnPnV0⋅Tnfi,i+1+Phn⋅Tnhi=PnV0⋅Tnf+Phn⋅Tnh.Combining equation (2) and equation (10), EnM can be calculated by (11)EnM=PnV0⋅ℒnV0+Phn⋅∑i=1KnIniCn.(2) Communication Energy Consumption. UAV communication-related energy consumption mainly occurs during the process of signal processing, signal radiation, signal reception, etc. Here, we assume that the transmitted power of UAVs remain constant and use equation (12) [29] to calculate the communication energy consumption of transmitting the data about kni from n to UAVr:(12)En,rkni=Inidn,rtni,0αetx,where dn,rtni,0 represents the communication distance between n and UAVr when n collects data from kni and etx represents the energy consumption generated by transmitting 1 bit data by 1 meter.Based on the above analysis, the total energy consumption of data collection UAVs, denoted byEsum, can be calculated by (13)Esum=∑n=1NEnM+∑i=1KnEn,rkni.


## 2.1.5. User Satisfaction Model

When evaluating the satisfaction of users, several factors, such as information acquisition time and information acquisition quality (quantity, precision, etc.), are usually considered. Here, we suppose the information acquisition quality can be well guaranteed, and the information acquisition time is mainly considered when describing user satisfaction. To quantifying user satisfaction, the concept of soft time window is used. For userm, when xm,ni=1, denote the expected time window for obtaining the required information as 0,tm,ni,e, and the acceptable time window for obtaining the information as tm,ni,e,tm,ni,a. When tm,ni∈0,tm,ni,e, take the information acquisition satisfaction, denoted by Sm,ni, as 1; when tm,ni∈tm,ni,e,tm,ni,a, an exponential is designed to calculate the value of Sm,ni; when tm,ni∈tm,ni,a,∞, take Sm,ni as 0. Here, we use time 0 to represent the time when BS receives user’s request, as well as the approximate time when data collection UAVs take off from BS.Besides, considering different users usually possess different service priorities, their priorities are also considered when describing user satisfaction. Here, we suppose users’ priorities to be known when BS conducts task assignment process, and the priority ofm is denoted as Pm. Among them, Pm is a positive actual number, and the higher the value of Pm, the higher the priority of m. The priority-driven user satisfaction model with a soft time window is described as (14)Sm,ni=1,tm,ni∈0,tm,ni,e,Am⋅exptm,ni,a−tm,ni+Bm,tm,ni∈tm,ni,e,tm,ni,a,0,others,where Sm,ni,max=1 represents the maximum satisfaction of m toward the information about target fkni, A=1−Sm,ni,min/exptm,ni,a−tm,ni,e−1, and B=Sm,ni,min−A.As shown in Figure2, we appoint that the higher the priority of m, the smaller the value of the Sm,ni,min. In addition, we suppose that the higher the user’s priority, the more time-sensitive their satisfaction is. That is, when m1 and m2 both require the information about fkni and their time window of acquiring information is the same, if tm1,ni>tm1,ni,e, then the satisfaction of high-priority users declines even faster over information acquisition time.Figure 2
Change trend of users’ satisfaction with information acquisition time.On this basis, a priority-oriented strategy is adopted to determine the value ofSn,min, which is described as (15)Sm,ni,min=MaxPj−Pm+εMaxPj−MinPj+ε,j∈1,M,where ε is a positive real number used to make sure the formula always makes sense. Besides, it makes users, with different priorities, have different gradients of satisfaction on the information acquisition time. This is helpful to ensure that the satisfaction of high-priority users can be better guaranteed by the algorithm described in Section 2.2. In this paper, we choose ε as MaxPj−MinPj/2, i.e., the value of the minimum satisfaction of the highest priority users is Sm,ni,max/3, and that of the lowest priority users is 1.Generally, in addition to considering the total satisfaction of users, we also need to ensure that the satisfaction of high-priority users is as high as possible when assigning tasks. To this end, users’ satisfaction is weighed accordingly based on their priorities, and the weighted satisfaction of users, denoted bySsumW, can be described in equation (16). Among them, α is an amplification factor that is bigger than 1.(16)SsumW=∑m=1M∑n=1N∑i=1KnPmα⋅xm,ni⋅Sm,ni.


## 2.2. Problem Formulation

Our goal is to maximizeSsumW while minimizing Esum through practical task assignment, subject to the constraints of target visiting in (1) and the constraints of flight time in (4). Since it is difficult to meet the two objectives of maximizing user satisfaction and minimizing energy consumption at the same time, we introduce two weight factors ϖ1 and ϖ2 to achieve a trade-off between them. Among them, ϖ1,ϖ2∈0,1 and ϖ1+ϖ2=1. On this basis, our optimization objective is formulated as (17)P1:maxa∈Aϖ1SsumWSmaxW+ϖ2EminEsum,s.t.14,where A represents the set of task assignment strategies and a∈A represents a feasible solution in A. SmaxW represents the maximum user satisfaction that can be achieved if taking user satisfaction maximization as optimization objective only, while Emin represents the minimum energy consumption that can be achieved if taking energy consumption minimization as optimization objective only. In particular, if we take ϖ1=1, problem P1 will degenerate into a satisfaction maximization problem, while problem P1 will degenerate into an energy consumption minimization problem if ϖ1=0.Obviously, problem P1 is a nonconvex optimization problem due to the nonconvexity of the objective function, and it is not easy to be solved directly to obtain an optimal solution. In this paper, we propose a multipopulation cooperation-based genetic algorithm (MPCGA), which preserves the advantages of genetic algorithm, i.e., simple, efficient, and fast convergence, and combines the advantages of swarm intelligence, i.e., solid global search-ability and the ability to jump out of locally optimal solutions.


## 3. Algorithm Description

### 3.1. Overview of GA

GA is a random search algorithm that simulates the genetic and evolutionary process of organisms, while it is suitable to deal with complex nonlinear optimization problems, such as COP, that are difficult to be solved by traditional search algorithms [41]. In GA, initial solutions are first generated randomly to form an initial population, where a solution is represented as a chromosome (or an individual). Then, the next population is generated through several evolutionary operators, i.e., selection operator, crossover operator, and mutation operator. In which process, a fitness function, which is closely related to the optimization objective, is needed to evaluate the performance of the solutions. After a certain number of iterations, with new populations constantly generated to renew their previous population, the algorithm can converge to the chromosome/individual with the best fitness value, which can be viewed as the optimal or suboptimal solution of the problem.GA has the advantages of simple structure, high efficiency, fast convergence, etc., but it is easy to fall into local optimal solutions prematurely, which leads to insufficient global search-ability. By adopting the idea of “exploration-exploitation” which is widely used in current swarm intelligence algorithms, such as ant colony algorithm, particle swarm algorithm, and artificial fish swarms algorithm [20, 42, 43]. The MPCGA is proposed and described in detail as follows.


### 3.2. Description of MPCGA

In this section, the MPCGA is proposed, and its specific steps are shown in Algorithm1. Following are the description of some details:SmaxW is calculated by assuming that all users’ satisfaction toward their desired information is 1, i.e., SmaxW=∑m=1M∑n=1N∑i=1KnPmα⋅xm,ni.Since the difference of UAVs’ total energy consumption under different task allocation strategies is mainly caused by the difference of UAVs’ total flying distance. Here, we use a mileage-saving algorithm (MSA) [44], which is more accurate than GAs, to calculate Emin and its specific steps is as showed in Algorithm 2.ail represents the local optimal feasible solution of the ith population in the lth iteration.aoptl represents the global optimal feasible solutions of the Np poplations till the l-th iteration.f⋅ is the fitness function based on SsumW and Esum, where fai,j=ϖ1Ssum,i,jW/SmaxW+ϖ2Emin/Esum,i,j.Evolutionary operators: (1) selection operator: when conducting selection operation for thei-th population, a proportional roulette selection operator is used within the population. While the ail and aoptl can also be selected as a parent with a certain probability that is independent of each other. (2) crossover operator: sequential crossover operator is used in the algorithm. (3) mutation operator: “two-element swap” operation is used in the algorithm.We implement different crossover and mutation probabilities for different populations to enhance the global search-ability of our algorithm.Algorithm1: MPCGA for multi-UAV task assignment.
Input:N, ℳ, xm,ni, K,lke, lr, population size N0, population Number Np, maximum iteration times Iter.Output: the optimal feasible solution aopt.(1)
CalculateSmaxW and Emin, respectively(2)
Population initialization(3)
fori=1 to Npdo(4)
ai0⟵ the task strategy ai,1 represented by the first individual in the i-th population;(5)
end(6)
aopt0⟵Maxai,1|i∈1,Np;(7)
l⟵1;(8)
whilel<iterdo(9)
fori=1 to Npdo(10)
forj=1 to N0do(11)
Calculate Ssum,i,jW and Esum,i,j achieved based on the task strategy ai,j that is represented by the j-th individual;(12)
Calculate the fitness of ai,j through fai,j;(13)
Evolutionary operation: selection, crossover, and mutation;(14)
end(15)
Calculate the fitness of each individual in the current population;(16)
Update ail;(17)
end(18)
Update aoptl;(19)
l⟵l+1;(20)
end(21)
aopt⟵aoptl;(22)
Returnaopt.Algorithm2: MSA for calculating Emin.
Input:N, K, lke, lr.Output:Emin.(1)
Calculate the shortest flight distance from BS to GSkk∈K, denoted as disB,k, and that between k1 and k2k1,k2∈K, denoted as disk1,k2, respectively(2)
Obtaining the mileage that can be saved if visitk1 and k2 one after the other in the same flight path according to saving-mileage formula, i.e., Δdisk1,k2=disB,k1+disB,k2−disk1,k2(3)
Sort the saving-mileage in descending order(4)
According to the constraints of flight time and energy consumption, as well as the value of saving-mileage, connect each GS sequentially to finally determine the flight routes of data collection UAVs, as well as the number of UAVs used(5)
CalculateEmin according to (13)(6)
ReturnEmin


### 3.3. Time Complexity Analysis of MPCGA

The time complexity of MPCGA is mainly dependent on two parts: (1) the complexity of calculatingSmaxW and Emin; (2) the complexity of multipopulation cooperation based GA. Generally, the complexity of calculating SmaxW is O1, and the complexity of calculating Emin is OK2. Besides, the complexity of multipopulation cooperation-based GA can be viewed as O (NpN0Ite). Then, the time complexity of MPCGA can be approximate as O (NpN0Ite+K2), which is polynomial.


## 3.1. Overview of GA

GA is a random search algorithm that simulates the genetic and evolutionary process of organisms, while it is suitable to deal with complex nonlinear optimization problems, such as COP, that are difficult to be solved by traditional search algorithms [41]. In GA, initial solutions are first generated randomly to form an initial population, where a solution is represented as a chromosome (or an individual). Then, the next population is generated through several evolutionary operators, i.e., selection operator, crossover operator, and mutation operator. In which process, a fitness function, which is closely related to the optimization objective, is needed to evaluate the performance of the solutions. After a certain number of iterations, with new populations constantly generated to renew their previous population, the algorithm can converge to the chromosome/individual with the best fitness value, which can be viewed as the optimal or suboptimal solution of the problem.GA has the advantages of simple structure, high efficiency, fast convergence, etc., but it is easy to fall into local optimal solutions prematurely, which leads to insufficient global search-ability. By adopting the idea of “exploration-exploitation” which is widely used in current swarm intelligence algorithms, such as ant colony algorithm, particle swarm algorithm, and artificial fish swarms algorithm [20, 42, 43]. The MPCGA is proposed and described in detail as follows.


## 3.2. Description of MPCGA

In this section, the MPCGA is proposed, and its specific steps are shown in Algorithm1. Following are the description of some details:SmaxW is calculated by assuming that all users’ satisfaction toward their desired information is 1, i.e., SmaxW=∑m=1M∑n=1N∑i=1KnPmα⋅xm,ni.Since the difference of UAVs’ total energy consumption under different task allocation strategies is mainly caused by the difference of UAVs’ total flying distance. Here, we use a mileage-saving algorithm (MSA) [44], which is more accurate than GAs, to calculate Emin and its specific steps is as showed in Algorithm 2.ail represents the local optimal feasible solution of the ith population in the lth iteration.aoptl represents the global optimal feasible solutions of the Np poplations till the l-th iteration.f⋅ is the fitness function based on SsumW and Esum, where fai,j=ϖ1Ssum,i,jW/SmaxW+ϖ2Emin/Esum,i,j.Evolutionary operators: (1) selection operator: when conducting selection operation for thei-th population, a proportional roulette selection operator is used within the population. While the ail and aoptl can also be selected as a parent with a certain probability that is independent of each other. (2) crossover operator: sequential crossover operator is used in the algorithm. (3) mutation operator: “two-element swap” operation is used in the algorithm.We implement different crossover and mutation probabilities for different populations to enhance the global search-ability of our algorithm.Algorithm1: MPCGA for multi-UAV task assignment.
Input:N, ℳ, xm,ni, K,lke, lr, population size N0, population Number Np, maximum iteration times Iter.Output: the optimal feasible solution aopt.(1)
CalculateSmaxW and Emin, respectively(2)
Population initialization(3)
fori=1 to Npdo(4)
ai0⟵ the task strategy ai,1 represented by the first individual in the i-th population;(5)
end(6)
aopt0⟵Maxai,1|i∈1,Np;(7)
l⟵1;(8)
whilel<iterdo(9)
fori=1 to Npdo(10)
forj=1 to N0do(11)
Calculate Ssum,i,jW and Esum,i,j achieved based on the task strategy ai,j that is represented by the j-th individual;(12)
Calculate the fitness of ai,j through fai,j;(13)
Evolutionary operation: selection, crossover, and mutation;(14)
end(15)
Calculate the fitness of each individual in the current population;(16)
Update ail;(17)
end(18)
Update aoptl;(19)
l⟵l+1;(20)
end(21)
aopt⟵aoptl;(22)
Returnaopt.Algorithm2: MSA for calculating Emin.
Input:N, K, lke, lr.Output:Emin.(1)
Calculate the shortest flight distance from BS to GSkk∈K, denoted as disB,k, and that between k1 and k2k1,k2∈K, denoted as disk1,k2, respectively(2)
Obtaining the mileage that can be saved if visitk1 and k2 one after the other in the same flight path according to saving-mileage formula, i.e., Δdisk1,k2=disB,k1+disB,k2−disk1,k2(3)
Sort the saving-mileage in descending order(4)
According to the constraints of flight time and energy consumption, as well as the value of saving-mileage, connect each GS sequentially to finally determine the flight routes of data collection UAVs, as well as the number of UAVs used(5)
CalculateEmin according to (13)(6)
ReturnEmin


## 3.3. Time Complexity Analysis of MPCGA

The time complexity of MPCGA is mainly dependent on two parts: (1) the complexity of calculatingSmaxW and Emin; (2) the complexity of multipopulation cooperation based GA. Generally, the complexity of calculating SmaxW is O1, and the complexity of calculating Emin is OK2. Besides, the complexity of multipopulation cooperation-based GA can be viewed as O (NpN0Ite). Then, the time complexity of MPCGA can be approximate as O (NpN0Ite+K2), which is polynomial.


## 4. Simulation Results

In this section, the performance of our proposed MPCGA for the multi-UAV task assignment problem is evaluated, while traditional GA with/without user’ satisfaction considered is also simulated for comparison. Among them, the GA with user’ satisfaction considered is denoted as BGA, while the algorithm without considering user satisfaction is denoted as GAWS.


### 4.1. Parameter Setting

The targets are assumed to be randomly distributed in a 1.5 km× 1 km rectangular area, while the circular area’s center is 1.75 km far from BS. Regarding the coordinate of BS as (0, 0, 25), set up a coordinate system with the line between BS and the center of the circular area as the X axis. That is, xke∈ [1000 2500] and yke∈ [−500 500]. Besides, Hke is supposed to follow a uniform distribution within [0 60]. The default number of targets, users, and available UAVs is set as 50, 10, and 5, respectively. Other major simulation parameters are as shown in Table 1.Table 1
Simulation parameters.
NotationPhysical meaningValueV0Flight speed of UAVs20 m/sHnRange of UAVs’ flight height100∼150 mIRange of data quantity collected from one target40∼80 MbitBCommunication bandwidth between GSs and UAVs2 MHzCn,rData transmission rate betweenUAVs and UAVr4 MbpsCr,BData transmission rate betweenUAVr and the BS8 MbpsTmaxMaximum flight duration ofUAVs600 sPmThe priority of userm1∼5αThe amplification factor for users’ priority2etxEnergy consumption parameter of communication10 pJ/(m bit)HkeHeight range of GSs0∼60 mσ2Additive white Gaussian noise (AWGN) power−174 dBmδAirfoil drag coefficient0.012WWeight of UAV20 NΩBlade angular velocity300 rad/sRRotor radius0.4 mUtipTip speed of the rotor blade120 m/sv0Mean rotor induced velocity in hovering4.03ρAir density1.225 kg/m3ARotor disc area0.503m3d0Fuselage resistance ratio0.6sRotor solidity0.05p0Transmit power of GSs5 mWβ0Power gain at the reference distanced0=1 m−50 dB


### 4.2. Performance Evaluation

Figure3 shows the convergence of MPCGA. It can be seen that, with the increase of the number of populations, the global search ability of the MPCGA will be enhanced to some extent, but when the number of populations is greater than a certain value, e.g., 8, the optimal solution converges to almost the same value, which means that to increase the number of populations too much does not make much sense. Besides, too large several populations will also increase the calculation complexity of the algorithm obviously. To show this more clearly, Table 2 displays the execution time of MPCGA with different population numbers, where N0 is set as 40, and Ite is set as 200. From the simulation results, one can see that the execution time of MPCGA will increase near linearly as the number of population increases, which is in line with the theoretical analysis results in Section 3. And, it indicates that, in the case of a similar convergence rate, a smaller population number is beneficial to reduce the running time of MPCGA.Figure 3
Convergence of MPCGA.Table 2
Execution time of MPCGA with different population numbers.
NPExecution time (s)36.4848.78612.59817.171020.951225.09Table3 displays the comparative results, i.e., the total energy consumption of UAVs, total weighted user satisfaction, and the max completion time of tasks, of MPCGA, BGA, and GAWS with ϖ1=0.7 and ϖ2=0.3. Among them, the situation with loose time window constraints means that most users can obtain their required information within their expected time window when UAVs visit the GSs according to the shortest path. In contrast, the situation with tight time window constraints means that most users cannot obtain their required information within their expected time window when UAVs visit the GSs according to the shortest path. The simulation results show that our proposed algorithm performs best in both situations, i.e., the highest weighted user satisfaction can be achieved at the cost of a small amount of energy consumption. In particular, when in the situation with tight time window constraints, our proposed algorithm can improve the weighted user satisfaction by about 47% compared with GAWS, while the energy consumption only increased by about 6%. Besides, compared with BGA, our proposed algorithm can also improve the weighted user satisfaction by about 5% with almost the same energy consumption.Table 3
Simulation results of MPCGA, BGA, and GAWS.
AlgorithmsEnergy consumption (J)Task completion time (S)Weighted user satisfactionMPCGALoose time window constraints3.21⋅1052512235.80Tight time window constraints4.20⋅1053651854.92BGALoose time window constraints3.60⋅1052712112.75Tight time window constraints4.26⋅1053391767.31GAWSLoose time window constraints3.12⋅1053141951.44Tight time window constraints3.95⋅1053501259.36To better show users’ satisfaction with different priorities, the simulation results of each user’s satisfaction when using different algorithms under the situation with tight time window constraints are shown in Figure4. Among them, users’ priorities are showed as labels, and the situations where users are with the same/different time-window constraints are shown, respectively. We can see from the simulation results that users with higher priorities usually can obtain higher satisfaction when completing task assignments by using MPCGA than using BGA or GAWS in both situations. For example, user 7 and user 8 can realize the highest satisfaction as they are with the highest priority, which is consistent with our original intention. Although user 7 is more satisfied than user 8 in some cases, while the opposite is true in other cases, considering their equal priority, this is an acceptable task assignment result. In addition, the average weighted user satisfaction of users with different priorities is shown in Figure 5. Sometimes users with higher priorities may achieve higher satisfaction when conducting task assignments by using BGA than MPCGA, e.g., the satisfaction of user 8 in Figure 4(a). However, from the average satisfaction of users with the same priority, MPCGA still performs better than BGA.Figure 4
Weighted satisfaction of users (a) with different time window constraints and (b) with the same time window constraints.
(a)(b)Figure 5
Average weighted satisfaction of users with different priorities (a) with different time window constraints and (b) with the same time window constraints.
(a)(b)Figure6 shows the weighted user satisfaction as well as total energy consumption of UAVs with different N, where M=10 and K=50. One can see that, with the increase of N, the weighted user satisfaction will increase correspondingly, while it finally converges since all the users can get their required data within their expected time window as long as N is big enough. For the total energy consumption of UAVs, it will still increase with the increase of N even after the user satisfaction has converged, which means that more data collection UAVs is not always better as it will cause extra energy consumption when N is large, and each UAV is assigned a mission set. On this basis, if we want to meet users’ needs as much as possible while saving energy consumption, the reasonable number of UAVs that are needed can be determined.Figure 6
Variation trend of weighted satisfaction and energy consumption with the number of UAVs.
(a)(b)Figure7 displays the average weighted user satisfaction as well as total energy consumption of UAVs with different K, where N=5 and M=10. It can be seen that, with the increase of K, the average weighted user satisfaction will decrease while the total energy consumption of UAVs will increase. The main reason is that with the increase of K, the UAVs need to visit more GSs, which will cause more flight time and hover time, resulting in more energy consumption. Besides, as it takes longer for users to get the data they need, their satisfaction will decrease correspondingly.Figure 7
Variation trend of weighted satisfaction and energy consumption with the number of GSs.
(a)(b)Figure8 shows the weighted user satisfaction as well as total energy consumption of UAVs with different I, where N=5, M=10, and K=50. From the simulation results, one can see that, with the increase of I, the average weighted user satisfaction will decrease since the data collection and data transmission time will increase, which results in a long time for users to get their required data. Besides, the total energy consumption of UAVs presents an upward trend as the hover energy consumption, and communication energy consumption of UAVs will increase. It is noted that since the minimization of energy consumption is considered in the objective function, the total energy consumption of UAVs does not always increase with the increase of I.Figure 8
Variation trend of weighted satisfaction and energy consumption with the data quantity collected from one GS.
(a)(b)The impact ofM on weighted user satisfaction as well as total energy consumption of UAVs is displayed in Figure 9. It can be seen that, with the increase of M, although the total user satisfaction will increase, the average satisfaction is about the same, and the total energy consumption of UAVs tends to stabilize. The main reason is that the increase of M may affect the order of UAVs’ visiting GSs, but not the number of GSs visited and the time of data collection and transmission. As a result, the total distance traveled by UAVs will vary, but there will not be significant fluctuations.Figure 9
Variation trend of weighted satisfaction and energy consumption with the number of users.
(a)(b)


## 4.1. Parameter Setting

The targets are assumed to be randomly distributed in a 1.5 km× 1 km rectangular area, while the circular area’s center is 1.75 km far from BS. Regarding the coordinate of BS as (0, 0, 25), set up a coordinate system with the line between BS and the center of the circular area as the X axis. That is, xke∈ [1000 2500] and yke∈ [−500 500]. Besides, Hke is supposed to follow a uniform distribution within [0 60]. The default number of targets, users, and available UAVs is set as 50, 10, and 5, respectively. Other major simulation parameters are as shown in Table 1.Table 1
Simulation parameters.
NotationPhysical meaningValueV0Flight speed of UAVs20 m/sHnRange of UAVs’ flight height100∼150 mIRange of data quantity collected from one target40∼80 MbitBCommunication bandwidth between GSs and UAVs2 MHzCn,rData transmission rate betweenUAVs and UAVr4 MbpsCr,BData transmission rate betweenUAVr and the BS8 MbpsTmaxMaximum flight duration ofUAVs600 sPmThe priority of userm1∼5αThe amplification factor for users’ priority2etxEnergy consumption parameter of communication10 pJ/(m bit)HkeHeight range of GSs0∼60 mσ2Additive white Gaussian noise (AWGN) power−174 dBmδAirfoil drag coefficient0.012WWeight of UAV20 NΩBlade angular velocity300 rad/sRRotor radius0.4 mUtipTip speed of the rotor blade120 m/sv0Mean rotor induced velocity in hovering4.03ρAir density1.225 kg/m3ARotor disc area0.503m3d0Fuselage resistance ratio0.6sRotor solidity0.05p0Transmit power of GSs5 mWβ0Power gain at the reference distanced0=1 m−50 dB


## 4.2. Performance Evaluation

Figure3 shows the convergence of MPCGA. It can be seen that, with the increase of the number of populations, the global search ability of the MPCGA will be enhanced to some extent, but when the number of populations is greater than a certain value, e.g., 8, the optimal solution converges to almost the same value, which means that to increase the number of populations too much does not make much sense. Besides, too large several populations will also increase the calculation complexity of the algorithm obviously. To show this more clearly, Table 2 displays the execution time of MPCGA with different population numbers, where N0 is set as 40, and Ite is set as 200. From the simulation results, one can see that the execution time of MPCGA will increase near linearly as the number of population increases, which is in line with the theoretical analysis results in Section 3. And, it indicates that, in the case of a similar convergence rate, a smaller population number is beneficial to reduce the running time of MPCGA.Figure 3
Convergence of MPCGA.Table 2
Execution time of MPCGA with different population numbers.
NPExecution time (s)36.4848.78612.59817.171020.951225.09Table3 displays the comparative results, i.e., the total energy consumption of UAVs, total weighted user satisfaction, and the max completion time of tasks, of MPCGA, BGA, and GAWS with ϖ1=0.7 and ϖ2=0.3. Among them, the situation with loose time window constraints means that most users can obtain their required information within their expected time window when UAVs visit the GSs according to the shortest path. In contrast, the situation with tight time window constraints means that most users cannot obtain their required information within their expected time window when UAVs visit the GSs according to the shortest path. The simulation results show that our proposed algorithm performs best in both situations, i.e., the highest weighted user satisfaction can be achieved at the cost of a small amount of energy consumption. In particular, when in the situation with tight time window constraints, our proposed algorithm can improve the weighted user satisfaction by about 47% compared with GAWS, while the energy consumption only increased by about 6%. Besides, compared with BGA, our proposed algorithm can also improve the weighted user satisfaction by about 5% with almost the same energy consumption.Table 3
Simulation results of MPCGA, BGA, and GAWS.
AlgorithmsEnergy consumption (J)Task completion time (S)Weighted user satisfactionMPCGALoose time window constraints3.21⋅1052512235.80Tight time window constraints4.20⋅1053651854.92BGALoose time window constraints3.60⋅1052712112.75Tight time window constraints4.26⋅1053391767.31GAWSLoose time window constraints3.12⋅1053141951.44Tight time window constraints3.95⋅1053501259.36To better show users’ satisfaction with different priorities, the simulation results of each user’s satisfaction when using different algorithms under the situation with tight time window constraints are shown in Figure4. Among them, users’ priorities are showed as labels, and the situations where users are with the same/different time-window constraints are shown, respectively. We can see from the simulation results that users with higher priorities usually can obtain higher satisfaction when completing task assignments by using MPCGA than using BGA or GAWS in both situations. For example, user 7 and user 8 can realize the highest satisfaction as they are with the highest priority, which is consistent with our original intention. Although user 7 is more satisfied than user 8 in some cases, while the opposite is true in other cases, considering their equal priority, this is an acceptable task assignment result. In addition, the average weighted user satisfaction of users with different priorities is shown in Figure 5. Sometimes users with higher priorities may achieve higher satisfaction when conducting task assignments by using BGA than MPCGA, e.g., the satisfaction of user 8 in Figure 4(a). However, from the average satisfaction of users with the same priority, MPCGA still performs better than BGA.Figure 4
Weighted satisfaction of users (a) with different time window constraints and (b) with the same time window constraints.
(a)(b)Figure 5
Average weighted satisfaction of users with different priorities (a) with different time window constraints and (b) with the same time window constraints.
(a)(b)Figure6 shows the weighted user satisfaction as well as total energy consumption of UAVs with different N, where M=10 and K=50. One can see that, with the increase of N, the weighted user satisfaction will increase correspondingly, while it finally converges since all the users can get their required data within their expected time window as long as N is big enough. For the total energy consumption of UAVs, it will still increase with the increase of N even after the user satisfaction has converged, which means that more data collection UAVs is not always better as it will cause extra energy consumption when N is large, and each UAV is assigned a mission set. On this basis, if we want to meet users’ needs as much as possible while saving energy consumption, the reasonable number of UAVs that are needed can be determined.Figure 6
Variation trend of weighted satisfaction and energy consumption with the number of UAVs.
(a)(b)Figure7 displays the average weighted user satisfaction as well as total energy consumption of UAVs with different K, where N=5 and M=10. It can be seen that, with the increase of K, the average weighted user satisfaction will decrease while the total energy consumption of UAVs will increase. The main reason is that with the increase of K, the UAVs need to visit more GSs, which will cause more flight time and hover time, resulting in more energy consumption. Besides, as it takes longer for users to get the data they need, their satisfaction will decrease correspondingly.Figure 7
Variation trend of weighted satisfaction and energy consumption with the number of GSs.
(a)(b)Figure8 shows the weighted user satisfaction as well as total energy consumption of UAVs with different I, where N=5, M=10, and K=50. From the simulation results, one can see that, with the increase of I, the average weighted user satisfaction will decrease since the data collection and data transmission time will increase, which results in a long time for users to get their required data. Besides, the total energy consumption of UAVs presents an upward trend as the hover energy consumption, and communication energy consumption of UAVs will increase. It is noted that since the minimization of energy consumption is considered in the objective function, the total energy consumption of UAVs does not always increase with the increase of I.Figure 8
Variation trend of weighted satisfaction and energy consumption with the data quantity collected from one GS.
(a)(b)The impact ofM on weighted user satisfaction as well as total energy consumption of UAVs is displayed in Figure 9. It can be seen that, with the increase of M, although the total user satisfaction will increase, the average satisfaction is about the same, and the total energy consumption of UAVs tends to stabilize. The main reason is that the increase of M may affect the order of UAVs’ visiting GSs, but not the number of GSs visited and the time of data collection and transmission. As a result, the total distance traveled by UAVs will vary, but there will not be significant fluctuations.Figure 9
Variation trend of weighted satisfaction and energy consumption with the number of users.
(a)(b)


## 5. Conclusion

This paper studied a multi-UAV-based sensor network where multiple UAVs need to collect data from multiple GSs in sequence and transmit the information back to BS through a relay UAV. In the process of task assignment, considering different users’ diverse priorities and corresponding priority-related satisfaction, a priority-driven user satisfaction model was constructed, where a piecewise function considering soft time window and users’ priority levels was designed to describe user satisfaction. A combinatorial optimization problem with multiple constraints was formulated, where the objective is maximizing the priority-weighted satisfaction of users while minimizing the total energy consumption of UAVs. Furthermore, a multipopulation-based cooperation genetic algorithm (MPCGA) was proposed by adopting the idea of “exploration-exploitation” into traditional GA. Simulation results showed the convergence and the effectiveness of our proposed algorithm.In the follow-up work, we will consider the distribution features of GSs and the priority-based fairness problem between users to improve our algorithm’s effectiveness and applicability further.



---

*Source: 2717733-2021-10-13.xml*