Open AccessArticle

A Low Complexity Reactive Tabu Search Based Constellation Constraints in Signal Detection

Jiao Feng

^1,2,*

Xiaofei Zhang

¹,

Peng Li

^1,2 and

Dongshun Hu

School of Electric and Information Engineering, Nanjing University of Information Science and Technology, 219 Ninliu Road, Nanjing 210044, China

Jiangsu Collaborative Innovation Center on Atmospheric Environment and Equipment Technology (CICAEET), Nanjing 210044, China

Author to whom correspondence should be addressed.

Algorithms 2018, 11(7), 99; https://doi.org/10.3390/a11070099

Submission received: 12 May 2018 / Revised: 13 June 2018 / Accepted: 28 June 2018 / Published: 3 July 2018

Download

Browse Figures

Versions Notes

Abstract

For Massive multiple-input multiple output (MIMO) systems, many algorithms have been proposed for detecting spatially multiplexed signals, such as reactive tabu search (RTS), minimum mean square error (MMSE), etc. As a heuristic neighborhood search algorithm, RTS is particularly suitable for signal detection in systems with large number of antennas. In this paper, we propose a strategy to reduce the neighborhood searching space of the traditional RTS algorithms. For this, we introduce a constellation constraints (CC) structure to determine whether including a candidate vector into the RTS searching neighborhood. By setting a pre-defined threshold on the symbol constellation, the Euclidean distance between the estimated signal and its nearest constellation points are calculated, and the threshold and distance are compared to separate the reliable estimated signal from unreliable ones. With this structure, the proposed CC-RTS algorithm may ignore a significant number of unnecessary candidates in the RTS neighborhood searching space and greatly reduce the computational complexity of the traditional RTS algorithm. Simulation results show that the BER performance of the proposed CC-RTS algorithm is very close to that of the traditional RTS algorithm, and with about 50% complexity reduction with the same signal-to-noise (SNR) ratio.

Keywords:

MIMO; maximum likelihood; RTS; CC; detection complexity

1. Introduction

The utilization of spatial multiplexed multiple-input multiple-output (MIMO) technology could linearly increase the link capacity of the communication systems without sacrificing spectrum and time resource [1,2]. A recent highlight for MIMO technologies is to consider massive number of receiving antennas at base stations and user equipments. In massive MIMO systems, the total number of antenna elements at user terminals are relatively small. This ensures satisfactory performance with simpler signal detection techniques. Massive MIMO is regarded as a core technology for the next generation mobile communication systems [1]. Harnessing such benefits of large-dimensions in practice, however, is challenging. In particular, with the increasing number of concurrent user data streams, detection complexity could become infeasible [3,4].

Several detection algorithms have been proposed in the literature to address the problem of detecting massive MIMO signal. It is well known that maximum likelihood (ML) [5] is the optimal algorithm for MIMO detection. The core of the ML algorithm is to calculate the respective ML cost for all trasmission combination candidates, and then find the one with the minimum cost. Theoretically, the algorithm provides optimal performance; however, with the increased number of antennas and modulation level, the computational complexity of the algorithm increases exponentially. For practical applications, the minimum mean square error algorithm [6] is usually low in computational complexity, but it may not obtain full diversity gain and has a performance worse than an ML detector. Sphere decoding (SD) [7] is an algorithm for searching a space of a multiple dimensional sphere which has a soft complexity may raise exponentially with the increased number of antennas. In addition, tabu search (TS) is a heuristic algorithm which is originally developed to obtain approximate solutions to combinatorial optimization problems [8]. Recently TS is increasingly being applied to communication problem [9,10,11,12]. In [9], a reactive tabu search to seek approximate ML solutions in large dimension is presented. In traditional RTS algorithm, the number of candidates involved in the calculation determines the complexity and the performance of the detection algorithm. However, in this work, we believe not all the candidates are required to perform the ML cost calculation, and many of the candidates can be excluded from the detection procedure and their performance impact on the detection results can be neglected.

The detection complexity of the RTS algorithm is associated with the number of candidates involved in calculating the ML cost for each candidate. A larger number of RTS candidates usually correspond to a higher complexity [13] for detection. Therefore, in this paper, inspired by [14,15], we propose a new scheme which may reducing the RTS complexity by decreasing the searching space of candidates with the help of their estimated reliability. A brief introduction of the proposed algorithm is summarised as follows: First, an initial solution vector is given, and the vector is usually given by an MMSE or ZF filter. Then, with the initial solutions, we separate the reliable decision candidates from the unreliable ones according to the proposed CC structure. Finally, we use the modified RTS algorithm for updating the unreliable candidates with the reliable decisions. The simulation results show that the proposed CC-RTS detection algorithm has a complexity about 50% lower than the traditional RTS with the same target SNR value.

