Improving Geographic Routing with Neighbor Sectoring

Abstract

An ad hoc network consists of many mobile devices which forms a network automatically. Among many ad hoc network routing algorithms, geographic routing algorithm is known as an efficient and scalable routing protocol. The most popular method for geographic routing is Greedy Forwarding. Although Greedy Forwarding is effective in many cases, packets may get routed to dead-end nodes.

We present a new geographic routing algorithm, Geographic Routing with Neighbor Sectoring (GRNS), which has ability to reduce the probability of forwarding packets to dead-end nodes. The GRNS algorithm, like any other geographic routing algorithms, uses location information for packet delivery in multi-hop ad hoc networks. In GRNS, each node in the network divides its neighbors into 16 sectors and informs its neighboring nodes of its identification, position information and its own sectoring information. A node forwards packets according to its neighboring nodes information (e.g. position, sectoring information) stored in the routing table. The simulation result shows the path length of GRNS is slightly longer than or similar to Greedy Forwarding in networks without dead-end nodes, and less than GPSR in networks with dead-end nodes. The performance of GRNS is very closer to Greedy Forwarding but reduces the probability of forwarding packets to a dead-end node.