[BACK]
Computer Systems Science & Engineering
DOI:10.32604/csse.2022.019734		 images
Article

Symbol Detection Based on Back Tracking Search Algorithm in MIMO-NOMA Systems

M. Nuri Seyman*

Bandirma Onyedi Eylul University, Enginering and Natural Sciences Faculty, Bandirma, 10200, Turkey
*Corresponding Author: M. Nuri Seyman. Email: mseyman@bandirma.edu.tr
Received: 23 April 2021; Accepted: 27 May 2021

Abstract: One of the most important methods used to cope with multipath fading effects, which cause the symbol to be received incorrectly in wireless communication systems, is the use of multiple transceiver antenna structures. By combining the multi-input multi-output (MIMO) antenna structure with non-orthogonal multiple access (NOMA), which is a new multiplexing method, the fading effects of the channels are not only reduced but also high data rate transmission is ensured. However, when the maximum likelihood (ML) algorithm that has high performance on coherent detection, is used as a symbol detector in MIMO NOMA systems, the computational complexity of the system increases due to higher-order constellations and antenna sizes. As a result, the implementation of this algorithm will be impractical. In this study, the backtracking search algorithm (BSA) is proposed to reduce the computational complexity of the symbol detection and have a good bit error performance for MIMO-NOMA systems. To emphasize the efficiency of the proposed algorithm, simulations have been made for the system with various antenna sizes. As can be seen from the obtained results, a considerable reduction in complexity has occurred using BSA compared to the ML algorithm, also the bit error performance of the system is increased compared to other algorithms.

Keywords: MIMO-NOMA; ML algorithm; heuristic; BSA Algorithm

1  Introduction

Insufficient frequency spectral resources are the biggest obstacle to high-rate data transmission. Interest in the use of the NOMA technique, which is a kind of multi-carrier system that provides high-rate data transmission by using spectral resources efficiently, has increased considerably in recent years. In addition to providing spectral efficiency of NOMA, its resistance to multipath damping is another important advantage of the system. Therefore, the NOMA technique also forms the basis of 5th generation communication systems [1].

The most significant drawback to being considered in the multiplexing methods is the destructive effects caused by multipath fading. One of the most important ways to deal with these destructive effects is to use a multi-antenna transceiver. By using NOMA combined with multiple antenna structures, not only high-rate data transmission is provided but also the destructive effects caused by fading are minimized [2–7]. However, symbol detection is a crucial process to detect symbols coherently in wireless communication systems [8–21]. Therefore, various algorithms such as zero-forcing (ZF), the vertical Bell Laboratories layered spice-time (VBLAST), and ML are used for symbol detection [8–17]. Although the ML algorithm is the best performing algorithm among these since the computational complexity of this algorithm increase in proportion to the increasing number of antennas, the practicality of this algorithm for the MIMO systems is very low [12]. Therefore, many studies take place in the literature on reducing the computational complexity problem of ML algorithms [13–16]. In the study of [14]; a differential metrics-based ML algorithm that does not require a computational complexity such as the QR decomposition matrix is proposed. In the study [15], an algorithm is for reducing the QR decomposition complexity, which is a pre-processing method for symbol detection, in proportion to the increase in antenna numbers. The authors of [17] in sparse code multiple access systems, modified single tree search scheme is proposed to soft outputs. From these studies, it can be seen that complexity is a serious problem in the detection of data and as a result, the availability of algorithms is restricted.

Many difficult real-time engineering problems have been solved by using heuristic algorithms inspired by the behavior of many events or creatures in nature [18–30]. With the help of heuristic algorithms such as genetic algorithm (GA), particle swarm optimization (PSO), and differential evolution algorithm (DE), ML estimation is computed recursively for optimizing subspace search. Because of ML algorithm needs computation of correlation matrix and matrix inversion, taking advantage of heuristic algorithms we can overcome these computational challenges [18–21]. In [18] GA has been proposed for the ML algorithm in pulse amplitude modulation (PAM) systems. Also, in the studies [19–20], they have obtained the results with less computational complexity close to the ML algorithm, using PSO for spatial multiplexing systems. In the study of [21], it is seen that the complexity of the symbol detector in the MIMO-OFDM system is reduced considerably by utilizing DE. BSA algorithm is a new evolutionary algorithm that provides more efficient solutions with fewer parameters and has recently been used in wide application areas [22]. some studies are using BSA in many areas such as antenna design, medicine, meteorology, Complementary metal oxide semiconductor (CMOS) circuit design, and chemistry [22–29]. When we consider the literature, there is no heuristic-based proposal to eliminate the disadvantages of ML algorithms in MIMO-NOMA systems.

