The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	A clustered back-bone for routing in ad-hoc networks
Author:	Kothawala, Delzad
View Online:	njit-etd2004-056 (ix, 36 pages ~ 1.7 MB pdf)
Department:	Department of Computer Science
Degree:	Master of Science
Program:	Computer Science
Document Type:	Thesis
Advisory Committee:	Czumaj, Artur (Committee chair) Rytter, Wojciech (Committee member) Nassimi, David (Committee member)
Date:	2004-05
Keywords:	Ad-hoc networks Topology control Power efficiency
Availability:	Unrestricted
Abstract:	In the recent years, a lot of research work has been undertaken in the area of ad-hoc networks due to the increasing potential of putting them to commercial use in various types of mobile computing devices. Topology control in ad-hoc networks is a widely researched topic; with a number of algorithms being proposed for the construction of a power-efficient topology that optimizes the battery usage of the mobile nodes. This research proposes a novel technique of partitioning the ad-hoc network into virtually-disjoint clusters. The ultimate aim of forming a routing graph over which power-efficient routing can be implemented in a simple and effective manner is realized by partitioning the network into disjoint clusters and thereafter joining them through gateways to form a connected, planar back-bone which is also a t-spanner of the original Unit Disk Graph (UDG). Some of the previously proposed algorithms require the nodes to construct local variations of the Delaunay Triangulation and undertake several complicated steps for ensuring the planarity of the back-bone graph. The construction of the Delaunay Triangulation is very complex and time-consuming. This work achieves the objective of constructing a routing graph which is a planar spanner, without requiring the expensive construction of the Delaunay Triangulation, thus saving the node power, an important resource in the ad-hoc network. Moreover, the algorithm guarantees that the total number of messages required to be sent by each node is O(n). This makes the topology easily reconfigurable in case of node motion.