1 Introduction

Wireless mesh network (WMN) has emerged as a promising technology for providing ubiquitous access to mobile users and it facilitates fast and easy extension of local area networks into a wider area. They are multi-hop wireless networks consisting of a number of static wireless routers which are interconnected with each other via wireless links to provide communication services to mobile or static users in their vicinities. Some of the routers are directly connected to a fixed infrastructure and serve as gateways for other wireless routers. WMNs are dynamically self-organized and self-configured, with nodes in networks automatically establishing and maintaining mesh connectivity among themselves by Akyildiz et al. (2005). WMNs have many advantages over conventional wired networks, such as low installation cost, wide coverage, and robustness, etc. Because of these advantages, WMNs are finding increasing applications including public Internet access, building automation, intelligent transportation system (ITS), metropolitan area networks and public safety.

Routing is one of the most essential design issues of multi-hop wireless networks. The routing traffic in WMNs is to adopt techniques similar to those for wired networks in which the best path for each source–destination pair is selected (according to some metric) and the traffic is sent through that path. Various approaches have been proposed for improving WMN routing, including the utilization of heuristics, a single metric, a composite metric, multiple metrics and multidimensional metrics. Hence efficient routing techniques should be designed for WMN and ensure that the data packets propagate in an optimal manner in terms of several metrics, such as energy consumption, delay, jitter, bandwidth and packet loss ratio. Due to the multiple criteria nature of the most real-world problems, the multi-objective evolutionary algorithms (MOEA) are the best choice because of its population-based approach. Multi-objective optimization problems involve multiple objectives, which should be optimized simultaneously and are often in conflict with each other. In multi-objective optimization, there may not exist a solution that is the best with respect to all objectives; instead, they are equally good solutions and it is called Pareto-optimal solutions.

In this paper, we have proposed an extension of Differential Evolution (DE) for solving multi-objective optimization problems. DE as developed by Storn and Price (1997) is one of the best evolutionary algorithms, and has proven to be a promising candidate to solve real-valued optimization problems. The computational algorithm of DE is very simple and easy to implement, with only a few parameters required to be set by a user. It has been successfully applied in numerous domains of science and engineering like scheduling, routing, data mining and pattern recognition (Gujarathi and Babu 2010; Pan et al. 2009; Rubio-Largo and Vega-Rodrguez 2013; Alatas et al. 2008; Das et al. 2012). The applications of DE on combinatorial optimization problems are still considered limited. Aiming at the discrete problems, novel discrete DE approaches have been proposed in recent literature to solve combinatorial optimization problems (Tasgetiren et al. 2010; Qian et al. 2009). The objective of this paper is to solve the multi-objective routing problem using discrete multi-objective differential evolution (DMODE) algorithm. We consider both packet delivery ratio (PDR) and delay simultaneously to determine the optimal routings for wireless mesh network.

The major contributions of this paper are as follows:

  1. 1.

    We formulate the problem as multi-objective shortest path routing for the maximization of PDR and minimization of delay.

  2. 2.

    We propose a discrete multi-objective differential evolution (DMODE) algorithm to find a Pareto-optimal solution to the problem which improves the PDR and decreases the delay. The redundancy path can be eliminated using weight mapping crossover algorithm and the diversity can be improved using the dynamic crowding distance method. Relative position-based indexing method is used for mutation phase.

  3. 3.

    Finally, we perform extensive evaluation of DMODE under several scenarios. We demonstrate the benefits of the proposed approach using simulation experiments.

The rest of the paper is organized as follows: Sect. 2 describes the related works. The mathematical problem formulation and the objective functions and related constraints are given in Sect. 3. The proposed DMODE for solving the routing problem is discussed in Sect. 4. The simulation result is provided in Sect. 5 and the conclusion in Sect. 6.

2 Related work

2.1 Routing in WMN

A single rate coordinated opportunistic routing protocol (CORP-M) of WMN is proposed by Ajmal et al. (2013). CORP-M divides the whole topology into different regions and each node calculates its own region when forwarding the packet, then processes next forwarder selection by providing the opportunity to relay packets toward the nodes nearer to destination with priority. The simulation result shows that CORP-M reduces duplicate transmissions by 70 % and network collisions by 30 %. A cross-layer multi-radio, multi-channel routing protocol (XCHARM) is proposed by Chowdhury et al. (2013). The selection of the next hop, channel and transmission rate is based on fading and interference. The routes are selected based on the availability of channels that support high data rates. The route maintenance is performed by first identifying and correcting the point of failure, before processing a global recovery action.

