© J. Liu et al., published by EDP Sciences, 2020

1 Introduction

In the past 10 yrs, Unmanned Aerial Vehicle (UAV) has been developing rapidly. Because of its small size, strong concealment, little restricted by human factors, flexible movement and long flight time, it is used in intelligence collection, route investigation, security inspection, target monitoring, military strike and other tasks. However, in some complex applications, multiple UAVs need to work together. In order to complete more complex network tasks, multi UAVs can independently form a cooperative integrated communication system, which is called Flying Ad Hoc Network (FANET) [1,2].

Due to various advantages and wide range of applications areas FANETs are getting attentions of research community around the globe. Three main applications are described below [3]:

• Surveillance/monitoring. This class contains applications that involve UAVs as flying cameras. The tasks typically involve capturing real-time images, video or audio from flying devices, in order to process them and catch sensitive information. For example, in search and rescue missions UAVs are looking/sensing for a target, typically on the ground.

• Environmental sensing. In this class, UAVs act as sensors that detect environmental information such as PM2.5 and other pollutant concentration in the specified air. In this context, applications might need several sensor data to evaluate some environmental conditions. A sensor network arranges sensors in proximity or within the phenomenon to be observed. Temperature, humidity, pressure, light intensity, pollution level are typical physical quantities that a sensor network can analyze.

• Relaying network. FANETs can deploy connectivity in areas that need a certain kind of communication. Autonomously operated UAVs are being used as airborne communication relays to efficiently and securely transmit information collected by ground sensors to distant control centers, and for increasing the communication range of relaying ground nodes.

Figure 1 shows a FANET as relay network. Each UAV is equivalent to a router, and the wireless link (air to air link, which is abbreviated as a2a) between them forms a network to achieve the purpose of relay communication, and the terminals can use this network to communicate with each other through air to ground link (which is abbreviated as a2g). In addition, a ground station is used to connect to a UAV and connect to the ground network. As a result of this all the UAVs including the ones which are out of the communication range can transmit information to the ground station and other terminator at any time.

Compared with traditional ad hoc network, FANET has the following characteristics:

• The movement speed of internal members is relatively high in general. It is about between 8 and 120 m/s. Such a high rate of movement will lead to drastic changes in the network topology, and sharp decline in the interconnection ability and protocol efficiency between members of the network.

• The computing ability of members is generally high. It often carries high-performance computing equipment with high speed and sufficient energy supply. With the use of various sensors such as navigation equipment, it can meet the needs of various calculations.

• The deployment density of members is generally low. The internal members are scattered in the high altitude, and the straight-line distance between members is mostly hundreds or more meters. In a certain space range, the deployment density of members will not be very high.

Due to the high moving speed of nodes, frequent link failures and poor network robustness in FANET, topology control is facing severe challenges. And topology in FANET affects network throughput.

Throughput is an important network performance metric, which is defined as the rate of information transmission. The throughput of a link depends on the load and the link capacity. The link capacity depends on the channel bandwidth and Signal-to-Noise Ratio (SNR), and the SNR is affected by the distance between the sender and the receiver. Therefore, the capacity can be controlled by changing the distance. For FANET, because the position of UAV can be moved, the distance between two nodes can be adjusted, and then the capacity of corresponding link can be optimized to improve the network throughput.

In this paper, we propose an algorithm based on genetic algorithm to optimize the position of UAV, and then maximize the throughput. The algorithm can be implemented and run in the ground station to control the whole network. The main contents of this paper include: building the mathematical model of FANET throughput optimization problem; proposed an optimization algorithm using genetic algorithm to maximize the throughput; using MATLAB to simulate the proposed algorithm. The results show that the throughput can achieve the expected through the control of node position.

Fig. 1 Flying ad hoc network (FANET).

2 Related work

FANET has different names in different occasions and shown in Table 1.

Although there are some differences in the emphasis of the above names, their common characteristics are: the communication between multiple UAVs does not completely rely on the ground control station or satellite and other basic communication facilities, but takes UAVs as network nodes. In this network, each node has the functions of transceiver and router, and forwards data to further nodes in the way of multi hop.

