Topology vs Position based Routing Protocols in Mobile Ad hoc Networks: A Survey

Topology vs Position based Routing Protocols in Mobile Ad hoc Networks: A Survey

Topology vs Position based Routing Protocols in Mobile Ad hoc Networks: A Survey

Sonam Jain

Pursuing Master of Engineering in Co mputer Sc ience & Engineering

fro m Shri Ra m Institute of Technology

Jabalpur, India

Sandeep Sahu

(M Tech, IIT Guwahati) Assistant Professor,

Shri Ra m Institute of Technology

Jabalpur, India

AbstractMobile Ad hoc networks perform multi-hop communication in an environment without a dedicated fixed infrastructure, with mobile nodes and changing network topology. In the last 15 years, the wireless networking community designed hundreds of new routing protocols targeting the various scenarios of this design space. The objective of this paper is to create taxonomy of the mobile ad hoc routing protocols, and to survey and compare representative examples for the topology based and position based routing protocols.

Keywords-topology based routing protocols;position based routing protocols;Mobile ad hoc Networks; styling; insert (key words)

1. INT RODUCTION

   WLAN [1] based on the IEEE 802.11a, IEEE 802.11b, and IEEE 802.11g and IEEE 802.11n standards became one of the most Omni present ways of networking with mobile nodes. Most of these networks, however, a re deployed in the configuration which can be called wired everywhere, e xcept the first hop. If the aim of the user of the mobile co mputer is to connect to a web server located around the world, then the best strategy is to escape as quickly as possible fro m the challenges of wire less domain and enter the reliability of fiber optical networks. In such networks, all the nodes connect to an access point which usually has a wired connection to the Internet. In th is scenario the nodes connected to the same WLAN co mmun icate with each other only indirectly via access point. There are, however, many important applicat ions where this model is not applicable. First, even if the goal is Internet access, the access point might not be able to cover all the relevant mobile nodes due to limitations in transmission range, cost or access rights constraints. Another case is when Internet access is of secondary importance, the main application being to co mmunicate locally a mong a g roup of mobile nodes. These scenarios can be serviced only if we allo w some (possibly all) routing hops to be performed in the wireless domain. Such networks can be set up in any location in an ad hoc manner, without the need of an e xisting fixed infrastructure. So these networks are known as ad hoc wire less networks [2], other proposed names being infrastructure less

   wireless networks, instant infrastructure [3] and mobile-mesh networking [4].One of the major technological challenges of such networks is that they require new types of routing protocols. As opposed to the wired infrastructure, because in ad hoc networks there are no dedicated router nodes: so the task of routing needs to be performed by the user nodes, which can be mobile, unreliable and have limited battery power and other resources. The goal of this paper is to survey the collection of technologies which have been proposed for routing in mobile ad hoc networks so far. This way, we hope to provide the student and researcher with a more c lear description of the state of the art routing technologies developed so far. We hope that this systematic approach will help the researcher understand the open challenges in the field of mobile ad hoc networks , as we ll as those which have been satisfactorily solved. As early ad hoc routing protocols have been classified into on topology based routing protocols (demand and table-driven protocols ) and position based routing protocols .

   Rest of the paper is organized as follows: Section 2 introduces about the applications of the mobile ad hoc networks (MANETs) in various fields. Section 3 introduces Ad hoc routing protocols .

2. APPLICATION OF MANETS

   Mobile Ad hoc networks, a lso defined in the broad sense by of the term as wireless networking in the absence of a wired fixed infrastructure, have a wide range of potential applications. So me of these applications have been already identified in early ad hoc literature [2]. In th is section we briefly survey some applicat ion areas of interest for ad hoc networks. There are some applications where ad hoc networks are the only possible solution, for instance, networking in areas where no fixed infrastructure is available . Beyond these applications, however, there is a much larger fie ld of various potential applicat ions where ad hoc networks compete with other possible technical solutions. Finally, there are application areas where mobile ad hoc networks can be used as part of a comb ination of technologies are as follows.

