Semester

Fall

Date of Graduation

2013

Document Type

Thesis

Degree Type

MS

College

Statler College of Engineering and Mineral Resources

Department

Lane Department of Computer Science and Electrical Engineering

Committee Chair

Vinod K. Kulathumani

Committee Co-Chair

Yaser P. Fallah

Committee Member

Vinod K. Kulathumani

Committee Member

James D. Mooney

Abstract

Geometric spanners are a popular form of topology control in wireless networks because they yield an efficient, reduced interference subgraph for both unicast and broadcast routing.;In this thesis work a distributed algorithm for creation of geometric spanners in a wireless sensor network is presented. Given any connected network, we show that the algorithm terminates in O(1) time, irrespective of network size. Our algorithm uses an underlying clustering algorithm as a foundation for creating spanners, and only relies on the periodic heartbeat messages associated with cluster maintenance for the creation of the spanners. The algorithm is also shown to stabilize locally in the presence of node additions and deletions. The performance of our algorithm is verified using large scale simulations. The average path length ratio for routing along the spanner for large networks is shown to be less than 2.;Geometric Spanners is a well-researched topic. The algorithm presented in this thesis differs from other spanner algorithms in the following ways: 1. It is a distributed locally self-stabilizing algorithm. 2. It does not require location information for its operation. 3. Creates spanner network in constant time irrespective of network size and network density.

Download

Share

COinS