Peng et al. (2014) proposes a random linear network coding-based fault-tolerant routing mechanism. This mechanism couples the multi-path routing and random network coding techniques and it does not need to know the topology information of global networks and encoding process of all the nodes. The packet information and encoding vectors are mixed at each coding node according to local coding method. A finite encoding operation is done in each link-disjoint path with piggyback of a coding coefficient, which can greatly reduce the computational complexity. Li et al. (2011) presents an optimized architecture for joint multi-path QoS routing and wireless link scheduling in WMNs. The contention matrix is employed in representing the wireless link interference. The Proximal Optimization Algorithm is used to overcome the non-strict concavity of the primal objective function and then solve the routing and scheduling problem using dual decomposition method.

Alotaibi and Mukherjee (2012) presented the variety of routing algorithm which are specially designed for wireless networks. It is classified into different categories based on the characteristics of wireless networks. The routing algorithm can be selected based on the network characteristics. In addition, this survey is compared, analyzed, and discussed the relationships among the different categories and the several routing issues. An interference aware quality-based routing protocol (IDAR) of WMN is proposed by Pal and Nasipuri (2011). IDAR considers two quality parameters such as maximizing the probability of successful transmission and minimizing the delay. Using the reactive route discovery, it collects the key parameters from the candidate routes and to estimate the probability of success and delay of data packets transmitted over them. The route selection is done by a gateway node that has global activity information about the network. A new load balancing routing metric Neighbourhood Load Routing metric (NLR) is described by Zhao et al. (2011) for handling the real time communication applications. To select a path, NLR considers three aspects which are current IFQ length, neighbourhood interference, and neighbourhood bandwidth. The packets should travel only on the lowest traffic load path instead of the shortest path and the heavy loaded node should not be involved in forwarding packets.

To improve the network performance, a temporal spatial multi-channel assignment and routing scheme was proposed by Jin et al. (2012). This temporal scheme ensures all the nodes that need to directly communicate with the gateway node. In the spatial scheme, the channels are assigned based on their neighbors channel usage and avoid channel interference among nodes. The selection of nodes is done based on the multiple factors to establish optimized routing paths for packet delivery from source nodes to the gateway. These factors include channel usage of nodes neighbour nodes, nodes memory size, nodes hop count, and nodes transmission history. A Modified Destination-Sequenced Distance-Vector routing mechanism (MDSDV) with cross-layer design method is presented by Kai et al. (2011). MDSDV uses the bandwidth and hop count as the routing metric for selecting the appropriate routes. Guo et al. (2011) addressed the On-demand routing protocols by focusing on Dynamic Source Routing (DSR) protocol and Ad hoc On-demand Distance Vector (AODV) routing protocol in WMNs. The simulation result shows that DSR protocol is not suitable for wireless transmission and AODV routing protocol is suitable for wireless transmission with rapid change of network topology. When compared to DSR, AODV has high network overhead since it mainly relies on the flooding routing method.

Borges et al. (2011) proposed the interference aware routing scheme for video streaming. The video quality is evaluated on two perspectives such as the network viewpoint and the user viewpoint. At the network level, video streaming quality is assessed through throughput, delay, jitter and routing overhead measures. At the user level, Quality of Experience metrics are evaluated. The performance of both the network and the user levels is affected by the interference-aware routing metrics. Brunoa and Nurchis (2010) described a detailed survey of the wireless diversity-based routing paradigm such as opportunistic forwarding routing, network coding routing and hybrid routing. Augusto et al. (2011) presented a REUSE algorithm, which combines both routing and link scheduling which take the advantage of spatial reuse and support the simultaneous activation of links. The author presented a reference routing model that searches for the optimal route in terms of a link metric. To provide backhaul access in WMN, Wireless-mesh-network Proactive Routing (WPR) protocol is proposed by Campista et al. (2012). WPR computes routes based on link states and it uses two Algorithms such as controlled flooding and Adapted Multipoint Relay set computation algorithm (AMPR) to improve the overall efficiency of the network. The controlled-flooding algorithm is used to reduce the overhead in WMNs by taking into account the traffic pattern of backhaul access networks. WPR avoids redundant routing messages by selecting a subset of one-hop neighbours using the AMPR set. The function of the AMPR set is similar to the MPR set of OLSR.

Camelo et al. (2011) proposed a new approach for routing problem in WMN using a multi-objective evolutionary algorithm as NSGA-II. The objectives considered are minimization of hop count, delay and energy consumption. In the shortest path routing algorithm, it only takes hop count in the path, but does not consider the conditions on the links included in that path. MOEA allows finding multiple paths which guarantee the QoS requirements established by the multimedia data transmission application. Benyamina et al. (2012) described the WMN planning problem as three multi-objective models using the hybrid combination of multi-objective Particle Swarm Optimization (MOPSO) and Genetic Algorithms (GAs). The two objectives of minimization of deployment cost and maximization of network throughput are optimized simultaneously. The high throughput was achieved in three ways: maximizing the overall flow-capacity ratio, minimizing the network interference and balancing the network links load. Computational results demonstrated that Load-Balanced Model supersedes the Flow-Capacity Model and outperforms the Interference Model.