With the help of reliability checking of the proposed CC structure, the RTS candidates with high reliability will be excluded from the neighborhood, and the number of candidates participating the following RTS procedures for evaluating the ML cost will be significantly reduced. Therefore the complexity of the overall detection algorithm is significantly reduced. The contribution of this paper is given as follows:

We propose a scheme, namely Constellation Constraints (CC) algorithm for determining the reliability of the initial vector.
With the proposed CC structure, the algorithm separate the reliable symbol estimates in the initial vector from unreliable symbols.
A algorithm is developed for generating a new candidate set and neighborhood searching space and their implementation with RTS detection.
The simulation results of the proposed scheme are given to verify that similar BER performance can be achieved with significant lower computational complexity.

The rest of this paper is organized as follows. The system model is introduced in Section 2, while the proposed algorithm in the massive MIMO configuration is described in Section 3. In Section 4, the attainable performance of our scheme is verified. Finally, the conclusion is given in Section 5.

2. System Model

The system model we considered in this paper can be expressed as the following

r = H s + n,

(1)

where

r = {[r_{1}, r_{2}, \dots, r_{N_{r}}]}^{T}

is an

N_{r} \times 1

received signal vector, and

r_{j}

represents the received signal at the jth received antenna. Vector

s

{[s_{1}, s_{2}, \dots, s_{N_{t}}]}^{T}

is the

N_{t} \times 1

transmitted signal vector, and

s_{i} \in A

represents the transmitted signal at the

i_{t h}

transmitting antenna. The signal is modulated by quadrature phase shift keying (QPSK) modulation, and

A

can be expressed as a constellation set of

A = \frac{1}{\sqrt{2}} {- 1 - j, - 1 + j, 1 - j, 1 + j}

. Noise

n

is a

N_{t} \times 1

vector that obeys Gaussian distribution with the mean value of 0 and variance

σ^{2}

. In addition, the matrix

H

is with the size of

N_{r} \times N_{t}

and its elements follow Rayleigh distribution.

3. CC-RTS Algorithm

Maximum Likelihood (ML): Maximum likelihood detection algorithm calculates the Euclidean distance between the received signal vector and the product of all possible transmitted signal vectors multiplied by channel H and searching for the one with the minimum distance. Let

A

denote the whole ML search space with a number of combination candidates which increases exponentially with a raising number of spatial multiplexed transmit antennas modulation level. ML algorithm determines the estimated transmitted signal vector

\hat{s}

as:

{\hat{s}}_{M L} = \underset{\hat{s} \in A^{N_{t}}}{arg min} | | r - H \hat{s} {| |}^{2}

(2)

where

| | r - H \hat{s} {| |}^{2}

corresponds to the ML metric of the candidate

\hat{s}

Traditional RTS Algorithm: The implementation of RTS algorithm in massive MIMO [10,11,12] is introduced in the following. With sufficient number of receiving antennas, the RTS algorithm has a performance closes to the ML algorithm, but with significant lower detection complexity. This algorithm use the MMSE output as the initial solution vector, and find the neighborhood candidates of the initial solution vector; Then, the algorithm computes the respective ML cost with these candidates and searching for the one with the minimum cost. If it is the case that the selected candidate does not appear in the tabu list (Tabu list is used to hold the initial solution of the next iterative process. The elements in the list follow first in first out FIFO rules. The tabu length indicates that the element will not be used again as the initial solution vector in the next few iterations. The length of tabu is divided into variable and immutable. If the tabu length is fixed, then the algorithm is called fixed tabu search. If the length is a variable, then the algorithm is termed reactive tabu search), the selected candidate is used as the initial value for the next iteration of searching, meanwhile the algorithm includes this selected candidate into the tabu list; On the other hand, if the candidate is already included in the tabu list, a suboptimal solution outside the tabu list is selected as the initial value for the next iteration of searching, and the suboptimal solution is added to the tabu list. After several iterations, the candidate with the minimum ML cost can be selected as the final output of the RTS algorithm.

