1 Introduction

Wireless mesh networks (WMNs) are dynamically self organizing, self configuring and easily deployable evolutionary wireless networks where nodes are capable of automatically creating and maintaining mesh connectivity between them. This kind of networking is very suitable for applications such as broadband home, community, neighborhood and enterprise networking etc. The data packets hop from one node to another until these reach the terminal node based upon multi hop transmissions. A detailed overview of WMNs discussing the challenges and open research issues of each layer, security, mobility management, cross layer design etc. is presented by Akyildiz et al. [1].

Nodes in WMNs are categorized in two classes: (1) Wireless Mesh Routers (WMRs); having either fixed location or limited mobility and (2) wireless mesh clients (WMCs). The architecture of WMNs can be classified as: (1) Infrastructure/Backbone WMN: In infrastructure type WMNs WMRs form an infrastructure mesh for WMCs. (2) Client WMNs: client WMNs provide peer-to-peer networks and WMCs perform routing and self-configuration functions too. (3) Hybrid WMNs: The most applicable WMN architecture-hybrid mesh is the combination of infrastructure and client meshing. WMCs can access the network through WMRs as well as directly meshing with other WMCs [1]. Popular commercial applications, architectures and key research areas are discussed by Bruno et al. [2].

WMNs are highly dynamic networks. This unpredictable dynamic network conditions critically affect the performance of WMNs. It is required that routing policies must work in a decentralized, self-organizing and self configuring way, while optimizing network resource utilization and fulfilling QoS requirements [3, 4]. The objective of routing policies is to maximize probability of data delivery, minimize delay, maximize throughput, minimize energy consumption, dynamically balancing the traffic load etc. It was shown by Decouto et al. [5] that conventional shortest path routing metric is not an affordable criterion to ascertain good paths. The performance metrics and routing issues in WMNs are discussed in detail by Waharte et al. [6]. The performance parameters in a WMN can be categorized as per flow (delay, packet loss ratio, delay jitter, hop count, throughput and interference); per node (computation complexity and power efficiency); per link (link quality, channel utilization, transmission rate, and congestion); inter flow (interference and fairness) and network wide parameters (QoS, total throughput etc.). Commonly used performance metrics are hop count, Expected Transmission Count (ETX), Expected Transmission Time (ETT), energy consumption and availability of reliable paths. Routing protocols can further be categorized based upon routing philosophy, network organization, location awareness and mobility management [6].

Due to complexities and constraints in exact reasoning based routing in dynamic wireless networks, nature inspired soft computing techniques have attracted significant attention from the research community. A detailed description of various nature inspired meta-heuristic algorithms including ACO, bee algorithm, bat algorithm, cuckoo search, firefly algorithm, particle swarm optimization (PSO) etc. is presented by Yang [7]. A genetic algorithm (GA) based dynamic shortest path routing approach was proposed by Yang et al. [8]. Soft computing techniques i.e. GA and Neural Networks approach was applied to optimize quality of service (QoS) parameters for channel allocation in cellular networks [9]. A hybrid combination of multi objective particle swarm optimization (MOPSO) and GA is proposed by Benyamina et al. [10] to optimize the performance of WMNs. An approach for routing in Mobile Ad hoc Networks (MANETS) based upon swarm intelligence is proposed by Caro et al. [11]. This approach was inspired from Ant Colony Optimization (ACO) algorithm [12, 13]. An insect society collective behavior based routing for next generation networks was reported by Farooq et al. [14].