2.2 Multi-objective differential evolution

MODE algorithm differs mainly on the type of selection mechanism, mutation strategy and diversity maintenance. In the selection mechanism, MODE can be further classified based on Pareto dominance proposed by Abbass (2002) and Pareto ranking concepts by Gujarathi and Babu (2010). In mutation strategy, MODE varies on the type of the criterion to select one of the individuals to be used in the mutation operator (called donor vector), the number of differences computed in the mutation operator and finally in choosing the recombination operator. Several kinds of mutation strategies were utilized in MODE namely DE/current to rand /1/bin, DE/rand/1/bin and DE/best/1/bin. In diversity maintenance, two major approaches were used. One is based on fitness sharing and the other is based on crowding distance.

A complete discussion of the differential evolution algorithm was presented by Das and Suganthan (2011). It provides the comprehensive introduction of the basic steps of DE algorithm and gives the overview of several variants of the conventional DE. An intense review of the modifications of DE for tackling multi-objective, uncertain, constrained and large-scale optimization problems is also given. A brief overview of various most significant engineering applications of DE and a number of future research directions are provided. Zhou et al. (2011) gave a detailed survey of numerous multi objective evolutionary algorithms.

A new way of extending DE for solving multi-objective optimization algorithm is presented by Robic and Filipic (2005). DE is implemented in three variants such as DEMO/parent, DEMO/closest/ dec and DEMO/closest/obj. Compared with other MOEAs in DMODE, the newly created good candidates immediately take part in the creation of the subsequent candidates. This enables fast convergence to the true Pareto front. The new multi-objective differential evolution algorithm was proposed by Ali et al. (2012). The population is initialized using the opposition-based learning method. In the mutation phase, the author used random localization for creation of trial vectors. During the selection, it employs a procedure of immediate replacement of the parent vector with the candidate that dominates it. This helps MODEA to obtain a faster convergence. For truncating the population of 2NP solutions to NP solutions, it uses the non-dominated sorting and crowding distance metric. The performance of the proposed algorithm is investigated on a set of nine bi-objective and five tri-objective benchmark test functions and the results showed the efficiency of the proposed algorithm.

Rubio-Largo et al. (2013) proposed the new multi-objective variant of the standard DE (DEPT) by including the Pareto tournaments and multi-objective fitness concept for the traffic grooming problem in WDM optical mesh networks. Their objective functions are to maximize the throughput of a given optical network, minimize the number of transceivers per node and the average propagation delay. To handle the discrete vector for mutation, the discrete set handling approach is used in the algorithm. This algorithm is compared with other two well known MOEAs such as NSGA-II and SPEA2. It is concluded that the DEPT algorithm surpasses the performance of existing algorithms. Ya et al. (2008) investigated an algorithm, namely Non-dominated Sorting Binary Differential Evolution (NSBDE) for the search of optimal network protection strategies against cascading failures within the complex network systems. This algorithm mainly focuses on the strategy of disconnecting edges to avoid or alleviate component overloads that may arise due to the occurrence of failures in the infrastructure. The problem formulation and the optimization algorithm proposed in this work are effective to obtain the optimal network protection strategy for mitigating the cascading failures at a low cost. Rubio-Largo and Vega-Rodrguez (2013) presented two different MOEAs, the Differential Evolution with Pareto Tournaments (DEPT) and the Multiobjective Variable Neighborhood Search(MO-VNS), for solving the static-Routing and Wavelength Assignment problem in the optical Wavelength Division Multiplexing (WDM) networks. DEPT simultaneously optimizes the number of hops and the number of wavelength conversions. The experimental result showed that DEPT performs better than NSGA-II. The performance of the algorithm is evaluated by the multi-objective indicators, namely hyper volume and coverage relation.

Xue et al. (2006) describes the routing problem in wireless sensor network (WSN) using a DMODE algorithm. Minimizing both energy and latency of the network were the two objectives. The routing update is based on the alternative optimal routes obtained using DMODE, when the nodes are moving from one place to another. The simulation result shows that DMODE identifies a set of Pareto-optimal routings with respect to these multiple objectives for both single and multipath routing problems. Yetgin et al. (2012) proposed the Non-dominated Sorting based Genetic Algorithm-II (NSGA-II) and the Multi-Objective Differential Evolution (MODE) algorithm for finding optimal routes from a given source to destination for the mobile ad-hoc network. The multi-objective function is considered by taking two objectives into account. One objective is to minimize the dissipated energy and the other is to minimize the end-to-end delay. The simulation result demonstrated that MODE algorithm is capable of finding solutions closer to the Pareto front and converges faster than the NSGA-II algorithm.

