1 Introduction

A mobile ad hoc network (MANETs) can be operated on multi hop wireless networks that comprises of self assembling autonomous nodes and these are dynamic temporary networks. MANETs does not use any centralized or existing infrastructure and when nodes are mobile, it can change its topology in a frequent manner. This network consists of freely moving hosts which can travel around the network and it holds each transmitting packets on the sake of every other nodes. In our paper, we look into the troubles in shortest path (SP) routing that is used to discover the routes between sources to particular destination with minimum cost related to the network. Perhaps, the cost factor depends on some factors: network throughput, reliability of the network and round trip delay. Thus, the network algorithms are used to develop, co-ordinate and disseminate the information regarding network states. In order to attain high performance, it renders executable routes among the nodes and it sends traffic by the selected path. This method has a problem called combinatorial optimization which grown in every planning and design circumstances [1, 2].

Generally, so many algorithms are available to yield solutions for SP problem such as Bellman-Ford algorithm, Dijkstra’s algorithm [3] and breadth-first search algorithm etc. Polynomial time complexity is the major retreat in above mentioned algorithms. So, in fixed infrastructure network the effectiveness of these algorithms provides better performance. In case of real time communications which has a property of frequently changing topologies that shows high computational complexities. Hence, these algorithms cannot provide suitable solution for computational complexity which presents in real time communication systems using SP. Since, some of the researches have been carried out to solve the computational complexity present in SP algorithms using artificial intelligence techniques like particle swarm optimization (PSO) [4], Artificial Neural Networks (ANNs) [5] and genetic algorithms (GA) [6].

However, these algorithms primarily concentrate on the static SP problem and while the topology change occurs in the network, it can consider this as a new network. Then, the solving procedure will be restarted for this new topology network. Because of the characteristics of MANETs like mobile nodes and battery exhaustion, the rapid topology change takes place and in MANETs, dynamic SP solving algorithms [7, 8] cannot give good performance and also it cannot satisfy the real time requirements since it needs frequent restart. So, there is a new approach is needed to meet the drawbacks in dynamic SP using mobile environment.

In this paper, a novel fuzzy based GA is used which can give the solution for dynamic network problem. In this proposed method, the paths between source and destination nodes have been represented with appropriate number of populations in GA. After certain time, these populations will be evolving to split into small populations and by exploiting the solution space it can precede its searching process. When the topology changes at once, the entire populations in a network will be processed in a way and then SP will be found.

We organize our paper as follows: in Sects. 2 and 3, we talk about the related work describes the basics of GA as existed in the literature. While in Sect. 4 the GA can be improved to find the SP. Simulation results are shown and discussed in Sect. 5. Finally, in Sect. 6 the conclusion is given.

2 Related Work

There are so many approaches have been introduced to solve the SP problem in Wireless Sensor Networks (WSNs). At first, the throughput optimal routing is proposed in [9] and then analyzed in various networks like cooperative relay networks [10, 11], multi hop wireless networks [12–14] and cellular networks [15]. Joint scheduling and joint power control based algorithms have been addressed in and [16]. Optimal scheduling which is used in multicast routing is considered in [17]. The SP information are used in back pressure algorithm and their performance has to be enhanced are studied in [18]. Low complexity routing algorithms are studied in [19]. To minimize the number of hops an alternate algorithm is used which is given in [20–24].

In order to extend the network life-time, an energy aware routing is used and it attracts the interest of everyone. Minimize maximum node cost and maximize time to partition are some of the energy aware quantities and SP algorithms mainly focus on such quantities are mentioned in [25]. To balance the energy consumption in every node in the network, there are two algorithms are employed such as flow argumentation algorithm and flow redirection algorithm that are explained in [26]. Extensions along this approach were addressed in [27]. Power aware routing that reduces most former times while a packet cannot be sent are studied by the author in online were described in [28]. A usage of geographical locations of wireless nodes for energy managements are given in [29]. When the unnecessary nodes are turned off, we can save the energy are designed in GAF algorithm was proposed in [30]. The conventional protocols like DSR and AODV protocols which haven’t any awareness on energy are re-imposes to take for energy-aware metrics.

3 Genetic Algorithm

Genetic algorithms are optimization techniques based one group of closely related algorithms that draw upon ideas of Darwinian evolution and genetics. Goldberg [31] defines GA are stochastic search algorithms based on the mechanism of natural selection and natural genetics. They are highly parallel and adaptive. GAs exploits the idea of the survival of fittest and an interbreeding population to create a novel and innovative search strategy. They are a form of randomized search, in that way in which strings are chosen and combined is stochastic process. This is radically different approach to the problem solving methods used by more traditional algorithms, which tend to be more deterministic in nature, such as gradient methods used to find the minima in graph theory.

