An optimization routing protocol for FANETs

Abstract

With the wide-ranging application of mobile ad hoc networks, flying ad hoc networks (FANETs) have received more and more attention from the industry. Routing technology is a key technology of ad hoc networks. The high-speed mobility of nodes poses a greater challenge to FANET routing technology. Based on the Dynamic Source Routing (DSR) protocol, the continuous Hopfield neural network is used to optimize the route to be adapted to the high-speed movement of the FANET node. In a simulation using NS3, the result shows that the optimized DSR protocol has greatly improved key indicators such as end-to-end average delay, throughput, and packet delivery ratio.

1 Introduction

In the past, mobile ad hoc networks (MANETs) had been applied more and more, and have expanded into the air to form flying ad hoc networks (FANETs) [1]. As an improved mobile ad hoc network, FANETs use the aircraft as a node for transmitting, receiving, or forwarding over the air wireless communication. It can set up a network at any time and any place without any fixed facilities and realize a multi-aircraft system. The network layer is effective communication. The FANETs have the commonality of traditional MANETs, such as no center, multi-hop, self-organization, and self-healing, but are also given their specific design goals and network characteristics. The characteristics of the aircraft nodes are fast, maneuverable, and complex in the flight environment and the high degree of confrontation. It will lead to restricted bandwidth of the communication transmission link, frequent switching changes, and high error rate. The network topology has dedicated time-varying and significant dynamic, so FANET routing design is also more difficult and at the same time very challenging.

Routing protocols [1,2,3,4,5,6] have always been the core technology in various types of wired networks and wireless networks, and are also research hotspots. For the highly dynamic FANETs, the strong mobility of a node may easily lead to route breaks, which will trigger routing updates frequently, generate a large amount of control overhead in the network, cause route convergence difficulties, increase data forwarding delay, and increase packet loss rate, and even the routing protocol is invalid. In order to realize reliable and effective networking of high dynamic nodes, routing protocols are one of the key issues that need to be solved in FANETs. The same as the MANET routing, the FANET routing protocol should also have the ability to self-organize and self-heal. At the same time, the FANET routing protocol also needs to adapt to frequent changes in the network topology brought by the high-speed movement of nodes. Compared with MANETs, nodes in FANETs have higher moving speed, and their routing is the most likely to break in the communication process. Although the traditional meaning of MANETs’ routing also considers the moving speed of nodes, it cannot be directly transplanted to FANETs with high moving speed. In the meantime, it is necessary to ensure the corresponding improvements or redesigns in conjunction with the actual situation of FANETs.

2 Related work

2.1 Overview of FANET routing protocol

At present, the industry does not have a proprietary routing protocol for FANET, and its main routing protocol still uses the routing protocol of MANETs. MANET routing protocols [7,8,9,10] can be divided into different types according to different classification criteria. According to the route discovery strategy, it is divided into reactive routing, proactive routing, and hybrid routing.

2.1.1 Reactive routing

This type of routing protocol creates a route only when the source node needs to communicate, and does not need to maintain the routing information of all nodes in real time like a table-driven routing protocol. Therefore, such routes are known as on-demand routing protocols. This type of routing protocol has poor stability in highly dynamic networks and is also less secure, for example, Dynamic Source Routing (DSR) [11,12,13] and ad hoc on-demand distance vector (AODV) [11, 14, 15].

2.1.2 Proactive routing

According to the characteristics of MANET, based on the wired network routing protocol, all nodes maintain a routing table that contains routing information from this node to other nodes. When the network topology changes, the node maintains the routing table updated by exchanging routing information, so the routing table can accurately reflect the network topology information. Because of FANETs, high-speed movement of nodes causes network topology to change very frequently, such routes are not suitable for use in FANETs, for example, Optimized Link State Routing Protocol (OLSR) [11, 16, 17] and Destination-Sequenced Distance Vector (DSDV) [11, 18].

2.1.3 Hybrid routing

This type of routing algorithm uses both active routing and on-demand routing. It divides the network into domains and uses active routing and reactive routing policies within and between domains, for example, Zone Routing Protocol (ZRP) [11, 19].

In the above main routing protocols, the DSR has low overhead and rapid response to network topology changes and can provide fast response services to ensure that data packets can successfully reach the destination node. Therefore, it is more suitable for FANETs with fast node movement and strong topological changes. Based on the DSR, it is optimized based on CHNN, and the expected route is more suitable for FANETs, thereby improving the performance of FANETs.

2.2 DSR protocol

