Mobile ad hoc network (MANET) is a dynamically reconfigurable wireless network with time-variable infrastructure. Given that nodes are highly mobile, MANET’s topology often changes. These changes increase the difficulty in finding the routes that the packets use when they are routed. This study proposes an algorithm called genetic algorithm-based location-aided routing (GALAR) to enhance the MANET routing protocol efficiency. The GALAR algorithm maintains an adaptive update of the node location information by adding the transmitting node location information to the routing packet and selecting the transmitting node to carry the packets to their destination. The GALAR was constructed based on a genetic optimization scheme that considers all contributing factors in the delivery behavior using criterion function optimization. Simulation results showed that the GALAR algorithm can make the probability of packet delivery ratio more than 99% with less network overhead. Moreover, GALAR was compared to other algorithms in terms of different network evaluation measures. The GALAR algorithm significantly outperformed the other algorithms that were used in the study.
Mobile ad hoc network (MANET) allows users to stay connected via wireless communication known as infrastructure-less network of mobile devices. This network has a series of mobile wireless nodes that travel in every direction and position independently [
The most challenging task for MANET is to identify the most efficient route between nodes because of dynamic topology changes and battery drain rate. Establishing the routes in the shortest time possible is the most crucial step because it reduces the delay of data delivery and helps achieve faster convergence [
MANET topology’s rapid and frequent changes cause the nodes’ free movement with no restriction in direction or mobility (i.e., speed and pause time). The problems that arise especially for nodes running at high speed and at different directions are data routing and packet dissemination. These issues emerge because of high mobility and regular topology changes. Wireless connections between such nodes can also break or expire. Consequently, the wireless connection must be re-established. When this occurs, the network is flooded with many control packets and route error packets.
Link breakages are frequently experienced in MANET with high node mobility. For example, one of the key limitations is that a node that is part of a path loses communication with its neighbors; it loses the ability to interact with the other nodes. The disconnected node then relays its disconnection message to the source node and consequently demands a new path exploration session. This event creates additional overhead on the network, slows the packets’ delivery time, and causes the broadcasting storm issue [
This work presents an analytical study that examines the location-aided routing (LAR) protocol in MANET. This well-known location-based routing method uses the information of the location of a mobile node via the global position system technique [
The rest of this paper is structured as follows. Section 2 addresses the research background and related studies. Section 3 describes the suggested GALAR strategy. Section 4 assesses and analyzes the efficiency of the GALAR. Section 5 summarizes the analysis and outlines the future work.
In this study, the LAR protocol, a well-known position-based protocol, is a mechanism that seeks to minimize the overhead control message of the ad-hoc on-demand distance vector routing protocol by flooding only a portion of the network that is likely to contain the destination route.
According to [
In LAR, flooding happens when the forwarding packets to the nodes do not enter the destination inside the request zone. Thus, for LAR to operate, nodes must know whether they are in the request zone to either drop or begin to flood the packet. Researchers who have undertaken LAR studies suggest two separate node schemes to assess whether they are in the requested region.
The first scheme includes a sender who sends a request for a route with the rectangle coordinates in the request zone. A node that receives this request for the route may discard the request for the route if it is not within the rectangle and forward it to the endpoint if it is inside the rectangle. When the route request (RREQ) has reached its destination, it will respond with the route reply (RREP) message.
As shown in
The second scheme does not explicitly identify the request zone when sending a request for a route. Instead, it forwards a packet depending on the distance from the destination of the sending node that is used in the RREQ. Thus, in
GA is a type of adaptive stochastic optimization algorithm that uses natural evolution concepts for searching and optimization [
A simple and effective GA is composed of three operators, namely, reproduction, crossover, and mutation. The first process is a reproduction, which initializes the start of a population. Reproduction is the main evolutionary loop that evaluates each individual’s fitness function based on the fitness score. By using one of the methods of selection, individuals from a population are chosen. The more desirable a candidate is, the better its odds of being chosen. Nature performs its function as the chosen individuals are partnered to experience the mating crossover phase to create one or more children from each pair.
The second approach is the crossover, which attempts to incorporate strategies to enable the child to inherit its parents’ features. It typically consists of one parent copying half of the genotype and filling another parent with the remaining genes.
The mutation is the third phase. Each child is granted the ability to experience a mutation phase in which certain parts of their genotype spontaneously change. This stage may have the randomness factor of the method to expand the search space. As a substitute for the older population, all new children serve the new generation. The whole process is replicated before one of the stopping conditions is met.
The evolution and natural selection processes in GA are measured on the sample of candidate solutions (individuals). Each individual (offspring) in the population is a specific solution to the problem; each individual is a series of traits written in the individual’s chromosome or genotype as in nature. Depending on the genotype, each individual is then evaluated on a fitness function. This function calculates the individual’s score on the nature of the issue in solving a specified study problem. The problem can be either a case of minimization, where low scores are preferred or a problem of maximization, whereby high scores are preferred [
This section contains related works, which present diverse classes of ad hoc directing conventions and evaluations of a few areas based on a routing protocol. To generate location information, the overwhelming majority of position-based routing protocols presume a necessary process known as location service. Location services are categorized into proactive and reactive levels [
A mobile node that uses a proactive protocol exchanges its position data regularly with multiple mobile nodes [
In [
In [
In [
The authors in [
The authors in [
In [
In [
In [
In [
In [
Most approaches enhance the LAR protocol from narrowing the search region of the candidate nodes and limiting the number of candidate nodes that carry the packets. Many methods rely on the position table that contains the nodes’ information location while they are in movement. This table is built by adding information about the sending node’s position to the header of the packet. However, the information displayed on the information table about the node’s position may not be exact because the node has moved to the current position. Thus, the earlier information of its location has expired. Therefore, any geometric-based expectation of the request and expected zones based on the single observation of the node’s location (even though it is the most recent one in the packet updates) can be misleading. Given that maintaining the information displayed on the table is impossible, sending the separate packets is the updated method because this may allocate a significant part of the bandwidth.
Despite all the developments of LAR, two main limitations exist in literature approaches. First, mobility is based on the assumption that the nodes operate at a constant speed, which is invalid all the time in MANET networks. Second, either the definition of the request zone is geometrical or ignores many other contributing variables in the nodes’ routing capability.
The proposed approach adds two main concepts of the LAR procedure. First, determining the destination node’s current position becomes more accurate because the position information of the transmitting node is added to the packet even if the transmitting node is only a routing node. Moreover, any node that receives a packet updates either the packet location information or its location table information to the most recent one. Second, selecting the contributing variables in the routing process and their significance is performed automatically based on genetic optimization. Genetic optimization is appropriate for avoiding local minima and determining the most accurate formula for the request zone. This formula is used to select the candidate nodes from a transmitting node’s coverage zone to carry a request packet to its destination for finding an optimum route for transmission between a source node and a destination node. The procedure for a developed LAR protocol consists of three sections, namely, route discovery using an RREQ packet), genetic optimization of criterion function, and GALAR algorithm operations.
In GALAR, an RREQ packet includes the information provided in
The criterion function of selecting the eligible node to carry the RREQ packet is related to six variables, as shown in
The six variables are used with their inverse in the criterion function. Thus, the criterion function contains 12 variables. The formula for this criterion function is
The coefficients
When a chromosome is enabled, the value of the criterion function is evaluated for its parameters with respect to each node in the coverage zone, and a threshold is applied to select a node from the coverage zone to be eligible for routing. To select the elite among the whole population for performing the mutation and crossover for generating the offspring, the fitness function value is calculated concerning three evaluation measures, namely, the length of the shortest route, the delay for obtaining the shortest route, and the number of routes that are generated from this criterion function. The variables are being minimized in this optimization. Thus, the elite is selected with the low value of the shortest route, its corresponding delay, and the number of routes generated from this chromosome. Once the elite is selected, 0.8/0.2 crossovers are performed, and 20% mutation is applied to maintain other solutions that may lead to the optimal one. The GA is enabled in two scenarios: the nodes are stationary (static), and the nodes are moving within 2 s interval (dynamic). Two criterion functions are found for each.
If the problem has been identified, then the candidate alternatives will follow the steps of a GALAR as follows.
Select two parent chromosomes (two possible solutions of the criterion function) based on the selection probability.
The crossover operator produces two offspring: crossover and multipoint crossover probability (
All offspring are mutated at each locus operator using the mutation given a defined mutation probability (
If n is odd, then a discard function is highly likely to discard a less fit chromosome.
For GALAR algorithm operations, this study has modified the mechanism of algorithms for sending an RREQ buffer, an RREQ buffer, a received RREQ buffer, and an ACK buffer. The GALAR algorithm detail operations are shown in
This section presents the simulation environment. The performance of the proposed GALAR algorithm was compared with that of LARwith, which is a development of the classical LAR by embedding the position information of the transmitting node in the RREQ packet where the information table is updated frequently about the other nodes’ positions than LAR. Moreover, GALAR was compared with Heuristics, which indicates designing the criterion function based on experience about how the variables of the embedded factors should influence the routing process. The criterion function’s coefficients should be guessed based on the nature of the corresponding term’s variable in the criterion function and compared with the standard protocol LAR, which has been proposed in [
In this study, 10, 20, 30, 40, 50, 60, 70, 80, 90, and 100 nodes were simulated to allow for the nodes’ arbitrary movement. The nodes have a fixed speed of 0.4 m/s for each node to avoid dealing with the high change of network dynamics and be suitable with the environment dimensions of 20 m
Description | Value | Unit |
---|---|---|
Simulator | MATLAB | – |
Channel type | Wireless | – |
Network area size | m2 | |
Number of mobile nodes | 100 | nodes |
Simulation time | 400 | s |
Routing protocol | LAR | – |
Node transmission range | 5 | m |
Nodes speed | 0.4 | ms |
Moving type | Random | – |
Threshold | 0.65 | – |
RREQ packets’ lifetime | 1.6 | ms |
Node check available routes | 2 | ms |
Packets’ generating rate | 250 | s |
The following are the performance metrics used in the simulation experiments.
where
This study enabled GA in two scenarios. The nodes were maintained at a stationary (static) position, and the nodes were made to move within a 2 s interval (dynamic). Two criterion functions were found for each. To determine which of the two functions is better; the PDR between them was compared. The results of the comparison are shown in
The graph shows that the network performs well when the movement of the nodes has been considered. The average value of PDR in a dynamic-node situation was 94.81%, whereas in a stationary-node situation, it was 88.14%. The efficient optimization scheme interprets this for establishing the route while tuning the criterion function in the dynamic situation. The reason is the great capability of capturing the dynamics of the environment and the moving nodes. Thus, the criterion function of a dynamic situation was used in the next experiments. The values of coefficients after tuning are as follows:
Experimental results indicate that the maximum weight observed was 1.3513, and the minimum weight was 0.3335. After tuning the criterion function coefficients, this study aims to prove that the proposed GALAR algorithm outperforms the traditional LAR algorithm. Thus, the PDR, PLR, E2E delay, RREQ overhead, and performance index were compared with an enabling GA for tuning the weights, GALAR.
The proposed GALAR algorithm acquired the least time to reach the data packet to the destination. The time at which the first packet was transmitted from the source was subtracted from the time where the first data packet arrived at the destination.
This delayed reduction in the GALAR algorithm is explained by the fact that the GALAR algorithm selects the most suitable node to be a candidate for routing the packets. The efficiency in routing is explained by the criterion function optimized based on a dynamic scenario while considering all factors in successful routing. The selection process caused no computational complexity.
To prove that this GALAR algorithm reduces the network load, the RREQ overhead needed to achieve the connection between nodes was calculated for 10 cases.
To evaluate the overall performance of the proposed protocol, the authors calculated the new performance metrics, namely, performance index. The results of the performance index are shown in
This work analyzed the performance estimation of LAR protocols, considering the use of location information to enhance ad hoc network routing protocols using two scenarios. First, the likelihood of achieving high accuracy in determining the current position of the destination node was achieved by adding the position information of the transmitting node to the packet even when the transmitting node is only a routing node. Moreover, any node that received a packet updated either the packet location information or its location table information to the most recent one. Second, selecting the contributing variables in the routing process and its significance was performed automatically based on genetic optimization.
Genetic optimization is appropriate for avoiding the local minima and determining the most accurate formula for the request zone. This formula selected the candidate nodes from a transmitting node’s coverage zone to carry a request packet to its destination to find an optimum route of transmission between a source node and a destination node. Location routing protocols can be improved significantly using an optimization scheme of node selection criteria to pass the packets to their final destination.
This study has proven that evolutionary genetic optimization can map the request zone to a node selection criterion. Moreover, this selection has converted routing from being geometric region-oriented in past research to being node-oriented. This approach proves and supports the concept that the request zone has nonlinearity due to different protocol natures, environments, and node dynamics. Thus, using an analytical definition of a request zone is a key factor in reducing overhead in the network, improving QoS, and addressing other delay measures. The simulation results show that the GALAR algorithm makes a packet delivery that reaches more than 99% with less RREQ, which poses a good performance with few overheads in the network. Moreover, GALAR was compared with other protocols concerning different evaluation measures, and the GALAR algorithm significantly outperformed the other methods.
As a future work, the energy level of the nodes should be considered in the selection criterion process. Nodes with less energy should be avoided to maintain the long lifetime of the network. Characterizing the influence of nodes’ mobility and dynamics on the performance of the protocol would also be helpful. Thus, more studies may be able to investigate the process of improving the protocols to handle several issues.