The position of UAVs affects various network performance metrics, such as throughput, coverage, connectivity, and revenue. To address the mismatch between the communication capacity and the traffic demand. Zhan [15] developed an algorithm for optimizing the performance of the ground-to-relay links through control of the UAV heading angle. Dixon [16] proposed a decentralized mobility control algorithm for an optimal end-to-end communication chain using a team of unmanned aircraft acting solely as communication relays. The chaining controller drives the position of a virtual control point, using estimates of the communication objective function gradient calculated using stochastic approximation techniques, to locations of improved relaying for unmanned aircraft. Guo [17] carried out a theoretical analysis of how capacity is affected by interference and derived a closed-form expression for capacity, which can be used to determine optimal locations for UAVs. Bor-Yaliniz [18] considered the locations of the radio access network elements are determined mainly based on the long-term traffic behavior and proposed a multi-tier drone-cell network to complement a terrestrial heterogeneous network and examined the positioning of drone base stations for coverage and revenue maximization. Rosario [19] considered routing protocols should consider a relay placement service to find the ideal location for UAVs that act as relay nodes, and thus avoiding the effects of UAV movements on the video dissemination and proposed a mechanism for the placement of UAV relays to support the transmission of high-quality live video with satisfactory Quality of Experience (QoE). Gao [20] found that the maximum network throughput is further characterized by optimally choosing the initial back off window sizes of all the nodes and shown to be closely dependent on the percentage of nodes that can be heard by multiple APs. Wang [21] proposed a variety of distributed gateway-selection algorithms and cloud-based stability-control mechanisms. Cheng [22] proposed a scheme for optimizing the trajectory of a UAV for offloading traffic at the edge regions of three adjacent BSs. In the proposed scheme, the sum rate of UAV-served edge users is maximized subject to the rate requirements for all the users, by optimizing the UAV trajectory in each flying cycle. Cumino [23] presented a cluster-based control plane messages management in software-defined flying ad-hoc Network. Based on UAV contextual information, the controller can predict UAV information without control message transmission.

3 System modeling

3.1 Problem description

It is assumed that there are m users who need to communicate in a certain area, and there are n UAVs (routers) in this area providing communication service.

As shown in Figure 2a, the hollow dot represents the user node in a certain area, and the solid dot represents the UAV node in FANET. Each UAV node can provide communication services for multiple user nodes, but each user node can select only one UAV node to enjoy the service, and the UAV nodes are connected into a network by self-organization. By optimizing the position of UAV nodes, the total throughput of the network is maximized. Figure 2b is a two-dimensional description of Figure 2a.

Fig. 2 FANET service areas.

3.2 Analysis of throughput influencing factors

(1) UAV Position affects the throughput

UAV Position affects the distance. The distance between nodes affects the corresponding link capacity, and then the throughput. Link throughput and link capacity are two different concepts, but link capacity limits link throughput. For a link, the factors affecting the capacity mainly include the link bandwidth and signal-to-noise ratio. Since the bandwidth of the link and the signal noise in the airspace are relatively constant, the realization of the capacity is related to the signal strength received by the receiver. For the same power transmission signal, due to the different distance between the transmitter and the receiver, the path loss is different, so the receiver receives different signals, so the capacity of the link has changed.

The corresponding relationship between link capacity and received signal strength is shown in Table 2 [24].

As shown in Table 2, when the signal strength received is not less than the corresponding value, the corresponding link capacity can be achieved. Due to the loss of wireless signal in space transmission, the capacity of the link is related to the distance between the sender and the receiver.

There are two kinds of communication links in FANET: the communication link from UAV to UAV (Link a2a in Fig. 1) and the communication link between UAV and ground communicator (Link a2g in Fig. 1). The characteristics of these two links are different, so the calculation methods are also different [25].

For UAV to user communication, we use the air to ground path loss model; while for UAV to UAV communication, we use free space path loss model.

The free space path loss model can directly give the path loss of the signal, as shown in the formula (1) [26].$$P{L}_{V2V}(dB)=20\log (f)+20\log (d)-27.55$$(1)

The air to ground path loss model is based on the free space path loss model, which is shown in the formula (2) [26].$$P{L}_{V2C}(dB)=P{L}_{V2V}(dB)+P(LoS){\eta }_{LoS}+P(NL\text{o}S){\eta }_{NLoS}$$(2)Where d is the distance between the UAV and the UAV / receiver in km, f is frequency in MHz, P(LoS) is the Line of Sight (LoS) probability, P(NLoS) is the No Line of Sight (NLos) probability, η _LoS and η _NLoS represent Additional loss of LoS or NLoS.P(LoS), P(NLoS), η _LoS and η _NLoS can be obtained from the reference [26].

It can be seen from formula (1) and (2) that for signals with a certain power, the received signal strength is different due to different loss when the path distance is different. According to Table 2, different link capacities can be obtained. The path distance depends on the two UAV position.

Based on the above analysis, we can conclude that the UAV position affects the network throughput.

Here use a simple example to illustrate the UAV position effect on throughput. There is shown four UAVs and eight users in Figure 3a.Where V _i Represents network node, C _i Represents the user node. The number on the link indicates the link capacity determined by the position of UAV at both ends of the link.

