Abstract

A unit disk graph and its proximity graphs are often used as the underlying topologies of a mobile ad hoc network. One category of unicast routing algorithms, position-based routing algorithms, has been developed and studied extensively in the context of 2-dimensions (2-D). This, however, poses evident questions in terms of the reliability and efficiency of these algorithms when practically the mobile host is an object positioned in the real world of 3-dimensions (3-D). Our first proposed 3-D routing algorithm, Projective FACE routing on two orthogonal planes, adopts a projective approach to adapt the 2-D FACE routing algorithm to a 3-D environment. This algorithm, shown by our simulation, performs significantly better in terms of delivery rate than the other deterministic routing algorithms such as 3-D Greedy , 3-D Compass routing algorithms. We provide a comparison of performance for routing in 2-D and in 3-D. Two versions, half-space partition and quadrant-space partition , for certain deterministic routing algorithms are proposed to accommodate the randomized routing in 3-D. We also study experimentally the properties of geometric graphs in 3-D and the performance of various 3-D routing algorithms on these graphs in this thesis.