Date of Award

Spring 1-1-2010

Document Type

Thesis

Degree Name

Doctor of Philosophy (PhD)

Department

Computer Science

First Advisor

Douglas Sicker

Second Advisor

Dirk Grunwald

Third Advisor

Manuel Laguna

Abstract

This document describes an approach to integrating antenna selection and control into a time-division MAC scheduling process. I argue that through such integration it is possible to achieve greater spatial reuse and interference mitigation than by solving the two problems separately. Without coupling between the MAC scheduling and physical antenna configuration processes, a "chicken-and-egg" problem exists: If antenna decisions are made before scheduling, they cannot be optimized for the communication that will actually occur. If, on the other hand, the scheduling decisions are made first, the scheduler cannot know what the actual interference and communications properties of the network will be.

This dissertation presents algorithms for optimal spatial reuse TDMA scheduling with reconfigurable antennas. I present and solve the joint beam steering and scheduling problem for spatial reuse TDMA and describe an implemented system based on the algorithms developed. The algorithms described achieve up to a 600% speedup over TDMA in the experiments performed. This is based on using an optimization decomposition approach to arrive at a working distributed protocol which is equivalent to the original problem statement while also producing optimal solutions in an amount of time that is at worst linear in the size of the input. This is, to the best of my knowledge, the first actually implemented STDMA scheduling system based on dual decomposition. This dissertation identifies and briefly address some of the challenges that arise in taking such a system from theory to reality.

Share

COinS