The four flows and their demands are shown in the first three columns of Table 3. Before optimization, the flow 1 uses capacity 3 of link V₁ V₃, so the flow 3 uses the remaining capacity 3 of link V₁ V₃. It can be seen that the existing UAV position cannot meet the demands of flow 3 and 4 because of the insufficient capacity of the link. Similarly, due to the insufficient capacity of links V₁ V₃, V₂ V₃ and V₁ C₂, and, the demands of flow 3 cannot be met. On the other hand, the capacity of the link V₃ V₄ is larger than the demand on the link. Therefore, by optimization the position of UAV, the capacity of link V₁ V₃ and V₂ V₃ can be increased, which can provide more capacity for flow 3 and 4. Thus, the total throughput of the system is increased. Figure 3b shows the position after optimization. The initial position of UAV is represented by a small dotted line circle. The UAV V₃ is approaching the UAV V₁ and V₂. Similarly, UAV V₁ and V₂ also approach UAV V₃. In addition, with the new positioning, the UAV V₁ is closer to the user C₂, thus increasing the capacity of link V₁ C₂. At this time, the capacity of links V₂ V₃, V₁ V₃ and V₁ C₂ is large enough to support their service demands. Similarly, the UAV V₄ has moved to the left (to compensate for the movement of UAV V₃) to maintain sufficient capacity for links V₃ V₄, V₄ C₇ and V₄ C₈. Although the capacity of link V₁ V₂ has been reduced from 8 to 7, it still exceeds the link demand 6. Therefore, with the optimization of UAV position, all flow demands are met, and the total throughput increases from 12 to 16.

(2) Terminator selection affects the throughput

User nodes choose different UAV nodes will also affect the overall throughput. A simple example is shown in Figure 4 with 3 UAV nodes and 6 user nodes. The flow demands between users are shown in the first three columns of Table 4. Because the UAV nodes connected by C₂ are different, the throughput achieved by using the scheme in the left figure is 10, and that in the scheme on the right is 19. The statistical result is shown in Table 4.

From the above analysis, we can conclude that the throughput of the system can be optimized by designing the position of UAV nodes and the users the UAV serves.

Fig. 3 UAV Position affects the throughput. (a) Position before optimization. (b) Position after optimization.

Fig. 4 User selection affects the throughput.

3.3 Modeling

(1) System representation

Record the system as S(V, C), Where V represents the UAV nodes in the area, with the total number n, C represents the communication users in the area, with the total number m. Position of each UAV node or user node is P _i  = (p _i (x), p _i (y), p _i (z)). Obviously, the nodes are in a three-dimensional space. However, for the sake of convenience, we will describe it in two-dimensional space, as shown in Figure 2b, that is P _i  = (p _i (x), p _i (y)). Because the throughput is related to the distance between nodes, and there is no essential difference between the distance on two-dimensional plane and in three-dimensional space.

(2) Data link

