User Association and Load Balancing Based on Monte Carlo Tree Search

Abstract

The user association algorithm for 5G ultra-dense heterogeneous networks (UD-HetNets) comprising multi-tier base stations is becoming increasingly complex. In UD-HetNets, small base stations (SBSs) play an important role in offloading data traffic of user equipments (UEs) requiring high data rate from macro base stations (MBSs) to enhance the quality of services (QoS) of them. However, the traditional cell range expansion (CRE) scheme poses a risk of congestion in certain SBSs and the emergence of UEs monopolizing resources in less congested SBSs, which causes SBS load imbalance and decreases fairness performance. At the same time, determining the optimal user association result for load balancing, considering all possible combinations of associations between UEs and SBSs, leads to prohibitively high computational complexity. To obtain a near-optimal user association solution with manageable computational complexity, in this paper, we propose a heuristic algorithm based on Monte Carlo tree search (MCTS) for user association in UD-HetNet. We model the user association problem as a combinatorial optimization problem and provide a detailed design of the MCTS steps to solve this NP-hard problem. The MCTS algorithm obtains a near-optimal UEs-SBSs combination in terms of load balancing and maximizes the fairness of the overall network. This combination derived from the proposed algorithm aims to achieve load balancing among SBSs and mitigate resource monopolization among UEs. The simulation results show that the proposed algorithm outperforms conventional user association schemes in terms of fairness. As a result, compared to traditional CRE schemes, the proposed method can provide good performance to the UEs receiving data rates of the bottom 50%. Furthermore, the gap between optimal and heuristic solutions does not exceed 4%. Due to its manageable computational complexity, the proposed algorithm can be implemented as an xApp on the O-RAN near-real-time RAN intelligent controller (RIC).

Keywords

• User association
• ultra-dense heterogeneous network
• load balancing
• Monte Carlo tree search
• cell range expansion