Review of Location Based Routing Protocols in Mobile Ad Hoc Networks

Review of Location Based Routing Protocols in Mobile Ad Hoc Networks

Dhaval S. Deolasi Jaishri M. Waghmare

M. Tech. Student Associate Professor

SGGSIE&T, Nanded SGGSIE&T, Nanded

Abstract

Many location based routing protocols have been developed for ad hoc networks. This paper presents the overview of Location-Aided Routing (LAR) protocol, Adaptive Cell Relay (ACR) Routing protocol and Distance Routing Effect Algorithm for Mobility (DREAM). LAR protocol makes use of location information obtained through global positioning system to reduce the routing area used for flooding route request packets. ACR protocol optimizes LAR protocol by dividing the routing area (a rectangular region in LAR) into multiple cells. Route request packet is then flooded to only a serial of small cells as opposed to a rectangular region in case of LAR which further reduces the routing overhead. ACR protocol also uses two routing strategies to handle the node density change in the network. DREAM is a proactive routing protocol that uses geographic location and speed information of mobile nodes for routing data packets.

1. Introduction

   A Mobile ad hoc network (MANET) contains wireless mobile nodes that communicate with each other over a wireless medium without any existing or fixed infrastructure. Setting up of fixed access points and backbone infrastructure is not always viable. For instance, infrastructure may not be present in a disaster area or war zone. Routes between two nodes in a MANET may contain multiple hops through other nodes in the network. In MANET, each mobile node operates as a host as well as a router and forwards packets to other mobile nodes in the network that may or may not be within direct transmission range of each other. Nodes in MANET can move in all possible directions in an arbitrary fashion. Such node mobility causes rapid topology change which results into frequent route failures.

   Thats why many routing protocols have been proposed for MANETs with the objective to increase the efficiency of routing. Examples include Ad hoc On-

   demand Distance Vector (AODV) [5], Dynamic Source Routing (DSR) [4], LAR [2], DREAM) [3], ACR [1],

   Highly Dynamic Destination-Sequenced Distance- Vector Routing (DSDV) [13], Zone Routing Protocol (ZRP) [14], Optimized Link State Routing Protocol (OLSR) [15], Fisheye State Routing (FSR) [16], Greedy Perimeter Stateless Routing (GPSR) [17], Temporally Ordered Routing Algorithm (TORA) [18]. Out of these protocols LAR, DREAM & ACR use location information obtained from global positioning system (GPS). LAR uses only one routing strategy to flood the route request packets. On the other hand, ACR uses two routing strategies to flood the route request packets, one for sparse network and the other for dense network. DREAM uses only one routing strategy to flood the data packets.

   The routing protocols for MANETs are reviewed based on different characteristics such as type of routing, network metrics, topology etc. [8, 9, 12]. Some authors have performed analysis and comparison between different routing protocols using various network simulators [7, 10, 11]. In this paper, we have surveyed major location based routing protocols for MANETs.

2. Routing in MANET

   The routing protocols used in MANETs are different from routing protocols of wired networks. The reasons are as follows:

   • Frequent route updates.

   • Mobility of nodes.

   • Limited transmission range.

     The performance criteria of nodes in MANETs are different than that of wired networks [6]. Some of the performance metrics of MANET routing protocols are as follows:

   • Energy consumption.

   • Bandwidth consumption.

   • Route Stability.

     Routing protocols in MANETs are mainly classified into proactive routing protocols and reactive routing protocols.

     1. Proactive protocols

        In proactive routing protocols, nodes maintain routes continuously. These protocols use periodic updates to maintain routes between every host pair in the MANET. Thus, they have high routing overhead. Each node consumes significant bandwidth to keep routes to other nodes up-to-date. But, there is little or no delay to determine route to destination since routes are always maintained up-to-date. DREAM belongs to the class of proactive routing protocols.

     2. Reactive protocols

     Reactive routing protocols are based on finding routes between two nodes, when source node wants to send message to destination node. So, route discovery procedure is used to set up route on demand. Since routes are determined on demand, they have low routing overhead and bandwidth consumption is less. But, there is significant delay in determining route to destination. LAR and ACR belong to the class of reactive routing protocols.

