Study and Comparison of Mobile Ad-Hoc Networks Using Ant Colony Optimization

Study and Comparison of Mobile Ad-Hoc Networks Using Ant Colony Optimization

1 Neha Ujala Tirkey, 2 Navendu Nitin , 3 Neelesh Agrawal , 4 Arvind Kumar Jaiswal

1 M. Tech student, 2&3 Assistant Professor, Department of ECE, 4 HOD, Department of ECE SHIATS, Allahabad U.P-211007,

Abstract

Mobile Ad-hoc Network (MANET) is a dynamic wireless network with or without fixed infrastructure. Nodes move freely and arrange themselves randomly. Since MANETs are highly dynamic in nature, either of multicasting or broadcasting strategies can be adopted at different scenarios. Using Ant colony optimization, the performance of mobile ad-hoc networks has improved in many ways. In this paper Ad-hoc On-Demand Vector and Mobile Ad-hoc Network using Hybrid Swarm Intelligence protocols have been taken to compare their performance. By the simulation results we will see that Mobile Ad-hoc Network using Hybrid Swarm Intelligence gives better performance with lower delay and lower overhead.

1. Introduction

   Wireless communication technology is increasing daily, with such growth sooner or later it would not be practical or simply physically possible to have a fixed architecture for this kind of network. Ad-hoc wireless network must be capable to self-organize and self-configure due to the fact that the mobile

   structure is changing all the time. Mobile hosts have a limited range and sending the message to another host, which is not in the senders host transmission range, must be forwarded through the network using other hosts which will be operated as routers for delivering the message throughout the network. The mobile host must use broadcast for sending messages and should be in promiscuous mode for accepting any messages that it receives. In the ad-hoc network there can be unidirectional hosts,that can transmit only to the one direction, so that the communication is not bi-directional as in the usual communication systems.

2. Mobile Ad-hoc Network (MANET)

   A Mobile Ad hoc Network (MANET)[4] is a dynamic wireless network with or without fixed infrastructure. Nodes may move freely and arrange themselves randomly. The contacts between nodes in the network do not occur very frequently. As a result, the network graph is rarely, if ever, connected and message delivery required a mechanism to deal with this environment. Routing in MANET using the shortest-path metric is not a sufficient condition to construct high-quality paths, because minimum hop

   count routing often chooses routes that have significantly less capacity than the best paths that exist in the network. Most of the existing MANET protocols optimize hop count as building a route selection.

   In areas in which there is little or no communication infrastructure or the existing infrastructure is expensive or inconvenient to use, wireless mobile users may still be able to communicate through the ad hoc network. In such a network, each mobile node operates not only as a host but also as a router, forwarding packets for other mobile nodes in the network that may not be within direct wireless transmission range of each other. Each node participates in an ad hoc routing protocol that allows it to discover multi-hop paths through the network to any other node.

   Mobile ad-hoc networks inherit the common problems of wireless networking in general, and add their own constraints specific to Ad-hoc routing. Some of the notable characteristics, complexities and design constraints of MANETs are presented below:

   • Wireless medium : In an ad hoc environment, nodes communicate wirelessly and share the same media (radio, infrared etc).The wireless medium has neither absolute, nor readily observable boundaries outside of which the stations are unable to receive network frames. Thus the channel is unprotected from outside signals and hence it is significantly less reliable than wired media.

   • Autonomous and infrastructure less : MANET does not depend on any established infrastructure or centralized administration. Each node operates in distributed peer-to-peer mode,

     acts as an independent router and generates independent data. Network management has to be distributed across different nodes, which brings added difficulty in fault detection and management.

   • Dynamic and changing network topology : In Mobile Ad hoc networks, because nodes can move arbitrarily, the network topology, which is typically multi-hop, can change frequently and unpredictably, resulting in route changes, frequent network partitions, and possibly packet losses.

   • Limited availability of resources : Because batteries carried by each mobile node have limited power supply, processing power is limited, which in turn limits services and applications that can be supported by each node. This becomes a bigger issue in MANET because, since each node is acting as both an end system and a router at the same time, additional energy is required to forward packets.

   Most popular routing in Ad-hoc networks is On- demand routing. Ondemand routing protocols build routes only when a node needs to send data packets to a destination. These are also known as Reactive Routing Protocols. Most popular on-demand routing protocol is :