Routing and Wavelength assignment problem using Differential Evolution with Pareto Tournaments (DEPT) was presented by Rubio-Largo et al. (2010). The objectives are hop count and number of wavelength conversion. The parental selection and replacement strategy can be done using domination concept. Each individual is assigned based on fitness function.The fitness value can be assigned based on the two subsets of population such as Dominates(ind) and Isdominated(ind). DEPT algorithm compared with the other multi-objective approaches like BIANT ,COMP ,MOAQ etc. and concluded that this algorithm performed better than other. Xu et al. (2012) proposed a new semi-supervised learning method as DCPE Co-training. This method does not need the sufficient and redundant views of data set. The diversity of different learning algorithms such as Naive Bayes, neural networks, k-nearest neighbors, and decision tree is used to perform label propagation. The experimental results show that the proposed method can achieve competitive results when it is compared with supervised learning methods and semi-supervised learning methods. Online WMN traffic classification using machine learning algorithm as C4.5 is described by Gu et al. (2011). It is a decision tree-based identification algorithm. Two aspects are considered for improving the accuracy and speed of the machine learning methods of WMN traffic classification. The first aspect as sub-flow selection method solved a critical problem of how to select appropriate sub-flows for achieving traffic classification. The second aspect as to achieve early detection this method allows the classifier to classify traffic flows early in the connection using the first p packets of flow. The effectiveness of proposed method can be evaluated by the experiments on real mesh traffic traces and the results show that this method can classify online WMN traffic with high accuracy. Xu et al. (2013) presented a filter method for unsupervised feature selection. It is based on the geometry properties of L1 graph. This graph established the relations of feature subspaces and the quality of features. Experimental results have demonstrated that the proposed algorithm is better than classic unsupervised feature selection methods (Laplacian score and Pearson correlation) and supervised method (Fisher score) on benchmark data sets.

The existing routing protocols in WMN consider only one objective in selecting the path, but do not consider more than one objective simultaneously for choosing the path. The proposed algorithm aims at preserving its search mechanism for discrete domains during mutation stage.

3 Problem formulation

The routing problem is formulated as a multi-objective mathematical programming problem which attempts to minimize the delay and maximize the PDR, while satisfying the constraints. The topology of a WMN is specified by an undirected graph \(G = (V, E) \) where V represents the set of nodes which consist of both mesh client and mesh routers and E represents wireless connectivity among the nodes. A path from node \(V_{i}\) to \(V_{j}\) is a sequence of nodes and no node appears more than once. The binary decision variable \(X_{ij}\) represents whether a particular link \(( i,j) \in E\) is included in a routing path or not.

3.1 Objective functions and related constraints

3.1.1 Delay

The total delay function is the sum of the delay of links along the path from the source to the destination. Objective function for delay can be expressed as follows:

$$\begin{aligned} f_1=\min \sum \limits _{(i,j)\in E} D_{i,j}X_{i,j} \end{aligned}$$
(1)

\(D_{ij}\) delay between the link (i, j).

3.1.2 Packet delivery ratio (PDR)

The PDR function is the sum of the PDR of links along the path from the source to the sink. It is the number of data packets delivered to the destination divided by the total number of packets generated by the source. The objective function is

$$\begin{aligned} f_2=\max \sum \limits _{(i,j)\in E} P_{i,j}X_{i,j} \end{aligned}$$
(2)

\(P_{ij}\) represents the PDR between the link (i, j).

3.1.3 Flow conservation constraints

To guarantee the uniformity of the model, we have to model the flow conservation constraints at the source, destination and intermediate nodes. S represents the source node and T represents the destination node. The flow conservation equation is represented as:

$$\begin{aligned}&\sum \limits _{(i,j)\in E}X_{ij}=1, \quad i=S\end{aligned}$$
(3)
$$\begin{aligned}&\sum \limits _{(i,j)\in E}X_{ij}=-1, \quad i=T\end{aligned}$$
(4)
$$\begin{aligned}&\sum \limits _{(i,j)\in E} X_{ij}-\sum \limits _{(i,j)\in E}X_{ji}=0, \quad i\ne S, \quad i\ne T. \end{aligned}$$
(5)

All data packets generated by the source node can reach the destination node which is confirmed by the constraints (3)–(5). It is assured that the solutions obtained are valid paths from the source S to the destination T.

4 Proposed algorithm

