Routing Algorithm in MANET A Comparative Study

Routing Algorithm in MANET A Comparative Study

Ms. Sheetal K. Dhamal Computer dept. LTCOE Koparkhairane

Navi Mumbai, India

Ms. Smita A. Attarde Computer dept. LTCOE Koparkhairane

Navi Mumbai, India

Abstract Wireless Ad hoc network, a developing network technology consists of self-organized mobile nodes without fixed communication infrastructures. In a Mobile Adhoc Network, nodes move randomly, therefore the network may experience rapid and unpredictable changes. Routing paths in MANETs potentially contain multiple hops, and every node in MANET has the responsibility to act as a router to discover routes to other nodes. Because of the constant change in network topology routing in MANET has been a challenging task .The routing protocols of MANETs have to cope with frequent topology changes (due to high node mobility) while attempting to produce correct routing tables. The routing algorithm considered are classified into following categories proactive (table driven), reactive (on demand) , hybrid routing protocol and geographic routing protocol. In this paper, we are going to discuss and compare DSDV, DSR, ZRP , GPSR routing protocols. The comparison among the three routing protocols are based on the various protocol property parameters such as Route Discovery , Routing Overhead, Throughput etc.

KeywordsMobile Adhoc Network, ZRP, DSR, DSDV,GPSR, Route Discovery

This paper is divided into following sections: Section II describes the two major categories of routing protocols. Section III, IV, V, VI describes DSDV, DSR, ZRP, GPSR protocols respectively. Section VII presents the comparison of routing protocols discussed in previous sections based on theoretical analysis .Section VIII concludes this paper, and then referenced materials are listed.

Fig . A Mobile Adhoc Network

1. INTRODUCTION

   A Mobile Adhoc Network (MANET) is a system of wireless mobile nodes that dynamically self-organize in arbitrary and temporary network topologies. Manet's are infrastructure less and form a temporary network without the aid of any centralized administration. In Mobile Ad hoc Network, each mobile node has to perform not only the job of a host but also that of a router i.e forwarding the packets for other mobile nodes in the network that may not be within direct wireless transmission range of each other .If only two hosts, located closely together, are involved in the ad hoc network, no real routing protocol or routing decisions are necessary. In many ad hoc networks, though, two hosts that want to communicate may not be within wireless transmission range of each other, but could communicate if other hosts between them also participating in the ad hoc network are willing to forward packets for them.

   Routing protocol provides assistance to mobile nodes in discovering multi-hop paths and forwarding packages correctly and smoothly to destinations. Many different routing protocols have been proposed in the past decade by different authors and researchers. Since the performance of Ad hoc networks is largely dependent on the efficiency of routing protocol, the research that compares different protocols is necessary and valuable.

2. ROUTING PROTOCOL

1. Proactive Routing Protocols

   These protocols are called as proactive protocols since the routing information is maintained even before it is needed. Each and every node in the network maintains routing information to every other node in the network. Routes information is generally kept in the routing tables and is regularly updated with the changes in network topology. Thus, when there is a need for a route to a destination, such route information is available immediately. If the network topology changes too frequently, the cost of maintaining the network might be very high. Sometimes it may happen that the network activity is low, the information about actual topology might never be used. DSDV, OLSR are proactive routing protocol.

2. Reactive Routing Protocols

   These protocols are also called on-demand routing protocols since they dont maintain routing information or routing activity at the network nodes in case when there is no communication between the nodes. Routes are searched as and when required and the connection is established in order to transmit and receive the packet. AODV, DSR are reactive routing protocol.

3. Hybrid Routing Protocols

   Hybrid routing protocols are combination of both proactive and reactive protocols. e.g. ZRP