Using E represent the link set between UAV nodes. The graph G(V, E) can represent the FANET. The adjacency matrix of the graph is denoted as A, that is $$A=\left[\begin{array}{cccc}\hfill a_{11}\hfill & \hfill a_{12}\hfill & \hfill \mathrm{...}\hfill & \hfill a_{1n}\hfill \\ \hfill a_{21}\hfill & \hfill a_{22}\hfill & \hfill \mathrm{...}\hfill & \hfill a_{2n}\hfill \\ \hfill \mathrm{...}\hfill & \hfill \mathrm{...}\hfill & \hfill \mathrm{...}\hfill & \hfill \mathrm{...}\hfill \\ \hfill a_{n1}\hfill & \hfill a_{n2}\hfill & \hfill \mathrm{...}\hfill & \hfill a_{nn}\hfill \end{array}\right],\text{where}{a}_{u,v}=\{\begin{array}{l}0,\text{If}\text{no}\text{link}\text{between}u\text{and}v\hfill \\ 1,\text{If}\text{link}\text{between}u\text{and}v\hfill \end{array}$$(3)

A communication link exists between two UAV nodes u and v if and only if the distance between them is within the transmission range of each other. That is$$a_{u,v}=1\iff d_{u,v}=dis\tan ce(p_u,p_v)\le R_{V2V}$$(4)

Here R _V2V is the maximum transmission range of communication between UAVs, p _u and p _v indicate the position of UAVs u and v respectively. If there are more than two nodes in the range of one UAV node, the nearest node is selected to establish the connection. Let's assume that the graph is connected.

Each UAV can communicate with all adjacent UAVs at the same time without interfering with other UAVs. This can be achieved in two ways. (1) Each UAV is equipped with multiple interfaces, and each interface uses a channel that is not used by any neighbors. (2) Each UAV has multi-user multi input multiple output (MU-MIMO) capability. All UAVs have the same maximum transmission range R _V2V for UAV to UAV Communication. Similarly, all UAVs have the same maximum transmission range R _V2C to the user communication. And R _V2V  ≥ R _V2C .

All users of network G serviced are recorded as C(G), and the users serviced by UAV u ∈ V are recorded asC(u)_. It is assumed that each user only receives communication services from one UAV node, and all UAV nodes cover all users.

That is:$$\begin{array}{l}C(u)\cap C(v)=\mathrm{\Phi }(u\ne v)\\ {\displaystyle \underset{u\in V}{\cup }}C(u)=C(G)\end{array}$$(5)

The relationship between UAV and user is represented by incidence matrix B, that is$$B=\left[\begin{array}{cccc}\hfill b_{11}\hfill & \hfill b_{12}\hfill & \hfill \mathrm{...}\hfill & \hfill b_{1m}\hfill \\ \hfill b_{21}\hfill & \hfill b_{22}\hfill & \hfill \mathrm{...}\hfill & \hfill b_{2m}\hfill \\ \hfill \mathrm{...}\hfill & \hfill \mathrm{...}\hfill & \hfill \mathrm{...}\hfill & \hfill \mathrm{...}\hfill \\ \hfill b_{n1}\hfill & \hfill b_{n2}\hfill & \hfill \mathrm{...}\hfill & \hfill b_{nm}\hfill \end{array}\right]$$(6)

Where $$b_{u,v}=\{\begin{array}{l}0,\text{If}\text{the}\text{user}v\text{accessing}\text{the}\text{network}\text{does}\text{not}\text{through}\text{UAV}u\hfill \\ 1,\text{If}\text{the}\text{user}v\text{accessing}\text{the}\text{network}\text{through}\text{UAV}u\hfill \end{array}$$

A communication link b _u,v exists between the UAV node u and the user node v if and only if the distance between them is within the transmission range. That is:$$b_{u,v}=1\iff d_{u,v}=dis\tan ce(p_u,p_v)\le R_{V2C}$$(7)

Here R _V2C is the transmission range of communication between the UAV and the user, p _u and p _v represent respectively the location of the UAV u and the user v.

(3) Flow demand

If the unordered pair (i, j) represents the communication flow between users i and j, the flow demand is expressed by f _ij , then the flow demand between m users is expressed by matrix T.$$T=\left[\begin{array}{cccc}\hfill 0\hfill & \hfill f_{12}\hfill & \hfill \mathrm{...}\hfill & \hfill f_{1m}\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \mathrm{...}\hfill & \hfill f_{2m}\hfill \\ \hfill \mathrm{...}\hfill & \hfill \mathrm{...}\hfill & \hfill 0\hfill & \hfill \mathrm{...}\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \mathrm{...}\hfill & \hfill 0\hfill \end{array}\right]$$(8)

The path of the flow (i, j) in network is recorded as P _ij . The link capacity can be calculated by formula (1) and obtained by looking up Table 2. It is recorded as c _l,(i,j) the allowable capacity of the flow (i, j) on the link l ∈ P _ij . When multiple flows pass through a link, the allowable capacity of each flow is allocated according to the principle of maximum and minimum fairness [27]. B _ij is recorded as the allowable capacity on the bottleneck link of the flow (i, j), that is$$B_{ij}={\displaystyle \underset{l\in P_{ij}}{\min }}(c_{l,(i,j)})$$(9)

The throughput achieved by the flow (i, j) is recorded as τ _ij , and$${\tau }_{ij}=\min (f_{ij},B_{ij})$$(10)

The maximum throughput that can be realized by the flow (i, j) is f _ij , if f _ij  ≤ B _ij . When f _ij  ≥ B _ij , τ _ij can be increased with B _ij increasing. One way to achieve this goal is to bring the nodes on the bottleneck link closer to each other. The bottleneck link can be between two UAVs, or between a UAV and its associated users.

(4) Throughput maximization description

Here let τ represent the total throughput of the system and $\tau ={\displaystyle \sum _{i=1}^m}{\displaystyle \sum _{j=i}^m}{\tau }_{ij}$.

Under the given conditions, the objective of all the optimization is $$\max mize{\displaystyle \sum _{i=1}^m}{\displaystyle \sum _{j=i}^m}{\tau }_{ij}$$(11a) $$\begin{array}{l}S.t.S(V,C,T)\\ d_{u,v}=distance(p_u,p_v)\le R_{V2V},\forall u\in V,\exists v\in V\\ d_{u,v}=distance(p_u,p_v)\le R_{V2C},\forall v\in C,\exists u\in V\end{array}$$(11b)

Formula (11a) represent maximizing the total throughput of all user flows. The first formula of (11b) indicates that the system is composed of UAV node V and user node V. The flow matrix between user nodes is T, which the initial input of the system is. The second formula of (11b) indicates that any UAV node has at least one UAV node with a distance less than R _V2V , and the third formula indicates that any user node has at least one UAV node with a distance less than R _V2C . Together, they indicate that all UAV nodes are connected to the network, and all users have UAV nodes to provide communication services, which are the system constraints.

4 Optimization algorithm using genetic algorithm

As mentioned above, the selection of user nodes for UAV and the position of UAV nodes affect the throughput of the network, and the optimization of throughput is a complex process. Therefore, we use genetic algorithm to get the maximum throughput by using its excellent global optimization ability.

Genetic algorithm [28] is a computational model of biological evolution process simulating natural selection and genetic mechanism of Darwin's biological evolution theory. Genetic algorithm starts from a population which represents the potential solution set of the problem, and the population is composed of a certain number of individuals encoded by chromosome. After the emergence of the first generation of population, t evolution produces better and better approximate solutions according to the principle of survival of the fittest. In each generation, individuals are selected according to the fitness and with the genetic operators of crossover and mutation to produce a new population. After decoding, the optimal individual in the last generation population can be regarded as the approximate optimal solution of the problem.

The key points of the algorithm include the following aspects.

4.1 Numbering area

In order to use genetic algorithm, the area of FANET is covered with multiple regular hexagons, and each hexagon has a different number. The position of each UAV node or user node is represented by it number. As shown in Figure 5, UAVs V₁, V₂, V₃, V₄ are located at hexagon 15, hexagon 60, hexagon 43 and hexagon 46 respectively. Obviously, the smaller the side length of a regular hexagon, the more hexagonal meshes is needed, and at the same time, the more accurate the UAV position is described. In order to characterize the fineness of the region divided by regular hexagon, we call the side length of the regular hexagon as the Radius of Particle Size (RPS).

Fig. 5 Regional grid diagram of FANET.

4.2 Determine the adjacency matrix A between UAV nodes

The self-organizing characteristic of FANET is that it can connect with other nodes autonomously in the effective communication range. That is According to the UAV node set {V _i }, the corresponding adjacency matrix A is determined.

As mentioned above, according to equations (1) and (2), the closer the distance between two nodes is, the larger the corresponding link capacity is. Therefore, the link generation between UAV nodes can adopt the following methods:

For any node u in {V _i }, calculate the space distance with other nodes, select the nearest node v ^* = arg min|p _u p _v | and establish a link with it.

Since the distance between adjacent nodes is always the minimum, the distance between adjacent nodes is always guaranteed. On this basis, the optimization process can be shortened.

According to the adjacency matrix A, the shortest path P between two nodes can be obtained by Dijkstra algorithm [29].

4.3 Determine the correlation matrix B between the user and UAV

As mentioned above, different UAV nodes selected by users may lead to different system throughput, so it is necessary to optimize the connection between users and UAVs.

If the traffic demand of the user i and the opposite end j is f _ij , the total traffic demand of the user i is $F_i={\displaystyle \sum _j}{f}_{ij}$; The sum of all link capacities of UAV node g is recorded as T _g ; If the user i is only in the effective communication range R _V2C of one UAV node g, it will connect to the UAV g directly, but if user i is in the effective communication range of multiple UAV nodes, it needs to choose which UAV to connect. Note that the set of users connected to the UAV node g is C _g , and then the exact one is determined by the following formula$$C_g^{*}=\arg \min {{\displaystyle \sum _{g\in V}}\left(\frac{{\displaystyle \sum _{i\in C_g}}{F}_i}{T_g}\right)}^2$$(12)

According to this method, the incidence matrix elements of other UAV nodes can also be obtained, and then the incidence matrix can be obtained.

Using the incidence matrix B and the traffic matrix T and the P in Section 4.2, the allowable capacity c _l,(i,j) of each flow (i, j) on the link l can be obtained, and then the bottleneck capacity B _ij can be obtained using formula (9).

The next step is to increase the link capacity B _ij by controlling the position of UAV nodes.

4.4 Determine the range of UAV node movement

The deployment position of UAV is determined by two factors: the position of service object (user) and the position of neighbor UAV node. It is required that the distance between UAV and its users is not greater than R _V2C , and the distance from its neighbor UAV is not greater than R _V2V . The UAV deployment scope can be obtained as shown in Figure 7.

There are three steps:

Step 1: Take the adjacent nodes as the center of the circle and draw a circle with the radius R _V , which no greater than R _V2V ;

Step 2: Take the user nodes as the center of the circle and draw a circle with the radius R _C , which no greater than R _V2C ;

Step 3: The intersection of all circles is the optional position for the UAV deployment.

Obviously, in this range, UAV and other UAV nodes or users can ensure normal connection. We call R _C and R _V as the Radius of Position Constraint (RPC). Obviously, the larger the RPC is, the greater the UAV movements range get.

As shown in Figure 6, take the movement range of UAV V₃ as an example. Take its neighbor UAV nodes V₁, V₂ and V₄ as the center of the circle, make the circle with the radiusR _V less than R _V2V ;Take its user node C₆ as the center, and make the circle with the radius R _C less than R _V2C . The overlapping part H of the four circles is the movement range of V₃, and the part H can be represented by hexagons number in Section 4.1. Similarly, the movement range of other UAV nodes can be determined.

Fig. 6 The Radius of Position Constraint (RPC).

4.5 Coding and using genetic algorithm to optimize

In order to solve the optimization problem, the genetic algorithm should first code the problem to form a population, and then carry out genetic operation on the population.

(1) Coding and population initialization

The optimization object is the position of UAV nodes. Therefore, for each UAV node, it is carried out in the optional position. In order to use classical genetic algorithm, binary coding is carried out here. Figures 5 and 6 are superimposed to form the numbering result of UAV movement position as shown in Figure 7. For example, the optional positions of UAV nodes V₃ are {17, 30, 37, 43, 50}, and there are five optional positions, which can be encoded by 3-bit binary number, as shown in Table 5.

Each UAV node is encoded according to the above method, and the binary strings are connected together according to the UAVs, which is a kind of representation of UAV position in the region.

Assuming that the code of the UAV node i is Code (i), then the chromosome code corresponding to a possible position scheme$$Code={\displaystyle \sum _i}Code(i)$$(13)

The sum here represents the connection of strings. According to the above method, multiple chromosomes are generated to form a population.

(2) Perform genetic operation according to fitness value

1) Fitness calculation

The network throughput corresponding to chromosome n is represented by τ(n), then$$\tau (n)={\displaystyle \sum _{i=1}^m}{\displaystyle \sum _{j=i}^m}{\tau }_{i,j}(n)$$(14)

Where τ _i,j (n) represents the flow value from the user i to j in the chromosome n.

Each chromosome code has an adaptive value, which is the basis for evaluating the chromosome. The fitness value is determined by fitness function. The design of fitness function should meet the following conditions: normative, reasonable, single value, continuous, small amount of calculation and universality. For the optimization problem in this paper, a fitness function can be designed as follows:$$Fit(n)=\{\begin{array}{cc}\hfill 0.5+0.5\times {\left(\frac{\tau (n)-{\tau }_{avg}}{{\tau }_m-{\tau }_{avg}}\right)}^2,\hfill & \hfill \text{when}\tau (n)\ge {\tau }_{avg}\hfill \\ \hfill 0.5\times {\left(\frac{\tau (n)}{{\tau }_{avg}}\right)}^2,\hfill & \hfill \text{others}\hfill \end{array}\hspace{0.17em}\hspace{0.17em}$$(15)

Where τ _m  and τ _avg is the maximum and average throughput of the current generation chromosomes.

The fitness function has the following properties:(1) The range of fitness is (0,1];(2) The fitness of the maximum throughput is 1. And the fitness of average throughput is 0.5 ;( 3) The closer to the optimal value, the more sensitive the fitness changes, while below the average value, the fitness decline is faster.

The advantages of the algorithm are: the individuals with lower fitness value are eliminated as soon as possible in the initial stage of the algorithm; the fitness distance of the points near the optimal solution is effectively widened in the later stage of the algorithm to avoid falling into the suboptimal solution.

2) Chromosome replication

When replication is performed, chromosomes n enter the next generation population with probability $\frac{Fit(n)}{{\displaystyle \sum _i}Fit(i)}$

3) Chromosome crossover

