Login | Register

Position-based routing algorithms for three-dimensional ad hoc networks


Position-based routing algorithms for three-dimensional ad hoc networks

Abdallah, Alaa Eddien Awad (2009) Position-based routing algorithms for three-dimensional ad hoc networks. PhD thesis, Concordia University.

[thumbnail of NR63398.pdf]
Text (application/pdf)
NR63398.pdf - Accepted Version


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

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Abdallah, Alaa Eddien Awad
Pagination:xv, 140 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Opatrny, J and Fevens, T
Identification Number:LE 3 C66C67P 2009 A23
ID Code:976204
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:21
Last Modified:13 Jul 2020 20:09
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

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top