3. Ad-hoc On-Demand Vector (AODV)

   AODV[5,6] is capable of unicast, multicast and broadcast routing. It is an on demand algorithm, meaning that it builds routes between nodes only as desired by source nodes. It maintains these routes as long as they are needed by the sources. Additionally, AODV forms trees which connect multicast group members[9]. The trees are composed of the group members and the nodes needed to connect the members. AODV uses sequence numbers to ensure

   the freshness of routes. It is loop-free, self-starting, and scales to large numbers of mobile nodes.

   AODV builds routes using a route request / route reply query cycle. When a source node desires a route to a destination for which it does not already have a route, it broadcasts a route request (RREQ) packet across the network. Nodes receiving this packet update their information for the source node and set up backwards pointers to the source node in the route tables. In addition to the source node's IP address, current sequence number, and broadcast ID, the RREQ also contains the most recent sequence number for the destination of which the source node is aware. A node receiving the RREQ may send a route reply (RREP) if it is either the destination or if it has a route to the destination with corresponding sequence number greater than or equal to that contained in the RREQ. If this is the case, it unicasts a RREP back to the source. Otherwise, it rebroadcasts the RREQ. Nodes keep track of the RREQ's source IP address and broadcast ID. If they receive a RREQ which they have already processed, they discard the RREQ and do not forward it.

   As the RREP propagates back to the source, nodes set up forward pointers to the destination. Once the source node receives the RREP, it may begin to forward data packets to the destination. If the source later receives a RREP containing a greater sequence number or contains the same sequence number with a smaller hop count, it may update its routing information for that destination and begin using the better route. As long as the route remains active, it will continue to be maintained. A route is considered active as long as there are data packets periodically travelling from the source to the destination along that path. Once the source stops sending data packets, the links will time out and eventuall be deleted from

   the intermediate node routing tables. If a link break occurs while the route is active, the node upstream of the break propagates a route error (RERR) message to the source node to inform it of the now unreachable destination(s). After receiving the RERR, if the source node still desires the route, it can reinitiate route discovery.

4. Optimized AODV

   In the optimized protocol[5], the interactions of ant like packets are used to proactively maintain the un- expired route connectivity following the stigmergy paradigm. The artificial ants (ant-like packets) are divided into two classes: forward ant and backward ant. The forward ants traverse the network to collect network traffic information, which mimics the ant in the searching mode and the backward ants utilize this information to update routing tables and other data structures, which mimics the ant in the carry mode. For simplicity, it is assumed that all of the forward ants will eventually find the destination and do not consider the ants in return mode. At the same time as using the proactive process to maintain the unexpired route connectivity, the reactive features of the original AODV protocol are retained for the new route discovery and route error handling.

5. Mobile Ad-hoc Network using Hybrid Swarm Intelligence (MANHSI) Protocol

   MANHSI[7] is an on-demand multicast routing protocol that creates a multicast connection among group members by determining a set of intermediate nodes that serve as forwarding nodes. This set, called a forwarding set, is shared among all the senders of the group. The protocol exploits a core-based

   technique where each member joins the group via the core node to establish a connection with the other group members. We adopt the swarm intelligence metaphor to allow nodes to learn a better multicast connection that yields a lower (total) forwarding cost. The exploring and learning mechanism enables MANHSI to learn a better forwarding set for each group, depending on how node cost is defined, as well as differentiates MANHSI from other existing ad hoc multicast routing protocols. Not that, by doing so, MANHSI attempts to evolve multicast connectivity into states that yield lower cost. It, however, does not guarantee that minimum-cost connectivity can be achieved.

6. Multicasting

   Multicast is the delivery of a message or information to a group of destination computed simultaneously in a single transmission from the source. Use of multicasting within a network has many benefits. Multicasting[9,11] offers optimized network performance, support to distributed application, resource economy, scalability and more network availability.

7. Results and Discussion

The investigation has been carried out by considering two different scenarios:

1. End-to end delay