3. AD HOC ROUTING PROTOCOLS AND COMPARISONS

   So far researchers have proposed a wide range of routing protocols for mobile ad hoc networks. But the basic goals [1] of these protocols are the same:

   Maximizing throughput. Minimizing pack et loss Minimizing control overhead Minimizing energy usage.

   But however, the re lative prio rit ies of these criteria in the routing protocol design for ad hoc networks differ a mong application areas of MANETs. In the reminder of this paper, we organize the discussed routing protocols into three categories based on their underlying architectural fra mework as follows (a lso shown in Fig. 1).

   1. Source-initiated (Reactive or on-demand) (Section 3.1).

   2. Table-driven (Pro-active) (Section 3.2).

   3. Location-aware (Geographical or Position based) (Section 3.2).

   Fig. 1: Categories of ad hoc routing protocols

   Source-in itiated routing represents a c lass of routing protocols where the route is created only when the source requests a route to a destination. The route is created through a route discovery procedure which involves flooding the network with route request packets are flooded to starting with the immed iate neighbors of the source. Once a route is fo rmed or mu ltip le routes are obtained to the destination, the route discovery process comes to an end. A route ma intenance procedure maintains the continuity of the route for the time span it is needed by the source. Some of the e xa mples of the source-in itiated routing protocols are as follows:

   ma jor role in the route selection process in this protocol.

   resulting in rebuilding of an a lternate routes much sooner.

   predetermined probability. In contrast to classical gossip algorith ms which forward each message with the same probability, this work considers the probability dependent on node locations and distances between each other.

   incorporated into the routing metrics to help choose the lin k with the highest availability in the route.

   (b) it can suffer fro m te mpora ry loops, de facto partit ion and count-to-infinity. The LSR approach is an attempt to overcome these proble ms by using the informat ion already needed in route requests to establish and ma intain loop-free routes and allows other nodes than the destination to initiate route replies.

   1. Table driven also called Pro-active routing protocols always ma intain up-to-date informat ion of routes fro m each node to every other node, means that a source node to every possible node in the network. Routing informat ion is stored in the routing table of each mobile node and route update packets are propagated throughout the network to keep the routing in formatio as update as possible. Different protocols keep trac k of d iffe rent routing state informat ion; however, all of the m have the common goal of reducing route maintenance overhead as much as possible. These types of protocols are not suitable for h ighly dyna mic networks due to the e xtra control overhead generated to keep the routing tables consistent and fresh for each node in the network.

      which the link state information is generated. The next hop table contains a list of next hop neighbors to forward the packets while the distance table ma intains the shortest distance to and from the node to various destinations. A weight function computes the distance of a link wh ich may be replaced by other QoS routing parameter.

      table. If a pac ket on the other hand is destined to a farther node, it is first routed to its nearest landmark node.

      the next with local proactive route discovery within a zone and reactive co mmunication between zones. The algorith m borro ws features from ZRP and DSR protocols and combines it with ACO based schemes.

   2. Location-awa re routing schemes in mobile ad hoc networks assume that the individual nodes are aware of the locations of all the nodes within the network. The best and easiest technique is the use of the Global Positioning System (GPS) to determine e xact coordinates of these nodes in any geographical location. This location information is then utilized by the routing protocol to determine the routes.

      increase effic iency, feedback is suggested as a mobility metric assisting ad hoc network protocols adapt to the current network scenario [71].

      [76]: Giruka and Singhal propose a geographic path routing protocol which does not depend on a location

      service to find the position of the destination. OGPR is stateless and uses greedy forwarding; react ive route discovery and source based routing. It is a hybrid protocol incorporating the effective techniques of other well known routing protocols for MANETs. OGPR constructs geographic paths to route packets between a source and a destination node.

      the next hop node is actually farther than the destination. This leads to looping within the network.

In this paper, we introduced taxonomy of ad hoc routing protocols. We have divided the ad hoc routing protocols into three categories:

1. source-initiated (reactive or on-demand)

2. table-driven (pro-active)

3. location-aware (geographical)

For each of these classes, we revie wed several representative protocols. While different classes of protocol operate under diffe rent scenarios, they usually share the common goal to reduce control packet overhead, ma ximize throughput, and minimize the end-to-end delay. The ma in d iffe rentiating factor between the protocols is the ways of finding and/or ma intaining the routes between sourcedestination pairs.