In this study, the BSA is proposed for symbol detection in MIMO-NOMA systems with various transmitter and receiver antennas. To highlight the complexity reduction and bit error rate (BER) efficiency of the proposal, the proposed BSA is compared to the classical algorithms such as ML, ZF and VBLAST and heuristic algorithms such as GA, PSO. The simulation results and complexity analysis demonstrate that our proposal is an effective solution for symbol detection.

This paper is organized as follows, Section 2 introduces the concept of the MIMO-NOMA system and ML scheme. The architecture of the backtracking search algorithm for data detection is described in Section 3. The simulation results and conclusion are drawn in Section 4 and Section 5 respectively.

2  MIMO-NOMA System Model

NOMA combined with MIMO is a new multicarrier modulation system that provides orthogonal access to the users either in frequency, time, space, or code. For this scheme, each user uses the same time and frequency where they are selected considering the power levels. In NOMA, the successive interference cancellation (SIC) is used to reserve the users both in the downlink and uplink [1–7].

When we consider a MIMO-NOMA system consists of N transmitter and M receiver antenna, the signal is transmitted in the same frequency and time domain but various power levels as;

s=Px→ (1)

Where x→ is Nx1 symbol vector, P is NxN precoding matrix used by the base station.

x→=[γ1,1x1,1+…+γ1,2x1,2⋮γN,1xN,1+…+γN,2xN,2] (2)

Where xn,k is information signal to belongs to the kth user in the nth cluster and γn,k is NOMA power allocation coefficient. The observed signal yn,k for kth user and nth cluster is

yn,k=Hn,kPx→+nn,k (3)

Where Hn,k channel matrix of base station (BS) and the kth user in nth cluster. After the detection vector is applied, the signal can be re-written as;

vn,kHyn,k=vn,kHHn,kPx→+vn,kHnn,k (4)

Where (.)H is the Hermitian transpose operation. Denote the nth of the column of P by pn . The signal can be rewritten as in Eq. (5)

vn,kHyn,k=vn,kHHn,kpn(γn,1xn,1+…+γn,Kxn,K)+∑m=1,n≠mNvn,kHHn,kpnxn→+vn,kHnn,k (5)

As can be seen from Eq. (6) received signal is a combination of desired and interference signal [2–3]. Interference signals consist of two parts called intra-cluster interference and inter-cluster interference [4]

vn,kHyn,k=vn,kHHn,kpnγn,kxn,k⏟desiredsignal+vn,kHHn,k∑j=1j≠kKpnγn,jxn,j⏟Intra−clusterInterference+vn,kHHn,k∑i=1j≠nMpixi→⏟Inter−ClusterInterference+vn,kHnn,k⏟noise (6)

Channel gains can be presented as follows,

|vn,kHHn,1pn|2≥|vn,2HHn,2pn|2n∈{1,2,…,N} (7)

Besides PA coefficients are ordered as

γ1,1≤…≤γ1,K (8)

To detect symbol, an ML algorithm can be implemented by maximizing the (9) metric;

x∗=Δarg⁡maxD(v|x) (9)

Data can be detected by using the Eq. (10) which minimize the squared Euclidian distance to the target vector,

x∗=arg⁡min‖v−xH‖2 (10)

For ML detection CN possible combinations must be searched [12].

3  Back Tracking Search Algorithm for Symbol Detection

BSA, is a population-based evolutionary algorithm that provides to make the right choice from a variety of ways to reach a goal or search for a value.

BSA is distinct from other similar algorithms in that it has a memory for storing a population from a previous generation, which is then used to create the search-direction matrix for the next iteration. Besides, Since BSA has a basic structure, it is efficient, fast, and capable of solving multidimensional problems. The mix-rate, which is the only control parameter in BSA, decreases the sensitivity of the inceptive values to the algorithm’s parameters greatly. Initialization, selection I, mutation, crossover, and selection II are the five processing stages in BSA [22].

The processing steps of the BSA are given in Fig. 1.

images

Figure 1: Process steps of BSA

For the symbol detection problem, in the BSA population of the individuals corresponds to the symbols. At the first steps of BSA, the individuals Gij ( j=1,2,…,D) which represents the solution of the problem are initialized randomly between the predefined upper and lower constraints as

Gi,j∼U(lowj,upj)i=1,2,…,Nj=1,2,…,D (11)

Where N population is size and D is the number of control parameters. In selection 1 step, the historical population which is used for determination of search direction is obtained as;

oldGi,j∼U(lowj,upj) (12)

The population is updated at the beginning of each epoch as follows

ifa<bthenoldG:=G|a,b∼U(0,1) (13)