RTS neighborhood: The selection criteria of neighborhood candidates in [9] is the metric of Euclidean distance, that is, to find the nearest constellation candidates from a given point. For example: If we use

\hat{s}

to indicate a transmitting signal symbol, and

Neb (\hat{s})

denotes the neighborhood candidates of

\hat{s}

. For QPSK modulation, if we consider a

2 \times 2

MIMO model and the initial value is considered to be

{\hat{s}}_{i} = \frac{1}{\sqrt{2}} {- 1 - j}

, the number of candidates for

{\hat{s}}_{i}

is 2, by finding the nearest two candidates, we have

Neb ({\hat{s}}_{i}) = \frac{1}{\sqrt{2}} {- 1 + j, 1 - j}

For the RTS algorithm, the most expensive step is to find the nearest constellation candidates by measuring Euclidean distance and calculate their respective ML costs [14,15,16,17]. Table 1 shows the number of nearest candidates in different modulation modes. With the increased number of antennas, the number of candidates for the RTS algorithm is raising. The main contribution of the proposed algorithm is to reduce the computational complexity of the conventional RTS by shorten the candidates list. In below, we will introduce in detail of the proposed CC algorithm, and how the CC algorithm can be used for reducing the number of candidates in each iteration of searching.

CC-RTS: The inspiration to use a CC device to improve traditional RTS algorithm in this paper comes from our previous work [14,15,16,17]. With the analysis of MMSE filter, theoretical research shows that the estimated symbols gradually converge with an increasing value of signal-to-noise ratio. For each transmission, the distance between an estimated symbol and its nearest constellation point can be regarded as an measurement of the reliability of the estimates. For the RTS algorithm, in this work, the proposed CC algorithm [17] is used to reduce the computational complexity for traditional reactive tabu search and the algorithm may prevent the search space from growing exponentially with the increased number of transimitting antennas. In [14,15,16,17], an estimation reliability measuring and refining strategy (CC algorithm) is used to detect MIMO signal with nonlinear decision feedback systems. Inspired by its principle of determining reliability, in this paper, we have modified the CC algorithm to improve heuristic neighborhood search algorithms, such as traditional RTS algorithm. A simplification of the proposed CC structure is shown in Figure 1. The parameters marked in the figure are given as follows,

σ_{s}

refers to the signal power, and the threshold

d_{t h}

represents the device radius which can control the shaded area. It can be designed as a constant, or a joint function of the signal power

σ_{s}

and the noise power

σ_{n}

. The value d represents the distance between the detection signal and its nearest constellation point. The following equation is given to determine the nearest constellation point for a given signal

{\hat{s}}_{i}

a_{i} = \underset{a_{c} \in A}{arg min} | {\hat{s}}_{i} - a_{c} |

(3)

where

a_{c}

represents the selected element of the constellation.

From Figure 1, we can see that the constellation space is divided into shaded areas and bright areas, we stipulate that if the candidate falls in the shaded area, we determine that this candidate is unreliable. The signal falling in the shadow area to meet the following condition.

| ℑ {{\hat{s}}_{i}} | \leq \frac{σ_{s}}{2} - d_{t h}, when | ℜ {{\hat{s}}_{i}} | \geq \frac{σ_{s}}{2}

(4)

d \geq d_{t h}, | ℑ {{\hat{s}}_{i}} | \leq \frac{σ_{s}}{2}, when \frac{σ_{s}}{2} - d_{t h} \leq | ℜ {{\hat{s}}_{i}} | \leq \frac{σ_{s}}{2}

(5)

| ℑ {{\hat{s}}_{i}} | \in R, when | ℜ {{\hat{s}}_{i}} | \leq \frac{σ_{s}}{2} - d_{t h}

(6)

If the signal to be detected satisfies the above conditions, the algorithm considers the candidate as unreliable. On the other hand, if the detection signal does not satisfy above conditions, the algorithm considers the candidate as reliable. If it is the case that the proposed CC structure considers the candidate as unreliable, it introduces more candidates as the output for test; While CC structure considers the candidate is reliable, the quantization of the candidate is performed at the output. The detected signals can be MMSE soft output or Zero Force soft output.

Reliable: The reliable condition is defined as that if the signal to be detected falls into the bright area of the graph. For instance if $\hat{s}$ is the initial value of RTS, and the soft output ${\hat{s}}_{i}$ falls into the bright area of graph, a hard decision is considered to determine the output ${\hat{s}}_{i}$ of the nearest constellation and, then we neither consider generating candidates nor conduct RTS algorithm for this soft output. A quantization operation $k (■)$ is then performed as