GA has been quite successfully, applied in machine learning and optimization problems. For a given problem to be solved, GA maintains a population of individuals called strings or chromosomes. These strings then are probabilistically modified by some genetic operators such as selection, crossover and mutation to get close optimal solution to the problem.

3.1 GA Working Methodology

In GA, the variables are represented as genes on a chromosome. A population of strings, representing solutions to a specified problem, is maintained by the GA. The GA then iteratively creates new populations from the old by ranking the strings and interbreeding the fittest to create new strings, which are closer to the optimum solution to the problem at hand. So I each generation, the GA create a set of strings from the bits and pieces of the previous string, occasionally adding random new data to keep the population from stagnating. The end result is a search strategy that is tailored for vast, complex, multimodal search spaces. The working method of GA involves several key genetic components: genetic representation, population initialization, fitness function, crossover, and mutation.

The following Fig. 1 shows the various steps in GA’s working principle.

Fig. 1
figure 1

GA’s working principle

Full size image

4 Proposed Algorithm

Our proposed genetic based SP routing algorithm is addressed for MANET operating within a fixed geographical region. This network is modeled as a network with undirected and connected topology graph G0 (N0, E0), where N0 are the set of wireless nodes (i.e. routers) and E0 represents the set of communication links connecting two nearby routers which are falling within the radio transmission range.

The following notations are used throughout this paper to represent the network and its components:

  • G (N 0 , E 0 )—Initial MANET topology graph;

  • G (N i , E i )—MANET topology after ith change;

  • s—Source node;

  • d—Destination node;

  • Pi(s,r)—Path from s to d in graph G;

  • DS—Total amount of packet sent from source node to destination node;

  • DR—Total amount of packet received at the destination node;

  • DD—Total amount of packet dropped throughout the network;

  • TT—Total packet transfer time.

In our approach, the network under consideration is represented as graph with 10 nodes (represented with integers 0, 1…9 corresponding to nodes in the route, whereas 0th node is called source node and 9th node is called as destination node). Excluding these source and destination nodes, the remaining eight nodes are undergone for GA process.

Initial population with two chromosomes is taken first, and their corresponding genes values are randomly selected from the 8 routing nodes without any repetition within the chromosomes. This step is illustrated in Fig. 2. In Fig. 2:

Fig. 2
figure 2

Initial population (a) Chromosome 1 (b) Chromosome 2

Full size image

  • S, D source and destination nodes,

  • C1N1, C1N2…C1N10—Genes (nodes) in chromosome 1,

  • C2N1, C2N2…C2N10—Genes (nodes) in chromosome 2

Then, single bit crossover between chromosome 1 and chromosome 2 is carried out in which half of the gene values are exchanged across the chromosomes. This step is illustrated in the Figs. 3 and 4. In Fig. 3, the genes marked with double brackets are swapped across chromosome 1 and chromosome 2 respectively. Figure 4 shows the results of genes position after crossover. Followed the crossover, single bit mutation is done in which gene values are interchanged within the chromosomes itself. Figures 5 and 6 shows the gene position before and after the mutation process.

Fig. 3
figure 3

Genes position before crossover (a) Chromosome 1 (b) Chromosome 2

Full size image
Fig. 4
figure 4

Genes position after crossover (a) Chromosome 1 (b) Chromosome 2

Full size image
Fig. 5
figure 5

Genes position before mutation (a) Chromosome 1 (b) Chromosome 2

Full size image
Fig. 6
figure 6

Genes position after mutation (a) Chromosome 1 (b) Chromosome 2

Full size image

At the end of the crossover and mutation process, we arrive at two new chromosomes with altered gene values that vary from initial population. Now we have four chromosomes equivalent to four different routing paths for which fitness values should be estimated. For each chromosome, DS, DR, DD and TT values are measured and the optimum chromosome to carry into the next generation is selected based on the fitness function computed using fuzzy logic.

The fitness function using fuzzy logic is designed in such a way that any one of the following fuzzy conditions should be met by the route in order to say that this is the optimum path. Let us consider, are the minimum values required to transmit a packet through the network via the selected route. Then the required fuzzy sets are:

  • (DS> & DR> & DD< & TT<) ||

  • (DS> & DD<) ||

  • (DS> & DR>) ||

  • (DS> & TT<) ||

  • (DS> & DR> & TT<) ||

  • (DR> & DD<) ||

  • (DD< & TT<) ||

  • (DR> & TT<) ||

  • (DR> & DD<) ||

  • (DR> & TT<)

The chromosome which gives optimum result based on the above fuzzy conditions is taken to the next generation and other chromosomes are discarded. Now, along with the current one, one more chromosome is formed with new randomly selected genes (nodes). Then the above mentioned genetic operators will be repeated for these two new chromosomes that will undergo further offspring procedure. This procedure is repeated up to particular iterations until an optimum solution is achieved. Once achieved, the chromosome which has been selected finally is considered the shortest route.