DSR [12] is a topology-based reactive routing protocol that uses active caching strategies and extracts topology information from source routes. The node can obtain the route to all the downstream nodes from the datagram header and can also derive more topology information by combining multiple pieces of information. In addition, in the network interface mode of the setup node, by listening to the route used by the neighbor node, it is possible to obtain more topology information, and more and more network topology information is stored in the cache to improve the cache hit rate of the route lookup. So, it can reduce the frequency of routing discovery process and save network bandwidth. DSR mainly includes route discovery and route maintenance.

2.2.1 Route discovery

When the communication node needs to transmit packet data, the route discovery process checks whether the node itself contains the destination and routing information for the initialization data. If it has, the route is initiated to establish a connection. Else, the route is initiated to establish a flood routing the request to determine whether the destination node exists. If it exists, the routing response is sent. The source node receives the response to establish a connection. If there is no destination node, it determines whether the routing information to the destination node is cached. If sure, routing response is sent, and the source node receives the response to establish a connection. Else, it determines whether the maximum hop count reached restrict, and then return to search again. If the limit reached, the route fails to establish a connection. When the routing connection is interrupted, the node will send an error packet to the source and the notice in reverse. At this point, the route discovery process is completed.

2.2.2 Route maintenance

After the route is established using the route discovery, a routing table will exist in the source node, and the data transmission will be performed according to the routing table. During the process of transmitting the data, the established route has to be maintained to be continuously available. By maintaining the routing table, the source node can monitor the network topology and discover changes in the network topology in time to determine whether the route to the destination node is continuously available. When a node in the network detects a route break, the node will send a route error packet, and the node who receives the error packet then caches it and deletes the route information. If the source node in a communication receives a route error packet, it deletes the route and the route discovery process is started.

2.3 Hopfield neural networks

The Hopfield neural networks [20,21,22,23,24] is a recurrent neural network, proposed by John Hopfield in 1982. It is a neural network that combines storage systems and binary systems. The Hopfield neural network is called the Hopfield neural network model, also known as the Hopfield model is a cyclic neural network with feedback connection from the output to the input. According to the different activation function selection, it can be divided into continuous Hopfield neural network (CHNN) and discrete Hopfield neural network (DHNN).

CHNN mainly solves the combinatorial optimization problem; Hopfield and Tank realize that with this basic neural network organization form, by selecting the weights and external inputs that can properly represent the function to be minimized and the desired state, it is possible to calculate the specific solution and the method of optimizing the problem. Updating neurons based on differential equations ensures that energy functions and optimization problems can be minimized at the same time. The analog nature of the neurons and the hardware implementation of the update process can be combined to create a fast and powerful solution. The key to solving various combinatorial optimization problems with neural networks is to map the problem into a neural network dynamic system and to write the corresponding energy function expressions and dynamic equations. They should satisfy the constraints of the problem. Finally, the neural network is studied. The dynamic process ensures that the steady-state output of the network corresponds to the minimum value of the energy function and the solution to the combinatorial optimization problem.

The features of the Hopfield neural network are as follows:

• (1) All neurons are both an input and an output, forming a single-layer fully connected recursive network.

• (2) The synaptic weight of the network is different from other neural networks obtained through supervised or unsupervised iterative learning, but is calculated according to certain rules when building the network, and the weight of the network is iterated throughout the network. No longer changing in the process.

• (3) The state of the network changes with time, and the output state of each neuron at time t is related to its own t-1 time.

• (4) Introduce the concept of energy function to judge the stability of network iteration, that is, the convergence of the network, that is, the energy function reaches a minimum value.

• (5) The solution of the network, that is, the state set of each neuron when the network runs to stability.

The circuit topology structure of CHNN is shown in Fig. 1, where U_i represents the input voltage of the electronic amplifying component, V_i represents the output voltage, and operational amplifier i represents the ith neuron.

Fig. 1

CHNN circuit topology. Hopfield neural network equivalent to amplifying electronic circuits. Input information of each electronic component (neuron), including constant external current input, and feedback connection with other electronic components

Its state equation is

$$ {C}_i\frac{du_i}{dt}=\sum \limits_{j=1}^n{T}_{ij}{v}_j-\sum \limits_{j=1}^n{T}_{ij}{u}_j-{T}_{i_0}{u}_i+{I}_i $$

(1)

$$ {C}_i\frac{du_i}{dt}=\sum \limits_{j=1}^n{T}_{ij}{v}_j-\sum \limits_{j=1}^n{T}_{ij}{u}_j-{T}_{i_0}{u}_i+{I}_i $$

(2)

where the input voltage v_i satisfies the nonlinear mapping rule f:

$$ {v}_i={f}_i\left({u}_i\right) $$

(3)

CHNN uses the energy function to measure the stability of the network, which is defined as:

$$ E=\frac{1}{2}\sum \limits_{i=1}^n\sum \limits_{j=1}^n{T}_{ij}{v}_{xi}{v}_{xj}+\sum \limits_{j=1}^n{v}_i{I}_i+\sum \limits_{i=1}^n\frac{1}{R_i}{\int}_0^{u_i}{f}^{-1}\left({v}_i\right){d}_{v_i} $$

(4)

3 Optimization method

3.1 Routing metric

Routing performance directly determines the performance of FANETs, and routing metrics directly determine the performance of the route. In ad hoc networks, due to frequent changes in the topology, the routing protocol usually considers that there are routes for communication, and does not consider the quality of the route. Therefore, the minimum hop becomes the main route metric. However, the hop count does not directly reflect the quality of the route. The result is that the hop count is the smallest, but the performance of the route is the worst.

In order to make the design of routing metric reflect the quality of routing, in the design of routing metric, we cannot rely solely on hop, link capacity, link stability, node energy, node performance, interference, node power, and other link and node factors; all need to be included. If the communication route only contains the hop count and does not consider other factors such as link stability, it is easy to cause the route to be broken due to frequent changes in the topology, causing the network to generate a high retransmission rate and causing high delay of the network, resulting in some nodes. The energy is consumed unnecessarily, which in turn affects the performance and longevity of the network. A reliable route is often determined by the stability of the link in ad hoc networks, so the design of the routing metric need to fully consider the stability of the link.

3.2 Definition of link stability

Let i and j be any two adjacent nodes in the network, and D is its communication distance. Assuming that the nodes are of the same type, the transmit power is the same, which also determines the effective communication range (set to D₀). Let the stability of the link between nodes be represented by S_ij, which is related to the effective range of communication and the distance between nodes, as defined below.