Multi-objective optimization problem can be solved by DE strategy, the original scheme of DE has to be modified since the solution set of a problem with multiple objectives does not consists of a single solution. There are two issues when designing a MOEA: (1) survivor selection, (2) population diversity. The first one addresses the selection of individuals in the population through non-dominated sorting approach and the second issue is to promote diversity among the individuals in the population which can be achieved by means of dynamic crowding distance measure. The motivation behind developing such algorithm is to provide the user with a set of Pareto-optimal solutions and give the liberty to choose the best solution from the set depending on the specific requirements.

4.1 Population initialization

Encoding is the process of mapping a decision variable into a chromosome. This is one of the most important step towards solving the routing problems using evolutionary algorithms. A chromosome corresponds to the possible solution of the optimization problem. The length of the chromosome is variable and may not be greater than the number of nodes, N. The routing path is encoded by a string of positive integers that represent the IDs of the nodes through which the path passes. The initial population is generated using priority-based encoding developed by Goldberg and Lingle (1985). The node ID is represented by the position of a gene and its value is represented by the priority. A unique path can be set using this encoding. The priority can be assigned to each node with a random mechanism and takes the highest priority for considering a path.

4.2 Mutation

The mutation of DE algorithm is different from other evolutionary algorithms. The variant which is proposed in this paper is denoted as DE/rand/1/WMX where DE refers to the name of the algorithm; the word rand indicates that the donor vector selected to compute the mutation values is chosen at random. The pairs of solutions chosen to calculate the mutation differential are indicated as 1 and finally WMX stands for Weight Mapping Crossover-based recombination. Assume \(X_{r1}\) is the donor solution which can be chosen either at random or it can be the best solution in the population. \(X_{r2}\) and \(X_{r3}\) are the pair of solutions chosen always at random. This difference is scaled with the F parameter. After that, it is added to \(X_{r1}\) to define the location of the mutation vector.

$$\begin{aligned} V_i =X_{r_1} + F (X_{r_2}- X_{r_3}) \end{aligned}$$
(6)

where \(r_{1} \ne r_{2} \ne r_{3}\) are mutually distinct random indices, and F is a differential weight, a scale factor applied to the differential vector. \(i= 1, 2,\) N represents the index of the individual in the population.

The DE algorithm is originally applicable to continuous optimization problems as its search mechanism is based on perturbations built with difference vectors. However, when dealing with combinatorial optimization problems involving permutations of integer vectors, the direct application of the differential mutation mechanism is not valid, since the arithmetic operations on symbolic values would not lead to any meaningful direction in the search space. Additionally, after scaling and adding this result to a third vector, invalid solutions are usually obtained. To compensate this drawback, Relative Position-based Indexing (RPI) is used to convert a continuous position vector for routing. This approach transforms the elements of the integer permutation vector into the floating-point interval [0, 1] and apply the differential mutation as in Eq. (6). The final values are then converted back into the integer domain using relative position indexing.

Three vectors are randomly chosen from the current population. The source and destination nodes are fixed. Let the source node be ‘1’ and the destination node be ‘6’.

$$\begin{aligned} r1= \left[ {\begin{array}{cc} 1 \\ 2 \\ 4 \\ 5 \\ 3 \\ 6 \\ \end{array}}\right] \end{aligned}$$
$$\begin{aligned} r2= \left[ {\begin{array}{cc} 1 \\ 3 \\ 4 \\ 2 \\ 5 \\ 6 \\ \end{array}}\right] \end{aligned}$$
$$\begin{aligned} r3= \left[ {\begin{array}{cc} 1 \\ 4 \\ 2 \\ 3 \\ 5 \\ 6 \\ \end{array}}\right] \end{aligned}$$

The transformation into floating-point values is achieved by dividing each element of the vector by the largest one of them.

$$\begin{aligned} X_{r_1}= \left[ {\begin{array}{cc} 1 \\ 0.4 \\ 0.8 \\ 1 \\ 0.6 \\ 6 \\ \end{array}}\right] \end{aligned}$$
$$\begin{aligned} X_{r_2}= \left[ {\begin{array}{cc} 1 \\ 0.6 \\ 0.8 \\ 0.4 \\ 1 \\ 6 \\ \end{array}}\right] \end{aligned}$$
$$\begin{aligned} X_{r_3}= \left[ {\begin{array}{cc} 1 \\ 0.8 \\ 0.4 \\ 0.6 \\ 1 \\ 6 \\ \end{array}}\right] \end{aligned}$$

Applying in Eq. (6) with \(F = 0.6\), the mutant vector is given by

$$\begin{aligned} V_{i}= \left[ {\begin{array}{cc} 1 \\ 0.28 \\ 1.04 \\ 0.88 \\ 0.6 \\ 6 \\ \end{array}}\right] \end{aligned}$$

To convert the mutant vector back into the integer domain using the RPI, that is to replace the smallest floating-point value by the smallest integer value, and then replace the next smallest floating point value by the next integer value until all the elements have been converted. The final mutant vector is

