Geographical routing using partial information for wireless ad hoc networks

In this article, we present an algorithm for routing in wireless ad hoc net works using information about geographical location of the nodes. We assume each node knows its geographical position and the position of the node to which it wants to send a packet. Initially, the nodes know only their neigh bors, but over time they discover other nodes in the network;. The routing table at a node S is a list ((p(i), S-i)), where p(i) is a geographical pos ition and Si is a neighbor of node S. When node S receives a packet fur a n ode D at position pos(D), it finds the p(i) in its routing table which is c losest to pos(D) and forwards the packet to the neighbor Si. We prove the c orrectness of the algorithm and show that our algorithm naturally aggregate s the nodes so that the routing tables remain small. We show that the mean routing table size is O(Llogn), where L is the average number of hops betwe en two nodes and n is the number of nodes in the network. We also present m ethods fur taking positional errors, node failures and mobility into accoun t. We justify the results through simulation.