Bionic Optimization Based Stability and Congestion Aware Routing Algorithm for Airborne Highly Dynamic Network

Abstract

Airborne highly dynamic ad hoc UAV network has features of high node mobility, fast changing network topology, and complex application environment. The performance of traditional routing algorithms is so poor over aspects such as end to end delay, data packet delivery ratio, and routing overhead that they cannot provide efficient communication for multi-UAVs carrying out missions synergistically. A bionic optimization based stability and congestion aware routing algorithm—BSCAR algorithm—is proposed to solve these problems. This algorithm integrates biological behavior and dynamic source routing algorithm, which can sense the congestion level of routes and the stability of routes. Ant colony optimization algorithm and the mathematical model of Physarum's behavior exert effort in the process of route discovery and maintenance. The level of pheromone in routes is chosen as a standard to choose route and calculated by the mathematical model of Physarum's behavior. A new volatilization mechanism of pheromone is also introduced into the algorithm. Meanwhile, the algorithm can make adjustment to the variance of UAV formation to prevent the compromise of the network performance. The simulation results show that the BSCAR algorithm has superiority over traditional algorithms and it is dependable in battlefield environment.

1. Introduction

The recent years have witnessed a wider application of UAVs, covering many fields for military and civilian purpose. UAVs also play a significant role in modern warfare, implementing a variety of missions including reconnaissance, surveillance, information gathering, communication relay, and fast attacking. The modern warfare is characterized by fierce conflicting, wide coverage, and large amount of information, and a single UAV would be unable to meet the demands of it; thus multi-UAVs cooperative combat becomes a focus of current researches. Flight formations are usually designed for multi-UAVs to implement missions cooperatively.

An ad hoc UAV network can be applied to interchange data concerning mission planning, flight status, and information when multi-UAVs perform tasks in flight formation, which improves the situation awareness of the UAV formations, making multi-UAVs cooperatively implementing missions possible. The ad hoc UAV network is a branch of aeronautical ad hoc network, which is a classic application of MANET in aviation field. The network ensures UAVs log in and out fast during war time; every UAV is designed to withhold an equal status in the network to enhance its robustness. In ad hoc UAV network, each UAV is regarded as a node.

However, ad hoc UAV network has the features of greater node mobility, faster network topology variance, more complicated appliance situations, and more frequent data interaction than mobile ad hoc network. These features have brought big challenges for the design of routing algorithm in ad hoc UAV network. Traditional routing algorithms are unable to satisfy the demands of multi-UAVs carrying out missions cooperatively in this situation, and the routing algorithms based on QoS can only be applied under certain circumstances, so in order to meet the demands of multi-UAVs carrying out missions cooperatively in complicated communication situations, a routing algorithm which is appropriate for ad hoc UAV network is required.

We believe that the routing algorithm for ad hoc UAV network is supposed to obtain such properties: (1) low end to end delay; (2) low data packet loss probability; (3) high reliability; (4) no congestion; (5) low routing overhead; and (6) maintaining of the network performance by adjusting the routing algorithm for the variance of formation. Traditional routing algorithms are unable to meet the above requirements. We summarized the three keys to designing the algorithm: the route length, the congestion level of a route, and the stability of a route. They should be taken into comprehensive consideration to design the routing algorithm for ad hoc UAV network. Meanwhile, we assume that every node has enough energy in ad hoc UAV network, so the energy is not the factor which can influence the performance of routing.

The ant colony optimization (ACO) algorithm was proposed by the Italian scholar Dorigo in 1992; it is a heuristic algorithm, which imitates the nature process of ants searching for food [1]. The ant colony is able to determine the shortest route between their nest and the food source, and the following ants can find the route by a chemical material (pheromone) to find food [2]. As is shown in Figure 1, each ant comes out of the nest in a random direction in the searching stage, and different ants get to the food source in different routes; when returning, all ants followed their original routes and release pheromone, which is in negative correlation with route length. With the passage of time, the pheromone in the optimal route is accumulated because of constant passage of ants, while the pheromone in other routes is volatilized or diluted because of the rare number of ants passing them. A series of combinatory optimization problems can be solved by ACO algorithm [3], and it is applied to wireless network routing in various ways. There exist examples to prove that the routing algorithms which are based on ACO algorithm have an advantage over traditional routings in terms of network performance [4].

Figure 1

The schematic diagram of ACO algorithm.

For dynamic source routing (DSR) algorithm [5], when the source node sends data package to destination node, the source node needs to determine whether there exist routes qualified to complete the transmission at first; if not, the source node broadcasts the RREQ message in the network through the way of flooding until the destination node receives the message; during this process, the intermediate nodes are recorded in RREQ message in order. After receiving the RREQ message, the destination node would send RREP message along the original route. The shortest route would be used to transmit data. In route maintaining phase, when an intermediate route is disconnected, the current node would send the route failure message to the source node through the upstream node, and the source node would update accessible routes. However, the DSR algorithm has many disadvantages: firstly, the mobility of nodes leads to obvious link breakage, which significantly increases the package loss rate; secondly, the flooding mechanism adopted in this algorithm increases the routing overhead and end to end delay.

In recent years, the Physarum has become a new focus of Physarum-inspired method. Physarum polycephalum is composed of tubular form and flowing fluid. The flowing fluid can transport nutrition and transmit signal for each of the several parts of Physarum polycephalum; at the same time, it also can adjust the change of tubular form [6, 7]. The mathematical model of Physarum's behavior can help us select appropriate routes.

We integrate the DSR algorithm and biological behavior and propose a bionic optimization based stability and congestion aware routing algorithm—BSCAR algorithm—after making many improvements. This routing algorithm basically reaches the proposed requirements and is able to satisfy the needs of sharing information when multi-UAVs implement missions cooperatively.

The contributions of this paper are concluded as follows:

• (1)

A route stability measurement method is proposed and a long-acting supervision mechanism is established, which greatly improves the measurement accuracy.

(2)

A method measuring congestion level of a route is proposed, which is followed by a nonlinear processing to enable the results to be fit for real situations.

(3)

The route discovery and choosing process of DSR algorithm are improved based on ACO algorithm and the mathematical model of Physarum's behavior, which significantly improves its performance and makes it possible to adjust to the changing formation of UAVs.

(4)

We improve the mechanism of pheromone volatilization through different routes using different decay coefficients, which decreases the routing overhead.

(5)

In the simulation environment, the BSCAR algorithm has superiority over other main routing algorithms.

The rest of the paper is organized as follows: Section 2 is about the related works. So, we select and summarize some papers which have the same issue. We describe the data structure of two control packets in Section 3. The proposed mechanism to estimate the stability of a route is detailed in Section 4. The proposed mechanism to estimate the congestion level of a route is described in Section 5. Section 6 is about the BSCAR algorithm. The performance evaluation of the proposed algorithm is included in Section 7. Finally, we conclude our work in Section 8.

2. Related Works