$$\begin{aligned} V_{i}= \left[ {\begin{array}{cc} 1 \\ 2 \\ 5 \\ 4 \\ 3 \\ 6 \\ \end{array}}\right] \end{aligned}$$

This approach always yields a feasible solution, except when two or more floating-point values are the same.

4.3 Chromosome repair

The conversion occurs between two operational domains, and the number of infeasible solutions created will be significant. There are three unique repairment strategies described by Godfrey and Donald (2009) to repair the replicated values. In this paper, front mutation method can be used. The steps are as follows:

  1. 1.

    Find all repetitive values in the infeasible solution.

  2. 2.

    Based on the replicated position, an array of missing values is generated.

  3. 3.

    An insertion array which indicates the position of the insertion of each value is randomly generated based on the missing values. Finally, the feasible solution can be generated.

4.4 Weight mapping crossover (WMX)

The nature of the priority-based encoding is a kind of permutation representations. This representation will produce illegal offspring by one-cut point crossover or other simple crossover operators. In this paper, we have selected weight mapping crossover (WMX) proposed by Lin and Gen (2007) as crossover operator. It is an extension of one-cut point crossover for permutation representation. At one cut point crossover, two chromosomes would choose a random-cut point and generate the offspring using a segment of its own parent to the left of the cut point, then remap the right segment based on the weight of other parent of right segment. The algorithm of WMX crossover is given below:

  1. 1.

    Random cutpoint of the parents are generated

  2. 2.

    Substring between the parents is exchanged

  3. 3.

    Weight of the right segment is mapped

  4. 4.

    Offsprings with mapping relationship are generated.

Here, the source and the destination nodes are fixed. In WMX crossover, repetition of nodes is avoided by a mapping function, hence no repair function is needed. Therefore, WMX finds many new paths without increasing the computational complexity.

4.5 Dynamic crowding distance (DCD)

The Diversity Maintenance Strategy (DMS) is the process of population maintenance, which uses a truncation operator to wipe off the individuals, when the number of non-dominated solutions exceeds the population size. In this paper, dynamic crowding distance (DCD) presented by Luo et al. (2008) based DMS is used. One individual with lowest DCD value every time is removed and the DCD for the remaining individuals is recalculated. The individual DCD is calculated as follows:

$$\begin{aligned} \text {DCD}=\frac{\text {CD}_i}{\log \left( \frac{1}{V_i}\right) } \end{aligned}$$
(7)

where \(\text {CD}_{i}\) is calculated based on the Eq. (8) and \(V_{i}\) is calculated from the Eq. (9)

$$\begin{aligned} \text {CD}_i=\frac{1}{r}\sum \limits _{k=1}^r \left| f_{i+1}^r-f_{i-1}^r\right| \end{aligned}$$
(8)

where r number of objectives. \(f_{i+1}^{k}\)] kth objective of \((i+1)\)th individual. \(f_{i-1}^{k}\)] kth objective of \((i-1)\)th individual.

$$\begin{aligned} V_i=\frac{1}{r}\sum \limits _{i=1}^r\left( \left| f_{i+1}^k-f_{i-1}^k\right| \text {CD}_i\right) ^2 \end{aligned}$$
(9)

where \(V_{i}\) is the variance of CDs of individuals which are neighbors of the ith individual.

If N is the population size and Q(t) is the non-dominated set at tth generation whose size is M. The DCD algorithm is given below:

  1. 1.

    If \(|Q(t)| \le N\) , goto step 4 else step 2.

  2. 2.

    Calculate individuals DCD in Q(t) based on Eq. (7). Sort the non-dominated set.

  3. 3.

    Remove individual which has the lowest DCD value in Q(t), go to step 2.

  4. 4.

    If \(|Q (t) | \le N\), stop the population maintenance. else go to step 2.

4.6 Discrete multi-objective differential evolution algorithm (DMODE)

The optimization process in DMODE starts with a random population of solutions using priority-based encoding. All the parents in the population P are used for creating the mutated parents of size \(Q_{M}\) using RPI. For all the mutated parents, the offspring is created using WMX crossover. The size of offspring \(Q_{C}\) is also having the same size of P. Now both the original parent and the offspring generated from recombination operator are combined together to form \(2*P\) set of individuals. After a generation, the combined parent and offspring population is then reduced back to original population size using non-dominated sorting and dynamic crowding distance. In the non-dominated sorting method, the new population is packed with solutions of different non-dominated fronts. The best non-dominated front is considered first,then continued by the second non-dominated front which is followed by the third and so on. When the total non-dominated solutions exceed the population size Z, reject some of the lower ranked non-dominated solutions. This is achieved through a sorting procedure which is done according to the dynamic crowding distance. Finally, the population of parents is generated using the binary tournament selection to the current population. It randomly selects the two solutions from the current population and chooses the best one. The algorithm is terminated when the maximum number of generations is reached.

