Quantized conflict graphs for wireless network optimization

Conflict graph has been widely used for wireless network optimization in dealing with the issues of channel assignment, spectrum allocation, links scheduling and etc. Despite its simplicity, the traditional conflict graph suffers from two drawbacks. On one hand, it is a rough representation of the interference condition, which is inaccurate and will cause suboptimal results for wireless network optimization. On the other hand, it only defines the interference between two entities, which neglects the accumulative effect of small amount interference. In this paper, we propose the model of quantized conflict graph (QCG) to tackle the above issues. The properties, usage and construction methods of QCG are explored. We show that in its matrix form, a QCG owns the properties of low-rank and high-similarity. These properties give birth to three complementary QCG estimation strategies, namely low-rank approximation approach, similarity based approach, and comprehensive approach, to construct the QCG efficiently and accurately from partial interference measurement results. We further explore the potential of QCG for wireless network optimization by applying QCG in minimizing the total network interference. Extensive experiments using real collected wireless network are conducted to evaluate the system performance, which confirm the efficiency of the proposed algorithms.