Issue 
Int. J. Metrol. Qual. Eng.
Volume 11, 2020



Article Number  11  
Number of page(s)  13  
DOI  https://doi.org/10.1051/ijmqe/2020012  
Published online  13 November 2020 
Research Article
Throughput optimization for flying ad hoc network based on position control using genetic algorithm
^{1}
School of Intelligent Engineering, Zhengzhou University of Aeronautics, Zhengzhou, PR China
^{2}
Department of Technology, Zhengzhou University of Aeronautics, Zhengzhou, PR China
^{*} Corresponding author: liujianqiang@qq.com; liujq@zua.edu.cn
Received:
23
August
2020
Accepted:
23
October
2020
In some complex applications, Flying Ad Hoc Network (FANET) can provide important support for multi UAV (Unmanned Aerial Vehicle) cooperation. In FANET each UAV is equivalent to a router, and the wireless link between them forms a network to achieve the purpose of relay communication. Throughput is an important network performance, and the position of UAV nodes affects it. In this paper, we analyze the influencing factors of FANET throughput with UAV position and terminator selection in first; Secondly we construct the mathematical model of throughput optimization of FANET; Thirdly we propose an algorithm based on genetic algorithm to optimize the position of UAV, and then maximize the throughput. Preparing for using genetic algorithm, we design the related details: Numbering Area, Determining the adjacency matrix and correlation matrix, determining the range of UAV node position movement. The key points of the genetic algorithm for FANET is proposed include the following aspects: coding and population initialization, fitness function, and chromosome replication/crossover/mutation and termination criteria. At last, Matlab is used to simulate the proposed algorithm from three aspects: performance, effect of Radius of Position Constraint (RPC) and effect of Radius of Particle Size (RPS). The results show that the throughput can reach the expected goal by controlling the UAV position, and the optimization speed is related to the RPC and RPS.
Key words: UAV / FANET / throughput / position control / genetic algorithm
© J. Liu et al., published by EDP Sciences, 2020
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
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 realtime 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 highperformance 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 straightline 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 SignaltoNoise 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 groundtorelay links through control of the UAV heading angle. Dixon [16] proposed a decentralized mobility control algorithm for an optimal endtoend 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 closedform expression for capacity, which can be used to determine optimal locations for UAVs. BorYaliniz [18] considered the locations of the radio access network elements are determined mainly based on the longterm traffic behavior and proposed a multitier dronecell 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 highquality 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 gatewayselection algorithms and cloudbased stabilitycontrol 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 UAVserved 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 clusterbased control plane messages management in softwaredefined flying adhoc Network. Based on UAV contextual information, the controller can predict UAV information without control message transmission.
Different names.
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 selforganization. By optimizing the position of UAV nodes, the total throughput of the network is maximized. Figure 2b is a twodimensional 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 signaltonoise 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\mathrm{log}(f)+20\mathrm{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_{1} V_{3}, so the flow 3 uses the remaining capacity 3 of link V_{1} V_{3}. 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_{1} V_{3}, V_{2} V_{3} and V_{1} C_{2}, and, the demands of flow 3 cannot be met. On the other hand, the capacity of the link V_{3} V_{4} is larger than the demand on the link. Therefore, by optimization the position of UAV, the capacity of link V_{1} V_{3} and V_{2} V_{3} 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_{3} is approaching the UAV V_{1} and V_{2}. Similarly, UAV V_{1} and V_{2} also approach UAV V_{3}. In addition, with the new positioning, the UAV V_{1} is closer to the user C_{2}, thus increasing the capacity of link V_{1} C_{2}. At this time, the capacity of links V_{2} V_{3}, V_{1} V_{3} and V_{1} C_{2} is large enough to support their service demands. Similarly, the UAV V_{4} has moved to the left (to compensate for the movement of UAV V_{3}) to maintain sufficient capacity for links V_{3} V_{4}, V_{4} C_{7} and V_{4} C_{8}. Although the capacity of link V_{1} V_{2} 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_{2} 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.
Relationship between link capacity and received signal strength.
Fig. 3 UAV Position affects the throughput. (a) Position before optimization. (b) Position after optimization. 
Throughput affected by distance.
Fig. 4 User selection affects the throughput. 
Throughput affected by user selection.
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 threedimensional space. However, for the sake of convenience, we will describe it in twodimensional 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 twodimensional plane and in threedimensional 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{\hspace{1em}}\text{where}\text{\hspace{0.17em}}{a}_{u,v}=\{\begin{array}{l}0,\text{\hspace{1em}}\text{If}\text{\hspace{0.17em}}\text{no}\text{\hspace{0.17em}}\text{link}\text{\hspace{0.17em}}\text{between}\text{\hspace{0.17em}}u\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}v\hfill \\ 1,\text{\hspace{1em}}\text{If}\text{\hspace{0.17em}}\text{link}\text{\hspace{0.17em}}\text{between}\text{\hspace{0.17em}}u\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}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\mathrm{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 multiuser multi input multiple output (MUMIMO) 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{\hspace{1em}}\text{If}\text{\hspace{0.17em}}\text{the}\text{\hspace{0.17em}}\text{user}\text{\hspace{0.17em}}v\text{\hspace{0.17em}}\text{accessing}\text{\hspace{0.17em}}\text{the}\text{\hspace{0.17em}}\text{network}\text{\hspace{0.17em}}\text{does}\text{\hspace{0.17em}}\text{not}\text{\hspace{0.17em}}\text{through}\text{\hspace{0.17em}}\text{UAV}\text{\hspace{0.17em}}u\hfill \\ 1,\text{\hspace{1em}}\text{If}\text{\hspace{0.17em}}\text{the}\text{\hspace{0.17em}}\text{user}\text{\hspace{0.17em}}v\text{\hspace{0.17em}}\text{accessing}\text{\hspace{0.17em}}\text{the}\text{\hspace{0.17em}}\text{network}\text{\hspace{0.17em}}\text{through}\text{\hspace{0.17em}}\text{UAV}\text{\hspace{0.17em}}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\mathrm{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}}{\mathrm{min}}}({c}_{l,(i,j)})$$(9)
The throughput achieved by the flow (i, j) is recorded as τ_{ ij }, and$${\tau}_{ij}=\mathrm{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 $$\mathrm{max}mize{\displaystyle \sum _{i=1}^{m}}{\displaystyle \sum _{j=i}^{m}}{\tau}_{ij}$$(11a) $$\begin{array}{l}S.t.\text{\hspace{1em}}S(V,C,T)\\ \text{\hspace{1em}}\text{\hspace{1em}}{d}_{u,v}=distance({p}_{u},{p}_{v})\le {R}_{V2V},\forall u\in V,\exists v\in V\\ \text{\hspace{1em}}\text{\hspace{1em}}{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_{1}, V_{2}, V_{3}, V_{4} 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 selforganizing 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 minp_{ 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}^{*}=\mathrm{arg}\mathrm{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_{3} as an example. Take its neighbor UAV nodes V_{1}, V_{2} and V_{4} as the center of the circle, make the circle with the radiusR_{ V } less than R_{ V2V };Take its user node C_{6} 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_{3}, 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_{3} are {17, 30, 37, 43, 50}, and there are five optional positions, which can be encoded by 3bit 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}\text{\hspace{0.17em}}\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_{3} 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,...},n1\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 $\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 $\stackrel{\u203e}{{\tau}_{m}}$ represents the average value of the maximum throughput of recent generations, and $\left{\tau}_{m}{\displaystyle \stackrel{\u203e}{{\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 1214 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. 
Genetic code of node position.
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_{2} V_{3}), 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_{2} V_{3} 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.
Throughput optimization statistics.
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.
Statistics of throughput with different RPC.
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
 W. Zafar, B.M. Khan, IEEE Technol. Soc. Mag. 35, 67–74 (2016) [CrossRef] [Google Scholar]
 K.O. Sahingoz, J. Intell. Robot. Syst. 74, 513–527 (2014) [Google Scholar]
 A. Bujari, C.E. Palazzi, D. Ronzani. FANET application scenarios and mobility models, in: Workshop on Micro Aerial Vehicle Networks (ACM, 2017) [Google Scholar]
 K. Kwak, Y. Sagduyu, J. Yackoski et al. Mag. IEEE 52, 30–36 (2014) [CrossRef] [Google Scholar]
 Y. Wang, T. Sun, G. Rao et al. IEEE J. Selected Areas Commun. 36, 1 (2018) [CrossRef] [Google Scholar]
 F.A. Aloul, N. Kandasamy, Sensor deployment for failure diagnosis in networked aerial robots: a satisfiabilitybased approach, in: SAT 2007. LNCS. vol. 4501, pp. 369– 376 [Google Scholar]
 R. Shirani, M. StHilaire, T. Kunz, Y. Zhou, J. Li, L. Lamont, Combined reactivegeographic routing for unmanned aeronautical adhoc networks, in: 8th International Wireless Communications and Mobile Computing Conference (IWCMC, 2012), pp. 820–826 [Google Scholar]
 Y. Cai, F.R. Yu, J. Li, Y. Zhou, L. Lamont, IEEE Trans. Veh. Tech. 62, 390–394 (2013) [CrossRef] [Google Scholar]
 A.I. Alshabtat, L. Dong, J. Li et al. Int. J. Electric. Comput. Eng. 6, 48–54 (2010) [Google Scholar]
 L. Reynaud, T. Rasheed, Deployable aerial communication networks: challenges for futuristic applications, in: Proceedings of the 9th ACM Symposium on Performance Evaluation of Wireless AdHoc, Sensor, and Ubiquitous Networks, 2012, pp. 9–16 [CrossRef] [Google Scholar]
 P.B. Bök, Y. Tuchelmann, Contextaware QoS control for wireless mesh networks of UAVs, in: International Conference Computer Communications and Networks (ICCCN), 2011, pp. 1–6 [Google Scholar]
 S. Rohde, N. Goddemeier, K. Daniel, C. Wietfeld, Link quality dependent mobility strategies for distributed aerial sensor networks, in: GLOBECOM Workshops, 2010, pp. 1783–1787 [Google Scholar]
 I. Bekmezci, O.K. Sahingoz, S. Temel, Ad Hoc Netw. 11, 1254–1270 (2013) [Google Scholar]
 E. Yanmaz, S. Yahyanejad, B. Rinner et al. Ad Hoc Netw. 68 (2017) [Google Scholar]
 P. Zhan, K. Yu, A.L. Swindlehurst, IEEE Trans. Aerosp. Electron. Syst. 47, 2068–2085 (2011) [Google Scholar]
 C. Dixon, E.W. Frew, IEEE J. Selected Areas Commun. 30, 883–898 (2012) [CrossRef] [Google Scholar]
 W. Guo, T. O'Farrell, IEEE J. Selected Areas Commun. 31, 1–10 (2013) [CrossRef] [Google Scholar]
 H. Yanikomeroglu, I. BorYaliniz, The new frontier in RAN heterogeneity: multitier dronecells. IEEE Commun. Mag. Articles News & Events Interest Commun. Eng. (2016) [Google Scholar]
 D. Rosário, J.A. Filho, D. Rosário et al. A relay placement mechanism based on UAV mobility for satisfactory video transmissions, in: Ad Hoc Networking Workshop (IEEE, 2017) [Google Scholar]
 Y. Gao, L. Dai, X. Hei, IEEE Trans. Commun. 65, 3399–3414 (2017) [Google Scholar]
 J. Wang, C. Jiang, Z. Han et al. IEEE Veh. Technol. Mag. 12, 73–82 (2017) [CrossRef] [Google Scholar]
 F. Cheng, S. Zhang, Z. Li et al. IEEE Trans. Veh. Technol. 67, 6732–6736 (2018) [Google Scholar]
 P. Cumino, K. Maciel, T. Tavares et al. Sensors 20, 67 (2019) [CrossRef] [Google Scholar]
 J. Yee, H. PezeshkiEsfahani, Commun. Syst. Des. 8, 32–35 (2002) [Google Scholar]
 A. Hourani, S. Kandeepan, A. Jamalipour, Modeling airtoground path loss for low altitude platforms in urban environments, in: Global Communications Conference (IEEE, 2015) [Google Scholar]
 A. AlHourani, S. Kandeepan, S. Lardner, Wireless Commun. Lett. IEEE 3, 569–572 (2014) [CrossRef] [Google Scholar]
 H.S. Bin Obaid, T.B. Trafalis, An approximation to max min fairness in multi commodity networks. Computat. Manag. Sci. (2018) [Google Scholar]
 J. Horn, A niched Pareto genetic algorithm for multiobjective optimization, in: Proceedings of the First IEEE Conference on Evolutionary Computation, 1994 [Google Scholar]
 H. Wang, Y. Yu, Q. Yuan, Application of Dijkstra algorithm in robot pathplanning, in: International Conference on Mechanic Automation & Control Engineering (IEEE, 2011) [Google Scholar]
Cite this article as: Jianqiang Liu, Shuai Huo, Yi Wang, Throughput optimization for flying ad hoc network based on position control using genetic algorithm, Int. J. Metrol. Qual. Eng. 11, 11 (2020)
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 
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.