${\hat{s}}_{i} = k ({\hat{s}}_{i})$

(7)
Unreliable: The unreliable condition is that the detection signal falls into the shaded area of the graph. If $\hat{s}$ is the initial value of RTS, and the soft output ${\hat{s}}_{i}$ falls into the shaded area of the graph, we conduct hard decision for ${\hat{s}}_{i}$ and generate candidates of $k ({\hat{s}}_{i})$ for the RTS algorithm. The CC processing is invoked and a candidates set is generated as

$Neb ({\hat{s}}_{i}) = [c_{1}, c_{2}, \dots, c_{m}, \dots, c_{M}] ϵ A$

(8)

The generated candidates are constrained by the constellation map and the candidate set is a selection of the M nearest constellation points to ${\hat{s}}_{i}$ . The size of $Neb ({\hat{s}}_{i})$ can be either fixed or adaptive with the channel condition which introduces a tradeoff between the performance and the detection complexity with a selection algorithm.

The pseudo code of the proposed CC-RTS algorithm is given in Table 2. In

Initialization

, we not only consider the hard output of MMSE but also include the soft output, generating the initial value of RTS algorithm; In

Constellation Constraints

, we define a vector

sit

. Through the distribution of

sit

, we divide the signals into reliable signals and unreliable signals. In

CC - RTS

, for the distribution of the

sit

, we only look for candidates of the initial value of

sit

is 1, and then execute RTS algorithm for these elements. This reduces the number of candidates in the traditional RTS algorithm, thereby reducing the complexity of the traditional RTS algorithm.

4. Simulation Results

In this part, we will shown the advantages of CC-RTS algorithm in terms of computational complexity and BER performance. The algorithm may approach the original RTS algorithm in terms of BER performance with various MIMO configurations. Meanwhile the proposed algorithm may significantly reduce the detection complexity of the traditional RTS algorithm for massive MIMO systems. To evaluate the achievable performance of the proposed scheme, we present our results based on MATLAB simulations. We set up a simulation model with the following parameters: the system is a MIMO using QPSK modulation with

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO antennas. We assume that the transmitted signal encounters independent Rayleigh Fading in the propagation channels. The transmitted

\hat{s}

are grouped into frames consisting of 100,000 symbol vectors, and 100,000 Monte Carlo simulation is carried to produce the results. In addition, the following RTS parameters are also used in the simulations: MMSE initial vector, initial tabu length is 3, and Iterations is 20. These parameters are shown in Table 3.

Performance: In Figure 2 and Figure 3, we present the simulated BER performance of the proposed CC-RTS algorithm with various selection of

d_{t h}

with Rayleigh channel. Figure 2 shows that the variation of BER as a function of the

d_{t h}

, with

N_{t}

N_{r}

= 4, 8, 16, 24, respectively, and all the simulations are with SNR = 8dB. It can be observed from Figure 2 that, depending on the choice of the value of

d_{t h}

, BER and

d_{t h}

rendering correlation. Figure 3 shows the performances of the proposed CC-RTS and reference RTS, with

N_{t}

N_{r}

= 4, 8, 16, 24, and

d_{t h}

=0.02. It can be seen that the proposed CC-RTS has a performance close to the traditional RTS algorithm.

Besides, in the case that the channel is time-varying, we also make a model simulation. The channel model adopted is Doppler Frequency Shift, and the value of

d_{t h}

is 0.02. In this simulation process, we used rayleighchan MATLAB build in function to generate channel with Doppler Frequency Shift. The sampling frequency shift was 1/15,000 and the maximum Doppler Frequency Shift is 500. The performance of the proposed CC-RTS and reference RTS with Channel with Doppler Frequency Shift is shown in Figure 4. From Figure 4, we can get a conclusion that: With Doppler Frequency Shift, CC-RTS algorithm also have the advantages of greatly reducing the computational complexity of RTS algorithm without affecting the performance of the traditional RTS algorithm, although the bit error rate is slightly different.

Complexity: In order to further verify the proposed algorithm, we exam the complexity reduction over the traditional RTS algorithm. The complexity analysis is based on the assumption that the radius of the CC device is given by 0.02. We can see from Figure 5 that with the proposed scheme, more than half number of the candidates are excluded under different antenna configurations compare to the traditional RTS algorithm. For same number of antennas, with an increasing value of SNR, the number of candidates is gradually reduced and the subsequently calculation of ML cost and overall detection complexity can be saved. In addition, from Figure 6 and Table 4, we can see that for a given target BER performance, such as