2. Overhead

   1. End-to end Delay

      The quality of service provided by the protocols can be compared with the average Delay. End-to-end delay is the average time taken by a data packet to

      reach to destination in seconds. Figure 7.1 shows the effect of Delay with the variations in the pause time. The End-to end delay decreases with reduced mobility.

      Figure7.1: Pause Time vs Delay

      Figure shows that AODV has the largest delay with high mobility due to its single path nature and inefficient manner to handle route failure. Optimized- AODV performs better than AODV and gives lower delay than AODV because instead of buffering data packets for a new route discovery, OAODV forwards the data packets through alternative routes. And in case of MANHSI, it does not always rely on the shortest paths between the core and the members to establish group connectivity, instead it creates a multicast connection among group members by determining a set of intermediate nodes that serves as forwarding nodes. Thus MANHSI incorporates a mobility-adaptive mechanism that allows the protocol to remain effective with the lowest delay than the other protocols even as mobility increases.

   2. Overhead

The control overhead is defined as the total number of routing control packets received. Figure 7.2 shows the effect of overhead with the variations of pause time.

Figure7.2 : Pause Time vs Overhead

The overhead decreases with the high mobility. In case of high mobility, MANHSI gives the least overhead compared to AODV and OAODV. With high mobility, route failure occurs more frequently, and AODV cause flooding of large number of route finding packets, OAODV shows lesser overhead but MANHSI has the least overhead [8] as mobility of nodes does not affect its performance. Even in the case of less mobility, it remains stable. The simulation results are carried out by Network Simulator 2 (NS2) [10].

Conclusion

During the study using Ant Colony Optimization [1,2], MANHSI shows better performance in the case of delay as well as overhead. MANHSI gives the lowest delay of all because during the path finding process, it does not always rely on the shortest paths between the core and the members to establish group connectivity, instead it creates a multicast connection

among group members by determining a set of intermediate nodes that serves as forwarding nodes. During the study of overhead, it was found that MANHSI performs better than AODV and OAODV as it incorporates a mobility-adaptive mechanism that allows the protocol to remain effective as mobility increases. The simulation results have shown that MANHSI performs both effectively and efficiently in static or low-mobility environments, yet still effectively in highly dynamic environments.

References

1. M. Heissenb¨uttel and T. Braun, Ants-based routing in large scale mobile ad-hoc networks Institute of Computer Science and Applied Mathematics, University of Berne, Tech. Rep. CH- 3012, 2003.

2. M.Gunes¸ U. Sorges, and I. Bouazisi, Ara – the ant-colony based routing algorithm for manets, in Proceedings of the ICPP Workshop on Ad Hoc Networks. IEEE Computer Society Press, 2002,pp. 7985.

3. Siba K.Udgata, Dharmendra K Singh and Lalan Kumar, Performance Evaluation of ACO Based on Demand Routing Algorithm for Mobile Ad – Hoc Networks, International Journal of Engineering Science and Technology (IJEST) Vol. 3 No. 3 Mar 2011

4. Mamoun Hussien Mamoun, A Novel Routing Algorithm for MANET, International Journal of Electrical and Computer Sciences Vol.10, No.02

5. C. E. Perkins and E. Royer, Ad-hoc on-demand distance vector routing, in the Second IEEE

   Workshop on Mobile Computing systems and Applications, 1999.

6. Aditya Goel and Ajaii Sharma, Performance Analysis of Mobile Ad-hoc Network Using AODV protocol, International Journal of Computer Science and Security(IJCSS), Volume(3): Issue (5)

7. Zeyad M. Alfawaer, GuiWei Hua, and Noraziah Ahmed, "A Novel Multicast Routing Protocol for Mobile Ad Hoc Networks, "American Journal of Applied Sciences 4 (5): 333-338, 2007, ISSN 1546- 9239.

8. Pariza Kamboj, Ashok.K.Sharma, Energy Efficient Multicast Routing Protocol for MANET with Minimum Overhead (EEMPMO), International Journal of Computer Applications, Volume 8 No.7,

   October 2010

9. E. Royer and C Perkins, Multicast Operation of the Ad-Hoc On-Demand Distance Vector Routing Protocol, In Proceedings Of the 5th Iinternational Conference on Mobile Computing and Networking (MobiCom99), pp 207-208, Seattle, WA, USA, August 1999.

10. The NS-2 Manual, the VINT Project

11. J.S.Baras and H.Mehta,A probabilistic emergent routing algorithm for mobile ad hoc networks, in Proceedings of Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2003.