The develop ment of the ad hoc routing protocols over the last 15 years is an e xa mple of one of the most systematic e xplorations of a design space in the history of computer science. Although, clearly, newer protocols have built upon the earlier ones, we cannot identify a single best protocol. Almost all the protocols we discussed in this paper have their own sweet spot deployment scenarios and performance met ric combinations where they outperform their co mpetitors.

Fro m the point of view of the practitioner, this creates a serious problem. To deploy an ad hoc network with an optimal performance, it requires a very ca reful analysis of the scenario and its require ments, and the appropriate choice of the routing protocol from the dozens applicable in the context. We hope that the taxonomy presented in this paper will be a helpful instrument for making this decision.

1. Azzedine Boukerche, Begumhan Turgut, Nevin Aydin, M ohammad Z. Ahmad, Ladislau Bölöni, Damla Turgut, Routing protocols in ad hoc networks: A survey,ELSEVIER M ay 2011.

2. C. Perkins (Ed.), Ad hoc Networking, Addison Wesley, 2001.

3. R. Bagrodia, M . Gerla, L. Kleinrock, J. Short, T. Tsai, A hierarchical simulation environment for mobile wireless networks, Technical report, Dept. of Computer Science, University of California at Los Angeles, 1996.

4. J. Al-Karaki, A. Kamal, Efficient virtual-backbone routing in mobile ad hoc networks, Computer Networks 52 (2) (2008) 327350.

5. D.B. Johnson, D.A. M altz, J. Broch, DSR: the dynamic source routing protocol for multi-hop wireless ad hoc networks, in:

   C.E. Perkins (Ed.), Ad Hoc Networking, Addison-Wesley, 2001, pp. 139172 (Chapter 5).

6. C. Perkins, E. Royer, Ad hoc On-demand Distance Vector Routing, in: Proceedings of the Second IEEE Workshop on M obile Computing Systems and Applications, 1999, pp. 99 100.

7. C. Perkins, P. Bhagwat, Highly dynamic destination-sequenced distance-vector routing (DSD V) for mobile computers, in: ACM SIGCOMM , AugustSeptember 1994, pp. 234244.

8. V.D. Park, M .S. Corson, A highly adaptive distributed routing algorithm for mobile wireless networks, in: Proceedings of INFOCOM, April 1997, pp. 14051413.

9. Temporally ordered routing algorithm. Available from web page <http://wiki.uni.lu/secan-lab/temporally ordered+routing+ algorithm.html>.

10. C.-K. Toh, Associativity -based routing for ad-hoc mobile networks,Wireless Personal Communications Journal 4 (2) (1997) 103139.Special Issue on M obile Networking and Computing Systems.

11. R. Dube, C.D. Rais, K.Y. Wang, S.K. Tripathi, Signal stability – based adaptive routing (SSA) for ad hoc mobile networks, IEEE Personal Communications M agazine (1997) 3645.

12. T. Goff, N.B. Abu-Ghazaleh, D.S. Phatak, R. Kahvecioglu, Preemptive routing in ad hoc networks, Journal of Parallel Distributed Computing 63 (2) (2003) 123140.

13. Q. Xue, A. Ganz, Ad hoc QoS on-demand routing (AQOR) in mobile ad hoc networks, Journal of Parallel Distributed Computing 63 (2) (2003) 154165.

14. M . Gunes, U. Sorges, I. Bouazizi, Ara-the ant-colony based routing algorithms for manets, in: Proceedings of IEEE ICPP Workshop on Ad Hoc Networks (IWAHN), August 2002, pp. 7985.

15. J. Raju, J. Garcia-Luna-Aceves, A new approach to on-demand loopfree multipath routing, in: Proceedings of the Eight IEEE International Conference on Computer Communications and Networks (IC3N), April 1999, pp. 522527.

16. W. Sum, M . Gerla, IPv6 flow handoff in ad-hoc wireless networks using mobility prediction, in: Proceedings of IEEE GLOBECOM , December 1999, pp. 271275.

17. M . Gong, S. M idkiff, S. M ao, On-demand routing and channel assignment in multi-channel mobile ad hoc networks, Ad Hoc Networks 7 (1) (2009) 6378.

