Login | Register

Routing protocols for ad hoc networks with uncertainty in the position of the destination


Routing protocols for ad hoc networks with uncertainty in the position of the destination

Patnaik, Anup (2006) Routing protocols for ad hoc networks with uncertainty in the position of the destination. Masters thesis, Concordia University.

PDF - Accepted Version


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

Divisions:Concordia University > Faculty of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Patnaik, Anup
Pagination:ix, 97 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Narayanan, Lata
ID Code:8857
Deposited By: Concordia University Libraries
Deposited On:18 Aug 2011 18:37
Last Modified:18 Aug 2011 18:37
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page


Downloads per month over past year

Back to top Back to top