Abstract

An ad hoc network comprises a set of computing devices, often mobile, that communicate using wireless transmissions with the devices within their transmission range. These devices or nodes are able to detect the presence of other nodes in their transmission range as well route packets on behalf of other nodes. Hence, the network does not need to depend on any predefined infrastructure. This lack of infrastructure makes the problem of routing and packet forwarding a challenging task in such networks. To carry out this task in an efficient and scalable manner, several authors have proposed position-based routing algorithms. Position-based routing algorithms utilize the position or location of the destination node to inform routing decisions. However, obtaining the accurate position of the destination may not be feasible in some settings. In this thesis, we consider the problem of routing in an ad hoc network where the source node knows the approximate position of the destination node, but is uncertain about its exact current location. We investigate two approaches to this problem: one, based on a traversal of the faces of a planar sub-graph of the graph representing the network, and the second, based on flooding a limited area of the graph that represents the region the destination is likely to be found. We propose several variants of both approaches, and do extensive simulations to analyze the performance of the algorithms. Our results indicate that a simple modification of the basic flooding approach yields the best trade-off for optimizing delivery rate, stretch factor, as well as transmission cost. If however, delivery is required to be guaranteed, then a variant of the face tree traversal approach that we propose has the best performance