# A Low Complexity Reactive Tabu Search Based Constellation Constraints in Signal Detection
## 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 increasednumber 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:  
1.