The following steps are adopted for the implementation of the proposed DMODE algorithm.

Algorithm 1: Discrete multi-objective differential evolution algorithm.

1.

Set \(t = 0\), \(N = Population\_Size\).

2.

Compute Initial population Routes using priority-based encoding.

3.

\(P_{t}\) =calculate the objective functions for the initial population.

4.

Repeat

5.

Perform mutation operation using RPI approach.

6.

Apply WMX crossover for the entire mutated parents to generate the offspring \(Q_{t}\).

7.

\(R_{t} = Q_{t} \cup P_t\).

8.

Perform non-dominated sorting for the combined parent and offspring population \((R_{t})\).

9.

Calculate DCD for the combined population based on the algorithm discussed in Section 4.5.

10.

Apply the selection of routes based on the binary tournament selection.

11.

\(i=i+1\).

12.

until \(t<Max\_Generation\).

5 Experimental setup

To analyze the performance of DMODE algorithm, we consider the Adhoc On demand Distance Vector routing protocol (AODV). We have selected NS-2.34 for the simulation study. The performance metrics considered in this algorithm are the PDR and average delay. The performance metrics are obtained by calculating the average result of 20 test runs. The average value with standard deviation is plotted as error graphs with 95 % confidence interval. A total of four simulation scenarios are carried out. The simulation parameters are shown in Table 1.

Table 1 Simulation parameters
Full size table

5.1 Parameter selection

The various methods of optimal parameter combinations are experimentally determined with different parameter settings by conducting a series of experiments before performing actual runs to collect the results. The crossover probability \((P_\mathrm{c})\) is selected between 0.5 and 0.95 in steps of 0.01 and for each \(P_\mathrm{c}\) performance is analyzed. It is found that \(P_\mathrm{c}\) = 0.85 produces the best results. The scaling factor F is varied in the range 0.1–1 in steps of 0.1 and it was found that \(F= 0.6\) produces the best result. Table 2 shows the set of control parameters selected after conducting the experiments.

Table 2 Control parameters selected for DMODE algorithm
Full size table

5.2 Performance analysis

In this section, we have presented the simulation results as the performance evaluation of our algorithm. The performance of proposed algorithm is compared with NSGA-II and DEPT in WMN in terms of the PDR and delay. Figure 1 shows the average delay for the 20 node network with 14 mesh clients and 6 mesh routers by varying the node mobility. DMODE performs well compared to NSGA-II and DEPT in case of low node mobility as well as the high node mobility. The paths between communication end points will break frequently, when we increase the mobility of the nodes. In DMODE algorithm, the redundancy of nodes in the path can be avoided using the mapping function of WMX crossover and hence there is no repair function needed for selecting the path in the crossover. It is clear that DMODE has lesser delay than NSGA-II and DEPT.

Fig. 1
figure 1

Average delay under increasing node mobility

Full size image

Figure 2 indicates the PDR (%) for 20 nodes with varying node mobility. The results indicate that mesh client speed of 5m/s. NSGA-II achieves 52 % PDR. DEPT achieves 59 % PDR while DMODE achieves 65 %. However, the PDR starts to decline rapidly as soon as the mesh client speed is increased. The PDR of NSGA-II and DEPT drops to almost 10 and 20 % when the maximum speed is increased to 25 m/s, DMODE drops to 27 % for the same increase in mesh client speeds. During the mutation phase, the infeasible solution can be eliminated using front mutation, so that the chance is more to retain the feasible solution. Therefore, the PDR of DMODE is higher than the NSGA-II.

Fig. 2
figure 2

Packet delivery ratio (%) under increasing node mobility

Full size image

Figure 3 plots the PDR comparison of DMODE, DEPT and NSGA-II algorithm with increasing simulation time and the maximum speed of mesh clients is 5 m/s. The PDR value of DMODE is higher than NSGA-II and DEPT with increasing simulation time. When the initial population is encoded at random, the chance of a feasible chromosome is less. Using priority-based encoding, the number of feasible solution is increased. Hence the packet delivery ratio of DMODE is higher than NSGA-II and DEPT.

Fig. 3
figure 3

Packet delivery ratio (%) under simulation time

Full size image

