International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Menu

ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Real Time Routing Algorithm Based On NSGA-II in Wireless Mesh Networks

Seidfarbod Seidali Routeh
Bachelor Student, Iran University of Science and Technology, IRAN
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Abstract

With the growing demand for real time services in Wireless Networks, quality of service (QoS) based routing has emerged as an interesting research topic. But offering some QoS guarantee in wireless networks raises significant challenges. This paper presents a real time routing algorithm based on NSGA-II. This algorithm has been widely used in optimization problems. NSGA-II is a non-dominated sorting genetic algorithm which consists of multi objective functions. NSGA-II algorithm starts with a random population. Each individual in population is considered as a chromosome. Two objective functions were considered in this paper: (i) End to end delay, (ii) path reliability. Final solutions were sorted by Pareto front method. The wireless mesh network was modeled as an undirected graph, in which the sets of nodes N and links L represent computer sites and communication cables. Experimental results proved that the proposed NSGA-II routing algorithm can achieve better performance in compare of other well-known methods like Ad Hoc on Demand Distance Vector (AODV).

Keywords
NSGA-II algorithm, routing algorithm, mesh network, objective function

INTRODUCTION
As the development of networking technologies and the increasing popularization of network based applications, computer networks are now being widely used in scientific researches, business, education, national defense and other domains [1, 2]. It also used as an important technology in the field of industrial process management [3, 4, 5, 6, 7, 8, 9, 10]. Several industrial organizations such as ISA [11], HART [12] and ZigBee [13] have been actively pushing the application of wireless technologies in industrial automation Routing is a general network design problem, in which an optimal assignment of network link capacity and the best selection of routes are to be determined in a reasonable amount of time.
Nowadays, real-time systems are found in many diverse application areas including; automotive electronics, avionics, computer network, telecommunications, space systems, medical imaging, and consumer electronics. In all of these areas, there is rapid technological progress. A real-time system controls an environment by receiving data, processing them, and returning the results sufficiently quickly to affect the environment at that time. A system is said to be realtime if the total correctness of an operation depends not only upon its logical correctness, but also upon the time in which it is performed. Real-time systems, as well as their deadlines, are classified by the consequence of missing a deadline:
• Hard: missing a deadline is a total system failure.
• Firm: infrequent deadline misses are tolerable, but may degrade the system's quality of service. The usefulness of a result is zero after its deadline.
• Soft: the usefulness of a result degrades after its deadline, thereby degrading the system's quality of service.
Thus, the goal of a hard real-time system is to ensure that all deadlines are met, but for soft real-time systems the goal becomes meeting a certain subset of deadlines in order to optimize some application-specific criteria. The particular criteria optimized depend on the application, but some typical examples include maximizing the number of deadlines met, minimizing the lateness of tasks and maximizing the number of high priority tasks meeting their deadlines.

RELATED WORK
Real time applications are used in wireless networks as well. [14] presented a real time full duplex radio design using signal inversion and adaptive cancellation. Tian He et al[15] proposed a real time communication protocol, which is called SPEED. SPEED is a highly efficient and scalable protocol for the sensor networks. Shen et al. [16] applied a Tabu search algorithm for the routing and capacity assignment problem in computer networks.
Evolutionary algorithms have been widely used in many fields like clustering, image processing and also routing problem as well. Genetic algorithm is an evolutionary algorithm which is inspired from natural process of selection and genetic. Ga has gained considerable attention in recent years for solving various optimization problems. Lin et al. [17] applied a genetic algorithm (GA) based approach to route selection and capacity flow assignment. A number of papers have demonstrated the usefulness of a GA based approach in sensor networks [18, 19, 20, 21]. The work of [20] focused on deriving an energy efficient scheme that satisfy the required detection probability [21] using a distributed GA. The work of [20] focused on finding an optimal traffic distribution to improve the lifetime of multi-sensor networks. A GA based approach for routing in two-tiered sensor networks is proposed in [22] that only used energy optimization to maximize life time of network. QuESt [23] is a routing protocol that uses Multi Objective GA to find paths in a flat (non-clustered) wireless sensor network.
Topology is one of the most important parameter which effects throughput and efficiency of a network. Mesh is one of common topologies which is widely used in computer networks. In a Mesh topology, each of the network nodes (computer and other devices) is interconnected with one another. Every node not only sends its own signals but also relays data from other nodes. In fact a true mesh topology is the one where every node is connected to every other node in the network.Fig.1 shows how nodes are connected through Mesh topology. Advantages of mesh topology can be listed as:
• In compare of topologies like Bus if one client fails to proceed, the others can continue their jobs.
• Data can be transmitted from different devices simultaneously. This topology can withstand high traffic.
• Expansion and modification in topology can be done without disrupting other nodes
In this paper, we presented a new real time routing algorithm based on NSGA-II in wireless Mesh networks. The Nondominated Sorting Genetic (NSGA) Algorithm is a Multiple Objective Evolutionary algorithm which is an extension of the Genetic Algorithm for multiple objective function optimizations.

