Abstract
This paper analyzes the complexity-performance trade-off of several heuristic near-optimum multiuser detection (MuD) approaches applied to the uplink of synchronous single/multiple-input multiple-output multicarrier code division multiple access (S/MIMO MC-CDMA) systems. Genetic algorithm (GA), short term tabu search (STTS) and reactive tabu search (RTS), simulated annealing (SA), particle swarm optimization (PSO), and 1-opt local search (1-LS) heuristic multiuser detection algorithms (Heur-MuDs) are analyzed in details, using a single-objective antenna-diversity-aided optimization approach. Monte- Carlo simulations show that, after convergence, the performances reached by all near-optimum Heur-MuDs are similar. However, the computational complexities may differ substantially, depending on the system operation conditions. Their complexities are carefully analyzed in order to obtain a general complexity-performance framework comparison and to show that unitary Hamming distance search MuD (uH-ds) approaches (1-LS, SA, RTS and STTS) reach the best convergence rates, and among them, the 1-LS-MuD provides the best trade-off between implementation complexity and bit error rate (BER) performance.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aarts E.H.L., Lenstra J.K. (2003) Local search in combinatorial optimization (536 pp). Princeton University Press, USA
Abrão, T., Ciriaco, F., & Jeszensky, P. J. E. (2004). Evolutionary programming with cloning and adaptive cost function applied to multi-user ds-cdma systems. In ISSSTA’04 (pp. 160–163), Sydney, Australia.
Abrão, T., Ciriaco, F., Oliveira, L. D., Angélico, B. A., Jeszensky, P. J. E., & Casadevall, F. (2008). Weighting particle swarm optimization simo mc-cdma multiuser detectors. In ISSSTA’08—10th international symposium on spread spectrum techniques and applications (pp. 69–73). Bologna, Italy.
Bashir, S., Khan, A. A., Naeem, M., & Shah, S. I. (2007). An application of ga for symbol detection in mimo communication systems. In Third international conference on natural computation ICNC 2007 (Vol. 2, pp. 404 – 410). Haikou.
Battiti R., Tecchioli G. (1994) The reactive tabu search. ORSA, Journal of Computing 6: 126–140
Cerny V. (1985) Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization theory and Application 45: 41–51
Ciriaco F., Abrão T., Jeszensky E. P. J. (2006) Ds/cdma multiuser detection with evolutionary algorithms. Journal Of Universal Computer Science, 12(4): 450–480
Ergün C., Hacioglu K. (2000) Multiuser detection using a genetic algorithm in cdma communications systems. IEEE Transactions on Communications 48: 1374–1382
Glover F. (1977) Heuristic for integer programming using surrogate contraints. Decision Sciences 8: 156–166
Glover F. (1986) Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13: 533–549
Glover F., Laguna M. (1997) Tabu search. Kluwer Academic Publishers, Boston
Goldberg D.E. (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading, MA
Hara S., Prasad R. (1997) Overview of multicarrier CDMA. IEEE Communications Magazine 35(12): 126–133
Jalden J., Ottersten B. (2005) On the complexity of sphere decoding in digital communications. IEEE Transactions on Signal Processing 53(4): 1474–1484
Jiang M., Hanzo L. (2007) Multiuser mimo-ofdm for next-generation wireless systems. Proceedings of the IEEE 95(7): 1430–1469
Jiang, Y., Zhong, Z., Yang, J., & Zhang, M. (2007). Sub-optimal multiuser detector using a time-varying gain chaotic simulated annealing neural network. In ICNC 2007—Third international conference on natural computation (Vol. 1, pp. 305–309). Haikou.
Katayama K., Narihisa H. (2001) Performance of simulated annealing-based heuristic for unconstrained binary quadratic programming problem. European Journal of Operational Research 134: 103–119
Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In IEEE international conference on neural networks (pp. 1942–1948).
Khan, A., Bashir, S., Naeem, M., & Shah, S. (2006). Heuristics assisted detection in high speed wireless communication systems. In IEEE multitopic conference (pp. 1–5). Islamabad.
Kirkpatrick S., Gellat C.D., Vecchi M.P. (1983) Optimization by simulated annealing. Science 220: 671–680
Lim H.S., Venkatesh B. (2003) An efficient local search heuristics for asynchronous multiuser detection. IEEE Communications Letters 7(6): 299–301
Ma W.K., Davidson T.N., Wong K.M., Luo Z.Q., Ching P.C. (2002) Quasi-maximum-likelihood multiuser detection using semi-definite relaxation with applications to synchronous cdma. IEEE Transactions on Signal Processing 50(4): 912–922
Mitchell M. (1998) An introduction to genetic algorithms. MIT Press, Cambridge
Mobasher, A., Taherzadeh, M., Sotirov, R., & Khandani, A. K. (2005). A near maximum likelihood decoding algorithm for mimo systems based on semi-definite programming. In ISIT 2005—International symposium on information theory (pp. 1686–1690). Adelaide, SA.
Moshavi S. (1996) Multi-user detection for ds-cdma communications. IEEE Communication Magazine 34: 132–136
Oliveira L.D., Ciriaco F., Abrão T., Jeszensky E.P. J. (2009) Local search multiuser detection. AEÜ International Journal of Electronics and Communications 63(4): 259–270
Oliveira, L. D., Ciriaco, F., Abrão, T., & Jeszensky, P. J. E. (2006). Particle swarm and quantum particle swarm optimization applied to ds/cdma multiuser detection in flat rayleigh channels. In ISSSTA’06—IEEE international symposium on spread spectrum techniques and applications (pp. 133–137). Manaus, Brazil.
Oliveira, L. D., Ciriaco, F., Abrão, T., & Jeszensky, P. J. E. (2007). Simplified local search algorithm for multiuser detection in multipath rayleigh channels. In The 16th IST mobile and wireless communications summit (pp. 1–4). Budapest, Hungary.
Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (1992) Numerical recipes in C: The art of scientifc computing. Cambridge University Press, Cambridge
Tan, P. H. (2001). Multiuser detection in cdma-combinatorial optimization methods. Master’s thesis, Chalmers University of Technology, Göteborg.
Tan P.H., Rasmussen L.K. (2001) The application of semidefinite programming for detection in cdma. IEEE Journal on Selected Areas in Communication 19(8): 1442–1449
Vardhan K.V., Mohammed K., Chockalingan A., Rajan B.S. (2008) A low-complexity detector for large mimo systems and multicarrier cdma systems. IEEE Journal on Selected Areas in Communication 26(3): 473–485
Verdú S. (1998) Multiuser Detection. Cambridge University Press., New York
Wang X.M., Lu W.S., Antoniou A. (2003) A near-optimal multiuser detector for ds-cdma using semidefinite programming relaxation. IEEE Transactions on Signal Processing 51(9): 2446–2450
Wei, H., & Hanzo, L. (2004). Reduced-complexity near-optimum genetic algorithm assisted multiuser detection for synchronous multicarrier cdma. In IEEE 59th vehicular technology conference (Vol. 3, pp. 1717–1721).
Yen K., Hanzo L. (2003) Antenna-diversity-assisted genetic-algorithm-based multiuser detection schemes for synchronous cdma systems. IEEE Transactions On Communications 51(3): 366–370
Zhao, H., Long, H., & Wang, W. (2006). Pso selection of surviving nodes in qrm detection for mimo systems. In GLOBECOM—IEEE global telecommunications conference (pp. 1–5). San Francisco, CA.
Zhao, Y., & Zheng, J. (2004). Particle swarm optimization algorithm in signal detection and blind extraction. In IEEE (Ed.), 7th international symposium on parallel architectures, algorithms and networks (pp. 37–41).
Zong P., Wang K., Bar-Ness Y. (2001) Partial sampling mmse interference suppression in asynchronous mc-cdma systems. IEEE Journal on Selected Areas in Communication 9(8): 1605–1613
Acknowledgements
This work was partially supported by the Brazilian CAPES Agency Grants, under Fellowship code BEX0556/07-6.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
Part of this paper was presented at ISSSTA’08—The 10th International Symposium on Spread Spectrum Techniques and Applications, Bologna, Italy, Aug. 2008.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Abrão, T., de Oliveira, L.D., Ciriaco, F. et al. S/MIMO MC-CDMA Heuristic Multiuser Detectors Based on Single-Objective Optimization. Wireless Pers Commun 53, 529–553 (2010). https://doi.org/10.1007/s11277-009-9701-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11277-009-9701-8