1 Introduction

The Big Bang Big Crunch (BB–BC) theory is one of the widely accepted theories of the evolution of our universe. Later this concept was formulated as a global optimization approach called BB–BC optimization algorithm [1,2,3]. Shakti et al. [4] extended it to a parallel BB–BC (PB3C) global optimization approach. PB3C is a multi-population approach and was demonstrated to have better convergence rate and accuracy than BB–BC based approach in a fuzzy model identification problem. The work reported here has been motivated by two objectives. The first one was to evaluate the PB3C performance on standards test functions and compare it with the performance of other algorithms. The second objective was to evaluate its performance on routing in WMNs. Routing in WMNs is a challenging issue that has attracted the attention of research community in the recent past [5]. Conventional static network shortest path routing approaches hit the road block in the case of WMNs where shortest path evaluation is quite difficult due to dynamic nature of WMNs in which almost all nodes can be mobile.

In order to assess the performance of PB3C algorithm and compare it with some of the commonly used algorithms available in the literature we evaluated the performance of PB3C algorithm on CEC-2014 test suite. It is an established fact today that in the case of complex problems falling in the category of NP hard or NP complete problems probability that a search will result into a best solution under a given time frame is very low and highly expensive computationally. Under such circumstances it has been observed that wherever best can be replaced with good enough solutions, soft computing approaches offer much better performance as compared to hard computing based approaches such as AODV, DSR etc. [6, 7]. Evaluation of shortest path under a given time constraint imposed due to node mobility in WMNs also belongs to this class of problems. Shakti et. al [8] presented 3 new integrated cost based, near shortest path routing approaches to wireless mesh networks. The algorithms performed reasonably well on small networks upto about 500 node WMNs. Their performance for higher node WMNs was observed to be unsatisfactory.

This paper evaluates the performance of PB3C algorithm on CEC 2014 benchmark and compares it with the performance of 16 other algorithms available in the literature. Further this paper proposes a PB3C based near shortest path routing approach to efficiently deal with the complex issue of routing in WMNs.

This paper is organized into 5 sections. Section 1 of the paper introduces the motivation for the paper, Sect. 2 discusses the simulation and performance of PB3C on CEC-2014 test bench and compares it with other algorithms. Section 3 proposes a PB3C algorithm based new routing approach, Sect. 4 discusses the implementation and performance of the approach for WMNs. The section compares the performance of proposed algorithm with 7 other algorithms found in the literature. Section 5 concludes the paper.

2 PB3C Algorithm and its Performance on CEC-2014 Test Bench

The original one population based big bang big crunch algorithm henceforth known as simple BBBC algorithm [1] has been modified to multi-population BB–BC called PB3C algorithm. The pseudo code for the PB3C approach is given as Algorithm 1. The Algorithm 1 and Algorithm 2 must update their elite(i) based upon local best of ith population. The algorithm was implemented in MATLAB and was tested using a Core i7 @ 2.2 GHz based laptop with 8 GB RAM. All the 30 functions of CEC-2014 test bench were tested with 25 trials for each function. We considered all functions with 10 dimensions only. The mean value of all the 30 functions is placed in Table 1. The functions on which PB3C gave unmatched results are given in Table 2.

The Table 3 indicates that PB3C gave best performance with minimum error for 7 functions. Out of these 7 functions there are 6 such function for which it gave performance unmatched by any other algorithm. For test function 26 it achieved the best results which was also achieved by 5 other algorithms namely UMOEAS, POBL_ADE, CMLSP, RMALSChCMA and MVMO. When we compare LSHADE and PB3C we find that both give minimum mean error on 7 test functions. However, LSHADE gives best performance on 3 test functions which no other algorithm could achieve and best performance (minimum mean error) on 4 other test functions namely function number f1, f2, f3 and f8; this best performance was also achieved by other algorithms namely FCDE, UMOEAS, DE_b6e6rlwithrestart,GaAPADE, RMALSChCMA and RSDE as well. As far as comparison with UMOEAS is concerned; UMOEAS performs best on 9 test functions but the UMOEAS is not unique on this count. This best performance of UMOEAS is also matched by other algorithms namely FCDE, DE_b6e6rlwithrestart, GaAPADE, RMALSChCMA, RSDE and SOO as well. Thus the observations clearly show that PB3C delivers unmatched best performance in 6 functions which no other algorithm could reach.

