Keywords

1 Introduction

Flying ad-hoc network (FANET) is a network which consist of group of many Unmanned aerial vehicles (UAV). The UAVs are connected to ground stations for proper communication between them. FANETs are dynamic in nature because of their continuous moving nodes or UAVs.

There is also frequent change in topology because of their consistent node mobility. These special factors make FANET different from other ad-hoc networks. There are many major concerns in proper data transmission in FANETs. Routing is one of the major issues in FANETs. After the unsatisfactory results of many conventional routing algorithms in FANET, Nature Inspired Algorithm (NIA), because of their efficient results according to previous research done, can be claimed as the major rescue for the routing solution in FANETs.

Ant Colony Optimization (ACO), Firefly algorithm (FA), and Genetic algorithm (GA) are the three NIA on which the performance evaluation is performed in this paper.

ACO is selected because of its ability to adapt to changes dynamically which is required in UAVs. FA is another optimization algorithm which is used for network analysis and is dynamic in nature. These algorithms provide great results in the field of ad-hoc networks. Till now they have not been majorly used in flying ad-hoc networks.

In this paper, an experimental implementation of three NIAs i.e. ACO, FA, and GA and modified version of FA and GA has been given and further the results of these algorithms are compared to find which is the most suitable algorithm for routing in FANET.

NIA has a wide scope from the beginning. These algorithms provide sufficiently good results in all sorts of ad-hoc networks. Following is the work done till now on few of the majorly used swarm intelligence algorithms including ACO and FA:

The comparison of AntHocNet and BeeAdhoc is done with DSR, DSDV, AODV for routing in FANETs [1]. The simulation results of the modeling shows that the bio-inspired algorithms AntHocNet and BeeAdHoc outperforms the traditional routing algorithms AODV, DSDV and DSR. Another computing technique based on Bio-inspired algorithms is analyzed [2]. In this technique, the analysis is done on the basis of behavior of animals. A scheme based on clusters is proposed further [3]. This scheme is known as Bio-Inspired Clustering Scheme. It uses hybrid mechanism based on glow-worm swarm optimization and krill herd. Another protocol is proposed based on bio-inspired method [4]. The performance of the proposed protocol is showed with various other algorithms on different parameters. [5] This paper shows uses Bee colony algorithm for routing in FANETs.

There is also a wide use of Genetic algorithms in ad-hoc networks. Although major work is not been done in GA for FANETs, but it has been used broadly in various other wireless networks. Following is the literature work cited by scholars:

A GA based on multipath distance vector protocol is proposed [6]. The simulations results show that optimized goals are achieved by the proposed algorithm. MEGA (Maximum enhanced genetic algorithm), an improved GA which uses local search technique was introduced [7]. Another optimization method to find the shortest path in an ad-hoc network using genetic algorithm is given [8]. An energy efficient routing protocol is proposed by researchers [9]. According to the simulation results, delivery rate of this protocol is increased by 40% when compared to other protocols. Another clustering-based algorithm is developed later [10]. The algorithm improves the parameters of previously developed algorithms namely Bio-inspired clustering scheme and energy aware link-based clustering.

Fig. 1
An illustration depicts four U A Vs linked to a ground station and each other.

Multiple UAVs connected to ground station

Full size image

2 Existing Algorithms

Nature-inspired algorithms are the algorithms which observes and analyzes the biological phenomena of living organisms [11]. These algorithms are used for complex optimization problems. NIA has shown tremendous results in past in the field of routing. Nature-inspired algorithms are classified into two categories. One is Genetic algorithms (GA) and the other is Swarm intelligence (SI) algorithms. Both of these algorithms are inspired by the behaviour of animals.

Genetic algorithms are a part of evolutionary computing [12]. Genetic algorithm is used to find or select optimal path. It represents chromosomes which are the set of solutions.

The other type of algorithm is Swarm Intelligence. Swarm intelligence are also used for path selection in wireless ad-hoc networks. It is a subfield of Artificial Intelligence which is related to intelligent behaviour of swarms [13]. There are many algorithms which come under the category of swarm intelligence algorithms. The algorithms like Fish swarm algorithm, Cat swarm algorithm, Chicken swarm optimization algorithm, flock based are all swarm-intelligence algorithms which are based on the behaviour of animals.

2.1 Ant Colony Optimization (ACO)

