Practical Conflict Graphs in the Wild
Xia Zhou
Zengbin Zhang
Gang Wang
Xiaoxiao Yu
Ben Y. Zhao
Haitao Zheng
IEEE/ACM Transactions on Networking, Vol. 23, No. 3, Pgs 824-835, June 2015
[Full Text in PDF Format, 1.7MB]
Paper Abstract
Today, most spectrum allocation algorithms use conflict graphs to capture
interference conditions. The use of conflict graphs, however, is often
questioned by the wireless community for two reasons. First, building accurate
conflict graphs requires significant overhead, and hence does not scale to
outdoor networks. Second, conflict graphs cannot properly capture accumulative
interference. In this paper, we use large-scale measurement data as ground truth
to understand how severe these problems are 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. Calibrated models are
imperfect, and we study the impact of their errors on multiple steps in the
process, from calibrating propagation models, predicting signal strengths, to
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. Our work produces several findings. Calibrated
propagation models generate location-dependent prediction errors, ultimately
producing conservative conflict graphs. While these "estimated conflict graphs"
lower spectrum utilization, their conservative nature improves reliability by
reducing the impact of accumulative interference. Finally, we propose a graph
augmentation technique to address remaining accumulative interference.