figure d
Table 1 Comparison of PB3C algorithm with other 16 algorithms on CEC-2014 benchmark functions
Full size table
Table 2 Number of functions for which PB3C gave the best performance
Full size table
Table 3 Comparative performance of various algorithms on CEC-2014 test bench
Full size table
Table 4 Architectural details of various client WMN scenarios
Full size table

3 PB3C Algorithm Based Routing Approach to WMNs

Wireless Mesh Networks (WMNs) have drawn significant attention of researchers in the recent past. These are rapidly deployable, self-aware, self-organizing, self-configured, self-healing and self-balancing networks. In WMNs within a given radio range each node (stationary or mobile) has the capability to join and create a network automatically. It is able to do so by sensing neighboring nodes with a similar capability within their radio range and admitting themselves to the radio network according to the given set of rules. Routing in WMNs is the process to direct data packets from a given source to a given destination. It requires significant attention in the dynamic network conditions of a WMN. It is desired that these routing algorithms must work in a decentralized self-organizing and self-configuring way in a highly dynamic environment. Due to their dynamic nature, routing in WMNs is a highly complex issue. Increasing size of WMNs further compounds the routing challenge. Due to complexities associated with exact reasoning there is an increasing demand for soft computing based techniques in WMN research. These techniques may make the WMNs more popular in terms of their self-organizing and self-configuring capabilities. Soft computing provides the optimal solution within an affordable resource/time permitted by the WMN dynamics. Since, computation times are very limited, the best solution needs to be replaced by good enough solutions such that a given WMN quickly adapts to dynamically changing environment [9]. The Parallel Big Bang and Big Crunch (PB3C) optimization is one such powerful tool that can help simplify the things. PB3C approach can be used to select the near shortest path for appropriate route selection in WMNs. The underlining priniciple is to compute appropriate path within a stipulated time frame and use it rather than the shortest path that may not get computed within a given time frame.

This appropriate path is the optimal cost path that may or may not be a least cost path. We shall call this optimal cost path as the ’near shortest path’. There are many different routing metrics available in the literature. Some of these are minimum hop count, per hop Round Trip Time (RTT) [10], Per-Hop Packet Pair Delay (PktPair) [11], Expected Transmission Count (ETX) [12], Expected Transmission Time (ETT), Weighted Cumulative ETT (WCETT) [13], Expected Transmission on a Path (ETOP) [14], Effective Number of Transmission (ENT) and Modified Expected Number of Transmissions (mETX) [15], Metric of Interference and Channel Switching (MIC) [16], Bottleneck Link Capacity (BLC) path metric [17]. A novel interference aware low overhead routing metric was proposed by Liran Ma et al. [18], cross layer link quality and congestion aware (LQCA)[19]. For the WMNs integrated link cost route function (ILC ) was defined as follows [6, 7, 20]:

$$\begin{aligned} \hbox {integrated link cost (ILC)} = \hbox {f (throughput,delay,jitter, node}\_\hbox {residua} l_{{\textit{energy}}}\hbox {)} \end{aligned}$$

Further we use the same route cost model for evaluating the cost as used in [20]

As discussed earlier PB3C is a multi-population based algorithm. In the PB3C algorithm based approach we generate a set of N populations of candidate solutions. Each population consists of NC candidate solutions. A route between source terminal pair is one potential candidate that may lead to near shortest path between source and terminal node. For our model we consider WMN as a connected, directed topology graph with nodes and links between adjacent nodes with respective ILCs. Our objective is to evolve an ILC based shortest possible path within a given timing constraint. We assume WMN under consideration to be static for the given time period (i.e. time constraint). We effect all movements of nodes after given timing constraint. For the next timing slot (time constraint) we consider network to be again static and recomputed the shortest path within the available time.

In order to create initial candidate solutions we construct the initial population as follows [9]:

We start to search a random path from source to destination by randomly selecting a node from the set of neighboring node of source node. Then, a node from the neighborhood of this node is selected randomly. We continue with this process until the destination node is reached. In order to keep the paths loop-free, those nodes which are already included in the current path are excluded from being selected as the next node to be added into the path, thereby avoiding re-entry of the same node into a path. This gives us a path between source and the destination node. Repeating this process, we get the initial population of N paths. The path with the lowest cost is selected as the elite.