The classical crossover operator of genetic algorithm is to select two chromosomes, select a crossover bit i randomly, and then the two chromosomes correspond to each other to exchange the segment from i + 1 to the last.

For this problem, because the chromosomes represent the positions of multiple UAV nodes in segments, if the crossover bits are selected randomly, the representation of UAV nodes corresponding to crossover bits may be wrong.

For example, if the segments of V₃ in chromosome are “001” and “100”, and if the crossover point is 2, then the crossover segments are “000” and “101”, and “101” is invalid gene.

In order to avoid this situation, the classical genetic algorithm is improved, and the crossover position is defined as the connection point of each gene segment, That is to say, the possible crossover site is $\left\{{\displaystyle \sum _{i=0}^j}L(Code(i)),j=\mathrm{0,1,...},n-1\right\}$, So as to ensure the integrity of each gene segment.

4) Chromosome mutation operation

The above crossover operations cannot generate new positions, that is to say, all possible positions cannot be searched. Therefore, mutation operation is used to complete.

The classical mutation operators generate random variation bits on chromosomes, that is, the corresponding bits are reversed. If used directly, it will also produce invalid genes. For segment “100”, if 2 or 3 mutation sites are selected, invalid genes will be produced. In order to avoid this situation, the mutation operator adds the gene health test on the basis of the classical mutation operator. If the invalid gene appears, the classical gene operator is repeated until the generated gene is legal.