3. LAR protocol

   LAR is an on-demand source routing protocol. In LAR, a node can obtain its location information using GPS.

   Flooding is a mechanism for reactive routing protocol. Whenever a node wants to send data to another node in the MANET, then it has to find out the route to destination node. So source node floods a route request message to all its neighboring nodes. Route request message contains fields like source identifier, destination identifier, session id etc. When a node receives a route request message, it checks whether its intended for itself. If answer is yes, then it forwards the route reply message to the source node otherwise it adds its identifier into the route request message and flood it to its neighboring nodes only once. If it had already flooded such route request message, then it simply discards the new message.

   In LAR, it is assumed that each node initially broadcast its location information to the other nodes in the network and it can broadcast the updated location information periodically. Route discovery is initiated when existing route to destination is broken or route to destination is unknown. So when a node wants to obtain the route to another node in the network, it uses the most recent location information about the destination node which may have become quite old by the time it wants to send data. Let, (XD, YD) be the location of destination node D at time t0, Vavg be the average speed with which D is moving and t1 be the time at which source node S wants to find out route to destination D. Therefore source node S can now determine an expected zone for destination which is a circular region of radius R = Vavg * (t1-t0) centered at

   (XD, YD). Expected zone is expected to hold the current location of the destination.

   Source node S defines a request zone which is a rectangular region that contains the expected zone and location of the sender node. The location coordinates of request zone are included in the route request packet. A node forwards a route request if and only if it belongs to the request zone. This helps in reducing the routing overhead as compared to flooding. If a neighbor of S determines it is within the request zone, it forwards the route request packet further. A node can determine whether it lies within the request zone by comparing the location coordinates of request zone and its own location coordinates obtained using GPS.

   Figure 1. Source node outside expected zone

   When source node is outside the expected zone, request zone is defined as S in one corner, (XS, YS) and the expected zone containing D in the other corner as shown in figure. 1. When source node is within the expected zone, request zone is defied as shown in figure. 2.

   Figure 2. Source node inside expected zone

   When the destination node D receives the route request message, it sends a route reply message back to the source using the path obtained by reversing the path recorded in the route reply message. Node D includes

   its current location and average speed within the route reply message.

4. ACR routing protocol

   In case of LAR, the request zone is large and can lead to large routing overhead. Under the ACR protocol, the entire routing area is divided into squares of the same size called cells. Route request packet is flooded to only a sequence of cells as compared to that of a rectangular region in LAR. So it reduces routing overhead to a large extent.

   ACR also uses location information. There are 3 components of ACR routing protocol.

   1. Cell Relay (CR) routing for dense networks.

   2. Large Cell (LC) routing for sparse networks.

   3. Adaptive scheme that monitors node density changes and selects either CR or LC routing, based on the current node density in the network.

   1. CR routing for dense networks

      Whenever source node wants to find route to destination node, a line is drawn joining the cell containing source node and the cell containing destination node. The sequence of cells is recorded. The cells in the expected zone of destination node are also included in the list of cells. Now, route request (RR) packet is flooded by source node to neighboring cell. Only nodes in that cell will process this packet and other nodes will discard that packet. Also only the node with highest remaining energy and less random back- off time succeeds first in flooding the RR packet to nodes in next cell. If a node in that cell hears the flooding of RR packet to next cell by some other node in same cell, then it will not forward the RR packet. This reduces routing overhead to a large extent.

      This procedure is repeated till RR packet reaches to destination node. On receiving the RR packet, destination node sends a route reply (RP) packet back to source node along the reverse route recorded in RR packet. When the source node receives the RP packet, it obtains the route to destination node and can now send data packets to destination node as depicted in figure. 3 where R denotes node transmission range and a denotes side length of cell.

      Figure 3. CR routing in ACR protocol

   2. LC routing for sparse networks

      It is essential to first guarantee the delivery of data packets in a sparse network. For this purpose, routing area is divided into multiple LCs such that each LC may contain at least one node. Same procedure as described in case of CR routing is followed except that in LC routing all nodes in the cell participate in flooding and they flood the RR packet to nodes in the same cell as well as the next cell. This is because some node in next LC may not be reachable directly by any node in current LC. Whereas in CR routing, a node in next cell is directly reachable by any node in current cell since network is dense and size of cell is less.

   3. Adaptive scheme for monitoring node density and changing routing strategy

   Node density is defined as the total number of nodes currently present in the network divided by the routing area. Node density in the network changes when the number of active nodes in routing area changes and/or size of the routing area changes. A node is selected as the adaptive head (AH) that detects node density change in the network. Initially AH broadcasts its location to all other nodes in the network. When node density in the network changes, a density change message is sent to the AH and accordingly AH modifies the node density.

   There are two initially defined thresholds for node density, D1 and D2, where D1 > D2. When the node density is greater than D1, AH switches the routing strategy from LC to CR and when the node density is less than D2, AH switches the routing strategy from CR to LC. New route discovery after this time instant will use the new routing strategy and all nodes in the network are notified about this change in routing strategy by AH via flooding of a strategy change message.

5. DREAM protocol

   In DREAM protocol, geographic location information is used to limit the flooding of data packets to a small region. DREAM is a proactive routing protocol. So, there is no route discovery procedure and no routing of route request packets in DREAM. It exploits location and mobility rate information of nodes for routing of data packets. In DREAM, each node records location information in a routing table. The routing table of a node contains location information of all other nodes in the network.

   When a source node wants to send a data packet, firstly it checks its routing table and obtains the location information of the destination node. Then, the source node forwards the data packet to a neighbor in the direction towards the destination. So, location information should be properly disseminated throughout the whole network. To do that, every

   mobile node sends control message containing its location co-ordinates. The frequency of location information dissemination is determined by distance effect and mobility rate.

   Considering distance effect, nodes that are far apart need to disseminate their location information less frequently than nodes that are closer together. To achieve this, an age is associated with each control message which tells how far from the sender that message travels. Considering mobility rate, node needs to communicate its location frequently if it is moving at a faster rate. Thus, the rate of control message generation can be optimized as per the mobility rate of each node. Distance effect limits the transmission range of the control message because when age expires, message is discarded.

