Abstract

In position-based routing algorithms, the nodes use the geographical information to make routing decisions. Recent research in this field addresses such routing algorithms in two-dimensional (2 D ) space. However, in real applications, the nodes may be distributed in three-dimensional (3 D ) space. Transition from 2 D to 3 D is not always easy, since many problems in 3 D are significantly harder than their 2 D counterparts. This dissertation focuses on providing a reliable and efficient position-based routing algorithms with the associated pre-processing algorithms for various 3 D ad hoc networks. In the first part of this thesis, we propose a generalization of the Yao graph where the cones used are adaptively centered on the nearest set of neighbors for each node, thus creating a directed or undirected spanning subgraph of a given unit disk graph (UDG). We show that these locally constructed spanning subgraphs are strongly connected, have bounded out-degree, are t -spanners with bounded stretch factor, contain the Euclidean minimum spanning tree as a subgraph, and are orientation-invariant. Then we propose the first local, constant time algorithm that constructs an independent dominating set and connected dominating set of a Unit Disk Graph in a 3 D environment. We present a truncated octahedral tiling system of the space to assign to each node a class number depending on the position of the node within the tiling system. Then, based on the tiling system, we present our local algorithms for constructing the dominating sets. The new algorithms have a constant time complexity and have approximation bounds that are completely independent of the size of the network. In the second part of this thesis, we implement 3 D versions of many current 2 D position-based routing algorithms in addition to creating many new algorithms that are specially designed for a 3 D environment. We show experimentally that these new routing algorithms can achieve nearly guaranteed delivery while discovering routes significantly closer in length to a shortest path. Because many existing position-based routing algorithms for ad hoc and sensor networks use the maximum transmission power of the nodes to discover neighbors, which is a very power-consuming process. We propose several localized power-aware 3 D position-based routing algorithms that increase the lifetime of a network by maximizing the average lifetime of its nodes. These new algorithms use the idea of replacing the constant transmission power of a node with an adjusted transmission power during two stages. The simulation results show a significant improvement in the overall network lifetime over the current power-aware routing algorithms