The problem of routing in ad hoc networks is the most difficult challenge to achieve, because it must find an optimal multihop route between any two nodes of the network, since mobile ad hoc networks (MANET) have no central bridge. So, each node must join its neighbors using its radio interface if it needs to contact any other nodes that dont exist in its zone area.
For the most existing modified AODV routing protocol1 the researchers focused on a single performance, but an ideal routing algorithm must satisfy all quality services.
Before we start giving details about our work and its implementation, we present an overview of the last works in this field. Many routing protocols have been presented to optimize quality of service across MAC layer and network layer.
The load balancing approach on-demand protocols select a route at any time based on the minimum energy availability of the routes and the energy consumption per packet of the route at that time. The transmission power will be controlled on a link by link basis to reduce the power consumption per node2.
Yin and Lin3 proposed a multipath minimum energy routing mechanism to minimize the overall energy consumption of the network. They model an ad hoc network by a set of nodes and links. Each link is associated with an energy cost function which is a function of the total traffic flowing over this link. They focus on the problem of how to split traffic among multiple paths to minimize the sum of the links energy cost.
An adaptive TTL-based protocol (AODV-TTL) modified ad hoc on-demand distance vector (AODV) routing protocol to route packets. The TTL value will be deducted dynamically according to the node speed and reaches zero quickly when the packet pass through some faster nodes. By this way, not only the broadcast range is restrained to a smaller range, the overall routing required number of broadcast packets can also be reduced. Consequently, the routing overheads will cut down and find a stable path because some faster speed nodes have been excluded automatically4.
Yadav et al.5 proposed a method for signal strength based link availability prediction to be used in AODV routing. The nodes estimate the link breakage time and further warns the other nodes about the link breaks in the route. Based on this information, either local route repair or new route discovery is initiated much earlier than the route breakage. This reduces the data packet losses as well as end-to-end delay.
In Qi et al.6 proposed a multi-path routing protocol (EM-AODV) that based on nodes energy. The EM-AODV designs methods of obtaining nodes energy by upgrading the route discovery and route maintenance process of AODV, calculates the path of comprehensive energy derived path priority by routes total hops and nodes energy to format the multi-path routing mechanism.
An optimized N-AODV protocol has been used. In N-AODV the reverse request NRREQ replaces the RREP used in AODV, which ultimately reduces the time for route finding. The route table and control message contains the information of two hops also reduces the time for route finding and improves the rate of route repair7.
Manickam and Manimegalai8 suggested a new protocol AODV energy based routing (AODV-EBR) protocol for energy constrained mobile ad hoc Networks. This protocol optimizes ad hoc on demand distance vector routing protocol (AODV) by creating a new route for routing the data packets in the active communication of the network. The proposed protocol efficiently manages the energy weakness node and delivers the packets to destination with minimum number of packets dropped. This protocol has two phases such as route discovery and route maintenance. The operation of AODV-EBR is similar to AODV considering the energy of a node during the establishment of route.
El Fergougui et al.9 implemented a new approach AODV Reduction Overhead and Energy (AODV-ROE), whose routing metric is based on the consumption of energy to reduce the number of control messages needed to discover and maintain a route. This new protocol has the main objective to ensure that network connectivity is maintained as long as possible and that the energy level of the entire network is similar. They have grouped these two goals in the deployment of several scenarios ad hoc. So, their goal is to reduce as possible the energy problem and minimizing the overload in the network.
Kyasanur and Vaidya10,11 used a hybrid channel assignment strategy with varying channel assignment. Their approach is designed for the scenario where the number of interfaces is smaller than the number of channels. For example, their results show that even with two interfaces, a five channel network can offer more than five-fold improvement over a single channel network.
Wu et al.12 propose a new multi-channel MAC protocol which can be applied to both FDMA and CDMA technology. The protocol requires two simplex transceivers per mobile host, one interface is assigned for control purposes and the second interface is switched between the remaining channels and used for data exchange.
Bouras et al.13 used the model of Calvo and Campo14 and design a cross-layer mechanism for an effective channel assignment and routing based on specific metrics used in Cognitive Radio Networks (CRN)15 for the purpose of improving the spectrum utilization. The proposed mechanism is based on tracking real time metrics (Sound to Noise Ratio (SNR) and channel collision) during data packets transmission.
Ma et al.16 studied Concurrent Transmission Capacity (CTC) using the physical interference model and also explores the impact on CTC of different physical parameters. Moreover, the relations between throughput and delay are achieved using two queuing systems in MCMI random networks, respectively. The deterministic results obtained with a group of real network configuration parameters demonstrate that the proposed tradeoff model could be applied to the real network scenarios.
Kim and Chung17 proposed IA-AODV which is based on multitarget path request, consists of the PREQ prediction scheme, the PREQ loss recovery scheme and the PREQ sender assignment scheme. A detailed operation according to various network conditions and services is introduced and the routing efficiency and network reliability of a network using IA-AODV are analyzed over the presented system model. When the proposed routing protocol is compared with the existing AODV routing protocol, it performs the path update using only 14.33% of the management frames, completely removes the routing malfunction and reduces the UDP packet loss ratio by 0.0012%.
Omkumar and Rajalakshmi18 modified the standard routing protocol for ad hoc network ad hoc on demand distance vector (AODV) by including Signal to Noise Ratio (SNR) and Trust Value (TV) as the routing parameter to increase the performance of the network. In this study, QoS, routing and the security parameters are mainly considered to increase the performance of ad hoc network. In route discovery phase, in addition to the bandwidth, delay and distance the node with highest SNR and the max TV is selected as the next relay node. So, the system provide high throughput while avoiding the malicious node presence in the route.
Viradia19 proposed a new protocol enhanced AODV (E-AODV) which is a modified version of AODV with enhanced packet delivery ratio and minimized end to end delay when frequent link failure in network due to mobility of the nodes in the network.
Sanabani et al.20 developed a new routing protocol called a Reverse AODV (RAODV). The RAODV tries multiple route replies which reduces the path fail correction packets and obtains better performance than other protocols. But RAODV has the most control packet overhead. Therefore, in their study, they propose an enhanced (EN-RAODV) that is improving the RAODV. Simulation results show that the proposed EN-RAODV improves the performance of network comparing with RAODV and AODV in most selected performance metrics such as packet delivery ratio, end to end delay, throughput, routing packet sent and routing overhead.
MATERIALS AND METHODS
MAC model: Ad hoc networks using single-channel single-interface environment suffer from end to end throughput decrease because of intra-flow interference and inter-flow interference. Therefore, we used multi-channel multi-interface environment to overcome this problem, but we need a channel assignment algorithm which provides schedules assignment and coordinates between the nodes because in general the number of available channels are greater than the number of interfaces due to power consumption and size constraints.
Channel assignment algorithm: The main objective of channel assignment in multi-channel multi-interface environment is to maximize channel utility without damaging network connectivity. There exist many approaches to solve the channel assignment problem. These approaches can be divided into three main categories: Static assignment, dynamic assignment and hybrid channel assignment.
In this study, we focus on hybrid channel assignment to obtain the advantages of two other mechanisms: Static and dynamic assignment.
For any two nodes N1, N2∈N such that there exists a logical link (N1, N2)∈L, we define a C×1 channel assignment vector If node N1 communicates with node N2 over the ith frequency channel, then the ith element in is equal to 1; otherwise, it is equal to zero. As an example, assume that C = 4 and node N1 is assigned to communicate with node N2 over the third channel. We have = [0 0 1 0]. To establish the logical link (N1, N2) ∈ L, nodes N1 and N2 should assign a common frequency channel to communicate with each other. This requires that:
In this approach each node in the network is equipped with multi-interfaces, one interface is configured to a fixed channel while the others interfaces can be dynamically switched between channels. The algorithm starts with each node assigning a fixed channel to its fixed interface and a default channels to its switchable. When a node has data to send, it switches its dynamic interface to the fixed channel of the receiver nodes interface.
Figure 1 illustrates the protocol operation. Assume that node N1 has packets to send to node N3 via node N2. Nodes N1, N2 and N3 have their fixed interfaces on channels 2, 3 and 1 and switchable interfaces on channels 1, 2 and 3, respectively. In the first step, node N1 switches its switchable interface from channel 1-3, before transmitting the packet, because channel 3 is the fixed channel of node N2. In the next step, node N2 switches its switchable interface to channel 1 and forwards the packet, which is received by node N3 using its fixed interface.
Channel queue: During the operation of the network, nodes may have very different loads to forward traffic to the other nodes, AODV protocol may select the most loaded nodes.
The proposed algorithms take into account the channel queue length to determine the best route to a destination node. The main goal of this operation is to reduce the end-to-end delay as well as the interferences on the wireless medium. So, an indicator of the load distribution/available capacity among nodes interfaces is needed to help in the selection of intermediate nodes. To solve practical problems, the first step is to identify the appropriate queuing system and then to calculate the performance measures. Our queuing system considers each interface the node Ni is an M/M/1 queuing system arrivals from different sources (either generated at Ni itself). Figure 2 shows The M/M/1 queuing model which we have implemented in our solution. We note that:
||Arrival defines the way packets enter the system. Mostly the arrivals are random with random intervals between two adjacent arrivals
||Queue represents a certain number of packets waiting for service or to be forwarding (the queue may be empty)
Because we have multi interface in each node, in this model (Fig. 3) arriving packets are served by the first interface available. The model assumes that there are S identical interfaces, the service time distribution for each interface is exponential.
Using these assumptions, we can describe the operating characteristics with the following equation:
||Number of interfaces in the system
||Protocol operation when using "Fixed" and "Switchable interfaces"
||M/M/1 queuing model
||Multi M/M/1 queuing system
The average utilization of the system. The probability that no packets are in the system:
The average number of packets waiting in line:
The average time spent waiting in line:
The average time spent in the system, including service:
The average number of packets in the service system:
Network model: Consider a multi-channel multi-interface ad hoc network and assume that N denotes the set of nodes. Each node is equipped with S interfaces. There are C frequency channels available. We assume that the networks logical topology has been predetermined. Let L denote the set of all unidirectional logical links. The logical link from node N1 to N2 is denoted by (N1, N2)∈L. We assume the connectivity to be symmetric. That is, link (N1, N2)∈L if and only if (N2, N1)∈L.
Each node is assumed to have an equal transmission range, denoted by r. Let rN1N2 denote the distance between nodes N1 and N2. Nodes N1 and N2 are said to be neighbors if they can directly communicate with each other if rN1N2<= r.
Queuing network and delay model: We apply an M/M/1 queue to our queuing network model. Each node has a finite buffer B, which means that packets are dropped when the buffer is full in the network. The packets are served by the nodes on a first in first out.
The queuing delay is the sum of waiting time at a source node and intermediate nodes due to the route establishment and network congestion. It is a key component of network delay. When packets arrive at a node, they have to be processed and transmitted. A node can only process one packet at a time. If packets arrive faster than the node process it puts them into the queue (buffer) until it can get around to transmitting them. The delay can also vary from packet to packet, so averages and statistics are usually generated when measuring and evaluating queuing delay.
The expected queuing delay that a packet waiting for transmission in the entire network from source to destination is given by:
where, Tq is the average time spent waiting in queue of a node and E (H) is the number of hop count between a source and destination pair.
Residual energy: The residual energy is the remaining energy at every node which is the energy left after the packet transmission. This approach selects a route that contains nodes having maximum available residual energy, so that, the energy usage among all nodes can be balanced. Energy is calculated at the time of broadcasting RREQ messages by using the equation:
where, ENi is the current remaining energy of the node i, ENj is the current remaining energy of the node j connected with i and H is the number of hops from the current node to the node that transmits the request (source node).
Model implementation: The interactions between these parameters make the development of a new routing protocol very complex. Our solution consists to develop a cross-layer to share key information between network and MAC layer. The goal of this technique is to take benefit of informations about the channel quality, residual energy of the node and channel queue to develop a best routing technique. The inter-layer interaction will be managed by the network status (Fig. 4) for giving on demand to each layer, the information about other layers. So, this interaction enables us to use the information the mac layer to define a new cost metric in ad hoc network using genetic or dynamic programming.
|Fig. 4:||Cross-layer interaction between MAC and network layer
||Example of propagation of RREQ in AODV-DP and AODV-GA
||Genetic algorithm process
GA-AODV and DP-AODV operations: This study describes mechanisms for the implementation of energy and queuing model in the routing protocol. This proposed protocols called DP-AODV (dynamic programing AODV) and GA-AODV (Genetic algorithm AODV) have main objectives for selecting a node with energy and load as a parameter. So, in order to increase the lifetime of the node, it is desirable to take into account the remaining energy and load. Therefore, it is significant to select a node with a high remaining energy and minimum load.
In order to implement queuing model and residual energy in our protocols, three new vectors, called residual energy vector (RE), queuing delay (Q) and node label vector (LB) are added to the RREQ. To find a route to a destination node, a source node floods a RREQ packet over the network. When neighbors nodes receive the RREQ packet, they update the RE, LB and Q by adding their residual energy, their queuing delay, their index and continue to broadcast the message to their neighbors and so on. The forwarding process is continued until the destination node is reached. An intermediate node can receive multiple copies of the same route request broadcast from various or same neighbors. In this later case if this path include the path has already received with the same source address and broadcast_id it will discard the packet without broadcasting it furthermore.
When destination node is reached it triggers the data collection timer in order to receive all RREQ messages forwarded through other routes, at the end of this process the node has a complete database of energy and queuing delay of each node in the LB vector. Destination node uses an algorithm to find the best route for communication, add this route in route reply and sends it for the source node. Figure 5 shows an example of broadcasting RREQ messages from the source node (1) to the destination node (7).
Genetic algorithm: Genetic algorithm is a search technique used in computing to find true and approximate solutions to optimization and search problems. The genetic algorithm process consists of the following steps: Encoding, evaluation, crossover and mutation. Figure 6 shows the genetic algorithm process.
A description of the GA implementation, which has been used in this study and its special features like the implementation of the fitness function and the other genetic operators will be further discussed and are illustrated on the figure.
The operations of our GA-AODV protocol are:
Encoding: As multi-path problem is ordering problem so we have used permutation encoding. In permutation encoding, every chromosome is a string of numbers, which represents number in a sequence, number represents each node. The first number is set to the source node index and the last is set to the destination node.
A chromosome which is represented by 1, 4, 6, 7 says order of nodes, in which the source node 1 will send data to the destination node 7 in this order 1→4→6→7.
Fitness evaluation: The fitness function that characterizes each chromosome represents the total length of the path from the source node to the destination moving according to the order of the genes in the chromosome.
In this approach fitness value of the path is based on multiple metrics as residual energy, hop count and queuing delay. So, it can be classified as multiple objectives optimization problem. Each objective function can be assigned a cost and then the costs are combined into a single objective function. Consider f1 as a fitness function due to the residual energy and hop count:
And f2 as fitness function due to the queuing delay :
So, the multiple objectives fitness is given as:
Initial population: The first step in the functioning of a GA is then, the generation of an initial population. This population encodes a possible solution for our problem. So, the algorithm in first generation randomly selects some paths as chromosomes from among the allowed paths from source node to destination node.
Next generation: At each step, the genetic algorithm uses the current population to create the children by applying crossover and mutation mechanisms to make up the next generation.
Selection: In our implementation we have selected the roulette wheel selection. In this technique, all the chromosomes in the population are placed on the roulette wheel according to their fitness value.
||Roulette wheel selection
|Fig. 8:||Crossover operation
A random number is generated and the chromosome whose segment spans the random number is selected. The process is repeated until the desired number of chromosomes is obtained (Fig. 7).
Crossover: Crossover refers to the process of creating a new offspring trial solution by combining gene values from two parents selected from the current generation. For example, using two paths from source node 1 to destination node 8 each path is a chromosome and we randomly pick a crossover point and then switch all genes after that point. In Fig. 8, we could choose the crossover point after the node 4 or 5 in this example we have chosen node 4.
Mutation: Mutation is performed after crossover and introduces random modifications. With some low probability we choose a point to mutate and switch that point (Fig. 9). For instance, in our example we have:
|Fig. 9:||Mutation operation
Dynamic programming algorithm: We implement Bellman-Ford algorithm to solve the single-source shortest-path problem. The algorithm initializes the distance to the source vertex to 0 and all other vertices to ∞. It then does V-1 passes (V is the number of vertices) over all edges relaxing or updating, the distance to the destination of each edge.
So, given our weighted graph G (V, E) of nodes with weighted edges f:E→R:
We define the path weight of a path p = <v0, v1,
So, the shortest-path weight from u to v is:
A shortest path from vertex u to vertex v is then defined as any path p with weight:
The pseudo code for this algorithm is illustrated as follows:
Simulation and performance metrics: We have created several scenarios to evaluate the three protocols. The topology of simulation varies with the number of nodes (5, 10, 15, 20 and 25) which work in the multi-channel multi-interface, placed uniformly, forming a mobile ad hoc network with nodes over a 1000×1000 m area for 600 sec of simulated time and varying pause time with minimum 3 sec and maximum of 25 sec have been considered. For network traffic we create a CBR connection pattern between nodes. Regarding the genetic algorithm we fixe 0.9 to crossover probability and 0.02 to mutation probability.
Performance is measured on the basis of four performance metrics:
||Average end-to-end delay
||Normalized Routing Load (NRL)
Figure 10 and 11 show delivery ratio of the data packets the Traditional AODV, GA-AODV and DP-AODV in terms of variation of number of mobile nodes and pause time. The packet delivery ratio needs to be high to get an effective performance of routing. It is further observed that, as the node density or pause time is increased, the routing protocols have a higher packet delivery ratio. We notice also that in all variation of the two parameters (node density and pause time) show higher values of GA-AODV and DP-AODV as compared to traditional AODV, because in general when active route fails, the interface queue becomes full,so this results into a higher packet drop rate. Proposed protocols GA-AODV and DP-AODV select the nodes which have less traffic and sufficient energy.
|Fig. 10:||Comparison of packet delivery ratio with number of nodes
|Fig. 11:||Comparison of packet delivery ratio with pause time
|Fig. 12:||Comparison of average end-to-end delay with number of nodes
|Fig. 13:||Comparison of average end-to-end delay with pause time
This mechanism reduces the chances of route failure which result in improving the packet delivery efficiency.
|Fig. 14:||Comparison of normalized routing overload with number of nodes
|Fig. 15:||Comparison of normalized routing overload with pause time
The results from the simulation show that as the pause time and node size increases the end-to-end delay is lower for the enhanced protocols as seen in Fig. 12 and 13. Average end to end delay in traditional AODV and under all scenarios, is always higher than it is in GA-AODV and DP-AODV. This is because data packets in traditional AODV spend more time in interface queues since this protocol doesnt consider the load situation of the nodes when discovering paths. When we compare just the two protocols GA-AODV and DP-AODV, we observe that GA-AODV works well while raising the number of nodes due to the shortest running time. However, the DP-AODV overhead GA-AODV when augmenting the pause time because the network becomes stable so the exact algorithm is appropriate.
From Fig. 14 and 15, the variation in number of mobile nodes and pause time depicts that Traditional AODV has more normalized overload than GA-AODV and DP-AODV. Normalized routing overload should be less for better performance. The number of nodes in the network and pause time will affect the requirement of route discovery between different pairs of source and destination. It can be seen from Fig. 16 that the control overhead also decreases when the pause time increases, because in the presence of high mobility, link failures can happen very frequently and it triggers new route discoveries in AODV since it has at most one route per destination in its routing table.
|Fig. 16:||Comparison of lifetime with number of nodes
|Fig. 17:||Comparison of lifetime with pause time
In these approaches the nodes of the more residual energy and minimum load are selected as intermediate nodes, so the route will not broke quickly, thus it reduces the number of routing discovery.
From Fig. 16 and 17, the results show that the energy consumption increases as the node density increases and the survival time of GA-AODV protocolis higher than traditional AODV and DP-AODV routing protocols because genetic algorithms dont necessarily find the global optimal solution. Thus they can diversify the traffic in the network and distribute the energy consumption better than the two other protocols, so we can save power consumption of nodes significantly. Other causes which let dynamic programming unfavorable than genetic algorithms are its long running time and usage a lot of memory.
In term of PDR and following the recommendation from Kyasanur and Vaidya10,11 the results are near optimality that assured and overcame the results of Manickam and Manimegalai8 based on the same conditions. Conversely, the results are inconsistent with Kumar et al.7 and Sharma and Patheja21 because as the number of node increase, as they move very frequently thereby increasing their mobility thus making the higher probability for routing breakage. Concerning the average end to end delay the results are consistent with Ambhaikar et al.22, Yadav et al.5 and Manickam and Manimegalai8 despite the approaches of these works is different from ours, although their protocol reacts the same way as the Fig. 12 and 13, but our approaches give better performance. We notice that the NRL results are consistent with the work of Kumar et al.7 so the number of nodes in the network and pause time will affect the requirement of route discovery between the nodes. Finally, in term of consumption the energy the results are consistent with Yadav et al.5 and Sharma and Patheja21 because the modified protocols in these works can diversify the traffic in the network, our approaches in addition of that can also distribute the energy consumption better than others.
CONCLUSION AND FUTURE RECOMMENDATION
In this study we proposed the GA-AODV and DP-AODV routing protocol for MANETs. In comparison to other competent approaches from the literature, our proposed solutions enhance significantly the AODV routing protocol by selecting routes that use multiple channels and alternate them at each intermediate node in order to reduce the intra-flow interferences, increasing significantly the network capacity by utilizing all the available channels, decreasing end to end delay by using load sharing mechanism, preserves the residual energy of nodes and balances the consumed energy to increase the network lifetime.
From these results, we can allow ad hoc networks to become as useful as telephone networks for audio conversations, as well as supporting new applications with even stricter service demands.
Further, this study can be extended to the other optimization situations such as multimedia multicast routing, minimum cost spanning trees, maximum-flow augmenting paths, location problems and other problem NP-complete.