Where a and b are uniform real numbers between [0–1] to check whether Pold is selected from the previous generation or not.

BSA alters a randomly selected population from the previous generation as the old population and keeps this old population in memory until it changes.

Population members are shuffled using the permitting function as follows;

oldG:=permuting(oldG) (14)

The mutation process is then performed using the Eq. (15).

mutant=G+F.(oldG−G) (15)

where F is a real number that is used for control of amplification in search space.

The purpose of mutation is to include the experiences of previous generations in the process. In the crossover step, the final version of the trial population (T) is produced. In selection-II, Gi is updated using Ti that have better fitness values than Pi . If the best value of G is better than the global minimum, the solution value is updated as the Pbest [22]. For symbol detection, these processes are repeated until the stopping criteria as 10−2.

4  Simulation Results

The performance evaluation of the algorithms has been made by considering the systems with 10 MHz bandwidth and 16QAM modulation for various antennas size over the channel. The NOMA system and channel parameters are given in Tabs. 1 and 2 respectively.

images

images

Besides the parameters of the proposed heuristic algorithms for data detection are given in Tab. 3.

images

A comparison between the results of the proposed method to other detectors for a NOMA system with a 2 × 2 antennas array is shown in Fig. 2.

Although it can be observed from Fig. 2 that the ML algorithm is the best performing algorithm, increasing the size of transmitter and receiver antennas makes this algorithm impractical in terms of complexity. Besides, the proposed BSA algorithm has better BER values than not only classical but also heuristic algorithms. At 10−1 BER, the BSA algorithm has a gain of 14 dB better than the worst-performing ZF and 2 dB better than the PSO with the closest performance to it. Also, the difference between BSA and VBLAST at a value of 20 dB signal to noise ratio (SNR) is around 10−1.

images

Figure 2: SNR versus BER performance of detectors for 2 × 2 NOMA system

The BER performance of the proposed detector for the systems with 4 × 4 antennas is shown in Fig. 3. It can be seen from Fig. 3 that to have BER = 10−2 GA requires 18 dB, PSO requires 16.5 dB whereas BSA requires 14 dB. Also, at fewer BER values the required SNR value of the proposal is less than the other algorithms.

Finally comparing the performance of the algorithms for the system with 8 × 8 antennas in Fig. 4, we observe that our proposal provides better detection capability not only for few antennas but also for larger antenna arrays. From Fig. 4, it is seen that BSA algorithm needs more than 21 dB of SNR to have BER = 10−3 while PSO and GA need around 23.5 dB and 26 dB of SNR respectively to reach the BER = 10−3. As can be seen from all figures that our proposal offers large SNR improvements compared to other detectors.

Furthermore, to demonstrate the computational complexity benefits of BSA over the ML detector, we can analyze the computational complexity of the detectors in terms of number complex multiplication [19].

images

Figure 3: SNR versus BER performance of detectors for 4 × 4 NOMA system

images

Figure 4: SNR versus BER performance of detectors for 8 × 8 NOMA system

In the ZF algorithm, there are 4N3+2N2M multiplications due to the pseudo-inverse matrix calculation [19]. In that case, multiplications of the ZF algorithm are

ZFmult.=4N3+2N2M (16)

In the VBLAST algorithm, after the calculation of N times the pseudo-inverse matrix and interference canceling, the complexity can be written as

VBLASTmult.=∑i=0N(4i3+2Mi2)+∑i=0N−1[N(M−1)+2N] (17)

=N4+(52+23M)N3+(72+M)N2+13NM (18)

When we consider the ML algorithm, the number of multiplications required for matrix multiplication and squaring operations are,

MLmult.=M(N+1)CN (19)

Where C is constellation size, in heuristic algorithms, the number of multiplications required to calculate the fitness of each particle in the population are,

HEURISTICSmult.=NP(NM) (20)

After applying the population updating parameters (µ) and Nitr times repetition to convergence to an optimal value, the complexity becomes as

HEURISTICSmult.=NP(NM+μ)Nitr (21)

The complexity comparison analysis of the detectors can be found in terms of the number of multiplications in Tab. 4.

images

As can be seen from this computational complexity analysis, the number of transceiver antennas increases the computational load of each algorithm. However, this amount of load is even higher for the ML detector when the number of antennas increases. For instance, the complexity value of the ML algorithm is 3250 for a 2 × 2 antenna, while the number of antennas is as high as 309 billion in the case of 8 × 8. It can be seen from this analysis that the increase in the number of antennas and modulation index makes the algorithm less practical. Although the complexity of the ZF and VBLAST algorithms is low, their error performance is worse than the heuristic algorithms. Although the value of complexity in heuristic algorithms is similar, the number of iterations required for convergence has a direct effect on the complexity of these algorithms.