4. Geographic Routing Protocols

   It is also called georouting or position-based routing. It is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address. The idea of using position information for routing was first proposed in the 1980s in the area of packet radio networks [16] and interconnection networks.[17] Geographic routing requires that each node can determine its own location and that the source is aware of the location of the destination. With this information a message can be routed to the destination without knowledge of the network topology or a prior route discovery.

   III DESTINATION SEQUENCED DISTANCE VECTOR (DSDV) PROTOCOL

   The destination sequenced distance vector [13], [4], [6] routing protocol is a proactive protocol which is a modification of conventional Bellman-Ford routing algorithm [2]. In DSDV routing protocol tables have one more column that is of a sequence number. An odd number as a sequence number is used to specify the distances which are unreachable and it indicates , while even numbers are used by the destination to stamp route updates. If the information received by any node contains a recent sequence number or greater sequence number then the routing table entry for destination node is updated with the fresh entry of sequence number. If the two routes have same sequence number then the route with better metric is selected .If for a specified interval no update is received for any route then that route entry is deleted. In DSDV, advertisement of route is delayed for an average settling time, as updates for the same destination are received from different neighbors and out of the many updates the best route is chosen.

   The DSDV protocol requires that each mobile station in the network must constantly advertise to each of its neighbors, its own routing table. The routing updates can be sent by incremental update in which case only the changed entries since the last full dump are transmitted and not the entire routing table as in the case of full dump. Using the incremental dump extra traffic can be avoided. In DSDV when route is broken, the sequence no. of route is incremented and it is advertised with infinite metric.

   1. DYNAMIC SOURCE ROUTING (DSR)

      DSR [4] is a reactive routing protocol, this protocol is truly based on source routing whereby all the routing information is maintained (continually updated) at mobile nodes. It has two phases Route Discovery and Route Maintenance. Route Reply would only be generated if the message has reached the intended destination node (route record which is initially

      contained in Route Request would be inserted into the Route Reply).

      Route Discovery: When node L wants to send a packet to node W, but does not know a route to W, node L initiates a route discovery. Discovery is based on flooding the network with a RREQ packet, which includes the following fields: the sender address, the targetaddress, a unique number to identify the request, and a route record .Each node appends own identifier when forwarding RREQ[4] .See fig 2 and fig 3 Destination W on receiving the first RREQ, sends a Route Reply (RREP). RREP is sent on a route obtained by reversing the route appended to receive RREQ. RREP includes the route from L to W on which RREQ was received by node W. Node L on receiving RREP, caches the route included in the RREP

      .When node L sends a data packet to W, the entire route is included in the packet header that is why it is also called source routing.

      Route maintenance: When a node discovers that there is error in the route or link is broken Route Error (RERR) is generated and it sends this message upstream and if alternate route to destination is available in its cache the packet is forwarded via that route where as the source route on receiving RERR piggybacks this RERR on a new RREQ so that all the nodes are aware of the error in the route [12], [14].

      Fig 2 An example of routing propagation request in DSR

      Fig 3.Route reply in DSR

   2. ZONE ROUTING PROTOCOL

      In ZRP [14], [4], [15] every node has a zone which is defined to be the nodes within the distance of n hops (n is a configurable parameter). Within the zone, intrazone routing protocol [15], which is a proactive protocol, is adopted to maintain the local topology. When the route between different zones is needed, Interzone routing protocol [15], which is a reactive protocol, is used to find the path between the source and destination.

      when required and no extra traffic is generated in updating the tables.

      Zone for node 1 for n=2

      Fig 4 Zone in ZRP

      In DSDV as it is proactive routing protocol, it has to maintain routing table and regularly broadcasts the updates, as the mobility of nodes is high so throughput in case of DSDV is not stable but DSR has better throughput because DSR caches all the routes and can use them depending on the requirement. DSR costs little time and bandwidth to maintain the altered routes.

      In ZRP intra zone routing protocol is proactive, the route towards the node within the zone is available before its needed, thus the delay and overhead of route discovery is

   3. GREEDY PERIMETER STATELESS ROUTING

The Greedy Perimeter Stateless Routing in Wireless Networks is a routing protocol for mobile ad-hoc networks. It was developed by B. Karp. It uses a Greedy algorithm to do the routing and orbits around a perimeter. GPSR is a geo routing method, which means that data packages are not sent to a special receiver but to coordinates. The packages should be relayed to the node that's geographically closest to the coordinates. This assumes that every node knows its own position[18][19][20].

VII. COMPARISON

After reviewing the concept of wireless Ad hoc networks and three routing protocols, we would like to make a comparative discussion based on theoretical analysis of the simulations done by various authors using NS2 [3], [7], [8], [9], [10], [11].

Route cache is widely adopted in DSR [9]. For example, the intermediate nodes cache the route towards the destination and backward to the source. Moreover, because the data packet contains the source route in the header, the overhearing nodes are able to cache the route in its routing cache.

Route cache greatly reduces the routing overhead and can speed up route discovery [14] , intermediate node can give route reply packet if it has the route towards the destination in its routing cache and can also help in packet salvaging i.e. if it realizes that downstream link is broken when forwarding a data packet, it can forward the packet along the new route, if it has another source route in its routing cache towards the same destination.

DSR supports multi-paths, if the source receives a route error packet, it can use an alternative path stored in the routing cache, thus saving the overhead of route discovery.

Route cache has one disadvantage though, as a single route discovery may yield many routes to the destination due to intermediate nodes replying from local caches and thus the packet header size grows with route length due to source routing.

Overhead in DSDV is more when the network is large and it becomes hard to maintain the routing tables at every node. In DSR overhead is less as routes are discovered

avoided. The path between different zones is built on demand, which saves the overhead of periodic broadcast of topology information throughout the MANET as in the case of proactive routing protocols.

Greedy forwarding tries to bring the message closer to the destination in each step using only local information. Thus, each node forwards the message to the neighbor that is most suitable from a local point of view. The most suitable neighbor can be the one who minimizes the distance to the destination in each step (Greedy)[21]. Greedy forwarding can lead into a dead end, where there is no neighbor closer to the destination.