In recent years, the routing protocols of aeronautical ad hoc network have been diversified. The protocols can be put into three categories based on the different routing information renewal mechanisms: (1) table driven (proactive) routing protocols, such as DSDV [8], FSR [9], STAR [10], OLSR [11], WRP [12], and TBRPF [13]. In proactive routing protocols, every node is required to maintain one or several routing tables, which contain the consistent and latest routing information in relation to other nodes in the network. To maintain such routing tables, each node needs to broadcast renewal routing information periodically, thus maintaining and memorizing the network topology and the node routing information. The table driven routing protocols have the advantage of low end to end delay and superior service quality during the network transmitting process. However, the protocols are costly, and a large number of routing control packages would greatly increase the routing overhead and the congestion level of nodes; (2) demands based (reactive) routing protocols, such as AODV [14], DSR [5], TORA [15], and SSR [16]. In reactive routing protocols, new routes are searched only when demand for communication exists. The routing overhead is relatively low and the network resource is saved due to the lack of necessity to broadcast renewal routing information; however, if there exist no available routes connecting the target node when the source node demands communication, a new search process is forced to be created and the data transmission could be delayed; (3) hybrid routing protocols, such as ZRP [17]. This kind of protocols integrates the previous two kinds but still could not solve the problem of overlarge routing overhead.

With the development of ant colony optimization algorithm, it is increasingly adopted to solve the routing problems in mobile ad hoc network. According to [18], the routing protocols based on ACO algorithm can be put into three categories. We illustrate the protocols which are representative and related to our work.

In Ant-DSR algorithm [19], unicast ant agent is used to establish and update routings; the other ant agents are used to detect neighbors. The method is a proactive routing algorithm; it can shorten the data transmitting delay but still cannot avoid the increase of routing overhead, which leads to congestion in the network. The Ant-Based Control (ABC) [20] algorithm is proactive and it can adapt to highly dynamic MANETs due to its high robustness to node failure. In this algorithm, the link with the most pheromone in the column corresponding to the destination can be selected by exploratory ants. But the best route is easy to get congested. The probabilistic ant routing (PAR) algorithm [21] has two kinds of agents—forward and backward ants. The forward ant explores the network to collect the traffic information. When the forward ant reaches the destination, it is deallocated and the backward ant inherits the stack contained in the forward ant. Each node is assigned a probability of $1/N$ , where N is the number of neighbors of a node. However, it cannot adapt to large network.

In ADSR algorithm [22], the forward ant and backward ant are used in routing discovery phase, and it belongs to reactive routing algorithms. ADSR takes into consideration three QoS parameters, namely, delay, jitter, and energy. However, the reliability of routes is not evaluated in the ADSR algorithm, and intermediate link breakage tends to frequently occur in high mobility ad hoc UAV network; thus the data packet delivery ratio is decreased. The probabilistic emergent routing algorithm (PERA) [23] has the routing table which stores the probability distribution for the neighbors. This probability associated with a neighbor reflects the likelihood of that neighbor forwarding and delivering the packet to the destination node. This scheme can be seen as the integration of the DSR and ACO algorithms. The drawback of this algorithm is that there is no result from passing packets, that is, no caching. The improvised ant colony optimization algorithm for MANETs (PACONET) [24] has two kinds of mobile agents. FANTs are transmitted to determine new routes. BANTs establish the path based on the information gathered by FANTs. These mobile agents leave certain amount of pheromone at the time they depart from the node. The data packets are routed stochastically on the path that has the highest pheromone value along the path to destination. But its overhead is too high.

HOPNET algorithm [25] and HRAZHLS algorithm [26] are both hybrid routing algorithms; four kinds of ants are included in the algorithms: intrazone forward ant, intrazone backward ant, interzone forward ant, and interzone backward ant. But the HOPNET algorithm lacks the expansibility for large-scale networks and is only adapted to small ones. The routing overhead of HRAZHLS algorithm is relatively large. More overhead is also AntHocNet's [27] main drawback. Ant routing algorithm for MANETs based on adaptive improvement (ARAAI) [28] has two tables. One contains initial node, last node, and heuristic value. The other contains the information of neighbors which represents the connection between the current node and other nodes. The FANT chooses next hop after considering both pheromone value and local heuristic value of the link. However, the route discovery delay is too high.

In summary, whether integrated with ACO algorithm or not, the proactive routing protocol, the reactive routing protocol, and the hybrid routing protocol cannot meet the demands for ad hoc UAV network. Meanwhile, the above routing algorithms cannot efficiently avoid the common problems in mobile ad hoc network, such as node congestion and link breakage, which could greatly increase package loss rate.

In order to measure the stability of a route, the stability of links in the route must be measured at first. There mainly exist two kinds of methods determining the link stability.

Firstly, for the methods based on distance [29, 30], they are set up upon the criterion that the closer the distance is, the better the stability would be, and the distance is calculated by the GPS or the signal-power of received “Hello” message. This method is single in form and is unable to establish a long-effective supervisory mechanism. If adopting this method, it would be inevitable to bring positioning error and external GPS interfering signal, which leads to failure in determination.

Secondly, for the methods based on mobility of nodes, they consist of two branches. One is to calculate the movement direction and velocity of nodes through the positioning information [31] or the Doppler frequency shift of “Hello” message; thus the link stability can be evaluated; however, the computing cost is relatively large, and GPS error is easy to be brought in the network if using the positioning information. The other is to evaluate the stability based on probabilistic methods; the method adopted in [32] is too complicated with large computing cost; [33] evaluates the link stability through the variation of neighbor nodes' numbers, which is inaccurate with big error; the computing method in [34] is relatively easy, but the generated links with high stability could locate in the margin of communication range, which are prone to disconnection.

The literatures addressing the network congestion proposed many solutions, but there still exist some inadequacy. In [35], the traffic load is represented by the ratio of the interface queue length in the MAC layer to the total length of interface queue, thus avoiding the heavy load node from being an intermediate node and causing network congestion; however, the process of measuring the congestion level of a route is insufficient. In [36], the evaluation of the route congestion level is based on buffer occupancy, channel load measurement, and package drop rate, but it puts the low energy cost in the first place, leading to inaccurate measurement of route congestion level.

The papers above consider the stability of a route or the congestion level of a route separately and never combine them. In [37], the measurement of route stability is combined with the evaluation of route congestion, which avoids the common problems in mobile ad hoc network; however, the method in this paper needs to be improved.

Tero et al. [6, 7] proposed a mathematical model for the behavior of Physarum polycephalum. Zhang et al. [38, 39] introduced the mathematical model of Physarum polycephalum's foraging behavior into the field of wireless sensor network and then used the modified model to select node as the next hop. At present, no literature uses this model in airborne highly dynamic ad hoc UAV network.

We propose a routing algorithm for ad hoc UAV network, which can fulfill the requirements, such as low end to end delay, high package delivery ratio, and low routing overhead. It also can avoid some common problems, such as link breakage and node congestion. Meanwhile, the routing algorithm can adapt the variance of UAV formation. Eventually, the routing algorithm we proposed overcomes all the deficiencies of the traditional routing algorithms.

3. Definition of the Control Packet Format