10^{- 2}

, the per-symbol-complexity (PSC) of the CC-RTS algorithm is smaller than that of the traditional RTS algorithm. The following is a detailed derivation of the mathematical expression of PSC:

It is known that the most expensive part of the RTS algorithm is to calculate the Euclidean distance. For the

N_{t} * N_{r}

MIMO models,

N_{t} * N_{r}

multiplication and

N_{t} * N_{r}

addition are needed in this process. If the number of iterations is

I t e m

, each symbol’s neighbor is M, then the computational complexity of each symbol in the RTS algorithm is

\frac{I t e m * M * N_{t} * (2 * N_{t} * N_{r} - 1)}{N_{t}}

. As an improvement of RTS algorithm, CC-RTS algorithm could significantly reduce the number of search candidates without reducing the ML cost of each set of candidates. Therefore, the computational complexity of CC-RTS algorithm and RTS algorithm on a vector is consistent, but the overall computational complexity of CC-RTS algorithm is smaller than that of RTS algorithm.

5. Conclusions

In this work, we propose an improved RTS algorithm based on constellation generated candidates for massive MIMO systems. By using the Euclidean distance metric, the proposed algorithm separates the unreliable estimates from the reliable ones and generate new tabu search lists. With this algorithm, a significant number of candidates can be reduced and the detection complexity is further reduced. The simulation results indicate that the proposed scheme has helped to achieve significant reduction in detection complexity of traditional RTS algorithm.

Author Contributions

J.F. designed the signal model and edited the paper; X.Z. was responsible for designing and simulating the signal detection algorithm and writing the paper; P.L. supervised the paperwork and comments; D.H. provided writing advice.

Funding

This work has been supported by National Natural Science Foundation of China (grant number 61501244), (grant number 61501245); Natural Science Foundation of Jiangsu Province (grant number BK20150932). Priority Academic Program Development of Jiangsu Higher Education Institutions, Innovation and Entrepreneurship Doctoral Program of Jiangsu, Startup Foundation for Introducing Talent of Nanjing University of Information Science & Technology.

Conflicts of Interest

The authors declare no conflict of interest.

References