18. J. Boice, J. Garcia-Luna-Aceves, K. Obraczka, Combining on- demand and opportunistic routing for intermittently connected networks,Ad Hoc Networks 7 (1) (2009) 201218.

19. L. Rosati, M . Berioli, G. Reali, On ant routing algorithms in ad hoc networks with critical connectivity, Ad Hoc Networks 6 (6) (2008) 827859.

20. M . Naserian, K. Tepe, Game theoretic approach in routing protocol for wireless ad hoc networks, Ad Hoc Networks 7 (3) (2009) 569578.

21. Z. Cheng, W. Heinzelman, Discovering long lifetime routes in mobile ad hoc networks, Ad Hoc Networks 6 (5) (2008) 661 674.

22. R. Beraldi, The polarized gossip protocol for path discovery inmanets, Ad Hoc Networks 6 (1) (2008) 7991.

23. J. Al-Karaki, A. Kamal, Efficient virtual-backbone routing in mobile ad hoc networks, Computer Networks 52 (2) (2008) 327350.

24. G. Ivascu, S. Pierre, A. Quintero, QoS routing with traffic distribution in mobile ad hoc networks, Computer Communications 32 (2) (2009) 305316.

25. J.-D. Abdulai, M . Ould-Khaoua, L. M ackenzie, Adjusted probabilistic route discovery in mobile ad hoc networks, Computers and Electrical Enineering 35 (1) (2009) 168182.

26. W. Lai, S.-Y. Hsiao, Y.-C. Lin, Adaptive backup routing for ad-hoc networks, Computer Communications 30 (2) (2007) 453464.

27. C. Yu, T.-K. Wu, R. Cheng, A low overhead dynamic route repairing mechanism for mobile ad hoc networks, Computer Communications 30 (5) (2007) 11521163.

28. M . Yu, A. M alvankar, W. Su, S. Foo, A link availability -based QoSaware routing protocol for mobile ad hoc sensor networks,Computer Communications 30 (18) (2007) 3823 3831.

29. H. Rangarajan, J. Garcia-Luna-Aceves, Efficient use of route requests for loop -free on-demand routing in ad hoc networks, Computer Networks 51 (6) (2007) 15151529.

30. N.-C. Wang, Y.-F. Huang, J.-C. Chen, A stable weight-based ondemand routing protocol for mobile ad hoc networks, Information Sciences 177 (24) (2007) 55225537.

31. J. Eisbrener, G. M urphy, D. Eade, C. Pinnow, K. Begum, S. Park, S.-M .Yoo, J.-H. Youn, Recycled path routing in mobile ad hoc networks, Computer Communications 29 (9) (2006) 15521560.

32. C. Ahn, Gathering-based routing protocol in mobile ad hoc networks, Computer Communications 30 (1) (2006) 202206.

33. C. Sengul, R. Kravets, Bypass routing: an on-demand local recovery protocol for ad hoc networks, Ad Hoc Networks 4 (3) (2006) 380397.

34. R. Beraldi, L. Querzoni, R. Baldoni, A hint -based probabilistic protocol for unicast communications in M ANETs, Ad Hoc Networks 4 (5) (2006) 547566.

35. J. Garcia-Luna-Aceves, M . M osko, C. Perkins, A new approach to ondemand loop -free routing in networks using sequence numbers,Computer Networks 50 (10) (2006) 1599 1615.

36. Y.-H. Wang, C.-F. Chao, Dynamic backup routes routing protocol for mobile ad hoc networks, Information Sciences 176 (2) (2006) 161185.

37. J.-S. Liu, C.-H.R. Lin, RBR: refinement-based route maintenance protocol in wireless ad hoc networks, Computer Communications 28 (8) (2005) 908920.

38. C. Perkins, P. Bhagwat, Highly dynamic destination-sequenced distance-vector routing (DSD V) for mobile computers, in: ACM SIGCOMM , AugustSeptember 1994, pp. 234244.

39. A. Boukerche, S.K. Das, A. Fabbri, Analysis of a randomized congestion control scheme with DSDV routing in ad hoc wireless networks, Journal of Parallel and Distributed Computing 61 (7) (2001) 967995.

40. T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum, L. Viennot, Optimized link state routing protocol for ad hoc networks, in: Proceedings of IEEE INMIC, Dece mber 2001, pp. 6268.