$$ {S}_{ij}=\left\{\begin{array}{c}0,D\ge {D}_0\\ {}1-\frac{D}{D_0},0\le D<{D}_0\end{array}\right. $$

(5)

When D is greater than or equal to D₀, the nodes cannot communicate directly, and S_ij is 0. Conversely, nodes can communicate directly, with S_ij between 0 and 1. Link stability prediction is based on the wireless propagation model. The wireless propagation model reveals the relationship between radio wave transmit power, received power, and propagation distance. When the two wireless nodes are in a very close position, the Friis model is closer to the actual situation. The two-ray model is more applicable when the two wireless nodes are farther away. In general, the nodes of wireless communication are far apart, so the two-ray model is used.

$$ {P}_r=\frac{P_i{G}_i{G}_r{\left({h}_i{h}_r\right)}^2}{D^4} $$

(6)

In the formula, P_i represents the transmission power, P_r represents the received power, G_i represents the transmit antenna gain, G_r represents the receive antenna gain, h_i represents the transmit antenna height, and h_r represents the receive antenna height. It has been set that P_i is a constant, and assuming that the node uses a directional antenna, G_iG(_rh_ih)² is a constant expressed in k₁. Thus, D can be obtained by the transformation of Eq. (6):

$$ D=4\sqrt{\frac{k_1{P}_i}{P_r}} $$

(7)

Let the lowest received power of the node be P₁, and the corresponding distance is the node effective communication range D₀, then k₁P_i = P₁D₀⁴ can be obtained from Eq. 3, and the calculated distance D can be obtained by substituting into Eq. (7):

$$ D=4\sqrt{\frac{P_1}{P_r}}{D}_0 $$

(8)

Finally, substituting Eq. (8) into Eq. (5) yields the calculated link stability S_ij.

$$ {\mathrm{S}}_{ij}=\left\{\begin{array}{c}0,D\ge {D}_0\\ {}1-4\sqrt{\frac{P_1}{P_r}}{D}_0,0\le D<{D}_0\end{array}\right. $$

(9)

3.3 Optimization method

Whether in MANETs or FANETs, routing finds an optimized source-to-destination communication path in a set of wireless nodes {N₁, N₂,...N_n}. In order to map routing problems to the dynamic evolution of a neural network, we must first find a suitable representation. The FANET network node is mapped to the CHNN, and the optimal route is searched through the dynamic evolution of the neural network state. When the network state tends to be stable, the obtained route is the optimal route or the suboptimal route. The search time of the neural network is the time when the state of the neural network reaches a stable state, and the calculation process is also the dynamic process of the neural network. So the key to solving the problem is to construct a suitable neural network energy function.

In order to optimize the CHNN routing of the FANET, the appropriate expression of the route must be found first. A route is an ordered arrangement, which has a source node, some of the intermediate nodes, and the destination node; the intermediate nodes can be represented in the form of n-dimensional vectors. In FANET, there have n intermediate nodes, and the required vector dimension is n − 2, such as there is a matrix representation of 5 intermediate nodes (Fig. 2). In Fig. 2, the only route is shown: Source - > N₄ - > N₂ - > N₃ - > N₁ - > N₅ - > Destination. For every possible route, every intermediate node can only reach once, so each row and column in this square can only have one element with 1 and the remaining elements with 0. This is the constraint of the routing problem. Every route with the above constraints can be represented by a transposition matrix. So, the first two terms of the energy function are set to

$$ g(V)=\frac{Q}{2}\sum \limits_{\begin{array}{c}m\\ {}\mathrm{m}\ne \mathrm{n}\end{array}}\sum \limits_n\sum \limits_i{V}_{mi}{V}_{ni}+\frac{S}{2}\sum \limits_m\sum \limits_j\sum \limits_{\begin{array}{c}i\\ {}i\ne j\end{array}}{V}_{mi}{V}_{mj} $$

(10)

Fig. 2

Use matrix to represent five nodes FANET routing. Use matrix to represent five nodes FANET routing; the only route is shown: Source - > N4 - > N2 - > N3 - > N1 - > N5 - > Destination

Using R_SD to represent the integrated distance from the node S to node D, the Fig. 2 total length of the route is

$$ {R}_{SD}={R}_{S4}+{R}_{42}+{R}_{23}+{R}_{31}+{R}_{15}+{R}_{5D} $$

(11)

For FANETs, routing cannot pass through each intermediate node. The size of the matrix must be set to an upper limit. When there are too many intermediate nodes, it is considered unreachable. Referring to the RIP routing protocol in the wired network, set to n = 16, the energy is the third function of the function is described as:

$$ h(V)=\frac{T}{2}{\left(\sum \limits_x\sum \limits_i{V}_{xi}-n\right)}^2 $$

(12)

In order to contain the effective solution route length information, the fourth term of the energy function is

$$ f(V)=\frac{\mathrm{P}}{2}\sum \limits_{\begin{array}{c}m\\ {}\mathrm{m}\ne \mathrm{n}\end{array}}\sum \limits_n\sum \limits_i{S}_{mn}{V}_{mi}\left({V}_{n\left(i+1\right)}+{V}_{n\left(i-1\right)}\right) $$

(13)

Therefore the total energy function can be expressed using the following equation:

$$ E=f(V)+h(V)+g(V) $$

(14)

The parameters Q, S, T, and P are called the weight, the first three items are the constraints that satisfy the route replacement matrix, and the last one contains the optimization objective function item.

In order to simplify the calculation, there is a need to ignore the integral subitem of the energy function, and then the neural network connection weight can be expressed as:

$$ {\displaystyle \begin{array}{c}{\upomega}_{mi, ni}=-S{\delta}_{mn}\left(1-{\delta}_{ij}\right)-Q{\delta}_{ij}\left(1-{\delta}_{mn}\right)-T\\ {}-P{S}_{mn}\left({\delta}_{j\left(i+1\right)}+{\delta}_{j\left(i-1\right)}\right)\end{array}} $$

(15)

The random item added is δ_ij ∈ {−1, 1} .

Calculate the increment of the input state using the CHNN dynamic equation:

$$ {\displaystyle \begin{array}{c}d{U}_{mi}=-S\sum \limits_{j\ne i}{V}_{mj}-\mathrm{Q}\sum \limits_{m\ne n}{V}_{nj}-T{\left(\sum \limits_m\sum \limits_j{V}_{mj}-16\right)}^2\\ {}-P\sum \limits_n{s}_{mn}\left({V}_{n\left(i+1\right)}+{V}_{n\left(i-1\right)}\right)-\frac{U_{mi}}{R_{mi}{C}_{mi}}\end{array}} $$

(16)

Update the output state of the neural network at the next moment by the sigmoid function:

$$ {V}_{mi}=f\left({U}_{mi}\right)=\frac{1}{2}\left[1+ th\left(\frac{U_{mi}}{U_0}\right)\right] $$

(17)

Penalty parameters S, Q, T, and P need to be fixed values. Hopfield [20] uses the set of parameters S = Q = P = 500, U₀ = 0.02 to balance these terms.

4 Simulation results and discussion

4.1 Simulation platform

In order to verify the effectiveness of CHNN-optimized routing, we simulated the FANET scenario to simulate the DSR and CHNN-DSR. We mainly analyze and compare the following parameters that determine routing performance [25, 26]:

• (1) Average end-to-end delay: Defined as the average of the packet delays for all successful delivery of the entire network. Its calculation formula is

$$ \mathrm{Delay}=\frac{1}{n}\sum \limits_{i=0}^{n-1}\left({p}_i\left({T}_{\mathrm{receive}}\right)-{p}_i\left({T}_{\mathrm{send}}\right)\right) $$

(18)

where p_i represents the ith packet and n indicates the total number of successfully delivered packets.

• (2) Packet delivery ratio: Defined as the number of packets accepted by the destination node and the number of packets transmitted by the constant bit rate (CBR) source. Its calculation formula is

$$ \mathrm{Delivery}\ \mathrm{Ratio}=\frac{\sum {\mathrm{Delivery}}_{\mathrm{Data}}}{\sum {\mathrm{Transmite}}_{\mathrm{Data}}} $$

(19)

• (3) Throughput: Defined as the average of the amount of data (kb/s) successfully delivered by each pair of communicating parties in the network per unit time.

4.2 Parameter settings

The simulation software uses the NS3 simulation system (https://www.nsnam.org/) [27]. The CHNN code is developed in C++ and can be directly applied to the NS3 system. When 30 nodes in the network start to simulate, they are evenly distributed in the area of 1000 m × 1000 m. The internode communication uses a CBR stream, and the data packet length is 1024 bytes. The MAC layer protocol uses IEEE 802.11 DCF. The transfer model uses Lucent’s WaveLan. The motion model adopts a random waypoint mobility model. The simulation runs for 900 s. See Table 1 for detailed settings.

Table 1 Network parameter setting

4.3 Results and discussion

In order to make the results more realistic, the simulation is performed multiple times and then the method of averaging is performed. Figures 3, 4, and 5 show the comparison of the average end-to-end delay, packet delivery ratio, and throughput of CHNN-DSR and DSR when the speed of the node movement increased. The results show that node mobility has a great impact on the routing in FANETs. In the case of high-speed mobility, the route interruption may occur very frequently. Therefore, the use of optimized routing in the route discovery process will effectively improve the stability of the network.

Fig. 3

Average end-to-end delay simulation results for DSR and CHNN-DSR. The simulation results of the average end-to-end delay for CHNN-DSR and DSR under the change of node movement speed

Fig. 4

Packet delivery ratio simulation results for DSR and CHNN-DSR. The simulation results of the packet delivery ratio for CHNN-DSR and DSR under the change of node movement speed

Fig. 5

Throughput simulation results for DSR and CHNN-DSR. The simulation results of the throughput for CHNN-DSR and DSR under the change of node movement speed

From Fig. 3, we can see that as the node moves faster, the average end-to-end delay increases. DSR uses source routing and storage routing, but the topology changes drastically cause source routing breaks and storage routes to failure. The risk is also increased, and CHNN-DSR uses optimized source routing, which has higher stability itself, so the probability of re-initiating route lookup is lower, and the communication quality is more secure.

From Fig. 4, we can see that as the node moves faster, the packet delivery ratio also decreases. The reason is that the route through CHNN-DSR is optimized and its stability is strong, so the packet delivery ratio can always be maintained at a higher ratio. It is worth noting that although the speed increases and packet delivery ratio decreases, the route delivery ratio of both routes is above 90%, indicating that DSR is still a better choice for FANETs.

From Fig. 5, we can see that as the node moves faster and the throughput performance is getting worse and worse. The optimized CHNN-DSR performance is obviously better than the DSR. This is because the DSR does not remove any mechanism of outdated invalid routing, and it is not determined. The freshness of each route is used to select the correct routing mechanism after the communication route fails, and the CHNN-DSR has a lower probability of routing failure than the DSR because of its strong stability.

5 Conclusions

It is feasible to apply artificial intelligence algorithms such as neural network algorithms to FANET routing optimization. In highly dynamic FANETs, the stability of the route determines the stability of the network. Based on CHNN, the DSR is optimized and named as CHNN-DSR, which obtains a more stable and stable route, which improves the stability of FANET and the communication efficiency of the network. The simulation results show that in the FANETs using CHNN-DSR, the key indicators such as packet delivery ratio, end-to-end average delay, and throughput are better than those directly using DSR. In the subsequent research, the application of artificial intelligence algorithms such as neural network algorithms to the design of FANET routing will be worthy of further research.