Groupe d’études et de recherche en analyse des décisions


Graph coloring to maximize the number of communicating mobiles in wireless networks

, et

Until recently, graph coloring being a computationally difficult problem, completely dynamic channel allocation was not considered 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 graph coloring model for maximizing 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. We consider the LTE 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 25 base stations with 120 channels. For small networks, e.g. 10 base stations and 45 mobile users, the algorithms are very close to the optimal channel allocation. The scalable resource allocation scheme has been run on a PC for a thousand users and 25 base stations with 120 channels.

, 19 pages