To reach optimal solutions for the 4 × 4 NOMA, 8 iterations in the BSA, 10 iterations in the PSO, and 11 iterations in the GA are needed. As a result, BSA, PSO, and GA need 1440, 1800, and 1980 multiplications respectively. Among heuristic algorithms, BSA has the lowest complexity.

Furthermore, BSA provides a 6.25% complexity reduction compared to the ML algorithm 2 × 2 systems. However, it significantly reduces the complexity by 99.59% and 99.9% in 4 × 4 and 8 × 8 systems.

5  Conclusion

In this study, the use of the BSA algorithm is proposed for data detection in the MIMO-NOMA systems which provide high-rate and quality of service. With this proposed algorithm, computational complexity is reduced in systems where the number of antennas and modulation constellation is large, and BER performance is increased compared to ML algorithm. As can be seen from the simulation results, the BSA algorithm has better values than the other heuristic algorithms in any case; also, it has a close performance to the ML algorithm. Besides, it is better than the classic algorithms such as ZF and VBLAST used for data detection, in terms of BER. So, we can say that the proposed algorithm can be used in a remarkable way for data detection in MIMO-NOMA systems.

Funding Statement: This work was supported by the Scientific Research Projects Coordination Unit of Bandirma Onyedi Eylül University. Project Number BAP-19-MF-1004-005.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

