An Efficient Geometric Routing Using Convex Hull Tree Information In Geographic Protocol

Abstract: Geographic routing is of interest for sensor networks because a point-to-point primitive is an important building block for data-centric applications. Improved Greedy Distributed Spanning Tree Routing (IGDSTR), is a new geographic routing algorithm that finds shorter routes and generates and less maintenance traffic than Greedy Perimeter Stateless Routing (GPSR) algorithms. Greedy forwarding faces the problem at local dead ends where geographic routing potentially scales well. GPSR handles dead ends by planarizing the node connectivity graph and then using the right-hand rule to route around the resulting faces. The proposed system introduces a new kind of spanning tree, called hull tree. Hull trees provide a way of aggregating location information built by convex hull to the spanning tree. Convex hull is used in routing to avoid paths that will not be productive, so it is able to traverse a significantly reduced sub tree, consisting of only the nodes with convex hulls that contain the destination point.

Keywords: Geographic Routing, Greedy Distributed Spanning Tree Routing, Hull Tree, Routing protocol