In order to generate next generation from elite, we use the following steps to evolve a new candidate solution (route) from the elite:

  1. (a)

    Generate a random number R between 1 and S, Where S is the size of the route/path. It is the total number of nodes in the elite (\(\ell _{{\textit{best}}(i)}\)).

  2. (b)

    Retain first R nodes of the elite discarding the remaining path.

  3. (c)

    From \(\hbox{Rth}\) node onward discover a path to destination node. Thus evolving a new path between source and terminal node.

We continue the above procedure till the next generation with NC routes (Candidate Solutions) has evolved. We generate N such generations/populations.

figure e

4 Performance of the Proposed Routing Approach: Simulation and Results

We implemented the proposed approach in MATLAB and performed simulations considering dynamic scenarios. The architectural details of various Client WMN scenarios are given in Table 4. We considered 100, 500, 1000, 1500, 2000 and 2500 node client WMN architectures. The proposed PB3C based routing approach was applied to all these networks. Performance of all these networks was evaluated for stipulated time constraints. For a given network and for each timing constraint we conducted the 20 trials for each set. For each time set minimum, average and maximum cost paths were enumerated. In this case the stop and re-evaluate criterion was defined as the available computing time in the form of given time constraint. Though we performed observations for 100, 500, 1000, 2000 and 2500 node WMNs, for the sake of brevity we have focused our discussion on the performance of large networks consisting of 1500, 2000 and 2500 node client WMNs only. We have included the performance of small networks consisting of 100, 500 and 1000 nodes towards the end of this section.

4.1 Comparative Performance of 1500 Node Client WMNs

For 1500 node client WMNs we evaluated the performance of eight algorithms.We conducted 11 sets of trials; each set consisted of 20 trials. The results are placed as Table 5 and are also shown as histogram in Fig. 1. We observe that for a processing time constraint of 1.4 s AODV, ACO and DSR failed to generate a path in any of the 20 trials of the set. PB3C topped the table by generating the minimal cost path in 10+A trials out of the total number of 20 trials of the set. PB3C produced minimal cost path 10+A = 18 times. Here, by 10+A = 18 means in 10 trials algorithm produced minimum cost path from amongst all the algorithms and A= 8 is the number of trials for which BBO, BBBC, Firefly (FA), PB3C and BAT algorithms produced the same result in this particular set only. 2 times PB3C generated paths costlier than minimum cost paths generated by other algorithms. BBBC generated minimal cost path 1+A = 9 times, FA generated 1+A = 9 times.

We further, observe that except for timing constraints of 2.6, 3.5 and 4 s, PB3C outperformed all other 7 competitors. For the timing constraint of 2.6 s BBBC evaluated the minimum cost route 6+G = 11 times followed by PB3C 5+G = 10 times and FA 4+G = 9 times. G = 5 is the number of trials for which BBO, BBC, FA, PB3C and BAT algorithms gave equal performance i.e. produced minimum cost paths with equal ILC. For the timing constraint of 3.5 s BBBC evaluated the minimum cost route 9+J = 12 times followed by PB3C 8+J = 11 times; J = 3 is the number of trials for which BBO, BBC, FA, PB3C and BAT algorithms gave equal cost paths. ACO, DSR and AODV failed to discover route in any of the trial sets. At the timing constraint of 4 s PB3C and BBBC generated minimum cost path 5+K = 6 times followed by FA 4+K = 5 times. Though, AODV could discover minimum cost route 5 times out of 20 trials yet it cannot be recommended for use in client WMNs due to the fact that it failed to generate any path in 15 of the 20 trials. Indicating that AODV is highly unreliable for routing in client WMNs.

As shown in Table 6 (Comparative Performance of all algorithms) for the total of 220 trials from 11 sets PB3C gave the best performance 98 times followed by BBBC 55 times, FA 24 times and AODV 5 times. 38 times BBO, BBC, FA, PB3C and BAT algorithms achieved same performance except for ACO, AODV and DSR.

Table 5 Performance of 1500 node client network
Full size table
Table 6 Comparative performance of all algorithms
Full size table
Fig. 1
figure 1

Comparative performance OF 1500 node client WMNs

Full size image