Ant Colony Optimization (ACO) is a Swarm based Intelligence algorithm. The algorithm was proposed by Dorigo [14]. It is among one of the popular algorithms used for routing. ACO is an optimization method that imitates the nature of ants when they move for the search of food. It uses ants and analyze the pattern of moving ants. These ants travel from one point to another in search of food. ACO is used to find the shortest path during the travel of ants when they start from their source to destination.

2.2 Firefly Algorithm

Another swarm-intelligence algorithm introduced by Yang in 2008 is Firefly Algorithm [15]. It is based on the behavior of fireflies. In this algorithm, the shortest and optimal path can be computed by analyzing the behaviour of firefly. The algorithm uses the flash lights of fireflies for the analysis. Whenever a firefly is moving the other firefly gets attracted to it its flash light. Therefore, the attractiveness of firefly is directly proportional to the brightness of a firefly depending upon the objective function. The brightness of firefly reduces when the distance between them increases which means distance and brightness are inversely proportional to each other [16].

The fireflies update depends on the real time performance of fireflies and according to that the location will get updates. The parameters in this algorithm are fixed which means the search behaviour will be same in all iterations for any state.

Modified Firefly Algorithm (MFA)

A new modified algorithm is proposed in this paper which can make routing in FANETs more efficient. This new approach is based on clustering mechanism. In this approach, the nodes are divided into many clusters. All the clusters have cluster head. The cluster head is selected based on the residual energy. Node with the highest residual energy is selected as cluster head.

2.3 Genetic Algorithm

Genetic Algorithms (GA) are search based meta-heuristic algorithm belonging to the class of Evolutionary algorithms (EA). These algorithms are based on the mechanism of natural selection and genetics.

Modified Genetic Algorithm (MGA)

The proposed method is location-based routing for FANETs using mobile coverage concept. It allows the neighbor node to communicate in assigned coverage network area to find the nearby neighbor nodes and detect the malicious nodes in the coverage area. This ensures less packet loss during transmission.

3 Parameters and Methods

Network simulator, ns-3.26 is used for simulation. The data considered for simulation of the following algorithms: ACO, Firefly algorithm and Genetic algorithm is shown in Table 1.

Table 1 Simulation parameters
Full size table

The parameters used to analyze the performance of routing algorithms ACO, MFA, and MGA are Packet Delivery Ratio, End-to-End delay, Throughput, Routing overhead.

4 Results and Discussion

For simulation, the test analysis of routing algorithms ACO, Modified Firefly algorithm and Modified Genetic algorithm is given. The results show that all three algorithms have fine possibility to be used as an effective solution for routing in FANET.

Table 2 shows the values at 50th node for all the algorithms considered for simulation. The packet delivery ratio is highest in modified firefly algorithm. ACO is having the second-best packet delivery ratio whereas modified genetic algorithm has lowest ratio. This is because the modified firefly algorithm (MFA) is the most accurate of all the algorithms in respect to successful packet delivery. The end-to-end delay is an important parameter while packet transmission. This depends upon the node availability and link stability. ACO has the lowest delay following MFA. These two algorithms are efficient in both the factors. Overhead is the next parameter considered. MFA shows the lowest overhead generated. ACO and MGA shows the same overhead. Fourth and most important parameter is throughput. MFA again has the highest throughput of all the algorithms which makes it the most optimal algorithm in terms of successful packet transmission. ACO comes second in terms of throughput with a difference of around 2% whereas MGA shows the least throughput with a difference of 7%.

Table 2 Comparison of algorithms
Full size table

5 Conclusion and Future Scope

The idea of using of swarm intelligence algorithms has created new dimensions for routing in Flying ad-hoc networks. Since routing in FANETs is not an easy task, NIA has brought it altogether as an emerging solution for routing. Many conventional algorithms have already been used and still used to find an effective solution to this problem. The paper presents performance comparison of the most extensively used ACO algorithm with the modified version of firefly and genetic algorithm. As per the analysis, modified firefly algorithm outperforms all other swarm-intelligence algorithms on all the parameters. ACO performs second best after MFA. Therefore, from the analysis it can be said that ACO and FA are the two algorithms which have potential to act as an optimal routing solution.

Thus, enhancing ACO and other swarm-based algorithms on more parameters can be considered as a future work to solve the routing issue. Another novel swarm-based algorithm can also be proposed to improve routing in FANETs.