Weighted coloring based channel assignment for WLANs

We propose techniques to improve the usage of wireless spectrum in the context of wireless local area networks (WLANs) using new channel assignment methods among interfering Access Points (APs). We identify new ways of channel re-use that are based on realistic interference scenarios in WLAN environments. We formulate a weighted variant of the graph coloring problem that takes into account realistic channel interference observed in wireless environments, as well as the impact of such interference on wireless users. We prove that the weighted graph coloring problem is NP-hard and propose scalable distributed algorithms that achieve significantly better performance than existing techniques for channel assignment. We evaluate our algorithms through extensive simulations and experiments over an in-building wireless testbed.