Minimum separation clustering algorithm with high separation degree in ultra-dense network

Ultra-dense network (UDN) can effectively improve the network throughput by increasing the deployment density of base stations. However, due to the randomness of the large number of base station deployments, UDN will lead to huge computational complexity and signaling overhead. The existing clustering algorithms cannot obtain effective clustering results in extremely dense scenarios. In this paper, we propose a minimum separation clustering (MSC) algorithm, which selects the split base stations (SBSs) to connect the multiple dense cluster base stations (CBSs). SBSs can reduce the interference between CBS clusters by using different radio resources from CBSs, because it has higher priority in the resource allocation procedure. Furthermore, the traditional clustering evaluation indexes such as the sum of square error are not applicable to UDN where the base stations are deployed randomly, and hence we design the separation degree function, which evaluates the clustering effect from the compactness within a cluster and the dispersion between different clusters. Simulation results show that the proposed algorithm can not only reduce the proportion of SBSs so as to improve the spectral efficiency, but also reduce the inter-cluster interference and network scale.