Location aware (Geographic) routing

The location aware routing protocols use the geographical location information of nodes provided by the GPS (or other systems) during the data forwarding process. A node selects the next hop for routing by considering only the physical location of its one-hop neighbors and the physical location of the destination. These routing protocols are called position-based or geographic approaches as the packets are forwarded to one-hop neighbor towards the receiver direction. Location aware routing protocols do not require storing the routing information. Moreover, these routing protocols do not require a network wide search as the packets are forwarded to the known coordinates. Therefore, location aware routing protocols quickly adapts to route changes and are more scalable compared to unicast routing protocols. Greedy forwarding, directed flooding and hierarchical routing are the three key strategies of location aware routing protocols. The chief idea behind these routing algorithms is to forward the packets to the nodes that are closer to the destination than itself. Greedy forwarding and directed flooding based protocols relay the packet to one or more neighbors respectively. Hierarchical routing protocols combine the characteristics of the position based and non-position-based routing algorithms.

Greedy Perimeter Stateless Routing (GPSR)

Greedy Perimeter Stateless Routing (GPSR) applies greedy forwarding in which data forwarding is in hop-by-hop fashion via the nexthop having positive progress towards the destination. Communication hole problem that arises while performing greedy forwarding is solved using the perimeter mode forwarding.

Position based opportunistic routing (POR)

Position based opportunistic routing (POR) protocol is an efficient geographic routing protocol and improves the reliability of data delivery. POR applies greedy forwarding and facilitates uninterrupted communication using air-backup. Backup nodes involve in packet in the case of link failure between source and next hop. In addition, a communication hole problem that arises while performing greedy forwarding is solved using the void handling mechanism, called Virtual Destination-based Void Handling (VDVH).

Solution in NS2

  • In NS2, geographic routing protocol (GPSR) is simulated with the help of the location information of the nodes. Distance is calculated from each neighbor to the destination. Neighbor which is having the least distance to the destination is selected as next hop and data is forwarded via the next hop to the destination.

  • To test the performance of geographic routing in dynamic network, mobility model is applied to the network.

  • The efficiency of the link failure handling mechanism via backup nodes in POR is analyzed in the network by applying various mobility scenarios.

  • Network density is varied in order to create the communication hole and to evaluate the efficiency of the VDVH mechanism in POR on such condition.

  • Performance of Geographic routing protocols (GPSR, POR) is compared with topology based routing protocol (AODV).

  • Geographic routing protocol provides better performance in terms of the packet delivery ratio, delay; throughput and overhead when compared to topology based routing protocol.

Related Project Titles:

  • Brad Karp, H. T. Kung Shengbo Yang, Chai Kiat Yeo, and Bu Sung Lee “Toward Reliable Data Delivery for Highly Dynamic Mobile Ad Hoc Networks” IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 11, NO. 1, JANUARY 2012

  • “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks” MobiCom 2000