4.2 Comparative Performance of 2000 Node Client WMNs

Table 7 and Fig. 2 present simulation results for 2000 node client WMNs. We observe that except for timing constraints of 2.6 and 3.5 s, PB3C outperformed all other competitors. At timing constraint of 2.6 s PB3C and BBBC gave equal performance by generating minimum cost paths 7+E = 12 times each, followed by FA 1+E = 6 times, In E = 5 trials out of 20, PB3C, BBO, FA, BAT and BBBC gave equal performance. At timing constraint of 3.5 s BBBC evaluated the minimum cost route 7+H = 11 times followed by PB3C, 6+H = 10 times and FA, 3+H = 7 times. ACO, AODV and DSR failed to discover a route in any of the trials of any of the sets.

As shown in Table 6 we find that for the total of 220 trials from 11 sets PB3C gave the best performance 106 times followed BBBC 51 times, FA 21. In 42 trials 5 algorithms namely BBBC, BBO, BAT, FA and PB3C achieved same performance.

Table 7 Performance OF 2000 Node Client Network
Full size table
Fig. 2
figure 2

Comparative performance of 2000 node client WMNs

Full size image

4.3 Comparative Performance of 2500 Node Client WMNs

For 2500 nodes networks 17 sets each consisting of 20 trials were conducted. Table 8 and histogram of Fig. 3 present the simulation results.

We observe that for all the timing constraints PB3C outperformed all other 7 algorithms. Up to time constraint of 8.5 s AODV failed to discover route in any of the trial sets. With the timing constraint going up to 9 s AODV discovered the route 4 times and failed to discover the route 16 times out of the total of 20 trials for this constraint. For both timing constraints of 9.5 and 10 s AODV succeeded to discover rout only once in each set and failed 19 times. Thus for the given client networks the AODV is highly unreliable protocol. Further the ACO and DSR could not discover the route in any of the trial sets.

For the total of 340 trials from 17 sets PB3C pulled up the best performance 167 times followed BBBC 91 times, FA 32 times, AODV 6 times and 44 times 5 algorithms i.e. BBBC, BBO, BAT, FA and PB3C based algorithms achieved same performance.

Table 8 Performance of 2500 node client network
Full size table
Fig. 3
figure 3

Comparative performance of 2500 node client WMNs

Full size image

4.4 Comparative Performance of All Approaches

For comparative performance of the given 8 WMN routing approaches we have conducted total of 1440 trials. We have included the observations on WMNs with 100, 500 and 100 nodes also here. As is evident in Fig. 4, the performance of BBBC and PB3C is better than other approaches for 100 and 500 node client WMNs. But when the number of nodes increases beyond 1000 nodes the performance of PB3C showed significant improvement, out performing all other competing approaches. Hence, for complex and large networks of 1000 node capacity and beyond the PB3C approach is observed to be the best suited approach as compared to given other soft computing and hard computing based approaches.

Fig. 4
figure 4

Comparative performance of all algorithm

Full size image

5 Conclusions

This paper evaluated the performance of PB3C algorithm on CEC-2014 test bench and compared it with 16 other commonly used algorithms found in the literature. Further PB3C algorithm was applied to near shortest path routing in WMNs. Routing under dynamic conditions as is the case with WMNs is a challenging issue faced by research community. As far as performance of PB3C over CEC-2014 test bench is concerned it gave best performance in 7 test bench functions. Out of these 7 it achieved unmatched best for 6 functions. Seventh best performance was achieved for test function number 26 of CEC-2014. However, this performance was also equalled by 5 other algorithms namely UMOEAS, POBL_ADE, CMLSP, RMALSChCMA and MVMO. Though UMOEAS gave minimal error on 9 functions yet this performance was equaled by other algorithms as well. Thus we find PB3C is the only algorithm that gives unique unmatched best performance in 6 of the test functions making it the best available algorithms out of the 17 algorithms. A PB3C based new routing approach was also proposed to evaluate near shortest path based routing in client WMNs. The approach was compared with the 7 other approaches found in the literature. Simulation results prove that the PB3C based routing approach outperforms all other 7 approaches when the network size grows to 1000 nodes or above. Thus establishing the clear superiority of the proposed approach over AODV, DSR, ACO, FA, BAT, BBO and BB–BC algorithm based approaches.