Practical Conflict Graphs for Dynamic Spectrum Distribution
Xia Zhou
Zengbin Zhang
Gang Wang
Xiaoxiao Yu
Ben Y. Zhao
Haitao Zheng
Proceedings of ACM SIGMETRICS 2013
Awarded Best Practical Paper
[Full Text in PDF Format, 1.3MB]
Paper Abstract
Most spectrum distribution proposals today develop their allocation algorithms that use conflict graphs to capture interference relationships. The use of conflict graphs, however, is often questioned by the wireless community because of two issues. First, building conflict graphs requires significant overhead and hence generally does not scale to outdoor networks, and second, the resulting conflict graphs do not capture accumulative interference.
In this paper, we use large-scale measurement data as ground truth to
understand just how severe these issues are in practice, and whether they
can be overcome. We build "practical" conflict graphs using
measurement-calibrated propagation models, which remove the need for
exhaustive signal measurements by interpolating signal strengths using
calibrated models. These propagation models are imperfect, and we study
the impact of their errors by tracing the impact on multiple steps in the process, from calibrating propagation models to predicting
signal strength and building conflict graphs. At each step, we analyze the
introduction, propagation and final impact of errors, by comparing each
intermediate result to its ground truth counterpart generated from
measurements. Our work produces several findings. Calibrated
propagation models generate location-dependent prediction errors,
ultimately producing conservative conflict graphs. While these
"estimated conflict graphs" lose some spectrum utilization, their
conservative nature improves reliability by reducing the impact
of accumulative interference. Finally, we propose a graph augmentation
technique that addresses any remaining accumulative interference, the last
missing piece in a practical spectrum distribution system using
measurement-calibrated conflict graphs.