A multi-objective evolutionary algorithm based QoS routing in wireless mesh networks
Graphical abstract
Introduction
Wireless mesh networks (WMN) have received due recognition because of their extended coverage, robustness, self healing, self configuring, easy maintenance and low cost broadband network services. WMN offers an attractive platform to a large variety of applications such as broadband home networking, building automation, public safety and emergency response communications, community networks and transportation systems. WMNs [1] are composed of static mesh routers and mobile mesh clients. Mesh routers provide connectivity between mesh clients which form the backbone infrastructure of WMN. The gateway functionality in mesh network enable the integration of WMN with other existing networks.
Multi-constrained QoS routing in WMN identifies feasible route in the network satisfying the multiple constraints. The constraints are usually imposed by quality of service (QoS) requirements such as minimum guaranteed bandwidth, a bounded end-to-end delay, packet loss and a limited interference among the wireless links. Many applications, such as audio, video conferencing and collaborative environments have multiple QoS requirements such as bandwidth, delay, packet loss, hop count, reliability, energy, etc. Multi-constrained routing problem cannot be solved in polynomial time because it is an NP-complete problem.
This work presents a multiobjective evolutionary algorithm approach for determining QoS routing in WMN. Multiobjective optimization problems having conflicting objective functions gives rise to a set of optimal solutions, instead of one optimal solution. No solution can be considered to be better than any other with respect to all objectives. These optimal solutions are known as Pareto-optimal solutions. The curve or surface describes the optimal trade-off solutions between objectives is known as the Pareto front. One of the major goals in multiobjective optimization is to find a set of well distributed optimal solutions along the Pareto front. Maintaining the diversity of the population not only requires a certain space distance between individuals, but also needs good uniformity for the non-dominated sets. There are several contemporary multiobjective evolutionary algorithms [2], [3], [4], [5], [6] which are aimed to find the Pareto-optimal front while achieving diversity in the obtained Pareto-optimal front. The major advantage of these multiobjective evolutionary algorithms (MOEAs) is that they produce a set of Pareto-optimal solutions in a single run. From this, the final solution is found by applying decision analysis technique. Analytic hierarchy process (AHP) is used for finding the best optimal solution from the set of Pareto-optimal solution. This paper focuses on the minimization of expected transmission count and transmission delay simultaneously by using MNSGA-II and AHP.
The remainder of the paper is organized as follows. Section 2 discusses the related work about the single objective and multiobjective evolutionary algorithms used in WMN and other networks. The mathematical problem formulation in multiobjective context is presented in Section 3. A meta-heuristic algorithm based on MNSGA-II to solve the multiobjective routing problem is proposed in Section 4. Section 5 present the simulation results to validate our algorithm. Finally, in Section 6 we summarize the conclusion of this article and discuss the possible lines of future work.
Section snippets
Single objective optimization in WMN
Several routing protocols are used in WMN but most of the protocols consider only one objective either throughput or delay or hop count or packet loss or energy. Sun et al. [10] proposed on demand code aware routing scheme (OCAR) for WMN. This scheme detects a route with more network coding opportunities along the entire route rather than the two-hop regions. By using Coding Aware and Interference avoid routing metric (RCAIA), OCAR handle both intra and inter flow interferences. RCAIA of link l
Problem formulation
Wireless mesh network can be represented as an undirected graph G = (V, E) where V is the set of nodes consisting of both mesh client and mesh routers and E is the set of edges representing wireless links between the nodes. A path from node Vi to node Vj is the sequence of nodes from V in which no node appears more than once. The routing problem is to determine a path between the source and destination nodes with minimum transmission delay and minimum expected transmission count.
Multiobjective evolutionary algorithm for routing problem
Multiobjective optimization can be solved by several methods, we have chosen MOEA because it has the ability to find multiple optimal solutions in one single simulation run [4]. NSGA-II is one of the most efficient and popular multiobjective evolutionary algorithm. In this paper, we propose MNSGA-II, an improved version of NSGA-II for solving the multiobjective routing problem. MNSGA-II algorithm uses non-dominated sorting for fitness assignments and dynamic crowding distance for improving the
Performance evaluation
To analyze the performance of MNSGA-II algorithm we consider the Optimized link state routing protocol (OLSR). In OLSR, the Multi-Point Relays (MPR) play a very crucial role in forwarding the packets. The node which chooses its MPR will forward the packets and reduce the redundant transmissions. The Fedora OS is used to run the simulation software NS2 (Network Simulator 2) version 2.34 for the evaluation. The patch for NS-2.34 to simulate the OLSR is given by Ross [35]. Simulation and
Conclusion
In this paper, Modified Non-dominated Sorting Genetic Algorithm-II (MNSGA-II) is proposed for routing in wireless mesh network. While considering the presence of links or connectivity between nodes, network-related status of links like transmission delay and expected transmission count in links are collected and measured. These measures offer an indication of how much a link is appropriate while deciding about paths for providing QoS routing. By using this algorithm, we are able to obtain
References (35)
- et al.
The development of a sub-population genetic algorithm II (SPGA II) for multi-objective combinatorial problems
Appl. Soft Comput.
(2009) - et al.
Developing scalable protocols for three-metric QoS routing in computer networks
Int. J. Comput. Telecommun. Netw.
(2002) - et al.
Prioritised best effort routing with four quality of service metrics applying the concept of the analytic hierarchy process
J. Comput. Oper. Res.
(2006) - et al.
Interference-aware routing for multi-hop wireless mesh networks
Comput. Commun.
(2010) - et al.
Multiobjective evolutionary algorithms: a survey of the state of the art
Swarm Evol. Comput.
(2011) - et al.
An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows
Comput. Oper. Res.
(2011) - et al.
Multi-objective optimization for coverage control in wireless sensor network with adjustable sensing radius
Comput. Math. Appl.
(2009) - et al.
Energy efficient coverage control in wireless sensor networks based on multi-objective genetic algorithm
Comput. Math. Appl.
(2009) - et al.
A simulated annealing algorithm for router nodes placement problem in wireless mesh network
Simul. Modell. Pract. Theory
(2011) Dynamic router node placement in wireless mesh networks: a PSO approach with constriction coefficient and its convergence analysis
Inf. Sci.
(2013)
A hybrid nature-inspired optimizer for wireless mesh networks design
Comput. Commun.
A survey on wireless mesh networks
IEEE Trans. Commun. Mag.
A fast and elitist multiobjective genetic algorithm: NSGA-II
IEEE Trans. Evol. Comput.
Multi-objective evolutionary algorithms: a comparative case study and the strength Pareto approach
IEEE Trans. Evol. Comput.
Multi-Objective Optimization Using Evolutionary Algorithms, Wiley-Interscience Series in Systems and Optimization
RM-MEDA: a regularity model based multi-objective estimation of distribution algorithm
IEEE Trans. Evol. Comput.
Mesh wlan networks: concept and system design
IEEE Trans. Wirel. Commun.
Cited by (39)
A velocity-based butterfly optimization algorithm for high-dimensional optimization and feature selection
2022, Expert Systems with ApplicationsCitation Excerpt :High-dimensional optimization problems are widely existed in science research and real-world applications such as fault detection (Long et al., 2021a), spacecraft design optimization (Trisolini, et al., 2018), machine learning (Zarshenas & Suzuki, 2016), mesh network Qos routing problems (Murugeswari, et al., 2016), engineering design problems (Kar, et al., 2020), and so on.
A multi-objective Dyna-Q based routing in wireless mesh network
2021, Applied Soft ComputingCitation Excerpt :The algorithm in [31] sets delay and energy consumption as the objectives, and compares the performance of NSGA-II and Multi-Objective Differential Evolution (MODE) [32]. Algorithms proposed by Murugeswari [10,33,34] solves problems by discrete PSO, NSGA-II and discrete MODE. Delay, ETX and packet delivery ratio are considered.
Determining the trade-offs between data delivery and energy consumption in large-scale WSNs by multi-objective evolutionary optimization
2020, Computer NetworksCitation Excerpt :The studies in [39–41] introduce linear programming models to formulate the routing problem. Both [40] and [39] consider flow conservation constraints to ensure that all data packets reach the destination and one of the objective functions is the minimization of transmission delay. On the one hand, the second objective function in [40] is the minimization of ETX.
Computational intelligence techniques for energy efficient routing protocols in wireless sensor networks: A critique
2024, Transactions on Emerging Telecommunications TechnologiesNDRA: An Efficient Multi-Objective Optimal Routing Algorithm Using Pareto Domination
2023, ACM MobiCom 2023 - Proceedings of the 18th Workshop on Mobility in the Evolving, Internet Architecture, MobiArch 2023