Resource Allocation in Radio Networks by Graph Coloring and Non-Smooth Optimization

Abstract

The number of devices connected to the internet is rapidly increasing and the demand for higher bandwidth is likely to increase in the future. In this thesis we will look at methods for channel allocation and signal strength adjustments for Wi-Fi routers, and how this will influence the interference and signal quality of Wi-Fi networks. We look at continuous and discrete optimization methods for signal strengths and channel allocation respectively. In addition, we utilize graph coloring algorithms as a method of assigning a channel to a Wi-Fi router.

From this we present some schemes for channel allocation and signal strength adjustments. Two graph coloring algorithms are presented, three schemes alternating between graph coloring and signal strength optimization are presented and two discrete optimization algorithms for the channel allocations are presented.

We perform tests where we first compare the two graph coloring algorithms, next we compare the schemes alternating between graph coloring and signal strength optimization, and in the end we compare the schemes where both optimization of the channel allocation and the signal strengths are implemented. Our results shows that utilizing optimization for both the channel allocation and the signal strengths leads to higher signal quality and less interference on Wi-Fi networks compared to the status quo.