There mainly exist two kinds of routing control packets in mobile ad hoc network (RREQ and RREP). RREQ (Route Request) control packet consists of the address and serial number of destination node, the serial number of broadcast, the address and serial number of source node, the address of the previous hop in route and the number of hops, and so forth. RREP (Route Reply) control packet consists of the address of source node, the address and serial number of the destination node, the number of hops, survival time, and so forth. Many improvements have been made based on the integration of biological behavior and DSR algorithm, and the data structure of RREQ and RREP must be modified to be fit for the proposed routing algorithm, which is shown in Figure 2. The two kinds of modified routing control packets are named after RREQ.Ant, RREP.Ant; they are also referred to as the forward ant and backward ant. The modified data structure is shown in Figure 2.

Figure 2

The format of the control packet.

The addresses of the source node and destination node are MAC address instead of IP address, which prevents the case when nodes disconnect from the network and IP address cannot be assigned to them. HC stands for the number of hops in the route connecting source node and the destination node in RREQ.Ant, and the value of HC is initially set as 0. However, HC is set as a constant in RREP.Ant. RC and RS are referred to as congestion level and stability of the route connecting source node and destination node, and the value of “a” is effective only in RREP.Ant, which is used to determine the transmitting route of backward ant. “Type” represents the type of routing control packets, which is set to be RREQ.Ant when Type = 1 and RREP.Ant when Type = 0. The last part is used to store the addresses of intermediate nodes in the route connecting the source node and destination node.

4. Sensing the Stability of a Route

In ad hoc UAV network, the link breakage is a common phenomenon because of the changing network topology, which is the result of the high speed and different missions of UAVs. A method evaluating the stability of links is proposed in this paper to avoid the compromise of the network performance caused by network disconnection. This method is established upon the signal strength of the received “Hello” message and the corresponding supervisory mechanism. The method can improve the performance of network by predicting and deleting the possible disconnecting links after comprehensively evaluating the stability of a certain link. Meanwhile, the positioning information is not adopted in this paper to avoid the possible influence caused by GPS positioning error or external GPS interfering signal.

When implementing reconnaissance mission under warfare environment, the UAV formation is composed of different kinds of aircrafts for the requirements of different missions; therefore, the velocity, the antenna gain, and the maximum transmitting power of each platform are different. The data packet format of “Hello” message is improved in this paper, which includes the address of source node, node congestion level, antenna gain, transmitting power, and speed.

According to the free space attenuation model [40], the received signal strength $P_{ri}$ of the “Hello” message in current node transmitted from the neighbor node i in a distance d is

$$\begin{array}{cc}& P_{ri}=P_t{G}_t{G}_r{\left(\frac{\lambda }{\mathrm{4}\pi d}\right)}^{\mathrm{2}},\end{array}$$

(1)

where λ is the length of radio wave, $G_r$ is the receiving antenna gain, $G_t$ is the transmitting antenna gain, and $P_t$ is the transmitting power of “Hello” message from neighbor node.

We assume that the covering range of antenna is a circular region whose radius is R. The average distance between two moving nodes in a circular region with radius of R is 0.9054R according to [41]. Hence the threshold value of received “Hello” message signal strength from neighbor node is defined as

$$\begin{array}{cc}& P_{\text{threshold}\hspace{0.17em}i}=P_t{G}_t{G}_r{\left(\frac{\lambda }{\mathrm{4}\pi \times \mathrm{0.9054}R}\right)}^{\mathrm{2}}.\end{array}$$

(2)

The threshold value of received signal strength can be calculated based on the known information of current node and the information included in the “Hello” message transmitted from neighbor node, and the initial judgment of link stability can be made after comparing the threshold value with the measured signal strength. The processes are as follows:

$$\begin{array}{cc}& {\mathrm{L}\mathrm{S}}_i=\left\{\begin{array}{cc}\mathrm{0},\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{P}_{ri}\le P_{\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}\mathrm{o}\mathrm{l}\mathrm{d}\hspace{0.17em}i},\hfill \\ \mathrm{1}-\frac{P_{\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}\mathrm{o}\mathrm{l}\mathrm{d}\hspace{0.17em}i}}{P_{ri}},\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{P}_{ri}\ge P_{\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}\mathrm{o}\mathrm{l}\mathrm{d}\hspace{0.17em}i}.\hfill \end{array}\right.\end{array}$$

(3)

The value of ${\mathrm{L}\mathrm{S}}_i$ represents the current stability of the link i; the greater the value is, the better the stability of the link would be, but the value cannot exceed 1. A link would be deleted from the cache if the ${\mathrm{L}\mathrm{S}}_i$ value of it is 0 and considered as an unstable link. Constant updates are needed to keep the instantaneity of ${\mathrm{L}\mathrm{S}}_i$ , and the interval (the period of broadcasting “Hello” message) t is

$$\begin{array}{cc}& t=\frac{R-\mathrm{0.9054}R}{V_{\mathrm{1}}+V_{\mathrm{2}}},\end{array}$$

(4)

where $V_{\mathrm{1}}$ refers to the maximum movement velocity of current node and $V_{\mathrm{2}}$ refers to the maximum movement velocity of the neighbor nodes. The corresponding t differ from each other because of the different types of neighbor nodes. Renewing the value of ${\mathrm{L}\mathrm{S}}_i$ by adopting the time interval guarantees the fact that the neighbor nodes in cache locate in the communication range during time span t, thus effectively taking advantage of the storage space and providing reliable options for the route discovery phase. This process effectively solves the deficiency of the fixed period of “Hello” message.

The above process only evaluates the stability of links at a certain moment, which lacks a long effective mechanism for comprehensively evaluating the stability of links. Therefore, the mobility of neighbor nodes is estimated and the nodes in cache with high mobility are deleted according to the signal strength variation of “Hello” message at different moments in our work.

The Bienayme-Chebyshev inequality [42] is as follows:

$$\begin{array}{cc}& P\left\{\left|X-E\left(X\right)\right|<\epsilon \right\}\ge \mathrm{1}-\frac{\mathrm{var}\left(X\right)}{{\epsilon }^{\mathrm{2}}},\end{array}$$

(5)

where X is a discrete variable, $E(X)$ is the expectation value of X, $\mathrm{var}(X)$ is the variance of X, and ε is an arbitrary positive number.

If $\mathrm{var}(X)=\mathrm{0}$ , then $P\left\{\left|X-E(X)\right|<\epsilon \right\}=\mathrm{1}$ , which means that the variable X is equal to its expected value, which also means that the smaller the variance of X is, the closer X would be to its expected value and the smaller the varied quantity of X would be.

According to multiple measurements of X, the variance $\mathrm{var}(X)$ is

$$\begin{array}{cc}& \mathrm{var}\left(X\right)=\left({\displaystyle \sum }_k^{}\frac{{X_k}^{\mathrm{2}}}{n}\right)-{\left(\sum _k^{}\frac{X_k}{n}\right)}^{\mathrm{2}}.\end{array}$$

(6)

Take the values of ${\text{LS}}_i$ at different moments as the multiple measured values of X and substitute them into (6):