In this paper, we propose optimized shortest path routing strategies appropriate for dynamic WMNs. We explored ACO, BB-BC and Firefly based optimization algorithms to evaluate near shortest path under a given time constraint as dictated by the dynamics of WMN. We first create a mesh network of all those nodes which are within a specified radio range of at least one of the network nodes. We then periodically update and maintain the network by including the new nodes entering the radio range of network and deleting those nodes which have left the radio range of the network. After a network is established, all network nodes compute the integrated link cost (ILC) for the adjacent nodes. This ILC decides the path length that exists between a given source and destination (terminal) node pair. On the given information by the ILC module for adjacent nodes, optimal paths/near shortest paths are enumerated. In this paper we enumerate near shortest path using new ACO, BB-BC and Firefly based shortest path evaluation algorithms. Based upon evaluated near shortest paths, routing tables are updated periodically, thus taking care of dynamically changing environment. This ensures that most of the times routing is near shortest path based routing. The proposed algorithms were simulated in MATLAB environment and the routing performance of these proposed algorithms is compared with Adhoc On-demand Distance Vector (AODV) [15] and Dynamic Source Routing (DSR) [16] algorithms.

The remainder of the paper is organized as follows. Section 2 explains the formulation of hybrid performance metric based upon fuzzy logic. Section 3 presents the description of proposed soft computing based routing approaches. Node architecture for the proposed system model and the proposed routing algorithm are presented in Sect. 4. Section 5 presents the detailed results and discusses the performance and applicability of the proposed algorithms. Finally the conclusions are drawn in Sect. 6.

2 Performance Metric Formulation

Fuzzy logic has emerged as a simple yet powerful methodology to solve non-linear functions of arbitrary complexities with vague, ambiguous or incomplete information while extracting definite conclusions [17]. We choose fuzzy logic as a suitable candidate to evaluate the integrated link cost (ILC) of WMNs based upon various input parameters. A fuzzy link cost based approach to achieve quality of service (QoS) and quality of experience (QoE) in WMNs is proposed by Gomes et al. [18]. In wireless multimedia sensor networks, fuzzy logic controller for traffic load parameter with priority based rate reduces the delay and loss probability [19]. The proposed ILC measure in this paper consists of four vital parameters of the network and nodes: throughput, end-to-end delay, jitter of the link and the residual energy of the node. For a link between adjacent nodes high throughput, low end-to-end delay and low jitter are the required conditions. A variety of applications in ‘always on’ dynamic multi-hop WMNs require optimal use of node energy. As WMRs deal with more heavy traffic load, optimized use of energy at WMRs is more significant. Keeping in mind the constraints on residual energy of nodes in wireless sensor networks an intra grid architecture [20] as well as new hierarchical clustering topology architectures [21] are proposed to obtain a longer network lifetime. Thus considering the significance of residual energy of a node we have included this parameter to optimize the performance of WMNs. The node having less energy must be used accordingly for hoping or other routing purposes. Based upon these four parameters the fuzzy logic evaluated ILC measure is used as the distance between the two particular adjacent nodes.

A basic fuzzy system as shown in Fig. 1 consists of four major modules: Fuzzification module, Inference engine, knowledge base module and Defuzzification module [22]. The fuzzification module transforms the crisp input(s): throughput, delay, jitter of the link and residual energy of the node into corresponding fuzzy values (linguistic variables). These fuzzy values are then processed (rule composition, implication and aggregation) in fuzzy domain by inference engine based upon the knowledge supplied by the domain expert(s) and produces fuzzy set as output. Defuzzification module transforms the processed output of inference engine from fuzzy domain to crisp domain.

Fig. 1
figure 1

A basic fuzzy system with input and output parameters

Full size image

The knowledge base module contains the knowledge of the application domain and the procedural knowledge. It consists of a data base and linguistic (fuzzy) control rule base or production rules. The data base furnishes the necessary definitions which are used to define linguistic control rules and fuzzy data manipulation in an fuzzy logic Controller. The rule base characterizes the control goals and control policy of the domain expert by a set of linguistic control rules.