41. L. Villasenor-Gonza lez, Y. Ge, L. La mont, HOLSR: a hierarchica l proactive routing mechanism for mobile ad hoc networks, IEEE Co mmunicat ions Magazine 43 (7) (2005) 118125.

42. W.L.C. Ch iang, H. Wu and M. Gerla, Routing in clustered multihop, mobile wire less networks, in: Proceedings of IEEE SICON, April 1997, pp. 197211.

43. S. Murthy, J.J. Ga rcia -Luna-Aceves, An effic ient routing protocol for wireless networks, MONET 1 (2) (1996) 183197.

44. T.-W. Chen, M . Gerla, Global state routing: a new routing scheme for ad-hoc wireless networks, in: Proceedings of IEEE ICC, vol. 1,June 1998, pp. 171175.

45. J.J. Garc ia-Luna-Aceves, M. Spohn, Source-tree routing in wire lessnetworks, in: Proceedings of IEEE ICNP, OctoberNovember 1999,pp. 273 282.

46. A. Munaretto, M. Fonseca, Routing and quality of service support for mobile ad hoc networks, Co mputer Networks 51 (11) (2007) 31423156.

47. P. Samar, M . Pearlman, S. Haas, Independent zone routing: an adaptive hybrid routing framework for ad hoc wireless networks,IEEE/ACM Transactions on Networking 12 (4) (2004) 595608.

48. G. Pei, M . Gerla, T.-W. Chen, Fisheye state routing in mobile ad hoc networks, in: Proceedings of IEEE ICDCS Workshop on Wireless Networks and Mobile Computing, April 2000, pp. D71D78.

49. G. Pei, M . Gerla, X. Hong, LANM AR: Landmark routing for large scale wireless ad hoc networks with group mobility, in: Proceedings of ACM M obiHoc, August 2000, pp. 1118.

50. G.N. Aggelou, R. Tafazolli, RDM AR: A bandwidth-efficient routing protocol for mobile ad hoc networks, in: Proceedings of ACM WOWM OM , August 1999, pp.2633.

51. S.-C. Woo, S. Singh, Scalable routing protocol for ad hoc networks,Wireless Networks 7 (5) (2001) 513529.

52. M. Joa-Ng, I.-T. Lu, A peer-to-peer zone-based two- level lin k state routing for mobile ad hoc network, IEEE Journal on Se lected Areas in Co mmunications 17 (8) (1999) 14151425.

53. S. Radhakrishnan, N. Rao, G. Racherla, C. Sekharan, S. Batsell, DST a routing protocol for ad hoc networks using distributed spanning trees, in: Proceedings of IEEE WCNC, September 1999,pp. 100104.

54. N. Nikaein, H. Labiod, C. Bonnet, DDR: distributed dynamic routing algorithm for mobile ad hoc networks, in: Proceedings of ACM M obiHoc, August 2000, pp. 1927.

55. G. Wang, Y. Ji, D.C. M arinescu, D. Turgut, A routing protocol for power constrained networks with asymmetric links, in: Proceedings of the ACM Workshop on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN),October 2004, pp. 6976.

56. G. Wang, D. Turgut, L. Bölöni, Y. Ji, D. M arinescu, Improving routing performance through m-limited forwarding in power- constrained wireless networks, Journal of Parallel and Distributed Computing (JPDC) 68 (4) (2008) 501514.

57. J. Wang, E. Osagie, P. Thulasiraman, R. Thulasiram, Hopnet: a hybrid ant colony optimization routing algorithm for mobile ad hoc network, Ad Hoc Networks 7 (4) (2009) 690705.

58. X. Xiaochuan, W. Gang, W. Keping, W. Gang, J. Shilou, Link reliability based hybrid routing for tactical mobile ad hoc network, Journal of Systems Engineering and Electronics 19 (2) (2008) 259267.

59. C.-C. Yang, L.-P. Tseng, Fisheye zone routing protocol: a multi-level zone routing protocol for mobile ad hoc networks, Computer Communications 30 (2) (2007) 261268.

60. S. Rajagopalan, C.-C. Shen, ANSI: A swarm intelligence-based unicast routing protocol for hybrid ad hoc networks, Journal of Systems Architecture 52 (8-9) (2006) 485504.

