Geographical routing using partial information for wireless ad hoc networks

We present an algorithm for routing in wireless ad hoc networks using information about the 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 neighbors. 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 position and S_i is a neighbor of node S. When node S receives a packet for a node D at position pos(D), it finds the p _i in its routing table which is closest to pos(D) and forwards the packet to the neighbor S_i. We prove the correctness of the algorithm and show that our algorithm naturally aggregates the nodes so that the routing tables remain small. We show that the mean routing table size is O(L¯logn), where L¯ is the average number of hops between two nodes and n is the number of nodes in the network. We also present methods for taking positional errors, node failures and mobility into account. We justify the results through simulation