Figure 1. Example of a Mobile Ad-hoc Network
Mobile ad-hoc networks (MANET) are formed by a group of mobile nodes and does not have any fixed infrastructure. Due to the node mobility nature in MANETs, different routing challenges such as, power constraints, link failures, and path breakages occur. Many routing protocols both proactive and reactive have been implemented to solve the routing challenges, but these protocols cannot defeat these issues in a complete manner. Researchers made an attempt to research on swarm intelligence based nature inspired algorithms to defeat the routing problems faced by the mobile ad-hoc networks. In the existing approach, BAT optimization which is a swarm intelligence technique was used to find the best path for Ad-hoc On-demand Multipath Distance Vector (AOMDV) protocol based on link availability and neighbour node queuing delay. But, this approach does not maintain a balanced control packet overhead. So, in this paper Bee Inspired routing Protocol (BeeIP) is proposed to provide multipath routing for mobile ad-hoc networks. BeeIP is a swarm intelligence based routing technique, which uses the honey bee forager behavior. Simulation results show that, the proposed approach BeeIP outperforms the BAT-AOMDV in terms of network performance metrics such as, packet delivery ratio, control overhead, average end to end delay.
Wireless Ad-Hoc Networks are the networks formed without any central supervision. In wireless ad hoc networks, mobile nodes are used as an interface for data transformation. These networks are also named as wireless mesh networks, and they prove many advantages over the traditional networks. Wireless ad-hoc networks become a good research area due to its applications in the real world. Wireless ad-hoc networks have two different kinds of networks, Mobile Ad-Hoc Networks (MANETs) and Wireless Sensor Networks (WSN).
As a type of wireless ad-hoc network, mobile ad-hoc networks (MANETs) also do not need any permanent environment for monitoring the behavior of mobile nodes. In mobile ad-hoc networks, every mobile node is selfdetermining and they show mobility nature. Here, intermediate nodes behave as two routers for data transformation. Mobile ad-hoc networks have many applications in real time environment due to its selfconfiguration and self-organization behavior. MANETs are facing different problems like, limited bandwidth, high energy/power usage, less security, etc., and all this makes routing in Mobile ad-hoc networks complex.
Figure 1 illustrates an example of a simple mobile ad-hoc network with 5 nodes. node 1, node 3 and node 5 are not within the range of each other, but the node 2 and node 4 can be used to forward the packets between node 1, node 3 and node 5. The node 2 and node 4 will act as a router and these five nodes jointly form a mobile ad-hoc network.
Figure 1. Example of a Mobile Ad-hoc Network
Routing protocols made routing in the Mobile ad-hoc networks success. MANETs have various kinds of protocols viz., Proactive and Reactive protocols.
Proactive protocols are also known as table-driven routing protocols. There are different proactive routing protocols such as, Optimized Link State Routing (OLSR) and Destination-Sequenced Distance 3 Vector (DSDV). The table-driven routing protocols maintain a table which consists of up-to-date routing information of every route from each node to another node in the network.
Reactive protocols are also known as On-Demand routing protocols. In the reactive type of protocols, the route discovery is done only when the data is required to send from source to the destination and no tables are used to store the routing information. There are different reactive routing protocols like, Dynamic Source Routing protocol (DSR) and Ad Hoc On-demand Distance Vector routing protocol (AODV).
Ad-hoc On-demand Multipath Distance Vector routing protocol (AOMDV) is a special type of reactive protocols and it is an extension protocol for AODV. Its main aim is to compute multiple loop-free and link-disjoint paths. AOMDV follows a new route discovery and route maintenance process based on hop count. This protocol selects an alternate path automatically, when a path failure occur, thus a new route discovery is not needed.
The present existing mobile ad-hoc network routing protocols exhibit many limitations, while they are used for routing like as below:
All these limitations give an idea to think of a new technique called Swarm Intelligence (SI) to use in the mobile adhoc networks.
Swarm Intelligence (SI) is an optimization technique inspired by the behavior of animals and insects and it is mainly used to solve the problems of optimization. Here, the word swarm means the set or group of mobile nodes/agents which are combined to solve a particular problem. Swarms are in large quantities found in nature. Naturally, animals or insects form into swarms to search for food, build nests, to hunt and keep away from being hunted from the other animals. Every single swarm follows a particular rule of an act and access to a limited amount of information via its direct neighbors. We have different Swarm Intelligence based techniques like Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), Honeybees paradigms, etc.
Particle Swarm Optimization (PSO) imitates the natural behavior of birds flock and fish schooling. PSO is mostly used to solve the population-based problems. Bird flock means a set of birds which are fly in a group from one place to another to find the food source. PSO algorithm mainly uses the parameters like velocity, and particle position to find the best solution. This technique is not very successful because it does not give a guaranteed optimal solution in a large search space.
Ant Colony Optimization (ACO) algorithm belongs to the family of swarm intelligence. ACO algorithm takes an inspiration from the attitude/behavior of ants and it mainly applies to optimization problems like finding the optimal path. In nature, the ants try to find the path from their food source and the colony and for this purpose, they follow a particular process which is an inspiration to the Ant Colony Optimization algorithm to solve the optimization problems.
Bee Colony Optimization (BCO) is inspired from the social behavior of natural honey bees. Similar to the ants, the honey bees also tries to find path from its hive to the food source. In nature, the scout bee goes to the food source and extracts honey from the flower. If it is satisfied with the food, then the bee returns to the hive in the same path it has found, and performs a special type of dance called Waggle Dance at the hive to give information to other bees about the food. Using the acknowledgment or feedback given by the forager bee, other bees move to the food source to fulfil their needs. The Bee Colony Optimization algorithm gives more efficient optimal solution than the other optimization algorithms.
Swarm intelligence based nature inspired Routing algorithms to have a few advantages like :
Adaptability means the capability of the algorithm and how fast and accurately it can adjust to different network conditions. Swarm intelligence based routing protocols can easily motivate to changes in the network environment, because of their advanced decision making skills used by the group of agents in parallel.
Robustness can be defined as the capability to behave correctly in any unseen conditions. Swarm intelligence based routing techniques are robust in case of individual agent errors, agent losses, communication errors, or other system failures. This is because of the co-operation and communication among the multiple agents in the network.
Scalability is the talent of a routing protocol to perform perfectly with one or more number of derived parameters of the network.
This paper mainly concentrates on BeeIP, a newly proposed swarm intelligence based routing protocol for MANETs, which is inspired by the honey bee’s behavior. Here, the paper is organized as follows:
Mobile ad-hoc networks are a good research area due to its flexibility and usage in real world applications. Many researchers have done their researches on MANETs and suggested different routing protocols, but the existing protocols are not completely successful in defeating the routing issues faced by the mobile ad-hoc networks. The researchers made an attempt to study on swarm intelligence. Several authors proposed various natureinspired routing algorithms for efficient routing in MANET's.
Xing She Yang (2010) developed a new swarm intelligence based optimization algorithm which imitates micro bat's echolocation behavior called the Bat Algorithm (BA). The Bat algorithm can find the optimal solution by using some parameters like frequency, loudness, pulse rates, and velocity. Naturally bats are the type of mammals that can fly and have an excellent echolocation capacity to identify the obstacles in the process of finding their food.
A new technique called BAT-AOMDV was proposed by Prabha R & Ramaraj N (2015). The bat optimization algorithm (BA) is used to find the optimal path using AOMDV (Ad-hoc On-Demand Multipath Distance Vector) routing algorithm based on the quality of link and queuing delay of the neighboring nodes. In this work, Prabha R & Ramaraj N (2015) followed a methodology referred by D. J., Jiang, S. M, & Rao J.Q (1999 & 2000) to predict the link availability and queue delay for a given source and destination and also multiple paths are discovered by using link metric in AOMDV by modifying the route discovery process. Here, the performance of BAT-AOMDV is shown in terms of Packet Delivery Ratio, End To End Delay and Routing Control Overheads. BAT-AOMDV show Routing Control Overhead, which is not constant at different number of nodes when compared to the other MANET routing protocols.
Adaptive Multi-metric (AM)-AOMDV is an improved and extended work of AOMDV (Ad-hoc on-demand multipath distance vector) based on multiple metrics like route metrics, a new local route update, and route maintenance algorithm. In this paper, Khimsara, Kambhatla K., Hwang J., Kumar S., & Matyjas J., (2010) made improvements in the route discovery process in terms of frequency and routing overhead during node mobility conditions. By using multiple metrics, they concluded that the AM-AOMDV technique improved the packet delivery ratio and decreased the end-to-end delay when compared to AOMDV.
Devi Manickavelu & Rhymed Uthariaraj Vaidyanathan, (2014) . gave a new route recovery algorithm in MANETs using a Particle Swarm Optimization (PSO), which is a swarm intelligence based technique. This method mainly predicts the lifetime of the link and node in the available bandwidth. The main aim of this method is to decrease the data loss and the control overhead.
Intelligent Routing Techniques for Mobile Ad-hoc Networks using Swarm Intelligence was proposed by CH. V. Raghavendran, G. Naga Satish, & P. Suresh, (2012). In this paper, the authors have done their study and research on a number of Swarm Intelligence (SI) based algorithms and bio-inspired routing protocols for MANETs. Here, they have given a brief discussion of some Ant Colony inspired algorithms like Hybrid Ant Colony Optimization Routing Algorithm for Mobile Ad Hoc Network (HOPNET), and Bee Colony inspired algorithm BeeAdHoc. Swarm Intelligence (SI) based algorithms may defeat the MANET routing problems like batter y, scalability, maintainability, survivability, flexibility and so on.
Mesut Gunes, Udo Sorges, & Imed Bouazizi (2002) gave a new ant-colony based routing algorithm for MANETs called ARA. Mobile ad-hoc network is a kind of temporary communication network and the main problem in these networks is to find the best path for communication. In this paper, the authors present a new on-demand routing algorithm for mobile, multi-hop ad hoc networks, which is a meta heuristic ant-colony algorithm based on the swarm intelligence technique. Swarm intelligence techniques are mainly used to solve the optimization problems. ARA protocol is very efficient, effective and scalable and the main aim of the ARA protocol is to minimize the routing overhead.
Data feature selection based on Artificial Bee Colony (ABC) algorithm was proposed by Mauricio Schiezaro & Helio Pedrini, (2013) . The ABC algorithm is a nature inspired swarm intelligence technique, which adapts the behavior of insect bees. In this paper, the authors present a feature selection method based on ABC algorithm. The ARA technique shows better results for the majority of the tested data sets compared to other algorithms.
Horst. F. Wedde, et al., (2005) projected a new protocol, Bee Ad-Hoc: An Energy Efficient Routing Algorithm for Mobile Ad-Hoc Networks Inspired by the Bee Behavior. BeeAdHoc is the latest routing algorithm for energy efficient routing in mobile ad hoc networks, which is inspired by the behavior of the insect bee. BeeAdHoc is the reactive routing algorithm and it consumes little energy for doing routing in MANETs. When compared to traditional mobile ad-hoc network routing algorithms, BeeAdHoc utilizes fewer control packets to do routing. BeeAdHoc shows improvement over the algorithms like DSR, DSDV, AODV in performance metrics in terms of packet delivery ratio, delay, and throughput.
BeeIP (Bee Inspired Protocol) is a new swarm intelligence based technique inspired by the behavior of honey bees. BeeIP uses the reactive method for route discovery and BCO (Bee Colony Optimization) technique to solve the difficult routing problem of finding an optimal route. The proposed method is designed in such a way that, it discover multiple paths and selects an optimal path for faster data transmission using the selection process inspired by the natural honey bees. Firstly, Alexandors Giagkos (2013) et al., has given an idea of the Bee Inspired routing Protocol. BeeIP design has some assumptions like, a source node is mapped with the honeybee hive, the destination node is mapped as the flower with honey and the intermediate nodes are mapped as the path in which the honey bees traversed from the hive to the flower. BeeIP also makes some assumptions during the route discovery process as the route request (RREQ) packet as scout packet, the route reply (RREP) packet as acknowledgment scout, sample packet as forager packet.
The processes in a BeeIP protocol are done in four different phases like scouting, foraging, path selection, and link failure. These phase are explained below:
In general BCO algorithms, the job of the scout bees is to find the food source and return back to the hive to place the collected food. In BeeIP, scouting process is used to discover multiple paths from source to the destination.
Whenever a source node needs to send a data to the destination, a route is required. BeeIP checks the previous information about the available paths. If no route exist, it starts route discovery by broadcasting the scout packet to its neighbors. The main responsibility of the scout packet is to set up neighboring nodes to each other. If the intermediate node is the desired destination, then an acknowledgment scout (ack-scout) packet is sent back to the source, knowing that the path is available. If the intermediate node is not the desired destination, then the process is repeated up to the destination is found. Here, destination node identifies multiple routes by sending ack-scout packets to each scout packet in the network. The destination node also gives a unique identification number to every path to differ from each other. By following this scouting process, multiple paths can be found.
In general, forager bees are those which collect the information of food from the scout bees. In BeeIP, foraging behavior is used to collect the quality of link and path.
When a finding of multiple paths is done successfully, there is a need to send the data. In BeeIP, data transformation is started by sending the forager packet to the destination node. After successful receiving of the forager packet by the destination node, an acknowledgment forager packet is generated (Ackforager packet). The (Ack-forager) packet stays at the destination like the real honey bee stays for few seconds at the flower, drinks honey, and collects information of sweetness of honey and then finally returns back in the same path from the flower to the hive. By imitating the same process, Ack- forager packet is send back to the source node. While it travels to the source node, it collects all the necessary information about the available paths and the intermediate links between the destination node and the source node. There is a necessity to estimate the link and path quality to select the optimal path. BeeIP computes the quality of a link and the path by considering the five different parameters, speed, energy, signal strength, queue, and delay.
To estimate the quality of link between two nodes a,b the below equation is used:
where, sig is the signal strength of an agent g,
qd is the queue delay,
txd is transaction delay, and
w is appropriate weights ( A. Giagkos, 2012).
Estimation of the quality of path from destination (d) to the source (s) can be done as the below equation:
where
Nn+1→ Nn is the two nodes with direction from the destination node to the source node.
BeeIP considers the below five parameters for the estimation of link quality and path quality :
The receiving node signal strength is considered and measured in units of dBms or Watts. A weak signal strength means that, a lengthy distance between the nodes that have an effect on the transmission in the network.
The sender node speed is considered and measured in units meters/second. Low speed will lead to transmission delays.
The remaining energy of a sender node is measured in Joules. The node with more remaining energy is to be considered for transmission.
Queue delay means the time a packet stays in the queue, before it is received by the receiver node. It is measured as bits/second.
The transmission delay between the sender and the receiver of a link is measured in seconds.
After the foragers collect and store the information of all the available paths, BeeIP follows different selection methods for selecting an optimal path. First, it computes the length of a packet and time of a packet weighting in the queue for every node between source and destination, and then it selects the best path based on the fastest path first. The fastest path selection is considered only at the source node. Second, at the intermediate nodes best path selection is done by considering the identification number and the direction of the available routes. The final selection process is done at the destination node by following the FIFO (first- in- fist- out) method.
Link and path breakages frequently occur in the network during the data transmission. Normally, all the traditional routing protocols follow the same process of choosing the alternate path, whenever a route failure arise. But BeeIP uses a different process for the detection of path failure, as if no packet returns back to the source in a particular time period. BeeIP considers it as path failure, and then it makes the capacity of the path to zero and unacknowledged. Here, a timer is set to a period of time for every data transmission, whenever the time is out. The timer removes the unwanted information of a particular path from its storage. This simple system guarantees the control overhead and improves the network performance.
In this paper, experimental analysis is done using NS-2.32, it is a commonly used popular Network Simulator tool for generating new network protocols and to show the comparison results for different protocols. NS2 mainly depends on two languages such as C++ and OTCL. This simulator uses C++ as a backend and OTCL (Object Oriented Tool Command) as a frontend, which is an interpreter.
As shown in the Table1, the simulation environment is set- 2 up as, the number of mobile nodes as 35, Area (m ) as 2000 x 1000, propagation model as Two-Way Random, the channel as a wireless channel, routing protocol used is AODV, the total simulation time is 150 seconds, and the range of the speed for different mobile nodes is between 1m/s to 25 m/s.
Table 1. Simulation Parameters used for the Experimental Analysis
In this paper, the simulation results are analyzed for the network performance metrics such as, packet delivery ratio, end to end delay, control overhead, and throughput.
The Packet Delivery Ratio (PDR) is calculated as the percentage of the number of packets received by the destination node and the total number of packets sent from the source node. The protocol should achieve a high packet delivery ratio to improve network performance.
Average End-to-end Delay is considered as the difference between the received time of the packet by the destination node and the sent time of the packet by the source node. The low delay for high data transformation and lesser end-to-end delay proves for an improved network performance.
Control overhead is defined as the total number of routing packets transmitted per total number of packets delivered. The routing protocol should exhibit a low control overhead for better network performance.
Throughput is considered as a total number of data packets received by the destination node in a duration of time. High throughput presents an improved network performance.
Figure 2 shows the packet delivery ratio comparison graph for BeeIP vs. BAT-AOMDV. As shown in Figure 2, BeeIP exhibits a minor higher packet delivery ratio than the other techniques as the function of different node speeds between 1 m/s to 25 m/s.
Figure 2. Comparison of Two protocols by Packet Delivery Ratio Vs Different Node Speeds
Figure 3 shows the Average end-to-end delay comparison graph for BeeIP vs. BAT-AOMDV. Figure 3 shows both the techniques performance results at the lower speed range of 1-5 m/s, but BeeIP exhibits a slightly lower Average end-to-end delay than the other techniques at a higher speed range.
Figure 3. Comparison of Two protocols by the Average End-to-End Delay Vs Different Node Speeds
Figure 4 shows the control overhead comparison result graph for BeeIP vs. BAT-AOMDV. As shown in the Figure 4, BeeIP performs a minor lower control overhead than the other technique as a function of different node speeds between 1 m/s to 25 m/s. But, the other technique also performs well at the higher number of packets and speed.
Figure 4. Comparison of Two Protocols by the Control overhead Vs Different Node Speeds
Figure 5 shows the throughput comparison graph for BeeIP and BAT-AOMDV. As shown in Figure 5, BeeIP exhibits a slightly higher throughput than the other techniques, when the speed range is 1-5 m/s. But, both the techniques present an equal performance at a higher range of speed and the lesser number of data.
Figure 5. Comparison of Two Protocols by Throughput Vs Different Node Speeds
This paper made a study on nature inspired swarm intelligence-based protocols for mobile ad-hoc networks, where, Swarm Intelligence (SI) means the study of the behavior and communication of simple nature agents, like ants, bees, bats, etc. SI based algorithms are mainly used to solve the complex optimization problems. Currently, there are many bio-inspired SI based algorithms, like Ant Colony Optimization (ACO), Bee Colony Optimization (BCO), and Bat Algorithm (BA) to solve the routing problems faced by the mobile ad-hoc networks. In this paper, a new routing protocol, BeeIP is proposed which is inspired from the natural honey bees behavior. The proposed protocol can find multiple paths for faster data transmission. Here, BeeIP is compared to the other SI approach BAT-AOMDV, which is inspired by the behavior of bats. The proposed approach shows low delay, high packet delivery ratio, and better throughput performance than the other SI based approach. BeeIP performs a balanced control overhead at various mobility conditions.