Advanced algorithms in CDMA detection

Abstract

Code-division multiple-access (CDMA) technology has been chosen for the air interface of the next generation (3G) wireless systems. However, CDMA-based systems are subject to the multiple access interference (MAI) which degrades the performance of the existing systems (e.g. IS-95). Among all techniques proposed to combat MAI, multiuser detection (MUD) is the most effective one, and it has been widely studied for the last fifteen years. Unfortunately, the optimum MUD detector based on exhaustive search is extremely complex for practical implementations with today's technologies. Thus, the focus of most of the researches in MUD detection was to find suboptimal algorithms that provide reliable performance and insure polynomial complexity. However, there still a large gap between the performance of the suboptimal detectors and that of the optimal one. Since the MUD problem can be considered as a quadratic optimization problem with binary or integer constraints; consequently, many advanced methods in binary quadratic programming, either heuristic or exact methods, can be applied to efficiently approximate the optimal multiuser detector performance. In this thesis work new detection algorithms for MUD, based on heuristic algorithms, have been developed. The memetic algorithm, the particle swarms optimization algorithm, and the combination of tabu search algorithm with local search algorithm were used to develop new detection structures that fairly approximate the performances of the optimal MUD detector with a considerably reduced implementation/computational complexity. Moreover, other existing heuristic based detectors are studied for comparison purposes. The performances of these detectors are compared to those of the conventional detector, the decorrelating detector, and the branch-and-bound based optimal detector. Keywords. CDMA, Multiuser detection (MUD), Multiple access interference (MAI), Heuristic algorithms, Genetic algorithm, Local search algorithm, Memetic algorithm, Particle swarm optimization algorithm, Tabu search algorithm, Branch-and-bound algorithm, Conventional detector, Decorrelating detector.