$$\begin{array}{cc}& \mathrm{var}\left({\text{LS}}_i\right)=\left({\displaystyle \sum }_{m=\mathrm{1}}^n\frac{{\text{LS}}_i{\left(t_m\right)}^{\mathrm{2}}}{n}\right)-{\left(\sum _{m=\mathrm{1}}^n\frac{{\text{LS}}_i\left(t_m\right)}{n}\right)}^{\mathrm{2}}.\end{array}$$

(7)

The mobility of a neighbor node can be gained according to (7), and the smaller the $\mathrm{var}({\mathrm{L}\mathrm{S}}_i)$ is, the less mobility of the node shows and the more stable the link i would be. This method only applies for determining the mobility of the neighbor nodes in the cache of the current node.

In summary, the procedures to determine the stability of a link are as follows: encode all nodes within the range of $0.9054R$ as number for each node, write them into the cache, and calculate the current stability ${\mathrm{L}\mathrm{S}}_i$ of each link according to (3) at set interval. Delete the links from the cache whose value of ${\mathrm{L}\mathrm{S}}_i$ is 0. Determine the mobility of a link when it gains two nonzero ${\mathrm{L}\mathrm{S}}_i$ in a row and conduct constant judgment for a link as long as ${\mathrm{L}\mathrm{S}}_i$ is not zero. If the $\mathrm{var}({\mathrm{L}\mathrm{S}}_i)$ of a certain link exceeds the previously set threshold value ${\mathrm{v}\mathrm{a}\mathrm{r}}_{\text{threshold}}$ third cumulatively, it means that the mobility of its neighbor nodes is high and the link is unstable; thus the link would be deleted from the cache of the current node. Meanwhile, for the sake of saving storage space, only five recent measured values of ${\mathrm{L}\mathrm{S}}_i$ can be stored in the cache. The number of nodes which is written into the cache is not limited.

In route discovery phase, the most stable route is usually chosen to transmit data, and the stability of the current link is supposed to be quantified comprehensively. A comprehensive quantifying method for measuring the stability of the current link is proposed as follows:

$$\begin{array}{cc}& {\text{CLS}}_i\left(t_m\right)=\frac{{\text{LS}}_i\left(t_m\right)}{e^{{\mathrm{var}}_m\left({\mathrm{L}\mathrm{S}}_i\right)}},\end{array}$$

(8)

where ${\mathrm{C}\mathrm{L}\mathrm{S}}_i(t_m)$ is the comprehensive stability of the link i at moment $t_m$ ; ${\mathrm{L}\mathrm{S}}_i(t_m)$ is the value of ${\mathrm{L}\mathrm{S}}_i$ at moment $t_m$ ; ${\mathrm{var}}_m({\mathrm{L}\mathrm{S}}_i)$ is the value of $\mathrm{var}({\mathrm{L}\mathrm{S}}_i)$ at moment $t_m$ . The value of $\mathrm{var}({\mathrm{L}\mathrm{S}}_i)$ is set to be empty when a neighbor node enters the cache for the first time at the moment, and we set ${\mathrm{var}}_m({\mathrm{L}\mathrm{S}}_i)=\mathrm{1}$ at the moment. And the bigger the value of ${\mathrm{C}\mathrm{L}\mathrm{S}}_i(t_m)$ is, the higher the comprehensive stability of the link would be.

In our work, each route control packet includes a RS value, which is calculated by route request control packet in the route discovery process. A forward ant departs from the source node and the initial value of RS is set as 1. When the forward ant moves in the network, the RS value would be renewed by the product of the current value of RS and the link stability ${\mathrm{C}\mathrm{L}\mathrm{S}}_i$ between the intermediate node and the previous node. When the forward ant arrives at the destination node, the stability of the route between the source node and the destination node can be gained:

$$\begin{array}{cc}& \text{RS}={\displaystyle \prod }_{j=\mathrm{1}}^n{\mathrm{C}\mathrm{L}\mathrm{S}}_i^j,\end{array}$$

(9)

where ${\mathrm{C}\mathrm{L}\mathrm{S}}_i^j$ is the stability for each link passed by the forward ant in route discovery phase and n represents the number of passed nodes.

5. Sensing the Congestion Level of a Route

When multiple UAVs implement surveillance mission to hot spot areas in formation, much target data need to be shared and transmitted to the base station. Network congestion would frequently occur if traditional routing algorithms are adopted to construct routes transmitting data. The network transmission performance would be compromised if network congestion occurs in ad hoc UAV network, such as increasing packets loss rate or average end to end delay.

We propose a method measuring the congestion level of a route, and it is measured based on buffer occupancy and channel load; the nonlinear processing is adopted to make the results fit for real situations.

5.1. Buffer Occupancy

The ratio of the interface queue length in MAC layer to the total length of interface queue in MAC layer represents the current buffer occupancy ( ${\mathrm{B}\mathrm{O}}_i$ ) of node $N_i$ , which can be calculated as follows:

$$\begin{array}{cc}& {\text{BO}}_i=\frac{Q_i}{Q_{\mathrm{m}\mathrm{a}\mathrm{x}}},\end{array}$$

(10)

where $Q_i$ is the interface queue length in MAC layer of node $N_i$ and   $Q_{\mathrm{m}\mathrm{a}\mathrm{x}}$ is the total length of interface queue in MAC layer.

The value of ${\mathrm{B}\mathrm{O}}_i$ in node $N_i$ is measured periodically to calculate the average buffer occupancy $\mathrm{A}\mathrm{v}\mathrm{e}\_{\mathrm{B}\mathrm{O}}_i(t)$ during a certain period of time. N times of measurement are assumed to be carried out during time t:

$$\begin{array}{cc}& \text{Ave}\_{\text{BO}}_i\left(t\right)=\frac{{\sum }_{j=\mathrm{1}}^N{\mathrm{B}\mathrm{O}}_i\left(j\right)}{N},\end{array}$$

(11)

where ${\mathrm{B}\mathrm{O}}_i(j)$ is the jth measurement result of ${\mathrm{B}\mathrm{O}}_i$ for node $N_i$ .

In general, a node is determined to be in high buffer occupancy when the ratio of the interface queue length in MAC layer to the total length of interface queue in MAC layer is bigger than 65% [43], so we adopt nonlinear to process $\mathrm{A}\mathrm{v}\mathrm{e}\_{\mathrm{B}\mathrm{O}}_i(t)$ , making it fit for practical needs:

$$\begin{array}{cc}& {\mathrm{N}\mathrm{B}\mathrm{O}}_i=\mathrm{1}-{\left(\mathrm{1}-\mathrm{A}\mathrm{v}\mathrm{e}\_{\mathrm{B}\mathrm{O}}_i\left(t\right)\right)}^5,\end{array}$$

(12)

where ${\mathrm{N}\mathrm{B}\mathrm{O}}_i$ is the nonlinearized average buffer occupancy of node $N_i$ .

5.2. Channel Load

According to [37], the channel load ${\mathrm{C}\mathrm{L}}_i$ can be obtained after channel sampling over certain time span periodically. The sampling process is shown in Figure 3:

$$\begin{array}{cc}& {\text{CL}}_i=\frac{N_{\text{busy}}}{N_{\text{busy}}+N_{\text{idle}}},\end{array}$$

(13)