6. Comparison of LAR, ACR and DREAM

   Location based routing protocols use location and node mobility information to perform the routing decisions. Their objective is to perform more efficient route discovery and limit the flooding of route request packets to reduce the routing overhead. Both LAR and ACR are reactive routing protocols whereas DREAM is a proactive routing protocol. LAR and ACR use location information for route discovery whereas DREAM uses location information for data delivery.

   In DREAM, there is little or no delay to determine route to destination as routes are maintained up-to-date. In contrast, LAR and ACR both have significant delay to determine route to destination as route is set up on demand using route discovery procedure. Thus, there is a trade-off depending on the traffic and mobility pattern in the MANET.

   Table 1. Comparison of location based routing protocols in MANET

   	LAR	ACR	DREAM
   Type of routing	Reactive	Reactive	Proactive
   Routing overhead	Medium	Low	Medium
   Scalability	Bad	Good	Bad
   Loop free	Yes	Yes	Yes
   Energy consumption	Medium	Low	Medium

7. Conclusions

   Although the flooding is constrained in both LAR and ACR by using location information, LAR is not suitable for large-scale ad hoc networks. In contrast to LAR, ACR uses node density measure to adapt to changing node density in the network. In ACR as two different routing strategies are used to handle the node

   density change, so it is scalable. Also, it outperforms LAR in case of efficiency, end-to-end delay and throughput under different traffic load. In DREAM, location information is used to constrain the flooding of data packets to a small region. DREAM is not suitable for large-scale ad hoc networks because routing overhead increases as the size of network increases.

8. References

1. X. Du and D. Wu, Adaptive cell relay routing protocol for mobile ad hoc networks, IEEE Trans. on Vehicular Technology, vol. 55, no. 1, Jan. 2006.

2. Y. B. Ko and N. H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proc. ACM/IEEE MobiCom 1998, pp. 6675, Dallas, TX, Aug. 1998.

3. S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward, A distance routing effect algorithm for mobility (DREAM), Proc. ACM/IEEE MobiCom 1998, Dallas, TX, pp. 7684. Aug. 1998.

4. D. B. Johnson and D. A. Maltz, Dynamic source routing in ad hoc wireless networking, Mobile Computing. T. Imielinski and H. Korth, Eds., ch. 5. Boston, MA: Kluwer, 1996.

5. C. E. Perkins and E. M. Royer, Ad-hoc on demand distance vector routing, in Proc. IEEE WMCSA99, New Orleans, LA, pp. 90100.

6. S. Corson and J. Macker, Mobile ad hoc networking (MANET): Routing protocol performance issues and evaluation considerations (Internet-draft), in: Mobile Ad- hoc Network (MANET) Working Group, IETF (1998).

7. T. Camp, J. Boleng, B. Williams, L. Wilcox and W. Navidi, Performance Comparison of two location based routing protocols for ad hoc networks, Proceedings of IEEE Infocom 2002, New York.

8. E. M. Royer, and C. K. Toh, A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks, IEEE Personal Communications, April 1999.

9. M. Mauve, J. Widmer, H. Hartenstein, A Survey on Position-Based Routing in Mobile Ad-Hoc Networks, IEEE Network, Vol. 15 (2001).

10. J. Broch, D. A. Maltz, D. B. Johnson, Y. C. Hu, and J. Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proc. MOBICOM, 1998.

11. S. R. Das, R. Castaneda, J. Yan and R. Sengupta, Comparative performance evaluation of routing protocols for mobile, ad hoc networks, in: Proc. of IEEE IC3N 98 (1998).

12. S. Ramanathan and M. Steenstrup, A survey of routing techniques for mobile communication networks, Mobile Networks and Applications (1996).

13. C. E. Perkins and P. Bhagwat, Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers, in: Proc. Of ACM SIGCOMM 94 Symposium on Communication Architecture and Protocols (1994).

14. Z. J. Haas and M. R. Pearlman, The zone routing protocol (ZRP) for ad hoc networks (Internet-draft), in: Mobile Ad-hoc Network (MANET) Working Group, IETF (1998).

15. T. Clousen and P. Jacquet, Optimized Link State Routing Protocol, IETF Network Working Group, Oct. 2003. [Online]. Available: http://www.ietf.org/rfc/rfc3626.txt.

16. G. Pei, M. Gerla, and T. W. Chen, Fisheye state routing: A routing scheme for ad hoc wireless networks, Proc. IEEE ICC 2000, New Orleans, LA, Jun. 2000.

17. B. Karp and H. T. Kung, GPSR: Greedy perimeter stateless routing for wireless networks, in Proc. MobiCom 2000, Boston, MA.

18. V. D. Park and S. Corson, Temporally-ordered routing algorithm (TORA) version 1 functional specification (Internet-draft), in: Mobile Ad-hoc Network (MANET) Working Group, IETF (1998).

International Journal of Engineering Research & Technology (IJERT)

ISSN: 2278-0181

Vol. 2 Issue 4, April – 2013