(3) Termination criteria

The termination criterion can be expressed as the maximum generation of algorithm execution. For this problem, the maximum throughput is the sum of the traffic demand of each user, that is ${\displaystyle \sum _i}{\displaystyle \sum _j}{f}_{ij}$. If the throughput of location optimization reaches this value, the optimization can be finished; another condition is that the system cannot meet the user's traffic demand. At this time, if the maximum optimized throughput has not been significantly improved, the iteration can be terminated and the current throughput value can be output as the optimization result of the problem.

To sum up, the algorithm can be represented by pseudo code such as Algorithm 1. Firstly, the grid of the area is generated; The second line generates the optional position P _o (i) of UAV node i for optimal selection; In line 6, a position is selected randomly in P _o (i) as the realization of the corresponding UAV position optimization; Line 8 uses string concatenation to get a chromosome Code(i), multiple chromosomes were obtained by cycling to form the initial population; The line 10 is the termination condition of genetic algorithm, where ${\displaystyle \overline{{\tau }_m}}$ represents the average value of the maximum throughput of recent generations, and $\left|{\tau }_m-{\displaystyle \overline{{\tau }_m}}\right|\ge \delta$ indicates that the difference between the current throughput and the average maximum throughput is greater than a certain amount; Line 11 is to calculate the fitness of each chromosome in the current population; Lines 12-14 perform chromosome operation according to the genetic operator mentioned above; The maximum throughput value of the current evolution population is obtained in line 15; Line 18 is to decode the value of the maximum throughput after the evolution, so as to get the position of the corresponding UAV. The optimized location can be sent to each UAV through the data link, and the flight control system performs the corresponding operation to control the UAV to the target location, so as to achieve the maximum network throughput.