Telatar, I.E. Capacity of multi-antenna Gaussian channels. Eur. Trans. Telecommun. 1999, 10, 585–595. [Google Scholar] [CrossRef]
Paulraj, A.; Nabar, R.; Gore, D. Introduction to Space-Time Wireless Communications; Cambridge University Press: Cambridge, UK, 2003. [Google Scholar]
Lu, L.; Li, G.; Swindlehurst, A.; Ashikhmin, A.; Zhang, R. An Overview of Massive MIMO: Benefits and Challenges. IEEE J. 2014, 8, 742–758. [Google Scholar] [CrossRef]
Wu, M.; Yin, B.; Wang, G.; Dick, C.; Cavallaro, J.; Studer, C. Large-Scale MIMO Detection for 3GPP LTE: Algorithms and FPGA Implementations. IEEE J. 2014, 8, 916–929. [Google Scholar] [CrossRef] [Green Version]
Noh, H.; Myoungseok, K.; Jaesang, H.; Chungyong, L. A practical MMSE-ML detector for a MIMO SC-FDMA system. IEEE Commun. Lett. 2009, 13, 902–904. [Google Scholar] [CrossRef]
Tran, X.N.; Le, A.T.; Fujino, T. Performance comparison of MMSE-SIC and MMSE-ML multiuser detectors in a STBC-OFDM system. In Proceedings of the IEEE 16th International Symposium on Personal, Indoor and Mobile Radio Communications, Berlin, Germany, 11–14 September 2005; pp. 1050–1054. [Google Scholar]
Guo, Z.; Nilsson, P. Algorithm and Implementation of the K-Best Sphere Decoding for MIMO Detection. IEEE J. 2006, 24, 491–503. [Google Scholar]
Glover, F. Tabu Search-Part I. ORSA J. Comput. 1989, 1, 190–206. [Google Scholar] [CrossRef]
Rajan, B.; Mohammed, S.; Chockalingam, A.; Srinidhi, N. Low complexity near-ML decoding of large non-orthogonal STBCs using reactive tabu search. In Proceedings of the IEEE International Symposium on Information Theory, Seoul, Korea, 28 June–3 July 2009; pp. 1993–1997. [Google Scholar]
Chockalingam, A. Low-complexity algorithms for large-MIMO detection. In Proceedings of the 4th International Symposium on Communications, Control and Signal Processing (ISCCSP), Limassol, Cyprus, 3–5 March 2010; pp. 1–6. [Google Scholar]
Datta, T.; Srinidhi, N.; Chockalingam, A.; Rajan, B.S. Random Restart Reactive Tabu Search Algorithm for Detection in Large-MIMO Systems. IEEE Commun. Lett. 2010, 14, 1107–1109. [Google Scholar] [CrossRef]
Srinidhi, N.; Datta, T.; Chockalingam, A.; Rajan, B. Layered Tabu Search Algorithm for Large-MIMO Detection and a Lower Bound on ML Performance. IEEE Trans. Commun. 2011, 59, 2955–2963. [Google Scholar] [CrossRef] [Green Version]
Sah, A.K.; Chaturvedi, A.K. Reduced neighborhood search algorithms for low complexity detection in MIMO systems. In Proceedings of the IEEE Global Communications Conference (GLOBECOM), San Diego, CA, USA, 6–10 December 2015; pp. 1–6. [Google Scholar]
Li, P.; Rodrigo, C.; De, L. Adaptive Decision Feedback Detection with Constellation Constraints for MIMO Systems. IEEE Trans. 2012, 61, 853–859. [Google Scholar] [CrossRef]
Li, P.; Rodrigo, C.; De, L.; Fa, R. Multiple Feedback Successive Interference Cancellation Detection for Multiuser MIMO Systems. IEEE Trans. 2011, 10, 2434–2439. [Google Scholar]
Li, P.; Rodrigo, C.; De, L. Distributed Iterative Detection with Reduced Message Passing for Networked MIMO Cellular Systems. IEEE Trans. 2014, 63, 2947–2954. [Google Scholar] [CrossRef]
Li, P.; Rodrigo, C.; De, L.; Liu, J. Adaptive decision feedback detection with parallel interference cancellation and constellation constraints for multiuser multi-input-multi-output systems. IET Commun. 2013, 7, 538–547. [Google Scholar] [CrossRef]

Figure 1. Constellation constraints structure.

a_{i}

is the coordinate point on the constellation. Shaded areas is unreliable area, and bright areas is reliable area. Value

d_{t h}

is the CC radius and d denotes the distance between the estimated symbol and its nearest constellation.

Figure 1. Constellation constraints structure.

a_{i}

is the coordinate point on the constellation. Shaded areas is unreliable area, and bright areas is reliable area. Value

d_{t h}

is the CC radius and d denotes the distance between the estimated symbol and its nearest constellation.

Figure 2. Bit error rate performance of different

d_{t h}

for

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO systems with QPSK modulation. (The dashed line indicates the performance of the reference traditional RTS.)

Figure 2. Bit error rate performance of different

d_{t h}

for

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO systems with QPSK modulation. (The dashed line indicates the performance of the reference traditional RTS.)

Figure 3. Bit error rate performance of CC-RTS taking MMSE solution as the initial vector for

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO system with Rayleigh channel , QPSK modulation,

d_{t h}

= 0.02.

Figure 3. Bit error rate performance of CC-RTS taking MMSE solution as the initial vector for

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO system with Rayleigh channel , QPSK modulation,

d_{t h}

= 0.02.

Figure 4. Bit error performance of CC-RTS taking MMSE solution as the initial vector for

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO system with Channel with Doppler Frequency Shift, QPSK modulation,

d_{t h}

= 0.02.

Figure 4. Bit error performance of CC-RTS taking MMSE solution as the initial vector for

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO system with Channel with Doppler Frequency Shift, QPSK modulation,

d_{t h}

= 0.02.

Figure 5. Candidates reduction: percentage of candidates over traditional RTS algorithm for

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO systems with QPSK modulation,

d_{t h}

= 0.02. With the proposed scheme, 50% of the candidates and their corresponding complexity of ML calculation can be saved.

Figure 5. Candidates reduction: percentage of candidates over traditional RTS algorithm for

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO systems with QPSK modulation,

d_{t h}

= 0.02. With the proposed scheme, 50% of the candidates and their corresponding complexity of ML calculation can be saved.

Figure 6. Per-symbol-complexity (PSC) in number of real operations and SNR required to achieve

