An improved spanning tree algorithm for baseband processing resource allocation in the baseband pool structure

Baseband processing resource allocation is an important aspect in the radio access network (RAN) based on the baseband pool structure. Minimizing the usage amount of baseband units (BBU) in the baseband pool has been proposed as a performance objective. We prove this problem is a NP-hard problem and present an Improved Spanning Tree (IST) algorithm to solve it. In our algorithm, a variable K is used to control the size of the spanning tree and reduce the computational complexity. We also define a structure called bucket to hold the best K partial solutions for every node in the tree. We prove that our algorithm is able to get the optimal solution by choosing a finite K. The simulation results show that our algorithm can get the near-optimal solutions and decrease the usage amount of BBUs in the baseband pool efficiently with a very small value of K.