Fig. 7 Schematic diagram of genetic code.

5 Simulation results and analysis

The simulation is carried out with MATLAB GA toolbox. Firstly, the location of communication users in the suburb region and the traffic demand of users are generated, and then the UAV node location is generated according to the above algorithm, so that the generated graph is connected.

The height of the UAV is maintained at 200 m. The transmission power of UAV to UAV Communication is 2W, while the transmission distance R _V2V of UAV to UAV Communication is maintained at 500 m. This means that if any two drones are within 500 m of each other, there can be a connection between them. The transmission power of UAV to user communication is 1W, while the transmission distance R _V2C of UAV to user communication is kept at 250 m. In order to estimate the throughput of the link, SNR is estimated based on the channel model and distance between transmit and receive. Then, use Table 2 to calculate the appropriate throughput value. For the parameters of genetic algorithm, the population size is 100, the replication probability is 0.4, the crossover probability is 0.4, and the mutation probability is 0.2.

The simulation is carried out from the aspects of verifying the algorithm effect and the influence of two radius PRC and PRS.

5.1 Influence of UAV position on network throughput

Table 6 shows the details of the four flows (RPC is 200 m and RPS is 30 m). Figure 8a shows the initial and final (determined by algorithm) positions of the UAV. With the initial position of the UAV, none of the traffic demands are met. However, with the determination of UAV's final position, the demands of flow 2 and flow 3 are fully met, and the throughput of flow 1 and flow 4 increases.

Figure 8b shows how the algorithm works by iteration. The maximum total throughput is achieved at generation 30. In generation 5, the requirements of flow 3 are met. In addition, since flow 1 and flow 4 share a bottleneck link (that is link V₂ V₃), their throughput is the same in most cases. However, at the late stage of evolution, the throughput of flow 4 is slightly higher than that of flow 1. This happens when UAV 3 is close to UAV 2. In the 34 generations of evolution, the demands of flow 4 were met (7 Mbps), The throughput of flow 1 increases slightly, while that of flow 2 drops sharply. The sharp decrease of throughput of flow 2 is caused by the decrease of link V₂ V₃ capacity. Therefore, at this point, flow 1 and flow 4 are competing with flow 2 for the position of UAV 3. Flow 1 and flow 4 want UAV 3 to be closer to UAV 2, while flow 2 wants UAV 3 to be closer to UAV 4. In the end, flow 2 wins because it can improve the throughput of the whole network more obviously.