Firstly the current measured values of these inputs are fuzzified at fuzzification module. This module receives the crisp inputs. These input variables are then scale mapped that is transferred from the range of values of input variables into corresponding universe of discourse (membership values). The input crisp variables transformed to fuzzy variables. The universe of discourse of fuzzy variables is divided into fuzzy subsets. The input variable is mapped into these subsets with varying grade of membership that are limited to an interval between 0 and 1, i.e., any value between 0 and 1 can express the membership degree of a certain element of the fuzzy set based on the inference functions used. Usually, the relevance degree of a value ‘χ’ regarding a membership function is represented by μ(χ). If A is a fuzzy set in a universe U, the membership of χ in A is evaluated by the membership function μ(A) as following [23]:

$$ \mu_{A} \left( \chi \right){:}\,U \to \left[ {0,1} \right] $$
(1)

And fuzzy set A is represented as

$$ A = \left\{ {_{i} , \mu_{A} ( {_{i} })} \right\}\quad \forall \in A $$
(2)

There are largely three types of fuzzifiers: singleton fuzzifier, Gaussian fuzzifier, and trapezoidal or triangular fuzzifier.

Figure 2 illustrates the commonly used triangular and trapezoidal membership functions. The triangular and trapezoidal membership functions are specified as follows:

$$ Triangle\,(\chi {:}\,a,b,c) = \left\{ {\begin{array}{*{20}l} 0 \hfill & {\chi \le a} \hfill \\ {\frac{{\chi - a}}{{b - a}}} \hfill & {a \le \chi < b} \hfill \\ {\frac{{c - \chi }}{{c - b}}} \hfill & {b \le \chi < c} \hfill \\ 0 \hfill & {\chi \ge c} \hfill \\ \end{array} } \right. $$
(3)
$$ Trapezoid\,(\chi {:}\,a,b,c,d) = \left\{ {\begin{array}{*{20}l} 0 \hfill & {\chi < a} \hfill \\ {\frac{{\chi - a}}{{b - a}}} \hfill & {a \le \chi < b} \hfill \\ 1 \hfill & {b \le \chi < c} \hfill \\ {\frac{{d - \chi }}{{b - c}}} \hfill & {c \le \chi < d} \hfill \\ 0 \hfill & {\chi > d} \hfill \\ \end{array} } \right. $$
(4)

Four linguistic input variables are Throughput, End-to-end Delay, jitter and residual energy and integrated link cost is the linguistic output variable. Low, medium and high are the linguistic values (fuzzy sets) for Throughput, jitter, Residual energy and ILC. For End-to-end Delay less, medium and high are the linguistic values. Membership functions of inputs as well as output: are shown in Fig. 3.

$$ \varvec{Integrated\, Link\, Cost }\,\left( {\varvec{ILC}} \right) = \varvec{f}\left( {\varvec{Throughput},\,\varvec{ Delay},\,\varvec{ Jitter},\,\varvec{ Residual}\_\varvec{Energy}} \right) $$
(5)
Fig. 2
figure 2

Triangular and trapezoidal membership functions

Full size image
Fig. 3
figure 3

Membership functions for the fuzzy set values. a Throughput, b end to end delay, c jitter, d residual energy, e integrated link cost

Full size image

Integrated link cost is a function of throughput, delay, jitter of the link and the residual energy of the node. Firstly the current measured values of these inputs are fuzzified and then processed by the inference engine where rule composition takes place. One such rule is given as:

If Throughput is High AND Delay is Less AND Jitter is Low AND Residual_Energy is High then ILC is Low.

Here linguistic variables Throughput, Delay, Jitter and Residual_Energy are the inputs; ILC is output; High, Medium, Less and Low are the linguistic values (fuzzy sets) in their universe of discourse. The input and output parameters with their fuzzy sets are shown in Table 1. In our proposed module 3 × 3 × 3 × 3 = 81 rules are formed.

Table 1 Input and output parameter membership functions
Full size table

These rules are then implicated by Mamdani implication process [24]. The output of each implicated rule is a fuzzy set and all these fuzzy sets are then aggregated. The resulting one aggregated fuzzy set is then defuzzified to present a single crisp output (integrated link cost).

From Fig. 3e the defuzzified output value is calculated as:

$$ ILC^{*} = \frac{{\int \mu_{i} \left( x \right).xd\left( x \right)}}{{\int \mu_{i} \left( x \right)d\left( x \right)}} $$
(6)

where μ i (x) is the membership of the output of ith rule (rule strength) and x i is the weight associated with the ith rule (action taken).

3 Proposed Algorithms

3.1 Ant Colony Optimization (ACO)

Ant Colony Optimization (ACO) is a population based meta-heuristic approach to solve combinatorial optimization problems by offering ‘good enough’ solutions in appropriate time [11, 13]. Social insect societies e.g., ant colonies are distributed systems that collectively exhibit intelligent behavior. ACO is inspired by the food searching (foraging) behavior of the real ants. Initially ants search for food randomly. After finding a food source, ants return to their nest while depositing a chemical pheromone trail on the ground. Other ants are guided to the food source by the quantity of pheromone deposited on various paths.

The Simple ACO (S-ACO) algorithm for finding the shortest path between source and terminal node in a network is as follows:

A completely connected, directed topology graph G (N, L) having N nodes and L links between adjacent nodes with a positive weight (cost) d ij is given. Neighborhood of an ant k at node i is given as N k i while L k is the length of ant k’s path. Minimizing the cumulative length of the path (cost) is considered as objective function. Initially a constant amount of pheromone τ ij between ith and jth node is assigned to all arcs of the graph. At a node i, the probability of selecting node j as next node with pheromone trails τ ij by ant k is computed as follows:

$$p_{{ij}}^{k} = \left\{ {\begin{array}{*{20}l} {\frac{{\tau _{{ij}}^{\alpha } }}{{\sum _{{l \in N_{i}^{k} }} \tau _{{il}}^{\alpha } }}} \hfill & {if\,j \in N_{i}^{k} } \hfill \\ {0,} \hfill & {if\,j \notin N_{i}^{k} } \hfill \\ \end{array} } \right.$$
(7)

where α is a constant. Previous node is not taken as next node to avoid loops. The ant k at node i further checks its neighborhood and hops from node to node using this stochastic decision criterion until the termination node is achieved. After reaching at terminal node, the forward ant k is converted into a backward ant to retrace the travelled path. The aim of this path retracing is to update the routing information at each node while eliminating the loops. Adaptation to new routing information is regulated by α. While returning to the source node, the ant k updates the pheromone value of arc (i, j) as

$$ \tau_{ij} \leftarrow \tau_{ij} + \Delta \tau^{k} $$
(8)

where Δτ k is the increment in pheromone quantity. For shorter paths more pheromone is deposited. The deposited pheromone trails at each arc evaporates similarly to normal evaporation of real pheromone in nature. The objective of the pheromone diffusion process is to avoid quick convergence to a sub optimal route. At arc (i, j) pheromone trails are updated as

$$ \tau_{ij} \leftarrow \left( {1 - \rho } \right)\tau_{ij} , \,\rho \in \left( {0,1} \right] $$
(9)

where ρ is an evaporation constant. The routing tables obtained are updated at regular interval or at detection of a change in network configuration.

Pseudo Code of the ACO based proposed routing algorithm for WMNs is as given in Fig. 4.

Fig. 4
figure 4

Pseudo Code of the ACO based routing algorithm applied in WMNs

Full size image

3.2 Big Bang Big Crunch (BB-BC)

The Big Bang theory is one of the most widely accepted theories of the evolution of this universe [25]. It is believed that that universe began about twelve to fifteen billion years ago in inflation similar to an explosion like situation. The nature of inflation was such that for an incomprehensibly small fraction of a second, the universe was an infinitely dense and infinitely hot fireball. A peculiar form of energy that we don’t know yet, suddenly pushed out the fabric of space time in a process called “inflation”, which lasted for only one millionth of a second. Thereafter, the universe continued to expand but with slower pace.

The BB-BC theory believes that energy discharged by the initial explosion i.e., kinetic energy, is counterbalanced by the energy of bodies attraction known as gravitational pull. If there is enough mass so that the later is bigger than the first when a critical density is reached, the expansion will stop and the universe will start to contract, leading to an end very similar to its beginning, named by the scientists as the big crunch (great implosion). In the Big Bang phase, energy dissipation produces disorder and randomness as the main feature of this phase. In the big crunch phase, randomly distributed particles are drawn into an order. This theory of repeated big bang followed by big crunch phases forms the basis of an optimization algorithm called the Big Bang-Big Crunch optimization algorithm [26, 27].

3.2.1 BB-BC Optimization Algorithm

Initially a set of candidate solutions (population) is generated randomly in the search space. The fitness as defined by the objective function, of each solution is calculated and ranked accordingly. After the random Big Bang phase contraction is applied in big crunch phase to compute the centre of mass as:

$$ x^{C} = \frac{{\mathop \sum \nolimits_{i = 1}^{N} \frac{1}{{f^{i} }}x^{i} }}{{\mathop \sum \nolimits_{i = 1}^{N} \frac{1}{{f^{i} }}}} $$
(10)

where x c = position of the centre of mass; x i  = position of ith candidate; f i = fitness function value of candidate i; N = population size.

Alternatively best fit individual can also be considered as the centre of mass in place of using Eq. (5). There after we generate new population around the centre of mass by adding or subtracting a normal random number whose value decreases as the iterations elapse. This can be formalized as:

$$ x^{new} = x^{C} + lr/k $$
(11)

where x C stands for center of mass, l is the upper limit of the parameter, r is a normal random number and k is the iteration number in process. Thus new point x new is upper and lower bounded. Figure 5 lists the Pseudo Code of BB-BC based Algorithm for optimal path evaluation in WMNs.

Fig. 5
figure 5

Pseudo Code of BB-BC based algorithm for optimal path evaluation in WMNs

Full size image

3.3 Firefly Algorithm (FA)

Firefly algorithm (FA) is a nature inspired evolutionary algorithm. It is inspired by the flashing light characteristics of fireflies. Fireflies produce short and rhythmic flashes to attract other fireflies, prey as well as a protective warning mechanism. The flashing light is produced by a process of bioluminescence. The flashing characteristics of fireflies can simply be described in three idealized rules [28–30]:

  1. 1.

    All the fireflies are unisex, so that attraction among them is unisexual.

  2. 2.

    Attractiveness is proportional to the brightness of the flash and the fireflies tend to move towards the brighter one in case of two flashing fireflies. Brightness decreases as their distance increases. It will move randomly, if no one is brighter than a particular firefly.

  3. 3.

    The brightness of a firefly is affected or determined by the landscape of the objective function.

In the case of continuous optimization problem e.g. optimization of routing path in WMN, the task is to minimize cost function f(x) for x∈ S (S-sample space). Cost function ILC is integrated cost function in the case of WMNs. For firefly i, x i represents a solution whereas f (x i ) denotes its ILC.

Initially all fireflies are dislocated in the sample space S randomly or deterministically following some strategy. Variation of light intensity and formulation of the attractiveness are the critical issues to be considered. Simply, it is assumed that the attractiveness of a firefly is determined by its brightness or light intensity which is related with the objective function.

The brightness I of a firefly at x can be denoted as I(x) ∝ f(x). The attractiveness β varies with distance r ij between ith and jth firefly. The attractiveness varies with the degree of absorption as light intensity decreases with distance. The light intensity, is a function of distance r, described as

$$ I\left( r \right) = I_{0} e^{ - \gamma r} $$
(12)

where I 0 is the actual light intensity and γ is the light absorption coefficient.The attractiveness β of a firefly can be represented as

$$ \beta = \beta_{0} { \exp }\left( { - \gamma r^{m} } \right),\,\left( {m \ge 1} \right) $$
(13)

where r is the distance between two fireflies and β 0 is their attractiveness at r = 0 and γ is a fixed light absorption coefficient.The distance between any two fireflies i and j at x i and x j respectively is computed by the Cartesian distance

$$r_{{ij}} = \left\| {X_{i} - X_{j} } \right\| = \sqrt {\sum\limits_{{k = 1}}^{d} {\left( {x_{{i,k}} - x_{{j,k}} } \right)^{2} } }$$
(14)

where x i,k is the kth component of spatial co-ordinate of x i and d is the number of dimensions.In two dimensional case distance is

$$ r_{ij} = \sqrt {\left( {x_{i} - x_{j} } \right)^{2} + \left( {y_{i} - y_{j} } \right)^{2} } $$
(15)

The movement of lesser bright firefly i towards another brighter firefly j is evaluated as

$$ {\mathbf{x}}_{i} = {\mathbf{x}}_{i} + \beta_{0} e^{{ - \gamma r_{ij}^{2} }} \left( {{\mathbf{x}}_{j} - {\mathbf{x}}_{i} } \right) + \alpha \left( {{\mathbf{rand}} - \frac{1}{2}} \right) $$
(16)

here the second term is due to the attraction as shown in Eq. (8) while the third term is randomization with α ∈ [0, 1] being the randomization parameter. “rand” is a random number generator uniformly distributed in [0, 1]. Mostly β 0  = 1 and α ∈ [0, 1]. Pseudo Code of the firefly algorithm is shown in Fig. 6.

Fig. 6
figure 6

Pseudo Code of the firefly algorithm

Full size image

4 Node Architecture

Figure 7 shows the proposed node architecture for WMN nodes. At each node there may be multiple inputs (\( X_{{i_{1} }} , X_{{i_{2} }} , \ldots X_{{i_{n} }} \) arriving from n adjacent nodes) and multiple outputs (\( Y_{{o_{1} }} , Y_{{o_{2} }} , \ldots Y_{{o_{m} }} \) forwarded towards m adjacent nodes). The Node Processing Unit (NPU) makes the decision of selecting the optimal links for corresponding communication within the constraints imposed by the network dynamics and assigns time slots through a queuing system for data packets to be routed. NPU provides this link state information to Parameter Evaluation Module (PEM) to evaluate various link parameters e.g. throughput, delay, jitter and residual energy of the node. Based upon this information a fuzzy logic based system evaluates the ILC i for the corresponding ith link. The routing tables of all nodes are updated periodically or on the occurrence of some event. This new information from the routing table is used for routing purposes.

Fig. 7
figure 7

Node architecture of a WMN node

Full size image

4.1 The Proposed Routing Algorithm and Validation

The proposed routing algorithm for establishing the near shortest path for a given source-terminal pair is as follows:

4.1.1 Algorithm

WMN initialization phase:

  1. 1.

    Create a WMN by adding the nodes falling within the radio range of mesh network.

  2. 2.

    Generate equal traffic from one node to its all adjacent nodes. Assuming equal throughput, network delays, jitter and full residual energy at each node. For each node compute shortest path to all other nodes of the network.

  3. 3.

    Create the routing tables and allow network traffic to flow.

WMN operational phase:

  1. 1.

    Maintain the network by adding incoming nodes and deleting the outgoing nodes.

  2. 2.

    Compute the ILC based distance, between the adjacent nodes.

  3. 3.

    For a given source terminal pair, evaluate the near shortest/shortest path using any of the nature inspired algorithms (ACO/BB-BC/FA).

  4. 4.

    Update the routing tables

  5. 5.

    Wait for stipulated time governed by the network dynamics.

  6. 6.

    Go to step 1.

4.1.2 Model Performance

In order to investigate and optimize the performance of routing algorithm of WMNs simulations were performed for various static and dynamic scenarios in MATLAB. We considered 9, 16, 25, 64 and 100 node networks for infrastructure WMN. These networks were placed within a 500 m × 500 m, 1000 m × 1000 m, 2000 m × 2000 m area. For client and hybrid WMNs. 10, 20, 30, 50 and 100 node networks were considered with an area of 500 m × 500 m, 1000 m × 1000 m, 2000 m × 2000 m. We varied transmission range of the nodes from 250 meters to 500 meters. In all the network models node number 1 acts as source and transmits data packets to the last node which is the terminal node (e.g. 10th node is the terminal node in a 10 node WMN). The data transmission is made possible through multiple hops via various adjacent nodes. In this type of wireless communication multiple routes/paths are available. Decision as regard to which path or route is to be used for any type of traffic, depends upon the current value of the ILC measure (distance) of the link connecting two adjacent nodes.

The proposed algorithms were implemented in MATLAB along with AODV and DSR for different architectures of WMNs with varying number of nodes, iterations as well as with different radio ranges and areas. The architectural and simulation details are provided in Tables 2 and 3 respectively. The near shortest/shortest path is computed by these five approaches for the same network architecture. The results for different WMN architectures are placed in Tables 4, 5, 6, 7, 8 and 9 for the proposed as well as conventional routing approaches. Each table presents the integrated link cost and processing time for a specific source-terminal node pair for varying number of nodes.

Table 2 Architectural details of WMNs
Full size table
Table 3 Simulation parameters
Full size table
Table 4 Results for client WMNs (20 trials for each set were conducted)
Full size table
Table 5 Results of DSR and AODV approaches for client WMNs
Full size table
Table 6 Results for hybrid WMNs (20 trials for each set were conducted)
Full size table
Table 7 Results of DSR and AODV approaches for hybrid WMNs
Full size table
Table 8 Results of static (Infrastructure) WMNs (20 trials for each set is conducted)
Full size table
Table 9 Results of DSR and AODV approaches for static (infrastructure) WMNs
Full size table

In an infrastructure WMN the nodes are placed uniformly in the specified area constructing a uniform mesh. In its routing tables only forward paths are considered to avoid loops. In client and hybrid WMNs, all the nodes are placed randomly in the specified area. This makes the adjacency matrix and hence, routing tables highly dynamic. Hybrid WMNs use some fixed Mesh Routers and there are dedicated links among them. Radio range of these Mesh Routers amongst them is assumed to be double the range of client nodes.

5 Results and Discussion

Client, hybrid and infrastructure type WMNs were simulated and the observations were recorded for various network environments. For each of network configurations 20 trials were conducted. The resulting observations are placed as Tables 4, 5, 6, 7, 8 and 9. Table 4 presents the results of the proposed routing approaches for 10, 20, 30, 50 and 100 node client WMNs and Table 5 depicts the results of DSR and AODV algorithms. The results of 10, 20, 30, 50 and 100 node hybrid WMNs are presented in Table 6 for the proposed routing approaches while the resulting observations for DSR and AODV are placed as Table 7. Tables 8 and 9 summarize the results of 9, 16, 25, 64 and 100 node Infrastructure (static) WMNs for the proposed and conventional routing approaches respectively.

Figure 8 presents specific network architectures of 10, 30, 50 and 100 node client WMNs. It portrays the random behavior of nodes. Figure 9 showcases network architectures of 10, 30, 50 and 100 node hybrid WMNs. WMRs are positioned on specific locations and having dedicated links amongst them. Figures 10 and 11 depict Time versus ILC plots for 10, 30, 50 and 100 node Client and hybrid WMNs respectively. Figure 12 draws the Time versus ILC plot for 9, 25, 64 and 100 node Infrastructure WMNs. For smaller network architectures the proposed algorithms updates the operational phase after an interval of 0.01, 0.02, 0.05, 0.07 and 0.1 s of time constraint while the larger networks are updated after every 0.05, 0.07, 0.1, 0.2 and 0.5 s of time constraint.

Fig. 8
figure 8

Network architecture (a–d) for 10, 30, 50 and 100 node client WMN

Full size image
Fig. 9
figure 9

Network architecture (a–d) for 10, 30, 50 and 100 node hybrid WMN

Full size image
Fig. 10
figure 10

Time versus ILC plot (a–d) for 10, 30, 50 and 100 node client WMN

Full size image
Fig. 11
figure 11

Time versus ILC plot (a–d) for 10, 30, 50 and 100 node hybrid WMN

Full size image
Fig. 12
figure 12

Time versus ILC plot (a–d) for 9, 25, 64 and 100 node Static WMN

Full size image

It was observed from all these results that proposed soft computing approaches namely ACO, BB-BC and FA outperform AODV in terms of ILC and processing time. The observations further ascertained that DSR outperforms ACO whereas BB-BC and FA performs better than DSR. In larger networks ACO is unable to converge towards optimal solutions in the given time frame whereas BB-BC and FA converge simply in the stipulated time. FA on the other hand converges much easily and with lesser time followed by BB-BC. As the number of nodes increase processing cost (time) increases accordingly. It was also observed that these proposed meta-heuristic approaches improve their performance with increasing processing time. However a WMN dynamics may allow only small amount of time within which the near shortest path must be computed and routing tables updated. Since, after this allowable time, nodes must have moved to new positions; new shortest or near shortest paths need to be found again.

6 Conclusion

This paper proposed three nature inspired routing algorithms for WMNs. The performance of these algorithms was compared with the two existing algorithms namely AODV and DSR. In order to compare the performance we defined a new performance measure namely integrated link cost (ILC). The ILC is based upon the four most significant WMN features namely throughput, delay, jitter and residual energy of the nodes. We applied fuzzy logic to integrate the four network parameters to a single performance measure. Based on these parameters the enumerated ILC was considered to be the distance between two adjacent nodes. Based upon this effective performance metric, the performance of five routing algorithms i.e. Firefly, BB-BC, ACO, DSR and AODV was enumerated between a specific source-terminal node pair. The proposed ILC measure does not affect the scalability and is quite suitable to the stochastic behavior of WMNs. All the five routing approaches were applied to 10, 20, 30, 50 and 100 node client and hybrid WMNs while 9, 16, 25, 64 and 100 node network architecture was considered for infrastructure (static) WMNs with various network topologies. The proposed soft computing based routing approaches were simulated for 0.01, 0.02. 0.05, 0.1, 0.2 and 0.5 s allowable time interval (constraint) for the same network topology. Effect of allowable computing time over ILC was recorded for the proposed soft computing based routing algorithms.

After the extensive simulations runs, we observed that Firefly optimization based routing strategy gives the best routing performance followed by BB-BC, DSR, ACO and lastly AODV. We further observed that Firefly, BB-BC and DSR based routing approaches yield almost similar results in terms of ILC however BB-BC and DSR are taking more time to select the optimized path compared to FA based approach. The ACO based routing algorithm required more computing time and is slower in converging to the optimal solution. Its performance is better than AODV only. For smaller networks, Firefly and BB-BC based approaches converge to reasonably good solutions in the stipulated time frame. ACO based approach was not able to converge to any reasonably good solution within given time frame. Hence, we find that this approach does not meet rigid WMN routing requirements adequately. Since, AODV and DSR performance does not meet WMN requirements at all these do not provide required solution within given time frame we are of opinion that these should be avoided for WMNs (Tables 4, 5, 6, 7, 8, 9). For large WMNs Firefly based routing approach outperforms other routing strategies in terms of ILC and computation time, making FA based approach most suitable followed by BB-BC based approach of the 5 approaches evaluated in this paper.