Figure 4 compares the average delay of the algorithms with increasing simulation time. The delay is increased with the increase in simulation time. During the initial stage itself, the infeasible solution is eliminated with priority-based encoding and front mutation and hence the delay is lesser than NSGA-II and DEPT. Thereby, it is clear that DMODE performs better than NSGA-II and DEPT. The simulation results of the PDR (%) to increase the number of nodes when the maximum speed of mesh client is 5 m/s are represented in Fig. 5. In DMODE algorithm, dynamic crowding distance method removes only one individual at a time and recalculate the individuals distance, so it provides more possibility to retain the individual in the non-dominated set. DMODE performs well for all the topologies and has the highest PDR.

Fig. 4
figure 4

Average delay under simulation time

Full size image
Fig. 5
figure 5

PDR (%) under increasing node size

Full size image

Figure 6 shows the simulation results for the average end-to-end delay for increasing the number of nodes when the mesh client speed is 5 m/s. In DMODE, both front mutation and mapping function of WMX crossover eliminate the redundancy of the path and hence DMODE provides lower delay than NSGA-II and DEPT.

Fig. 6
figure 6

Average delay under increasing node size

Full size image

From Fig. 7, we observe that average delay in DEPT, NSGA-II and DMODE continuously increases with the increasing packet transmission rate. When the packet transmission rate continues to increase, the average delay of DMODE is shorter than NSGA-II and DEPT because DMODE considers both the PDR and delay to select the appropriate path for packet transmission.

Fig. 7
figure 7

Average delay under increasing packet transmission rate

Full size image

5.2.1 Optimal Pareto front

The best Pareto front is obtained among 20 simulation runs using DMODE, which is portrayed in Fig. 8. For a good MOEA, a user is expected to find solutions close to the true Pareto-optimal front as well as solutions that span the entire Pareto-optimal region uniformly. It is obvious from Fig. 8 that there is a gap between the NSGA-II, DEPT and the best Pareto front obtained from DMODE. This is due to the premature convergence of NSGA-II. In NSGA-II, the crowding distance operator will ensure diversity along the non-dominated front but lateral diversity is lost. Due to the lack of diversity in the particular decision variables, the search slows down and drives the search towards better regions of optimality. For better convergence, a search algorithm may need diversity in both aspects along the Pareto-optimal front and lateral to the Pareto-optimal front. Hence, WMX and DCD operators are used to perform modification in both recombination and selection strategies to improve the lateral diversity in NSGA-II. It is clear that all the obtained non-dominant solutions lie on the Pareto-optimal front and they also maintain a uniform distribution over the entire Pareto-optimal region.

Fig. 8
figure 8

Pareto-optimal solution of DMODE, DEPT and NSGA-II

Full size image

5.2.2 Validation of performance metric

To validate the performance of the proposed DMODE algorithm, spread metric \((\Delta )\) by Deb (2001) is used. An algorithm finding a smaller \((\Delta )\) value is able to find a better diverse set of non-dominated solutions.

$$\begin{aligned} \Delta =\frac{\sum \nolimits _{m=1}^M d_m^e+\sum \nolimits _{i=1}^{|Q|}\left| d_i-\overline{d}\right| }{\sum \nolimits _{m=1}^M d_m^e+|Q|\overline{d}} \end{aligned}$$

where \(d_{i}\) distance measure between neighboring solutions. \(\overline{d}\) mean value of the distance measures. \(d_m^e\) distance between the extreme solutions.

From Fig. 9, all the scenarios DMODE have less spread value than NSGA-II and DEPT, which indicate that dynamic crowding distance improves convergence and simultaneously improves the diversity of the non-dominated solutions.

Fig. 9
figure 9

Comparison of DMODE against NSGA-II,DEPT using spread metric

Full size image

The comparison of performance metrics with its best, mean, worst and standard deviation values is represented in Table 3. From Table 3, it is clear that Spread statistical performance measures have minimum mean values in DMODE as compared to NSGA-II and DEPT. Hence, it is obvious that DMODE performs much better than NSGA-II and DEPT in this contingency condition.

Table 3 Statistical comparison of performance metric
Full size table

6 Conclusion

In this paper, the routing problem in WMN is taken into consideration for the multi-objective optimization contexts, where PDR and delay are optimized simultaneously. To represent the initial solution, the priority-based encoding was used and penalty function was designed to eliminate replicated solutions during the mutation process. The simulation results have shown that our proposed algorithm DMODE performs better than NSGA-II,DEPT and it has improved the PDR and minimized the delay. The concept of WMX crossover and DCD is successfully employed in DMODE algorithm to improve convergence and to maintain diversity among the set of solutions in the Pareto front. The results show that DMODE is efficient for solving multi-objective routing problem where multiple Pareto-optimal solutions can be found in one simulation run. The diversity performance of DMODE algorithm is validated using the performance measure spread. The approach is quite flexible so that other formulations using different objectives and/or a larger number of objectives are possible. Our future work includes the extension of DMODE-based routing approach to incorporate multiple channels with multiple radios.