Kiran Khurshid, Safwat Irteza, Adnan Ahmed Khan, S. I. Shah

Abstract: Heuristic and metaheuristic techniques are used for solving computationally hard optimization problems. Local search is a heuristic technique while Ant colony optimization (ACO), inspired by the ants' foraging behavior, is one of the most recent metaheuristic technique. These techniques are used for solving optimization problems. Multiple-Input Multiple-Output (MIMO) detection problem is an NP-hard combinatorial optimization problem. We present heuristic and metaheuristic approaches for symbol detection in multi-input multi-output (MIMO) system. Since symbol detection is an NP-hard problem so ACO is particularly attractive as ACO algorithms are one of the most successful strands of swarm intelligence and are suitable for applications where low complexity and fast convergence is of absolute importance. Maximum Likelihood (ML) detector gives optimal results but it uses exhaustive search technique. We show that 1-Opt and ACO based detector can give near-optimal bit error rate (BER) at much lower complexity levels. Comparison of ACO with another nature inspired technique, Particle Swarm Optimization (PSO) is also discussed. The simulation results suggest that the proposed detectors give an acceptable performance complexity trade-off in comparison with ML and VBLAST detectors.

Keywords: Spatial Multiplexing System, 1-Opt, ACO, Multi-Input Multi-Output Systems, Symbol Detection

Cite this paper: nullK. Khurshid, S. Irteza, A. Khan and S. Shah, "Application of Heuristic (1-Opt local Search) and Metaheuristic (Ant Colony Optimization) Algorithms for Symbol Detection in MIMO Systems," Communications and Network, Vol. 3 No. 4, 2011, pp. 200-209. doi: 10.4236/cn.2011.34023.

References

[1]   A. Paulraj, R. Nabar and D. Gore, “Introduction to Space-Time Wireless Communications,” Cambridge University Press, New York, 2003.

[2]   S. Aon Mujtaba, “TGn Sync Proposal Technical Specification,” 2005. http://www.tgnsync.org/techdocs/11-04-0889-06-000n-tgnsyncproposal-technical-specification.doc

[3]   G. J. Foschini and M. J. Gans, “On Limits of Wireless Communications in a Fading Environment When Using Multiple Antennas,” Wireless Personal Communications, Vol. 6, No. 3, 1998, pp. 311-335. doi:10.1023/A:1008889222784

[4]   E. Lumer and B. Faieta, “Diversity and Adaptation in Populations of Clustering Ants,” In: J. A. Meyer and S. W. Wilson, Eds., Proceedings of the Third International Conference on Simulation of Adaptive Behavior: From Animals to Animats, Vol. 3, MIT Press, Cambridge, 1994, pp. 501-508.

[5]   M. Campos, E. Bonabeau, G. Theraulaz and J.-L. Deneubourg, “Dynamic Scheduling and Division of Labor in Social Insects,” Adapt Behavior, Vol. 8, No. 3, 2000, pp. 83-96. doi:10.1177/105971230000800201

[6]   J. Kennedy and R. C. Eberhart, “Particle Swarm Optimization,” Proceedings of the 1995 IEEE International Conference on Neural Networks, Vol. 4, IEEE Press, Piscataway, 1995, pp. 1942-1948. doi:10.1109/ICNN.1995.488968

[7]   M. Dorigo, V. Maniezzo and A. Colorni, “Positive Feedback as a Search Strategy,” Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, 1991.

[8]   H. Bolcskei, D. Gesbert and C. Papadias, “Space-Time Wireless Systems: From Array Processing to MIMO Communications,” Cambridge University Press, New York, 2005.

[9]   A. A. Khan, M. Naeem and S. I. Shah, “A Particle Swarm Algorithm for Symbols Detection in Wideband Spatial Multiplexing Systems,” GECCO-07, 2007.

[10]   L. Zheng and D. Tse, “Diversity and Multiplexing: A Fundamental Tradeoff in Multiple Antenna Channels,” IEEE Transaction on Information Theory, Vol. 49, No. 5, May 2003, pp. 1073-1096. doi:10.1109/TIT.2003.810646

[11]   A. Goldsmith, S. A. Jafar, N. Jindal and S. Vishwanath, “Capacity Limits of MIMO Channels,” IEEE Journal on Selected Areas in Communications, Vol. 20, No. 5, June 2003.

[12]   G. J. Foschini, “Layered Space-Time Architecture for Wireless Communication in a Fading Environment When Using Multiple Antennas,” Bell Labs Technical Journal, Vol. 1, No. 2, 1996, pp. 41-59. doi:10.1002/bltj.2015

[13]   F. Glover and G. Kochenberger, “Handbook of Metaheuristics,” Kluwer Academic, Norwell, 2002.

[14]   S. Verdu, “Multiuser Detection,” Cambridge University Press, New York, 1998.

[15]   M. Dorigo, V. Maniezzo and A. Colorni, “Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 26, No. 1, 1996, pp. 29-41. doi:10.1109/3477.484436

[16]   S. Haykin, “Adaptive Filter Theory,” 3rd Edition, Prentice-Hall, Upper Saddle River, 1996.

[17]   A. Sayed, “Fundamentals of Adaptive Filtering,” Wiley-IEEE Press, Piscataway, 2003.

[18]   V. Tarokh, H. Jafarkhani and A. R. Calderbank, “Space-Time Block Codes for Orthogonal Designs,” IEEE Transactions on Information Theory, Vol. 45, No. 5, 1996, pp. 1456-1466. doi:10.1109/18.771146

[19]   C. Blum and A. Roli, “Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison,” ACM Computing Surveys, Vol. 35, No. 3, 2003, pp. 268-308. doi:10.1145/937503.937505

[20]   J. Handl, J. Knowles and M. Dorigo, “Ant-Based Clustering and Topographic Mapping,” Artificial Life, Vol. 12, No. 1, 2006, pp. 35-62. doi:10.1162/106454606775186400

[21]   H. H. Hoos and T. Stutzle, “Stochastic Local Search: Foundations and Applications,” Elsevier, Amsterdam, 2004.

[22]   F. Glover, “Future Paths for Integer Programming and Links to Artificial Intelligence,” Computers & Operations Research, Vol. 13, No. 5, 1986, pp. 533-549. doi:10.1016/0305-0548(86)90048-1

[23]   J. L. Deneubourg, S. Aron, S. Goss and J. M. Pasteels, “The Self-Organizing Exploratory Pattern of the Argentine Ant,” Journal of Insect Behavior, Vol. 3, No. 2, 1990, pp. 159-168. doi:10.1007/BF01417909

[24]   M. Dorigo and T. Stutzle, “Ant Colony Optimization,” MIT Press, Cambridge, 2004.

[25]   G. H. Golub and C. F. V. Loan, “Matrix Computations,” 3rd Edition, John Hopkins University Press, Baltimore, 1996.