References

  1. Z. Ding, Y. Liu, J. Choi, Q. Sun, M. Elkashlan et al., “Application of non-orthogonal multiple access in LTE and 5G networks,” IEEE Communication Magazine, vol. 55, no. 2, pp. 185–191, 2017.
  2. Z. Ding, F. Adachi and H. V. Poor, “The application of MIMO to non-orthogonal multiple access,” IEEE Transaction on Wireless Communication, vol. 15, no. 1, pp. 537–552, 2016.
  3. Y. Liu, G. Pan, H. Zhang and M. Song, “On the capacity comparison between MIMO-NOMA and MIMO-OMA IEEE Access,” Special Selection on Green Communications and Networking for 5G Wireless, vol. 4, pp. 2123–2129, 2016.
  4. M. Rihan, L. Huang and P. Zhang, “Joint interference alignment and power allocation for NOMA-based multi-user MIMO systems,” EURASIP Journal on Wireless Communications and Networking, vol. 2018, no. 217, pp. 1–13, 2018.
  5. D. Zhang, Z. Zhou, C. Xu, Y. Zhang, J. Rodriguez et al., “Capacity analysis of non-orthogonal multiple access with mmWave massive MIMO systems,” IEEE Journal on Selected Areas in Communications, vol. 35, no. 7, pp. 1606–1618, 2017.
  6. Z. Ding, R. Schober and H. Poor, “A general MIMO framework for NOMA downlink and uplink transmission based on signal alignment,” IEEE Transactions on Wireless Communications, vol. 15, no. 6, pp. 4438–4454, 201
  7. A. Akbar, S. Jangsher and F. A. Bhatti, “NOMA and 5G emerging technologies: A survey on issues and solution techniques,” Computer Networks, vol. 190, no. 2021, pp. 1–40, 2021.
  8. J. Zhang, Y. Zhu, S. Ma, X. Li and K. K. Wong, “Large system analysis of downlink MISO-NOMA system via regularized zero-forcing precoding with imperfect CSIT,” IEEE Communications Letters, vol. 24, no. 11, pp. 2454–2458, 2020.
  9. S. Ozyurt, E. P. Simon and J. Farah, “NOMA with zero-forcing V-BLAST,” IEEE Communication Letters, vol. 24, no. 9, pp. 2070–2074, 2020.
  10. L. Xiao, P. Xiao, Z. Liu, W. Yu, H. Haas et al., “A compressive sensing assisted massive SM-VBLAST system: Error probability and capacity analysis,” IEEE Transactions on Wireless Communications, vol. 19, no. 3, pp. 1990–2005, 2020.
  11. X. Chen, M. Wen and S. Dang, “On the performance of cooperative OFDM-NOMA system with index modulation,” IEEE Communication Letters, vol. 9, no. 9, pp. 1346–1350, 2020.
  12. M. X. Chang and W. Y. Chang, “Maximum-likelihood detection for MIMO systems based on differential metrics,” IEEE Transactions on Signal Processing, vol. 65, no. 14, pp. 3718–3732, 2017.
  13. F. Fisher and C. Windpassinger, “Real versus complex-valued equalization in V-BLAST systems,” IET Electronic Letters, vol. 39, no. 5, pp. 470–471, 2003.
  14. T. H. Kim, “Low complexity sorted QR decomposition for MIMO systems based on pairwise column symmetrization,” IEEE Transactions on Wireless Communications, vol. 13, no. 3, pp. 1388–1396, 20
  15. B. Hassibi and H. Vikalo, “On the sphere-decoding algorithm I. expected complexity,” IEEE Transactions on Signal Processing, vol. 53, no. 8, pp. 2806–2818, 2005.
  16. M. M. Mansour, S. P. Alex and M. A. Jalloul, “Reduced complexity soft output MIMO sphere detectors-part II, architectural optimizations,” IEEE Transactions on Signal Processing, vol. 62, no. 21, pp. 5506–5520, 2014.
  17. L. Li, J. Wen, X. Tang and C. Tellambura, “Modified sphere decoding for sparse code multiple access,” IEEE Communication Letters, vol. 22, no. 8, pp. 1544–1547, 2018.
  18. S. Chen and Y. Wu, “Maximum likelihood channel and data estimation using genetic algorithms,” IEEE Transactions on Signal Processing, vol. 46, pp. 1469–1473, 1998.
  19. A. A. Khan, S. Bashir, M. Naeem, S. I. Shan and X. Li, “Symbol detection in spatial multiplexing system using particle swarm optimization meta-heuristics,” International Journal of Communication Systems, vol. 21, no. 12, pp. 1239–1257, 2008.
  20. H. Rehman, S. I. Shah, I. Zaka and J. Ahmad, “An MBER-BLAST algorithm for OFDM-SDMA communication using particle swarm optimization,” International Journal of Communication Systems, vol. 24, no. 2, pp. 185–201, 2011.
  21. M. N. Seyman and N. Taşpınar, “Symbol detection using differential evolution algorithm in MIMO-OFDM systems,” Turkish Journal of Electrical Engineering & Computer Sciences, vol. 21, no. 2, pp. 373–380, 2013.
  22. P. Civicioglu, “Backtracking search optimization algorithm for numerical optimization problems,” Applied Mathematics and Computation, vol. 219, no. 15, pp. 8121–8144, 2013.
  23. H. Wang, Z. Hu, Y. Sun, Q. Su and X. Xia, “Modified backtracking search optimization algorithm inspired by simulated annealing for constrained engineering optimization problems,” Computational Intelligence and Neuroscience, vol. 2018, no. 4, pp. 1–28, 2018.
  24. S. K. Agarwal, S. Shah and R. Kumar, “Classification of mental tasks from EEG data using backtracking search optimization based neural classifier,” Neurocomputing, vol. 166, pp. 397–403, 2015.
  25. C. Zhang, J. Zhou, C. Li, W. Fu and T. Peng, “A compound structure of ELM based on feature selection and parameter optimization using hybrid backtracking search algorithm for wind speed forecasting,” Energy Conversion and Management, vol. 143, no. c, pp. 360–376, 2017.
  26. S. Mallick, R. Kar, D. Mandal and S. P. Ghoshal, “CMOS analog amplifier circuits optimization using hybrid backtracking search algorithm with differential evolution,” Journal of Experimental and Theoretical Artificial Intelligence, vol. 28, no. 4, pp. 1–31, 2015.
  27. A. Askarzadeh and L. dos Santos Coelho, “A backtracking search algorithm combined with Burger’s chaotic map for parameter estimation of PEMFC electrochemical model,” International Journal of Hydrogen Energy, vol. 39, no. 21, pp. 11165–11174, 2014.
  28. S. N. A. Latif, J. Shi, H. A. Salman and Y. Tang, “Optimization of demand-response-based intelligent home energy management system with binary backtracking search algorithm,” Information-an International Interdisciplinary Journal, vol. 11, no. 8: 395, pp. 1–18, 2020.
  29. H. Zhang, S. Xiao and P. Zhou, “Matching pursuit algorithm for backtracking regularization based on energy sorting,” Symmetry, vol. 12, no. 2: 231, pp. 1–12, 2020.
  30. C. Ocak, I. Tarimer, A. Dalcali and D. Uygun, “Investigation effects of narrowing rotor pole embrace to efficiency and cogging torgue at PM BLDC motor,” TEM Journal, vol. 5, no. 1, pp. 25–31, 2016.
  31.  A. Bishnu and V. Bhatia, “On performance analysis of IEEE 802.22 (PHY) for COST-207 channel models,” in 2015 IEEE Conference on Standards for Communications and Networking (CSCNTokyo, Japan, pp. 229–234, 2015.
images This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.