VIII CONCLUSION

The study reveals that, DSDV routing protocol consumes more bandwidth, because of the frequent broadcasting of routing updates. While the DSR is better than DSDV as they dont maintain any routing tables at nodes which results in less overhead and more bandwidth. The route discovery mechanism requires packets to obtain required routes initially so in the beginning the average delay time of DSR is more than that of DSDV or any other table driven protocol. It can be assumed that DSDV routing protocols works better for smaller networks but not for larger networks. The goal of GPSR protocols is to deliver data packets to a group of nodes that are inside a specified geographical area. In the networks subject to frequent changes or requiring high throughput ZRP and DSR turn out to be more efficient.

REFERENCES

1. David B. Johnson,David A. Maltz,Dynamic Source Routingin

   Ad Hoc Wireless Networks, Carnegie Mellon University, Pittsburgh

2. Thomas H.Cormen,Charles E.Leiserson,Ronald L. Rivest, Clifford Stein, Introduction To Algorithms,3rd edition ,2011

3. Qian Feng, Zhongmin Cai, Jin Yang, Xunchao Hu, A Performance Comparison of the Ad Hoc Network Protocols, Second International Workshop on Computer Science and Engineering,2009,china

4. Mohammad Ilyas,THE HANDBOOK OF AD HOC WIRELESS NETWORKS,CRC Press Publisher,2003

5. Harminder S. Bindra, Sunil K. Maakar, A. L. Sangal , Performance Evaluation of Two Reactive Routing Protocols of MANET using Group Mobility Model, IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 10, May 2010

6. Krishna Gorantala, Routing Protocols in Mobile Ad-hoc Networks, Masters Thesis in Computing Science,

   UMEA University,SWEDEN, June 15, 2006

7. G.Vijaya Kumar , Y.Vasudeva Reddyr, Dr.M.Nagendra,Current Research Work on Routing Protocols for MANET: A Literature

   Survey, (IJCSE) International Journal on Computer Science and EngineeringVol. 02, No. 03, 706-713, 2010

8. I.Vijaya, Pinak Bhusan Mishra, Amulya Ratna Dash, Amiya Kumar Rath, Influence of Routing Protocols in Performance of Wireless Mobile Adhoc Network Second International Conference on Emerging Applications of Information Technology,2011

9. Basu Dev Shivahare,Charu Wahi , Shalini Shivhare, Comparison Of Proactive And Reactive Routing Protocols In Mobile Adhoc Network Using Routing Protocol Property, International Journal of Emerging Technology and Advanced Engineering, ISSN 2250-2459, Volume 2,

   Issue 3, March 2012

10. Drs. Baruch Awerbuch & Amitabh Mishra,Advanced Topics in Wireless Networks,Lecture Notes, Johns Hopkins University,2008

11. Hui Xu, Xianren Wu, Hamid R. Sadjadpour, and J. J. Garcia-Luna- Aceves,A Unified Analysis of Routing Protocols in MANETs, IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 58, NO. 3,

    MARCH 2010

12. Wireless adhoc networks , Available : [online] http:/en.wikipedia.org/wiki/Wireless_ad-hoc_network

13. Ashutosh Yadav,Performance Analysis of Various Routing Protocols in Ad-hoc Network-A Survey, International Journal of Emerging Technology and Advanced Engineering (ISSN 2250-2459, Volume 2, Issue 1, January 2012)

14. Hongbo Zhou, A Survey on Routing Protocols in MANETs, Michigan State University, Mar 28, 2003

15. Available :[online] , http://www.netmeister.org/misc/zrp/

16. Takagi, H.; Kleinrock, L. (March 1984). "Optimal transmission ranges for randomly distributed packet radio terminals". IEEE Transactions on Communications 32 (3): 246257. doi:10.1109/TCOM.1984.1096061.

17. Finn, Gregory G. (March 1987). "Routing and Addressing Problems in Large Metropolitan-Scale Internetworks" (PDF). University of Southern California, ISI/RR-87-180.

18. B.Karp: Challenges in Geographic Routing: Sparse Networks, Obstacles, and Traffic Provisioning. in DIMACS Workshop on Pervasive Networking, Piscataway, NJ, May 2001

19. B.Karp: Geographic Routing for Wireless Networks. Ph.D. Dissertation,

    Harvard University, Cambridge, MA, October 2000

20. B.Karp, H.T.Kung: Greedy Perimeter Stateless Routing for Wireless Networks. In Proceedings of the Sixth Annual ACM/IEEE

    International Conference on Mobile Computing and Networking (MobiCom 2000), Boston, MA, August 2000, pp. 243-254

21. Stojmenovic, Ivan; Lin, Xu (2001). "Loop-free hybrid single- path/flooding routing algorithms with guaranteed delivery for wireless networks". IEEE Transactions on Parallel and Distributed Systems 12 (10): 10231032. doi:10.1109/71.963415.