A performance-complexity analysis of four suboptimal SDMA algorithms

Space division multiple access (SDMA) is a promising solution to improve the spectral efficiency of future mobile radio systems. However, finding the group of mobile stations (MSs) that maximizes the system capacity using SDMA is a complex combinatorial problem, which can only be assuredly solved through an exhaustive search (ES). Because an ES is usually too complex, several suboptimal SDMA algorithms have been proposed. SDMA algorithms mainly differ on the grouping metrics they employ to quantify the spatial compatibility among MSs and on the grouping algorithm used to build the SDMA groups while avoiding ESs. In this work, the performance-complexity trade-off of four SDMA algorithms is investigated in terms of the average system capacity they achieve and on the number of operations they require. Expressions for the computational complexity of the algorithms are presented and it is shown that the algorithms proposed by the authors by Maciel and Klein (2007) attain almost the same average system capacity with comparable or lower complexity than other algorithms considered for benchmarking.