NSGA-II ALGORITHM
The objective of the NSGA-II [24] algorithm is to improve the adaptive fit of a population of candidate solutions to a Pareto front constrained by a set of objective functions. The NSGA-II is an improvement of a previous algorithm developed by the same authors called NSGA. NSGA algorithm has features like:
• These algorithms do not consider the use of elitism strategies, which prevent the loss of good solutions, and can hence be a key factor in speeding up the search.
• Additional parameters must be set for ensuring diversity, mostly with the help of a sharing parameter
• NSGA is suitable for continuous optimization problems
Fig.2 shows flowchart of NSGA-II process for finding optimized solutions. NSGA-II algorithm starts with random population. Each individual in population is considered as a chromosome. Each Chromosome contains solution which we are seeking to find it. Chromosomes will be evaluated by objective functions till expected answer is reported or max iteration reaches. For making diversity between solution, crossover and mutation is included in process of algorithm. NSGA-II sorts solutions with Pareto front method. In this method, Population would be sorted based on nondomination into each front. The first front is being completely non-dominant set in the current population and the second front is being dominated by the individuals in the first front. To each individual in each front a rank (fitness) would be assigned. Also another value is given to each chromosome based on which front they belong to. Individuals in first front are given a fitness value of 1 and individuals in second are assigned fitness value as 2.

PROPOSED ALGORITHM
Routing problem is considered as a complex nonlinear programming which has many restrained conditions and it is known to be NP-completeness [25, 26]. The objective of routing problem is finding set of links to deliver packages from sender node to receiver. The routing algorithm is that part of the network layer software responsible for deciding a route of each packet from its source node to its destination based on the network topology. The motivation here is to provide a set of Pareto optimal solutions by the NSGA-II algorithm and give it the flexibility to choose the best possible solution from this set. The design objectives in our routing algorithm are:
1. Keep the average delay per packet or message below a given level
2. Keep desirable reliability in whole network
A computer network can be modelled as an undirected graph G = (N, L), in which the sets of nodes N and links L represent computer sites and communication cables. Following figure shows an example of graph model of a network.
A sample chromosome of above network in our proposed algorithm is depicted in figure 4. A path (route) is encoded by listing nodes from its source to its destination based on the topology of the network.
For reliability metric, we used ETX [27] for calculating the path reliability. ETX is defined as the expected number of transmissions (including retransmission) for a successful end-to-end data forwarding and hop-by-hop acknowledgment. The following expression shows how to compute the ETX metric for a path:
image
• fdv : The forward delivery ratio is the measured probability that a data packet successfully arrives at the recipient
• rdv : the reverse delivery ratio is the probability that the ACK packet is successfully received End to end delay is measured by following equation:
image
In our method, for the cause of real timing, if Delay time exceeds the maximum time then solution would be considered as failed.
To determine the ability of a chromosome to survive and produce offspring, Eq. (1) and Eq. (2) are used as objective functions. When we apply GAs to a n -objective optimization problem, we have to evaluate the values of n objective functions for each solution. A weighted-sum objective is used to evaluate the chromosome. The way to transform the values of objective functions to the fitness value of each string x in the generation is to combine the 2 objective functions as follows:
image
• Fi is fitness value of chromosome with number (i)
• The value of W1 and W2 is between zero and one (0<W1,W2<1)

SIMULATION RESULTS
The proposed routing algorithm is based on NSGA-II algorithm and its application is optimizing real time routing through mesh networks. The processing of the proposed approach is explained in the above sections, now, in this section, we present the experimental results of the proposed algorithm which has been implemented in MATLAB. MATLAB is a high-level language and interactive environment for numerical computation, visualization, and programming. Fig.5 shows main classes which were developed for implementing proposed method. Classes are described as below:
• Topology class is developed for making a Mesh wireless network.
• Run class is used for controlling real timing systems
• Action class is responsible controlling routing algorithm, state of clients like sending and receiving
Table 1 shows result of comparison between NSGA-II algorithm and Ad Hoc On Demand Distance Vector (AODV). The proposed algorithm was evaluated under different scenarios and nodes. Experimental results proved that NSGA-II can proceed in less amount of time in compare to AODV.
Following figure shows average delay time through iteration. A comparison was made between AODV and NSGA-II algorithm. Average delay time of proposed NSGA-II routing algorithm is less than AODV. This factor demonstrates the fact that packet lost and packet re-sending is decreased in NSGA-II real time routing algorithm.
Value of NSGA-II parameters were assigned as:
• Number of generation = 10
• Crossover method = single point
• Mutation method = Bit string flip
• Population = 100

CONCLUSION AND FUTURE WORK
In this paper, we study the real time routing problem in wireless mesh networks. Our goal was optimizing reliability and end to end delay. Proposed method is based on NSGA-II algorithm which is a Multiple Objective evolutionary algorithm and the objective of this algorithm is to improve the adaptive fit of a population of candidate solutions to a Pareto front constrained by a set of objective functions. The algorithm uses an evolutionary process with surrogates for evolutionary operators including selection, genetic crossover, and genetic mutation. We implemented proposed algorithm in MATLAB. A comparison was made between NSGA-II real time routing algorithm and Ad Hoc On Demand Distance Vector (AODV). Following results were observed within experimental analysis:
• Execution time for finding desirable path in proposed algorithm was less that AODV
• Decreasing Delay time for sending packets
• In compare to AODV, less number of lost and dropt packets was observed
 

Tables at a glance
Table icon
Table 1
 

Figures at a glance
Figure 1 Figure 2 Figure 3
Figure 1 Figure 2 Figure 3
Figure 4 Figure 5 Figure 6
Figure 4 Figure 5 Figure 6
 

References