A multi-cell graph based dynamic resource allocation scheme for multi-user wireless networks

Dynamic resource allocation being a computationally difficult problem, static spectrum management is more commonly used in large-scale networks. The combination of virtualization technologies, where powerful centralized allocation algorithms can be implemented, and recent advances in graph coloring algorithms prompts the revisiting of this view. We describe a new graph based framework to maximize the number of simultaneously communicating mobiles in a wireless network. Since the considered problem is NP-hard, we propose various heuristic algorithms and analyze their performance, in comparison with standard decentralized channel assignment strategies such as Fractional Frequency Reuse (FFR). We consider the LTE uplink and downlink with the WINNER channel as the reference model. We show that for blocking probabilities below 2%, our scheme typically increases the number of mobile users by 25%. For example with 25 base stations and 120 channels, running the resource allocation scheme takes one second on a PC and permits to increase the number of mobiles requiring one single channel each from 750 to 950, a 25% increase in efficiency compared to FFR.