where $N_{\mathrm{b}\mathrm{u}\mathrm{s}\mathrm{y}}$ represents the times when the channel is busy during the span, while $N_{\mathrm{i}\mathrm{d}\mathrm{l}\mathrm{e}}$ represents the times when idle.

Figure 3

The sampling process for channel load measurement.

With the increase of channel load ${\mathrm{C}\mathrm{L}}_i$ , the congestion is getting worse. We conducted many consecutive measurements for ${\mathrm{C}\mathrm{L}}_i$ and obtained the average channel load during time t:

$$\begin{array}{cc}& \text{Ave}\_{\text{CL}}_i\left(t\right)=\frac{{\sum }_{j=\mathrm{1}}^N\mathrm{C}\mathrm{L}\left(j\right)}{N},\end{array}$$

(14)

where ${\mathrm{C}\mathrm{L}}_i(j)$ is the measurement result of ${\mathrm{C}\mathrm{L}}_i$ in the jth time and N is the measuring times during time t. In most cases, the value of t is set to be 30 s, and the measurement time is 5 to 10 s.

The results of channel load require nonlinear processing, which is similar to that of buffer occupancy. We believe that the channel load is high when it is greater than 0.7. The nonlinear processing is as follows:

$$\begin{array}{cc}& {\text{NCL}}_i=\mathrm{1}-{\left(\mathrm{1}-\text{Ave\_}{\text{CL}}_i\left(t\right)\right)}^4.\end{array}$$

(15)

The following equations are defined to comprehensively evaluate the congestion level of a certain node:

$$\begin{array}{cc}& M_i\left(t\right)=\frac{{\text{NBO}}_i+{\text{NCL}}_i}{\mathrm{2}},\\ {\text{CNC}}_i\left(t\right)=\nu \times M_i\left(t-\mathrm{1}\right)+\left(\mathrm{1}-\nu \right)\times M_i\left(t\right),\end{array}$$

(16)

where $M_i(t)$ is the node congestion level during current time window, ν, $(\mathrm{1}-\nu )$ are the node congestion level weight factors assigned to the previous and current time windows, and ${\mathrm{C}\mathrm{N}\mathrm{C}}_i(t)$ represents the comprehensive value of current node congestion level.

Each route control packet has a RC value, which is calculated and obtained during the route discovery process. A forward ant departs from the source node and establishes the route from the source node to the destination node; when the forward ant arrives at the destination node, the maximum node congestion level ${\mathrm{C}\mathrm{N}\mathrm{C}}_i(t)$ of all nodes in the route is defined as the congestion level RC of the route:

$$\begin{array}{cc}& \text{RC}=\max \left({{\text{CNC}}_i}^j\right);\hspace{1em}\forall j=\mathrm{1}\dots n,\end{array}$$

(17)

where ${{\mathrm{C}\mathrm{N}\mathrm{C}}_i}^j$ represents the congestion level of each node passed by forward ant during route discovery process and n represents the number of nodes passed by the forward ant.

6. Bionic Optimization Based Stability and Congestion Aware Routing Algorithm

6.1. Route Discovery Process

There exist multiple kinds of formation for UAVs based on different missions. This paper focuses on how the density of UAVs in formation affects the routing of ad hoc UAV network. Therefore, this paper proposes two kinds of route discovery algorithm according to the density of nodes in ad hoc UAV network.

According to [44], we consider that the UAV formation is concentrated when ANP (Average Network Partitioning) is fewer than 3%, or it is considered as sparse formation. The difference of the two algorithms lies in the broadcasting scheme of RREQ.Ant, and the remaining aspects are the same.

6.1.1. RREQ.Ant Delivery

(1) Sparse Formation. When a UAV acquires the target information and needs to share the information to other UAVs, the current node firstly makes comparison among the existing routes in cache; if there exist routes which are able to accomplish the information transmission, the optimal route would be chosen to transmit the target information according to the route choosing process; if there does not exist qualified routes to transmit target information, the route discovery process would be started, thus sending forward ants to all stable nodes in its neighborhood. Compared with the flooding method proposed in [45], the method proposed in this paper can overcome the disadvantage (such as no directivity and blindness) of flooding method, which can improve the dependability of the discovered routes.

When an intermediate node receives the forward ant from the previous node, the hop number HC in the control packet is first to be determined. The maximum value of HC is 127 with the limit of storage space; once the maximum value of HC is discovered, the intermediate node would delete the packet to prevent the distance measuring error.

Secondly, a preventive mechanism is proposed in this paper to avoid the unfavorable effect caused by route circle to the ad hoc UAV network. When an intermediate node discovers the node address of itself in the INA, the route discovery process is considered to be in circular status. Firstly, the RREQ.Ant is modified and the nodes entering the circle would be deleted; subsequently, stable nodes from the neighborhood which would not enter a circle can be chosen, and RREQ.Ant would be transmitted to them.

Finally, if there is not circular problem, the current intermediate node will look for qualified routes which can arrive at destination node in its cache, if there exist such routes, the corresponding information in the forward ant needs to be renewed (the number of hops, the stability, the congestion level, etc.) and route reply process would be started; this method can decrease the end to end delay and route overhead; if there do not exist such qualified routes, the current intermediate node would renew the current forward ants and broadcast them to the stable neighbor nodes.

For destination node, if receiving RREQ.Ant, it needs to be renewed. Meanwhile, the route reply process is started.

(2) Concentrated Formation.For concentrated formation, if adopting the same routing algorithm as sparse formation, with the increase of node density, the broadcasting number of RREQ.Ant would significantly increase, thus tending to cause broadcast storm and compromise the performance of network. Hence, two modifications are made in the routing algorithm of concentrated formation. The first is to attach the list of stable neighbor nodes of the current node to previous Hello message; the second is to modify the broadcasting scheme of forward ant. Inspired by [44], a probabilistic broadcasting scheme is proposed to reduce the number of RREQ.Ant and decrease probability of occurring of the broadcast storm. Meanwhile, this scheme guarantees the redundancy of discovered routes, which can be reliable in battlefield environment.

The probabilistic broadcasting scheme can be only applied to intermediate nodes, and the forward ant broadcasting scheme of sparse formation is still applied to source node to ensure the redundancy of discovered routes. When an intermediate node D receives the forward ant from the previous node F, a comparison would be made between the list in Hello message of node F and the current list, thus calculating the broadcasting probability p of forward ant; and the node D would broadcast the renewed forward ant to stable neighbor nodes under probability p. The equation calculating the broadcasting probability is as follows:

$$\begin{array}{cc}& p=\frac{n+q}{m+n+q},\end{array}$$

(18)

where m is the number of mutual stable neighbor nodes of the two nodes; n means the number of stable neighbor nodes belonging to node F while not belonging to node D; and q means the number of stable neighbor nodes belonging to node D while not belonging to node F.

Although the modification made to Hello message in this section increases the occupied time of wireless media, the probabilistic broadcasting scheme can significantly decrease the number of forward ants, thus decreasing the routing overhead and guaranteeing the dependability of the discovered routes. Above all, it does more good than harm. The pseudocode of the RREQ.Ant delivery algorithm is shown in Algorithm 1.

