nach oben

Journal of Combinatorial Optimization

Erschienen in:

28.06.2016

A new effective branch-and-bound algorithm to the high order MIMO detection problem

verfasst von: Ye Tian, Ke Li, Wei Yang, Zhiyong Li

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper develops a branch-and-bound method based on a new convex reformulation to solve the high order MIMO detection problem. First, we transform the original problem into a \(\{-1,1\}\) constrained quadratic programming problem with the smallest size. The size of the reformulated problem is smaller than those problems derived by some traditional transformation methods. Then, we propose a new convex reformulation which gets the maximized average objective value as the lower bound estimator in the branch-and-bound scheme. This estimator balances very well between effectiveness and computational cost. Thus, the branch-and-bound algorithm achieves a high total efficiency. Several simulations are used to compare the performances of our method and other benchmark methods. The results show that this proposed algorithm is very competitive for high accuracy and relatively good efficiency.

Vorheriger Artikel Bounds for the traveling salesman paths of two-dimensional modular lattices

Nächster Artikel A new upper bound for the online square packing problem in a strip

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Billionnet A, Elloumi S (2007) Using a mixed integer quadratic programming solver for the unconstrained quadratic 0–1 problem. Math Program 109:55–68MathSciNetCrossRefMATH

Bunse-Gerstner A, Kubaliń D, Vossen G, Wilczek D (2010) \(h_2\)-norm optimal model reduction for large scale discrete dynamical MIMO systems. J Comput Appl Math 233:1202–1216MathSciNetCrossRefMATH

Damen M, El Gamal H, Caire G (2003) On maximum-likelihood detection and the search for the closest lattice point. IEEE Trans Inf Theory 49:2389–2402MathSciNetCrossRefMATH

Fincke U, Pohst M (1985) Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math Computat 44:463–471MathSciNetCrossRefMATH

El Gamal H, Caire G, Damen M (2004) Lattice coding and decoding achieve the optimal diversity-multiplexing tradeoff of MIMO channels. IEEE Trans Inf Theory 50:968–985MathSciNetCrossRefMATH

Goldberger J, Leshem A (2011) MIMO detection for high-order QAM based on a Gaussian tree approximation. IEEE Trans Inf Theory 57:4973–4982MathSciNetCrossRef

Grant M, Boyd S (2010) CVX: matlab Software for Disciplined Programming. Version 1.2. http://cvxr.com/cvx

Jaldén J, Elia P (2010) DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models. IEEE Trans Inf Theory 56:4765–4780MathSciNetCrossRef

Jaldén J, Ottersten B (2005) On the complexity of sphere decoding in digital communications. IEEE Trans Signal Process 53:1474–1484MathSciNetCrossRef

Kisialiou M, Luo Z (2005) Performance Analysis of Quasi-Maximum-Likelihood Detector Based on Semidefinite Programming. In: Proceedings of the IEEE International Conference on Acoustics Speech and Signal Process, vol III, pp 433–436

Liu S, Ling C, Stehlé D (2011) Decoding by sampling: A randomized lattice algorithm for bounded-distance decoding. IEEE Trans Inf Theory 57:5933–5945MathSciNetCrossRef

Lu C, Guo X (2015) Convex reformulation for binary quadratic programming problems via average objective value maximization. Optim Lett 9:523–535MathSciNetCrossRefMATH

Luzzi L, Stehlé D, Ling C (2013) Decoding by embedding: Correct decoding radius and DMT optimality. IEEE Trans Inf Theory 59:960–2973MathSciNetCrossRef

Ma W, Davidson T, Wong K, Ching P (2004) A block alternating likelihood maximization approach to multiuser detection. IEEE Trans Signal Process 52:2600–2611MathSciNetCrossRef

Ma W, Su C, Jaldém J, Chang T, Chi C (2009) The equivalence of semidefinite relaxation MIMO detectors for higher-order QAM. IEEE J Select Top Signal Process 3:1038–1052CrossRef

Mao Z, Wang X, Wang X (2007) Semidefinite programming relaxation approach for multiuser detection of QAM signals. IEEE Trans Wire Commun 6:4275–4279CrossRef

Pan J, Ma W, Jaldém J (2014) MIMO detection by Lagrangian dual maximum-likilihood relaxation: Reinterpreting regularized lattice decoding. IEEE Trans Signal Process 62:511–524MathSciNetCrossRef

Pardalos P, Rodgers G (1990) Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45:131–144MathSciNetCrossRefMATH

Sidiropoulos N, Luo Z (2006) A semidefinite relaxation approach to MIMO detection for higher-order constellations. IEEE Signal Process lett 13:525–528CrossRef

Singh A, Elia P, Jaldén J (2012) Achieving a vanishing SNR gap to exact lattice decoding at a subexponential complexity. IEEE Trans Inf Theory 58:3692–3707MathSciNetCrossRef

Taherzadeh M, Khandani A (2010) On the limitations of the naive lattice decoding. IEEE Trans Inf Theory 56:4820–4826MathSciNetCrossRef

Tan P, Rasmussen L (2001) The application of semidefinite programming for detection in CDMA. IEEE J Select Areas Commun 19:1442–1449CrossRef

Tian Y, Dang JF (2015) MIMO detection for high order QAM by canonical dual approach. J Appl Math. doi:10.1155/2015/201369 MathSciNet

Tse D, Viswanath P (2005) Fundamentals of wireless communication. Cambridge University Press, CambridgeCrossRefMATH

Vandenberghe L, Boyd S (1996) Semidefinite programming. SIAM Rev 38:49–95MathSciNetCrossRefMATH

Verdú S (1998) Multiuser detectection. Cambridge University Press, Cambridge

Viterbo E, Boutros J (1999) A universal lattice code decoder for fading channels. IEEE Trans Inform Theory 45:1639–1642MathSciNetCrossRefMATH

Wang Z, Fang SC, Gao D, Xing W (2008) Global extremal conditions for multi-integer quadratic programming. J Ind Manage Optim 4:213–225MathSciNetCrossRefMATH

Wiesel A, Eldar Y, Shamai S (2005) Semidefinite relaxation for detection of 16-QAM signaling in MIMO channels. IEEE Signal Process Lett 13:525–528

Wübben D, Seethaler D, Jaldén J, Matz G (2011) Lattice reduction. IEEE Signal Process Mag 28:70–91CrossRef

Titel: A new effective branch-and-bound algorithm to the high order MIMO detection problem
verfasst von: Ye Tian
Ke Li
Wei Yang
Zhiyong Li
Publikationsdatum: 28.06.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-016-0045-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2017

Paired-domination number of claw-free odd-regular graphs

A tighter insertion-based approximation of the crossing number

The solution of a generalized secretary problem via analytic expressions

A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance

Optimal RSUs deployment with delay bound along highways in VANET

A new upper bound for the online square packing problem in a strip

Premium Partner