Fig. 8 Influence of UAV position on network throughput. (a) position. (b) throughput.

5.2 Influence of Radius of Position Constraint (RPC)

Table 7 shows the details of the four flows. Note that throughput may be further improved with the increase of Radius of Position Constraint (RPC). This is because more UAV positions can be tested to improve throughput as the RPC increases. Figure 9 shows how the RPC affects throughput improvement.

In the initial evolution process, the algorithm gains similar throughput for all RPC. However, in the 10th evolution, the throughput with RPC 100 m fell behind RPC 150 and 200 m. Similarly, in the 14th evolution, the throughput with RPC 150 m fell behind RPC 200 m radius 150 m fell behind 200 m. This is because the smaller the RPC, the more restricted the maneuverability of UAV. When the RPC is 100 m, the reachable position of UAV is a subset of the reachable positions at 150 and 200 m. Therefore, in the 10th generation of evolution, the algorithm tries to locate at RPC 150 and 200 m, which leads to performance improvement. However, these locations are not suitable for the RPC 100 m case because they fall outside the RPC. Similarly, in iteration 13, the algorithm attempts a position with RPC 200 m, which cannot be used in a RPC with 150 m. Therefore, when the radius of RPC is large, the throughput improvement can be greater than that of the smaller radius.

Fig. 9 Influence of RPC.

5.3 Influence of Radius of Particle Size (RPS)

Figure 10 shows the effect of RPS when the algorithm searches (approximately) the optimal UAV location. In the initial generation, larger RPS will lead to a sharp increase in throughput; Later, throughput with the smaller RPS will gradually increase. When the RPS is large, the convergence speed of the algorithm is faster. But in general, the determined solution is not as close to the optimal solution as the RPS is small. The smaller the RPS is, the slower the convergence speed of the algorithm get, but the closer the determined solution is to the optimal solution.

Fig. 10 Influence of RPS.

6 Conclusion

Throughput is an important network performance metric. The distance between the sender and the receiver can affect the throughput. For FANET, because the position of UAV can be moved, the distance between two nodes can be adjusted, and then the capacity of corresponding link can be optimized to improve the network throughput.

In this paper, a mathematical model of throughput optimization of UAV ad hoc network is constructed, and an algorithm based on genetic algorithm is proposed to control the position of UAV, optimize the topology of FANET, and then maximize the throughput. The proposed algorithm is simulated and analyzed by MATLAB. The results show that the average throughput can reach the expected goal by controlling the network topology, and the optimization speed is related to the RPC and the RPS. Throughput may be further improved with the increase of RPC. The smaller the RPS is, the slower the convergence speed of the algorithm get, but the closer the determined solution is to the optimal solution.

The algorithm proposed in this paper can be deployed in the actual network, specifically in the ground station. The link between UAVs can use IEEE 802.11 or LTE technology, and Each UAV is equipped with multiple interfaces and each interface uses a channel that is not used by any of its neighbors to ensure that the channels do not affect each other as much as possible. Each UAV sends its own position and user's location information to the ground station, which uses the current position information of all UAVs to estimate SNR, According to Table 2, the throughput capacity of the wireless link between UAVs is estimated, and then the position is optimized according to the algorithm, and the results are sent back to each UAV. The flight control of each UAV controls itself to the optimized position, so as to optimize the throughput of the whole network.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (Grant No. 61801435), the Scientific and Technological Key Project of Henan Province (Grant No. 202102210325, Grant No. 202102210326), and the Key Scientific Research Project of Colleges and Universities in Henan province plan (Grant No. 21B510011, Grant No. 21A510013).

References

All Tables

All Figures

	Fig. 1 Flying ad hoc network (FANET).
In the text

	Fig. 2 FANET service areas.
In the text

	Fig. 3 UAV Position affects the throughput. (a) Position before optimization. (b) Position after optimization.
In the text

	Fig. 4 User selection affects the throughput.
In the text

	Fig. 5 Regional grid diagram of FANET.
In the text

	Fig. 6 The Radius of Position Constraint (RPC).
In the text

	Fig. 7 Schematic diagram of genetic code.
In the text

	Fig. 8 Influence of UAV position on network throughput. (a) position. (b) throughput.
In the text

	Fig. 9 Influence of RPC.
In the text

	Fig. 10 Influence of RPS.
In the text