Algorithm 1:The pseudocode of the RREQ.Ant delivery algorithm.

RREQ.Ant Delivery ()

{

 To Source Node:

 % Source node A sending data packet B to destination node C.

  $X\leftarrow 0$ ;

 If there are feasible paths found between A and C

  {

    $X\leftarrow \mathrm{r}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}$ selection();

   B is sent through path[X];

  }

 If ( $X=0$ )

  {

   Broadcast RREQ.Ant;

  }

 To Intermediate Node:

 % Intermediate node D receiving a packet E from node F.

If receives packet

  {

  If (D ≠ destination address)

   {

    If (type = 1)

   {

     $\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}\leftarrow 0$ ;

    If (HC = 127)

     {

      Discard the packet;

     }

    For $i=1$ to end

    {

     If (INA[i] = D)

      {

        $\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}\leftarrow 1$ ;

       break;

      }

     Else

     Continue;

    }

    If (loop = 1)

     {

    For $j=i+1$ to end

    {

      $A[k]\leftarrow \mathrm{I}\mathrm{N}\mathrm{A}[j]$ ;

      $\mathrm{I}\mathrm{N}\mathrm{A}[j]\leftarrow 0$ ;

    }

     $i\leftarrow 0$ ;

    For $n=1$ to end

    {

     For $k=1$ to end

     {

      If (link[n] ≠ A[k])

       i++;

     }

     If ( $I=k_{\mathrm{m}\mathrm{a}\mathrm{x}}$ )

      RREQ.Ant is forward to link[n];

    }

      }

     If (loop = 0)

    {

     If there are feasible paths to C

      {

        $X\leftarrow \mathrm{r}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}$ selection ();

        $\mathrm{R}\mathrm{C}\leftarrow \mathrm{m}\mathrm{a}\mathrm{x}$  {RC[X], RC, CNC[F]};

        $\mathrm{R}\mathrm{S}\leftarrow \mathrm{R}\mathrm{S}\ast \mathrm{R}\mathrm{S}[X]\ast \mathrm{C}\mathrm{L}\mathrm{S}[F]$ ;

        $\mathrm{a}\leftarrow \mathrm{H}\mathrm{C}$ ;

        $\mathrm{H}\mathrm{C}\leftarrow \mathrm{H}\mathrm{C}+\mathrm{H}\mathrm{C}[X]+\mathrm{1}$ ;

        $\mathrm{I}\mathrm{N}\mathrm{A}\leftarrow \mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}[X]$ ;

       RREP.Ant Delivery ();

      }

     If no route is found

       {

         $\mathrm{H}\mathrm{C}\leftarrow \mathrm{H}\mathrm{C}+\mathrm{1}$ ;

         $\mathrm{R}\mathrm{S}\leftarrow \mathrm{R}\mathrm{S}\ast \mathrm{C}\mathrm{L}\mathrm{S}[F]$ ;

         $\mathrm{R}\mathrm{C}\leftarrow \max \hspace{0.17em}\left\{\right.\mathrm{R}\mathrm{C},\mathrm{C}\mathrm{N}\mathrm{C}[F]\left.\right\}$ ;

        Broadcast RREQ.Ant;

       }

      }

     }

    }

  }

To Destination Node:

% Destination node C receiving a packet H from node I.

If receives packet

 {

  If (destination address = C)

   {

    If (type = 1)

     {

       $\mathrm{H}\mathrm{C}\leftarrow \mathrm{H}\mathrm{C}+\mathrm{1}$ ;

       $\mathrm{R}\mathrm{S}\leftarrow \mathrm{R}\mathrm{S}\ast \mathrm{C}\mathrm{L}\mathrm{S}[I]$ ;

       $\mathrm{R}\mathrm{C}\leftarrow \max \hspace{0.17em}\left\{\right.\mathrm{R}\mathrm{C},\mathrm{C}\mathrm{N}\mathrm{C}[I]\left.\right\}$ ;

      RREP.Ant Delivery ();

     }

   }

 }

}

6.1.2. RREP.Ant Delivery

When the destination node receives RREQ.Ant, it transforms the type of route control packet into RREP.Ant and returns to the source node along the previous routes. For intermediate nodes, when receiving RREP.Ant, they only need to transmit it along the route; when receiving RREQ.Ant and finding the route connecting the destination node, they need to transform the type of route control packet into RREP.Ant and return to the source node along the previous routes, too. When the source node receives RREP.Ant, it starts the route choosing process, and the optimal route would be chosen to transmit target data. The pseudocode of the RREP.Ant delivery algorithm is shown in Algorithm 2.

Algorithm 2:The pseudocode of the RREP.Ant delivery algorithm.

RREP.Ant Delivery ()

{

 To Destination Node:

 If receives RREQ.Ant

  {

    $\mathrm{a}\leftarrow \mathrm{H}\mathrm{C}-\mathrm{1}$ ;

    $\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}\leftarrow \mathrm{0}$ ;

    $A\leftarrow \mathrm{D}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\hspace{0.17em}\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}$ ;

   Destination $\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}\leftarrow \mathrm{S}\mathrm{o}\mathrm{u}\mathrm{r}\mathrm{c}\mathrm{e}$ address;

   Source $\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}\leftarrow A$ ;

   Send the RREP.Ant to INA[a];

  }

 To Intermediate Node:

 If (receives RREQ.Ant; loop = 0; feasible paths to destination node)

  {

    $\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}\leftarrow 0$ ;

    $A\leftarrow \mathrm{D}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$ address;

   Destination $\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}\leftarrow \mathrm{S}\mathrm{o}\mathrm{u}\mathrm{r}\mathrm{c}\mathrm{e}$ address;

   Source $\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}\leftarrow A$ ;

   Send the RREP.Ant to INA[a];

  }

 If (receives packet; type = 0)

  {

    $\mathrm{a}\leftarrow \mathrm{a}-1$ ;

   If ( $\mathrm{a}=0$ )

    Send the RREP.Ant to destination address;

   Else

    Send the RREP.Ant to INA[a];

  }

 To Source Node:

 If (receives packets; type = 0)

 {

  Route selection ();

 }

}

6.1.3. Route Selection

On the basis of the literature [6], we can get the foraging model of Physarum polycephalum:

$$\begin{array}{cc}& Q_{ij}=\frac{\pi r_{ij}^{\mathrm{4}}\left(P_i-P_j\right)}{\mathrm{8}\eta L_{ij}}=\frac{D_{ij}\left(P_i-P_j\right)}{L_{ij}}=\frac{D_{ij}\Delta P_{ij}}{L_{ij}},\end{array}$$

(19)

where $Q_{ij}$ is the flux through the tube, $\Delta P_{ij}=P_i-P_j$ is the difference of pressures, $r_{ij}^{}$ is the radius of the tube, η is the viscosity of the fluid, $D_{ij}=\pi r_{ij}^{\mathrm{4}}/\mathrm{8}\eta$ is a measure of the conductivity of the tube, and $L_{ij}$ is the length of the tube.