5 Simulation Work

The proposed algorithm was applied to network topology shown in Fig. 7. The objective is to find the SP for the source node 1 to reach destination node 10. The network in Fig. 7 is simulated using NS2 simulator to find the SP. The initial population consists of 2 chromosomes with 10 genes of each. The best results are obtained using single points of crossover. The simulation result for various iterations is given in the Tables 1, 2, 3 and 4.

Fig. 7
figure 7

Network topology for simulation

Full size image
Table 1 Simulation results for all measures
Full size table
Table 2 Simulation results DS and DR
Full size table
Table 3 Simulation results for TT and DR
Full size table
Table 4 Simulation results for TT and DD
Full size table

Table 1 shows the results obtained for four network parameters by applying the proposed method with different number of iterations. From the table, it is very clear that as the number of iterations increases, the amount of packet sent and amount packet received reaches high, while the amount of packet dropped goes low with decrease in transmission time which shows the potential of our proposed method.

The following figures illustrate the results obtained for various iterations.

In Fig. 7, the path marked in green color (0 → 3 → 4 → 6 → 9) indicates the SP found by our proposed method.

In order to prove the effectiveness of our proposed algorithm further, our algorithm is compared with different existing algorithms for various network parameters with different network nodes and the comparison results are given as follows (Figs. 8, 9, 10, 11).

Fig. 8
figure 8

DR versus Iterations

Full size image
Fig. 9
figure 9

TT versus Iterations

Full size image
Fig. 10
figure 10

DD versus Iterations

Full size image
Fig. 11
figure 11

DS, DR versus Iterations

Full size image

Table 5 contain the comparison results for the network parameter “Data received” for the networks of 100, 300 and 600 nodes respectively. From these tables, it is very clear that our proposed method delivers highest data to the destination comparing to others. Comparison result for “Data send”, “Data received” and “Data dropped” for the network consists of 100 nodes is given in the Table 6. Our proposed method is computationally less cost than others.

Table 5 Comparison of network parameters for 100, 300 and 600 nodes
Full size table
Table 6 Comparison based on number of iterations
Full size table

Figure 12 shows that the average end to end delay and it is defined as the time taken to transmit the data between one end user to another end user. The proposed technique has lesser end to end delay of 1800 ms. The other techniques of DAWMNet, AntHocNet, ARAWSN and AOMDV has higher delay due to the more number of users in the existing techniques. These existing techniques increases the delay but the proposed scheme reduces the delay with the help of topology maintenance.

Fig. 12
figure 12

Average End to End delay

Full size image

Figure 13 shows that the queueing length per node analysis and this has been calculated based on the queuing length of each node. The proposed technique has lesser queuing length compared to other techniques. The traditional algorithm has high queuing length and this analyzed per node. When the queuing interval is high that will increase the queuing length for each node. But the proposed scheme has low queuing interval so that reduces the queuing length per node has reduced. That will increase the network performance.

Fig. 13
figure 13

Per-node Queue length

Full size image

The average number of hops between the source and destination is calculated using the routing table. Based on that information, proposed technique has lesser average number of hops which is shown in Fig. 14. By reducing the number of hops between the source and destination will reduce the delay and increase the network efficiency. The proposed scheme is used to increase the reliability and scalability and this has to maintain the topology. Lesser number of hop counts between the source and destination will transmit the data without loss rate and failure rate.

Fig. 14
figure 14

Average number of Hops

Full size image

The lesser number of hops and hop count has reduced the delay. If the delay decreases the delivery ratio is increased. That delivery ratio increases in the proposed technique which is shown in Fig. 15. Delivery ratio is defined as the ratio of number of packets successfully received with respect to the number of packets transmitted. Compared to other traditional algorithms, proposed scheme increase the delivery rate and decreases the drop rate. When the delivery rate increases that reduces the routing overhead. This proposed algorithm has high reliable communication and balancing the load without flooding and increases the delivery rate.

Fig. 15
figure 15

Delivery Rate Analysis

Full size image

6 Conclusion

A novel multi-path shortest routing algorithm for wireless networks is proposed in this article. The proposed algorithm uses genetic optimization algorithm to find the SP among the different nodes in the network. The simulation results demonstrate that the proposed algorithm works well when compared to the traditional algorithms in terms of average data transfer time, data sent, data received, data dropped and routing overhead. Moreover, the proposed algorithm can adapt with topological changes. Therefore, this algorithm achieves deterministic and reliable communication, ensures load balance, and has the ability to adapt with topological changes without high flooding. Several possible lines of work can be studied further on this proposed method. The advantages of this approach in larger number of nodes network are not that evident. Thus, the proposed algorithm should be improved to be made to allow it to adapt to larger network scales. And the proposed algorithm will be improved to combine with the Neural Fuzzy System to improve the accuracy in networks with larger number of nodes.