10^{- 2}

BER in QPSK for

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO system (Ref: Figure 5 ).

Figure 6. Per-symbol-complexity (PSC) in number of real operations and SNR required to achieve

10^{- 2}

BER in QPSK for

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO system (Ref: Figure 5 ).

Table 1. The number of nearest neighbors for different modulation modes: BSPK, QPSK, 16-QAM, 64-QAM.

Modulation Mode	BPSK	QPSK	16-QAM	64-QAM
Neighbors	$N_{t}$	2 $N_{t}$	4 $N_{t}$	4 $N_{t}$

Table 2. The proposed CC-RTS algorithm.

Input: $r$ , $H$ , $d_{t h}$

Output: ${\hat{s}}_{b e s t}$

Initialization:

{\hat{s}}_{s o f t} \leftarrow

the output of MMSE

\hat{s} \leftarrow

corresponding hard decision of

{\hat{s}}_{s o f t}

s_{s t e m p} \leftarrow \hat{s}

I t e m

← Number of iterations

Best-so-far

\leftarrow | | r - H s_{s t e m p} {| |}^{2}

P ← the length of tabulist

Constellation Constraints:

for

i \leftarrow

1 to

N_{t}

j \leftarrow i_{t h}

element of

{\hat{s}}_{s o f t}

if j is unreliable

{sit}_{i} \leftarrow 1

else

{sit}_{i} \leftarrow 0

end if

end for

CC-RTS:

it = 1

while it ≤

I t e m

cat - matrix \leftarrow []

generate tabulist according to P

for

k \leftarrow

1 to

N_{t}

{sit}_{k} = = 1

cat \leftarrow

the candidates of

k_{t h}

element of

s_{t e m p}

cat - matrix \leftarrow [cat - matrix; cat]

end if

end for

Using simplified

cat - matrix

to perform traditional RTS algorithm

it = it+1

end while

Table 3. Simulation parameters.

Modulation	Channels	Symbol Vectors	Initial Tabu Length	Iterations
QPSK	Rayleigh Fading Channel	100,000	3	20

Table 4. Per-symbol-complexity (PSC) in number of real operations and SNR required to achieve BER =

10^{- 2}

with QPSK for

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO systems (Ref: Figure 5 ).

Table 4. Per-symbol-complexity (PSC) in number of real operations and SNR required to achieve BER =

10^{- 2}

with QPSK for

4 \times 4

8 \times 8

16 \times 16

24 \times 24

MIMO systems (Ref: Figure 5 ).

Algorithm	Per-Symbol-Complexity in Number of Real Operations and SNR Required to Achieved $10^{- 2}$ BER for QPSK								The Computational Complexity of Each Symbol
	4 × 4		8 × 8		16 × 16		24 × 24
	PSC	SNR	PSC	SNR	PSC	SNR	PSC	SNR
RTS	1320	8.3	2600	7.1	20,520	6	46120	5.8	O(M) + O( $N_{t}^{2}$ )
CC-RTS	573	8.2	1148	7.1	9168	6	20662	5.8	O(M) + O( $N_{t}^{2}$ )

© 2018 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Feng, J.; Zhang, X.; Li, P.; Hu, D. A Low Complexity Reactive Tabu Search Based Constellation Constraints in Signal Detection. Algorithms 2018, 11, 99. https://doi.org/10.3390/a11070099

AMA Style

Feng J, Zhang X, Li P, Hu D. A Low Complexity Reactive Tabu Search Based Constellation Constraints in Signal Detection. Algorithms. 2018; 11(7):99. https://doi.org/10.3390/a11070099

Chicago/Turabian Style

Feng, Jiao, Xiaofei Zhang, Peng Li, and Dongshun Hu. 2018. "A Low Complexity Reactive Tabu Search Based Constellation Constraints in Signal Detection" Algorithms 11, no. 7: 99. https://doi.org/10.3390/a11070099

APA Style

Feng, J., Zhang, X., Li, P., & Hu, D. (2018). A Low Complexity Reactive Tabu Search Based Constellation Constraints in Signal Detection. Algorithms, 11(7), 99. https://doi.org/10.3390/a11070099

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

A Low Complexity Reactive Tabu Search Based Constellation Constraints in Signal Detection

Abstract

1. Introduction

2. System Model

3. CC-RTS Algorithm

4. Simulation Results

5. Conclusions

Author Contributions

Funding

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI