@INPROCEEDINGS{Anderson2011Signal,
AUTHOR="Eric W Anderson and Caleb T Phillips and Douglas Sicker and Dirk Grunwald",
TITLE="Signal Quality Pricing: Decomposition for Spectrum Scheduling and System
Configuration",
BOOKTITLE="Fifth IEEE International Symposium on New Frontiers in Dynamic Spectrum
Access Networks 2011(DySPAN 2011) (IEEE DySPAN 2011)",
ADDRESS="Aachen, Germany",
KEYWORDS="optimization; scheduling; pricing; TDMA; spatial re-use",
ABSTRACT="Who gets to use radio spectrum, and when, where, and how? Many problems in
traditional radio communication, wireless networking, and cognitive radio
are variants of this question. Optimization decomposition based on
Lagrangian relaxation of signal quality requirements provides a
mathematical framework for solving this type of combined problem. This
paper demonstrates the technique as a solution to optimal spatial reuse
time-division multiple access (STDMA) scheduling with reconfigurable
antennas. The joint beam steering and scheduling (JBSS) problem offers both
a challenging mathematical structure and significant practical value. 
We present algorithms for JBSS and describe an implemented system based on
these algorithms. We achieve up to a 600\% speedup over TDMA with a mean of
234\% speedup in our experiments. The decomposition approach leads to a
working distributed protocol which is provably equivalent to our 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 our knowledge, the first actually implemented wireless scheduling system
based on dual decomposition. We identify and briefly address some of the
challenges that arise in taking such a system from theory to reality."
}