61. A. Bamis, A. Boukerche, I. Chatzigiannakis, S. Nikoletseas, A mobility aware protocol synthesis for efficient routing in ad hoc mobile networks, Computer Networks 52 (1) (2008) 130 154.

62. O. Souihli, M .Frikha,M .Hamouda, Load-balancing in M ANET shortest path routing p rotocols, Ad Hoc Networks 7 (2) (2009) 431442.

63. Y. Ko, N. Vaidya, Location-Aided Routing (LAR) in mobile ad hoc networks, in: Proceedings of ACM M obiCom, October 1998, pp. 6675

64. Y.-B. Ko, N.H. Vaidya, GeoTORA: A protocol for geocasting in mobile ad hoc networks, in: Proceedings of IEEE ICNP, November 2000, pp.240249.

65. S. Basagni, I. Chlamtac, V.R. Syrotiuk, B.A. Woodward, A distance routing effect algorithm for mobility (DREAM ), in:

    Proceedings of the ACM M OBICOM , October 1998, pp. 76 84.

66. B. Karp, H. Kung, GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, in: Proceedings of ACM MobiCom, August 2000,pp. 243254.

67. C.-H. Chou, K.-F. Ssu, H. Jiau, Dynamic route maintenance for geographic forwarding in mobile ad hoc networks, Computer Networks 52 (2) (2008) 418431.

68. M . Colagrosso, N. Enochs, T. Camp, Improvements to location-aided routing through directional count restrictions, in: Proceedings of International Conference on Wireless Networks (ICWN), June 2004,pp. 924929.

69. B. Williams, T. Camp, Comparison of broadcasting techniques for mobile ad hoc networks, in: Proceedings of ACM M obiHoc, June 2002, pp. 194205.

70. J. Boleng, T. Camp, Adaptive location aided mobile ad hoc network routing, in: Proceedings of IEEE International Performance,Computing, and Communications Conference (IPCCC), April 2004,pp. 423432

71. J. Boleng, Exploiting location information and enabling adaptive mobile ad hoc networking protocols, Ph.D. Thesis, Colorado School of M ines, 2002.

72. Y. Liu, X. Hu, M . Lee, T. Saadawi, A region-based routing protocol for wireless mobile ad hoc networks, IEEE Network 18 (4) (2004) 1217.

73. J. Li, P. M ohapatra, LAKER: Location aided knowledge extraction routing for mobile ad hoc networks, in: Proceedings of IEEE WCNC, M arch 2003, pp. 11801184.

74. L. Blazevic, J.-Y.L. Boudec, S. Giordano, A location-based routing method for mobile ad hoc networks, IEEE Transactions on M obile Computing 4 (2) (2005) 97110.

75. G. Boato, F. Granelli, M ORA: a movement -based algorithm for adhoc networks, in: Proceedings of The Tenth International Conference on Distributed M ultimedia Systems (DM S), 2004, pp.171174.

76. V. Giruka, M . Singhal, A self-healing on-demand geographic path routing protocol for mobile ad-hoc networks, Ad Hoc Networks 5 (7) (2007) 11131128.

77. J.-H. Song, V. Wong, V. Leung, Secure position-based routing protocol for mobile ad hoc networks, Ad Hoc Networks 5 (1) (2007) 7686.

78. J. Ghosh, S. Philip, C. Qiao, Sociological orbit aware location approximation and routing (solar) in manet, Ad Hoc Networks 5 (2) (2007) 189209.

79. N. Carlsson, D. Eager, Non-euclidian geographic routing in wireless networks, Ad Hoc Networks 5 (7) (2007) 11731193.

80. J. Na, C.-K. Kim, Glr: a novel geographic routing scheme for large wireless ad hoc networks, Computer Networks 50 (17) (2006) 34343448.

81. S. Kwon, N. Shroff, Geographic routing in the presence of location errors, Computer Networks 50 (15) (2006) 2902 2917.

82. M . Yuksel, R. Pradhan, S. Kalyanaraman, An implementation framework for trajectory -based routing in ad hoc networks, Ad Hoc Networks 4 (1) (2006) 125137.