Energy Efficient Multipath Routing Protocol for Mobile ad-hoc Network Using the Fitness FunctionMueen Uddin*1, Aqeel Taha1, Raed Alsaqour2, Tanzila Saba3*1Department of Information System, Faculty of Engineering, Effat University Jeddah Saudi Arabia 1School of Computer Science, Faculty of Information Science and Technology, Universiti Kebangsaan Malaysia, 43600, Bangi, Selangor, Malaysia 2College of Computation and Informatics, Saudi Electronic University, Jeddah Saudi Arabia 3College of Computer and Information Sciences, Prince Sultan University Riyadh Saudi ArabiaAbstract – Mobile Ad Hoc Network (MANET) is a collection of wireless mobile nodes that dynamically form a temporary network without the reliance on any infrastructure or central administration. Energy consumption is considered as one of the major limitations in MANET, as the mobile nodes do not possess permanent power supply and have to rely on batteries, thus reducing network lifetime as batteries get exhausted very quickly as nodes move and change their positions rapidly across MANET. The research proposed in this paper highlights this very specific problem of energy consumption in MANET by applying the Fitness Function technique to optimize the energy consumption in Ad Hoc On Demand Multipath Distance Vector (AOMDV) routing protocol. The proposed protocol is called Ad Hoc On Demand Multipath Distance Vector with the Fitness Function (FF-AOMDV). The fitness function is used to find the optimal path from the source to the destination to reduce the energy consumption in multipath routing. The performance of the proposed FF-AOMDV protocol was evaluated by using Network Simulator Version 2 (NS-2), where the performance was compared with AOMDV and Ad Hoc On Demand Multipath Routing with Life Maximization (AOMR-LM) protocols, the two most popular protocols proposed in this area. The comparison was evaluated based on energy consumption, throughput, packet delivery ratio, end-to-end delay, network lifetime and routing overhead ratio performance metrics, varying the node speed, packet size and simulation time. The results clearly demonstrate that the proposed FF-AOMDV outperformed AOMDV and AOMR-LM under majority of the network performance metrics and parameters.Index Terms: Energy efficient protocol, mobile ad hoc network, multipath routing, and fitness function.I. INTRODUCTIONThe performance of computer and wireless communications technologies has advanced in recent years. As a result, it is expected that the use and application of advanced mobile wireless computing will be increasingly widespread. Much of this future development will involve the utilization of the Internet Protocol (IP) suite. Mobile ad hoc networks (MANETs) are envisioned to support effective and robust mobile wireless network operation through the incorporation of routing functionality into mobile nodes. These networks are foreseen to have topologies that are multihop, dynamic, random, and sometimes rapidly changing. These topologies will possibly be composed of wireless links that are relatively bandwidth-constrained 1. Ad hoc networks are crucial in the evolution of wireless networks, as they are composed of mobile nodes which communicate over wireless links without central control. The traditional wireless and mobile communication problems like bandwidth optimization, transmission quality enhancement and power control are directly inherited by ad-hoc wireless networks. Furthermore, new research problems like Configuration advertising, discovery and maintenance are also brought on by ad hoc networks because of their multi-hop nature, lack of a fixed infrastructure and ad-hoc addressing and self-routing. There have been numerous proposals on different approaches and protocols as there are multiple standardization efforts being done in the Internet Engineering Task Force and even as academic and industrial ventures 2.In MANETs, the limited battery capacity of a mobile node affects network survivability since links are disconnected when the battery is exhausted. Therefore, a routing protocol considering the mobile nodes energy is essential to guarantee network connectivity and prolong the network lifetime 3. Power-aware routing protocols deal with techniques that reduce the energy consumption of the batteries of the mobile nodes. This approach is basically done by forwarding the traffic through nodes that their batteries2169-3536 (c) 2016 IEEE. Translations and content mining are permitted for academic research only. Personal use is also permitted, but republication/redistribution requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html for more information.This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/ACCESS.2017.2707537, IEEE Accesshave higher energy levels. This will increase the network lifetime.Various power-aware routing protocols have been proposed by taking into account the energy consumption for the transmission or the remaining battery level of the mobile nodes or both. By using such power-aware information, various routing costs and path selection algorithms have been investigated for the purpose of improving the energy efficiency in the MANET 4. Many routing protocols have been developed during the last years to increase the lifetime of a route and in turn the lifetime of the network. One of these developments is multipath routing protocols. Multipath routing protocols enable the source node to choose the best route among many routes during a single route discovery process. This process in multipath routing will decrease the number of route discovery processes since there are backup routes already available and in case one route fails will reduce the end-to-end delay, energy consumption and the network lifetime.Multipath routing protocols flood a route request to learn more than one path to the destination to forward packets through them. It is not necessary that the source will always find the optimum or the shortest path available. Since the power source of the mobile nodes is limited, the power consumption by these nodes should be controlled to increase the network lifetime. Multipath routing protocols have several issues. One of them is finding an optimum path from the sources to the destinations. The issue becomes more complicated with a large number of mobile nodes that are connected to each other for transferring the data. In this case, most of the energy is going to be consumed at the time of investigating for shortest routes. Subsequently, the more energy is wasted at data transfer.The research in this paper presents an energy efficient multipath routing protocol called Ad-Hoc On demand Multipath Distance Victor with the Fitness Function (FF-AOMDV). The FF-AOMDV uses the fitness function as an optimization method, in this optimization, we seek for two parameters in order to select the optimum route are; energy level of the route and the route distance in order to transfer the data to the destination more efficiently by consuming less energy and prolonging the network lifetime. Based on the results of the simulation, the FF-AOMDV routing protocol outperformed both Ad-Hoc On demand Multipath Distance Victor (AOMDV) and Ad-Hoc On demand Multipath Routing with Life Maximization (AOMR-LM) routing protocols in terms of throughput, packet delivery ratio, end-to-end delay, energy consumption, network lifetime and routing overhead ratio except the AOMR-LM when comparing with energy consumption and network lifetime where it has better performance than FF-AOMDV with these two metrics.The rest of the paper is organized as follows: Section 2 discusses the background of AOMDV, fitness function and related studies; Section 3 presents the proposed FF-AOMDV; Section 4 presents the results and evaluation, Section 5 concludes the study and presents the future work.II. BACKGROUD & RELATED WORKA. AOMDV Routing ProtocolAn on-demand routing protocol, AOMDV has its roots in the Ad hoc On-Demand Distance Vector (AODV), a popular single-path routing protocol. AOMDV creates a more extensive AODV by discovering, at every route discovery process, a multipath (i.e. several other paths) between the source and the destination. The multipath has a guarantee for being loop-free and link-disjoint. AOMDV likewise offers two key services: route discovery and route maintenance. Since it greatly depends on the AODV route information, which is already available, AOMDV incurs less overhead than AODV through the discovery of multiple routes. Compared to AODV, AOMDV’s only additional overhead is extra RREPs and RERRs intended for multipath discovery and maintenance, along with several extra fields to route control packets (i.e. RREQs, RERRs and RREPs) 5. Adding some fields and changing others modified the structure of the AOMDV’s routing table. Figure 1 presents the routing table entries’ structure for AODV and AOMDV. In AOMDV, advertised_hopcount is used instead of the hopcount in AODV 6. A route_list stood as a replacement for nexthop; this change essentially defining multiple nexthops with respective hopcounts. All nexthops, however, are still allotted the same destination sequence number. Every time the sequence number gets updated, the advertised_hopcount is initialized.After performing the simulations using NS-2, the overall performance comparison between AOMDV-AODV shows that the former algorithm was able to cope up with route failures more effectively that are mobility-induced. Particularly, AOMDV decreases the packet loss to 40% and greatly improves the end-to-end delay. It also causes a reduction of routing overhead to about 30% by decreasing route discovery operations’ frequency hence improving the overall2169-3536 (c) 2016 IEEE. Translations and content mining are permitted for academic research only. Personal use is also permitted, but republication/redistribution requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html for more information.This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/ACCESS.2017.2707537, IEEE Accessperformance of MANET compare to AODV algorithm.Fig. 1. Routing table structure for AODV and AOMDV 21B. Route discovery and maintenanceRoute discovery and route maintenance involve finding multiple routes from a source to a destination node. Multipath routing protocols can try to discover the link-disjoint, node disjoint, or non-disjoint routes 7, 8. While link-disjoint routes have no common links, it may have nodes in common. Node-disjoint routes, which are also referred to as totally disjoint routes, do not have common nodes or links. Non-disjoint routes, on the other hand, can have both nodes and links that are in common 9. AOMDV’s primary idea is in discovering multiple routes during the process of route discovery. The design of AOMDV is intended to serve highly dynamic ad-hoc networks that have frequent occurrences of link failure and route breaks. A new process of route discovery is necessary in the event that all paths to the destination break.AOMDV utilizes three control packets: the route request (RREQ); the route reply (RREP); and the route error (RERR). Initially, when a source node is required to transmit data packets to a specific destination, the source node broadcasts a RREQ 10. Because the RREQs is a flooded network-wide, several copies of the very same RREQ may be received by a node. In the AOMDV, all duplicate copies undergo an examination to determine the potential alternate reverse path. However, of all the resulting set of paths to the source, only the use of those copies, which preserve loop-freedom and disjointedness, get to form the reverse paths. In the event the intermediate nodes get a reverse path through a RREQ copy, it conducts a check to determine the number of valid forward paths (i.e. one or many) to the destination. If so, a RREP is generated by the node and the request is sent back to the source using the reverse path. Since this route discovery, the RREP has a forward path that was not employed in any prior RREPs. The RREQ is not further propagated by the intermediate node. Otherwise, the node would broadcast the RREQ copy again in case any other copy of this RREQ has not been previously forwarded and this copy has led to the updating or the formation of a reverse path.Like intermediate nodes, the destination likewise forms reverse paths when it receives RREQ copies. As a response to each RREQ copy arriving through a loop-free path towards the source, the destination produces a RREP, despite forming reverse paths that use only RREQ copies arriving through loop-free and disjoint alternate paths towards the source. A RERR packet is used in AOMDV route maintenance. In the event a link breaks, it generates a RERR message, listing lost destinations. The RERR is sent upstream by the node towards the source node. In the case of the existence of the previous multiple hops, which were using this link, the RERR is broadcast by the node. If there are no previous multiple hops, the request is unicast. Upon getting a RERR, the receiving node initially checks whether the node which sent the RERR is its own next hop towards any of the destination that is listed in the RERR 11. If the sending node is indeed the recipient node’s next hop, the receiving node makes this route table invalid, after which it propagates the RERR back to the source. In this manner, the RERR continues to be forwarded until the source receives the request. Once this happens, it can initiate the route discovery again if it still requires the said route.C. Disjoint PathTwo types of disjoint path exist, the node-disjoint path and link-disjoint path 12. In a node-disjoint path, there is no common node exists in a specific path other than the source and destination nodes. In a link-disjoint path, there is no common link at all 13.Fig. 2. Link and node disjoint path. (a) Link and node disjoint path, (b) Link disjoint path, (c) Not disjoint path2169-3536 (c) 2016 IEEE. Translations and content mining are permitted for academic research only. Personal use is also permitted, but republication/redistribution requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html for more information.This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/ACCESS.2017.2707537, IEEE AccessFigure 3.3 illustrates the notion of node and link disjoint paths. The routes ABE, ACE, and ADE have no common node or link, as illustrated in Figure 2 (a). Thus, they are link and node-disjoint paths. Figure 2 (b) shows the routes ABCDE and ACE have node C in common; however, there is no link in common, which makes a link-disjoint path without a node disjoint path. Lastly, Figure 2 (c) illustrates the routes ABCE and ABE, which have both the link AB and the node B in common; therefore, they do not have a disjoint path.D. Fitness FunctionThe fitness function is an optimization technique that comes as a part of many optimization algorithms such as genetic algorithm, bee colony algorithm, firefly algorithm and particle swarm optimization algorithm. The fitness function finds the most important factor in the optimization process, which could be many factors depending on the aim of the research. In MANET, the fitness factor is usually energy, distance, delay, and bandwidth. This matches the reasons for designing any routing protocol, as they aim to enhance the network resources. In this research, the fitness function used is part of the Particle Swarm Optimization (PSO) algorithm as proposed in 14. It was used with wireless sensor networks to optimize the alternative route in case the primary route fails. The factors that affect the choice of the optimum route are:? The remaining energy functions for each node? The distance functions of the links connecting the neighboring nodes? Energy consumption of the nodes? Communication delay of the nodesThe PSO algorithm is initialized with a population of random candidate solutions, conceptualized as particles. Each particle is assigned a randomized velocity and iteratively moved through the problem space. It is attracted towards the location of the best fitness achieved so far by the particle itself and by the location of the best fitness achieved so far across the whole population 15. The PSO algorithm includes some tuning parameters that greatly influence the algorithm performance, often stated as the exploration–exploitation trade-off: “Exploration is the ability to test various regions in the problem space in order to locate a good optimum, hopefully the global one. Exploitation is the ability to concentrate the search around a promising candidate solution in order to locate the optimum precisely 16, 17”. In this case, the particles are attracted towards two fitness parameters which are; energy level of the mobile nodes and the distance of the route. With these two parameters, the optimization could be found by forwarding traffic through the route that has the highest level of energy and less distance in order to minimize the energy consumption related studies.Smail et al. proposed an energy-efficient multipath routing protocol, called Ad hoc On-demand Multipath Routing with Lifetime Maximization (AOMR-LM), which preserves the residual energy of nodes and balances the consumed energy to increase the network lifetime. They used the residual energy of nodes for calculating the node energy level. The multipath selection mechanism uses this energy level to classify the paths. Two parameters are analysed: the energy threshold and the coefficient. These parameters are required to classify the nodes and to ensure the preservation of node energy. The AOMR-LM protocol improves the performance of MANETs by prolonging the lifetime of the network. This novel protocol has been compared with both AOMDV and ZD-AOMDV. The protocol performance has been evaluated in terms of network lifetime, energy consumption, and end-to-end delay 18.Manickavelu & Vaidyanathan concentrated on the route discovery process effect on the data loss, communication overhead and energy consumption. For these reasons, they proposed a particle swarm optimization (PSO) based lifetime prediction algorithm for route recovery in MANET. This technique predicts the lifetime of link and node in the available bandwidth based on the parameters like the relative mobility of nodes and energy drain rate. Using predictions, the parameters are fuzzified and fuzzy rules were shaped to decide on the node status. This information is made to exchange among all the nodes. Thus, the status of every node is verified before data transmission. Even for a weak node, the performance of a route recovery mechanism is made in such a way that corresponding routes are diverted to the strong nodes. The simulation results indicate that the proposed technique minimizes the packet loss and communication overhead 19.Sharma et al. proposed an energy efficient reactive routing protocol that uses the received signal strength (RSS) and power status (PS) of mobile nodes. Proposed Link Failure Prediction (LFP) algorithm used the link-layer feedback system to update active routes. Comparing the results of the proposed algorithm with existing algorithms, in terms of energy consumption, link failure probability, and retransmission of packets, the proposed algorithm outperform the existing algorithms 20.Nasehi et al. tried to discover the distinct paths between the source and destination nodes by using Omni directional antennas, to send information