In [38, 39], the mathematical model of Physarum polycephalum can select the appropriate routes which is used for data transmission. We improve this model, which can make it conduct route selection in ad hoc UAV network. We replace $D_{ij}$ by the link quality Φ. $\Delta P_{ij}$ is replaced by $\mathrm{R}\mathrm{S}$ and $\mathrm{R}\mathrm{C}$ . $L_{ij}$ is replaced by the normalized hop count $\widehat{\mathrm{H}\mathrm{C}}$ . $Q_{ij}$ is replaced by the pheromone level of a route.

For each backward ant which is received by the source node, the source node would extract value of HC, RC, and RS to calculate the pheromone level of the route, which is calculated as follows:

$$\begin{array}{cc}& \text{Pheromone\hspace{0.17em}\hspace{0.17em}level\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}a\hspace{0.17em}\hspace{0.17em}route}=\frac{\Phi \times \left(k\times \mathrm{R}\mathrm{S}+\left(\mathrm{1}-k\right)\times \left(\mathrm{1}-\mathrm{R}\mathrm{C}\right)\right)}{\widehat{\mathrm{H}\mathrm{C}}},\end{array}$$

(20)

where k is a coefficient satisfying $\mathrm{0}<k<\mathrm{1}$ . The value of Φ is usually set as 1.

The source node would calculate the pheromone level for each route and choose the route with maximum pheromone level to transmit information. The route used for transmitting information has the characteristic of small hop counts, high stability, and low congestion level. The source node usually preserves multiple available routes in case that the optimal route is disrupted. Meanwhile, a mechanism is defined to decrease end to end delay: when the source node receives the first RREP.Ant, it starts to transmit target information along the route which is provided by the backward ant; when receiving the second RREP.Ant, the source node would choose the route with the highest level of pheromone to transmit information; the same case goes for the following situations until the last RREP.Ant. Owing to the fact that the pheromone volatilization mechanism is introduced in this paper, for each received backward ant, all known routes are required to be chosen for it once again, and the previous level of pheromone for each route cannot be used. The pseudocode of the route selection algorithm is shown in Algorithm 3.

Algorithm 3:The pseudocode of the route selection algorithm.

Route selection ()

{

  $k\leftarrow 0$ ;

 To Source Node:

 If receive the RREP.Ant

  {

   K++;

   Path $[k]\leftarrow \mathrm{I}\mathrm{N}\mathrm{A}$ ;

   Pheromone $[k]\leftarrow (k\ast \mathrm{R}\mathrm{S}+(1-k)\ast (1-\mathrm{R}\mathrm{C}))/\mathrm{H}\mathrm{C}$ ;

  }

  $\mathrm{a}\leftarrow 0$ ;

 For $i=1$ to end

 {

  If (Pheromone $\left[i\right]>\mathrm{a}$ )

  {

    $\mathrm{a}\leftarrow \mathrm{P}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{m}\mathrm{o}\mathrm{n}\mathrm{e}[i]$ ;

    $\mathrm{b}\leftarrow i$ ;

  }

 }

 B is send through path[b];

}

6.1.4. Target Information Delivery

Before transmitting target information, the addresses of selected route's intermediate nodes are required to be written into the target information, which enables the target information to arrive at destination node along the route. When the destination node receives the target information, ACK message would be sent to the source node to show the successful transmission of this time. If the source node does not receive ACK message during a certain period of time, the backup route would be used to transmit target information; if there exists no available route, the route discovery process would be reinitialized.

6.2. Route Maintenance

In ad hoc UAV network, the node mobility and the dynamic change of network topology make the route maintenance extremely important. Route disconnection and route dead circle are two major problems in route maintenance.

According to ACO algorithm, when ants look for food, different paths would be used for arriving at food source. Pheromone would be left in the returning process, and the value of pheromone represents the available degree of the route. If a route is constantly used by returning ants, the value of pheromone will be accumulated; when the food source has been run out and there exist no returning ants, the level of pheromone would be gradually volatilized to zero.

Inspired by the food searching process of ants and [46], the volatilization mechanism is improved in this paper to meet the demands of our algorithm. The level of pheromone of a certain route can be expressed as follows:

$$\begin{array}{cc}& \text{Ph}{\left[k\right]}_t=\left\{\begin{array}{cc}\text{Ph}{\left[k\right]}_{t-\mathrm{1}}\times e^{-\alpha \left(t\times v_{\mathrm{m}\mathrm{a}\mathrm{x}}/n\right)},\hfill & \text{Ph}{\left[k\right]}_{t-\mathrm{1}}\times e^{-\alpha \left(t\times v_{\mathrm{m}\mathrm{a}\mathrm{x}}/n\right)}>\beta ,\hfill \\ 0,\hfill & \text{Ph}{\left[k\right]}_{t-\mathrm{1}}\times e^{-\alpha \left(t\times v_{\mathrm{m}\mathrm{a}\mathrm{x}}/n\right)}\le \beta ,\hfill \end{array}\right.\end{array}$$

(21)

where $\mathrm{P}\mathrm{h}[k{]}_t$ is the value of pheromone of a certain route at t moment; α is the attenuation coefficient, which is used to alter the attenuation amplitude and can be tuned based on practical needs; $v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ is the maximum moving velocity of all nodes; and n is the number of received ACK messages of the source node.

The route maintenance process is started once a certain route receives a backward ant. During this process, the backward ant functions the same as ACK message, and $n=\mathrm{1}$ when $t=\mathrm{0}$ . The value of pheromone of the route would constantly “increase” when the route transmits data properly; of course, the “increase” is determined compared with the situation when no data is transmitted. In general, the level of pheromone tends to decrease even in routes transmitting data properly, but at a relatively low speed; when the route is not used or disconnected, the level of pheromone decreases dramatically, and it would be removed out of source node cache when the level is lower than β. Meanwhile, the maximum node moving velocity is also an important factor affecting the level of pheromone; the higher the velocity is, the route disconnection is more likely to occur; hence, the attenuation degree of pheromone is in positive correlation with the velocity of node.

In route maintenance section, the values of α and β can be adjusted under different demands. In general, the α value in adopted route which is used to transmit data is higher than the idle ones. The reason is that the pheromone level in the chosen route which is used to transmit data is the highest; if the route is disconnected due to the disruption of a certain node, the pheromone level will dramatically decrease and in a rate which is the same as those idle routes (if the α values of all routes are the same). A route is considered to be failed when its value of pheromone is less than β, but all backup routes have been determined to be failed, and the route discovery process is required to be reinitialized, thus increasing routing overhead. As a consequence, we distinguish the attenuation degree of routes' pheromone; the attenuation degree of pheromone is large for the route being used; once the route is destroyed, the pheromone level of the route will dramatically decrease to be invalid; the alternate route can be used to transmit data when the main route is invalid because the attenuation degree of pheromone of the alternate route is small; thus the route discovery process is not required to be reinitialized which decreases the routing overhead.

The route circle problem has been solved in the route discovery phase. The addresses of all intermediate nodes passed by forward ant are added to the ant information; the ant documents it and only passes the nodes that have not been visited. Therefore, the algorithm itself efficiently avoids the route circle.

7. Simulation Results

In simulation environment, some comparisons are made between BSCAR algorithm and several mainstream algorithms, which include DSR algorithm [5], Ant-DSR algorithm [19], and HOPNET algorithm [25]. The simulation software is NS-2 (Network Simulator v2.34). In order to make the contributions of the proposed algorithm more sufficient and reasonable, we evaluate the routing performance with varying maximum movement speed and varying maximum communication range.

7.1. Routing Performance Metrics versus Maximum Movement Speed

First of all, we evaluate the routing performance with varying maximum movement speed. The simulation parameters are given in Table 1. In this paper, two routing strategies aiming at the sparse formation and concentrated formation are proposed, and two scenarios are needed to test their performance. The difference of two scenarios is the number of the UAVs.

Table 1

Simulation parameters.

Parameters	Values
Environment size	1000 m ∗ 1000 m
Number of UAVs	30 (sparse formation) 200 (concentrated formation)
Transmitter range	250 m
Simulation time	600 s
Traffic model	Constant Bit Rate
Mobility model	Random Way Point
Maximum speed limit of an UAV	10 m/s–60 m/s
MAC protocol	IEEE 802.11
Propagation model	Two-ray ground
UAV placement strategy	Random

To simulate the warfare and show the superiority of proposed BSCAR algorithm, some nodes are randomly closed to show that the ad hoc UAV network is damaged to a certain degree in war time. Meanwhile, in order to reduce the random error, the simulation results have been presented by taking average of 30 runs of each simulation setting.

Figures 4 and 5 show the data packet delivery ratio versus maximum movement speed for different algorithms in sparse and concentrated formation. When the maximum movement speed increases, the data packet delivery ratio of all algorithms in two scenarios decreases gradually. That is because the increase of the movement speed aggravates the instability of links between UAVs, and then it can result in frequent link breakage; the packet loss ratio increases gradually. However, the BSCAR algorithm can predict the state of links and avoid using unstable links, which can reduce the adverse effect produced by speed increase. Therefore, the descent rate of BSCAR's data packet delivery ratio is slower than other algorithms. On the whole, no matter how the maximum movement speed changes, the BSCAR algorithm keeps a higher data packet delivery ratio in both scenarios. The possibility of connecting nodes in concentrated formation is higher, which lead to higher data packet delivery ratio when adopting BSCAR algorithm in concentrated formation.

Figure 4

Data packet delivery ratio versus maximum movement speed in sparse formation.

Figure 5

Data packet delivery ratio versus maximum movement speed in concentrated formation.

Figures 6 and 7 show the average end to end delay versus maximum movement speed for different algorithms in sparse and concentrated formation. The average end to end delay of all algorithms in both scenarios increases with the increase of the movement speed. The increase ratio of the proposed algorithm is slower than the other three algorithms, which indicates that movement speed cannot affect this algorithm obviously. The BSCAR algorithm can still keep a lower end to end delay with high speed. On the whole, no matter how the movement speed changes, the BSCAR algorithm can keep a lower end to end delay in both scenarios. The performance is mainly attributed to the routing discovery process and routing maintaining process of BSCAR algorithm.

Figure 6

Average end to end delay versus maximum movement speed in sparse formation.

Figure 7

Average end to end delay versus maximum movement speed in concentrated formation.

Figures 8 and 9 show the routing overhead versus maximum movement speed for different algorithms in sparse and concentrated formation. The increase of maximum movement speed results in more frequent link breakage; therefore it needs more routing packets to maintain links, so the routing overhead of all algorithms increases in both scenarios. The BSCAR algorithm has the link prediction mechanism; as a result, the increase rate of its routing overhead is lower than that of the other three algorithms. The BSCAR algorithm can provide lower routing overhead in both scenarios no matter how the movement speed increases, which decreases the energy cost in the network to a certain degree. Meanwhile, the routing overhead of DSR algorithm is relatively large because it adopts flooding mechanism in routing discovery process.

Figure 8

Routing overhead versus maximum movement speed in sparse formation.

Figure 9

Routing overhead versus maximum movement speed in concentrated formation.

7.2. Routing Performance Metrics versus Maximum Communication Range

We also test the routing performance of the four algorithms with varying maximum communication range. Some simulation parameters are changed. The changed simulation parameters are given in Table 2. Other parameters are the same as in Section 7.1.

Table 2

The changed simulation parameters.

Parameters	Values
Environment size	3000 m ∗ 3000 m
Transmitter range	250 m–500 m
Maximum speed limit of an UAV	20 m/s

Figures 10 and 11 show the data packet delivery ratio versus maximum communication range for different algorithms in sparse and concentrated formation. The increase of communication range can reduce the effect of high mobility; the stability of routes used for transmitting data increases; as a result, the data packet delivery ratio of all these algorithms increases in both scenarios. No matter how the maximum communication range changes, the BSCAR algorithm can always provide a higher data packet delivery ratio than the other three algorithms in both scenarios. That is because the proposed algorithm can get the more stable and uncongested routes.

Figure 10

Data packet delivery ratio versus maximum communication range in sparse formation.

Figure 11

Data packet delivery ratio versus maximum communication range in concentrated formation.

Figures 12 and 13 show the average end to end delay versus maximum communication range for different algorithms in sparse and concentrated formation. The BSCAR algorithm shows lower delay in both scenarios than the other three algorithms with the increase of communication range. The BSCAR algorithm can provide lower data transmission delay for different communication range.

Figure 12

Average end to end delay versus maximum communication range in sparse formation.

Figure 13

Average end to end delay versus maximum communication range in concentrated formation.

Figures 14 and 15 show the routing overhead versus maximum communication range for different algorithms in sparse and concentrated formation. With the increase of communication range, the links become more stable and the current routes are less likely to be disabled. As a result, the routing algorithm does not need to conduct routing discovery frequently, which can reduce the number of routing packets. Therefore, the routing overhead of all algorithms decreases in both scenarios with the increase of communication range. It is clearly shown that the routing overhead has been significantly decreased by adopting the proposed BSCAR algorithm.

Figure 14

Routing overhead versus maximum communication range in sparse formation.

Figure 15

Routing overhead versus maximum communication range in concentrated formation.

8. Conclusion

If traditional routing algorithms are adopted in ad hoc UAV network, the performances would be so low that they are unable to meet the demands for the information sharing of multiple UAVs carrying out missions in formation. We propose a bionic optimization based stability and congestion aware routing algorithm, BSCAR algorithm, which is inspired by the movements of ant colony and the foraging model of Physarum polycephalum and is integrated with dynamic source routing algorithm. This algorithm effectively avoids congestion and link breakage by sensing the stability of a route and the congestion level of a route. Meanwhile, the algorithm can adjust the routing strategies to the varied UAV formation and prevent the corresponding performance from being compromised. Simulated performance comparisons have been made among BSCAR algorithm and DSR, Ant-DSR, and HOPNET algorithms; the results show that BSCAR algorithm can ensure lower average end to end delay, routing overhead, and higher data packet delivery ratio in both sparse and concentrated formation in battlefield environment, so it can meet the demands of UAVs carrying out missions in formation.